Question

Boolean algebra demorgan's theorem proof

Answer 1

Proof of DeMorgan's Theorem (b):
For any theorem X=Y, if we can show that X Y = 0, and that X + Y = 1, then
by the complement postulates, A A = 0 and A + A = 1,
X = Y. By the uniqueness of the complement, X = Y.
Thus the proof consists of showing that (A*B)*( A + B) = 0; and also that (A*B) + ( A + B) = 1.

Prove: (A*B)*( A + B) = 0
(A*B)*( A + B) = (A*B)*A + (A*B)*B) by distributive postulate
= (A*A)*B + A*(B*B) by associativity postulate
= 0*B + A*0 by complement postulate
= 0 + 0 by nullity theorem
= 0 by identity theorem
(A*B)*( A + B) = 0 Q.E.D.
Prove: (A*B) + ( A + B) =1
(A*B) + ( A + B) =(A + A + B))*(B + A + B) by distributivity B*C + A = (B + A)*(C + A)
(A*B) + ( A + B) =(A + A + B))*(B + B + A) by associativity postulate
=(1 + B)*(1 + A) by complement postulate
=1*1 by nullity theorem
=1 by identity theorem
(A*B) + ( A + B) =1 Q.E.D.

Since (A*B)*( A + B) = 0, and (A*B) + ( A + B) =1,
A*B is the complement of A + B, meaning that A*B=(A + B)';
(note that ' = complement or NOT - double bars don't show in HTML)
Thus A*B= (A + B)''.
The involution theorem states that A'' = A. Thus by the involution theorem, (A + B)'' = A + B.
This proves DeMorgan's Theorem (b).
DeMorgan's Theorem (a) may be proven.