PROPERTIES OF THRESHOLD FUNCTIONS OF MORE THAN EIGHT VARIABLES,
AND THEIR DETECTION
by
SURESHOHANDER
Thesis submitted to the Indian Institute of Technology, Delhi for the award of the Degree of
DOCTOR OP PHILOSOPHY
Department of Electrical Engineering Indian Institute of Technology, Delhi
July, 1974
CERTIFICATE
Certified that the thesis "Properties of Threshold Functions of More than Eight Variables, and their Detection", which is being submitted by Shri Sureshchander for the award of the degree of Doctor of Philosophy to the Indian Institute of Technology, Delhi, is a record of student's own work carried out by him under my supervision and guidance. The matter embodied in this thesis has not been submitted for the award of any other degree or diploma.
July) , 1974
J\.5 Dr.
\_ (\ 4.C(P. Batt Assstant Professor Computer Center
Indian Institute of Technology New Delhi
ACKNOVLE,D GEMENT
The author expresses his deep sense of gratitude and thanks to Dr. P.C.P. Bhatt for introducing Threshold Logic to him, and for his overall guidance during this work.
The thanks are due to the Ministry of
Education, Govt. of India, and G.B. Pant University of Agriculture and Technology, Pantnagar for
providing the financial support under the quality improvement programme. In particlar, thanks are due to Dr. D.P. Singh, Vice-Chancellor, Dr. M.
Chaudhury, Dean, Technology, Prof. P. Kundu and Shri O.S. Mishra, Registrar, all of the G.B. Pant University of Ag. & Technology, for their keen interest in sponsoring the author for the Ph.D.
programme. Thanks are also due to his colleagues, in the Electrical Engineering Department of the University, for having agreed to share his duties during his absence from the University.
The author is grateful to Prof. J.C. Shouri, Head, Computer Center, Indian Institute of Technology, and others of this Computer Center for their co-
operation during his stay here. Special thanks are, however, due to Dr. M. Ibramsha for his keen interest in his work, and sugge3tions.
The author, also, thanks the Q.I.P. office and in particular, Prof. C.S. Jha, Co-ordinator, QIP, for the liaison work.
Last but not the least, the author expresses indebtedness, also, to all those, whose names do not appear here, for their co-operation during his stay here.
SYNOPSIS
The gates based on threshold decision principle hold•:.promise in the synthesis of logical systems, especially digital computers. The popularity'of these gates has been rather limited because of poor signal to noise ratio-, and the fact that precision components are required to implement threShold ogic gags,
116wever, with advances in technology, especiallY.inthe field of ICs, it should be possible to have reliable and inexpensive threshold gates in the near future,
The properties of switching functions which are threshold or 1-realizable have been extensively studied
by various research workers for n 8, where n is the number of variables in a switching function® The threshold functions of nine or more variables have not been studied in any meaningful way as their properties are almost unknown. The reason why a function of nine or more variables should be tested for 3-asummability, besides 2-asummability, (for checking for 1-realizability) has not been known so far. However, this fact has been established by .exhaustive enumeration and counter examples The functions of nine or more variables could not be
studied because of_enormous computation required to test m-asummability, strictly spe'aking, m here; is unbounded;
though m is finite for finite ni i.e:, there exists an m such that if a function is m-asummable, then it is also k-asummable, for k,im. But unfortunately the bound on m has not been established so far, in general.
In this thesis, properties of threshold functions have been investigated, in general. In particular, this study is devoted to properties of threshold functions of nine or more variables. The necessary and sufficient conditions for the 1-realizability of functions upto 15 variables have been obtained. The reason for restricting the study upto 15 variables is due to the fact that no mathematical relationship between m and n, in general, could be found. However, a condition has been established under which an (m 1)-asummable function may become
m-summable function. Further, this condition has been used to find the values of m for functions upto 15 variables.
It was found that 3-asummability is a necessary and sufficient condition for 1-realizability for 9 and 10 variable functions, whereas functions must be tested for 4-asummability for n = 11, 12 and 13, and for 5-asummab- ility for n = 14 and 15.
The S
T class of functions, viz., the threshold (13)
functions, is a subset of the S class of functions
(Definition 2.2,2), i.e., ST S0. It is easier to test for membership in the Sc class of functions than in the S class of functions. It is of advantage to know the condition(s) under which both these classes are identical. It has been shown that S0 = S
T for n x..14
The property of superunateness has been introduced to test the asummability of switching functions.
Superunateness, along with other properties of threshold functions (described in this thesis), has been used to construct tables for testing 3-asummability of switching functions of 9 and 10 variables. These tables have
reduced the overall computational effort, for checking 3-asummability, by a factor of -106 and about 67,000 for 9 and 10 variables respectively.
A new property has been described, i.e,, a pivot- vertex (there are only two pivot vertices for each n), defined in this thesis, should be TRUE if a pseudo-major and pseudo-canonical function is to be 1-realizable.
This is a very useful property for preliminary checking of functions for 1-realizability.
Also, fast techniques have been proposed for testing 2-asummability as testing for this property is required for all n.
In the course of this investigation, certain othertroperties of switching functions have been, also, examined. These are of advantage in testing for
1-realizability of switching functions, also. The algorithms so developed are for testing i) unateness, ii) redundancy of variables, iii) partial and total symmetries, and iv) for minimization of switching
functions. These algorithms are given in the appendices 9
CONTENTS
1. INTRODUCTION 1
1.1. Introduction 1
1.2. Definition of a Threshold Gate 2 1.3. Identification of Threshold
Functions 4 1.4. This Thesis 7
2. THRESHOLD FUNCTIONS, AND PROPERTIES AND TESTING OF THRESHOLD FUNCTIONS
OF FEW VARIABLES 11
2.1. Introduction 11
2.2. Definitions and Theorems 12 2.3. Testing for 2-Asummability -
a Unified Approach 23
2.3.1. Testing for Dual-Monotonicity 23 2.3.2. Testing for Monotonocity 25
2.3.3® Testing for 2-Asummability Using both Monotonicity and Dual-Monotonicity 27, 2.3.4. Effect of Theorem 2.2.15 on Checking 2-Asummability 29 2.4. Ale/ 7:e Algorithm for Testing
Asummability of Boolean Functions 30 2.4.1. Definitions and Theorem 31 2.4.2. The Algorithm 35
2.4.3. Methods 35 2.4.4. Algorithms 37 2.4.5. An Example 39
2.5. Conclusions 40
3. SUPERUNATENESS AND ADVANCED
PROPERTIES OF THRESHOLD FUNCTIONS 42 3.1. Introduction 42
J lei.
3.2. Ayperunateness 43 3.3. Use of L
2 Tables 52
3.4. Theorems on 2-Asummability 62 3.5, Testing for 2-Asummability using
Superunateness and Advanced
Properties of Threshold Functions 71 3.5.1. Testing of d-Dual-
MOnotonicity 72 3.5.2. Testing for d-Dual-
Comparability of
SUperunate Functions 74
3.5.3.
Testing for 2-Asummability of Superunate Functions 803.5.4.
Further Remarks on Testing of 2-Asummability 833.5.5.
Minimal Testing for 2-Asummability85 3.6.
Conclusions 864. THRESHOLD FUNCTIONS OF MORE THAN
EIGHT VARIABLES 88
4.1. Introduction 88
4.2. Properties of Threshold Functions 90 4.2.1. Advanced Properties of
Threshold Functions 91 4.2.2. Properties of Ayperunate Threshold Functions
99
4.2.3.
Bound on m for a Given n 106 4.2.4, Construction of Examples 111 4.2.5. SC and ST Classes ofSwitching Functions 114 4.3. Conclusions 116
5. CONCLUSIONS 118
Appendix A. TESTING OF UNATENESS AND
DUAL-COMPARABILITY 121 A.1. Testing for Unateness 121 A.2. Checking for Dual-
Comparability 132
Appendix B. TESTING FOR REDUNDANCY 134 Appendix C. TESTING FOR SYMMETRIES 137 Appendix D. A FAST TECHNIQUE FOR MINIMIZATION
OF SWITCHING FUNCTIONS 142 D.1. Introduction 142
D.2. Definitions and. Theorems 144 D.3. The Method 149
D.4. Example 154
D.5. Generation of (I.) Terms 156 D.6. Conclusions 159 J
Appendix E. L2 TABLES 161 Appendix F. TABLES FOR CHECKING
3-ASUMMABILITY OF 10-VARIABLE
FUNCTIONS 177
REFERENCES 201
