Accession Number : AD0801011

Title :   APPLICATIONS OF LATTICE THEORY TO THRESHOLD LOGIC.

Descriptive Note : Interim rept. Jun 63-Jun 66,

Corporate Author : SYRACUSE UNIV RESEARCH INST NY

Personal Author(s) : Foster, Garth H.

Report Date : SEP 1966

Pagination or Media Count : 128

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)

Descriptors :   (*MATHEMATICAL LOGIC, ALGEBRA), FUNCTIONS(MATHEMATICS), INEQUALITIES, SPECIAL FUNCTIONS(MATHEMATICAL), NETWORKS, THEOREMS.

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE