4
$\begingroup$

Is it possible for a formula in propositional logic that its disjunctive normal form (DNF) and its conjunctive normal form (CNF) are the same?

For example, can $A \land C$ be both the conjunctive normal form and the disjunctive normal form of the formula below?

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

$\endgroup$
2
  • 2
    $\begingroup$ Can you add your work to show how you simplified the highlighted expression to $A\land C$? $\endgroup$
    – amWhy
    Commented Aug 2, 2018 at 14:56
  • $\begingroup$ Yes, the formula $A \land C$ can both be interpreted as CNF and DNF. $\endgroup$
    – Sudix
    Commented Aug 2, 2018 at 16:39

2 Answers 2

2
$\begingroup$

A conjunctive normal form is a conjunction of a sequence of disjunctions of a sequence of literals or their negations.   Abreviated as: a conjunction of disjunctions of literals or their negations.

A single literal is a conjunction of a sequence of one literal.   It is also a disjunction of a sequence of one literal.

Thus $A\wedge C$ is a conjunction of two disjunctions of one literal; and also a disjunction of two conjunctions of one literal.   That is it is both a conjunctive normal form and a disjunctive normal form.


Now, is it a CNF/DNF for $(A\vee((A\wedge B)\vee(\neg A\wedge\neg B\wedge\neg C)))\wedge C$?

Well, $C$ must be true for the statement to hold.   When we substitue $\top$ for $C$, that becomes $(A\vee((A\wedge B)\vee(\neg A\wedge\neg B\wedge \bot)))\wedge \top$ which simpliefies to $A$.   So $A$ must be true too.   The value of $B$ is irrelevant.

Therefore $A\wedge C$ is indeed a CNF/DNF equivalent to the statement.

$\endgroup$
1
$\begingroup$

The short answer is: yes!

Indeed, $A \land C$ is both a CNF (because it is a conjunction of two disjunctive clauses, each one made of just one literal) and a DNF (with just one conjunctive clause).

To prove that $A \land C$ is a CNF and a DNF of $(A \lor ((A \land B) \lor (\lnot A \land \lnot B \land \lnot C))) \land C$, it remains to prove that $A \land C$ is logically equivalent to $(A \lor ((A \land B) \lor (\lnot A \land \lnot B \land \lnot C))) \land C$. To prove it, I use logical equivalences listed here as rewriting rules (the use of the associativity is left implicit):

\begin{align} (A \lor (A \land B) \lor (\lnot A \land \lnot B \land \lnot C)) \land C &\equiv (A \lor (\lnot A \land \lnot B \land \lnot C)) \land C &\text{absortion law} \\ &\equiv (A \lor \lnot A) \land (A \lor \lnot B) \land (A \lor \lnot C) \land C &\text{distributivity law} \\ &\equiv (A \lor \lnot B) \land (A \lor \lnot C) \land C &\text{identity law} \\ &\equiv (A \lor (\lnot B \land \lnot C)) \land C &\text{distributivity law} \\ &\equiv (A\land C) \lor (\lnot B \land \lnot C \land C) &\text{distributivity law} \\ &\equiv A\land C &\text{identity law} \end{align} where the first identity law can be applied since $A \lor \lnot A$ is a tautology, and the second identity law can be applied because $\lnot B \land \lnot C \land C$ is a contradiction.


Remark. Pay attention that a CNF of a given formula is not unique, and similarly for DNF. For instance, also $A \land C \land (B \lor \lnot B)$ is a CNF of $(A \lor ((A \land B) \lor (\lnot A \land \lnot B \land \lnot C))) \land C$. So, properly speaking it is not clear what you refer to when you talk of the CNF (or the DNF) of a given formula.

More interesting remarks about the non-uniqueness of CNF (or DNF) of a given formula are in this question.

$\endgroup$

You must log in to answer this question.

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