Digital Circuits Cheatsheet
Boolean Algebra
Use this Digital Circuits reference while you build software engineering projects, review code, or refresh the syntax you reach for most.
Overview
Boolean algebra is the mathematical foundation of digital logic. Variables take only two values — 0 (false/LOW) and 1 (true/HIGH) — and operations follow a small, closed set of laws.
Basic Operations
| Operation | Symbol | Expression | Meaning |
|---|---|---|---|
| AND | · or ∧ | A · B | 1 only if both are 1 |
| OR | + or ∨ | A + B | 1 if at least one is 1 |
| NOT | ¬ or ′ or overline | A′ | Inverts the value |
| NAND | ↑ | (A · B)′ | NOT AND |
| NOR | ↓ | (A + B)′ | NOT OR |
| XOR | ⊕ | A ⊕ B | 1 if inputs differ |
| XNOR | ⊙ | (A ⊕ B)′ | 1 if inputs are equal |
Axioms (Postulates)
These are assumed true without proof; all other rules derive from them.
| Name | 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 · A′ = 0 | A + A′ = 1 |
| Involution | (A′)′ = A | — |
Fundamental Theorems
| Theorem | AND form | OR form |
|---|---|---|
| Commutative | A · B = B · A | A + B = B + A |
| Associative | (A·B)·C = A·(B·C) | (A+B)+C = A+(B+C) |
| Distributive | A·(B+C) = A·B + A·C | A+(B·C) = (A+B)·(A+C) |
| Absorption | A · (A + B) = A | A + A·B = A |
| Consensus | A·B + A′·C + B·C = A·B + A′·C | (A+B)·(A′+C)·(B+C) = (A+B)·(A′+C) |
The distributive law in OR form is non-intuitive — it has no direct analogue in ordinary algebra.
De Morgan's Theorems
The most-used identities for simplification and gate conversion:
Theorem 1: (A · B)′ = A′ + B′
Theorem 2: (A + B)′ = A′ · B′
Generalized form: - (A · B · C · …)′ = A′ + B′ + C′ + … - (A + B + C + …)′ = A′ · B′ · C′ · …
Mnemonic: "Break the bar, change the operation."
NAND: (A · B)′ = A′ + B′ (NOR with inverted inputs) NOR: (A + B)′ = A′ · B′ (NAND with inverted inputs)
Canonical Forms
Minterm (Sum of Products, SOP)
Each minterm covers exactly one row of the truth table where output = 1.
- mᵢ: product term where each variable appears true if that bit is 1, complemented if 0.
- F = Σm(…) — sum of minterms
Maxterm (Product of Sums, POS)
Each maxterm covers exactly one row where output = 0.
- Mᵢ: sum term where each variable appears complemented if that bit is 1, true if 0.
- F = ΠM(…) — product of maxterms
Example: F(A, B, C) = Σm(1, 3, 5, 7)
| Row | A | B | C | F | Minterm |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | — |
| 1 | 0 | 0 | 1 | 1 | A′B′C |
| 2 | 0 | 1 | 0 | 0 | — |
| 3 | 0 | 1 | 1 | 1 | A′BC |
| 4 | 1 | 0 | 0 | 0 | — |
| 5 | 1 | 0 | 1 | 1 | AB′C |
| 6 | 1 | 1 | 0 | 0 | — |
| 7 | 1 | 1 | 1 | 1 | ABC |
F = A′B′C + A′BC + AB′C + ABC = C (after simplification)
Algebraic Simplification
Work towards fewer literals and fewer terms.
| Step | Expression | Rule applied |
|---|---|---|
| Start | A′B′C + A′BC + AB′C + ABC | — |
| Group pairs | A′C(B′+B) + AC(B′+B) | Distributive |
| Simplify | A′C·1 + AC·1 | Complement |
| Group again | C(A′+A) | Distributive |
| Result | C | Complement |
Duality Principle
Every Boolean identity has a dual obtained by: 1. Swapping AND (·) and OR (+) 2. Swapping 0 and 1 3. Leaving variables and their complements unchanged
If a statement is true, its dual is also true.
XOR Properties
| Property | Expression |
|---|---|
| Commutative | A ⊕ B = B ⊕ A |
| Associative | (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C) |
| Identity | A ⊕ 0 = A |
| Self-inverse | A ⊕ A = 0 |
| Complement | A ⊕ 1 = A′ |
| Useful identity | A ⊕ B = A′B + AB′ |
XOR is used extensively in parity generation, adders, and encryption (XOR cipher).
Standard Forms Comparison
| SOP (Sum of Products) | POS (Product of Sums) | |
|---|---|---|
| Built from | Minterms (AND terms) | Maxterms (OR terms) |
| Output 1 when | Any minterm is 1 | All maxterms are 1 |
| Implemented with | AND-OR network | OR-AND network |
| Two-level NAND | NAND-NAND equivalent | — |
| Two-level NOR | — | NOR-NOR equivalent |