[Math] Converting boolean logic to disjunctive normal form and conjunctive normal form

conjunctive-normal-formdisjunctive-normal-form

$(\lnot q \lor \lnot r) \rightarrow (\lnot r \land (q \rightarrow p))$

  • Put the statement into disjunctive normal form
  • Put the statement into conjunctive normal form

I don't know how to convert the statement into each of the forms it asks me to. Would be nice if someone could explain the steps to solving it.

Best Answer

There is also a requirement that in DNF, the expression is written as an OR over clauses which only use AND, and vice versa for CNF (you can use NOT only directly before single variables). So a good first step would be to convert everything to AND, OR, and NOT, then use De Morgan's laws to help push NOT's to single variables. From there, you can distribute the AND's and OR's, depending on your target form.

For example, given $\neg (p \land (q \implies r)) \land \neg (p \implies \neg q)$, we would first convert the implications: $$ \neg (p \land (\neg q \lor r)) \land \neg (\neg p \lor \neg q) $$ Then move negations to single variables: $$ (\neg p \lor \neg (\neg q \lor r)) \land (p \land q) $$ $$ (\neg p \lor (q \land \neg r)) \land (p \land q) $$ If we want this to be in CNF, we have to make it a conjunction of disjunctions, so distribute: $$ ((\neg p \lor q) \land (\neg p \lor \neg r)) \land (p \land q) $$ $$ (\neg p \lor q) \land (\neg p \lor \neg r) \land p \land q $$ This is now in CNF; you could further eliminate some redundancy further if you wanted to. The conversion to DNF is similar; follow the same steps, but distribute conjunction over disjunction, rather than the other way around, which we did above.

Related Question