|
Chapter 5: Truth-Trees |
|
|
|
|
|
5.1: Introduction |
|
|
If an argument or a formula has more than three propositional letters its truth-table becomes unwieldy. We need a short cut. We'll see two methods based on truth tables.
|
|
|
5.2: Searching for a Counter-Example |
|
|
Both methods are based on the idea of searching for counter-examples to claims of validity.
As you will recall, if there is a row of the truth table for a formula that makes it false then the formula is not a tautology and that row is a counter-example. If there is no counterexample then the formula is a tautology. Similarly if there is a row in the truth table of an argument in which all the premisses are true and the conclusion is false then the argument is not valid and that row is a counter-example. If there is no counterexample then the argument is valid.
|
|
|
5.3: Method of Assigning Values |
|
|
Given an argument assume that there is a counterexample, then try to work out the values that have to be assigned to the fundamental parts of the formulae.
Consider the argument
p É q q p
A counterexample (row in the truth table) to this argument has 0 for the conclusion and 1 for the premisses. So we know this much.
p q ( p É q ) q p 1 1 0
In fact we also know.
p q ( p É q ) q p 0 1 0 1 1 1 0
which is a counterexample with p=0, q=1.
There are not always unique choices for assigning values. In that case we have to make alternative rows. Consider the argument
p É q p º q
A counterexample (row in the truth table) to this argument has 0 for the conclusion and 1 for the premiss. So we know this much.
p q ( p É q ) p º q 1 0
There are two possibilities for p and q. Try one row with p=1 and another with p=0
p q ( p É q ) p º q 1 0 1 1 0 1 0 0 0 1 0 1 1 0 0 1
Obviously the first row doesn't work because there is an impossible assignment in the premiss. The second row does work though, so it's a counter-example.
|
|
|
5.4: MAV for Formulae |
|
|
The same technique can be used for finding counter-examples to claims of tautology for formulae. Consider the formula
((p É q) º (~ p v q))
A counterexample (row in the truth table) to this argument has 0 under the main operator. So we know this much.
p q ((p É q) º (~ p v q)) 0
There are two possibilities for the subformulae (p É q) and ~(p v q). Try one row with the former valued as 1 and another with it valued as 0
p q ((p É q) º (~ p v q)) 1 0 0 0 0 1
Now on the first row there is a unique assignment to satisfy the value for 'v', and on the second row there is a unique assignment to satisfy the value for 'É', so:
p q ((p É q) º (~ p v q)) 1 0 1 1 0 0 0 1 0 0 1 0 1 0 0 0 0 1 1 0
But the assignment of the first row is impossible for 'É', and on the second row it is impossible for 'v'. These are all the possibilities, so there is no counterexample and the formula is a tautology.
|
|
|
5.5: Truth-Tree Principles |
|
|
The idea behind truth-trees is that one decomposes a formula or collections of formulae into branches of subformulae which may all be true at the same time as the initial formulae. When the branch can include all the propositional letters of the original formulae then that indicates an assignment of values to satisfy those formulae. If no such branch is possible then no such assignment is possible.
Here are the rules of decomposition.
1. ~ ~ p X p
because ~~p is true just when p is true. The X, or a tick, marks the decomposed formula so it doesn't get done twice.
2. (p & q) X p q
because p & q is true just when both p and q are true.
3. (p v q) X / \ p q
This is a branching decomposition. It occurs p v q is true if p is true (no matter how q is valued) or if q is true (no matter how p is valued). You can now work out for yourself what all the other decomposition rules are going to be, but here are some others anyway.
4. ~(p & q) X / \ ~p ~q
5. ~(p v q) X ~p ~q
6. (p É q) X / \ ~p q
7. ~(p É q) X p ~q
8. (p º q) X / \ p ~p q ~q
9. ~(p º q) X / \ p ~p ~q q
|
|
|
5.6: Arguments and Counter-Examples |
|
|
To find a counterexample to the validity of an argument using the tree method list the premisses and the negation of the conclusion and decompose that set of formulae. Whenever a path/branch contains both a formula and its negation put an X under it and never use that path again. It is closed. All paths that aren't closed are open. If at the end of the decomposition there is a path that is not closed then by assigning true to the formulae on that path you find a possible evaluation that makes the premisses true and the conclusion false.
Consider the example:
p É q q p
Begin by writing the new set of formulae
p É q q ~p
Then decompose the first line to get
p É q X q ~p / \ ~p q
We see that both branches are open, so there are two counterexamples found by running up the two branches: the left branch gives p=0, q=1, and the right branch gives q=1, p=0, which is just the same as the left branch - so there's only really one counterexample.
Consider the example:
p É q p q
Begin by writing the new set of formulae
p É q p ~q
Then decompose the first line to get
p É q X p ~q / \ ~p q X X
We see that both branches close, so there is no counterexample.
It isn't necessary for all paths to remain open for a tree to provide a counterexample. One is enough.
|
|
|
5.7: Tautologies and Counter-Examples |
|
|
To find a counterexample to the tautologousness of a test formula using the tree method list the negation of the test formula (NTB) and decompose it. If at the end of the decomposition there is a path that is not closed then by assigning true to the formulae on that path you find a possible evaluation that makes the test formula false.
Consider the example:
~(p & ~p)
Begin by writing the NTB
~~(p & ~p)
Then decompose to get
~~(p & ~p) X (p & ~p) X p ~p X
We see that all branches close. So there's no assignment that will make the NTF true, so the test formula is a tautology.
|
|
|
5.8: Complex Truth-Trees |
|
|
Note that formulae can be quite a way from the bottom of the tree when they are decomposed. The results of their decomposition goes onto the end of every open path below the formula.
Follow the tree construction for the test formula ((p É q) v s) É ((q v p) & s)
1 ~(((p É q) v s) É ((q v p) & s)) X 2 ((p É q) v s) X 3 ~((q v p) & s) X / \ 4 ~(q v p) ~s / \ / \ 5 (p É q) s (p É q) s (from 2)
and ~(q v p) on line 4 will decompose only under the two left most branches of line 5.
For reasons of practicality, put off branching decompositions for as long as possible. They tend to make the tree unwieldy.
There are various ways of keeping track of the process of tree construction. Numbering the lines allows you to label later formulae to see where they came from. You can also list the lines that show how a branch came to be closed beside or under the X that marks that closure.
|
|
|
5.9: Contradictions and Sets |
|
|
There's an obvious extension of the technique that allows us to test for contradictions - just decompose under the formula and if there's no open path then there's no way to make the formula true and so the formula is a contradiction.
Similarly for the consistency of a set of formulae. List that set. Decompose. If there's no open path then there's no way to make all the formulae in the set true together and so the set of formulae is inconsistent.
|
|