0

sigh stuck on another problem

Premises P

Conclusion (( ~(Q → R) → ~P) → (~R → ~Q))

I am allowed to use Modus Ponens, Modus Tollens, Hypothetical Syllogism, Simplification, Conjunctions, Addition, Disjunctive Syllogism, Constructive Dilemma, and Double Negation, as well as a basic conditional proof (assuming the antecedent of the conclusion).

  1. P / (( ~(Q → R) → ~P) → (~R → ~Q)  )

    __________

  2. | ( ~ ( Q → R ) → ~ P ) 1 CPA

  3. | ~~ P 1 DN

  4. | ( ~~ ( Q → R )) 2,3 MT

  5. | ( Q → R ) 4 DN

Then I'm stuck. Is there a trick for converting the ( Q --> R ) to a ( ~Q --> ~R)?

Improve this question
3
  • "a trick for converting the ( Q --> R ) to a ( ~Q --> ~R)?" NO: the two are not equivalent.
    – Mauro ALLEGRANZA
    Jun 6, 2019 at 10:25
  • Well, I actually looked at this wrong, I need to flip the R and Q and change them both to nots... Looking at your comment below and seeing if this will help
    – littlewierdo
    Jun 6, 2019 at 10:37
  • " Is there a trick for converting the ( Q --> R ) to a ( ~Q --> ~R)?" No, that's not possible, but also not what you want. You actually seek (~R → ~Q) which is obtained by assuming ~R, assuming Q, deriving a contradiction from Q → R, thus enabling you to discharging the assumptions with negation introduction and conditional introduction.
    – Graham Kemp
    Jun 6, 2019 at 23:50

3 Answers 3

Reset to default
1

Skecht of a proof with Natural Deduction :

Assume the antecedent of the formula to be proved : ~(Q → R) → ~P and assume in addition ~ R, Q and Q → R.

Use the "ausiliary" assumptions to derive R through two contradictions.

Alternative proof, following your attempt :

1) P --- premise

2) ~(Q → R) → ~P --- assumed

3) ~~P --- from 1) by Double Negation

4) ~~(Q → R) --- from 2) and 3) ny Modus Tollens

5) (Q → R) --- from 4) by DN

6) (~R → ~Q) --- from 4) by Transposition.

Improve this answer
8
  • I dont understand, I cant assume ~R because it isnt one of the premises, nor is it part of the antecedent of the conclusion.
    – littlewierdo
    Jun 6, 2019 at 10:40
  • This involves rules that I cannot use, or I am not seeing what lines you are getting ~R from. Using the rules Ive been given, I cant just assume a ~R unless I can use a rule to generate it. Does that make sense? Im taking introduction to logic so many of the more advanced rules are things we cant use :(
    – littlewierdo
    Jun 6, 2019 at 10:49
  • Yea, in this system, we can only assume the antecedent of the conclusion, at least for now. Maybe more advanced stuff lets us assume more, but we have to work within the confines of that limitation for the time being. The name of the text book is Introduction to formal logic, if that helps
    – littlewierdo
    Jun 6, 2019 at 10:55
  • Ive done 25 of these tonight, I got through all myself except 3, one of which you helped me earlier with, then this one, and one other that hopefully I can figure out
    – littlewierdo
    Jun 6, 2019 at 11:01
  • Looking through the textbook, I can use transposition, Im going to look up a proof for how to derive that. We didnt cover contraposition or material implication so I cant use those, or perhaps they go by a different name?
    – littlewierdo
    Jun 6, 2019 at 11:08
0

Here is a solution formatted using a Fitch-like natural deduction proof checker linked to below with a text explaining the rules in more detail:

enter image description here

I proceeded similarly to the way you are proceeding.

Because the goal is a conditional I assume the antecedent of the conditional on line 2.

Since the consequence of that conditional is also a conditional, I start another subproof assuming the antecedent of that conditional ¬R on line 3. This is where our proofs differ.

The subproof on lines 4 and 5 are needed for this proof checker since I do not have double negative introduction, but I can easily derive it. However, I do have double negative elimination (DNE) which allows me to derive line 7.

This is similar to where you are in your proof except for my line 3 where I assumed ¬R. Again the reason I assumed that is because the consequence of the goal, ¬R → ¬Q, is a conditional. I have to derive that first and so assume its antecedent.

There is no need to go from (Q→R) to (¬Q→¬R). By assuming ¬R on line 3 I can derive ¬Q on line 12 and then introduce the desired conditional on line 13.

The rules I have used are modus tollens (MT), double negative elimination (DNE), conditional elimination (→E), conditional introduction (→I), contradiction introduction (⊥I) and negation introduction (¬I).

Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.openlogicproject.org/

P. D. Magnus, Tim Button with additions by J. Robert Loftis remixed and revised by Aaron Thomas-Bolduc, Richard Zach, forallx Calgary Remix: An Introduction to Formal Logic, Winter 2018.

Improve this answer
3
  • So, this has me confused. How is the antecedent of ~ ( Q --> R ) --> P equivalent to ~R? Or more simply, how is ~ ( Q --> R ) equivalent to ~ R? As noted in the original post, I cant make any inferences other than the rules I mentioned, I have to derive how ~(Q-->R) is equivalent to ~R
    – littlewierdo
    Jun 6, 2019 at 12:53
  • @littlewierdo That antecedent, after assuming it on line 2, must allow us to derive the consequent. But note what the consequent is. It is ~R --> ~Q.. To derive that means to deal with it like we dealt with the larger conditional which is our goal. We have to make another assumption of ~R and derive ~Q. If we can do that then we can derive ~R --> ~Q. If we can do that then we can derive the larger conditional which is the goal.
    – Frank Hubeny
    Jun 6, 2019 at 13:21
  • @littlewierdo The technique is similar to what you would need to do on the other question you asked. I provided an answer to that as well hoping to make the technique clear: philosophy.stackexchange.com/a/63858/29944
    – Frank Hubeny
    Jun 6, 2019 at 13:55
0

You seek to introduce two conditionals. Do that.

 1.|_ P                             Premise
 2.|  |_ ~(Q → R) → ~P              Ass
 3.|  |  |_ ~R                      Ass
   :  :  :
  .|  |  |  ~Q                      
  .|  |  ~R → ~Q                    →I 3-?
  .|  (~(Q → R) → ~P) → (~R → ~Q)   →I 2-?

Now you need to introduce a negation. Let's do that.

 1.|_ P                             Premise
 2.|  |_ ~(Q → R) → ~P              Ass
 3.|  |  |_ ~R                      Ass
 4.|  |  |  |_ Q                    Ass
   :  :  :  :
  .|  |  |  |  #                    
  .|  |  |  ~Q                      ~I 4->
  .|  |  ~R → ~Q                    →I 3-?
  .|  (~(Q → R) → ~P) → (~R → ~Q)   →I 2-?

But what are we contradicting? We have a nice choice of premises and assumptions.

Well, if we can derive ~(Q→R), we can use it to derive ~P to contradict the premise. 

 1.|_ P                             Premise
 2.|  |_ ~(Q → R) → ~P              Ass
 3.|  |  |_ ~R                      Ass
 4.|  |  |  |_ Q                    Ass
   :  :  :  :
  .|  |  |  |  ~(Q → R)             ?
  .|  |  |  |  ~P                   →E 2,?
  .|  |  |  |  #                    ~E 1,?
  .|  |  |  ~Q                      ~I 4-?
  .|  |  ~R → ~Q                    →I 3-?
  .|  (~(Q → R) → ~P) → (~R → ~Q)   →I 2-?

Now we need to introduce a negation. And we're done.

 1.|_ P                             Premise
 2.|  |_ ~(Q → R) → ~P              Ass
 3.|  |  |_ ~R                      Ass
 4.|  |  |  |_ Q                    Ass
 5.|  |  |  |  |_ Q → R             Ass
 6.|  |  |  |  |  R                 →E 5,4 
 7.|  |  |  |  |  #                 ~E 6,3
 8.|  |  |  |  ~(Q → R)             ~I 5-7
 9.|  |  |  |  ~P                   →E 2,8
10.|  |  |  |  #                    ~E 1,9
11.|  |  |  ~Q                      ~I 4-10
12.|  |  ~R → ~Q                    →I 3-11
13.|  (~(Q → R) → ~P) → (~R → ~Q)   →I 2-12
Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .