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?

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.

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?

Re: disjunctive normal form question

Well, the way I got to your answer is as follows:

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.

Removing it, you are left with your answer provided.

I'm not sure if that is what you are looking for.

Re: disjunctive normal form question

But my question is how do you get this answer by looking at the truth table? You just got this answer using the logical laws. Sometimes we are required to do it via the table, not logical laws.