Abstract

In the paper, we consider the problem of checking whether cubes from a set S are implicants of a DNF formula D, at the same time minimizing the overall time taken by the checks. An obvious but inefficient way of solving the problem is to perform all the checks independently. In the paper, we consider a different approach. The key idea is that when checking whether a cube C from S is an implicant of D we can deduce (learn) implicants of D that are not implicants of C. These cubes can be used in the following checks for search pruning. Experiments on random DNF formulas, DIMACS benchmarks and DNF formulas describing circuits show that the proposed learning procedure reduces the overall time taken by checks by up to two orders of magnitude.