# Cover set of Boolean formulas with conjunctions

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.

• aren't you just looking for prime implicants?
– holf
Oct 10, 2019 at 8:47
• @holf It seems like prime implicants are defined for a single formula. I'm looking for a similar concept, but for multiple formulas. Oct 10, 2019 at 16:40
• yeah but then they are the prime implicant of the disjunction of your formulas aren't they?
– holf
Oct 10, 2019 at 22:44
• @holf Not necessarily, are they? Say you had a third formula $p_3 = (\neg A \land \neg X \land B)$, then $p_2$ would be a prime implicant and $p_3$ is not represented. Oct 11, 2019 at 17:27