1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Apr 1, 2012 #1
    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. jcsd
  3. Apr 1, 2012 #2
    [itex]\varphi[/itex][itex]\rightarrow[/itex][itex]\psi[/itex] Is introduced as an abbreviation for or shown to be equivalent to [itex]\neg[/itex][itex]\varphi[/itex] v [itex]\psi[/itex] earlier in that chapter, and [itex]\varphi[/itex][itex]\leftrightarrow[/itex][itex]\psi[/itex] for ([itex]\varphi[/itex][itex]\rightarrow[/itex][itex]\psi[/itex]) ^ ([itex]\psi[/itex][itex]\rightarrow[/itex][itex]\varphi[/itex]), so what you have to show is that

    ([itex]\neg[/itex]P v Q) ^ ([itex]\neg[/itex]Q v R) [itex]\Leftrightarrow[/itex] ([itex]\neg[/itex]P v R) ^ (((P ^ Q) v ([itex]\neg[/itex]P ^ [itex]\neg[/itex]Q)) v ((R ^ Q) v ([itex]\neg[/itex]R ^ [itex]\neg[/itex]Q)))

    Does that help?
  4. Apr 1, 2012 #3
    Im sorry ive shouldve been more clear. That formula is what i have tried to get to but with no success.
  5. Jul 15, 2012 #4
    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.
  6. Jul 15, 2012 #5
    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook