Switching Circuits

Every Boolean function of one or more variables is realized by a formula. A certain class of electrical devices computes exactly the Boolean functions as well, so the algebra of formulas becomes the algebra of circuit design.¹

Consider a device — traditionally a black box — with $n$ inputs and one output, where every wire carries one of two values, $F$ and $T$ (say $0$ and $1$ volts). Assume the device has no memory: its output depends only on the present inputs, not on past history. Then its behavior is a Boolean function

G (X_{1}, \dots, X_{n}) = the output level for inputs X_{1}, \dots, X_{n} .

Such devices are the combinational part of digital circuitry. The basic gates realize the basic functions: the two-input AND gate outputs the minimum of its inputs (realizing $\land$ ), the OR gate outputs the maximum (realizing $\lor$ ), and the NOT gate, or inverter, outputs the opposite of its single input (realizing $\neg$ ).

The three basic gates and the Boolean functions they realize: AND outputs the smaller of its two inputs, OR the larger, and NOT the opposite of its single input.

Circuits and formulas

Wire gates together and the output wire carries a value that is a Boolean function of the inputs. Labeling each internal wire with the wff computing its value, the circuit comes to look like the formation tree of the output formula: each gate is one formula-building operation, each input wire a sentence symbol. Conversely, a wff prescribes a circuit — one gate per connective.

A formula drawn as a gate network. The shared AND gate computing (A and B) feeds two later gates, so the common subformula is built once rather than duplicated.

The figure realizes $((A \land B) \land D) \lor ((A \land B) \land (\neg C))$ . The subformula $A \land B$ occurs twice in the wff, but the circuit computes it once and fans the result out to both later gates — a first sign that the formula and the cheapest circuit for it are not the same object.

Series, parallel, and relays

In the older relay model the primitives are switches rather than gates. A switch labeled $A$ is closed when $A$ is $T$ . Current reaches the output when a closed path exists from input to output, so the two ways of combining switches realize the two binary connectives.

Series switches pass current iff both are closed: conjunction.
Parallel switches pass current iff either is closed: disjunction.

The two switch combinations realize the two connectives: switches in series conduct only when both are closed (AND), switches in parallel conduct when either is closed (OR).

A relay circuit for $A \leftrightarrow B$ is $(A \land B) \lor ((\neg A) \land (\neg B))$ : current passes iff the two inputs agree. Because the biconditional flips value whenever one input flips, this is the circuit behind a hallway light controlled from two switches. Relays differ from gates in one respect: they are bilateral, passing current in either direction, which allows bridge circuits that the gate methods here do not describe.

Cost and delay

Tautologically equivalent formulas realize the same function, so their circuits behave identically at the output — but they can differ in cost (number of gates) and speed. Speed is measured by delay (or depth): the largest number of gates a signal passes through from any input to the output. Delay is computed from the formula by recursion, exactly the pattern of the recursion lesson.

Formula	Delay
sentence symbol	$0$
$\neg α$	$1 + delay (α)$
$α \land β$	$1 + max (delay (α), delay (β))$

The other binary connectives follow the last line.

Two circuits for one function. The left uses three gates on a signal path of length two; the right uses five gates on a path of length four, so equivalent formulas can differ sharply in cost and depth.

The engineer's problem follows: given a target function, find a realizing circuit of minimum cost subject to a delay bound, drawn from an available catalog of devices. If the catalog corresponds to a complete set of connectives, some circuit always exists; the catalog then is a formal language, one connective per device.

Designing and simplifying

Post's theorem gives a first circuit for any specification: build the DNF and wire it up. That circuit is rarely minimal, and tautological equivalences shrink it.

Two circuits for the same majority function. Factoring the shared input out of two AND terms removes one gate at no cost in delay; three gates are provably not enough.

Simplification also exploits don't-care inputs — combinations that never occur, whose output value is free to choose. Enderton's four-input example places the required $T$ s and $F$ s on a coordinate diagram, leaves three squares blank, and finds a region covering all the $T$ s and no $F$ s that corresponds to the simple formula $(\neg A) \lor ((\neg C) \land D)$ — which ignores input $B$ entirely. Choosing the don't-cares to enlarge a clean region is the idea behind Karnaugh-map minimization. Two design problems from single-gate catalogs:

Equality from NOR. Testing $A = B$ with two-input NOR alone: $((A ↓ A) ↓ B) ↓ ((B ↓ B) ↓ A)$ , five gates.
Whether a minimal circuit can be found efficiently is a separate and much harder question, one Enderton only raises; it is the practical face of the intractability foreshadowed by P versus NP.

The five-NOR circuit testing equality of A and B; two gates form the negations, two combine them, and the final gate outputs T exactly when the inputs agree.

The correspondence runs both ways and loses nothing: reasoning about circuits is reasoning about formulas, and the completeness results carry over to hardware, letting a single gate type — a NAND or NOR — implement any specification at all.

Enderton, §1.6 — memoryless devices as Boolean functions, AND/OR/NOT gates, circuits as formation trees, delay by recursion, the cost–delay design problem, the majority and equality examples, the don't-care simplification, and the bilateral-relay caveat. ↩

Circuits and formulas

Series, parallel, and relays

Cost and delay

Designing and simplifying

Footnotes