Department of Computer Science Course: CS 3724

Canonical forms of switching functions:

We know that it is possible to construct a truth table for any switching function (i.e., any function of switching variables.) However, such a truth table does not aid us directly in constructing a set of logic gates which can be used to evaluate the function, or to design a logic circuit. The truth table is useful in that it does provide a complete, unique description of the switching function, but it is cumbersome.

We can derive from the truth table certain unique expressions which defines the function exactly; in fact, the expression is exactly equivalent to the truth table and consequently shares the properties of the truth table. One such expression is called the minterm form of the expression, or, alternately, the sum of products (SOP) form.

e.g., for the function , the truth table is:

A B

0 0 0

0 1 1

1 0 1

1 1 0

This is equivalent to

This is the minterm form, or sum of products form, of the function. It is obtained by ANDing together the variables, or their complements, which have a 1 in the function column. If the variable has value 1, the variable is taken; if not, its complement is taken. Each of these ANDs of all the variables, or their complements, is called a minterm. The minterms are then ORed together to give the function specified in the truth table.

Note:

1. Each minterm contains all the variables or their complements, exactly once.
2. Each minterm is unique, except for permutation of the variables. Therefore, the minterm form of the function is unique.
3. Any expression which contains only variables in the minterm (sum of products) form, where each product term contains all the variables, or their complement, exactly once, is a minterm expression. This means that, no matter how a function is derived, if it contains only minterms then it must be a minterm form of the function.

Comment: The properties of switching functions which allow this kind of simplification are:

1. The AND of any set of variables which results in a 1 is unique.
2. Any terms equal to 1 which are ORed together still equal 1. (i.e., 1 + A = 1).

A dual form of the preceding, called a maxterm form, or product of sums (POS) form can also be written. The maxterm form of a function can be obtained from the truth table for a function by applying the principle of duality to the way described previously for deriving the minterm form of a function. Another way to find the maxterm form of a function is to write down the minterm expression for the complement of the function, , and apply de Morgans theorem; e.g.,

A B

0 0 0 1

0 1 1 0

1 0 1 0

1 1 0 1

In minterm form,

Complementing both sides,

Applying de Morgans theorem,

This is the maxterm form of the switching functions It can be obtained easily from the truth table by ORing together all the variables or their complements which give a zero for the function; if the variable has value 0 then it is ORed directly, if it has a value 1, it is complemented. Each term is called a maxterm, or a sum term. The expression is equal to the AND of all the maxterms, and is said to be the maxterm form of the function.

Example: Find the minterm and maxterm expressions corresponding to the following truth table:

A B C Y Minterms Maxterms

0 0 0 0 1

1 0 0 1 0

2 0 1 0 1

3 0 1 1 1

4 1 0 0 0

5 1 0 1 0

6 1 1 0 1

7 1 1 1 1

Minterm form:

(Note that as many minterms are used as the number of 1's in the truth table for Y.)

Maxterm form:

(Note that as many maxterms are used as the number of 0's in the truth table for Y.)

Sometimes the minterm and maxterm expression are written in a kind of ``shorthand,'' where the values (0 or 1) of the set of variables is used to form a binary number, the decimal equivalent of which designates the appropriate minterm or maxterm. e.g., the minterm form of the above function is written as:

The maxterm form is written as:

Note that the order in which the variable are written down in the truth table is important, in this case. Also, note that the possible numbers have values from 0 to where n is the number of variables, and that the numbers which appear in the minterm form do not appear in the maxterm form, and vice versa.

The minterm or maxterm form of the function is not usually the simplest or most concise; e.g., the preceding function can be simplified as follows; from the minterm form:

Systematic ways exist to reduce the complexity of minterm or maxterm forms of switching functions but we will not discuss them here. The problem is computationally complex for functions with a large number of variables (more than 20 variables is considered quite complex) but for a small number of variables (up to 6 or 8) interesting techniques are available.

The following is an algorithm for finding the minterm form of a switching function of n variables :

1. Expand the expression fully, eliminating all parentheses. This should result in a set of AND terms, all of which are ORed together.
2. Examine each AND term; if it is a minterm (i.e., if it contains each variables or its complement exactly once) retain it, and consider the next term.
3. In each AND expression which is not a minterm, for each variables which does not occur, AND the expression with
4. Expand each expression and eliminate redundant terms.

Example: We can find the minterm expression for , the function we previously simplified, as follows:

as before.

In a similar way, we can write an algorithm to derive the maxterm form of a switching function. In this case, step (2) becomes:

2

In each OR expression which is not a maxterm, for each variable which does not occur, OR the expression with

Step (3) will normally require the use of the distributivity theorem

Example: Find the maxterm form of

as before.