h the reader can check out using truth tables: aQb=(avb)^(avb) (15.2) (a)). It is seen that the last solution in this equation makes exclusive use of NAND (A) and NOT (x) operations. The NOT can also be realized with NAND, taking into account the property a = a is a. Thus, we obtain from Eq. (15.2) (15.3) which shows that an XOR gate can be built exclusively with a Boolean circuit of NAND gates. It is easily established that the NAND gate can be used as a universal building block in Boolean circuits to construct all elementary logic gates. This property is illustrated in Fig. 15.5. We have, thus, identified the basic constitutive elements of computation: logic gates (NOT, AND, OR, XOR) with NAND representing a universal building block, and wires to realize any Boolean circuit, from elementary to complex. We can then consider other types of logic gates derived from these. First, the XOR gate can also be used to perform yet another logical function called controlled-NOT, corresponding to the CNOT gate. Given (a, x) as inputs, with a being called the control bit, the output of CNOT is a + X. For a = 0, we have a + X = x; and for a = 1, we have a +x=x. Thus the value of x is flipped if the control bit is set to a = 1 and is left unchanged otherwise, hence the name "controlled-NOT" gate. Another Boolean-circuit component, which was only implicitly introduced, is the wire splitter that enables one to use the same bit to feed different gate inputs. This logical splitting function is referred to as FANOUT. Another logical function of interest is CROSSOVER (also called SWAP), which consists of switching two bits (a, b) into Reversible computation Figure 15.5 Construction of logic gates NOT, AND, OR, and XOR from Boolean circuits of NAND gates. (b, a), depending on the value of a control bit C. As we shall see later, the function CROSSOVER is the key to building reversible logic gates. Here, we shall overlook more complex logical-gate arrangements, whereby the wires can form circuit loops, thus enabling output bits to be f