Boolean Algebra

Algebra With Only Two Numbers

Ordinary algebra manipulates symbols standing for numbers. Boolean algebra does the same thing over a domain of exactly two elements. In it, “the values of the variables are the truth values true and false, usually denoted by 1 and 0.” The operations are three: “conjunction (and) denoted as $\wedge$, disjunction (or) denoted as $\vee$, and negation (not) denoted as $\neg$.” That is the entire alphabet. Everything a digital computer decides is written in it.

Note

The payload: Boolean algebra “is a formal way of describing logical operations in the same way that elementary algebra describes numerical operations.” Because the structure is defined by its laws rather than its objects, the same algebra is being obeyed by logical propositions, by set operations, and by physical switches at once. Prove an identity in one and it holds in all three. Simplifying a Boolean expression and minimizing a circuit are literally the same act.

The Operations and Their Laws

The three operations satisfy a fixed set of identities. The ones that do real work:

Law	Form
Commutativity	$x\wedge y=y\wedge x$, $x\vee y=y\vee x$
Associativity	$(x\wedge y)\wedge z=x\wedge (y\wedge z)$
Distributivity	$x\wedge (y\vee z)=(x\wedge y)\vee (x\wedge z)$
Identity	$x\wedge 1=x$, $x\vee 0=x$
Complement	$x\wedge \neg x=0$, $x\vee \neg x=1$
Idempotence	$x\wedge x=x$, $x\vee x=x$
Absorption	$x\wedge (x\vee y)=x$

Distributivity is where Boolean algebra departs from the numbers: in ordinary arithmetic $\wedge$ (as multiplication) distributes over $\vee$ (as addition), but the reverse fails. In Boolean algebra it holds both ways, so $\vee$ also distributes over $\wedge$.

De Morgan’s Laws

The single most used pair. Negation turns each operation into the other:

$(\neg x)\wedge (\neg y)=\neg (x\vee y)(\neg x)\vee (\neg y)=\neg (x\wedge y)$

Wikipedia states both forms in exactly this shape. They are the algebraic engine behind rewriting conditions in code: “not (a or b)” becomes “not a and not b,” which is how a compiler or a careful programmer pushes negations inward and flattens branch logic. They also come straight out of the truth tables, since Boolean algebra and propositional logic are the same laws under different names.

Simplification

Minimizing an expression means applying these identities until no shorter equivalent remains. $x\vee (x\wedge y)$ collapses to $x$ by absorption. $x\wedge (\neg x\vee y)$ reduces to $x\wedge y$. Each removed term is a gate not built, so simplification is not cosmetic: it sets the transistor count of the final circuit.

The Bridge to Digital Logic

Boolean algebra “is used in digital electronics, and is provided for in all modern programming languages.” That is not a coincidence of notation. Claude Shannon showed in 1937 that the algebra of switches is exactly Boole’s algebra of logic: a series connection is AND, a parallel connection is OR, and a normally-closed relay is NOT. Every logic gate is one Boolean operator in silicon, and a minimized Boolean expression is a minimized gate netlist.

Example

Simplify $F=(x\wedge y)\vee (x\wedge \neg y)$. Factor $x$ out by distributivity: $F=x\wedge (y\vee \neg y)$. By complement, $y\vee \neg y=1$, so $F=x\wedge 1=x$. Two AND gates and an OR gate reduce to a bare wire carrying $x$. The truth table would have shown $F$ equals $x$ in all four rows; the algebra reaches the same conclusion without enumerating them.

Related Notes

• Propositional Logic - the same two-valued algebra presented as connectives and truth tables
• Set Theory Basics - union, intersection, and complement obey these identities one for one
• George Boole and the Algebra of Logic - the historical origin of the two-valued system
• Shannon’s Switching Thesis - the proof that this algebra is the mathematics of circuits

Sources

• Boolean algebra (Wikipedia) - the two truth values, the three operations, De Morgan’s laws, and the link to digital electronics and programming languages.