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).

Figure 6.3: Computing and3 by composing two and functions.

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).