Mathematics

DeMorgan’s Theorem with Proof

DeMorgan’s Theorem Statement:

1. The complement of the sum of two or more variables is equal to the product of the complements of the variables. If X and Y are the two logical variables, then according to the De Morgan’s Theorem we can write: (X + Y)’ = X’.Y’.

For n number of logical variables say X1, X2, ………………., Xn it can be written as: (X1 + X2 + …………+ Xn)’ = X’1.X’2…………….X’n.

2. The complement of the product of two or more logical variables is equal to the sum of the complements of the variables. If Z and Y are the two logical variables, the according to the second law of De Morgan’s theorem we can write: (X.Y)’ = X’ + Y’

For n numbers of variables say X1, X2, ………………, Xn the second theorem can be written as: (X1.X2……………Xn)’ = X’1 + X’2 + ……………….. + X’n.

Proof:

There are two De Morgan’s theorems:

1.  (X+Y)’ = X’.Y’
2.  (X.Y)’ = X’+ Y’

First let us prove (X+Y)’ = X’.Y’ as:

To prove this theorem, we will use complementary laws that are as follows:  X+X’ = 1 and, X.X’ = 0.
Now, let P = X+Y,  where P, X, Y are three logical variables,
According to the complementary laws we have:
P+P’ =1 and P.P’ = 0, if P = X+Y, then P’ = (X+Y)’. If we take (X+Y)’ = X’.Y’.
Therefore to prove (1) we have to show that,
(X+Y)+(X’.Y’) should be equal to 1 and (X+Y).(X’.Y’) should be equal to 0.
(X+Y)+(X’.Y’)                                                             [BY X+YZ = (X+Y)(X+Z)]
= ((X+Y)+X’).((X+Y)+Y’)
= (X+Y+X’).(X+Y+Y’)                                                   [BY X+Y = Y+X]
= (X+X’+Y).(X+Y+Y’)                                                   [BY X+X’ = 1]
= (1+Y).(X+1)                                                                 [BY X+1 = 1]
= 1.1
= 1
So, the first part is proved. Now, we have to prove the second part (X+Y).(X’.Y’)
[BY X.(Y+Z) = X.Y+X.Z ]
= X.X’.Y’ + Y.X’.Y’
[BY X.Y = Y.X]
= X.X’.Y’ + X.Y.Y’
[BY X.X’ = 0]
= 0.Y’ + X.0
= 0 + 0
= 0
So, the second part is also proved.
Therefore, we can say that (X+Y)’ = X’.Y’

Therefore to prove (2) we have to show that, De Morgan’s theorem (X.Y)’ = X’+ Y’ is proved in same way by letting P = X.Y.

Here, we again use the complementary laws.

X+X’ = 1 and X.X’ = 0. If we take P = X.Y, then P’ = (X.Y)’.

If we assume that P’ = (X.Y)’ = X’+Y’ then, we have to prove,
(X.Y)+(X’+Y’) should be equal to 1.
(X.Y).(X’+Y’) should be equal to 0.
(X.Y)+(X’+Y’)
[BY X+YZ = (X+Y)(X+Z)]
= (X+X’+Y’).(Y+X’+Y’)
[BY X+Y = Y+X]
= (X+X’+Y’).(X’+Y+Y’)
[BY X+X’ = 1]
= (1+Y’).(X’+1)
[BY 1+X’ = 1]
= 1.1
= 1
So, the first part is proved.
Now, we have to prove the second part as:
(X.Y).(X’+Y’)
[BY X.(Y+Z) = X.Y+X.Z]
= X.Y.X’ + X.Y.Y’
[BY X.Y = Y.X]
= X.X’.Y + X.Y.Y’
[BY X.0 = 0]
= 0.Y + X.0
= 0+0
= 0
So, the second part is also proved.
Therefore, we can write (X.Y)’ = X’+ Y’
Hence the proof.