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:

• Closure. The boolean system is closed with respect to a binary operator if for every pair of boolean values, it produces a boolean result. For example, logical AND is closed in the boolean system because it accepts only boolean operands and produces only boolean results.

• Commutativity. A binary operator "%" is said to be commutative if AB = BA for all possible boolean values A and B.

• Associativity. A binary operator "%" is said to be associative if

(A % B) % C = A % (B % C)

for all boolean values A, B, and C.

• Distribution. Two binary operators "%" and "#" are distributive if

A % (B # C) = (A % B) # (A % C)

for all boolean values A, B, and C.

• Identity. A boolean value I is said to be the identity element with respect to some binary operator "%" if

A % I = A.

• Inverse. A boolean value I is said to be the inverse element with respect to some binary operator "%" if

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:

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:

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.

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:

The 16 Possible Boolean Functions of Two Variables
Function #	Description
0	Zero or Clear. Always returns zero regardless of A and B input values.
1	Logical NOR (NOT (A OR B)) = (A+B)'
2	Inhibition = BA' (B, not A). Also equivalent to B>A or A < B.
3	NOT A. Ignores B and returns A'.
4	Inhibition = AB' (A, not B). Also equivalent to A>B or B<A.
5	NOT B. Returns B' and ignores A
6	Exclusive-or (XOR) = A B. Also equivalent to A<>B.
7	Logical NAND (NOT (A AND B)) = (A·B)'
8	Logical AND = A·B. Returns A AND B.
9	Equivalence = (A = B). Also known as exclusive-NOR (not exclusive-or).
10	Copy B. Returns the value of B and ignores A's value.
11	Implication, B implies A = A + B'. (if B then A). Also equivalent to B >= A.
12	Copy A. Returns the value of A and ignores B's value.
13	Implication, A implies B = B + A' (if A then B). Also equivalent to A >= B.
14	Logical OR = A+B. Returns A OR B.
15	One or Set. Always returns one regardless of A and B input values.

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 F14 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:

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

Finally, put zeros in all the entries that you did not fill with ones in the first step above:

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:

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.

Chapter Two: Boolean Algebra (Part 1)
26 SEP 1996