Boolean Algebra

Digital Logic 101 · 12 min read

Postulates and identities

Name	AND form	OR form
Identity	A · 1 = A	A + 0 = A
Annihilator	A · 0 = 0	A + 1 = 1
Idempotence	A · A = A	A + A = A
Complement	A · A' = 0	A + A' = 1
Double negation	(A')' = A
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)
DeMorgan	(A · B)' = A' + B'	(A + B)' = A' · B'
Absorption	A · (A + B) = A	A + A·B = A

Figure 1. The core algebraic identities. Every Boolean simplification reduces to repeated application of these — usually one rule per step.

Boolean algebra is the algebra of two values, $\{0, 1\}$ , with two binary operations ( $\cdot$ for AND, $+$ for OR) and one unary operation ( $\overline{A}$ for NOT, sometimes written $A'$ ).

Every identity comes in a pair. Swap $\cdot \leftrightarrow +$ and $0 \leftrightarrow 1$ in any true statement and the result is also true — this is the duality principle.

DeMorgan’s theorems

Figure 2. DeMorgan as bubble pushing. Pushing the output bubble past an AND flips it into an OR (and inverts each input); pushing it past an OR flips it into an AND. The function is unchanged — only the symbol shape redistributes the negations.

$\overline{A \cdot B} = \overline{A} + \overline{B}$ and $\overline{A + B} = \overline{A} \cdot \overline{B}$ . Negation distributes over AND/OR by flipping the operator. In CMOS this lets you redraw any AND-OR network as a NAND-NAND network without changing the function — useful because NAND is cheaper to fabricate.

Absorption

A	B	A·B	F = A + A·B	G = A
0	0	0	0	0
0	1	0	0	0
1	0	0	1	1
1	1	1	1	1

Figure 3. Absorption swallows a redundant product or sum. If A is already 1 in the first term, the whole AB term is unreachable as a tie-breaker — it can never make the function 1 when A wasn't already going to. Symmetric argument for the AND form.

$A + A \cdot B = A$ and $A \cdot (A + B) = A$ . The shorter term "absorbs" the longer one whenever they share a literal.

Absorption is the most common simplification in real schematics. Whenever a product term contains a literal already present elsewhere, look for an absorption.

Consensus theorem

$AB + \overline{A}C + BC = AB + \overline{A}C$ . The third term BC is the consensus of the first two, and it can be removed without changing the function. This one is harder to spot by eye — Karnaugh maps make it obvious because consensus terms sit on a diagonal in the K-map.

Worked simplification

Start: F = A·B + A·B' + A'·B

Step	Expression	Identity used
1	A·(B + B') + A'·B	Distributive (factor A)
2	A·1 + A'·B	Complement (B + B' = 1)
3	A + A'·B	Identity (A·1 = A)
4	A + B	Absorption (A + A'·B = A + B)

Result: F = A + B

Figure 4. Step-by-step simplification of F = AB + AB' + A'B. Each step cites the identity that fires. The minimum SOP is A + B — confirmable by Quine–McCluskey or by inspection on a 2-variable K-map.

The Simulate stage lets you type any expression and click identity-rule cards to drive the same kind of step-by-step rewrite, then compare against an automatic Quine–McCluskey result.