Recall from Chapter 5 that, in logic, a proposition is something that evaluates unequivocally to either TRUE or FALSE. Here are some examples:
2 + 3 = 52 + 3 > 7Jupiter is a starMars has two moonsVenus is between Earth and Mercury
Of these, Nos. 1, 4, and 5 are true and Nos. 2 and 3 are false—though we do need to be rather careful in the case of No. 5 over what exactly we mean by “between”! (To be a little more precise about the matter, what I mean by it is this: If we denote the distances of Mercury, Venus, and Earth from the sun by m, v, and e, respectively, then m < v < e.) Be that as it may, a good informal test for whether something, p say, is a valid proposition is to ask whether “Is it true that p?” is a sensible question. For example, “Is it true that 2 + 3 > 7?” is certainly a sensible question, even though the answer is no. To check your understanding of this point, which of the following do you think are legal propositions? (You might want to check the answers in Appendix F before continuing with this chapter.)
Bach is the greatest musician who ever lived.
What’s the time?
Supplier S2 is located in some city, x.
Some countries have a female president.
All politicians are corrupt.
Supplier S1 is located in Paris.
We both have the same favorite author, x.
It will rain tomorrow.
Supplier S6’s city is unknown.
By the way, there’s a very fine point here (which I’m mostly going to ignore; I mention it only to head off at the pass, as it were, certain criticisms that persons trained in formal logic might be tempted to level at this chapter): A proposition isn’t really a declarative sentence as such; rather, it’s the assertion made by that sentence. For example, “It’s hot” and “Il fait chaud” are distinct sentences, but they both assert the same proposition. That said, I’ll continue to assume from this point forward for simplicity that a proposition is indeed just a declarative sentence. Analogous remarks apply to predicates also (see later).
Given some set of propositions, we can combine propositions from that set to form further propositions, using various connectives. The connectives most commonly encountered in practice are NOT, AND, OR, IF ... THEN ... (also known as IMPLIES or “⇒”), and IF AND ONLY IF (also known as IFF, or BI-IMPLIES, or IS EQUIVALENT TO, or “⇔”, or “≡”). Here are a few examples of propositions that can be formed from Nos. 3, 4, and 5 from the foregoing list:
( Jupiter is a star ) OR ( Mars has two moons )( Jupiter is a star ) AND ( Jupiter is a star )( Venus is between Earth and Mercury AND NOT ( Jupiter is a star )IF ( Mars has two moons ) THEN ( Venus is between Earth and Mercury )IF ( Jupiter is a star ) THEN ( Mars has two moons )
Note: I’ve used parentheses to make the scope of the connectives clear in these examples; in practice, we adopt certain precedence rules that allow us to omit many of the parentheses that might otherwise be required. Of course, it’s never wrong to include them, even when they’re logically unnecessary, and sometimes they can improve clarity.
In general, the connectives can be regarded as logical operators—they take one or more propositions as their input and return another proposition as their output. NOT is a monadic operator, the other four are dyadic. A proposition that involves no connectives is called a simple proposition; a proposition that isn’t simple is called compound, or composite. And the truth value of a compound proposition can be determined from the truth values of its constituent simple propositions in accordance with the following truth tables (in which, for space reasons, I’ve abbreviated TRUE and FALSE to just T and F, respectively):
By the way, truth tables can also be drawn in the following slightly different style (and here I’ve abbreviated IF ... THEN ... to just IF, again for space reasons):
Neither style is more correct than the other; it’s just that sometimes one is more convenient, sometimes the other is. Anyway, let’s take a closer look at one of the foregoing compound propositions (number 9, to be specific). Here it is again:
9. IF ( Mars has two moons ) THEN ( Venus is between Earth and Mercury )
This proposition is of the form IF p THEN q (equivalently, p IMPLIES q), where p is the antecedent and q is the consequent. Since the antecedent and the consequent both evaluate to TRUE, the overall proposition evaluates to TRUE also, as you can see from the truth table. But whether Venus is between Earth and Mercury obviously has nothing to do with whether Mars has two moons! So what exactly is going on here?
The foregoing example highlights a problem that people with no training in formal logic often experience: namely, that implication is notoriously difficult to come to grips with. So I’d like to offer the following argument, or rationale, in an attempt to clarify the matter:
First of all, observe that there are exactly 16 dyadic connectives altogether, corresponding to the 16 possible dyadic truth tables (just four of which are shown above). Note: Exercise 10.1 asks you to draw all of those truth tables, and it might be worth having a go at that exercise right now.
Of those 16 dyadic connectives, some but not all are given common names such as AND and OR. But those names are really nothing more than a mnemonic device; they don’t have any intrinsic meaning, they’re chosen simply because the connectives so named have behavior that’s similar (not necessarily identical) to that of their natural language counterparts. Indeed, it’s easy to see that even AND doesn’t mean quite the same thing as “and” in natural language. In logic, p AND q and q AND p are equivalent—but their natural language counterparts might not be. Here’s an illustration: The natural language statements
“I was seriously disappointed and I voted for a change in leadership”
and
“I voted for a change in leadership and I was seriously disappointed”
are most certainly not equivalent! In other words, AND is a kind of logical distillate of “and” in natural language; very importantly—and unlike “and” in natural language—its meaning is context independent. Similar remarks apply to all of the other connectives.
Aside: The foregoing example (concerning AND) is perhaps a little misleading, in that it could be argued that “I was seriously disappointed” means different things in the two statements quoted. In the first, it means “I was seriously disappointed in the status quo”; in the second, it means “I was seriously disappointed in the outcome of the vote.” If this analysis is correct, it would be strictly incorrect to symbolize the two statements as p AND q and q AND p, respectively; although the two q’s are the same, the two p’s aren’t. But the example does at least show—not for the first time, perhaps—that we have to be rather careful in mapping natural language utterances to their symbolic logic counterparts. End of aside.
Of the 16 available dyadic connectives, the one called IMPLIES has behavior that most closely resembles that of implication as understood in natural language. For example, “if Mars has two moons, then it certainly has at least one moon” is a valid implication, both in logic and in natural language. But nobody would or should claim that logical implication and natural language implication are the same thing. In fact, logical implication, like all of the connectives, is (of necessity) formally defined—i.e., it’s defined purely in terms of the truth values, not the meanings, of its operands—whereas the same obviously can’t be said of its natural language counterpart.
Let’s look at another example (number 10 from the foregoing list):
IF ( Jupiter is a star ) THEN ( Mars has two moons )
Perhaps even more counterintuitively, this one evaluates to TRUE also (check the truth table), because the antecedent is false; yet whether Mars has two moons, again obviously, has nothing to do with whether Jupiter is a star. Again, part of the justification—for the fact that the implication evaluates to TRUE, that is—is just that IMPLIES is formally defined. In this case, however, there’s another argument (a database example, in fact) that you might find a little more satisfying. Suppose the suppliers-and-parts database is subject to the constraint that red parts must be stored in London (I deliberately state that constraint here in somewhat simplified form):
IF ( COLOR = 'Red' ) THEN ( CITY = 'London' )
Clearly we don’t want this constraint to be violated by a part that isn’t red. It follows, therefore, that we want the proposition overall (which is a logical implication) to evaluate to TRUE if the antecedent evaluates to FALSE.
It follows from all of the above that the proposition p IMPLIES q (equivalently, IF p THEN q) is logically equivalent to the proposition (NOT p) OR q—it evaluates to FALSE if and only if p evaluates to TRUE and q to FALSE, as you can see from the truth table. And, just incidentally, this equivalence serves to illustrate the point that the connectives NOT, AND, OR, IMPLIES, and IF AND ONLY IF aren’t all primitive; some of them can be expressed in terms of others. As a matter of fact, all possible monadic and dyadic connectives can be expressed in terms of suitable combinations of NOT and either AND or OR.[137] (Exercise: Check this claim.) Perhaps even more remarkably, all such connectives can in fact be expressed in terms of just one primitive. Can you find it?
The connectives AND and OR are commutative; that is, the compound propositions p AND q and q AND p are logically equivalent, and so are the compound propositions p OR q and q OR p. As a consequence, you should never write code involving such propositions that assumes that p will be evaluated before q or the other way around. For example, let the function SQRT (“nonnegative square root”) be defined in such a way that an exception is raised if its argument is negative, and consider the following SQL expression:
SELECT ...
FROM ...
WHERE X >= 0 AND SQRT ( X ) <= 100 ...This expression isn’t guaranteed to avoid raising the exception, because the SQRT function might be invoked before the test to ensure X is nonnegative is done.
Consider again the database constraint discussed above in connection with logical implication:
IF ( COLOR = 'Red' ) THEN ( CITY = 'London' )
Let me now point out that this expression is logically equivalent to the following one:
IF NOT ( CITY = 'London' ) THEN NOT ( COLOR = 'Red' )
This latter expression is the contrapositive of the original one. In general, in fact, we have the following equivalence:
IFpTHENq≡ IF NOTqTHEN NOTp
So here’s a question for you: How many of the following expressions are logically distinct?
IF ( WEIGHT > 17.0 ) THEN ( CITY ≠ 'Paris' )IF ( CITY = 'Paris' ) THEN ( WEIGHT ≤ 17.0 )( WEIGHT ≤ 17.0 ) OR ( CITY ≠ 'Paris' )NOT ( ( CITY = 'Paris' ) AND ( WEIGHT > 17.0 ) )
Well, I hope you can see that all four of these expressions in fact say the same thing. However, I think you’ll agree also that this fact isn’t immediately obvious! Let’s take a closer look. Let’s use p and q to denote the subexpressions (WEIGHT > 17.0) and (CITY ≠ ‘Paris’), respectively. The four expressions become:
IFpTHENqIF NOTqTHEN NOTpNOTpORqNOT ( ( NOTq) ANDp)
Now I think it’s easier to see that the four are all equivalent to one another.[138] So the example demonstrates two things: First (to repeat), the equivalences aren’t always obvious; second, introducing symbols like p and q allows us to manipulate the expressions in a purely formal manner and makes it easier to see what’s really going on (easier to see the forest as well as the trees, one might say). I’ll have more to say about such matters in the next chapter.
[137] Conventional logic (i.e., so called two valued logic, 2VL) is thus truth functionally complete. In general, a logic is truth functionally complete if and only if every possible connective can be defined in terms of the given ones. Truth functional completeness is an extremely important property; a logic that didn’t satisfy it would be like an arithmetic that was missing certain operations (the operation of addition, say) and would thus be of extremely limited utility.
[138] Easier, yes, but it’s still necessary to appeal to certain transformation laws that I haven’t yet defined (though they’re intuitively obvious). See Chapter 11 for further discussion.