Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

The shortest disjunctive normal forms of Boolean functions by reducing the number of arguments Yung, Ho Sen 2002

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

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

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  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

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>
                        
                    
IIIF logo 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

Comment

Related Items