Deriving the Truth Table for Material Implication

Question

The truth table for material implication seems to be inevitable given the laws of the excluded middle and double negation as well as certain other "common sense" notions about logical implications; namely, modus ponens, the deduction theorem and reductio ad absurdum.

Thm: $A\land B \implies [A\implies B]$

1. $A\land B\space\space\space$ (Assume)
2. $A\space\space\space$ (Assume)
3. $B\space\space\space$ ($\land_{ER}$)
4. $A\implies B\space\space\space$ ($\implies_{I,2,3}$)
5. $A\land B \implies [A\implies B]\space\space\space$ ($\implies_{I,1,4}$)

Thm: $A\land \neg B \implies \neg[A\implies B]$

1. $A\land \neg B\space\space\space$ (Assume)
2. $A\implies B\space\space\space$ (Assume)
3. $A\space\space\space$ ($\land_{E,1}$)
4. $\neg B\space\space\space$ ($\land_{E,1}$)
5. $B\space\space\space$ (MP, 2, 3)
6. $B\land \neg B\space\space\space$ ($\land_I$, 5, 4)
7. $\neg [A\implies B]\space\space\space$ (RAA, 2,6)
8. $A\land \neg B \implies \neg[A\implies B]\space\space\space$ ($\implies_I$, 1,7)

Thm: $\neg A \implies [A\implies B]$

1. $\neg A\space\space\space$ (Assume)
2. $A\space\space\space$ (Assume)
3. $\neg B\space\space\space$ (Assume)
4. $A \land \neg A\space\space\space$ ($\land_{ I,1,2}$)
5. $\neg\neg B\space\space\space$ (RAA, 3,4)
6. $B\space\space\space (\neg\neg_{E,5})$
7. $A\implies B\space\space\space (\implies_{I,2,6})$
8. $\neg A \implies [A\implies B]\space\space\space (\implies_{I,1,7})$

Also see my blog posting Material Implication: If Pigs Could Fly.

Comments?

Answer 1

$\def\fitch#1#2{~\begin{array}{|l}#1\\\hline#2\end{array}}$ $\def\labelfitch#1#2#3{\begin{array}{|l|}\hline#1\\\hline~\fitch{#2}{#3}\\ \hline\end{array}}$

The truth table for material implication seems to be inevitable given the Law of the Excluded Middle.

EDIT: Also given certain "common sense" notions about logical implications, namely: modus ponens, the deduction theorem, reductio ad absurdum and removing double negations.

Well, these "common sense notions" are basically answers to the question "what the hey do these symbols even mean?"   So when certain of these rules of inference are accepted they will, of course, define the "truth table" for the symbols in the logic system that uses them.   It is rather the point.

However, The Law of Excluded Middle, is not required to produce the usual table for material implication.   Don't confuse it with the Law of Non-Contradiction.

The Principle of Explosion -that anything may be a valid conclusion from a contradiction- is required for one of the tableau's rows.

So the "truth table" is valid in Intuitionistic and Classical, Two-Valued Logic systems, but not when using a Minimal Logic.

$$\begin{split}A, B&\vdash A\to B\\ \neg A, B&\vdash A\to B\\ \neg A,\neg B&\vdash A\to B\\A,\neg B&\vdash \neg(A\to B) \end{split}$$

---

$A\wedge B\vdash A\to B$ holds via the "conjunctive elimination" and "conditional introduction" rules of inference. $$\fitch{A\wedge B}{B\\\fitch{A}{B}\\A\to B}$$

---

$\neg A\wedge B\vdash A\to B$ likewise holds if we accept the validity of these rules of inference.$$\fitch{\neg A\wedge B}{B\\\fitch{A}{B}\\A\to B}$$

In fact we may as well just affirm $B\vdash A\to B$ is a consequence of the "conditional introduction" rule. In axiomatic systems, this would be accepting $B\to(A\to B)$ as an axiom.

---

$A\wedge\neg B\vdash \neg(A\to B)$ holds when using the rules of "conjunctive elimination", "conditional elimination", "contradiction introduction", and "negation introduction" rules.

$$\fitch{A\wedge\neg B}{\neg B\\A\\\fitch{A\to B}{B\\ \bot}\\\neg(A\to B)}$$

---

Now for the row in the truth table that seems most counterintuative to grasp.

$\neg A\wedge\neg B\vdash A\to B$ holds using "conjunctive elimination", "contradiction introduction", "contradiction elimination", and "conditional introduction" rules.

$$\fitch{ \neg A\wedge\neg B }{ \neg A \\ \fitch{ A }{ \bot \\ B } \\ A\to B }$$

This one usually causes new students to go "what.".   It seems rather bizarre to assume something contrary to a premise in order to utilise the principle of explosion to conclude something contrary to the other premise, and therefore deduce the implication.

---

$$\begin{array}{lll}\labelfitch{\wedge\text{ Elimination}}{\psi\wedge\phi}{\phi}&\labelfitch{\to\text{ Elimination}\\\text{ modus ponens}}{\psi\\\psi\to\phi}{\phi}&\labelfitch{\to\text{ Introduction}\\\text{ deduction theorem}}{\fitch{\psi}{\phi}}{\psi\to\phi}\\\labelfitch{\bot\text{ Introduction}\\\text{ contradiction}}{\phi\\\neg\phi}{\bot}&\labelfitch{\neg\text{ Introduction}\\\text{ reductio ad absurdum}}{\fitch{\phi}{\bot}}{\neg\phi}&\labelfitch{\bot\text{ Elimination}\\\text{explosion}}{\bot}{\phi}\\\hdashline&\labelfitch{\neg\neg\text{ Elimination}}{\neg\neg\phi}{\phi}\end{array}$$

Answer 2

When it comes to "common sense" and "self-evident", we could also meander a little differently. Here is a nice way. First we look at the undisputed rows of implication, namely:

A   B     A => B
----------------
F   F       ?
F   T       ?
T   F       F
T   T       T

So the third and fourth row would be undisputed and only the other rows would be occult. Now there are the following options to fill-in the blanks:

A   B      T1    T2    T3    T4
---------------------------------
F   F       F     T     F     T
F   T       F     F     T     T

But only T4 would make X=>(X v Y) a tautology.
Credits: Edmund M. Clarke
https://www.cs.cmu.edu/~emc/15414-f12/lecture/propositional_logic.pdf