1

I've been through the truth table and I can see how it works but I can't exactly understand why. The proof presented in the book (Logical Reasoning: A First Course by Nederpelt and Kamareddine) says that the derivation is as follows:

$$1. \{Assume: P\}$$ $$2. \{Assume: Q\}$$ $$3. \{Valid(1): P\}$$ $$4. \{By(2) and (3): Q \implies P\}$$ $$5. \{By(1) and (4): P \implies (Q \implies P)\}$$

Khaled Nassar
  • 115
  • Beginners often have trouble grasping the intuition of material implication. Voted to reopen. – Dan Christensen Oct 02 '14 at 19:18
  • I'd like to know if this derivation is based on having seen "the Deduction Theorem" or something similar, to give context to what the OP is missing or misunderstanding in the presentation. – hardmath Oct 02 '14 at 19:59
  • I haven't seen "the Deduction Theorem" before, at least not that it was mentioned. All that the book mentioned was that this derivation is based on Natural Deduction. It's a university intro book to logic and doesn't seem to elaborate much on anything. – Khaled Nassar Oct 06 '14 at 08:02

3 Answers3

1

It is a tautology, i.e. a formula identically true (i.e. a formula $\mathcal A$ such that $\mathcal A \equiv T$), as you as verified using truth table method.

Thus, by Completeness Theorem for propositional logic it must be provable.

In many proof system in Hilbert-style (for propositional logic) it is an axiom.

We can prove it with Natural Deduction.

Proof :

i) $P$ - assumed

ii) $Q$ --- assumed

iii) $P,Q \vdash P$ --- from i) and ii)

iv) $P \vdash (Q \rightarrow P)$ --- from iii) by $\rightarrow$-I

v) $\vdash P \rightarrow (Q \rightarrow P)$ --- from iv) by $\rightarrow$-I.

For an explanation, see Jan von Plato, Elements of Logical Reasoning (2013), page 22 :

There is a limiting case of a derivation in which an assumption $A$ is made. It is at the same time a derivation of the conclusion $A$ from the assumption $A$, as in:

<ol>
<li><p>$A$ : hypothesis</p></li>
<li><p>$A \rightarrow A$ : 1,$\rightarrow$-I</p></li>
</ol>

<p>In terms of the derivability relation, the hypothesis on line 1 can be written as $A \vdash A$ and line 2 as $\vdash A \rightarrow A$.</p>

<p>Consider as another case $\vdash A \rightarrow (B \rightarrow A)$. Verbally, if we assume $A$, then $A$ follows under any other assumption $B$ :</p>

<ol>
<li><p>$A$ : hypothesis</p></li>
<li><p>$B \rightarrow A$ : 1,$\rightarrow$-I</p></li>
<li><p>$A \rightarrow (B \rightarrow A)$ : 1–2,$\rightarrow$-I</p></li>
</ol>

<p>This does not look particularly nice: We have closed an assumption $B$ that was not made. But if we say that an assumption was used $0$ times, the thing starts looking more reasonable. [...] we can say that assumption $B$ in the derivation of $A \rightarrow (B \rightarrow A)$ was used <em>vacuously</em>.</p>
Mauro ALLEGRANZA
  • 94,169
  • It is Natural Deduction, my apologies. And if I got this right, then this is (equivalent to) self-equivalence ($A \implies A \equiv T$) and it doesn't matter what $B$ is as $A \implies A$ is a tautology as soon as $A$ was assumed to be true? – Khaled Nassar Oct 01 '14 at 10:10
  • @KhaledNassar - your comment is not clear. (i) Right : $A \rightarrow A$ is a tautology (i.e. is $\equiv T$). (ii) From it we can derive other formula by substitution, like : $B \rightarrow B$ or $(P \lor Q) \rightarrow (P \lor Q)$. But (iii) there is no substitution into $A \rightarrow A$ which can give $P \rightarrow (Q \rightarrow P)$. – Mauro ALLEGRANZA Oct 01 '14 at 10:18
  • I get it now but could you elaborate more on the last part of the excerpt from the book please? About the assumption $B$ being used vacuously? – Khaled Nassar Oct 01 '14 at 10:27
  • Compare the derivation of $A→A$. Assume $A$; from it $A$ follows; then "discharge" the assumption to get $A→A$. Now, with $A→(B→A)$ assume $A$ and $B$; derive $A$: here the second assumption $B$ is not necessary (the assumption $B$ being used vacuously). Then we "discharge" it deriving $(B→A)$ and finally discharge also $A$ to derive $A→(B→A)$. It is like a "trick" but it works; it formalize the "intuitive" fact that if something (call it:Z) follows from an assumption X, adding a "vacuous" assumption Y does not make any harm: the proof of Z from X "works" also as a proof of Z from X and Y. – Mauro ALLEGRANZA Oct 01 '14 at 11:16
1

Prove $P\implies [Q\implies P]$, or equivalently $\neg[P\land [Q\land \neg P]]$.

Suppose to the contrary that $P\land [Q\land \neg P]$ is true and obtain the obvious contradiction $P \land \neg P$.

Everything, even that which is false, implies that which is true.

Similarly, we could also prove that $P\implies [\neg P \implies Q]$, or equivalently $\neg[P \land [\neg P \land \neg Q]]$.

Everything, even that which is false, follows from that which is false.

Dan Christensen
  • 14,529
0

This is a proof by Natural Deduction. The variables $Q$ and $P$ have been discharged respectively in steps $4$ and $5$. But the semantics are thus:

This essentially means If $P$ then $[$ If $Q$ then $P$ $]$. Now suppose $P$ is true. Then the statement If $Q$ then $P$ is true regardless of what the statement $Q$ is. Because $P$ if true if $Q$ is true because $P$ is true anyway. Now we have just concluded that if $P$ is true then the statement $[$ If $Q$ then $P$ $]$ is true. Whence, we can conclude that If $P$ then $[$ If $Q$ then $P$ $]$ is a true statement.

Ishfaaq
  • 10,034
  • 2
  • 30
  • 57