0
$\begingroup$

$(\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.

$\endgroup$
  • $\begingroup$ What have you tried so far? Are you familiar with the definitions of these two normal forms? $\endgroup$ – platty Nov 30 '18 at 0:07
  • $\begingroup$ @platty I have read up on the forms and I am a little confuse on the forms but from what I can tell I assume disjunctive normal forms means the statement is connected through the OR operators and the conjunctive form is when the statement is combined with AND operators. But I don't know how to convert it to those forms. I assume you use properties that exists within boolean algebra to convert it, but I don't know how to start $\endgroup$ – Viserom Nov 30 '18 at 0:11
0
$\begingroup$

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.

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