CONSISTENCY AND COMPLETENESS (challenge level)
That the truth tree method is consistent with the rules of inference we have developed so far would seem to be self-evident. As we remarked in chapter 12.1, each of those rules corresponds to a valid argument form, thus establishing the consistency of the rules of inference of propositional logic: any sequent or argument form that is provable using the rules of inference of propositional logic is itself valid.
We did not, however, prove that any argument form that is valid according to the definition of formal validity is provably valid by those rules, i.e., that the set of rules of inference of propositional logic is complete. [See the definitions of consistency and completeness in section 12.1.2 above.] It is easier, however, to prove the consistency and completeness of the truth tree method.First let’s consider the individual tree rules. We may define the consistency and completeness of truth tree rules as follows:
A truth tree rule is consistent iff whenever the premise has the truth value T, all the statements derived from it by the rule on at least one branch also have the value T.
If this were not the case, it would be possible to derive a false statement from a true one by the rule, contrary to the definition of formal validity. Conversely,
A truth tree rule is complete iff the premise also has the truth value T whenever all the statements derived from it by the rule on at least one branch have the value T.
To establish the completeness of the truth tree method itself, we need first to assure ourselves that a complete truth tree always terminates. We note that according to the rules of formation for Statement Logic, any compound statement is formed by the five truth-functional operators (four binary and one unary) operating on simple statements.
The decomposition rules—one for each of the four binary operators and one for each of the negations of them—will therefore be sufficient to reduce any finite compound statement to literals, statements of the form p or
where p is a simple statement. Since each decomposition rule results in at most a doubling of the number of branches, there will therefore be a finite number of paths in the complete tree. Now we note that if the two premises and the negation of the conclusion—all the statements “above ground” in the tree—are consistent with one another, it will be possible to assign them all the truth value T. But now an application of any of the rules to any statement above it in the tree will result in all the statements derived from it on at least one branch also having the value T, by the definition of consistency of the rules. This shows that any tree beginning with all the above-ground statements T will have at least one open path. Because the number of such applications is finite, we are therefore guaranteed that the tree will be completed, and that in such a complete tree there will be at least one complete open path: one where all the literals in it are T. Contrarily, if the tree is closed, the premises together with the negation of the conclusion cannot be consistent. That is, for any given argument form or sequent of Statement Logic, if the truth tree associated with it is closed, the argument form or sequent is valid. The truth tree method is consistent.
A reversal of this kind of reasoning can now be used to establish the completeness of the truth tree method. If below the above-ground statements there is a complete open path consisting of only true literals, then, because this can only be reached by applying decomposition rules each of which is itself complete, the above-ground statements must all be true on that evaluation, and are therefore consistent.
Thus if there is at least one complete open path in a complete tree corresponding to an argument or sequent, the premises together with the negation of the conclusion will be consistent. Conversely, the truth tree associated with any valid argument or sequent of Statement Logic will be closed. The truth tree method is complete.SUMMARY
• If a compound statement is a contradiction, then all paths downwards from it in the corresponding truth tree are closed. If a compound statement is a tautology, then all paths downwards from its negation in the corresponding truth tree are closed.
• A truth tree rule is consistent iff whenever the premise has the truth value T, all the statements derived from it by the rule on at least one branch also have the value T.
• A truth tree rule is complete iff the premise also has the truth value T whenever all the statements derived from it by the rule on at least one branch have the value T.
• Since every argument form or sequent of Statement Logic that is associated with a closed truth tree is valid, the truth tree method is consistent, and since the truth tree associated with any valid argument form or sequent of Statement Logic is closed, the truth tree method is complete.
EXERCISES 14.2
23. Determine using a truth tree which of the following abstract statements is a contradiction. For each that is not a contradiction, is it a tautology, or a contingent statement?
24. One of the following three statement forms is tautologous, and one contradictory. Use a truth tree method to determine which is which.
25. Determine using a truth tree whether
is logically equivalent to
26. Determine using a truth tree whether
, is logically equivalent to
27. (CHALLENGE) Give a detailed argument for the soundness and completeness of each of the following rules, making explicit the truth tables for the appropriate operators:
28. (CHALLENGE) If the truth tree for each rule is complete, why is this not enough to prove the completeness of the truth tree method as a whole? What more is needed, and why?