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$
4
  • $\begingroup$ aren't you just looking for prime implicants? $\endgroup$
    – holf
    Oct 10, 2019 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, 2019 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, 2019 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, 2019 at 17:27

0

Reset to default

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.