What are De-Morgan's theorems? Prove algebraically the De-Morgan's theorem.

Q. What are De-Morgan's theorems ? Prove algebraically the De-Morgan's theorem.

Answer :-

One of the most powerful identities used in Boolean logic is De-Morgan's theorem. Augustus De-Morgan had paved the way to Boolean logic by discovering these two important theorems This section introduces these two theorems of De-Morgan.

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

Now to prove De-Morgan’s first theorem, we will use complementarity laws. Let us assume that P = x + Y where, P, X, Y are logical variables. Then, according to complementation law

P + P’ =1 and P . P’= 0

That means, if P, X, Y are Boolean variables hen this complementarity law must hold for variables P. In other words, if P i.e., if (X + Y)’= X’.Y’then

(X + Y) + (XY)’must be equal to 1.   (as X + X’= 1)
and (X + Y) . (XY)’must be equal to 0.  (as X . X’= 0)

Let us prove the first part, i.e.,

X + Y) + (XY)’ = 1

(X + Y) + (XY)’= ((X + Y) +X’).((X + Y) +Y’)  (ref. X + YZ = (X + Y)(X + Z))

= (X + X’+ Y).(X + Y +Y’)
= (1 + Y).(X + 1)   (ref. X + X’=1)
= 1.1 (ref. 1 + X' =1)
= 1

So first part is proved.

Now let us prove the second part i.e.,

(X + Y).(XY)’= 0
(X + Y) . (XY)’ = (XY)’.(X + Y) (ref. X(YZ)= (XY)Z)
= (XY)’X + (XY)’Y    (ref. X(Y + Z) = XY + XZ)
= X(XY)’ + X’YY’
= 0 .Y + X’ . 0 (ref. X . X’=0)
= 0 + 0
= 0

So, second part is also proved, Thus: X + Y = X’ . Y

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

Again to prove this theorem, we will make use of complementary law i.e.,
X + X’= 1 and X . X’= 0
If XY’s complement is X + Y then it must be true that
(a) XY + (X’+ Y’) = 1
(b) XY(X’+ Y’) = 0

To prove the first part

L.H.S = XY + (X’+Y’)
= (X’+Y’) + XY (ref. X + Y = Y + X)
= (X’+Y’ + X).(X’+Y’ + Y) (ref. X + YZ = (X + Y)(X + Z))

= (X + X’+Y’).(X’ + Y +Y’)
= (1 +Y’).(X’ + 1) (ref. X + X’=1)
= 1.1 (ref. 1 + X =1)
= 1
= R.H.S

Now the second part i.e.,
XY.(X + Y) = 0

L.H.S = (XY)’.(X’+Y’)
= XYX’ + XYY’  (ref. X(Y + Z) = XY + XZ)
= XX’Y + XYY’
= 0.Y + X.0    (ref. X . X’=0)
= 0 + 0 = 0 = R.H.S.
XY.(X’ + Y’)= 0
and XY + (Xʹ +Y’) = 1
(XY)’= X’ + Y’. Hence proved