Propositional Formula - Normal Forms - Reduction By Use of The Map Method (Veitch, Karnaugh) - (3) Reduce Minterms

(3) Reduce Minterms

Minterms of adjacent (abutting) 1-squares (T-squares) can be reduced with respect to the number of their literals, and the number terms also will be reduced in the process. Two abutting squares (2 x 1 horizontal or 1 x 2 vertical, even the edges represent abutting squares) loose one literal, four squares in a 4 x 1 rectangle (horizontal or vertical) or 2 x 2 square (even the four corners represent abutting squares) loose two literals, eight squares in a rectangle loose 3 literals, etc. (One seeks out the largest square or rectangles and ignores the smaller squares or rectanges contained totally within it. ) This process continues until all abutting squares are accounted for, at which point the propositional formula is minimized.

For example, squares #3 and #7 abut. These two abutting squares can loose one literal (e.g. "p" from squares #3 and #7), four squares in a rectangle or square loose two literals, eight squares in a rectangle loose 3 literals, etc. (One seeks out the largest square or rectangles.) This process continues until all abutting squares are accounted for, at which point the propositional formula is said to be minimized.

Example: The map method usually is done by inspection. The following example expands the algebraic method to show the "trick" behind the combining of terms on a Karnaugh map:

Minterms #3 and #7 abut, #7 and #6 abut, and #4 and #6 abut (because the table's edges wrap around). So each of these pairs can be reduced.

Observe that by the Idempotency law (A V A) = A, we can create more terms. Then by association and distributive laws the variables to disappear can be paired, and then "disappeared" with the Law of contradiction (x & ~x)=0. The following uses brackets only to keep track of the terms; they have no special significance:

• Put the formula in conjunctive normal form with the formula to be reduced:

q = ( (~p & d & c ) V (p & d & c) V (p & d & ~c) V (p & ~d & ~c) ) = ( #3 V #7 V #6 V #4 )

• Idempotency (absorption) [ A V A) = A:

( #3 V V V #4 )

• Associative law (x V (y V z)) = ( (x V y) V z )

( V V )

V V .

• Distributive law ( x & (y V z) ) = ( (x & y) V (x & z) ) :

( V V )

• Commutative law and law of contradiction (x & ~x) = (~x & x) = 0:

( V V )

• Law of identity ( x V 0 ) = x leading to the reduced form of the formula:

q = ( (d & c) V (p & d) V (p & ~c) )