Digital Logic Foundations
Truth Tables and De Morgan's Laws
Truth tables are systematic tools for evaluating Boolean expressions. De Morgan's Laws allow transformation between AND/OR forms, essential for circuit simplification.
Truth Tables
A truth table lists all possible input combinations and their corresponding output for a Boolean expression. For n input variables, there are 2n rows.
Truth Table for A·B + C·D
This circuit has 4 inputs → 24 = 16 rows. The table evaluates the intermediate steps A·B and C·D, then combines them with OR.
| A | B | C | D | A·B | C·D | A·B+C·D |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
De Morgan's Laws
De Morgan's Laws are the most important identities in Boolean Algebra. They allow you to swap between AND and OR by distributing or factoring the NOT operator.
Law 1: NOT of AND = OR of NOTs
A·B = Ā + B̄
Gate equivalence: A NAND gate equals an OR gate with inverted inputs.
Law 2: NOT of OR = AND of NOTs
A+B = Ā · B̄
Gate equivalence: A NOR gate equals an AND gate with inverted inputs.
Applying De Morgan — XNOR Example
Starting from XNOR: X = A⊕B
Expanded: X = AB + ĀB̄ (output is 1 when inputs are equal)
Applying De Morgan twice gives an alternative form:
Both expressions produce the same truth table — they are logically equivalent.
Boolean Identities Summary
| Identity | AND form | OR form |
|---|---|---|
| Identity | A · 1 = A | A + 0 = A |
| Null | A · 0 = 0 | A + 1 = 1 |
| Idempotent | A · A = A | A + A = A |
| Complement | A · Ā = 0 | A + Ā = 1 |
| Double Negation | NOT(NOT A) = A | |
| De Morgan 1 | NOT(A·B) = Ā + B̄ | |
| De Morgan 2 | NOT(A+B) = Ā · B̄ | |
Using De Morgan in Gate Design
When designing circuits, De Morgan allows you to shift inverter bubbles from outputs to inputs (or vice versa), enabling you to merge gate layers and reduce component count. For example:
So a NAND gate can be replaced by an OR gate with both inputs inverted — same function, different physical implementation.