---
title: Switching Circuits
module: Sentential Logic
moduleNumber: 2
lessonNumber: 6
order: 206
summary: >
  A memoryless two-valued circuit computes a Boolean function, so every formula
  names a gate network and every network a formula. Cost and delay are read off
  the formula by recursion, and tautological equivalence and normal forms design
  and simplify circuits realizing a given specification.
topics: [Sentential Logic]
sources:
  - book: Enderton
    ref: "Ch. 1 — Sentential Logic; §1.6 Switching Circuits"
draft: false
---

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.[^enderton-circ]

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) = \text{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 $\wedge$), the **OR gate** outputs the maximum (realizing
$\vee$), and the **NOT gate**, or inverter, outputs the opposite of its single
input (realizing $\neg$).

$$
% caption: 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.
\begin{tikzpicture}[font=\footnotesize,
  g/.style={draw=acc, minimum width=15mm, minimum height=12mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[g] (and) at (0,0) {AND};
  \draw[black] (-1.45,0.25)--(-0.75,0.25);
  \draw[black] (-1.45,-0.25)--(-0.75,-0.25);
  \draw[black] (0.75,0)--(1.25,0);
  \node[g] (or) at (3.6,0) {OR};
  \draw[black] (2.15,0.25)--(2.85,0.25);
  \draw[black] (2.15,-0.25)--(2.85,-0.25);
  \draw[black] (4.35,0)--(4.85,0);
  \node[g] (not) at (7.2,0) {NOT};
  \draw[black] (5.75,0)--(6.45,0);
  \draw[black] (7.95,0)--(8.45,0);
\end{tikzpicture}
$$

## 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.

$$
% caption: 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.
\begin{tikzpicture}[font=\footnotesize,
  io/.style={font=\footnotesize},
  gate/.style={draw, minimum width=13mm, minimum height=8mm, align=center, font=\scriptsize},
  sh/.style={draw=acc, text=acc, minimum width=13mm, minimum height=8mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[io] (A) at (0,3.2) {A};
  \node[io] (B) at (0,2.4) {B};
  \node[io] (C) at (0,1.0) {C};
  \node[io] (D) at (0,-0.6) {D};
  \node[sh] (and1) at (2.2,2.8) {AND};
  \node[gate] (not) at (2.2,1.0) {NOT};
  \node[gate] (and2) at (5.0,1.9) {AND};
  \node[gate] (and3) at (5.0,0.2) {AND};
  \node[gate] (or) at (7.6,1.05) {OR};
  \node[io] (out) at (9.3,1.05) {output};
  \draw[black] (A) -- (and1); \draw[black] (B) -- (and1);
  \draw[black] (C) -- (not);
  \draw[acc] (and1) -- (and2);
  \draw[acc] (and1) -- (and3);
  \draw[black] (D) .. controls (3.4,-0.6) and (3.6,1.4) .. (and2);
  \draw[black] (not) -- (and3);
  \draw[black] (and2) -- (or); \draw[black] (and3) -- (or);
  \draw[black] (or) -- (out);
\end{tikzpicture}
$$

The figure realizes $((A \wedge B) \wedge D) \vee ((A \wedge B) \wedge (\neg C))$.
The subformula $A \wedge 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.

$$
% caption: 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).
\begin{tikzpicture}[font=\footnotesize,
  sw/.style={draw, minimum width=9mm, minimum height=6mm, font=\scriptsize}]
  \definecolor{acc}{HTML}{4A6FA5}
  % series
  \node[font=\footnotesize\itshape, text=acc] at (2.0,2.3) {series = AND};
  \fill[black] (0,1.4) circle (1.3pt);
  \draw[black] (0,1.4) -- (0.8,1.4);
  \node[sw] (sa) at (1.4,1.4) {A};
  \draw[black] (2.0,1.4) -- (2.6,1.4);
  \node[sw] (sb) at (3.2,1.4) {B};
  \draw[black] (3.8,1.4) -- (4.6,1.4);
  \fill[black] (4.6,1.4) circle (1.3pt);
  % parallel
  \node[font=\footnotesize\itshape, text=acc] at (8.4,2.85) {parallel = OR};
  \fill[black] (6.4,1.4) circle (1.3pt);
  \draw[black] (6.4,1.4) -- (7.0,1.4) -- (7.0,2.0) -- (7.6,2.0);
  \node[sw] (pa) at (8.2,2.0) {A};
  \draw[black] (8.8,2.0) -- (9.4,2.0) -- (9.4,1.4);
  \draw[black] (7.0,1.4) -- (7.0,0.8) -- (7.6,0.8);
  \node[sw] (pb) at (8.2,0.8) {B};
  \draw[black] (8.8,0.8) -- (9.4,0.8) -- (9.4,1.4);
  \draw[black] (9.4,1.4) -- (10.0,1.4);
  \fill[black] (10.0,1.4) circle (1.3pt);
\end{tikzpicture}
$$

A relay circuit for $A \leftrightarrow B$ is $(A \wedge B) \vee ((\neg A) \wedge
(\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](/logic/sentential-logic/induction-and-recursion).

| Formula | Delay |
| --- | --- |
| sentence symbol | $0$ |
| $\neg\alpha$ | $1 + \text{delay}(\alpha)$ |
| $\alpha \wedge \beta$ | $1 + \max(\text{delay}(\alpha), \text{delay}(\beta))$ |

The other binary connectives follow the last line.

> **Worked example.** Compute the delay of $(A_1 \wedge A_2) \vee (\neg A_3)$ and
> of the equivalent $\neg(A_3 \wedge ((\neg A_1) \vee (\neg A_2)))$ from the delay
> recursion.
>
> For the first formula:
>
> $$
> \begin{aligned}
> \text{delay}(A_1 \wedge A_2) &= 1 + \max(0, 0) = 1, & \text{delay}((\neg A_3)) &= 1,\\
> \text{delay}((A_1 \wedge A_2) \vee (\neg A_3)) &= 1 + \max(1, 1) = 2. &&
> \end{aligned}
> $$
>
> For the second:
>
> $$
> \begin{aligned}
> \text{delay}((\neg A_1) \vee (\neg A_2)) &= 1 + \max(1, 1) = 2,\\
> \text{delay}(A_3 \wedge ((\neg A_1) \vee (\neg A_2))) &= 1 + \max(0, 2) = 3,\\
> \text{delay}(\neg(A_3 \wedge ((\neg A_1) \vee (\neg A_2)))) &= 1 + 3 = 4.
> \end{aligned}
> $$
>
> Both realize the same function, one with three gates at delay $2$, the other
> with five gates at delay $4$.

$$
% caption: 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.
\begin{tikzpicture}[font=\footnotesize,
  io/.style={font=\scriptsize},
  g/.style={draw, minimum width=11mm, minimum height=6mm, font=\scriptsize},
  bg/.style={draw=acc, text=acc, minimum width=11mm, minimum height=6mm, font=\scriptsize}]
  \definecolor{acc}{HTML}{4A6FA5}
  % left circuit: 3 gates, delay 2
  \node[io] (la1) at (0,2.4) {A1};
  \node[io] (la2) at (0,1.7) {A2};
  \node[io] (la3) at (0,0.4) {A3};
  \node[g] (land) at (1.5,2.05) {AND};
  \node[g] (lnot) at (1.5,0.4) {NOT};
  \node[bg] (lor) at (3.1,1.3) {OR};
  \node[io] (lout) at (4.2,1.3) {out};
  \draw[black] (la1)--(land); \draw[black] (la2)--(land);
  \draw[black] (la3)--(lnot);
  \draw[black] (land)--(lor); \draw[black] (lnot)--(lor);
  \draw[black] (lor)--(lout);
  \node[text=acc, font=\scriptsize] at (2.1,3.1) {3 gates, delay 2};
  % right circuit: 5 gates, delay 4
  \begin{scope}[xshift=6cm]
  \node[io] (ra1) at (0,2.4) {A1};
  \node[io] (ra2) at (0,1.5) {A2};
  \node[io] (ra3) at (0,0.0) {A3};
  \node[g] (rn1) at (1.4,2.4) {NOT};
  \node[g] (rn2) at (1.4,1.5) {NOT};
  \node[g] (ror) at (2.9,1.95) {OR};
  \node[g] (rand) at (4.3,1.0) {AND};
  \node[bg] (rnot) at (5.7,1.0) {NOT};
  \node[io] (rout) at (6.9,1.0) {out};
  \draw[black] (ra1)--(rn1); \draw[black] (ra2)--(rn2);
  \draw[black] (rn1)--(ror); \draw[black] (rn2)--(ror);
  \draw[black] (ror)--(rand);
  \draw[black] (ra3) .. controls (2.6,0.0) and (3.0,0.6) .. (rand);
  \draw[black] (rand)--(rnot); \draw[black] (rnot)--(rout);
  \node[text=acc, font=\scriptsize] at (3.2,3.1) {5 gates, delay 4};
  \end{scope}
\end{tikzpicture}
$$

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.

> **Worked example.** Build a circuit for the majority of $A, B, C$ (output agrees
> with at least two inputs) from two-input AND and OR gates.
>
> Post's construction disjoins the three pairs, then a factoring shrinks it:
>
> $$
> ((A \wedge B) \vee (A \wedge C)) \vee (B \wedge C) \ \models\mid\models \ (A \wedge (B \vee C)) \vee (B \wedge C).
> $$
>
> The DNF form uses five gates — three AND, two OR — at delay $3$. Factoring $A$
> out of its two conjuncts removes one AND gate: the right side uses four gates at
> the same delay. No three-gate circuit realizes the function, so four is optimal.

$$
% caption: 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.
\begin{tikzpicture}[font=\footnotesize,
  g/.style={draw, minimum width=12mm, minimum height=7mm, font=\scriptsize},
  bg/.style={draw=acc, text=acc, minimum width=12mm, minimum height=7mm, font=\scriptsize}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[font=\footnotesize\itshape] at (2.2,3.0) {5 gates};
  \node[g] (a1) at (1.2,2.2) {AND};
  \node[g] (a2) at (1.2,1.2) {AND};
  \node[g] (a3) at (1.2,0.2) {AND};
  \node[g] (o1) at (3.2,1.7) {OR};
  \node[g] (o2) at (3.6,0.7) {OR};
  \draw[black] (a1)--(o1); \draw[black] (a2)--(o1);
  \draw[black] (o1)--(o2); \draw[black] (a3)--(o2);
  \node[font=\footnotesize\itshape, text=acc] at (8.0,3.0) {4 gates};
  \node[bg] (or) at (6.8,1.5) {OR};
  \node[g] (an) at (8.4,1.5) {AND};
  \node[g] (an2) at (8.4,-0.2) {AND};
  \node[g] (or2) at (10.2,0.65) {OR};
  \draw[black] (or)--(an); \draw[black] (an)--(or2); \draw[black] (an2)--(or2);
\end{tikzpicture}
$$

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) \vee ((\neg C) \wedge 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 \downarrow A) \downarrow B) \downarrow ((B \downarrow B) \downarrow 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](/logic/sentential-logic/truth-assignments-and-tautologies).

> **Worked example.** Verify that
> $((A \downarrow A) \downarrow B) \downarrow ((B \downarrow B) \downarrow A)$
> computes $A \leftrightarrow B$ using two-input NOR ($\downarrow$) alone.
>
> Unfold the NOR gates by stages, with $X \downarrow Y = \neg(X \vee Y)$:
>
> $$
> \begin{aligned}
> A \downarrow A &= \neg A, & (A \downarrow A) \downarrow B &= \neg((\neg A) \vee B) = A \wedge (\neg B),\\
> B \downarrow B &= \neg B, & (B \downarrow B) \downarrow A &= \neg((\neg B) \vee A) = B \wedge (\neg A).
> \end{aligned}
> $$
>
> The outer gate then gives
>
> $$
> (A \wedge (\neg B)) \downarrow (B \wedge (\neg A)) = \neg((A \wedge (\neg B)) \vee (B \wedge (\neg A))),
> $$
>
> the negation of exclusive-or, which is $A \leftrightarrow B$. The circuit uses
> five NOR gates and no other gate type.

$$
% caption: 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.
\begin{tikzpicture}[font=\footnotesize,
  io/.style={font=\scriptsize},
  g/.style={draw, minimum width=12mm, minimum height=6mm, font=\scriptsize},
  bg/.style={draw=acc, text=acc, minimum width=12mm, minimum height=6mm, font=\scriptsize}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[io] (A) at (0,2.6) {A};
  \node[io] (B) at (0,-0.2) {B};
  \node[g] (g1) at (1.7,2.6) {NOR};
  \node[g] (g2) at (1.7,-0.2) {NOR};
  \node[g] (g3) at (3.7,1.9) {NOR};
  \node[g] (g4) at (3.7,0.5) {NOR};
  \node[bg] (g5) at (5.7,1.2) {NOR};
  \node[io] (out) at (7.0,1.2) {out};
  \draw[black] (A)--(g1);
  \draw[black] (B)--(g2);
  \draw[black] (g1)--(g3);
  \draw[black] (g2)--(g4);
  \draw[black] (B) .. controls (1.3,0.9) and (2.2,1.9) .. (g3);
  \draw[black] (A) .. controls (1.3,1.5) and (2.2,0.5) .. (g4);
  \draw[black] (g3)--(g5);
  \draw[black] (g4)--(g5);
  \draw[black] (g5)--(out);
\end{tikzpicture}
$$

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-circ]: 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.