2
$\begingroup$

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\}$:

enter image description here

I want to partition the solution space into conjunctions and represent all formulas as disjunctions of such conjunctions:

enter image description here

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.

Improve this question
$\endgroup$
  • $\begingroup$ aren't you just looking for prime implicants? $\endgroup$ – holf Oct 10 '19 at 8:47
  • 1
    $\begingroup$ @holf It seems like prime implicants are defined for a single formula. I'm looking for a similar concept, but for multiple formulas. $\endgroup$ – madbeebop Oct 10 '19 at 16:40
  • $\begingroup$ yeah but then they are the prime implicant of the disjunction of your formulas aren't they? $\endgroup$ – holf Oct 10 '19 at 22:44
  • 1
    $\begingroup$ @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. $\endgroup$ – madbeebop Oct 11 '19 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.