APPLICATIONS OF LATTICE THEORY TO THRESHOLD LOGIC.
Abstract
The pertinent results of threshold logic are summarized and a brief introduction to lattice theory is given. Complete monotonicity is equivalent to a total ordering, chain condition, in the lattice of switching function residues under all possible valuations. Partial conditions are related to the k-monotonicities and such considerations reduce the effort in checking complete monotonicity; the cases for 3 and 4 (hyper-) monotonicity are explicitly discussed. The Hasse diagram of the n-cube lattice with a switching function mapped on it is manipulated to establish a regular (positive 2-monotonic function with lexico-graphically ordered arguments) function which for n not too large may be checked for complete monotonicity. Threshold functions are also characterized in terms of the lattices of convex cones and functions not linearly separable have sublattices representing minimally inconsistent systems of inequalities. Such characterizations lead to an alternate form of summability, termed t-joinability. Logical conditions equivalent to 3 and 4-summability are given and from these conditions and the t-joinabilities sufficiently of complete monotonicity for linear separability for functions of less than 9 arguments may be seen. The Hasse diagram of the n-cube lattice may be used as a geometric tool in the heuristic synthesis of two level threshold gate network. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1966
- Accession Number
- AD0801011
Entities
People
- Garth H. Foster
Organizations
- Syracuse University