Section 4.5
DeMorgan's Theorem

DeMorgan's theorems are extremely useful in simplifying expressions in which a product or sum of variables is inverted. The two theorems are:

(16) (x+y)' = x' * y'

(17) (x*y)' = x' + y'

Theorem (16) says that when the OR sum of two variables is inverted, this is the same as inverting each variable individually and then ANDing these inverted variables.

Theorem (17) says that when the AND product of two variables is inverted, this is the same as inverting each variable individually and then ORing them.

---

Example

X	= [(A'+C) * (B+D')]'
	= (A'+C)' + (B+D')' [by theorem (17)]
	= (A''*C') + (B'+D'') [by theorem (16)]
	= AC' + B'D

---

Three Variables DeMorgan's Theorem

(18) (x+y+z)' = x' * y' * z'

(19) (xyz)' = x' + y' + z'

---

Implications of DeMorgan's Theorem

For (16): (x+y)' = x' * y'

---

For (17): (x*y)' = x' + y'

---