Boolean algebra and simplification

The laws worth memorising

Identity: $A+0=A$, $A\cdot1=A$. Null: $A+1=1$, $A\cdot0=0$. Idempotent: $A+A=A$, $A\cdot A=A$. Complement: $A+\overline{A}=1$, $A\cdot\overline{A}=0$. Double negation: $\overline{\overline{A}}=A$.

The three that do the real work

Distributive: $A\cdot(B+C)=AB+AC$ and, less obviously, $A+(B\cdot C)=(A+B)\cdot(A+C)$. Absorption: $A+AB=A$ and $A\cdot(A+B)=A$. De Morgan: $\overline{A+B}=\overline{A}\cdot\overline{B}$ and $\overline{A\cdot B}=\overline{A}+\overline{B}$ — break the bar, change the sign.

Why simplify

Fewer gates means lower cost, lower power, less heat and a faster circuit because the signal passes through fewer levels. Questions almost always ask for the practical reason as well as the algebra.

Karnaugh maps

For up to four variables a K-map is faster and safer than algebra. Label rows and columns in Gray code ($00,01,11,10$) so adjacent cells differ in one variable. Group 1s in rectangles of $1,2,4,8$ — as large as possible, overlapping allowed, wrapping around edges allowed. Each group drops the variable that changes within it. A variable that stays 0 throughout the group appears complemented; one that stays 1 appears plain.

Checking your answer

Always verify a simplification against the original truth table, or at least against the rows where the output is 1. An algebraic slip is invisible until you test it.