The 16 Possible Boolean Functions of Two Variables
B. Also equivalent to A<>B.
Art of Assembly/Win32 Edition is now available. Let me read that version.
PLEASE: Before emailing me asking how to get a hard copy of this text, read this.
Important Notice: As you have probably discovered by now, I am no longer updating this document. The reason is quite simple: I'm working on a Windows version of "The Art of Assembly Language Programming". In the past I have encouraged individuals to send me corrections to this text. However, as I am no longer updating this material. However, I am collecting errata that I will post to Webster someday, so feel free to continue sending corrections to AoA/DOS (16-bit) to rhyde@cs.ucr.edu. If you're more interested in leading edge material, please see the information about the Win/32 edition, above.
AB = BA for all possible boolean values A and B.(A % B) % C = A % (B % C)
for all boolean valuesA,B, andC.
A % (B # C) = (A % B) # (A % C)
for all boolean valuesA, 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.
F0 = AB+C| AND | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| OR | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 1 |
| F = AB + C | BA | ||||
|---|---|---|---|---|---|
| 00 | 01 | 10 | 11 | ||
| C | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | |
| 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 | |
| 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 |
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 on page 50). 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.
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.
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 |
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 |
| 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 |
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 |