Class 3 on jan 26: ch. 3.1-3.3

Claude prompt: make best summary of this discrete structures summary and lecture me - YOU HAVE TO THROUGHLY AND COMPACT FORMAT-LY AND EASILY PREPARE ME FOR THE QUIZ, THIS TOPIC IS INCLUDED. IT'S REALLY IMPORTANT and hard for me and I am really asking you to help me and deliver all information to me in a well structured, easy and compact way, chapter text:

exercise prompt: now do all the exercises by the end for me TO HELP ME PRACTICE FOR MY QUIZ, REALLY IMPORTANT, I NEED YOU TO SHOW ME HOW TO DO EVERYTHING DISCUSSED IN THIS CHAPTER in these exercises - make solutions easy to understand and very compact!!!. exercises:

PREDICATES AND QUANTIFIED STATEMENTS 3.1 - COMPLETE STUDY GUIDE

1. CORE CONCEPTS

What is a Predicate?

A predicate is a statement that contains variables. Its truth value depends on what values you substitute for those variables.

Example:

• P(x) = "x is a square"

• When x = a specific square → TRUE

• When x = a circle → FALSE

2. THE TWO MAIN QUANTIFIERS

A. UNIVERSAL QUANTIFIER (∀)

Meaning: "For ALL," "For EVERY," "For ANY," "For EACH"

Notation: ∀x , P(x) OR ∀x ∈ D , P(x)

Truth Condition: Statement is TRUE only if P(x) is true for EVERY element in the domain.

• ONE counterexample makes it FALSE.

Format 1: ∀x , if P(x) then Q(x)

Example: ∀x , if x is a square then x is a rectangle.
Means: Every square is a rectangle.

Format 2: ∀x (with restriction), Q(x)

Example: ∀ squares x , x is a rectangle.
Means: For all squares x, x is a rectangle.

B. EXISTENTIAL QUANTIFIER (∃)

Meaning: "There EXISTS," "There IS," "There IS SOME"

Notation: ∃x such that P(x) OR ∃x ∈ D such that P(x)

Truth Condition: Statement is TRUE if P(x) is true for AT LEAST ONE element in the domain.

• Need only ONE example to make it TRUE.

Format 1: ∃x such that P(x) ∧ Q(x)

Example: ∃n such that Prime(n) ∧ Even(n).
Means: There exists an integer that is both prime and even.
(Answer: n = 2)

Format 2: ∃ (with restriction) x such that Q(x)

Example: ∃ a prime number n such that Even(n).
Means: There exists a prime number n such that n is even.

3. QUICK COMPARISON TABLE

4. REWRITING STATEMENTS - KEY SKILL

Converting Between Forms

Universal Statement:

• Original: "All squares are rectangles"

• Form 1: ∀x , if x is a square then x is a rectangle

• Form 2: ∀ squares x , x is a rectangle

• Both mean the SAME thing

Existential Statement:

• Original: "There is an integer that is both prime and even"

• Form 1: ∃n such that Prime(n) ∧ Even(n)

• Form 2: ∃ a prime number n such that Even(n)

• Both mean the SAME thing

5. IMPLICIT QUANTIFICATION (HIDDEN QUANTIFIERS)

Sometimes quantifiers aren't written explicitly, but they're implied.

Rule 1: The Word "A" or "AN"

Indicator: Presence of indefinite article "a" or "an" usually signals universal quantification.

Statement: "If a number is an integer, then it is a rational number"
Actual meaning: ∀ integers x, x is a rational number

Rule 2: Context Determines Quantification

In mathematics, the context of the course/subject determines if the quantification is universal or existential.

Context: Algebra course where x always represents a real number
Statement: If x > 2 then x² > 4
Actual meaning: ∀ real numbers x , if x > 2 then x² > 4

Rule 3: Different Statements, Different Quantifications

a. (x + 1)² = x² + 2x + 1  
   → UNIVERSAL (true for all x)
   
b. Solve 3x - 4 = 5
   → EXISTENTIAL (find x value that works)

6. ADVANCED NOTATION: ⇒ and ⇔

These symbols indicate implicit universal quantification.

P(x) ⇒ Q(x)

Meaning: "P(x) implies Q(x)" for ALL x

Formal equivalent: ∀x , P(x) → Q(x)

What it means: Every element in the truth set of P(x) is in the truth set of Q(x)

Example: n is a factor of 4 ⇒ n is a factor of 8
Meaning: If n divides 4, then n divides 8
(Truth sets: {1,2,4} ⊆ {1,2,4,8})

P(x) ⇔ Q(x)

Meaning: "P(x) if and only if Q(x)" for ALL x

Formal equivalent: ∀x , P(x) ↔ Q(x)

What it means: P(x) and Q(x) have IDENTICAL truth sets

Example: n is a factor of 4 ⇔ (n < 5 AND n ≠ 3)
Meaning: These two conditions define the SAME set {1,2,4}

7. TRUTH SETS AND DOMAINS

Definition

Truth set of P(x): The set of all elements in the domain for which P(x) is true.

Example

Domain: Z⁺ (positive integers)

Notice: The last two have identical truth sets, so:

• n is a factor of 4 ⇔ n < 5 AND n ≠ 3

8. TARSKI'S WORLD (PRACTICAL APPLICATION)

What It Is

A computer program for learning logic using visual blocks on a grid.

Key Predicates Used

• Triangle(x): "x is a triangle"

• Blue(y): "y is blue"

• Square(z): "z is a square"

• RightOf(x, y): "x is to the right of y"

• Gray(x): "x is gray"

Example: Evaluating Statements

Statement a: ∀t , Triangle(t) → Blue(t)

• Translation: "All triangles are blue"

• How to evaluate: Check EVERY triangle. If ALL are blue → TRUE. If even ONE is not blue → FALSE.

Statement b: ∀x , Blue(x) → Triangle(x)

• Translation: "All blue objects are triangles"

• How to evaluate: Find one blue object that's NOT a triangle → FALSE (counterexample: a blue square)

Statement c: ∃y such that Square(y) ∧ RightOf(d, y)

• Translation: "There exists an object that is both square AND d is to its right"

• How to evaluate: Find at least ONE square with d to its right → TRUE. Can't find any → FALSE.

Statement d: ∃z such that Square(z) ∧ Gray(z)

• Translation: "There exists a square that is gray"

• How to evaluate: Find one gray square → TRUE. No gray squares exist → FALSE.

10. COMMON MISTAKES TO AVOID

❌ Mistake 1: Treating universal and existential statements as equivalent

• They're NOT. ∀x P(x) is much stronger than ∃x P(x)

❌ Mistake 2: Thinking one example proves a universal statement

• One example proves ∃x, but NOT ∀x

• Need to prove it for ALL

❌ Mistake 3: Missing implicit quantifiers

• Always look for "a," "an," or context clues

• They might be hidden!

❌ Mistake 4: Confusing → (implication) with ⇒ (implicit universal implication)

• p → q is one statement

• P(x) ⇒ Q(x) means ∀x, P(x) → Q(x)

❌ Mistake 5: Not identifying the domain

• The domain MATTERS for truth values

• Always clarify what x can be

13. PRACTICE PATTERNS

Type 1: Identify the Quantifier

Statement: "Some integers are prime"
Answer: ∃x such that Integer(x) ∧ Prime(x)
Quantifier: Existential (∃)

Type 2: Evaluate Truth Value

Domain: {1, 2, 3, 4}
Statement: ∀x, x > 0
Answer: TRUE (all numbers in domain are positive)

Type 3: Find Counterexamples

Statement: ∀x, if x² = 4 then x = 2
Counterexample: x = -2 (since (-2)² = 4 but -2 ≠ 2)
Answer: FALSE

Type 4: Rewrite in Different Forms

Original: "All dogs are animals"
Form 1: ∀x, if x is a dog then x is an animal
Form 2: ∀ dogs x, x is an animal

FINAL SUMMARY

Universal (∀): ALL elements satisfy condition → One counterexample = FALSE Existential (∃): At least ONE element satisfies condition → One example = TRUE

Implicit Quantifiers: Look for "a," "an," and context clues

⇒ and ⇔: These hide universal quantification—expand them mentally to ∀x

Truth Sets: Organize what makes each predicate true

Tarski's World: Apply logic visually—evaluate each statement carefully

EXERCISE SOLUTIONS 3.1

EXERCISE 2: Integer/Real Number Properties

EXERCISE 3: P(x) = "x > 1/x"

Part a: Evaluate specific values

Part b: Truth set if domain is R (all reals)

Analysis:

• Positive numbers > 1 always satisfy: x > 1/x (both sides positive)

• For 0 < x < 1: x < 1/x (doesn't satisfy)

• Negative numbers < -1 work: −8 > −0.125 ✓

• Negative numbers between -1 and 0 don't work

Truth Set: {x ∈ R : x > 1 OR x < −1} In interval notation: (−∞, −1) ∪ (1, ∞)

Part c: Truth set if domain is R⁺ (positive reals only)

For positive x: x > 1/x Multiply both sides by x (positive): x² > 1 Therefore: x > 1

Truth Set: {x ∈ R⁺ : x > 1} In interval notation: (1, ∞)

EXERCISE 4: Q(n) = "n² ≤ 30"

Part b: Truth set if domain is Z (all integers)

Find integers where n² ≤ 30:

• √30 ≈ 5.48

• So: −5 ≤ n ≤ 5

Truth Set: {−5, −4, −3, −2, −1, 0, 1, 2, 3, 4, 5}

Part c: Truth set if domain is Z⁺ (positive integers only)

• √30 ≈ 5.48

• So: 1 ≤ n ≤ 5

Truth Set: {1, 2, 3, 4, 5}

EXERCISE 6: R(m,n) = "If m is factor of n² then m is factor of n"

Part a: Why R(25, 10) is false

• n² = 100, m = 25

• Is 25 a factor of 100? → 100 ÷ 25 = 4 ✓ YES (hypothesis TRUE)

• Is 25 a factor of 10? → 10 ÷ 25 = 0.4 ✗ NO (conclusion FALSE)

• Implication FALSE → R(25, 10) is FALSE

Part b: Other counterexamples

• m = 4, n = 2: 4 is factor of 4 but not of 2

• m = 9, n = 3: 9 is factor of 9 but not of 3

• m = 100, n = 10: 100 is factor of 100 but not of 10

Part c: Why R(5, 10) is true

• n² = 100, m = 5

• Is 5 a factor of 100? → 100 ÷ 5 = 20 ✓ YES (hypothesis TRUE)

• Is 5 a factor of 10? → 10 ÷ 5 = 2 ✓ YES (conclusion TRUE)

• Implication TRUE → R(5, 10) is TRUE

EXERCISE 7: Find Truth Sets

a. "6/d is an integer" with domain Z

d must divide 6 evenly. Divisors of 6: ±1, ±2, ±3, ±6

Truth Set: {−6, −3, −2, −1, 1, 2, 3, 6}

c. "1 ≤ x² ≤ 4" with domain R

From 1 ≤ x²: x ≤ −1 or x ≥ 1 From x² ≤ 4: −2 ≤ x ≤ 2

Combining: (−2 ≤ x ≤ −1) or (1 ≤ x ≤ 2)

Truth Set: [−2, −1] ∪ [1, 2]

d. "1 ≤ x² ≤ 4" with domain Z

Integers where 1 ≤ x² ≤ 4:

• x² = 1: x = ±1 ✓

• x² = 2: x = ±√2 (not integer)

• x² = 3: x = ±√3 (not integer)

• x² = 4: x = ±2 ✓

Truth Set: {−2, −1, 1, 2}

EXERCISES 9-12: Find Counterexamples

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

Counterexample: x = 0.5

• 0.5 > 1/0.5?

• 0.5 > 2? ✗ FALSE

Statement is FALSE

10. ∀a ∈ Z, (a−1)/a is not an integer

Counterexample: a = 1

• (1−1)/1 = 0/1 = 0 (which IS an integer)

Statement is FALSE

11. ∀ positive integers m and n, m·n ≥ m+n

Counterexample: m = 1, n = 1

• 1·1 = 1

• 1+1 = 2

• Is 1 ≥ 2? ✗ NO

Statement is FALSE

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

Counterexample: x = 1, y = 1

• Left side: √(1+1) = √2 ≈ 1.414

• Right side: √1 + √1 = 1 + 1 = 2

• Is 1.414 = 2? ✗ NO

Statement is FALSE

EXERCISE 13: Equivalent Forms of "∀ basketball players x, x is tall"

Answer: a, e, f

EXERCISE 14: Equivalent Forms of "∃x ∈ R such that x² = 2"

Answer: b, c, e, f

EXERCISE 15: Rewrite Without Variables (2+ ways each)

a. ∀ rectangles x, x is a quadrilateral

Way 1: All rectangles are quadrilaterals. Way 2: Every rectangle has four sides. Way 3: If something is a rectangle, then it is a quadrilateral.

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

Way 1: There exists a set with 16 subsets. Way 2: Some set has 16 subsets. Way 3: A set can have exactly 16 subsets. (Note: A = {1,2,3,4} since 2⁴ = 16)

EXERCISE 16: Rewrite in Form "∀ x, ___"

a. All dinosaurs are extinct

∀ dinosaurs x, x is extinct.

b. Every real number is positive, negative, or zero

∀ real numbers x, x is positive OR x is negative OR x is zero.

c. No irrational numbers are integers

∀ irrational numbers x, x is not an integer. OR: ∀ x, if x is irrational then x is not an integer.

EXERCISE 17: Rewrite in Form "∃ x such that ___"

a. Some exercises have answers

∃ an exercise x such that x has an answer.

b. Some real numbers are rational

∃ a real number x such that x is rational.

EXERCISE 18: Student Predicates

Let D = all students, M(s) = "math major," C(s) = "CS student," E(s) = "engineering student"

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

∃ a student s such that E(s) ∧ M(s).

b. Every computer science student is an engineering student

∀ students s, C(s) → E(s).

c. No computer science students are engineering students

∀ students s, C(s) → ¬E(s). OR: ¬∃ a student s such that C(s) ∧ E(s).

d. Some computer science students are also math majors

∃ a student s such that C(s) ∧ M(s).

e. Some CS students are engineering students and some are not

∃ a student s such that C(s) ∧ E(s), AND ∃ a student t such that C(t) ∧ ¬E(t).

EXERCISE 21: Rewrite with Quantifier at End

a. For any graph G, the total degree of G is even

The total degree is even, for any graph G.

b. For any isosceles triangle T, the base angles of T are equal

The base angles are equal, for any isosceles triangle T.

c. There exists a prime number p such that p is even

There is a number that is prime and even. (or) A number exists that is both prime and even.

d. There exists a continuous function f such that f is not differentiable

There is a continuous function that is not differentiable.

EXERCISE 22: Rewrite in "∀ x, if ___ then ___" Form

a. All Java programs have at least 5 lines

∀ Java programs x, if x is a program then x has at least 5 lines. (Simplified: ∀ Java programs x, x has at least 5 lines.)

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

∀ arguments x, if x is valid AND x has true premises then x has a true conclusion.

EXERCISE 24: Rewrite in Both Existential Forms

a. Some hatters are mad

Form 1: ∃ x such that Hatter(x) ∧ Mad(x).

Form 2: ∃ a hatter x such that Mad(x). (or: ∃ a mad person x such that Hatter(x))

b. Some questions are easy

Form 1: ∃ x such that Question(x) ∧ Easy(x).

Form 2: ∃ a question x such that Easy(x). (or: ∃ an easy thing x such that Question(x))

EXERCISE 25: Rewrite in Both Forms (Universal)

a. The reciprocal of any nonzero fraction is a fraction

Form 1: ∀ nonzero fractions x, 1/x is a fraction.

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

b. The derivative of any polynomial function is a polynomial function

Form 1: ∀ polynomial functions f, f' is a polynomial function.

Form 2: ∀ f, if f is a polynomial function then f' is a polynomial function.

c. The sum of the angles of any triangle is 180°

Form 1: ∀ triangles T, the sum of angles of T is 180°.

Form 2: ∀ T, if T is a triangle then the sum of angles of T is 180°.

EXERCISE 26: Combined Universal and Existential

Original: "All integers are rational numbers but some rational numbers are not integers"

Part a: ∀...but ∃ form

∀ integers x, x is a rational number, BUT ∃ rational numbers x such that x is not an integer.

EXERCISES 28-30: Rewrite Without Quantifiers

28. Domain = objects in mathematics, Pos(x) = positive, Neg(x) = negative, Int(x) = integer, Real(x) = real

a. Pos(0)

Rewrite: "0 is a positive real number"

Answer: FALSE (0 is neither positive nor negative)

b. ∀x, Real(x) ∧ Neg(x) → Pos(−x)

Rewrite: "If x is a real number and x is negative, then −x is positive"

Answer: TRUE (if x < 0, then −x > 0)

c. ∀x, Int(x) → Real(x)

Rewrite: "Every integer is a real number"

Answer: TRUE (Z ⊂ R)

d. ∃x such that Real(x) ∧ ¬Int(x)

Rewrite: "There exists a real number that is not an integer"

Answer: TRUE (e.g., π, √2, 0.5 all work)

29. Domain = geometric figures, Square(x) = square, Rect(x) = rectangle

a. ∃x such that Rect(x) ∧ Square(x)

Rewrite: "There exists a figure that is both a rectangle and a square"

Answer: TRUE (every square is a rectangle)

b. ∃x such that Rect(x) ∧ ¬Square(x)

Rewrite: "There exists a rectangle that is not a square"

Answer: TRUE (non-square rectangles exist)

c. ∀x, Square(x) → Rect(x)

Rewrite: "All squares are rectangles"

Answer: TRUE (squares have 4 equal sides & right angles—meets rectangle definition)

30. Domain = integers Z, Odd(x) = odd, Prime(x) = prime, Square(x) = perfect square

a. ∃x such that Prime(x) ∧ ¬Odd(x)

Rewrite: "There exists a prime that is not odd" (i.e., an even prime)

Answer: TRUE (x = 2 is prime and even)

b. ∀x, Prime(x) → ¬Square(x)

Rewrite: "No prime number is a perfect square"

Answer: TRUE (if p is prime and p = n², then n must be ±1, making p = 1, but 1 isn't prime)

c. ∃x such that Odd(x) ∧ Square(x)

Rewrite: "There exists an odd perfect square"

Answer: TRUE (e.g., 9 = 3², 25 = 5², 49 = 7²)

EXERCISE 31: Find Implicit Universal Quantification

(This requires searching external texts—you'll need to find one yourself)

Template when you find an example:

Original: [Quote the statement exactly as it appears]

Explicit version: Make the universal quantifier clear with ∀

Source: Title, Author, Publisher, Year, Page #

SECTION 3.2: NEGATIONS, CONTRAPOSITIVES & LOGICAL EQUIVALENCES

NECESSARY & SUFFICIENT CONDITIONS

Definition Overview

Memory Aids

Sufficient: P is enough to guarantee Q

P is sufficient for Q  →  if P then Q
(P guarantees Q)

Necessary: P is required for Q (can't have Q without P)

P is necessary for Q  →  if Q then P
(need P to have Q)

Only If: Q is required for P (can't have P without Q)

P only if Q  →  if P then Q
(P happens only when Q is true)

7. EXAMPLES OF NECESSARY/SUFFICIENT

Example 1: Squares and Rectangles

"Squareness is a sufficient condition for rectangularity"

Rewrite: ∀x, if x is a square then x is a rectangle

Square → Rectangle
(being a square is ENOUGH to guarantee being a rectangle)

Example 2: Age and U.S. Presidency

"Being at least 35 years old is a necessary condition for being President"

Rewrite: ∀x, if x is President then x is at least 35 years old

President → At least 35 years old
(you MUST be 35 to be President)

OR by contrapositive (equivalent):

if x < 35 then x cannot be President
(if NOT 35+, then NOT President)

Example 3: "Only If"

"A product is 0 only if one of the numbers is 0"

Rewrite: ∀ numbers, if product = 0 then one number = 0

Product = 0  →  One number = 0

OR by contrapositive:

if both numbers ≠ 0 then product ≠ 0

EXERCISE SOLUTIONS 3.2

EXERCISE 25: Find Converses & Counterexamples

a. Original: If n is prime > 2, then n+1 is even

Converse: If n+1 is even, then n is prime and > 2

Counterexample: n = 3 gives n+1 = 4 (even), but need n > 2 and prime Actually, n = 4 gives 4+1 = 5 (odd) - bad example

Better Counterexample: n = 5 (even: 5+1 = 6, but 5 is NOT prime... wait 5 IS prime)

Let me think: we want n+1 even. That means n is odd. Take n = 9 (odd): 9+1 = 10 (even) ✓, but 9 is NOT prime ✓

Counterexample: n = 9

b. Original: If m is odd, then 2m is even

Converse: If 2m is even, then m is odd

Counterexample: m = 2 gives 2m = 4 (even), but m = 2 is NOT odd ✓

Counterexample: m = 2

c. Original: If two circles intersect in exactly 2 points, then they don't have a common center

Converse: If two circles don't have a common center, then they intersect in exactly 2 points

Counterexample: Two circles can NOT intersect at all (but don't share a center) ✓

Counterexample: Two non-intersecting circles with different centers

EXERCISES 26-33: Write Converse, Inverse, Contrapositive

Example: Exercise 16: ∀x ∈ R, if x² ≥ 1 then x > 0

Original: ∀x, if x² ≥ 1 then x > 0

Truth: FALSE (x = −2 gives 4 ≥ 1 but −2 ≯ 0)

Contrapositive: ∀x, if x ≤ 0 then x² < 1

Truth: FALSE (x = −2 gives −2 ≤ 0 but 4 ≱ 1)
Both false ✓ (same truth value as original)

Converse: ∀x, if x > 0 then x² ≥ 1

Truth: FALSE (x = 0.5 gives 0.5 > 0 but 0.25 ≱ 1)

Inverse: ∀x, if x² < 1 then x ≤ 0

Truth: FALSE (x = 0.5 gives 0.25 < 1 but 0.5 > 0)

EXERCISE 35: Universal Conditional NOT Equivalent to Inverse

Show: Original ≢ Inverse

Example: ∀x ∈ R, if x > 2 then x² > 4

Original: TRUE (if x > 2, definitely x² > 4)

Inverse: if x ≤ 2 then x² ≤ 4

Inverse is FALSE: x = −3 gives −3 ≤ 2 but 9 ≱ 4

Conclusion: TRUE ≠ FALSE, so they're NOT equivalent ✓

EXERCISE 36: Predicate with Different Domains (Challenging)

a. P(x) such that R is true, S and T are false

Need: ∀x ∈ Z, P(x) is TRUE but ∀x ∈ Q, P(x) is FALSE

Solution: P(x) = "x is an integer"

R: All integers are integers ✓ TRUE
S: All rationals are integers ✗ FALSE (e.g., 1/2)
T: All reals are integers ✗ FALSE

EXERCISES 39-42: Sufficient & Necessary to If-Then

Exercise 39: Earning C− is sufficient for counting toward graduation

Sufficient means: if C− then counts toward graduation

∀ grades, if grade is C− then it counts toward graduation

Exercise 40: Being divisible by 8 is sufficient for being divisible by 4

Rewrite: ∀ integers n, if n is divisible by 8 then n is divisible by 4

EXERCISES 43-46: Negate "Necessary" and "Sufficient" Statements

Exercise 43: Being divisible by 8 is NOT necessary for being divisible by 4

Original: If divisible by 4 then divisible by 8 (necessary form)

Negation of "necessary": ∃ an integer divisible by 4 that is NOT divisible by 8

Informal: Some numbers divisible by 4 are not divisible by 8
(Example: 4 = 4 · 1, divisible by 4 but not by 8)

Exercise 44: Large income is NOT necessary for happiness

Original necessary claim: If NOT rich then NOT happy (or: if happy then rich)

Negation: ∃ a person who is happy AND NOT rich

Informal: Some people are happy without large income

Exercise 45: Large income is NOT sufficient for happiness

Original sufficient claim: If rich then happy

Negation: ∃ a rich person who is NOT happy

Informal: Some rich people are not happy

Statement: "You may select among carriers only if they offer the same lowest fare"

Logical Form: selection is only if (same lowest fare)

Means: If you select → they have same lowest fare

Question: Does this guarantee freedom to choose if two carriers offer same lowest fare?

Answer: NO ✗

Why: "Only if" gives us: selection → same lowest fare

The CONVERSE would be: same lowest fare → selection (freedom to choose)

But converse is NOT logically equivalent!

The statement only promises that IF you select, the fares must match. It does NOT promise that matching fares lets you freely select.

SECTION 3.3: MULTIPLE QUANTIFIERS

2. READING MULTIPLE QUANTIFIERS (Left to Right!)

Rule: Always read from LEFT to RIGHT

∀x ∃y P(x,y)
├─ For ALL x...
   ├─ there EXISTS at least one y...
   └─ such that P(x,y) is true

Meaning: For every x, you can find some y that works

Compare These Two (They're Different!)

∀x ∃y P(x,y) = "For every x, there exists some y with P(x,y)"

Reading left-to-right:
- Pick ANY x
- Then find (possibly different) y that works
Each x might need a DIFFERENT y

∃y ∀x P(x,y) = "There exists some y such that for all x, P(x,y)"

Reading left-to-right:
- Find ONE y first
- Then that SAME y must work for ALL x
Much stronger statement!

Key Insight: Order MATTERS!

∀x ∃y ≠ ∃y ∀x
(Order changes the meaning!)

3. SIMPLE EXAMPLES TO INTERNALIZE

Example 1: ∀x ∃y, x < y

Meaning: For every number x, there exists a number y that is greater

Translation: Every number has a larger number
True? YES ✓ (e.g., if x=5, pick y=6)

Example 2: ∃y ∀x, x < y

Meaning: There exists a number y such that every number x is less than y

Translation: There's a maximum number
True? NO ✗ (impossible - always find larger number)

The Difference

∀x ∃y (x < y)   TRUE   ← for each x, find a y > x
∃y ∀x (x < y)   FALSE  ← find ONE y bigger than all x

4. NEGATION RULES (THE MECHANICAL PART)

Rule 1: Negate a Universal

∼(∀x P(x)) ≡ ∃x ∼P(x)

"NOT all have property P" = "Some DON'T have property P"

Rule 2: Negate an Existential

∼(∃x P(x)) ≡ ∀x ∼P(x)

"NOT some have property P" = "None have property P"

Rule 3: Negate an If-Then

∼(P → Q) ≡ P ∧ ∼Q

"NOT (if P then Q)" = "P AND NOT Q"

Rule 4: De Morgan's Laws

∼(P ∧ Q) ≡ ∼P ∨ ∼Q    (NOT and = OR not)
∼(P ∨ Q) ≡ ∼P ∧ ∼Q    (NOT or = AND not)

5. STEP-BY-STEP NEGATION PROCESS

The Mechanical Algorithm

Step 1: Write the statement in formal notation with parentheses

Step 2: Place ∼ in front

Step 3: Apply rules from outside IN (left to right)

Step 4: Keep applying until fully simplified

Example: Negate "∀x (Circle(x) → Above(x, f))"

Step 1: Original statement

∀x (Circle(x) → Above(x, f))

Step 2: Apply negation

∼(∀x (Circle(x) → Above(x, f)))

Step 3: Apply Rule 1 (negate ∀ → change to ∃)

∃x ∼(Circle(x) → Above(x, f))

Step 4: Apply Rule 3 (negate if-then → P ∧ ¬Q)

∃x (Circle(x) ∧ ∼Above(x, f))

DONE! This is fully negated

7. DETAILED EXAMPLES FROM THE TEXTBOOK

Example 3.3.10a: ∀x (Circle(x) → Above(x, f))

Statement: "For all circles x, x is above f"

Negation:

Step 1: ∼(∀x (Circle(x) → Above(x, f)))
Step 2: ∃x ∼(Circle(x) → Above(x, f))        [negate ∀]
Step 3: ∃x (Circle(x) ∧ ∼Above(x, f))        [negate →]

Final Negation: "There exists a circle that is not above f"

Example 3.3.10b: ∃x (Square(x) ∧ Black(x))

Statement: "There is a square x such that x is black"

Negation:

Step 1: ∼(∃x (Square(x) ∧ Black(x)))
Step 2: ∀x ∼(Square(x) ∧ Black(x))           [negate ∃]
Step 3: ∀x (¬Square(x) ∨ ¬Black(x))          [De Morgan]

Final Negation: "For all x, x is not square or x is not black" (Informal: "No object is both square and black")

Example 3.3.10c: ∀x (Circle(x) → ∃y (Square(y) ∧ SameColor(x,y)))

Statement: "For all circles x, there is a square y such that x and y have the same color"

Negation:

Step 1: ∼(∀x (Circle(x) → ∃y (Square(y) ∧ SameColor(x,y))))

Step 2: ∃x ∼(Circle(x) → ∃y (Square(y) ∧ SameColor(x,y)))
        [negate ∀]

Step 3: ∃x (Circle(x) ∧ ∼(∃y (Square(y) ∧ SameColor(x,y))))
        [negate →]

Step 4: ∃x (Circle(x) ∧ ∀y ∼(Square(y) ∧ SameColor(x,y)))
        [negate ∃]

Step 5: ∃x (Circle(x) ∧ ∀y (¬Square(y) ∨ ¬SameColor(x,y)))
        [De Morgan]

Final Negation: "There exists a circle x such that for all y, either y is not a square or x and y don't have the same color"

Example 3.3.10d: ∃x (Square(x) ∧ ∀y (Triangle(y) → RightOf(x,y)))

Statement: "There is a square x such that for all triangles y, x is to the right of y"

Negation:

Step 1: ∼(∃x (Square(x) ∧ ∀y (Triangle(y) → RightOf(x,y))))

Step 2: ∀x ∼(Square(x) ∧ ∀y (Triangle(y) → RightOf(x,y)))
        [negate ∃]

Step 3: ∀x (¬Square(x) ∨ ∼(∀y (Triangle(y) → RightOf(x,y))))
        [De Morgan on ∧]

Step 4: ∀x (¬Square(x) ∨ ∃y ∼(Triangle(y) → RightOf(x,y)))
        [negate ∀]

Step 5: ∀x (¬Square(x) ∨ ∃y (Triangle(y) ∧ ¬RightOf(x,y)))
        [negate →]

Final Negation: "For all x, either x is not a square or there exists a triangle y such that x is not to the right of y"

8. QUICK DECISION TREE FOR NEGATION

START: You have a statement to negate

├─ Does it start with ∀?
│  └─ Change to ∃ and negate the rest
│
├─ Does it start with ∃?
│  └─ Change to ∀ and negate the rest
│
├─ Does it have →?
│  └─ Change to (P ∧ ¬Q)
│
├─ Does it have ∧?
│  └─ Change to (¬P ∨ ¬Q)
│
├─ Does it have ∨?
│  └─ Change to (¬P ∧ ¬Q)
│
└─ Repeat until fully simplified

9. TARSKI'S WORLD APPLICATION

When working with Tarski world problems:

Given predicates:

• Triangle(x), Circle(x), Square(x) = shape

• Blue(x), Gray(x), Black(x) = color

• RightOf(x,y), Above(x,y) = position

• SameColorAs(x,y) = same color

Writing statements:

"All triangles are blue"
→ ∀x (Triangle(x) → Blue(x))

"Some circles are gray"
→ ∃x (Circle(x) ∧ Gray(x))

"Every triangle is above some square"
→ ∀x (Triangle(x) → ∃y (Square(y) ∧ Above(x,y)))

Negating statements: Use the mechanical steps from section 5

10. PROLOG BASICS (Optional but helpful)

What is Prolog?

A programming language based on first-order logic.

Simple Syntax

isabove(g, b₁)        means  "g is above b₁"
color(g, gray)        means  "g is colored gray"
?color(b₁, blue)      means  "Is b₁ blue?" → Answer: Yes
?isabove(X, w₁)       means  "What is above w₁?" → Answer: X = g, X = b₁

Inference Rule

isabove(X,Z) if isabove(X,Y) and isabove(Y,Z)
→ This is formal logic: ∀X,Y,Z [isabove(X,Y) ∧ isabove(Y,Z) → isabove(X,Z)]

11. COMMON MISTAKES & HOW TO AVOID THEM

❌ MISTAKE 1: Wrong order of quantifiers

WRONG: ∃x ∀y P(x,y) means something different than ∀x ∃y P(x,y)
RIGHT: The order is CRITICAL - write it exactly as given

❌ MISTAKE 2: Forgetting to negate nested quantifiers

WRONG: ∼(∀x ∃y P(x,y)) = ∃x ∃y ¬P(x,y)  ✗
RIGHT: ∼(∀x ∃y P(x,y)) = ∃x ∀y ¬P(x,y)  ✓
       (flip ∀ to ∃, then flip ∃ to ∀)

❌ MISTAKE 3: Not fully simplifying negations

WRONG: Stop at ∃x ¬(Square(x) ∧ Black(x))
RIGHT: Continue to ∃x (¬Square(x) ∨ ¬Black(x))  ✓
       (apply De Morgan's law)

❌ MISTAKE 4: Confusing → with ∧

WRONG: ∼(P → Q) = ∼P ∨ ∼Q  ✗
RIGHT: ∼(P → Q) = P ∧ ∼Q   ✓
       (this is different from De Morgan!)

❌ MISTAKE 5: Rushing through multiple negations

WRONG: Try to do it all at once
RIGHT: Apply rules ONE AT A TIME, step by step
       This mechanical approach prevents errors

12. MASTER TEMPLATE FOR ANY PROBLEM

To Write a Statement with Multiple Quantifiers:

Step 1: Identify all subjects and what varies

Example: "For every circle, there's a square with same color"
Subjects: circles (x), squares (y)

Step 2: Write the quantifiers left-to-right

∀x (Circle(x) → ∃y (Square(y) ∧ ...))

Step 3: Fill in the relationships

∀x (Circle(x) → ∃y (Square(y) ∧ SameColor(x,y)))

To Negate Any Statement:

Step 1: Write it with full parentheses

∼(∀x (Circle(x) → ∃y (Square(y) ∧ SameColor(x,y))))

Step 2: Apply rules mechanically, left to right

∃x ∼(Circle(x) → ∃y (Square(y) ∧ SameColor(x,y)))
∃x (Circle(x) ∧ ∀y ∼(Square(y) ∧ SameColor(x,y)))
∃x (Circle(x) ∧ ∀y (¬Square(y) ∨ ¬SameColor(x,y)))

Step 3: Done! Don't stop early.

13. SYMBOL SUMMARY

14. TRUTH VALUE QUICK REFERENCE

For Statements with ∀ then ∃:

∀x ∃y P(x,y)
└─ TRUE if: for every x, you can find (possibly different) y making P true
└─ FALSE if: there exists at least one x for which NO y makes P true

For Statements with ∃ then ∀:

∃x ∀y P(x,y)
└─ TRUE if: there's one x that works with ALL y values
└─ FALSE if: every x fails for at least one y

15. PRACTICE PATTERNS

Pattern A: All have property

All triangles are blue
→ ∀x (Triangle(x) → Blue(x))
Negation: ∃x (Triangle(x) ∧ ¬Blue(x))

Pattern B: Some have property

Some circles are gray
→ ∃x (Circle(x) ∧ Gray(x))
Negation: ∀x (¬Circle(x) ∨ ¬Gray(x))

Pattern C: For all X, there exists Y

Every circle has a square with same color
→ ∀x (Circle(x) → ∃y (Square(y) ∧ SameColor(x,y)))
Negation: ∃x (Circle(x) ∧ ∀y (¬Square(y) ∨ ¬SameColor(x,y)))

Pattern D: There exists X such that for all Y

Some square is right of all triangles
→ ∃x (Square(x) ∧ ∀y (Triangle(y) → RightOf(x,y)))
Negation: ∀x (¬Square(x) ∨ ∃y (Triangle(y) ∧ ¬RightOf(x,y)))

17. KEY FORMULAS TO MEMORIZE

∼(∀x P(x)) = ∃x ¬P(x)
∼(∃x P(x)) = ∀x ¬P(x)
∼(P → Q) = P ∧ ¬Q
∼(P ∧ Q) = ¬P ∨ ¬Q
∼(P ∨ Q) = ¬P ∧ ¬Q
∼(∼P) = P

SUPER QUICK REFERENCE:

When you see ∼ in front of quantified statement:

∼∀ → change to ∃ and keep simplifying
∼∃ → change to ∀ and keep simplifying
∼→ → becomes (P ∧ ¬Q)
∼∧ → becomes (¬P ∨ ¬Q)  [De Morgan]
∼∨ → becomes (¬P ∧ ¬Q)  [De Morgan]

That's literally all you need. Repeat until done.