Boolean Algebra & Logic Gates

Every digital circuit, no matter how large, is ultimately an expression in an algebra with exactly two values: 0 and 1. Boolean algebra is that algebra — a small set of operations and rules that let you manipulate logic expressions symbolically, the same way ordinary algebra lets you manipulate x and y, except every variable here can only ever be 0 or 1.

The three basic operations

Everything in Boolean algebra is built from three operations, each with a corresponding physical gate:

Operation	Symbol used here	Meaning	Gate
AND	A · B (or AB)	1 only if both A and B are 1	AND gate
OR	A + B	1 if either A or B (or both) is 1	OR gate
NOT	A' (or Ā)	Inverts A	NOT gate (inverter)

A truth table — every possible combination of inputs, and the output for each — is the ground truth for what a Boolean expression means:

A	B	A·B	A+B
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	1

Everything else in this page — every law, every derived gate, every simplification technique in the next page — is provably consistent with these three operations and their truth tables. When in doubt about whether an algebraic manipulation is valid, a truth table is the objective way to check it.

Derived gates

Three more gates are used constantly enough to have their own names and symbols, even though each is just AND/OR/NOT combined:

• NAND ((A·B)') — AND followed by NOT.
• NOR ((A+B)') — OR followed by NOT.
• XOR (A ⊕ B) — 1 if A and B differ; equivalent to AB' + A'B.
• XNOR ((A ⊕ B)') — 1 if A and B are the same; equivalent to AB + A'B'.

XOR is worth pausing on: it's the bit-level "difference detector," and it's exactly the gate that computed the per-bit sum in Binary Arithmetic's full adder, the parity bit in Digital Codes, and the single-bit-change property of Gray code — the same primitive quietly doing three different jobs.

Boolean postulates and theorems

These identities are the algebraic toolkit for manipulating expressions. Every one of them is verifiable with a truth table, and every one has a direct dual — swap every · for +, every + for ·, every 0 for 1 and 1 for 0, and the law still holds. That duality isn't a coincidence; it falls directly out of AND/OR being symmetric in how they're each other's "opposite" operation.

Law	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
Commutative	A · B = B · A	A + B = B + A
Associative	(AB)C = A(BC)	(A+B)+C = A+(B+C)
Distributive	A(B+C) = AB+AC	A+BC = (A+B)(A+C)
Absorption	A + AB = A	A(A+B) = A

The OR-distributive law (A + BC = (A+B)(A+C)) is the one that most often surprises people coming from ordinary algebra — it has no numeric-algebra analogue at all, and it's easy to mistrust until you check it against a truth table (or notice it's just the dual of the familiar AND-distributive law above it).

De Morgan's theorem

The single most load-bearing identity in practical logic design:

(A · B)' = A' + B'
(A + B)' = A' · B'

In words: the complement of an AND is the OR of the complements, and vice versa. This is what lets you freely convert between AND/OR-based expressions and NAND/NOR-based ones — which matters enormously in practice, because of the next section.

Universal gates

NAND and NOR are each, individually, functionally complete — either one alone can implement AND, OR, and NOT, and therefore any Boolean function at all, with no other gate type required.

NOT from NAND:      A' = (A · A)' = NAND(A, A)
AND from NAND:       AB = ((AB)')' = NAND(NAND(A,B), NAND(A,B))
OR from NAND:      A+B = A'' + B'' = (A'B')' = NAND(NAND(A,A), NAND(B,B))   (via De Morgan)

This isn't just a theoretical curiosity — it's the reason CMOS standard-cell libraries are built almost entirely from NAND and NOR gates rather than AND and OR directly. A CMOS NAND gate is physically simpler to build than a CMOS AND gate (an AND gate is literally a NAND followed by an extra inverter stage internally), so synthesis tools default to expressing logic in terms of NAND/NOR wherever possible, and De Morgan's theorem is the algebraic tool that makes that translation possible for arbitrary expressions.

Canonical forms: SOP and POS

Any Boolean function can be written directly from its truth table in one of two standard, mechanical forms:

• Sum of Products (SOP) — OR together one AND term (a minterm) for every row where the output is 1, with each minterm containing every input variable, complemented if that input was 0 in that row.
• Product of Sums (POS) — the dual: AND together one OR term (a maxterm) for every row where the output is 0.

Truth table:
A B | F
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 0

SOP (from the two rows where F=1):
F = A'B + AB'

POS (from the two rows where F=0):
F = (A+B)(A'+B')

Both forms are guaranteed correct by construction — read directly off the truth table, no creativity required — but neither is guaranteed to be efficient. F = A'B + AB' above happens to already be minimal (it's just XOR), but canonical forms in general tend to produce more gates than necessary, especially as the number of input variables grows. Turning a correct-but-bloated canonical expression into a minimal one is exactly the subject of the next page.

What's next

With the algebra and canonical forms established, the next page covers Karnaugh maps — the standard visual technique for taking a truth table or an SOP/POS expression straight to a minimal gate-level implementation, without needing to grind through Boolean algebra manipulations by hand.