Tree Tutorial 2: More Propositional Tree Rules

Topic
Logical System

Tree Tutorial 2 More Rules

2013

Skills to be acquired in this tutorial:

To become familiar with the rules for propositional truth trees.

Reading

Colin Howson, [1997] Logic with trees Chapter 2

Tutorial:

Truth Tree Rules

Trees are going to be used to 'picture' the truth conditions or requirements for a formula (then, as the technique is developed, for several formulas at once).

Any easy way to remember the rules is to regard them as having been built from the truth tables.

The truth table for 'and' is

Conjunction

F G (F∧G)
True True True
True False False
False True False
False False False

For a conjunction to be true, each of its immediate subformulas have to be true. A tree can be extended from a conjunction, and it is extended by adding each of the immediate subformulas to all the branches that the conjunct belongs to. Thus

The truth table for 'or' is

Disjunction

F G (F∨G)
True True True
True False True
False True True
False False False

For a disjunction to be true, either of its immediate subformulas have to be true. A tree can be extended from a disjunction, and it is extended by adding two sub-branches, one containing one of the immediate subformulas and the other containing the other immediate subformula (to all the branches that the disjunct belongs to). Thus

The truth table for 'conditional' is

Conditional

F G (F→G)
True True True
True False False
False True True
False False True

For a conditional to be true, either of its antecedent subformula has to be false or its consequent subformula has to be true. A tree can be extended from a conditional, and it is extended by adding two sub-branches, one containing the negation of the antecedent and the other containing the consequent (to all the branches that the conditional belongs to). Thus

The truth table for 'biconditional' is

Biconditional

F G (F↔G)
True True True
True False False
False True False
False False True

For a biconditional to be true, either both of its subformula have to be true or both of its subformulas have to be false. A tree can be extended from a biconditional, and it is extended by adding two sub-branches, one containing both the subformulas and the other containing the negations of both the subformulas (to all the branches that the biconditional belongs to). Thus

 

You might think we are finished, but we are not!

We need to be able to draw trees for all sentential logic formulas, we need to be able to picture the truth conditions for any formula. To do that we need tree extension rules for the cases when the connective occur in combination with negation.

Here they are

Double Negation

F ¬¬F
True True
False False

 

Negated Conjunction

F G ¬(F∧G)
True True False
True False True
False True True
False False True

 

Negated Disjunction

F G ¬(F∨G)
True True False
True False False
False True False
False False True

 

Negated Conditional

F G ¬(F→G)
True True False
True False True
False True False
False False False

 

Negated Biconditional

F G ¬(F↔G)
True True False
True False True
False True True
False False False

 

Example

Here is an example of a larger tree (in all its glory)

Starting from a collection of formulas, rather than a single formula

Trees can be grown from a collection of formulas. Say we wished to draw a tree for F, (F→G), and ¬G, all of them at once together. One approach might be to think of them as being 'anded' together, and do a tree for the single composite formula F∧(F→G)∧¬G

But equally, and more simply, we could just write down all the members of the collection as the (extended) root and go on from there (instead of putting the 'ands' in then taking them out to get that point). Thus

[The last two trees are shown with their closed branches marked as closed by a cross.]

Starting from a collection or set of formulas will prove to be useful.

 


Exercises to accompany Tree Tutorial 2

Try building some trees (click on the formula to select, choose 'extend' from the menu). Close branches if you can (click on a formula to select, click, or touch, on the negation of that formula (in the same branch), choose 'close' from menu).

Try building different trees from the same starting point (the order you apply the rules matters in terms of the tree generated) ie click on Tree 1, build it, click on Tree 1 again and build it again.

Notice

a) you cannot extend the same formula twice (once it is 'ticked' it is dead and unusable).
b) no rule applies to either an atomic formula or the negation of an atomic formula
c) you get a smaller tree if you delay using splitting rules (ie use 'straight ahead' rules first).
d) you get a smaller tree if you close branches as soon as you can.