Syntax and Semantics

The syntax of Functional Logic is the same as that of Relational Logic except for the addition of function constants and functional expressions.

As we shall see, function constants are similar to relation constants in that they are used in forming complex expressions by combining them with an appropriate number of arguments. Accordingly, each function constant has an associated arity, i.e. the number of arguments with which that function constant can be combined. A function constant that can combined with a single argument is said to be unary; one that can be combined with two arguments is said to be binary; one that can be combined with three arguments is said to be ternary; more generally, a function constant that can be combined with n arguments is said to be n-ary.

A functional expression, or functional term, is an expression formed from an n-ary function constant and n terms enclosed in parentheses and separated by commas. For example, if f is a binary function constant and if a and y are terms, then f(a,y) is a functional expression, as are f(a,a) and f(y,y).

Note that, unlike relational sentences, functional expressions can be nested within other functional expressions. For example, if g is a unary function constant and if a is a term, g(a) and g(g(a)) and g(g(g(a))) are all functional expressions.

Finally, in Functional Logic, we define a term to be a variable or an object constant or a functional expression. The definition here is the same as before except for the addition of functional expressions to this list of possibilities.

And that is all. Relational sentences, logical sentences, and quantified sentences are defined exactly as for ordinary Relational Logic. The only difference between the two languages is that Functional Logic allows for functional expressions inside of sentences whereas ordinary Relational Logic does not.

The semantics of Functional Logic is effectively the same as that of Relational Logic. The key difference is that, in the presence of functions, the Herbrand base for such a language is infinitely large.

As before, we define the Herbrand base for a vocabulary to be the set of all ground relational sentences that can be formed from the constants of the language. Said another way, it is the set of all sentences of the form r(t₁,...,t_n), where r is an n-ary relation constant and t₁, ... , t_n are ground terms.

For a vocabulary with a single object constant a and a single unary function constant f and a single unary relation constant r, the Herbrand base consists of the sentences shown below.

A truth assignment for Functional Logic is a mapping that gives each ground relational sentence in the Herbrand base a unique truth value. This is the same as for Relational Logic. The main difference from Relational Logic is that, in this case, a truth assignment is necessarily infinite, since there are infinitely many elements in the Herbrand Base.

Luckily, things are not always so bad. In some cases, only finitely many elements of the Herbrand base are true. In such cases, we can describe a truth assignment in finite space by writing out the elements that are true and assuming that all other elements are false. We shall see some examples of this in the coming sections.

The rules defining the truth of logical sentences in Functional Logic are the same as those for logical sentences in Propositional Logic and Relational Logic, and the rules for quantified sentences in Functional Logic are exactly the same as those for Relational Logic.