TREE GRAMMARS

In logic, what corresponds to grammar is the set of formation rules for the symbols, that is, the rules which define a formula. Although I shall eventually argue that some of the structures exemplified in the formulas of modern logic are more complex than trees, many of them certainly are trees and probably the majority of logicians has assumed that all of them are. So it is fitting to take tree grammars as typical of logic in the way that string grammars have been taken as typical of linguistics.

A tree is a finite set of one or more nodes which fulfil two conditions: first, that just one node is called the root and, second, that the remaining nodes are partitioned into disjoint trees, called sub-trees of the whole. Each root is connected to the roots of each of its sub-trees by a line and, intuitively, the resulting diagrams look like upside-down trees, with the root at the top and the branches spreading out downwards. The bottom-most nodes are called the leaves of the tree and the set of leaves constitutes the tree frontier.

As with a string grammar, a distinction is drawn between non-terminals (category symbols) and terminals but, in addition, each of these symbols is assigned a degree (sometimes also called a ‘rank’), which is the number of sub-trees which issue from it.