We now state and prove the equivalent of Theorem 1 with this new size notion.

A previous work [Kearns et al.1987] proves a similar theorem concerning the minimization of the size of a DNF. Theorem 3 can be shown to be more general, as the class of DC with two rules strictly contains that of DNF with two monomials.

The statement of Theorems 1, 2, 3 as optimization problems was chosen for pure convenience ; replacing them by their associated decision problems (decide whether there exist a consistent formula whose size is no more than some fixed threshold) would trivially make the problems not only -Hard, but also -Complete.