[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: 8n 2 N; n 15 ) n3
10n2 + 3 165.
(b) [3 marks] Prove or disprove: 8n 2 N; n 15 ^ n3
10n2 + 3 165.
[6 marks] Ceiling function.
Recall that the ceiling function is the function dxe : R ! Z de ned 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.
8x 2 R; 8k 2 Z; k x ) k dxe (Fact 1)
8x 2 R; 8k 2 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
n = n.
m
[3 marks] We de ne the function nextF ifty : N ! N as nextF ifty(n) = 50 50nm. Also, recall that for integers n and d, we say n is a multiple of d when d j n.
Prove that for all n 2 N, nextF ifty(n) is the smallest multiple of 50 greater than or equal to n.l
[6 marks] Divisibility.
This question is a continuation of Question 2: you may use the de nitions, given Facts 1 and 2, and statements in parts (2a) and (2b) in your proofs below.1
(a) [4 marks] Prove the following statement:
8n 2 N; n 2300 ) 49 j n , 50 (nextF ifty(n)
n) = nextF ifty(n)
(b) [2 marks] Disprove the following statement:
8n 2 N; 49 j n , 50 (nextF ifty(n) n) = nextF ifty(n)
[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.)
[2 marks] Express the statement \f is bounded" in predicate logic.
[4 marks] Let f; g : N ! R 0. We de ne the sum of functions as the function (f + g) : N ! R 0
as follows: for all n 2 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.
[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
