6.2.3 Arithmetic

Not only is the nand function complete for Boolean logical functions, it is also enough to implement all discrete arithmetic functions. First, consider the problem of adding two one-bit numbers.

There are four possible pairs of inputs:

A   B   $r_1$ $r_0$
0 + 0 = 0 0
0 + 1 = 0 1
1 + 0 = 0 1
1 + 1 = 1 0

We can compute each of the two output bits as a logical function of the two input bits. The right output bit, $r_0$, is 1 if exactly one of the input bits is 1:

$r_0$ = (or (and (not A) B) (and A (not B)))

This is what the xor function computes, so:

$r_0$ = (xor A B)

The left output bit, $r_1$, is 0 for all inputs except when both inputs are 1:

$r_1$ = (and A B)

Since we have already seen how to implement and, or, xor, and not using only nand functions, this means we can implement a one-bit adder using only nand functions.

Adding larger numbers requires more logical functions. Consider adding two $n$-bit numbers:

$a_{n-1}$ $a_{n - 2}$ $\cdots $ $a_1$ $a_0$
+ $b_{n-1}$ $b_{n - 2}$ $\cdots $ $b_1$ $b_0$
= $r_{n}$ $r_{n-1}$ $r_{n - 2}$ $\cdots $ $r_1$ $r_0$

The elementary school algorithm for adding decimal numbers is to sum up the digits from right to left. If the result in one place is more than one digit, the additional tens are carried to the next digit. We use $c_ k$ to represent the carry digit in the $k^{th}$ column.

$c_{n}$ $c_{n-1}$ $c_{n - 2}$ $\cdots $ $c_1$
$a_{n-1}$ $a_{n - 2}$ $\cdots $ $a_1$ $a_0$
+ $b_{n-1}$ $b_{n - 2}$ $\cdots $ $b_1$ $b_0$
= $r_{n}$ $r_{n-1}$ $r_{n - 2}$ $\cdots $ $r_1$ $r_0$

The algorithm for addition is:

  • Initially, $c_{0} = 0$.

  • Repeat for each digit $k$ from $0$ to $n$:

    1. $v_1v_0 = a_ k + b_ k + c_ k$ (if there is no digit $a_ k$ or $b_ k$ use $0$).

    2. $r_ k$ = $v_0$.

    3. $c_{k+1} = v_1$.

This is perhaps the first interesting algorithm most people learn: if followed correctly, it is guaranteed to produce the correct result, and to always finish, for any two input numbers.

Step 1 seems to require already knowing how to perform addition, since it uses $+$. But, the numbers added are one-digit numbers (and $c_ k$ is $0$ or $1$). Hence, there are a finite number of possible inputs for the addition in step 1: 10 decimal digits for $a_ k$ $\times $ 10 decimal digits for $b_ k$ $\times $ 2 possible values of $c_ k$. We can memorize the 100 possibilities for adding two digits (or write them down in a table), and easily add one as necessary for the carry. Hence, computing this addition does not require a general addition algorithm, just a specialized method for adding one-digit numbers.

We can use the same algorithm to sum binary numbers, except it is simpler since there are only two binary digits. Without the carry bit, the result bit, $r_ k$, is 1 if (xor ). If the carry bit is 1, the result bit should flip. So,

$r_ k$ = (xor (xor ) )

This is the same as adding $a_ k + b_ k + c_ k$ base two and keeping only the right digit.

The carry bit is 1 if the sum of the input bits and previous carry bit is greater than 1. This happens when any two of the bits are 1:

$c_{k+1}$ = (or (and ) (and ) (and ))

As with elementary school decimal addition, we start with $c_{0} = 0$, and proceed through all the bits from right to left.

We can propagate the equations through the steps to find a logical equation for each result bit in terms of just the input bits. First, we simplify the functions for the first result and carry bits based on knowing $c_0 = 0$:

 (and $x_0$ $x_0$)

$r_0$ = (xor (xor $a_0 b_0$ ) $c_0$ ) = (xor $a_0 b_0$ )

$c_1$ = (or (and $a_0 b_0$ ) (and $a_0 c_0$ ) (and $b_0 c_0$ )) = (and $a_0 b_0$ )

Then, we can derive the functions for $r_1$ and $c_2$:

$r_1$ = (xor (xor $a_1 b_1$ ) $c_1$ ) = (xor (xor $a_1 b_1$ ) (and $a_0 b_0$ ))

$c_2$ = (or (and $a_1 b_1$ ) (and $a_1 c_1$ ) (and $b_1 c_1$ ))

= (or (and $a_1 b_1$ ) (and $a_1$ (and $a_0 b_0$ )) (and $b_1$ (and $a_0 b_0$ )))

As we move left through the digits, the terms get increasingly complex. But, for any number of digits, we can always find functions for computing the result bits using only logical functions on the input bits. Hence, we can implement addition for any length binary numbers using only nand functions.

We can also implement multiplication, subtraction, and division using only nand functions. We omit the details here, but the essential approach of breaking down our elementary school arithmetic algorithms into functions for computing each output bit works for all of the arithmetic operations.

Exercise 6.7. Adding logically.

  1. What is the logical formula for $r_3$?

  2. Without simplification, how many functions will be composed to compute the addition result bit $r_4$?

  3. $\left[\star \right]$Is it possible to compute $r_4$ with fewer logical functions?

Exercise 6.8. Show how to compute the result bits for binary multiplication of two 2-bit inputs using only logical functions.

Exercise 6.9. $\left[\star \right]$Show how to compute the result bits for binary multiplication of two inputs of any length using only logical functions.