On Boolean threshold functions with minimum specification number

A set S of Boolean points is a specifying set for a threshold function f if the only threshold function consistent with f on S is f itself. The minimal cardinality of a specifying set for f is the specification number of f and it is never smaller than n + 1 for a function with n relevant variables. In the present paper, we develop an inductive approach to describing the set of Boolean threshold functions with minimum specification number by means of operations that allow us to extend functions of n variables in this set to functions of n + 1 variables.

Authors

• Vadim Lozin
• Viktor Zamaraev
• Elena Zamaraeva
• Nikolai Yu. Zolotykh

Keywords

• Boolean threshold function
• Specification number
• Essential points