Derivation tree

From Encyclopedia of Mathematics
Revision as of 17:17, 7 February 2011 by (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

A notation for derivations (cf. Derivation, logical) in a calculus, in which the elements of the derivations from which is obtained by one application of a derivation rule are written down above each element . For instance, the derivation in which , and are axioms, is obtained by one application of some rule from and , and is obtained from and , while is obtained from and , may be written down as follows:

This notation, though more cumbersome than the linear notation, often proves to be a convenient tool in the investigation of derivations: It is easy to follow up the interconnections between the elements; the information comprised in the derivation tree represents a more complete description of the situation than does linear ordering (its completeness is almost as satisfactory as that of the information comprised in an analytical derivation). If required, the derivation tree is also given an analysis, i.e. each line is written with the number of the respective rule; axioms are written with their numbers.

How to Cite This Entry:
Derivation tree. Encyclopedia of Mathematics. URL:
This article was adapted from an original article by S.Yu. Maslov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article