Table of Content | Chapter Two (Part 2) |
CHAPTER
TWO: BOOLEAN ALGEBRA (Part 1) |
||
2.0 -
Chapter Overview 2.1 - Boolean Algebra 2.2 - Boolean Functions and Truth Tables 2.3 - Algebraic Manipulation of Boolean Expressions 2.4 - Canonical Forms 2.5 - Simplification of Boolean Functions 2.6 - What Does This Have To Do With Computers Anyway? 2.6.1 - Correspondence Between Electronic Circuits and Boolean Functions 2.6.2 - Combinatorial Circuits 2.6.3 - Sequential and Clocked Logic 2.7 - Okay What Does It Have To Do With Programming Then? 2.8 - Generic Boolean Functions |
Copyright 1996 by Randall Hyde
All rights reserved. Duplication other than for immediate display through a browser is prohibited by U.S. Copyright Law. This material is provided on-line as a beta-test of this text. It is for the personal use of the reader only. If you are interested in using this material as part of a course please contact rhyde@cs.ucr.edu Supporting software and other materials are available via anonymous ftp from ftp.cs.ucr.edu. See the "/pub/pc/ibmpcdir" directory for details. You may also download the material from "Randall Hyde's Assembly Language Page" at URL: http://webster.ucr.edu Notes: This document does not contain the laboratory exercises programming assignments exercises or chapter summary. These portions were omitted for several reasons: either they wouldn't format properly they contained hyperlinks that were too much work to resolve they were under constant revision or they were not included for security reasons. Such omission should have very little impact on the reader interested in learning this material or evaluating this document. This document was prepared using Harlequin's Web Maker 2.2 and Quadralay's Webworks Publisher. Since HTML does not support the rich formatting options available in Framemaker this document is only an approximation of the actual chapter from the textbook. If you are absolutely dying to get your hands on a version other than HTML you might consider having the UCR Printing a Reprographics Department run you off a copy on their Xerox machines. For details please read the following EMAIL message I received from the Printing and Reprographics Department:
We are currently working on ways to publish this text in a form other than HTML (e.g. Postscript PDF Frameviewer hard copy etc.). This however is a low-priority project. Please do not contact Randall Hyde concerning this effort. When something happens an announcement will appear on "Randall Hyde's Assembly Language Page." Please visit this WEB site at http://webster.ucr.edu for the latest scoop. Redesigned 10/2000 with "MS FrontPage 98" using
17" monitor 1024x768 |
Logic circuits are the basis for modern digital computer systems. To appreciate how computer systems operate you will need to understand digital logic and boolean algebra. This Chapter provides only a basic introduction to boolean algebra. This subject alone is often the subject of an entire textbook. This Chapter will concentrate on those subject that support other chapters in this text.
Boolean logic forms the basis for computation in modern binary computer systems. You can represent any algorithm or any electronic computer circuit using a system of boolean equations. This chapter provides a brief introduction to boolean algebra truth tables canonical representation of boolean functions boolean function simplification logic design combinatorial and sequential circuits and hardware/software equivalence.
The material is especially important to those who want to design electronic circuits or write software that controls electronic circuits. Even if you never plan to design hardware or write software than controls hardware the introduction to boolean algebra this chapter provides is still important since you can use such knowledge to optimize certain complex conditional expressions within IF WHILE and other conditional statements.
The section on minimizing (optimizing) logic functions uses Veitch Diagrams or Karnaugh Maps. The optimizing techniques this chapter uses reduce the number of terms in a boolean function. You should realize that many people consider this optimization technique obsolete because reducing the number of terms in an equation is not as important as it once was. This chapter uses the mapping method as an example of boolean function optimization not as a technique one would regularly employ. If you are interested in circuit design and optimization you will need to consult a text on logic design for better techniques.
Although this chapter is mainly hardware-oriented keep in mind that many concepts in this text will use boolean equations (logic functions). Likewise some programming exercises later in this text will assume this knowledge. Therefore you should be able to deal with boolean functions before proceeding in this text.
Boolean algebra is a deductive mathematical system closed over the values zero and one (false and true). A binary operator "" defined over this set of values accepts a pair of boolean inputs and produces a single boolean value. For example the boolean AND operator accepts two boolean inputs and produces a single boolean output (the logical AND of the two inputs).
For any given algebra system there are some initial assumptions or postulates that the system follows. You can deduce additional rules theorems and other properties of the system from this basic set of postulates. Boolean algebra systems often employ the following postulates:
AB = BA
for all possible boolean
values A
and B
.(A % B) % C = A % (B % C)
for all boolean values
A
B
andC
.
A % (B # C) = (A % B) # (A % C)
for all boolean values
A B
andC.
A % I = A
.
A % I = B
and B<>A
(i.e. B is the opposite value of A in a boolean system).
For our purposes we will base boolean algebra on the following set of operators and values:
The two possible values in the boolean system are zero and one. Often we will call these values false and true (respectively).
The symbol "" represents the logical AND operation; e.g.
A B
is the
result of logically ANDing the boolean values A
and B
. When
using single letter variable names
this text will drop the "" symbol;
Therefore
AB
also represents the logical AND of the variables A
and B
(we will also call this the product of A
and B
).
The symbol "+" represents the logical OR
operation; e.g.
A + B is the result
of logically ORing the boolean values A
and B
. (We will also
call this the sum of A
and B.)
Logical complement
negation
or
not
is a unary operator. This text will use the ('
) symbol to denote logical
negation. For example
A'
denotes the logical NOT of A
.
If several different operators appear in a single boolean expression the result of the expression depends on the precedence of the operators. We'll use the following precedences (from highest to lowest) for the boolean operators: parenthesis logical NOT logical AND then logical OR. The logical AND and OR operators are left associative. If two operators with the same precedence are adjacent you must evaluate them from left to right. The logical NOT operation is right associative although it would produce the same result using left or right associativity since it is a unary operator.
We will also use the following set of postulates:
P1 Boolean algebra is closed under the AND OR and NOT operations.
P2 The identity element with respect to is one and + is zero. There is no identity element with respect to logical NOT.
P3 The and + operators are commutative.
P4 and + are distributive with respect to one another. That
is
A (B + C) = (A B) + (A C)
and A + (B C) = (A + B) (A + C).
P5 For every value A
there exists a value A'
such that AA' =
0 and A+A' = 1.
This value is the logical
complement (or NOT) of A.
P6 and + are both associative. That is
(AB)C = A(BC)
and (A+B)+C = A+(B+C)
.
You can prove all other theorems in boolean algebra using these postulates. This text will not go into the formal proofs of these theorems however it is a good idea to familiarize yourself with some important theorems in boolean algebra. A sampling include:
Th1: A + A = A
Th2: A A = A
Th3: A + 0 = A
Th4: A 1 = A
Th5: A 0 = 0
Th6: A + 1 = 1
Th7: (A + B)' = A' B'
Th8: (A B)' = A' + B'
Th9: A + AB = A
Th10: A (A + B) = A
Th11: A + A'B = A+B
Th12: A' (A + B') = A'B'
Th13: AB + AB' = A
Th14: (A'+B') (A' + B) = A'
Th15: A + A' = 1
Th16: A A' = 0
Theorems seven and eight above are known as DeMorgan's Theorems after the mathematician who discovered them.
The theorems above appear in pairs. Each pair (e.g. Th1 & Th2 Th3 & Th4 etc.) form a dual. An important principle in the boolean algebra system is that of duality. Any valid expression you can create using the postulates and theorems of boolean algebra remains valid if you interchange the operators and constants appearing in the expression. Specifically if you exchange the and + operators and swap the 0 and 1 values in an expression you will wind up with an expression that obeys all the rules of boolean algebra. This does not mean the dual expression computes the same values it only means that both expressions are legal in the boolean algebra system. Therefore this is an easy way to generate a second theorem for any fact you prove in the boolean algebra system.
Although we will not be proving any theorems for the sake of boolean algebra in this text we will use these theorems to show that two boolean equations are identical. This is an important operation when attempting to produce canonical representations of a boolean expression or when simplifying a boolean expression.
A boolean expression is a sequence of zeros ones and literals separated by boolean operators. A literal is a primed (negated) or unprimed variable name. For our purposes all variable names will be a single alphabetic character. A boolean function is a specific boolean expression; we will generally give boolean functions the name "F" with a possible subscript. For example consider the following boolean:
F0 = AB+C
This function computes the logical AND of A and B and then logically ORs this result with C. If A=1 B=0 and C=1 then F0 returns the value one (10 + 1 = 1).
Another way to represent a boolean function is via a truth table. The previous chapter used truth tables to represent the AND and OR functions. Those truth tables took the forms:
AND | 0 | 1 |
---|---|---|
0 | 0 | 0 |
1 | 0 | 1 |
OR | 0 | 1 |
---|---|---|
0 | 0 | 1 |
1 | 1 | 1 |
For binary operators and two input variables this form of a truth table is very natural and convenient. However reconsider the boolean function F0 above. That function has three input variables not two. Therefore one cannot use the truth table format given above. Fortunately it is still very easy to construct truth tables for three or more variables. The following example shows one way to do this for functions of three or four variables:
Truth Table for a Function with Four Variables |
|||||
F = AB + CD | BA | ||||
---|---|---|---|---|---|
00 | 01 | 10 | 11 | ||
DC | 00 | 0 | 0 | 0 | 1 |
01 | 0 | 0 | 0 | 1 | |
10 | 0 | 0 | 0 | 1 | |
11 | 1 | 1 | 1 | 1 |
In the truth tables above the four columns represent the four possible combinations of zeros and ones for A & B (B is the H.O. or leftmost bit A is the L.O. or rightmost bit). Likewise the four rows in the second truth table above represent the four possible combinations of zeros and ones for the C and D variables. As before D is the H.O. bit and C is the L.O. bit. The table below shows another way to represent truth tables. This form has two advantages over the forms above - it is easier to fill in the table and it provides a compact representation for two or more functions.
C | B | A | F = ABC | F = AB + C | F = A+BC |
---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 | 0 | 1 |
0 | 1 | 0 | 0 | 0 | 0 |
0 | 1 | 1 | 0 | 1 | 1 |
1 | 0 | 0 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 1 | 1 |
1 | 1 | 0 | 0 | 1 | 1 |
1 | 1 | 1 | 1 | 1 | 1 |
Note that the truth table above provides the values for three separate functions of three variables. Although you can create an infinite variety of boolean functions they are not all unique. For example F=A and F=AA are two different functions. By theorem two however it is easy to show that these two functions are equivalent that is they produce exactly the same outputs for all input combinations. If you fix the number of input variables there are a finite number of unique boolean functions possible. For example there are only 16 unique boolean functions with two inputs and there are only 256 possible boolean functions of three input variables. Given n input variables there are 2**(2**n) (two raised to the two raised to the nth power) unique boolean functions of those n input values. For two input variables 2**(2**2) = 2**4 or 16 different functions. With three input variables there are 2**(2**3) = 2**8 or 256 possible functions. Four input variables create 2**(2**4) or 2**16 or 65 536 different unique boolean functions. When dealing with only 16 boolean functions it's easy enough to name each function. The following table lists the 16 possible boolean functions of two input variables along with some common names for those functions:
Beyond two input variables there
are too many functions to provide specific names. Therefore
we will refer to the
function's number rather than the function's name. For example
F8
denotes
the logical AND of A
and B
for a two-input function and F
14
is the logical OR operation. Of course
the only problem is to determine a function's
number. For example
given the function of three variables F=AB+C
what is
the corresponding function number? This number is easy to compute by looking at the truth
table for the function (see Table 14). If we treat the values
for A
B
and C
as bits in a binary number with C
being the H.O. bit and A
being the L.O. bit
they produce the binary numbers
in the range zero through seven. Associated with each of these binary strings is a zero or
one function result. If we construct a binary value by placing the function result in the
bit position specified by A
B
and C
the resulting binary
number is that function's number. Consider the truth table for F=AB+C
: CBA: 7
6 5 4 3 2 1 0 F=AB+C : 1 1 1 1 1 0 0 0 If we treat the function values for F
as a binary number
this produces the value F816 or 248 (decimal). We will usually denote
function numbers in decimal. This also provides the insight into why there are 2**(2**n)
different functions of n variables: if you have n input variables
there are 2**n bits in
function's number. If you have m bits
there are 2**m different values. Therefore
for n
input variables there are m=2**n possible bits and 2**m or 2**(2**n) possible functions.
You can transform one boolean expression into an equivalent expression by applying the postulates the theorems of boolean algebra. This is important if you want to convert a given expression to a canonical form (a standardized form) or if you want to minimize the number of literals (primed or unprimed variables) or terms in an expression. Minimizing terms and expressions can be important because electrical circuits often consist of individual components that implement each term or literal for a given expression. Minimizing the expression allows the designer to use fewer electrical components and therefore can reduce the cost of the system. Unfortunately there are no fixed rules you can apply to optimize a given expression. Much like constructing mathematical proofs an individual's ability to easily do these transformations is usually a function of experience. Nevertheless a few examples can show the possibilities:
ab + ab' + a'b = a(b+b') + a'b By P4 = a1 + a'b By P5 = a + a'b By Th4 = a + a'b + 0 By Th3 = a + a'b + aa' By P5 = a + b(a + a') By P4 = a + b1 By P5 = a + b By Th4 (a'b + a'b' + b')' = ( a'(b+b') + b')' By P4 = (a' + b')' By P5 = ( (ab)' )' By Th8 = ab By definition of not b(a+c) + ab' + bc' + c = ba + bc + ab' + bc' + c By P4 = a(b+b') + b(c + c') + c By P4 = a1 + b1 + c By P5 = a + b + c By Th4
Although these examples all use algebraic transformations to simplify a boolean expression we can also use algebraic operations for other purposes. For example the next section describes a canonical form for boolean expressions. Canonical forms are rarely optimal.
Since there are a finite number of boolean functions of n
input variables
yet an infinite number of possible logic expressions you can construct
with those n input values
clearly there are an infinite number of logic expressions that
are equivalent (i.e.
they produce the same result given the same inputs). To help
eliminate possible confusion
logic designers generally specify a boolean function using a
canonical
or standardized
form. For any given boolean function there exists a unique
canonical form. This eliminates some confusion when dealing with boolean functions.
Actually
there are several different canonical forms. We will discuss only two here and
employ only the first of the two. The
first is the so-called sum of minterms and the second is the product of maxterms. Using
the duality principle
it is very easy to convert between these two. A term is a variable or a product (logical
AND) of several different literals. For example
if you have two variables
A and B
there
are eight possible terms: A
B
A'
B'
A'B'
A'B
AB'
and AB
.
For three variables we have 26 different terms: A
B
C
A'
B'
C'
A'B'
A'B
AB'
AB
A'C'
A'C
AC'
AC
B'C'
B'C
BC'
BC
A'B'C'
AB'C'
A'BC'
ABC'
A'B'C
AB'C
A'BC
and ABC.
As you can see
as the number of variables increases
the
number of terms increases dramatically. A minterm is a product
containing exactly n literals. For example
the minterms for two variables are A'B'
AB'
A'B
and AB
. Likewise
the minterms for three variables A
B
and C
are A'B'C'
AB'C'
A'BC'
ABC'
A'B'C
AB'C
A'BC
and
ABC
. In general
there are 2**n minterms for n variables. The set of possible
minterms is very easy to generate since they correspond to the sequence of binary numbers:
Binary Equivalent (CBA) | Minterm |
---|---|
000 | A'B'C' |
001 | AB'C' |
010 | A'BC' |
011 | ABC' |
100 | A'B'C |
101 | AB'C |
110 | A'BC |
111 | ABC |
We can specify any boolean function using a sum (logical OR) of minterms. Given F248=AB+C the equivalent canonical form is ABC+A'BC+AB'C+A'B'C+ABC'. Algebraically we can show that these two are equivalent as follows:
ABC+A'BC+AB'C+A'B'C+ABC'= BC(A+A') + B'C(A+A') + ABC' = BC1 +B'C1 + ABC' = C(B+B') + ABC' = C + ABC' = C + AB
Obviously the canonical form is not the optimal form. On the other hand there is a big advantage to the sum of minterms canonical form: it is very easy to generate the truth table for a function from this canonical form. Furthermore it is also very easy to generate the logic equation from the truth table. To build the truth table from the canonical form simply convert each minterm into a binary value by substituting a "1" for unprimed variables and a "0" for primed variables. Then place a "1" in the corresponding position (specified by the binary minterm value) in the truth table: 1) Convert minterms to binary equivalents:
F248 = CBA + CBA' + CB'A + CB'A' + C'BA = 111 + 110 + 101 + 100 + 011
2) Substitute a one in the truth table for each entry above
C | B | A | F = AB+C |
---|---|---|---|
0 | 0 | 0 | |
0 | 0 | 1 | |
0 | 1 | 0 | |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 1 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 |
Finally put zeros in all the entries that you did not fill with ones in the first step above:
C | B | A | F = AB+C |
---|---|---|---|
0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 |
0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 1 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 |
Going in the other direction generating a logic function from a truth table is almost as easy. First locate all the entries in the truth table with a one. In the table above these are the last five entries. The number of table entries containing ones determines the number of minterms in the canonical equation. To generate the individual minterms substitute A B or C for ones and A' B' or C' for zeros in the truth table above. Then compute the sum of these items. In the example above F248 contains one for CBA = 111 110 101 100 and 011. Therefore F248 = CBA + CBA' + CB'A + CB'A' + C'AB. The first term CBA comes from the last entry in the table above. C B and A all contain ones so we generate the minterm CBA (or ABC if you prefer). The second to last entry contains 110 for CBA so we generate the minterm CBA'. Likewise 101 produces CB'A; 100 produces CB'A' and 011 produces C'BA. Of course the logical OR and logical AND operations are both commutative so we can rearrange the terms within the minterms as we please and we can rearrange the minterms within the sum as we see fit. This process works equally well for any number of variables. Consider the function F53504 = ABCD + A'BCD + A'B'CD + A'B'C'D. Placing ones in the appropriate positions in the truth table generates the following:
The remaining elements in this truth table all contain zero. Perhaps the easiest way to generate the canonical form of a boolean function is to first generate the truth table for that function and then build the canonical form from the truth table. We'll use this technique for example when converting between the two canonical forms this chapter presents. However it is also a simple matter to generate the sum of minterms form algebraically. By using the distributive law and theorem 15 (A + A' = 1) makes this task easy. Consider F248 = AB + C. This function contains two terms AB and C but they are not minterms. Minterms contain each of the possible variables in a primed or unprimed form. We can convert the first term to a sum of minterms as follows:
AB = AB 1 By Th4 = AB (C + C') By Th 15 = ABC + ABC' By distributive law = CBA + C'BA By associative law
Similarly we can convert the second term in F248 to a sum of minterms as follows:
C = C 1 By Th4 = C (A + A') By Th15 = CA + CA' By distributive law = CA 1 + CA'1 By Th4 = CA (B + B') + CA' (B + B') By Th15 = CAB + CAB' + CA'B + CA'B' By distributive law = CBA + CBA' + CB'A + CB'A' By associative law
The last step (rearranging the terms) in these two conversions is optional. To obtain the final canonical form for F248 we need only sum the results from these two conversions:
F248 = (CBA + C'BA) + (CBA + CBA' + CB'A + CB'A') = CBA + CBA' + CB'A + CB'A' + C'BA
Another way to generate a canonical form is to use products of maxterms. A maxterm is the sum (logical OR) of all input variables primed or unprimed. For example consider the following logic function G of three variables:
G = (A+B+C) (A'+B+C) (A+B'+C).
Like the sum of minterms form there is exactly one product of maxterms for each possible logic function. Of course for every product of maxterms there is an equivalent sum of minterms form. In fact the function G above is equivalent to
F248 = CBA + CBA' + CB'A + CB'A' + C'BA = AB +C.
Generating a truth table from the product of maxterms is no more difficult than building it from the sum of minterms. You use the duality principle to accomplish this. Remember the duality principle says to swap AND for OR and zeros for ones (and vice versa). Therefore to build the truth table you would first swap primed and non-primed literals. In G above this would yield:
G = (A' + B' + C') (A + B' + C') (A' + B + C')
The next step is to swap the logical OR and logical AND operators. This produces
G = A'B'C' + AB'C' + A'BC'
Finally you need to swap all zeros and ones. This means that you store zeros into the truth table for each of the above entries and then fill in the rest of the truth table with ones. This will place a zero in entries zero one and two in the truth table. Filling the remaining entries with ones produces F248. You can easily convert between these two canonical forms by generating the truth table for one form and working backwards from the truth table to produce the other form. For example consider the function of two variables F7 = A + B. The sum of minterms form is F7 = A'B + AB' + AB. The truth table takes the form:
F7 | A | B |
---|---|---|
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 1 |
1 | 1 | 1 |
Working backwards to get the product of maxterms we locate all entries that have a zero result. This is the entry with A and B equal to zero. This gives us the first step of G=A'B'. However we still need to invert all the variables to obtain G=AB. By the duality principle we need to swap the logical OR and logical AND operators obtaining G=A+B. This is the canonical product of maxterms form. Since working with the product of maxterms is a little messier than working with sums of minterms this text will generally use the sum of minterms form. Furthermore the sum of minterms form is more common in boolean logic work. However you will encounter both forms when studying logic design.
Table of Content | Chapter Two (Part 2) |
Chapter Two: Boolean Algebra (Part 1)
26 SEP 1996