Converting a propositional formula to DNF form

Question

I got a propositional formula and would like to know on how to construct a DNF equivalent step by step.

Here goes the formula: P<->(¬Q->R)

Answer 1

Here's one way, which is conceptually illuminating about what's going on in finding DNF forms.

Write down a truth-table for the formula:

$P\quad Q \quad R\quad\quad (P \leftrightarrow (\neg Q \to R))\\ T\quad T\quad T\ \quad\quad\quad T\\ T\quad T\quad F\ \quad\quad\quad T\\ T\quad F\quad T\ \quad\quad\quad T\\ T\quad F\quad F\ \quad\quad\quad F\\ F\quad T\quad T\ \quad\quad\quad F\\ F\quad T\quad F\ \quad\quad\quad F\\ F\quad F\quad T\ \quad\quad\quad F\\ F\quad F\quad F\ \quad\quad\quad T$

Now look at the lines where the wff comes out true and write down the conjunction corresponding in the obvious way to the assignment of truth-values to the atoms on each of those line:

$(P \land Q \land R)\\ (P \land Q \land \neg R)\\ (P \land \neg Q \land R)\\ (\neg P \land \neg Q \land \neg R)$

So our wff is true just whenever one of those conjunctions is true. So

Take the disjunction of those conjunctions

And we have a wff in DNF which is equivalent to the original one! Moreover, we see why the resulting wff is the correct DNF form.

Answer 2

Begin with the disjunctive eqivalent form of the biconditional:

$$\def\getsto{\mathop{\leftrightarrow}} {p\getsto(\neg q\to r)\\ (p\wedge(\neg q\to r))\vee(\neg p\wedge\neg(\neg q\to r))}$$

Then apply the conditional equivalence, negation of conditional, and distribution.

That is all.