1.3
Predicate Logic

1.3.1 Introduction

Although sentential logic studied in Sections 1.1 and 1.2 is probably sufficient to get you through your daily activities, it is not sufficient for higher mathematics. This was realized in the late 1800s by the German logician Gottlob Frege, who observed that mathematics requires a more extensive language than simple logical sentences connected by ∧, ∨, ∼, ⇒, ⇔. Frege introduced what is called predicate logic1(or first‐order logic), which are sentences which in addition to the logical connectives of sentential logic, includes quantifiers, variables, and functions called predicates (or propositions). Predicate logic allows one to express concepts we often hear in mathematics, like

for any real number x, there exists a real number y such that x < y

which is impossible to express in sentential logic.

1.3.2 Existential and Universal Quantifiers

Two phrases one hears again and again in mathematics are for all, and there exists. These expressions are called quantifiers and are necessary to describe mathematical concepts. The meaning of an expression like x < y in itself is not clear until we describe the extent of x and y. This leads to the two basic quantifiers of predicate logic, the universal quantifier, meaning “for all” and denoted by ∀ (upside down A), and the existential quantifier, meaning “there exists,” and denoted by ∃ (backwards E). Inherent in the use of quantifiers is the concept of a universe set, which is the collection or set of objects under discussion, often being the real numbers, integers, natural numbers, and so on.

Some common number universes in mathematics are the following.

1.3.3 More than One Variable in a Proposition

Propositions (or predicates) in predicate logic often contain more than one variable, which means the proposition must contain more than one quantifier to put limits on the variables. The following Table 1.29 illustrates propositions with two variables and what it means for the propositions to be true or false. To simplify notation, we assume the universe is known, so we do not include it.

Table 1.29 Propositions with two variables.

Proposition Proposition is true when Proposition is false when
(∀x)(∀y)P(x, y) For all x and y, P(x, y) is true There exists some x, y. such that P(x, y) is false
(∃x)(∀y)P(x, y) There is an x such that for all y, P(x, y) is true For all x, P(x, y) is false for some y
(∀x)(∃y)P(x, y) For all x, P(x, y) is true for some y There exists an x such that for all y P(x, y) is false
(∃x)(∃y)P(x, y) There exists x, y. such that P(x, y)is true For all x, y. P(x, y) is false

Table 1.30 Sentences in predicate logic.

Proposition English meaning Truth value
(∀x ∈ ℝ)  (x2 ≥ 0) For any real number, its square is nonnegative. True
(∃n ∈ ℕ)  (n is a prime number) There exists a prime number. True
(∃n ∈ ℕ) (2 /| n) There exists at least one odd natural number. True
(∃n ∈ ℕ)  (2 | n) There exists at least one even natural number. True
(∀x ∈ ℕ)  (∃y ∈ ℕ)  (x = y + 1) For any natural number x, there is a natural number y satisfying x = y + 1. False
(∀x ∈ ℝ)  (∃y ∈ ℝ)  (x < y) For any real number x, there is a real numbery greater than x. True
(∃x ∈ ℝ)  (∀y ∈ ℝ)  (x < y) There exists a real number x such that all real numbers y are greater than x. False
(∀x ∈ ℝ)(∃y ∈ ℝ) (y = 2x) For any positive real number x, there is a real number y that satisfies y = 2x. True

1.3.4 Order Matters

Here's a question to ponder. Do the two propositions (∃x)(∀y)P(x, y) and (∀y)(∃x)P(x, y) mean the same thing or does one imply the other or are they completely unrelated? For example do the following to two propositions:

  • (∃x ∈ ℝ)(∀y ∈ ℝ)(x < y)
  • (∀y ∈ ℝ)(∃x ∈ ℝ)(x < y)

mean the same thing? The answer is they do not since the first proposition is false, while the second proposition is true. Do you understand that?

To show how the order of the universal and existential quantifiers makes a difference in the meaning of a proposition, here's a simple example of a third‐grade class consisting of three boys and three girls, members of the sets

equation

and the two‐variable predicate (or proposition)

equation

where Figure 1.7 illustrates the relationships between the quantifiers ∀ ∀, ∃  ∀, ∀  ∃, ∃ ∃. The dot at the intersection of a boy and girl indicates the boy likes the girl. For example, Figure 1.7a means every boy likes every girl, while Figure 1.7c means Bob likes Ann and Betty, and Carl likes Carol.

Graphs of Carol, Betty, and Ann versus Abe, Bob, and Carl displaying nine (a), three (b), three (c), and one (d) solid circle marker indicating the likeness of a boy to a girl.

Figure 1.7 Universal and existential implications.

Figure 1.7 gives visual support for the implications

equation

which is stated explicitly in Figure 1.8.

No alt text required.

Figure 1.8g ∀ b ≡  ∀ b ∀ g ⇒  ∃ b ∀ g ⇒  ∀ g ∃ b ⇒  ∃ g ∃ b ≡  ∃ b ∃ g.

1.3.5 Negation of Quantified Propositions

In the next few sections, we will introduce strategies for proving theorems, and it will be necessary to know how quantified propositions are negated. The propositions in Table 1.31 show their negations in the language of predicated logic. The universe U, where the variables x and y are members might be any one of the common number systems ℕ, ℤ, ℚ, ℝ, ℂ or a subset of one line the intervals [0, 1], [0, ∞), and so on.

Table 1.31 Negation in predicate logic.

Proposition Negation of proposition
(∀x ∈ U)  P(x) (∃x ∈ U)  [∼P(x)]
(∃x ∈ U)  P(x) (∀x ∈ U) [∼P(x)]
(∀x ∈ U) (∃y ∈ U)  P(x, y) (∃x ∈ U) (∀y ∈ U)  [∼P(x, y)]
(∃x ∈ U) (∀y ∈ U)  P(x, y) (∀x ∈ U) (∃y ∈ U) [∼P(x, y)]
(∀x ∈ U)(∀y ∈ U)P(x, y) (∃x ∈ U)(∃y ∈ U)[∼P(x, y)]
(∃x ∈ U)(∃y ∈ U)P(x, y) (∀x ∈ U)(∀y ∈ U)[∼P(x, y)]

1.3.6 Conjunctions and Disjunctions in Predicate Logic

As an aid to understanding and involving conjunctions and disjunctions, Professor Snarf has conducted a survey among his students about their liking for peanuts and qumquats.3 If we let

  • P(s)= student s likes peanuts (p)
  • Q(s)= student s likes qumquats (q)

we can write the following propositions about students likings of peanuts and qumquats.

  1. (∀s)[P(s) ∧ Q(s)] means all students like p and q
  2. (∀s)P(s) ∧ (∀s)Q(s) means all students like p and all students like q
  3. (∃s)[P(s) ∧ Q(s)] means some student likes p and q
  4. (∃s)P(s) ∧ (∃s)Q(s) means some student likes p and some student likes q
  5. (∃s)[P(s) ∨ Q(s)] means some student like p or q
  6. (∃s)P(s) ∨ (∃s)Q(s) means some student likes p or some student likes q
  7. (∀s)P(s) ∨ (∀s)Q(s) means all students like p or all students like q
  8. (∀s)[P(s) ∨ Q(s)] means all students like p or q

There are several important relations between these propositions, including

equation

which means that if every student likes peanuts or every student likes qumquats, then it follows that every student likes peanuts or qumquats. But the converse does not follow since just because every student in the class likes either peanuts or qumquats that does not mean the class belongs to one of two distinct groups, peanut lovers or qumquat lovers.

Several important relationships between the previous propositions are as follows:

  1. (∀s)[P(s) ∧ Q(s)] ⇔ (∀s)P(s) ∧ (∀s)Q(s)
  2. (∃s)[P(s) ∧ Q(s)] ⇒ (∃s)P(s) ∧ (∃s)Q(s)
  3. (∀s)P(s) ∨ (∀s)Q(s) ⇒ (∀s)[P(s) ∨ Q(s)]
  4. (∃s)[P(s) ∨ Q(s)] ⇔ (∀s)P(s) ∨ (∀s)Q(s)

Problems

  1. Write the following quotes in the symbolic language of predicate logic.
    1. Learn from yesterday, live for today, hope for tomorrow. …Albert Einstein
    2. A woman can say more in a sigh than a man in a sermon.

      …Arnold Haultain

    3. “We all go a little mad sometimes.”

      …Norman Bates

    4. Cowards die many times before their deaths, the valiant never taste of death but once.

      …William Shakespeare

    5. All people are mortal.
    6. All that glitters is not gold.
  2. Translate to Predicate Logic

    Write the following sentences in the symbolic language of predicate logic. The universe of each variable is given in parentheses. For these problems, we use the notation

    equation
    1. If a|b and b|c, then a|c, where a, b, c are integers. (Integers)
    2. 4 does not divide n2 + 2 for any integer. (Integers)
    3. x3 + x + 1 = 0 for some real number x. (Real numbers)
    4. Everybody loves mathematics. (All people)
    5. For every positive real number a, there exists a real number x that satisfies ex = a. (Real numbers)
    6. For every positive real number ε > 0, there exists a real number δ > 0 such that |x − a| < δ ⇒ |f(x) − f(a)| < ε, where a, x are arbitrary real numbers.
    7. Everyone always attends class. (All students)
    8. The equation x2 + 1 = 0 has no solution. (Real numbers)
    9. The equation x2 − 2 = 0 has no solution. (Rational numbers)
  3. True or False

    Which of the following propositions are true in the given universe? The universe is given in parentheses.

    1. (∀x)(x ≤ x) (Real numbers)
    2. (∃x)(x2 = 2) (Real numbers)
    3. (∃x)(x2 = 2) (Rational numbers)
    4. (∃x)(x2 + x + 1 = 0) (Complex numbers)
    5. (∀x)[x ≡ 1 (mod5)] (Integers)
    6. (∃x)(ex = 1) (Real numbers)
    7. (∀x)(x ≤ x) (Integers)
  4. True or False

    Very quickly, true or false.

    1. ∼(∀x)(P(x)) ≡ (∃x)[∼P(x)]
    2. ∼(∃x)(P(x)) ≡ (∀x)[∼P(x)]
    3. ∼(∀x)[∼P(x)] ≡ (∃x)[P(x)]
    4. ∼(∃x)[∼P(x)] ≡ (∀x)[P(x)]
    5. (∀x)[P(x) ⇒ Q(x)] ≡  ∼ (∃x)[P(x) ∧  ∼ Q(x)]
    6. ∼(∃x)[P(x) ∧ Q(x)] ≡ (∀x)[P(x) ⇒  ∼ Q(x)]
  5. Expanding Universes

    In which of the universes ℕ, ℤ, ℚ, ℝ, ℂ are the following sentences true for x and y.

    1. (∀x)(∃y)(y = 1 − x)
    2. (∀x ≠ 0)(∃y)(y = 1/x)
    3. (∃x)(x2 − 2 = 0)
    4. (∃x)(x2 + 2 = 0)
  6. Not as Easy as It Looks

    Tell if the sentence

    equation

    is true or false in the following universe U.

    1. U = {4}
    2. U = {3}
    3. U = {6, 8, 10}
    4. U = {6, 8, 10, 12}
    5. U = {6, 7, 8, 10, 12}
  7. Small Universe

    Which statements are true in the universe U = {1, 2, 3}.

    1. 1 < 0 ⇒ (∃x)(x < 0)
    2. (∃x)(∀y)(x ≤ y)
    3. (∀x)(∃y)(x ≤ y)
    4. (∃x)(∃y)(y = x + 1)
    5. (∀x)(∀y)(xy = yx)
    6. (∀x)(∃y)(y ≤ x + 1)
  8. Well‐Known Universe

    Given the statements

    equation

    which of the following sentences are true in the universe of real numbers.

    1. (∀x)[I(x) ∨ R(x)]
    2. (∀x)[I(x) ∧ R(x)]
    3. (∀x)R(x) ∨ (∀x)I(x)
    4. (∀x)[R(x) ∨ I(x)] ⇒ [(∀x)R(x) ∨ (∀x)I(x)]
    5. [(∀x)R(x) ∨ (∀x)I(x)] ⇒ (∀x)[R(x) ∨ I(x)]
  9. Famous Theorems

    State the following famous theorems in the language of predicate logic.

    1. Intermediate Value Theorem

      Let f be a continuous function on the closed interval [a, b]. If f changes sign from negative to positive on [a, b], then there exists a number c between a and b, such that f(c) = 0.

    2. Fermat's Last Theorem

      If n is a natural number greater than 2, then there are no natural numbers a, b, and c that satisfy an + bn = cn.

    3. Euler's Theorem

      If P is any regular polyhedron and if v, e, f are the number of vertices, edges, and faces, respectively, then v − e + f = 2.

    4. Binomial Theorem

      If a, b are real numbers and n is a positive integer, then

      equation
  10. Negation

    Negate the following sentences in words.

    1. All women are moral.
    2. Every player on the team was over 6 feet tall.
    3. For any real number y, there exists a real number x that satisfies y = tan x.
    4. There exists a real number x that satisfies 0 < x < 5 and x3 − 8 = 0.
    5. The equation an + bn = cn does not have positive integer solutions a, b, c for n a natural number n > 2.
  11. Negation in Predicate Logic

    Negate the following sentences in symbolic form.

    1. (∀x)[P(x) ⇒ Q(x)]
    2. (∀x)[x > 0 ⇒ (∃y)(x2 = y)]
    3. (∀x)(∃y)(∀z)(xyz = 1)
    4. (∃x)(∃y)(∀z)(xy < z)
  12. Convergence and Nonconvergence

    A sequence images of real numbers converges to a limit L if and only if

    (∀ε > 0)(∃N ∈ ℕ)(∀n > N)(|xn − L| < ε)

    1. State the negation of this sentence.
    2. Using this negation show the sequence 1/2n, n = 1, 2, … does not converge to 1/4.
  13. Graph to the Rescue

    If P(x, y) : y ≤ x2 + 1, where (x, y) are points in the plane, determine which of the following is true. Hint: A picture (i.e. graph) is worth a thousand words.

    1. (∀x)(∀y)P(x, y)
    2. (∀x)(∃y)P(x, y)
    3. (∃x)(∀y)P(x, y)
    4. (∃x)(∃y)P(x, y)
    5. (∃y)(∀x)P(x, y)
    6. (∀y)(∃x)P(x, y)
  14. Order Counts

    Which of the following statements are true and which are false for real numbers x, y?

    1. (∀x)(∀y)(x < y)
    2. (∃x)(∀y)(x < y)
    3. (∀y)(∃x)(x < y)
    4. (∃x)(∃y)(x < y)
  15. Fun Time

    State the denial of words of wisdom attributed to Abraham Lincoln: “You can fool some of the people all the time and all the people some of the time, but you can't fool all the people all of the time.”

  16. In Plain English

    Restate the following sentences in plain English.

    1. (∀x ∈ ℝ)(∀y ∈ ℝ)[(x < y) ⇒ (∃z ∈ ℝ)[(x < z) ∧ (z < y)]]
    2. (∀x ∈ ℝ)[(x > 0) ⇒ (∃y ∈ ℝ)(x = y2)]
    3. (∀m, n ∈ ℕ)[(n > 1) ⇒ [m ∣ n ⇒ (m = 1) ∨ (m = n)]]
  17. True Here, False There

    Tell if the following sentences are true or false in each universe ℕ, ℤ, ℚ, ℝ.

    1. (∀x)(∃y)(x < y)
    2. (∀y)(∃x)(x < y)
    3. (∃x)(∀y)(x < y)
    4. (∃y)(∀x)(x < y)
    5. (∀x)[(x > 0) ⇒ (∃y)(y = x2)]
  18. Satisfiable in Predicate Logic

    A satisfiable sentence is a sentence that is true in at least some universe. For example, the sentence (∃x ∈ U)(x > 0) is satisfiable since it is true in the universe of real numbers. Tell if the following sentences are satisfiable, and if so, give a universe.

    1. (∃x ∈ U)[(x > 0) ∧ (x < 0)]
    2. (∃x ∈ U)(x2 =  − 3)
    3. (∃x ∈ U)[P(x) ∧  ∼ P(x)]
    4. (∃x ∈ U)[(x > 0) ∨ (x < 0)]
  19. Translation into Predicate Logic

    Letting

    equation

    translate the following sentence to predicate logic.

    1. Not every integer is even.
    2. Some integers are odd.
    3. Some integers are even, and some integers are odd.
    4. If an integer is even, then it is not odd.
    5. If an integer is even, then the integer two larger is even.
  20. Internet Research

    There is a wealth of information related to topics introduced in this section just waiting for curious minds. Try aiming your favorite search engine toward predicate logic, negation of logical statements, first‐order‐logic, and universal quantifier.

Notes

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.91.8.23