I showed in the previous section that one way to get a proposition from a predicate is to invoke it with an appropriate set of arguments. But there's another way, too, and that's by means of quantification. Let p(x) be a monadic predicate (I show the single parameter x explicitly, for clarity). Then: The expression: EXISTS x ( p ( x ) ) is a proposition, and it means: "There exists at least one possible argument value a corresponding to the parameter x such that p(a) evaluates to TRUE" (in other words, the argument value a satisfies predicate p). For example, if p is the predicate "x is a logician," then: EXISTS x ( x is a logician ) is a proposition one that evaluates to TRUE, as it happens (for example, take a to be Bertrand Russell). The expression: FORALL x ( p ( x ) ) is a proposition, and it means: "All possible argument values a corresponding to the parameter x are such that p(a) evaluates to TRUE" (in other words, all such argument values a satisfy predicate p). For example, if again p is the predicate "x is a logician," then: FORALL x ( x is a logician ) is a proposition one that evaluates to FALSE, as it happens (for example, take a to be George W. Bush). Observe that it's sufficient to produce a single example to show the truth of the EXISTS proposition and a single counterexample to show the falsity of the FORALL proposition. Observe too in both cases that the parameter must be constrained to "range over" some set of permissible values (the set of all people, in the example). I'll come back to this point later, in the section "Database Constraints." The term used in logic for the expressions EXISTS x and FORALL x in the foregoing discussion is quantifiers (the term derives from the verb to quantify, which simply means to express as a quantity that is, to say how much of something there is or how many somethings there are). Quantifiers of the form EXISTS...are said to be existential; quantifiers of the form FORALL...are said to be universal. (And in logic texts, EXISTS is usually represented by a backward E and FORALL by an upside-down A. I use the keywords EXISTS and FORALL for typographical reasons not to mention readability.) By way of another example, let q be the dyadic predicate "x is taller than y." If we "quantify existentially over x," we obtain: EXISTS x ( x is taller than y ) Now, this statement is not a proposition, because it isn't unequivocally either true or false; in fact, it's a monadic predicate it has a single parameter, y. Suppose we invoke this predicate with argument Steve. We obtain: EXISTS x ( x is taller than Steve ) This statement is a proposition (and if there exists at least one person Arnold, say who's taller than Steve, then it evaluates to TRUE, of course). But another way to obtain a proposition from the original predicate q is to quantify over both of the parameters x and y. For example: EXISTS x ( EXISTS y ( x is taller than y ) ) This statement is indeed a proposition; it evaluates to FALSE only if nobody is taller than anybody else and to TRUE otherwise (think about it!). There are several lessons to be learned from this example:
|