Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
MATH1061 Discrete Mathematics
Page 1 of 15
This exam paper must not be removed from the venue
School of Mathematics & Physics
EXAMINATION
Exam Conditions:
This is a Central Examination
This is a Closed Book Examination - no materials permitted
During reading time - write only on the rough paper provided
This examination paper will be released to the Library
Materials Permitted In The Exam Venue:
(No electronic aids are permitted e.g. laptops, phones)
Calculators - Casio FX82 series or UQ approved (labelled)
Materials To Be Supplied To Students:
None
Instructions To Students:
Additional exam materials (eg. answer booklets, rough paper) will be
provided upon request.
Complete all examination questions in the space provided on this examination
paper. If more space is required, use the backs of pages. The final page is a
formula sheet, which you may detach. Nothing written on the formula sheet will
be marked.
Answer each question in the space provided on this examination paper, using the backs of pages if
more space is required. Each question is worth the number of marks indicated on the right.
1. For statement variables p, q and r, prove that
∼ ((p→ q) ∧ (p→ r)) ≡ p ∧ (∼ q ∨ ∼ r).
(4 marks)
Page 2 of 15
Semester One Final Examination, 2018 MATH1061 Discrete Mathematics
2. Consider the sequence defined recursively as
a1 = 2, a2 = 3, a3 = 4 and ak = ak−1 + ak−2 + ak−3 for all integers k ≥ 4.
Prove that an ≤ 2n for each integer n ≥ 1.
(6 marks)
Page 3 of 15
Semester One Final Examination, 2018 MATH1061 Discrete Mathematics
3. Indicate whether each of the following statements is true or false, by circling True or False as
appropriate. No explanation is required.
(5 marks)
(a) Z ∈ Q.
True False
(b) ∀ sets A, ∅ ∈ A.
True False
(c) If A = {∅} then |P(A)| = 2.
True False
(d) ∀ sets A and B, if |A| = |B| then every one-one function f : A→ B is an onto function.
True False
(e) If A = {a, b, c} and B = {d, e} then f = {(a, d), (b, d), (c, d)} is a function from A to B.
True False
(f) Let A be a non-empty set, and let ρ be a relation defined on P(A) where ∀X, Y ∈ P(A),
XρY if and only if X ∩ Y 6= ∅.
(i) ρ is reflexive.
True False
(ii) ρ is symmetric.
True False
(iii) ρ is transitive.
True False
(g) (Z+,×) is a group, where × represents multiplication.
True False
(h) Let A = {1, 2, 3, 4}. The set of all functions from A to A with the binary operation of
composition of functions is a group.
True False
Page 4 of 15
Semester One Final Examination, 2018 MATH1061 Discrete Mathematics
4. Prove the following statement. For all sets A and B, P(A) ⊆ P(B) if and only if A ⊆ B.
(5 marks)
Page 5 of 15
Semester One Final Examination, 2018 MATH1061 Discrete Mathematics
5. Prove that the set Z+ × Z+ × Z+ × Z+ is countable.
(7 marks)
Page 6 of 15
Semester One Final Examination, 2018 MATH1061 Discrete Mathematics
6. For each positive integer x, define d(x) to be the number of positive divisors of x. Let ρ be the
relation on Z+ defined as follows: ∀m,n ∈ Z+, (m,n) ∈ ρ if and only if d(m) ≤ d(n).
(a) Explain why (1, n) ∈ ρ for all n ∈ Z+.
(1 mark)
(b) Prove or disprove the following statement: the relation ρ is reflexive.
(2 marks)
(c) Prove or disprove the following statement: the relation ρ is symmetric.
(2 marks)
(d) Prove or disprove the following statement: the relation ρ is anti-symmetric.
(2 marks)
(e) Prove or disprove the following statement: the relation ρ is transitive.
(2 marks)
Page 7 of 15
Semester One Final Examination, 2018 MATH1061 Discrete Mathematics
7. (a) List the cyclic subgroups of (Z3 × Z3,+).
(5 marks)
(b) Explain why (Z3 × Z3,+) is not isomorphic to (Z9,+).
(2 marks)
Page 8 of 15
Semester One Final Examination, 2018 MATH1061 Discrete Mathematics
8. Solve the equation 12x + 15 = 11 in the field (Z53,+, ·). Hence determine the smallest positive
integer y such that 12y + 15 ≡ 11 (mod 53).
(Hint: 12× 31 = 7× 53 + 1.)
(3 marks)