School of Computing and Mathematical Sciences MATH111 - Calculus and Algebra I Worksheet 1: Mathematical Logic and Methods of Proof
Dr J. Yves Semegni
1. Propositions
- Definition: A proposition is a statement that is either true or false but not both.
- Examples and Truth Values:
- (a) The earth is a planet. Truth Value: True
- (b) 2 + 4 = 7. Truth Value: False
- (c) Please go home. Truth Value: Not a proposition (not a statement)
- (d) What a day! Truth Value: Not a proposition (not a statement)
- (e) Find the value of x for which (x − 3)³ = 0. Truth Value: Not a proposition (not a statement)
- (f) For each real number x, sin x + cos x = 1. Truth Value: False
- (g) All lawyers are dishonest. Truth Value: False
2. Converse, Contrapositive and Inverse
Converse, Contrapositive, and Inverse Definitions:
- Converse (of a statement "If p, then q"): "If q, then p"
- Contrapositive: "If not q, then not p"
- Inverse: "If not p, then not q"
Examples:
- (a) Statement: If Bronwyne lives in Cape Town, then she lives in South Africa.
- Converse: If she lives in South Africa, then Bronwyne lives in Cape Town.
- Contrapositive: If she does not live in South Africa, then she does not live in Cape Town.
- Inverse: If Bronwyne does not live in Cape Town, then she does not live in South Africa.
- (b) Statement: If it is morning, then the sun is in the east.
- Converse: If the sun is in the east, then it is morning.
- Contrapositive: If the sun is not in the east, then it is not morning.
- Inverse: If it is not morning, then the sun is not in the east.
- (c) Statement: If Mary understands logic, then Mary is clever.
- Converse: If Mary is clever, then she understands logic.
- Contrapositive: If Mary is not clever, then she does not understand logic.
- Inverse: If Mary does not understand logic, then she is not clever.
- (d) Statement: If John is lazy, then John will fail.
- Converse: If John will fail, then he is lazy.
- Contrapositive: If John does not fail, then he is not lazy.
- Inverse: If John is not lazy, then he will not fail.
- (e) Statement: If x > 0, then x² > 0.
- Converse: If x² > 0, then x > 0.
- Contrapositive: If x² ≤ 0, then x ≤ 0.
- Inverse: If x ≤ 0, then x² ≤ 0.
- (f) Statement: If xy = 0, then x = 0 or y = 0.
- Converse: If x = 0 or y = 0, then xy = 0.
- Contrapositive: If x ≠ 0 and y ≠ 0, then xy ≠ 0.
- Inverse: If xy ≠ 0, then x ≠ 0 and y ≠ 0.
- (g) Statement: If xy = 1, then x = 1 or y = 1.
- Converse: If x = 1 or y = 1, then xy = 1.
- Contrapositive: If xy ≠ 1, then x ≠ 1 and y ≠ 1.
- Inverse: If xy ≠ 1, then x ≠ 1 or y ≠ 1.
- (h) Statement: If x > 0, then x³ > 0.
- Converse: If x³ > 0, then x > 0.
- Contrapositive: If x ≤ 0, then x³ ≤ 0.
- Inverse: If x ≤ 0, then x³ ≤ 0.
3. Negations
Negation Definition: The negation of a statement p is the assertion that p is false, denoted as ¬p.
Negations of Statements:
- (a) If Mary understands logic, then Mary is clever.
- Negation: Mary understands logic and Mary is not clever.
- (b) Either Mary is clever or John is lazy.
- Negation: Mary is not clever and John is not lazy.
- (c) Mary is clever and John is lazy.
- Negation: Mary is not clever or John is not lazy.
- (d) If x > 0, then x² > 0.
- Negation: x > 0 and x² ≤ 0.
- (e) If xy = 0, then x = 0 or y = 0.
- Negation: xy = 0 and x ≠ 0 and y ≠ 0.
- (f) If xy = 1, then x = 1 or y = 1.
- Negation: xy = 1 and x ≠ 1 and y ≠ 1.
- (g) If x > 0, then x³ > 0.
- Negation: x > 0 and x³ ≤ 0.
- (h) A function f has an inverse if f is both one-to-one and onto.
- Negation: f is one-to-one or f is not onto.
- (i) √2 is a rational number.
- Negation: √2 is not a rational number.
- (j) Every real number has a multiplicative inverse.
- Negation: There exists a real number that does not have a multiplicative inverse.
- (k) There exists a real number x such that x² = 4.
- Negation: For every real number x, x² ≠ 4.
4. Logical Equivalences
Logical Equivalence Definition: Two statements are logically equivalent if they have the same truth values in all possible scenarios.
Examples of Logical Equivalences:
- (a) Prove that ¬(p ⇒ q) ≡ p ∧ ¬q using a truth table.
- (b) Prove that ¬(p ∧ q) ≡ ¬p ∨ ¬q using a truth table.
- (c) Prove that ¬(p ∨ q) ≡ ¬p ∧ ¬q using a truth table.
- (d) Prove that p ∧ (q ∧ r) ≡ (p ∧ q) ∧ r using a truth table.
- (e) Prove that p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) using a truth table.
- (f) Prove that p ⇒ q ≡ ¬q ⇒ ¬p using a truth table.
- (g) Prove that p ⇔ q ≡ (p ⇒ q) ∧ (q ⇒ p) using a truth table.
5. Tautology or Contradiction
Definition of Tautology and Contradiction:
- Tautology: A statement that is always true regardless of the truth values of its components.
- Contradiction: A statement that is always false.
Determine the nature of the following statements using truth tables:
- (a) p ∧ ¬p
- (b) p ∨ ¬p
- (c) ¬(p ⇒ q) ⇔ (p ⇒ ¬q)
- (d) (p ⇒ q) ⇔ (¬q ⇒ ¬p)
- (e) ¬p ∧ (p ⇒ q)
- (f) (p ∧ ¬q) ∨ (¬p ∨ q)
- (g) (q ∧ r) ∧ (¬p ∧ q) ∧ ¬q
- (h) (p ∧ ¬q) ∧ (¬p ∨ q)
6. Direct Proofs
Definition of Direct Proof: A method of proving a statement where one begins with the assumption of the hypothesis and proceeds logically to arrive at the conclusion.
Examples of Direct Proofs:
- (a) The sum of two even numbers is even.
- (b) If n is an even integer, then n² is also even.
- (c) If n is an even integer, then n² + 3 is odd.
- (d) If x and y are consecutive integers, then x + y is odd.
- (e) If n is an odd integer, then n² is also odd.
- (f) Let a and b be real numbers. If a and b are rational, then a + b is also rational.
7. Indirect Proofs (Contrapositive)
Definition of Indirect Proof: A proof that shows that the contrapositive of the statement is true, which then implies that the original statement is true.
Examples of Indirect Proofs:
- (a) Let a and b be integers. If ab is even, then at least one of a or b is even.
- (b) Let a and b be integers. If a + b is even, then a and b are either both even or both odd.
- (c) If 5 does not divide n², then 5 does not divide n.
- (d) If the sum a + b is not odd, then a and b are not consecutive integers.
8. Proof by Contradiction or Counterexample
Definition of Proof by Contradiction: A proof that assumes the opposite of what needs to be proven, leading to a contradiction.
Examples:
- (a) √2 is irrational.
- (b) For all x, x² = 4.
- (c) If n is even and m is odd, then (m + n)² is odd.
- (d) There is no greatest integer.
- (e) There is no smallest positive rational number.
9. Proof by Mathematical Induction
Definition of Mathematical Induction: A method of proving statements about natural numbers by establishing a base case and demonstrating that if the statement holds for an arbitrary case, it holds for the next case.
Examples:
- (a) For all integers n ≥ 1, 1 + 2 + 3 + + n = rac{n(n + 1)}{2}.
- (b) For all integers n ≥ 1, 1^2 + 2^2 + 3^2 + + n^2 = rac{n(n + 1)(2n + 1)}{6}.
- (c) For all integers n ≥ 1, 1^3 + 2^3 + 3^3 + + n^3 = igg( rac{n(n + 1)}{2}igg)^2.
- (d) For all integers n ≥ 1, 2 + 4 + 6 + + 2n = n(n + 1).
- (e) For all integers n ≥ 1, 1 + 4 + 7 + 10 + + (3n - 2) = rac{n(3n - 1)}{2}.
- (f) For all integers n ≥ 1, 1 + 2^2 + 2^3 + + 2^{n - 1} = 2^n - 1.
- (g) For all integers n ≥ 1, 1 + 3 + 32 + + 3^{n - 1} = rac{3^n - 1}{2}.
- (h) For all integers n, is divisible by 5.
- (i) For any natural integer n ≥ 5, n^2 < 2n.