Boolean Algebra

Overview

Boolean algebra is the mathematical framework for reasoning about logic functions. It operates on binary variables with the operations AND (·), OR (+), and NOT (overbar). The precedence rule is: NOT binds tightest, then AND, then OR. So $a \cdot b + c$ means $(a \cdot b) + c$, not $a \cdot (b + c)$.

A combinational logic circuit has no internal stored state (no memory); its output depends solely on its current inputs. Boolean algebra describes the behaviour of such circuits and allows us to simplify them.

Basic Identities

Identities Involving Constants

Name	Identity	Meaning
OR with 0	$a + 0 = a$	OR-ing with FALSE leaves $a$ unchanged
AND with 0	$a \cdot 0 = 0$	AND-ing with FALSE always gives FALSE
OR with 1	$a + 1 = 1$	OR-ing with TRUE always gives TRUE
AND with 1	$a \cdot 1 = a$	AND-ing with TRUE leaves $a$ unchanged

Complementation

Name	Identity	Meaning
Complement	$a + \bar{a} = 1$	A variable OR its complement is always TRUE
	$a \cdot \bar{a} = 0$	A variable AND its complement is always FALSE

Idempotence

Name	Identity	Meaning
	$a + a = a$	OR-ing a variable with itself gives the variable
	$a \cdot a = a$	AND-ing a variable with itself gives the variable

Involution (Double Complement)

$\overline{\overline{a}} = a$

Complementing twice returns the original value. This is also why two bubbles in series cancel.

Commutative, Associative, and Distributive Laws

Commutative

$a + b = b + a$ $a \cdot b = b \cdot a$

The order of operands does not matter for AND or OR.

Associative

$(a + b) + c = a + (b + c)$ $(a \cdot b) \cdot c = a \cdot (b \cdot c)$

Grouping does not matter, so we write $a + b + c$ or $a \cdot b \cdot c$ without parentheses.

Distributive

Boolean algebra has two distributive laws, and the second one has no analogue in ordinary algebra:

$a \cdot (b + c) = (a \cdot b) + (a \cdot c)$ $a + (b \cdot c) = (a + b) \cdot (a + c) \qquad \text{(NEW: not true in ordinary algebra)}$

The second law can be verified by truth table or algebraic expansion:

$(a + b) \cdot (a + c) = a \cdot a + a \cdot c + b \cdot a + b \cdot c = a + a \cdot c + a \cdot b + b \cdot c = a + b \cdot c$

where the last step uses absorption (below).

Absorption Laws

$a + (a \cdot c) = a$ $a \cdot (a + c) = a$

Proof of the first: $a + a \cdot c = a \cdot 1 + a \cdot c = a \cdot (1 + c) = a \cdot 1 = a$.

Proof of the second: $a \cdot (a + c) = a \cdot a + a \cdot c = a + a \cdot c = a$ (using idempotence and the first absorption law).

Intuition: in $a + a \cdot c$, if $a = 1$ the output is 1 regardless of $c$; if $a = 0$ then $a \cdot c = 0$ and $0 + 0 = 0$. So the output is always exactly $a$.

De Morgan’s Theorem (Preview)

De Morgan’s theorem tells us how to push complements through AND and OR:

$\overline{a + b} = \bar{a} \cdot \bar{b}$ $\overline{a \cdot b} = \bar{a} + \bar{b}$

This is treated in full in the De Morgan’s Theorem note. For now, note its algebraic role: it allows us to transform AND expressions into OR expressions and vice versa.

Worked Simplification Examples

Example 1: $a \cdot b \cdot c + a \cdot b \cdot \bar{c}$

$$\begin{aligned} a \cdot b \cdot c + a \cdot b \cdot \bar{c} &= a \cdot b \cdot (c + \bar{c}) \quad \text{(factor } a \cdot b \text{)} \\ &= a \cdot b \cdot 1 \quad \text{(complement: } c + \bar{c} = 1 \text{)} \\ &= a \cdot b \end{aligned}$$

The two terms differ only in the complementation of $c$; they combine to eliminate $c$ entirely. This technique, factoring out common literals and applying $x + \bar{x} = 1$, is the core algebraic simplification method.

Example 2: Show $a \cdot (\bar{a} + b) = a \cdot b$

$$\begin{aligned} a \cdot (\bar{a} + b) &= a \cdot \bar{a} + a \cdot b \quad \text{(distribute } a \text{)} \\ &= 0 + a \cdot b \quad \text{(complement: } a \cdot \bar{a} = 0 \text{)} \\ &= a \cdot b \end{aligned}$$

The term $a \cdot \bar{a}$ vanishes because a variable AND its complement is always 0.

Example 3: Show $a + (\bar{a} \cdot b) = a + b$

$$\begin{aligned} a + (\bar{a} \cdot b) &= (a + \bar{a}) \cdot (a + b) \quad \text{(distribute OR over AND)} \\ &= 1 \cdot (a + b) \quad \text{(complement: } a + \bar{a} = 1 \text{)} \\ &= a + b \end{aligned}$$

This uses the “new” distributive law $a + (b \cdot c) = (a + b) \cdot (a + c)$, which has no parallel in ordinary arithmetic.

Example 4: Simplify $x \cdot y + y \cdot z + x \cdot z + x \cdot y \cdot z$

We use the technique of expanding each term to include all variables (by multiplying terms by $(v + \bar{v}) = 1$ for missing variables), then cancelling:

First, expand every term to include $x$, $y$, and $z$:

• $x \cdot y = x \cdot y \cdot (z + \bar{z}) = x \cdot y \cdot z + x \cdot y \cdot \bar{z}$
• $y \cdot z = (x + \bar{x}) \cdot y \cdot z = x \cdot y \cdot z + \bar{x} \cdot y \cdot z$
• $x \cdot z = x \cdot (y + \bar{y}) \cdot z = x \cdot y \cdot z + x \cdot \bar{y} \cdot z$
• $x \cdot y \cdot z$ is already fully expanded

Now list all minterms:

$x \cdot y \cdot z$ (from $xy$), $x \cdot y \cdot \bar{z}$ (from $xy$), $x \cdot y \cdot z$ (from $yz$), $\bar{x} \cdot y \cdot z$ (from $yz$), $x \cdot y \cdot z$ (from $xz$), $x \cdot \bar{y} \cdot z$ (from $xz$), $x \cdot y \cdot z$ (from $xyz$).

Removing duplicates, the distinct minterms are: $x \cdot y \cdot z$, $x \cdot y \cdot \bar{z}$, $\bar{x} \cdot y \cdot z$, $x \cdot \bar{y} \cdot z$.

Group:

$x \cdot y \cdot z + x \cdot y \cdot \bar{z} + \bar{x} \cdot y \cdot z + x \cdot \bar{y} \cdot z$ $= x \cdot y \cdot (z + \bar{z}) + y \cdot z \cdot (x + \bar{x})$ $= x \cdot y + y \cdot z$

So the original expression simplifies to $x \cdot y + y \cdot z$.

Consensus Theorem

The consensus theorem states:

$a \cdot b + \bar{a} \cdot c + b \cdot c = a \cdot b + \bar{a} \cdot c$

The term $b \cdot c$ is the consensus of $a \cdot b$ and $\bar{a} \cdot c$: it is formed by taking the AND of all literals that appear in both terms, excluding the variable and its complement ($a$ and $\bar{a}$). The consensus term is redundant and can be added or removed without changing the function.

Proof

$$\begin{aligned} a \cdot b + \bar{a} \cdot c + b \cdot c &= a \cdot b + \bar{a} \cdot c + b \cdot c \cdot (a + \bar{a}) \quad \text{(multiply } b \cdot c \text{ by 1)} \\ &= a \cdot b + \bar{a} \cdot c + a \cdot b \cdot c + \bar{a} \cdot b \cdot c \quad \text{(distribute)} \\ &= (a \cdot b + a \cdot b \cdot c) + (\bar{a} \cdot c + \bar{a} \cdot b \cdot c) \quad \text{(rearrange)} \\ &= a \cdot b \cdot (1 + c) + \bar{a} \cdot c \cdot (1 + b) \quad \text{(factor)} \\ &= a \cdot b + \bar{a} \cdot c \quad \text{(since } 1 + x = 1 \text{)} \end{aligned}$$

Dual Form

The dual of the consensus theorem (swap AND with OR, 0 with 1) gives:

$(a + b) \cdot (\bar{a} + c) \cdot (b + c) = (a + b) \cdot (\bar{a} + c)$

The dual can be proven by applying De Morgan’s theorem to both sides of the original, or by a similar algebraic expansion.

Using Consensus: Adding and Eliminating Terms

The theorem works in both directions:

• Elimination: If you see $a \cdot b + \bar{a} \cdot c + b \cdot c$, remove $b \cdot c$ to get $a \cdot b + \bar{a} \cdot c$.
• Addition: If you have $a \cdot b + \bar{a} \cdot c$ and need to combine it with other terms, you can add $b \cdot c$ without changing the function (useful for hazard removal, see Hazard Removal).

Example: Simplify $a \cdot b + \bar{a} \cdot c + b \cdot c + \bar{b} \cdot c + a \cdot \bar{b}$.

First, identify consensus terms. The term $b \cdot c$ is the consensus of $a \cdot b$ and $\bar{a} \cdot c$, so it can be removed. After removal: $a \cdot b + \bar{a} \cdot c + \bar{b} \cdot c + a \cdot \bar{b}$.

Now examine what remains. The term $\bar{b} \cdot c$ and $a \cdot \bar{b}$ look for consensus with others. But note that $\bar{a} \cdot c + \bar{b} \cdot c = \bar{a} \cdot c$ does not directly give consensus removal. In this case further algebraic inspection (or a K-map) reveals the minimal form.

Example with clear elimination: Simplify $a \cdot b + \bar{a} \cdot c + b \cdot c + \bar{b} \cdot c$.

The term $b \cdot c$ is consensus of $a \cdot b$ and $\bar{a} \cdot c$ (remove it). Check if $\bar{b} \cdot c$ is consensus of any pair: no obvious pair. Result: $a \cdot b + \bar{a} \cdot c + \bar{b} \cdot c$. Further, note $\bar{a} \cdot c + \bar{b} \cdot c = (\bar{a} + \bar{b}) \cdot c$, which cannot be simplified further without additional context. The final expression depends on the specific terms.

Summary of Boolean Laws

Law	OR form	AND form
Identity	$a + 0 = a$	$a \cdot 1 = a$
Null	$a + 1 = 1$	$a \cdot 0 = 0$
Idempotence	$a + a = a$	$a \cdot a = a$
Complement	$a + \bar{a} = 1$	$a \cdot \bar{a} = 0$
Involution	$\overline{\overline{a}} = a$
Commutative	$a + b = b + a$	$a \cdot b = b \cdot a$
Associative	$(a+b)+c = a+(b+c)$	$(a \cdot b) \cdot c = a \cdot (b \cdot c)$
Distributive	$a + b \cdot c = (a+b) \cdot (a+c)$	$a \cdot (b+c) = a \cdot b + a \cdot c$
Absorption	$a + a \cdot b = a$	$a \cdot (a+b) = a$
De Morgan	$\overline{a+b} = \bar{a} \cdot \bar{b}$	$\overline{a \cdot b} = \bar{a} + \bar{b}$
Consensus	$a \cdot b + \bar{a} \cdot c + b \cdot c = a \cdot b + \bar{a} \cdot c$	$(a+b) \cdot (\bar{a}+c) \cdot (b+c) = (a+b) \cdot (\bar{a}+c)$