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: I need help with logic

  1. Sep 20, 2005 #1

    _E_

    User Avatar

    Hi Everyone.

    I need some help with a few logic problems. For some reason I just get stuck and can't continue betond the first steps.

    First one
    1. P -> (Q -> R)
    2 S -> (Q -> T)
    3. (Q ^ ~R) ^ ~T
    4. ~P ^ ~S
    Show ~P ^ ~S

    Second One
    1. ~(P v Q) -> R
    2. ~S -> ~Q
    3. ~ <--> ~S
    4. R v S
    Show R v S

    Third One
    1. ([P ^ Q] v R) ^ (~R v Q) -> (P -> Q)
    Show ([P ^ Q] v R) ^ (~R v Q) -> (P -> Q)

    Thanks.
     
    Last edited: Sep 20, 2005
  2. jcsd
  3. Sep 20, 2005 #2

    honestrosewater

    User Avatar
    Gold Member

    Are those your assumptions (aka premises)? What are you trying to prove?
     
  4. Sep 20, 2005 #3

    _E_

    User Avatar

    Ok, sorry about not being clear enough.
    I have gone back and made corrections, I have specified what I am trying to prove.
     
  5. Sep 20, 2005 #4

    honestrosewater

    User Avatar
    Gold Member

    Try the contrapositives of (1) and (2):
    4) Q ^ ~R [from 3]
    5) ~(Q -> R) -> ~P [1]
    6) ~(~Q v R) -> ~P [5]
    7) (~~Q ^ ~R) -> ~P [6]
    8) (Q ^ ~R) -> ~P [7]
    9) ~P [8, 4]

    Try to get ~S the same way.
    Typo?
    Are you taking ([P ^ Q] v R) ^ (~R v Q) as a premise or trying to prove (([P ^ Q] v R) ^ (~R v Q)) -> (P -> Q) from no premises? I'm not sure which rules you have.
     
    Last edited: Sep 20, 2005
  6. Sep 20, 2005 #5

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Looking at his first two examples, it looks as though he's just trying to prove

    ([P ^ Q] v R) ^ (~R v Q) -> (P -> Q)

    from no premises, since in the first two examples he's also made it look like the desired conclusion is the last premise. There is a problem, however, in that this last question is ambiguous. You're missing brackets, so do you want it to be:

    (([P ^ Q] v R) ^ (~R v Q)) -> (P -> Q)

    or

    ([P ^ Q] v R) ^ ((~R v Q) -> (P -> Q))

    ?
     
  7. Sep 20, 2005 #6

    _E_

    User Avatar

    (([P ^ Q] v R) ^ (~R v Q)) -> (P -> Q)
    This is the correct one.
    Sorry about the confusion.
    Also I left something out here, I forgot the P.
    The corrected question is.
    1. ~(P v Q) -> R
    2. ~S -> ~Q
    3. ~P <--> ~S

    Show R v S
     
  8. Sep 21, 2005 #7

    honestrosewater

    User Avatar
    Gold Member

    Did you get the first one?
    _______
    1. ~(P v Q) -> R
    2. ~S -> ~Q
    3. ~P <--> ~S
    Did you try reductio? Assume (~R ^ ~S) and try to derive a contradiction. If you do, you can infer ~(~R ^ ~S), which is equivalent to (R v S). Here's a start:
    4)) ~R ^ ~S [assumption]
    5)) ~R [4]
    6)) ~R -> ~~(P v Q) [1]
    7)) ~R -> (P v Q) [6]
    8)) P v Q [7, 4 (now try to derive ~(P v Q), which is equivalent to (~P ^ ~Q)]
    9)) ~S [4]
    ... can you see it from here? There may be a shorter way that I just can't see yet, but if the proof works...
    _________
    How far can you get by yourself on the last one?
     
  9. Sep 21, 2005 #8

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Could you also specify what rules you have to work with. honestrosewater has recommended that you do things like show ~(P v Q) and use the fact that it is equivalent to (~P ^ ~Q). But are you allowed to use DeMorgan's Law (the one that allows you to infer (~P ^ ~Q) directly from ~(P v Q)) or would you have to derive one of those sentences from the other?
     
  10. Sep 26, 2005 #9

    _E_

    User Avatar

    Well DeMorgan's law is not allowed for these problems.
    I am trying to use an indirect approach to solve them.

    Also, (([P ^ Q] v R) ^ (~R v Q)) -> (P -> Q) is a Theorem.
    So I have to solve it without premisis
     
  11. Sep 26, 2005 #10

    honestrosewater

    User Avatar
    Gold Member

    If your rules are complete, you can prove DeMorgan's laws with them - it's just more work for you. Anywho, what rules do you have? There are many different sets of rules possible.
    These?
    http://en.wikipedia.org/wiki/Propositional_calculus#Inference_rules
    These?
    http://www.mathpath.org/proof/proof.inference.htm
    Different ones?
     
    Last edited: Sep 26, 2005
  12. Sep 26, 2005 #11

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Code (Text):
    1  | (((P & Q) v R) & (~R v Q))      assumption
       |--------------------------
    2  || P                           assumption
       ||-------------------------
    3  || ((P & Q) v R)          from 1
    4  || (~R v Q)               from 1
    5  ||| ~Q                     assumption
       |||------------------------
    6  |||| ~R                      assumption
       ||||-----------------------
    7  |||| ~R                        from 6
       |||
    8  |||| Q                             assumption
       ||||-----------------------
    9  ||||| R                           assumption
       |||||----------------------
    10 ||||| Q                           from 8
    11 ||||| ~Q                          from 5
    12 |||| ~R                           from 9-11 (reductio)
    13 ||| ~R                            from 4, 6-7, 8-12 (disjunction elimination)
    14 |||| R                          assumption
       ||||-----------------------
    15 |||| R                            from 14
       |||
    16 |||| (P & Q)                      assumption
       ||||-----------------------
    17 ||||| ~R                           assumption
       |||||----------------------
    18 ||||| Q                              from 16
    19 ||||| ~Q                            from 5
    20 |||| R                           from 17-19
    21 ||| R                            from 3, 14-15, 16-20 (disj. elim.)
    22 || Q                           from 3, 13, 21 (reductio)
    23 | (P -> Q)                   from 2, 22 (conditional introduction)
    24 ((((P & Q) v R) & (~R v Q)) -> (P -> Q))      from 1, 23 (cond. intro.)
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook