## Mock Exam

Please select one answer for each of the following questions. At the bottom of the page, you will be able to grade your answers, as well as see the correct response to each question. This mock exam is based on a previous exam that students were given three hours to complete.

1. Which of the following sentences is a proposition?
2. What is the negation of the proposition "The summer in Ottawa is sunny and warm."?
3. What is the negation of the proposition "If the exam is easy, then I am happy."?
4. What is the contrapositive of the implication "If the exam is easy, then I am relaxed and happy."?
5. Consider the proposition $((p \rightarrow q) \wedge (\neg r \rightarrow \neg q)) \rightarrow (\neg p \vee r)$. This proposition is a:
6. Consider the proposition $\neg((a \rightarrow \neg b) \rightarrow (b \rightarrow \neg a))$. This proposition is a:
7. Which of the following pairs of propositions are logically equivalent?
8. Which of the following pairs of propositions are logically equivalent?
9. Let $C(x,y)$ be a propositional function that depends on $x$ and $y$. What is the negation of $\forall x \exists y\;C(x,y)$?
10. Suppose the universe of discourse is the set of positive integers. Let $C(x,y)$ denote "$x \le y$". What is the negation of the proposition "There exists a number that is less than or equal to all numbers."?
11. Consider the following premises: If you do not buy food, then you do not eat. If you buy food, then you have money. If you have money, then you have a job. You do not have a job. What is a valid conclusion to infer from these premises?
12. Consider the following premises, where the universe of discourse is the set of all people: Everyone who enjoys french fries also enjoys burgers. Everyone who enjoys burgers is not a vegetarian. At least one student in this class enjoys french fries. What is a valid conclusion to infer from these premises?
13. Consider the following argument with premise $\forall x \; (P(x) \vee Q(x))$ and conclusion $(\forall x \; P(x)) \wedge (\forall x \; Q(x))$. \begin{array}{lll} 1. & \forall x \; (P(x) \vee Q(x)) & \therefore (\forall x \; P(x)) \wedge (\forall x \; Q(x)) \\\hline 2. & P(c) \vee Q(c) & \text{Universal Instantiation of 1} \\ 3. & P(c) & \text{Simplification of 2} \\ 4. & \forall x \; P(x) & \text{Universal Generalization of 3} \\ 5. & Q(c) & \text{Simplification of 2} \\ 6. & \forall x \; Q(x) & \text{Universal Generalization of 5} \\ 7. & (\forall x \; P(x)) \wedge (\forall x \; Q(x)) & \text{Conjunction of 4 and 6} \\ \end{array}
14. Let $A = \{a, c, 4, \{4,5\}, \{1, 4, 3, 3,2\}, d,e, \{3\}, \{4\}\}$. Which of the following statements is true?
15. Let $A = \{a, c, 4, \{4,5\}, \{1, 4, 3, 3,2\}, d,e, \{3\}, \{4\}\}$. Which of the following statements is true?
16. Let $A = \{x, y, 7, \{7,5\}, \{6, 7, 3, 3,2\}, u,v, \{3\}, \{7\}\}$. What is $|A|$ (i.e., the cardinality of $A$)?
17. Which set does the following Venn diagram represent?

18. Let $f$ be a function from the set of real numbers to the set of real numbers defined by $f(x) = -3x^2$.
19. Let $f$ be a function from the set of real numbers to the set of real numbers defined by $f(x) = -5x^3$.
20. Let $f$ be a function whose domain and codomain are the set $\{a,b,c,d,e,f,g\}$. Assume that $f(a)=g$, $f(b)=b$, $f(c)=a$, $f(d)=g$, $f(e)=f$, $f(f)=c$, and $f(g)=d$.
21. Which of the following sets is uncountable?
22. Evaluate the sum $\sum_{i=1}^{n}(i^2-\frac{1}{3}i+3)$.
23. Let $f(n) = 34n^4 - 71n^3 + 18n + 200$ and $g(n) = 18n^7 + 17n^5 - 879$. Which of the following is true?
24. Let $f(n) = 3n^2 - 5n + 1$. Which of the following values of $c$ and $k$ show that $f(n)$ is $\Omega(n^2)$?
25. Suppose you are trying to prove the statement $P(n)$ is true for every integer $n \ge 1$. You already know that $P(1)$ is true. How do you complete the proof?
26. Suppose you are trying to prove the statement "$n^3 + 2n$ is divisible by $3$ for every positive integer $n$" by induction. What value of $n$ should be used for the basis step?
27. Consider the following inductive step of a proof by induction of the statement "$n^3 + 2n$ is divisible by $3$ for every positive integer $n$" by induction.

Assume that $k^3 + 2k$ is divisible by $3$ for some $k \ge 1$. We want to show that $(k+1)^3 + 2(k+1)$ is divisible by $3$. We have that: \begin{array}{rcl} (k+1)^3 + 2(k+1) &=& k^3 + 3k^2 + 3k + 1 + 2k + 2\\ &=& (k^3 + 2k) + (3k^2 + 3k + 3) \end{array} $(k^3 + 2k)$ is divisible by $3$ because $\underline{\hspace{0.5in}(1)\hspace{0.5in}}$. $(3k^2 + 3k + 3)$ is divisible by $3$ because $\underline{\hspace{0.5in}(2)\hspace{0.5in}}$. Therefore, $(k+1)^3 + 2(k+1)$ is divisible by $3$.

28. Recall that $H_n$ is the $n$-th harmonic number: $H_n = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}$. Suppose we are trying to prove that $H_{2^n} \le 1 + n$ for all non-negative integers $n$ by induction. In the inductive step, we must show that $H_{2^{k+1}} \le 1 + (k+1)$. Which of the following is a reasonable first step in this part of the proof?
29. Let $A=\{a,b,c,d,e,f,g,h\}$ and $R = \{(a,a), (b,b), (c,d), (c,g), (d,g), (e,h), (f,f), (g,g) \}$ be a relation on $A$. Then $R$ is:
30. The matrix below defines an equivalence relation on the set $\{ a,b,c,d,1,2,3,4,x,y,z \}$. Each "$1$" indicates an element of the relation; for example, $(3,d)$ is in the relation, because the entry in row $3$ and column $d$ has a "$1$". Each "$0$" indicates an element that is not in the relation; for example, $(d,4)$ is not in the relation, because the entry in row $d$ and column $4$ has a "$0$". \begin{array}{c|ccccccccccc} & a & b & c & d & 1 & 2 & 3 & 4 & x & y & z \\ \hline a & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ b & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ c & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ d & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 3 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 4 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ x & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ y & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ z & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ \end{array} Which of the following sets is an equivalence class of this relation?
31. In the above Hasse diagram, which of the following statements is true?
32. In the above Hasse diagram, which of the following is the least element?
33. In the above Hasse diagram, which of the following is the greatest element?
34. In the above Hasse diagram, what are the upper bounds of $\{f,b\}$?
35. Which of the following total orders is compatible with the partial order represented by the above Hasse diagram?
36. How could the above graph be classified?
37. In the above graph, which of these vertices has degree $3$?
38. Suppose a depth-first search (DFS) is performed on the above graph starting at vertex $i$. Suppose further that first vertex reached after $i$ is $c$. How many tree edges will be incident to vertex $c$ once the algorithm has finished?
39. Suppose a breadth-first search (BFS) is performed on the above graph starting at vertex $f$. What is the depth (distance) of vertex $c$ with respect to the starting vertex $f$?
40. The above graph is planar.