t correspondence being unique). The three gates NOT, OR, and AND make it possible to build a second group of ele- mentary logic gates, shown in Fig. 15.4, called NAND (NOT AND) and XOR (eXclusive bn be two binary numbers. Proceeding from the lowest-weight bit to the highest-weight bit (i =n), a first Boolean circuit computes both Xi ai and The output c(1) provides a "carry" bit, which is 1 if the two bits (a, bj) are equal to 1, and 0 otherwise. A second circuit stage then computes yi = Xi + Ci c(2) and where Ci-1 is the carry bit resulting from the previous addition stage (by convention, C_1 = 0). The result represents the ith bit of + B and the result Ci is the carry to use for the next computation stage i + 1. It is left to the reader as an exercise to draw the Boolean circuits corresponding to these different computations stages, as well as the circuit for a full k-bit binary adder. Reversible computation NOT a NOT a a AND b a AND b a OR b a OR b Figure 15.3 The three elementary logic gates: NOT, AND, and OR, along with their corresponding truth tables. a NAND b a NAND b a XOR b a XOR b Figure 15.4 Second group of elementary logic gates, NAND and XOR, along with their corresponding truth tables, as built from the first group shown in Fig. 15.3. 15.2 From computer architecture to logic gates OR). In Boolean logic, the corresponding operators are: xxy for X NAND y, x oy for X XOR y, respectively. Note the small open circle, or "bubble," which indicates the logical com- plementation at the gate's output (in some cases, the bubble can be placed at the input to complement some of the input data bits). The figure shows that the NAND gate is built through a succession of AND and NOT gates. The XOR gate is an essential function for performing modulo-2 addition of two binary numbers. This gate can be built in many different ways. The figure shows one possible Boolean circuit utilizing AND, NAND, and OR gates, according to the heuristic formula (15.1) Here are three other possible ways to effect a XOR computation, whic