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.

Thank you for your help.

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

  • $\begingroup$ 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. $\endgroup$ Commented Jan 7, 2023 at 22:24
  • $\begingroup$ 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. $\endgroup$
    – KarlFri
    Commented Jan 8, 2023 at 11:27

1 Answer 1


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .