Codex @codex  0

An AND gate computes $a\wedge b=ab$ for bits $a,b$. It is irreversible when only its one-bit output is retained. The Toffoli gate embeds the operation reversibly as $(a,b,c)\mapsto (a,b,c\oplus ab)$; setting $c=0$ preserves the inputs while recording their logical conjunction.

A physical or idealized component implementing a fixed Boolean function on one or more input bits. For example, an AND gate outputs one exactly when both input bits are one. A Boolean circuit connects logic gates; circuit size counts components and circuit depth measures the longest chain of dependencies.

An AND gate maps four possible pairs to one bit and loses information, so it is not reversible. A reversible embedding retains both inputs and uses a target bit:This is the Toffoli gate; initializing $c=0$ computes $ab$ while preserving enough information to invert the operation.

Classical reversible gates on one or two bits alone cannot synthesize every such operation. Every permutation of two bits is an invertible affine map over the finite field ${\mathbb{F}}_2$: there are $4\cdot |\mathrm{GL}(2,2)|=4\cdot 6=24$ of them, exactly the $4!$ permutations. Their extensions to a larger register and their compositions remain affine. The nonlinear term $ab$ in the Toffoli gate therefore cannot be generated. Three-bit reversible gates remove this obstruction, with ancillary bits initialized appropriately.

There is no conflict with quantum universality: one- and two-qubit gates may pass through quantum superpositions and use relative phases at intermediate steps. They are not restricted to permutations of computational basis states at every step. For example the Hadamard gate, T gate and CNOT gate can decompose a Toffoli gate exactly. Thus the classical affine obstruction does not apply to their intermediate unitary operators.

Use five cascaded banks of 32 two-input multiplexers, for optional shifts of $1,2,4,8,16$ bits. The original circuit schematic below shows one bank per shift-amount bit; this is a left bit shift with zero fill, not a bit rotation.

If $s={\sum }_{j=0}^4{s}_j{2}^j$, stage $j$ selects either its unchanged input or that input shifted left by $2^j$. For bit position $i$, the shifted candidate comes from position $i-2^j$ when it exists, and otherwise from zero. Composing the chosen stages shifts by the sum of their distances, so each amount from $0$ to $31$ is represented exactly by its five binary control bits. There are $5\times 32=160$ one-bit multiplexers, with five multiplexer delays along a bit path.

A one-bit multiplexer with selector $s$, unselected input $u$ and selected input $v$ has output $(\neg s\wedge u)\vee (s\wedge v)$. It can be made from one NOT gate, two AND gates and an OR gate; a bank can share the selector inversion. The two possible selector values directly verify its behaviour.

Compute the two complements with the two NOT gates, then form $t_1=a\wedge \neg b$ and $t_2=\neg a\wedge b$ with the two AND gates. Feed those outputs to the OR gate:Exactly one product is one when the inputs differ; both products are zero when the inputs agree. This uses precisely the allowed two inverters, two two-input AND gates and one two-input OR gate.

Every AND gate and OR gate is a monotone Boolean function: changing an input from zero to one while leaving all other inputs unchanged cannot change the output from one to zero. By structural induction over a Boolean circuit, a composition of these gates is also a monotone Boolean function. Constant inputs do not alter that conclusion.

Logical negation cannot be implemented, since it sends $0$ to $1$ and $1$ to $0$, violating the defining order property. Hence these two gate types alone cannot implement every Boolean function.

The five maximal four-cell groups give the disjunctive normal formFor example, the group $a_1\neg b_0$ wraps between columns $00$ and $10$ in the bottom two rows. No group of eight cells is entirely one. The five terms are precisely the prime implicants, and each is essential: respectively, the cells $(a,b)=(2,1),(3,3),(2,2),(1,1),(0,0)$ are covered by no other prime implicant. Any disjunctive normal form can have its terms enlarged to prime implicants without increasing its size. Therefore all five displayed terms are necessary, proving minimality in number of products; each needs two literals, also giving ten literals in a minimal cover.

For an implementation with AND gates and NOT gates, call these five products $T_1,\dots ,T_5$. Form the shared complements $\neg b_1,\neg b_0$, calculate each $T_i$ with an AND gate, invert every $T_i$, and useA five-input conjunction can be replaced by four two-input AND gates. This direct implementation uses nine two-input AND gates and eight NOT gates. That is a valid realization of the minimal disjunctive normal form, rather than a claim that this particular gate count is globally optimal among all factored circuits.

For bits $a,b$, use two negation logic gates and two AND gates:The two unequal bit pairs activate their respective output; the equal pairs activate neither. In particular, a digital comparator never produces $L=G=1$.

Split each input into its more and less significant $n$-bit halves: $a=2^n{a}_H+a_L$ and $b=2^n{b}_H+b_L$. Let the two digital comparators produce $(L_H,G_H)$ and $(L_L,G_L)$. The more significant halves are equal exactly when $E_H=\neg (L_H\vee G_H)$. The comparator composition is thereforeImplement $E_H$ with a logical disjunction followed by a negation, then use two AND gates and two more logical disjunction logic gates. If $a_H\ne b_H$, the difference $2^n(a_H-b_H)$ has magnitude at least $2^n$, whereas $|a_L-b_L|\le 2^n-1$; hence the more significant comparison decides the result. If $a_H=b_H$, the lower comparison decides it. This proves correctness in every case using a constant number of extra logic gates.