Sentential logic exercise from 'How to Prove it - A Structured Approach'

1. Apr 1, 2012

RUBSTEP

1. The problem statement, all variables and given/known data

This is an exercise from 'How to Prove it - A Structured Approach' (Exercise 7a, page 54) . So far a a really great book.

2. Relevant equations

The DeMorgan, Absorption, Idempotent, Double Negation, Commutative, Associative, Distributive, Tautology, Contradiction, Conditional and Contrapositive law is what the book has gone through so far.

3. The attempt at a solution

I have been banging my head at this for hours. Constructing a truth table is trivial. But i havent been able to go from one formula to the other by use of the stated laws. All exercises up to this have just required a few applications of the laws. So all my attempts at solving this so far have been mostly pages of jumping between formulas using the applicable laws.

I really feel like im missing something. So any help would be greatly appreciated!

2. Apr 1, 2012

920118

$\varphi$$\rightarrow$$\psi$ Is introduced as an abbreviation for or shown to be equivalent to $\neg$$\varphi$ v $\psi$ earlier in that chapter, and $\varphi$$\leftrightarrow$$\psi$ for ($\varphi$$\rightarrow$$\psi$) ^ ($\psi$$\rightarrow$$\varphi$), so what you have to show is that

($\neg$P v Q) ^ ($\neg$Q v R) $\Leftrightarrow$ ($\neg$P v R) ^ (((P ^ Q) v ($\neg$P ^ $\neg$Q)) v ((R ^ Q) v ($\neg$R ^ $\neg$Q)))

Does that help?

3. Apr 1, 2012

RUBSTEP

Im sorry ive shouldve been more clear. That formula is what i have tried to get to but with no success.

4. Jul 15, 2012

bonfire09

yeah I remember doing this one. Velleman isn't too clear on what he wants. I made a table but that did seem a little too simple. I tried hard to try to transform that first part into the second part but it is quite tricky. I wouldn't worry too much about it.

5. Jul 15, 2012

pendesu

I would start by assuming (P→Q) and (Q→R) and then try to prove the rest. I can get you started in this direction. For example,

Suppose P. Then Q. Then R. Thus, P→R.

Then show the disjunction with the bijections is true too and then the "backwards" direction of assuming RHS and proving LHS of the bijection that you're trying to establish.

(Didn't realize how old this thread is -_-)

Last edited: Jul 15, 2012