1. Not finding help here? Sign up for a free 30min 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!

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.)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: I need help with logic
  1. I need a lot of help. (Replies: 3)

Loading...