On the gap between ess(f) and cnf_size(f)

Given a Boolean function ff, the quantity ess(f) denotes the largest set of assignments that falsify ff, no two of which falsify a common implicate of ff. Although ess(f) is clearly a lower bound on cnf_size(f) (the minimum number of clauses in a CNF formula for ff), C˘epek et al. showed it is not, in general, a tight lower bound [6]. They gave examples of functions ff for which there is a small gap between ess(f) and cnf_size(f). We demonstrate significantly larger gaps. We show that the gap can be exponential in nn for arbitrary Boolean functions, and Θ(n) for Horn functions, where nn is the number of variables of ff. We also introduce a natural extension of the quantity ess(f), which we call essk(f), which is the largest set of assignments, no kk of which falsify a common implicate of ff.