disjunctive normal form question

Printable View

November 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 $((p \to q) \wedge (q \to r))$ .

The solution has to be $(((\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

$((\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?
November 6th 2011, 08:35 PM
terrorsquid

Re: disjunctive normal form question

Are you familiar with the fact that:

$((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.
November 6th 2011, 08:50 PM
demode

Re: disjunctive normal form question

Quote:

Originally Posted by terrorsquid

Are you familiar with the fact that:

$((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?
November 6th 2011, 09:12 PM
terrorsquid

Re: disjunctive normal form question

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

from

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

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

$(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.
November 6th 2011, 11:22 PM
demode

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.