Laws of 2-element Boolean algebra.

1. Commutative law:

a˅ b=b ˅ a; a ˄ b = b˄ a

2. Associative law:

(a˅ b) ˅ c = a ˅ (b ˅ c); (a˄ b) ˄ c = a˄ (b˄ c)

3. Distributive law:

a ˅ b ˄ c=(a ˅ b) ˄ (a ˅ c); a˄ (b ˅ c)=a˄ b˅ a˄ c

4. Law for constants:

a ˅ 0 =a; a ˅ 1=1;

a˄ 0 = 0; a˄ 1 = a

5. Idempotent laws:

a ˅ a = a; a ˄ a = a:

6. Negation laws:

a ˅ ā =1; (excluded middle) a ˄ ā = Ø:

7. De Morgan’s laws:

a Ú b=a ˄ b; a ˄ b = a Ú b;

8. a = a; (Double negation law)

H/a: prove laws3 and 7 by building truth tables.

Equivalent transformations of formulas of 2-valued Boolean algebra.

F(x, y, z, v)= () ˄ () =

= () ˄ ( ˄ ˄ ) = (De Morgan’s)

=(x ˄ y ˄ z) ˅ ( ˄ y ˄ z) = (double negation)

=(x ˄ ˄ y˄ z) ˅ (y˄ ˄ y˄ z) ˅ () = (distributive, idempotent, excluded middle)

= ( ˄ y˄ z)˅ ( ˄ y ˄ ) =(x˄ y)˄ (z˅ ) = x ˄ y;

Building a truth table by the formulae of 2-element Boolean functions:

Given: f(x, y, z)=

Set#	x	y	z	f(x, y, z)=
				= = 1
				= = 1
				= = 1
				= 1
				= = 1
				= 1

Building a formula by a truth table. A method based on 1-values of a Boolean function. Given: a 2-values Boolean function:

	x	y	z	f(x, y, z)
				only for x=0, y=0, z=1 nly for x=0, y=1, z=1 nly for x=1, y=0, z=0     0

f(x, y, z) = ˅ ˅ = ˅ ˅ .

This formula takes value 1 only for such sets of variable values:

x=0, y=0, z=1

x=0, y=1, z=1

x=0, y=0, z=0.

On other sets x, y, z – values (on other interpretations) this function is equal to 0.

Definition: A formula of a Boolean function which is a disjunction of its minterms is called its Perfect Disjunctive Normal Form (PDNF). In technical papers such a formula is called a Complete Sum of Products Form(CSPF).

We can pass from a table to a formula based on 0- values of the Boolean function.

x˅ y ˅ z. This formula =0 only for x=0, y=0, z=0. On other sets of x, y, z – values if it =1. It is called a maxterm(=disjunction of all variables). x˅ ˅ .. This is maxterm=0 only for x=0, y=1, z=1. ˅ ˅ z. This is maxterm=0 only for x=1, y=1, z=0.

f1(x, y, z) = (x˅ y˅ z) ˄ (x˅ ˅ ) ˄ ( ˅ ˅ z) = (x˅ y˅ z)(x˅ ˅ )( ˅ ˅ z).

Now let x=0, y=1, z=1.

f₁(x, y, z) = (x˅ y˅ z)(x˅ ˅ )( ˅ ˅ z)= 0

1 0 0

Let x=0, y=1, z=0

f₁(x, y, z = (x˅ y˅ z)(x˅ ˅ )( ˅ ˅ z) = 1

Such a formula which is a conjunction of maxterms is called the Perfect Conjunctive Normal Form(PCNF) or more frequenly Complete Product-of-Sums Form(CPSF).