# Stumped on a deduction problem

1. Mar 1, 2005

### honestrosewater

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. Mar 1, 2005

### Owen Holden

[(Q -> (R -> S)) & (Q -> R)] -> (Q -> S), is tautologous by truth tables.

3. Mar 1, 2005

### Galileo

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.

4. Mar 1, 2005

### honestrosewater

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?

5. Mar 1, 2005

### honestrosewater

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.
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
6. Mar 1, 2005

### honestrosewater

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]

7. Mar 2, 2005

### Bartholomew

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.

8. Mar 2, 2005

### honestrosewater

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.

9. Mar 2, 2005

Aha, I see.