Page 166 - Engineering Digital Design

4.3 INTRODUCTION TO LOGIC FUNCTION GRAPHICS 137

to Eqs. (4.8) and (4.9), there results

/ + / = y^m(0, 2, 5,6) + y~^w(l, 3,4,7)

= £m(0, 1,2,3,4,5,6,7)
= 1.

Generally, the Boolean sum of all 2" minterms of a function is logic 1 according to

^m/ = l. (4.10)
;=0
Similarly, by using the AND law, X • X = 0, and the AND form of the commutative laws,
there results

/- / = f[M(l,3,4,7).]~[M(0,2,5,6)
= ]~[M(0, 1,2,3,4,5,6,7)
= 0.

Or generally, the Boolean product of all 2" maxterms of a function is logic 0 according to

Equations (4.10) and (4.11) are dual relations by the definition of duality given in Subsection
3.10.2.
To summarize, the following may be stated:

Any function ORed with its complement is logic 1 definite, and any function ANDed
with its complement is logic 0 definite — the form of the function is irrelevant.

4.3 INTRODUCTION TO LOGIC FUNCTION GRAPHICS

Graphical representation of logic truth tables are called Karnaugh maps (K-maps) after M.
Karnaugh, who, in 1953, established the map method for combinational logic circuit syn-
thesis. K-maps are important for the following reasons: (1) K-maps offer a straightforward
method of identifying the minterms and maxterms inherent in relatively simple minimized
or reduced functions. (2) K-maps provide the designer with a relatively effortless means of
function minimization through pattern recognition for relatively simple functions. These
two advantages make K-maps extremely useful in logic circuit design. However, it must be
pointed out that the K-map method of minimization becomes intractable for very large com-
plex functions. Computer assisted minimization is available for logic systems too complex
for K-map use. The following is a systematic development of the K-map methods.