Deriving the Truth Table for Material Implication

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.

• You are effectively equating material implication with logical implication. – Bram28 Mar 10 '18 at 18:23
• You seem to be assuming a whole lot of assorted stuff for your "inevitable". – Henning Makholm Mar 10 '18 at 19:43
• @DanChristensen "Without LEM, I could only derive the first line of the table here." This is false. All of those theorems are constructively true. – Derek Elkins Mar 10 '18 at 22:34
• @DanChristensen It depends on the proof systems, but in LJ (and likely most structural proof systems) all of the statements would be derived. If you want a Hilbert-style proof system, then the one on Wikipedia also does not include any of these as axioms, though it does mention a variation with the last as an axiom. This is not surprising as the last is the principle of explosion, and if dropped produces minimal logic. – Derek Elkins Mar 10 '18 at 23:29
• @DanChristensen The Law of Excluded Middle is $\vdash \phi\vee\neg\phi$ ("a proposition is true or false; there isn't anything else it could be.") which should not be confused with the Principle of Bivalence (or Reductio Ad Absurdum, Law of Non-Contradiction) which is $\vdash \neg(\phi\wedge\neg\phi)$ (a proposition cannot be both true and false). – Graham Kemp Mar 10 '18 at 23:38

$\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}$$

• Re: "Well, these 'common sense notions' are basically answers to the question what the hey do these symbols even mean?" Exactly so. The truth table for material implication was not cooked up so that some the results would "turn out right." It can be derived from common sense, everyday notions of logical implication. There is nothing "fishy" or paradoxical about it. For true-or-false propositions $A$ and $B$, it seems inevitable, for example, that $\neg A \implies [A \implies B]$. Or, equivalently, that everything follows from a falsehood. – Dan Christensen Mar 11 '18 at 5:52
• Do note, however, that the 'common sense, everyday notions' are not the only ones possible. There are logics which do not admit some of them. – Graham Kemp Mar 11 '18 at 10:42
• Duly noted. Thanks. Also note that everything following from a falsehood might be more directly stated as $A\implies [\neg A \implies B]$. – Dan Christensen Mar 11 '18 at 14:25
• That is indeed the presentation for explosion in an axiomatic system (eg Hilbert). Basically $(\phi\wedge\neg\phi)\to\psi$, or simply $\bot\to\psi$ when using the falsum constant. – Graham Kemp Mar 11 '18 at 22:24

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

• +1 A nice alternative development for the "disputed" cases. – Dan Christensen Mar 18 '18 at 20:07