CSC165H1: Problem Set 2

CSC165H1 Problem Set 2
CSC165H1: Problem Set 2

General instructions
Please read the following instructions carefully before starting the problem set. They contain important
information about general problem set expectations, problem set submission instructions, and reminders
of course policies.
• Your problem sets are graded on both correctness and clarity of communication. Solutions that are
technically correct but poorly written will not receive full marks. Please read over your solutions
carefully before submitting them.
• Each problem set may be completed in groups of up to three. If you are working in a group for this
problem set, please consult https://github.com/MarkUsProject/Markus/wiki/Student_Groups
for a brief explanation of how to create a group on MarkUs.
Exception: Problem Set 0 must be completed individually.
• Solutions must be typeset electronically, and submitted as a PDF with the correct filename. Handwritten submissions will receive a grade of ZERO.
The required filename for this problem set is problem set2.pdf.
• Problem sets must be submitted online through MarkUs. If you haven’t used MarkUs before, give
yourself plenty of time to figure it out, and ask for help if you need it! If you are working with a
partner, you must form a group on MarkUs, and make one submission per group. “I didn’t know
how to use MarkUs” is not a valid excuse for submitting late work.
• Your submitted file should not be larger than 9MB. This may happen if you are using a word
processing software like Microsoft Word; if it does, you should look into PDF compression tools to
make your PDF smaller, although please make sure that your PDF is still legible before submitting!
• Submissions must be made before the due date on MarkUs. You may use grace tokens to extend
the deadline; please see the Problem Set page for details on using grace tokens.
• The work you submit must be that of your group; you may not refer to or copy from the work of
other groups, or external sources like websites or textbooks. You may, however, refer to any text
from the Course Notes (or posted lecture notes), except when explicitly asked not to.
Additional instructions
• For each proof you present, start by writing a precise statement of what you are proving. Express it
using a fully simplified statement in predicate logic. For a disproof, clearly write the fully simplified
negation.
• For proofs involving the ceiling function, you may not use any external facts other than those
mentioned in the questions. You should not (and will not need to) prove any external facts to
complete this problem set.
• For any concrete numbers, you may state whether one divides another, or whether a number is
prime, without proof. For example, you can write statements “3 | 12” and “15 is not prime”
without justification.
Page 1/5
CSC165H1, Winter 2018 Problem Set 2
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, Winter 2018 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, Winter 2018 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, Winter 2018 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