2.4 Boolean Algebra, Gates, and Circuits

Sections 2.1 and 2.2 used propositions that were either true or false. A digital system stores the same two possibilities as bits: $1$ for true and $0$ for false. Boolean algebra gives us rules for calculating with these values, and logic gates turn those rules into circuits.

A combinational circuit can be read as a directed dependency diagram: input signals feed gates, and wires carry each result to the next gate. Chapter 11 will later formalize diagrams like this as graphs with vertices and edges; here, an arrow simply shows which signal must be available before another can be computed.

Boolean values and variables

The Boolean domain is

A Boolean variable such as $x$ takes exactly one value from $\mathbb B$. A Boolean function

receives $n$ Boolean inputs and produces one Boolean output.

For example, a two-input function has four possible input assignments because

A truth table lists the output for every assignment. With $n$ inputs, it has $2^n$ input rows.

NOT, AND, and OR

The three basic Boolean operations match the logical connectives from Sections 2.1 and 2.2.

NOT, written $\neg x$, reverses one value:

AND, written $x\land y$, equals $1$ only when both inputs are $1$.

OR, written $x\lor y$, equals $1$ when at least one input is $1$.

An electronic logic gate implements one Boolean operation. A NOT gate has one input. AND and OR gates may have two or more inputs; this section uses two-input gates unless stated otherwise.

Evaluating an expression step by step

Consider

Parentheses specify the dependency order. For input $(x,y,z)=(1,0,0)$:

1. compute $\neg y=\neg0=1$;

2. compute $x\land\neg y=1\land1=1$;

3. compute $(x\land\neg y)\lor z=1\lor0=1$.

The output is therefore $f(1,0,0)=1$.

Without parentheses, use the precedence order

Thus $\neg x\land y\lor z$ means $((\neg x)\land y)\lor z$.

From expressions to circuits

To build a circuit for $(x\land\neg y)\lor z$:

1. send $y$ through a NOT gate;

2. send $x$ and $\neg y$ into an AND gate;

3. send the AND output and $z$ into an OR gate.

Each wire carries one Boolean signal. A gate cannot calculate until all of its input signals are available. Because this is a combinational circuit, its output depends only on the current inputs, not on earlier inputs.

The dependency arrows must not loop back to a gate that is still being evaluated. Such a loop would make a current output depend immediately on itself. Chapter 11 will call a dependency diagram without these loops acyclic; Chapter 12 will introduce stored state so that controlled feedback can have a precise meaning over time.

Send three live input signals through two configurable gate stages. Toggle the inputs and their inverters, choose each gate type, and watch the labeled signals, stage-by-stage evaluation, output, and truth table update immediately.

Boolean identities

Two Boolean expressions are equivalent when they produce the same output for every input assignment. We write

A truth table can prove equivalence by comparing the two output columns row by row. Boolean identities let us make the same transformations algebraically.

For $x,y,z\in\mathbb B$:

The De Morgan laws move a negation through parentheses while swapping AND and OR:

For example,

The first expression needs two AND gates, one NOT gate, and one OR gate. The simplified expression is just the wire carrying $x$. Equivalent functions can have very different circuit costs.

NAND and NOR are universal

A NAND gate computes

A NOR gate computes

A gate type is functionally complete when circuits using only that type can implement every Boolean function. NAND alone is functionally complete because

and OR can then be constructed with De Morgan's law. NOR has a dual construction.

Building a function from its truth table

A literal is a variable or its negation, such as $x$ or $\neg x$. A minterm is an AND of literals that equals $1$ on exactly one truth-table row.

For row $(x,y,z)=(1,0,1)$, the minterm is

It selects that row because each literal requires the stated input value.

To build any Boolean function from a truth table:

1. write one minterm for every row whose output is $1$;

2. join those minterms with OR.

The result is disjunctive normal form (DNF), also called a sum-of-products form.

Suppose $f(x,y)=1$ on rows $01,10,11$. Then

Algebraic simplification gives

DNF guarantees a correct construction; simplification reduces its cost.

XOR and the half-adder

Exclusive OR, written $x\oplus y$, equals $1$ exactly when the inputs differ:

A half-adder adds two one-bit numbers $x$ and $y$. Its outputs are:

for the sum bit, and

for the carry bit.

The two outputs illustrate that a circuit may implement several Boolean functions over the same inputs.

Choose a two- or three-input target and paint the output rows that should equal \(1\). The forge turns each selected row into a minterm, builds the canonical DNF circuit live, counts its literals and mismatches, and confirms when every truth-table row agrees with the target.

From current signals to remembered state

Boolean algebra explains how current inputs produce current outputs. A combinational circuit has no memory: applying the same inputs always produces the same outputs.

Traffic lights, login protocols, vending machines, and communication controllers must remember what happened earlier. Chapter 12 will add a finite state variable so that the same current input can cause different actions in different states. Before then, Chapter 3 develops the proof methods needed to justify Boolean identities and the other claims made throughout the course.