Boolean functions with a simple certificate for CNF complexity

► We study certain lower bounds for a CNF size (number of clauses) of a Boolean function. ► The lower bound is given by the maximum number of disjoint essential sets of implicates. ► Boolean functions for which this lower bound is tight are called coverable. ► Non-coverable functions exist and the gap may be arbitrarily large. ► Complexity of computing the lower bound under different conditions is investigated.