Universal 2-bit gates

Question

I'd like to show that there is no set of 2 bit reversible gates which is universal. I'm not sure as to where & how do I start here? I tried to assume by contradiction that such a set exists, thus it can implement both $OR$ ($\vee$) and $AND$ ($\wedge$), and then since each of the gates used is reversible, I thought going backwards, and to get the original entry values $X,Y$ out of the value of $X\wedge Y$, in a contradiction to $AND$ not being reversible. But I'm not sure if its ok? Or perhaps there is another way to prove so?

Answer 1

The truth table of a 2-bit gate will have two input columns and two output columns:

 Input | Output
 A  B  |  X  Y
-------+--------
 0  0  |  ?  ?
 0  1  |  ?  ?
 1  0  |  ?  ?
 1  1  |  ?  ?

In order for the gate to be reversible, each output column must contain exactly two ones and two zeroes. This limits the possible output columns to one of $\binom42=6$ Boolean functions of $A$ and $B$, namely $A$, $B$, $A \mathbin{\sf XOR} B$, and their negations. So everything that can be computed by a network of arbitrary reversible 2-bit gates can also be computed by a network of NOT and XOR gates.

Knowing this, we can prove by induction on the number of gates that every result of a NOT/XOR network has one of the following relations to each of the network's inputs: Either the result does not depend on that input at all, or the result will invert whenever that input is inverted.

(In terms of abstract algebra, the possible outputs are always affine functions of the input over $\mathbb F_2$).

Because $A\lor B$ does not have this property, it cannot be produced by such a network.

---

On the other hand, three-bit reversible gates are universal when results can be discarded. Specifically, this particular 3-bit gate which computes $4-x \bmod 2^3$ is universal:

 Input | Output
 A B C |  X Y Z
-------+---------
 0 0 0 |  1 0 0
 0 0 1 |  0 1 1
 0 1 0 |  0 1 0
 0 1 1 |  0 0 1
 1 0 0 |  0 0 0
 1 0 1 |  1 1 1
 1 1 0 |  1 1 0
 1 1 1 |  1 0 1

Wiring all three inputs of this gate together will produce a steady 0 on the $Y$ output, and feeding this 0 to the $A$ input of another gate will make it produce $B\mathbin{\sf NOR}C$, which is known to be universal.