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$

Solution 1:

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.