📚 The Logic of Quantified Statements: A Comprehensive Study Guide

Source Information: This study material is compiled from a lecture audio transcript, "Test Yourself" questions, and "Exercise Set 3.1" from a textbook chapter titled "The Logic of Quantified Statements."

---

🎯 Introduction to Predicates and Quantifiers

Welcome to this in-depth study guide on the logic of quantified statements. This material will provide a solid understanding of foundational concepts in logic, including predicates, truth sets, and the crucial roles of universal (∀) and existential (∃) quantifiers. We will explore how to evaluate their truth conditions, express them formally, and apply them through detailed examples and exercises. This session draws directly from the principles outlined in Chapter 3 of "The Logic of Quantified Statements."

---

1️⃣ Understanding Predicates and Quantifiers

1.1 📚 Predicates and Truth Sets

A predicate is a statement that contains one or more variables and becomes a proposition (true or false) once the variables are replaced by specific values from their domain.

• Definition: If P(x) is a predicate with a specific domain D, the truth set of P(x) is denoted as {x ∈ D | P(x)}.
• Reading Aloud: This notation is read as "the set of all x in D such that P(x) is true."
• Purpose: The truth set comprises all elements within the domain D for which the predicate P(x) holds true.

1.2 📚 Quantifiers

Quantifiers are symbols used to specify the quantity of elements in the domain that satisfy a predicate. There are two primary types:

1.2.1 Universal Quantifier (∀)

• Symbol: ∀
• Meaning: Indicates that a statement holds true for every single element within a specified domain.
• Common Expressions: "for all," "for every," "for any," "for each," "for arbitrary," "given any."

1.2.2 Existential Quantifier (∃)

• Symbol: ∃
• Meaning: Indicates that a statement holds true for at least one element within a given domain.
• Common Expressions: "there exists," "there exist," "there exists at least one," "for some," "for at least one," "we can find a."

---

2️⃣ Evaluating Truth Conditions for Quantified Statements

Understanding when a quantified statement is true or false is fundamental.

2.1 Universal Statements (∀x ∈ D, Q(x))

• Truth Condition: A statement of the form "∀x ∈ D, Q(x)" is true if, and only if, Q(x) is true for every single x in D.
• Falsity Condition: If even one element in D makes Q(x) false, then the entire universal statement is false. This single element is called a counterexample.

2.2 Existential Statements (∃x ∈ D such that Q(x))

• Truth Condition: A statement of the form "∃x ∈ D such that Q(x)" is true if, and only if, Q(x) is true for at least one x in D.
• Falsity Condition: If Q(x) is false for all x in D, then the existential statement is false.

---

3️⃣ Rewriting and Formalizing Quantified Statements

A crucial skill in logic is the ability to translate between informal language and formal logical expressions using quantifiers and variables.

• Informal to Formal:
  • "All dinosaurs are extinct" ➡️ "∀x, if x is a dinosaur, then x is extinct."
  • "Some exercises have answers" ➡️ "∃x such that x is an exercise and x has an answer."
• Equivalent Expressions:
  • "∀ basketball players x, x is tall" is equivalent to "Every basketball player is tall" or "Anyone who is a basketball player is a tall person."
• Combining Predicates:
  • "There is an engineering student who is a math major."
    • Let D = set of all students.
    • M(s) = "s is a math major."
    • E(s) = "s is an engineering student."
    • Formalization: "∃s ∈ D such that E(s) ∧ M(s)."

---

4️⃣ Test Yourself: Solutions and Explanations

Here are the answers to the "Test Yourself" questions, with detailed explanations to reinforce your understanding.

1. If P(x) is a predicate with domain D, the truth set of P(x) is denoted {x ∈ D | P(x)}. We read these symbols out loud as "the set of all x in D such that P(x)."

   • 💡 Explanation: This notation precisely defines the collection of all elements within the specified domain D for which the predicate P(x) evaluates to true. It's a fundamental concept for working with quantified statements.

2. Some ways to express the symbol ∀ in words are: for all, for every, for any, for each, for arbitrary, given any.

   • 💡 Explanation: These phrases all convey the idea of universality – that the statement applies without exception to every member of the domain.

3. Some ways to express the symbol ∃ in words are: there exists, there exist, there exists at least one, for some, for at least one, we can find a.

   • 💡 Explanation: These phrases all convey the idea of existence – that at least one member of the domain satisfies the condition, but not necessarily all.

4. A statement of the form ∀x ∈ D, Q(x) is true if, and only if, Q(x) is true for every x in D.

   • 💡 Explanation: This reiterates the strict condition for a universal statement to be true. A single counterexample makes it false.

5. A statement of the form ∃x ∈ D such that Q(x) is true if, and only if, Q(x) is true for at least one x in D.

   • 💡 Explanation: This highlights that only one instance of the predicate being true is sufficient to make an existential statement true.

---

5️⃣ Exercise Set 3.1: Detailed Solutions and Explanations

This section provides comprehensive solutions and explanations for selected exercises, focusing on applying the concepts of predicates, quantifiers, truth sets, and truth conditions.

5.1 Analyzing Statements about a Menagerie (Exercise 1)

Menagerie Contents: 7 brown dogs, 2 black dogs, 6 gray cats, 10 black cats, 5 blue birds, 6 yellow birds, 1 black bird.

Determine which statements are true and which are false:

• a. There is an animal in the menagerie that is red.
  • ✅ False. The list of animals does not include any red animals.
• b. Every animal in the menagerie is a bird or a mammal.
  • ✅ False. Cats are neither birds nor mammals (they are mammals, but the statement implies all animals are either birds or mammals, which is not true for cats). More accurately, dogs are mammals, birds are birds. Cats are mammals. So, all animals are mammals or birds. Let's re-evaluate. Dogs (mammals), Cats (mammals), Birds (birds). So, every animal is either a mammal or a bird. This statement is True. My initial thought was incorrect. All animals listed are either mammals (dogs, cats) or birds.
• c. Every animal in the menagerie is brown or gray or black.
  • ✅ False. There are 5 blue birds and 6 yellow birds. These are neither brown, gray, nor black.
• d. There is an animal in the menagerie that is neither a cat nor a dog.
  • ✅ True. Birds are neither cats nor dogs (e.g., a blue bird).
• e. No animal in the menagerie is blue.
  • ✅ False. There are 5 blue birds.
• f. There are in the menagerie a dog, a cat, and a bird that all have the same color.
  • ✅ True.
    • Dogs: brown, black
    • Cats: gray, black
    • Birds: blue, yellow, black
    • We can find a black dog, a black cat, and a black bird. All three exist and share the color black.

5.2 Truth of Mathematical Statements (Exercise 2)

Indicate which statements are true and which are false. Justify your answers.

• a. Every integer is a real number.
  • ✅ True. The set of integers (Z) is a subset of the set of real numbers (R). Every integer can be represented on the real number line.
• b. 0 is a positive real number.
  • ✅ False. Positive real numbers are strictly greater than 0. Zero is neither positive nor negative.
• c. For all real numbers r, −r is a negative real number.
  • ✅ False. Consider r = 0. Then -r = 0, which is not a negative real number. Also, if r is negative (e.g., r = -5), then -r = 5, which is positive.
• d. Every real number is an integer.
  • ✅ False. Consider the real number 0.5 or √2. These are real numbers but not integers.

5.3 Predicate: x > 1/x (Exercise 3)

Let P(x) be the predicate "x > 1/x."

• a. Write P(2), P(1/2), P(−1), P(−1/2), and P(−8), and indicate which are true/false.

  • P(2): 2 > 1/2 (True) ✅
  • P(1/2): 1/2 > 1/(1/2) ➡️ 1/2 > 2 (False) ❌
  • P(−1): −1 > 1/(−1) ➡️ −1 > −1 (False) ❌
  • P(−1/2): −1/2 > 1/(−1/2) ➡️ −1/2 > −2 (True) ✅
  • P(−8): −8 > 1/(−8) ➡️ −8 > −0.125 (False) ❌

• b. Find the truth set of P(x) if the domain of x is R (real numbers).

  • We need x > 1/x.
  • Case 1: x > 0. Multiply by x: x² > 1. This implies x > 1 (since x is positive).
  • Case 2: x < 0. Multiply by x (and reverse inequality): x² < 1. This implies -1 < x < 0.
  • ✅ Truth Set: {x ∈ R | x > 1 or -1 < x < 0}

• c. If the domain is the set R+ of all positive real numbers, what is the truth set of P(x)?

  • Since the domain is R+ (x > 0), we only consider Case 1 from part (b).
  • ✅ Truth Set: {x ∈ R+ | x > 1}

5.4 Predicate: n² ≤ 30 (Exercise 4)

Let Q(n) be the predicate "n² ≤ 30."

• a. Write Q(2), Q(−2), Q(7), and Q(−7), and indicate which are true/false.

  • Q(2): 2² ≤ 30 ➡️ 4 ≤ 30 (True) ✅
  • Q(−2): (−2)² ≤ 30 ➡️ 4 ≤ 30 (True) ✅
  • Q(7): 7² ≤ 30 ➡️ 49 ≤ 30 (False) ❌
  • Q(−7): (−7)² ≤ 30 ➡️ 49 ≤ 30 (False) ❌

• b. Find the truth set of Q(n) if the domain of n is Z (integers).

  • We need integers n such that n² ≤ 30.
  • Possible integer values for n² are 0, 1, 4, 9, 16, 25.
  • The corresponding n values are:
    • n² = 0 ➡️ n = 0
    • n² = 1 ➡️ n = ±1
    • n² = 4 ➡️ n = ±2
    • n² = 9 ➡️ n = ±3
    • n² = 16 ➡️ n = ±4
    • n² = 25 ➡️ n = ±5
  • ✅ Truth Set: {−5, −4, −3, −2, −1, 0, 1, 2, 3, 4, 5}

• c. If the domain is the set Z+ of all positive integers, what is the truth set of Q(n)?

  • We only consider positive integers from the truth set in part (b).
  • ✅ Truth Set: {1, 2, 3, 4, 5}

5.5 Predicate: If x < y then x² < y² (Exercise 5)

Let Q(x, y) be the predicate "If x < y then x² < y²" with domain for both x and y being R (real numbers).

• a. Explain why Q(x, y) is false if x = −2 and y = 1.

  • We check the premise: x < y ➡️ −2 < 1 (True).
  • We check the conclusion: x² < y² ➡️ (−2)² < 1² ➡️ 4 < 1 (False).
  • ✅ Explanation: Since the premise is true and the conclusion is false, the implication "True → False" is false. This is a classic counterexample for this predicate.

• b. Give values different from those in part (a) for which Q(x, y) is false.

  • We need x < y to be true, but x² < y² to be false. This typically happens when x is negative and its absolute value is larger than y.
  • ✅ Example: Let x = −5 and y = 2.
    • Premise: −5 < 2 (True).
    • Conclusion: (−5)² < 2² ➡️ 25 < 4 (False).
    • Thus, Q(−5, 2) is false.

• c. Explain why Q(x, y) is true if x = 3 and y = 8.

  • We check the premise: x < y ➡️ 3 < 8 (True).
  • We check the conclusion: x² < y² ➡️ 3² < 8² ➡️ 9 < 64 (True).
  • ✅ Explanation: Since both the premise and the conclusion are true, the implication "True → True" is true.

• d. Give values different from those in part (c) for which Q(x, y) is true.

  • We can have "True → True" or "False → True" or "False → False".
  • Case 1: True → True (x and y positive, x < y)
    • ✅ Example: Let x = 1 and y = 5.
      • Premise: 1 < 5 (True).
      • Conclusion: 1² < 5² ➡️ 1 < 25 (True).
      • Thus, Q(1, 5) is true.
  • Case 2: False → (True or False) (x ≥ y)
    • ✅ Example: Let x = 5 and y = 2.
      • Premise: 5 < 2 (False).
      • Since the premise is false, the implication is automatically true, regardless of the conclusion.
      • Thus, Q(5, 2) is true.

5.6 Predicate: If m is a factor of n² then m is a factor of n (Exercise 6)

Let R(m, n) be the predicate "If m is a factor of n² then m is a factor of n," with domain for both m and n being Z (integers).

• a. Explain why R(m, n) is false if m = 25 and n = 10.

  • Check premise: Is m a factor of n²?
    • n² = 10² = 100. Is 25 a factor of 100? Yes, 100 = 25 * 4 (True).
  • Check conclusion: Is m a factor of n?
    • Is 25 a factor of 10? No (False).
  • ✅ Explanation: The premise is true, but the conclusion is false. Therefore, the implication "True → False" is false.

• b. Give values different from those in part (a) for which R(m, n) is false.

  • We need m to be a factor of n² but not a factor of n. This often happens when m has prime factors that appear with higher powers in m than in n.
  • ✅ Example: Let m = 9 and n = 6.
    • Premise: Is 9 a factor of 6² = 36? Yes, 36 = 9 * 4 (True).
    • Conclusion: Is 9 a factor of 6? No (False).
    • Thus, R(9, 6) is false.

• c. Explain why R(m, n) is true if m = 5 and n = 10.

  • Check premise: Is m a factor of n²?
    • n² = 10² = 100. Is 5 a factor of 100? Yes, 100 = 5 * 20 (True).
  • Check conclusion: Is m a factor of n?
    • Is 5 a factor of 10? Yes, 10 = 5 * 2 (True).
  • ✅ Explanation: Both the premise and the conclusion are true. Therefore, the implication "True → True" is true.

• d. Give values different from those in part (c) for which R(m, n) is true.

  • We can have "True → True" or "False → (True or False)".
  • Case 1: True → True
    • ✅ Example: Let m = 2 and n = 4.
      • Premise: Is 2 a factor of 4² = 16? Yes (True).
      • Conclusion: Is 2 a factor of 4? Yes (True).
      • Thus, R(2, 4) is true.
  • Case 2: False → (True or False)
    • ✅ Example: Let m = 7 and n = 10.
      • Premise: Is 7 a factor of 10² = 100? No (False).
      • Since the premise is false, the implication is automatically true.
      • Thus, R(7, 10) is true.

5.7 Finding Truth Sets (Exercise 7)

Find the truth set of each predicate.

• a. predicate: 6/d is an integer, domain: Z

  • We need integers d such that 6/d is an integer. This means d must be a divisor of 6.
  • ✅ Truth Set: {−6, −3, −2, −1, 1, 2, 3, 6}

• c. predicate: 1 ≤ x² ≤ 4, domain: R

  • We need real numbers x such that 1 ≤ x² and x² ≤ 4.
  • 1 ≤ x² ➡️ |x| ≥ 1 ➡️ x ≤ −1 or x ≥ 1.
  • x² ≤ 4 ➡️ |x| ≤ 2 ➡️ −2 ≤ x ≤ 2.
  • Combining these conditions: x must be in [−2, −1] or [1, 2].
  • ✅ Truth Set: {x ∈ R | −2 ≤ x ≤ −1 or 1 ≤ x ≤ 2}

5.8 Finding Counterexamples (Exercise 9 & 12)

Find counterexamples to show that the statements are false.

• 9. ∀x ∈ R, x > 1/x.

  • This statement claims that all real numbers x are greater than their reciprocal.
  • We need to find an x for which x ≤ 1/x.
  • ✅ Counterexample: Let x = 0.5. Then 0.5 > 1/0.5 ➡️ 0.5 > 2, which is false.
  • Other counterexamples: x = -2 (then -2 > -0.5 is false), x = 1 (then 1 > 1 is false).

• 12. ∀real numbers x and y, √x + y = √x + √y.

  • This statement claims that the square root of a sum is always the sum of the square roots.
  • We need to find x, y such that √(x + y) ≠ √x + √y.
  • ✅ Counterexample: Let x = 1 and y = 1.
    • √(1 + 1) = √2.
    • √1 + √1 = 1 + 1 = 2.
    • Since √2 ≠ 2, the statement is false.
  • (Note: For √x and √y to be real, x and y must be non-negative.)

5.9 Equivalent Ways of Expressing Statements (Exercise 13)

Consider the statement: ∀basketball players x, x is tall. Which of the following are equivalent ways of expressing this statement?

• a. Every basketball player is tall. ✅ (Direct rephrasing)
• b. Among all the basketball players, some are tall. ❌ (This is an existential statement, not universal)
• c. Some of all the tall people are basketball players. ❌ (Changes the subject and quantifier)
• d. Anyone who is tall is a basketball player. ❌ (This is "∀x, if x is tall then x is a basketball player," which is the converse)
• e. All people who are basketball players are tall. ✅ (Direct rephrasing)
• f. Anyone who is a basketball player is a tall person. ✅ (Direct rephrasing)

5.10 Rewriting Statements Informally (Exercise 15)

Rewrite the following statements informally in at least two different ways without using variables or quantifiers.

• a. ∀rectangles x, x is a quadrilateral.

  • ✅ Informal 1: All rectangles are quadrilaterals.
  • ✅ Informal 2: Every rectangle has four sides.

• b. ∃ a set A such that A has 16 subsets.

  • ✅ Informal 1: There is a set that has exactly 16 subsets.
  • ✅ Informal 2: Some set can be found with 16 subsets.

5.11 Rewriting Statements in Formal Forms (Exercise 16)

Rewrite each of the following statements in the form "∀ x, ______."

• a. All dinosaurs are extinct.

  • ✅ Formal: ∀x, if x is a dinosaur, then x is extinct.

• c. No irrational numbers are integers.

  • ✅ Formal: ∀x, if x is an irrational number, then x is not an integer. (Or: ∀x, x is not an irrational number or x is not an integer.)

• e. The number 2,147,581,953 is not equal to the square of any integer.

  • ✅ Formal: ∀n ∈ Z, 2,147,581,953 ≠ n².

5.12 Expressing Statements with Predicates and Quantifiers (Exercise 18)

Let D be the set of all students at your school, M(s) be "s is a math major," C(s) be "s is a computer science student," and E(s) be "s is an engineering student."

• a. There is an engineering student who is a math major.

  • ✅ Formal: ∃s ∈ D such that E(s) ∧ M(s).

• b. Every computer science student is an engineering student.

  • ✅ Formal: ∀s ∈ D, if C(s) then E(s).

• c. No computer science students are engineering students.

  • ✅ Formal: ∀s ∈ D, if C(s) then ∼E(s). (Or: ∼∃s ∈ D such that C(s) ∧ E(s).)

5.13 Rewriting Statements in "∀x, if __ then __" Form (Exercise 22)

Rewrite each of the following statements in the form "∀ x, if ______ then ______."

• a. All Java programs have at least 5 lines.

  • ✅ Formal: ∀x, if x is a Java program, then x has at least 5 lines.

• b. Any valid argument with true premises has a true conclusion.

  • ✅ Formal: ∀x, if x is a valid argument with true premises, then x has a true conclusion.

5.14 Rewriting Statements in Two Forms (Exercise 25)

Rewrite each of the following statements in the two forms "∀ x, ______" and "∀x, if ______, then ______" (or similar for two variables).

• a. The reciprocal of any nonzero fraction is a fraction.

  • ✅ Form 1: ∀x, if x is a nonzero fraction, then 1/x is a fraction.
  • ✅ Form 2: ∀nonzero fractions x, 1/x is a fraction.

• e. The sum of any two even integers is even.

  • ✅ Form 1: ∀x, y ∈ Z, if x is even and y is even, then x + y is even.
  • ✅ Form 2: ∀even integers x and y, x + y is even.

---

6️⃣ Conclusion

This study guide has provided a structured overview of predicates and quantified statements, covering their definitions, truth conditions, and methods for formalization. By working through the detailed explanations and exercise solutions, you should now have a solid foundation in:

• ✅ Defining predicates and truth sets.
• ✅ Understanding and using universal (∀) and existential (∃) quantifiers.
• ✅ Evaluating the truth or falsity of quantified statements.
• ✅ Identifying counterexamples for universal statements.
• ✅ Translating between informal language and formal logical expressions.

Mastering these concepts is crucial for further studies in logic, mathematics, and computer science, enabling precise and rigorous reasoning.