- NNF, s-NNF, d-NNF, BDD and CNF. Immediate since each of these languages satisfy ∧C **(see**
above).

- DNNF, d-DNNF, sd-DNNF, FBDD and OBDD**. Checking whether the conjunction of two** OBDD<
formulas α1 and α2 (w.r.t. two different variable orderings <) is consistent is NP**-complete**
(see Lemma 8.14 in (Meinel & Theobald, 1998)). Since OBDD satisfies CO**, it cannot satisfy**
∧BC unless P = NP**. Since** OBDD ⊆ FBDD ⊆ d-DNNF ⊆ DNNF**, and** d-DNNF and DNNF **satisfy** CO, none of them can satisfy ∧BC unless P = NP**. Finally, since every** d-DNNF **formula**
can be turned in polynomial time into an equivalent smoothed d-DNNF **formula and since**
sd-DNNF satisfies CO**, it cannot be the case that** sd-DNNF satisfy ∧BC **unless** P = NP.

- OBDD<**. Well-known fact (Bryant, 1986).**
- f-NNF**. Let** α1 =Vn−1 i=0 (x2i ∨ x2i+1**) be a** CNF **formula and** α2 =Wn−1 i=0 (x
′
2i ∧ x
′
2i+1) a DNF
formula. α1 has 2n essential prime implicants and n **essential prime implicates (see the**
proof of Proposition 3.1, Table 9). By duality, α2 has n **essential prime implicants and 2**n essential prime implicates. Now, α1 and α2 **are two** f-NNF **formulas. By Lemma A.13, we**
know that every f-NNF formula β **can be turned in polynomial time into a** CNF **formula or**
a DNF **formula. If** f-NNF would satisfy ∧BC**, then a** f-NNF formula β s.t. β ≡ α1∧α2 **could**
be computed in time polynomial in the input size. Hence, either a CNF **formula equivalent**
to α1 ∧ α2 **or a** DNF formula equivalent to α1 ∧ α2 **could be computed in polytime. But**
this is impossible since α1 ∧ α2 has n + 2n **essential prime implicates and** n ∗ 2 n **essential**
prime implicants. Hence every CNF **(resp.** DNF ) formula equivalent to α1 ∧ α2 **has a size**
exponential in |α1| + |α2|.

Note that in the case where the two f-NNF formulas α1 and α2 **into consideration can**
be turned in polynomial time into either two CNF **formulas or two** DNF **formulas, then a**
f-NNF formula equivalent to α1 ∧ α2 **can be computed in time polynomial in the input**
size (this is obvious when two CNF **formulas are considered and the next item of the proof** shows how this can be achieved when two DNF **formulas are considered).**
- DNF and MODS. If α1 and α2 are sentences in one of these languages L**, then we can construct**
a sentence in L which is equivalent to α1 ∧α2 **by simply taking all the conjunctions of one**
term from α1 and one term from α2**, while removing redundant literals in the resulting**
terms and removing any inconsistent terms in the result. The disjunction of all the resulting terms is a sentence from L equivalent to α1 ∧ α2 **and it has been computed in**
polynomial time.

- PI**. Let** α1 =Wk i=1 pi and α2 =Vk i=1 Vm j=1(¬pi∨qi,j ). Sentence α1 **has one prime implicate**
and α2 has m ∗ k prime implicates. But α1 ∧ α2 has (m + 1)k + m ∗ k **prime implicates**
(Chandra & Markowsky, 1978).

- IP. Let IP(α) be the set of prime implicants for α. We have IP(α1 ∧ α2**) = max(**{β1 ∧
β2 | β1 ∈ IP(α1),β2 ∈ IP(α2)}, |**=) (up to logical equivalence). See e.g., (dual of) Proposition 40 in (Marquis, 2000).**