De Morgan

De Morgan\'s theorem is one of the most powerful tools in Boolean algebra for simplifying logic expressions and converting between different gate implementations. It provides the mathematical basis for understanding why NAND and NOR gates are called universal gates.

Statement of De Morgan\'s Theorem

First Theorem

"The complement of a sum equals the product of the complements."

Second Theorem

"The complement of a product equals the sum of the complements."

Easy Memory Rule: "Break the Bar, Change the Sign"

• Break the bar over the expression
• Change OR to AND (or AND to OR)
• Complement each individual variable

Algebraic Proof

Proof of (A + B)' = A\'·B\'

To prove X = Y in Boolean algebra, show that:

1. X + Y\' = 1, and
2. X · Y\' = 0

Let X = (A+B)' and Y = A\'·B\'

Show X + Y = 1: (A+B)\' + (A+B) = 1 (complement law) — but let\'s show A\'B\' + (A+B) = 1: A\'B\' + A + B = A + A\'B\' + B = A + B + A\'B\' = (A + A\'B\') + B = (A + B\') + B (absorption) ...

Actually, the truth table proof is most straightforward for exam purposes.

Generalization to n Variables

De Morgan\'s theorem extends to any number of variables:

Example with 3 variables:

Applying De Morgan\'s to Complex Expressions

Example 1: Find the complement of F = AB + CD

Example 2: Find the complement of F = (A+B)(C+D)

Example 3: Simplify (A\' + B\'C)\'

Example 4: Simplify ((AB)\'+ C)\'

Circuit Implementation

De Morgan\'s theorem shows the equivalence between different gate configurations:

NOR Gate = Bubbled AND

NAND Gate = Bubbled OR

Converting AND-OR to NAND-NAND

Using De Morgan\'s theorem, any SOP expression can be implemented using only NAND gates:

Original: F = AB + CD

Circuit:

Converting OR-AND to NOR-NOR

Any POS expression can be implemented using only NOR gates:

Original: F = (A+B)(C+D)

Common Mistakes to Avoid

Practice Problems

Problem 1: Find complement of F = A\'B + AB\'C

Problem 2: Prove (A + B\')(A\' + B) has complement = A\'B\' + AB

Interview Questions

Q1: State De Morgan\'s theorem and explain its significance in digital design.

(A+B)\' = A\'·B\' and (AB)\' = A\'+B\'. Significance: It allows conversion between AND-OR and NAND-NAND (or NOR-NOR) implementations, proves universality of NAND/NOR gates, and enables systematic simplification of complemented expressions.

Q2: How does De Morgan\'s theorem prove that NAND is a universal gate?

Since (AB)\' = A\'+B\', a NAND gate with same inputs gives NOT: (AA)\' = A\'. NAND followed by NOT gives AND. De Morgan\'s shows NAND with inverted inputs gives OR. Thus NAND can implement NOT, AND, and OR — making it universal.

Q3: Apply De Morgan\'s theorem to simplify: ((A+B)\' · C)\'

= (A+B)\' \' + C\' = (A+B) + C\' = A + B + C\'. We used De Morgan\'s to break the outer complement, then involution on the double complement.

Q4: What is the dual of De Morgan\'s first theorem?

First theorem: (A+B)\' = A\'B\'. Its dual (swap +↔·, keep complements): (AB)\' = A\'+B\'. This is exactly the second theorem! De Morgan\'s theorems are duals of each other.

Q5: How do you apply De Morgan\'s to a multi-level expression like ((AB + C)\'D)\'?

Work from the outermost complement inward: ((AB+C)\'D)\' = (AB+C)\'\' + D\' = (AB+C) + D\' = AB + C + D\'. Each application of De Morgan\'s handles one complement bar, and involution removes double complements.