Single stage threshold logic

Abstract

This paper discusses properties of an often encountered class of switching functions: those whose outputs are determined by the sign of a linear combination of numerical equivalents of the inputs, i.e., a weighted summation followed by a threshold discrimination. Any function can be realized by a network of such devices; those functions realized in Just one stage we call realizable. A general property of realizable function, complete monotonicity, is derived and split into useful special properties, k-monotonicities. Several theorems develop these concepts further, l-monotonicity is shown equivalent to the idea of unateness, and two useful properties of 1-monotonic functions are derived. An ordering of the variables of a 2-monotonic function is defined and shown equivalent to the numerical ordering of the weighting coefficients in any realization of the function. An effective test for checking the order by inspection is established. Examples include a function of E. F. Moore, which demonstrates that a completely monotonic function needn't be realizable. A canonical Boolean form for realizable functions, with an effective procedure for enumerating all realizable functions, is developed. Test-synthesis algorithms for completely- and incompletely-specified functions are given, generalizing from R. McNaughton's treatment. The number of realizable functions of n arguments is shown not to exceed 2Σ0n (2n-1 i).