CS计算机代考程序代写 discrete mathematics flex Semester One Final Examinations, 2018 MATH1061 Discrete Mathematics

Semester One Final Examinations, 2018 MATH1061 Discrete Mathematics

Page 1 of 15

This exam paper must not be removed from the venue

School of Mathematics & Physics

EXAMINATION

Semester One Final Examinations, 2018

MATH1061 Discrete Mathematics

This paper is for St Lucia Campus and St Lucia Campus (External) students.

Examination Duration: 120 minutes

Reading Time: 10 minutes

Exam Conditions:

This is a Central Examination

This is a Closed Book Examination – specified 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.

Venue ____________________

Seat Number ________

Student Number |__|__|__|__|__|__|__|__|

Family Name _____________________

First Name _____________________

For Examiner Use Only

Question Mark

Total ________
Out of 70

Barbara Maenhaut

Semester One Final Examination, 2018 MATH1061 Discrete Mathematics

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

Barbara Maenhaut

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

Barbara Maenhaut

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

(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

Barbara Maenhaut

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

Barbara Maenhaut

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

Barbara Maenhaut

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)

(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

Barbara Maenhaut

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

Barbara Maenhaut

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)

Page 9 of 15

Barbara Maenhaut

Semester One Final Examination, 2018 MATH1061 Discrete Mathematics

9. Consider a standard deck of cards having 52 cards, that is, 13 cards (Ace, 2, 3, . . . , 10, Jack,
Queen, King) of each suit (Hearts, Diamonds, Spades and Clubs).

(a) Determine the number of sets of four cards that can be selected from the deck of 52 cards.
(You do not need to simplify your answer.)

(1 mark)

(b) If four cards are chosen at random from the deck, what is the probability that the four
cards are all hearts? (You do not need to simplify your answer. )

(2 marks)

(c) Determine the number of sets of four cards that can be selected from the deck such that
the four cards include at least one Ace or at least one 2 (where ‘or’ means ‘inclusive or’).
(You do not need to simplify your answer.)

(4 marks)

Page 10 of 15

Barbara Maenhaut

Semester One Final Examination, 2018 MATH1061 Discrete Mathematics

10. Determine the smallest integer n such that if A is any subset of cardinality n chosen from the
set S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13} then A contains at least two integers whose difference
is divisible by 3. Explain your answer clearly including a justification that your integer n is as
small as possible.

(4 marks)

Page 11 of 15

Barbara Maenhaut

Semester One Final Examination, 2018 MATH1061 Discrete Mathematics

11. Use the Binomial Theorem to calculate the coefficient of x9 in the expansion of (2×3 − 5)10.
(You do not need to simplify your answer.)

(3 marks)

Page 12 of 15

Barbara Maenhaut

Semester One Final Examination, 2018 MATH1061 Discrete Mathematics

12. Let T be a tree with 8 edges that has exactly 5 vertices of degree 1. Prove that if v is a vertex
of maximum degree in T , then 3 ≤ deg(v) ≤ 5.

(6 marks)

Page 13 of 15

Barbara Maenhaut

Semester One Final Examination, 2018 MATH1061 Discrete Mathematics

13. For each of the following lists of conditions, either draw a graph with the stated properties or
explain why no such graph exists.

(a) A graph with 5 vertices and 3 edges.

(1 mark)

(b) A graph with 6 vertices of which 3 have degree 3 and 3 have degree 2.

(1 mark)

(d) A tree having 5 vertices and degree sequence 3,2,2,2,1.

(1 mark)

END OF EXAMINATION

Page 14 of 15

Barbara Maenhaut

Semester One Final Examination, 2018 MATH1061 Discrete Mathematics

MATH1061/MATH7861 Examination Formula Page
Logical Equivalences
Given any statement variables p, q and r, a tautology t and a contradiction c, the following logical
equivalences hold.

Commutative laws p ∧ q ≡ q ∧ p p ∨ q ≡ q ∨ p
Associative laws (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
Distributive laws p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Identity laws p ∧ t ≡ p p ∨ c ≡ p
Negation laws p∨ ∼ p ≡ t p∧ ∼ p ≡ c
Double negative laws ∼ (∼ p) ≡ p
Idempotent laws p ∧ p ≡ p p ∨ p ≡ p
Universal bound laws p ∨ t ≡ t p ∧ c ≡ c
De Morgan’s laws ∼ (p ∧ q) ≡∼ p∨ ∼ q ∼ (p ∨ q) ≡∼ p∧ ∼ q
Absorption laws p ∨ (p ∧ q) ≡ p p ∧ (p ∨ q) ≡ p
Negations of t and c ∼ t ≡ c ∼ c ≡ t

Valid Argument Forms
Modus Ponens p→ q Elimination (a) p ∨ q (b) p ∨ q

p ∼ q ∼ p
∴ q ∴ p ∴ q

Modus Tollens p→ q Transitivity p→ q
∼ q q → r
∴∼ p ∴ p→ r

Generalization (a) p (b) q Proof by p ∨ q
∴ p ∨ q ∴ p ∨ q division into cases p→ r

Specialization (a) p ∧ q (b) p ∧ q q → r
∴ p ∴ q ∴ r

Conjunction p Contradiction Rule ∼ p→ c
q ∴ p
∴ p ∧ q

Set Identities For all sets A, B and C that are subsets of a universal set U :
1. Commutative Laws (a) A ∪B = B ∪ A (b) A ∩B = B ∩ A
2. Associative Laws (a) (A ∪B) ∪ C = A ∪ (B ∪ C)

(b) (A ∩B) ∩ C = A ∩ (B ∩ C)
3. Distributive Laws (a) A ∪ (B ∩ C) = (A ∪B) ∩ (A ∪ C)

(b) A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩ C)
4. Identity Laws (a) A ∪ ∅ = A (b) A ∩ U = A
5. Complement Laws (a) A ∪ Ac = U (b) A ∩ Ac = ∅
6. Double Complement Law (Ac)c = A
7. Idempotent Laws (a) A ∪ A = A (b) A ∩ A = A
8. Universal Bound Laws (a) A ∪ U = U (b) A ∩ ∅ = ∅
9. De Morgan’s Laws (a) (A ∪B)c = Ac ∩Bc (b) (A ∩B)c = Ac ∪Bc
10. Absorption Laws (a) A ∪ (A ∩B) = A (b) A ∩ (A ∪B) = A
11. Complement of U and ∅ (a) U c = ∅ (b) ∅c = U
12. Set Difference Law A−B = A ∩Bc

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 p1, p2, . . . , pk, and positive integers e1, e2, . . . , ek such that n = p

e1
1 p

e2
2 · · · p

ek
k ,

and any 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-Bernstein Theorem For all sets A and B, if |A| ≤ |B| and |A| ≥ |B| then |A| = |B|.

Page 15 of 15

DiscreteMathematics_FinalCover
MATH1061FinalExamination

Related Posts