I want to cover a set of Boolean formulas (over the same variables) with disjunctive conjunctions. Here's an example with two formulas $p_1$ and $p_2$ over the set of variables $\{A, B, X, Y\}$:
I want to partition the solution space into conjunctions and represent all formulas as disjunctions of such conjunctions:
In the left example, the solution space is partitioned into five conjunctions. Both $p_1$ and $p_2$ can be represented as disjunctions of these conjunctions, as shown. Note that not every conjunction appears in a disjunction. However, it is still needed to partition the solution space.
I am looking for such a partition with the minimal number of conjunctions. So although the partition on the right also admits a representation as disjunctions, it consists of six conjunctions and is therefore not minimal.
Is this a solved problem? I am interested in both structural and algorithmic results.