# Can CNF be converted to DNF using double negation?

Is it possible to convert a formula in conjunctive normal form (CNF) to disjunctive normal form (DNF) using double negation?

For example, given the following formula in CNF:

(¬A ∧ B ∧ ¬C) ∨ (A ∧ ¬B ∧ C) ∨ (A ∧ B ∧ C)
¬¬((¬A ∧ B ∧ ¬C) ∨ (A ∧ ¬B ∧ C) ∨ (A ∧ B ∧ C))
¬((A ∨ ¬B ∨ C) ∧ (¬A ∨ B ∨ ¬C) ∧ (¬A ∨ ¬B ∨ ¬C))


I am not sure if it is still a valid DNF.

EDIT: And with double negation it should also work the other way too, from DNF to CNF. Or am I wrong?

• The first formula that you give is not in CNF. Rather, it is in DNF. If you start with a formula in CNF, you can convert it to DNF by using Demorgan's law twice. Commented Jan 7, 2023 at 22:24
• Oh yes, my error in the example, I go from DNF to CNF. But my question was mainly about the double negation, which as far as I understand can be used to go from DNF to CNF and from CNF to DNF. Commented Jan 8, 2023 at 11:27

The first of your given expressions is actually allready in DNF. Using double negation you will get: \begin{aligned} \alpha:&(\lnot A\land B \land \lnot C) \lor (A \land \lnot B \land C) \lor (A \land B \land C) \\ \equiv& \lnot(\lnot ((\lnot A\land B \land \lnot C) \lor (A \land \lnot B \land C) \lor (A \land B \land C))) \\ \equiv& \lnot((A \lor \lnot B \lor C) \land (\lnot A \lor B \lor \lnot C) \land (\lnot A \lor \lnot B \lor \lnot C)) && (1) \end{aligned}

Drawing a truth table might help understanding what this means. Let $$\alpha = \alpha_1 \lor \alpha_2 \lor \alpha_3$$: $$\begin{array}{ccc|cl} A & B & C & \alpha \\ \hline T & T & T & \boxed{T} & \Rightarrow \alpha_1: A \land B \land C \\ T & T & F & F & \Rightarrow \hat\alpha_1: A \land B \land \lnot C \\ T & F & T & \boxed{T} & \Rightarrow \alpha_2: A \land \lnot B \land C\\ T & F & F & F & \Rightarrow \hat\alpha_2: A \land \lnot B \land \lnot C \\ F & T & T & F & \Rightarrow \hat\alpha_3: \lnot A \land B \land C \\ F & T & F & \boxed{T} & \Rightarrow \alpha_3: \lnot A \land B \land \lnot C \\ F & F & T & F & \Rightarrow \hat\alpha_4: \lnot A \land \lnot B \land C \\ F & F & F & F & \Rightarrow \hat\alpha_5: \lnot A \land \lnot B \land \lnot C \end{array}$$ Lets take the DNF for $$\lnot\alpha = \hat\alpha_1 \lor \hat\alpha_2 \lor \hat\alpha_3 \lor \hat\alpha_4 \lor \hat\alpha_5$$

$$\lnot\alpha : (A \land B \land \lnot C) \lor (A \land \lnot B \land \lnot C) \lor (\lnot A \land B \land C) \lor (\lnot A \land \lnot B \land C) \lor (\lnot A \land \lnot B \land \lnot C)$$

Inverting $$\lnot\alpha$$ will result in the CNF of $$\alpha$$:

\begin{aligned} \alpha \equiv& \lnot(\lnot\alpha) \\ \equiv& \qquad\;\;\; \lnot((A \land B \land \lnot C) \lor (A \land \lnot B \land \lnot C) \lor (\lnot A \land B \land C) \lor (\lnot A \land \lnot B \land C) \\&\qquad\qquad\qquad\qquad\qquad\qquad\quad \lor (\lnot A \land \lnot B \land \lnot C)) \\ \equiv& \lnot(A \land B \land \lnot C) \land \lnot(A \land \lnot B \land \lnot C) \land \lnot(\lnot A \land B \land C) \land \lnot(\lnot A \land \lnot B \land C) \land \lnot(\lnot A \land \lnot B \land \lnot C) \\ \equiv& (\lnot A \lor \lnot B \lor C) \land (\lnot A \lor B \lor C) \land (A \lor \lnot B \lor \lnot C) \land (A \lor B \lor \lnot C) \land (A \lor B \lor C) \end{aligned}

Notice that this is still equivalent to $$(1)$$. The definition of CNF/DNF requires that the not operator has to precede a propositional variable or a predicate symbol. This requirement is not fulfilled by $$(1)$$.

So it is possible to convert DNF to CNF using double negation and vice versa but make sure to be aware what exactly you are negating.