UNIVERSITY OF ILLINOIS LIBRARY AT URBANA-CHAMPAISN The person charg-ino- t h i<5 mo , sponsible for its S + material ls re- which it was withdr* thC librar ^ fro ™ the University. * m<,y reso " &• di smisso , from To renew call Telephone Center 3 33 s * nn L161— Q-1096 Digitized by the Internet Archive in 2013 http://archive.org/details/expositionoftiso993cutl If* le f3 UIUCDCS-R-79-993 L ^ UILU-ENG 79 1741 EXPOSITION OF TISON'S METHOD TO DERIVE ALL PRIME IMPLICANTS AND ALL IRREDUNDANT DISJUNCTIVE FORMS FOR A GIVEN SWITCHING FUNCTION by R. B. Cutler K. Kinoshita S . Muroga October 1979 DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN URBANA, ILLINOIS THE LIBRARY OF THE lYIMf b U UNIVERSITY OF ILLINOIS ' 'P^ANA- CHAMPAIGN uiucdcs-r-79-993 EXPOSITION OF TISON'S METHOD TO DERIVE ALL PRIME IMPLICANTS AND ALL IRREDUNDANT DISJUNCTIVE FORMS FOR A GIVEN SWITCHING FUNCTION by R. Cutler K. Kinoshita* S . Muroga November 197^ Revised May 1979 Department of Computer Science University of Illinois at Urbana-Champaign Urbana, Illinois *Leave of absence from Department of Electronic Engineering, • Osaka University This work was supported in part by the National Science Foundation under Grant Nos. NSF-GJ-U0221, DCR73-03^21, and MCS-77-097 1 ^ . TABLE OF CONTENTS Page 1. INTRODUCTION 1 2 . DERIVATION OF ALL PRIME IMPLI CANTS 2 3. DERIVATION OF ALL GENERALIZED CONSENSUS RELATIONS 32 k. DERIVATION OF ALL IRREDUNDANT DISJUNCTIVE FORMS FOR A COMPLETELY SPECIFIED FUNCTION 55 5. ELIMINATION OF ABSOLUTELY DISPENSABLE PRIME IMPLICANTS 73 6. DERIVATION OF ALL IRREDUNDANT DISJUNCTIVE FORMS FOR AN INCOMPLETELY SPECIFIED FUNCTION 8k 7. DERIVATION OF ALL IRREDUNDANT DISJUNCTIVE FORMS FOR A COMPLETELY SPECIFIED MULTIPLE- OUTPUT FUNCTION 9k 8. DERIVATION OF ALL IRREDUNDANT DISJUNCTIVE FORMS FOR AN INCOMPLETELY SPECIFIED MULTIPLE- OUTPUT FUNCTION 112 REFERENCES 119 SUMMARY OF NOTATIONS 120 INDEX TO THEOREMS, LEMMAS, ALGORITHMS, COROLLARIES AND EXAMPLES 121 APPENDIX: IMPLEMENTATION TO TISON' S ALGORITHMS 122 1. INTRODUCTION An algebraic approach to derive all prime implicants and all irredundant disjunctive forms for a given switching function (in contrast to tabular methods) was explored by a few people, e.g. [1] ~ [3]. Then in 1967 P. Tison completed this approach [h] t [5]. This expository paper discusses the derivation of all the prime implicants of a given function and all the irredundant disjunctive forms for a completely specified function based on [U], [5], elimination of absolutely dispensable prime implicants based on [3], and derivation of all the irredundant disjunctive forms for an incompletely specified function, a completely specified multiple-output function, and an incompletely specified multiple-output function based on [^] 5 [5]. Corrections and extensions to some of the theory are also included. 2. DERIVATION OF ALL PRIME IMPLICANTS First, let us briefly review some definitions and the switching theory terminology we use throughout this paper. Definition 1 A switching function f (x , . . . , x ) is defined as a mapping {0,1}" -> {0,1} of 2 combinations of the values and 1 assigned to variables x. , . .. , x into either f = or f = 1. A function f. is In 1 said to imply a function f if f = 1 for each combination of values of variables such that f = 1. This is written f . c f . If there exists at least one combination where f = 1 and f = 0, then f is said to strictly imply f , written f <= f . Function f is said to include or strictly include f respectively. The common way to express a switching function f is as an algebraic formula ¥ consisting of literals x n , x. , x , x_, ..., x , x & ° 1» 1' 2 2 n n and operators AND (^ or •) and OR (v), writing f = V. Two formulas V and ¥ are said to be equivalent or equal if f = V and f = ¥ (i.e. , 4f 1 and ^ are expressions for the same function f). Two expressions V and ^ are identical , written ¥ 5 ¥ if they are exactly the same formula. Definition 2 A product (i.e., conjunction or AND) of literals, A, is said to be an implicant of a function f if we have the relation A c f . A is said to be a prime implicant of f if there exists no other implicant B of f such that A c B. When A cr b holds between two products of literals, A and B, A is said to subsume B. (Notice that it includes the case A = B. When A = B is excluded, it is denoted with A c B and A is said to strictly (or properly) subsume B. ) Thus we may say that A is a prime implicant of f if there exists no other implicant B of f which A strictly subsumes. ■ Definition 3 Let A , k , ..., A and X be products of literals. When we have a disjunction (i.e., logical sum or OR) of products equal to 1, 1 = £ A. , this is said to be irredundant if no term A. can be removed i=l i l without invalidating the equality. An implication relation X c .v? A. is said to be irredundant if we can neither delete a literal from the left side of the relation nor remove a term from the right side of the relation without invalidating the implication relation. Irredundancy is denoted by writing (irr) beside the relation, as l=.v A.(irr) and X^f a (irr) Vi v Note that 1= .v, A. (irr ) is the same as lc.^-.A, (irr) i=l i —i=l x Example 1 Consider the implication relation alj c ax y by ./ xy . This is irredundant because neither a nor b can be removed from ab and neither ax, by, nor xy can be removed from ax ^ by \/ xy without invalida- ting the relation: a ^ ax v by v xy b ^ ax v by v xy ab ^ by v xy ab £ ax ^ xy ab £ ax s, by The implication relation ab c ax v by v bxy is also irredundant despite the fact that b can be deleted from bxy without invalidating the relation. A disjunctive form for a function f is a disjunction of products of literals such as f = .\A I i=l "i An implicant A. is called redundant in the disjunctive form of f if j-1 I ^ A v A i=l i v i=j+l i is also a disjunctive form of f. Any literal x in an implicant A. is called redundant if the product A.' formed from A. by deleting x is an impli- J J cant of f . An irredundant disjunctive form of f (which is often abbreviated as IDF) is a disjunctive form with no redundant implicants or literals. It is easy to see that only prime implicants of f will appear in an irredundant disjunctive form of f. For determining if a term is redundant in any disjunctive form f ■ \ s i=i A i • the following lemma is useful. Lemma _1: Let ^ be a disjunction of products of literals where A is one of the disjuncts, and T be the disjunction of the other disjuncts in ¥ : ¥ E Av y . Then A is redundant in y if and only if A c f . Proof : Assume Ac y ? . Combining this with ¥ ? c ^p yields A v f ? c y v y 2 , or ^ c ? gl Since ? = A v/ ^ ^ - V Then ' because \ - Y 2 and ¥ 2 - \' * and ^ express the same function so A can be deleted as redundant. Assume A is redundant. Then f and y express the same function, so Y —V?' Since A is a term in | , A E ^-i • Thus, by transitivity A 5 f 2 . Q.E.D. Definition U Let X and A be products of literals. The residue or ratio of A A with respect to X, written as — , is defined as the expression equal to A. A when only the literals which appear in X are set to 1. " The following are examples : (1) A = abc and X = a A abc , x = — =bc (2) A = abc and X = cd A abc X cd ~ a (3) A = abc and X = ab A _ abc __ X ab (1+) A = abc and X = abed A abc _ , X " abed Definition 5 Given a set S of p products, S= {A , . .., A ), a monoform variable is a variable such that only one of its literals appears in A , . . . , A . If both literals of a variable appear in A., . . . , A , the variable is called a biform variable . The literals of a monoform (or biform) variable are called monoform (or biform) literals . If we denote the product of the monoform literals in S with X, the char - acteristic sum of S = {A , . . . , A } is the disjunction of the residues ■p j^ with respect to X, written as .£•_ _i . ■ l-l x Definition 6 The generalized consensus of a set S of p products B. {A^ .... A p ) . where p > 1 is the product X of the monoform literals in S,if and only if the characteristic sum of S is irredundantly equal to 1. This relation that the product X of the monoform literals in S is the generalized consensus of S is written as X=€(A_,, .... A ). 1 p This definition includes the case for a single product A. , in other words, C(A. ), as a special case for the sake of notational conven- ience (see the paragraphs between Example 2 and Lemma 2 ). Definition 7 Given a generalized consensus relation X=C(A , ..., A ), the set G = {A. , . . . , A } is called the generation of X, and each A. in 1 p M l [A , . . . , A } is called a generator of X. A , . . . , A are said to generate X. The number of generators in a generation is called the order of the generalized consensus relation. Example 2 de = C (ace, ab, bd, bed) Since the monoform variables are d and e and the characteristic sum is ace ab bd bed de v de v de v de = ac \/ ab s/ b v be = 1 (irr) The generation is {ace, ab, bd, bed} and this generalized consensus relation is of order h* Obviously an ordinary "consensus" known in switching theory is a special case of the generalized consensus: it is the generalized consensus of order 2. The generalized consensus of a single product A. appears to be an artificial definition but the expression C(A. ) is conven- ient as we shall see. This may be interpreted as C(A. )=A. since the product of monoform variables in A. is A. and the characteristic sum is 1=1 (irr) and is called trivial . Notice that if A., . . . , A contain no biform variable where 1 p p > 2, it is impossible for them to generate a generalized consensus because the characteristic sum is not irredundantly equal to 1 ( the characteristic sum becomes the disjunction of more than one 1, i.e., lvl v ...vl). Furthermore if we happen to have the relation X=C(A , ...,A ) in this case with p>l, p must be 1 and X = A = C(A ). Lemma 2 : When the disjunction of products, A , ,,,, A , is irredundantly equal to 1, i.e. , A, v ... v A =1 (irr), 1 P no monoform variable can appear in any of A , . . . , A . Proof : Suppose a monoform variable x appears in A , ..., A . If we set x = 0, then those terms containing x will become 0. The remaining terms must still constitute an equality to 1 for all combinations of values of the remaining variables. Thus the terms containing x are not needed in the equality, and are redundant, contradicting the irredundancy of the given equality. Q.E.D. P' following Theorem 1 asserts that X must be the product of the monoform If Xc .v-_A. (irr) holds among products X, A n , ..., A , the — i=l l '1 p variables in A n) ..., A and that the characteristic sum of {A n , ..., A } 1' r> 1 p P is irredundantly equal to 1. Theorem 1: X=e(A n , ..., A ) if and only if X c .5,A. (irr) holds among 1 p — i=l i products X, A , . . . , A . IP P Proof: (1) Let us first prove IQ v A. (irr) if X = C(A A ) i=l v holds . If X = e(A_, ..., A ), then X is the product of the monoform 1 P literals of {A , . . . , A } and by Definition 6 P A, L=1 "x This can be written as 1 c .£ ^L (irr). If we multiply both sides — 1=1 v 1 = . y, _i ( irr ) . X X by X, we obtain 1=1 T or Thus we have X = .8. (X ^i) c P A . — 1=1 Y — 1=1 1 X c .5 A. — i=l i We must now show that this implication relation is irredundant . Suppose some term A ± s removed from the right side. When K. only literals contained in X are set to 1, we have X = 1. But .v-., A. which becomes .£., Ai cannot be 1, since i=l l i=l ~n~ Mk i^k X 1 =.n>, 2i (irr). Thus no A can be removed from the right side of i-l x k x^.E A., - 1=1 1 Suppose some monoform literals XL are removed from Xe X X . When the remaining literals X p in X are set to 1, the monoform literals X_ removed from X remain as literals in .£•-. A. which becomes 1 1=1 l P A- i=l — when X is set to 1. Then by Lemma 2, .5- 2i. is not *2 d 1 - 1 X, irredundantly equal to 1, contradicting 1= .£■_ _i (irr). Thus the i=i Xo "D A- removal of any literals from X invalidates 1 = .v _i (irr). ^2 Therefore the irredundancy of X .5-Yi a - ( irr ) has been proved. (2) <= Given XE Aa. (irr), we shall prove X = C(A,...,A ) by showing that X consists of only all the monoform literals of {A j ..., A } and that the characteristic sum of {A , ..., A }, P A ._, -rr— is irredundantly equal to 1. 1 — -L A 10 Suppose X c .§•_ A. (irr). Let S = {A , . .., A }. (a) X contains only literals that appear in S because any literals appearing in X and not in S can be deleted from X to form X' and X' c. v n A. would remain valid, contradicting the ir redundancy. (b) X contains only monoform literals, because if X contains a biform literal, any term A that contains the complement of that literal could be deleted from the right side of the relation X c ,£ a., i.e., — i=l i' ' holds, but this contradicts the irredundancy of the relation. (c) X contains all the monoform literals of S for the following reason. Suppose a monoform literal x, appears in S but not K. in X. Then by Lemma 2, .y n A. is not irredundantly equal to 1 when we set X = 1. This contradicts the irredun- dancy of the relation X ^ .£ A. (irr). Thus X contains all the monoform literals of S and p A. no others. So the characteristic sum of S is.^ _JL . i=l X This is equal to 1 irredundantly for the following reason. If we set X=l, then the relation X c .\L A. (irr) leads to 7 — i=l l 1 <= .£. ^L ( irr ) - i=l x A (this is irredundant because if any term _JL is eliminated, X this contradicts X 3yi ^. (^ rr )) an< i consequently 11 !-&£(*»>. P A ± , £l T U Therefore X = C(A , A , . .., A ) by Definition 6. Q.E.D. Example • Consider Example 2: de = C(aca, ab, bd, bed) The characteristic sum is 1 = ac v ab v b v be (irr) . We therefore have the relation de 5; ace ^ ab v bd v bed (irr) Conversely if the last relation holds, 1 = ac v ab v b v be (irr) holds . Therefore de = €(ace, ab, bd, bed). Theorem 2 : Suppose a function f which is the disjunction of products A , . .., A is given. Then each prime implicant of f can be expressed as the generalized consensus of a subset of S = {a , ..., A }. Proof : Since a prime implicant X of f implies f , we get X C A sy . . . v A . - 1 p After deleting redundant terms from the right side, we get X <= A v ... ^ A . — u v Now deletion of any term from the right side invalidates this implication relation. No literal can be deleted from X without invalidating the implication relation, because if we delete any literals and denote the 12 rest of X with X' , we get X' c a ^ ... v A c f and X C X' — u v — against the assumption that X is a prime implicant of f . Also if X contains any biform literals or does not contain some of the monoform literals which are present in A , . . . , A , the corresponding terms among A , . . . , A can be deleted without invalidating the relation X c A v ••• v A against the property that deletion of any term in the — u v right side invalidates the relation. Thus the irredundancy of the relation has been established: X c A sy ... v A (irr). — u v Thus by Theorem 1, X = C (A , . . . , A ) . The case where S consists of a single term A, , i.e., S = {A } is included in the above argument, since X' 5 A -i S f contradicts that X is a prime implicant of f . Q.E.D. Example k Let f be given by the disjunction of the products in S = {abde, abe, acd, bed, bd} , i.e., f = abde v abe v acd v bed ^ bd Consider the prime implicant X = ab. Then ab c abde ss abe v acd v bed vbd = f . The term bd is redundant since it contains b so remove it to form ab c abde ^ abe v acd v bed (irr) thus ab = €(abde, abe, acd, bed) holds, since the characteristic sum is 1 = de v e v cd v cd (irr). 13 Now consider X = €(A , ..., A ), where p _> 2. We can write each A as B i • M., where B. is the product of the biform literals of the genera- tion in A and M. is the product of the monoform literals of the generation in A. (letting the product of no variables equal l). The characteristic s um of A., . . . , A is thus P ± l ± B - 1 (irr) . (1) Choosing any biform variable b, we can reorder the subscripts so that the products B. to B, each contain b, products B, _ to B each contain * Ik ' * k+ 1 m neither b nor b, and products B ^ to B each contain b. We can m + 1 p rewrite equation (l) as (b.l ?L) v (.*, ,B.) v (b .1 *k ) = 1 (irr). (2) v i=l b v i=k+l x v i=m+ir v By setting b = 1 in (2), we have ^li t ] v ( i^i V = x • (3) By setting b = in (2), we have (.5L, b.) v (.?. 51) = 1 . (k) i=k+l i i=m+l r- Equations (3) and {k) are not necessarily irredundant. The following two Lemmas show that if any redundant terms appear in (3) or (k) , then they must appear in the .v.. ,B. , and that no term 1— K~rJ- 1 which is common in (3) and (k) can be redundant in both (3) and (U). Lemma 3 : If any redundant term appears in (3) or (U), then it must appear in . v. _ B . . i=k+l 1 Proof : Suppose there is a term Bq that is redundant in the first disjunc- ~b~ tion in (3). Then by Lemma 1, <*■ C .v, l) V (.V ,__i) SS (.v ,-B. ) -5- - v i=l — i =c l f l b v i=k+l i y 14 always holds. If we multiply both sides of this by b, B c (QcJ B.) - (> B ) - (.^> B. b). q — 1=1 1 i=q+l l i=k+l l From B. «b ^ B. , we obtain l — i ^ B b ^ B . i=k+l i - i=k+l i So we can write B c (^ B .) - (.$ B.). q — 1=1 l i=q+l l But this implies that B is redundant in (l) by Lemma 1. This is a contra- il diction to its irredundancy. In a similar fashion, this can be proved for (h) . Q.E.D. Lemma k : No term common in (3) and {h) can be redundant in both (3) and (h) . Proof : Suppose a term B is redundant in both (3) and (k) . By Lemma 3, M. m . . B must be m . v: B. and consequently from (3) using Lemma 1, q — 1=1 b i=k+l l i=q+l i' always holds. Multiplying both sides by b, we get B • •b c (A B.) v (£* B - b ) - ^?L-. B ^ a — i=l l i=k+l l i=q+l l Since B. • b c= B. , l — l ,q-l , . m B b c ? v . B. ) v .v -B.). q — l-l i i=q+l l Similarly, from (U) we find B be (?^B.) v (.<$ ._B.). q — i-k+1 l i=q+l l If we combine these last two relations, we get B c (.3 B.) v/ (.5 .,%). q — i=l l i=q+l^- 15 By Lemma 1, this implies that B is redundant in (l). This contra- dicts that (l) is ir redundant. Q.E.D. Theorem 3 : Every generalized consensus relation of order p (p>2) X = C (A , . . . , A ) can be expressed as the generalized consensus relation of order 2 of two products, X_ and XL, X = € (X^ X 2 ) where each of X.^ and X can be expressed as the generalized consensus relations of order lower than p, X 1 EbX|=e(A. ) ...,A.) 1 u X e bX» - € (A , . . . , A ) J l d v using an arbitrary biform variable b of {A , ..., A } and using S l = {A i ' ••" A i } 1 U S„ = {A , . . . , A J J l J v with the following properties. S.. and S_ are subsets of {A., ..., A } x d 1 p such that each product in {A , . . . , A } is contained in at least one of S and S and such that S_ and S contain b and b as a monoform variable, 1 2 12 respectively. When S or S contains only one product A. we can denote this as the special case, C (A. ) = A. (the expression C(A. ) emphasizes the fact that A. cannot be expressed as the generalized consensus of any of the other products). 16 Proof : By choosing any biform variable b, we can derive (2), (3), and (h) from the characteristic sum. From Lemma 3 we know that any redundant terms ir. (3) can occur only in terms B, , to B . We can thus reorder the subscripts in (3) so k+1 m that the products B, , _ to B , are not redundant in (3) and the products k+l m' B , , to B are redundant, where k+l < m' < m. We can then write (3) as m'+l m — — (A ?1) s, (.£ _B.) = 1 (irr) (5) v i=l b i=k+l i v ' K " Similarly we can reorder the subscripts in (k) so that the redundant terms are B, ,to B, , and the non-redundant terms are B, , _ to B . k+l k' k'+l P Notice that k' < m' + 1 because of Lemma k. Thus (k) can be written as (.5...B.) v (.£ _ h.) = 1 (irr) . (6) i=k +1 x i=m+l 5" Fig. 1 shows graphically which terms are included in these equations. Index Equation (1) k k+l k' k'+l m* m'+l m m+1 (2) t (3) (h) redundant (3) in v redundant (U) in (5) i (6) *— *- l ( k Bi k / m' B v x l=l D v l=k+l i is irredundantly equal to 1. We therefore have X.^ = € (A , ..., A t) of order m' < p-1. Similarly, we have x 2 = Nlvi M i = e ( Vr — > V of order p - k 1 <_ p - 1. Since k 1 ' m' from Lemma h we see that each A is a ~~ 1 generator of at least one of X.. and Xp. Finally, since m' X, = b • n M. 1 i=l X and X = b • n M. i=k'+l x X l X 2 b is the only biform variable in {X ,XJ and — • -3- = n M. = X, we have L i=l 1 = £(X ,X„) with characteristic sum 1 = b ^ b, Q.E.D. 18 Definition 8 The process of determining X_ and X p by applying Theorem 3 such that X = € (X , X ) is called reduction of the generalized consensus relation X = € (A , . .., A ) with p >_ 2 since the order of each of the consensus relations for X and X is less than p. Theorem 3 asserts that reduction can only take place when a biform variable is chosen. Therefore if we attempt to apply Theorem 3 with respect to a monoform variable or one that does not appear in the generation then no reduction will take place. Thus if we apply Theorem 3 to X = € (A , ..., A ) using a biform variable b reducing it to X = € (X j X p ) and then attempt to apply Theorem 3 to X = e (A. , . .., A. ) 1 u using b again, no reduction will take place since b is now a monoform variable in A, s . . . t a Example 5 i ' ' l 1 u Consider the prime implicant ab of Example k- (A 1 ) (Ag) (A3) (A k ) ab = €(abde, abe, acd, bed) with characteristic sum (B^ (B 2 ) (B 3 ) (B k ) 1 = de v e v cd v cd (irr) (7) Choose a biform variable, say e, Then for e = 1, we have &) fe) &) (i) 1 = d v s, cd ss cd ^ ' and for e = B 'i) (I) (I) (I) 1 = v 1 ^cd-^cd (9) 19 is redundant in (8) so ft) ft) ft) 1 = d v cd v cd (10) Also, 0, cd and cd are redundant in (9), so 1=1 (irr) (11) (Notice that the equation numbers, (7) through (ll), correspond to (2) through (6), respectively.) Thus, (\) (M 3 ) (M u ) x l = e • ab a • b = abe \- e (M 2 ) ab = abe Therefore ab = €(abde, abe, acd, bed) is reduced to ab = e(x , Xp) = €(abe, abe) ( A x ) (A3) (\) with abe = €(abde, acd, bed) abe = e(abe) Each A. is a generator of abe or abe. (Theorem 3 is illustrated also by 1 1 Example T , where X. 4 X p . ) Lemma 5 : Let X , X_ and X be products of literals such that X subsumes X (i.e., X E X ) and such that €(X , X) exists with respect to a biform 20 variable b. Then €(X ,X) subsumes either C(X 2 , X) if b 6 X 2 or X 2 if b/ X 2 . Proof : Let X e ZI where Z is the product of literals in X, but not in X r Suppose X contains b and X contains b. Then b is contained in either Z or X , Thus two cases arise: (l) When b e X and F € X, e(x ,I) a i.I B z.i.5c-2.S. €(X p) X) 1 b b b b ~bb ^ (2) When b fi X 2 and b € X, b must be contained in Z since b is contained in X . Thus , c(x 1 , x) = I • x 2 • z ^x 2 . b Q.E.D. Theorem k: Suppose a set of products S^ = (A n , .... A } with biform 1 p variables b_ , ..., b , and a function f which is the disjunction of 1 m A , . .., A are given. Then every prime implicant of f can be found by the following procedure: first let i = 1; then (l) form every possible generalized consensus of order 1 or 2 among the products in the set S. . with respect to biform variable b. and place these along with the products in set S. . into a set S . Eliminate, from S., products which subsume other, l-l i i (2) Repeat (l) for each of the remaining biform variables (i = 2 through m). The final set, S , will consist of all the prime implicants of f. 21 Example 6 (To illustrate Theorem k) Consider the function of Example k S„ = {abde, abe, acd, bed, _bd} consensus with respect to b abde and bd do not have a consensus. Notice that retaining abde and bd is the generalized consensus of order 1 and that the forma- tion of ade and cd is the generalized consensus of order 2. consensus with respect to c S n = { abde, abe, acd, bSa, bd, ade, cd} ad bed is deleted because it subsumes cd S = {abde^abe, a*d, bd, ale, cd, ad} abce abe consensus with respect to d abde and bd do not have a consensus, acd and ade are removed because they subsume ad. = {a^e, abe, bd, cd, ad, ab)^e, abe} consensus with respect to e abde and abce are deleted because they subsume abe. S. = {a^e? bd, cd, ad, aVe, ab} abe and abe are deleted because they subsume ab. Thus the prime implicants of f are {bd, cd, ad, ab}. 22 Proof : (l) Suppose all the prime implicants of f have been obtained. Then by Theorem 2, each prime implicant X can be expressed as the generalized consensus of a subset of S_, X = €(A , .... A ). Assume u v that the set {A , ..., A } consists of two or more products, A , .... A . u' ' v * ' u' ' v (The case where the set consists of a single product A., i.e., X = C(A. ) will be considered later.) Then by Theorem 3, X can be expressed as the consensus of two products, X.^ and X , with respect to a biform variable b , and each of X n and X can be expressed as the generalized consensus m l r *btf — 1** i ^**-abc bed — "^T"^ ^bed — I bed 30 Tracing the formation tree for aM (heavy lines) shows that it is not a reduction tree. Even though a generalized consensus relation of order 1 or 2 holds at each level in this tree, ac = €(bc, abc") , bed = e(bcd), and abd = €(ac, bed), it is not true that abd = €(bc, abc", bed) because abdc be - abc" - bed is not irredundant . In general an X formed starting with A , ..., A is not always the generalized consensus of A^ ..., A g . 1 s The following Algorithm 1 which derives all the prime implicants of a given function f based on Theorem h generally produces non-prime implicants (which must be deleted in Step (3)) as well as prime implicants. Also notice that when we get X starting with implicants J^ A g , of a function f , X is an implicant of f no matter whether X is still in an intermediate level in the formation tree or whether X is not a prime implicant of f, as can be seen from Fig. 9- Since x X !^ X 11- X 12 (irr) ' ^\ x 2 E* 21 - x 22 ^' and \ . x X 2 X 12 21 X ^X 1 sy X 2 (irr), XCX n v X 12 v X 21 v X 22 holds. Fig. 9 ^ X 22 . , . 4, * TTni . . . ,p t ) is defined as the disjunction of all the minterms x{l X J2 . . . xJn p *l . . . # for which 4 1 A 2 ■ ■ ■ xJ „ n s k i A i v k 2 A 2 - ■■■- Vt 3k is a valid implication relation for the function f (x. ,x rt , . . . , x ) with 12 n prime implicants S = {A , . . . ,A } , considering all possible combinations of j. = or 1 and k = or 1 for i = 1, ..., n and I = 1, ..., t. This is demonstrated in the following example. Example 9 A l A 2 Consider the set S = {ab, a }. The verity function V (a,b,p ,p ) b 1 C- is constructed as follows j l j 2 k l k 2 implication test valid? minterm of V_ n 1 l l 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ab 5 ab E a ab E ab ab E ab ^ a ab£ ab E a ab E ab ab E ab va ab E ab E a ab E ab ab E ab -v a ab E ab E a ab E ab ab E ab s/ a no yes no abp x P 2 yes abp 1 P 2 no yes abp 1 P 2 no - yes abp 1 P 2 no no no no no no yes abp x P 2 yes abp P p V S = a ^ p i p 2 v atp iP2 ^ ab P]_P2 v ab P 1 P 2 ^ ab PiP 2 V ab PiP 2 = ap 2 v abp x 35 Lemma 6: The implication relation n x. 1 ^ V k A iel X ' ZeL l l is a valid implication relation if and only if \ n xk • n P ^ iel x I V£eL * is an implicant of the verity function V , where I is a subset of {l,2,...,n} and L is a subset of {l,2,...,t}, and each j. and k is either zero or one. Proof: (l) First assume n x ic v k„A„ iel £eL is a valid implication relation. Let I be the set of indices not in I such that I U I = {l,2,...,n} and L be the set of indicies not in L such that L U L {l,2,...,t}. Then for every combination of values for j . and k for iel and 5, eL it is true that ^^•Uj^^L^^i. 7 -^ i v - UeL since adding literals to the left side or implicants to the right side does not change its validity. Then n x. J i • n xH • f n P M • n P H> v Q is true for every combination of values of j . for iel and k for £ e L 36 since the lefthand side of the above relation is a minterm of V q from the definition of V and naturally implies V . It follows then that D b j .=0 or l,iel k^=0 or l.fceL c V. This can be rewritten as j.=0 or l,iel k x =0 or l,£eL S V, since I D I = and L D L = 0. This leads to . p W = v s because j .=0 or l,iel kj=0,or l.fceL iel X £eL = 1 (This is a canonical form). Thus, if n x^i £ v iel £eL k^A^, then n x; iel Ji n p*M sv ? £eL (2) Next assume n tf?i iel n ^Uv c £eL 37 By reversing the steps in the first part of this proof we can obtain ii * )' Lit ^ )- U^l-U" for every possible combination of values for j. and k for i e I and I e L. In particular, for the case where k = for all £ e L we have II xpi) • [ n x^i ] c v k A k lel X / iei X J " £eL l l For all combinations of values for j. for iel. Summing these all together yields V I xH \ ' I n xH ] c v k A j i =0 or 1 U-el X / \iel / " £eL which is equal to n xh) ' j v [ n xH |lc v k a iel \ j.=0 or 1 liel X )( leL Since v [ n_ xl 1 ] = l , j .=0 or 1 liel 1 iel ^ this reduces to n x. J i C v k n A . T i - _ T £ £ iel £eL Q.E.D, 38 Example 10 Consider the verity function derived in Example 9. Term ap p. is an implicant of V , and the corresponding implication relation a c o — • ab vl • a is valid. Based on this Lemma it can he seen that if a term XP (with X = Hx. i i and P = IT p. ^ ) is an implicant of V , then another implicant XP' of V c can be formed by deleting all the complemented literals from P. This is because the corresponding k A is and does not contribute to the disjunction. Thus there are no p ' s in any prime implicant of the verity function. This is shown as part of the following lemma. Lemma 7 There is a one-to-one correspondence between prime implicant s of Vo and consensus relations with generators which are subsets of S. Proof : (l) Consider a prime implicant of V_, By Lemma 6 this has the corresponding implication relation n x«?i t= V k n A„ lei leL This is an irredundant relation and each k = 1 since deletion of any x. 1 or A g would lead to an implication relation with a corresponding implicant of V~ with fewer literals than in the given prime implicant. This yields a generalized consensus relation by Theorem 1. 39 (2) Next, consider a consensus relation with a generator that is a subset of S and corresponds to n x^i c V A„ (irr) iel 2.eL Corresponding to this is an implicant of V , a This is a prime implicant of V since deletion of any literal leads to an implicant which would have a corresponding implication relation with fewer literals on the left side or fewer terms on the right side, contradicting its irredundancy. > Q.E.D. Example 11 The prime implicants of the verity function of Example 9 are {abp.. ,ap ,bp p }. The corresponding consensus relations among the terms of S are ab = €(ab) a = £(a) b = £(ab,a) By Lemma 7, then, for any set S = {A ,A , ...,A }, the verity function V can be formed. Each prime implicant ( n x i 1 )( lip.) of V corresponds to b iel ieL b a generalized consensus relation among the terms of S. These ( n x^i)( n Pj^)' s iel £eL are thus called generalized consensus relation representatives . Of particular interest are generalized consensus relation representatives that correspond to generalized consensus relations of order 1, A = € (A ). For these, ( II x. x ) = * *- iel x ko A and ( IT p.) consists of just one literal p„. So every term A p where A e S is a prime implicant of V q . In Example 11 these A p 's are abp, and ap p . This property is used in the following lemma. Lemma 8 : For a set of implicants S = {A n ,...,A }, the disjunction is a disjunctive form of the verity function V c . o Proo f: Consider any prime implicant X,P, = ( II x.i)( II p„) of V such that k k ieI i ui i S L contains more than one index. This has a corresponding implication relation X e n x] 1 <£ V A (irr) iel JleL by Lemma 7- When the mono form variable p is added to each A„ and to TL for all I e L we get £eL / £eL This is a valid implication relation because when P = n p is set to 1 it reduces to the preceeding implication relation. So, in any disjunctive form that contains both X, P and V A^p^, X.P, is redundant by Lemma 1. Let y be the disjunction of all the prime implicants of V (the complete sum expression for V_): " E » (X k P k» • keK In By Lemma 7, all of the prime implicants of V that correspond to generalized consensus relations of order 1 are among these terms of Y. These are of the form X,P, = A p with P containing just one literal p . We can thus separate these terms from the others and rewrite ¥ as * E Zi ** ~ i. v. Now each P for k e K' has more than one literal in it. It was just shown t that every term X, P, can be deleted as redundant since X, P c v A^pjj. for each k. Hence, this is equivalent to * 5 V \ P £ 1=1 * * i.e., V A p is a disjunctive form of the verity function, £=1 * iL Q.E.D. Theorem 5 : All the generalized consensus relations with generators which are in subsets of a set S = {A , ...,A } have a one-to-one correspondence with t the prime implicants of Y„ = .V n A p p p . o £—1 K * t Proof : By Lemma 8, V Q = V A^p^ is a disjunctive form of the verity function. By Lemma 7» every generalized consensus relation corresponds to a prime im- plicant of the verity function, and is therefore represented by it. Q.E.D. Algorithm 2 is based on this theorem. It is the application of Algorithm 1 to find all the prime implicants of V starting from the disjunctive form t V g = V AgP£ with Pp's added as index integers and treated as literals. k2 Al gorithm 2: To find all irredundant implication relations X c A v ... - p ^ A (irr), i.e., all generalized consensus relations X = €(A > . . . ,A ) from 1 p q the given set S of products. Here notice that X's which are not in the original S may be produced. (This algorithm is illustrated in Example 12). (1) Index each product A. in S with an integer, denoting it with A.I. 1 (2) Choose a biform variable b, (a) Form the list R or residues with respect to b and the list R^ of residues with respect to b, as in Algorithm 1, along with indices. A.I (b) Form every product XK of a term -r-— in K and a term A.J — =•— in Rr, letting the index K for product X be the conjunc- tion of index I of A. and index J of A.. Thus the new J A. A. product with an index, XK is obtained by X = — r— ,— r 1 ^ b b and K = IJ. (c) Place every new non-zero indexed product XK in S. (d) Compare every new indexed product, A U to every other product A V in S, regarding indices as literals and regard- ing each of A U and A V as a single product. Then u v eliminate A U from S, if A U subsumes A V. For example, u u v * ' abl3U subsumes eiblk but not bl5. (if U and V are not taken into account, some consensus relations may not be obtained. In Example 12, if acdel2 in S is deleted on the grounds that acde subsumes ace of ace5, . ,acel23 is not obtained, leading to an incomplete result.) (3) Repeat Step(2) for the remaining biform variables. k3 (h) Then the integers in the index part of each product in the final S indicate that the products corresponding to these integers are generators of that product. For example if a.cel23 is found in S, the products originally indexed as 1, 2, and 3 are generators of product ace. Thus we get all generations for each product in the final S. The terms in the final set S are the generalized consensus relation representa- tives. Remarks about the use of Algorithm 2 : (a) Notice that in the final S derived by Algorithm 2, A. 's which are not present in the original S are usually present, as will be seen in the following Example 12. (b) When all irredundant disjunctive forms for a completely specified function f are to be derived by Algorithm 3 or ^, based on Algorithm 2, the initial set S of Algorithm 2 is formed with all the prime implicants of f. In the final set S, non-prime implicants of f (though they are implicants of f ) generally show up but are ignored. Only the generalized consensus relations for prime implicants are used in Algorithm 3 or k. (c) When all irredundant disjunctive forms for an incompletely specified function f are to be derived by Algorithm 5, the initial set S of Algorithm 2 is formed with all the "useful" prime implicants of an "upper bound" function B(f). Then all the generalized consensus relations for non-prime implicants as well as for prime implicants of B(f) which are obtained in the final S are used in Algorithm 5. hk (d) When all irredundant disjunctive forms for a completely specified multiple- output function F = {f^,...,^} are to be derived by Algorithm 6, the initial set S of Algorithm 2 for each f" k is formed as all the prime im- plicants of f, and all possible intersections of f with other functions K. K. f. ... f ... f . Consequently some products in the initial S may subsume others. Then the generalized consensus relations for only prime implicants of f, which are obtained in its corresponding final S are used in K. Algorithm 6. (e) When all irredundant disjunctive forms for an incompletely specified xltiple-output function F = {f. ,...,f } are to be derived by Algorithm 7, 1 m muJ the initial set S of Algorithm 2 for each f, is formed as all the "useful" K. prime implicants of the "upper bound" of f , B(f ), and all possible inter- sections of B(f ) with the "upper bounds" of other functions, B(f.) ... K. 1 B(f ) ... B(f ). All the generalized consensus relations obtained in each final S are used in Algorithm 7. (f) Also notice that Algorithm 2 usually generates some redundant implication relations which correspond to non-prime implicants of V . These get o deleted in Step 2(d). Example 12 Suppose the prime implicants of f , S = {abe, bed, ade, abd, ace, bde} are given. Index them with 1 through 6 k5 s Set of implicants Biform variable x R X R- X Products abel, bcd2, ade3 , a bel bdU : s o abdU, ace5, bde6 de3 ce5 bcde45 abel, bcd2, ade3 , b cd2 ael acdel2 ■ s. abd4, ace5, bde6, &6h 1 1 1 ! bcde^5 de6 cde^5 ac^ 5 ( S ~ S ) abel, bcd2, ade3, d bc2 ae3 abce23 S 2 abdU, ace5, bde6, bcdei+5, acdel2 be6 bce i )-5 acel2 acel23 abel,bcd2,ade3, e abl bd6 abd4, ace5,bde6, ad3 S 3 bcde45 , acdel2, abce23, acel23 ac5 bcd^5 acdl2 abc23 acl23 abcd56 bcdi+56 ab / )s^.236 /subsumes\ I b(cd2 / ab/^1236/'s ubsumesN V bcd2 / The generalized consensus relation representatives corresponding to prime implicants of f are underlined. 1*6 Thus we obtain S. = {abel, bcd.2, ade3, abd 1 *, ace5, bde6, bcde^5, acdel2, abce23, acel23, abcd56, bcd^56}. For A 1 = abe, only abel can be found in S. so A = e(A ) only can be derived. For A ? = bed, bcd2 and bcd^ ^6 only can be found in S^. Thus A 2 = C(A 2 ) and k^ = e^A^Ag) . Similarly A,- = C^A^) but none of A , A. , As can be generated from other prime implicants: a 3 , e(A 3 ) \ = e(\) a 5 = e(A 5 ), a ? = e(A i; Ag, a 3 ) a 6 . e(A 6 ) Notice that bede, acde, abce, and abed are not prime implicants of f, though they are implicants of f . Step 3(d) of Algorithm 2 differs from Tison's method in that only certain pairs of terms need to be compared when checking for subsuming terms (instead of comparing all pairs). This is shown in Theorem 6. Let A. p. stand for indexed implicant A., X.J. stand for an implicant 11 ^ ill of the verity function where J. is a product of p.'s (or a single literal p.), i J J and b , ..., b be the biform variables used in Algorithm 2 in this order. In the procedure of Algorithm 2 when two terms X J and X p J occur such that X J c X J , X J is deleted. Theorem 6 limits the comparing that needs to be done. Before stating it, let us first examine a few lemmas. Lemma 9 - Let there exist a term A p with A C b„ and a term X n J n formed q q q — I 11 via consensus with respect to b with J c p . If £ > k then X cr b . (See Fig. 12.) hi Proof : In any level, a term X J formed by consensus has the property that X is the product of all the A.'s corresponding to p.'s for which J c p. without some of the biform variables used to form it. This can u — 1 easily be seen by an induction argument that at any level h where X J = €(XJ,XJ),J =JJ and X = X X without b and b . Thus for term vvwwu vw u vw h h X n J n with J., c p all the literals of A other than the b, 's for k > h > 1 1 1 1 — *q q h — — must be included in X . If I > k, b must also be in X . Q.E.D. Lemma 10 : Let X p J p be a term formed via consensus with respect to variable b . Then there exist two terms in the zeroth level A p and A p such that I q*q r*r A q cb £) A r c b £ , and J g E P q P r (see Fig. 12). X q X li Proof : Let X^ = CU^.X^) = ~ • =- • J^. J^ where X 3 c b £ and X^ £ b^. Since X_ is the product of A.'s corresponding to p.'s such that J_ c p. without some of the biform variables used to form XX, there exists an A c t> in level zero with J_ c p . Similarly, there exists an A cr b. c q-£, 3 - q r~£ in level zero with J, cp , Since J = J. . Ji, J„ Qp p k — r r 2 3 U 2 *q^r Q.E.D, Lemma 11 : Let X J be a term formed via consensus with respect to b and XpJ be a term formed via consensus with respect to b . If k < £, then X-jjJ cannot subsume X ? Jp. (See Fig. 12.) Proof : By Lemma 10 there exist A p and A p such that A C b , A c b„ * q-^q r^r q - l r - l and J cp p , Assume that X J q x ?Jp* But this means J c Jp, meaning J-j_ £ P qP r " Applying Lemma 9 to A p , this means X c b . Applying Lemma 9 to A^p r leads to X c: b i.e., X c b and X c D , so X = 0. This is a contradiction. Thus X,J cannot subsume X Jp. Q.E.D. U8 i level n X„J 2i 2 P„P 0. r \ ••* b 2 A , . . . ,A. without 1 s t ^1 some of b n , . . . ,TL , 1 1 Ta *X J 1 u u P s' >iJ t C J J- - V V >^ X J 1 w v w_ r V -.' A p , S3 1^ I 1 V _ -+ Vi / \ \ X 3 J 3 —- -t""" Vu > / 4^ I I * level I level A-l v l - - 1 _^A p ft " H - . A p : I 1 1 " A p r*r J level k level 1 level I Fig. 12 Formation trees U9 Theorem 6 : No term X ? Jp formed as the consensus with respect to variable b p is subsumed by any term X J, in a previous level in Algorithm 2. Proof : By Lemma 11, X p Jp cannot be subsumed by X, J if X J is formed as a consensus; and X_J p cannot be subsumed by X, J if J, consists of a single literal since Jp must contain two or more literals. Q.E.D. In passing, we will consider the question: Suppose two indexed products, B J, and B p Jp, are produced by Algorithm 2. If J = J p , is it true that B = Bp always holds? (This paragraph is not related to the rest of this paper.) If both B, and B ? are generalized consensus of A , ..., A where J =1, 2 ... t, B = B p must hold since the generalized consensus of A , . . . , A is uniquely determined as the product of the monoform variables J_ x> d ;bcdfl2 abcef 123^5 abefl23U5 bcefl23 i +5 bcdfl2 abde3^5 abdfl2i+ bdef23^5 acdl abf2 ace3 *bcd^5 abd5 Fig. 13 50 by Definition 6. But when they are not generalized consensi, the following example which was found by implementing Algorithm 2 without deleting subsuming terms [9] shows that B is not necessarily identical to B p . The set of pro- ducts, acdl, abf2, ace3, acU, and abd5 have the trees in Fig. 13, among other possible ones which are not shown. For the identical index J = 123^5, there are three different B's. None of them is the generalized consensus of given products, acdl, abf2, ace3, ack t and abd5. As we shall see later, in the case of an incompletely specified function f, for each implicant X in a dijsunctive form of f (X is not neces- sarily a prime implicant of f ) we need every possible subset {A , . . . , A } of the prime implicants of f such that X c a ss ... v A " p q. where deletion of any term in the right side invalidates this implication relation. Corollary 1 assserts that all such subsets of prime implicants can be found in S derived by Algorithm 2. Corollary 1 : For each implicant X of f , there exists an implicant X' of f such that X c X» and X'c A v ... v A (irr) - - p q where A , .... A are a subset of the prime implicants of f. All such P q irredundant implication relations X' ^ A ss . . . v A (irr) are present - P q in the last S derived by Algorithm 2. Proof : Since X implies f, there exists a subset {A , . . . , A } of the prime implicants of f such that X c A v . . . v A where deletion of any - p q term from the right side invalidates this implication relation. If no literal can be deleted from X without invalidating this 51 implication relation, then X c A ss ... A (irr). If literals can "be - P q deleted, we get X' c A v ... v A (irr) - P q by denoting the remainder of x with x ' • By Theorem K such an irredundant implication relation must be produced by some formation tree in Algorithm 2. Q.E.D. Notice that X ' stated in Corollary 1 is not necessarily a prime implicant of f. Examples are the non-underlined products in S^ in Example 12. When one attempts to find all the generations by Algorithm 2, often the testing for subsuming terms is very time-consuming. One way to reduce this time is to adjoin , to each term the set of biform variables which were used to form it. Thus each term is written as XIB with X: implicant part I : index part B: biform variable part. Then, given two terms X, I B and X p I ? B ? , to form a consensus with respect to b we will have X-I B with X X x 3 = €(Xl ,x 2 ) =-- T X 3 = h * Z 2 B 3 = B 1 • B 2 • b However, if X_ and B_ have any common variables, the term X-I-B- can be deleted as shown in Theorem 7. Then after Step 3 of Algorithm 2, the B part can be deleted from each XIB before Step k is done. This condition could be checked before X~I_B is formed by comparing X and B and also X ? and B . In the following Example 13 we could eliminate 52 acdelU5ab either because variable a is common to acde and ab, or because acdelUj? subsumes ace5, or we could avoid forming it because variable a is common to the B part of cdeU5a and the X part of ael. Example 13 s Set of implicants Biform variable x R X R- X Products abel, bcd2, ade3, abdl+, ace5, bde6 a b bel de3 ce5 bd4 bcdeU^a 1 abel, bcd2, ade3» abdh, ace5, bde6, bcdei+5a cd2 de6 cde^5a ael acdel2b- acdX^ab I S 2 abel, bcd2, ade3, abdU, ace5, bde6, bcde^5a, acdel2b d bc2 Hbk be6 bcei+5a acel2b ae3 abce23d abc^3i+5ad acel23bd S 3 abel,bcd2,ade3, abd^ ace5 bde6 » — » > bcde^5a, acdel2b , abce23d,acel23bd e aBl ad3 ac5 bcd^5a acdl2b abc23d acl23bd . bd6 abcd56e bcd^56ae a^dl26be ab>^236de ab^J.236bde 53 Theorem 7: Any term X_I_B_ formed as described above in which a variable b. 3 3 3 k is in both X and B can be deleted without changing the outcome of Algorithm Proof : Corresponding to II is an implication relation, letting I = Pl P 2 ...P q , x 3^ A r A 2 \ Since variable b. appears in B_, b, is biform in {A. ,A n , . . . ,A }. But b, k 3k l'2''q k (or b ) is also in X~, so at least one term on the right side is redundant K. -J since it contains b (or b, ). Then, since X,.I_ corresponds to a non-ir- rendundant implication relation, there exists another term X, I,B« such that X-.I_ c Xi Ji which corresponds to an implication relation derived from X_ c A \^ . . . \^ A by eliminating redundancy. q By Theorem 6, X, IiB, must appear either in a previous level or the same level as X_I B , in order for X_I_ c X, I, . But this means that X_I 33 3 3 3" H 33 will always subsume another term, and can be deleted. Q.E.D. Unfortunately, when X_ and B_ have no variables in common, it is not always true that II corresponds to an irredundant implication. Consider {acl, abcd2,abd3,adU} . Two of the formation trees this set produces are shown in Fig. ik. Term cdl23^+ab corresponds to a redundant implication relation cdc A v A v/ A -/ Ai , though X_ = cd and B = ab have no. common variables. It should be noted that it is not necessary to delete subsuming terms, but doing it helps later in reducing processing time. The method presented in this chapter is based on deriving prime impli- cants of the verity function and transforming them into consensus relations. 54 cdl23ab !<1123Uab bcdl2a bcdl3a bcd24a acl = abcd2 ■ abd3 = ad4 = Vl A 2 P 2 A3P3 A 4 P 4 Fig. 14 Tison's prime implicant formation algorithm, Algorithm 1, is used to derive these prime implicant s. Actually, any algorithm which derives all the prime implicants starting with an arbitrary disjunctive form can be used for Steps 2 and 3 of Algorithm 2. As a final remark, notice that in an implication relation Xc A >/ A v . . . v A if X • A. =0 for any A., then A. is redundant. Thus, given X, all the gener- alized consensus relations for X can be derived using Algorithm 2 starting with S = {A.p.|X • A. /= 0}. This simply excludes terms which cannot contribute to any implication X c A v A^ such that no A. can be deleted, t 1 55 4. DERIVATION OF ALL IRREDUNDANT DISJUNCTIVE FORMS FOR A COMPLETELY SPECIFIED FUNCTION Before proceeding to the derivation of all the irredundant dis- junctive forms, we will describe a few lemmas. Lemma 12 : If a function g is such that g £ & v a v . . . \y A and A_ c B, v . . . v B. , then g c B. v . . . v B, v A, v . . . v A — 1 k — 1 kl s Proof : Combining the two implication relations A. v/ . . . A c A_ v . . . v A 1 s - 1 s and A_ tions. Form f = A n ^ A„ v A„ v A. >• A c v/ A^ (12) 1 2 3 4 5 6 Replace A c by At v A_ v A, to form j 1 z b duplicates f = A x ^ A 2 ^ A 3 n/ A 4 v (A 1 ~ ^ ~ A^) v A & (13) Replace A, in (12) by A ^ A, ^ A to form duplicates f^A^A^^vA^vy^v^v X 5 ) (14) Replace both A c and A, in (12) to form j o duplicates duplicates f = A ± v A 2 s, A 3 v A 4 v (A x n/ / 2 n/ A fi ) v (A 3 v A 4 v A 5 ) (15) (12), (13), (14), and (15) are all disjunctive forms for f. Thus, (13) and (14) are IDF's since (12) and (15) contain all the prime implicants in (13) and (14). Proof : As is well known, f can be expressed as the disjunction of all its prime implicants: 60 f = A, ^ . . . v A 1 P By Lemma 14, each disjunction formed by replacing a prime impli- cant A, with a disjunction of prime implicants which constitute a generation of A^ must be a disjunctive form of f . So every disjunction derived in Step (2) is a disjunctive form of f . We will now show that every disjunction of prime implicants which expresses f is formed in Step (2) . Let ¥ be any disjunction of prime implicants which expresses f and let S = {A , . . . , A } be the prime implicants of f not in ¥ . By Lemma 15 ¥ must contain for each A^ of S a disjunction A, v . . . v A. for which P q A. Q \ v • • • v A, . By the replacement of the A^'s by these correspon- P q ding disjunctions in the complete sum f ■ A- v « . . v A in Step (2), then, ¥ is derived. Thus, all the disjunctive forms of f consisting of prime implicants are derived in Step (2). Then by Step (3), all the disjunctive forms with re- dundant prime implicants are removed, leaving the desired set of all irredun- dant disjunctive forms. Q.E.D. Notice that in the construction of irredundant disjunctive forms in Theorem 8, exactly one of the generations for each prime implicant is consider- ed in Step (2). But some irredundant disjunctive form of f may contain two or more generations for the prime implicant. This is not a contradiction. The second or other generations are associated with other prime implicants consi- dered during the construction. An example is shown in the following. Example 15 For a function that consists of 61 the following prime implicants, their generations are obtained by Algorithms 1 and 2 (since the derivation is too long to list here, we list only the final results) . A = ac B = abc C = abf D = bcf E = abd F - acd G = cde H = ace I = bed J = bdf K = ade L = adf M = cdf A B = e (E, F) = e (E, G, H) c = e (A, d) = e (j, l) = e (d, i, l) = e (a, j, m) d = e (b, c) = e (j, m) = e (c, e, m) = e (c, f, j) = e (b, j, l) = e (c, e, f) = e (f, j, l) = e (c, g, h, j) = e (c, e, g, h) = e (g, h, j, l) e = e (b, i) f = e (G, H) G = e (F, K) H i = e (a, e) j = e (c, e) = e (d, i) = e (a, d, e) = e (b, c, i) k = e (A, G) L = e (A, M) M = e (F, L) = e (G, H, L) f = AvCvEvGvHvMisan irredundant disjunctive form of the given 62 function, because none of these prime implicants can be deleted without causing ¥ not to equal f and for each prime implicant not present here the following re- lations hold: B c E v G n/ H (irr) DqCn/EvGv/H (irr) F c G s/ H (irr) I c A ^ E (irr) J c C ss E (irr) KcAvG (irr) L SA vM (irr) However, for D we have another generation DQCvEvM. Therefore, for D, the irredundant disjunctive form ¥ contains two generations, C v E sy G sy H and C v E v M, both of which are present in V . So we can consider that Y is obtained by the following two cases: (1) A v (E v G v H) v C v (C v E v M) v e v (G v H) v g v H v (A v E) ^ (C v E) v (AvG) ^(A^M)^M = AvC^E^G N/ H v 'M . (2) A ^ (E v G v, H) v C v (C v E s, G v H) v e v (g n/ R) v G ^ H ^ (A ^ E) n/(C v E)^ (A^G) v (A^M)v M = A^C^E^G^H^M . Thus, the presence of B ^ C and C v E v M in f which are both generations of D may be interpreted as follows: In case (1) C ^ E v G ^ H is associated with prime implicants C, E, G, and H, and C v E v M is associated with D. In case (2) Cv/EvGvH is associated with D, and C v E v M is associated with C, E, and M. The derivation of irredundant disjunctive forms (IDF's) for a given f stated in Theorem 8 can be accomplished by forming a switching expression that represents all IDF's of f, as follows. 63 Algorithm 3 : To derive all the IDF's of a given completely specified func- tion f. Generations for each of the prime implicants, A , . . . , A , of f are assumed to be found by Algorithm 2 (although S derived by Algorithm 2 gen- erally contains non-prime implicants, ignore these non-prime implicants and consider only prime implicants of f in S) . (1) We define a presence factor p. that is equal to 1 if and only if prime im- plicant A. is "present" in an IDF. For Example 14, we have p = p~ = p = p = p = 1 and p = for IDF (13). Since either prime implicant A or one of its nontrivial generations (k) G. = {A. , . . . , A } must be present in any IDF, we introduce a 1 V k 1 u (k) generation factor P^ which is the product of the presence factors p. p. corresponding to the kth generation V \ 1 u (k) G = {A. , . . . , A } of prime implicant A ; V k 1 u p< k) - P . ... p. k. k 1 u where A. = € (A , . . . , A ) . For Example 14, since A,. = € (A 1 \ \ * l ' 1 u A , A ) holds, we have P^ = p. p p, . Also P^ = p_ p. p c since A, ^ DiZD O J 4 J D C (,A_ , A,, A,.; , Then we associate to each A an inclusion function Q(A.) which is the dis- i i junction of p. and all nontrivial generation factors of it, P. , . . . , P (w) • i e Q(A 1 ) ~ Pj^ v P £ ^ ... v P. 64 For Example 14, Q(A_) - p c ^ P* 1 ' and Q(A,) = p, ^ pf 1 ^ . The inclu- j j j bob sion function means that for each A we must have exactly one of A and (1) (w) its w generations G , . . . , G . Inclusion functions are also called presence relations . (2) Then form the product of all the inclusion functions P T = n Q(A ) 1=1 which is called Tison function or presence function . For Example 14, T = ( Pl ) (P 2 ) (p 3 ) (p 4 ) (P 5 s,P^ 1} ) (p 6 ^P b 1} ). (3) Express each generation factor with its presence factors, in T. For Example 14, P^ = p x p 2 p & and p 6 = P 3 P 4 P 5 • Then expand T into a disjunctive form and delete subsuming terms, leaving where each $. is the product of p ' s. Then each . represents an IDF and is hence called IDF representative . In other words, all the p.'s contained in $ . represent prime implicants that are "present" (i.e., contained) in an IDF. All the IDF's for f are represented by these $.'s. Of course, IDF's with the minimal number of p.'s among them represent minimal disjunctive forms (i. e. , minimal sums) when considering only the. number of prime im- plicants as the criterion of minimality. Minimal sums by any other criter- ion can be selected since all the IDF's are represented. For Example 14, we get T = Pl P 2 P 3 P 4 (P 5 v Pl P 2 P 6 ) (p 6 v P 3 P 4 p 5 ) = P X P 2 P 3 P 4 P 5 P 6 v P X P 2 P 3 P 4 P 6 v Pi P 2 P 3 P 4 P 5 - P l p 2 P 3 P 4 P 5 P 6 65 = P X P 2 P 3 P A P 6 - P x P 2 P 3 P 4 P 5 • The terms in the last expression of T represent all the IDF's for f, y., E A n v A_ v A„ v- A. n/ A, and ¥« = A- v A„ v A \/ A. \/ A c . 112346 212345 Example 16 Suppose the following function is given: f = ax v ay \/ bx v by v bz \/ xy v xz v xy v yz Corresponding Prime Implicants Generations Inclusion Functions A 1 = ax {A 2 A 6 ) ?1 v p 2 p 6 A = ay {A 1 A g } P 2 v p 1 p g A 3 ■ b * U 4 A 6 >,{A 5 A ? } {A 5 A 6 A 9 > ?3 v ?4 ?6 v ?5 P? v ?5 p & p g „ A 4 = by {A 3 A g },{A 5 A 9 > {A 5 A ? A g } p 4 v ^ Pg v ^ Pg v ?5 p? Pg A 5 = bz p 5 A 6 = ^ P 6 A ? = xi {A 6 A 9 > p ? v p 6 p 9 A 8 = Xy P 8 A 9 ■ yz * A 7 A 8 > P 9 ~ P 7 P 8 Thus T - (P X N/ P 2 P 6 ) (P 2 N/ P X Pg) (P3 V P 4 P 6 - P 5 P ? - P 5 P 6 Pg) (P 4 - P3 Pg v P 5 P 9 v P 5 Py P 8 ) (P 5 ) (P 6 ) (Py v P 6 P 9 ) (Pg) (P 9 v P 7 P 8 ) T = Pl P 5 P 6 P? Pg v, Pl P 5 p 6 P 8 P 9 - p 2 P 5 P 6 P ? P 8 - P 2 P 5 P 6 P 8 P 9 Therefore all the irredundant disjunctive forms for f are: t. = A 1 sy A_ v A, s/ A_ v A_ = ax v bz s/ xy \/ xz v xy 2 = A. v A c v A, v A v A n = ax v bz v Xy v xy ^ yZ i -> o o y 66 L = A. v A v A^ v A v Ag = ay v bz v icy v xz v xy ¥, = A A v A P v A, v A fl v A = ay v bz v x? v xy v yi 425609 From Theorem 8 it is easy to see why Algorithm 3 yields all IDF's of f. In Theorem 8, we derived all the IDF's, starting from the disjunction of all prime implicants. But as will be shown next, even if we start from an arbitral IDF or furthermore any disjunction of some prime implicants which expresses f but i: not necessarily irredundant, we can still derive all IDF's. Theorem 9 : (Chang and Mott [3]) Given an arbitrary disjunctive form for f which consists of prime implicants only but is not necessarily irredundant, all IDF's for f can be derived as follows. Let $ = P x P 2 . • . P t denote the product of presence factors corresponding to the prime implicants A , . . . , A contained in the given disjunctive form for f . Replace each It p. (i = 1, 2, . . . , t) in * by the inclusion function QUJ = p i v T ± v v pn' where P , . . . , P.^- are generation factors corresponding i i 1 to the generations G. , . . . , G. 1 ' of A. . Expand the resulting product t W. / X t' = n ( P . v(^£ pp)) i=l into a disjunctive form and delete subsuming terms. Then we have These terms $g's represent all IDF's for f. Proof : First we show that each $g obtained represents a disjunctive form for f , By the assumption, the disjunctive form which corresponds to $ = p 1 . . . p expresses f, ^ = A x v A 2 v . . . v a , 67 Any term (other than $) derived in the disjunctive form of T 1 can be obtain- (k) ed by replacing p.'s in $ by P. 's. This corresponds to replacing A. 's with (k) the corresponding G. ' s . By Lemma ik , each disjunction obtained this way expresses f. Furthermore, deletion of subsuming terms of T 1 corresponds to deleting non-irredundant disjunctive forms. Therefore we have shown that only disjunctive forms of f are pro- duc ed . Next we will show that all the IDF's of f are represented by some term in the disjunctive form of T- = I (p. w (J* P<*>)) . 1=1 As the first step, notice that if p , . . . , p denote the presence factors not contained in $ = p . . . p , then all the IDF's of f are repre- J- w sented among the terms in the disjunctive form of T = T' (p v ( ! U P^ } )) . . . (p v ( 3 V p| J) )) j=l j=l by Theorem 8, where (p v ...),..., (p v . .' . ) in T are the inclusion functions of p , . . . , p respectively, because the presence factors corres- ponding to all the prime implicants of f are contained in I as p , . . . , p , p . . . p . u r v As the second step, let us prove that the disjunctive form of t' (p u v ( y p^ } )), where p is the presence factor corresponding to any prime implicant A does not contain any new terms which represent IDF's that are not represented by any terms in the disjunctive form of T' . Let $ denote an arbitrary term in the disjunctive form of T' after deleting subsuming terms. 68 Then there is no possibility that $, p or $, P represents a new IDF because by Lemma 15 <3>, must contain either p or some P and consequently J h u u neither 1) p nor $ P^ j; contains presence factors other than those contained in n u h u . . Even if we further multiply T ' (p ^ ( .v. P )) by the inclusion functions h u j=l u * of other presence factors not in $ = p . . . p no new terms are generated. W / .V Therefore, the disjunctive form of T 1 (p ^ ( .-^, P )) does not contain any u j =1 u new terms representing IDF's which terms in the disjunctive form of T 1 do not represent. Summarizing the above two steps, we have shown that all the IDF's of f are represented by some terms in the disjunctive form of T 1 which remain after deleting subsuming terms. Q.E.D. The disjunctive form f = A v . . . v A used to form T' = Q(A ) X "C 1 . . . Q(A t ) in Theorem 9 is called the base . Algorithm 3 uses the complete sum for the base. As a special case, we get all IDF's for f from an IDF instead of from a disjunctive form which is not necessarily irredundant as the base. Corollary 2 : Given an arbitrary IDF for f as the base, all the IDF's for f can be derived by the process stated in Theorem 9. Example 17 Consider $ in f of Example l6, h = p l p 5 p 6 p 7 p 8 69 Multiply out only the inclusion functions corresponding to these presence factors (p l v p 2 p 6 } (p 5 } (p 6 } (p T v p 6 p 9 } (p 8 } = (P 5 ) (Pg) (P Q ) (P X V Pg) (Vrj V P ) = P x P 5 P 6 P T P 8 - P x P 5 P 6 p 8 P 9 - P 2 P 5 P 6 P T p 8 - p 2 P 5 p 6 p 8 P 9 • which is the same as the T obtained in Example l6 when we started with the pro- duct of inclusion functions for all the prime implicants of f. If f is given by an arbitrary disjunctive form Y = A ^ . . . v/ A^, where each A. is not necessarily a prime implicant, then the set of prime im- plicants required for the base in Theorem 9 can be found from this V by replac- ing each A. of ¥ with some prime implicant B. of f such that A. a B.. i J i ~ J In Theorem 8, we obtain all IDFs. If we want to form only one IDF for a function f, we can do this with the following simpler procedure by consi- dering the inclusion functions and Lemma 12. If a disjunctive form 4* = A •<• L v . . . sy A for f consisting of prime implicants contains a prime impli- t cant A^ and other terms B. (i = 1, . . . ,t) such that A^ c v B. (irr) i=l then A^ is redundant and can be deleted from H' and the remainder, V, still expresses f . If we do this iteratively starting from ¥ equal to the disjunc- tion of all the prime implicants, we can form an IDF. Consider the following procedure which is a generalization of one given by Chang and Mott [3] to form a near-IDF: 1. Set $ = p . . . p the conjunction of the presence factors corresponding to all the prime implicants. (k) 2. Select some generation factor P. . If all of them have been tested, $ l is an IDF representative, so quit. TO (k) 3. If $ contains p. and $ £P. , then delete p. from $ . Otherwise, do *i 1 ■ ' 1 nothing. k. Go to Step 2. Testing whether ¥ contains A. and other terms B. (j = 1, . . . , t) t X J (k), such that A. £ ^ B. (irr) is done in Step 3. When all the P. ' s have "been 1 j-i J tested, no more p.'s can be deleted from $, so the corresponding f is irredun- dant . For Example 16, form ® = v ± V 2 P3 P^ P^ P5 P- P Q Pq • p l ' = P 2 p 6 2 $ so delete p l : $ = p 2 p 3 p l+ p 5 p 6 p 7 p 8 p 9 P 2 X) = p l p 8 * * p 3 = P U P 6H $ so delete p 3 : $ = p 2 p l* p 5 p 6 p 7 p 8 P 9 (2) (3) Since $ does not contain p now, we skip P and P p^ - p 3 p 8 ^ $ (2) p ^ = P 5 P 9 2 $ so delete p^ : $ = ? 2 v^ p g p ? p Q ?9 P T = P 6 P 9 2 $ so delete p ? : $ = p 2 ?5 p g p Q ?9 P 9 1} = P T P 8 * * Thus, $ = p p p.- pn p is an IDF representative. Let us describe a property of products of inclusion functions that we will use in proving Lemma 16. (This property is not directly related to the derivation of IDF's.) Corollary 3 : For a disjunction of some of the prime implicants of a function f. ¥ e A ^ A v ... v A u v w even when ¥ may not be an expression for f , each term in the irredundant dis- junctive form T" = $ v $ v . . . \/ $ into which the product 71 T" = Q(A ) . Q(A ) . . . Q(A J U V W is expanded, represents a disjunction of prime implicants of f that is implied irredundantly "by ¥, i.e., YEA^Av...^Ac v A. for J = 1, ..., I U V W r . I -.1 ii p. e a. ) with no redundant terms on the right hand side. If Y expresses f, then the terms in T" represent all IDF's of f. The proof of this is similar to the proof of Theorem 8. T" represents the replacement of the A.' s of ¥ by generations of them. For example, in Example 16 we can form T" = Q(A ? ) . Q(A 9 ) = (p T v P 6 p Q ) (p Q v P ? Pg) = P T P 9 - P ? Pg - P 6 P 9 for l 8 ' Now $2. $2 ^3 T" = P ? P 9 - P ? P 8 - P 6 P 9 represents three disjunctions U T v A 9 , A T v- Ag, A 6 v A 9 > . _ Each of these is implied irredundantly "by A y A : 1) for $ 1 , A s, A c A v A is xz" ^ yz c xz ^ yz and no term can be deleted from the right hand side, 72 2) for $ , A v A c A >, A Q is xz v yz cz xz v xy and no term can be deleted from the right hand side. 3) for $ , A v, A c Ag n, A is xZ v yz c xy v yz and no term can be deleted from the right hand side. Furthermore, these three disjunctions are the only disjunctions of prime im- plicants of f that are implied by A 7 v A irredundantly. 73 5. ELIMINATION OF ABSOLUTELY DISPENSABLE PRIME IMPLI CAM'S When a function has many prime implicants, it usually takes a lot of time to expand the Tison function mentioned in Algorithm 3 into disjunc- tive form. The following theorems can simplify this. A prime implicant is said to be essential if the prime implicant is contained in every IDF. Theorem 10 : A prime implicant is essential if and only if it cannot be repre- sented as a consensus of any other prime implicants (i.e., as a generalized consensus of order 2 or greater). Proof : If a prime implicant A^ cannot be represented as a generalized con- sensus of any other prime implicants, every IDF must contain A^ since in The- orem 8 A^ can never be replaced by a generation in Step (2). If A^ can be represented as a generalized consensus of some other prime implicants, there is a disjunctive form for f which does not contain A^ but contains one of its generations in Step (2) of Theorem 8. Then by Step (3) of Theorem 8, this disjunctive form or the disjunctive form obtained by deleting redundant terms is an IDF for f which does not contain A^ . Thus A^ is not an essential prime implicant. Q.E.D. Definition 9 A prime implicant of a function is said to be absolutely dispensable if it is not contained in any IDF of f. Examples of absolutely dispensable prime implicants will be shown later. lh Definition 10 A prime implicant is said to be conditionally eliminable if it is neither essential nor absolutely dispensable. In Theorem 11 we will show a sufficient condition for a prime im- plicant to be absolutely dispensable. Before proceeding to Theorem 11, let us present Lemma 16 about a property of inclusion functions. Given a prime implicant A and one of its O generations {A , A , . . . , A } , the product T = Q(A 1 ) . Q(A 2 ) . . . Q(A t ) can be formed. Lemma l6 states that if p is not present in this product, o then each term $ of T in irredundant disjunctive form subsumes some genera- tion factor of Q(A ) other than term p . This is illustrated as follows. g g Suppose the inclusion functions for some prime implicants of a function are given as follows (this example is part of a more complete Example 19): Q(A 3 ) = (p 3 ^p 1 p^) Q(a 5 ) = (p 5v , p 2 p 9 ) Q(A 1Q ) = (p 1Q v p u p 9 v p 3 P 5 v Pl V k P 5 v P 2 P 3 P 9 ) {A , A } is a generation of A . In the product Q(A 3 ) . Q(A ) = (p 3 v P x p^) (p 5 v P 2 p ) = P 3 P 5 s, P 2 P 3 P 9 v P x P U "P 5 v/ P x P 2 P^ P 9 no p appears. Then, by Lemma 16, each term in the disjunctive form of Q(A ) . QCA-) subsumes some nontrivial generation factor of Q(A,q) (e.g., the last term of Q(A ) . Q(A ) , p p p, p , subsumes the generation factor p, p q of Q(A 1Q ) ). 75 Lemma l6 : Given a generation factor corresponding to a nontrivial generation (s) of a prime implicant A , P = p. p_ . . . p, , consider the product of the (s) inclusion functions corresponding to the presence factors in P v , 6 T = ( P] _ v (.l{ Pp } )) (p 2 - (^ P^ } )) . . . (p t v (.^ P( d) )) (1) (n i } (1) (1) ^0 If none of P^ ' , . . . , P. ; P£ ', ...;...; P* ', ... P. contains the presence factor p corresponding to A among its presence factors, then each term in the disjunctive form of T subsumes some P ' (i.e., each term con- g tains all the presence factors which constitute some P . The value of j g can be s. ) In order to see the reason for this, consider what is represented by inclusion functions: for Q(A ) : A c A (irr) A 3 £ A ! v A^ ( irr ) for Q(A C ) : A_ £ A c (irr) 5 5 5 A c A 2 v A (irr) for Q(A 1Q ): ^ C^ (irr) A 10 cA^ V A 9 (irr) A 10 - A 3 v A 5 ^ irr ^ A 10 Q A l v A h v A 5 ^ irr ^ A 10- A 2 ^ A 3 vA 9 ^ irr ^ . Next consider Q(A 3 ) . Q(A^) = p 3 p^ v p g p 3 p 9 v p_ L p^ p 5 v p 1 p 2 p^ p 9 As described at the end of the last chapter, this corresponds to A v A c A v A A 3 ^ A^ c A 2 ^ A 3 v A 76 A 3 v A 5 £ A i v \ v A 5 A 3 ^ A 5 <= A ! -^ A 2 ^ A U ^ A 9 ' Since A . ^a vA , we also have the following relations, by transitivity, which are not necessarily irredundant : A 10 eA 3 .A 5 A 10 £A 2^V /A 9 A 10 £A l^\ vA 5 A 10 £A 1 ^ A 2 V \- A 9 ' Each of these can be made irredundant by elimination of some terms on the right hand side, resulting in one of the irredundant implication relations for A listed for Q(A ) . However, since A n never appears on the right side of these, the relation A cA (irr) will never be obtained by doing this. It thus follows that each term of Q(A ) . Q(A ) subsumes some term of Q(A ) other than p , i.e., some generation factor of Q(A ) . Proof of Lemma 16 : First expand T into disjunctive form, removing subsuming terms T = $ 1 N/ $ 2 V . . . sy $ By Corollary 3, this means A.. v A n/ . . . A^ c , ■ >/ A. for each j=l, . . . , k 1 2 t ~ {i p. e $.} x We also have A c A., ^ . . . ^ A^ . Therefore, g - 1 t A c , , v A. for each j=l, . . . , k g" (i | P± e ^} i To make each one of these implication relations irredundant, we can remove terms from the right , forming one of the irredundant relations for A o However, since A never appears on the right of any of these, A c A (irr) will never be obtained, but for each implication relation above, one of the 77 consensus relations of order 2 or more will "be obtained, corresponding to some (k) P . It thus follows that each $. of T must subsume some term of Q(A ) other g J g than p g Q.E.D. Theorem 11* : (Chang and Mott [3]) Let A be a prime implicant with inclusion function Q(A ) = (p v ( x, P ) ) . If for some P , none of presence fac- g g s=l g g (s) tors p, ' s contained in P is such that the inclusion function corresponding h g to prime implicant A^ contains a P which contains the p , then A is absol- utely dispensable. Proof- Let P = p P • • • P. fulfill the above condition. Then by Lemma g 12 t 16 each term in the disjunctive form of t t' = n ( P t n. / .x = n ( P . v ( v 1 p! jj )) i=l ! J X * Theorem 11 was stated in Chang - Mott's paper [3] (as Theorem h) with both a necessary and sufficient condition for a prime implicant to be absolutely dis- pensable. However, this is not a necessary condition, as the following counter- example shows, [ll] Consider the function f given by its prime implicants: A l A 2 A 3 \ A 5 A 6 A 7 f = {abed, abe, abed, bee, cde, ade, bde} The product of the inclusion function is T = (p 1 ) (p 2 ) (p 3 ) (p^) (p 5 v p x p 2 p 6 v p x p 6 p ? ) (pg v p 3 p^ p 5 v p 3 p^ p ) (P T -P 2 P 6 -P U P 5 ) = V ± p 2 p 3 p u p 5 v Pl p 2 p 3 p u p 6 Thus, A is absolutely dispensable but both P.1 = p p, and P2, = p, p have presence factors corresponding to prime implicants whose inclusion functions contain p , Q(A_) and Q(A^) . 7 5 6 78 subsumes some P where j can be s. g Next, consider an expression for all the IDF's of f, n. v 1 ( i) T = T 1 n (p. v ( v P. J; )) i=t+l X j 1 where p , p , . . . , p. , P ++ -i » • • • » P are the presence factors corres- ponding to the prime implicants of f (by Theorem 9 all IDF's of f are repre- sented by the terms of the disjunctive form of T) . Each term in the disjunctive form of T subsumes some P since T 1 g is part of T. Since both P and p cannot be contained simultaneously in o o any irredundant disjunctive form representation by Lemma 13, no IDF which is represented by any term of the disjunctive form of T can contain p . Therefore O A is absolutely dispensable. Q.E.D. The following corollary is a special case of Theorem 11 for the in- stance where the inclusion function corresponding to each presence factor p. ( s ) in some P = p n p. . . . p^ has no generation factor, g 1 2 t Corollary h : Let A be a prime implicant with inclusion function Q(A ) = g S (p v ( v. P )) . Then if there exists some P " which consists of only the g s=l g g presence factors of essential prime implicants, A is absolutely dispensable. If Q(A ) has one or more generation factors, then the corresponding prime implicant A cannot be essential. Taking this fact into account, the contrapositive of Theorem 11 is stated as follows. Corollary 5 : Let A be a prime implicant with inclusion function Q(A^) = > ~ l5_ p (s) )). If A g s-1 g g (p v ( v P ' )). If A is conditionally eliminable, then for every P g s=l s g J ' g (s) some generation factor corresponding to at least one p. contained in P in- eludes the p g Theorem 11 is useful for simplification of Algorithm 3. 19 Algorithm h : To derive all the IDF's of a given completely specified function f , modifying Algorithm 3. Form the Tison function as in Algorithm 3 or Theorem 9 5 hut remove the inclusion functions for absolutely dispensable prime implicants found by Theorem 11. If any generation factor contains a presence factor .corresponding to one of these absolutely dispensable prime implicants, delete that generation factor entirely. (This corresponds to setting the presence factors to zero.) We can speed up the multiplication to form disjunctive forms by "fac- toring" essential prime implicants and deleting subsuming alterms and terms as we multiply, as we shall see in Example 19. Example 18 : The inclusion functions for the function defined by the disjunction of prime implicants A , A , . . . , An are given as follows: Prime implicants Inclusion functions A ± = de Q(A X ) = Pl A 2 = cde Q(A 2 ) = p 2 A 3 = acd Q(A 3 ) = p 3 v p 2 p^ (1) 3 v ' '3 = P, v P A^ = ace Q(A^) = p^ v V ± P3 "> v IP A 5 = abd Q(A 5 ) = p 5 Ag = abe ^ A ^ = Pg ^ P-l P 5 = V6- ? 6 (1) A^ = bed Q(A ) = P T v P 2 Pg v p 3 p 5 sy p 2 p 3 p 6 s, p 2 p^ p^ v p 2 p^ p 6 . n p (l) _(2) _(3) P (U) p (5) - Py V P V P sy P s/ P V P 80 Ag = bee Q(Ag) = P g v V± ^ ^ P]+ p g v V± ^ p^ v P] _ ?3 p g v P;L p^ ?5 . (1) (2) (3) p (U) _(5) - Pg v Pg V Pg V P q v Pg v/ P Q A , A and A are essential prime implicants, since they have no generation factors by Theorem 10. By Corollary h, A^ is an absolutely dispensable prime implicant, be- cause its generation factor consists of only presence factors corresponding to essential prime implicants. By Theorem 11, A is absolutely dispensable, because there exists (T) Pp = Po Pq sucn that neither Q(A_) nor Q(A_) contain p . By Theorem 11, An is absolutely dispensable, because there exists / o \ ~P = p> p^- such that neither Q(Ai ) nor Q(A^-) contain p 8 . Since A,-, A and Ao are absolutely dispensable, we can delete Q(A^-), Q(A„) and Q(A Q ) from the Tison function. We thus have 7 o T = P x P 2 (p 3 v/ P 2 P^) (p^ v P 1 P 3 ) P 5 = P x P 2 P 3 P 5 - Pl P 2 P^ P 5 , whose terms represent all IDF's. Example 19 : The inclusion functions are obtained as follows for the function defined by the disjunction of given prime implicants A , A , . . . , A , : Prime implicants Inclusion functions A 1 = ac Q(A 1 ) = p-L A 2 = abc Q(A g ) = P 2 n/ p^ Pg vp^ p^ p Q A 3 = abf Q(A 3 ) = P 3 v/ P 2 p^ k k = bef Q(A U ) = p u v p 2 P 3 -p 3 P 5 p 6 -P 3 P 6 p 1Q - P 3 P 5 P 7 P 8 - P 3 P T P 8 P 10 81 A^ = abd Q(A ) = p^ v p 2 p Ag = acd Q( A g) = P5 v Pt P3 A^ = cde Q(A^) = p^ s, p^ p u Ag = ace" Q(Ag) = Pg a 9 = t^d q(a 9 ) = p 9 vPl p 5 A A 1Q = bdf Q(A 1Q ) = p 1Q v Vk p 9 -p 3 p 5 - V± T> k P 5 - P 2 P3 P 9 u = ade Q(A X1 ) = p^ v Pl P? A and Aq are essential. A is absolutely dispensable, since (2) there exists P = p p such that neither Q(A) nor QCA^) contains p . It is easy to see that A v A_ v A v A v Aq is a disjunctive form for f, because A 2 c A v A v Ag \ £ A 3 v A 5 ^ A T v A 8 A 6 E A T v Ag A 9 EV A 5 A 10^ A 3-S A n £ A i - A T and consequently each prime implicant or one of its generations is contained in A. sy A v/ A_ v A_ n/ A q . 1 3 5 T Therefore, all IDF's for the given function can be obtained by Theorem 9 as follows : T = Q(A ] _) . Q(A 3 ) . Q(A ) . Q(A ) . Q(A g ) = P-l (P3 - V 1 P U ) (P 5 - P 2 P 9 ) (P 7 - P 6 P U ) Pg = P-l P 3 P 5 P ? Pg - P-l P 2 P 3 P ? Pg P 9 - P-l P U P^ P T Pg - P X P 2 P U P T P 8 P 9 v Pi P 3 P 5 P 6 P8 P ll v P l P 2 P 3 P 6 P 8 P 9 P ll 82 - Pi P U P 5 P 6 P8 p ll v p l p 2 p l* p 6 p 8 p 9 P ll * This result shows that prime implicants A , A , A, , A , A,-, A , A , and A are conditionally eliminable. This example is very interesting in the sense that there exists absolutely dispensable prime implicants each of which is "absolutely dispens- (s) able" not due to the condition in Corollary h (i.e., P consists of only the presence factor of essential prime implicants) but due to the other condition stated in Theorem 11. If we had used Algorithm k, we would proceed as fol- lows : 11 T = n Q(A.) i=l x = P x (P 2 V P 5 Pg ss P 5 P ? P q) (p 3 v P 1 P U ) (p^ v Pg P 3 sy P 3 P 5 Pg v P 3 V P 1Q V p 3 p 5 p 7 p 8 s, p 3 P 7 i/p 10 ) (p 5 - p 2 p 9 ) (p 6 - p t p 8 ) (p 7 - p 6 p n ) (p 8 ) (P 9 ^ P-l P 5 ) (P i;L ^ P 1 P^) We delete p p^ p., _ and r>„ x>„ p Q p_ . because they contain p.. , and since A_ . 3 6 10 3 7 o 10 10 10 is absolutely dispensable, p = 0. To speed up the multiplication, we can first "factor out" p and Po. (if we multiply out the above expression in a straight forward manner, processing time is far greater. ) T = P x P Q (p 2 v P^ Pg v p^ P^) (p 3 v P^) (p^ n/ P 2 P 3 v p 3 p^ Pg s/ P 3 p^ P T ) (P 5 ^P 2 Pp) (Pg v/Py) (Py V Pg P^) (Pp N/P 5 ) (P i:l V Py) We can delete (p^ v p ) since (pg v p„) (p„ v Pg p^) = (p.v Pg P-^) and simi- larly delete (p g v p^), (p- ^P^), and (P^^Py)- Then T = P x Pq (p 2 v/ P 5 Pg v P 5 p ) (p^ v P 2 P 3 v P 3 P 5 Pg v P 3 P 5 P ? ) (P 5 v P 2 P 9 ) (P 7 ^Pg P 1X ) 83 = P-l P Q (Pg P^ n/ P 2 Pg ^ P^ P 5 Pg ^ P 3 P 5 Pg ss V^ P 5 P T ss P 3 P 5 P T ) (p 5 v P 2 P 9 ) ( P T ^ ?6 p ll ) (deleting subsuming terms as we multiply) = P x P Q (P 2 p u P 5 - P 2 P U P 9 - p 2 P 3 P 5 - p 2 P 3 P 9 v Pl| p 5 p 6 ^ P 3 P 5 p 6 v p^ P 5 p ? V P 3 P 5 Pj) (Pj V Pg V ±1 ) = P-l Pg (P U P 5 P ? v P 3 P 5 P T - P 3 P 5 P 6 P 1X - P U P 5 Pg P n - P 2 P^ P T P 9 - P 2 P U Pg P 9 P n - P 2 P 3 P T P 9 - P 2 P 3 Pg P 9 P 1X ) = V ± Pg (P 3 v P^) (p^ v P 2 pJ (p v pg p^), as derived above. The Tison function is equivalent to the Petrick function known in switching theory. In disjunction form they are the same since both contain representatives for all the IDF's of the function. 8U 6. DERIVATION OF ALL IRREDUNDANT DISJUNCTIVE FORMS FOR AN INCOMPLETELY SPECIFIED FUNCTION Next, we will discuss the derivation of all irredundant disjunc- tive forms (iDF's) of an incompletely specified function f. Suppose a dis- junctive form ¥ for f is given as Y = (A. v- A_ n/ . . . n/ A^ ) s/ (k_ B n v . . . n/ k B ) 1 d til s s where A^ . . . , A t and B^ . . . , B g are products of literals, and k , . . . , k are constant coefficients which can be arbitrarily set to or 1, representing "don't care conditions of f " : In association with f we define the following two functions b(f) and B(f): (1) Lower bound of f , b(f),is obtained by setting all k , . . . , k ' J- s to 0. (2) Upper bound of f , B(f),is obtained by setting all k , . . . , k X s to 1. Any completely specified function g(f) such that b(f)£ g(f)c B(f) expresses f (note that g(f) can also be b(f) or B(f) as a special case). We are interested in deriving a g(f ) which has the most compact expression, in other words, the expression with a minimum number of terms as the primary criterion and with a minimum number of literals, as the secondary criterion, corresponding to the minimal disjunctive forms of a completely specified fun- ction which have been discussed. At first thought, an IDF of f (from which minimal disjunctive forms are to be found) could be defined simply as a dis- 85 junctive form of g(f ) such that deletion of any term invalidates the relation b (f ) S g( f ) • Notice that it is not ohvious whether the terms in this disjunc- tive form should he prime implicants of B(f) or should be even prime implicants of g(f). But we use the following definition for an IDF, since the IDF's in the following definition have the same or a more compact expression than those of g(f) above, as we will show in Lemma 17. Definition 11 An irredundant disjunctive form (IDF) of an incompletely specified function f is defined as a disjunction of some of the prime implicants of B(f), i.e., A., \/ A_ n/ . . . v A , such that deletion of any of A n , A., . . . , A 12 p 12 p invalidates b(f) a A. v A . . . ^ A - 1 2 p Lemma 17 : Let ¥ denote a disjunctive form of g(f) such that the deletion of any term from ¥ invalidates b(f) c ¥ . Then for each such "P there is an IDF of f which has no more terms as the primary criterion and no more literals as the secondary criterion than Y . Proof : Since g(f) c B(f), every term X. in V is an implicant of B(f) . Thus X. subsumes some prime implicant of B(f) . So if each term in ¥ is replaced by the corresponding prime implicant of B(f), we get the disjunction 4" of prime implicants of B(f) in which each term contains no more literals than the corresponding term in ¥ . Thus 4" has no more literals than ¥ . Furthermore we may have a disjunction of fewer prime implicants of B(f) in T than implicants in V . Q.E.D. A prime implicant A. of B(f) is called useless if b(f)-A. is iden- J J tically equal to 0. Otherwise A is called useful . J 86 Lemma 18 : Every IDF of an incompletely specified function f consists of only useful prime implicants of B(f ) . Proof : Suppose A v A v . . . v A is an IDF of f and A is a useless prime implicant of B(f) . Since b(f) • A = 0, A = when b(f) = 1. So we can delete A P without invalidating the implication relation, t>(f) C A v A„ v . .-• , ^A This contradicts the assumption that A n v . . . v A is an IDF of f. 1 P Q.E.D. Notice that useless prime implicants of B(f) are prime implicants produced from don't care conditions only (i.e., from the products with the co- efficients k.'s) in the disjunctive form of B(f) . Algorithm 5 : To derive all IDF's of an incompletely specified function f. (1) Express lower bound b(f) of f with an arbitrary disjunctive form: b(f) = X x v X 2 ^ . . . v X^ where each term is not necessarily a prime implicant of b(f) or B(f) . (The minterms, prime implicants, or other implicants of b(f) may be chosen as the terms in this disjunctive form, but the prime implicants would be appropriate computationally.) This disjunctive form is called the base . (2) Derive all the prime implicants of upper bound B(f) by Algorithm 1 and then delete useless prime implicants. (3) Starting with the useful prime implicants obtained in (2), find the set of irredundant implication relation representatives S by Algorithm 2. The set S obtained generally contains prime implicants and non- prime implicants of f along with their indices. (h) For each X. in b(f), find all the products in S which are subsumed by X. (disregarding the indices), as follows: 87 prime implicants of B(f), A. with index I. where I. consists of a single integer, £, prime implicants of B(f), B. with index J. where J. consists of integers, j , . . . , j and non-prime implicants of B(f), C. with index K. where K. consists of integers, k , . . . , k 1 _L u where X. <=A., X. c b., and X. c c. . Notice that there may be more l—ii—i i—i than one A., B . , or C, and there will always be at least one of A. . ill i (5) For each X., form the disjunctive form in which each term consists of the presence factor corresponding to prime implicant A. or the product of presence factors corresponding to prime implicants that are indexed j , . . . , j or k , . . . , k . In other words, (p, v p ' v . . . ) ss (p. . . . p . v . . . ) v (p . . . p \/ . . . ) . This is called J l J s k l K t the inclusion function for X., Q(X.) . In the following Example 20 (see the first alternative expression of b(f)), acd in b(f) subsumes cdl, cdlU5, and acdi+5. Thus we form a dis- junctive form Q(acd) = p v P^Pe v p U P 5" Delete any terms which subsume others in this disjunctive form. In the above example, p p, p,- is deleted since it subsumes p^ p . (6) Form the product T of all of these inclusion functions corresponding to all the different terms X. in b(f ) . After expanding T into a disjunc- tive form, delete terms which subsume others. The remaining terms re- present all the IDF's of f . Example 20 Given an incompletely specified function f = abc v abd ^ abd v k^b ^ k acd v k acd 88 (1) B(f) and b(f) are derived as follows: b(f) = abc sy abd ^ abd B(f ) = abc \y abd ^ abd vab v acd \^ acd. (2) By Algorithm 1, we find the all prime implicants of B(f) Terms in B(f) Biform variable x R X R- X Products s o ■abo 5 abd, abd ab, acd, acd a bd b cd be bd cd bed > *>od Fc, bed Fed" s l abd, abd, ab, aod ■bod. b ad ad cd cd a c cd ad, cd aod ^ cd S 2 abd, ab, be, ad, cd, cd c b d d bd S 3 abd, ab, be, ad, cd, cd, bd d ab c a c b ' abc ac ■©to-, be The prime implicants of B(f) are ab, be, ad, cd, cd, bd, ac, abc, abd. Since ab • b(f ) = 0, ab is useless. Therefore the useful prime implicants of B(f) are be, ad, cd, cd, bd, ac, abc, abd. (3) • By Algorithm 2, we obtain the following: S = {acl, ad2, abc~3, abdU, bc5, bd6, cd7, cd~8, bcdll+, bcd23, acd36, acdi+5, cdl^5, cd236, adl8, bd58, abd37, abci+8, ac27, bc67) 89 Note that acd.^5 is not a prime implicant but is still retained in S and that it plays an important role in {k)\ (k) abc in b(f) = abc v abd ^ abd subsumes bc 5 and bc67 in S. Consider abd and abd similarly. Then we obtain the following disjunctive forms: Q(abc) = (p v p 6 p^) Q(abd) = (p^ v P 3 P ? ) Q(abd) = (p 2 ss p^g) (5) Form the product T of these disjunctive forms: T = (p^ v P 6 P 7 )(p^ v p Py)(P 2 ^ p^g) = P 2 P^P 5 - P 2 P 3 P 5 P 7 - PAP5P8 - PiP 3 P 5 P 7 P 8 v P 2 P^P 6 P 7 - P 2 P 3 P 6 P 7 - PiPi + P6P 7 p 8^ p i P 3 p 6 P 7 P 8 These terms represent all the IDF's of f. Of course term p p, p represents the minimal disjunctive form. First alternative expression of b(f) : In Step (1), if b(f) is expressed as b(f) = abd s' abd v abc v acd then Steps (k) and (5) become as follows. (p 2 v P-^) f °r abd (p^ v p 3 p 7 ) for abd (p sy PgP„) for abc (P 7 v Pj3P^^Pl + P 5 ) for acd 90 (5)' • T= (p g ^ p 1 P Q )(p lf v P 3 P 7 )(p 5 v P 6 P 7 )(p ? v p^p ) This multiplication leads to the same result as (5). Second alternative expression of b(f) : In Step (l),if b(f) is expressed with minterms, Steps (k) and (5) become as follows. W" Q(abcd) = (p 1 v p^ sy p 2 v Pi Pq) = Pi v p g Q(abcd) = (p 2 v p^g vpg v P2P3P6 v P 2 P 3 ) =P 2 v P8 Q(Sbcd) = (p^ v P 3 P ? v p ? v P-^P^ v PjP^ v p^ 5 )=p 1+ v p 7 Q(abcd) = (p v p^Pg v p^ v PoPrJ =P 3 v p^ Q(abcd) = (p 5 v- p 6 P 7 s/ p 7 n/ P-^P^ v P^P^) =P 5 v p 7 Q(abcd) = (p v p^ n/ p 6 v, p^pg) =p v p 6 (5)" Ta^v P 2 )(p„v P 8 )(P4 ^ Pyl^JV' P U^ Y V^JT P 6^ = (p 2 - P^s^Pu v P 3 p^p7^ P 6 t^HP 7 ^X p 5 ) The last expression is identical to that in T in {k) ' . So we will get the same result as (5). Theorem 12 : Algorithm 5 yields all the IDF's of f, no matter what disjunctive form is used to express b(f) (e.g., with prime implicants or minterms). Proof : First we will show that every disjunctive form? derived by Algorithm 5 is an IDF; i.e., b(f) c V and Y consists of prime implicants of B(f). Through Steps (2) and (3), we obtain all the irredundant implication relations 91 A Q E A : v . . . v A g ( irr ) such that A , . .., A are useful prime implicants of B(f). Then, in Steps 1 o (U) and (5)» starting with b(f ) = x x s, x 2 V ... v X^ we derive all the disjunctions for each X. such that X. cr A. v . . . v A. , 1_ X l, x s and then replace each X. with a disjunction A. v ... v A. which it i 1 l 1 S implies. By Lemma 12, we can see that b(f) c (A v ... v A_ ) v ... v (A v ... ^ -A. ) E! X l 1 S k l k s Thus, since each A. of ¥ is a prime implicant of B(f), ¥ is a disjunctive form of f. Since subsuming representatives are deleted in Step (6), only IDF's are formed. Next, we will show that all IDF's are formed. Assume there exists an IDF ¥ = A„ v . . . v A that Algorithm 5 does £ m produce using b(f ) = X v . . . v X.. Since h(f) £ V £ B(f), X. v X_, \y , . . s/X. C A. \/ ... \/A 12 k — £ m not and X- c A. v . . . n/ A 1 — £ m X 2S\ A X. c A n v ... ^ A K — £ m Eliminating redundancy yields "' ; X' c A' v . .. sy A' (irr) x ■ 1' 1 — £ m X cX';X'cA"v ...v A" (irr) d — d d — £ m \^XiSA< k) ~... -4 k) (irr) 92 (k) So, for each X. there exists a suhset S. of {A„ v . . . ^ A } such that X. ■ i i I m i (k) implies the disjunction of the terms in S. and none can be deleted. Since all such subsets are found in Step 5 and representatives of them are put in (k) the inclusion function for X. , a representative P. of the terms in S must he included in that inclusion function. Therefore, each Q(X. ) in T contains (k) (k) a P. so that all the A'. s corresponding to presence factors in P. are in the IDF Y. Thus • - I p w 1=1 1 is an implicant of T, so there exists a disjunctive form of f in which all the A Is are also in ¥. Thus either V is not an IDF, or ¥ is produced by Algorithm J 5. Each case is a contradiction. Q.E.D. . The Petrick function is closely related to the Tison function, as follows. If a minterm expansion is used to represent b(f) in Step (l), it is not necessary to find all the generalized consensus relations. The set of indexed useful prime implicants of the upper bound B(f), instead of the generalized consensus relation representatives, can be used in Step k. This is because if minterm M. <= C(A. , A, , . . . , A. ) where A. , A, , . . . , A. are prime i— J k J, K I implicants, then M. subsumes at least one of A., ..., A . It follows that all i J * terms that do not consist of single factors get deleted in Step (6), as seen in Example 20, second alternative. The resulting Tison function is the same as the Petrick function. Notice also that Algorithm 5 can be used for completely specified functions where b(f) = f = B(f). Using Algorithm 5 instead of Algorithm '3 enables any arbitrary disjunctive form of f = b(f ) to be used for forming inclusion functions. 93 It is also worth pointing out that the theorems about absolutely dispensable and essential prime implicants derived in Chapter 6 do not apply in this chapter since the inclusion functions do not correspond to prime implicants, but implicants of b(f). 9h 7. DERIVATION OF ALL IRREDUNDANT DISJUNCTIVE FORMS FOR A COMPLETELY SPECIFIED MULTIPLE-OUTPUT FUNCTION Now we will discuss the synthesis of a two level network with multiple outputs, using AND gates in the first level and OR gates in the second level (i.e., the output level). A multiple -output function F is a set of functions {f , f ? , ...,f }, all of which depend on the same set of variables. First we consider an example. Suppose F is given as follows. F: f = acd s/ abc v ab v abd v abed f p = acd v bed v abed sy abed v ab (l) f = abc v abc v abc v acd v acd. By finding an irredundant disjunctive form for each f . , we have f = ad \y abed ^ cd ^ ab ^ ac f ? = be v bed v cd ^ ab (2) f = be v cd v ad when we realize F = {f , f p , f_} by a two-level AND-OR network. This representation requires Ik gates, because f and fp have ab in common, But we can represent F = {f , f , f } differently as f_ = ad v abed \/ cd ^ acd ^ abc fp = be v bed \/ acd v abc v acd (3) f~ = bed v ac sy abc \/ acd. 95 In this representation, each f. is not an IDF, but there are many common terms acd, abc, bed, acd in this. Using this representation we can realize F with 12 gates. Therefore it is not appropriate to treat each f. seperately. In Eq(3) acd is not a prime implicant of the function f_ or f p , but acd is a prime implicant of the function f_ • f p , the intersection of f and f ? . In order to obtain common terms in their simplest form, we must consider prime implicants of the intersections of the given functions. Definition 12 Let F = {f , f p , ..., f } be a multiple-output function. When prime implicants of each of the functions f , f_, ..., f , f-,fp> f -| f v ..., f _f , ..., f_f_...f , are formed, all the prime implicants together m-1 m 1 2 m are called multiple -output prime implicants of F . Definition 13 A representation of a multiple -output function F = (f , fp,...,f ) is called an irredundant set of disjunctive forms or irredundant disjunctive form for F (IDF) if each f. is represented by a disjunctive form such that it is not possible to do any of the following without causing the disjunctive form for any f . not to equal f . : (1) Delete any product from any one f.. Even if this product appears in functions other than f . , do nothing about the other functions. (2) Remove any product A. (if A. appears in more than one f . , remove the A. from all these functions) and express each of these functions as disjunctions of the remaining products which appear in the representation for F. 96 (3) Delete any literal which appears in any product. (If this product appears in more than one function, delete the literal from this product in all these functions.) Example 21 Let us consider a multiple -output function F = {f , f , f } which is expressed with multiple -output prime implicants as follows: f = ad v bed sy abc v abd f = ab v acd ^ abd v ac (i+) f„ = acd v abd v cd \/ bd, where ad, bed, abc and abd are prime implicants of f . ab and ac are prime implicants of f p . cd and bd are prime implicants of f~. acd is a prime implicant of f • f . acd is a prime implicant of f . f . abd is a prime implicant of f • f ? * f . First we consider the disjunctive form of f . We can delete abd from f n and the remaining terms still express f , because abd = €(bcd, abc). Since this means the condition (l) of Definition 13 is satisfied, (k) is not an IDF of F. By deleting abd from the disjunctive form of f , we have the new representation of F: f = ad sy bed \y abc f = ab v acd v abd v ac (5) f = acd \/ abd v cd v bd 97 Since ad = acd v acd, we can delete ad from f and still we can express f as a disjunction of the remaining terms using acd in f and acd in f_. Since this satisfies the condition (2) of Definition 13, (5) is not an IDF of F. We thus have f = acd ^ acd v bed v abc f = ab v acd v abd s/ ac (6) f = acd v abd ^ bd v cd. As will be seen later in Lemma 20 , if we find prime implicants of the intersection of two or more functions, it is easy to see whether literals in a term which these functions have in common can be deleted. So let us consider the intersection f p * f_. Obviously f p • f, contains a prime implicant ad. Since abd c ad in the disjunctive forms for f p and fL, we can delete literal b from the product abd which appears in f and f_. This means that the condition (3) of Definition 13 is satis- fied. So (6) is not an IDF of F. When a two level network with AND gates in the first level and OR gates in the second level is synthesized based on an IDF, neither a gate nor a connection can be deleted from the network because no gate is redundant by conditions (l) and (2) of Definition 13 and no connection is redundant by oondition (3). Therefore if we want to derive a two-level AND-OR network with a minimum number of gates as the primary criterion and with a minimum number of connections as the secondary criterion, it will be represented by a certain IDF. 98 Lemma 19 : Let B be an implicant of the intersection f f...,f, of functions f , f_, ..., f. . Then B is an implicant of the intersection f.f •••f» of any subset of f , f , ..., f and each intersection f f ...f. has a prime implicant A such that B cr A (as a special case, B is an implicant of f. and f. has a prime implicant A such that B£ A). Proof : Since B = 1 leads to f . = 1 for 1=1,2,-. ,-.-, k, B is an implicant of any intersection f . * f . ••« f„ of a subset of f . . . . f , . Therefore ID* Ik if B is not a prime implicant of f.f....f-, then there exists a prime implicant A of f.f ....f* such that B c A. l *> Q.E.D. The set of all the prime implicants of f . and those of all the intersections of functions including f . is called the multiple-output prime implicants associated with f . Lemma 20 : Let f be an IDF of a multiple-output function F = {f, , f p , . ..,f } and A be a term present in the disjunctive forms for function f . , f., . . . ,f i 3 " in y . Then the following holds : (a) A is a prime implicant of the intersection f. • f. • ... • f» of these functions. As a special case, if A is present in f. only, A is a prime implicant of f.. (b) The disjunctive form for each f. in *f consists of only multiple- output prime implicants associated with f . such that deletion of any term causes the remainder not to equal f . . Proof : First we will prove part (a). If A is not a prime implicant of f. • f . • ... • f 0> then there l * exists a prime implicant B of f. • f. * ... * f» such that A c B, because 1 j x> 99 f. = A v .... f. = A v .... .... ffl = A >• ... leads to f . • f .••••. 'f* = A v . 1 j I 1 j # and consequently A is an implicant of the intersection f. • f. ••• f g , 1 J Su Since B is an implicant of f . , f., ..., f g by Lemma 19, we can replace i 3 * A by B in the disjunctive forms for f . , f , . .., f g . In other words, we i 3 * can delete some literals in term A in all the disjunctive forms that contain A. This means the condition (3) of Definition 13 is satisfied. Therefore the representation which contains A is not an IDF of F. We thus have proved (a). Next we will prove part (b). By (a) any term A. in f. must be a multiple- output prime implicant. Since A. implies the function f . , A. must be an implicant of f. or an implicant of the intersection of some functions including f . . Therefore f . can be represented as f. = A _ v ... ^ A , where A , ..., A are multiple-output prime implicants associated with f . . l If any A. can be removed from the above equation, then the J condition (l) of Definition 13 is satisfied. This contradicts that T is an IDF of F = (f. , ..., f . , .... f }. 1 l m Therefore no term in the disjunctive form for f. in T can be deleted. Q.E.D. ' Let A n be a prime implicant of the intersection of f. • f. • ••* f„, 1 * i 3 Hi If A appears in all the disjunctive forms for f . , f ., ..., f , then no 1 1 3 a literal can be deleted from A without causing the disjunctive forms for f., f., ..., f g not to equal the original ones, i .1 u 100 Proof: By assumption, f , = A v «... J 1 f i = A 1 v If a literal is deleted from A.. , then we have A.. ' such that A c a • and f . = A_ f v 1 1 In — "-., s/ • • • » This equation means that A. 1 is a implicant of f . • f . ••• f„. 1 i J i> This contradicts that A is a prime implicant of t.f .•••£* because Ac: A' in f . • f . ••• f „, Q.E.D. Algorithm 6 : To derive all the IDF's of a completely specified multiple- output function F = {f n , f , .... f }. 12m (1) Derive the multiple-output prime implicants by Algorithm 1 (i.e., derive all the prime implicants for each of f , ..., f , fjfg. ..., f x - f„). (2) ' For each f . , derive the set of all the generalized consensus relations S(f.) by Algorithm 2, starting with all the multiple-output prime implicants associated with f . . Notice that the initial set S(f. ) of Algorithm 2 has a property somewhat different from the case 101 of a single output function fj i.e., unlike the case of a single function f where Algorithm 2 is started with all the prime implicants of f , Algorithm 2 in this case must be started with all prime implicants of f . , f f , f . f , . . . , f ,f . • .f f . ..f i' l 1' l 2' i 1 i-l i+l m, and consequently there are multiple-output prime implicants which may subsume others in the initial set S of Algorithm 2. (3) For each prime implicant of each f . (not multiple-output prime impli- cants), derive the inclusion function by searching for occurrences of it among the final S(f . ) derived in (2). For each f . , form the product T. of the inclusion functions of the prime implicants of f... Expand this product into the disjunctive form and then delete terms which subsume others. (k) Form product T T ••• T and expand it into the disjunctive form. Delete terms which subsume others. (5)* For each remaining term $ obtained in (U), we must determine how each function is realized, i.e., we must determine every way that function f . , 1=1, ..., m can be formed using the multiple-output prime implicants whose presence factors are in $, since this is not usually unique. We can do this by finding all terms of T. that $ subsumes; i.e., all terms of T. that $ subsumes represent all possible ways. For example, in the following Example 18, the term PkPc-P^Pd P 10 P li+ P 15 P l6 P 17 °" btained in Ste P (*0 subsumes only term P^PeP^P^ * Footnote on the following page. 102 In [5], Tison presents an alternate method for this step. Each presence factor of each T. is indexed with the number i, indicating which T. it appears in. For example if T = AG ^ BG T = BE v< EF we form T- = BC v CD , T i = A i°i v B i G i T 2 = B 2 E 2 v E 2 F 2 T 3 = B 3 C 3 V C 3 D 3 Then ve form T = T-,T ? T = (A^ v B^XBgEg v EgF 2 )(B 3 C 3 v c^) = (A 1 E 2 F 2 G 1- B 12 G 1 E 2 )(B 3 C 3 VC 3 D 3 ) = VsftVA v B i 2 iWi- • In this case, indicies are combined for identical presence factors (e.g., B • B ? =B p ). Indicies are ignored when checking for subsuming terms. The indiciei on the presence factors indicate how the IDF is formed. For A C_ D E F G , the prime implicants corresponding to A and G are used in f , to E and F in f and to C and D in f^. For B C_ E G , the prime implicants correspond- ing to B and G are used in f , to B and E in f p , and to B and C in f p . This method is more cumbersome to implement in a computer program than that in the text. 103 of T x , only term Ps^^^^iY of T 2' but both terms p 6 P 10 P l6 P 17 and P8 p io p i6 P 17 of T V Thus f n is the ^sj^cfci 011 of A ^» A r> A^ and A^-; f„ is the disjunction of An, Lui,, A -i£> an< ^ A _;andf-is either the disjunction of A^, A.,., A n ^ 5 and A n „ or the disjunction of b 10 lb 1( V A io' A l6' and V Corresponding to each possible combination of representations for f , , ..., f , form a disjunctive form for F. 1 m ° (6) For each disjunctive form for F = {f , ..., f } obtained in (5)» check whether each literal in any term can be deleted without caus- ing the resultant expressions not to equal f.'s. We can accomplish this by determining the f.'s that use a term, say A.. If A. is not a prime implicant of the intersection of these functions, then that A can be replaced with a prime implicant of the intersection and the J set of disjunctive forms is not an IDF, using Lemma 21. If no lite- ral can be deleted, that set of disjunctive forms is an IDF for F. If some literals can be deleted, discard that set of disjunctive forms for f.'s. l In this manner all the IDF's for F have been derived. Example 22 Suppose the following multiple-output function F is given. F : f = ad v abed v cd v ab ss ac f« = tc v bed ss cd v ab t = be v cd v ad ioU (l) The multiple -output prime implicants are obtained as follows f : {ab , ac, ad, abed, cd} *1 A 2 A 3 \ A 5 f : {ab, acd, be, bed, cd} *1 A 6 A 7 A 8 A 9 f : {ac, ad, be, cd} A 10 A ll A 12 ^3 f f 12 f f 13 f f 2*3 f f f 12 3 {ab, acd, acd, bed} A l A 6 hk A 15 {abc, acd, abed} A 16 A 6 \ {abc, acd, bed, acd} A l6 A 17 A 8 A 6 {abc, acd} A 16 A 6 (2) Algorithm 2 is applied for the above set of multiple -output prime implicants. For example, for f , S = {ab • 1, ac • 2, ad • 3, abed • h, cd • 5> acd • 6, acd • lU, bed • 15, abc • 16} S^ = {ab • 1, ac • 2, ad • 3, abed • 4, cd • 5» acd • 6, acd • lU, bed • 15, abc • l6, ad • 2 • 6, ad • 5 • 6, abd • 6 • 15, ab • 2 • 16, abd • 5 • 16, abd • 15 • 1-6, abd • ik • l6, ac • 3 • Ik, ac • 5 • 1^, abc • ik • 15, ab • 5 • lU 16, ab • 3 • lU • 16, ab • ik • 15 • 16. } m (3) The following inclusion functions are obtained. 105 For f. w = P x - p 2 p l6 v P 3 P ll+ P l6 v P 5 P 1^ P 16 s w = P 2 - P 3 P lJ+ - P 5 P li+ Ql (A 3 ) = P3 - p 2 P 6 v P 5 P 6 Q X (A U ) ■ V k Q,(A 5 ) = P 5 For f 2 Q 2 (A X ) = Pl v P ? P l6 - P 9 P 15 P l6 ^ p lU p 15 P l6 Q 2 (A 6 ) = p 6 - P1 P 8 - P 8 P 16 Q 2 (A T ) = P? v p 9 p 15 - P!P 15 P 17 v p lU p 15 P 17 Q 2 (Ag) = p 8 W = p 9 v v lk v 17 Forf 3 W = P 10 v P H P 13 " P 8 P 11 P 12 v P ^ P 12 P 13 v P ^ P 8 P 12 q 3 ( Aii ) = Pll - P 10 P 1? - P U P 12 P 17 Q 3 (A 12 ) = p 12 - P 10 P l6 - P u P 13 P l6 Q 3 (A 13 } = p 13 v p 6 p 10 v p 8 p 12 v p 8 p 10 p l6 By expanding T. into the disjunctive form and deleting terms which subsume others, we have the following: T x = ( Pl v p 2 p i6 v P 3 P ll+ P l6 - P 5 P li| P l6 - Pll+Pl 5 Pi6 ) (P 2 <* P 3 P li+ V P 5 P ll+ )(P 3 N/ P^ V P^) P^P 5 = P 1 P 2 P 3 P^P5 - P 2 p 3 p li p 5 p l6 v p i p 3 p ^ P 5 P l^ v p 3 Wl^ p l6 v P 1 P 2 P U P 5 P 6 - P^i^P^ v p A p 5 p 6 p lU ^ W6 p lU p l6' 106 T 2 = ( P;L - p 7 p i6 - P 9 P 15 P l6 - P li ,P 15 P l6 ^P6 - Pi?8 v p 8 p l6 } ( P? v P9 P 15 v P^P-^ - P lJ+ P 15 P 17 ) P 8 (P 9 - P lU P 1? ) = P!P 7 P 8 P 9 - P 7 P 8 P 9 Pi6 v p l p 7 p 8 p H+ p 17 v p 7 P 8 p l4 p l6 p l7 - P 1 P 8 P 9 P 15 - P 8 P 9 P 15 P l6 - PiP8 p iU p l 5 p 17 v p 8 p lU p 15 P l6 p 17 '3 = (p 10 v p ll p 13 v P 8 P 11 P 12 v p l+ p 12 p i3 v p l^ p 8 p 12 ) ( Pll v p 10 p 17 v P i+ P 12 P 17 )(P 12 - P 10 Pi6 v PiiPi 3 p l6 ) (p 13 v P 6 P 10 v P 8 P 12 v p 8 p l0 p l6 ) = p 10 p 12 p 13 P 17 v P 11 P 12 P 13 v p ^ P 12 p 13 P 17 v p 10 p 13 P l6 p 17 v p ll p 13 p l6 v p 6 p l0 P ll p l2 v p 6 p lO p l2 p i 7 v p 6 p lO p i6 p 17 v P 8 P 10 P 12 P 17 v p 8 p ll p l2 - V8 P 12 P 17 v p 8 p l0 p ii p i6 ^ p 8 p lO p i6 p l7 ^ P 6 p l0 p n p i6 (4) Expanding T T T into the disjunctive form and deleting subsuming terms, we have T l T 2 T 3 = p U p 5 p 6 p 7 p 8 p 10 p Hi p l6 p l7 v p 3 p 4 p 5 P 7 P 8 p 10 p l^ p l6 p l7 p l + p 5 p 6 p 8 P lO P l^ P 15 P l6 P 17 v ' * ' (5T others) V • • • • \/ (5) Corresponding to term P^P^PsPjoP^P^P^P^y we hav e the following two sets since the presence factors in this term can be assigned to f , f 2' f 3 in tw0 different ways (see (5) of Algorithm 6): A v A 5 , A 6 , A lk , A ]6 are in f^ < V \k> V A l6' A 17 are in f 2 A 6' A 10> A l6> A 17 are in f 3 107 and V V A 6' A lV A l6 are in f l { A 8' A lV A 15' A l6> A l? are ln f 2 A 8' A 10> A l6' A 17 are in f. (The only difference between these two sets is A^ or Ag in f^) Thus we have the following two sets of equations: r and v ^ f_ = abed v cd v acd v acd v abc f = bed s/ acd v bed v abc \/ acd 2 f = acd \/ ac v abc s/ acd f = abed v cd ^ acd ^ acd v abc f = bed ^ acd v bed \/ abc ss acd f = bed v ac sy abc ^ acd (6) To determine if either of these sets of equations is an IDF, test each term, using Lemma 21. For example, A . is among the disjunctions for f and f , and therefore should be a prime implicant of f • f . For the 1 first set we have: 108 term should "be a prime implicant of is it? 10 L ll* 15 IT f • f 1 3 f • f 1 2 f • f • f 1 2 3 f • f 2 3 yes yes yes yes yes yes no yes yes Since A _ is not a prime implicant of f 2> this is not an IDF. Similarly the second set of equations in (5) is not an IDF either. We can replace A - = bed by A„ = be, which is a prime implicant of f_, thereby forming an IDF. The term p, p p^p p„p p ,p ^p which represents this IDF is among the terms of the disjunctive form of T T T in (k) . Notice, however , that p. p P/-p pop p i p ,-p can also be interpreted two ways, subsuming p U p 5 p 6 p ll; p l6 of V p 7 p 8 p ll* p l6 p l7 ° f V and both p 6 p io p l6 p iT ^ p 8 p io p l6 p lT of T . The set of disjunctive forms using pxp p ,-p of T is an IDF but the set using p Q p n _p n ^p, „ is not, since A Q is a prime implicant of f. • f n o 10 lb If o ± d but not of f . Hence A,- can replace A ft . The seven IDF's can be derived from the following table. 109 IDF representative p 2 p 3 p U P 5 P T P 8 P 9 P 10 P ll P l6 p 2 p I + p 5 p 6 p T P 8 p 9 P lO p ll p l6 p 3 p U P 5 P T P 8 p 10 P lU p l6 p lT p l + p 5 p 6 p T P 8 p lO p lU p l6 p lT P 2 P 3 P 1+ P 5 P T P 8 P 9 P 11 P 13 P l6 P 1 P 2 P 3 P 1+ P 5 P T P 8 P 9 P 11 P 12 P 1 P 3 Pl + P 5 P T P8 p i2 p lli p lT term in T n p 2 p 3 p U p 5 P l6 p 2V 5 P 6 p l6 p 3 p U p 5 p lU p l6 p U p 5 p 6 p lU p l6 p 2 p 3 p U p 5 p l6 p l p 2 p 3 P U P 5 P 1 P 3 P 1| P 5 P 1 1 + term in T, p T p 8 p 9 p l6 p T p 8 p 9 P l6 p T p 8 p lU p l6 p lT p T p 8 p lU p i6 p i7 p T p 8 p 9 p i6 p l P T p 8 P 9 p l p T P 8 p lU p lT term in T, p 8 p i0 p ll p l6 p 6 p l0 p ll p l6 p 8 p l0 p l6 p lT p 6 p lO p l6 p lT p ll p l3 p l6 p 8 p il p l2 p U p 8 p l2 p lT If only the IDF's that have a minimum number of terms as the primary- criterion and a minimum number of literals as the secondary criterion are to be found, Step (6) can be avoided for each set; only these $'s which have the minimal number of p.'s and the minimal number of literals in implicants repre- sented by those p.'s need to be found. No test needs to be made since there exists no other representation with fewer literals or terms, so none can be removed. Theorem 13 : Algorithm 6 derives all the IDF's of a completely specified multiple -output function F = [f. , f ? , ..., f }. Proof : In Step (3) consideration of only the prime implicants instead of multiple -output prime implicants is sufficient for deriving the inclusion functions, because multiple-output prime implicants subsume some prime implicants anyway as shown in Lemma 19. Then when f . is represented by the disjunction of all the prime implicants of f., i.e., 1 1 2 p 110 (note that there is no subsuming relation among A_ , ..., A ), all the possible disjunctive forms for f . are obtained by replacing each prime implicant by the disjunction of each of its generations in all possible ways, by Theorem 8 (strictly speaking, by a theorem which has a statement similar to that of Theorem 8 for a multiple-output function and which can be similarly proved). In this case each disjunctive form consists of multiple-output prime implicants as required by Lemma §0 , since the generations of each prime implicant are expressed with multiple -output prime implicants by Algorithm 2. Thus T. obtained in Step (3) asserts that condition (l) of Definition 13 is not satisfied. By forming product T n T. ... T and deleting subsuming id m terms in its disjunctive form, we can obtain the multiple-output prime implicants which are necessary to represent F. So the product obtained in Step (k) asserts that condition (2) of Definition 13 is not satisfied. Since we check condition (3) of Definition 13 in Step (6), the obtained representations represent all the IDF's of F. In Step (6), representations from which some literals can be deleted can be discarded for the following reason. When some literals can be deleted from a representation, the representations of F obtained by deleting all possible literals are also IDF's of F. But this can be produced by another pro- duct obtained in Step (k) for the following reason. Let A be a product whose literals can be deleted without causing the disjunctive forms for F not to equal to the original ones in Step (6). Ill When each of f . , f., ,,,, f. is expressed with the A. and other functions do not contain the A , A' , the remainder of A after deleting as many literals as possible, is a prime implicant of the intersection f. • f. ••• f fl , by Lemmas 20 and 21. Therefore T., T T id * v y • i include the presence factor corresponding to A ' . Since all the possible representations for F are considered in Step (k) , there must be the representation obtained by replacing A by A ' . (When only one f . is expressed with A^ as a special case, we can similarly prove the property.) Q.E.D. 112 8. DERIVATION OF ALL IRREDUNDANT DISJUNCTIVE FORMS FOR AN INCOMPLETELY SPECIFIED MULTIPLE-OUTPUT FUNCTION Next we will discuss a method to derive all the irredundant disjunctive forms of an incompletely specified multiple -output function. This can be done by modifying Algorithm 6 in accordance with Algorithm 5. In other words, in Algorithm 6 the upper bound B(f . ) of function f . will be used for obtaining the multiple-output prime impli- cants instead of f. , and the lower bound b(f.) will be used for repre- senting each function with multiple-output prime implicants. First we give some definitions. Definition Ik A representation of an incompletely specified multiple -output function F = {f n , f„, .... f } is said to be an irredundant set of disjunctive 12 m ' — — forms, or an irredundant disjunctive form (IDF) for F , if g(f i ) is obtained for each i = 1, 2, ...» m such that b(f. ) Eg(f.) = A. ^ A. ^...^A. ^B(f.) i = l,2,...m (l) v i' BV l' i 1 ip i t i ' ' i and such that it is not possible to do any of the following without invalidating at least some of the implication relations in (l): (1) Delete any product from any one f . . Even if this product appears in functions other than f., do nothing about the other functions. (2) Remove any product A. (if A. appears in more than one f . , remove J J the A. from all these functions) and express each of 113 these functions as disjunctions of the remaining products which appear in the representative for F. (3) Delete any literal which appears in any product. (if this pro- duct appears in more than one function, delete the literal from this product in all these functions.) Let A. be a prime implicant of intersection B(f.) • B(f.) * B(f ). A. is called useless in B(f.) • B(f ) • ... ; B(f ) if A. • b(f ,) for any k = i, j, . . . , £ is identically equal to zero. Otherwise A. is called useful in B(f ) ; B(f ) • ... • B(f ). The set of multiple-output prime implicants which are useful for B(f . ) and also for all the intersections of upper hounds including B(f.) is called the useful multiple-output prime implicants associated with B ( f . ) . In a manner similar to Lemma 17 > we can prove the following. Lemma 22 : Let "P denote a set of disjunctive forms for g(f.) for all i = 1, 2, ..., m such that the deletion of any term invalidates b(f . ) £g(f.). Then for each such ¥ there are irredundant disjunctive forms for F which has no more terms as the primary criterion and no more literals as the secondary criterion than the disjunctive form for each g(f.) in ¥. It is easy to modify Lemma 18 as follows. Lemma 23 : The disjunctive form for each f . in an IDF of an incompletely specified multiple-output function F = {f,f_, ..., f } consists of only useful i d m multiple-output prime implicants associated with B(f.). Now we can get the following Algorithm 7 which is similar to Algorithm 6. It is not difficult to see why Algorithm 7 works, by considering Theorems 12 and 13. * Footnote on the following page, 11U The definition of "usefulness" given by Tison [U] is different from the definition presented here because using Tison' s definition causes some IDF's not to he found. Tison defined a prime implicant A of B(f . ) • B(f.) J -*• J ... B(f„) to he useless if A b^) • h(f ) • h(f £ ) = 0. To show that this leads to a wrong result [ll], consider the function F = (W Then f = ah ^ hcd n/ k ahcd f = ab ^ acd ^ k ahcd h(f ] B(f n h(f, B(f r B(f n = ah v bed = ab v be = ab v bed = ab v ac • b(f 2 ) = • B(f 2 ) = abc where the terms in B(f ), B(f ), and B(f ) • B(f ) are prime implicants of the respective functions. Using Algorithm 7 and the definition of "useless" given in the text, none of the prime implicants of upper bounds are deleted as useless, and an IDF jf = ab -v abc F = ^f = ab v abc can be derived. However, using Tison 's definition of "useless", implicant abc is deleted, so this IDF cannot be derived. 115 Algorithm 7 : To derive all IDF's of an incompletely specified multiple- output function F= {f n , ..., f }. 1 m (1) Derive the upper bound B(f.) and lower "bound b(f.) for each f . . Express b(f.) with an arbitrary disjunctive form. (2) Derive all the multiple-output prime implicants for B(f ), ..., B(f ) by Algorithm 1. (i.e., derive all the prime implicants of every possible intersection of functions B(f ), B(f p ), ..., B(f ), and find the useful prime implicants for each intersection. ) (3) For each B(f.) derive the set S(f.) of all the generalized consensi by Algorithm 2 starting with the useful multiple-output prime implicants associated with B(f.. ) obtained in (2). {k) For each term X in each b(f.), find all the products in S(f . ) that are subsumed by X. in the same way as in Step (k) of J Algorithm 5» (5) For each X. of each b(f.), form the inclusion function as in Step J i (5) of Algorithm 5. Denote the resulting disjunctive form with w- (6) Form the product of the Q.(X.)'s for each i, that is i J T ±- W ' W ••• V\ ) i where k. is the number of X 's contained in b(f.). Expand T. into disjunctive form and delete terms which subsume others. (7) Form the product T T ... T . Expand it into disjunctive form and delete terms which subsume others. (8) Determine all the ways that the functions can be formed from the implicants associated with each term obtained in (7). 116 (9) For each disjunctive form for F obtained in (8), check whether any literal in any term can be deleted without causing the result- ant expressions not to equal the f . 's, by carrying out Step (6) of Algorithm 6 wins the prime implicants of the upper bounds. If some literals can be deleted, discard that set of dis- junctive forms for the f . 's. If no literal can be deleted, that set of disjunctive forms is an IDF for F. In this manner all the IDF's for F have been derived. Example 23 Suppose an incompletely specified multiple-output function F = (f 1? f 2 ) is given: f = ab v ac s/ bed v ad ^ k acd f = abc sy ad ^ abc v bed v k abc v k_abcd (1) The upper and lower bounds are as follows. b(f. ) = ab v ad v bed \/ ac B(f ) = ac v ad v be s/ acd b(f ) = abc vadv abc v bed B(f ) = ab ss ac sy abc \/ cd (2) We have the following useful multiple -output prime implicants B^) : {ab, ac , ad, be, a?d} (by acd • b(f ) = 0) 1 A l A 5 A 7 A 8 A ll B(f 2 ) : {ab, ac , ad, ab'c , cd} (by abc • b(f 2 ) = 0) A 3 A 5 A 6 A 12 A 10 B(f ) -B(f 2 ) : {abd, abd, ac, a^e, a^d, bed} A 2 A k A 5 A 12 A n A 9 117 (3)(M(5) Using Algorithm 2, we have the following inclusion . functions. For b(f ) = ab v ad v ac v bed we obtain the following: Q x (ab) = p x v p 5 p Q v/ p 2 P T v P 5 P 7 P 9 Q 1 (ad) = p ? - P;L P U - p u P 5 Pg Q 1 (ac) = p 5 Q (bcd)= p Q For b(f_) = ad v abc v abc v bed we obtain the following: Q 2 (ad) = p 6 v p 2 p 3 v p 5 P 1() - p 3 p 5 p 9 Q 2 (abc)= p 3 v, P]+ p 6 v/ p 4 p i() Q 2 (abc)= p 5 Q 2 (bHd)= p 1Q (6) Find T and T : T l = Q i^ ab ^ ' Q^**) ' Q-^ac) * Q 1 ('bcd) = (p 1 *• p p g v p 2 p v/ p p p ) (p t - p^pj; v p^p 5 p 8 ) p 5 p 8 = P 5 P T P 8 - P U P 5 Pq T 2 = Q 2 (ad) • Q 2 (abc) • Q 2 (abc) • Q 2 (bcd) = (p g v p 2 p 3 v P 5 P 10 ^ P 3 P 5 P 9 )(P3-PUP 6 -P1 + P 1 0) P5P10 = P 3 P 5 P 10 - P U P 5 P 10 (T) ^ T 2 = (p^pg v Pl| p 5 p 8 )(p 3 p 5 p 10 v P U P 5 P 1Q ) • = *W8 P 10 " P 3 P 5 P T P 8 P 10 ' (8) Corresponding to p^p pgP 10 , A, , A,_ , A must be in f , k 3 5 8 1 A. , A , A must be in f p since the interpretation on where A, , A , An, A belong is unique . 118 Thus we have f = abd \s ac \s be fp = abd v^ ac v^ cd Corresponding to p p p p Q p 10 , A_j A , A Q must be in f_ 5 7 J- A_, A_, A._ must be in f 3 5 10 2 since the interpretation is unique. Thus we have f = ac v ad v be f = ab v ac v cd (1) (2) (9) For Equations (l), A, and A,, are prime implicants of B(f ) • B(f ) , Ao is a prime implicant of B(f ), and A is a prime implicant of B(f ). Thus no literal can be deleted from Equation (l) so it is an IDF. Similarly, no literal can be deleted from Equations (2), so this is also an IDF. 119 REFERENCES (1) Ghazala, M. J., "Irredundant disjunctive and conjunctive forms of a Boolean function," IBM Journal of Research and Development, April 1957, PP. 171-176. (2) Mott, T. H. , Jr., "Determination of irredundant normal forms of a truth function by iterated consensus of the prime implicants ," IRE TEC, June i960, pp. 2^5-252. (3) Chang, D. M. Y. and T. H. Mott, Jr., "Computing irredundant normal forms from abbreviated presence functions," IEEE TEC, June I965 , pp. 335-3^2. (k) Tison, P., "Generalization of consensus theory and application to the minimization of Boolean functions," IEEE TEC, August 1967, pp. kk6-h56. (5) Tison, P., "Theorie de Consensus," Dissertation, University of Grenoble, France, 19^5. (6) Cutler, R. B. . and S. Muroga, "Absolutely dispensable prime implicants," to appear as a report. (7) Cutler, R. B. and S. Muroga, "Useless prime implicants of incompletely specified multiple-output switching function," to appear as a report. (8) Cutler, R. B. , "Program manual for the programs ILLOD-MINSUM-TX, ILLOD-MINSUM-TXM, ILLOD-MINSUM-TB , and ILLOD-MINSUM-TPIIDF to derive minimal sums or irredundant disjunctive forms for switching functions," to appear as a report. (9) Cutler, B. R. , "MINSUM: A Library of subroutines for finding irredundant disjunctive forms or minimal sums for switching functions - program manual," to appear as a report. (10) Cutler, R. B. , "MINSUM: A Library of subroutines for finding irredund- dant disjunctive forms or minimal sums for switching functions - sub- routine descriptions," to appear as a report. (11) Cutler, R. B. and S. Muroga, "Comments on generalization of consensus theory and application to the minimization of Boolean functions," IEEE Transactions on Computers , July 1979, pp. 5^2-5^3. 120 SUMMARY OF NOTATIONS e (irr) Ij I-|j i' ^ » **' x , x, , x, , a , b , c , A, B, C, A. , B. , . . S, G, S., G^ k) , { } v, r, i, j, K, 1, 2, 3, . b(f), B(f) g(f) p i p (k) i Q(A.) ; , Qj(A.) logically equivalent implies identical disjunction (logical sum) conjunction (logical product) ratio, residue consensus is contained in irredundantly single-output switching function multiple-output switching function literals implicants, product terms sets disjunctive form indices lower and upper bound realization of f presence factor for A. generation factor of A. inclusion function for A. i T, T, Tison function IDF representative 121 INDEX TO THEOREMS, LEMMAS, ALGORITHMS, COROLLARIES, AND EXAMPLES Number Page on which to find i Definition i Theorem i Lemma i Algorithm i Corollary i example i 1 2 8 5 30 50 3 2 2 11 7 1+2 68 7 3 3 15 13 63 70 11 1+ 5 20 Ik 79 78 12 5 6 kl 19 86 78 18 6 6 h9 35 100 21 7 6 53 38 115 27 8 18 58 1+0 31 9 73 66 k6 31+ 10 lh 73 hi 38 11 85 77 hi 39 12 95 90 55 1+1+ 13 95 109 56 52 Ik 112 56 59 15 57 60 16 75 65 IT 85 68 18 86 79 19 98 80 20 98 87 21 99 96 22 113 103 23 113 116 122 APPENDIX IMPLEMENTATION OF TISON'S ALGORITHMS Computer programs which implement Tison's algorithms have "been written and included in the MINSUM system in subroutines DFTOPI, PINDEX, IFA, PFEXP, PFEXPM, AND PIIDF. Some program manuals describing the use of the MINSUM system are listed in the references. The subroutines in- corporate algorithms for multiple-output incompletely specified functions but have special provisions for single-output or completely specified functions. This appendix discusses the algorithms. The sequence DFTOPI, PINDEX, IFA, PFEXPM corresponds to Algorithm 7. 123 Subroutine DFTOPI For single-output functions, this subroutine implements Algorithm 1 for finding prime implicants. For multiple-output functions, this implements Steps (l) and (2) of Algoritms 6 and 7. For in- completely specified functions, this subroutine also finds the useful prime implicants. Let b(f.) and B(f.) for i = 1, . . . , m be the lower and upper bounds for an m-output switching function in disjunctive form. (if there is just one output then i = 1. If the function is completely specified then b(f.) = B(f.) for i = 1, . . . , m. ) For each intersection of upper bounds I = B(f. ) • B(f ) ••• B(f ), the product is expanded into disjunctive form. Then j k x. Algorithm 1 is applied to find the prime implicants. If the function is incompletely specified, then useless ones are removed. (For a prime implicant A, if A • b(f ) = for any h = j, k, ..., i then A is useless in the inter- section.) Thus, DFTOPI forms lists of the useful prime implicants of inter- sections of upper bounds. Subroutine PINDEX To enable easy processing of the indices used in representing generalized consensus relations, presence factors are used for indexing instead of integers. This also enables direct con- version of generalized consensus relation representatives into inclusion functions. The sole purpose of this subroutine is to assign presence factors ( p-indices) to the prime implicants. For multiple-output func- tions, when one prime implicant occurs in more than one intersection, it is assigned the same index. 12U Subroutine IFA This subroutine uses Algorithm 2 to derive gen- eralized consensus relations and then converts them to inclusion functions. First, a base is formed for each f . . By default, it consists of all the prime implicants of b(f. ). Then, for each i, all the indexed use- ful prime implicants associated with f . are collected, and Algorithm 2 is applied to form the set of generalized consensus relation representatives. Finally, these are compared to the terms in the base for f . , and inclusion functions are formed. Subroutine PFEXP This subroutine simply multiplies together the inclusion functions to derive the Tison function in disjunctive form, and determine an IDF with a minimal number of prime implicants primarily and a minimal number of literals secondarily. For multiple-output func- tions, each disjunctive form for an output f. is constructed as the disjunc- tion of all of those prime implicants which are associated with f . . Thus in the result, some terms may be redundant in the expressions for the f.'s, but no term is redundant in all of them. Subroutine PFEXPM This subroutine is an extension of PFEXP especially for multiple-output functions. After the Tison function T is formed and the minimal number M of the number of prime implicants in an IDF is known, an IDF with M prime implicants which has secondarily the minimal sum of the number of literals and the total number of terms is sought. This is done by finding minimal realizations for each of the f.'s for every term of T which has M literals. The procedure described in Step (5) of Algorithm 6 is used to do this. 125 Subroutine PIIDF A veil-known procedure for finding an IDF is by starting with the complete sum and eliminating redundant prime impli-r cants, one-by-one, by comparing them with the remaining ones. This includes the test of whether X^ c X n v x^ v . . . v X 0-12 p holds , in other words , whether X, X„ y = v v, V — 1-_ x o x o "• x o holds In this subroutine, Algorithm 1 is used for this test. If X l X 2 X — V — — v . . . V x o x o x o is equal to 1, then X Q £ X 1 v X g v ... v X p . This subroutine uses this procedure repeatedly for multiple- output functions to derive an IDF. BLIOGRAPHIC DATA EET 1. Report No. UIUCDCS-R-79-993 Title and Subtitle {POSITION OF TISON'S METHOD TO DERIVE ALL PRIME IMPLICANTS ¥D ALL IRREDUNDANT DISJUNCTIVE FORMS FOR A GIVEN SWITCHING JNCTION 3. Recipient's Accession No. 5. Report Date October 11, 1979 Author(s) R. B. Cutler, K. Kinoshita, S. Muroga 8. Performing Organization Rept. No - UIUCDCS-R-79-993 Performing Organization Name and Address jpartment of Computer Science liversity of Illinois :bana, Illinois 61801 10. Project/Task/Work Unit No. 11. Contract /Grant No. MCS77-09744 and MCS77-09744 A01 Sponsoring Organization Name and Address itional Science Foundation J00 G. Street, N.W. ishington, D.C. 13. Type of Report & Period Covered Technical 14. Supplementary Notes Abstracts Tison's algebraic approach for minimization of switching functions is examined, ese functions may be completely specified or incompletely specified or single- tput or multiple-output. Corrections and extensions to some of the theory are so included. (Key Words and Document Analysis. 17a. Descriptors Boolean minimization, covering problem, logic design, minimal sum, lime implicants, minimal networks, AND gates, OR gates. J Identifi iers/Open-Ended Terms generalized consensus, presence function, inclusion functions • COSATI Fie Id /Group !J. vailability Statement Release unlimited 19. Security Class (This Report) UNCLASSIFIED 20. Security Class (This Page UNCLASSIFIED 21. No. of Pages 129 22. Price It NT1S-35 ( 10-70) USCOMM-DC 40329-P71 MAY 2 3 AUG 2 9 13