Boolean algebra: laws, normal forms and truth tables

Values and operations

A Boolean variable takes the value 0 (false) or 1 (true). The basic operations are defined by their truth tables:

A	B	¬A (not)	A ∧ B (and)	A ∨ B (or)	A ⊕ B (xor)	A → B (implies)	A ↔ B (iff)
0	0	1	0	0	0	1	1
0	1	1	0	1	1	1	0
1	0	0	0	1	1	0	0
1	1	0	1	1	0	1	1

Two rows deserve a second look. “Or” is inclusive: $1 \lor 1 = 1$ . And an implication $A \to B$ is only false when $A$ is true and $B$ is false. “If it rains, the ground is wet” is not broken by a dry day without rain. You may see the same operations written as $AB$ or $A \cdot B$ for and, $A + B$ for or, and $\overline{A}$ or $A'$ for not, especially in circuit design.

A truth table for any expression

With $n$ variables there are $2^n$ combinations of values, and listing the expression’s value for each one settles every question about it. The generator below builds that table, with a column for each sub-expression so you can follow the evaluation. It also classifies the expression: a tautology is always 1, a contradiction always 0, and anything else is a contingency.

The expression it starts with is De Morgan’s law written as a single formula. Its final column is all 1s, which is exactly what it means for the two sides to be equivalent.

The laws

Every law below can be checked with a truth table, and each has a dual: swap ∧ with ∨ and 0 with 1, and you get another law.

Law	“And” form	“Or” form (the dual)
Identity	$A \land 1 = A$	$A \lor 0 = A$
Domination	$A \land 0 = 0$	$A \lor 1 = 1$
Idempotence	$A \land A = A$	$A \lor A = A$
Complement	$A \land \lnot A = 0$	$A \lor \lnot A = 1$
Double negation	$\lnot\lnot A = A$	—
Commutativity	$A \land B = B \land A$	$A \lor B = B \lor A$
Associativity	$(A \land B) \land C = A \land (B \land C)$	$(A \lor B) \lor C = A \lor (B \lor C)$
Distributivity	$A \land (B \lor C) = (A \land B) \lor (A \land C)$	$A \lor (B \land C) = (A \lor B) \land (A \lor C)$
Absorption	$A \land (A \lor B) = A$	$A \lor (A \land B) = A$
De Morgan	$\lnot(A \land B) = \lnot A \lor \lnot B$	$\lnot(A \lor B) = \lnot A \land \lnot B$

Most of these match ordinary arithmetic if you read ∧ as multiplication and ∨ as addition. Two don’t. Idempotence ( $A \lor A = A$ ) has no arithmetic counterpart, and the second distributive law, $A \lor (B \land C) = (A \lor B) \land (A \lor C)$ , would say $a + bc = (a + b)(a + c)$ , which is false for numbers.

Worked example: simplifying with the laws

Simplify $(A \land B) \lor (A \land \lnot B)$ .

Distributivity, read right to left: $A \land (B \lor \lnot B)$ .
Complement: $B \lor \lnot B = 1$ , giving $A \land 1$ .
Identity: $A$ .

Whatever $B$ is, the expression equals $A$ . Paste it into the generator to confirm: its minimal form is just A.

Normal forms

Every Boolean function can be written in two standard shapes.

Disjunctive normal form (DNF) is an OR of ANDs: $(A \land \lnot B) \lor (\lnot A \land B)$ . To get it from a truth table, take one AND-term (a minterm) for each row where the function is 1, matching that row exactly, and OR them together.
Conjunctive normal form (CNF) is an AND of ORs: $(A \lor B) \land (\lnot A \lor \lnot B)$ . Take one OR-clause (a maxterm) for each row where the function is 0, ruling that row out, and AND them together.

Worked example: the majority function

“At least two of $A, B, C$ are 1” is true on rows 3, 5, 6 and 7 (writing the rows as binary numbers $ABC$ ). The canonical DNF has one minterm per true row:

(\lnot A \land B \land C) \lor (A \land \lnot B \land C) \lor (A \land B \land \lnot C) \lor (A \land B \land C).

Combining minterms that differ in one variable (rows 3 and 7 differ only in $A$ , so they merge into $B \land C$ ) gives the minimal form

(A \land B) \lor (A \land C) \lor (B \land C).

The generator finds this automatically with the Quine–McCluskey method: it repeatedly merges terms that differ in one variable to find the prime implicants, then picks the fewest of them that cover every true row.

CNF matters well beyond textbooks. SAT solvers, which decide whether a formula can be made true and power hardware verification, scheduling and package managers, take their input in CNF. Deciding satisfiability of CNF formulas was the first problem shown to be NP-complete.

Fewer operations are enough

A set of operations is functionally complete if it can express every Boolean function. {∧, ∨, ¬} is, because of the DNF construction. So is {∧, ¬}, because De Morgan gives $A \lor B = \lnot(\lnot A \land \lnot B)$ . Remarkably, NAND alone is enough:

\lnot A = A \uparrow A, \qquad A \land B = (A \uparrow B) \uparrow (A \uparrow B), \qquad A \lor B = (A \uparrow A) \uparrow (B \uparrow B).

That is why a chip can be built from a single kind of gate. Check any of these identities in the generator: type A nand A or (A nand B) nand (A nand B).

From Boole to circuits George Boole set out his algebra of logic in 1854. In 1938 Claude Shannon showed that relay switching circuits obey the same algebra, so circuit design could be done with Boolean algebra. Modern digital logic grew from that observation.

References

C. E. Shannon, “A symbolic analysis of relay and switching circuits”, Transactions of the AIEE 57(12), 1938. doi:10.1109/T-AIEE.1938.5057767
E. J. McCluskey, “Minimization of Boolean functions”, Bell System Technical Journal 35(6), 1956. doi:10.1002/j.1538-7305.1956.tb03835.x
G. Boole, An Investigation of the Laws of Thought, Walton and Maberly, 1854.
“Boolean algebra”, Wikipedia.

Boolean algebra: laws, normal forms and truth tables

Values and operations

A truth table for any expression

Truth table generator

Normal forms

LaTeX

The laws

Worked example: simplifying with the laws

Normal forms

Worked example: the majority function

Fewer operations are enough

References

Values and operations

A truth table for any expression

Truth table generator

Normal forms

LaTeX

The laws

Worked example: simplifying with the laws

Normal forms

Worked example: the majority function

Fewer operations are enough

References

Keep going

Truth table generator

Sets, relations and functions

Finite-state machines