ICS 6B Sections 1.6-1.11

• 1.6: Predicates and quantifiers
• 1.7: Quantified statements
• 1.8: De Morgan’s law for quantified statements
• 1.9: Nested quantifiers
• 1.10: More nested quantified statements
• 1.11: Logical reasoning

1.6: Predicates and quantifiers

• Predicate: A statement whose truth value depends on one or more variables, even if the outcome is predetermined
  • Represented as a function; “P of x”
  • Ex: “x is an even number” would be true if x = 4, but not if x = 5
  • Domain: All of the possible values of x for a predicate
    • “x is an even number” would have a domain of all natural numbers
    • If not apparent from context, should be defined in the predicate
  • Predicates do not have to be strictly mathematical; general statements can be turned into predicates as well
• Universal quantifier: A way to turn a predicate into a proposition; denoted by ∀ which reads as “for all”
  • ∀x P(x) reads as “for every x, P(x)” and is a proposition that only returns true if every x in the domain is true
    • ∀x P(x) is a universally quantified statement

  • Proof showing that a universally quantified statement is true:

  • Counterexample: An element in the domain of a universally quantified statement that is false; used to prove that a statement is false
• Existensial equantifier: A way to turn a predicate into a proposition; denoted by ∃ which reads as “there exists”
  • ∃x P(x) reads as “there exists an x, such that P(x)” and is a proposition that returns true if any x in the domain is true
    • ∃x P(x) is an existentially quantified statement
  • Example: An element in the domain of a existentially quantified statement that is true; used to prove that a statement is true
  • Proof showing that an existentially quantified statement is false:

---

1.7: Quantified statements

• Can combine quantifiers and logical expressions to create quantified statements
  • Example: Let P(x) = x is prime and O(x) = x is odd; ∃x (P(x) ∧ ¬O(x)) states that there exists a positive number that is prime and not odd
• A free variable is defined as a variable that can be any value in the domain, while a bound variable is defined as a variable that is bound to a quantifier
  • x in P(x) is a free variable, while x in ∃x P(x) is a bound variable
  • A statement is a proposition if it contains no free variables
• Can express quantified statements in English
  • Let P(x) = x came to the party and S(x) = x was sick
  • ∃x (S(x) ∨ P(x)) is true because Joe satisfies the proposition: S(Joe) ∨ P(Joe) == True

Name	S(x)	P(x)
Joe	F	T
Theodore	T	F
Gertrude	F	T
Samuel	F	F

• If there are no values in the domain/set, then a universally quantified statement is vacuously true and a existentially quantified statement is false

---

1.8: De Morgan’s law for quantified statements

• ¬∀x F(x) can be rewritten as ∃x ¬F(x); AKA ¬∀x F(x) ≡ ∃x ¬F(x)
  • Ex: “Not every bird can fly” == “There exists a bird that cannot fly”
• Likewise, ¬∃x F(x) can be rewritten as ∀x ¬F(x); AKA ¬∃x F(x) ≡ ∀x ¬F(x)
  • Ex: “There does not exist a bird that can fly” == “Every bird cannot fly”
• When simplifying a quantifier, make sure to use a double negation on it
  • Example:

---

1.9: Nested quantifiers

• When there are multiple variables in a predicate, you must use multiple, nested quantifiers
  • Examples of nested quantifiers:
• Propositions with multiple variables can be thought of as pairs
  • Take ∀x ∀y M(x, y); this proposition is false if there is ANY pair of x, y that does not satisfy M(x, y) (including if x and y are the same)
  • For ∃x ∃y M(x, y), the proposition is false if ALL pairs of x, y are not true for M(x, y) (also including if x and y are the same)
• If a quantified statement has two quantifiers (one existential (∃) and one universal (∀)), it’s effective to think of the statement as a two player game
  • The existential player (variable) tries to make the expression true, while the universal player (variable) tries to make the expression false
  • The player (variable) on the left goes first, and the next player (variable) tries their best to succeed in their goal
  • Ex: In ∀x ∃y (x + y = 0), x goes first and chooses a random value; y tries its best to set x + y = 0 and is successful because it can always become -x
• DeMorgan’s can be applied to nested quantifiers as well; it switches the signs of the quantifier to its opposite

---

1.10: More nested quantified statements

• If you want to express ∀x ∀y without including situations where x == y, then you can write the proposition as ∀x ∀y ((x ≠ y) → M(x, y))
  • If x == y, then x, y cannot be used as a counter example because it’s not false
• To express uniqueness, you can use a combination of nested quantifiers and conditionals

• You can also move the quantifiers depending on where it is located in the statement

NOTE TO SELF: Challenge activity 1.10.1 is good practice

---

1.11: Logical reasoning

• Argument: A sequence of propsitions (AKA hypotheses) that is followed by a final proposition (AKA conclusion)
  • Valid arguments have true conclusions when all hypotheses are true; invalid otherwise
  • ∴ symbol denotes “therefore”

  • Commutative law allows hypotheses to be in any order

  • Ex: These two arguments are the same

  • Proving an arguments validity via truth table:

  • You can prove that an argument is invalid by showing an example where the hypotheses are true but the conclusion is not
• An argument’s form is found by replacing propositions with variables
  • Ex: “It is raining today. + If it is raining today, I will not ride my bike to school. ∴ I will not ride my bike to school.” can be replaced with “p + (p –> q) ∴ q”
  • Forms can be useful because it can invalidate an argument with known truth values
    • Ex:
• If an argument does not have an assignment where the hypotheses are true, then the argument is valid

NOTE TO SELF: Challenge activity 1.11.1 is good practice

Questions:

What is the difference between (x != y) -> and (x != y) ^? Is it because ^ is for existentials and -> is for universals?