Exercises — Boolean algebra laws (commutative, associative, distributive)

WHAT: We swapped the order of the two operands of an OR. WHICH LAW: the commutative law (OR form). WHY it holds: $A+B=\max (A,B)$, and $\max$ doesn't care about order — the bigger of two numbers is the bigger no matter which you read first. Answer: Commutative law.

WHAT: Only the brackets (grouping) moved; the operator is AND throughout and the order of $P,Q,R$ is unchanged. WHICH LAW: associative law (AND form). WHY: $\min (\min (P,Q),R)=\min (P,Q,R)=\min (P,\min (Q,R))$ — the smallest of three numbers is the same whichever pair you compare first. Answer: Associative law.

WHAT: The $A$ was "shared out" across both terms inside the bracket. WHICH LAW: distributive law, AND over OR. This is the one that looks exactly like ordinary school algebra. Answer: Distributive law (AND over OR).

WHAT & WHY, term by term:

• $C\cdot A=A\cdot C$ — commutative (AND), lets $A$ lead.
• $B\cdot A=A\cdot B$ — commutative (AND), same reason. Result: $A\cdot C+A\cdot B$. Now $A$ is visibly common in both products, which is the setup for factoring later. Answer: $\mathbf{A}\cdot \mathbf{C}+\mathbf{A}\cdot \mathbf{B}$.

WHAT: Share $X$ into each term of the three-term OR. WHY three terms is fine: by associativity $Y+Z+W$ is one big OR $(Y+Z)+W$, and distribution splits over every OR term. Result: $X\cdot Y+X\cdot Z+X\cdot W$.

WHAT: Use the "weird" Boolean form $A+B\cdot C=(A+B)\cdot (A+C)$. Match up: $A=P$, $B=Q$, $C=R$. Result: $(P+Q)\cdot (P+R)$. WHY the $P$ appears twice: the lone term $P$ must be OR-ed into both brackets — it copies, it doesn't split. Answer: $(\mathbf{P}+\mathbf{Q})(\mathbf{P}+\mathbf{R})$.

• $A\cdot B+A\cdot \overline{B}=A\cdot (B+\overline{B})$ — distributive (factor out $A$).
• $B+\overline{B}=1$ — complement law (from Boolean Algebra Identity & Null Laws): a bit OR its own flip is always 1.
• $A\cdot 1=A$ — identity law. Result: $\mathbf{A}$. Two AND gates + one OR gate collapse to a bare wire.

Group the first two (they share $A\cdot B$):

• $A\cdot B\cdot C+A\cdot B\cdot \overline{C}=A\cdot B\cdot (C+\overline{C})$ — distributive.
• $C+\overline{C}=1$, so $=A\cdot B\cdot 1=A\cdot B$ — identity. Now combine with the last term:
• $A\cdot B+A\cdot \overline{B}=A\cdot (B+\overline{B})=A\cdot 1=A$ — distributive then complement then identity. Result: $\mathbf{A}$.

• $A+A\cdot B=A\cdot 1+A\cdot B$ — identity, writing $A$ as $A\cdot 1$ so a common $A$ appears.
• $=A\cdot (1+B)$ — distributive (factor $A$).
• $=A\cdot 1$ — null law $1+B=1$ (OR with 1 is always 1).
• $=A$ — identity. $■$ WHY this matters: the whole $A\cdot B$ term vanished — the $B$-gate was wasted silicon.

WHAT — factor in stages. Group by the first letter using commutativity to line things up:

• $A\cdot C+A\cdot D=A\cdot (C+D)$ — distributive.
• $B\cdot C+B\cdot D=B\cdot (C+D)$ — distributive. So $Y=A\cdot (C+D)+B\cdot (C+D)$. Now $(C+D)$ is a common factor — factor it out (distributive again): $Y=(A+B)\cdot (C+D).$ Gate count:
• Before: 4 ANDs + 1 OR (4-input) $=5$ gates.
• After: 1 OR ($A+B$) + 1 OR ($C+D$) + 1 AND $=3$ gates. Saved: 2 gates, and the widest gate shrank from 4-input to 2-input. Same truth table, cheaper chip — the payoff Combinational Circuit Simplification chases.

WHAT: Apply $A+X\cdot Y=(A+X)(A+Y)$ but with $X=B$, $Y=C\cdot D$:

• $A+B\cdot (C\cdot D)=(A+B)\cdot (A+C\cdot D)$. Now expand the right bracket the same way, $A+C\cdot D=(A+C)(A+D)$:
• $=(A+B)\cdot (A+C)\cdot (A+D)$. Result: $(\mathbf{A}+\mathbf{B})(\mathbf{A}+\mathbf{C})(\mathbf{A}+\mathbf{D})$ — the lone $A$ copied into every bracket.

• $A=B=C=0$: LHS $(0+0)+0=0$; RHS $0+(0+0)=0$. ✓
• $A=1,B=0,C=0$: LHS $(1+0)+0=1$; RHS $1+(0+0)=1$. ✓ WHY it can never break: both sides equal $\max (A,B,C)$ regardless of the values. There are only $2^3=8$ possible input rows and every one gives LHS=RHS, because "the biggest of three bits" is a single well-defined number. Degenerate (all-zero) inputs are just one of those 8 rows — nothing special. Associativity is total, not conditional.

Find a counterexample: try $A=1,B=0,C=0$.

• Correct value: $A+B\cdot C=1+0\cdot 0=1+0=1$.
• Student's form: $(A+B)\cdot C=(1+0)\cdot 0=1\cdot 0=0$. $1\ne 0$ → the identity is false. Correct identity: $A+B\cdot C=(A+B)\cdot (A+C)$. Re-test that same row: $(1+0)(1+0)=1\cdot 1=1$ ✓. The lone $A$ must live in both brackets.

Start from the RHS and reach the LHS:

• $(A+B)(A+C)=A\cdot A+A\cdot C+B\cdot A+B\cdot C$ — AND-over-OR distributive, expand fully.
• $=A+A\cdot C+A\cdot B+B\cdot C$ — idempotent $A\cdot A=A$; commutative $B\cdot A=A\cdot B$.
• $=A\cdot (1+C+B)+B\cdot C$ — factor $A$ from the first three terms (distributive), writing the bare $A$ as $A\cdot 1$.
• $=A\cdot 1+B\cdot C$ — null law $1+C+B=1$ (OR with 1 is always 1).
• $=A+B\cdot C$ — identity $A\cdot 1=A$. $■$ This is exactly the algebraic proof previewed in the parent note — now every single line is justified.

Can you now, without notes:

• Factor $A\cdot B+A\cdot C$ and state the gate saving? ::: Yes → $A(B+C)$, 3 gates down to 2.
• Break $A+BC=(A+B)C$ with one input? ::: Yes → $A=1,B=0,C=0$ gives $1\ne 0$.
• Refactor $AC+AD+BC+BD$? ::: Yes → $(A+B)(C+D)$, 5 gates down to 3.