On the characterization of threshold functions
On the characterization of threshold functions
复制标题
关于阈值函数的表征
作者：
C. Chow
本文推导了表征单阈值器件可实现功能的一组参数。N元布尔函数是n维正方体顶点上0和1的函数。将顶点看作n维向量，真顶点的普通向量和(或重心)和真顶点的个数决定了可实现性。证明了：如果两个函数的特征向量和真顶点个数分别相等，则两个函数要么都是可实现的，要么都不能实现；如果其中一个函数是可实现的，则两个函数是相同的。由于这些特征参数的唯一性，可以用来标记已知的阈值函数。结合将函数缩减为标准形式的过程使用该标签提供了确定任意函数是否是已知阈值函数之一的方便手段。描述了特征参数的一些简单性质：特征参数直接给出实现阈值函数的权重的代数符号和它们之间的序数关系；特征向量关于偏序是最小的。给出了一类门限函数的结果。
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.