1
$\begingroup$

So I understand that CNF is the conjunction of one or more disjunctive clauses and that a DNF is a disjunction of one or more conjunctive clauses, however, I was wondering if there could be a case where a CNF is also a DNF.

An example would be a proposition like $P \land Q \land \neg R$ which is a CNF, but could this count as a DNF of one conjunctive clause? Or would it have to be something in the form (P ∧ Q) ∨ ¬R

$\endgroup$

1 Answer 1

0
$\begingroup$

Yes: specifically an expression is in CNF and DNF if and only if at most one of the connectives $\{\land,\lor\}$ appears. For the "only if" part, notice that if an expression is in CNF or DNF, and we postulate that the parenthesis are only the ones necessary to remove ambiguities of non-associativity, then whether or not the second type of connective appears inside or outside parenthesis excludes one of the two forms: \begin{array}{c|c|c}&\lor\text{ 2nd}&\land\text{ 2nd}\\ \hline\text{inside parenthesis}&\text{not DNF}&\text{not CNF}\\ \hline\text{outside parenthesis}&\text{not CNF}&\text{not DNF}\end{array}

$\endgroup$
1
  • $\begingroup$ so just to confirm the example I presented with the parenthesis would not be considered as a proposition in CNF and DNF $\endgroup$ Commented Jan 30, 2022 at 19:24

You must log in to answer this question.

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