Reversible logic

In an ordinary Boolean function with n inputs there is no unique way to tell from its output which of the 2ⁿ possible sets of inputs was given. But as noted in the 1970s, it is possible to set up systems that evaluate Boolean functions, yet operate reversibly. The basic idea is to have m outputs as well as m inputs—with every one of the 2^m possible sets of inputs mapping to a unique set of outputs. Normally one specifies the first n inputs, taking the others to be fixed, and then looks say at the first output, ignoring all others. One can represent the inside of such a system much like a sorting network from page 1142—but with s-input s-output gates instead of pair comparisons. If each such gate is itself reversible, then overall reversibility is guaranteed. With gates that in effect implement {p, q}  {p ⊼ q} and {p}  {p, p} (with other inputs constant, and other outputs ignored) one can set up a direct translation of Boolean functions given in the form shown on page 619. Of the 24 possible reversible s = 2 gates, none can yield anything other than additive Boolean functions (as formed from Xor and Not). But of the 40,320 (8!) reversible s = 3 gates (in 52 distinct classes) it turns out that 38,976 (in 23 classes) can be used to reproduce any possible Boolean function. A simple example of such a universal gate is {p_, q_, 1}  {q, p, 1}—and not allowing permutations of gate inputs (or in effect wire crossings) a simple example is {p_, q_, q_}  {q, 1 - p, 1 - p}. (Compare pages 1147 and 1173.)