More about threshold logic
- 1 January 1961
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
We pursue in this paper some of the ideas discussed a year ago at the First Annual Symposium on Switching Theory and Logical Design. For a general discussion of threshold logic, and for definitions and motivations of the terms used below, the reader is referred to "Single Stage Threshold Logic" also published in this volume [13]. Also, a general survey of recent papers in the subject has been published elsewhere [14]. The main subject treated below is compound synthesis. The importance of such a study was shown last year: The family of functions of n arguments realizable in a single stage becomes a vanishing fraction of all switching functions of n arguments as n grows (for n = 7 the ratio is about 1028 1/2). We provide an algorithm for determining "2-realizability" -- reallzability with two threshold elements. The general approach produces a good solution in any case, but one guaranteed optimal only for 2-realizable functions. We use here a geometric terminology; this new language is also used in the second section, where "higher" necessary conditions for realizability are discussed. A conjecture that certain of these conditions might be sufficient is disproved; three related conditions are treated in a common language. The final section considers optimal integral single-stage realizations, and disproves a conjecture made last year: That such a realization gives equal arguments equal weights.Keywords
This publication has 6 references indexed in Scilit:
- Theory of majority decision elementsJournal of the Franklin Institute, 1961
- Unate Truth FunctionsIEEE Transactions on Electronic Computers, 1961
- Linear-Input LogicIEEE Transactions on Electronic Computers, 1961
- Axiomatic Majority-Decision LogicIEEE Transactions on Electronic Computers, 1961
- A Theorem for Deriving Majority-Logic Networks Within an Augmented Boolean AlgebraIEEE Transactions on Electronic Computers, 1960
- Systems of Linear InequalitiesAnnals of Mathematics, 1922