DeMorgan’s Theorems

Overview

DeMorgan’s theorems are fundamental principles in Boolean algebra that establish the relationship between AND, OR, and NOT operations. These theorems are essential for simplifying logic circuits and converting between different gate implementations. They state that the complement of a sum equals the product of complements, and the complement of a product equals the sum of complements.

Detailed Explanation

The Theorems

1. First Theorem

(A + B)' = A'•B'

Truth Table Proof:
A B | A+B | (A+B)' | A' B' | A'•B'
---|-----|--------|-------|-------
0 0 | 0   |   1    | 1  1  |  1
0 1 | 1   |   0    | 1  0  |  0
1 0 | 1   |   0    | 0  1  |  0
1 1 | 1   |   0    | 0  0  |  0

2. Second Theorem

(A•B)' = A' + B'

Truth Table Proof:
A B | A•B | (A•B)' | A' B' | A'+B'
---|-----|--------|-------|-------
0 0 | 0   |   1    | 1  1  |  1
0 1 | 0   |   1    | 1  0  |  1
1 0 | 0   |   1    | 0  1  |  1
1 1 | 1   |   0    | 0  0  |  0

Circuit Transformations

Before DeMorgan:        After DeMorgan:
A --|\                  A --o--|
     |)o-- F    ===          |
B --|\                  B --o--|AND-- F

Applications

1. Gate Conversion

NAND = AND + NOT
NOR = OR + NOT

NAND to NOR conversion:
A NAND B = (A•B)' = A' + B' = A NOR B

2. Circuit Simplification

Original: (A•B•C)'
Using DeMorgan: A' + B' + C'

Practice Problems

1. Apply DeMorgan’s theorems:

   • (A + B + C)’
   • (A•B•C•D)’
   • ((A + B)•(C + D))’

2. Convert these circuits:

   • NAND to AND-OR
   • NOR to OR-AND

References

• Digital Design by Morris Mano
• Logic Design Theory by Kohavi
• DeMorgan’s Laws Tutorial

← Back to Minor - Digital Electronics