Namespaces
Variants
Actions

Difference between revisions of "Derivation tree"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
 
Line 1: Line 1:
A notation for derivations (cf. [[Derivation, logical|Derivation, logical]]) in a [[Calculus|calculus]], in which the elements of the derivations from which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031240/d0312401.png" /> is obtained by one application of a [[Derivation rule|derivation rule]] are written down above each element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031240/d0312402.png" />. For instance, the derivation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031240/d0312403.png" /> in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031240/d0312404.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031240/d0312405.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031240/d0312406.png" /> are axioms, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031240/d0312407.png" /> is obtained by one application of some rule from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031240/d0312408.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031240/d0312409.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031240/d03124010.png" /> is obtained from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031240/d03124011.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031240/d03124012.png" />, while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031240/d03124013.png" /> is obtained from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031240/d03124014.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031240/d03124015.png" />, may be written down as follows:
+
{{TEX|done}}
 +
A notation for derivations (cf. [[Derivation, logical|Derivation, logical]]) in a [[Calculus|calculus]], in which the elements of the derivations from which $P$ is obtained by one application of a [[Derivation rule|derivation rule]] are written down above each element $P$. For instance, the derivation $P_1,\ldots,P_6$ in which $P_1$, $P_2$ and $P_4$ are axioms, $P_3$ is obtained by one application of some rule from $P_1$ and $P_2$, and $P_5$ is obtained from $P_4$ and $P_3$, while $P_6$ is obtained from $P_3$ and $P_5$, may be written down as follows:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031240/d03124016.png" /></td> </tr></table>
+
$$\dfrac{P_1,P_2}{P_3}\quad\dfrac{\dfrac{P_4,\dfrac{P_1,P_2}{P_3}}{P_5}}{P_6}$$
  
 
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.
 
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.

Latest revision as of 19:15, 16 April 2014

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

$$\dfrac{P_1,P_2}{P_3}\quad\dfrac{\dfrac{P_4,\dfrac{P_1,P_2}{P_3}}{P_5}}{P_6}$$

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: http://encyclopediaofmath.org/index.php?title=Derivation_tree&oldid=31802
This article was adapted from an original article by S.Yu. Maslov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article