The Shortest Disjunctive Normal Forms of Boolean Functions by Reducing the Number of Arguments by Ho Sen Yung B. Sc., University of British Columbia, 2000 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF Master of Science in THE FACULTY OF GRADUATE STUDIES (Department of Computer Science) We accept this thesis as conforming to the required standard The University of British Columbia April 2002 © Ho Sen Yung, 2002 In p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t of the requirements f o r an advanced degree at the U n i v e r s i t y of B r i t i s h Columbia, I agree that the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r reference and study. I f u r t h e r agree that permission f o r extensive copying of t h i s t h e s i s f o r s c h o l a r l y purposes may be granted by the head of my department or by h i s or her r e p r e s e n t a t i v e s . I t i s understood that copying or p u b l i c a t i o n of t h i s t h e s i s f o r f i n a n c i a l gain s h a l l not be allowed without my w r i t t e n permission. Department of Computer Science The U n i v e r s i t y of B r i t i s h Columbia Vancouver, Canada Date A p r i l 23. 2002 Abst rac t Denoting the length of a shortest disjunctive normal form of a Boolean function / by £{f), this thesis provides a way to express £(f) in terms of £(g) for some Boolean function g with no more arguments than / and with the same number of zeros as / . This method is useful for finding the shortest disjunctive normal forms of Boolean functions / with few zeros. It also gives explicitly the values of 1(f) for / with three or fewer zeros, and some bounds for £(f) for a certain class of Boolean functions / . For n much larger than k, the zeros of a Boolean function f oi n arguments with k zeros have the property that for some large subsets P = {11,12, • • • ,id} of {1,2,. . . , n} and 1 < c < d, all k zeros s satisfy Si1 = S j 2 = • • • = Sic = Sic+1 = Sic+2 = • • • = Sj^. Thus, one may consider all dimensions in each P as a single dimension and construct a corresponding Boolean function g with fewer arguments. Abstract Contents 1 Introduction 2 Reductions 3 Complete and Irreducible Sets of Zeros 4 Conclusion Bibliography Contents ii iii 1 7 21 24 26 in Chapter 1 Introduction A Boolean function of n arguments is a map B™ —> B, where B = {0,1} and n £ Z + . A disjunctive normal form, also called a sum of products, of a Boolean function is a representation of the function as a disjunction of conjunctions of literals, each of which is an argument or the complement of an argument. We define the length of a disjunctive normal form to be the number of conjunctions in it and denote the minimum of the lengths of all disjunctive normal forms of a Boolean function / by £(f), also called the length of the Boolean function f. We regard each conjunction as corresponding to a subcube (in the domain B™ of the Boolean function) where the Boolean function assumes the value 1. So, we also define £(0) — 0 and = 1. A zero of a Boolean function / is a point x 6 B" such that f(x) = 0. It is easy to find the shortest disjunctive normal forms of Boolean functions with few nonzeros. For Boolean functions with about the same numbers of zeros and nonzeros, whose nonzeros do not form large subcubes, one may need to resort to the algorithms given by Quine [4, 5] and McCluskey [3]. In the next chapter, we shall present a method for finding "almost the shortest" disjunctive normal forms of Boolean functions whose nonzeros form large subcubes; such functions include 1 those with few zeros. The XOR (exclusive OR) operator, denoted by © and defined as a © b = < 1 ifa^b l a if 6 = 0 0 i£a = b [a if b = 1 will be used to test for equality of Boolean values. In most cases, a will be an argument and b a constant, so that a © b is a literal in a. We call two points in B" adjacent if the Hamming distance between them is one. A Boolean function / : W1 B is uniquely defined by the set 5 = { s G B™ : f(s) = 0 } of zeros, for the obvious reason that f(x) ^ 0 implies f(x) = 1. The char-1 if x G R acteristic function of a set R is charR(x) = < . Then / is the complement 0 if x & R chars of the characteristic function of S. For non-empty R C B 7 1 , let C{R) = {x G B n : Vi <E {1, 2, . . . , n}, 3y G R, xl = yi]. The set C(R) is the unique, smallest subcube containing R. Every subcube containing R contains C(R). Claim 1 Let R C B" be non-empty and a: B n —>• B 6e a conjunction of literals such that for all x £ R, a(x) = 1. T/ten /or a// x G C(i?), a(:r) = 1. Proof: The subcube of nonzeros of a contains R and hence C(R). • 'Let us now find the lengths of Boolean functions with one zero. Cla im 2 For any Boolean function f of n arguments with only one zero, £(f) = n. Proof: Consider a Boolean function char^ with only one zero s e l ™ . DeMorgan's Law gives char^(x) = /\™=1 Xi © Si = \J™=1(xi © Si), so i(char^) < n. On the other hand, s has n adjacent points, and any conjunction that takes on the value 1 at two or more adjacent points of s must also takes on the value 1 at s by Claim 1. Since char^(s) = 0 and char^(x) = 1 for all x ^ s, £{char^) > n. So, we have i(char^) = n. M If the i t h components of all elements of S C B™ are the same (i.e. 3b £ B, Vs £ S, Si = b), then chars can be expressed as a disjunction of a literal in X{ and charx (namely chars{x) = (xi © b) V charr{x\, £2, • • •, ^ i - i , Xi+i, • • •, xn) ), where T C B n _ 1 is the set of points obtained by removing the ith components of the elements in 5. So, <!(chars) is at most 1 + £{charr)- We will concentrate on functions whose zeros have no common component, i.e. C(S) = B™. To justify this, we use the following claim. Claim 3 Let S C B n be non-empty and T C B n _ 1 be the set of points obtained by removing the ith components of the elements in S. If the ith components of all elements of S are b € B, then £(chars) = 1 + l(charT)-Proof: Define x — (x\,X2, • • • , £ i + 2 , • • • ,xn). From the above discussion, we have £(chars) < 1 + £{charx) and chars{x) = (x^ © b) V charrix). Assume (for contra-diction) that £(chars) < 1 + £(charr), i.e. £(chars) <£(charr)- Let chars(x) = 7(£) V [(xi ffi 6) A a(z)] V Xi® b A (3(x) such that £(chars) = £{7) + £(a) + £(/3). 3 For Xi = b, charxix) = (xi © 6) V charr{x) = chars(x) = j(x) V [{xi © b) A a(x)] V x~®b A fi(x) = 7 ( £ ) V / ? ( £ ) . Then£(7) + 1(a) + £{j3) = £(chars) < £(charT) < £{j)+i{f3), so £{a) = 0 and chars(x) j(x) V Xi © b A (3(x) for all i £ l " . But Xi^b implies x & S and 7(2;) = j(x) V © b A /3(s)j = chars(x) = 1, meaning 7 = 1, chars = 1, and 5 = 0. • Claim 3 shows that we can reduce the number of arguments of a Boolean function with the penalty of just one additional conjunction per removed argument, provided that each of the corresponding components is constant over all zeros. Consider a non-empty S = {s 1, s 2 , . . . , sk} C B n . Because the order of the elements in S is important in the following concepts, we view 5 as an ordered, finite sequence of distinct elements. Let M(S) = ^s1 s2 • • • sk^j > where we treat elements in B n as column vectors. An isomorphism from S C B n to S' C B" corresponds to a transformation of M(S) to M(S') consisting of exchanges of 0 and 1 in some rows (a configuration), a permutation of rows (an equivalence map), and/or a permutation of columns. We call S C I " and S" C B n isomorphic and write S = 5' if there is an isomorphism between S and 5'. Code isomorphisms are generally defined as isometries extendible to the whole space (see Constantinesu and Heise [1]). The metric is, of course, the Hamming distance. M(S) is an n x k matrix and may (or may not) contain rows that are the same. We partition the rows in M(S) into m groups (not necessarily maximal) of equal rows and construct a smaller, m x k matrix M by "collapsing" each group into a single row. We refer to the set of dimensions that correspond to the rows in a single group as a zone. The set T = {tl,t2,... ,**} C B m for which M(T) = M is called an (n — m)-step reduction of S if C(S) = Bn. A p-step reduction of S is proper if p > 1. A set 5 with C(S) = W is irreducible if all sets isomorphic to S have no proper reduction; that is, every two rows in M(S) are distinct and are not the complements of each other. Denoting the origin by O, for k > 2, we call a set S complete if { (s2 © sj, sf © s j , . . . , sk © s)) : i G {1,2,... , n} } U {O} = l ' 1 " 1 (or equivalents if { (sj, sj,..., sk), (s\, If,..., ~s$) : i G {1, 2, . . . , n} } U {O, 0} = Mk). We make a simple observation that for any non-negative integers p and q, a {p + step reduction of 5 is equivalent to a p-step reduction of a g-step reduction of S; we refer to this property as the step-additivity of reduction. Since the complement in each literal in a disjunctive normal form is optional, for non-empty S = 5", £(chars) = £(chars>)- Given any x € W, {s © x : s G 5} is isomorphic to S, where the XOR operator © on W1 is taken component-wise. By choosing x G S, we can obtain a set isomorphic to S that contains the origin O. For the remainder of the thesis, we consider, without the loss of generality, only those non-empty sets S = { s1 = O, s2,..., sk } C W with C(S) = B". Since s 1 = O, the definition of irreducibility for S becomes the rows of M(S) being distinct; and since C(S) = Mn, the definition of completeness for S becomes { (s2, s?, . . . , sk) : ,G{l,2,...,n}} = B f c " 1 \ { 0 } . 5 Example 1 M(S) (o 0 1 l \ 0 1 0 0 0 1 0 0 0 0 1 1 0 1 0 0 \ 0 1 1 0 / M(T) (o 1 0 o\ 0 0 1 1 0 1 1 0 \0 1 0 OJ Zones Pi = {2,5} P 2 = {1,4} ^3 = {6} PA = {3} T is a 2-step reduction of S. The first and the last rows of M(T) are the same, so T is not irreducible and the zones P i and P4 are not unique. • Example 2 For any non-empty S C B™ w i t h C(S) = B n , S is an improper reduction of 5 w i t h zones Pj = {j}- D Example 3 M(S) /o 1 1 o\ 0 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 \ 0 1 0 1/ M ( T ) /o 1 1 o\ 0 0 0 1 \0 1 0 1/ Zones Pi = {1,2,3} P 2 = {4} P 3 = {5,6,7} T is a 4-step irreducible reduction of 5. Therefore, the zones are unique and maxi -mal . • 6 C h a p t e r 2 Reductions We start by defining a notation for the number of pairs of adjacent points (between which the Hamming distance is one) in a subset of B n . Definition 1 The adjacency number A(S) of S C f is the number of unordered pairs of adjacent points in S. The equality/inequality of this number of a set and that of its reduction characterizes the relationship between the shortest disjunctive normal forms of the corresponding Boolean functions. Equality of components in each zone is the defin-ing characteristics of reductions. Thus char^Q is the foundation of our discussion and is studied first. Lemma 4 For {0,0} C B n , £ ( c / i a r { 0 ^ } ) = n - A({0,0}). Proof: First, we note that char^0 qj{x) = (xn Ax~i) V y^Zi^i ^xi+i)- To see this, think of each conjunction (in a disjunctive normal form of char<Q q-,) being 0 as a constraint 7 for x £ {O, O}. Since X{ A Xj = 0 <=> Xi < Xj, we have n-l (xn A xi) V \J (xi A xTpi) = 0 z n < xi < a;2 < • • • < xn i=i <£==> xi = x 2 = • • • = xn x £ {0,0}. For n > 2, A({0, O}) = 0 and £(char^Q QJ) < n. Since n > 2, each of O and O has n adjacent points not in {O, O}. Applying the same argument used to prove Claim 2, we have £(char^0 q^) > n. For n = l , A({0,0}) = 1. char^0 qj(x) = x\ A x\ = 0, and £(c / iar | 0 Qj) = 0 = n - 4 ( { 0 , 0 } ) . • As we will see, char^QQ^ is so fundamental that it has some very simple properties. In fact, its shortest disjunctive normal forms are comparable to directed Hamiltonian cycles in graph theory, and its disjunctive normal forms to bidirection-ally connected multigraphs. Proposition 5 (The Uniqueness of the Shortest DNF of char^0Q^) Let Sn denote the (symmetric) group of permutations on {1,2,... ,n}. Let { ctk : B n —)• B | k £ {1, 2,... , n} } be a set of n conjunctions of literals. If n > 2 and char^Q = VJt=i ak, then for some a £ Sn, { ak(x) : k 6 {1,2,. . . , n} } = { xa(n) A x ^ , xa{i) A x a { i + 1 ) : i £ {1,2, . . . , n - 1} }. Proof: For j £ {1,2, . . . , n}, let ej £ B" such that ejj = 1 and Vi + j, 4 = 0. Since n > 2, by Lemma 4, £(char^QQj) = n so Vfc=i afc * s a shortest disjunctive 8 normal form of char^QQ^ and none of the a^'s is identically zero. By previ-ous arguments (n adjacent nonzeros and Claim 1), \/k E {1,2, . . . , n } , 3 unique i,j € {1,2,... , n}, ak{e%) — a(ei) — 1 because el and e-? are respectively adjacent to O and O. Moreover, ak(x) must depend on both X{ and Xj\ otherwise, 0 = char{Q^(0) > ak(0) = ak(el) = 1 or 0 = char{0Q}(0) > ak(0) = ak(ei) = 1. So, ak(x) — Xi Axj A0(x), where x is x with the ith and the jth components removed and 0 is a conjunction of literals. We also know that i ^ j for i = j =^ ak(x) < Xi A Xj = 0. To see that 0 = 1, substitute e1 and e?' into a; and get 0(0) = 1 A 0 A 0(0) = a^e*) = 1 and 0(0) = 1 A O A 0 ( O ) = a f c (^) = 1. Since 0 is a conjunction of literals and 0(0) = 0(0) = 1, by Claim 1,0 = 1. We have established that otk(x) = XikAxJk~, where ik ^ jk and { i k : k 6 {1,2,... , n} } {ifc : G {1) 2,..., n} } = {1,2,. . . , n}. Let t E Sn such that r ( ^ ) = j ' ^ . It is obvious that r partitions {1,2, . . . , n} into equivalence classes Pp (the orbits of {1,2, . . . , n} under the action of (T)) such that i ' ~ j' <^ => 3r € Z , Tr(i') = j1, the |r|-time composition t o • • • or if r > 0 the |r|-time composition r _ 1 o • • • o r _ 1 if r < 0 • the identity 1 £ S„ if r = 0 Using the equivalence ak(x) = Xi A xj = 0 •<=>• Xi < rc ,^ we immediately see that Vfc=i ctk{x) = \/1kl-i{xik A xT(ikf) = 0 if and only if for each p, X{ is constant over where t t = < i G Pp. In order for char^QQ^ = V ^ i 0 ^ ' there must be exactly one equivalence class Pp = { 1 , 2 , . . . ,n} (and the order |r | of r is n). Therefore, {rr(l) : r G { 1 , 2 , . . . , n } } = { 1 , 2 , . . . , n} and ctk{x) = xik A x r ( i f c ) . We can define cr G Sn by CT(T-) = r r ( l ) . The conclusion follows because ak(x) = xik A ^ ( u ) = x<r(<T-l(ik)) A ^ ( l + o - i • The following lemma gives an obvious upper bound. Finikov [2] used similar ideas to give an upper bound for the maximum of the minimum numbers of literals in logical formulas for Boolean functions with a fixed number of nonzeros. L e m m a 6 Let T C B m be a reduction of S C B n. Then £{chars) <n + £{charT). Proof: Let S = {s1,s2,...,sk} a n d T = {t1 ,t2,... ,tk}. The n components of the points in S are partitioned into m zones, which are in bijec-tive correspondence with the m components of the points in T. Let { P i , P 2 , . . . , P m } be the partition of { 1 , 2 , . . . , n) into m zones such that V u e {l , 2 , . . . , f c } , V j G {\,2,...,m}y%ePj,sV = tui. Let neqj(x) be the Boolean function obtained by applying char^Q to x's compo-nents in the zone Pj; i.e. for Pj = {i\,i2, • • • >*|P,|} a n d {0,0} C B ^ ' l , neqj(x) = char^0Qj (xix,Xi2,... ,x^Pl), so l(neqj) < \Pj\ by Lemma 4. Then by picking a representative from each zone, i.e. kj G Pj, we have m chars(x) = charT{xkl,xk2, • •. ,xkm) V \ / neq^x) ( 2 . 1 ) J=I and £(chars) < n + £(charx). B 1 0 The following corollary will be used to prove Proposition 9. Corollary 7 Let T C I " - 1 be a reduction ofSCW1. If A(T) > A(S), then £(chars) = 2 + £(charT). Proof-Let Pi,P2,... ,Pn-i be the n — 1 zones as defined in Lemma 6. Without the loss of generality, let P\ = {1,2} and Pj = {j + 1} for j ^ 1. By Lemma 4, for j > 1, the neqj in equation (2.1) are identically zero, and £{neq{) — \P\\ = 2. So, £{chars) < 2 + £(charT). For x G B " , let x = ( £ 3 , X 4 , . . . , x n ) . We refer to the part excluding the literals in xi and £ 2 , of each conjunction in chars{x) as a(x). Since there is a pair of adjacent points in T whose corresponding points in S are not adjacent, let y G B n ~ 2 such that {(0, y), (l,y)} C T. Since chars(0,0, y) = chars(l,l,y) = 0, by Claim 1, conjunctions taking on the value 1 at (0,1, y) must be in the form X2 A x T A a(x), and those taking on the value 1 at (1,0, y) must be in the form x\ A x~2 A a(x). However, chars(0,1, y) = c/mrs(l, 0, y) = 1 so every disjunctive normal form of chars(x) contains one conjunction in the form xi Ax2 Aa(x) and another in the form x^ Ax\ Aa{x). We may as well extend these two conjunctions to x\ Ax~2 and X2AX1, or simply neqi(x). This gives chars{x) — 7(2;) V neqx{x) and £{chars) = 2 + ^(7) for some Boolean function 7. Since charT{xo,x) = charS{XQ,XQ,X) = ~/(xo,xo,x) V neql(xo,XQ,X) = J(XO,XQ,X), £(charT) < £{j)- We have £(chars) — 2 + ^(7) > 2 + £{charT). U A result better than the one given in Lemma 6 can be obtained for adjacency-preserving reductions. 11 Proposition 8 LetTC B m be a reduction ofSCW. If A(T) = A(S), then £{chars) < n - m + £(charT). Proof: Let S = {s\s2,...,sk} andT = {t\t2,... ,tk}. First, note that A(T) — A(S) is equivalent to saying that su and sv are adjacent whenever tu and tv are adjacent ({su,sv} C S, {tu,tv} C T). This is because a reduction does not increase the Hamming distance between any two points. We use the zones Pj's as defined in Lemma 6 and let pj = mm Pj and qd = max Pj. Without the loss of generality, assume that the zones do not interleave, i.e. Pj = \pj, q-) D Z. We use the disjunctive normal form (xqj A Xp~) V \/^Lp^(xi A x~i+i) f ° r neqj(x) in equation (2.1). We remove the conjunction xQj Ax^~ from each of neg '^s and change the literals in charx to the literals in the removed conjunctions as follows, so that the modified version of charx will do the jobs of both charx and the m removed conjunctions. Let g: B 2 m —> B such that charx(x) = g(xi,x~i,X2,x~2,... ,xm,xm), £(charx) = £(g), and a disjunctive normal form of g contains no complement. The existence of such a g is obvious. Then g is monotone. We replace charx(xkx,Xk2,... ,Xkm) in equation (2.1) with g(xqi,x^,xq2,x^,... ,xqm,xPm). If xqj < xPj for some j, the remainder of neqj(x) will be 1 as it is 0 if and only if xPj < x P j + \ < ... < xqj, which contradicts xQj < xPj. Thus, we only need to consider the case where xq. > xPj for all j; and there is no need to consider the case where xqj = xPj for all j because all removed conjunctions are zero in this case. 12 Therefore, in order to show that g(xqi,xPl,xq2,xP2,... ,xqm,xPrn) does the job of xq. A Xp~, it suffices to show that if xqj > xPJo for some jo and xqj > xPj for all j, then g{xqi, xpi, xq2, xP2,..., xqm, £p m ) = 1. If xq.Q > xPJQ for one jo and r c 9 j = xPj for all j ^ jo, then 0%o,^~) = (1,1) and by the monotonicity of g, g(xqi, xpi,xq2,xP2,..., xqm, xPm) > g(xqi, xqi, xq2, xq2,...,xqm, xqm) = charT(xqi,xq2,...,xqm). Similarly, g(xqi, xPl, xq2, x P 2 , x q m , xPrn) > char j - { x P i , x P 2 , ... ,xPm). Assume (for contradiction) that g(xqi,xPl,xq2,xP2,...,xqm,xPm) = 0. Then charT(xqi,xq2,... ,xqm) = charT(xPl,xP2,. •. ,xPm) = 0. The adjacent points (xqi, xq2,... , xqm) and (xPl, xP2,..., xPm) are in T with xQjo > x P j q . By hypothesis, the corresponding points su and sv in S are adjacent, and by the definition of zones, Vi G Pj0isi = xqj0 > xpj0 = si- This means that |Pj 0 | is the Hamming distance between su and sv, which are adjacent, so \Pj0\ — 1 and qj0 = pj0, contradicting XqJQ > XpJQ . By the monotonicity of g, if xqj > x P j q for some jo and xQj > xPj for all j, then g(xqi, x^, xq2, x^,..., xqm, Xp~^) = 1. This concludes the proof. • We now define the notion of embedded disjunctive normal forms to more precisely and easily describe our results. Definition 2 Let { ak: W -> B | k G {1, 2,. . . , c} } and { r3k: W1 ->• B | k G {1,2,... ,d}} be two sequences of conjunctions of literals for some positive integers c > d. The disjunctive normal form Vfc=i Pk is embedded in the disjunctive normal 13 form Vfc=i (*k if • Vfc=l Ph < Vfc=l ak a n d • 3 infective map f>: {1,2,... ,d} —¥ {1, 2,. . . ,c}, V/c G {1,2,... ,d}, a^k^ < From Definition 2, we may replace a^k)s m Vfc=i afc with Bks without changing the length of the disjunctive normal form or the Boolean function it repre-sents. For conjunctions a, 8: B n —>• B of literals that are not identically zero, a < 8 if and only if the set of literals in 8 is a subset of the set of literals in a. Definition 3 The disjunctive normal forms 8\, 82, . •., fid are disjointly embedded in a disjunctive normal form a if the disjunction Vfe=i Pk * s embedded in a. By step-additivity of reduction, given a reduction T C B m of 5 C B", we may consider only one zone at a time. To do this, we introduce intermediate reduc-tions where all but one of the zones are singleton sets. The proof of the following proposition shows that in this case, if A(T) > ^4(5), then a disjunctive normal form of neqj0 for which Pj0 is not a singleton set, must be embedded in each disjunctive normal form of char$-Proposition 9 Let T C B m be a reduction of S C B n in which Pj0 is the only non-singleton zone. Let {ak: W -> B | k E {1,2,... , c} } and {Bk: W -> B | k E {1,2,... ,d}} be two sequences of conjunctions of literals for some non-negative integers c and d such that the set of literals contained in each (3k is minimal subject to 1. chars = V L i a * v V L i & / 2. e(chars) = c + d; 14 3. Vfc € {1, 2 , . . . , c}, afc ^ neQj0; and 4. VA; 6 {1,2,... ,d}, A < neg j 0. / M ( T ) > A(S), i/ien 1. d — \Pj0 \ =71 — 771 + 1, 5. neq30 = \ldk=lBk, 3. charT{x) = Vfc=i w/iere Xj = rcj /or i £ Pj, and 4- £{chars) = d + £(charr) = n - m + 1 + £(charr)-Proof: Without the loss of generality, let Pj = {j} for j < m and P m = {m, m + 1,..., n}. Let Qj = Pj = {j} for j < m and {Qm,<3m+i} ^ 0 be a partition of P m . Let U C B m + 1 be the reduction of 5 with zones Qu Q2,..., QTO+i- Then T C B m is a reduction of U C B m + 1 , which is a reduction of S C B". (If n = m +1, then f7 =" 5.) Since <5m and Q m +i are from the same zone P m and other zones Qj (j < rn) are singleton sets, A(U) = A(S) giving A(T) > A(U). From the proof of Corollary 7, every disjunctive normal form of charu(x) contains a conjunction with the liter-als xm and xm+i and another conjunction with the literals xm+i and x~^. With charu(x) = chars(x) where x\ = Xj for i £ Qj, this means that every disjunc-tive normal form of chars(x) contains a conjunction with the literals X{0 and x~T and another conjunction with the literals x^ and x~T where {«o>4} — Q™ an<^ {i'0,h} Q Qm+i for any partition {Qm,Qm+i} of P m . Fix a disjunctive normal form of chars(x) and consider the directed graph (V,E) with the vertex set V = Pm and the edge set E = : a conjunction in the fixed 15 disjunctive normal form of char${x) contains the literals Xi and XjT}. Then every bipartition {Qm,Qm+i} $ 0 of V = Pm is bidirectionally connected. This means that the graph is bidirectionally connected and contains a directed Hamiltonian closed walk. By the minimality of /Vs , Pk(x) = Xi AxjT for some {i,i'} C P m . This is due to the fact that f3k < ne<lj Pk(x) = XiAxjj A^{x) where x is obtained by removing the 2th and the z / t h components oix and the fact that if chars(x) = S(x)V(xi Axj/Aj(x)), then S(x) V (xi A Xj/ A 7(2:)) = chars(x) = char${x) V (XJ A #y) = 8(x) V (xi Ax]* A 7(x)) V (XJ A ^7) = <5(:r) V (xi A x~jf). Applying the equivalence X{ A x^ = 0 •<=>• Xi < xy for in the Hamiltonian closed walk gives neqm = Vfc=i A:- By Lemma 4 and the minimum length of the disjunctive normal form (l(chars) = c + d), d = \Pm\ = n — m + 1. For the remaining conclusions, simply express charT in terms of chars- charr(x) — chars(x) = VSUi^fc^) v neam(x) = \l°k=\ak{x)^ where Xi = Xj for i 6 P/. So, l(charx) < c and (.{chars) = c + d > ((charx) + d, but from equation (2.1), e(chars) < £{charT) + d. • In the above proof, of course, one might look at any section of chars identified by a pair of adjacent points in T with corresponding points in S non-adjacent (as identified by y in Corollary 7) to see that neqm is embedded. 16 Example 4 Consider the following irreducible reduction T C I 5 of S C B 1 1 . M{S) / 0 1 0 1 l \ 0 1 0 1 1 0 1 0 1 1 0 0 1 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 \0 0 0 0 1/ M(T) Zones / 0 1 0 1 l \ 0 0 1 0 1 0 0 0 1 0 0 0 0 1 1 \ 0 0 0 0 1/ Pi , = {1,2,3} P 2 = {4,5} Ps = {6, 7} P 4 = {8,9,10} Pb = {11} Let g: B 7 -» B such that charr(x) — g(xi,X2,X3,X3,X4,xZ,X5), ((charx) = ((g), and a disjunctive normal form of g(x\,X2,xz,xy,x±,xy,x§) contains none of the literals xs, xy, x~i, and x~^. We introduce an intermediate reduction U\. / 0 0 0 M(S) 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 M(m) 1\ 1 1 1 1 0 0 1 1 1 7 , M(T) (o 1 0 1 l\ 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 v° 0 0 0 9 , (0 1 0 1 1\ 0 0 1 0 1 0 0 0 1 0 0 0 0 1 1 \o 0 0 0 V \0 0 0 0 1/ 17 Since A(T) = 2 = A(Ui), by Proposition 8, charuiix) = g(xi,X2,x^,X3,x7,X5,xs)y \J (xt A xi+i), i6{3,5,6} 2 so chars{x) = charu1(xi,x^,x^,XT,xs,xg,xio,xii) V \J neq^x) 3 = 1 2 = g(xi,x^X7,xE,xio,x^,xn) V \f (xiAxi^) V \f neq^x) ie{6,8,9} 3=1 We now look at two other intermediate reductions U2 and U3. M(U2) M(S) M(U3) /o 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1\ 1 1 0 0 1 1 1 /o \0 0 0 0 1/ 0 0 0 1 1 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1\ 1 1 1 1 0 0 1 1 1 /o 0 0 > 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 A 1 1 1 0 0 1 1 1 \0 0 0 0 1/ \0 0 0 0 1J The first two columns of M(U2) are adjacent but those of M(S) are not. The first and the third columns of M{U$) are adjacent but those of M(S) are not. Therefore, A(U2) > A(S) < A(U3) and hence, by Proposition 9, a shortest disjunctive normal form of neq1 V neq2 is embedded in every shortest disjunctive normal form of chars-• We now present an application of reduction. Proposition 10 Let S C W with \S\ = 3. Then £(chars) = n + 1 - A(S). 18 Proof: By Claim 3, assume that C{S) = W1 and O £ S. Let T = {t1 = 0,t2,t3} C B m be an irreducible reduction of S = {s1 = O, s2, s 3}. The matrix t2 i 3 ^ has only two non-isomorphic forms: fo 0 l\ and A) 0 1^ V° 1 V 0 1 1 V° 1 <V For the first form, there are two zones (m=2) and £{charx) = 1. The points tl and t2 are adjacent with different second components, and t2 and t3 are adjacent with different first components. Thus, if A(S) = 0, we can apply Proposition 9 to both zones and get £(chars) = n + £{charx) = n + l = n + l — A(S). If A(S) = 1, then one zone is a singleton set and the other is not, and we can apply Proposition 9 to the non-singleton zone and get £(chars) = n — 1 + £{charT) = n — n + 1 — A(S). If A(S) = 2, then S = T and so n = 2, £(chars) = £{charT) = 1 = n + 1 - A(5). For the second form, m = 3, £(charT) = 4 = m + 1, and A(5) < A(T) = 0 so A(S) = A(T). Using Proposition 8, £{chars) < n-m + £(charT) = n - 3 + 4 = n + 1. For the reverse inequality, we note that A(S) = 0, i.e. each zero of chars has n adjacent nonzeros. By previous arguments, £(chars) > n. If £(chars) = n, then for each zero of chars, each conjunction in a shortest disjunctive normal form of chars must take on the value 1 at a point adjacent to that zero. Let {Pi, P2, P 3 } be the partition of {1,2,. . . , n) into the three zones. Define (f>: B 3 —> B" by f>{x)i = Xj for i £ Pj; so f>{tu) = su and chars 0 f> = charx- Since chars(<f>{0,0,1)) = c/iorr(0,0,1) = 1, let a: B" —>• B be a conjunction in a dis-junctive normal form of chars with a(<f>(0,0,1)) = 1. With a((f>(0,0,1)) = 1 and 19 a((j)(0,1,1)) = 0, we know that a(x) must contain the literal xj^ for some i 2 G P 2 . With a((j)(0,0,1)) = 1 and a(</>(0,0,0)) = 0, we know that a(x) must contain the literal X{3 for some 23 G -P3. However, a(x) = 1 ==> A Xi3 = 1 (rr i 2,x l 3) = (0,1) [ and (s?2,s?a) = (1,0) ] ==> x and s 3 are not adjacent. So, there is a conjunction in every disjunctive normal form of chars that takes on the value 0 at every points adjacent to s3. This means that l(chars) > n + 1. • Definition 4 Let S C B 7 1 6e non-empty. The set DO(S) of adjacency-occupied dimensions of 5 is 730(5) = {« G {1,2, ...,n} : 3{s u,s , ;} C 5, sf ^ SV and s u and sv are adjacent }. XTie set DF(S) — {1,2,... ,n} \ DO(S) is called the set of adjacency-free dimensions of S. We summarize the upper bounds from our propositions. Proposition 11 Let T C I ™ be a reduction of S C B" . T/ien £{char^) < \DF{S)\ - \DF{T)\ + £(cha7^). Proof: The conclusion of Proposition 8 is l(chars) < \DF(S)\ - \DF(T) \ + £(charT). The conclusion of Proposition 9 is £{chars) = \DF(S)\ - \DF(T)\ + £(charT). If we consider one zone at a time, either Proposition 8 or Proposition 9 is applicable because A(T) > A{S). • 20 Chapter 3 Complete and Irreducible Sets of Zeros Recall that for S = {s1 = 0,s2,..., sk} C B" with C(S) = B n , S is complete if { (sf, sf,..., sk) : % G {1, 2,. . . , n} } = B f c _ 1 \ {O}; and 5 is irreducible if the rows of M(S) are distinct. Completeness is defined only for sets with cardinalities at least two. The set {O, 0} C B™ is the only subset of B™ containing the origin, contained in no subcube other than B", and with cardinality two. If S C B" is complete with \S\ > 3, then A(S) = 0. To see this, note that the Hamming distance between the origin and each non-origin point in S is at least half of the cardinality of B ' s l _ 1 , and that by exchanging 0 and 1 in some components of all elements in S, we can obtain an isomorphic set S' with any point in S corresponding to the origin in S'. By the definitions of completeness and irreducibility, for complete and irre-ducible S C B n , n = 2 l 5 l _ 1 — 1. Moreover, for any positive integer k, all complete and irreducible 5 with |5| = k are isomorphic, and the Hamming distance between 21 every two points in S is 2k 2. Proposition 12 If S — {s1 = O, s2,..., sk} C B n is complete and irreducible with k = \S\> 3, i/ien £{chars~) < 1 + 3(2A ;-1 - k). Proof: From above, n = 2k~l - 1. Consider A; > 4. Let V C B n _ 1 be the set ob-tained by removing sk from S and removing the io t h components of all points in 5, where s"Q = 0 for all u ^ k; this is possible because S is complete. De-fine x = {xi,x2,...,Xi0-i,Xi0+i,xio+2,...,xn), and let W = {sk} C B " _ 1 . Then chars(x) = (xj^ A c/iary(x)) V ( X J 0 A charw{x))-The set V C B n _ 1 = B 2 ( 2 f e _ 2 _ 1 ) is complete and contains k — 1 > 3 points. Let T C B m be an irreducible reduction of V with common components removed. Then T is also complete with k — 1 points. Hence m = 2k~2 - 1 and A(V) < A(T) = 0. By Claim 3 and Proposition 8, l(charv) < n — 1 — m + (.{charx) = 2k~2 — 1 + £(charr)-The set W C B n _ 1 is a singleton set. By Claim 2, £{charw) = n - l = 2{2k~2 - 1). Therefore, £(chars) < £{charw) + £{charv) < Z(2k~2 - 1) + £{charT) where T is complete and irreducible with 1 point fewer than S. For complete and irreducible R with 3 points, one easily sees that £(charR) = 4; the second non-isomorphic form in the proof of Proposition 10 is complete and irreducible. The sequence {ak}k>3 defined by a 3 = 4 and ak = 3{2k-2 - 1) + a f c_i is {1 + 3(2k~1 - k)}k>3. • With Lemma 4 and Proposition 10, we now consider complete and irreducible sets of at least 4 zeros. We can view the method used in the proof of Proposition 12 as bipartitioning the set of zeros. Representing the successive bipartitions as a binary tree, we see that the method in the above proof has a very unbalanced binary tree. 22 By using balanced bipartitioning, we get a better result. Proposition 13 If S C Mn is complete and irreducible with \S\ = 2r for some integer r>2, then £{chaT~s) < 2 - 3 • 2r~x + 2T + £ p = 3 2 r ~ P + 2 P _ 1 . Proof: Since S is complete, let io G {1,2,... ,n} such that 2~ s^es sio = ^ = 2 r ~ 1 . Define x = (xi,x2, • • • ,xio-i,xio+i,xio+2, • • • ,xn). Let V = {s : s G 5, s;0 = 0} and W = {s: s G S, Si0 = 1}. Then char${x) = (xi0 A c/tary(x)) V (xi0 A c/iorM/(x)). Let W 9 O be isomorphic to W. Both F and W are complete and each contains 2 r _ 1 points. Using arguments similar to those in the above proof, by Claim 3 and Propositions 8 and 9, for R G {V, W'}, £(char^) < {22r~l - 1 - 1) - (2 2 r~ 1~ 1 - 1) + l(charT) if |T| > 3 L(charT) = \(22''-2r ' ) - l + L{charT), where L(charT) = ^ 1 if |T| = 2 v. 1 1 and T is complete and irreducible with 2r~l points. The reason for the special treatment for \T\ = 2 is that |T| = 2 <^=> T = B 1 and that ^ (B 1 ) = 1 > 0. Proposition 9 and Lemma 4 require that L(char^i) = 1 + ((char^i) = 1. We have L(chars) = t(chars) < l(charv) + l(charw) — l(charv) + ((chary/1) < 2T - 2 2 r _ 1 - 2 + 2L{c~ha7^). The sequence {6 r} r>i defined by 6X = 1 and br — 2T - 2T~l - 2 + 2br-\ is {2 -2 r _ 1 + E p = 2 2 r - p (2 2 P - 2 2 P _ 1 )},.>!. The subsequence {br}r>2 is {2 - 3 • 2r~l + 22" + E ; = 3 2 r- p + 2 P"}r>2. • 23 C h a p t e r 4 Conclusion We have shown how to find a disjunctive normal form of a Boolean function / by finding a shortest disjunctive normal form of another Boolean function g such that the set of zeros of g is a reduction of the set of zeros of / . In the concrete cases we have investigated, namely Boolean functions with three or fewer zeros, the disjunctive normal form of / constructed in this way is the shortest. We have also provided some elementary upper bounds for the lengths of the shortest disjunctive normal forms of Boolean functions with complete and irreducible sets of zeros. The missing part that would enable us to know for certain that the disjunc-tive normal forms constructed in this way are the shortest is the equality version of Proposition 8. Intuitively, like removing common components, adjacency-preserving reductions retain all subcube-topological properties, except the decrease in the num-ber of dimensions. Thus we propose the following conjecture. Conjecture 1 Let T C W71 be a reduction of non-empty S C B™. Then t(chaJ^) = \DF(S)\ - \DF(T)\ + £(c~ha~r~^). In fact, Claim 2, Lemma 4, and Proposition 10 are specializations of this 24 conjecture. This is because \DO(S)\ = A(S) for \S\ < 3, as three points cannot form subcubes of dimensions higher than one. With this conjecture, it is perceivable that for an irreducible reduction T of S, the shortest disjunctive normal forms of neqfs with Pfs non-singleton and j 's adjacency-occupied dimensions of T and the disjunctive normal forms each consist-ing of \Pj\ — 1 conjunctions in a shortest disjunctive normal form of neqj with Pj non-singleton and j an adjacency-free dimension of T must be disjointly embedded in every shortest disjunctive normal form of chars-For non-empty S C Bn, the disjunctive normal forms of chars can be viewed as encodings of \S\ distinct sequences of n Boolean values. Thus, from an information-theoretic point of view, ((chars) should be strictly increasing in the multiset of the rows of M(S) for S with a fixed cardinality. That is, if S C B n and T C B m have the same positive cardinality and the multiset of the rows of M(T) is a submultiset of the multiset of the rows of M(S), then ((chars) — ((charx) > n — m. (This requires proof.) Not only does this imply the equality version of Proposition 8, it also gives a nontrivial lower bound for ((chars) for complete and irreducible S. The "worst-case" Boolean function 5: B r + 1 ->• B, 8(x) = 0£l11 Xi has 2 r zeros and length ((5) — 1T. The set of zeros of 5 is irreducible for r > 2. Therefore, for r > 2 and a complete and irreducible set S C B22 1 - 1 with cardinality 2 r , ((chars) > ( 2 2 r - i _ i) _ ( r + i) + £(5) = 2 2 ' - 1 + 2 r - r - 2. 25 Bibliography [1] I. Constantinescu and W. Heise. On the concept of code-isomorphy. Journal of Geometry, 57:63-69, 1996. [2] B. I. Finikov. On a family of classes of functions in the logic algebra and their realization in the class of rr-schemes. Dokl. Akad. Nauk SSSR, 115:247-248, 1957. [3] E. J. McCluskey. Minimization of Boolean functions. Bell System Technical Journal, 35:1417-1444, 1956. [4] W. V. Quine. The problem of simplifying truth functions. American Mathemat-ical Monthly, 59:521-531, 1952. [5] W. V. Quine. A way to simplify truth functions. American Mathematical Monthly, 62:627-631, 1955. [6] P. M. Winkler. Isometric embeddings in products of complete graphs. Discrete Applied Mathematics, 7:221-225, 1984. 26
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- The shortest disjunctive normal forms of Boolean functions...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
The shortest disjunctive normal forms of Boolean functions by reducing the number of arguments Yung, Ho Sen 2002
pdf
Page Metadata
Item Metadata
Title | The shortest disjunctive normal forms of Boolean functions by reducing the number of arguments |
Creator |
Yung, Ho Sen |
Date Issued | 2002 |
Description | Denoting the length of a shortest disjunctive normal form of a Boolean function / by l(f), this thesis provides a way to express l(f) in terms of l(g) for some Boolean function g with no more arguments than f and with the same number of zeros as f . This method is useful for finding the shortest disjunctive normal forms of Boolean functions f with few zeros. It also gives explicitly the values of l(f) for f with three or fewer zeros, and some bounds for l(f) for a certain class of Boolean functions f . For n much larger than k, the zeros of a Boolean function f of n arguments with k zeros have the property that for some large subsets P = {i₁,i₂,…,i[sub d]} of {1,2,..., n} and 1 ≤ c ≤ d, all k zeros s satisfy Si₁ = Si₂ = ... = Si[sub c] = Si[sub c]+1 = Si[sub c]+2 = ... = Si[sub d]. Thus, one may consider all dimensions in each P as a single dimension and construct a corresponding Boolean function g with fewer arguments. |
Extent | 1163407 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-08-17 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
IsShownAt | 10.14288/1.0051443 |
URI | http://hdl.handle.net/2429/12280 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2002-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_2002-0299.pdf [ 1.11MB ]
- Metadata
- JSON: 831-1.0051443.json
- JSON-LD: 831-1.0051443-ld.json
- RDF/XML (Pretty): 831-1.0051443-rdf.xml
- RDF/JSON: 831-1.0051443-rdf.json
- Turtle: 831-1.0051443-turtle.txt
- N-Triples: 831-1.0051443-rdf-ntriples.txt
- Original Record: 831-1.0051443-source.json
- Full Text
- 831-1.0051443-fulltext.txt
- Citation
- 831-1.0051443.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051443/manifest