Boolean Algebra

Boolean algebra is the algebra of binary variables. Variables take only two values — $0$ and $1$ — and the operations are AND ( $\land$ ), OR ( $\lor$ ), and NOT ( $\neg$ ). Every digital circuit’s behavior can be written as a Boolean expression and simplified using its laws.

The point of working in Boolean algebra is reducing a logic expression to fewer gates. A circuit with two terms after simplification is faster, smaller, and cheaper than one with eight, even if both compute the same function.

Logical operations

The three basic operations, plus the derived ones:

Disjunction – $X \lor Y$ – truth table $1110$
Conjunction – $X \land Y$ – $1000$
Negation – $\neg X$ – $01$
Exclusive disjunction (XOR) – $X \oplus Y$ – $0110$
Material biconditional (XNOR) – $X \leftrightarrow Y$ – $1001$
Material conditional – $X \to Y$ – $1011$

In digital logic, $\land$ is often written as multiplication ( $X Y$ or $X \cdot Y$ ), and $\lor$ is written as addition ( $X + Y$ ). Don’t confuse this with arithmetic — $1 + 1 = 1$ in Boolean algebra, since both operands being true makes the OR true.

Laws

The laws come in dual pairs related by the duality principle: swap every $\land$ with $\lor$ and every $0$ with $1$ , and a true law stays true.

Identity

$X \land 1 = X X \lor 0 = X$

Annihilation (domination)

$X \land 0 = 0 X \lor 1 = 1$

Complementation

$X \land \neg X = 0 X \lor \neg X = 1$

The second identity is heavily used: any expression OR’d with the missing case completes to $1$ . That’s how the Karnaugh Map grouping rule works — it absorbs a variable.

Involution

$\neg (\neg X) = X$

Two negations cancel. In circuits, a NOT followed by a NOT is wire.

Idempotence

$X \land X = X X \lor X = X$

Boolean variables don’t have powers — $X$ AND’d with itself is just $X$ .

Commutativity

$X \land Y = Y \land X X \lor Y = Y \lor X$

Associativity

$X \land (Y \land Z) = (X \land Y) \land Z X \lor (Y \lor Z) = (X \lor Y) \lor Z$

Distributivity

$X \land (Y \lor Z) = (X \land Y) \lor (X \land Z) X \lor (Y \land Z) = (X \lor Y) \land (X \lor Z)$

The OR-over-AND form ( $X \lor (Y \land Z) = (X \lor Y) \land (X \lor Z)$ ) is the one that surprises people coming from arithmetic — it has no analog in regular algebra.

Absorption

$X \land (X \lor Y) = X X \lor (X \land Y) = X$

If $X$ is in there, the smaller term wins.

Minimization (redundancy)

$(X \lor Y) \land (X \lor \neg Y) = X (X \land Y) \lor (X \land \neg Y) = X$

The cases for $Y$ and $\neg Y$ are exhaustive — together they cover everything, so $Y$ drops out.

Consensus

$(X \lor Y) \land (\neg X \lor Z) \land (Y \lor Z) = (X \lor Y) \land (\neg X \lor Z)$

$(X \land Y) \lor (\neg X \land Z) \lor (Y \land Z) = (X \land Y) \lor (\neg X \land Z)$

The third term is implied by the first two and can be dropped.

De Morgan’s laws

$\neg (X \lor Y) = \neg X \land \neg Y \neg (X \land Y) = \neg X \lor \neg Y$

How you push a negation through a parenthesis. These are the workhorses of converting between NAND/NOR forms and AND/OR forms.

Useful simplification identities

A few shortcuts that come up constantly when minimizing:

$A + \overline{A} X = A + X$

$A + CB = (A + B) (A + C)$

If a set of minterms covers every possible input combination, their OR is $1$ :

$x_{1} x_{2} + \overline{x_{1}} x_{2} + x_{1} \overline{x_{2}} + \overline{x_{1}} \overline{x_{2}} = 1$

These come from the laws above but it’s faster to recognize them as patterns than to derive them every time.

Idriss Rami — Notes

Explorer