Boolean Methods in Operations Research and Related Areas
In classical analysis, there is a vast difference between the class of problems that may be handled by means of the methods of calculus and the class of problems requiring combinatorial techniques. With the advent of the digital computer, the distinction
- PDF / 1,141,301 Bytes
- 14 Pages / 439 x 666 pts Page_size
- 33 Downloads / 153 Views
288
XIV. MinimizatIOn Problems in Automata Theory
The expression (2) of a given function I is not unique; for instance, the function (5) 10 = x y U Y Z U IE Y Z may also be written in the forms
yz U
(5')
10 = x
(5/1)
lo=xzuxyuxz,
X
YZU
X
YZU
X Y Z u IE Y z,
(5/1') lo=xyuz, etc. An elementary conjunction c, appearing in a clisjunctive expression (2) of a Boolean function I is called an implicant of I. An equivalent definition is the following: the conjunction (3) is an implicant of the function I if !(XI, ... , xp) = 1 for all (Xl, ... , Xp) E which satisfy X'1 = ex'1' ••• , x'plt) = ex'p(,)' If (3) is an implicant of and the deletion
Be
t
of any letter x> [j = 1, ... , p(i)] transforms (3) into a conjunction J which is no longer an implicant of I, we say that (3) is a prime implicant of the function I. For instance, all elementary conjunctions appearing in formulas (5)-(5/1) are implicants of the function 10; the conjunctions x y and z are prime implicants. Now the problem is to choose, among the various disjunctive forms to which a Boolean funetion I may be brought, the minimal one(s), i.e. that (those) for which the total number of occurrences of the variables Xl, ... , xp is minimal. From the practical point of view, this problem corresponds to that of minimizing the number of contacts of a switching circuit. It is well-known* that a minimal clisjunctive form of a Boolean function I is made up of prime implicants, so that the above minimization problem is to be solved in two steps: 1) Determination of the prime implicants. 2) Determination of a minimal clisjunctive form made up of prime implicants. There are numerous methods for solving the above problems 1) and 2); this situation is due to the fact that, for large values of the number n of variables, the computations are cumbersome, even when u':ling an electronic computer. We shall give below a pseudo-Boolean approach to step 2). Several authors (see 1. B. PYNE and E. J. MCCLUSKEY JR. [1], T. L. MA"STROVA [1], M. A. BREUER [1], P. L. HAMMER, I. ROSENBERG
* See any standard textbook on switching algebra, for instance those quoted in BiblIography B.
§ 1. ~Iinimization of Normal Forms of Boolean Functions
289
and S. RUDEANU [2]) have observed that problem 2) may be formulated as one of bivalent linear programming*, as follows: Let
t=
(6)
01 v
... V
am
be the disjunctive canonical form of the given function t; this means that {ai' ... , alii} = a is the set of those complete elementary conjunctions Xi' ... x? which are implicants of t, i.e. (0(1, ... , O(p) = 1 (see Chapter I, § 2). Let {PI, ... , P,,} = P be the set of all prime implicants of the function t; this set was determined at step 1). Each prime implicant P J is a disjunction of 2p - P (J) conjunctions from the set 0, p (j) being the number of variables which occur in P j :
t
(j
1, ... , n).
=
We say that a conjunction 0, E a is covered by P J ' if 0, appears in the right-hand side of (7. i). We say that a subset p* ~ P covers the set 0, if every conjunction 0, E a is cove
Data Loading...
