Informal proofs in zeroeth order logic

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. To illustrate this I’ll use the statement \({ \{ [ (p ⊃ q) ∧ (q ⊃ r) ] ⊃ (p ⊃ r) \} }\) which I proved earlier by the method of truth tables. I’ll first give a version without tableaux and then explain how tableaux can be used to organise the argument.

Suppose \({ \{ [ (p ⊃ q) ∧ (q ⊃ r) ] ⊃ (p ⊃ r) \} }\) is 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 }\).