Logic and Boolean Algebra — CAPE Applied notes

Boolean algebra is the arithmetic of two values, 1 and 0 — true and false, on and off. It is the mathematics inside every digital circuit, and the point of it is simplification: fewer gates, less cost, less delay.

Propositions and connectives

A proposition is either true (1) or false (0). Three basic operations combine them:

Operation	Boolean notation	Logic notation	Meaning
AND	$A \cdot B$ or $AB$	$A \wedge B$	both
OR	$A + B$	$A \vee B$	at least one
NOT	$A'$ or $\bar{A}$	$\neg A$	the opposite

Truth tables

A truth table lists every combination of inputs and the resulting output. With $n$ inputs there are $2^n$ rows — 4 for two inputs, 8 for three, 16 for four.

$\begin{array}{cc|cccc} A & B & AB & A+B & A \oplus B & (AB)' \\ \hline 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 \end{array}$

Logic gates

Gate	Output is 1 when	Boolean form
AND	all inputs are 1	$AB$
OR	at least one input is 1	$A + B$
NOT	the input is 0	$A'$
NAND	not all inputs are 1	$(AB)'$
NOR	no input is 1	$(A+B)'$
XOR	exactly one input is 1	$A \oplus B$

NAND is an AND gate followed by a NOT; NOR is an OR gate followed by a NOT. Both are important in practice because every logic function can be built from NAND gates alone — a fact that simplifies manufacturing enormously.

Boolean algebra laws

Law	AND form	OR form
Identity	$A \cdot 1 = A$	$A + 0 = A$
Null	$A \cdot 0 = 0$	$A + 1 = 1$
Idempotent	$A \cdot A = A$	$A + A = A$
Complement	$A \cdot A' = 0$	$A + A' = 1$
Double negation	$(A')' = A$	$(A')' = A$
Commutative	$AB = BA$	$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(A+B) = A$	$A + AB = A$

De Morgan's laws

$(A \cdot B)' = A' + B' \qquad (A + B)' = A' \cdot B'$

Break the bar and change the sign. Negating a compound expression negates each part and swaps AND with OR.

Check the first against the table above: $(AB)'$ gives $1,1,1,0$ , and $A'+B'$ gives $1+1$ , $1+0$ , $0+1$ , $0+0$ — that is $1,1,1,0$ ✓

In circuit terms: a NAND gate is equivalent to an OR gate with both inputs inverted.

Simplifying circuits

Fewer gates means cheaper, faster, more reliable hardware.

Simplify $A + AB$ .

$A + AB = A(1 + B) = A \cdot 1 = A$

The $B$ input is irrelevant, and an entire AND gate can be removed.

Simplify $AB + AB'$ .

$AB + AB' = A(B + B') = A \cdot 1 = A$

Simplify $A + A'B$ .

$A + A'B = (A + A')(A + B) = 1 \cdot (A+B) = A + B$

using the second distributive law. Verify with a truth table: the values are $0, 1, 1, 1$ for both expressions ✓