CmpSci 535 Discussion 5
Logic Design
George Boole
Boolean algebra is named for its inventor, English mathematician George Boole, born in 1815. His father, a tradesman, began teaching him mathematics at an early age. But Boole initially was more interested in classical literature, languages, and religion—interests he maintained throughout his life. By the time he was 20, he had taught himself French, German, and Italian. He was well versed in the writings of Aristotle, Spinoza, Cicero, and Dante, and wrote several philosophical papers himself.
At 16, to help support his family, he took a position as a teaching assistant in a private school. His work there and a second teaching job left him little time to study. A few years later, he opened a school and began to learn higher mathematics on his own. In spite of his lack of formal training, his first scholarly paper was published in the Cambridge Mathematical Journal when he was just 24. Boole went on to publish over 50 papers and several major works before he died in 1864, at the peak of his career.
Boole's The Mathematical Analysis of Logic was published in 1847. It would eventually form the basis for the development of digital computers. In the book, Boole set forth the formal axioms of logic (much like the axioms of geometry) on which the field of symbolic logic is built.
Boole drew on the symbols and operations of algebra in creating his system of logic. He associated the value 1 with the universal set (the set representing everything in the universe) and the value 0 with the empty set, and restricted his system to these two quantities. He then defined operations that are analogous to subtraction, addition, and multiplication. Variables in the system have symbolic values. For example, if a Boolean variable P represents the set of all plants, then the expression 1 – P refers to the set of all things that are not plants. We can simplify the expression by using –P to mean "not plants." (0 – P is simply 0 because we can't remove elements from the empty set.)
The expression 0 + P is the same as P. However, 0 + P + F, where F is the set of all foods, is the set of all things that are either plants or foods. So the addition operator in Boole's algebra is the OR operator.
The analogy can be carried to multiplication: 0 ´ P is 0, and 1 ´ P is P. But what is P ´ F? It is the set of things that are both plants and foods. In Boole's system, the multiplication operator is the AND operator.
In 1854, Boole published An Investigation of the Laws of Thought, on Which Are Founded the Mathematical Theories of Logic and Probabilities. In the book, he described theorems built on his axioms of logic and extended the algebra to show how probabilities could be computed in a logical system. Five years later, Boole published Treatise on Differential Equations, then Treatise on the Calculus of Finite Differences. The latter is one of the cornerstones of numerical analysis, which deals with the accuracy of computations. (In Chapter 10, we examine the important role numerical analysis plays in computer programming.)
Boole received little recognition and few honors for his work. Given the importance of Boolean algebra in modern technology, it is hard to believe that his system of logic was not taken seriously until the early twentieth century.
In 1948, Claude Shannon, considered the father of modern information theory, rediscovered Boolean algebra and recognized how it could be applied to electronic circuits to construct a computing machine. His paper, “A Symbolic Analysis of Relay and Switching Circuits,” established the basis for electronic digital computers.
From both programming and prior work with assembly, you should be familiar with the Boolean AND, OR, Exclusive OR, and NOT operations. In hardware, these operations are implemented by circuits known as gates. Since we design computers by physically connecting gates together, we use diagrams where symbols represent the gates and lines represent the wires that connect them. Because it is common to have to invert the value of signals, a symbol for a gate may be followed by a small circle, indicating that its output is followed by NOT operation. The names of these gates are written in shorthand as NOR, NAND, and Exclusive NOR. The inverse of NOT, of course is nothing, but in logic design we call this a “buffer” and it represents a stage in which the signal is amplified and suffers a delay comparable to another gate.
Let’s see how we would draw the function (A AND NOT B) AND NOT (C OR D) (or in Java syntax : (A && !B) && !(C || D) ):
We can
simplify this diagram using a NOR gate and a special notation that puts the
small circle on the B input to the AND gate:
And there is also an algebraic notation that is often used:
Creating Logic Functions
Starting to create a logic function typically begins with a truth table. We organize the table with the input variables and outputs listed across the top and underneath the inputs we write the combinations of binary values that they can take. Under the outputs we write the result values that correspond to each input combination. For example, here is a truth table that has three inputs (A, B, C) and space for writing in the values of two output variables (X, Y):
|
A |
B |
C |
X |
Y |
|
0 |
0 |
0 |
|
|
|
0 |
0 |
1 |
|
|
|
0 |
1 |
0 |
|
|
|
0 |
1 |
1 |
|
|
|
1 |
0 |
0 |
|
|
|
1 |
0 |
1 |
|
|
|
1 |
1 |
0 |
|
|
|
1 |
1 |
1 |
|
|
Here is the same table with the outputs filled in. Before proceeding, see if you can recognize the output functions.
|
A |
B |
C |
X |
Y |
|
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
0 |
|
0 |
1 |
0 |
1 |
0 |
|
0 |
1 |
1 |
0 |
1 |
|
1 |
0 |
0 |
1 |
0 |
|
1 |
0 |
1 |
0 |
1 |
|
1 |
1 |
0 |
0 |
1 |
|
1 |
1 |
1 |
1 |
1 |
After writing out all of the input values and the corresponding outputs, we have a complete function that can be directly converted to a Boolean expression. For each place that there is a 1 in the output column we write a term in the expression. Thus, the expression for X in the above truth table contains four terms.
Each term consists of the input variables ANDed together. If the input for a variable in that row of the table is 1, then the variable is written directly. If the input is a 0, then we invert the variable. Thus, the first term in the expression for X corresponds to the row where A=0, B=0, and C=1. So it is
NOT A AND NOT B AND C
Or
The terms are combined with OR operations. So the expression for X is:
We call this a canonical sum-of-products form. It is rarely the simplest form of the expression (the form using the fewest operations and copies of inputs), but it is an easy place to begin. There are various ways to simplify Boolean expressions. One is through the application of the laws of Boolean algebra, just as we can reduce algebraic expressions. Another approach is a graphical technique called a Karnaugh map, where the function is rearranged into a different tabular format, groups of ones are circled, and a set of rules tells how to convert the grouped ones into simpler terms. Karnaugh maps are reliable up to four variables, but become unwieldy for more variables because the tables become multidimensional. A third technique, called the Quine-McCluskey method, is a tabular algorithmic technique for simplifying larger expressions. In this class we are not going to be concerned with these techniques, but you should be aware that they exist.
Of the three simplification techniques, only the use of the algebraic identities would reveal that the function X is really the three-input exclusive OR operation:
The expression for Y is
Additional thought would reveal that this can be reduced as follows. Because
We can eliminate one term and shorten
the expression to
Recognizing that
We can change the form to
Knowing that
We substitute the exclusive OR of B and C
for the portion in parentheses and get a final form for this expression:
Performing
Arithmetic Using Logic
Let’s take a closer look at these two functions. First, let’s reconsider the exclusive OR of two inputs:
|
B |
C |
X |
|
0 |
0 |
0 |
|
0 |
1 |
1 |
|
1 |
0 |
1 |
|
1 |
1 |
0 |
The two-input exclusive OR outputs a one whenever it has a single one as an input. A pair of zeroes or a pair of ones cause it to output zero. This is the same as the sum of two binary digits, ignoring overflow. When there are two ones, we generate a carry. The function that detects when both of two inputs are one is just an AND gate. So we could build a simple adder as follows:
In fact, another name for this circuit is a half-adder. What it lacks is an input for a carry from another bit of a multi-bit pair of operands. Well, as you may have guessed, that’s precisely what our three-input , two-output function above is for. The sum is
And the carry is
But notice that the carry and the sum share the common exclusive OR of B and C. Rather than build these as separate circuits, we can combine them as follows:
This circuit is called a full-adder, and is the basis for addition in computers.
Summary
Boolean logic forms the basis for electronic digital computers. We have seen that logic expressions can be directly converted into a circuit representation using electronic components called gates. Combinations of gates can be used to perform binary arithmetic on multi-bit operands, enabling computers to be built for arithmetic of any degree of precision. Creating a logic expression typically begins with a truth table, from which we can directly write a canonical sum-of-products function. The SOP form is rarely minimal, and various techniques can be used to reduce the expression. Because each term of an expression becomes a gate in logic circuit, there is economic benefit to reducing the expression. In addition, a smaller circuit is faster and so reducing its complexity can improve computational performance.
© Copyright
1995, 1996 Charles C. Weems Jr. All rights reserved.