<p>I want to cover a set of Boolean formulas (over the same variables) with disjunctive conjunctions. Here's an example with two formulas <span class="math-container">$p_1$</span> and <span class="math-container">$p_2$</span> over the set of variables <span class="math-container">$\{A, B, X, Y\}$</span>:</p>

<p><a href="https://i.sstatic.net/6v51e.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/6v51e.png" alt="enter image description here"></a></p>

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

<p><a href="https://i.sstatic.net/OMoMd.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/OMoMd.png" alt="enter image description here"></a></p>

<p>In the left example, the solution space is partitioned into five conjunctions. Both <span class="math-container">$p_1$</span> and <span class="math-container">$p_2$</span> 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.</p>

<p>I am looking for such a partition with the <em>minimal</em> 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.</p>

<p>Is this a solved problem? I am interested in both structural and algorithmic results.</p>

CC BY-SA 4.0
2019-10-10T08:47:14.723Z
aren't you just looking for [prime implicants](https://en.wikipedia.org/wiki/Prime_implicant#Prime_implicant)?
holf
CC BY-SA 4.0
2019-10-10T16:40:03.727Z
@holf It seems like prime implicants are defined for a single formula. I'm looking for a similar concept, but for multiple formulas.
madbeebop
CC BY-SA 4.0
2019-10-10T22:44:59.090Z
yeah but then they are the prime implicant of the disjunction of your formulas aren't they?
holf
CC BY-SA 4.0
2019-10-11T17:27:54.040Z
@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.
madbeebop
<lo.logic><boolean-functions><boolean-formulas><covering-problems>
Cover set of Boolean formulas with conjunctions
madbeebop
# Cover set of Boolean formulas with conjunctions

(Asked by: username_0 on 2019-10-10)

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](https://i.sstatic.net/6v51e.png)](https://i.sstatic.net/6v51e.png)

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

[![enter image description here](https://i.sstatic.net/OMoMd.png)](https://i.sstatic.net/OMoMd.png)

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.

**Tags:** lo.logic, boolean-functions, boolean-formulas, covering-problems
> **Comments:**
> **username_1**: aren't you just looking for [prime implicants](https://en.wikipedia.org/wiki/Prime_implicant#Prime_implicant)?  
> **username_0**: @holf It seems like prime implicants are defined for a single formula. I'm looking for a similar concept, but for multiple formulas.  
> **username_1**: yeah but then they are the prime implicant of the disjunction of your formulas aren't they?  
> **username_0**: @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.  

---

## 0 answers

