Basic Theory of Logic Functions:Implication Relations and Prime Implicants.

Implication Relations and Prime Implicants

In this section, we discuss the algebraic manipulation of logic expressions; that is, how to convert a given logic expression into others. This is very useful for simplification of logic expression. Although simplification of a logic expression based on a Karnaugh map, which will be discussed in Chapter 28, is convenient in many cases, algebraic manipulation is more convenient in many other situations [3].

called antecedent and consequent, respectively. If an implication relation holds between f and g. That is, if f ⊆ g or f ⊇ g holds, f and g are said to be comparable (more precisely, “⊆-comparable” or “implication-comparable”). Otherwise, they are incomparable.

When two functions, f and g, are given, we can find by the following methods at least whether or not there exists an implication relation between f and g; for example, using a truth table for f and g, directly based on Definition 27.4. If and only if there is no row in which f = 1 and g = 0, the implication relation f ⊆ g holds. Furthermore, if there is at least one row in which f = 0 and g = 1, the relation is tightened to f ⊂ g. Table 27.1 shows the truth table for f = x1x3 ∨ x1x2x3 and g = x1 ∨ x2. There is no row with f = 1 and g = 0, so f ⊆ g holds. Furthermore, there is a row with f = 0 and g = 1, so the relation is actually f ⊂ g.

Although “g implies f ” means “if g = 1, then f = 1,” it is to be noticed that “g does not imply f ” does not necessarily mean “f implies g” but does mean either “f implies g” or “g and f are incomparable.” In other words, it does mean “if g = 1, then f becomes a function other than the constant function which is identically equal to 1.” (As a special case, f could be identically equal to 0.) Notice that “g does not imply f ” does not necessarily mean “if g = 0, then f = 0.”

Definition 27.5: An implicant of a logic function f is a term that implies f.

For example, x1, x2, x1x2, and x1x3x2 are examples of implicants of the function x1∨x2. But x1x2 is not. Notice that x1x3 is an implicant of x1 ∨ x2 even though x1 ∨ x2 is independent of x3. (Notice that every

product of an implicant of f with any dummy variables is also an implicant of f. Thus, f has an infinite number of implicants.) But x1x2 is not an implicant of f = x1x3 ∨ x2 because x1x2 does not imply f. (When x1x2 = 1, we have f = x3, which can be 0. Therefore, even if x1x2 = 1, f may become 0.) Some implicants are not obvious from a given expression of a function. For example, x1x2 ∨ x1x2 has implicants x2x3 and x2x3x4. Also, x1x2 ∨ x2 x3 ∨ x1x3 has an implicant x3 because, if x3 = 1, x1x2 ∨ x2 x3 ∨ x1x3 becomes x1x2 ∨ x2 ∨ x1 = x1 ∨ x2 ∨ x1 = (x1 ∨ x1) ∨ x2 = 1∨ x2 , which is equal to 1.

Definition 27.6: A term P is said to subsume another term Q if all the literals of Q are contained among those of P. If a term P which subsumes another term Q contains literals that Q does not have, P is said to strictly subsume Q.

For example, term x1x2x3x4 subsumes x1x3x4 and also itself. More precisely speaking, x1x2x3x4 strictly subsumes x1x3x4 . Notice that Definition 27.6 can be equivalently stated as follows: “A term P is said to subsume another term Q if P implies Q; that is, P ⊆ Q. Term P strictly subsumes another term Q if P ⊂ Q.”

Notice that when we have terms P and Q, we can say, “P implies Q” or, equivalently, “P subsumes Q.”

But the word “subsume” is ordinarily not used in other cases, except for comparing two alterms (as we will see in Section 28.4). For example, when we have functions f and g that are not in single terms, we usually do not say “f subsumes g.”

On a Karnaugh map, if the loop representing a term P (always a single rectangular loop consisting of 2i 1-cells because P is a product of literals) is part of the 1-cells representing function f, or is contained in the loop representing a term Q, P implies f or subsumes Q, respectively. Figure 27.3 illustrates this.

Conversely, it is easy to see that, if a term P, which does not contain any dummy variables of f, implies f, the loop for P must consist of some 1-cells of f, and if a term P, which does not contain any dummy variables of another term Q, implies Q, the loop for P must be inside the loop for Q.

The following concept of “prime implicant” is useful for deriving a simplest disjunctive form for a given function f (recall that logic expressions for f are not unique) and consequently for deriving a simplest logic network realizing f.

Definition 27.7: A prime implicant of a given function f is defined as an implicant of f such that no other term subsumed by it is an implicant of f.

For example, when f = x1x2 ∨ x1x3 ∨ x1x2x3 ∨ x1x2x3 is given, x1x2 , x1x3, and x2x3 are prime implicants. But x1x2x3 and x1x2x3 are not prime implicants, although they are implicants (i.e., if any of them is 1, then f = 1). Prime implicants of a function f can be obtained from other implicants of f by stripping off unnecessary literals until further stripping makes the remainder no longer imply f. Thus, x2x3 is a prime implicant of x1x2 ∨ x1x3, and x2x3x4 is an implicant of this function but not a prime implicant. As seen from this example, some implicants, such as x2x3, and accordingly some prime implicants are not obvious from a given expression of a function. Notice that, unlike implicants, a prime implicant cannot contain a literal of any dummy variable of a function.

On a Karnaugh map, all prime implicants of a given function f of at least up to four variables can be easily found. As is readily seen from Definition 27.7, each rectangular loop that consists of 2i 1-cells, with i chosen as large as possible, is a prime implicant of f. If we find all such loops, we will have found all prime implicants of f. Suppose that a function f is given as shown in Figure 27.4(a). Then, the prime implicants are shown in Figure 27.4(b). In this figure, we cannot make the size of the rectangular loops

any bigger. (If we increase the size of any one of these loops, the new rectangular loop will contain a number of 1-cells that is not 2i for any i, or will include one or more 0-cells.)

Consensus

Next, let us systematically find all prime implicants, including those not obvious, for a given logic function. To facilitate our discussion, let us define a consensus.

Definition 27.8: Assume that two terms, P and Q, are given. If there is exactly one variable, say x, appearing noncomplemented in one term and complemented in the other—in other words, if P = xP′ and Q = x Q ′ (no other variables appear complemented in either P′ or Q′, and noncomplemented in the other)—then the product of all literals except the literals of x, that is, P ′Q′ with duplicates of literals deleted, is called the consensus of P and Q.

For example, if we have two terms, x1x2x3 and x1x2x4x5, the consensus is x2x3x4x5. But x1x2x3 and x1x2x4x5 do not have a consensus because two variables, x1 and x2, appear noncomplemented and complemented in these two terms.

A consensus can easily be shown on a Karnaugh map. For example, Figure 27.5 shows a function f = x1x2 ∨ x1x4. In addition to the two loops shown in Figure 27.5(a), which corresponds to the two prime implicants, x1x2 and x1x4, of f, this f can have another rectangular loop, which consists of 2i 1-cells with chosen as large as possible, as shown in Figure 27.5(b). This third loop, which represents x2x4, the consensus of x1x2 and x1 x4 , intersects the two loops in Figure 27.5(a) and is contained within the 1-cells that represent x1x2 and x1x4. This is an important characteristic of a loop representing a consensus. Notice that these three terms, x2x4, x1x2, and x1x4, are prime implicants of f. When rectangular loops of 2i 1-cells are adjacent (not necessarily exactly in the same row or column), the consensus is a rectangular loop of 2i 1-cells, with i chosen as large as possible, that intersects and is contained within these loops. Therefore, if we obtain all largest possible rectangular loops of 2i 1-cells, we can obtain all prime implicants, including consensuses, which intersect and are contained within other pairs of loops. Sometimes, a consensus term can be obtained from a pair consisting of another consensus and a term, or a pair of other consensuses that do not appear in a given expression. For example, x1x2 and x2x3 of x1x2 ∨ x2x3 ∨ x1x3 yield consensus x1x3, which in turn yields consensus x3 with x1x3. Each such consensus is also obtained among the above largest possible rectangular loops.

As we can easily prove, every consensus that is obtained from terms of a given function f implies f. In other words, every consensus generated is an implicant of f, although not necessarily a prime implicant.

Derivation of All Prime Implicants from a Disjunctive Form The derivation of all prime implicants of a given function f is easy, using a Karnaugh map. If, however, the function has five or more variables, the derivation becomes increasingly complicated on a Karnaugh map. Therefore, let us discuss an algebraic method, which is convenient for implementation in a computer

program, although for functions of many variables even algebraic methods are too time consuming and we need to resort to heuristic methods.

The following algebraic method to find all prime implicants of a given function, which Tison [4,5] devised, is more efficient than the previously known iterated-consensus method, which was proposed for the first time by Blake in 1937 [2].

The last expression is called the complete sum or the all-prime-implicant disjunction. The complete sum is the first important step in deriving the most concise expressions for a given function. D Generation of prime implicants for an incompletely specified function, which is more general than the case of completely specified function described in Procedure 27.1, is significantly speeded up with the use of BDD (described in Chapters 27.1 and 27.4) by Coudert and Madre [1].