T F
F T
Dr. Daniel C. Hyde
Department of Computer Science
Bucknell University
August, 1993
Updated August 24, 1995
Portions Based On Notes By
Dr. Donald Utter
Department of Computer Science
Bucknell University
The term algebra is commonly used in connection with the real numbers. The number system has two operations + and *, which are extended to relations between variables to build up algebraic expressions such as x+y, 2*x, x*x, etc. Here x and y vary over the set of numbers.
The essence of algebra is that the symbols do not have to stand for numbers. The structure of symbolic logic, switching circuits, probability theory and set theory is captured by Boolean Algebra. The first two of these are crucial for computers.
How does a computer work? How does a computer add numbers? A computer is made of a bunch of electronic paraphernalia. The theory of how these gadgets are to be hooked up is contained in Boolean Algebra. The goal of this handout is to construct a circuit which will add positive whole numbers.
II. Symbolic Logic
An algebraic structure consists of objects and operations. To describe symbolic logic as an algebraic system we need only give the objects and the operations which will be used to combine the objects. The objects are a collection of statements, and the operations are the usual logical operations of "and", "or", "if, then", "not", and "if and only if". A statement is either True or False. The operation "not" is defined to be
(a) If A is True, then not A is False.
(b) If A is False, then not A is True.
This is better displayed in the following table, called a truth table. A bar over the variable or expression is used to represent not.
Notation:
A, B, C, . . . are statements
T True
F False
A + B A or B
A * B A and B
Click here for Picture not A
A => B (If A, then B) or (A implies B)
A = B (If A, then B and if B, then A) or
(A if and only if B) or (A is logically equivalent to B)
These operations are defined in the following truth tables:
A B A * B A + B A => B A = B T T T T T T T F F T F F F T F T T F F F F F T TTwo statements are said to be logically equivalent if they have the same truth tables. For example, A = A * A. To verify this, one need only draw up the truth table.
A A * A T T F FThis can be extended to A = A * A * A * A * A * A * A. Another example: Is (A => B) = ( Click here for Picture + B)?
A BNotice that this says that any statement which contains a "=>" can be replaced by one with Click here for Picture and +.A => B
+ B T T F T T T F F F F F T T T T F F T T T
AThe notation A + Click here for Picture = T and A* Click here for Picture = F will mean that these are statements which always have the values T or F.A+
A*
T F T F F T T F
The usual algebraic rules hold in symbolic logic.
(1) A+B = B+A; A*B = B*A
(2) (A+B)+C = A+(B+C); A*(B*C) = (A*B)*C
(3) A+F = A; A*T= A
The first statement in (4) and both statements in (5) are not true in the algebra of the real numbers.
(4) A + (B*C) = (A+B)*(A+C); A*(B+C) = A*B + A*C
(5) A + Click here for Picture = T; A* Click here for Picture = F
All of these are verified by consulting the truth tables. Several of these have already been established, and now we will verify that the first statement in (4) holds.
A B C B*C A+(B*C) A+B A+C (A+B)*(A+C) T T T T T T T T T T F F T T T T T F T F T T T T T F F F T T T T F T T T T T T T F T F F F T F F F F T F F F T F F F F F F F F FTwo very useful equivalences are known as DeMorgan's Laws. They are:
(a) Click here for Picture (b) Click here for Picture
Once again, these are verified by consulting truth tables.
A BUsing the identity Click here for Picture , the importance of DeMorgan's laws is seen; namely that + can be substituted for * and visa versa. This means that it is possible to write down every statement and never use +.
A+B
T T F F T F F T F F T T F F F T T F T F F F F T T F T T
(a) Click here for Picture (b) Click here for Picture
An example of the elimination of + is
Click here for Picture Click here for Picture
A binary operation has two inputs and one output. If each input has two states, then there are 16 possible binary operations. The table below shows all of them. Notice that most of the operations do not have names.
A B True Nand => = Nor +These operations add nothing new because any one of them can be expressed as a combination of the basic logical operations. This will be illustrated through an example using exclusive or, denoted Click here for Picture .* False T T T F T F T F T F T F T F T F T F T F T T F F T T F F T T F F T T F F F T T T T T F F F F T T T T F F F F F F T T T T T T T T F F F F F F F F
A BMethod I - Sums of ProductsT T F T F T F T T F F F
(a) Find the rows in the truth table for which Click here for Picture is T.
(b) From these rows, write the product terms separated by + as follows:
To check if this is correct, draw up the truth table.
Method II - Products of Sums
(a) Find the rows in the truth table for which Click here for Picture is F.
(b) From these rows, write sum terms complementing the variables separated by * as follows:
This could be checked with a truth table.
The equivalence of Method I and Method II can also be shown by using the algebraic identities pointed out above.
Click here for Picture Click here for Picture
Method I is explained by noting that the product (and) is True only on the desired line and False elsewhere, and the sum (or) of these will be True on exactly those lines which some product (and) is True. The consequence of Method I is that any operation is a combination of *, + and Click here for Picture (i. e., and, or and not). When this is coupled with DeMorgan's laws, we have the following :
Theorem: Any operation can be expressed in terms of * and Click here for Picture .
The most primitive operations are the Nand, denoted Click here for Picture and the Nor, denoted Click here for Picture . The names come from the equivalences
Click here for Picture = Click here for Picture
A|B = Click here for Picture
Each one in itself is sufficient to generate all 16 operations. This will be established if we can show that * and Click here for Picture can be expressed in terms of Click here for Picture , and + and Click here for Picture can be expressed in terms of |.
Theorem: Any operation can be expressed in terms of Nand ( Click here for Picture ).
Theorem: Any operation can be expressed in terms of Nor (|).
In terms of circuits, these theorems mean that all logical circuits can be defined using only Nor gates, or using only Nand gates.
III. Axioms for Boolean Algebra
The purpose of this section is to explicitly formulate the structure of Boolean Algebra in the most efficient manner possible. Don't panic as we are not going to follow the footsteps of the mathematician and prove theorems from these axioms.
A Boolean Algebra Click here for Picture consists of a set of objects with two operations, + and *, which satisfy the following conditions:
(1) (A+B) + C = A + (B+C); A*(B*C) = (A*B)*C Associative Law
(2) A + B = B + A; A*B = B*A Commutative Law
(3) A+(B+C) = (A+B)*(A+C); A*(B+C) = (A*B)+(A*C) Distributive Law
There are members of the set 0 and 1, such that
(4) A+0 = A; A*1 = A
For each element A, and each pair 0,1 satisfying (4) there exists elements Click here for Picture such that
(5) Click here for Picture ; Click here for Picture .
Recall that the real number system is not a Boolean Algebra. For example, (3) is false, 5 + (2*3) != (5+2)*(5+3). If we interpret the + as "or" in symbolic logic, * as "and" and Click here for Picture as "not", then it is clear that symbolic logic is a Boolean Algebra. It is actually too clear because the same operation symbols were used in both cases.
We now give the simplest example of a Boolean Algebra. The set of objects consists only of the two elements 0 and 1. The "sum" and "product" operations have yet to be defined. Properties (4) and (5) imply that certain things must be true for any candidate for "sum" or "product."
1 + 0 = 1 1 * 1 = 1
0 + 1 = 1 1 * 0 = 0
0 + 0 = 0 0 * 1 = 0
Putting this information in a table, we obtain:
A B A+B A*B 1 1 [ ? ] 1 1 0 1 0 0 1 1 0 0 0 0 [ ? ]Notice that two places in the table are still left unspecified. There are four choices for specifying the two operations. The choice of 1+1 = 1 and 0*0 = 0 makes the operations the same as "or" and "and" of symbolic logic. The choice of 1+1 = 0 and 0*0 = 1 also yields a Boolean Algebra.
Let's have a quick check on our new math. Is 1+1 = 2? Appearing in the above paragraph are the expressions 1+1 = 1 and 1+1 = 0. The symbols 0 and 1 which appear, and the operation "+" must not be occurring within the domain of the real numbers. It is better to think of them as T and F, so the expression T+T = T is not so strange, it is, in fact, just what is expected. Finally, the other choice of addition, 1+1 = 0, will prove to be exactly what is needed for part of the circuit that will do addition (modulo-two arithmetic).
IV. Switching Theory
In this section, the wiring and switches necessary for a circuit to model the logical operators are given. For example, an "or" circuit will have two inputs and one output. If either of the wires is high, then there will be an output; while if both input wires are low, the output will be low. The whole circuit is called an Or gate, and the internal wiring is called hardware. In a computer these are called Integrated Circuits (ICs) and are manufactured in plastic rectangular packages called "chips."
An easy way to build circuits is to use switches which have the value 1 if on and 0 when off. One approach to realizing symbolic logic which was used in old computers is to have the input open or close the switch. This is done by an electromagnet which is called a relay. To construct a relay, a wire is coiled around a ferrous core. When electricity passes through the wire, the ferrous core becomes magnetized and pulls the flexible metal strip to break or make contact. In the below diagram, when the coil of wire is energized, the strip is pulled away from the contact and breaks the connection forming a Not relay.
This relay is said to be Normally Closed (NC) because the switch is closed when no electricity is present. Other relays are Normally Open (NO) which means that the flexible strip is not making contact unless the relay is energized. Below are circuits for an And relay and an Or relay. Both use normally open relays.
The discipline of minimizing the number of relay contacts is called Switching Theory. Switching Theory was important for the development of telephone switching networks.
Since the above diagrams are hard to draw, we represent normally open contacts with two vertical bars and normally closed contacts with a slash across the two vertical bars. Below are the three operations represented as relay logic diagrams.
V. Logic Circuits
A more modern representation or realization of symbolic logic is logic gates. The symbols for a Not gate, And gate and Or gate are shown below.
In the following sections, we will use these logic gates to develop more complicated circuits.
One of the equivalences of DeMorgan's Law is Click here for Picture . Since they are logically equivalent, any inputs A, B will yield the same output. But the equivalence also yields two different circuits (shown below). Each will do the same behavior.
VI. The Half Adder
The purpose of this section is to design a circuit that will add two one-place binary numbers and keep track of the carry. This circuit is called a Half Adder.
0 1 0 1
+ 0 + 0 + 1 + 1
___ ___ ___ ___
0 1 1 10
If we ignore the carry for a moment and think of 0 and 1 as the Boolean
symbols, we are led to find a circuit which will give the following operation
for S, the sum bit..
A B A
B
1 1 0
1 0 1
0 1 1
0 0 0
The symbol
was used because we have described the Exclusive Or operation in Section
II, on page 4. The following two formulas are determined by using the sums of
products method and the product of sums method.
sum of products
product of sums
Either one will allow us to construct an Exclusive Or box out of
Ands, Ors and Not gates. We represent the Exclusive
Or operation as an Or symbol with
inside it.
The carry operation (C) is given in the following truth table.
A B C
1 1 1
1 0 0
0 1 0
0 0 0
The sums of products method yields A
B.
The products of sums method yields
.
We will select the simpler of the two and draw the logic circuit for both
S and C.
The above circuit for a Half Adder will be represented by the following
box with inputs and outputs having arrows to show the flow of the data.
VII. The Full Adder
The Half Adder had two inputs and two outputs, i. e., the two numbers to be
added, the C and the S. The Full Adder has three inputs and two
outputs. The inputs are the two numbers to be added and the carry from a
previous addition. The outputs are the Sum and the Carry.
1 0 1 1 0 1 0 0
1 1 0 1 0 0 1 0
+ 1 + 1 + 1 + 0 + 1 + 0 + 0 + 0
___ ___ ___ ___ ___ ___ ___ ___
11 10 10 10 1 1 1 0
Which gives us the following truth table.
A B C Carry Sum
T T T 1 1
T T F 1 0
T F T 1 0
T F F 0 1
F T T 1 0
F T F 0 1
F F T 0 1
F F F 0 0
The sum of products method gives both the Carry and Sum
operations.
Having these we could design the circuit. But, we first check to see if there
are any logically equivalent statements that would lead to a better equivalent
circuit.
With a little algebraic manipulation, one can see that
Using these results we can construct our Full Adder using two Half
Adders and an Or gate. To distinguish the C of the Half
Adders from the C input of the Full Adder, we have labeled
the latter Carryin.
To add numbers of several bits, one need only join Full Adders
together, one for each bit in the number.
Since the carry ripples from right to left, this adder is called a
carry-ripple adder .