5/15/09 10 Software
Prerequisities
You need to know some sentential logic to be able to understand this. In particular, you need to know about the symbols used in sentential logic, truth tables, satisfiability, consistency, and semantic invalidity (by counter example). You do not need to know sentential rules of inference and derivations. [The tutorials on sentential logic elsewhere on this site give the required background. Alternatively
M.Bergmann, J.Moor, J.Nelson, [2008] The Logic Book Chapter 4
would put you about where you need to be.]
Skills to be acquired in this tutorial:
To become familiar with the notions of tree, branch, open branch, closed branch.
Reading
M.Bergmann, J.Moor, J.Nelson, [2008] The Logic Book Chapter 4
[The use of trees (or 'tableaux') in logic was pioneered by Beth, Hintikka, and Smullyan, and their use was brought into a teaching context by such books as the standard Jeffrey text. See
E.W. Beth, [1959] The Foundations of Mathematics
G.Gentzen, [1934-5] 'Untersuchungen uber das logische Schliessen', Mathematische Zeitschrift, vol 39, 1934-5, pp.176-210, 405-31
J. Hintikka [1955] ' Two papers on Symbolic Logic', Acta Philosophica Fennica, vol 8 1955
R.C.Jeffrey, [1967] Formal Logic: Its Scope and Limits
R.M. Smullyan, [1968] First Order Logic
]
Tutorial:
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 are a few graphs
Graph 1 is a graph consisting of a single node only. Graphs 2 and 5 are graphs with five nodes. Graph 3 has five nodes and two links; graph 6 also has five nodes and two links, but it is a different graph to 3 because different nodes are linked.
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.
A walk is an alternating sequence of nodes and links which starts and ends with a node. So, in graph 2, a->d->e is a walk. A path is a walk with no repeated nodes.
A graph is connected if there is a path between every two nodes in it. Graphs 2, 4, and 5 are connected. Graphs 1, 3, and 6 are not.
A tree is a connected graph in which between every two nodes there is only one path (ie there are no 'cycles'). Graphs 4 and 5 are trees, graph 2 (which has a cycle) and the others (which are not connected) are not.
With the kind of trees of interest to us, it is usual to pick one of a tree's nodes as being the 'root'. Then it is common to draw them with the root at the top, and the other nodes appearing below. So were the node 'd' to be chosen as the root of Graphs 4 and 5, those two graphs might be drawn as follows.
Graph 5 would be alright as it is.
Graph 4 might be re-drawn
Common examples of trees are organizational ('org') charts, genealogical trees, any the display of any hierarchy (such as genus-species in biology, subjects in librarianship).
With a tree, there are nodes which do not have other nodes below them. These are leaves. In graph 4, a,c,b, and e are all leaves; in graph 5 c, a, and b are all leaves.
With any leaf, there is exactly one path from the root to it, such a path is a branch. With graph 5 there are three branches
[The reason trees are often drawn 'upside down', with the root at the top, and the 'branches' and 'leaves' coming downward is that they are often constructed from the root and enough room has to be left on the sheet of paper to draw them.]
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 applet that we will look at shortly, 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 one of the products of the first extension, and so on).
Try building some 'and' trees (click on the formula to select, choose 'extend' from the menu).
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 applet allows you to close (suitable) branches. To do this you have to select two formulas (on WIndows and Mac computers this is done by clicking on the first then command-clicking on the second), one of the formulas has to be the negation of the other, then you select 'Close' from the menu.
The concepts of open and closed can be extended to trees. A closed tree is a tree in which every branch is closed. An open tree is a tree which has at least one open branch.
Exercises to accompany Tutorial 1
Exercise 1 (of 1) (very brief):
For Tree 3 above, extend the tree, then select both F and ~F (click on the first, command click on the second) then select 'Close' from the menu. This is just to introduce you to the notation for closed branches.