1 
 
 I 
 
 
 
 < ■ 
 
 : 1 
 
 
 ! 
 
 
 
 
 : 
 
 
 • 
 
 
 
 
 
 | 
 
 
 
 4 | 
 t 1 
 
 • j 
 
 
 .}!iJ 
 
w 
 
 II B URY 
 
 OF THE 
 U N IVERSITY 
 Of ILLI NOIS 
 
 s\o-8a- 
 
 r\o. 2A3- 2A9 
 ceo. 2, 
 
 — ■MWWM —WM i 
 
The person charging this material is re- 
 sponsible for its return on or before the 
 Latest Date stamped below. 
 
 Theft, mutilation, and underlining of books 
 are reasons for disciplinary action and may 
 result in dismissal from the University. 
 
 UNIVERSITY OF ILLINOIS LIBRARY AT URBANA-CHAMPAIGN 
 
 *■*( \ 3 1972 
 
 6EB 1 6 Kecd 
 
 L161— O-1096 
 
''■■■■'■ 
 
 -■■■■■•'■• 
 
3. 2 + 1 
 
 N A TH n 
 
 19C8 
 
 ENUMERATION OF THRESHOLD FUNCTIONS OF EIGHT VARIABLES 
 
 by 
 
 S Muroga 
 
 I. Tsuboi 
 
 C. R. Bauch 
 
 August 2, 1967 
 

Feport No 2U5 
 
 ENUMERATION OF THRESHOLD FUNCTIONS OF EIGHT VARIABLES 
 
 by 
 
 5 Muroga 
 
 T. Tsuboi 
 
 C. R. Baugh 
 
 August 2, I967 
 
 Tepartment of Computer Science 
 University of Illinois 
 T rbana, Illinois 618OI 
 
TAB. I " VENT 3 
 
 N, ............... , 
 
 2. ........... 
 
 E_ AIW EXTREMAL INEQUALIT] 
 
 NAL PROCEDURE ........... 
 
 Zo 3 ........... . 
 
 6, T( MINIMIZE A OLD. . . , 
 
 . . . . . . . . . . . . . . . . < 
 
 Page 
 1 
 8 
 11 
 
 17 
 
 28 
 kQ 
 57 
 
S : . MMaRY 
 
 The number oj shold functions of eight vari&: s counted 
 by ' II, the computer of the University of IHinoii < '■ • s of op 
 
 ghts of majority elements realizing these functions also are investigated, 
 Actually canonical positive self-dual threshold functions of nine variabl 
 are investigated instead of investigating directly 'hre shold functions of 
 eight variables because it is easier to deal with them rhe number and 
 optimum weights of threshold functions of eight variables are easily ot • 
 'ained from these functions of nine variables and their realization. 
 
 First a linear program r o minimize the total input is con- 
 sidered., Canonical pc. dual function? of nine variables are 
 generated by modifying Winder's method ana tested by the simplex method to 
 find whether they are threshold functions or not. The number of canonical 
 positive self-dual threshold functions of exactly nine variables and I 
 number of all threshold func*ions of exactly eight, variables are 1 7 2 ? 9?8 
 and 1.7,1+91+, 930, 604,032, respectively. There is no completely monotonic 
 function of exactly eight variables which is not a threshold function. 
 Unlike the case of threshold functions of seven or fewer variables, there 
 are some threshold functions of exactly eight variables whose extr- 
 optimum weights include fractional numbers, Many other properties of thesi 
 functions are explored. 
 
 Next a linear program to minimize a threshold is red ^he 
 linear program is considerably different from the previous linear program 
 to minintze the weigh' with respect to uniqueness of an cptimum 
 
 solution, The number of threshold functions which have multiple optin 
 solutions is counted. 
 
 1 INTRODUCTION 
 
 is an interesting problem to find how many of Boolean functions 
 
 of n variables are actually threshold functions. Phreshold functions have 
 
 (1) (?) (13) 
 
 been enumerated by a. few authore for n equal to J or fewer ' 
 
 this paper we enumerated all threshold functions of 1 . Lables 
 
 and investigated algebraic proper' ies of these functions a >f optimum 
 
 structures which realize The digital computer of -he 1 y of 
 Illinois, C II was used for this si 
 
E i r st a line ar_ program to minimize_the total input wejgr. r is con- 
 
 Sidered 
 
 Properties Df Dptimum weights of threshold functions of 8 variahl.es 
 which will he defined :r the following are quite different from those of 7 
 or fewer variables. For example, functions of 7 or fewer variables have 
 only integral and unique optimum weights- But some of the functions of 
 
 8 variables have nor integral weights and some others multiple optimum 
 weights . Whether there are completely mo no tonic functions which are not 
 threshold functions for ft variables is an interesting question, because 
 there is none for 7 or fewer variables but there is at leas' one known for 
 
 9 variables, Bu" no s Function was found. 
 
 Next a linear pro gram to minimize thre s hold is considered. This 
 linear program is fairly different from the one to minimize the total in- 
 put weight 
 
 These two linear programs and. their solutions are discussed in 
 this paper, 
 
 To facilitate our discussion, lei: us define Terminology,, 
 
 A threshold fined as a Boolean function 
 
 f (x, , . , o ,x ) for whicl bhere exists a se* of real numbers called weights 
 
 1 n 
 
 w_, w,, . o o ,w su ai 
 
 7 ' n 
 
 f(: 
 
 U) 
 
 lj) ) - 1 if E w. f. U) + w g > 1 
 1 ..11 o o — 
 
 (1.1) 
 
 and 
 
 f(x 2 
 
 ,3) 
 
 >\ - 
 
 
 ' ) ■ ■ n if Z w | 
 
 \ < 
 
 o o - 
 
 (1.2) 
 
 for the j-th set cf variables, 
 
 h - 2x i lf 
 
 (j) .-2x 
 
 U) 
 
 n 
 
 1, (J ■ 1, 2, 
 
 ,2 n ) 
 
 where % is a constant whicr. is identically equal to either of +1 or -1 
 o 
 
 The inequa] i T Les , (1 ,l) and (1 .2) are called a normalized system of in- 
 
 (3) 
 
A Boolean function f is called positive when it has a Boolean 
 expression wii the complement x. for each variable x. If a threshold 
 fur . : ve and dependent on x., then positiveness cf the weight, 
 w. > 0. can be shown. 
 
 Let us formulate -.he following linear programming problem 
 for a positive threshold function of n variables, f(x., . . . ,x ) 
 Minimize the objective function 
 
 w = E w. 
 
 o ■ 
 
 (1.3) 
 
 under the constraints 
 
 w > and w. > (i = 1, 
 
 o — i — 
 
 n 
 
 (J) 
 
 (J) 
 
 Z w. £ u; + w % > 1 for f( Xl u; , 
 1 "i o o — 1 
 
 i=j. 
 
 ,n) 
 
 ,*J J) ) =1 
 
 U.M 
 
 (1.5) 
 
 and 
 
 n 
 
 v. iS ^ + w ? < -1 for f(x-/ J % 
 .,11 o o — 1 ' 
 
 1=1 
 
 ,x ( J } ) =0 
 7 n 
 
 (1.6) 
 
 whe 
 
 L (j) = 2x. 
 
 i i 
 
 (,3) -1 (i = 1, 2, . . . ,n) 
 
 a solution w-, , . „ . ,w and w £ for which the. value of the objective 
 J-' n o o 
 
 function (1.3) is minimum and finite is called an optimu m solut ion, optimum 
 
 wei ghts of f, or an opt imum s t rue t ur e of f. 
 
 n 
 The sum of the absolute values of all weights, i.e. Z , is 
 
 called 3 - a I i r.pu t ^e i gh T . Since w. > for i =0, 1, 2, . „ . ,n, (1=3) 
 is the to r al input weight, 
 
 e minirriza r ion of (1,3) has engineering significance When 
 
 is minimized, the inpu T bolerance and reliability of a majority element are 
 
 . . . (11) 
 maximized. 
 
When a solution (w.. , <, » 
 linear convex sum of any other two solutions, i.e. when there are no two 
 
 ,w , w £ ) cannot be expressed as a 
 n o o 
 
 other solutions, (w ', 
 
 n 
 
 v ' £ ') and (w ", 
 
 . g M) 
 
 such that w. = kw. ' + (1 - k)w. ! ' for i - 1. 2. 
 
 i 
 
 w 6 ■ '— /n '-^ 
 o o 
 
 r and 
 
 kw 'I ' + (l - k) w B, £ where <. k < 1, the solution is called an 
 o o o o 
 
 e xtre me solution. When an optimum solution is an extreme solution, it is 
 
 .(5) 
 
 called an extreme optimum solution. It is Jtnown that if an optimum 
 solution of the linear program, (1.3) r o (1-6), is unique, it is an extreme 
 solution of T he sei cf inequalities, (l.^-) to (1,6), and if not unique, 
 optimum solutions consis: cf extreme optimum solutions and their linear 
 convex sums . 
 
 A Boolean function f is called self-dual when it is identical to 
 
 its dual f (x. , o . . ,x ) = f(x,, . . . >x ), i.e. when f = f holds., 
 1 n 1 n 
 
 (2?) 
 Comparability and monotonicity are defined as follows. As 
 
 two Boolean functions, f (x, , . . 
 
 sume 
 
 ,x n ) and g(x 1 , . 
 
 ,x ) are given . 
 7 n 
 
 If each combination of values of x^ 
 
 ,x which satisfies f = 1 
 
 ' n 
 
 satisfies g = 1 also, it is expressed as 
 
 fu r 
 
 > x n ) 5 g( X T/ • 
 
 ) 
 
 (1.7) 
 
 and f and g are called comparable , In addition, if f = and g = 1 holds 
 similtaneously : 
 is expressed as 
 
 similtaneouelv for a certain corr.bination of values of x, , , . » ,x , it 
 
 i n 
 
 f(x ] _, ,x n ) C g(x., 
 
 ,) 
 
 (1.8) 
 
 If either 
 
 d d 
 f =) f or f c f J 
 
 holds between a function f arc its dual f , f is called dual -comparable . 
 If f => f , f is called a. rca^or^une^lon. and f cf -, a minor function. 
 
 Assign the values, 1 and 0, to an arbitrary set of k variables 
 of a Boolean function f.. Denote bhis assignment with A and it is called 
 
 
a k-asslgnme] ~f k - n, jailed a complete assignment A is 
 
 complement of A. Let f - denote f with "hose chosen k variables assigned 
 
 by A . 
 
 A - A 
 
 01 f A 2f A 
 
 (1.9) 
 
 holds for every possible k-assignmerr. (i.e. for all possible combinations 
 of 1 and C to chosen k variables and for all possible selections of k out 
 of n variables. The value of k is fixed.), f is called k -comparable. , If 
 f is k -comparable, for every k such that 1 < k < m, then f is called Ki- 
 mono toni c , In particular if a function f of n variables is n-monotonic, 
 f is called corople tely mono " o nic . 
 
 Two-monotonici: y is especially importan* Consider * he assignment 
 
 of 1 and to two variables, x. and x., of a Boolean function f. If 
 
 i J 
 
 f(x. - 1, x. - 0) ^ f( x . = 0, x. = 1) 
 i J - l J 
 
 (1.10) 
 
 holds, it is denoted as x. £ x . , In particular, if ^ holds in (l.,10), i T is 
 
 - 1 - d 
 
 denoted as x. > x., and otherwise, as x. ~ x.. When f is a positive threshold 
 function, the following can be shown, Tf x. >- x.. then w. > w. in ev< 
 solution which satisfies (1.1) and (1.2). If x. ~ x., f is symmetric 
 x. and x. and there exists a sel of weights ir. which w. = w., although 
 w. - w. does no: hold ir every solution. 
 
 A function which satisfies 
 
 X l £ x 2 
 
 > x - 
 
 is called can onica l. If we have the set of all canonical pos self 
 
 dual threshold functions of r variables, all nor ons 
 
 of (n ■ 1) variables can be generated by complementing and permu r a'ing 
 variables, and assigning the value 1 or to one of the variables . Therefore 
 in the following, canonical positive self-dual threshold functions of 9 
 variables with 
 
 *! JS *, it 
 
 >* 9 
 
will be considered. This greatly simplified our computational procedure „ 
 
 Boolean fur.c T i 3ns ot saine 3 from a given function f by any of the 
 following three opera one are lefined as-. N^-ej^u i vale nt fr net ions with 
 f: (l) Negation (or corrj - bion) of :r- ~r more variables of f: (2) 
 permutation of variables arc (3) negatior of f, i.e. f. A class of Boolean 
 functions is called ar NPN- class if the class consists of all Boolean 
 functions whicb are. mutually NH - juivaleni Sin Ly a FN- class is 
 defined if onlv the first two operation?., (l) and (2), are used instead 
 
 of the above three, k ;lass of Boole a- bions is called a se_lf-dual^it_y_ 
 
 (15) 
 class if the class consists 01 Boole- Lons (non- self -dual functions 
 
 of exactly n variables and self clual fui exactly (n + l) variables) 
 
 which coincide by the following operations: 
 
 Self -duali zation, i e conversion of a non-self -dual function 
 
 f(x 1 , 
 
 X 
 
 r. 
 
 ) uro a self dual function f (x. 
 
 ,x , x , ) with 
 n n+1 
 
 a new variable x 
 
 
 f \x j9 . 
 
 'n+1 
 
 
 
 
 \ d, 
 
 ,X ) v x , f (x n , 
 n n+1 1 
 
 ,x Q ) (1.11) 
 
 where f is. the dual of f 
 
 (2) Non~ self -duali zat conversion of a self-dual function 
 
 f (x, , . o . ,x - ) in1 non.' self -dual function by assigning 1 or to 
 
 n+j 
 
 x . off 
 n+1 
 
 (3) Negation and permutation of variables (and consequently negation of a 
 function results from the other O] s). 
 
 Canonical posit iv* self -dual threshold functions of exactly n 
 variables may be regarded as representatives of * he. self-duality classes 
 of threshold functions of exactly variables (i.e. nor- self- dual, threshold 
 functions of exactly (n ■ l) variables and self -dual tireshold functions 
 of exactly n variables) . 
 
 Give n r tuples, 
 
 v 
 
 f l' y 
 
 2' 
 
 »y„) 
 
 n 
 
 
and 
 
 Z l' V * ' ' ' Z n' 
 
 v. > z. for i = 1, 
 1 - 
 
 , n, 11 is denoted as 
 
 Y > I 
 
 (1.12) 
 
 and Y is s ai d no : r c " be smal ler rhan Z a In particular, if y. > z. for some 
 
 J <J 
 
 j, (1„12) will tx tten as 
 
 Y > Z 
 
 and Y is s ai d to be gre ater :han Z Consider the sei of 'rue. n- tuples of a 
 positive function f. Its subset, for each n- tuple of which no other smaller 
 
 .pies exist in the set, is called minimal r rue n- tuples of f . Maximal 
 false n - tupl es of f are similarly defined, The minimal true n- tuples and 
 the. maximal false n-tuples of a positive function f together are called 
 the extremal n- tuples, of f „ 
 
 Some, of the inequalities, (1.5) an< i (1-6), characterizing a positive 
 
 threshold function f are redundant, i.e.* satisfied by any solution wb 
 
 certain o'her inequalities are satisfied, Inequalities corresponding to 
 
 minimal true n-tuples of f among -rose of (1.5) are cai tie minimal true 
 
 lyal it if s , Inequalities corresponding to the maximal false n-tuples of 
 
 f among those (1,6) are called the maximal false inequalities . Bo r t sets of 
 
 inequalities a^e call- e xtremal _ine qual j_*. if _s When the extremal 
 
 inequalities are satisfied by a solution (w , w. , . . . ,w ), all the otl 
 
 o 1 n 
 
 inequalities of (1,5) and (1.6) are satisfied. I or^ when feasible 
 solt T ions of (1,5) and (1.6) are sought, searching for only solutions 
 satisfying the extremal inequalities will be. sufficient in order r o ey 
 all solutions 
 
Winder 
 
 (6) 
 
 e basic properties 
 
 : an important property tha^ if the self -dualized 
 
 ft.r.c 4 ion of a giver non-self -dual function f(x. 
 
 ) by (1.11) ii 
 
 + l)/3] -monotonic, whe f x] is the greatest integer which is not 
 greater than x, f is completely monotonia. This can he easily strengthened 
 into the following necessary and sufficient condition, which Winder apparently 
 knew but did no: state This theorem will be useful for finding whether a 
 given threshold function of e rariables is completely monotonic, by examining 
 whether the self -dualized function is [(n + l)/3l -monotonic We will make 
 use of this proper" 
 
 Theorem 2. 1: A non-self -dual function f of n variables is completely 
 monotonic if and or the self-dualized function f by (loll) 
 
 f S x . f vx , f d 
 n+1 n+1 
 
 is [ (n+1 )/ 3] -monotonic . 
 
 (6) 
 Fro of ; Winder sh< Lai the ! (n + l)/3]-nionotonicity of the self- 
 
 dualized function is sufficient for f to be. completely monotonic . 
 
 Therefore lei us show -ha* if f is completely monotonic, the self- 
 dualized function P is [(n + l)/3]-nionotonJ 
 
 Let -A be an assignmenl of 1 and to an arbitrary number of variables 
 
 except x 
 
 n+1 
 
 f f 3 f , wf - 
 
 and then f . => f 
 
 A 
 
 t 8 . = f ft X , V f ? X _ => fr X - v f - X - 
 
 A A r A r.+l - A n+i. A n+1 
 
 -- f- 
 
 Therefore f. and fj are comparable . 
 
 t\ 
 
 Next consider an assignment which includes x 
 
 Let AB be an 
 
 assignment where B is an assignment of 1 to x 
 similar. ) From 
 
 n+1 
 
 n+1 
 : e case of will be 
 
 
f S = f x _ v f d X _ , 
 n+1 n+1 
 
 we have 
 
 S aI =f A andf A§ = f A 
 
 Assume that f. and fr are not comparable. Then there must be C and D, 
 assignments r .o all other variables, such that 
 
 f AC " X > f A0 " ° 
 f AD ' ° • 4 " X 
 
 Rewriting C = EF and D = EF, these become 
 
 f =1 f _ =0 
 AEF ' AEF 
 
 'AEF 
 
 °' f AEF " X 
 
 i is r.c - null because if it is null, the last equality f?.= = 1 will yield 
 f = which contradicts the first of the above four equalities. Frorr 
 
 f AEF = ° and f AEF = Xt We have 
 
 f -- = 1 and f ,- = 0, 
 AE F AFF 
 
 Comparing these with the other two 
 
 f AEF " X and f AEF = °' 
 
 we conclude that f and f=, are not comparable ■. This contradicts I assumption 
 
 ili E 
 
 s s 
 f is completely mono+onic. Therefore f._ and f-r- are comparable. 
 
 r AB AB 
 
 c 
 
 In conclusion, f is completely mono + onic and accordingly 
 i(n + l)/3l-monotonic. QE7 
 
C orollary 2.2: A self-dual function g is; completely monotonic 
 if and only if g is [(n + l)/3]-monotonic. 
 
 Proof If g is. completely monotonie, g is obviously [(n + l)/3] -monotonie. 
 On the contrary, if g is [(n + l)/3j"monotonic, non-self -dualized function 
 is completely monotonie from the Winder's sufficiency proof of Theorem 2.1. 
 Then as seer from the necessity proof of Theorem 2.1, the self-dualized 
 function of this, i.e., g, • is completely monotonic. Therefore if g is 
 [(n + l)/3] -monotonie, g is completely monotonic. QFT 
 
 le r us introduce the concept of strongly asymmetric threshold 
 functions , because bhey will he used for checking the generation of 
 functions in our computer program, 
 
 ie f i nit i on 2 .1 ; If a positive self-dual -'-reshold function f of strictly n 
 variables satisfies the following conditions 
 
 (1) 
 
 f (x, 
 
 y X , X-. 
 
 n 1 
 
 x. 
 
 y) 
 
 for f with x and x substi uted by y and 
 
 (2) y is (one of greatest variable(s) in the > ordering of the variables 
 
 of 
 
 f X. 
 
 ,x 
 
 ^ 2 - y> x x a y), 
 
 the function with x n substituted by y ar.d x by y, 
 
 n f is called a strongly asymmetrical pcsi'ive self - dual thr esho ld function. 
 From these conditions Li results T he.- x., and x-, are 'he grea-es 1 variables 
 of f and that x, > x_. 
 
 Theorem 2.3 ■ Fh< se1 of strongly asymmetrical canonical, positive self- 
 dual threshold functions of exactly n variables has, one-to-one correspondence 
 
 b the se r of canonical positive self -dual threshold functions of exactly 
 (n - l) variables. 
 
 This one-to-one correspondence was used in our program to see 
 whether or not self -dual functions of nine variables are being generated 
 and tested, although it is no* a complete check. 
 
3 EI ION OF CERTAIN EXTREMAL INEQUALIT 
 
 n we solve + .he linear program, (lo3) "through (1.6), it is 
 desirable to eliminate unnecessary extremal inequali ies before solving 
 by the simplex method. Ls section two elimination methods will be- 
 discussed, although one of them was not fully utilized in our enumeration 
 of threshold functions since a different approach would be desirable for 
 the enumeration of the whole set of functions . 
 
 The first elimination method was briefly discussed in the paper 
 Here lei us discuss more explicitely the me r hod with a new definition. 
 
 Definition 3-1 : Given a Boolean function f of exactly n variables, 
 
 x, , . . . ,x , compare two arbitrary complete assignments of 1 and r o n 
 
 (1) 
 
 variables, A and A 
 
 If rr ". of n coordinates of A^ and A^ dis- 
 
 agree; let these m coordinates in A ' and A^ be denoted by A and A, re> 
 spectively. If 
 
 f => T-, 
 A - A , 
 
 (3-D 
 
 11 be den 
 
 A 
 
 (1) 
 
 f (2) 
 
 
 (No .• bhe (n-m) - ng coc. -s are taken back as the original 
 variables in the comparison (3>l).) In particular, if an equality is not 
 -iuded L] l), we replace (3.2) by 
 
 A* 1 ' I ^ 
 
 (3 3) 
 
 If only an equal □ (3.1), we replace (3«2) by 
 
 A (D f A (e) 
 
 (3.U) 
 
 Definition 3. 2' Let p be a prime implicant of a pcsi. ive function f of n 
 
 (p) 
 variables, Let A. be the complete assignment v -a - c f. ! 
 
 only for the variables appearing in p (withou - Inversion) and whose other 
 
 11 
 
/ \ 
 
 coordinates are zerc ( encefortl a will be called t he complete assignment 
 corresponding to the prime implicant p .) If there exists some other prime 
 
 implicant q of f si ai ^ > A holds for the complete assignment A^ q 
 corresponding to o er bhe prime implicant p is called an ex trin sic prime 
 implicant of f, C \e ii is called an intr insic prime implicant „ The 
 corresponding true q= tuples are called ir/rinsic and ext rinsic minima l true 
 n° tuples of f, respect i Similarly we define intrinsic maximal false 
 n- tuples of f and extrinsic, maximal false n- tuples of f. Both extrinsic 
 minimal r pies and. maximal false n- tuples are called extrinsic ex- 
 tremal n-_t i. ]:>.?. of f , Larly intrinsic extremal n°tuples are defined. 
 
 (8) 
 
 .or em 3°1 - 5 corresponding to all extrinsic extremal 
 
 n- tuples of a positive threshold function f are satisfied by strict in- 
 equality l - f • gl I s for f. 
 
 j of ; Firs*. Ie1 beme] for ,he [ > 3ic prime implicants 
 
 (i.e. the extrinsic minimal brue c tuples) Df + " 
 
 Let p he an extri] - impli f f , From Definition 3»2, 
 
 ion f has a \ Lmplican* q such ti 
 
 P) 
 
 > A 
 
 M) 
 
 (3.5) 
 
 Assume, without 2oss of gi I bhe firsl 11 oordinates agree in 
 
 comparison of A ' ^ err. A ' rhen (3»! !: 1 xistence of a certain 
 
 coml Lnatio] of va2 . I x. . x,, . . . ,x. sue 
 
 ] 2' m 
 
 ba1 
 
 f(x x , 
 
 >> 
 
 f( X] 
 
 i > ,, 
 
 (p) . P) 
 
 c v + 2 '• 
 
 ( 
 
 m+1 ' a m+2 ' 
 
 (?) 
 
 r 
 
 ) = 1 
 
 x q) ) = 
 
 (3.6) 
 
 (3*7) 
 
 Accord: ng] y 
 
 m n 
 
 E w .. ( 2x - 1 ) 4 z. 
 
 . , 1 
 
 P). ] 1 + 
 
 w.(2a.' *'■ 1) + w £ > 1 
 
 1 1 
 
 m n / \ 
 
 > -1 > Z w, (2x. - 1) + 1 r.(2a. Vq; - l) + w £ 
 
 i-1 
 
 i=m+l 
 
 o"o 
 
 12 
 

 a (f) - 1) + w I >E w.(2a. (q) - 1) + w g 
 . , o o .. • o o 
 
 - 
 
 (3.8) 
 
 for . v, , . . . ,w i w P j satisfying i jriralized set of i" 
 
 1 n o o j <=> 
 
 equal f(A^ P ') = 1 and f(A^) - 1, if 
 
 I w_ l) - 1) + w 
 
 
 p - 1 
 
 O 
 
 n (3=8) yields the relation 
 
 Z w,(2a 4 (p) - 1) + v ! 
 
 p > 1 
 
 
 o o 
 
 (3-9) 
 
 >f the ey c maximal false n- tuples is similarly proved, QF- 
 
 f i;nc ■ 
 
 For example bhe prim? Lmplicant x,y of bhe pop i br< "Id 
 
 X X^ v-X X >• X X, v X X vX-Xi 
 
 is an extrinsic prime i replicant. 
 
 , 5) 
 
 "• baa been known in the *y of linear programming" bat 
 among the inequalities, (1.5) and (1.6), bhere exists e. linearly in lent 
 
 of equalities which are sal y by any optimum extreme 
 
 solution. In order to get the set of all o] solutions, we need get 
 
 •• op-.imum extreme solutions, because other m solutions can be 
 
 expressed as linear convey sums of the optimum extreme solutions 
 
 
 By 
 
 orem 3«lj (1-5) an ~ (l»6) need include onl.v the ey rema] 
 
 (10 
 
 ■^sponding to bh« Lr rinsic ey-remal n-tuples of f. Lf : ii 
 
 shold function. 
 
 When every pair of inequa] are compared by i Lc 
 
 property of Theorem. 3«lj all inequalities which can be elin 3 by mono- 
 
 tonic proper-. ies ar< All inequalities which can be elimir 
 
 13 
 
by m-monotonicity a^e eliminated by comparing a pair of inequalities which 
 differ in m coefficients. Particularly if a pair of inequalities whic 
 
 differ in twc co c f^:::f-n'?- all. inequalities which can be eliminated by 
 
 x.. > x, n arc: positiveness of f can be eliminated. Winder's elimination 
 
 1 ^ l+l * 
 
 corresponds to this :ase c^ n = 2. ""ore the elimination method is an 
 erf icier* method when we want be eliminate inequalities by making use of 
 monotonic properties, r .sr> 2ially complete monotonicity. (The elimination 
 might destroy the inconsistency of the original set of inequalities if a 
 - ; n function is not a threshold function, and if a pair of inequalities 
 : Liffer more than two coefficients are compared. If so, w^ have 
 check whether an optimum solution obtained represent! giver function, 
 or equivalently whether t T satisfies the eliminated inequalities..) 
 
 a ion me -nod will be concerned with symmetrical 
 
 variables, We could simplify some inequalities and reduce the number of 
 
 variables by setting w w. in advance for symmetrical variables x. and. 
 
 <j ■*■ 
 
 x., i.e. when x. ~ x . „ However since we are interested in deriving the 
 
 J i 
 
 whole sei of optimum solutions if a threshold function has more than one 
 
 solution of optimum weights, this is not appropriate, The second elim- 
 ination method is based on the following simple property and let us derive 
 T he whole se1 of optimum 
 
 Theorem ■ Assumi a positive threshold function f is symmetric in 
 
 each set of variables, x 
 
 a. 
 
 ' x a 
 
 v 
 
 'X' 
 
 —y J - - " ' y *•••"» 
 
 '1 ■ c 
 
 Then even if th 
 
 1 3 
 
 6 l p ? P 3 
 
 w > w 
 a-1 a 
 
 ^b-l ? b 
 
 (3.10) 
 
 are added to the const] T ? , (1.5) ^nd. (1.6), the linear program cf (1.3) 
 through (1,6) will retail th original extreme optimum solutions except for 
 those which will be ol Lned by interchanging the weights of the symmetrj t 
 
 Ik 
 
Labl.es Lned solutions. (N( mum solution! 
 
 w w 
 
 equal "- for e variables., L.e wj • - CU. , , i rray 
 
 pn whe se are new or no* by examining 
 
 las + ableao as will be i ) 
 
 ^£-.°_2? - program hai ar on< > optimum s 
 
 :mum solutions may be divided Lnto two s< one. whose sol 
 
 satii Fiei ion do- p y some r ^ alH 
 
 of (3ol0)o Therefore if the constraints (3-10) are added, the s< 
 of optimum solutions will be B er, we can 
 
 Lea and acco: ? the c I tl of the 
 
 2h a way : 2 0) is fa 
 
 an extreme optimum solution because the interchange cf -.he variables simply 
 Implies ■ ange of columns In ~"e linearly inde I of co- 
 
 columns in the constraints, (1.5) and (1.6). There 
 sol. to some solution in set of extreme optimum 
 
 solutions I *>rem statemenl has beer shown QJ~.' 
 
 J ables have a 
 
 number of pr - . ants and accordingly bhe "jorrei 
 
 solved is large. T -^f e>: •mmetrj Fund ns of 
 
 n variables prime implicants in its 
 
 form is 
 
 whgre 
 
 W j 
 
 is an Integer not gr c ater than v ,* the close-si 
 
 em 3 ill " i in reducing greatly r of es 
 
 corresponding to j mplicants wi1 
 
 Winder's elimination also Ls based ■-■r, ;orpora1 f I 
 
 inequalities, (3»10) » but here rheorem 3«2 and following 
 
 11 assert ■ ; on of (3. 10) rray be made us< 
 
 all optimum ; ; ons instead of one op Lmun e ■■ For, 
 
 When a J Ly give" 
 
 equ ' ) and (1.6) can be eliminated by the at r < I an 
 
 e and then the 1 program, (1.3) thi I, an b*- solve 
 
 fewer 1 
 
 f a certaj 
 ar c to be gei progri 
 
 15 
 
different approaches might be appropriate. Winder devised an efficient 
 
 method to generate extremal inequalities for canonical positive self -dual 
 
 (2) 
 functions In our enumeration of threshold functions of eight variables,, 
 
 or equivalently canonical positive self -dual functions of nine variables, 
 
 e adopted the Winder's generation method to generate the extremal in- 
 
 e :ualities foi two-monc : functions which are candidates for threshold 
 
 ictions. rhe generatioE method eliminates some of the inequalities which 
 can be eliminated by the above two elimination methods but not all of them, 
 
 lis incomplete aination was due to Winder's treating x differently 
 from other variables u generation method.) In other words, a majority 
 of inequalities which "an be eliminated by two monotonicity are eliminated 
 
 '■': rier c s generation method. But any inequalities which can be eliminated 
 by three or more monotor ' ? are not eliminated. Also a majority of 
 inequalities which can be. eliminated by the second method is eliminated by 
 his generation method but nc of them, T .n our computer program., we 
 eliminate further inequalities by the second, elimination me'. hod. after using 
 Winder's g^r^ ■ :e : r is i o incorporate, However we did 
 
 not incorpors • firsl method because the firs method was partly in- 
 corporated already in Winder's arc it was difficult to evaluate the 
 effectiveness of the re n nation power of the m« although 
 
 the effectiveness wag investigated separately after the enumeration of 
 : uphold t\ ties „ 
 
 16 
 
 OVM 
 
' ":•:■ .TATICNAL procio 
 
 comp; al procedure is as follows . 
 
 By Winder's method, part of extremal Inequalities for each canonical 
 Lc posi + :w. self-dual function are generated. The variables of 
 function are ordered as 
 
 X T > * <~ 
 
 £ * 
 
 n 
 
 I 
 
 According to the elimination method for symmetric variables ; 
 second method of Section 3)* 
 
 w 2 > w 2 > w 3 
 
 . w _ > w > 
 n-1 — n — 
 
 
 may be added. Since the generated functions are self -dual, only inequalii 
 of (1,5) should be considers 
 When an extremal inequal 
 
 of (1.5) should be considered by setting w - and {1.6) may be ignored 
 
 r. / . \ 
 
 E w . 6 . U ' + v 6 > 1 
 
 ..11 00 — 
 1 =1 
 
 (4.3) 
 
 is redi. -erms of v^°2) and other extremal inequalities, in other 
 words, when we can prove by using {k.2) and other extremal inequalities 
 that the left side of (4.3) is not smaller than 1, the extremal inequality 
 (4.3) may be eliminated. let, X = ( 
 
 X. 
 
 ,x ) be an n-tuple. Define 
 
 ' n 
 
 x = (y r 
 
 ,y ) with y - Z x 
 1 k-1 K 
 
 (2) 
 
 for i = 1, 2, 
 
 o ,n and let us 
 
 call it a cumulat : aple . Form cumulative n-tuples for the extremal 
 iples. Comp- pair of them and eliminate a greater one if I 
 
 pair are comparable,. Only the extremal n-tuples corresponding to the 
 'ulative n-tuple lef 1 " will be considered for our linear program. The 
 
 c x-remal n-tuples generated by Winder's method do not include the ex1 emal 
 yples which e Lant in terms of the inequalities (^.2) of 
 
 w , . . . ,w t e redundant ones in terms of the inequalit th 
 
 17 
 
w, . The elimination of these redundant ones cakes little computer time 
 
 • reduction of computer ime for the linear programming due to this 
 elimination is significant. 
 
 When the secor 5 method of Section 3 is incorporated, the. further 
 incorporation of the first method, i.e. the elimination based on extrinsic 
 prime implicants is less powerful, than the incorporation of the first method 
 alone . 
 
 
 -n we considered the following linear program for a canonical 
 self -dual function, ty converting the unknowns w_. f s c 
 program (1*3) through (1.6) into their differences; Minimize 
 
 positive self -dual function, ty converting the unknowns w r s of the linear 
 
 n-1 
 
 Z 
 
 i=] 
 
 id 
 
 w . n ) + nw 
 l+l n 
 
 (4.4) 
 
 under the constraints 
 
 (w n - w,J > , (v. - w_) > , . . . , (w - - w ) > 0, w > 
 
 1 2 — ' ■ 2 3 n "l n - ' n — 
 
 and the extremal inequalities left after the above elimination method, 
 
 (4.5) 
 
 ^JK w ) Z ft ( 4 + w p Z ft ^ >1 (J -1, 2, . . . ,r). (4.6) 
 i--li. i ) i=l 
 
 (2) 
 As j^-r; ed oul by Winder , taking the differences (w. - w. .. ) 
 
 as the unknown wiU ms i jmber of iterations fewer than that by taking 
 
 w. themselves a? bb unknowns, ir solving the following dual linear program. 
 
 n the dual linear program of the above linear program, was 
 formulated, as follows : 
 
 Maximize Z v 
 j=l " 
 
 (4.7) 
 
 under the constraints 
 
 v. > 
 J - 
 
 ■9 <-) 
 
 (4.8) 
 
 18 
 
and 
 
 Z v. (|. CJ)) 
 
 j-1 J 
 
 < 1 
 
 r 2 (j) 
 
 £ v, ( E f ) < 2 
 j-i J to-i k 
 
 (^9) 
 
 (j) 
 
 E v. ( E L ') < n. 
 
 Then eliminate some inequalities of (k„9) 
 equalities such as 
 
 Since absurd in- 
 
 < i (1 < i < n) 
 
 (4.10) 
 
 and 
 
 -E v . s . < 1 where s . > for all j in E 
 
 (ij-.ll) 
 
 usually appear, eliminate them. Another type of eliminable inequality La an 
 inequality which is satisfied when there exists another one satisfied. When 
 a pair of inequalities 
 
 E v . s . < i_ . and E v . t . < i_ 
 
 J J - 1 J J - 2 
 
 appear, divide the first inequality by s. and the second by t , assuming 
 that v appears in both inequalities (if not, choose any other common 
 variable). If we can show that 
 
 Z v. ( S ./ Sl ) - (i^) - ]E,(t/V-i 2 /il> o 
 
 by using only v. > 0, the second inequality may be eliminated. 
 J 
 
 For example, consider the canonical self-dual positive function 
 
 x.jX_ n/ x g x x^x v x 2 x_x^xg v x g x x x^ v/ x 1 x 2 
 
 VX-,X|X,_ vX.X,X/ vX,X c X/ 
 
 1 4 5 1 4 6 15 6' 
 
 19 
 
The variables are ordered as 
 
 X 1> X 2 
 
 x 3 > x^ ~ x 
 
 5 
 
 By eliminating inequalities, we have only three inequalities left instead 
 of 8 inequalities corresponding to the prime implicants of the function. 
 Then the primal linear program of (4.4) to (h.6) becomes: 
 
 n-1 
 
 Minimize Z i (w. - w. , ) +■ 6 \j r 
 . , l l+l 6 
 
 i=l 
 
 under the constraints 
 
 w. - w. , > 
 
 l l+l — 
 
 (i-1, 2, . . . ,5) 
 
 (w 1 - 
 ■(w, - 
 
 ,w. 
 
 
 w 6 >0 
 
 
 - 2 ) 
 
 + (w ■ 
 
 • V 
 
 Wg) 
 
 + (w 3 ■ 
 
 ■ V 
 
 w 2 ) 
 
 - (v ■ 
 
 ■ V 
 
 - (w c - wj 
 
 -2w. > 1 
 6 — 
 
 - 2(w. - 
 
 + (w 
 w 5 ) + (w 5 
 
 w 6 ) +2w 6 > 
 w 6 ) 
 
 1 
 1 
 
 The dual linear program of (4.7) to (4.9) becomes 
 
 Maximize v + v + v 
 
 under the constraints 
 
 v 2 > °, v 2 - ° ; V 3 - ° 
 
 v x - v 2 + v 3 < 1 
 
 < 2 
 
 V l + V 2 " v 3 ~ 3 
 
 -2v . 4 
 
 " v l + Y 2 " Y 3 - 5 
 
 ■2^ + 2v 2 
 
 < 6 
 
 20 
 
The inequalities < and v_ < k are absurd and eliminable The second 
 inequality from th I is redur.. erma of * he last one,, Therefore 
 aJ linear program becomes: 
 
 Max Ld v + v + v 
 
 una- • corf rai : bs 
 
 f v 3 > °> v 2 - °' V 3 - ° 
 
 V" ■- v^ + v„ < 1 
 
 1 1 ~~ 
 
 V. 
 
 v 2 - v 3 < 3 
 
 k -2v x + 2v 2 
 
 < 6 
 
 Solve the dual linear prograrr of (h,' 7 ) to (k„9) by the simplex 
 The advantage of dealing with the dual linear program is avail- 
 ability of the initial feasible solution without introducting artificial 
 variables. A T the last simplex tableau we will ge r . either the symptom of 
 no solution or an extreme optimum solution for the prirral linear program 
 (k,4) through (4o6), as well as for I t] 2 i ne ar program, (^-.7) * hrough 
 {h.9) } itself, Simplex tableaux for the above example are shown in Table 
 -.1 
 
 We want to exhaust all extreme optimum solutions in order to 
 all optimum solutions . The last tableau is examined to determine 
 whether *here is a symptom for mu] extreme optimum solutions, as 
 follows 
 
 Assume that we have sol" ie following linear program which 
 
 dual to the primal problem, (k k) through [k.6): (Since, the following 
 
 argumen T if general, the formulae, [k 12) through (U,l r ), are express- 
 Ld general forms 
 
 Maximize Z b.v. 
 j=l J J 
 
 (4.12) 
 
 unde r the CO] □ • s 
 
 21 
 
TABLE k.l SIMPLEX TABLEAUX FOR AW EXAMPLE 
 
 i 
 
 Basis 
 
 b 
 
 c 
 
 1 
 v l 
 
 1 
 
 1 
 
 
 
 
 
 
 
 V 2 
 
 V 3 
 
 \ 
 
 V 5 
 
 v 6 
 
 1 
 
 \ 
 
 
 
 -L 
 
 © 
 
 -1 
 
 1 
 
 1 
 
 
 
 
 
 2 
 
 V 5 
 
 
 
 3 
 
 1 
 
 1 
 
 -1 
 
 
 
 1 
 
 
 
 3 
 
 v 6 
 
 
 
 6 
 
 -2 
 
 -2 
 
 
 
 
 
 
 
 1 
 
 k 
 
 
 
 
 
 - 1 
 
 -1 
 
 -1 
 
 
 
 
 
 
 
 1 
 
 V I 
 
 1 
 
 l 
 
 1 
 
 -1 
 
 1 
 
 1 
 
 
 
 
 
 2 
 
 V 5 
 
 
 
 2 
 
 
 
 © 
 
 -2 
 
 -1 
 
 1 
 
 
 
 3 
 
 v 6 
 
 
 
 8 
 
 
 
 
 
 2 
 
 2 
 
 
 
 1 
 
 h 
 
 X 
 
 X 
 
 
 
 
 -2 
 
 
 
 1 
 
 
 
 
 
 l 
 
 v l. 
 
 I 
 
 2 
 
 1 
 
 
 
 
 
 1/2 
 
 1/2 
 
 
 
 2 
 
 V 2 
 
 1 
 
 1 
 
 
 
 1 
 
 -1 
 
 -1/2 
 
 1/2 
 
 
 
 3 
 
 v 6 
 
 
 
 8 
 
 
 
 
 
 © 
 
 2 
 
 
 
 1 
 
 k 
 
 X 
 
 X 
 
 3 
 
 
 
 
 
 -2 
 
 
 
 1 
 
 
 
 1 
 
 v l 
 
 l 
 
 2 
 
 1 
 
 
 
 
 
 1/2 
 
 1/2 
 
 
 
 2 
 
 V 2 
 
 i 
 
 5 
 
 
 
 1 
 
 
 
 1/2 
 
 1/2 
 
 1/2 
 
 3 
 
 V 3 
 
 l 
 
 k 
 
 
 
 
 
 1 
 
 1 
 
 
 
 1/2 
 
 h 
 
 /\ /\ 
 
 11 
 
 
 
 
 
 
 
 2 
 
 1 
 
 1 
 
 w 
 
 / O Ox / O Ox o 
 
 Optimum weights: w - w = 2, w - w, = 1, w^ = 1 
 
 r 6 
 
 Thus w 
 
 o, o o^o o o , 
 
 4, W^ = W^ = 2, W, = W r = M r - 1 
 
 2 3 4 5 
 
 1 
 
 '6 
 
 22 
 
v. > for j = 1, 2, 
 J 
 
 ,m + n 
 
 (*.13) 
 
 and 
 
 m + n 
 
 i 
 
 3 - i 
 
 a. . v. = c 
 
 (i - 1, 2, 
 
 ,n) 
 
 (4.14) 
 
 where 
 
 ij 
 
 ■{S 
 
 for j = m + i 
 
 for j > m but | m + i 
 
 (*.15) 
 
 Then assume that we have obtained the last tableau for this problem, as 
 shown in Table 4,2. The simplex method provides only one extreme optimum 
 
 solution of the primal problem as z , - b , , 
 
 m+1 m+1 
 
 , z - b , at the 
 
 m+ n m+n 
 
 last tableau, no matter whether there is more than one extreme optimum. 
 solution or not, However useful information of other extreme optimum 
 solutions and accordingly all optimum solutions (all optimum solutions are 
 expressed as linear convex sums of all extreme optimum solutions) are ob- 
 tained at the last tableau. 
 
 If no zero appears in the column for c" excep+ "he bottom entry 
 
 in the last tableau, and if all bottom entries of the columns for the 
 
 bors a*, of (4.1.4) except those in the last basis are positive (; 
 J 
 
 z. - b. > 0), then the extreme optimum solution for the dual problem 
 J J 
 (4.13) through (4.15) which is given as the entries of the column '"c 
 
 and also the extreme optimum solution for the primal problem, (4,4) 
 
 through (4,6), which is given as z , - b , , . . . ,z - b at the 
 
 e v ' B m+1. m+1 m+n m+n 
 
 bottom entries of the columns for the slack variables are both unique . 
 Ar example is Table 4.1. 
 
 If the conditions stated are not satisfied, we must examine 
 las: tableau more carefully, The following is due to R. F. Gomory, 
 
 In the above last tableau, pick up all rows whose, entries in 
 column ""c" are zeros (exclude, the bottom row). Denote the entries of the 
 Irh of these rows by 
 
 23 
 
t-3 
 > 
 
 ro 
 
 CD 
 
 1-3 
 
 CO 
 
 I 
 
 24 
 
1 
 a h 
 
 m 
 
 m+1 
 
 *v , v 
 a ' a, 
 
 h h 
 
 ,v. 
 
 m+n 
 
 a. 
 
 16) 
 
 Denote the bottom row by 
 
 z, - b, , . . . , z -b , z t - b , , 
 
 1 1' ' m m ' m+1 m+1' 
 
 ,z - b , >^ 17) 
 
 m+n m+n ' 
 
 where 
 
 z , - b ,,..., z -b 
 
 m+1 m+1 7 m+n m+n 
 
 is an optimum solution, 
 
 (w 1 - w 2 ), (w g - w ), 
 
 , (w . - w ), w 
 
 n-1 n n 
 
 for the primal problem, (4.4) through (4.6). Let u be the number of such 
 rows . Then a set of 
 
 (z. - b.) + Z g^v J 
 J J h=l h a h 
 
 (j = m+1, . 
 
 , m+n, 
 
 (4.18) 
 
 yields all optimum solutions for any set of g 8 s such that 
 
 (z - b ) + E g v J > for j = 1, 2, 
 J J h=l h 
 
 ,m, m+1, . . . ,m+n (1.19) 
 
 and 
 
 l h > f or h = 1, 2, 
 
 (4.20) 
 
 For the optimum value of the objective function (4.12) which is equal to 
 the optimum value of (4.4) is not changed and (4.18) satisfies all the 
 constraints of the primal problem. Therefore when we look at the last 
 tableau, we have the following two cases, as easily seen: 
 
 (1) If g = for all h is the only set of g 's which satisfy (4.19) and 
 
 (4.20), the optimum solution which we have obtained in the last tableau 
 
 is unique for the primal problem, (4,4) through (4,6). We can find whether 
 
 25 
 
■'•->.'/' 
 
 all g ha^e to be. zero, by checking only v ' s in the columns where 
 h a h 
 
 z. - b. = but the procedure would be complicated if u becomes large, 
 J J 
 
 (2) If g can be positive for some h, then the primal problem has more 
 than one optimum solution Exhaust all extreme solutions of the set of 
 solutions of (4,19) and (if. 20). Then they are all extreme optimum solutions 
 for the primal problem, (4.4) through (4.6). The linear convex sums of 
 these extreme optimum solutions yield all optimum solutions of the primal 
 problem, Exhaustion of all extreme points is easy when u is a small integer 
 but would be cumbersome, for large u. 
 
 The flow chart of our computer program in a macroscopic scale 
 is shown in Table 4.3< In the block Gen , the extremal inequalities of 
 a canonical positive self -dual function are generated, by Winder's gen- 
 eration and further eliminating inequalities by the second elimination 
 method of Section 3° In the block LP, the linear program, (4.1.2) through 
 (4,15), dual t d the problem (4.^) through (4.6) is formulated (We did not 
 eliminate the inequalities in this linear program in spite of our discussion 
 around the inequalities, (4,10) and (4.11)) and solved, by the simplex method. 
 If j 1 is not solvable, whether the function under consideration is 3-mono- 
 tonic or not is tested in the block 3M. If it is 3 _nl onoton.ic, the function 
 is completely monotonic but not a threshold, function. If it is solvable, 
 the function is a threshold function. In the block Spe c , the special prop- 
 erties of the function are tested, whether it is of 9 variables or fewer, 
 in what variables L"t is symmetric, whether it has the unique extreme optimum 
 solution, whether some of its extreme optimum weights are fractional and 
 whether i1 Ls strongly asymmetrical. The results of this test are entered 
 in the fable of statistics in block St . Then the program control is re- 
 turned to Gen, and the above process is repeated. When all functions are 
 exhausted by Gen, the program stops, 
 
 The program was written in NICAP, the assembly language for 
 
 u>IAC II, 
 
 26 
 
 
TABLE' ^. 3 FLOW CHART CF C ;R COMPTfTER PRC3PAM 
 
 V 
 
 .en 
 
 Generation of a 
 
 canonical two- mono tonic 
 
 positive self -dual function 
 
 and elimination of inequalities 
 
 \/ 
 
 L..P. 
 
 Simplex method to solve the 
 
 dual LP 
 
 No solution 
 (Non- threshold 
 function) 
 
 \/ 
 
 3M 
 
 Test of 
 3-mono tonicity 
 
 J 
 
 Solvable 
 
 (Threshold 
 
 function) 
 
 \/ 
 
 S^ec, 
 
 Tes + of special properties, 
 e.g. 9 or fewer variable 
 function, symmetry of a 
 function, multiple optimum 
 solutions, fractional weights 
 and strongly asymmetrical 
 functions 
 
 T 
 
 \/ 
 
 St. 
 
 Table of statistics 
 
 \/ 
 
 27 
 
5. COMPUTATIONAL RESULTS 
 
 In the "block Gen, 319* 124 canonical two-monotonic positive self- 
 dual functions are generated. We have solved the same number of linear 
 programs. 1 7 5,^28 of them turned out to be threshold functions and the 
 remaining 1^3*696 t, ° ^ e non- threshold functions. By Winder's generation 
 and the further elimination of the extremal inequalities, we had totally 
 1, 898, 9^7 ex r remal inequalities for threshold functions (3*^77.? 178 extremal 
 inequalities for all generated functions). This means that each threshold 
 function on the average has 10.8 extremal inequalities. (Each of all gen- 
 erate functions or the average has 10. 9 extremal inequalities.) The 
 maximum number of extremal inequalities for a threshold function was 23. 
 
 Since a large number of linear programs had to be solved, the 
 computer program of simplex method had to be fast. Features of Illiac II 
 were made use of, ^ En LP, 1,566,70^- simplex tableaux (the count does not 
 include initial tableaux) were formed for threshold functions. Therefore 
 each threshold function had 8..9 iterations on the average. (We did not try 
 to eliminate the inequalities of the dual linear program. If we did, the 
 number of iterations would be fewer,) The maximum number of iterations 
 for a threshold function is 18. 
 
 
 The statistics of the number of threshold functions and other types 
 of functions are shown in Table 5-1- Some figures were available already 
 
 and our results are checked s.gains' them. (One obviously erroneous mistake 
 
 (2) 
 
 in Winder's table " of nondegenerate threshold functions of 7 
 
 variables was corr 
 
 T < t P be the number of threshold functions of up to n variables. 
 
 ' ( 1 f\ \ 
 
 The bounds on E are known as 
 
 n 
 
 < lim ■-— log^ R < 1. 
 — n-» « 2 2 n *— 
 
 The values of —-- log P from the figures in Table 5-1 are computed in 
 n 
 
 Table c „2„ The value reaches a minimum at n=5 and increases again for 
 larger n, 
 
 28 
 

 r— 
 
 
 vo 
 
 OJ 
 
 
 
 
 CVI 
 
 
 
 -o 
 
 H 
 
 
 
 CO 
 
 OO 
 
 
 I 
 
 CO 
 
 co 
 
 
 
 j — 
 
 
 jF 
 
 OO 
 
 OJ 
 
 
 CO 
 
 L"\ 
 
 
 
 •vO 
 
 O 1 
 
 ■ 
 
 
 H 
 
 ^o 
 
 
 
 
 LTN 
 
 
 
 o 
 
 
 
 O 
 
 IfN 
 
 
 oo 
 
 r- 
 
 
 
 
 
 i 
 
 
 m 
 
 IT\ 
 
 
 i 
 
 -ct 
 
 ON 
 
 
 
 
 H 
 
 ^ 
 
 OS 
 
 •s 
 
 •V 
 
 
 
 
 
 
 •s 
 
 • 
 
 
 N 
 
 s 
 
 
 i 
 
 »» 
 
 
 
 
 
 X 
 
 
 _• 
 
 
 
 
 
 
 
 o 
 
 
 i 
 
 
 VO 
 
 rH 
 
 
 i 
 
 
 CVI 
 
 
 
 vo 
 
 VO 
 
 la~v 
 
 
 
 
 
 
 
 
 nn 
 
 
 
 
 VO 
 
 LTV 
 
 
 
 t- 
 
 N- 
 
 
 
 H 
 
 h 
 
 
 vo 
 
 
 
 
 VO 
 
 
 
 h- 
 
 t>- 
 
 
 
 
 m 
 
 
 
 
 r~\ 
 
 
 
 Q 
 
 ■ 
 
 os 
 
 •s 
 
 »s 
 
 
 IN 
 
 <N 
 
 
 
 
 
 
 
 OS 
 
 °s 
 
 
 
 
 
 
 
 r— 1 
 
 <-\ 
 
 0> 
 
 o 
 
 OO 
 
 on 
 
 OO 
 
 OO 
 
 i 
 
 
 CVI 
 
 
 
 
 r-1 
 
 
 
 
 
 
 
 oo 
 
 -P 
 
 o 
 
 X 
 
 -p 
 
 03 
 
 no 
 
 LA 
 
 H 
 
 vO 
 
 in 
 H 
 
 J- 
 *\ 
 
 r— 
 
 rH 
 
 VO 
 CO 
 
 ao" 
 vo 
 
 no 
 
 co 
 vo 
 
 -3- 
 
 J- 
 
 
 
 
 
 
 
 
 
 
 i 
 I 
 
 
 
 OJ 
 
 -! 
 Q 
 
 
 
 DO 
 
 X) 
 
 J 
 
 Q 
 
 
 
 o 
 
 OO 
 
 
 
 
 cv 
 
 
 
 IT\ 
 
 CO 
 
 
 
 : 
 
 LTN 
 
 
 oo 
 
 oo 
 
 VO 
 
 -r 
 
 ON 
 
 lO 
 
 LT\ 
 
 vO 
 
 
 
 ^^ 
 
 vO 
 
 
 
 u> 
 
 CO 
 
 
 
 
 OO 
 
 •H 
 
 
 
 
 CO 
 
 -d" 
 
 lT\ 
 
 CO 
 
 
 r-H 
 
 
 
 v^ 
 
 -\J 
 
 i 
 
 
 t*- 
 
 H 
 
 
 
 .j- 
 
 0^ 
 
 
 
 H 
 
 H 
 
 as 
 
 *v 
 
 •s 
 
 •■ 
 
 ^ 
 
 •s 
 
 j 
 
 
 •s 
 
 
 
 
 "V 
 
 
 
 
 
 - 
 
 
 
 X 
 
 X 
 
 
 [ — 
 
 H 
 
 vo 
 
 t- 
 
 
 3 
 
 
 • 
 
 CO 
 
 
 
 J 
 
 J 
 
 
 
 M 
 
 
 ; 
 
 
 J- 
 
 -4" 
 
 h — 
 
 
 on 
 
 3F 
 
 o 
 
 VO 
 
 ■ 
 
 
 
 OJ 
 
 
 
 H 
 
 H 
 
 
 
 
 
 
 
 • 
 
 ■ 
 
 
 
 
 VO 
 
 OJ 
 
 CVI 
 
 . 
 
 
 
 
 
 ■ 
 
 
 
 
 
 
 
 
 t«- 
 
 o^ 
 
 -1 
 
 • 
 
 X 
 
 oo 
 
 oo' 
 t— 
 m 
 
 CO*" 
 
 CO 
 
 sO 
 
 
 m 
 
 OO 
 
 1 
 
 3 
 
 
 
 
 
 
 
 i 
 
 3 
 
 
 
 
 i 
 
 
 
 H 
 
 
 
 - 
 
 C 
 
 
 
 3 
 
 _- 
 
 
 CO 
 
 o 
 
 
 ON 
 
 X) 
 
 
 
 -7 
 
 -- 
 
 ao 
 
 ,^_ 
 
 J- 
 
 
 
 U\ 
 
 -d- 
 
 d 
 
 
 H 
 
 H 
 
 oo 
 
 -3" 
 
 LTN 
 
 VO 
 
 VO 
 
 ^-i 
 
 cvi 
 
 N -- 
 
 
 ON 
 
 30 
 
 
 VO 
 
 " 
 
 
 
 OO 
 
 H 
 
 t* 
 
 
 O 
 
 O 
 
 H 
 
 O 
 
 
 m 
 
 
 ir\ 
 
 r — 
 
 ir> 
 
 H 
 
 ON 
 
 
 c 
 
 ir> 
 
 IT\ 
 
 
 
 H 
 
 r-i 
 
 u 
 
 
 H 
 
 H 
 
 »\ 
 
 ^ 
 
 °s 
 
 Ov 
 
 •s 
 
 <v 
 
 * *v 
 
 OS 
 
 •s 
 
 
 *\ 
 
 
 
 
 t 
 
 3 
 
 
 
 +- 
 
 
 N 
 
 X 
 
 CO 
 
 ~— 
 
 _cf 
 
 VO 
 
 
 
 0^ 
 
 lTx 
 
 H 
 
 
 c— 
 
 
 
 
 i 
 
 | 
 
 
 
 CO 
 
 
 CO 
 
 OD 
 
 rvj 
 
 co 
 
 3 
 
 CVI 
 
 
 H 
 
 -3" 
 
 ... 
 
 
 
 
 
 
 
 i 
 
 1 
 
 
 
 "' 
 
 
 o 
 
 
 
 c 
 
 J- 
 
 
 
 H 
 
 H 
 
 X) 
 
 C 
 
 
 
 
 □> 
 
 
 
 
 
 
 
 H 
 
 
 H 
 
 r-l 
 
 LT\ 
 
 
 
 
 
 
 £ 
 
 OS 
 
 
 
 ■• 
 
 
 
 
 
 
 
 
 S3 
 
 
 -t-> 
 
 
 H 
 
 H 
 
 
 
 
 
 ; 
 
 o 
 
 
 
 LTV 
 
 LTN 
 
 
 
 ; 
 
 1 
 
 
 
 ., 
 
 
 2 
 
 J 
 
 
 
 
 
 
 
 DO 
 
 30 
 
 
 
 OA 
 
 
 
 
 
 
 
 
 H 
 
 <0 
 
 O 
 
 XI 
 CD 
 
 o 
 XI 
 
 cti 
 
 
 
 
 • 
 
 
 
 c 
 
 
 
 
 no 
 
 ' 
 
 
 
 
 
 
 
 JQ 
 
 ■H 
 
 
 
 
 
 
 
 
 
 ■• 
 
 c^, 
 
 •s 
 
 
 
 •>.. 
 
 
 
 
 ". 
 
 I 
 
 
 
 
 
 
 
 
 
 
 
 
 O 
 
 
 
 
 
 
 
 
 1 
 
 
 
 
 
 
 
 
 
 
 
 
 
 o 
 
 " 1 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 J- 
 
 3 
 
 
 
 
 VI 
 
 
 
 
 
 
 
 -1 
 
 
 0\ 
 
 ON 
 
 OJ 
 
 ^ 
 
 ^_ 
 
 
 - 
 
 
 30 
 
 •^ 
 
 J 
 
 
 vO 
 
 
 ■ 
 
 iX 
 
 CO 
 
 U > 
 
 H 
 
 J- 
 
 + 
 
 
 
 o 
 
 C- 
 
 CO 
 
 CO 
 
 Q 
 
 OO 
 
 
 LPS 
 
 LT\ 
 
 
 
 
 
 VO 
 
 -rf 
 
 jA 
 
 I s - 
 
 OJ 
 
 H 
 
 
 
 
 H 
 
 UA 
 
 O 
 
 
 VO 
 
 VO 
 
 ro 
 
 
 
 r-i 
 
 
 
 0> 
 
 
 
 
 oo 
 
 
 
 --; 
 
 
 X 
 
 X 
 
 •s 
 
 **\ 
 
 «s 
 
 ■s 
 
 •>■ 
 
 os 
 
 D> 
 
 i^ 
 
 
 
 OS 
 
 o-. 
 
 
 
 OS 
 
 0\ 
 
 
 
 
 
 oo 
 
 ft 
 
 J" 
 
 VO 
 
 oo 
 
 
 -1 
 
 -1 
 
 30 
 
 r— 
 
 
 
 vO 
 
 
 
 OV 
 
 
 
 
 H 
 
 
 ■ 
 
 ■ 
 
 ON 
 
 CO 
 
 
 
 
 
 VI 
 
 
 
 
 H 
 
 
 
 
 o 
 
 
 
 
 
 LT\ 
 
 
 X 
 
 
 
 
 
 
 
 H 
 
 CVI 
 H 
 
 
 
 VO 
 
 
 
 
 
 r-1 
 
 H 
 
 
 
 a 
 
 DQ 
 ry) 
 
 
 - 
 
 ^t 
 
 - 
 
 VO 
 
 D 
 
 vo 
 
 — . 
 
 VO 
 
 - 
 
 
 - 
 
 t~- 
 
 
 co 
 
 
 J 
 
 ^> 
 
 VO 
 
 -— 
 
 _t 
 
 • 
 
 
 nn 
 
 ON 
 
 CO 
 
 m 
 
 IT\ 
 
 0> 
 
 co 
 
 -d- 
 
 o 
 
 nc: 
 
 CO 
 
 H 
 
 > 
 
 
 
 
 OO 
 
 r- 
 
 
 
 . 
 
 
 LPl 
 
 IT\ 
 
 CO 
 
 lf\ 
 
 
 
 
 
 J- 
 
 
 
 
 
 
 
 
 
 
 
 
 
 ft 
 
 
 «N 
 
 
 » 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 • 
 
 
 ITv 
 
 
 
 H 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 sO 
 
 - 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 r ^ 
 
 CO 
 
 jt 
 
 
 
 
 
 -J- 
 
 
 sO 
 
 
 IT\ 
 
 J- 
 
 
 VO 
 
 oo 
 
 C^- 
 
 * 
 
 oo 
 
 ~i 
 
 - 
 
 pT) 
 
 
 H 
 
 
 
 
 
 
 • 
 ! 
 
 
 
 
 
 
 
 
 
 
 
 
 
 - 
 
 
 
 T 
 
 -1 
 
 
 ^O 
 
 ■ 
 
 ^+ 
 
 1 
 
 
 
 
 1 r 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 r 1 
 
 
 
 CO 
 
 . "-0 
 
 
 j- 
 
 H 
 
 oo 
 
 Lf 
 
 
 Ut- 
 
 
 oo 
 
 ! 
 
 OO 
 
 ^j 
 
 ■OJ 
 
 H 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 i 
 
 
 
 
 
 
 
 
 
 H 
 
 -- 
 
 
 j- 
 
 
 
 
 
 ' 
 
 O 
 
 ~ 
 
 ---I 
 
 
 H 
 
 • 
 
 
 
 
 H 
 
 o 
 
 —1 
 
 O 
 
 1 1 
 
 O 
 
 
 CVI 
 
 CVI 
 
 
 ' 
 
 
 ~i 
 
 H 
 
 
 \j 
 
 M 
 
 M 
 
 rH 
 
 i 
 
 
 H 
 
 i 
 
 H 
 
 1 
 
 H 
 
 
 
 
 
 
 
 
 
 
 | 4 
 
 
 
 
 
 
 j 
 
 
 
 
 rH 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 ■ (. j 
 
 
 
 
 
 
 
 
 
 ' 
 
 
 
 
 
 
 1 
 
 
 
 ra 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 v 
 
 
 
 
 
 
 
 
 CO 
 
 
 
 
 
 
 
 
 
 
 
 
 tfl 
 
 H 
 
 
 
 
 
 
 
 
 < V 
 
 <U 
 
 
 
 
 
 
 
 
 
 
 
 
 a, 
 
 X 
 
 •s 
 
 
 
 
 
 >, 
 
 
 
 H 
 
 
 
 
 
 
 (/l 
 
 H 
 
 
 
 
 
 H 
 
 
 X 
 
 
 
 
 
 
 .-*> 
 
 p< 
 
 X 
 
 
 
 
 
 
 V 
 
 x 
 
 ft 
 
 
 
 H^ 
 
 X 
 
 >H 
 
 
 
 
 
 
 
 
 T< 53 
 
 Tj " 1 
 
 
 X 
 
 ft 
 
 
 - 
 
 
 3 
 
 
 
 CO 
 
 H 
 
 30 
 
 
 
 
 - 
 
 
 
 
 
 
 H 
 
 *: 
 
 3 
 
 
 a 
 
 
 
 
 
 P 
 
 
 Td * 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 a 
 
 
 
 
 
 
 
 H f> 
 
 •s 
 
 
 ft 
 
 
 ft 
 
 r* 
 
 
 
 
 
 
 • 
 
 <i-; 
 
 
 d 
 
 O 
 
 
 
 
 
 X 
 
 
 J 
 
 
 
 
 X 
 
 4-> 1 
 
 
 
 
 
 
 
 3 
 
 
 
 
 
 ft 
 
 X 
 
 
 
 +3 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 (U 
 
 
 M ± 
 
 a) S 
 
 ' ~- 
 
 
 
 m 
 
 - 
 
 - 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 a> h 
 
 
 
 O 
 
 V 
 
 
 
 - 
 
 r~ 
 
 
 a 
 
 a 
 
 
 
 
 
 
 <*H 
 
 
 rH 
 
 ±J 
 
 
 
 H 
 
 
 
 
 '•in H 
 
 +3 c! 
 
 
 
 
 
 
 
 
 
 •H 
 
 
 
 X! J» 
 
 
 
 
 
 
 11 
 
 
 X 
 
 
 
 
 
 ■H 
 
 
 
 
 
 
 
 
 • 
 
 •P H 
 
 P 
 
 
 >-t 
 
 
 C 
 
 n h 
 
 T3 J) 
 
 
 
 
 
 
 
 
 
 
 
 
 +J 
 
 
 C 
 
 
 
 
 
 H x 
 
 
 
 a3 
 
 
 
 
 
 
 
 . 
 
 
 0) 
 
 
 
 a> u 
 
 
 
 P 
 
 ' 
 
 - 
 — 
 
 
 
 
 'd ft 
 
 3 >» 
 
 +3 
 
 
 
 
 a, 
 
 « 
 
 
 ft 
 
 ■ 
 
 
 S ft 
 
 ft cC 
 
 XI 
 
 
 
 
 
 
 
 
 i P 
 
 
 ft 
 
 
 
 
 
 
 
 
 p 
 
 P 
 
 
 p a> 
 
 *- 
 
 
 C <U 
 
 
 a 
 
 
 
 
 
 3 
 
 
 
 
 
 
 TJ 
 
 
 a 
 
 '/) 
 
 
 
 
 
 
 3 
 
 
 - 
 
 
 r-1 CC 
 
 
 
 ti 
 
 
 
 
 
 
 
 >. CO 
 
 
 
 m 
 
 
 fi a 
 
 - 
 
 H 'D 
 
 
 X 
 
 
 
 (U X 
 
 • 
 
 
 
 
 
 
 
 
 
 M H 
 
 
 
 p 
 
 
 a 
 
 >j 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 •H X 
 
 
 H 
 
 o 
 
 
 M r. 
 
 tiD H 
 
 Ti H 
 
 
 
 
 
 
 
 
 
 
 r /2-| 
 
 
 
 
 
 
 B 
 
 
 
 C *j 
 
 -i X 
 
 
 
 
 
 
 
 
 
 <u 
 
 
 (LX 
 
 a) 
 
 
 CO fl 
 
 
 
 
 
 
 
 3 JO 
 
 
 
 
 
 
 
 
 p, 
 
 
 
 
 
 H 
 
 3 D 
 
 
 * 
 
 
 
 E ~ 
 
 X -H 
 
 X H 
 
 
 
 
 
 
 
 
 
 
 
 
 
 -Cl -H 
 
 
 
 
 
 * 
 
 ■fl h 
 
 
 w ft 
 
 
 
 w '" 
 
 
 
 
 
 • 
 
 MP II 
 
 
 • 
 
 • 
 
 
 
 -P £ 
 
 
 
 
 •H p 
 
 
 
 h c: 
 
 t^ 
 
 
 • 
 
 
 
 
 
 
 
 
 
 
 
 •H 
 
 H > 
 
 
 a 
 
 
 
 
 
 
 
 g 
 
 Bl 
 
 
 ■ 
 
 
 
 
 
 
 ra -p 
 
 
 En £ 
 
 X 
 E- Ej 
 
 Q- 
 
 ! 
 
 Oh 
 
 • 
 
 
 g 
 
 
 
 
 g 
 
 
 ^ +. 
 
 
 
 
 
 
 
 
 
 
 
 > 
 
 
 
 
 
 
 
 
 . 
 
 
 
 
 
 
TABLE 5.2 
 
 n 
 No . of 
 
 1 
 2 
 n 
 
 - log 2 R n 
 
 Variables 
 
 ... _ „., . 
 
 
 1 
 
 
 2 
 
 2 
 
 
 0.95184 
 
 3 
 
 
 0.7Mj49 
 
 . k 
 
 
 O.67988 
 
 5 
 
 
 0.66117 
 
 6 
 
 
 0.66226 
 
 n 
 
 
 0.67273 
 
 8 
 
 
 0.687^0 
 
 
 30 
 
s 
 
 CABLE 5.3 SYMMETRY 3TPES OF C, [TIVE SELI 7 
 
 Number of functions of symme 
 
 Number of possibilities of assigning a constant value to 
 a variable 
 
 N P 
 s c 
 
 N P : 
 s p 
 
 Number of functions with an assigned constant 
 Number of possibilities of permuting va 
 Number of functions with per: Les 
 
 Symmetry types are expressed as follows: 32211, for example, of 
 -able (h), means that the function is symme ric in x-,, x~, x_, in x. , 
 x , in x^, x 7 and no 1 symmetric i] Lae two variables. 
 
 
 No. of 
 
 Variables 
 
 n = 1 
 
 • ype 
 
 N I P 
 
 s c 
 
 ' [ 
 
 c r> 
 
 P j IV 7 
 P s p 
 
 — 
 
 3 i 
 
 n » h 
 
 n ■ 5 
 
 5 
 
 X 
 
 1 
 
 1 
 
 1 
 
 2 
 
 41 
 
 1 
 
 2 
 
 2 
 
 C 
 
 5 
 
 32 
 
 1 
 
 2 
 
 2 
 
 10 
 
 10 
 
 221 
 
 1 
 
 3 
 
 3 
 
 30 
 
 30 
 
 * oi al 
 
 L 
 
 
 Q 
 8 
 
 
 fO 
 
 
 = 6 
 
 51 
 411 
 
 33 
 
 321 
 
 2211 
 
 21111 
 
 al 
 
 4 
 
 - 
 5 1 
 
 2 
 
 18 
 12 
 
 5 
 
 6 
 
 30 
 
 20 
 
 60 
 
 180 
 
 360 
 
 
 12 
 
 30 
 20 
 
 360 
 
 360 
 1322 
 
 31 
 
TABLE q 3 SYMMETRY TYPES OF CANONICAL POSITIVE SELF-DUAL 
 THRESHOLD FUNCTIONS ( cont . ) 
 
 I 
 
 No. of 
 Variables 
 
 Symmetry type— 
 
 N 
 s 
 
 P i 
 c 
 
 N P 
 s c 
 
 P 
 P 
 
 N P 
 s p 
 
 n = 7 
 
 7 
 
 1 
 
 1 
 
 1 
 
 1 
 
 1 
 
 
 6l 
 
 2 
 
 2 
 
 4 
 
 7 
 
 14 
 
 
 52 
 
 2 
 
 2 
 
 1* 
 
 21 
 
 1*2 
 
 
 511 
 
 1 
 
 3 
 
 3 
 
 1+2 
 
 42 
 
 
 43 
 
 3 
 
 2 
 
 6 
 
 35 
 
 105 
 
 
 1*21 
 
 9 
 
 3 
 
 27 
 
 105 
 
 94.5 
 
 
 1*111 
 
 2 
 
 4 
 
 8 
 
 210 
 
 420 
 
 
 331 
 
 5 
 
 3 
 
 15 
 
 11*0 
 
 700 
 
 
 # 322 
 
 7 
 
 3 
 
 21 
 
 210 
 
 1470 
 
 
 3211 
 
 19 
 
 4 
 
 76 
 
 1*20 
 
 7980 
 
 
 31111 
 
 6 
 
 5 
 
 30 
 
 81*0 
 
 5040 
 
 
 2221 
 
 12 
 
 4 
 
 48 
 
 630 
 
 7560 
 
 i 22111 
 i 
 
 26 
 
 5 
 
 130 
 
 1.260 
 
 32760 
 
 ! 211111 
 
 16 
 
 6 
 
 96 
 
 2520 
 
 40320 
 
 
 1111111 
 
 3 
 
 1 
 
 21 
 
 50l*0 
 
 15120 
 
 
 total 
 
 114 
 
 1- 
 
 1*90 
 
 
 112519 
 
 32 
 
JLE 5.3 SYMMETRY TYPES OF CANONICAL POSITIVE SELF-I jAL 
 
 THFJESHOLI FUNCTIONS (cont.) 
 
 No . of 
 
 
 
 
 
 
 
 Variables 
 
 rametry type 
 
 N 
 s 
 
 F 
 C 
 
 N F 
 s c 
 
 P 
 P 
 
 ' P 
 
 £ P 
 
 D - B 
 
 71 
 
 3 
 
 2 
 
 6 
 
 
 24! 
 
 
 611 
 
 3 
 
 3 
 
 9 
 
 56 
 
 168 
 
 
 53 
 
 k 
 
 2 
 
 8 
 
 56 
 
 \k 
 
 
 521 
 
 16 
 
 3 
 
 48 
 
 168 
 
 2688 
 
 
 5111 
 
 4 
 
 L 
 
 16 
 
 336 
 
 1344 
 
 
 431 
 
 22 
 
 3 
 
 66 
 
 280 
 
 6160 
 
 
 4211 
 
 56 
 
 4 
 
 224 
 
 840 
 
 47040 
 
 
 Lll 
 
 18 
 
 5 
 
 90 
 
 1680 
 
 30240 
 
 
 332 
 
 It 
 
 3 
 
 ^ 
 
 560 
 
 ^840 
 
 
 3311 
 
 31 
 
 k 
 
 124 
 
 1120 
 
 34720 
 
 
 3221 
 
 122 
 
 act 
 
 k 
 
 488 
 
 1680 
 
 504960 
 
 
 32111 
 
 226 
 
 5 
 
 1130 
 
 3360 
 
 759360 
 
 
 3IIIU 
 
 102 
 
 6 
 
 61.2 
 
 6720 
 
 68 c ^4o 
 
 
 22211 
 
 233 
 
 5 
 
 1165 
 
 5040 
 
 1172 
 
 
 221111 
 
 588 
 
 6 
 
 3528 
 
 1 0080 
 
 7040 
 
 
 2111111 
 
 626 
 
 7 
 
 4382 
 
 20160 
 
 620160 
 
 
 11111111 
 
 267 
 
 8 
 
 2136 
 
 40320 
 
 IO765440 
 
 _ 
 
 total 
 
 2335 
 
 
 74 
 
 
 32267168 
 
 33 
 
TABLE 5.3 SYMMETRY TYPES OF CANONICAL. POSITIVE SELF-DUAL 
 THRESHOLD FUNCTIONS (cont.) 
 
 No. of 
 Variables 
 
 n = 
 
 Symmetry type 
 
 N 
 
 P 
 
 9 
 81 
 
 72 
 711 
 
 63 
 
 621 
 
 6111 
 
 54 
 
 531 
 
 522 
 
 5211 
 
 51111 
 
 kkl 
 
 U32 
 
 1*311 
 
 1*221 
 
 1*2111 
 
 1*11111 
 
 333 
 
 3321 
 
 33m 
 
 3222 
 
 32211 
 
 321111 
 
 3111111 
 
 22221 
 
 222111 
 
 2211111 
 
 21111111 
 
 111111111 
 
 1 
 
 3 
 
 3 
 
 3 
 h 
 
 22 
 
 9! 
 
 5 
 
 30 ! 
 
 18 I 
 
 93 J 
 
 50 I 
 1 
 
 17 ! 
 
 52 
 
 I 
 
 11*1 
 
 237 
 670 
 
 390 I 
 
 8 i 
 
 315 
 
 473 
 11*7 
 
 2530 ! 
 6i*7i J 
 
 1*521 
 7li* ! 
 
 8551 J 
 335 v 5 
 611*95 
 52U10 I 
 
 N P 
 s c 
 
 1* 
 
 6 
 
 7 
 
 5 
 
 6 
 7 
 8 
 
 1 
 
 6 
 6 
 
 9 
 8 
 66 
 36 
 10 
 90 
 
 51* 
 
 ?7 p 
 
 51 
 
 156 
 
 561* 
 
 9^8 
 
 3350 
 
 231*0 
 
 2k 
 
 1260 
 
 2365 
 
 588 
 
 1265O 
 
 38826 
 
 3161+7 
 
 3570 
 
 51306 
 
 23 c 02 c; 
 
 491960 
 
 1 
 
 9 
 
 36 
 
 72 
 
 84 
 
 252 
 
 501* 
 
 126 
 
 501* 
 
 756 
 
 I.512 
 
 3021+ 
 
 63O 
 1260 
 
 2520 
 
 3780 
 
 7560 
 
 15120 
 
 1680 
 
 5040 
 
 1^080 
 
 7560 
 
 15120 
 
 30 
 
 601*80 
 22680 
 45360 
 90720 
 l8l44o 
 
 N P 
 s p 
 
 o r ai 
 
 172958 
 
 1 
 -f- 
 
 9 j 471.690 {36^880 
 1349228 
 
 1 
 
 27 
 
 108 
 I 
 216 
 
 336 
 
 4^36 
 
 630 
 
 151.20 
 
 13608 
 
 14061.6 
 
 151200 
 
 10710 
 
 65520 
 
 35; 
 
 895860 
 
 5065200 
 
 5896800 
 
 13440 
 
 1587600 
 
 476^840 
 
 1111320 
 
 38253600 
 
 195683040 
 
 27343OO8O 
 
 1.6193520 
 
 387873360 
 
 304^924000 
 
 11157652800 
 
 19018540800 
 
 3415365s 
 
 31* 
 
 
Table 5«3 shows the symmetry types of canonical pos ■'. r-.elf-dual 
 
 threshold functions, ow many groups of symmetrical variables each of 
 the canonical positive self -dual threshold functions has, and ir numbers, 
 
 A set of optimum weights which includes the maximum w is 
 :, 18, 15, 13, 10, 8, h, 3 
 
 A set of optimum weights which includes the maximum w is 
 28, 22, 20, 19, 18, 15, Ik, 12, 11. 
 
 ? 
 
 The maximum of the optimum total input weight, i.e. L w. 
 
 1 
 was 209. The set of optimum weights (unique) for this function is 3^-, 
 
 32, 28, 2 V , 2k, 20, 18, 15, 11 (T = 105). The minimum is of course 9. 
 
 Each of the optimum weights for the 175* ^28 threshold functions 
 are added up and are shown in Table 5 k with the average size for each 
 weight, For functions which have multiple extreme optimum solutions, 
 average optimum weights were added (i.e. since all these functions have 
 only two extreme optimum solutions, the optimum weights at *he middle 
 point, were addec . ) 
 
 •Twelve canonical positive self -dual threshold functions of 
 exactly 9 variables were discovered to have multiple extreme optimum 
 solutions, although none of those of 8 or fewer variables had multiple 
 solutions. These are listed in Table 5-5° Each function has only single 
 pair of symmetrical variables whose weights are encircled [f encircled 
 weights are interchanged, the other extreme optimum solution is obtained. 
 
 Two functions were discovered to have an extreme optimum solution 
 which included fractional weights. Both solutions were unique extn 
 optimum, ones. These are shown in Table 5-6. When a function has multiple 
 
 reme optimum solutions of integral, weights, we may have an extreme 
 optimum solution having fractional weights in the last tableau which were 
 not originally extreme solutions but were brought in by the constraints 
 (3.10). Of course such functions v/ere not counted. 
 
 Each time we discover a set of optimum weights for a generated 
 
 canonical positive self -dual threshold func-ion of up r o 9 variables, we 
 
 checked how many of the extremal inequalities used for the primal linear 
 program 
 
 35 
 
TABLE 5A AVERAGE SIZE OF WEIGHTS 
 
 
 Total sum 
 
 Average size 
 
 w l 
 
 3,367,^9 
 
 19.2 
 
 W 2 
 
 2,6^3,212 
 
 15.1 
 
 W 3 
 
 2,150,516.5 
 
 12. 3 
 
 w 4 
 
 1,762,3^1 
 
 10.0 
 
 W 5 
 
 1,^2,171 
 
 8.2 
 
 v 6 
 
 1,145,993-5 
 
 6.5 
 
 W T 
 
 882,375.5 
 
 5-0 
 
 w 8 
 
 628,050,5 
 
 3.6 
 
 W 9 
 
 379,9U6 
 
 2.2 
 
 36 
 
CANONICAL POSITIVE SELF-DUAL THRESHOLD FUNC5 
 IPLE EXTREME OPTIMA SOLUTIONS 
 
 C how ; s Fa r ame r e r 
 
 83, 33, 31, 
 
 87, 33, 31, 
 
 72, 44, 32, 
 
 79, 41, 31, 
 
 77, -3, 31, 
 
 68, 52, 32, 
 
 66, 54, 32, 
 
 • 53, 3 7 , 
 
 66, 54, 36, 
 
 59, 47, ■ 
 
 65, 55, 4l, 
 
 64, 56, 40, 
 
 31, 19, 19, 19, 13, 13 
 25, 25, 21, 9, 7, 7 
 
 32, 30, 18, 18, 12, 12 
 31, 23, 23, 11, 9, 9 
 
 31, 25, 25, 9, 7 , 7 
 
 32, 22, 22, 22, 8, 8 
 
 32, 24, 2k, 20, 6, 6 
 
 27, 2 7, 19, 19, 7, 7 
 
 28, 28, 20, 18, 6, 6 
 
 33, 25, 25, 19, 19, 7 
 
 31, 23, 15, 15, 5, 5 
 
 32, 24, 16, 14, k, k 
 
 One set of extreme o; wei ghts* 
 
 13, 7, 6, 6, 4., 4, l,Q0 
 
 17, 9, 8, © 5, 3, 2, : 
 
 13, 9, 7 , 7, 6, k, 4,00 
 
 14, 9, (3 © 5, 5, 3, 2, 2 
 
 17, 12, 8, 8, © © 3, 2, 2 
 11, 9, 6, 6, k, 4, 4,0 
 13, 11, 7, 7, 5, 5, 4,©Q 
 13, 11, 8, 6, 6, 4, 4,0 
 
 15, 13, 9, T , 7 > 5. S©,© 
 13, ll, 10, 8, 6, 6,0©, 2 
 
 16, 14, 11, 9, 6, 4, 4,0© 
 
 18, 16, 12, 1.0, 7, 5, 4, 
 
 * The other set of ex r reine optimum weights is obtained by interchangirg 
 encircled weights. 
 
 37 
 
TABLE 5-6 CANONICAL POSITIVE SELF-DUAL THRESHOLD FUNCTIONS 
 
 WHOSE EXTREME OPTIMUM SOLUTIONS INCLUDE FRACTIONAL 
 
 WEIGHTS 
 
 Chow f s Parameters 
 
 Unique Optimum Weights* 
 
 
 66, 54, 40, 30, 24, 16, 16, 6, 6 
 65, 55, 39, 31, 25, 17, 15, 5, 5 
 
 14.5, 12.5, 9-5, 7-5, 6, 4, 4, 1.5, 1.5, T - 
 16.5, 14.5, 10.5, 8.5, 7, 5, 4, 1.5, 1-5, T = 
 
 = 31 
 : 35 
 
 * T is a threshold 
 
 
 38 
 
 
■Jl_.|_i|_il_lt_ l |_i|_i|_.|_j|_. 
 
 ^j \) m o^O CO~J Cn^ -p-uorot-'OV£>CO--jaVv-n -P-OJ 
 
 rt 
 
 £ 
 
 fl> 
 
 t 
 
 a 
 
 4 
 
 ■n 
 
 & 
 
 X 
 
 r 
 
 H- 
 
 D 
 
 C 
 
 • 
 
 p 
 
 B 
 
 - 
 
 0! 
 
 -i 
 
 o 
 
 a- 
 
 
 H 
 
 
 m 
 
 
 ..... 
 
 
 d 
 
 | 
 
 4 
 
 
 
 H- 
 
 H 
 
 r 
 
 
 
 
 
 
 
 
 ■q 
 
 p. 
 
 
 
 
 D 
 
 
 
 
 i-t 
 
 
 
 1 
 
 
 
 D (11 tf 
 
 Hj 
 
 a 
 
 
 ►O X cc 
 
 c 
 
 
 
 C d <j 
 
 a 
 
 § 
 
 "- 1 - oraM 
 
 03 -i P- 
 
 o 
 
 ry 
 
 H uu a^'"V)00•f--vl0^t- , v^lOo-p-^- , 
 
 h <d a 
 
 r^ 
 
 1) 
 
 M^n 4^-ujvo MVOvnvo ON VO *-* 00 >"\3 -jvn h-> 
 
 P S (X) 
 
 |-J. 
 
 t-j 
 
 M •F-vJII-'OOO-^-J -p-vooovo r-j HW mui^ w 
 
 <-t CD 
 
 O 
 
 
 H i- 1 .o -slu) CD^O^O -J u \ii 3) -J "0 a ^ -J -0 O -P~ C7\ 00 vn 
 
 H- i- 1 3 
 
 a 
 
 o 
 
 
 ft 
 
 CD 
 
 Hi 
 
 
 a 
 
 
 
 H ro £- CT\— J -J n i.jo m 
 h 'J v^ vo ^i vo vn P-MDCTN-Joovjioii- 1 
 
 oroHooocouiOMr-j^oroworf-ro poo^ 
 
 H O O0Q\w 0>ODO\-P-VO^!00'- J 
 "-■P-OOVO JONOOOWONONOC'-'f'^OU) 
 
 X) f~ -J VO -J jJ H 
 
 LaJ rO f 35 00U) H nI^O\ <.»j \. 
 . O w Onw uj iu H ^">jvn OMOuJVO Ji i'O O O O 
 
 ^ ro PC\ t- 
 ^ f ^ -J O) D r o jim 
 ^ D \D O CT\VO . 3 H 
 
 O D'-'^o >ovO ^ >J -JUOCDt-C-O-NO-NO'-' O 3 O 
 
 H WW 
 iX> _n r -~l w V CD m 
 Jn M- 1 v£> 00 *-■ ON "- 1 ONVO i\3 
 O OOoovO O -J ON^n 00 VQ ~1 •-<) O O 'O j D ^ 
 
 
 t -Aj 
 
 I" 
 
 3> H ONOW 
 
 I 
 
 "o od o ' vo <-• 
 
 ju r, n j vo /i „■ Co n 
 
 o o o o 
 
 O O ^o 
 
 H J H 
 
 C-.nCDH XvO H O O 
 
 .5 J> O 
 
 £" 0C 
 
 DOHIViOVOOM- 1 DO 
 
 O O O H • J _> 3 D D 3 
 
 i 
 
 ON 
 
 00 
 
 1 
 
 VO 
 
 • 2 
 
 cn 
 
 TO 
 
 a 
 
 S 
 
 o 
 
 CD 
 
 E 
 
 g 
 
 H 
 
 C+ 
 
 B 
 
 c 
 
 H- 
 
 a- 
 
 c- 
 
 r^ 
 
 CD 
 
 CD 
 
 -r. 
 
 p> 
 
 Ha 
 
 4 
 
 hi 
 
 O 
 
 P- 
 
 
 
 a 
 
 P 
 
 ^-^ 
 
 O 
 
 
 u. 
 
 3 
 
 Hi 
 
 
 cr 
 
 t 
 
 Hj 
 
 
 <<: 
 
 
 
 C 
 
 5 
 
 
 rp 
 
 i— i 
 
 rj 
 
 
 d 
 
 o 
 
 - 
 
 
 1 
 
 
 ^ 
 
 
 P- 
 
 
 □ 
 
 
 O 
 
 
 
 a 
 
 
 * 
 
 Pi 
 
 [0 
 
 
 P- 
 
 T) 
 
 s! 
 
 
 a 
 
 X 
 
 3' 
 
 
 'D 
 
 d 
 
 p. 
 
 
 >n 
 
 hi 
 
 o 
 
 
 c 
 
 ; 
 
 -T 
 
 
 05 
 
 i=f 
 
 
 
 H 
 
 
 :r 
 
 
 P' 
 
 i— i 
 
 P 
 
 
 c+ 
 
 
 g* 
 
 
 <<: 
 
 J 
 
 a 
 
 T 
 
 
 T 
 
 D 
 
 d 
 
 
 ••<: 
 
 iQ 
 
 n' 
 
 
 
 C 
 
 I 
 
 
 CD 
 
 CS 
 
 
 
 •j 
 
 i— i 
 
 Hi 
 
 
 
 P° 
 
 O 
 
 
 o 
 
 -* 
 
 H 
 
 
 •d 
 
 - 1 - 
 
 ^ J 
 
 
 ■i 
 
 D 
 
 Q 
 
 
 H- 
 
 -n 
 
 « 
 
 
 S 
 
 
 • 
 
 o 
 
 . 
 
 39 
 
■ o ' 
 
 o o o o o o o o o o o o o 
 
 EH 
 
 <y 03 
 
 o 
 
 EH O 
 
 
 
 
 r- 
 
 
 2- 
 
 
 
 
 
 ►■-• 
 
 c 
 
 
 
 
 
 
 
 
 2 
 
 
 cj 
 
 QC 
 
 
 
 
 
 
 
 
 -l ( 
 
 
 1 
 
 
 « 
 
 o 
 
 Ph 
 
 H O 
 
 
 H -f--' 
 
 o 
 
 c 
 
 
 Ch bf ! 
 
 
 C 
 
 s 
 
 
 H 
 
 
 a 
 
 G 
 
 > ra 
 
 - 
 
 CO 
 
 en 
 
 j. - 
 o H 
 
 •H H 
 
 ! 
 
 
 
 
 
 1 
 
 l 
 
 
 
 
 O O O O O O O O O H o o 
 
 
 1 
 i 
 
 i 
 
 i cc 
 1 
 
 1 
 
 
 
 
 OOOOOOOJ-NCNOCMHO 
 
 c c 
 
 i 
 1 
 
 
 
 
 O O O H -f CT> O 
 
 — 1 LI 
 
 ■; c 
 
 h° 
 
 
 
 o 
 
 OO OrHVCrnOnHWCJ-JOJH 
 MH ON CC; O POH 
 
 <— i r— ! f— | H 
 
 rH O 
 
 i 
 
 
 o 
 
 c 
 
 O O H OO ij u-.n mH\C 0\0 4 H 
 CM CM u -. On u . O -H V. 
 
 H '.' ■ .--i 
 
 O O 
 
 
 
 o 
 
 o 
 
 O ON O NO CC NO CO Oi ltn O- H CVi NO or. 
 CO OJ NO On : or- on CM 
 on CO or- _J ON LT\ CM 
 
 r-l H 
 
 O C 
 
 1 
 
 1 rv. 
 
 ; 
 
 o o 
 
 o 
 
 ltn 
 
 O LTN NO LT> NO ON O. NT O ON LTN LTN O r-| 
 On NO CM t~ J O GO CO ON 0, H 
 Oi CO O ON ,d NO LP NO CM 
 
 CM i ' |r| 
 
 o o 
 
 & 
 
 I 
 
 cy 
 
 3 . 
 o a 1 B 
 
 O O O ONVO t>-00 POCMNOOiOoOH-cf-H-H/LrNCMOO 
 CM On onoo ltn On C H C- r- • u^ J- CO m 
 r-l co_j- c on ir r- cm vo no cm 
 
 CM LT\ C— t~- I 
 
 
 4~ U- 
 O ( 
 
 w 
 
 a> a 
 
 a 
 
 "0 no ONC--ONONH oOnO LP -4" r-i or.. CO ON CO 
 OO NO C\- O CC_-t- C b-ONOO-COr-iHVOCM 
 r-i r- oo _t oo On Li - 1 1 PO LT> CM 
 
 CM LT-ON H rH CO LTN CM r-i 
 
 r-l -H 
 
 o o 
 
 — I 
 
 tr\ co --j- oo cm CM 0" co cm mj- o mn rooj-* o- - H O -4 
 CM U"N CM 1 .-=f CO O ONLI 4 LTN C— I s - C»- ON LTn C oo lt\ cm H 
 H LTy LTN _H/ OO OCC >- LTN H 4" CMVD OO H 
 H OONO cOOnCC NO -4- OJ r-l 
 
 C r-l 
 
 •H l/j 
 
 S H -r) 
 
 bj t3 -h 
 
 ,c a ri i-, cd 
 
 p 3 
 
 o a 
 o 
 
 X cr 
 
 T:' ti- 
 
 lt- O)n0 4 O r-r- CMCC CM C-~- CO LP, 
 
 CM U > LP H O-N ,-H h- J- ONfO ON-J 
 
 rH LP f~ CM CO rH ON VO ON LTN ON 
 
 H -i CO ltnH NO o- J- CO 
 rH CM H 
 
 H C- On On CO oo C-- 
 
 0- [-- OO C rH LP -H; 
 
 rH ON <y~ .4 LTn H 
 CM ^O OO H 
 
 H 
 
 o- h H 
 
 
 <t-. r; <u 
 
 c . ■ u. 
 
 E 
 
 I 
 
 I r-i tf} 
 
 rQ rH T3 B 
 S-r' 3 <U -H 
 
 3 X a 1 
 
 tU 3 Pi 
 
 oo -J- lp no r- CO On O n CM 
 
 "1 LP NO 0- CO ON C H CM or; 
 
 H r—l rH rH r-1 rH r-l CM CM ' ' 
 
 he 
 
are . 
 
 :"or all canonical : i i :'-dual are 
 
 able 5«7« Duld be read as follows 
 
 numbered 6 con- a::.- >f extrei 
 
 prii near program (6), mical pog . 
 
 threshold ' 9 or fewei 
 
 cal poi 
 fund 1 6 ex- I by equal - 
 
 ( 33 r - ' i ber of self -or 
 
 >nly one of 1 brid v - 
 
 equality (8*-l), oi two of the 6 ex 
 
 tremal inequalities are s LnequalU 
 
 -5 only one I 2^ inequ* Litiei by 
 
 equal 1- OJ 9, 3, 7, 6, '" • , . 
 
 As discussed in Sec xl ^responding 
 
 to the exl ce the extrec 
 
 - prime ate ■ .- fron 
 
 implican-f in - wo 1 Is are eliminated 
 
 ns ic prirr-- Lmplicants - ds< • 
 
 -e or rror- of a generated function maj from thf 
 
 ■ s of the primal linear program. 
 
 T acle owe how ne Long hs specii of 
 
 extr Lmplican 5 among ] ■ • , . mal 
 
 ' progr-. . 3r examp] , rov numb< 
 
 con;-:rs mber of e> 
 
 r o s ( 6 ) , 1 oj 
 
 self -dual :- o^ 9 0> 
 
 j (L23~), the number extrins 
 
 ( Z 1 -^ • Der of the J 
 
 ("26), 
 
 !9) 
 
 nation i f Section 3 ver< 
 ess, ?2i of - 
 
 of 6 
 4. 
 
 -i 
 
Cable 5-9 shows how the whole distribution of the number o^ 
 canonical positive self -dual functions of 9 or fewer variables vs. 
 number of extremal inequalities would change if the first elimination 
 method were fully adopted at the expense of complexity of the pi re. 
 
 our computer program of Table ^„3> the first elimination method was 
 no- adopted and in 'his case rV e average number of inequalities per linear 
 prograrr is 10.8 as shown in the bottom row of Table r 9„ f the first 
 elj on method were added, "he average numter would be lowered to 9.6. 
 • is about a 10$ reduction. This means that computation time, for simplex 
 mett; .Id be reduced by a greater percentage t v ar, 10$ " J owever the 
 :i *cg c of full incorporation of the firs' elimination method is not 
 clear "because the procedure of comparison of Lnequal differ 
 
 in more than T wo coefficlert? is also time, consuming. 
 
 As seen in Tatle 5 7 > six functions have . . which 
 satisfied by s"r:c* ir.equal J .ty by an optimum solution. Bu r if we i 
 Table ^.8, we wiU find that some of these strict inequalities are eliminated 
 as the ine a corresponding to extrinsic prirre implicants. In this 
 
 se these are interesting funcior.s, T et us discuss one of these six 
 functions as an example 
 
 The eel r ~ dual threshold function expressed by the follo A r irg optimum 
 we :' gh s ( u n i que optimum solu tion) ; 
 
 23, 1 7 ~ IS 13, 11, 9, 7 , 5, 3 (T = 52) 
 
 Lme i ,r pl ".cants, 35 of which are extrinsic and. 1? of which are 
 in r rinsic. Py elin Lon of inequalities, 2 n ex^erral inequalities are 
 
 left In *he primal linear program and the corresponding dual linear program 
 is solved by the simplex rrethod, By the optimum solution obtained, 10 of 
 these inequalities are satisfied by equality and the remaining 10 by si 
 Inequality. However 8 of these 10 s^ inequalities can be eliminated, as 
 
 ■ r e inequalities corresponding to extrinsic prime implicants but r r^ r^ - 
 Lg 2 strict inequalities correspond, to intrinsic p^ime implicants 
 
 As defined in refinit : on 3-?, decision of whether a prime trr - 
 plicant :s extrins or intrinsic requires comparison of the. corresponding 
 
 pie with o^^ minimal true n-tuples of f. We ascertained by a computer 
 program that even if minimal true n-tuples are compared only with other 
 
 12 
 
HMOF OF "ION OF THE N\MBEF ^NS 
 
 '■IE! N'JMBEF OF OJEQ . BY 
 
 OF THE FIRST EI IMINATION MI 
 
 . . 
 
 Whe a ls1 me t hod 
 
 were 
 
 When 1st rre bhoc 
 
 
 I Of fX' 
 
 1 
 
 i ine jual It 
 
 i fully adopted 
 
 
 no* adopted 
 
 I 
 
 1 
 
 
 1 
 
 . 
 
 lUSfd i 
 i 
 
 Mm), 
 
 m N (m) 
 
 N 2 (i . 
 
 m N (m) 
 
 i prime 
 
 1 
 
 Number of 
 
 functions— 
 having a 
 
 - ies 
 
 1 
 1 
 
 1 
 
 [ Number of 
 functions 
 having rr 
 Inequalit ies 
 
 
 * 
 
 ■ 
 
 1 
 
 
 1 
 
 1 
 
 5 
 
 ! 
 
 5 
 
 c 
 
 2 
 
 30 
 
 60 
 
 28 
 
 56 
 
 3 
 
 185 
 
 555 
 
 156 
 
 468 
 
 4 
 
 7 2 c 
 
 2900 
 
 554 
 
 2216 
 
 5 
 
 2525 
 
 12625 
 
 1710 
 
 8550 
 
 6 
 
 6998 
 
 ^1988 
 
 37 
 
 25422 
 
 7 
 
 15658 
 
 IO9606 
 
 881^ 
 
 61719 
 
 8 
 
 26621 
 
 212968 
 
 15172 
 
 l 51376 
 
 9 
 
 ^L7}7 
 
 312453 
 
 948 
 
 197532 
 
 10 
 
 33562 
 
 335620 
 
 56692 
 
 2669-0 
 
 11 
 
 2T037 
 
 275407 
 
 27937 
 
 307 
 
 12 
 
 : r i88 
 
 182256 
 
 24598 
 
 295176 
 
 13 
 
 ^922 
 
 102986 
 
 18945 
 
 246285 
 
 14 
 
 ■ 
 
 3728 
 
 52192 
 
 ■ 
 
 >394 
 
 15 
 
 1530 
 
 22950 
 
 6977 
 
 104655 
 
 16 
 
 629 
 
 10061 
 
 3339 
 
 S3I 
 
 17 
 
 229 
 
 3893 
 
 1409 
 
 7 C ~ 
 
 18 
 
 92 
 
 I656 
 
 516 
 
 9324 
 
 19 
 
 31 
 
 589 
 
 153 
 
 2907 
 
 20 
 
 11 
 
 220 
 
 ^ 
 
 94^. 
 
 
 4 
 
 84 
 
 13 
 
 
 
 
 
 
 
 
 
 
 1 
 
 23 
 
 1 
 
 1 
 
 23 
 
 al 
 
 175^28 
 
 1681100 
 
 175^28 
 
 18989- 7 
 
 " 1 
 
 - 
 
 
 
 1 
 
 
 1 ber of in- 
 
 
 9 6 
 
 1 
 
 1 
 
 10.8 
 
 ^s 
 
 
 
 
 
 ! per 
 
 
 
 
 
 -3 
 
minimal true n-tuples which are left after application of the second elimj - 
 nation method, instead of all minimal true n-tuples, they could be determined 
 
 correctly as extrinsic or intrinsic ones at least for canonical posi*t T 'e 
 self -dual threshold functions of 9 °r fewer variables 
 
 Table 5-10 shows the number of extremal inequalities for - v e 
 cases of 8, 1, 6, ^, k, variables, extending ^able 5°7« There is at leas - 
 one self-dual threshold function of six variables which has an extrinsic 
 prime implicant eliminated by the generation method or the elimination 
 method in our program, These functions are not counted in Table c ,10 (c). 
 
 re was no 3 -monotor i : self -dual function of exactly 9 variables 
 
 which was no* a threshold function. By Theorem 2.1, Corollary 2,2, and 
 
 (2 
 
 Winder's res -It of 8 or fewer variable case 
 
 it means that there is no 
 
 completely monotonic self-dual function of exactly 9 variables which is 
 not a threshold function and also that there is J no completely monotonic 
 
 function of 8 or fewer variables which is not a threshold function, There- 
 
 (10) 
 fore as Gabelman had srown , for 9 variables there appears for the first 
 
 time a completely monotonic function which is no* a threshold function. 
 
 The computer program which we wrote in !\" T CAP for ILIiIAC II contains 
 various error checking procedures, All strongly asymmetrical threshold 
 
 r iors of exactly 9 variables are printed out and compared witr. T re. self- 
 dual T ^reshold functions of exactly 8 variables, This pertly served to insure 
 tha r -he generation program generated all 9 variable functions, because 
 strongly asymmetrical canonical posi*iv c threshold functions of exactly n 
 variables have one-* o-one correspondence with canonical positive Threshold, 
 functions of exactly (n - l) variables, as shown in r neorerr. 2,3 
 
 following criterion based on computed optimum weights instead, 
 of Boolean expression of Ief : ru*lon 2.1 was- used r o find strongly asyrrme trical 
 thres v old fun: t i one 
 
 w 2 + w 2 > v 
 
 "} " W ? > W 
 
 w 9 >0 
 
 w, + 
 4 
 
 T .nfortuna r ely r he second inequality w, - w > w is not a necessary condition 
 
 U 
 
 
TAEI: BER OF EXTFEMAL INEQUALITIES 
 
 (a) f extremal inequalities satisfied as strict inequality for 
 
 canonical positive self -dual threshold functions of 8 or fewer 
 variables , 
 
 al number 
 
 Number of 
 
 
 
 
 tn of extre^c.l 
 
 functions 
 
 
 
 
 inequalit ies 
 
 having m 
 
 
 
 
 used in IP 
 
 extremal 
 
 
 
 
 
 
 
 
 1 
 
 2 
 
 
 inequalit ies 
 
 
 
 
 1 
 
 k 
 
 k 
 
 
 
 2 
 
 18 
 
 18 
 
 
 
 3 
 
 72 
 
 72 
 
 
 
 k 
 
 
 171; 
 
 
 
 5 
 
 3^3 
 
 335 
 
 8 
 
 
 6 
 
 ii88 
 
 k6l 
 
 27 
 
 
 7 
 
 5^6 
 
 kl6 
 
 69 
 
 1 
 
 8 
 
 ki 3 
 
 339 
 
 72 
 
 2 
 
 9 
 
 256 
 
 188 
 
 61 
 
 7 
 
 10 
 
 ill 
 
 7^ 
 
 31 
 
 6 
 
 n 
 
 36 
 
 27 
 
 6 
 
 3 
 
 12 
 
 8 
 
 6 
 
 1 
 
 1 
 
 13 
 
 1 
 
 1- 
 
 L 
 
 ! 
 
 total 
 
 2Uvq 
 
 21.75 
 
 275 
 
 20 1 
 
 Number for 7 or fewer variables 
 
 Teal number 
 m of ex'.rf 
 inequalit ies 
 
 used ir 
 
 j Number of 
 
 ! furctions 
 
 1 u 
 
 i naving m 
 
 i extremal 
 
 i "' r>e qualities i 
 
 1+5 
 
TABLE 5.10 NUMHEE OF EXTREMAL EKEQmLITIES (cont.) 
 
 c) Number for 6 or fewer variables 
 
 Total number 
 1 m of ex r remal 
 I ine qua! ities 
 
 used ir. LP 
 
 I Number of 
 unctions 
 
 having m 
 i extremal 
 i ine qualities 
 
 i 
 
 
 3 
 
 3 
 
 2 
 
 6 
 
 6 
 
 3 
 
 8 
 
 8 
 
 k 
 
 3 
 
 3 
 
 c 
 
 1 
 
 1 
 
 total 
 
 21 j 21 
 
 (d) Number for 5 or fewer variables 
 
 Total number 
 m of extremal 
 Lnequalil ies 
 used in 
 
 Number of 
 
 functions 
 having m 
 extremal 
 
 inequalities 
 
 
 
 (e) Number for I or fewer variable; 
 
 Total numbe - 
 m of ex'rerral 
 ; 1 1 qual i ties 
 used in 
 
 ! Number of 
 fund ions 
 having m 
 
 ' x r remal 
 
 j re qual it ies 
 
 46 
 
for the c Lon 2 o: oition 2.1 to be true. Therefore we may miss 
 som< jr.gly asynnnetrical threshold functions although the functions 
 
 .e above three inequalities are certainly strongly asymmetrical 
 inctiona However these functions picked up by the above 3 in- 
 equalities showed one-to-one correspondence with the canonical positive 
 old functions of exactly 8 variables. In conclusion, 
 
 (1) For nine variables, the above three inequalities are a necessary and 
 ficient condition that a canonical positive self -dual threshold function 
 a strongly asymmetrical self -dual threshold function. 
 
 (2) rongly asymrr.e - rical self-dual threshold function of 9 or fewer 
 variables has a unique optimum solution. 
 
 (?) When 
 
 o o o 
 w 2 > w 2 - w 3 
 
 > v > 
 7 
 
 are optimum weights of a strongly asymmetrical self-dual threshold function, 
 
 1 ° °\ ° 
 
 (w - w_ ) , w_ , 
 
 3 
 
 • • - 9 
 
 are also optimum weights for the corresponding self-dual threshold function 
 of exactly 3 variables This property holds for 8 and fewer variables. 
 
 Computation time of our computer prograrr of Table U„3 was abou*" 
 10 hours of HI 11 C1 includes time for auxiliary programs like those 
 Lg programs and intermediate printings. rhe program was run 
 to prove error -free computation. 
 
 hi 
 
6 LINEAR PROGRAM TO MINIMIZE A 5JHRESHOLI 
 
 In this section, the linear program to minimize a threshold will 
 be die cussed , 
 
 Let us define a linear program corresponding ^o the threshold 
 expression, as folio "s 
 
 Minimize T 
 
 (6.1) 
 
 - - f he constre 1 * s 
 
 I ,. x. u) : 
 
 
 i i 
 
 w 
 
 , > (i o 1, 2, . . . ,n) 
 
 for 
 
 f(x^ j) 
 
 ,x (J) ) ■ 1 
 
 7 n 
 
 (6.2) 
 
 (6.3) 
 
 a.',:. 
 
 I w. x. ( J } < 
 i=l 
 
 l l 
 
 1 for f(x. 
 
 (j) 
 
 ' X n ; 
 
 (6J0 
 
 for & posil • )n f Minimization of I has some engineering mo + 
 Ion. ve max ion of input tolerance (Revision of 
 
 proof of pape] ( L) -ill be given els* « : ), yielding iro' 
 
 reliable operation of threshold elements., inequalities, (6.3) and (6„^) 
 are called a ncorma sys r err of_ inequa.] ' • ; e s in r hr g s v Did expression . 
 
 Note ' y f • : |ualities in majority expression (1 c ) arc. (1.6), 
 ■ he converted into (6.^) and (6.k) respectively, by the onversion 
 formula 
 
 .a/ £ 
 o 
 
 L w. f 1 - 2 r 
 1-1 X 
 
 (6.5) 
 
 and vice versa 
 (6.5), when £ 
 
 objective function, (6.1), is equivalent *o (1.3) ty 
 
 -1 or w = Put they are d.if f erent when £ = +1, '; 
 o " o 
 
 l& 
 
n 
 
 ■ r wor - linear program to minimize E w. of (1.3) through (I06) 
 
 1=0 1 
 equivalent *.o the 11 rear program to minimize T of (6.1) through (6.4), 
 
 if a given function is a minor function or a self-dual function. If the 
 
 (11) 
 
 function is a major function, these two linear programs are not equivalent, 
 
 they have different solutions for some major functions. For example, 
 an optimum solution of the linear program to minimize T for the major 
 funct ion 
 
 f(x,, x g , x ) = x 2 v 
 
 x 2 x 3 
 
 If 
 
 w 2 > 2, 
 
 o o ,_0 
 
 - ■ w = 1 and T = 2, 
 
 Le its optimum solution for the linear program to minimize Z w. is 
 
 i=0 x 
 . 1, 1; w £ =l) which is unique. In other words, the linear program 
 
 for this f defined by (6.1.) through (6.k) has multiple optimum solutions, 
 
 while -ir:a T defined by (1.3) through (1.6) has a unique, solution. 
 
 I is easy r o prove the. following which was observed by Y. Yen. 
 
 Theorem 6. - e linear program to minimize T, (6.1) through (6.4) for a 
 positive threshold function has optimum weights of unbounded magnitude if 
 and only function contains a prime impl leant consisting of a single 
 liters . 
 
 Therefore at leas'', for these functions which have single literal 
 Lmplicants, the linear program to minimize T has different optimum 
 solutions from those of 'he linear program to minimize W, (1,3) through 
 (1 6), since the latter l:" c 6r program always has optimum weights, of finj 
 magnitude 
 
 Table 6,1 shows the number of canonical positive major threshold 
 :' ions (NPB classes) of exactly n variables and also shows how many of 
 m have at least one single literal prime implicant , 
 
 A computer prograrr. was written for investigating how many of 
 n)) of Table 6.1 have different optimum structures in threshold 
 
 h9 
 
PABLE 6.2 K V BEP 0^ ! CANONICAI POSITIVE MAJOR THRESHOLE FONCTIOME 
 
 ani NUMBER of those which have single literai prime 
 
 EMPI ECANTS 
 
 M(n), 
 
 Number of 
 
 canonical 
 J positive 
 ; major *-hresl ■ 
 
 i old functions 
 of exactly n 
 variables 
 
 2 
 8 
 
 LI 
 U90 
 
 1,3^9,228 
 
 S(n), 
 
 how many of 
 M(n) have at 
 least one 
 single lit- 
 eral prime 
 i replicant 
 
 
 
 1 
 
 2 
 
 5 
 
 17 
 
 92 
 
 99 k 
 
 28,262 
 
 M(n) - S(n 
 how many of 
 do not have 
 literal prim 
 implicants 
 
 - 
 
 13, 
 1,3 • 
 
 
 
 
 
 3 
 
 H 
 
 398 
 080 
 
 966 
 
 50 
 
expression from those in majority expression. The 1 - number of the "interesting 
 
 fund :>f 8 variables, 1, 320, 966, is unfortunately too big to handle. 
 
 vest igat ion --as limited only to the case of the functions of 7 or 
 
 fewer variables 
 
 - linear programs to minimize T, (6,1) through (6 ,k) , were 
 
 formula'ed for all canonical positive major threshold functions of 7 or 
 
 fewer variables except those with single literal prime, implicants. After 
 
 solving these linear programs by simplex method, it is checked whether the 
 
 optimum solution (w , . . . , w : T ) obtained in the last tableau is 
 
 l n 
 
 identical T .o the optimum solution (w , . . . ,w , w^ £_) of the linear 
 
 
 
 
 
 program of (1-3/ 'hrough (1.6), by the conversion formula, (6.5)0 
 
 s whole computer program is also written in NICAP, ILL LAC 
 assembly language 
 
 As was s< Table 6,1, 3 (^ variables), 2 V (5 variables), 398 
 (6 variables) and 13,080 ( 7 variables) major functions were actually in- 
 vestigated T o find whether they have different structures in threshold 
 expression and majority expression. Table 6.2 shows the result of this 
 igation 
 
 Totally 320 functions of 7 or fewer variables are found which do 
 no* have single liberal prime implicants and which have a different optimum 
 structure in * nreshold expression from an optimum structure in majority 
 expression. All of -hose s~r:. bave the following properties 
 
 Ltiple and bounded 
 
 (2) ore of the extreme optimum solutions agrees. 'he structure derived 
 fro:: al majority stru< . by the conversion formula (6-. 5)- 
 
 functions cf 6 variables with multiple solutions are listed, in Table 
 6,3 '■'-■ this table 1 is any number in the shown range. For example w 1 
 of rs 1 row is any number between 6 and 7 , These 3! 1 * fun 1* ions of 
 7 variables which hav ipie optimum solutions, are classified into 
 eight "ypes in Table 6 h. These fairly crude classifications are cho: 
 only to demonstrate a few of the general patterns observed in the. list of 
 ariable functions r er * ypp 1, w may be any number between a and a + 1 
 a is the. numbe : -rrined for each fine* ion w = 2, w <. a and 
 
 51 
 
I = a + 2 for all functions in this type. x_ x is a prime implicant 
 bu: x x is not. For the type 3 both w., and u may be any numbers be- 
 tween a and a + 1, but not necessarily w, = w . Type 8 is a miscellany 
 
 roes not belong to the previous 7 types and whos< all functions are 
 shown in L< 6,5 = The firs- function of type 8 in "able 6 J -as w which 
 may be ar number between 1 3 and 11 but threshold is not related in 
 a way as in type ] Table 6.5 shows some examples of functions of 
 .pes of Table 6,4» For t rpes, 3> 7 ? and 6, all functions are e 
 
 52 
 
-j on vn -P" oo ru 
 
 ■p- O -P" 
 
 CD W ^ O 
 
 VO 
 
 4=- 
 
 VO 
 
 ~j vn ro H 
 
 •P- 
 
 CTn O 
 
 o 
 
 T 
 
 CD 
 
 H- 
 
 Co 
 
 O' 
 
 M 
 
 n 
 
 o ct"d 
 
 co tr p. 
 o o <j 
 
 i-" a, 
 
 o 
 
 Hi 
 
 a" in 
 
 Hj 03 O 
 
 C c-i. pj 
 
 3 O 3 
 
 O M O 
 
 c- 13 
 
 O 
 3 
 
 
 3 
 
 o 
 
 tn h> 
 
 rn l— i t* 
 CD H- 
 
 a, o h 
 
 o? -. 
 
 - ■* 
 4 
 Co 
 
 
 -1 
 
 en c 
 c+ 3 
 
 O C 
 
 - 1) 
 
 T> CD 
 C_j. 
 
 O 
 
 H- 
 C+ 
 
 ro 
 
 1 P 
 
 Ho 
 
 «j 
 
 D 
 
 3 
 O 
 3 
 i 
 
 fji 
 o 
 
 p. 
 
 < 
 Co 
 
 (— i 
 D 
 
 3 
 
 ►d 
 
 4 
 
 pg 
 
 3 
 
 CO O 
 H 
 P* 
 
 4* 
 
 D 
 
 3" CD 
 4 3 
 
 m o 
 
 -r at? 
 o 
 
 £ ' s 
 a, ^-^ 
 
 3 
 Co v_. 
 
 3 
 
 c 
 
 3 
 
 Co 
 
 C_i. 
 
 O 
 4 
 H- 
 
 rr 
 
 I o o o o o o o 
 
 f> C 
 
 CO Cr ^-> 
 
 ►Q 3 
 
 c+ 3 OO 
 
 (3 H- 
 
 
 H-..Q 
 
 <; c 
 
 -5 =! ^ 
 
 CO T 
 
 ct co s* 
 £ c. 4 
 
 H 
 
 a, ~, 
 
 4 o -* 
 
 3 C 
 
 -* ^ on 
 
 • 
 
 rn m. J3- 
 
 
 
 3 
 
 cf^ H 
 
 O 
 
 O CL 
 
 << v 
 
 - 
 
 '.-■ 
 -i 
 
 D 
 
 3" 
 
 
 ■^1 
 
 UO 
 
 
 ON 
 
 VO 
 
 ro 
 
 On 
 
 o 
 
 -j 
 
 LaJ 
 
 CD •-« 
 DO H 
 
 CO c+ ' 
 
 ^ . 
 
 E0 -d s 
 
 pr a- r ' 
 
 o i- 
 
 P> 3 3 
 
 g 
 
 3 
 OS 
 
 c c: 
 
 3 3 
 
 n cr 
 s o 
 
 •— 3 O I 
 
 3 r n Mj, 
 
 . 
 
 i 
 
 ON 
 
 "O 
 
 a 
 
 53 
 
TABLE 6.3 MULTIPLE OPTIMUM STRUCTURES OF FUNCTIONS OF 6 VARIABLES 
 
 w l 
 
 w 2 
 
 W 3 
 
 w 4 
 
 W 5 
 
 w 6 
 
 T 
 
 6 ~ 7 
 
 4 
 
 3 
 
 3 
 
 2 
 
 2 
 
 8 
 
 5 ~ 6 
 
 4 
 
 3 
 
 3 
 
 2 
 
 2 
 
 7 
 
 7~8 
 
 5 
 
 k 
 
 3 
 
 2 
 
 2 
 
 9 
 
 6 ~ 7 
 
 5 
 
 h 
 
 3 
 
 2 
 
 2 
 
 8 
 
 5 ~ 6 
 
 3 
 
 3 
 
 2 
 
 2 
 
 2 
 
 7 
 
 U ~ 5 
 
 3 
 
 3 
 
 2 
 
 2 
 
 2 
 
 6 
 
 54 
 

 
 i 
 
 
 
 
 
 
 
 
 
 
 
 1 
 
 
 
 (V 
 
 o. 
 
 0. 
 
 on 
 
 
 
 
 
 
 
 + 
 
 + 
 
 + 
 
 + 
 
 i 
 
 
 
 c_ 
 
 
 PO 
 
 
 £> 
 
 £> 
 
 ^ 
 
 X> 
 
 
 
 
 
 + 
 
 + 
 
 + 
 
 + 
 
 + 
 
 + 
 
 + 
 
 
 
 
 
 1 
 
 CD 
 
 aj 
 
 00 
 
 CO 
 
 ai 
 
 CO! 
 j 
 
 
 
 
 I 
 1 
 
 
 
 
 
 
 
 i 
 
 
 
 
 1 _ 
 
 
 
 
 
 
 
 i 
 
 c 
 
 
 
 
 
 
 
 
 
 
 i 
 
 1 
 
 
 
 
 
 
 
 
 
 
 1 
 
 
 > 
 
 OJ 
 
 m 
 
 CJ 
 
 ^> 
 
 
 
 ,o 
 
 
 £g 
 
 
 
 
 
 
 
 
 
 
 i 
 
 X o 
 
 
 
 1 
 
 
 
 
 
 
 
 i 
 
 5 fa 
 
 
 
 
 
 
 
 
 
 
 i 
 
 fa 
 
 
 
 
 
 
 
 
 
 
 i 
 
 ^ . 
 
 
 
 
 
 
 OJ 
 
 
 
 m 
 
 i 
 
 
 
 
 
 
 
 
 
 
 
 
 i—. "=£ 
 
 
 \c 
 
 
 
 
 + 
 
 ,£■ 
 
 
 + 
 
 
 CD fa 
 
 
 > 
 
 
 
 
 
 
 
 
 
 sa 
 
 
 
 
 
 
 £> 
 
 
 
 H 
 
 ex i-q 
 
 
 
 
 
 
 
 
 
 
 < 
 
 
 
 
 
 
 
 
 
 
 L 1 
 
 > PC 
 
 
 
 
 
 
 
 
 
 o 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 cv 
 
 
 i i 
 
 i 
 
 
 
 u- 
 
 
 
 
 
 + 
 
 ,a 
 
 
 i 
 
 c a 
 
 
 5 
 
 
 
 
 
 
 
 
 i 
 
 
 
 
 
 
 
 
 & 
 
 
 
 i 
 
 . 
 
 
 
 
 
 
 
 
 
 
 i 
 
 . 
 
 
 
 
 
 
 
 
 
 
 i 
 
 
 
 
 
 
 
 
 
 
 
 
 ■ 
 
 
 
 
 
 
 
 
 
 
 
 : 
 
 
 
 
 
 
 
 
 
 
 . N 
 
 . 
 
 
 
 
 
 
 
 
 CM 
 
 
 U"\ 
 
 fs 
 
 
 
 
 
 
 
 
 
 
 • 
 
 2 
 
 
 -3- 
 
 
 
 
 
 
 + 
 
 
 VO 
 
 5- 
 
 
 3 
 
 
 
 
 
 
 ,Q 
 
 
 (L 
 
 
 
 
 
 
 
 
 
 
 
 H 
 
 
 
 
 
 
 
 
 
 
 
 cO 
 
 
 
 
 
 
 
 
 
 
 - c 
 
 
 
 
 
 
 
 
 
 
 EH 
 
 • 
 
 
 
 
 
 
 
 
 
 
 
 - 
 E fa fa 
 
 
 
 
 
 
 
 
 
 
 CD 
 
 
 3 
 
 
 
 
 
 
 
 
 a, 
 03 
 
 e- m to i 
 
 
 
 
 
 
 
 
 
 ■ 
 
 ' -— 
 
 2 
 
 
 
 
 
 H 
 
 
 
 
 
 >2 
 
 
 
 
 
 + 
 
 
 
 
 
 ni 
 
 I 
 
 
 
 
 
 
 
 
 
 
 cO 
 
 ££ s ! 
 
 
 
 
 
 CO 
 
 
 
 
 
 H 
 
 H 
 
 >H <q O 
 
 
 
 
 
 / 
 
 
 
 
 
 0) 
 
 FH W En l 
 
 i 
 
 
 3 
 
 
 
 cO 
 
 
 
 
 
 CJ 
 
 en 
 
 * 
 
 
 
 1 — 1 
 
 
 H 
 
 H 
 
 H 
 
 H 
 
 OJ 
 
 
 H 
 
 
 
 
 
 
 
 
 
 
 
 
 
 + 
 
 + 
 
 + 
 
 + 
 
 + 
 
 + 
 
 + 1 1 
 
 1 
 
 
 
 CO 
 
 CO 
 
 CO 
 
 CO 
 
 CO 
 
 CO 
 
 CO 
 
 I 
 
 i 
 
 
 H 
 
 
 
 
 
 
 
 
 
 i 
 l 
 
 
 3 
 
 
 I 
 
 ? 
 
 I 
 
 ? 
 
 ? 
 
 I 
 
 ■ 
 
 ! 
 
 i 
 
 
 
 cd 
 
 CO 
 
 CO 
 
 cO 
 
 CO 
 
 CO 
 
 cO 
 
 
 
 u 
 
 C 
 O 
 
 
 
 
 
 
 
 
 
 
 
 •H 
 
 c 
 
 OJ 
 
 MD 
 
 VD 
 
 CO 
 
 o 
 
 -J- 
 
 CO 
 
 
 & 
 
 
 o 
 
 OJ 
 
 
 J 
 
 H 
 
 <H 
 
 
 
 
 a 
 
 o o 
 
 0. 
 
 
 
 
 
 
 
 
 | 
 
 j 
 
 G 
 
 
 
 
 
 
 
 
 
 i 
 i 
 
 c 
 
 3 
 
 
 
 
 
 
 
 
 
 I 
 
 
 0/ 
 
 
 
 
 
 
 
 
 
 
 
 a 
 
 
 
 
 
 
 
 
 
 
 
 :>> 
 
 —i 
 
 : 
 
 OO 
 
 -=t 
 
 LTN 
 
 VO 
 
 r- 
 
 CO 
 
 i 
 
 
 4-> 
 
 
 
 
 
 
 
 
 
 55 
 
TABLE 6.5 EXAMPLES OF THRESHOLD FUNCTIONS SHOWN IN TABLE 6.k. 
 
 type 
 
 1 
 i 
 
 
 opt 
 
 imum 
 
 weights 
 
 T 
 
 1 
 
 6 ~ 7, 
 
 5, 
 
 ^ 
 
 ^ 
 
 3. 
 
 3, 
 
 2 
 
 8 
 
 2 
 
 L_ 7 ~ 9, 
 
 6, 
 
 5, 
 
 ^ 
 
 k 
 
 3 
 
 3 
 
 10 
 
 
 5 ~ 6, 
 
 
 6, 
 
 *, 
 
 3. 
 
 3, 
 
 2, 2 
 
 7 
 
 
 6 ~ 7, 
 
 6 ~ 
 
 7, 
 
 5, 
 
 k. 
 
 3, 
 
 2, 2 
 
 8 
 
 3* 
 
 h ~ 5, 
 
 ij. ~ 
 
 5, 
 
 3, 
 
 3, 
 
 2, 
 
 2, 2 
 
 6 
 
 
 7 ~ 8, 
 
 7 ~ 
 
 8, 
 
 
 k_ 
 
 3, 
 
 2, 2 
 
 9 
 
 
 5-6, 
 
 5 - 
 
 6, 
 
 3, 
 
 3, 
 
 2, 
 
 2, 2 
 
 7 
 
 
 6 ~ 7, 
 
 6 ~ 
 
 7, 
 
 ^, 
 
 _1 
 
 3, 
 
 2, 2 
 
 8 
 
 k 
 
 6 ~ 7, 
 
 K 
 
 *, 
 
 3, 
 
 3. 
 
 3> 
 
 1 
 
 9 
 
 5 
 
 8 ~ 9, 
 
 7, 
 
 6, 
 
 5, 
 
 
 3> 
 
 3 
 
 13 
 
 6 
 
 10 ~ 11, 
 
 9; 
 
 7, 
 
 6, 
 
 Jl 
 
 k } 
 
 2 
 
 16 
 
 
 13 - 15, 
 
 9, 
 
 7, 
 
 6, 
 
 k, 
 
 k, 
 
 1 
 
 17 
 
 7* 
 
 11 - 13, 
 
 9, 
 
 7 , 
 
 6, 
 
 k> 
 
 k, 
 
 1 
 
 15 
 
 
 11 ~ 13, 
 
 7, 
 
 6, 
 
 
 i, 
 
 k, 
 
 1 
 
 15 
 
 
 _ 9 ~ 11, 
 
 7, 
 
 6, 
 
 5, 
 
 hj 
 
 k } 
 
 1 
 
 13 
 
 
 10 ~ 11, 
 
 9, 
 
 8, 
 
 5, 
 
 3> 
 
 2, 
 
 2 
 
 17 
 
 
 8-9, 
 
 6, 
 
 
 5, 
 
 2> 
 
 2, 
 
 2 
 
 12 
 
 i 
 
 7 - 8, 
 
 6, 
 
 5, 
 
 5, 
 
 2; 
 
 2, 
 
 2 
 
 11 
 
 1 r, 
 
 8* 
 
 9 - 10, 
 
 7 , 
 
 6, 
 
 5, 
 
 2, 
 
 2, 
 
 2 
 
 13 
 
 
 8~9, 
 
 7, 
 
 6, 
 
 5, 
 
 2, 
 
 2, 
 
 2 
 
 12 
 
 
 9, 7 ~ 
 
 8, 
 
 5, 
 
 5, 
 
 3> 
 
 2, 
 
 2 
 
 ik 
 
 
 9, 6~ 
 
 7, 
 
 5, 
 
 5, 
 
 3, 
 
 2, 
 
 2 
 
 13 
 
 1 
 
 9, 8, 
 
 6 ~ 
 
 v , 
 
 5, 
 
 3; 
 
 2, 
 
 2 
 
 13 
 
 * All functions of types 3)7 and 8 in table 6.h are shown here 
 
 56 
 
7 . CONCLUSION 
 
 number of threshold functions of 8 variables and the number 
 al pos ^elf-dual threshold functions of 9 variables are 
 courrec Lnteresting properties which did not show up for the case of 
 fewer ^eriatles are s For example, for the linear program to minimize 
 the total in: Lght there are threshold functions of exactly 8 variable e 
 which have multiple optimum solutions while all threshold functions of 7 
 or fewer variables have unique optimum solutions, Also, there are threshold 
 functions of exactly 8 variables which have extreme optimum we igh* s of 
 fractional numbers while all threshold functions of 7 or fewer variables 
 have integer optimum weights. It is proved that there is no completely 
 monotonic function of exactly 8 variables which is not a threshold function. 
 
 Also multiplicity of optimum solutions for the linear program 
 to minimize threshold was investigated. 
 
 case of 9 variables considered in this paper would be of 
 practical limit for computation. ILLIAC IV which is being designed at 
 the "niversity of Illinois will be very fast. Probably the number of 
 canonical positive self-dual threshold functions of 10 variables would be 
 on the border line between being computable and non-computable with ELLIAC 
 IV. 
 
 - 1 arbors are grateful to Dr. I. Toda for his inspiring discussion 
 at the early stage of this work. 
 
 57 
 
REFERENCES 
 
 (1) Muroga, S., Foda, 7. , and Kondo, M., Majority decision functions of 
 up to six variable?, Math Com put . , Vol. 1.6, Oct. I962, pp , 459-^72. 
 (published in Japanese in 1959 and 1960), 
 
 (2) Winder, R. 0., Enumeration of seven-argument threshold functions," 
 I.E.E.E. Trans, on Elec. Comp ., Vol. EC-14, No, 3, June I965, pp. 
 315-325. 
 
 (3) Muroga, 
 
 Functional forms of dual -comparable functions and a 
 
 necessary and sufficient condition for realizability of a majority 
 
 function", I.E.E.E. Tran s. on Comm. and Elec , Sept., 196^, pp. 
 
 klk-kB6. 
 
 (k) Muroga, S., Foda, I., and Takasu, S., 'Theory of majority decision 
 elements, J ournal of Frank lin Institute , pp. 376-k-l.Q, May I.96I. 
 I ,'apanese version was presented in Journal of Inst , of Elec Comm, Eng. 
 of Japan , Oct. and lee 1960). 
 
 (5) For example, Hadley, G , linear Programming, Addison-Wesley, I962. 
 
 (6) 
 (7) 
 
 (8) 
 (9) 
 
 (10) 
 (11) 
 (12) 
 (13) 
 
 Winder, F. , Properties of threshold, functions, " : . E.F •£. Tran s 
 on Elec. Comp. , Vol. EC-14, No, 2, Apr. 1965, pp. 252-25*4-. 
 
 Muroga, 
 
 Generation and asymmetry of self -dual threshold functions 8 ', 
 
 I.E.E.E. Trans on Elec . Comp , Vol . EC-14, No 2, Apr., 1965, pp* 125 = 
 
 I36, The ^beorerr statement is corrected in Pheorem 2.3 here. 
 
 The property s*a T ed in this theorem was somewhat implicitely discussed 
 as Processes C and I in the paper (k) . 
 
 Baugh, C. R., A linear progr amming code to de termine whether a B ool ean 
 function is a th r esho ld function, Nov. 28, I966, Master Tegree Thesis, 
 lep'. of Corr,pu t er Science, niv of 111., Urbana, 111. 
 
 Gabelman, I, J,, T he functional behav ior of majo rity elements, 
 Doctoral dissertation for Syracuse '.niv., E. E. Dept., June 1961. 
 
 Muroga, S., Majority logic and _pr obi ems of probabilistic behavior in 
 self -organizing systems, Spartan Books, 1962, pp. 2^-3-281. 
 
 Rohr , J . A . , M ajo r and minor threshold functions of six va riables , 
 Merer legree rhesis, Dept. of E. E., T 'niv. of 111 , June I96 7 . 
 
 Dertouzos, M r . , rhreshold logic, a synthesis approach, M. I.T. 
 
 Press, 1965, 
 
McNaughton, F be Truth Functions, :i I.E.E.E.. Tr ans, on Elec . 
 Comm ., pp 1-6, Marcr. 1961. 
 
 Goto, E. and Takahashi, Ho, Threshold, majority and bilateral 
 
 I ing devices, Switching theory in space technology , pp , k'jS'J, 
 ford Univ. Press, 1963. ' 
 
 Perkins, D. T., Willis, E. G., and Whitmore, E. A,, unpublished work 
 at Lockheed Aircraft Corp. 
 
 Winder, R 0., "Single stage threshold logic', Symp. of switchin g 
 theory an d Logica l Eesign , pp, 321-332, Sept, I96I. 
 
 Cameron, S. F , An estimate of the complexity requisite in a universal 
 
 decision network, Bio nics Symp. V APE> Report 60-600 , pp. 197-212, 
 
 Eec. i960. 
 
 Yajima, S., and Ebaraki, T., "A lower bound of the number of threshold 
 functions," E.E. E.E. T rans , on Elec. Comm., pp. 926-929, Dec. 1965 . 
 
 Smith, D. R,, ''Bounds on the number of threshold, functions, ° : I.E.E.E . 
 Trans on Elec, C o mm. , pp. 368-369, June I966. 
 
 ga, S , and Toda, 1., Lower bound of the number of threshold 
 functions," E „E. Trans- on E lec. Comm.,, pp„ 8O5-8O6, Oct. 1966. 
 
 Tor the definition of basic concepts, see (2), (3), (k) , (17) and 
 Lewis, R. M. and Coates, C„ L.: Threshold logic, Wiley, 1967= 
 The following is an excellent survey of threshold logic in general. 
 Winder, R. 0.: Tee status of threshold logic, The Firs 1 : Annual Princ* • 
 *on Conference on Information Sciences ana Systems, Princeton, March, 
 196 . 
 
 59 
 


Mr—mrmnnnm iwiinw inmTnfM immWHIBini 
 
uma 
 
 j 011 * 004249840 
 
 
 
 
 
 
 
 
 
 vi }' 
 
 
 [\i\\ [iWiti IH.liJ 
 
 ■;:. i,."!' ';; lv^ "Itri