Coverable Boolean Functions

Petr Kucera

(joint work with Endre Boros, Ondrej Cepek, and Alex Kogan)

Abstract: An essential set of implicates E of a given Boolean function f is a set of implicates, which can be derived by resolution from prime implicates and such that for every implicate C which is a resolution of implicates C_1 and C_2, if C belongs to E, then one of the parent clauses C_1 and C_2 must belong to E as well. These sets have many interesting properties, among them the fact that the number of pairwise disjoint essential sets of implicates of f is less than or equal to the number of clauses in a minimum CNF. A class of functions is called "coverable" if equality holds instead of the above inequality for every function in the class. We shall show in this talk, that the classes of acyclic, quasi-acyclic, quadratic and CQ functions are coverable. Interestingly for each of these classes we also have a polynomial time minimization algorithm. This talk is a continuation of the talk to be given by Ondrej Cepek.