Consider the following statements:[139]
xis a starxhas two moonsxhasmmoonsxis between Earth andyxis betweenyandz
Here x, y, z, and m are parameters or placeholders. As a consequence, the statements aren’t propositions (i.e., they aren’t unequivocally either true or false), precisely because they do involve such parameters. For example, the statement “x is a star” involves the parameter x, and we can’t say whether it’s true or false unless and until we’re told what that x stands for—at which point we’re no longer dealing with the given statement anyway but a different one instead, as the paragraph immediately following makes clear.
Now, we can substitute arguments for the parameters and thereby obtain propositions from those parameterized statements. For example, if we substitute the argument the sun for the parameter x in “x is a star,” we obtain “the sun is a star.” And this statement is indeed a proposition, because it’s unequivocally either true or false (in fact, of course, it’s true). But the original statement as such (“x is a star”) is, to say it again, not itself a proposition. Rather, it’s a predicate, which—as you’ll recall from Chapter 5—is a truth valued function; that is to say, it’s a function that, when invoked, returns a truth value. Like all functions, a predicate has a set of parameters; when it’s invoked, arguments are substituted for the parameters; substituting arguments for the parameters effectively converts the predicate into a proposition; and we say the arguments satisfy the predicate if and only if that proposition is true. For example, the argument the sun satisfies the predicate “x is a star,” while the argument the moon does not.
As an aside, I remind you from Chapter 5 that logicians speak not of invoking a predicate but rather of instantiating it (in fact, for reasons that needn’t concern us here, their concept of instantiation is slightly more general than that of the familiar notion of function invocation). However, I’ll favor the terminology of invocation in this chapter. Also, Exercise 5.18 in Chapter 5 showed that a proposition can be regarded as a degenerate predicate; to be precise, it’s a predicate for which the set of parameters is empty (and the truth valued function that is that predicate thus always returns the same result, either TRUE or FALSE, every time it’s invoked). In other words, all propositions are predicates, but most predicates aren’t propositions.
Now consider the predicate “x has m moons,” which involves two parameters, x and m. (For example, substituting the arguments Mars for x and 2 for m yields a true proposition; substituting the arguments Earth for x and 2 for m yields a false one.) In general, in fact, predicates can conveniently be classified according to the cardinality of their set of parameters. Thus we speak of an n-place predicate, meaning a predicate with exactly n parameters; for example, “x is between y and z” is a 3-place predicate, while “x has m moons” is a 2-place predicate. A proposition is a 0-place predicate. Note: An n-place predicate is also called an n-adic predicate. If n = 1, the predicate is monadic; if n = 2, it’s dyadic. And a proposition is a niladic predicate.
Next, given a set of predicates, we can combine predicates from that set to form further predicates using the logical connectives already discussed (NOT, AND, OR, and so forth); in other words, the connectives are logical operators that operate on predicates in general, not just on the special predicates that happen to be propositions. A predicate that involves no connectives is called simple; a predicate that isn’t simple is called compound, or composite. Here’s an example of a compound predicate:
(xis a star ) OR (xis between Earth andy)
This predicate is dyadic—not because it involves two simple predicates, but because it involves two parameters, x and y (one of which is referenced twice and the other once only).
It’s a bit of a digression from my main purpose in this chapter, but as an aside I can now give a (somewhat loose) definition of predicate logic. Logic in general can be defined as the science or scientific study of the methods and principles used in valid reasoning. Predicate logic in particular can be defined as a formal system involving predicates and connectives and the inferences that can be made using such predicates and connectives. Observe, therefore, that predicate logic involves certain rules of inference—i.e., rules by which additional truths can be proved from established truths. The additional truths are called theorems, and the established truths are either axioms or theorems that have previously been proved.
One important inference rule is called modus ponens. This rule states that if we know that p is true, and if we also know that IF p THEN q is true, then we can infer that q is true. For example, given the truth of both “I have no money” and “If I have no money, then I will have to wash dishes,” we can infer the truth of “I will have to wash dishes.”
Another important inference rule is modus tollens, which says that if we know that IF p THEN q is true, but we also know that q is false, then we can infer that p is false. This rule is relevant to the process of database integrity checking. Conceptually, what happens is this: When an update is requested, the proposed new database value is checked against known integrity constraints; if the proposition expressed by some constraint—see Chapter 8—now evaluates to FALSE, that proposed new value must also represent falsehood, and so the update must be rejected.
[139] Recall from Chapter 5 that statements in logic aren’t the same as statements in a programming language; in some respects, in fact, a statement in logic is more like a programming language expression, at least inasmuch as it denotes a value (a truth value, of course). In logic contexts, therefore, I’ll use the terms statement and expression (both in this chapter and the next) more or less interchangeably—and I apologize if this usage on my part leads to any confusion.