# disjunctive normal form question

• Nov 6th 2011, 08:16 PM
demode
disjunctive normal form question
I want to find a statement form in relaxed disjunctive normal form that is logically equivalent to $\displaystyle ((p \to q) \wedge (q \to r))$.

The solution has to be $\displaystyle (((\neg p \wedge \neg q) \vee (\neg p \wedge r))\vee (q \wedge r))$. But I don't see how the got this answer.

I used a truth table, where I've marked with a * the rows where the statement is true:

http://img39.imageshack.us/img39/231/tabledx.jpg

by looking at those rows the disjunctive normal form is

$\displaystyle ((\neg p \wedge \neg q) \wedge \neg r) \vee ((\neg p \wedge \neg q) \wedge r) \vee ((\neg p \wedge q) \wedge r) \vee ((p \wedge q) \wedge r)$

So how did they get a different answer? How can we get the right answer using the table?
• Nov 6th 2011, 08:35 PM
terrorsquid
Re: disjunctive normal form question
Are you familiar with the fact that:

$\displaystyle ((p\rightarrow q)\wedge (q\rightarrow r)) \equiv (\neg p \vee q )\wedge (\neg q \vee r)$

If you continue you will find one false term.
• Nov 6th 2011, 08:50 PM
demode
Re: disjunctive normal form question
Quote:

Originally Posted by terrorsquid
Are you familiar with the fact that:

$\displaystyle ((p\rightarrow q)\wedge (q\rightarrow r)) \equiv (\neg p \vee q )\wedge (\neg q \vee r)$

If you continue you will find one false term.

Yes, that follows from the impliction law. But what do you mean that I find one false term?
• Nov 6th 2011, 09:12 PM
terrorsquid
Re: disjunctive normal form question

from

$\displaystyle (\neg p \vee q )\wedge (\neg q \vee r)$

$\displaystyle ((\neg p \wedge \neg q) \vee (\neg p \wedge r))\vee ((q \wedge \neg q)\vee (q \wedge r))$

$\displaystyle (q\wedge \neg q)$ is clearly false.