Table 8:

L NNF DNNF d-DNNF FBDD OBDD OBDD< DNF CNF PI IP MODS sd-DNNF

![0_image_1.png](0_image_1.png)

NNF ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤
DNNF ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤ ≤
d-DNNF ≤ ≤ ≤ ≤ ≤ ≤
FBDD ≤ ≤ ≤
OBDD ≤ ≤
OBDD< ≤
DNF 6≤ ≤ 6≤ 6≤ ≤ ≤ CNF 6≤ 6≤ 6≤ ≤ ≤ 6≤
PI 6≤ 6≤ 6≤ 6≤ ≤ 6≤
IP 6≤ 6≤ 6≤ 6≤ 6≤ ≤
MODS ≤
sd-DNNF ≤ ≤
Table 9:

![0_image_0.png](0_image_0.png)

we mark all relationships that are proved in that step–we don't show these marks in the very first table though.

Table 8: **Follows immediately from the language inclusions reported in Figure 4.**
Table 9: **We can prove both that** DNF 6≤ PI and CNF 6≤ IP **(this slightly generalizes the results**
DNF 6≤ CNF and CNF 6≤ DNF **given in (Gogic et al., 1995)).**
Let us consider the CNF formula Σn =Vn−1 i=0 (x2i ∨ x2i+1**). This formula is in prime implicates**
form7(and each clause in Σn is an essential prime implicate of it). Hence its negation ¬Σn **is in**
prime implicants form (as an easy consequence of Lemma A.14).

Since Quine's early work (Quine, 1959), we know that the number of essential prime implicants
(resp. prime implicates) of a formula is a lower bound of the number of terms (resp. clauses) that can be found in any DNF (resp. CNF) representation of it (indeed, any such representation must include the essential prime). Σn has 2n **essential prime implicants. Indeed, this can be easily shown**
by induction on n given that (i) every literal occurring in Σn **occurs only once, (ii) the set of prime**
implicants of any nontautological clause is the set of literals occurring in **it (up to logical equivalence),** and (iii) the distribution property for prime implicants (see e.g., (dual of) Proposition 40 in (Marquis, 2000)) which states that IP(α∧β) = max({PIα ∧PIβ | PIα ∈ IP(α), PIβ ∈ IP(β)}, |**=) (up to logical**
equivalence). Subsequently, ¬Σn has 2n **essential prime implicates (cf. Lemma A.14). Accordingly,**
we obtain that both DNF 6≤ PI and CNF 6≤ IP. We also obtain PI 6≤ IP and IP 6≤ PI**. Now, it is**
well–known that some DNF formulas have exponentially many prime implicants (see the proof of Proposition 5.1 where we show that IP does not satisfy SFO**). Hence, their negations are CNF**