Scribd
Upload
17 views2 pages

Proof Techniques in Discrete Mathematics

The document outlines tutorial exercises for a Discrete Mathematics course focusing on various methods of proof, including direct proof, proof by contraposition, proof by cases, proof by contradiction, and mathematical induction. It presents specific questions requiring proofs for statements about integers and real numbers, as well as identifying errors in logical arguments. The exercises aim to enhance understanding of fundamental proof techniques in mathematics.

Uploaded by

holyshitjk48
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
17 views2 pages

Proof Techniques in Discrete Mathematics

The document outlines tutorial exercises for a Discrete Mathematics course focusing on various methods of proof, including direct proof, proof by contraposition, proof by cases, proof by contradiction, and mathematical induction. It presents specific questions requiring proofs for statements about integers and real numbers, as well as identifying errors in logical arguments. The exercises aim to enhance understanding of fundamental proof techniques in mathematics.

Uploaded by

holyshitjk48
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

COMP S264F Discrete Mathematics

Unit 2 : Methods of Proof


Tutorial Exercises

Question 1 (Direct proof). Prove the following statements.

(a) The product of any two consecutive integers is even.

(b) For any integer x, x2 + 2x + 1 is even if and only if x is odd.

Question 2 (Proof by contraposition). Prove the following statements.

(a) If a product of two positive real numbers is greater than 100, then at least one of the numbers is greater
than 10.

(b) For all integers m, n, if m + n is even, then m and n are both even or both odd.

Question 3 (Non-proof). Identify the error or errors in the following arguments that supposedly shows that
if ∀x (P (x) ∨ Q(x)) is true, then ∀x P (x) ∨ ∀x Q(x) is true.

1. ∀x (P (x) ∨ Q(x))

2. P (c) ∨ Q(c) for any element c in the domain

3. P (c), from step 2

4. ∀x P (x)

5. Q(c), from step 2

6. ∀x Q(x)

7. ∀x P (x) ∨ ∀x Q(x), from steps 4 and 6

Question 4 (Proof by cases). Prove that for all integers n, n2 − n + 3 is odd.

Question 5 (Proof by cases). Let x and y be some integers. Prove or disprove the following.

(a) (x is odd) ↔ (x2 + 6x + 9 is even)

(b) (xy is odd) ↔ (x and y are both odd)

Question 6 (Proof by contradiction). Prove the following statements.

(a) If a, b are integers, then a2 − 4b − 2 ̸= 0.

(b) Suppose a, b are real numbers. If a is rational and ab is irrational, then b is irrational.

Question 7 (Mathematical induction). Prove the following statements.

(a) For any positive integer n, 3n + 1 is divisible by 2.

(b) For any positive integer n, 1 + 3 + 5 + . . . + (2n − 1) = n2 .

You might also like