Problem Detail: 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:
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
Asked By : Padenton
Answered By : Gilles
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.
$(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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/22514
