Truth Trees in Sentence Logic

Truth trees are a purely mechanical method for testing the validity of arguments in sentence logic.  They work on a combination of principles from the method of indirect proof and truth tables.  The essence of the idea behind them is that of the distinction between validity and invalidity.  A valid argument is one in which, if the premises are true, the conclusion must be true.  An invalid argument is one such that if the premises are true, the conclusion may not be true.  Another way to put the point is that in a valid argument, the assumption of the falsehood of the conclusion is inconsistent with the truth of the premises.  In an invalid argument, the assumption of the falsehood of the conclusion is consistent with the truth of the premises.

On the basis of this distinction (between validity and invalidity), it is possible to find a method by which to determine whether an argument is valid or invalid by assuming that the conclusion is true and discovering what the quality of the premises must be on this assumption.  If all the premises can be true while the conclusion is false, the argument is invalid.  But if all the premises cannot be true while the conclusion is false, the argument is valid.

The best means by which to understand both the method and the principle behind truth trees is to do one.  Consider the following argument:

A v B

-A/ B

The first step is to add the negation of the conclusion to the set of premises.  Once this is done, you have formed the "trunk" of the truth tree.  The "branches" of the truth tree are formed by "decomposed" statements.  Below is a completed truth tree.  Following that is an explanation of each step in its construction and what the completed tree shows and why that it is the case.

A v B

~A/ B

~B

A         B

(x)        (x)

(The (x) under each "branch" of the truth tree indicates that the branch is closed.)

Explanation:  The first step is to negate the conclusion.  Then, once the conclusion has been negated, "decompose" each statement in the argument that is a compound sentence so that you may see all the atomic sentence components.  -A is already as "simple" as it can be, as is -B.  But "A v B" is a compound sentence that must be decomposed into its smallest atomic sentence components.  Every disjunction is true when at least one of the disjuncts is true.  Since it is not necessary that both disjuncts be true, the truth tree "branches" on a disjunction.  Once the branch has been produced, check the resulting branches back through the trunk to see whether there are any logical contradictions derived on the basis of the falsehood of the conclusion.  There are.  In the branch on the left, A is contradicted by the negation of A.  In the branch on the right, B is contradicted by the negation of B.  This means that the branches of the truth tree are all closed.  When all the branches of a truth tree are closed, it indicates that the argument is valid.  If at least one branch remains open, it indicates that the argument is invalid.  In other words, when all the branches are closed, it indicates that the falsehood of the conclusion is inconsistent with the truth of the premises (or, put another way, it indicates that the premises cannot all be true while the conclusion is false).  When at least one branch of the truth tree is open, it indicates that the falsehood of the conclusion is consistent with the truth of the premises (or, in other words, it indicates that the premises can all be true while the conclusion is false).

Consider the next argument:

A ® B

A × B/~B

B

A

B

-A                                 B

(x)                                open

Since at least one branch of the truth tree is open, the argument in question is invalid.

The first step in constructing the truth tree is to assume that the conclusion is false.  (Note that if the conclusion were a compound sentence, such as "A v B", the negation would be ~(A v B).  If the conclusion were a compound such as that given in the note above, it would also need to be decomposed according to the rules for decomposition that appear below.)  Once you have negated the conclusion, check for contradictions.  It sometimes happens that the truth tree runs itself into contradictions before you have decomposed all the sentences.  If that happens, and all the branches close, it is not necessary to continue to decompose any statements at all.  Simply indicate that all the branches are closed and write that the argument is valid.  The second step is to decompose the statement that is a conjunction.  It is always easier to do that, since every statement that remains to be decomposed must be decomposed on every available open branch. So, for example, if you were to decompose the disjunction (every implication turns into a disjunction), you would have to decompose the conjunction twice in this truth tree.  Decomposing the conjunction first eliminates that problem.  Check for contradictions after you have decomposed the conjunction.  Since there are none, decompose the disjunction.  Once that is done (and you have now decomposed all the statements in the argument), check for contradictions.  You note that there is only one branch that shows a contradiction.  The other one does not.  Therefore, the argument in question has been shown to be invalid.

Rules for Decomposition of Statements in SL Truth Trees

 p ® q ~p     q p v q p    q p . q p q p « q p     ~p q     ~q ~(p ® q) p ~q ~(p v q) ~p ~q ~(p × q) ~p      ~q p    ~p ~q     q

The rules for decomposition are very simple.  If you were to check each one on a truth table, you would find that all of them are logically equivalent.  That is, consider the first rule:

(p ® q) « (~p v q).  All that the decomposition shows is this rule without the logical symbols being all present.  The truth tree shows schematically what the rule "material implication" shows with symbols.  The same is the case for all the other rules.

One more truth tree should suffice to explain how they are done:

[A v (B × C)]

C ® A

A × D  /  B v D

~(B v D)

~B

~D

A

D

(x)

The truth tree closes even before all the statements are decomposed since D is contradicted by -D.  The argument is shown to be valid.