� Chapter 5 First-Order Logic 5.1 Quantifiers There are a couple of assertions commonly made about a predicate: that it is some-times true and that it is always true. For example, the predicate “x 2 ≥ 0” is always true when x is a real number. On the other hand, the predicate “5x 2 − 7 = 0” is only sometimes true; specifically, when x = ± 7/5. There are several ways to express the notions of “always true” and “sometimes true” in English. The table below gives some general formats on the left and spe-cific examples using those formats on the right. You can expect to see such phrases hundreds of times in mathematical writing! Always True For all n, P (n) is true. For all x ∈ R, x2 ≥ 0. P (n) is true for every n. x2 ≥ 0 for every x ∈ R. Sometimes True There exists an n such that P (n) is true. There exists an x ∈ R such that 5x2 − 7 = 0. P (n) is true for some n. 5x2 − 7 = 0 for some x ∈ R. P (n) is true for at least one n. 5x2 − 7 = 0 for at least one x ∈ R. All these sentences quantify how often the predicate is true. Specifically, an assertion that a predicate is always true is called a universal quantification, and an assertion that a predicate is sometimes true is an existential quantification. Some-times the English sentences are unclear with respect to quantification: 7374 CHAPTER 5. FIRST-ORDER LOGIC “If you can solve any problem we come up with, then you get an A for the course.” The phrase “you can solve any problem we can come up with” could reasonably be interpreted as either a universal or existential quantification: “you can solve every problem we come up with,” or maybe “you can solve at least one problem we come up with.” In any case, notice that this quantified phrase appears inside a larger if-then state-ment. This is quite normal; quantified statements are themselves propositions and can be combined with and, or, implies, etc., just like any other proposition. 5.1.1 More Cryptic Notation There are symbols to represent universal and existential quantification, just as there are symbols for “and” (∧), “implies” (−→), and so forth. In particular, to say that a predicate, P , is true for all values of x in some set, D, one writes: ∀x ∈ D. P (x) The symbol ∀ is read “for all”, so this whole expression is read “for all x in D, P (x) is true”. To say that a predicate P (x) is true for at least one value of x in D, one writes: ∃x ∈ D. P (x) The backward-E, ∃, is read “there exists”. So this expression would be read, “There exists an x in D such that P (x) is true.” The symbols ∀ and ∃ are always followed by a variable —usually with an indication of the set the variable ranges over —and then a predicate, as in the two examples above. As an example, let Probs be the set of problems we come up with, Solves(x) be the predicate “You can solve problem x”, and G be the proposition, “You get an A for the course.” Then the two different interpretations of “If you can solve any problem we come up with, then you get an A for the course.” can be written as follows: (∀x ∈ Probs. Solves(x)) IMPLIES G, or maybe (∃x ∈ Probs. Solves(x)) IMPLIES G.5.1. QUANTIFIERS 75 5.1.2 Mixing Quantifiers Many mathematical statements involve several quantifiers. For example, Gold-bach’s Conjecture states: “Every even integer greater than 2 is the sum of two primes.” Let’s write this more verbosely to make the use of quantification clearer: For every even integer n greater than 2, there exist primes p and q such that n = p + q. Let Evens be the set of even integers greater than 2, and let Primes be the set of primes. Then we can write Goldbach’s Conjecture in logic notation as follows: ∀n ∈ Evens ∃p ∈ Primes ∃q ∈ Primes. n = p + q. � �� �� �� � for every even there exist primes integer n > 2 p and q such that 5.1.3 Order of Quantifiers Swapping the order of different kinds of quantifiers (existential or universal) usu-ally changes the meaning of a proposition. For example, let’s return to one of our initial, confusing statements: “Every American has a dream.” This sentence is ambiguous because the order of quantifiers is unclear. Let A be the set of Americans, let D be the set of dreams, and define the predicate H(a, d) to be “American a has dream d.”. Now the sentence could mean there is a single dream that every American shares: ∃ d ∈ D ∀a ∈ A. H(a, d) For example, it might be that every American shares the dream of owning their own home. Or it could mean that every American has a personal dream: ∀a ∈ A ∃ d ∈ D. H(a, d) For example, some Americans may dream of a peaceful retirement, while others dream of continuing practicing their profession as long as they live, and still others may dream of being so rich they needn’t think at all about work. Swapping quantifiers in Goldbach’s Conjecture creates a patently false state-ment that every even number ≥ 2 is the sum of the same two primes: ∃ p ∈ Primes ∃ q ∈ Primes ∀n ∈ Evens. n = p + q. � �� �� �� � there exist primes for every even p and q such that integer n > 276 CHAPTER 5. FIRST-ORDER LOGIC Variables Over One Domain When all the variables in a formula are understood to take values from the same nonempty set, D, it’s conventional to omit mention of D. For example, instead of ∀x ∈ D ∃y ∈ D. Q(x, y) we’d write ∀x∃y. Q(x, y). The unnamed nonempty set that x and y range over is called the domain of discourse, or just plain domain, of the formula. It’s easy to arrange for all the variables to range over one domain. For exam-ple, Goldbach’s Conjecture could be expressed with all variables ranging over the domain N as ∀n. n ∈ Evens IMPLIES (∃ p∃ q. p ∈ Primes ∧ q ∈ Primes ∧ n = p + q). 5.1.4 Negating Quantifiers There is a simple relationship between the two kinds of quantifiers. The following two sentences mean the same thing: It is not the case that everyone likes to snowboard. There exists someone who does not like to snowboard. In terms of logic notation, this follows from a general property of predicate formu-las: NOT ∀x. P (x) is equivalent to ∃x. NOT P (x). Similarly, these sentences mean the same thing: There does not exist anyone who likes skiing over magma. Everyone dislikes skiing over magma. We can
View Full Document
Unlocking...