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!

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...