• Source: Term logic

In logic and formal semantics, term logic, also known as traditional logic, syllogistic logic or Aristotelian logic, is a loose name for an approach to formal logic that began with Aristotle and was developed further in ancient history mostly by his followers, the Peripatetics. It was revived after the third century CE by Porphyry's Isagoge.
Term logic revived in medieval times, first in Islamic logic by Alpharabius in the tenth century, and later in Christian Europe in the twelfth century with the advent of new logic, remaining dominant until the advent of predicate logic in the late nineteenth century.
However, even if eclipsed by newer logical systems, term logic still plays a significant role in the study of logic. Rather than radically breaking with term logic, modern logics typically expand it.




Aristotle's system


Aristotle's logical work is collected in the six texts that are collectively known as the Organon. Two of these texts in particular, namely the Prior Analytics and De Interpretatione, contain the heart of Aristotle's treatment of judgements and formal inference, and it is principally this part of Aristotle's works that is about term logic. Modern work on Aristotle's logic builds on the tradition started in 1951 with the establishment by Jan Lukasiewicz of a revolutionary paradigm. Lukasiewicz's approach was reinvigorated in the early 1970s by John Corcoran and Timothy Smiley – which informs modern translations of Prior Analytics by Robin Smith in 1989 and Gisela Striker in 2009.
The Prior Analytics represents the first formal study of logic, where logic is understood as the study of arguments. An argument is a series of true or false statements which lead to a true or false conclusion. In the Prior Analytics, Aristotle identifies valid and invalid forms of arguments called syllogisms. A syllogism is an argument that consists of at least three sentences: at least two premises and a conclusion. Although Aristotle does not call them "categorical sentences", tradition does; he deals with them briefly in the Analytics and more extensively in On Interpretation. Each proposition (statement that is a thought of the kind expressible by a declarative sentence) of a syllogism is a categorical sentence which has a subject and a predicate connected by a verb. The usual way of connecting the subject and predicate of a categorical sentence as Aristotle does in On Interpretation is by using a linking verb e.g. P is S. However, in the Prior Analytics Aristotle rejects the usual form in favour of three of his inventions:

P belongs to S
P is predicated of S
P is said of S
Aristotle does not explain why he introduces these innovative expressions but scholars conjecture that the reason may have been that it facilitates the use of letters instead of terms avoiding the ambiguity that results in Greek when letters are used with the linking verb. In his formulation of syllogistic propositions, instead of the copula ("All/some... are/are not..."), Aristotle uses the expression, "... belongs to/does not belong to all/some..." or "... is said/is not said of all/some..." There are four different types of categorical sentences: universal affirmative (A), universal negative (E), particular affirmative (I) and particular negative (O).

A - A belongs to every B
E - A belongs to no B
I - A belongs to some B
O - A does not belong to some B
A method of symbolization that originated and was used in the Middle Ages greatly simplifies the study of the Prior Analytics.
Following this tradition then, let:

a = belongs to every
e = belongs to no
i = belongs to some
o = does not belong to some
Categorical sentences may then be abbreviated as follows:

AaB = A belongs to every B (Every B is A)
AeB = A belongs to no B (No B is A)
AiB = A belongs to some B (Some B is A)
AoB = A does not belong to some B (Some B is not A)
From the viewpoint of modern logic, only a few types of sentences can be represented in this way.




Basics


The fundamental assumption behind the theory is that the formal model of propositions are composed of two logical symbols called terms – hence the name "two-term theory" or "term logic" – and that the reasoning process is in turn built from propositions:

The term is a part of speech representing something, but which is not true or false in its own right, such as "man" or "mortal". As originally conceived, all terms would be drawn from one of ten categories enumerated by Aristotle in his Organon, classifying all objects and qualities within the domain of logical discourse.
The formal model of proposition consists of two terms, one of which, the "predicate", is "affirmed" or "denied" of the other, the "subject", and which is capable of truth or falsity.
The syllogism is an inference in which one proposition (the "conclusion") follows of necessity from two other propositions (the "premises").
A proposition may be universal or particular, and it may be affirmative or negative. Traditionally, the four kinds of propositions are:

A-type: Universal and affirmative ("All philosophers are mortal")
E-type: Universal and negative ("All philosophers are not mortal")
I-type: Particular and affirmative ("Some philosophers are mortal")
O-type: Particular and negative ("Some philosophers are not mortal")
This was called the fourfold scheme of propositions (see types of syllogism for an explanation of the letters A, I, E, and O in the traditional square). Aristotle's original square of opposition, however, does not lack existential import.




Term


A term (Greek ὅρος horos) is the basic component of the proposition. The original meaning of the horos (and also of the Latin terminus) is "extreme" or "boundary". The two terms lie on the outside of the proposition, joined by the act of affirmation or denial.
For early modern logicians like Arnauld (whose Port-Royal Logic was the best-known text of his day), it is a psychological entity like an "idea" or "concept". Mill considers it a word. To assert "all Greeks are men" is not to say that the concept of Greeks is the concept of men, or that word "Greeks" is the word "men". A proposition cannot be built from real things or ideas, but it is not just meaningless words either.




Proposition


In term logic, a "proposition" is simply a form of language: a particular kind of sentence, in which the subject and predicate are combined, so as to assert something true or false. It is not a thought, or an abstract entity. The word "propositio" is from the Latin, meaning the first premise of a syllogism. Aristotle uses the word premise (protasis) as a sentence affirming or denying one thing or another (Posterior Analytics 1. 1 24a 16), so a premise is also a form of words.
However, as in modern philosophical logic, it means that which is asserted by the sentence. Writers before Frege and Russell, such as Bradley, sometimes spoke of the "judgment" as something distinct from a sentence, but this is not quite the same. As a further confusion the word "sentence" derives from the Latin, meaning an opinion or judgment, and so is equivalent to "proposition".
The logical quality of a proposition is whether it is affirmative (the predicate is affirmed of the subject) or negative (the predicate is denied of the subject). Thus every philosopher is mortal is affirmative, since the mortality of philosophers is affirmed universally, whereas no philosopher is mortal is negative by denying such mortality in particular.
The quantity of a proposition is whether it is universal (the predicate is affirmed or denied of all subjects or of "the whole") or particular (the predicate is affirmed or denied of some subject or a "part" thereof). In case where existential import is assumed, quantification implies the existence of at least one subject, unless disclaimed.




Singular terms


For Aristotle, the distinction between singular and universal is a fundamental metaphysical one, and not merely grammatical. A singular term for Aristotle is primary substance, which can only be predicated of itself: (this) "Callias" or (this) "Socrates" are not predicable of any other thing, thus one does not say every Socrates one says every human (De Int. 7; Meta. D9, 1018a4). It may feature as a grammatical predicate, as in the sentence "the person coming this way is Callias". But it is still a logical subject.
He contrasts universal (katholou) secondary substance, genera, with primary substance, particular (kath' hekaston) specimens. The formal nature of universals, in so far as they can be generalized "always, or for the most part", is the subject matter of both scientific study and formal logic.
The essential feature of the syllogism is that, of the four terms in the two premises, one must occur twice. Thus

All Greeks are men
All men are mortal.
The subject of one premise, must be the predicate of the other, and so it is necessary to eliminate from the logic any terms which cannot function both as subject and predicate, namely singular terms.
However, in a popular 17th-century version of the syllogism, Port-Royal Logic, singular terms were treated as universals:

All men are mortals
All Socrates are men
All Socrates are mortals
This is clearly awkward, a weakness exploited by Frege in his devastating attack on the system.
The famous syllogism "Socrates is a man ...", is frequently quoted as though from Aristotle, but in fact, it is nowhere in the Organon. Sextus Empiricus in his Hyp. Pyrrh (Outlines of Pyrronism) ii. 164 first mentions the related syllogism "Socrates is a human being, Every human being is an animal, Therefore, Socrates is an animal."




= The three figures

=
Depending on the position of the middle term, Aristotle divides the syllogism into three kinds: syllogism in the first, second, and third figure. If the Middle Term is subject of one premise and predicate of the other, the premises are in the First Figure. If the Middle Term is predicate of both premises, the premises are in the Second Figure. If the Middle Term is subject of both premises, the premises are in the Third Figure.
Symbolically, the Three Figures may be represented as follows:




= The fourth figure

=
In Aristotelian syllogistic (Prior Analytics, Bk I Caps 4-7), syllogisms are divided into three figures according to the position of the middle term in the two premises. The fourth figure, in which the middle term is the predicate in the major premise and the subject in the minor, was added by Aristotle's pupil Theophrastus and does not occur in Aristotle's work, although there is evidence that Aristotle knew of fourth-figure syllogisms.




Syllogism in the first figure


In the Prior Analytics translated by A. J. Jenkins as it appears in volume 8 of the Great Books of the Western World, Aristotle says of the First Figure: "... If A is predicated of all B, and B of all C, A must be predicated of all C." In the Prior Analytics translated by Robin Smith, Aristotle says of the first figure: "... For if A is predicated of every B and B of every C, it is necessary for A to be predicated of every C."
Taking a = is predicated of all = is predicated of every, and using the symbolical method used in the Middle Ages, then the first figure is simplified to:

If AaB

and BaC

then AaC.
Or what amounts to the same thing:

AaB, BaC; therefore AaC
When the four syllogistic propositions, a, e, i, o are placed in the first figure, Aristotle comes up with the following valid forms of deduction for the first figure:

AaB, BaC; therefore, AaC
AeB, BaC; therefore, AeC
AaB, BiC; therefore, AiC
AeB, BiC; therefore, AoC
In the Middle Ages, for mnemonic reasons they were called "Barbara", "Celarent", "Darii" and "Ferio" respectively.
The difference between the first figure and the other two figures is that the syllogism of the first figure is complete while that of the second and third is not. This is important in Aristotle's theory of the syllogism for the first figure is axiomatic while the second and third require proof. The proof of the second and third figure always leads back to the first figure.




Syllogism in the second figure


This is what Robin Smith says in English that Aristotle said in Ancient Greek: "... If M belongs to every N but to no X, then neither will N belong to any X. For if M belongs to no X, neither does X belong to any M; but M belonged to every N; therefore, X will belong to no N (for the first figure has again come about)."
The above statement can be simplified by using the symbolical method used in the Middle Ages:

If MaN

but MeX

then NeX.

For if MeX

then XeM

but MaN

therefore XeN.
When the four syllogistic propositions, a, e, i, o are placed in the second figure, Aristotle comes up with the following valid forms of deduction for the second figure:

MaN, MeX; therefore NeX
MeN, MaX; therefore NeX
MeN, MiX; therefore NoX
MaN, MoX; therefore NoX
In the Middle Ages, for mnemonic reasons they were called respectively "Camestres", "Cesare", "Festino" and "Baroco".




Syllogism in the third figure


Aristotle says in the Prior Analytics, "... If one term belongs to all and another to none of the same thing, or if they both belong to all or none of it, I call such figure the third." Referring to universal terms, "... then when both P and R belongs to every S, it results of necessity that P will belong to some R."
Simplifying:

If PaS

and RaS

then PiR.
When the four syllogistic propositions, a, e, i, o are placed in the third figure, Aristotle develops six more valid forms of deduction:

PaS, RaS; therefore PiR
PeS, RaS; therefore PoR
PiS, RaS; therefore PiR
PaS, RiS; therefore PiR
PoS, RaS; therefore PoR
PeS, RiS; therefore PoR
In the Middle Ages, for mnemonic reasons, these six forms were called respectively: "Darapti", "Felapton", "Disamis", "Datisi", "Bocardo" and "Ferison".




Table of syllogisms






Decline of term logic


Term logic began to decline in Europe during the Renaissance, when logicians like Rodolphus Agricola Phrisius (1444–1485) and Ramus (1515–1572) began to promote place logics. The logical tradition called Port-Royal Logic, or sometimes "traditional logic", saw propositions as combinations of ideas rather than of terms, but otherwise followed many of the conventions of term logic. It remained influential, especially in England, until the 19th century. Leibniz created a distinctive logical calculus, but nearly all of his work on logic remained unpublished and unremarked until Louis Couturat went through the Leibniz Nachlass around 1900, publishing his pioneering studies in logic.
19th-century attempts to algebraize logic, such as the work of Boole (1815–1864) and Venn (1834–1923), typically yielded systems highly influenced by the term-logic tradition. The first predicate logic was that of Frege's landmark Begriffsschrift (1879), little read before 1950, in part because of its eccentric notation. Modern predicate logic as we know it began in the 1880s with the writings of Charles Sanders Peirce, who influenced Peano (1858–1932) and even more, Ernst Schröder (1841–1902). It reached fruition in the hands of Bertrand Russell and A. N. Whitehead, whose Principia Mathematica (1910–13) made use of a variant of Peano's predicate logic.
Term logic also survived to some extent in traditional Roman Catholic education, especially in seminaries. Medieval Catholic theology, especially the writings of Thomas Aquinas, had a powerfully Aristotelean cast, and thus term logic became a part of Catholic theological reasoning. For example, Joyce's Principles of Logic (1908; 3rd edition 1949), written for use in Catholic seminaries, made no mention of Frege or of Bertrand Russell.




Revival


Some philosophers have complained that predicate logic:

Is unnatural in a sense, in that its syntax does not follow the syntax of the sentences that figure in our everyday reasoning. It is, as Quine acknowledged, "Procrustean," employing an artificial language of function and argument, quantifier, and bound variable.
Suffers from theoretical problems, probably the most serious being empty names and identity statements.
Even academic philosophers entirely in the mainstream, such as Gareth Evans, have written as follows:

"I come to semantic investigations with a preference for homophonic theories; theories which try to take serious account of the syntactic and semantic devices which actually exist in the language ...I would prefer [such] a theory ... over a theory which is only able to deal with [sentences of the form "all A's are B's"] by "discovering" hidden logical constants ... The objection would not be that such [Fregean] truth conditions are not correct, but that, in a sense which we would all dearly love to have more exactly explained, the syntactic shape of the sentence is treated as so much misleading surface structure" (Evans 1977)




Boole’s acceptance of Aristotle



George Boole's unwavering acceptance of Aristotle's logic is emphasized by the historian of logic John Corcoran in an accessible introduction to Laws of Thought Corcoran also wrote a point-by-point comparison of Prior Analytics and Laws of Thought. According to Corcoran, Boole fully accepted and endorsed Aristotle's logic. Boole's goals were “to go under, over, and beyond” Aristotle's logic by:

providing it with mathematical foundations involving equations;
extending the class of problems it could treat– from assessing validity to solving equations; and
expanding the range of applications it could handle– e.g. from propositions having only two terms to those having arbitrarily many.
More specifically, Boole agreed with what Aristotle said; Boole's ‘disagreements’, if they might be called that, concern what Aristotle did not say. First, in the realm of foundations, Boole reduced the four propositional forms of Aristotle's logic to formulas in the form of equations– by itself a revolutionary idea. Second, in the realm of logic's problems, Boole's addition of equation solving to logic– another revolutionary idea –involved Boole's doctrine that Aristotle's rules of inference (the “perfect syllogisms”) must be supplemented by rules for equation solving. Third, in the realm of applications, Boole's system could handle multi-term propositions and arguments whereas Aristotle could handle only two-termed subject-predicate propositions and arguments. For example, Aristotle's system could not deduce “No quadrangle that is a square is a rectangle that is a rhombus” from “No square that is a quadrangle is a rhombus that is a rectangle” or from “No rhombus that is a rectangle is a square that is a quadrangle”.




See also






Notes






References


Bochenski, I. M., 1951. Ancient Formal Logic. North-Holland.
Louis Couturat, 1961 (1901). La Logique de Leibniz. Hildesheim: Georg Olms Verlagsbuchhandlung.
Gareth Evans, 1977, "Pronouns, Quantifiers and Relative Clauses," Canadian Journal of Philosophy.
Peter Geach, 1976. Reason and Argument. University of California Press.
Hammond and Scullard, 1992. The Oxford Classical Dictionary. Oxford University Press, ISBN 0-19-869117-3.
Joyce, George Hayward, 1949 (1908). Principles of Logic, 3rd ed. Longmans. A manual written for use in Catholic seminaries. Authoritative on traditional logic, with many references to medieval and ancient sources. Contains no hint of modern formal logic. The author lived 1864–1943.
Jan Łukasiewicz, 1951. Aristotle's Syllogistic, from the Standpoint of Modern Formal Logic. Oxford Univ. Press.
William Calvert Kneale and Martha Kneale, 1962. The Development of Logic. Oxford [England] Clarendon Press. Reviews Aristotelean logic and its influences up to modern times.
Pratt-Hartmann, Ian (2023-03-30). Fragments of First-Order Logic. Oxford University Press. ISBN 978-0-19-196006-2.. Chapter 2 presents a modern overview, with a bibliography.
John Stuart Mill, 1904. A System of Logic, 8th ed. London.
Parry and Hacker, 1991. Aristotelian Logic. State University of New York Press.
Arthur Prior
1962: Formal Logic, 2nd ed. Oxford Univ. Press. While primarily devoted to modern formal logic, contains much on term and medieval logic.
1976: The Doctrine of Propositions and Terms. Peter Geach and A. J. P. Kenny, eds. London: Duckworth.
Willard Quine, 1986. Philosophy of Logic 2nd ed. Harvard Univ. Press.
Rose, Lynn E., 1968. Aristotle's Syllogistic. Springfield: Clarence C. Thomas.
Sommers, Fred
1970: "The Calculus of Terms," Mind 79: 1-39. Reprinted in Englebretsen, G., ed., 1987. The new syllogistic New York: Peter Lang. ISBN 0-8204-0448-9
1982: The logic of natural language. Oxford University Press.
1990: "Predication in the Logic of Terms," Notre Dame Journal of Formal Logic 31: 106–26.
and Englebretsen, George, 2000: An invitation to formal reasoning. The logic of terms. Aldershot UK: Ashgate. ISBN 0-7546-1366-6.
Szabolcsi Lorne, 2008. Numerical Term Logic. Lewiston: Edwin Mellen Press.




External links



Term logic at PhilPapers
Smith, Robin. "Aristotle's Logic". In Zalta, Edward N. (ed.). Stanford Encyclopedia of Philosophy.
"Term logic". Internet Encyclopedia of Philosophy.
Aristotle's term logic online-This online program provides a platform for experimentation and research on Aristotelian logic.
Annotated bibliographies:
Fred Sommers.
George Englebretsen.
PlanetMath: Aristotelian Logic.
Interactive Syllogistic Machine for Term Logic A web based syllogistic machine for exploring fallacies, figures, terms, and modes of syllogisms.
• Source: Term (logic)

In mathematical logic, a term denotes a mathematical object while a formula denotes a mathematical fact. In particular, terms appear as components of a formula. This is analogous to natural language, where a noun phrase refers to an object and a whole sentence refers to a fact.
A first-order term is recursively constructed from constant symbols, variables and function symbols.
An expression formed by applying a predicate symbol to an appropriate number of terms is called an atomic formula, which evaluates to true or false in bivalent logics, given an interpretation.
For example, ⁠



(
x
+
1
)
∗
(
x
+
1
)


{\displaystyle (x+1)*(x+1)}

⁠ is a term built from the constant 1, the variable x, and the binary function symbols ⁠



+


{\displaystyle +}

⁠ and ⁠



∗


{\displaystyle *}

⁠; it is part of the atomic formula ⁠



(
x
+
1
)
∗
(
x
+
1
)
≥
0


{\displaystyle (x+1)*(x+1)\geq 0}

⁠ which evaluates to true for each real-numbered value of x.
Besides in logic, terms play important roles in universal algebra, and rewriting systems.




Formal definition



Given a set V of variable symbols, a set C of constant symbols and sets Fn of n-ary function symbols, also called operator symbols, for each natural number n ≥ 1, the set of (unsorted first-order) terms T is recursively defined to be the smallest set with the following properties:

every variable symbol is a term: V ⊆ T,
every constant symbol is a term: C ⊆ T,
from every n terms t1,...,tn, and every n-ary function symbol f ∈ Fn, a larger term f(t1, ..., tn) can be built.
Using an intuitive, pseudo-grammatical notation, this is sometimes written as:

t ::= x | c | f(t1, ..., tn).
The signature of the term language describes which function symbol sets Fn are inhabited. Well-known examples are the unary function symbols sin, cos ∈ F1, and the binary function symbols +, −, ⋅, / ∈ F2. Ternary operations and higher-arity functions are possible but uncommon in practice. Many authors consider constant symbols as 0-ary function symbols F0, thus needing no special syntactic class for them.
A term denotes a mathematical object from the domain of discourse. A constant c denotes a named object from that domain, a variable x ranges over the objects in that domain, and an n-ary function f maps n-tuples of objects to objects. For example, if n ∈ V is a variable symbol, 1 ∈ C is a constant symbol, and add ∈ F2 is a binary function symbol, then n ∈ T, 1 ∈ T, and (hence) add(n, 1) ∈ T by the first, second, and third term building rule, respectively. The latter term is usually written as n+1, using infix notation and the more common operator symbol + for convenience.




= Term structure vs. representation

=
Originally, logicians defined a term to be a character string adhering to certain building rules. However, since the concept of tree became popular in computer science, it turned out to be more convenient to think of a term as a tree. For example, several distinct character strings, like "(n⋅(n+1))/2", "((n⋅(n+1)))/2", and "






n
(
n
+
1
)

2




{\displaystyle {\frac {n(n+1)}{2}}}

", denote the same term and correspond to the same tree, viz. the left tree in the above picture.
Separating the tree structure of a term from its graphical representation on paper, it is also easy to account for parentheses (being only representation, not structure) and invisible multiplication operators (existing only in structure, not in representation).




= Structural equality

=
Two terms are said to be structurally, literally, or syntactically equal if they correspond to the same tree. For example, the left and the right tree in the above picture are structurally unequal terms, although they might be considered "semantically equal" as they always evaluate to the same value in rational arithmetic. While structural equality can be checked without any knowledge about the meaning of the symbols, semantic equality cannot. If the function / is e.g. interpreted not as rational but as truncating integer division, then at n=2 the left and right term evaluates to 3 and 2, respectively.
Structural equal terms need to agree in their variable names.
In contrast, a term t is called a renaming, or a variant, of a term u if the latter resulted from consistently renaming all variables of the former, i.e. if u = tσ for some renaming substitution σ. In that case, u is a renaming of t, too, since a renaming substitution σ has an inverse σ−1, and t = uσ−1. Both terms are then also said to be equal modulo renaming. In many contexts, the particular variable names in a term don't matter, e.g. the commutativity axiom for addition can be stated as x+y=y+x or as a+b=b+a; in such cases the whole formula may be renamed, while an arbitrary subterm usually may not, e.g. x+y=b+a is not a valid version of the commutativity axiom.




= Ground and linear terms

=
The set of variables of a term t is denoted by vars(t).
A term that doesn't contain any variables is called a ground term; a term that doesn't contain multiple occurrences of a variable is called a linear term.
For example, 2+2 is a ground term and hence also a linear term, x⋅(n+1) is a linear term, n⋅(n+1) is a non-linear term. These properties are important in, for example, term rewriting.
Given a signature for the function symbols, the set of all terms forms the free term algebra. The set of all ground terms forms the initial term algebra.
Abbreviating the number of constants as f0, and the number of i-ary function symbols as fi, the number θh of distinct ground terms of a height up to h can be computed by the following recursion formula:

θ0 = f0, since a ground term of height 0 can only be a constant,





θ

h
+
1


=

∑

i
=
0


∞



f

i


⋅

θ

h


i




{\displaystyle \theta _{h+1}=\sum _{i=0}^{\infty }f_{i}\cdot \theta _{h}^{i}}

, since a ground term of height up to h+1 can be obtained by composing any i ground terms of height up to h, using an i-ary root function symbol. The sum has a finite value if there is only a finite number of constants and function symbols, which is usually the case.




= Building formulas from terms

=
Given a set Rn of n-ary relation symbols for each natural number n ≥ 1, an (unsorted first-order) atomic formula is obtained by applying an n-ary relation symbol to n terms. As for function symbols, a relation symbol set Rn is usually non-empty only for small n. In mathematical logic, more complex formulas are built from atomic formulas using logical connectives and quantifiers. For example, letting




R



{\displaystyle \mathbb {R} }

denote the set of real numbers, ∀x: x ∈




R



{\displaystyle \mathbb {R} }

⇒ (x+1)⋅(x+1) ≥ 0 is a mathematical formula evaluating to true in the algebra of complex numbers.
An atomic formula is called ground if it is built entirely from ground terms; all ground atomic formulas composable from a given set of function and predicate symbols make up the Herbrand base for these symbol sets.




Operations with terms



Since a term has the structure of a tree hierarchy, to each of its nodes a position, or path, can be assigned, that is, a string of natural numbers indicating the node's place in the hierarchy. The empty string, commonly denoted by ε, is assigned to the root node. Position strings within the black term are indicated in red in the picture.
At each position p of a term t, a unique subterm starts, which is commonly denoted by t|p. For example, at position 122 of the black term in the picture, the subterm a+2 has its root. The relation "is a subterm of" is a partial order on the set of terms; it is reflexive since each term is trivially a subterm of itself.
The term obtained by replacing in a term t the subterm at a position p by a new term u is commonly denoted by t[u]p. The term t[u]p can also be viewed as resulting from a generalized concatenation of the term u with a term-like object t[.]; the latter is called a context, or a term with a hole (indicated by "."; its position being p), in which u is said to be embedded. For example, if t is the black term in the picture, then t[b+1]12 results in the term






a
∗
(
b
+
1
)


1
∗
(
2
∗
3
)





{\displaystyle {\frac {a*(b+1)}{1*(2*3)}}}

. The latter term also results from embedding the term b+1 into the context






a
∗
(

.

)


1
∗
(
2
∗
3
)





{\displaystyle {\frac {a*(\;.\;)}{1*(2*3)}}}

. In an informal sense, the operations of instantiating and embedding are converse to each other: while the former appends function symbols at the bottom of the term, the latter appends them at the top. The encompassment ordering relates a term and any result of appends on both sides.
To each node of a term, its depth (called height by some authors) can be assigned, i.e. its distance (number of edges) from the root. In this setting, the depth of a node always equals the length of its position string. In the picture, depth levels in the black term are indicated in green.
The size of a term commonly refers to the number of its nodes, or, equivalently, to the length of the term's written representation, counting symbols without parentheses. The black and the blue term in the picture has the size 15 and 5, respectively.
A term u matches a term t, if a substitution instance of u structurally equals a subterm of t, or formally, if uσ = t|p for some position p in t and some substitution σ. In this case, u, t, and σ are called the pattern term, the subject term, and the matching substitution, respectively. In the picture, the blue pattern term ⁠



x
∗
(
y
∗
z
)


{\displaystyle x*(y*z)}

⁠ matches the black subject term at position 1, with the matching substitution { x ↦ a, y ↦ a+1, z ↦ a+2 } indicated by blue variables immediately left to their black substitutes. Intuitively, the pattern, except for its variables, must be contained in the subject; if a variable occurs multiple times in the pattern, equal subterms are required at the respective positions of the subject.
unifying terms
term rewriting




Related concepts






= Sorted terms

=

When the domain of discourse contains elements of basically different kinds, it is useful to split the set of all terms accordingly. To this end, a sort (sometimes also called type) is assigned to each variable and each constant symbol, and a declaration of domain sorts and range sort to each function symbol. A sorted term f(t1,...,tn) may be composed from sorted subterms t1,...,tn only if the ith subterm's sort matches the declared ith domain sort of f. Such a term is also called well-sorted; any other term (i.e. obeying the unsorted rules only) is called ill-sorted.
For example, a vector space comes with an associated field of scalar numbers. Let W and N denote the sort of vectors and numbers, respectively, let VW and VN be the set of vector and number variables, respectively, and CW and CN the set of vector and number constants, respectively. Then e.g.






0
→



∈

C

W




{\displaystyle {\vec {0}}\in C_{W}}

and 0 ∈ CN, and the vector addition, the scalar multiplication, and the inner product is declared as ⁠



+
:
W
×
W
→
W
,
∗
:
W
×
N
→
W


{\displaystyle +:W\times W\to W,*:W\times N\to W}

⁠, and ⁠



⟨
.
,
.
⟩
:
W
×
W
→
N


{\displaystyle \langle .,.\rangle :W\times W\to N}

⁠, respectively. Assuming variable symbols






v
→



,



w
→



∈

V

W




{\displaystyle {\vec {v}},{\vec {w}}\in V_{W}}

and a,b ∈ VN, the term



⟨
(



v
→



+



0
→



)
∗
a
,



w
→



∗
b
⟩


{\displaystyle \langle ({\vec {v}}+{\vec {0}})*a,{\vec {w}}*b\rangle }

is well-sorted, while






v
→



+
a


{\displaystyle {\vec {v}}+a}

is not (since + doesn't accept a term of sort N as 2nd argument). In order to make



a
∗



v
→





{\displaystyle a*{\vec {v}}}

a well-sorted term, an additional declaration ⁠



∗
:
N
×
W
→
W


{\displaystyle *:N\times W\to W}

⁠ is required. Function symbols having several declarations are called overloaded.
See many-sorted logic for more information, including extensions of the many-sorted framework described here.




= Lambda terms

=



Motivation

Mathematical notations as shown in the table do not fit into the scheme of a first-order term as defined above, as they all introduce an own local, or bound, variable that may not appear outside the notation's scope, e.g.



t
⋅

∫

a


b


sin
⁡
(
k
⋅
t
)

d
t


{\displaystyle t\cdot \int _{a}^{b}\sin(k\cdot t)\;dt}

doesn't make sense.
In contrast, the other variables, referred to as free, behave like ordinary first-order term variables, e.g.



k
⋅

∫

a


b


sin
⁡
(
k
⋅
t
)

d
t


{\displaystyle k\cdot \int _{a}^{b}\sin(k\cdot t)\;dt}

does make sense.
All these operators can be viewed as taking a function rather than a value term as one of their arguments. For example, the lim operator is applied to a sequence, i.e. to a mapping from positive integer to e.g. real numbers. As another example, a C function to implement the second example from the table, Σ, would have a function pointer argument (see box below).
Lambda terms can be used to denote anonymous functions to be supplied as arguments to lim, Σ, ∫, etc.
For example, the function square from the C program below can be written anonymously as a lambda term λi. i2. The general sum operator Σ can then be considered as a ternary function symbol taking a lower bound value, an upper bound value and a function to be summed-up. Due to its latter argument, the Σ operator is called a second-order function symbol.
As another example, the lambda term λn. x/n denotes a function that maps 1, 2, 3, ... to x/1, x/2, x/3, ..., respectively, that is, it denotes the sequence (x/1, x/2, x/3, ...). The lim operator takes such a sequence and returns its limit (if defined).
The rightmost column of the table indicates how each mathematical notation example can be represented by a lambda term, also converting common infix operators into prefix form.



Definition


Given a set V of variable symbols, the set of lambda terms is defined recursively as follows:

every variable symbol x∈V is a lambda term;
if x∈V is a variable symbol and t is a lambda term, then λx.t is also a lambda term (abstraction);
if t1 and t2 are lambda terms, then ( t1 t2 ) is also a lambda term (application).
The above motivating examples also used some constants like div, power, etc. which are, however, not admitted in pure lambda calculus.
Intuitively, the abstraction λx.t denotes a unary function that returns t when given x, while the application ( t1 t2 ) denotes the result of calling the function t1 with the input t2. For example, the abstraction λx.x denotes the identity function, while λx.y denotes the constant function always returning y. The lambda term λx.(x x) takes a function x and returns the result of applying x to itself.




See also


Equation
Expression (mathematics)




Notes






References


Franz Baader; Tobias Nipkow (1999). Term Rewriting and All That. Cambridge University Press. pp. 1–2 and 34–35. ISBN 978-0-521-77920-3.

Kata Kunci Pencarian:

• Logika leksikal
• Britania Raya
• Semiotika
• Sifat komutatif
• Agama Hindu
• Filsafat sejarah
• Filsafat Bahasa
• Paradoks gagak
• Agnostisisme
• Sosialisme
• Term logic
• Term (logic)
• Logic
• Term
• Syllogism
• History of logic
• Proposition
• Classical logic
• Converse (logic)
• First-order logic