Minimal Samples of Positive Examples Identifying k-CNF Boolean Functions

AbstractA consistent learning algorithm can reconstruct any Boolean function belonging to a given class from a sufficiently large number of examples; therefore such samples may be interpreted as an encoding of functions. We investigate the complexity of encoding by examples for functions representable by k-CNF logic formulas. Lower and upper bounds for the sampling complexity of k-CNF functions are expressed in terms of the Vapnik-Chervonenkis dimension (trace number) and related combinatorial indices. Combinatorial characterization of k-CNF functions which cannot be identified from a sample smaller than the complete list of truth assignments is also investigated