An extremal point of a positive threshold Boolean function $f$ is either a maximal zero or a minimal one. It is known that if $f$ depends on all its variables, then the set of its extremal points completely specifies $f$ within the universe of threshold functions. However, in some cases, $f$ can be specified by a smaller set. The minimum number of points in such a set is the specification number of $f$. Hu (1965) showed that the specification number of a threshold function of $n$ variables is at least $n+1$. Anthony et al. (1995) proved that this bound is attained for nested functions and conjectured that for all other threshold functions the specification number is strictly greater than $n+1$. In the present paper, we resolve this conjecture negatively by exhibiting threshold Boolean functions of $n$ variables, which are non-nested and for which the specification number is $n+1$. On the other hand, we show that the set of extremal points satisfies the statement of the conjecture, i.e.~a positive threshold Boolean function depending on all its $n$ variables has $n+1$ extremal points if and only if it is nested. To prove this, we reveal an underlying structure of the set of extremal points.
展开▼
机译：正阈值布尔函数$ f $的极点为最大零或最小一。众所周知，如果$ f $取决于其所有变量，则其极值点集将在阈值函数范围内完全指定$ f $。但是，在某些情况下，可以用较小的集合指定$ f $。这样的集合中的最小点数是$ f $的规范数。 Hu（1965）指出，$ n $变量的阈值函数的规格数至少为$ n + 1 $。安东尼等。 （1995年）证明了嵌套函数的边界，并推测对于所有其他阈值函数，规范号严格大于$ n + 1 $。在本文中，我们通过展示$ n $变量的阈值布尔函数来否定地解决该猜想，该变量是非嵌套的，其规格编号为$ n + 1 $。另一方面，我们证明极值点集满足猜想的陈述，即，当且仅当嵌套时，取决于其所有$ n $变量的正阈值布尔函数才具有$ n + 1 $极值点。为了证明这一点，我们揭示了极值点集的基本结构。
展开▼
