Description
1. [6 marks] AND vs. IMPLIES. Students often confuse the meanings of the two propositional operators
⇒ and ∧. In this question, you’ll examine each of these in a series of statements by writing formal
proofs/disproofs of each one.
(a) [3 marks] Prove or disprove: ∀n ∈ N, n > 15 ⇒ n
3 − 10n
2 + 3 ≥ 165.
(b) [3 marks] Prove or disprove: ∀n ∈ N, n > 15 ∧ n
3 − 10n
2 + 3 ≥ 165.
Page 2/5
CSC165H1, Problem Set 2
2. [6 marks] Ceiling function.
Recall that the ceiling function is the function dxe : R → Z defined as dxe is the smallest integer greater
than or equal to x. You may use the following two facts about ceilings in your proofs below, as long as
you clearly state where you are using them.
∀x ∈ R, ∀k ∈ Z, k ≥ x ⇒ k ≥ dxe (Fact 1)
∀x ∈ R, ∀k ∈ Z, dx + ke = dxe + k (Fact 2)
(a) [3 marks] Prove that for all natural numbers n and m, if n < m then
m − 1
m
· n
= n.
(b) [3 marks] We define the function nextF if ty : N → N as nextF if ty(n) = 50 ·
l n
50
m
. Also, recall
that for integers n and d, we say n is a multiple of d when d | n.
Prove that for all n ∈ N, nextF if ty(n) is the smallest multiple of 50 greater than or equal to n.
Page 3/5
CSC165H1, Problem Set 2
3. [6 marks] Divisibility.
This question is a continuation of Question 2: you may use the definitions, given Facts 1 and 2, and
statements in parts (2a) and (2b) in your proofs below.1
(a) [4 marks] Prove the following statement:
∀n ∈ N, n ≤ 2300 ⇒
49 | n ⇔ 50 · (nextF if ty(n) − n) = nextF if ty(n)
(b) [2 marks] Disprove the following statement:
∀n ∈ N, 49 | n ⇔ 50 · (nextF if ty(n) − n) = nextF if ty(n)
1You may use (2a) and (2b) for full marks here even if you didn’t prove them in the previous question.
Page 4/5
CSC165H1, Problem Set 2
4. [9 marks] Functions.
Let f : N → R
≥0
. We say f is bounded if there exists a real number k such that f never outputs a value
greater than k. (Recall that R
≥0 denotes the set of real numbers greater than or equal to zero.)
(a) [2 marks] Express the statement “f is bounded” in predicate logic.
(b) [4 marks] Let f, g : N → R
≥0
. We define the sum of functions as the function (f + g) : N → R
≥0
as follows: for all n ∈ N, (f + g)(n) = f(n) + g(n). For example, if f(n) = n
2 + 1 and g(n) = 165n,
(f + g)(n) = n
2 + 1 + 165n.
Prove that for all functions f1, f2 : N → R
≥0
, if f1 and f2 are bounded, then f1 + f2 is bounded.
(c) [3 marks] Prove or disprove: for all functions f1, f2 : N → R
≥0
, if f1 + f2 is bounded, then f1 is
bounded and f2 is bounded.
Page 5/5
