Canonical normal form
[Quick review of Boolean algebra basics: all variables take on the values 0 or 1 only, sometimes referred to as false and true respectively because George Boole focused on a "propositional calculus" (the logic of true and false propositions) rather than binary numbers as such. The only interesting function of one variable is complement, which changes 0 to 1 or 1 to 0, and is denoted by a trailing apostrophe; e.g. x' means the complement of x. There are sixteen possible functions of two variables, but in digital logic hardware, the simplest gate circuits implement only four of them: conjunction (AND), disjunction (inclusive OR), and the complements of those (NAND and NOR). The usual notation for AND is that of multiplication; e.g. x y means x AND y. The usual notation for OR is that of addition; e.g. x + y means x OR y. Most gate circuits accept more than 2 input variables; for example, the spaceborne Apollo Guidance Computer, which pioneered the application of integrated circuits in the 1960s, was built with only one type of gate, a 3-input NOR. The usual purpose of doing Boolean algebra is to simplify the design of a digital circuit that performs a function, either to minimize the number of gates, or to minimize the time for the value of the function to settle down after a change in its input(s), or some other practical criterion.] Template:Technical (expert) In Boolean algebra, any Boolean function can be expressed in a canonical form using the dual concepts of minterms and maxterms. Minterms are called products because they are the AND of a set of variables, and maxterms are called sums because they are the OR of a set of variables (further definition appears in the sections headed Minterms and Maxterms below). These concepts are called duals because of their mirror-image symmetrical relationship as expressed by De Morgan's laws, which state that AND(x,y,z,...) = NOR(x',y',z',...) and OR(x,y,z,...) = NAND(x',y',z',...).
The dual canonical forms of any Boolean function are a "sum of minterms" and a "product of maxterms." The term "Sum of Products" or "SoP" is widely used for the canonical form that is a disjunction (OR) of minterms. Its De Morgan dual is a "Product of Sums" or "PoS" for the canonical form that is a conjunction (AND) of maxterms. These forms allow for greater analysis into the simplification of these functions, which is of great importance in the minimization or other optimization of digital circuits.
Minterms
For a boolean function of variables , a product term in which each of the variables appears once (in either its complemented, or uncomplemented form) is called a minterm. Thus, a minterm is a logical expression of n variables that employs only the complement operator and the conjunction operator.
For example, , and are examples of minterms for a Boolean function of the three variables , and . The customary reading of the last of those is a AND b AND NOT-c.
There are 2n minterms of n variables, since a variable in the minterm expression can be in either its direct or its complemented form--two choices per n variables.
Indexing minterms
In general, one assigns each minterm an index based on a conventional binary encoding of the complementation pattern of the variables (where the variables in all the minterms are written in the same order, usually alphabetical). This convention assigns the value 1 to the direct form () and 0 to the complemented form (). For example, we assign the index 6 to the minterm (110) and denote that minterm as . Similarly, of the same three variables is (000), and is (111).
Functional equivalence
It is apparent that minterm n gives a true value (i.e., 1) for just one combination of the input variables. For example, minterm 5, a b' c, is true only when a and c both are true and b is false--the input arrangement where a = 1, b = 0, c = 1 results in 1.
If one is given a truth table of a logical function, it is possible to write the function as a "sum of products". This is a special form of disjunctive normal form. For example, if given the truth table for the arithmetic sum bit u of one bit position's logic of an adder circuit, as a function of x and y from the addends and the carry in, ci:
| ci | x | y | u(ci,x,y) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
Observing that the rows that have an output of 1 are the 2nd, 3rd, 5th, and 8th, we can write u as a sum of minterms and . If we wish to verify this: u(ci, x, y) = = (ci' x' y) + (ci' x y') + (ci x' y') + (ci x y) evaluated for all 8 combinations of the three variables will match the table.
Maxterms
A maxterm is a logical expression of n variables that employs only the complement operator and the disjunction operator. Maxterms are a dual of the minterm idea (i.e., exhibiting a complementary symmetry in all respects). Instead of using ANDs and complements, we use ORs and complements and proceed similarly.
For example, the following are two of the eight maxterms of three variables:
- a+b'+c
- a'+b+c
There are again 2n maxterms of n variables, since a variable in the maxterm expression can also be in either its direct or its complemented--two choices per n variables.
Indexing maxterms
Each maxterm is assigned an index based on the opposite conventional binary encoding used for minterms. The maxterm convention assigns the value 0 to the direct form and 1 to the complemented form . For example, we assign the index 6 to the maxterm (110) and denote that maxterm as M6. Similarly M0 of these three variables is (000) and M7 is (111).
TEMP HALT IN EXPANSION
Functional equivalence
It is apparent that maxterm n gives a false value (i.e., 0) for just one combination of the input variables. For example, maxterm 5, a' + b + c', is false only when a and c both are true and b is false--the input arrangement where a = 1, b = 0, c = 1 results in 0.
If one is given a truth table of a logical function, it is possible to write the function as a "product of sums". This is a special form of conjunctive normal form. For example, if given the truth table for the carry-out bit co of one bit position's logic of an adder circuit, as a function of x and y from the addends and the carry in, ci:
| ci | x | y | co(ci,x,y) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Observing that the rows that have an output of 0 are the 1st, 2nd, 3rd, and 5th, we can write co as a product of maxterms and . If we wish to verify this: co(ci, x, y) = = (ci + x + y) (ci + x + y') (ci + x' + y) (ci' + x + y) evaluated for all 8 combinations of the three variables will match the table.
Dualization
The complement of a minterm is the respective maxterm. This can be easily verified by using de Morgan's law. For example
- m1' = M1
- (a'b)' = a+b'
Non canonical PoS and SoP forms
It is often the case that the canonical minterm form can be simplified to an equivalent SoP form. This simplified form would still consist of a sum of product terms. However, in the simplified form it is possible to have fewer product terms and/or product terms that contain fewer variables (=that are shorter). For example, the following 3-variable function:
a b c f(a, b, c) 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1
Has the canonical minterm representation: But it has an equivalent simplified form: In this trivial example it is obvious that but the simplified form has both fewer product terms, and the term has fewer variables. The most simplified SoP representation of a function is referred to as a minimal SoP form.
In the similar manner, a canonical maxterm form can have a simplified PoS form.
A convenient method for finding the minimal PoS/SoP form of a function with up to four variables is using a Karnaugh map.
The minimal PoS and SoP forms are very important for finding optimal implementations of boolean functions and minimizing logic circuits.