Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Stumped on a deduction problem

  1. Mar 1, 2005 #1

    honestrosewater

    User Avatar
    Gold Member

    This is Propositional Logic. I just need to fill in the steps. Most obviously, if I can infer R -> S, I have a hypothetical syllogism, but I can't see how to infer R -> S. And nothing else I've tried works.

    1. Q -> (R -> S) Premise
    2. Q -> R Premise
    3.
    4.
    5. Q -> S Conclusion
     
  2. jcsd
  3. Mar 1, 2005 #2
    [(Q -> (R -> S)) & (Q -> R)] -> (Q -> S), is tautologous by truth tables.
    Therefore your argument is valid.
     
  4. Mar 1, 2005 #3

    Galileo

    User Avatar
    Science Advisor
    Homework Helper

    I don't know how to write it out formally. You could make a truth table.

    Anyway, suppose Q, then R->S because of (1) and R because of (2), thus S.
     
  5. Mar 1, 2005 #4

    honestrosewater

    User Avatar
    Gold Member

    I'm sure it's valid- it's a problem from a book. I have to actually infer the conclusion using natural deduction- and show each step. For instance,
    1. ~A -> A [/therefore, A]
    2. ~~A v A [1, Impl.]
    3. A v A [2, D.N.]
    4. A [3, Taut. /QED]

    The book gives the premise(s) and conclusion and tells you how many steps to use. I've done a gazillion of them; They usually only take a few seconds, but I can't get anywhere on this one. Should I list the rest of the inference rules?
     
  6. Mar 1, 2005 #5

    honestrosewater

    User Avatar
    Gold Member

    I can't suppose Q. And I don't want to infer S, I want infer (Q -> S). I'll post the rules.

    Edit:
    Here are the inference rules. You can only apply one rule per step/line. (read "/" as a line break, ".:" as "therefore"):
    1. Modus Ponens (M.P.)
    2. Modus Tollens (M.T.)
    3. Hypothetical Syllogism (H.S.): p -> q / q -> r / .: p -> r.
    4. Disjunctive Syllogism (D.S.): p V q / ~p / .: q.
    5. Constructive Dilemma (C.D.): (p -> q) & (r -> s) / p V r / .: q V s.
    6. Absorption (Abs.): p -> q / .: p -> (p & q).
    7. Simplification (Simp.): p & q / .: p.
    8. Conjunction (Conj.): p / q / .: p & q.
    9. Addition (Add.): p / .: p V q.
    Here are the replacement rules. One rule per step. (read "/" as a line break):
    1. De Morgan's Theorems: ~(p & q) <=> ~p v ~q -and same for disjunction.
    2. Commutation: You know (if not, ask).
    3. Association: You know.
    4. Distribution: You know.
    5. Double Negation: You know.
    6. Transposition: (p -> q) <=> (~q -> ~p)
    7. Material Implication: (p -> q) <=> (~p v q)
    8. Material Equivalence: (p <=> q) <=> [(p -> q) & (q -> p)] <=> [(p & q) v (~p & ~q)]
    9. Exportation: [(p & q) -> r] <=> [p -> (q -> r)]
    10. Tautology: p <=> p & p - and same for disjunction.

    You apply a rule to a premise or premises, getting a new proposition and repeat until you infer the conclusion. Of course, you can also apply rules to any proposition you've inferred from the premise(s). So, for instance,
    1. ~A -> A [/.: A] {(Premise) (Conclusion sought)}
    2. ~~A v A [1, Impl.] {(New proposition) (Line # rule was applied to) (Rule applied)}
    3. A v A [2, D.N.]
    4. A [3, Taut. /QED]
     
    Last edited: Mar 1, 2005
  7. Mar 1, 2005 #6

    honestrosewater

    User Avatar
    Gold Member

    This is seriously driving me crazy. I can prove it in several more steps than required. Maybe someone can see a way to shorten the longer proof:

    1. Q -> (R -> S)
    2. Q -> R [/.: Q -> S]
    3. (Q & R) -> S [1, Exp.]
    4. (R & Q) -> S [3, Comm.]
    5. R -> (Q -> S) [4, Exp.]
    6. Q -> (Q -> S) [2, 5, H.S.]
    7. (Q & Q) -> S [6, Exp.]
    8. Q -> S [7, Taut./QED]

    Please help if you can- it's really eating at me.
     
  8. Mar 2, 2005 #7
    I don't think it's possible with just those rules you have there. One thing to note, you can't infer R->S by any means since it is not necessarily true. The steps I would use are, "((R->S)&R)->S, Q->((R->S)&R)," but those don't seem to be in your system.
     
  9. Mar 2, 2005 #8

    honestrosewater

    User Avatar
    Gold Member

    Eureka! :biggrin: It's about d@mn time.

    1. Q -> (R -> S)
    2. Q -> R [/.: Q -> S]
    3. Q -> (Q & R) [2, Abs.]
    4. (Q & R) -> S [1, Exp.]
    5. Q -> S [3, 4, H.S./QED]

    How did I miss that?! Oh well. Thanks, everyone.
     
  10. Mar 2, 2005 #9
    Aha, I see.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Stumped on a deduction problem
  1. Need deduction to help (Replies: 1)

Loading...