Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Can $R$ be inferred from $P$, $Q$, and $(P \to Q) \to R$ using only modus ponens?
My understanding is that it can, as shown below, but I was told this was incorrect.

Proof of ${P, Q, (P \to Q) \to R} \vdash R$ using modus ponens:

P, Q, (P->Q)->R  : Given  
Q, (Q)->R        : By Modus Ponens  
R                : By Modus Ponens  
share|improve this question
    
I don't believe you can get it via MP directly. What you can get is (P^Q) from P and Q, and, though I don't recall if it is an axiom or requires proof, (P^Q)->(P->Q). From that, you can get your (P->Q), from which you can get R. Been ages since I did logic proofs like this, so please correct me if I'm wrong here. –  Will Mar 12 at 3:59

2 Answers 2

up vote 5 down vote accepted

Given $P$, $Q$ and $(P \to Q) \to R$, there is no way to apply modus ponens. You would need to have $(P \to Q)$. If you had $P$, $Q$ and $P \to (Q \to R)$, then you could apply modus ponens twice the way you did, but $P \to (Q \to R)$ and $(P \to Q) \to R$ are different.

$P \to (Q \to R)$ says “if I have P, then if I have Q, then I can get R”.
$(P \to Q) \to R$ says “if I can get Q given P, then I can get R”. It requires a method of getting from P to Q.

It is true that given $P$, $Q$ and $(P \to Q) \to R$, you can deduce $R$. You can see that with truth tables, for example. However this requires logical rules that go beyond modus ponens. This has a mathematical consequence: this deduction is only valid in logics where those extra rules are available (such as classical logic).

There is a computational interpretation of these deductions. $P \to Q$ can be interpreted as a function that produces a $Q$ given a $P$. Modus ponens then comes down to applying a function. Given a function $f : P \to (Q \to R)$, you can apply $f$ to a $P$, which produces a new function $Q \to R$; when you apply this function to a $Q$, you get an $R$. Given a function $g : (P \to Q) \to R$, the situation is different: you need a function from $P$ to $Q$ to get started. Given a $Q$, it's easy: you can use a constant function that returns this $Q$. But that first step of constructing the constant function is not modus ponens.

share|improve this answer

No, you can't get $R$ using only modus ponens. Your second line is incorrect. If we knew $P \to Q$, then from that and $(P \to Q) \to R$ you could get $R$. But you can't get $Q \to R$ from $P$ and $(P \to Q) \to R$ using modus ponens (maybe with some other rule, but not modus ponens alone).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.