I invoked the general concepts of equivalence and distinction at this point in order to keep the wider backdrop of ideas in mind but since we’ve been focusing on boolean functions to coordinate the semantics of propositional calculi we can get a sense of the links between operations and relations by looking at their relationship in a boolean frame of reference.
Let and a positive integer. Then is the set of -tuples of elements of
- A -variable boolean function is a mapping
- A -place boolean relation is a subset of
The correspondence between boolean functions and boolean relations may be articulated as follows:
- Any -place relation as a subset of has a corresponding indicator function (or characteristic function) defined by the rule that if is in and if is not in
- Any -variable function is the indicator function of a -place relation consisting of all the in where The set is called the fiber of or the pre-image of in and is commonly notated as