1
$\begingroup$

Is the following formula in DNF?

$$((P \land Q) \land ( \neg R \land \neg S)) \lor ((r \lor s) \land (\neg p \lor \neg q))$$

I think it is not a DNF, because in the second part there are OR's inside an AND. Is this correct?

How should I rewrite this to a proper DNF?

$\endgroup$
1
$\begingroup$

You must simply expand it performing the AND's in the second part (following the same rule as if AND were a multiplication and OR an addition), so obtaining: $$(p\land q\land \neg r\land\neg s)\lor(\neg p\land s)\lor(\neg p\land r)\lor(\neg q\land s)\lor(\neg q\land r)$$

$\endgroup$
  • $\begingroup$ Thank you.How is this rule formally called? $\endgroup$ – Raymond Timmermans Sep 10 '17 at 11:03
  • 1
    $\begingroup$ Distributivity: the AND operation distributes over the OR operation. Notice that in boolean algebra there is one more distributivity rule, whereby the OR operation distributes over the AND operation. In this last case you cannot use the suggestion I told you where AND is though of as multiplication and OR as addition. $\endgroup$ – trying Sep 10 '17 at 11:08
  • $\begingroup$ Well explained. Thank you! $\endgroup$ – Raymond Timmermans Sep 10 '17 at 11:09
  • $\begingroup$ you're welcome. If it can be of any help, yesterday I solved a minimization problem that had as solution just your DFN (probably asked by one of your colleagues): math.stackexchange.com/a/2423199/309917 $\endgroup$ – trying Sep 10 '17 at 11:12
  • $\begingroup$ Yep, very well could be one of my colleagues :P. That post was usefull thanks. $\endgroup$ – Raymond Timmermans Sep 10 '17 at 11:16

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.