Mathematical Statements and Proofs Lecture 2 (Handout)

MOE Advanced Level Higher 3 (H3) Math Mathematical Proofs and Reasoning Lecture 2 1 / 37

Telegram Chat https://t.me/+My2fLlPuAUxlYjY1 2 / 37

Conent 1 Contrapositive 2 Proof by Contradiction 3 Properties of Rational Numbers 4 Primes and Properties 3 / 37

Truth Table Given some (Mathematical) statements, we may form a truth table to list the truth value of some combinations of the statements depending on the truth value of the original statements. Example Modus Ponen: P ⇒ Q P Q P ⇒ Q T T T T F F F T T F F T Question. Why is P ⇒ Q true whenever P is false? This is known as vacuously true . 4 / 37

Negation Definition Let P be a (mathematical) statement. The negation of P , read as not P , denoted as ¬P , is true when P is false, and false when P is true. P ¬P T F F T Example P : n is an odd integer. ¬P : n is not an odd integer. In this case, ¬P is equivalent to n is an even number. Exercise. ¬(¬P ) ≡ P . 5 / 37

Negation of Universal Statement Recall that universal statements are statements with the quantifier “for all”, “for any”. In standard form it is written as for all x in D, P (x), or in the syntax is ∀x ∈ D, P(x). The negation of a universal statement is an existential statement, ¬(∀x ∈ D, P(x)) ⇔ ∃ x ∈ D, ¬P (x) Example ∀x ∈ D, P(x): Everyone in class gets a chocolate. ∃x ∈ D, ¬P (x): Someone in class did not get a chocolate. 6 / 37

Example Is the following statement true? For all integer n ≥ 1, n2 + 1 is a prime number. P (n): n2 + 1 is prime. D: integers ≥ 1. The statement is ∀n ∈ D, P(n). For n = 1, 12 + 1 = 2is prime. For n = 2, 22 + 1 = 5is prime. For n = 3, 32 + 1 = 10is not a prime. The statement is false, since ¬(∀n ∈ D, P(n)) = ∃n ∈ D, ¬P (n), n = 3 is a counter-example . 7 / 37

Negation of Existential Statements The negation of an existential statement is a universal statement. ¬(∃x ∈ D, P(x)) ⇔ ∀ x ∈ D, ¬P (x). Example ∃x ∈ D, P(x): Some students in the class likes durian. ∀x ∈ D ¬P (x) Every student in the class does not like durian. Equivalent to: No student in class likes durian. 8 / 37

Modus Tollen or Contrapositive Theorem If x2 is an even integer, then x is an even integer. Proof. Let x2 = 2m for some integer m. ... cannot x = √ 2m ... required conclusion is x = 2n for some integer n. 9 / 37

Modus Tollen or Contrapositive Let P and Q be (mathematical) statements. Consider the statement ¬Q ⇒ ¬P . P Q ¬P ¬Q P ⇒ Q ¬Q ⇒ ¬P T T F F T T T F F T F F F T T F T T F F T T T T Observe that the truth values for P ⇒ Q are equal to those for ¬Q ⇒ ¬P . That is, P ⇒ Q is logically equivalent to ¬Q ⇒ ¬P ; denoted as (P ⇒ Q) ≡ (¬Q ⇒ ¬P ). Example P ⇒ Q: If you do well in your exam, then you will get a sweet. ¬Q ⇒ ¬P : If you got did not get a sweet, then you did not do well in your exam. 10 / 37