CSE2500 Chapter 3: THE LOGIC OF QUANTIFIED STATEMENTS

Key Symbols and Their Meanings

Symbol

Meaning

Read As

Universal Quantifier

"For all," "For every," "For each," "For any"

Existential Quantifier

"There exists," "For some," "There is at least one"

P(x)

Predicate

Statement about variable x

Conditional

"If...then," "Implies"

Biconditional

"If and only if," "Necessary and sufficient"

Logical AND

"And"

Logical OR

"Or"

¬

Negation

"Not"

3.1 Predicates and Quantified Statements I

Predicates

  • A predicate is a statement containing variables

  • The truth set of a predicate is the set of all values that make the predicate true

  • Domain refers to the set of all possible values for the variables

Example: Finding Truth Sets

  • Given Q(n): "n is a factor of 8"

    • Truth set with domain of positive integers: {1, 2, 4, 8}

    • Truth set with domain of all integers: {1, 2, 4, 8, -1, -2, -4, -8}

Universal Quantifier (∀)

  • Indicates that a predicate is true for all elements in a domain

  • Example: ∀x ∈ H, x is mortal (read as "For every x in H, x is mortal")

  • A universal statement is true when the predicate is true for all elements

  • A universal statement is false if there exists at least one counterexample

Existential Quantifier (∃)

  • Indicates that a predicate is true for at least one element in a domain

  • Example: ∃p ∈ P such that p is a student in CSE2500

  • An existential statement is true if the predicate is true for at least one element

  • An existential statement is false if the predicate is false for all elements

Universal Conditional Statements

  • Form: ∀x, if P(x) then Q(x)

  • Most important form of statement in mathematics

  • Can be written informally in various ways:

    • "If a real number is greater than 2, then its square is greater than 4"

    • "All integers are rational numbers"

Equivalent Forms

  • ∀x ∈ U, if P(x) then Q(x) ≡ ∀x ∈ D, Q(x) where D is the subset of U where P(x) is true

  • ∀x ∈ D, Q(x) ≡ ∀x, if x is in D then Q(x)

3.2 Predicates and Quantified Statements II

Negating Quantified Statements

  • Negation of ∀: ¬(∀x, P(x)) ≡ ∃x, ¬P(x)

    • "It is not true that all X are Y" ≡ "There exists at least one X that is not Y"

  • Negation of ∃: ¬(∃x, P(x)) ≡ ∀x, ¬P(x)

    • "It is not true that there exists an X that is Y" ≡ "All X are not Y"

Negating Universal Conditional Statements

  • ¬(∀x, if P(x) then Q(x)) ≡ ∃x, P(x) ∧ ¬Q(x)

    • "Not all X with property P have property Q" ≡ "There exists an X with property P that doesn't have property Q"

Relation Among ∀, ∃, ∧, and ∨

  • Universal statements (∀) are related to AND (∧) statements

    • If domain is finite: ∀x ∈ {a,b,c}, Q(x) ≡ Q(a) ∧ Q(b) ∧ Q(c)

  • Existential statements (∃) are related to OR (∨) statements

    • If domain is finite: ∃x ∈ {a,b,c}, Q(x) ≡ Q(a) ∨ Q(b) ∨ Q(c)

Vacuous Truth

  • A universal statement is vacuously true if the domain is empty or if the condition P(x) is false for all x

  • Example: "All elephants in this room are pink" is vacuously true if there are no elephants in the room

Variants of Universal Conditional Statements

  • Contrapositive: ∀x, if ¬Q(x) then ¬P(x)

    • Logically equivalent to the original statement

  • Converse: ∀x, if Q(x) then P(x)

    • Not logically equivalent to the original statement

  • Inverse: ∀x, if ¬P(x) then ¬Q(x)

    • Not logically equivalent to the original statement

Necessary and Sufficient Conditions

  • P is a sufficient condition for Q means "if P then Q"

  • P is a necessary condition for Q means "if Q then P" (or "only if P, Q")

  • "Only if" indicates a necessary condition

    • "A product is 0 only if one of the factors is 0" means "If a product is 0, then one of the factors is 0"

3.3 Statements with Multiple Quantifiers

Order of Quantifiers Matters

  • ∀x ∃y P(x,y) ≠ ∃y ∀x P(x,y)

    • "For every x, there exists a y such that P(x,y)" means you can find a (possibly different) y for each x

    • "There exists a y such that for every x, P(x,y)" means there is one specific y that works for all x

Examples

  • "∀x ∃y (x loves y)" means "Everyone loves someone" (possibly different for each person)

  • "∃y ∀x (x loves y)" means "There is someone whom everyone loves" (same person)

Same Quantifiers

  • Order doesn't matter when quantifiers are the same type:

    • ∀x ∀y P(x,y) ≡ ∀y ∀x P(x,y)

    • ∃x ∃y P(x,y) ≡ ∃y ∃x P(x,y)

Negating Statements with Multiple Quantifiers

  • ¬(∀x ∃y P(x,y)) ≡ ∃x ∀y ¬P(x,y)

  • ¬(∃x ∀y P(x,y)) ≡ ∀x ∃y ¬P(x,y)

Formal Logical Notation

  • ∀x in D, P(x) can be written as ∀x (x in D → P(x))

  • ∃x in D such that P(x) can be written as ∃x (x in D ∧ P(x))

3.4 Arguments with Quantified Statements

Universal Instantiation

  • Form:

    • ∀x, P(x)

    • a is a particular element

    • Therefore, P(a)

  • Example: "All men are mortal. Socrates is a man. Therefore, Socrates is mortal."

Universal Modus Ponens

  • Form:

    • ∀x, if P(x) then Q(x)

    • P(a), for a particular a

    • Therefore, Q(a)

  • Combines universal instantiation with modus ponens

Universal Modus Tollens

  • Form:

    • ∀x, if P(x) then Q(x)

    • ¬Q(a), for a particular a

    • Therefore, ¬P(a)

  • Combines universal instantiation with modus tollens

  • Used in proof by contradiction

Testing Validity with Diagrams

  • Universal statements (∀x ∈ A, P(x)) can be represented by placing set A inside the set of things with property P

  • This helps visualize relationships in arguments to determine validity

Common Reasoning Errors

  • Converse Error: Assuming "if P then Q" means "if Q then P"

  • Inverse Error: Assuming "if P then Q" means "if not P then not Q"

  • These are invalid unless the original premise is a biconditional (if and only if)

Application Tips

  1. When finding truth values:

    • For universal statements (∀), check if the predicate is true for ALL elements in the domain

    • For existential statements (∃), check if the predicate is true for AT LEAST ONE element in the domain

  2. When negating statements:

    • ∀ becomes ∃ (and vice versa)

    • The predicate gets negated

    • For multiple quantifiers, negate from left to right, changing each quantifier type

  3. When analyzing arguments:

    • Use universal instantiation to apply universal statements to specific cases

    • Check the form of the argument (universal modus ponens or universal modus tollens)

    • Be careful of converse and inverse errors

  4. When translating between formal and informal language:

    • "All X are Y" = ∀x, if x is X then x is Y

    • "No X are Y" = ∀x, if x is X then x is not Y

    • "Some X are Y" = ∃x such that x is X and x is Y

    • "Some X are not Y" = ∃x such that x is X and x is not Y

Key Definitions to Remember

  • Predicate: A statement that contains variables

  • Truth Set: Set of values that make a predicate true

  • Domain: Set of all possible values for variables

  • Universal Quantifier (∀): Indicates truth for all elements

  • Existential Quantifier (∃): Indicates truth for at least one element

  • Vacuous Truth: A universal statement that is true because the condition is never satisfied

  • Sufficient Condition: If P is sufficient for Q, then P implies Q

  • Necessary Condition: If P is necessary for Q, then Q implies P

robot