Boolean Algebra

Why This Matters

A one-bit full adder has three inputs and two outputs. Its carry output is $ab+ac+bc$. Written without Boolean algebra, the same circuit might be drawn from a full truth table with four separate product terms, wasting gates and wire delay.

Chip design tools still start from this algebra. A compiler, hardware description language, or hand schematic turns predicates into Boolean functions $f:\lbrace 0,1\rbrace^n \to \lbrace 0,1\rbrace$, rewrites them using identities, then maps the result to NAND, NOR, multiplexers, lookup tables, or standard cells.

Core Definitions

Operators and Truth Tables

The four operators used constantly are AND, OR, NOT, and XOR. We write AND by juxtaposition or $\cdot$, OR by $+$, NOT by a bar, and XOR by $\oplus$.

XOR differs from OR in exactly one row. For $a=b=1$, OR returns $1$ while XOR returns $0$. This is the source of many bugs when a bit mask operation is mistaken for a logical condition.

A truth table for three inputs has eight rows. The majority-of-three function returns $1$ when at least two inputs are $1$.

The canonical SOP is $f=\bar a b c+a \bar b c+a b \bar c+a b c$. Boolean algebra reduces it to $f=ab+ac+bc$, the carry output of a full adder.

The same operators act on all bits of a machine word in C. This example uses one byte so the layout fits on one line.

#include <stdint.h>
#include <stdio.h>

int main(void) {
    uint8_t x = 0b10110100;
    uint8_t mask = 0b00001111;

    uint8_t low  = x & mask;   // 00000100
    uint8_t set  = x | mask;   // 10111111
    uint8_t flip = x ^ mask;   // 10111011
    uint8_t inv  = (uint8_t)~x; // 01001011

    printf("%02x %02x %02x %02x\n", low, set, flip, inv);
}

Byte layout for the first operation:

x       10110100
mask    00001111
x&mask  00000100

Each output bit is computed independently. Bit 2 survives because both inputs have a $1$ there; bit 7 becomes $0$ because the mask has a $0$.

Algebraic Identities

Boolean algebra has identities similar to ordinary algebra, plus identities that depend on two-valued logic.

The second distributive law, $x+yz=(x+y)(x+z)$, is valid in Boolean algebra but has no direct analogue in ordinary arithmetic. Verify it by cases. If $x=1$, both sides equal $1$. If $x=0$, both sides equal $yz$.

Absorption is the standard cleanup after expanding a circuit expression. Starting from $a+ab$, factor $a(1+b)$. Since $1+b=1$, the expression is $a$. In a circuit this removes the AND gate and the OR gate; the output wire is just $a$.

A small instruction-selection example shows the same algebra in software. Suppose an execution unit should start when valid is true and either is_add or is_sub is true.

uint8_t issue(uint8_t valid, uint8_t is_add, uint8_t is_sub) {
    return valid & (is_add | is_sub);
}

If the decoder guarantees is_add | is_sub only when valid is already true, then valid & (is_add | is_sub) absorbs to is_add | is_sub. That rewrite is legal only with the stated invariant.

De Morgan's Laws and Gate Rewrites

De Morgan's laws move negation across AND and OR.

$\overline{xy}=\bar x+\bar y$

$\overline{x+y}=\bar x\bar y$

They matter because real gate libraries often prefer NAND and NOR gates. A NAND is $\overline{xy}$. A NOR is $\overline{x+y}$. By pushing bubbles through a schematic, a designer can replace mixed NOT, AND, and OR gates with a small number of NAND or NOR gates.

Consider this expression:

$g=\overline{a(b+c)}$

Apply De Morgan twice.

$g=\bar a+\overline{b+c}$

$g=\bar a+\bar b\bar c$

The original circuit has an OR for $b+c$, an AND with $a$, and a final inverter. The rewritten form has three inverters, one AND, and one OR. That is not always fewer gates. But if the target library has cheap NAND gates, implement the original as one OR feeding one NAND, or rewrite the OR itself with NAND gates.

A NAND-only implementation of $b+c$ follows from De Morgan:

$b+c=\overline{\bar b\bar c}$

Using NAND, $\bar b=\operatorname{NAND}(b,b)$ and $\bar c=\operatorname{NAND}(c,c)$. Then $b+c=\operatorname{NAND}(\bar b,\bar c)$.

SOP, POS, and Karnaugh Maps

Canonical SOP is formed from rows where $f=1$. For variables $a,b,c$, row $101$ contributes $a\bar b c$. If $f$ is $1$ on rows $3,5,6,7$, then

$f=\Sigma m(3,5,6,7)$

$f=\bar a b c+a\bar b c+ab\bar c+abc$

After simplification, this becomes $ab+ac+bc$.

Canonical POS is formed from rows where $f=0$. A maxterm is false on exactly one row. For row $a=1,b=0,c=1$, the maxterm is $\bar a+b+\bar c$. The variable is complemented when the row value is $1$, because the OR term must evaluate to $0$ on that row.

For majority-of-three, the zero rows are $0,1,2,4$.

$f=\Pi M(0,1,2,4)$

$f=(a+b+c)(a+b+\bar c)(a+\bar b+c)(\bar a+b+c)$

A Karnaugh map arranges truth-table cells so adjacent cells differ in one variable. For four variables, use Gray-code order $00,01,11,10$ on both axes. Let $f(A,B,C,D)=1$ on minterms $0,2,5,7,8,10,13,15$.

The four corner cells form one wraparound group. They share $B=0$ and $D=0$, so the term is $\bar B\bar D$. The central $2 \times 2$ group shares $B=1$ and $D=1$, so the term is $BD$. Thus $f=\bar B\bar D+BD$, which is $B$ XNOR $D$. Inputs $A$ and $C$ vanished.

Algorithmic Minimization

Karnaugh maps work well for three or four variables. Five variables are possible but error-prone. More inputs need algorithms.

Quine-McCluskey groups minterms by the number of $1$ bits, combines terms that differ in one position, and repeats until no more combinations exist. A dash means the variable disappeared.

m0  0000
m2  0010  combine with m0  00-0
m8  1000  combine with m0  -000
m10 1010  combine with m2  -010

00-0 and 10-0 combine to -0-0

The implicant -0-0 means $B=0,D=0$, so it represents $\bar B\bar D$. Repeating the process for minterms $5,7,13,15$ gives -1-1, which represents $BD$.

Quine-McCluskey is exact, but the prime implicant chart can grow fast. Espresso, introduced by Brayton and coauthors, is a heuristic minimizer for two-level logic. It does not promise the smallest expression for every input, but it handles cases that are too large for hand maps. Binary decision diagrams are another representation of Boolean functions, but they are outside this page.

Main Theorem

Common Confusions

Exercises

References

Canonical:

• Charles Petzold, Code: The Hidden Language of Computer Hardware and Software, 2nd ed. (2022), ch. 10-14, relays, gates, binary addition, and feedback
• David A. Patterson and John L. Hennessy, Computer Organization and Design: The Hardware/Software Interface, 5th ed. (2013), Appendix B, logic design basics and combinational circuits
• M. Morris Mano and Michael D. Ciletti, Digital Design, 5th ed. (2013), ch. 2-3, Boolean algebra, gates, minimization, and combinational logic
• Stephen Brown and Zvonko Vranesic, Fundamentals of Digital Logic with VHDL Design, 3rd ed. (2009), ch. 2-4, Boolean functions, Karnaugh maps, and circuit implementation
• J. Clark Scott, But How Do It Know? The Basic Principles of Computers for Everyone (2009), ch. 1-6, gates, memory, and the path from switches to a computer

Accessible:

• Randy H. Katz and Gaetano Borriello, Contemporary Logic Design, 2nd ed., ch. 2, Boolean algebra and two-level logic
• R. K. Brayton, G. D. Hachtel, C. T. McMullen, and A. L. Sangiovanni-Vincentelli, Logic Minimization Algorithms for VLSI Synthesis (1984), ch. 2-4, exact and heuristic two-level minimization
• UC Berkeley CS61C notes on synchronous digital systems and combinational logic

Next Topics

• /computationpath/logic-gates
• /computationpath/nand-universality
• /computationpath/combinational-circuits
• /topics/propositional-logic
• /topics/sat