Boolean Algebra

Boolean algebra, formulated by George Boole in 1854, is a system of algebra built entirely around a choice between exactly two options -- yes/no, or high/low -- represented by the binary digits 0 and 1; its value for digital circuit design was only fully realised much later, but today's entire digital world rests on it. (The high/low, 1/0 idea itself is older than Boole's algebra in application: Claude Shannon applied it to telephone switching circuits as early as 1938.) The three basic Boolean operations -- NOT ($\overline{A}$), OR ($A+B$) and AND ($A\cdot B$) -- obey a compact set of laws. The COMPLEMENT law: $A\cdot\overline{A}=0$ and $A+\overline{A}=1$ (a variable ANDed with its own complement is always 0; ORed with its own complement is always 1). The OR laws: $A+0=A$, $A+1=1$, $A+A=A$, $A+\overline{A}=1$. The AND laws: $A\cdot0=0$, $A\cdot1=A$, $A\cdot A=A$, $A\cdot\overline{A}=0$. And three further structural laws mirror ordinary arithmetic algebra: COMMUTATIVE ($A+B=B+A$ and $A\cdot B=B\cdot A$), ASSOCIATIVE ($A+(B+C)=(A+B)+C$ and $A\cdot(B\cdot C)=(A\cdot B)\cdot C$), and DISTRIBUTIVE ($A(B+C)=AB+AC$ and $A+BC=(A+B)(A+C)$ -- the second distributive form has no ordinary-arithmetic analogue and is a genuinely Boolean-specific identity). These laws are the toolkit used to simplify complicated logic expressions -- and, correspondingly, to simplify the physical logic circuitry that implements them, since fewer terms in the simplified expression generally means fewer physical gates needed to build it. …