1.3.5: Binary Addition

Last updated
Save as PDF

Page ID: 9857

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

All this explains nicely the relationship between logic and circuits, but it doesn’t explain why logic circuits should be used in computers in the first place. Part of the explanation is found in the fact that computers use binary numbers. A binary number is a string of zeros and ones. Binary numbers are easy to represent in an electronic device like a computer: Each position in the number corresponds to a wire. When the wire is on, it represents one; when the wire is off, it represents zero. When we are thinking in terms of logic, the same states of the wire represent true and false, but either representation is just an interpretation of the reality, which is a wire that is on or off. The question is whether the interpretation is fruitful.

Once wires are thought of as representing zeros and ones, we can build circuits to do computations with binary numbers. Which computations? Any that we want! If we know what the answer should be for each combination of inputs, then by Theorem 2.3 we

屏幕快照 2019-06-26 11.48.11.png

Figure 2.8: Input/output tables for the addition of three binary digits, A, B, and C.

can build a circuit to compute that answer. Of course, the procedure described in that theorem is only practical for small circuits, but small circuits can be used as building blocks to make all the calculating circuits in a computer.

For example, let’s look at binary addition. To add two ordinary, decimal numbers, you line them up one on top of the other, and add the digits in each column. In each column, there might also be a carry from the previous column. To add up a column, you only need to remember a small number of rules, such as 7+6+1 = 14 and 3+5+0 = 8. For binary addition, it’s even easier, since the only digits are 0 and 1. There are only eight rules:

0 + 0 + 0 = 00 0 + 0 + 1 = 01

0 + 1 + 0 = 01 0 + 1 + 1 = 10

1 + 0 + 0 = 01 1 + 0 + 1 = 10

1 + 1 + 0 = 10 1 + 1 + 1 = 11

Here, I’ve written each sum using two digits. In a multi-column addition, one of these digits is carried over to the next column. Here, we have a calculation that has three inputs and two outputs. We can make an input/output table for each of the two outputs. The tables are shown in Figure 2.8. We know that these tables can be implemented as combinatorial circuits, so we know that circuits can add binary numbers. To add multi- digit binary numbers, we just need one copy of the basic addition circuit for each column in the sum.

Exercises

1. Using only and, or, and not gates, draw circuits that compute the value of each of the propositions A → B, A ↔ B, and A ⊕ B.

2. For each of the following propositions, find a combinatorial logic circuit that computes that proposition:

a) A ∧ (B ∨ ¬C) b) (p ∧ q) ∧ ¬(p ∧ ¬q)

c) (p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r) d) ¬(A ∧ (B ∨ C)) ∨ (B ∧ ¬A)

3. Find the compound proposition computed by each of the following circuits:

屏幕快照 2019-06-26 11.54.14.png

4. This section describes a method for finding the compound proposition computed by any com- binatorial logic circuit. This method fails if you try to apply it to a circuit that contains a feed- back loop. What goes wrong? Give an example.

5. Show that every compound proposition which is not a contradiction is equivalent to a propos- ition in disjunctive normal form. (Note: We can eliminate the restriction that the compound proposition is not a contradiction by agreeing that “F” counts as a proposition in disjunctive normal form. F is logically equivalent to any contradiction.)

6. A proposition in conjunctive normal form (CNF) is a conjunction of disjunctions of simple terms (with the proviso, as in the definition of DNF that a single item counts as a conjunction or disjunction). Show that every compound proposition which is not a tautology is logically equivalent to a compound proposition in conjunctive normal form. (Hint: What happens if you take the negation of a DNF proposition and apply DeMorgan’s Laws?)

7. Use the laws of Boolean algebra to simplify each of the following circuits:

屏幕快照 2019-06-26 11.56.11.png

8. Design circuits to implement the input/output tables for addition, as given in Figure 2.8. Try to
make your circuits as simple as possible. (The circuits that are used in real computers for this purpose are more simplified than the ones you will probably come up with, but the general approach of using logic to design computer circuits is valid. If you are interested to learn
more about this, the second year variant course Digital Systems describes circuit design in more detail.)