Rules of Inference

Truth tables and exponential explosion

We know there’s a way to establish the validity (or invalidity) of any propositional logic argument using the truth-table method. It’s simple and easy to mechanize in terms of actionable steps. But this method suffers from one small problem. Let’s see if we can identify the problem.

Imagine we had to prove if the following argument is valid or not. We would have to create the associated table given below:

$\text{p} → \text{q}, \text{p}, ∴\text{q}$

Let’s further imagine extending the argument slightly, where one more symbol is added to it:

$\text{p}, \text{p} → \text{q}, \text{q} → \text{r}, ∴\text{r}$

Here’s how we’d extend the same argument, but this time by incorporating all 26 letters of the English alphabet:

$a,a \to b,b \to c,...,y \to z ∴ z$ ...