# Is it possible for the DNF and CNF to be the same

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$$

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

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.

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.