DocumentCode
3264383
Title
Truth functions realizable by single threshold organs
Author
Elgot, Calvin C.
fYear
1961
fDate
17-20 Oct. 1961
Firstpage
225
Lastpage
245
Abstract
A threshold function is a mapping from {0, 1}n into {0, 1} satisfying: there exists integers w1, w2,..., wn, t such that f(x1, x2,..., xn) = 1 iff Sigmai=1n wi xi geq t. Two chains of conditions necessary for a function to be a threshold function are discussed. Early parts of the two chains are equivalent. One chain constitutes a sufficient condition while it is not known whether the other more intrinsic condition is sufficient or not. It is shown that any set of threshold functions of n variables realizable by a common set of weights is included in a maximal chain of threshold functions of length 1 + 2n realizable by a common set of weights. If f depends on at most 5 variables or if f or its dual has at most 4-prime implicants, then f is a threshold function iff it is 2-monotonic.
Keywords
Sufficient conditions;
fLanguage
English
Publisher
ieee
Conference_Titel
Switching Circuit Theory and Logical Design, 1961. SWCT 1961. Proceedings of the Second Annual Symposium on
Conference_Location
Detroit, MI, USA
Type
conf
DOI
10.1109/FOCS.1961.39
Filename
5397278
Link To Document