In mathematical logic, an uninterpreted function or function symbol is one that has no other property than its name and n-ary form. Function symbols are used, together with constants and variables, to form terms.
Contents
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 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. The satisfiability problem for free theories is solved by syntactic unification; 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 E-Unification and Narrowing.
Example
An array can be specified by the following equational axiom:
select(store(a,i,v),j) = (if i = j then v else select(a,j))This axiom can be used to deduce
select(store(store(a,1,−1),2,−2),1) = select(store(a,1,−1),1) = −1Note that this reasoning did not use any 'definition' or interpretation for the functions select and store. All that is known is the axiom.
Discussion
The decision problem for free theories is particularly important, as many theories can be reduced to it; the above example is the prototypical example of the theory of arrays, where 'select' and 'store' are the canonical array access functions.
Free theories can be solved by searching for common subexpressions to form the congruence closure. Solvers include satisfiability modulo theories solvers.