Function Glossary
Definition
A function takes as input objects from some domain and gives as output an object. We refer to the inputs as its arguments, and the output as its value for those arguments.
A function symbol is an expression standing for a function. In logic as presented in the lectures, we use lower case letters such as 'f' and 'g' as function symbols. In Logic for Fun function symbols may be strings of characters.
Comments
Each function we consider has a definite arity or number of arguments it takes.
In the basic case, we only consider total functions, which are those which have a value for every possible argument. Sometimes we relax this to consider partial functions, which may be undefined for some of their arguments.
It is not required that there is a way to compute the value of a function given its arguments. Even in well-behaved domains such as the natural numbers, most functions are uncomputable, in fact. All that is required is that the value exists.
Examples
- Addition in the ordinary number systems is a familiar example of a total function with two arguments. Given inputs 5 and 7, for example, it returns the value 12.
- In the domain of Australians, the spouse function maps each married person to their husband or wife. This function is partial, as some Australians are not married.
- In Logic for Fun, a predicate is just a function whose value sort is bool, and a connective is just a symbol for a predicate whose arguments are all bool as well.