On the characterization of threshold functions

Abstract

This paper derives a set of parameters which characterize functions realizable with single threshold devices. A Boolean function of n variables is a function on the vertices of an n-dimensional cube to 0 and 1. Considering the vertices as n-dimensional vectors, the ordinary vector sum (or the center of gravity) of the true vertices and the number of true vertices determine the realizability. It is proven that, if the characterizing vectors and the numbers of the true vertices of two functions are respectively equal, then either both functions are realizable or both are not realizable and, if one of the functions is realizable, then both functions are identical. Because of the uniqueness, these characterizing parameters can be used to label known threshold functions. The use of this label in conjunction with a procedure of reducing functions to a standard form provides a convenient means of ascertaining whether an arbitrary function is one of the known threshold functions. Some simple properties of the characterizing parameters are described: the characterizing parameters give directly the algebraic signs of, and the ordinal relations among, the weights to realize a threshold function; the characterizing vector is minimal with respect to a partial ordering. Results on a class of threshold functions are given.