Exam information
Course code and name Semester
Exam date and time
Exam duration
Copyright By PowCoder代写 加微信 powcoder
Reading time Exam window
Permitted materials
MATH7861 Discrete Mathematics Semester 2, 2020
Online, non-invigilated
Please refer to your personalised timetable
Working time: 120 minutes + additional online allowance: 30 minutes. TOTAL exam duration: 2 hrs 30 minutes from the advertised exam commencement time
Reading time has not been formally allocated for online exams, however students are encouraged to review and plan their approach for the exam before they start. The total exam time should be sufficient to do this.
You must commence your exam at the time listed in your personalised timetable. The exam will remain open only for the duration of the exam.
This is an open book exam – all materials permitted. Any calculator is permitted.
Additional time
30 minutes additional time has been incorporated in recognition of the online environment and the different circumstances that students face in their home environments. This includes time for download and upload, and allowances for network or connection issues.
This exam is weighted at either 50% or 70% of your total mark for this course, whichever gives you the highest overall grade.
There are 80 marks available in total on this exam.
Instructions
Answer all questions.
You can print the exam and write in the exam paper, or write your answers on blank paper (clearly label your solutions so that it is clear which problems they are solutions to), or annotate an electronic file on a suitable device.
You must submit your answers as a single electronic file in PDF format through Blackboard before the end of the allowed time.
You should include your name and student number on the first page of the file that you submit.
Who to contact
If you have any concerns or queries about a particular question, or need to make any assumptions to answer the question, state these at the start of your solution to that question. You may also include queries you may have made with respect to a particular question, should you have been able to ‘raise your hand’ in an examination room.
If you experience any technical difficulties during the exam, contact the Library AskUs service for advice (open 7am–10pm, 7 days a week, Brisbane time):
Chat: https://support.my.uq.edu.au/app/chat/chat_launch_lib/p/45
Phone: +61 7 3506 2615
You should also ask for an email documenting the advice provided so you can provide this on request.
In the event of a late submission, you will be required to submit evidence that you completed the exam in the time allowed. We recommend you use a phone camera to take photos (or a video) of every page of your exam. Ensure that the photos are time-stamped.
Page 1 of 18
If you submit your exam after the due time then you should send details (including any evidence) to SMP Exams as soon as possible after the end of the exam.
Important exam condition information
The normal academic integrity rules apply.
You cannot cut-and-paste material other than your own work as answers.
You are not permitted to consult any other person – whether directly, online, or through any other means – about any aspect of this assessment during the period that this assessment is available.
If it is found that you have given or sought outside assistance with this assessment then that will be deemed to be cheating and will result in disciplinary action.
By undertaking this online assessment you will be deemed to have acknowledged UQ’s academic integrity pledge to have made the following declaration:
“I certify that my submitted answers are entirely my own work and that I have neither given nor received any unauthorised assistance on this assessment item”.
Page 2 of 18
Semester Two Final Examination, 2020 MATH7861 Discrete Mathematics
1. (a) For statement variables p and q, prove that
p ∨ (p → q)
is a tautology.
You may use either truth tables or logical equivalences. If you use logical equivalences, you should name the laws you use at each step.
Page 3 of 18
Semester Two Final Examination, 2020 MATH7861 Discrete Mathematics
(b) Prove that the following argument is valid. You should use only the laws of inference (i.e., the list of valid argument forms from lectures) and/or logical equivalences.
1. (a ∨ b) → c 2. d→a
Page 4 of 18
Semester Two Final Examination, 2020 MATH7861 Discrete Mathematics
2. (a) Using the Euclidean algorithm, compute gcd(588, 90). Show all your working.
(b) Using your answer to part (a), compute lcm(588, 90).
Page 5 of 18
Semester Two Final Examination, 2020 MATH7861 Discrete Mathematics
3. (a) Prove the following statement: Foralln∈Z,ifnisoddthen(n+2)2 ≡n2 (mod8).
(b) Find a counterexample to disprove the following statement: Foralln∈Z,(n+2)2 ≡n2 (mod8).
Page 6 of 18
Semester Two Final Examination, 2020 MATH7861 Discrete Mathematics
4. Let a0, a1, a2, . . . be the sequence defined recursively by a0 = 0, a1 = 1, and an =n2·(3+an−1−an−2)forallintegersn≥2.
(a) Compute the terms a2, a3 and a4.
(b) Guess an explicit formula for this sequence, and prove that your formula is correct.
(Hint: If you have trouble guessing, you may find that computing more terms can help.)
Page 7 of 18
Semester Two Final Examination, 2020 MATH7861 Discrete Mathematics
5. Let b0, b1, b2, . . . be the sequence defined recursively by b0 = 0, b1 = 1, and bn = 2(bn−1 + bn−2) for all integers n ≥ 2.
Using strong mathematical induction, prove that for all integers n ≥ 0, bn ≡ n (mod 3). (5 marks)
Page 8 of 18
Semester Two Final Examination, 2020 MATH7861 Discrete Mathematics
6. (a) Write out the elements of P({1}) and P(P({1})).
(b) Suppose sets A, B and C have cardinalities |A| = 3, |B| = 4 and |C| = 5. What is the cardinality of A × B × C?
Page 9 of 18
Semester Two Final Examination, 2020 MATH7861 Discrete Mathematics
Recall that [a,b] denotes the interval from a to b including its endpoints, that (a,b) denotes the interval from a to b excluding its endpoints, and that |S| denotes the cardinality of the set S.
Prove that |[0, 1] ∪ [2, 3]| = |(4, 5)|.
(Hint: You might wish to use the Schr ̈oder-Bernstein theorem.)
Page 10 of 18
Semester Two Final Examination, 2020 MATH7861 Discrete Mathematics
7. Consider the function f : Z → {0,1,2} defined by f(n) = n2 mod 3.
(a) What is the image of the set {0, 1, 2}? You do not need to show your working.
(b) What is the preimage of 0? You do not need to show your working.
(c) What is the image of Z? You do not need to show your working.
(d) Is f one-to-one? Is f onto? You do not need to explain your answers.
Page 11 of 18
Semester Two Final Examination, 2020 MATH7861 Discrete Mathematics
8. Define a relation ρ on N by xρy if and only if x×y is a perfect square.
Determine whether ρ is reflexive, whether ρ is symmetric, and whether ρ is transitive. For
each property, explain why or why not.
(Recall that, in this course, N = {1, 2, 3, . . .}, and a perfect square is a number of the form n2 where n ∈ Z.)
Page 12 of 18
Semester Two Final Examination, 2020 MATH7861 Discrete Mathematics
9. It is time to elect the University President! There are two candidates: Donald and Joe.
The university contains six faculties, and each faculty gets one vote. To win the election, you
need a majority of votes (i.e., four or more faculties must vote for you).
(a) How many different ways could the faculties cast their votes to ensure a perfect tie (i.e., Donald and Joe each receive exactly three votes)?
Give your answer as a single integer.
(b) If each faculty votes for either Donald or Joe at random (e.g., by flipping a coin), what is the probability that Donald wins the election?
Give your answer in the form of a fraction.
Page 13 of 18
Semester Two Final Examination, 2020 MATH7861 Discrete Mathematics
Now suppose that the Science faculty publicly declares that they will not choose their own vote, but instead they will vote in the same way as the Arts faculty.
If each of the other five faculties (including Arts but not Science) votes for either Donald or Joe at random, and then Science votes exactly the same way as Arts, what is the probability that Donald wins the election?
Give your answer in the form of a fraction.
Page 14 of 18
Semester Two Final Examination, 2020 MATH7861 Discrete Mathematics
10. Let G denote the group (Z2 ×Z2,+), and let H denote the group ({1,3,5,7},◦) where x◦y is defined to be x × y (mod 8).
(a) Write out the full Cayley tables for G and H.
(b) Are groups G and H isomorphic? Explain why or why not.
Page 15 of 18
Semester Two Final Examination, 2020 MATH7861 Discrete Mathematics
11. (a) A graph has 12 edges, and every vertex of the graph has degree 3. How many vertices does the graph have?
(b) In a tree, every vertex has degree 1 or degree 3. If there are exactly four vertices of degree 3, how many vertices have degree 1?
END OF EXAMINATION
Page 16 of 18
Semester Two Final Examination, 2020 MATH7861 Discrete Mathematics MATH1061/MATH7861 Examination Formula Pages
Logical Equivalences
Given any statement variables p, q and r, the following logical equivalences hold, where t denotes a tautology and c denotes a contradiction:
Commutative laws Associative laws Distributive laws Identity laws Negation laws Double negative laws Idempotent laws Universal bound laws De Morgan’s laws Absorption laws Negations of t and c
Valid Argument Forms
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) p∨c≡p
∼ (p ∨ q) ≡ ∼ p ∧ ∼ q p ∧ (p ∨ q) ≡ p ∼c≡t
p∧q≡q∧p (p∧q)∧r≡p∧(q∧r) p∧(q∨r)≡(p∧q)∨(p∧r) p∧t≡p
p∨t≡t ∼(p∧q)≡∼p∨∼q p∨(p∧q)≡p
p→q p∼q∼p ∴q∴p∴q
Generalization (a)
Elimination
p ∧ q ∴p∴q∴r
p Contradiction Rule ∼ p → c q∴p ∴p∧q
Transitivity p→q q→r
∴p→r Proofby p∨q
Specialization Conjunction
Set Identities
(b) p ∧ q q→r
∴p∨q divisionintocases p→r
Given any sets A, B and C that are subsets of a universal set U, the following laws hold:
1. CommutativeLaws 2. AssociativeLaws
3. DistributiveLaws
4.IdentityLaws
5. ComplementLaws
6. Double Complement Law 7. IdempotentLaws
8. Universal Bound Laws
9. DeMorgan’sLaws
10. AbsorptionLaws
11. Complement of U and ∅ 12. Set Difference Law
(a)A∪B=B∪A (b)A∩B=B∩A (a)(A∪B)∪C=A∪(B∪C)
(b) (A ∩ B) ∩ C = A ∩ (B ∩ C) (a)A∪(B∩C)=(A∪B)∩(A∪C)
(b) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) (a)A∪∅=A (b)A∩U=A
(a)A∪Ac =U
(a) A ∪ U = U
(a)(A∪B)c =Ac ∩Bc (b)(A∩B)c =Ac ∪Bc (a)A∪(A∩B)=A (b)A∩(A∪B)=A (a)Uc =∅ (b)∅c =U
A − B = A ∩ Bc
Page 17 of 18
(b)A∩Ac =∅ (b)A∩A=A
(b) A ∩ ∅ = ∅
Semester Two Final Examination, 2020 MATH7861 Discrete Mathematics
The Quotient-Remainder Theorem Given any integer n and any positive integer d, there exist unique integers q and r such that n = dq + r and 0 ≤ r < d.
Unique Factorisation Theorem Given any integer n > 1, there exists a positive integer k, distinct prime numbers p ,p ,…,p , and positive integers e ,e ,…,e such that n = pe1pe2 ···pek, and any
12k 12k 12k
other expression for n as a product of prime numbers is identical to this except perhaps for the order in which the factors are written.
Schro ̈der- For all sets A and B, if |A| ≤ |B| and |A| ≥ |B| then |A| = |B|. Binomial Theorem Given any real numbers a and b, and any nonnegative integer n,
n nnn−kk (a+b)= kab.
Page 18 of 18
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com