Boolean Algebra | Truth Tables | Expressions from Truth Tables
Universal Functions | Function Reduction | Functions Classified

Boolean algebra is the branch of mathematical logic that considers functions which can have only two possible values, true and false. Boolean functions are usually presented in one of two ways: as a truth table, listing the function value for every possible combination of input values, or as an algebraic expression, combining the input values using logical operators such as AND, OR and NOT.

This Entry shows how to convert a function given as a Boolean Truth Table into an equivalent algebraic expression. 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 are suitable for computer implementation. Throughout the rest of this Entry, we will use the logician's term 'arguments' to denote the input values.

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 give comparatively simple expressions if the truth table of the given function has been well abbreviated.

Basic Concepts

Given a function F, with arguments A, B, C etc, we can write Y = F ( A, B, C, … ), 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 argument values is true if one or more of the argument values is true and is false only if all the argument values are false.

• The logical product, that is Boolean AND, of several argument values is false if any of the argument values is false and is true only if all the argument values are true.

• The definition of the Boolean NOT function ensures that NOT false = true and NOT true = false.

Note that the AND function is considered to be a product, not a sum¹. These properties, which are essentially just the definitions of the OR, AND and NOT functions, are all that are necessary.

Strategy

We start by considering the complete, unabbreviated truth table. If F has n arguments, such a truth table has 2ⁿ entries², one for each possible combination of the argument values.

The truth table is a mixture of entries for which F is true and entries for which F is false³.

There are two complementary methods for converting each entry in a truth table into an algebraic expression; one produces the minterm and the other the maxterm.

Creating Minterms

One strategy is to select the entries for which F is true and for each such entry in turn, an expression is formed which is true for this particular combination of arguments and no other. The logical sum of these expressions is then true whenever F is true. These minimally true expressions are known as minterms. The algebraic expression of F is then obtained as the logical sum (the OR) of the selected minterms.

We make a minterm for an entry by writing down all the arguments. For those which have a value of false, we change them to true by putting a NOT in front of them, then combine all the arguments together using the logical AND function. So for example, if a function has three arguments, A, B and C and the function is true when A is true, B is false and C is true, then we write:

A, NOT B, C

Then we combine them using the logical AND so that the appropriate minterm is the logical product:

A AND NOT B AND C

Creating Maxterms

A similar, equally valid strategy is to select the entries for which F is false; for each such entry in turn, an expression is formed which is false for this particular combination of arguments and no other. The logical product of these expressions is then false whenever F is false. These maximally true expressions are known as maxterms. The algebraic expression of F is then obtained as the logical product (the AND) of the selected maxterms.

We make a maxterm for an entry by writing down all the arguments. For those which have a value of true, we change them to false by putting a NOT in front of them, then combine all the arguments together using the logical OR function. So for example, if a function has three arguments, A, B and C and the function is false when A is true, B is true and C is false, then we write:

NOT A, NOT B, C

Then we combine them using the logical OR so that the appropriate maxterm is the logical sum:

NOT A OR NOT B OR C

Combining The Terms

At this point the function F defined by the truth table has been converted from a table of argument values into a series of minterms (when F is true) and maxterms (when F is false), each term being equivalent to one entry in the original table. As stated in the strategy these algebraic expressions can be combined into a single expression (either as the logical sum of all the minterms or the logical product of all the maxterms), which represents the function. The two methods provide the two canonical forms of the truth table.

Canonical Forms

The algebraic expressions 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 methods for creating minterms and maxterms given above ensure the existence of both forms when F is not constant⁴.

While minterms and maxterms can always be constructed for any combination of argument values, it is important to remember that only those relevant to the function value need to be considered when constructing a canonical form: minterms when F is true, maxterms when F is false.

The following table lists the minterm and maxterm for each possible combination of arguments of a function with three arguments:

Minterms are formed using the AND and NOT functions and are joined together using the OR function. Maxterms are formed using the OR and NOT functions and are joined together using the AND function.

Unfortunately, the canonical forms tend to contain 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 ( A,B,C ) = A OR B OR C, 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 ( A,B,C ) = A AND B AND C, 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 (A,B,C) = A. 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 A.

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 necessary to use 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 A and B as ( NOT A AND B ) OR ( A AND NOT B ) = ( A OR B ) AND ( NOT A OR NOT B ).

Generalisation

The methods given need only slight adaptation to be applied to abbreviated tables⁵; that is, ones with don't care values, 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.

Mathematical Validity of the Process for Abbreviated Tables

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 J say, the original products would be of the form NOT J AND (rest) and J AND (rest), where (rest) denotes the contribution from the remaining arguments. The total contribution to the sum is then ( NOT J AND (rest) ) OR ( J AND (rest) ), which can be written in the form ( NOT J OR J) AND (rest), which, as NOT J OR J is always true, reduces to (rest), the contribution of the other arguments. The argument J is omitted, but it is also these circumstances that cause J 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 J, the original sums would be of the form NOT J OR (rest) and J OR (rest) and contribute ( NOT J OR (rest) ) AND ( J OR (rest) ) to the product. The algebraic manipulation is more complicated, but once again it can be shown that the Js drop out and this reduces to just (rest), the contribution of the other arguments. The argument J is omitted, but it is also these circumstances that cause J 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, but this does not 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 no longer be called minterms or maxterms, but are just products and sums respectively.

Examples of Abbreviated Tables

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, simplifies to

The algebraic expression can be read off from either the products in sum column or the sums in product column as:

F ( A,B,C ) = A OR B OR C

The truth table for the AND function, with used terms shown in bold, simplifies to

The algebraic expression can be read off from either the products in sum column or the sums in product column as:

F ( A,B,C ) = A AND B AND C

The function F ( A,B,C ) = A is independent of two of its arguments. Its truth table, with used terms shown in bold, simplifies to:

The algebraic expression can be read off from either the products in sum column or the sums in product column as:

F ( A,B,C ) = A