Decision Tree Viewer

Guido Tack

Visualization of boolean (prime) decision trees

What is it?

A decision tree is a representation of a boolean formula. To be precise, DTV displays prime trees, a reduced form of decision trees.

Prerequisites

DTV depends on the package
mogul:/tack/TkTreeWidget
Please install it before installing DTV.

Installation

The package can be installed via ozmake. If you downloaded the package from mogul, type
ozmake --install -p [FILENAME]
Alternatively, you can install it directly from the internet:
ozmake --install -p mogul:/tack/DecisionTree

Entering a formula

Start DTV by typing dtv at the command line. The main window should open.

At the bottom of the window, you find a text area where you can enter the boolean formula. The simple syntax for formulae is as follows:

sf ::= false
     | true
     | X
     | -sf
     | sf1 ^ sf2
     | sf1 v sf2
     | sf1 => sf2
     | sf1 <=> sf2
     | (sf)
Where X is a variable (a string beginning with an uppercase letter).

There is an extended syntax, allowing for abbreviations (or macros) of formulae:

flist ::= goal := sf
        | y := sf;flist
Where y is a macro name (a string beginning with a lowercase letter). In an extended formula, a macro name can appear instead of a variable (in case it has been defined before).

Variable order

In decision trees, the order of variables matters. With DTV, you can change the order as you like:
After you have entered a formula, the order of the variables will be the order in which they appear in the formula. The variables are displayed on the right, ordered from top to bottom. Now you can select a variable and move it up or down using the "Up" and "Down" buttons. "Reverse" just brings the variables in reverse order, "Sort" sorts them lexicographically. Anytime you change the order, the tree will adjust accordingly.

Normal forms

Prime trees make it easy to compute a disjunctive and conjunctive normal form of a formula. The normal forms corresponding to the current variable order are displayed below the entry field.

Postscript export

By selecting the menu entry "DTV -> Save tree", you can save the picture of the current tree in encapsulated postscript format.

Example

This is an example for a formula in extended syntax, taken from a course on logics at Saarland University:

"What is the secret of your long life?" a hundred-year-old is asked. He replies: "I strictly obey three rules: Anytime I don't drink beer, I eat fish. If I have fish as well as beer, I won't eat ice cream. Should I eat ice cream or not drink beer, I won't have fish."

This problem could be modelled as follows:
r1   := -Beer => Fish;
r2   := Fish ^ Beer => -IceCream;
r3   := IceCream v -Beer => -Fish;
goal := r1 ^ r2 ^ r3

If you order the variables as Beer < IceCream < Fish, you can see that the old man always drinks beer (this doesn't seem to be a surprise ;-), but eats only either fish or ice cream.

This is what the output of dtv for this example may look like:

Guido Tack
Last modified: Wed May 1 20:33:10 CEST 2002