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
    Aug 2, 2018 at 14:56
  • $\begingroup$ Yes, the formula $A \land C$ can both be interpreted as CNF and DNF. $\endgroup$
    – Sudix
    Aug 2, 2018 at 16:39

2 Answers 2

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.