x’y’z’+x’y’z+x’yz+x’yz’+xy’z+xy’z=x’+y’z.
Prove using boolean algebra.
Answers
Answer:
Boolean Algebra
Definition: A Boolean Algebra is a math construct (B,+, . , ‘, 0,1) where B is a non-empty set, + and . are
binary operations in B, ‘ is a unary operation in B, 0 and 1 are special elements of B, such that:
a) + and . are communative: for all x and y in B, x+y=y+x, and x.y=y.x
b) + and . are associative: for all x, y and z in B, x+(y+z)=(x+y)+z, and x.(y.z)=(x.y).z
c) + and . are distributive over one another: x.(y+z)=xy+xz, and x+(y.z)=(x+y).(x+z)
d) Identity laws: 1.x=x.1=x and 0+x=x+0=x for all x in B
e) Complementation laws: x+x’=1 and x.x’=0 for all x in B
Examples:
(B=set of all propositions, ∨, ∧, ¬, T, F)
(B=2A, U, ∩, c
, Φ,A)
Theorem 1: Let (B,+, . , ‘, 0,1) be a Boolean Algebra. Then the following hold:
a) x+x=x and x.x=x for all x in B
b) x+1=1 and 0.x=0 for all x in B
c) x+(xy)=x and x.(x+y)=x for all x and y in B
Proof:
a) x = x+0 Identity laws
= x+xx’ Complementation laws
= (x+x).(x+x’) because + is distributive over .
= (x+x).1 Complementation laws
= x+x Identity laws
x = x.1 Identity laws
= x.(x+x’) Complementation laws
= x.x +x.x’ because + is distributive over .
= x.x+0 Identity laws
= x.x
b) x+1 =x+(x+x’) Complementation laws
= (x+x)+x’ + is associative
= x+x’ using (a)
= 1 Complementation laws
0.x =(x’.x).x Complementation laws
= x’.(x.x) . is associative
= x’.x using (a)
=0 Complementation laws
c) x+(xy) = x.1+x.y Identity laws
=x.(1+y) because + is dist