At the moment we have a language and an interpretation, or rather a class of interpretations of that language but we don’t have the axioms or rules of inference necessary for a formal system so we can’t do formal proofs. We can still do informal proofs though since our interpretation, or rather interpretations, give us a notion of truth. One method of informal proof is truth tables. It’s not a very efficient method though. The number of logical operators appearing in an expression is called the “degree” of the expression. A truth table for an expression of degree \({ d }\) with \({ n }\) variables will have \({ d + n }\) columns and \({ 2 ^ n }\) rows. There are better methods, including what’s called the ``method of analytic tableaux’’, which is our next topic.
The method of analytic tableaux is really just a bookkeeping device for proof by contradiction combined with a form of case by case analysis. Truth table methods also involve a form of case by case analysis, but analytic tableaux use a less drastic one, where the number of cases to consider needn’t grow exponentially with the number of variables. I’ll illustrate this with a few examples, first giving a version without tableaux and then showing how tableaux can be used to organise the arguments.
Our first example will be the tautology \({ \{ [ ( ¬ p ) ∧ ( ¬ q ) ] ⊃ [ ¬ ( p ∨ q ) ] \} }\). How could \({ \{ [ ( ¬ p ) ∧ ( ¬ q ) ] ⊃ [ ¬ ( p ∨ q ) ] \} }\) fail to be true? It’s a statement of the form \({ ( P ⊃ Q ) }\), where \({ P }\) is \({ [ ( ¬ p ) ∧ ( ¬ q ) ] }\) and \({ Q }\) is \({ [ ¬ ( p ∨ q ) ] }\). Strictly speaking it’s of the form \({ \{ P ⊃ Q \} }\), but our convention is that different types of parentheses are considered interchangeable, so we cat treat it just like we treat statements of the form \({ ( P ⊃ Q ) }\). We can tell that it’s a \({ ⊃ }\) type expression because \({ ⊃ }\) is the only operator inside only one set of parentheses. For \({ ( P ⊃ Q ) }\) to be false \({ P }\) would need to be true and \({ Q }\) would need to be false. In our case, \({ [ ( ¬ p ) ∧ ( ¬ q ) ] }\) needs to be true and \({ [ ¬ ( p ∨ q ) ] }\) needs to be false. We “want” \({ [ ( ¬ p ) ∧ ( ¬ q ) ] }\) to be true and \({ [ ¬ ( p ∨ q ) ] }\) to be false. I’ve put the quotation marks in because ultimately we want a contradiction, so we will want the opposite of what I’ve just written, but for now we proceed as if we were trying to make this true. If \({ [ ( ¬ p ) ∧ ( ¬ q ) ] }\) is true then so are \({ ( ¬ p ) }\) and \({ ( ¬ q ) }\). So both \({ p }\) and \({ q }\) are false. If \({ [ ¬ ( p ∨ q ) ] }\) is false then \({ ( p ∨ q ) }\) is true. Then \({ p }\) is true or \({ q }\) is true. But we already know both are false. So \({ \{ [ ( ¬ p ) ∧ ( ¬ q ) ] ⊃ [ ¬ ( p ∨ q ) ] \} }\) can’t fail to be true. In other words, it’s a tautology. Is this any faster than writing down a truth table? Probably not, but it generalises better.
As a second example, consider the tautology \({ \{ [ (p ⊃ q) ∧ (q ⊃ r) ] ⊃ (p ⊃ r) \} }\). Suppose \({ \{ [ (p ⊃ q) ∧ (q ⊃ r) ] ⊃ (p ⊃ r) \} }\) were false for some value of \({ p }\), \({ q }\) and \({ r }\). For those values \({ [ (p ⊃ q) ∧ (q ⊃ r) ] }\) must be true and \({ (p ⊃ r) }\) must be false. Since \({ [ (p ⊃ q) ∧ (q ⊃ r) ] }\) is true so are \({ (p ⊃ q) }\) and \({ (q ⊃ r) }\). So in our hypothetical example \({ (p ⊃ q) }\) and \({ (q ⊃ r) }\) are true and \({ (p ⊃ r) }\) is false. Since it is false \({ p }\) must be true and \({ r }\) must be false. This is as far as we can get without splitting the argument into cases. Since \({ (p ⊃ q) }\) is true \({ p }\) is false or \({ q }\) is true. But we already saw that \({ p }\) is true so we can exclude that possibility and conclude that \({ q }\) must be true. Since \({ (q ⊃ r) }\) is true \({ q }\) is false or \({ r }\) is true. But we already saw that \({ q }\) is true \({ r }\) is false so we can exclude both possibilities. Thus the assumption that there are \({ p }\), \({ q }\), and \({ r }\) which make \({ \{ [ (p ⊃ q) ∧ (q ⊃ r) ] ⊃ (p ⊃ r) \} }\) false is untenable. In other words \({ \{ [ (p ⊃ q) ∧ (q ⊃ r) ] ⊃ (p ⊃ r) \} }\) holds for all values of \({ p }\), \({ q }\), and \({ r }\).
As a third example, consider \({ \{ [ p ⊃ ( q ⊃ r ) ] ⊃ [ ( p ⊃ q ) ⊃ ( p ⊃ r ) ] \} }\). Again we have something of the form \({ ( P ⊃ Q ) }\), so for this to be false \({ P }\) must be true and \({ Q }\) must be false, i.e. \({ [ p ⊃ ( q ⊃ r ) ] }\) is true and \({ [ ( p ⊃ q ) ⊃ ( p ⊃ r ) ] }\) is false. \({ [ ( p ⊃ q ) ⊃ ( p ⊃ r ) ] }\) is also of the form \({ ( P ⊃ Q ) }\). For it to be false we need \({ ( p ⊃ q ) }\) to be true and \({ ( p ⊃ r ) }\) to be false. \({ ( p ⊃ r ) }\) is also of the form form \({ ( P ⊃ Q ) }\). For it to be false we need \({ p }\) to be true and \({ r }\) to be false. So \({ [ p ⊃ ( q ⊃ r ) ] }\), \({ ( p ⊃ q ) }\) and \({ p }\) are all true and \({ r }\) is false. How can \({ [ p ⊃ ( q ⊃ r ) ] }\) be true? It’s of the form \({ ( P ⊃ Q ) }\) and so can be true if \({ P }\) is false or \({ Q }\) is true. In this case that means \({ p }\) is false or \({ ( q ⊃ r ) }\) is true. But \({ p }\) is true so \({ ( q ⊃ r ) }\) must be true.
Where are we? We wanted to show \({ \{ [ p ⊃ ( q ⊃ r ) ] ⊃ [ ( p ⊃ q ) ⊃ ( p ⊃ r ) ] \} }\) is true, so we assumed it was false and have found that \({ ( q ⊃ r ) }\), \({ ( p ⊃ q ) }\) and \({ p }\) must be true and \({ r }\) must be false. If \({ ( p ⊃ q ) }\) is true then \({ p }\) is false or \({ q }\) is true, but \({ p }\) is true so \({ q }\) is true. If \({ ( q ⊃ r ) }\) is true then \({ q }\) is false or \({ r }\) is true, but \({ q }\) is true and \({ r }\) is false, so we have a contradiction. Therefore \({ \{ [ p ⊃ ( q ⊃ r ) ] ⊃ [ ( p ⊃ q ) ⊃ ( p ⊃ r ) ] \} }\) must be true. The main problem with such arguments is keeping track of what we know and, if we need to split things into cases, which case or subcase we’re in.