Description

General instructions
• 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.
• 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.
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.
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 ⇒ n3 − 10n2 + 3 ≥ 165.
(b) [3 marks] Prove or disprove: ∀n ∈ N, n > 15 ∧ n3 − 10n2 + 3 ≥ 165.
2. [6 marks] Ceiling function.
∀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 .
(b) [3 marks] We define the function . 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, nextFifty(n) is the smallest multiple of 50 greater than or equal to n.
3. [6 marks] Divisibility.

(b) [2 marks] Disprove the following statement:
∀n ∈ N, 49 | n ⇔ 50 · (nextFifty(n) − n) = nextFifty(n)
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) = n2 + 1 and g(n) = 165n, (f + g)(n) = n2 + 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.