Term (logic)


In mathematical logic, a term is an arrangement of dependent/bound symbols that denotes a mathematical object within an expression/formula. 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, variable symbols, 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, 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, terms play important roles in universal algebra, and rewriting systems.

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 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 can be built.
Using an intuitive, pseudo-grammatical notation, this is sometimes written as:
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 add ∈ 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 "", "", 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 and invisible multiplication operators.

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.
Structurally 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.
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⋅ is a linear term, n⋅ 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,
  • , 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 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 denote the set of real numbers, ∀x: x ∈ ⇒ ⋅ ≥ 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. 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. 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, 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 relates a term and any result of appends on both sides.
  • To each node of a term, its depth can be assigned, i.e. its distance 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