On specifying Boolean functions by labelled examples

We say a function t in a set H of 0, 1-valued functions defined on a set X is specified byS⊆ X if the only function in H which agrees with t on S is t itself. The specification number of t is the least cardinality of such an S. For a general finite class of functions, we show that the specification number of any function in the class is at least equal to a parameter from Romanik and Smith (1990) known as the testing dimension of the class. We investigate in some detail the specification numbers of functions in the set of linearly separable Boolean functions of n variables — those functions f such that f−1(0) and f−1(1) can be separated by a hyperplane. We present general methods for finding upper bounds on these specification numbers and we characterise those functions which have largest specification number. We obtain a general lower bound on the specification number and we show that for all nested functions, this lower …