This paper is a broad treatment of Chow parameters--a set of n+l integers which can be abstracted from any given n-argument switching function.Basic properties and alternative definitions of these numbers are established and correlated with several earlier works in the subject.The main results are as follows: The class of "unique" functions--those with unique Chow parameter N-tuples--lies properly between the classes of threshold functions and the class of completely monotonic functions.The class of "extremal" functions-with locally minimal or maximal single parameters --lies properly between the class of unique functions and the class of unate functions (and these inclusions cannot be tightened in terms of other k-monotonicities).A closely related question recently raised is settled.Quadratic bounds and an infinite family of linear bounds, all tight, are obtained.A smooth well-behaved surface exists which encloses only the Chow parameters of nonthreshold functions and whose tangent hyperplanes define realizations of the function whose parameters lie outside the point of tangency.

Let Rnmbe the number of linearly separable n-argument functions specified on some m points of the n-cube. Let R̄nmand Ṟnmbe, respectively, the minimum and maximum values attained over all choices of the m points. It is known that R̄nmn/n!. 1) Two published "simplifications" of the argument which establish this upper bound are shown to be fallacious. 2) It is proved that Ṟnm≥4m(lg m−1)/2. 3) It is proved that if m is less than exponential in n, then as n→∞, R̄nm≈(m/n)n + lower order terms. 4) Let Lnmbe the maximum number of threshold gates needed to realize an arbitrary n-argument switching function specified on m points. It is shown that Lnm≳2(m/lg m)1/2.

This paper is based on the following idea. If the two residues xi⋅ f(x) and } x̄i⋅ f(x) are realizable, respectively, with p and q threshold gates, then f is realizable with at most p+q gates. And conversely, if the residues require separately at least r gates, then so does f. Thus, given a table of minimal realizations for 4-argument functions (which require at most three gates), realizations for 5-argument functions can be obtained which are demonstrably minimal or close to it, by considering the five different pairs of residues.

The problem of choosing a standard circuit package with which to realize a given logic design can be solved for threshold logic design by the use of majority gates. However, the use of asymmetric threshold gates allows substantial improvements in the amount of logic done per signal pin of the circuit package. Examples are given, illustrating savings in logic design effort, total cost of integrated circuit packages, and total cost of printed circuit boards.

Seven methods are compared for deriving approximate realizing weights and threshold for a threshold function, given its Chow parameters. These include use of the parameters themselves, methods published by Dertouzos and the author, and several new methods. The comparison is made over all seven-argument self-dual threshold function types, and establishes a certain "geometric rule" as best. One third of the types were exactly realized by the approximation, and the average number of mistakes was very small.

The idea of ``similarity'' between threshold functions is developed in a unified fashion and illustrated geometrically. Formulas are given to transform the corresponding threshold gate realizations.

It has been pointed out Prof. S. Muroga that the entry in Table V of the above-named paper (ibid., vol. EC-14, pp. 315-325, June 1965) for the number of nondegenerate threshold functions of 7a rguments is incorrect. The original author notes that he neglected to include the self-dual functions making the correct entry: 8 274 797 440. Also, Prof. J. Sklansky has pointed out a mistake in the AFCRL report, "Threshold Functions Through n = 7" (see AF Cambridge Research Labs., Bedford, Mass., AFCRL Rept, 64-925, under Contract AF19(604)-8423 with RCA Labs., October 1964.) On page 1, the formula for Chow parameters is corrected. It should also be noted that the column "E" in the latter report does not represent the number of extremals as claimed; more inequalities can in some cases be eliminated by further monotonicity checks.

Where previous authors have considered linear approximations with a minimum sum of squared differences, we consider, instead, Chehyshev linear approximations, which minimize the maximum deviation. We obtain thus: 1) A new characterization of threshold functions, 2) A characterization of optimal threshold realizations as being virtually identical to the Chebyshev-best linear approximations, and 3) A new insight into the test-synthesis problem with which we opened this note.

A tabulation of the 2470 representative threshold functions of seven arguments has been prepared by the author. This paper discusses the methods used in, and the threshold logic implications of, the enumeration. The self-dual classification method of Goto-Takahasi was employed. A lattice was defined on the 8-cube in terms of which all 2-monotonic, canonical, self-dual functions of eight arguments were directly generated. Each such representative function was then treated by a modified form of the Muroga-Toda-Takasu linear programming test-synthesis procedure to obtain minimal 1-realizations. The Chow parameters for each function were calculated, and the final enumeration was ordered lexicographically by these parameters to afford a trivial test-synthesis procedure for n≤7. The enumeration demonstrated that minimal 1-realizations are still integral for n≤7; it corroborated Cobham's result that complete monotonicity is equivalent to 1-realizability, and established hyper-2-monotonicity as a useful characterization, for n≤7. It significantly extended our knowledge of the number of threshold functions and the various symmetry types, the size of weights and threshold required, the number of iterations required by the linear program, and similar statistics.

This paper presents methods for realizing simple threshold functions of n arguments by networks of k-input majority gates, where k≪n. An optimal network realization of the 5-argument majority function using 3-input majority gates is given, and it is then generalized by steps with realizations for the (2n-l)-argument majority function (where n = 3, 4, ...) using (2n-3)-input majority gates, and then for the (2n-1)-argument majority function using (2k-l)-input majority gates (where k≪n). In a final generalization an array network using (2k-l)-input majority gates introduced for the realization of an (m/n), ``simple,'' threshold function (where m = 1, 2, ...,n). The array network is then applied to the synthesis of arbitrary symmetric functions; in the latter synthesis a realization of ``adjustable logic'' is given where, by simple control of network connections, the same network can be made to compute any symmetric function. The specific networks for ``5 by 3's'' (5-argument majority function realized by a 3-input majority gate), ``7 by 5's'', and ``7 by 3's'' are the best known.