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 ...
, an uninterpreted function or function symbol is one that has no other property than its name and ''
n-ary
-ary may refer to:
* The arity of a function, operation, or relation
** -ary associativity, a specific rule attached to -ary functions
*** -ary group, a generalization of group
* The radix of a numerical representation system
* The number of le ...
'' form. Function symbols are used, together with constants and variables, to form
terms.
The theory of uninterpreted functions is also sometimes called the free theory, because it is freely generated, and thus a
free object, or the empty theory, being the
theory
A theory is a rational type of abstract thinking about a phenomenon, or the results of such thinking. The process of contemplative and rational thinking is often associated with such processes as observational study or research. Theories may be s ...
having an empty set of
sentences (in analogy to an
initial algebra). Theories with a non-empty set of equations are known as
equational theories
Equational may refer to:
* Equative, a construction in linguistics
* something pertaining to equations, in mathematics
* something pertaining to equality, in logic
See also
*
* Equation (disambiguation)
* Equality (disambiguation)
Equality ma ...
. The
satisfiability problem for free theories is solved by
syntactic unification In logic and computer science, unification is an algorithmic process of solving equations between symbolic expressions.
Depending on which expressions (also called ''terms'') are allowed to occur in an equation set (also called ''unification prob ...
; algorithms for the latter are used by interpreters for various computer languages, such as
Prolog. Syntactic unification is also used in algorithms for the satisfiability problem for certain other equational theories, see
Unification (computer science) In logic and computer science, unification is an algorithmic process of solving equations between symbolic expressions.
Depending on which expressions (also called ''terms'') are allowed to occur in an equation set (also called ''unification prob ...
.
Example
As an example of uninterpreted functions for SMT-LIB, if this input is given to an
SMT solver:
(declare-fun f (Int) Int)
(assert (= (f 10) 1))
the SMT solver would return "This input is satisfiable". That happens because
f is an uninterpreted function (i.e., all that is known about
f is its
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 ...
), so it is possible that
f(10) = 1. But by applying the input below:
(declare-fun f (Int) Int)
(assert (= (f 10) 1))
(assert (= (f 10) 42))
the SMT solver would return "This input is unsatisfiable". That happens because
f, being a function, can never return different values for the same input.
Discussion
The
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...
for free theories is particularly important, because many theories can be reduced by it.
Free theories can be solved by searching for
common subexpression
Common may refer to:
Places
* Common, a townland in County Tyrone, Northern Ireland
* Boston Common, a central public park in Boston, Massachusetts
* Cambridge Common, common land area in Cambridge, Massachusetts
* Clapham Common, originally com ...
s to form the
congruence closure
In mathematics, a subset of a given set is closed under an operation of the larger set if performing that operation on members of the subset always produces a member of that subset. For example, the natural numbers are closed under addition, bu ...
. Solvers include
satisfiability modulo theories solvers.
See also
*
Algebraic data type
*
Initial algebra
*
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 ...
*
Theory of pure equality
In mathematical logic the theory of pure equality is a first-order theory. It has a signature consisting of only the equality relation symbol, and includes no non-logical axioms at all.
This theory is consistent but incomplete, as a non-empty set ...
Notes
References
{{Formalmethods-stub
Specification languages