Boolean Expressions from Truth Tables
Created | Updated Apr 7, 2005
This entry describes how algebraic expressions can be formulated to accurately represent functions which are defined only as Boolean Truth Tables. This must involve some algebra, but it is not terribly complicated, and is mainly used to provide nomenclature for the processes involved. The methods given are systematic, always producing a correct result whatever the given function, and suitable for computer implementation.
The expressions obtained may be simplified by algebraic or other means, but such techniques are beyond the scope of this entry. In all cases, the expression is obtained using only the AND, OR and NOT functions. The methods do give comparatively simple expressions if the truth table of the given function has been well abbreviated.
Basic Concepts
Given a function F, with n arguments X1, X2 … Xn, we can write Y = F ( X1,X2 … Xn ), signifying that Y can be obtained by applying the function F to the given arguments. The objective is to find an expression for Y in terms of those arguments, given only the definition of F as a valid truth table. To do this, the properties of Boolean functions can be used
The logical sum, that is Boolean OR, of several values is true if any of the values is true, and is false only if all the values are false.
The logical product, that is Boolean AND, of several values is false if any of the values is false, and is true only if all the values are true.
The definition of the Boolean NOT function ensures that NOT ( false ) = true and NOT ( true ) = false
These properties, which are essentially just the definitions of the OR, AND and NOT functions, are all that are necessary.
Strategy
The methods are generalisations of the fundamental techniques producing the canonical forms1 of a function F from the complete, unabbreviated truth table. As F has n arguments, such a truth table has 2n entries, one for each combination of the argument values.
If F is constant, that is has a value which is always true or always false, then trivially the expression required is Y = true or Y = false, and does not refer to the arguments. In non-trivial cases, the truth table is a mixture of entries for which F is true, and entries for which F is false.
One strategy is to select the entries for which F is true, and for each such entry in turn, an expression which is true is formed. The logical sum of these expressions is then true whenever F is true, but there is a danger that the resulting expression is also true sometimes when F is false. This does not occur when the expression formed for each entry is true for that entry and no other, and these minimally true expressions are known as minterms. The representation of F is then obtained as the logical sum of the selected minterms.
The minterm for an entry is formed by using each argument in turn to form an element, and the minterm is the product of such elements. An element uses its argument literally if its value is given as true, but complemented if given as false, so that the resulting element is true for the stipulated argument value. The logical product of these elements is then also true for the argument values stipulated for the entry. When one or more argument values are changed, the corresponding elements become false, and their logical product also becomes false. The combination of argument values of every entry is unique, so the value of the product of elements is true for only one entry of the truth table. For example, in row 5 of the table below, X1 is true, X2 is false and X3 is true. So X1, being true, appears literally as X1, X2, being false, appears complemented as NOT X2, and X3, being true, appears literally as X3. The resulting minterm for row 5 is thus X1 AND NOT X2 AND X3.
A similar, equally valid strategy is to select the entries for which F is false, and for each such entry in turn, an expression which is false is formed. The logical product of these expressions is false whenever F is false, but could also be false when F is true. When the expression formed for each entry is false for that entry alone, it is true for every other entry, and such maximally true expressions are known as maxterms. A representation of F is then obtained as the logical product of the selected maxterms.
The maxterm for an entry is formed by using each argument in turn to form an element, and the maxterm is the sum of such elements. An element uses its argument literally if its value is given as false, but complemented if given as true, so that the resulting element is false for the stipulated argument value. The logical sum of these elements is then also false for the argument values stipulated for the entry. When one or more argument values are changed, the corresponding elements become true, and their logical sum also becomes true. The combination of argument values of every entry is unique, so the value of the sum of elements is false for only one entry of the truth table. For example, in row 5 of the table below, X1 is true, X2 is false and X3 is true. So X1, being true, appears complemented as NOT X1, X2, being false, appears literally as X2, and X3, being true, appears literally as NOT X3. The resulting maxterm for row 5 is thus NOT X1 OR X2 OR NOT X3.
Canonical Forms
The representations of a function F as a logical sum of minterms, or a logical product of maxterms, are known as the canonical forms of F. The constructions given above ensure the existence of both forms when F is not constant, and using the conventions that an empty sum of zero minterms is regarded as false and an empty product of zero maxterms is regarded as true, apply even when the function F is constant.
The selection of minterms and maxterms depends upon the value given for the function F in a particular entry, but the term formed does not. The minterms and maxterms can be formed for all argument combinations, and the following table gives every minterm and maxterm for any function of three variables as an example.
|
The sum of minterms uses the OR function to form the sum, unless there is a single minterm. The minterms use the AND function, unless there is a single argument, and the NOT function unless all arguments have the value true in the particular minterm. The canonical sum of products requires the AND, OR and NOT functions only. Similarly, the canonical product of sums uses the AND function to form the product, unless there is a single maxterm. The maxterms use the OR function, unless there is a single argument, and the NOT function unless all arguments have the value true in the particular maxterm. The canonical product of sums requires the AND, OR and NOT functions only.
Both canonical forms use only the AND, OR and NOT functions, but tend to give complicated expressions, because the terms always involve all the function arguments. The problem is illustrated by three examples
the function which is false for row 0 only, and true for all the others. The product of maxterms has only one maxterm, and gives F ( X1,X2,X3 ) = X1 OR X2 OR X3, but the entirely equivalent sum of minterms is a horrendous expression, the sum of all minterms in rows 1, 2, 3, 4, 5, 6 and 7.
the function which is true for row 7 only, and false for all the others. The sum of minterms has only one minterm, and gives F ( X1,X2,X3 ) = X1 AND X2 AND X3, but the entirely equivalent product of maxterms is a horrendous expression, the product of all maxterms in rows 0, 1, 2, 3, 4, 5 and 6.
the function which is false for rows 0, 1, 2 and 3, and true for rows 4, 5, 6 and 7, which is the function F ( X1,X2,X3 ) = X1. The canonical forms are the sum of the minterms of rows 4, 5, 6 and 7, and the product of the maxterms of rows 0, 1, 2 and 3. Both expressions are rather complicated, but are equivalent to X1.
The canonical forms always exist, and so always provide a means to form expressions. These expressions can, if necessary, be reduced to simpler form by algebraic methods (which are beyond the scope of this entry). However, it is sometimes useful to obtain the canonical forms, particularly for functions which cannot be simplified. For example, the exclusive OR function of two variables has the truth table
|
The required terms are shown in bold, and give the equivalent expressions for the exclusive OR of X1 and X2 as ( NOT X1 AND X2 ) OR ( X1 AND NOT X2 ) = ( X1 OR X2 ) AND ( NOT X1 OR NOT X2 )
Generalisation
The constructions given need only slight adaptation to be applied to abbreviated tables, to give expressions in the forms of a sum of products or a product of sums. In forming terms, each argument with a don't care value is simply ignored - that argument is not present in the term being formed.
The final expression is then simpler for two reasons. Each term is simpler, by virtue of the argument omitted, and as each entry with don't care values represents at least two raw entries, there are less terms formed.
The validity of the final expression is guaranteed by the procedure used to abbreviate a table, and the validity of the canonical forms. Each don't care arises by merging two entries for which the function value is fixed, a step which corresponds to an algebraic simplification which depends upon the function value.
When the function value is true, that entry contributes to the sum of products only, as the maxterms are never selected. If there are two entries which differ only in the value given to Xj say, the original products would be of the form NOT Xj AND (rest) and Xj AND (rest), where (rest) denotes the contribution from the remaining arguments. The total contribution to the sum is then ( NOT Xj AND (rest) ) OR ( Xj AND (rest) ), which can be written in the form ( NOT Xj OR Xj) AND (rest), which as NOT Xj OR Xj is always true, reduces to (rest), the contribution of the other arguments. The argument Xj is omitted, but it is also these circumstances that cause Xj to be given a don't care value.
Similarly, when the function value is false, that entry contributes to the product of sums only, as the minterms are never selected. If two entries differ only in the value given to Xj, the original sums would be of the form NOT Xj OR (rest) and Xj OR (rest), and contribute ( NOT Xj OR (rest) ) AND ( Xj OR (rest) ) to the product. This is ( NOT Xj AND Xj ) OR ( (rest) AND Xj ) OR ( NOT Xj AND (rest) ) OR ( (rest) AND (rest) ), which as NOT Xj AND Xj is always false reduces to (rest) AND ( NOT Xj OR NOT Xj OR (rest) ), and then as just (rest), the contribution of the other arguments. The argument Xj is omitted, but it is also these circumstances that cause Xj to be given a don't care value.
The abbreviation process may also involve the duplication of entries. Visualised in terms of the canonical forms, this directly corresponds to adding redundant terms. In the sum of products form, this may result in more than one term being simultaneously true, but does not change the overall sum. In the product of sums form, this may result in more than one term being simultaneously false, does this does change change the overall product. When such redundant lines are merged to give more don't care values, the same things happen. In the sum of products, more than one product may be true, or in the product of sums, more than one sum may be false, but in neither case is the value changed.
The above considerations together validate the simple rule given for the modified terms which arise from abbreviated tables. Note that the terms produced can now longer be called minterms or maxterms, but are just products and sums respectively.
It is instructive to reconsider the three examples given for the canonical form, but with optimally abbreviated truth tables. In every one of those cases, the simplest expression emerges naturally.
The truth table for the OR function, with used terms shown in bold, simplfies to
|
The truth table for the AND function, with used terms shown in bold, simplfies to
|
The function
F ( X1,X2,X3 ) = X1, with used terms shown in bold, simplfies to
|
defined later
