Boolean Algebra logic and De Morgan theorem

Boolean algebra

1. Boolean Algebra By, Neethu Anna Issac Assistant Professor ECE department KCG College of Technology

2. Introduction

3. Boolean Algebra Terminology 1) Variable Symbol which represent an arbitrary element of Boolean algebra Eg : Y = A.B + C.D Here, Variables – A,B,C,D (value can be 0 or 1) Function – Y (value 0 or 1 depends on expression AB + CD) 2) Constant It’s value is fixed Y = A.B + 1 Here, 1 is a constant

4. Boolean Algebra Terminology ( cntd .) 3) Complement Inverse of a variable or symbol Represented by a ‘bar’ ( ‾ )or ‘prime’ ( ′ ) symbol Complement of A is A’ 4) Literal Each occurrence of a variable in Boolean function Can be either in complemented or uncomplemented form F = A.B + B’.C 3 – variables, 4- literals 5) Boolean Function Constructed by connecting the Boolean constants and variables with the boolean operators Eg : f(A,B,C) = A.B’ + C or f = A.B’ + C

5. Boolean Postulates and Laws 1.(a) Closure with respect to the operator + (b) Closure with respect to operator . Eg : If a and b are elements of a closed set of natural numbers,N = {1,2,3,4,………..}, Then, a + b = c also ɛ N Similarly, , a . b = c also ɛ N 2. (a) An identity element wrt + , designated by 0 x + 0 = 0 + x = x (Identity Law) (b) An identity element wrt . , designated by 1 x . 1 = 1 . x = x (Identity Law)

6. Boolean Postulates and Laws( cntd .) 3.(a) Commutative with respect to + x + y = y + x (b) Commutative with respect to . x . y = y . x 4.(a) . is distributive over + x . (y + z) = (x . y) + (x . z) (b) + is distributive over . x + (y . z) = (x + y) . (x + z)

7. Boolean Postulates and Laws( cntd .) 5. For every element x ɛ B, there exists an element x’ ɛ B (called the complement of x) such that (a) x + x’ = 1 (b) x . x’ = 0 6. There exists atleast two elements x , y ɛ B such that x ≠ y

8. Proof for Boolean laws and postulates Consider a set of two elements B = {0,1}. Two binary operators + or . to prove the postulates. AND (logical multiplication) x y x.y 1 1 1 1 1 x y x+y 1 1 1 1 1 1 1 OR(logical addition) A A’ 1 1 NOT

9. Proof for Boolean laws and postulates( cntd .) 1. Closure : x + y ɛ B x . y ɛ B Since the result of each operation is either 1 or 0 2. Identity Property (a) 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 So, x + 0 = x (b) 1 . 1 = 1 . 1 = 1 . 0 = So, x . 1 = x

10. Proof for Boolean laws and postulates( cntd .) 3. Commutative laws are obvious x + y = y + x eg : 0 + 1 = 1 + 0 = 1 x . y = y . x eg : 0 . 1 = 1 . 0 = 0 4. Distributive Law1 x . (y + z) = (x . y) + (x . z ) Proof: Truth Table x y z y+z x.( y+z ) x.y x.z x.y + x.z 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

11. Proof for Boolean laws and postulates( cntd .) Distributive law2: x + (y . z) = (x + y) . (x + z ) Proof: Truth Table x y z y.z x+( y.z ) x+y x+z ( x+y ) . ( x+z ) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

12. Proof for Boolean laws and postulates( cntd .) 5. Complement Law: (a) x + x’ = 1 0 + 0’ = 0 + 1 = 1 1 + 1’ = 1 + 0 = 1 (b) x . x’ = . ’ = 0 . 1 = 0 1 . 1 ’ = 1 . = 0 6. There exists two elements 1,0 ɛ B such that 1 ≠

13. PRINCIPLE OF DUALITY Principal of Duality states that: A Boolean relation can be derived from another Boolean relation by, Changing each OR sign to an AND sign Changing each AND sign to an OR sign Complementing any 0 or 1 appearing in the expression Eg : Dual of A + A’ = 1 is A . A’ = 0 Dual of A . (B+C) =0 is A +(B.C) = 1

14. Basic Theorems: 1. Idempotent Theorem (a) x + x = x (b) x . x = x 2. Annulment Theorem (a) x + 1 = 1 (b) x . 0 = 0 3. Involution or Double Inversion Theorem (x’)’ = x

15. Basic Theorems( cntd ): 4. Associative Law (a) x + (y + z) = (x + y) + z (b) x . (y . z) = (x . y) . z 5. Absorption Law (a) x + x.y = x (b) x . (x + y) = x 6. Redundant Literal Rule (a) x + x’.y = x + y (b) x . (x’ + y) = x.y

16. Basic Theorems( cntd ): 7. Demorgan’s Theorem (a) (x + y)’ = x’ . y’ (b) (x . y)’ = x’ + y’ 8. Consensus Theorem (a) x.y + x’.z + y.z = x.y + x’.z (b) (x + y) . (x’ + z) . (y + z) = (x + y) . (x’ + z)

17. Proof for Boolean Theorems 1. Idempotent Theorem (a) x + x = x We have, x + x = (x + x).1 ( x.1 = x) = (x + x).(x + x’) ( x + x’ = 1) = x + x.x ’ ( ( x+y ).( x+z )= x+y.z , by distributive law) = x + 0 ( x.x ’ = 0) = x (b) x . x = x We have, x . x = (x . x) + 0 ( x + 0 = x) = (x . x ) + ( x . x’) (x . x’ = 0) = x . (x + x’) ( ( x.y )+( x.z )= x.( y+z ), by distributive law ) = x . 1 (x + x ’ = 1) = x

18. Proof for Boolean Theorems( cntd .) (2) Annulment Theorem (a ) x + 1 = 1 We know, x + 1 = 1 . (x + 1) (1.x = x) = (x + x’) . (x + 1) (x + x’ = 1) = x + (x’ .1) ( ( x+y ).( x+z )= x+y.z,by distributive law ) = x + x’ (x.1 = x) = 1 (b) x . 0 = We know, x . 0 = 0 + (x . 0) (0 + x = x) = (x . x’) + (x . 0) (x . x’ = 0) = x . (x’ + 0) ( ( x.y )+( x.z )=x.( y+z ) ,by distributive law ) = x . x’ (x + 0 = x) =

19. Proof for Boolean Theorems( cntd .) 3. Involution or Double Inversion Theorem (x’)’ = x Proof: Let x =1 ; then, x’ = 1’ = 0 (x’)’ = 0’ = 1 ie , (x’)’ = x Similarly, if x = 0 ; then , x’ = 0’ = 1 (x’)’ = 1’ = ie , (x’)’ = x

20. Proof for Boolean Theorems( cntd .) 4. Associative Law (a) x + (y + z) = (x + y) + z Proof: Truth Table x y z y+z x+( y+z ) x+y ( x+y )+z 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

21. Proof for Boolean Theorems( cntd .) 4. Associative Law (b) x . ( y . z) = ( x . y ) . z Proof: Truth Table x y z y.z x.( y.z ) x.y ( x.y ).z 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

22. Proof for Boolean Theorems( cntd .) 5. Absorption Law (a) x + x.y = x x + x.y = x.1 + x.y ( x.1 = x) = x . (1 + y) ( ( x.y )+( x.z ) = x .( y+z ), by distributive law ) = x . (y + 1) (x + y = y + x, by commutative law) = x . 1 ( x + 1 = 1) = x (b) x . (x + y) = x x . (x + y) = (x + 0) . (x + y) (x+0 = x) = x + (0 . y ) ( ( x+y ).( x+z ) = x+y.z , by distributive law ) = x + (y . 0) ( x . y = y . x, by commutative law) = x + 0 ( x . 0 = 0) = x

23. Proof for Boolean Theorems( cntd .) 6. Redundant Literal Rule (a) x + x’.y = x + y x + x’.y = (x + x’).(x + y) ( x + y . z = (x + y).(x + z), by distributive law) = 1. (x + y) (x + x’ = 1) = x + y (1.x = x) (b) x . (x’ + y) = x . y x . (x’ + y) = (x . x ’) + ( x . y) (x . (y + z) = ( x.y )+( x.z ), by distributive law) = 0 + (x . y) (x . x’ = 0) = x . y (0 + x = x)

24. Proof for Boolean Theorems( cntd .) 7. DeMorgan’s Theorem Theorem 1: The complement of a product is equal to the sum of complement of each term. (A.B)’ = A’ + B’ Proof: Truth Table A B A’ B’ A.B (A.B)’ A’ + B’ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Logic Diagram

25. Proof for Boolean Theorems( cntd .) 7. DeMorgan’s Theorem Theorem 2: The complement of a sum is equal to the product of complement of each term. ( A + B )’ = A’ . B’ Proof: Truth Table A B A’ B’ A + B (A + B)’ A’ . B’ 1 1 1 1 1 1 1 1 1 1 1 1 1 Logic Diagram

26. Proof for Boolean Theorems( cntd .) 8. Consensus Theorem (a) x.y + x’.z + y.z = x.y + x’. z Proof: x.y + x’.z + y.z = x.y + x’.z + y.z (x + x’) = x.y + x’.z + y.z.x + y.z.x ’ = x.y + x’.z + x.y.z + x’. y.z = x.y (1 + z) + x’.z (1 + y) (by distributive law) = x.y + x’.z (1 + x = 1) (b) (x + y).(x’ + z).(y + z) = (x + y).(x’ + z) Proof: We have, x.y + x’.z + y.z = x.y + x’.z By applying Principle of Duality, (x + y).(x’ + z).(y + z) = (x + y).(x’ + z)

27. Minimise the following Boolean functions using Boolean laws and theorems 1 ) A.A’.C = 0.C ( A.A’ = 0) = 0 2) ABCD + ABD = ABD ( C + 1) (By distributive law) = ABD 3) ABCD + AB’CD = ACD(B + B’) (By distributive law) = ACD.1 =ACD

28. Minimise the following Boolean functions using Boolean laws and theorems 4 ) A .(A +B) =A.A + A.B (By distributive law) = A + A.B ( A.A = A) = A (By absorption Law) 5) AB + ABC + ABC’ + A’BC = AB ( 1 + C + C’) + A’BC = AB (1) + A’BC = AB + A’BC = B (A + A’C) = B (A + C) (x + x’y = x + y) = BA + BC = AB + BC

29. Minimise the following Boolean functions using Boolean laws and theorems 6) A’B’C’ + A’BC’ + A’BC = A’C’ (B’ + B) + A’BC = A’C’ .(1) + A’BC = A’C’ + A’BC = A’ (C’ + BC) = A’ (C’ + B) (x + x’y = x + y) = A’C’ + A’B 7) A’BCD’ + BCD’ + BC’D’ +BC’D = BCD’(A’ + 1) + BC’(D’ + D) = BCD’ + BC’ (x + 1 = 1 and x + x’ = 1) = B (CD’ + C’) = B (C’ + D’) (x + x’y = x + y ) = BC’ + BD’

30. Minimise the following Boolean functions using Boolean laws and theorems 8) ((AB)’ + A’ + AB)’ = ((A’ + B’) + A’ + AB)’ ( DeMorgan’s theorem, ( xy )’ = x’ + y’) = (A’ + B’ + A’ + AB)’ = (A’ + B’ + AB )’ ( x + x = x) = (A’ + B’ + A)’ ( x + x’y = x + y) = (1 + B’)’ ( x + x’ = 1) = (1)’ (1 + x = 1) = 0 9) (A + BC’)’ = A’ . (BC’)’ ( DeMorgan’s theorem, ( x + y )’ = x’.y ’) = A’ . (B’ + C) ( DeMorgan’s theorem, ( xy )’ = x’ + y’) = A’B’ + A’C (By distributive law)

31. Minimise the following Boolean functions using Boolean laws and theorems 10) (x + y).(x + y’) = x.x + x.y ’ + y.x + y.y ’ = x + x.y ’ + y.x + 0 (A.A = A and A.A’ = 0) = x ( 1 + y’ + y) ( 1 + A = 1) = x 11) Find the complement of A + BC + AB F = (A + BC + AB)’ = ( A + BC + AB )’ = (A + BC)’ ( x + x.y = x ) = (A’ . (BC)’) ( DeMorgan’s theorem, (x + y)’ = x’.y ’) = A’ .(B’ + C ’) ( DeMorgan’s theorem, ( xy )’ = x’ + y’) = A’B’ + A’C ’ ( By distributive law)

32. Minimise the following Boolean functions using Boolean laws and theorems 12) AB + (AC)’ + AB’C (AB + C) = AB + (AC)’ + AB’CAB + AB’CC (by distributive law) = AB + (AC)’ + 0 + AB’C (B’.B = 0 and C.C = C) = AB + A’ + C’ + AB’C ( DeMorgan’s Theorem, ( xy )’ = x’ + y ’) = A’ + B + C’ + AB’ ( x + x’y = x + y) = A’ + C’ + B + A ( x + x’y = x + y ) = 1 + C’ + B ( A + A’ = 1) = 1 ( 1 + x = 1) 13) ((A + B + C).D)’ = (A + B + C)’ + D’ ( DeMorgan’s theorem, ( xy )’ = x’ + y’) = A’.B’.C’ + D’ ( DeMorgan’s theorem, (x + y + z)’ = x’.y’.z ’)

33. Minimise the following Boolean functions using Boolean laws and theorems 14) W’X (Z’ + YZ) + X(W + Y’Z) = W’X (Z’ + Y) + X(W + Y’Z) (A + A’B = A + B) = W’XZ’ + W’XY + XW + XY’Z (By distributive law) = X ( W’Z’ + W’Y + W + Y’Z) = X ( W’Z’ + W + Y + Y’Z) ( A + A’B = A + B ) = X ( W + Z’ + Y + Z) ( A + A’B = A + B ) = X ( W + Y + 1) (A + A’ = 1) = X(1) (A + 1 = 1) = X

34. 15) Prove the following using DeMorgan’s Theorem: (a) AB + CD = ((AB)’.(CD)’)’ (b) (A + B).(C + D) = ((A + B)’ + (C + D)’)’ Solution: (a) LHS : AB + CD By Involution Theorem, x’’ = x So, AB + CD = (AB + CD)’’ Applying DeMorgan’s Theorem, (x + y)’ = x’ . y’, we get, (AB + CD)’’ = ((AB)’ . (CD)’)’ (B) LHS : (A + B) . (C + D) By Involution Theorem, x’’ = x So , (A + B) . (C + D) = ( ( A + B) . (C + D) )’’ Applying DeMorgan’s Theorem, (x . y)’ = x’ + y’, we get, ( (A + B) . (C + D) )’’ = ((A + B)’ + (C + D)’)’

35. 16) If A and B are Boolean variables and if A = 1 and (A + B)’ = 0, find B. Solution: Given, (A + B)’ = 0 and A = 1 (A + B)’ = 0 , So, A + B = 1 Substituting value of A in the above expression, we get, 1 + B = 1 We know, 1 + 0 = 1 and 1 + 1 = 1 So, B can be either 0 or 1

36. Minimise the following Boolean functions using Boolean laws and theorems 17) x’y’z ’ + x’yz + xy’z ’ + xyz’ = x’y’z ’ + x’yz + xz ’(y’ + y) = x’y’z ’ + x’yz + xz ’ = z’ ( x’y ’ + x) + x’yz = z’ (x + y’) + x’yz = z’x + z’y ’ + x’yz = xz ’ + y’z ’ + x’yz 18) Prove that (x1 + x2).(x1’.x3’ + x3).(x2’ + x1x3)’ = x1’.x2 See ‘DPSD Video 1.1 Minimization using Boolean Laws and Theorems’

37. Minimise the following Boolean functions using Boolean laws and theorems 19) Prove that ( A + B).(A’C’ + C).(B’ + AC)’ = A’B Solution: ( A + B).(A’C’ + C).(B’ + AC )’ = (A + B).(A’C’ + C ).[B’’ . (AC)’] = (A + B).(A’C’ + C ).[B . (A’ + C’)] = (A + B ).(C + A’).(BA’ + BC’) = (AC + AA’ + BC + BA’).(BA’ + BC’) = (AC + BC + BA’).(BA’ + BC ’) = A CB A’ + B C B A’ + B A’ B A’ + A C B C’ + B C B C’ + B A’ B C’ = A’BC + A’B + A’BC’ = A’B(C + 1 + C’) = A’B