Digital Circuits Cheatsheet
Boolean Algebra
Use this Digital Circuits reference while you build software engineering projects, review code for technical interview prep, or polish examples for a software engineer resume.
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 |