Is there any method that can be used to convert any formula do a DNF/CNF form using only the truth table? For example if I have the following formula
p → ¬(q∨r)
How can I convert it into DNF?
p q r (q∨r) ¬(q∨r) p → ¬(q∨r)
0 0 0 0 1 1
0 0 1 1 0 1
0 1 0 1 0 1
0 1 1 1 0 1
1 0 0 0 1 1
1 0 1 1 0 0
1 1 0 1 0 0
1 1 1 1 0 0
On
Note that you can rewrite $p\to\neg(q\lor r)$ as $\neg p\lor(\neg(q\lor r))$, i.e. $\neg p\lor(\neg q\land\neg r)$. This fits exactly the truth table (as you would expect), and shows that the proposition is true whenever $p$ is false or both $q$ and $r$ are false.
This would usually enough be enough to answer your question, but we can also give a full disjunctive normal form of all the cases making the proposition true, as follows: \begin{align}\neg p&\land q\land r\\\lor\ \neg p&\land q\land\neg r\\\lor\ \neg p&\land\neg q\land r\\\lor\ \neg p&\land\neg q\land\neg r\\\lor\quad p&\land\neg q\land\neg r\end{align}
On
Of course, we can use also the tableau method, obtaining the same result produced by the use of truth-table.
We have to apply the tableau to the original formula, checking its satisfiability.
Each open path defines a (set of) assignments to the sentential variables satisfying the formula. Every assignment will form a "basic conjubct" that must be "disjoined" to have the required $DNF$.
If we start with $T[p \to ¬(q \lor r)]$ and apply the rule for $T\to$, we get two branches: one with $Fp$ and the other with $T[¬(q∨r)]$, i.e. $F[q∨r]$.
The left branch is finished without closing and thus gives the four possible conjuncts with $p$ false, i.e. the four conjuncts : $\lnot p \land \ldots$ (see the above answer).
The same for the right branch; applying the rule for $F\lor$ we get: $Fq$ and $Fr$, i.e. the two conjuncts : $p \land \lnot q \land \lnot r$ and $\lnot p \land \lnot q \land \lnot r$.
We have only to note that the second one is already present among the four conjuncts previously produced by the left branch, and we are done.
On
See also K-map: http://en.wikipedia.org/wiki/Karnaugh_map It is a very clever and fast method to derive DNF and other useful things
On
If you write out the truth table for your formula...
p q r p → ¬(q∨r)
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 0
To get the DNF, look at every result that is True; those lines directly correspond to the following clauses in DNF: $$(\lnot p\land\lnot q\land\lnot r)\lor(\lnot p\land\lnot q\land r)\lor(\lnot p\land q\land \lnot r)\lor(\lnot p\land q\land r)\lor(p\land \lnot q\land \lnot r)$$ This is a complete description of the formula in DNF - look at how the zeros in the table inputs result in a negation of a literal, and ones result in plain literals.
To get the CNF, look at every result that is False; those lines directly correspond to the following clauses in CNF: $$(p\lor \lnot q\lor r)\land(p\lor q\lor \lnot r)\land(p\lor q\lor r)$$ Again, this is a complete description of the formula in CNF.
It follows then, that if you also wish to convert a DNF to a CNF then what you need to do is reverse engineer this process. Say for instance you had a DNF:
This process can be followed to convert CNF to DNF as well if we swap True and False, DNF and CNF etc..
I am assuming you mean truth table in the title. Consider a conjunction of literals such as $p \land \lnot q \land \lnot r$: this is true for the assignment given by the row with $(p, q, r) = (1, 0, 0)$ in the truth table and not for any other row. The DNF is the disjunction of the conjunctions corresponding to the rows in which your formula is true. $$ \begin{align*} & \lnot p \land \lnot q \land \lnot r\\ {}\lor {} &\lnot p \land \lnot q \land r \\ {}\lor {} &\lnot p \land q \land \lnot r \\ {}\lor {} &\lnot p \land q \land r \\ {}\lor {} &p \land \lnot q \land \lnot r \\ \end{align*} $$