# 6.2.2 Composing Operations

We can implement *and*, *or* and *not* using wine, but is that enough to
perform interesting computations? In this subsection, we consider how
simple logical functions can be combined to implement any logical
function; in the following subsection, we see how basic arithmetic
operations can be built from logical functions.

We start by making a three-input conjunction function. The *and3* of
three inputs is *true* if and only if all three inputs are *true*. One
way to make the three-input *and3* is to follow the same idea as the
two-input *and* where all three inputs pour into the same basin, but
make the basin with the output nozzle above the two bottle level.

Another way to implement a three-input *and3* is to compose two of the
two-input *and* functions, similarly to how we composed procedures in
Section 4.2. Building *and3* by composing two
two-input *and* functions allows us to construct a three-input *and3*
without needing to design any new structures, as shown in Figure 6.3. The output of
the first *and* function is fed into the second *and* function as its
first input; the third input is fed directly into the second *and*
function as its second input. We could write this as ```
(and (and A B)
C)
```

.

Composing logical functions also allows us to build new logical
functions. Consider the *xor* (exclusive or) function that takes two
inputs, and has output *true* when exactly one of the inputs is *true*:

A | B | (xor A B) |

false | false | false |

true | false | true |

false | true | true |

true | true | false |

Can we build *xor* by composing the functions we already have?

The *xor* is similar to *or*, except for the result when both inputs are
*true*. So, we could compute `(xor A B)`

as ```
(and (or A B) (not (and A
B)))
```

. Thus, we can build an *xor* machine by composing the designs we
already have for *and*, *or*, and *not*.

We can compose any pair of functions where the outputs for the first
function are consistent with the input for the second function. One
particularly important function known as *nand* results from *not* and
*and*:

A | B | |

false | false | true |

true | false | true |

false | true | true |

true | true | false |

*All* Boolean logic functions can be implemented using just the *nand*
function. One way to prove this is to show how to build all logic
functions using just *nand*. For example, we can implement *not* using
*nand* where the one input to the *not* function is used for both inputs
to the *nand* function:

`(not A)`

$\equiv$ `(nand A A)`

Now that we have shown how to implement *not* using *nand*, it is easy
to see how to implement *and* using *nand*:

`(and A B)`

$\equiv $ `(not (nand A B))`

Implementing *or* is a bit trickier. Recall that *A* *or* *B* is
*true* if any one of the inputs is *true*. But, *A* *nand* *B* is
*true* if both inputs are *false*, and *false* if both inputs are
*true*. To compute *or* using only *nand* functions, we need to invert
both inputs:

`(or A B)`

$\equiv $ `(nand (not A) (not B))`

To complete the proof, we would need to show how to implement all the
other Boolean logic functions. We omit the details here, but leave some
of the other functions as exercises. The universality of the *nand*
function makes it very useful for implementing computing devices.
Trillions of *nand* gates are produced in silicon every day.

**Exercise 6.2. ** Define a Scheme procedure, `logical-or`

, that takes
two inputs and outputs the logical or of those inputs.

**Exercise 6.3. ** What is the meaning of composing *not* with itself?
For example, (*not* (*not* *A*)).

**Exercise 6.4. ** Define the *xor* function using only *nand*
functions.

**Exercise 6.5. ** $\left[\star \right]$ Our definition of ```
(not
A)
```

as `(nand A A)`

assumes there is a way to produce two copies of a
given input. Design a component for our wine machine that can do this.
It should take one input, and produce two outputs, both with the same
value as the input. (Hint: when the input is *true*, we need to produce
two full bottles as outputs, so there must be a source similarly to the
*not* component.)

**Exercise 6.6. ** $\left[\star \right]$ The digital abstraction
works fine as long as actual values stay close to the value they
represent. But, if we continue to compute with the outputs of functions,
the actual values will get increasingly fuzzy. For example, if the
inputs to the *and3* function in Figure 6.3 are initially all
$\frac{3}{4}$ full bottles (which should be interpreted as *true*),
the basin for the first *and* function will fill to $1\frac{1}{2}$,
so only $\frac{1}{2}$ bottle will be output from the first *and*.
When combined with the third input, the second basin will contain
$1\frac{1}{4}$ bottles, so only $\frac{1}{4}$ will spill into the
output bottle. Thus, the output will represent *false*, even though all
three inputs represent *true*. The solution to this problem is to use an
*amplifier* to restore values to their full representations. Design a
wine machine amplifier that takes one input and produces a strong
representation of that input as its output. If that input represents
*true* (any value that is half full or more), the amplifier should
output *true*, but with a strong, full bottle representation. If that
input represents *false* (any value that is less than half full), the
amplifier should output a strong *false* value (completely empty).