8.2: Predicate logic

Predicate logic

Propositional logic can represent a lot of things, but it turns out to be too limiting to be practically useful. And that has to do with the atomic nature of propositions. Every proposition is its own opaque chunk of truthhood or falsity, with no way to break it down into constituent parts. Suppose I wanted to claim that every state in the union had a governor. To state this in propositional logic, I’d have to create a brand new proposition for each state:

Let G1 be the proposition that Alabama has a governor.

Let G2 be the proposition that Alaska has a governor.

Let G3 be the proposition that Arizona has a governor.

…

and then, finally, I could assert:

G1 \(\wedge\) G2 \(\wedge\) G3 \(\wedge \cdots \wedge\) G50.

That’s a lot of work just to create a whole bunch of individual propositions that are essentially the same. What we need is some kind of proposition template, with which we can “mint" new propositions of a similar form by plugging in new values.

This is exactly what a predicate is, which forms the basis for predicate logic, or “first-order predicate logic," to be more exact.¹ A predicate is a formula that yields a proposition for each value of its inputs. For instance, I can define a predicate called “HasGovernor" as follows:

Let HasGovernor(\(x\)) be the proposition that \(x\) is a state that has a governor.

Then I can assert:

HasGovernor(Virginia)

to state that Virginia has a governor. This mechanism alleviates the need to define fifty nearly-identical propositions. Instead, we define one predicate.

If you’re a programmer, you can think of a predicate as a function that returns a boolean. Whether you’re a programmer or not, you can think of a predicate as a function (in the chapter  sense) mapping objects to propositions: \[HasGovernor : \Omega \rightarrow P,\] where \(P\) is the set of all propositions. Note that the domain of this function is \(\Omega\), the entire domain of discourse. This means that you can give any input at all to the predicate. For instance, we can assert:

\(\neg\)HasGovernor(mayonnaise)

which is perfectly true.²

You may recall the word “predicate" from your middle school grammar class. Every sentence, remember, has a subject and a predicate. In “Billy jumps," “Billy" is the subject, and “jumps" the predicate. In “The lonely boy ate spaghetti with gusto," we have “the lonely boy" as the subject and “ate spaghetti with gusto" as the predicate. Basically, a predicate is anything that can describe or affirm something about a subject, which is exactly what we’re doing here. Imagine asserting “Jumps(Billy)" and “AteSpaghettiWithGusto(lonely boy)."

A predicate can have more than one input. Suppose we define the predicate IsFanOf as follows:

Let IsFanOf(\(x,y\)) be the proposition that \(x\) digs the music of rock band \(y\).

Then I can assert:

IsFanOf(Stephen, Led Zeppelin)

IsFanOf(Rachel, The Beatles)

IsFanOf(Stephen, The Beatles)

\(\neg\)IsFanOf(Stephen, The Rolling Stones)

We could even define TraveledToByModeInYear with a bunch of inputs:

Let TraveledToByModeInYear(\(p,d,m,y\)) be the proposition that person \(p\) traveled to destination \(d\) by mode \(m\) in year \(y\).

The following statements are then true:

TraveledToByModeInYear(Stephen, Richmond, car, 2007)

TraveledToByModeInYear(Rachel, Austria, plane, 2010)

\(\neg\)TraveledToByModeInYear(Johnny, Mars, spaceship, 1776)

Defining multiple inputs gives us more precision in defining relationships. Imagine creating the predicate “AteWithAttitude" and then asserting:

AteWithAttitude(lonely boy, spaghetti, gusto)

\(\neg\)AteWithAttitude(Johnny, broccoli, gusto)

AteWithAttitude(Johnny, broccoli, trepidation)

Predicates and relations

The astute reader may have noticed that the IsFanOf predicate, above, seems awfully similar to an isFanOf relation defined between sets \(P\) (the set of people) and \(R\) (the set of rock bands), where isFanOf \(\subseteq P \times R\). In both cases, we have pairs of people/bands for which it’s true, and pairs for which it’s false.

Indeed these concepts are identical. In fact, a relation can be defined as the set of ordered pairs (or tuples) for which a predicate is true. Saying “IsFanOf(Rachel, The Beatles)" and “\(\neg\)IsFanOf(Stephen, The Rolling Stones)" is really just another way of saying “Rachel isFanOf The Beatles" and “Stephen --isFanOf-- The Rolling Stones."

Quantifiers

One powerful feature of predicate logic is the ability to make grandiose statements about many things at once. Suppose we did want to claim that every state had a governor. How can we do it?

We’ll add to our repertoire the notion of quantifiers. There are two kinds of quantifiers in predicate logic, the first of which is called the universal quantifier. It’s written “\(\forall\)" and pronounced “for all." Here’s an example: \[\forall x\ HasGovernor(x).\] This asserts that for every x, HasGovernor is true. Actually, this isn’t quite right, for although Michigan and California have governors, mayonnaise does not. To be precise, we should say: \[\forall x\in S\ HasGovernor(x),\] where \(S\) is the set of all fifty states in the U.S.

We can use a quantifier for any complex expression, not just a simple predicate. For instance, if \(H\) is the set of all humans, then: \[\forall h\in H\ Male(h) \oplus Female(h)\] states that every human is either male or female, but not both. Another (more common) way to write this is to dispense with sets and define another predicate Human. Then we can say: \[\forall h\ Human(h) \Rightarrow Male(h) \oplus Female(h).\] Think this through carefully. We’re now asserting that this expression is true for all objects, whether they be Brad Pitt, Lady Gaga, or a bowl of oatmeal. To see that it’s true for all three, let \(h\) first be equal to Brad Pitt. We substitute Brad Pitt for \(h\) and get: \[\begin{aligned} Human(\text{Brad Pitt}) & \Rightarrow Male(\text{Brad Pitt}) \oplus Female(\text{Brad Pitt}) \\ \text{true} & \Rightarrow \text{true} \oplus \text{false} \\ \text{true} & \Rightarrow \text{true} \\ \text{true} & \ \checkmark\end{aligned}\] Remember that “implies" (\(\Rightarrow\)) is true as long as the premise (left-hand side) is false and/or the conclusion (right-hand side) is true. In this case, they’re both true, so we have a true end result. Something similar happens for Lady Gaga: \[\begin{aligned} Human(\text{Lady Gaga}) & \Rightarrow Male(\text{Lady Gaga}) \oplus Female(\text{Lady Gaga}) \\ \text{true} & \Rightarrow \text{false} \oplus \text{true} \\ \text{true} & \Rightarrow \text{true} \\ \text{true} & \ \checkmark\end{aligned}\] So these two cases both result in true. But perhaps surprisingly, we also get true for oatmeal: \[\begin{aligned} Human(\text{bowl of oatmeal}) & \Rightarrow Male(\text{bowl of oatmeal}) \oplus Female(\text{bowl of oatmeal}) \\ \text{false} & \Rightarrow \text{false} \oplus \text{false} \\ \text{false} & \Rightarrow \text{false} \\ \text{true} & \ \checkmark\end{aligned}\] Whoa, how did true pop out of that? Simply because the premise was false, and so all bets were off. We effectively said “if a bowl of oatmeal is human, then it will either be male or female. But it’s not, so never mind." Put another way, the bowl of oatmeal did not turn out to be a counterexample, and so we’re confident claiming that this expression is true “for all h": \(\forall\)h.

The other kind of quantifier is called the existential quantifier. As its name suggests, it asserts the existence of something. We write it “\(\exists\)" and pronounce it “there exists." For example, \[\exists x\ HasGovernor(x)\] asserts that there is at least one state that has a governor. This doesn’t tell us how many states this is true for, and in fact despite their name, quantifiers really aren’t very good at “quantifying" things for us, at least numerically. As of 2008, the statement \[\exists x\ President(x) \wedge African-American(x)\] is true, and always will be, no matter how many more African-American U.S. presidents we have. Note that in compound expressions like this, a variable (like \(x\)) always stands for a single entity wherever it appears. For hundreds of years there have existed African-Americans, and there have existed Presidents, so the expression above would be ridiculously obvious if it meant only “there have been Presidents, and there have been African-Americans." But the same variable \(x\) being used as inputs to both predicates is what seals the deal and makes it represent the much stronger statement “there is at least one individual who is personally both African-American and President of the United States at the same time."

It’s common practice to negate quantifiers, both universal and existential. As of 2012, the following statement is still true: \[\neg \exists p\ President(p) \wedge Female(p).\] This conveys that there does not exist a female president. As another example, if one day Missouri overhauls its government structure and replaces it with a mobocracy, perhaps we’ll state: \[\neg \forall x\ HasGovernor(x).\]

Interchanging quantifiers

Some illuminating themes can be seen when we examine the relationship that the two types of quantifiers have to each other. Consider this one first: \[\begin{aligned} \forall x \ P(x) \Leftrightarrow \neg \exists x\ \neg P(x), (\PageIndex{1})\end{aligned}\] where P is any predicate (or for that matter, any expression involving many predicates). That’s sensible. It states: “if \(P\) is true of all things, then there does not exist anything that it isn’t true for." Three other equivalences come to light: \[\begin{aligned} \neg \forall x \ P(x) & \Leftrightarrow \exists x\ \neg P(x) (\PageIndex{2}) \\ \forall x \ \neg P(x) & \Leftrightarrow \neg \exists x\ P(x) (\PageIndex{3}) \\ \neg \forall x \ \neg P(x) & \Leftrightarrow \exists x\ P(x) (\PageIndex{4}) \end{aligned}\]

In words, identity  \PageIndex{2} says “if it’s not true for everything, then it must be false for something." Identity  \PageIndex{3} says “if it’s false for everything, then there’s nothing it’s true for." And identity  \PageIndex{4} says “if it’s not false for everything, then it must be true for something." All of these are eminently logical, I think you’ll agree. They also imply that there are nearly always multiple correct ways to state something. In our apocalyptic vision of Missouri, for example, we stated “\(\neg \forall x\) HasGovernor\((x)\)," but we could just as well have stated “\(\exists x\ \neg\)HasGovernor\((x)\)," which amounts to the same thing.

Order matters

When you’re facing an intimidating morass of \(\forall\)’s and \(\exists\)’s and \(\vee\)’s and \(\Rightarrow\)’s and God knows what else, it’s easy to get lost in the sauce. But you have to be very careful to dissect the expression to find out what it means. Consider this one: \[\begin{aligned} \forall x \in \mathbb{R} \exists y \in \mathbb{R} \ x+1=y.\end{aligned}\] This statement is true. It says that for every single real number (call it \(x\)), it’s true that you can find some other number (call it \(y\)) that’s one greater than it. If you generate some examples it’s easy to see this is true. Suppose we have the real number \(x=5\). Is there some other number \(y\) that’s equal to \(x+1\)? Of course, the number 6. What if \(x=-32.4\)? Is there a number \(y\) that satisfies this equation? Of course, \(y=-31.4\). Obviously no matter what number \(x\) we choose, we can find the desired number \(y\) just by adding one. Hence this statement is true for all \(x\), just like it says.

What happens, though, if we innocently switch the order of the quantifiers? Let’s try asserting this: \[\begin{aligned} \exists y \in \mathbb{R} \forall x \in \mathbb{R} \ x+1=y.\end{aligned}\] Is this also true? Look carefully. It says “there exists some magic number \(y\) that has the following amazing property: no matter what value of \(x\) you choose, this \(y\) is one greater than \(x\)!" Obviously this is not true. There is no such number \(y\). If I choose \(y=13\), that works great as long as I choose \(x=12\), but for any other choice of \(x\), it’s dead in the water.

The lesson learned here is that the order of quantifiers matters. You have to take each quantifier/variable pair in turn, and think to yourself, “okay, this statement is asserting that once I choose the first variable, the rest of the expression is true for that choice."

The value of precision

This fluency with the basic syntax and meaning of predicate logic was our only goal in this chapter. There are all kinds of logical rules that can be applied to predicate logic statements in order to deduce further statements, and you’ll learn about them when you study artificial intelligence later on. Most of them are formalized versions of common sense. “If you know A is true, and you know A\(\Rightarrow\)B is true, then you can conclude B is true." Or “if you know X\(\wedge\)Y is false, and then you discover that Y is true, you can then conclude that X is false." Etc. The power to produce new truth from existing truth is the hallmark of AI systems, and why this stuff really matters.

If you can imagine a program doing this sort of automated reasoning, it will become clear why the precision of something like predicate logic — instead of the sloppiness of English — becomes important. English is a beautiful and poetic language, but its ambiguity is notorious. For example, back in chapter  we used the phrase “some employee belongs to every department" when describing relations. Now consider that English sentence. What does “some employee belongs to every department" actually mean? Does it mean that there is some special employee who happens to hold membership in every department in the company? Or does it mean that no department is empty: all departments have at least one person in them, for crying out loud? The English could mean either. In predicate logic, we’re either asserting: \[\exists x\ Employee(x) \wedge \forall y\ BelongsTo(x,y)\] or \[\forall y\ \exists x\ Employee(x) \wedge BelongsTo(x,y)\] These are two very different things. A human being would realize that it’s the second one the speaker means, drawing from a whole range of experience and common sense and context clues. But a ’bot has available none of these, and so it demands that the language clearly and unambiguously state exactly what’s meant.

English is rife with these ambiguities, especially involving pronouns. “After John hit George he ran away." What happened? Did John run away after striking George, fearing that George would retaliate? Or did George run away after getting hit, fearing additional abuse? It’s unclear what “he" refers to, so we can’t say from the sentence alone.

Here’s a funny one I’ll end with. Consider the sentence “He made her duck." What is intended here? Did he reach out with his hand and forcefully push her head down out of the way of a screaming projectile? Or did he prepare a succulent dish of roasted fowl to celebrate her birthday? Oh, if the computer could only know.

---

1. Or, if you want to sound really nerdy, you can call it first-order predicate calculus, which is a synonym.
2. By the way, when I say you can give any input at all to a predicate, I mean any individual element from the domain of discourse. I don’t mean that a set of elements can be an input. This limitation is why it’s called “firstorder” predicate logic. If you allow sets to be inputs to predicates, it’s called “second-order predicate logic,” and can get quite messy