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

- MODS**. Let** α1 =Vn i=1 xi and α2 = y. Sentence α1 has 1 model over Vars(α1) and α2 has 1 model over Vars(α2). But α1 ∨ α2 has 2n + 1 models over Vars(α1) ∪ **Vars**(α2).
- ¬C.

- NNF, s-NNF, f-NNF, BDD, FBDD, OBDD and OBDD<**. The property is obviously satisfied by**
NNF. s-NNF also satisfies ¬C **since every** NNF **formula can be turned in polynomial time** into an equivalent s-NNF **formula.** f-NNF satisfies ¬C **since applying De Morgan's laws**
on a f-NNF **formula results in a** f-NNF **formula. Finally, for all the forms of BDDs, it is**
sufficient to switch the labels of the sinks to achieve negation (Bryant, 1986).

- CNF**. Because the negation of a** DNF **formula is a** CNF **formula that can be computed in**
polynomial time, if CNF would satisfy ¬C**, then it would be possible to turn any** DNF
formula into an equivalent CNF **formula in polynomial time (by involution of negation).**
But we know that it is not possible in polynomial space since CNF 6≤ DNF**(see the proof of**
Proposition 3.1). Hence, CNF **does not satisfy** ¬C.

- DNF**. Dual of the proof just above (just replace** CNF by DNF and **vice-versa**).

- PI**. The formula Σ**n =Vn−1 i=0 (x2i ∨ x2i+1**) is in prime implicates form (see the proof of**
Proposition 3.1, Table 9). This formula has exponentially many prime **implicants, that**
are just the negations of the prime implicates of ¬Σn. Since ¬Σn **has exponentially many**
prime implicates, it cannot be the case that PI **satisfies** ¬C.

- IP**. We just have to take the dual of the above proof (prime implicates case). The formula**
Σn =Wn−1 i=0 (x2i∧x2i+1**) is in prime implicants form. This formula has exponentially many**
prime implicates, that are just the negations of the prime implicants of ¬Σn**. Since** ¬Σn has exponentially many prime implicants, it cannot be the case that IP **satisfies** ¬C.

- DNNF**. The negation of any** CNF **formula can be computed in polynomial time as a** DNF
formula, hence as a DNNF **formula. If** DNNF would satisfy ¬C**, then it would be possible**
to turn a CNF **formula into an equivalent** DNNF **one (by involution of negation). Because** DNNF satisfies CO**, we would have** P = NP.

- d-NNF**. Following is a procedure for negating a** d-NNF **sentence ∆:**9
∗ Traverse nodes in the DAG of ∆, visiting the children of a node before you visit the node itself. When visiting a node, construct its negation as follows:
· true is the negation of **false**. · false is the negation of **true**.

· ∧(N′1
,... ,N′k
) is the negation of ∨(N1,... ,Nk**). Here,** N′
i is the node representing the negation of Ni.

· ∨(∧(N′1
,M1)**,... ,**∧(N′k
,Mk)) is the negation of ∧(N1,... ,Nk**). Here,** N′
i is the node representing the negation of Ni, and Miis a node representing the conjunction N1 ∧ ... ∧ Ni−1.

∗ **Return the negation of the root of** d-NNF ∆.

We can implement the above four steps so that we when we visit a node with k **children,**
we only construct O(k) nodes and O(k) edges.10 **Hence, the procedure complexity is**