ique correspondence between the input and the output information, hence, computation through the Fredkin gate is reversible. Because the Fredkin gate can perform both NOT and AND logical functions, it can be used as a universal building block to construct any other logic gate. To prove this point, we need to introduce De Morgan's law (or theorem).14 Such a theorem can be put in the form of the following equations: avb=anb, a\b=avb. (15.4) In ensemble theory, De Morgan's law equivalently translates into the relations AUB = An B and ANB = AUB, which can be readily verified from Venn diagrams (see Fig. 1.4). Using Eq. (15.4) we observe that the OR function can be generated through 14 See http://en.wikipedia.org/wiki/De_Morgan%27s_laws. Reversible computation Figure 15.7 Fredkin gate diagram, with corresponding truth table. Figure 15.8 Fredkin gate configurations (a) REPEAT, (b) CROSSOVER, (c) NOT [port a'] and FANOUT [ports b' and c'], (d) AND [port a'] and NOT X AND y [port b']. the identity avb=avb=arb, (15.5) which exclusively uses the NOT and AND gates. Using the above property and the relations in Eq. (15.1) (with a b=a/b), we observe that the function XOR can be constructed either with NOT and AND gates or with NOT, AND, and OR gates. 15 Here, the key difference with the previous "classical" logic of the ALU in the VN It is left as an exercise to construct different possibilities of XOR circuits exclusively based on Fredkin gates. 15.3 Reversible logic gates and computation abca'b'c 000000 001001 010010 011011 100100 101101 C'=c + ab 110111 111110 Figure 15.9 Toffoli gate diagram, with corresponding truth table, showing bit-flipping of C if the two control bits are set to a = b 1. computer is that all gate circuits constructed from Fredkin gates perform fully reversible computations, by virtue of the gate's reversible logic. We consider next a second type of elementary reversible-logic gate, which is called the Toffoli gate. Its diagram and corresponding truth table are shown in Fig. 15.9. Like the Fredkin gat