• 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