**DeMorgan’s Theorem Statement: **

**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:

- (X+Y)’ = X’.Y’
- (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]

[BY X.Y = Y.X]

= X.X’.Y’ + X.Y.Y’

[BY X.X’ = 0]

[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)]

[BY X+YZ = (X+Y)(X+Z)]

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

[BY X+Y = Y+X]

[BY X+Y = Y+X]

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

[BY X+X’ = 1]

[BY X+X’ = 1]

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

[BY 1+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]

[BY X.(Y+Z) = X.Y+X.Z]

= X.Y.X’ + X.Y.Y’

[BY X.Y = Y.X]

[BY X.Y = Y.X]

= X.X’.Y + X.Y.Y’

[BY X.0 = 0]

[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.

Advertisements