# Use tableau to convert formula to DNF/CNF form

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

• en.wikipedia.org/wiki/… answers your question. similar for KNF Commented May 16, 2015 at 15:45
• In the question title you want to use a tableau; in the body you want to use a truth table. Those are not the same thing -- which do you mean? Commented May 16, 2015 at 15:46
• Your truth table wasn't correct, by the way. Fixed it for you. Commented May 16, 2015 at 16:11

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*}

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:

• map each clause in the DNF to a line in the truth table that results in True
• map all other combinations of inputs to False
• then follow the process above to get the CNF from the resulting truth table

This process can be followed to convert CNF to DNF as well if we swap True and False, DNF and CNF etc..

• @6005 I felt that this was more simply worded than the answers provided, also with a very simple step-by-step process. The other answers are fine, its just that this is how I understand this process, and none of the other answers really went in this direction. Commented May 18, 2016 at 10:01
• Good point. I agree this is more thorough. Commented May 18, 2016 at 10:04

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}

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.

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