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 F U L F I L L M E N T OF THE REQUIREMENTS FOR T H E D E G R E E 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 r e q u i r e m e n t s f o r an advanced d e g r e e a t the U n i v e r s i t y of B r i t i s h Columbia, I a g r e e t h a t 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 r e f e r e n c e and s t u d y . I f u r t h e r a g r e e t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g of t h i s t h e s i s f o r s c h o l a r l y p u r p o s e s may be g r a n t e d by the head of my department o r by h i s o r her r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g o r 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 g a i n s h a l l not be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . Department o f Computer The U n i v e r s i t y of B r i t i s h Vancouver, Canada Date April 23. Science Columbia 2002 Abstract 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 Si = S j = • • • = Si = Si = Si = • • • = Sj^. Thus, one may consider all dimensions in each P as a single dimension and construct a corresponding Boolean function g with fewer arguments. 1 c+2 2 c c+1 Contents Abstract ii Contents iii 1 1 Introduction 7 2 Reductions 3 Complete and Irreducible Sets of Zeros 21 4 Conclusion 24 26 Bibliography 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 A zero of a Boolean function / is a point x 6 B" such that f(x) = 1. = 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 1 a ©b=< ifa^b la 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 / : W 1 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 char1 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 , let C{R) = {x G B : Vi <E {1, 2,... , n}, 3y G R, x = 71 n l yi]. The set C(R) is the unique, smallest subcube containing R. Every subcube containing R contains C(R). C l a i m 1 Let R C B" be non-empty and a: B —>• B 6e a conjunction of literals such n 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. C l a i m 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) = /\™ Xi © Si = \J™ (xi =1 =1 © Si), so i(char^) On the other < n. 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) i(char^) = 0 and char^(x) = 1 for all x ^ s, £{char^) > n. So, we have = n. If the i M 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) where T C B n _ 1 = (xi © b) V charr{x\, £2, • • •, ^ i - i , Xi+i, is the set of points obtained by removing the i th the elements in 5. So, <!(chars) is at most 1 + £{charr)- • • •, x ) ), n components of 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 be non-empty and T C B n removing the i th components n _ 1 of the elements in S. elements of S are b € B, then £(chars) be the set of points If the i th obtained by components of all l(charT)- = 1+ Proof: Define x — (x\,X2, • • • , £ i + 2 , • • • ,x ). n £(chars) < 1 + £{charx) and chars{x) diction) that £(chars) < 1 + £(charr), = (x^ © b) From the above discussion, we have V charrix). Assume (for contra- i.e. £(chars) <£(charr)- 7(£) V [(xi ffi 6) A a(z)] V Xi® b A (3(x) such that £(char ) s 3 Let chars(x) = £{7) + £(a) = + £(/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) = (£)V/?(£). 7 T h e n £ ( 7 ) + 1(a) + £{j3) = £(char ) s < £(char ) T < £{j)+i{f3), so £{a) = 0 and char (x) s 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 , s ,..., s } C B . Because the order of the 1 2 k n elements in S is important in the following concepts, we view 5 as an ordered, finite sequence of distinct elements. Let M(S) = ^s 1 s 2 • • • s ^j > where we k treat elements in B as column vectors. An isomorphism from S C B to S' C B" n n 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 isomorphic and n 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 = {t ,t ,... l 2 ,**} C B m for which M(T) = M is called an (n — m)-step reduction of S if C(S) = B . A p-step reduction of S is n 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 { (s © sj, sf © s j , . . . , s © s)) : i G {1,2,... , n} } U {O} = l ' " 2 k equivalents if { (sj, sj,..., s ), (s\, k 1 (or 1 If,..., ~s$) : i G {1, 2,... , n} } U {O, 0} = M ). k 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 W is taken component-wise. By 1 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 = { s = O, s ,..., s } C W with C(S) = B". Since 1 2 k s = O, the definition of irreducibility for S becomes the rows of M(S) being distinct; 1 and since C(S) = M , the definition of completeness for S becomes { (s , s?,..., s ) : n 2 ,G{l,2,...,n}} = B " \ { 0 } . f c 1 5 k Example 1 M(S) (o 0 1 l \ 0 1 0 0 (o 0 0 0 0 0 11 0 1 0 0 1 \0 Pi = {2,5} 1 0 o\ 0 1 0 0 \0 Zones M(T) 11 P = {1,4} 2 1 1 0 ^3 1 0 OJ = {6} PA = {3} 1 0/ T is a 2-step r e d u c t i o n of S. T h e first a n d the last rows of M(T) are the same, so T is not irreducible a n d the zones P i a n d P4 are not unique. • Example 2 For any non-empty S C B™ w i t h C(S) = B , S is a n i m p r o p e r r e d u c t i o n n of 5 w i t h zones Pj = {j}- D Example 3 M(T) Zones /o 1 1 o \ 0 0 0 1 P i = {1,2,3} P = {4} P = {5,6,7} 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 \0 1 0 1/ 2 3 1/ T is a 4-step irreducible reduction of 5. Therefore, the zones are unique a n d m a x i mal. • 6 Chapter 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 defining characteristics of reductions. Thus char^ Q is the foundation of our discussion and is studied first. Lemma 4 For {0,0} C B , £(c/iar ^ ) = n n { 0 } A({0,0}). Proof: First, we note that char^ qj{x) = (x Ax~i) V y^Zi^i 0 n ^ i+i)x To see this, think of each conjunction (in a disjunctive normal form of char< q-,) being 0 as a constraint Q 7 for x £ {O, O}. Since X{ A Xj = 0 <=> Xi < Xj, we have n-l (x A xi) V \J (xi A xTpi) = 0 i=i z < xi < a; < • • • < x n n 2 n <£==> xi = x = • • • = x 2 n 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^ qj(x) = x\ A x\ = 0, and £ ( c / i a r | Q j ) = 0 = 0 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 bidirectionally connected multigraphs. Proposition 5 (The Uniqueness of the Shortest D N F of Let S n char^ Q^) 0 denote the (symmetric) group of permutations on {1,2,... ,n}. Let { ctk : B —)• B | k £ {1, 2,... , n} } be a set of n conjunctions of literals. n If n > 2 and char^ = VJt=i k, then for some a £ S , a Q n { a (x) : k 6 { 1 , 2 , . . . , n} } = { x ( k a n) Ax^, x a{i) Ax a { i + 1 ) : i £ { 1 , 2 , . . . , n - 1} }. Proof: For j £ { 1 , 2 , . . . , n}, let e £ B" such that e = 1 and Vi + j, 4 = 0. j j j Since n > 2, by Lemma 4, £(char^ Qj) Q = n so Vfc=i fc * a 8 sa shortest disjunctive normal form of char^QQ^ and none of the a^'s is identically zero. B y previ- ous arguments (n adjacent nonzeros and Claim 1), \/k E {1,2, . . . , n } , 3 unique i,j € {1,2,... , n}, a {e ) — a(ei) — 1 because e and e-? are respectively adjacent % l k to O and O. Moreover, a (x) must depend on both X{ and Xj\ otherwise, k 0 = char ^(0) > a (0) = a (e ) = 1 or 0 = char Q (0) > a (0) = a (ei) = 1. {Q {0 So, a (x) k k } k l k k — Xi Axj A0(x), where x is x with the i and the j th components removed th and 0 is a conjunction of literals. We also know that i ^ j for i = j =^ a (x) k < Xi A Xj = 0. To see that 0 = 1, substitute e and e?' into a; and get 1 0(0) = 1 A 0 A 0(0) = a^e*) = 1 and 0(0) = 1 A O A 0 ( O ) = a ( ^ ) = 1. fc Since 0 is a conjunction of literals and 0(0) = 0(0) = 1, by Claim 1,0 = 1. We have established that ot (x) = Xi AxJ ~, where i ^ j and {i k {ifc k k k k G {1) 2,..., n} } = {1,2,..., n}. Let t E S : n : k 6 {1,2,... , n} } k such that r ( ^ ) = j ' ^ . obvious that r partitions {1,2, . . . , n } into equivalence classes P p {1,2, . . . , n } under the action of (T)) such that i ' ~ j' the |r|-time composition t o • • • or where t t = < the |r|-time composition r the identity 1 £ S„ Using the equivalence a (x) k = \/ -i{xi 1 l k k o• • • or (the orbits of 3r € Z , T (i') r = j, 1 if r > 0 _ 1 if r < 0 • if r = 0 = Xi A xj = 0 •<=>• Xi < rc^, we immediately see that k Vfc=i ct {x) _ 1 <^=> It is A x (i f) T k = 0 if and only if for each p, X{ is constant over i G Pp. In order for char^QQ^ = V ^ i ^ ' there must be exactly one equivalence 0 class P = { 1 , 2 , . . . ,n} (and the order |r| of r is n). p Therefore, {r (l) : r G { 1 , 2 , . . . , n } } = { 1 , 2 , . . . , n } and ct {x) = x r k We can define cr G S ik A l k ^ A k ( l + o - ). = r ^ ( u ) = <r(<T- (i )) x r(ifc byCT(T-)= r ( l ) . The conclusion follows because a (x) n x A x ik 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 . Then £{char ) <n + n s £{char ). T Proof: Let S = {s ,s ,...,s } 1 2 k a n d T = {t ,t ,... ,t }. 1 2 k The n components of the points in S are partitioned into m zones, which are in bijective 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 = t. u i Let neqj(x) be the Boolean function obtained by applying char^ Q nents in the zone Pj; i.e. for Pj = {i\,i2, • • • >*|P,|} char^ Qj (xi ,Xi ,... 0 x 2 ,x^ ), Pl a n d {0,0} to x's compoC B ^ ' l , neqj(x) = 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) = char {x ,x , T and £(chars) kl • •. ,x ) k2 km < n + £(charx). V \ / neq^x) J=I (2.1) B 10 The following corollary will be used to prove Proposition 9. Corollary 7 If A(T) Let T > A(S), C I"- 1 be a reduction then £(char ) = 2 + s ofSCW . 1 £(char ). T ProofLet Pi,P2,... be the ,P -i n 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 1, the j > £{char ) in x xi G B", and \P\\ — = 2. So, T let £2, £{neq{) £(char ). < 2 + s For in equation (2.1) are identically zero, and neqj x = (£3,X4,...,x ). n of each conjunction in We refer to the part excluding the literals as chars{x) 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 such that {(0, y), (l,y)} C T. Since chars(0,0, y) = chars(l,l,y) = 2 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, contains one conjunction in the form chars(x) x^ Ax\ y) = c/mrs(l, 0, y) = 1 so every disjunctive normal form of Aa{x). or simply This gives for some Boolean function l and another in the form We may as well extend these two conjunctions to neqi(x). neq (xo,XQ,X) xi Ax2 Aa(x) = J(XO,XQ,X), 7. chars{x) Since — 7(2;) charT{xo,x) £(charT) < £{j)- 2 + £{char ). V neq {x) x and x\ Ax~2 We have £(chars) X2AX1, 2+ ^(7) = ~/(xo,xo,x) V £{chars) = charS{XQ,XQ,X) and — = 2 + ^(7) > U T A result better than the one given in Lemma 6 can be obtained for adjacencypreserving reductions. 11 Proposition 8 LetTC B m be a reduction If A(T) = A(S), then £{char ) ofSCW. <n-m + s £(char ). T Proof: Let S = {s\s ,...,s } 2 k andT = {t\t ,... ,t }. 2 k First, note that A(T) — A(S) is equivalent to saying that s and s are adjacent u C S, {t ,t } whenever t and t are adjacent ({s ,s } u v u v u v C T). v 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 q = max Pj. Without d the loss of generality, assume that the zones do not interleave, i.e. Pj = \pj, q-) D Z. We use the disjunctive normal form (x A qj Xp~) V \/^L ^(xi A x~i+i) f ° neqj(x) in r p equation (2.1). We remove the conjunction x Ax^~ from each of neg^'s and change Qj 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,... ,x ,x ), m £(charx) m = £(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 equation (2.1) with g(x ,x^,x ,x^,... qi q2 ,x ,x ). qm Pm charx(xk ,Xk ,... x If x qj remainder of neqj(x) will be 1 as it is 0 if and only if x < x Pj <x Pj P j + ,Xk ) 2 m for some j, the \ < ... < x , qj which contradicts x < x . Thus, we only need to consider the case where x . > x Qj Pj in q Pj for all j; and there is no need to consider the case where x = x for all j because all qj removed conjunctions are zero in this case. 12 Pj Therefore, in order to show that g(x ,x ,x ,x ,... qi Pl q2 x . A Xp~, it suffices to show that if x q >x qj pi If x . > x q Q PJQ q2 PJo qm does the job of Prn for some jo and x >x qj Pj for all j, x , £ p ) = 1. then g{x , x , x , x ,..., qi ,x ,x ) P2 P2 qm for one jo and m rc 9 j = 0% ,^~) = (1,1) for all j ^ jo, then x Pj o and by the monotonicity of g, g(x , x ,x ,x ,..., qi pi q2 x , x ) > g(x , x , x , x ,...,x , P2 qm Pm qi qi = Similarly, g(x , x , x , x qi Pl q2 P , x 2 q m q2 q2 T Prn P i ,x qi P 2 , q2 qm ... ,x ). Pm Assume (for contradiction) that g(x ,x ,x ,x ,...,x ,x ) Then charT(x ,x ,... qi Pl q2 P2 qm ,x ) = charT(x ,x ,. q2 qm Pl = 0. Pm •. ,x ) = 0. The adjacent points P2 Pm (x , x ,... , x ) and (x , x ,..., x ) are in T with x qi q2 qm Pl P2 qm char (x ,x ,...,x ). , x ) > char j - { x qi x ) qm Pm > Qjo x By hypothesis, . P j q the corresponding points s and s in S are adjacent, and by the definition of zones, u Vi G Pj i i s = 0 > qj x 0 = pj x v i- This means that | P j | is the Hamming distance s 0 0 between s and s , which are adjacent, so \Pj \ — 1 and qj = pj , contradicting u v 0 Xq > X JQ pJQ 0 0 . By the monotonicity of g, if x qj >x P j q for some jo and x Qj >x Pj for all j, then g(x , x^, x , x^,..., x , Xp~^) = 1. This concludes the proof. qi q2 • qm We now define the notion of embedded disjunctive normal forms to more precisely and easily describe our results. Definition 2 Let { a : W -> B | k G {1, 2,... , c} } and { r3 : W ->• B | k G 1 k k {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 k a • 3 infective a n d map f>: {1,2,... ,d} —¥ {1, 2,... ,c}, V/c G {1,2,... From Definition 2, we may replace a^k) s ,d}, a^ ^ k < Vfc=i fc with B s without a m k changing the length of the disjunctive normal form or the Boolean function it represents. For conjunctions a, 8: B —>• B of literals that are not identically zero, a < 8 n 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 * embedded in a. s 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 reductions 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 neqj for which Pj is not a singleton set, must be embedded in each disjunctive 0 0 normal form of char$Proposition 9 Let T C B singleton {1,2,... zone. ,d}} Let {a : k m be a reduction of S C B in which Pj is the only nonn 0 W -> B | k E {1,2,... , c} } and {B : k be two sequences of conjunctions W -> B | k E of literals for some non-negative integers c and d such that the set of literals contained in each (3 is minimal k to 1. chars = V L i * V L i & / a 2. e(chars) v = c + d; 14 subject 3. Vfc € {1, 2 , . . . , c}, afc ^ Qj ; ne d an 0 4. VA; 6 {1,2,... ,d}, A < neg . j0 / M ( T ) > A(S), i/ien 1. d \Pj \ — 0 5. neq 30 =71 — 771 + 1, = \l B , d k=l k 3. charT{x) = Vfc=i 4- £{chars) = d + £(charr) w/iere Xj = rcj /or i £ Pj, and = n - m + 1+ £(charr)- Proof: Without the loss of generality, let Pj = {j} for j < m and P = {m, m + 1,..., n}. m Let Qj = Pj = {j} for j < m and {Q ,<3m+i} ^ 0 be a partition of P . Let m U CB m + 1 m be the reduction of 5 with zones Q Q ,..., u reduction of U C B m + 1 Q +i- Then T C B m TO is a , which is a reduction of S C B". (If n = m +1, then f7 =" 5.) Since <5 and Q + i are from the same zone P m 2 m 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 literals x m and x i m+ and another conjunction with the literals x +i and x~^. With charu(x) = chars(x) m where x\ = Xj for i £ Qj, this means that every disjunc- tive normal form of chars(x) contains a conjunction with the literals X{ and x~T 0 and another conjunction with the literals x^ and x~T where {«o>4} — Q™ {i' ,h} Q Qm+i for any partition {Q ,Q i} 0 m m+ ^ an< of P . m Fix a disjunctive normal form of chars(x) and consider the directed graph (V,E) with the vertex set V = P and the edge set E = m 15 : a conjunction in the fixed disjunctive normal form of char${x) contains the literals Xi and XjT}. Then every bipartition {Q ,Qm+i} $ 0 m of V = P m is bidirectionally connected. This means that the graph is bidirectionally connected and contains a directed Hamiltonian closed walk. By the minimality of / V s , Pk(x) = Xi AxjT for some {i,i'} C P . This is due to the m fact that f3k < lj Pk(x) = XiAxjj A^{x) ne< 2 and the z th /th where x is obtained by removing the 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 closed walk gives neq m in the Hamiltonian = Vfc=i A:- By Lemma 4 and the minimum length of the disjunctive normal form (l(chars) = c + d), d = \P \ = n — m + 1. m For the remaining conclusions, simply express charT in terms of chars- charr(x) — chars(x) = l(charx) e(char ) s VSUi^fc^) v m( ) nea x = \l°k=\ k{x)^ a where Xi = Xj for i 6 P/. So, < c and (.{chars) = c + d > ((charx) + d, but from equation (2.1), < £{char ) T + 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 neq is embedded. m 16 Example 4 Consider the following irreducible reduction T C I /0 1 0 1 1 1 Zones M(T) M{S) of S C B . 5 l \ 0 1 0 1 1 0 1 0 1 1 0 0 1 0 1 /0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0 Ps = {6, 7} 0 0 0 1 0 0 0 0 1 1 P 0 0 0 1 1 \0 0 0 0 1 1 0 0 0 1 1 1 0 1 1 0 0 0 0 l \ Pi, = {1,2,3} 1 P 1/ = {4,5} 2 = {8,9,10} 4 Pb = {11} \0 0 0 0 1/ Let g: B 7 -» B such that charr(x) — ((charx) = g(xi,X2,X3,X3,X4,xZ,X5), 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 1\ 0 0 1 0 0 1 1 1 0 0 0 0 1 1 7 , 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1/ \0 M(T) M(m) M(S) (o 1 0 1 l\ 0 0 1 0 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 9 , v° 0 0 0 17 1 ((g), (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 Since A(T) = 2 = A(Ui), by Proposition 8, charuiix) = g(xi,X2,x^,X3,x ,X5,xs)y \J 7 (xt A x ), i+i i6{3,5,6} 2 so chars{x) = charu (xi,x^,x^,XT,xs,xg,xio,xii) V \J 1 neq^x) 3= 1 2 = g(xi,x^X7,xE,xio,x^,x ) \f V n (xiAxi^) V \f ie{6,8,9} neq^x) 3=1 We now look at two other intermediate reductions U2 and U3. M(S) M(U ) 2 /o 0 0 0 0 0 0 0 \0 1 0 0 0 0 0 0 0 0 0 1 1 0 1\ 1 1 0 0 1 1 1 0 0 1/ /o 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 M(U ) 3 0 0 0 1 1\ 1 1 1 0 0 0 0 0 1 0 0 1 1 1 1 > \0 0 0 0 1/ /o 0 0 0 0 0 0 0 1 0 0 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 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 neq V neq is embedded in every shortest disjunctive normal form of chars1 2 • We now present an application of reduction. Proposition 10 Let S C W with \S\ = 3. Then £(char ) s 18 = n + 1 - A(S). Proof: By Claim 3, assume that C{S) = and O £ S. Let T = {t = 0,t ,t } 1 W 1 2 an irreducible reduction of S = {s = O, s , s }. The matrix 1 2 t 3 2 3 CB m be i ^ has only 3 two non-isomorphic forms: A) V° fo 0 1^ 1 and V 0 l\ 0 1 1 V° <V 1 For the first form, there are two zones (m=2) and £{charx) = 1. The points t and l t are adjacent with different second components, and t and t are adjacent with 2 2 3 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) A(S) = 2, then S = T and so n = 2, £(char ) s For the second form, m = 3, £(char ) T A(S) = A(T). = £{char ) T = n — n + 1 — A(S). If = 1 = n + 1 - A(5). = 4 = m + 1, and A(5) < A(T) Using Proposition 8, £{char ) < n-m s = 0 so = n - 3 + 4 = n + 1. + £(char ) T 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>{t ) = s u u 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 G P . 2 2 With a((j)(0,0,1)) = 1 and a(</>(0,0,0)) = 0, we know that a(x) must contain the literal X{ for some 23 G -P3. However, 3 a(x) = 1 ==> A Xi = 1 3 (rr ,x ) = (0,1) i2 l3 [ and (s? ,s? ) = (1,0) ] 2 a ==> x and s are not adjacent. 3 So, there is a conjunction in every disjunctive normal form of chars that takes on the value 0 at every points adjacent to s . This means that l(chars) > n + 1. • 3 Definition 4 Let S C B 71 6e non-empty. The set DO(S) of adjacency-occupied dimensions of 5 is 730(5) = {« G {1,2, ...,n} : 3{s ,s } C 5, sf ^ V and s u ,; u S and s are adjacent }. XTie set DF(S) — {1,2,... ,n} \ DO(S) is called the set of v 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(char ) s conclusion of Proposition 9 is £{char ) s < \DF(S)\ = \DF(S)\ - \DF(T) \ + £(char ). - \DF(T)\ T + £(char ). T The 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 = {s = 0,s ,..., s } C B" with C(S) = B , S is complete if 1 2 k n { (sf, sf,..., s ) : % G {1, 2,... , n} } = B k 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 ' l , and that by exchanging 0 and 1 in some s _ 1 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 irreducible S C B , n = 2 l l n 5 _ 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 2 . k 2 Proposition 12 If S — {s = O, s ,..., s } C B is complete and irreducible with 1 2 n k k = \S\> 3, i/ien £{chars~) < 1 + 3(2 - - k). A; 1 Proof: From above, n = 2 ~ - 1. Consider A; > 4. Let V C B k l tained by removing s from S and removing the i o k th be the set ob- n _ 1 components of all points in 5, where s" = 0 for all u ^ k; this is possible because S is complete. DeQ fine x = {xi,x ,...,Xi -i,Xi i,x 2,...,x ), 2 0 0+ io+ and let W = {s } C B " . Then _ 1 k n A c/iary(x)) V ( X J A charw{x))- chars(x) = (xj^ 0 The set V C B n _ 1 =B ( 2 2fe_2_1 ) is complete and contains k — 1 > 3 points. Let T C B be an irreducible reduction of V with common components removed. Then m T is also complete with k — 1 points. Hence m = 2 ~ - 1 and A(V) < A(T) = 0. By k Claim 3 and Proposition 8, l(charv) < n — 1 The set W C B n _ 1 — 2 m + (.{charx) = 2 ~ — 1 + k is a singleton set. By Claim 2, £{char ) = n - l = 2{2 ~ k w Therefore, £(char ) s < £{char ) < Z(2 ~ + £{char ) w k v 2 £(charr)- 2 - 1) + £{char ) T 2 1). 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 {a }k>3 k defined by a = 4 and a = 3{2 k 3 k 2 - 1) + a _i is {1 + 3(2 ~ - k)} > . k fc 1 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 M is complete and irreducible with \S\ = 2 for some n integer r>2, r +£p then £{chaT~ ) < 2 - 3 • 2 ~ + 2 r x T s 2 ~P+ r = 3 2 P _ 1 . ^ = Proof: Since S is complete, let io G {1,2,... ,n} such that 2~^es io s = s x = (xi,x , • • • ,x -i,x i,x 2, 2 io io+ • • • ,x ). io+ 2 ~ . Define r 1 Let V = {s : s G 5, s; n 0 = 0} and W = {s: s G S, Si = 1}. Then char${x) = (xi A c/tary(x)) V (xi A c/iorM/(x)). 0 0 0 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^) < {2 ~ - 1 - 1) - (2 ~ ~ - 1) + 2r l 2r 1 l(char ) if |T| > 3 1 if |T| = 2 T L(char ) = \(2 ''-2 2 T r ' ) - l + L{char ), T where L(char ) 1 =^ T v. 1 1 and T is complete and irreducible with 2 ~ points. The reason for the special r l treatment for \T\ = 2 is that |T| = 2 <^=> T = B and that ^ ( B ) = 1 > 0. Proposition 9 and Lemma 4 require that L(char^i) = 1 + ((char^i) = 1. We have 1 1 L(chars) = t(chars) < l(charv) + l(charw) — l(charv) + ((chary/ ) 1 < 2 T - 2 2 r _ 1 - 2 + 2L{c~ha7^). The sequence {6 } >i defined by 6 = 1 and b — 2 - 2 ~ - 2 + 2b -\ is {2 T r 2 r _ 1 r + E p = 2 - (2 r p X 2P 2 E; 3 2 r = p+2P -2 2 P _ 1 T r l r )},.>!. The subsequence {b } > is {2 - 3 • 2 ~ + 2 " + r r "}r>2. r l 2 2 • 23 Chapter 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 disjunctive 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 number of dimensions. Thus we propose the following conjecture. Conjecture 1 Let T C W 71 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 consisting 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 charsFor non-empty S C B , the disjunctive normal forms of chars can be n 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 and n T CB 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 "worstcase" Boolean function 5: B ->• B, 8(x) = 0£l Xi has 2 zeros and length r + 1 1 r 1 ((5) — 1 . The set of zeros of 5 is irreducible for r > 2. Therefore, for r > 2 T and a complete and irreducible set S C B ( 2 - i _ i) _ ( r 2 i) + £(5) = 2 ' 2 r + 1 22 1 - 1 + 2 - r - 2. r 25 with cardinality 2 , ((chars) > r 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 Mathematical Monthly, 59:521-531, 1952. [5] W. V . Quine. A way to simplify truth functions. Monthly, 62:627-631, 1955. American Mathematical [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 |
File Format | 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. |
DOI | 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 |
Graduation Date | 2002-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | 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