0
$\begingroup$

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?

$\endgroup$
2
  • $\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

0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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