Boolean Algebra

Boolean Algebra •Binary Values •Axiomatic Definition •Two Valued Boolean Algebra •Basic Theorems And Postulates

Binary Values Two discrete signal levels can be represented by binary digits 1 and 0 respectively. This Binary digit is referred to as a Bit. These two levels can also be referred as TRUE And FALSE ON And OFF

Boolean Algebra Boolean Algebra is an algebraic structure defined by a set of S, together with the two binary operators, + and •, provided that the following postulates are satisfied: 1(a).Closure with respect to the operator +. 1(b).Closure with respect to the operator • .

2(a). An identity element with respect to + x+0=0+x=x (b) An identity element with respect to • x•1=1•x=x 3(a) Commutative w.r.t the operator +. x+y=y+x 3(b) Commutative w.r.t the operator •. x•y=y•x

4(a) • is distributive over +. x• (y + z) = (x • y) + (x • z) 4(b) + is distributive over •. x+ (y • z) = (x + y) • (x+ z) 5. For every element x∈S there exists an inverse element(called complement , x`∈S) such that x + x` = 1 x x` = 0 6. There exists at least two elements x ,y ∈S Such that x ≠ y.

Two Valued Boolean Algebra S = { 0, 1} 1. Closure 2. Identity Element 3. The commutative Law 4. Distributive Law 5. Inverse Element 6. Distinct Elements 0 , 1 ∈ S , and 0 ≠ 1.

X 0 0

Y 0 1

X + Y X .Y 0 0 1 0

1

0

1

0

1

1

1

1

Duality It states that every algebraic expression deducible from the Postulates of Boolean Algebra remains valid if the operator and identity elements are interchanged. Ex : x + 0 = x x.1= x

x . x` = 0 x + x` = 1

Basic Rules of Boolean Algebra 1. A + 0 = A

7. A • A = A

2. A + 1 = 1

8. A • A` = 0

3. A • 0 = 0

9. (A`)` = A

4. A • 1 = A

10. A + AB = A

5. A + A = A

11. A + A`B = A + B

6. A + A` = 1

12.A + BC = (A+B)(A+C)

Basic Theorems And Postulates Postulates Postulate 2(a) x + 0 = x 2(b) x . 1 = x

Postulate 3(a) x + y = y + x 3(b) xy = yx

Postulate 4(a) x(y + z) = xy + xz 4(b) x + yz = (x+y)(x+z)

Postulate 5(a) x + x` = 1 5(b) x . x` = 0

Theorems Theorem 1(a) x + x = x 1(b) x . x = x Theorem 2(a) x + 1 = 1 1(b) x . 0 = 0 Theorem 3 (x`)`= x

Theorem 4(a) x +(y + z) = (x + y) + z 4(b) x(yz) = (xy)z Theorem DeMorgan 5(a) (x + y)` = x`y` 5(b) (xy)` = x`+ y` Theorem6 Absorption 6(a) x + xy = x 6(b) x(x + y) = x

The complement of a sum of variables is equal to the product of the complements of the variables. (A + B + C + • • • + N)` = A`B`C`• • • N` The complement of a product of variables is equal to the sum of the complements of the variables. (A B C • • • N)` = A` + B` + C`• • • + N`

The generalized form of DeMorgan’s Theorem states that the complement of a function is obtained by interchanging AND and OR operators and complementing each literal.

Theorem 1(a).

x+x =x

x + x = (x + x) . 1

by postulate 2(b)

= (x + x)(x + x`)

5(a)

= x + xx`

4(b)

=x+0

5(b)

x+x=x

2(a)

Theorem 6(a). x + xy = x.1 + xy

x + xy = x by postulate 2(b)

= x(1 + y)

4(a)

= x(y + 1)

3(a)

= x .1

2(a)

x + xy = x

2(b)

Boolean Functions F = x + y`z Truth Table

n  Number of variable in the function 2n  Number of rows in the truth table F can have 8 values

F = x + y`z X 0 0 0 0 1 1 1 1

Y 0 0 1 1 0 0 1 1

Z 0 1 0 1 0 1 0 1

F1 0 1 0 0 1 1 1 1

F2 0 1 0 1 1 1 0 0

F1 = x + y`z x

y z

F1

y`z

F2 = x`y`z +x`yz + xy` x y F2

z

F2 = x`y`z +x`yz + xy` F2 = x`z(y`+y) + xy` F = xy` +x`z

F2 = xy` + x`z

Simplify the Boolean expression AB + A(B+C) + B(B+C)

Complement of the Function F is the function F` is its complement F=A+B+C F` = (A + B + C)` = (A + D) [Substitute B + C= D] = A`D` = A`(B + C)` = A`B`C` (A + B + C) = A`B`C`

Canonical And Standard Forms •Sum-of-Products (SOP) •Product- of- sums (POS) Consider two binary variables x and y Combined with an AND operation. x y , x`y , x y`, x`y` x  unprimed

Minterms X 0 0 0 0 1 1 1 1

Y 0 0 1 1 0 0 1 1

Z 0 1 0 1 0 1 0 1

Term x`y`z` x`y`z x`y z` x`y z x y`z` x y` z x y z` xyz

Designation m0 m1 m2 m3 m4 m5 m6 m7

X 0 0 0 0 1 1 1 1

Y 0 0 1 1 0 0 1 1

Z 0 1 0 1 0 1 0 1

F1 0 1 0 0 1 0 0 1

F2 0 0 0 1 0 1 1 1

F1 = x`y`z + x y`z` + xyz F1 = m1 + m4 + m7 F1 = Σ(1, 4, 7) F2 = x`y z + x y`z + xyz`+ xyz F2 = m3 + m5 + m6 + m7 F2 = Σ(3, 5, 6, 7)

Maxterms X Y 0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

Z

Term

Designation

0 1 0 1 0 1 0 1

x + y +z x +y +z` x +y`+ z x+y`+ z` x`+ y + z x`+ y+ z` x`+ y`+ z x`+ y`+ z`

M0 M1 M2 M3 M4 M5 M6 M7

F1 = (x+y+z)(x+y`+z)(x+y`+z`)(x`+y+z`) (x`+y`+z) F1 = M0.M2.M3.M5.M6 F1(x y z) = Π(0,2,3, 5, 6) F2 = M0.M1.M2.M4 F2 =Π(0, 1, 2, 4)

Sum Of Products (SOP)

F1 = y` + xy +x`yz`

Product Of Sums (POS)

F2 = x(y` + z)(x` + y + z`)

1.Convert the following expression into SOP and POS. (AB + C)(B + C`D) 2.Express the following function in sum of minterms and product of maxterms F(A,B,C,D) = B`D + A`D + BD

Levels of Integration •Small Scale Integration SSI •Medium Scale Integration MSI •Large Scale Integration LSI •Very Large Scale Integration VLSI

Prove 1. x + yz = (x + y)( x + z) F = x + yz , then show that FF` = 0 F + F` = 1. Simplify 2. xy +x(wz + wz`) 3. A`B(D` + C`D) +B(A + A`CD)