Tree Tutorial 1 Propositional Logic Truth Trees: Introduction
5/25/12
Graph theory and trees
'Trees' are a type of structure within the mathematical theory of graphs.
Graphs consist of two things: nodes (other words for these, 'vertices', 'points') and links (other words for these, 'edges', 'lines', 'ties'). In applications, nodes typically model individual people, countries, businesses, web pages, genes, amino acids, etc. Links typically model friendships, web hyperlinks, telephone lines, communications, etc. For us, nodes are going to represent formulas and the links will show the decomposition, or transformation, of a formula into other formulas.
You can think of a node and being a dot or a point, and a link as being a line or an edge which runs from a node to a node. So here is a graph
The size of a graph is the number of nodes in it. This one is of size 7.
The degree of a node is the number of links that connect to it. So, for example, the node d has degree 2 and g degree 3.
How the links are drawn is irrelevant (you can draw them as curves or straight lines or locate them differently, and the links can cross each other without that meaning anything)-- all that matters is which nodes they connect. These two graphs are actually the same graph.
A walk is an alternating sequence of nodes and links, which starts and ends with a node. So, in the first example graph, a->d->e is a walk. A path is a walk with no repeated nodes. The length of a walk is the number of links included in it. Two nodes are adjacent if there is a link between them.
A graph has a cycle, or is cyclic, if there is a walk of non-zero length that starts and ends on the same node (otherwise the graph is said to be acyclic).
A graph is connected if there is a path between every two nodes in it. The first example graph is not connected (because the node b cannot be reached), and the second example graph is connected.
There are a couple of different ways of explaining or defining trees (and which is preferable depends a little on what is going to be done with the resulting trees).
A tree is a connected graph in which between every two nodes there is only one path (ie there are no 'cycles'). For example,
is a tree (you can walk from node to node (so it is connected) but you cannot walk around in a circle (so there are no cycles)).
With a tree, there are nodes which do not have other nodes below them. These are leaves. So, in the above tree, d is the root, and c, f and b are leaves. With any leaf, there is exactly one path from the root to it, such a path is a branch.
d-a-g-f is a branch in the above tree.
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.
For example, 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 is started with the conjunction as the root, and it is extended by adding a branch containing each of the immediate subformulas. Thus
before
after
[These images come from the running software, the tick is just to show which formula has been extended.]
The tree extension rules are also used to grow a tree even when the formula that is being used to make the extension is not the root. For example, here is a perfectly good tree built using the conjunction rule three times in a row (first on the root, then on the second formula, and so on).
Try building some 'and' trees (click on the formula to select, press the 'Extend' button).
You'll notice that when a Tree starts, the formulas it starts from are justified by 'SM'. This stands for 'Set Member' just to show that the formulas are members of the starting set of formulas.
a) F,F&G
b) F&G,G&H&I
c) F&~F
A tree 'pictures' truth conditions. It shows what has to happen for a formula to be true. The idea is: if all the atomic formulas in a branch are true, or are assigned true, and all the negations of atomic formulas in a branch are true, ie their atomic components are assigned false, then all the formulas in the branch will be true. So, for example, (F&G) is true if F is true and G is true, and (H&~I) is true if H is true and I is false. However, this is subject to a condition. Consider the formula (F&~F), it is not satisfiable, no assignment of truth values to its atomic components can make it true. If you do a tree for a formula like this (Tree 3 above), you will end up with a branch that has both F and ~F in it; this means that you will be trying to assign F both true and false (which is impossible).
Any branch that contains a formula and the negation of that formula is said to be closed. (And any branch that is not closed is open.)
The running software allows you to close (suitable) branches. To do this you have to select two formulas, one of the formulas has to be the negation of the other, then you click the 'Close' button. To select (or unselect) a formula, click on it if you have a mouse, or touch it with your finger, if you are using a touchscreen device
Exercises to accompany Tutorial 1
Exercise 1 (of 1) (very brief):
For Tree 3 above, extend the tree, then select both F and ~F (touch, or click on, the first, touch or click the second) then push the 'Close' button. This is just to introduce you to the notation for closed branches.
If you decide to use the web application you can launch it from here Deriver [default] — username 'logic' password 'logic'. Then either copy and paste
F,F&G
F&G,G&H&I
F&~F
into the Journal or use the Deriver File Menu to Open Web Page with this address
https://softoption.us/test/treesStandAlone/CombinedTutorialsDefault.html
Then select the desired formula(s) and Start Tree off the Actions Menu.
Preferences
[If you find you need to set the Preferences for the web application (because you, or someone else, has been doing something totally different with Deriver on the computer in use),
- set the parser to default
The title bar of the Deriver window will show you what system you are running e.g. 'DeriverDefault', 'DeriverGentzen', etc.]