In
mathematical logic
Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of for ...
, a term denotes a mathematical object while a
formula
In science, a formula is a concise way of expressing information symbolically, as in a mathematical formula or a ''chemical formula''. The informal use of the term ''formula'' in science refers to the general construct of a relationship betwee ...
denotes a mathematical fact. In particular, terms appear as components of a formula. This is analogous to natural language, where a
noun phrase
In linguistics, a noun phrase, or nominal (phrase), is a phrase that has a noun or pronoun as its head or performs the same grammatical function as a noun. Noun phrases are very common cross-linguistically, and they may be the most frequently oc ...
refers to an object and a whole
sentence refers to a fact.
A
first-order
In mathematics and other formal sciences, first-order or first order most often means either:
* "linear" (a polynomial of degree at most one), as in first-order approximation and other calculus uses, where it is contrasted with "polynomials of high ...
term is
recursively constructed from constant symbols,
variables and
function symbols.
An expression formed by applying a
predicate symbol In mathematical logic, a predicate variable is a predicate letter which functions as a "placeholder" for a relation (between terms), but which has not been specifically assigned any particular relation (or meaning). Common symbols for denoting predi ...
to an appropriate number of terms is called an
atomic formula
In mathematical logic, an atomic formula (also known as an atom or a prime formula) is a formula with no deeper propositional structure, that is, a formula that contains no logical connectives or equivalently a formula that has no strict subformu ...
, which evaluates to
true
True most commonly refers to truth, the state of being in congruence with fact or reality.
True may also refer to:
Places
* True, West Virginia, an unincorporated community in the United States
* True, Wisconsin, a town in the United States
* Tr ...
or
false in
bivalent logics, given an
interpretation.
For example, is a term built from the constant 1, the variable , and the binary function symbols and ; it is part of the atomic formula which evaluates to true for each
real-numbered value of .
Besides in
logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...
, terms play important roles in
universal algebra
Universal algebra (sometimes called general algebra) is the field of mathematics that studies algebraic structures themselves, not examples ("models") of algebraic structures.
For instance, rather than take particular groups as the object of study, ...
, and
rewriting system
In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewrite engines, or reduc ...
s.
Formal definition
![Tree structure of mathematical first-order terms svg](https://upload.wikimedia.org/wikipedia/commons/a/ac/Tree_structure_of_mathematical_first-order_terms_svg.svg)
Given a set ''V'' of variable symbols, a set ''C'' of constant symbols and sets ''F''
''n'' 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 ''t''
1,...,''t''
''n'', and every ''n''-ary function symbol ''f'' ∈ ''F''
''n'', a larger term ''f''(''t''
1, ..., ''t''
''n'') can be built.
Using an intuitive, pseudo-
grammatical
In linguistics, grammaticality is determined by the conformity to language usage as derived by the grammar of a particular variety (linguistics), speech variety. The notion of grammaticality rose alongside the theory of generative grammar, the go ...
notation, this is sometimes written as:
:''t'' ::= ''x'' , ''c'' , ''f''(''t''
1, ..., ''t''
''n'').
The
signature
A signature (; from la, signare, "to sign") is a handwritten (and often stylized) depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and intent. The writer of a ...
of the term language describes which function symbol sets ''F''
''n'' are inhabited. Well-known examples are the unary function symbols ''sin'', ''cos'' ∈ ''F''
1, and the binary function symbols +, −, ⋅, / ∈ ''F''
2.
Ternary operation
In mathematics, a ternary operation is an ''n''-ary operation with ''n'' = 3. A ternary operation on a set ''A'' takes any given three elements of ''A'' and combines them to form a single element of ''A''.
In computer science, a ternary operator i ...
s and higher-arity functions are possible but uncommon in practice. Many authors consider constant symbols as 0-ary function symbols ''F''
0, thus needing no special syntactic class for them.
A term denotes a mathematical object from the
domain of discourse
In the formal sciences, the domain of discourse, also called the universe of discourse, universal set, or simply universe, is the set of entities over which certain variables of interest in some formal treatment may range.
Overview
The domain ...
. 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''-
tuple
In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...
s of objects to objects. For example, if ''n'' ∈ ''V'' is a variable symbol, 1 ∈ ''C'' is a constant symbol, and ''add'' ∈ ''F''
2 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
Infix notation is the notation commonly used in arithmetical and logical formulae and statements. It is characterized by the placement of operators between operands—" infixed operators"—such as the plus sign in .
Usage
Binary relations a ...
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.
[; here: Sect.II.1.3] However, since the concept of
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
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 "", "", and "
", 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 ''un''equal 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.
[Since atomic formulas can be viewed as trees, too, and renaming is essentially a concept on trees, atomic (and, more generally, quantifier-free) formulas can be renamed in a similar way as terms. In fact, some authors consider a quantifier-free formula as a term (of type ''bool'' rather than e.g. ''int'', cf. #Sorted terms below).]
[Renaming of the commutativity axiom can be viewed as alpha-conversion on the ]universal closure
In mathematical logic, a universal quantification is a type of Quantification (logic), quantifier, a logical constant which is interpretation (logic), interpreted as "given any" or "for all". It expresses that a predicate (mathematical logic), pr ...
of the axiom: "''x''+''y''=''y''+''x''" actually means "∀''x'',''y'': ''x''+''y''=''y''+''x''", which is synonymous to "∀''a'',''b'': ''a''+''b''=''b''+''a''"; see also #Lambda terms below.
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
In mathematical logic, a ground term of a formal system is a term that does not contain any variables. Similarly, a ground formula is a formula that does not contain any variables.
In first-order logic with identity, the sentence Q(a) \lor P(b) ...
''; 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
In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewrite engines, or reduc ...
.
Given a
signature
A signature (; from la, signare, "to sign") is a handwritten (and often stylized) depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and intent. The writer of a ...
for the function symbols, the set of all terms forms the ''
free
Free may refer to:
Concept
* Freedom, having the ability to do something, without having to obey anyone/anything
* Freethought, a position that beliefs should be formed only on the basis of logic, reason, and empiricism
* Emancipate, to procur ...
term algebra
In universal algebra and mathematical logic, a term algebra is a freely generated algebraic structure over a given signature. For example, in a signature consisting of a single binary operation, the term algebra over a set ''X'' of variables is exa ...
''. The set of all ground terms forms the ''
initial
In a written or published work, an initial capital, also referred to as a drop capital or simply an initial cap, initial, initcapital, initcap or init or a drop cap or drop, is a letter at the beginning of a word, a chapter, or a paragraph that ...
term algebra''.
Abbreviating the number of constants as ''f''
0, and the number of ''i''-ary function symbols as ''f''
''i'', the number θ
''h'' of distinct ground terms of a height up to ''h'' can be computed by the following recursion formula:
* θ
0 = ''f''
0, since a ground term of height 0 can only be a constant,
*
, 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 ''R''
''n'' 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 ''R''
''n'' is usually non-empty only for small ''n''. In mathematical logic, more complex
formulas
In science, a formula is a concise way of expressing information symbolically, as in a mathematical formula or a ''chemical formula''. The informal use of the term ''formula'' in science refers to the general construct of a relationship betwee ...
are built from atomic formulas using
logical connective
In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary co ...
s and
quantifiers. For example, letting
denote the set of
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s, ∀''x'': ''x'' ∈
⇒ (''x''+1)⋅(''x''+1) ≥ 0 is a mathematical formula evaluating to true in the algebra of
complex number
In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the form ...
s.
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
In first-order logic, a Herbrand structure ''S'' is a structure over a vocabulary σ that is defined solely by the syntactical properties of σ. The idea is to take the symbols of terms as their values, e.g. the denotation of a constant symbol ' ...
for these symbol sets.
Operations with terms
![Example term for position, path, depth, match svg](https://upload.wikimedia.org/wikipedia/commons/f/f2/Example_term_for_position%2C_path%2C_depth%2C_match_svg.svg)
* 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 . 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
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
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 . The term can also be viewed as resulting from a generalized concatenation of the term ''u'' with a term-like object ; 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 results in the term
. The latter term also results from embedding the term into the context
. 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
In theoretical computer science, in particular in automated theorem proving and term rewriting,
the containment, or encompassment, preorder (≤) on the set of term (logic), terms, is defined by
:''s'' ≤ ''t'' if a Term (logic)#Operatio ...
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 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 matches the black subject term at position 1, with the matching substitution 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
In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewrite engines, or reduc ...
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
[I.e., "symbol type" in the Many-sorted signatures section of the Signature (logic) article.] of domain sorts and range sort to each function symbol. A ''sorted term'' ''f''(''t''
1,...,''t''
''n'') may be composed from sorted subterms ''t''
1,...,''t''
''n'' only if the th subterm's sort matches the declared th 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
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...
comes with an associated
field
Field may refer to:
Expanses of open ground
* Field (agriculture), an area of land used for agricultural purposes
* Airfield, an aerodrome that lacks the infrastructure of an airport
* Battlefield
* Lawn, an area of mowed grass
* Meadow, a grass ...
of scalar numbers. Let ''W'' and ''N'' denote the sort of vectors and numbers, respectively, let ''V''
''W'' and ''V''
''N'' be the set of vector and number variables, respectively, and ''C''
''W'' and ''C''
''N'' the set of vector and number constants, respectively. Then e.g.
and , and the vector addition, the scalar multiplication, and the inner product is declared as , and , respectively. Assuming variable symbols
and , the term
is well-sorted, while
is not (since + doesn't accept a term of sort ''N'' as 2nd argument). In order to make
a well-sorted term, an additional declaration is required. Function symbols having several declarations are called ''overloaded''.
See
many-sorted logic
Many-sorted logic can reflect formally our intention not to handle the universe as a homogeneous collection of objects, but to partition it in a way that is similar to types in typeful programming. Both functional and assertive "parts of speech" i ...
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.
doesn't make sense.
In contrast, the other variables, referred to as ''free'', behave like ordinary first-order term variables, e.g.
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 term
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation ...
s'' can be used to denote ''
anonymous function
In computer programming, an anonymous function (function literal, lambda abstraction, lambda function, lambda expression or block) is a function definition that is not bound to an identifier. Anonymous functions are often arguments being passed to ...
s'' 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''. ''i''
2. 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
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
(''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
An infix is an affix inserted inside a word stem (an existing word or the core of a family of words). It contrasts with ''adfix,'' a rare term for an affix attached to the outside of a stem, such as a prefix or suffix.
When marking text for int ...
operators into
prefix
A prefix is an affix which is placed before the Word stem, stem of a word. Adding it to the beginning of one word changes it into another word. For example, when the prefix ''un-'' is added to the word ''happy'', it creates the word ''unhappy'' ...
form.
int sum(int lwb, int upb, int fct(int))
int square(int i) // implements anonymous function (lambda i. i*i); however, C requires a name for it
#include
int main(void)
Definition
See also
*
Equation
In mathematics, an equation is a formula that expresses the equality of two expressions, by connecting them with the equals sign . The word ''equation'' and its cognates in other languages may have subtly different meanings; for example, in ...
*
Expression (mathematics)
In mathematics, an expression or mathematical expression is a finite combination of symbols that is well-formed according to rules that depend on the context. Mathematical symbols can designate numbers ( constants), variables, operations, f ...
Notes
References
*
{{Mathematical logic
Mathematical logic
Rewriting systems
Elementary mathematics