MATH1005/MATH6005 Discrete Mathematical Models Midsemester Exam, Semester 1, 2021
Artwork by FABP.
Throughout this exam, we adopt the following conventions: We write N for the set of positive integers and N⋆ for the set of non-negative integers.
Copyright By PowCoder代写 加微信 powcoder
Problem 1 (5 marks) (a) Explain, using new examples, the difference between statements and predi- cates, and two different ways in which predicates become statements. Your examples should be new in the sense that they do not appear in the lecture notes or in any other course materials. Write no more than five sentences.
(b) Let P denote the set of primes. Each of the following is a famous conjecture (a statement that has not been proved or disproved, but that many suspect to be true) concerning P.
(Conjecture1)∀n∈N (((n≥4)∧(∃k∈Z(n=2k)))→(∃p1,p2∈P n=p1+p2)). (Conjecture 2) For every positive integer n, there exists a prime p such that n2 < p < (n + 1)2.
(i) Restate Conjecture 1 as a statement in English. Make the statement as brief as you can.
(ii) Use symbolic notation, like that used to state Conjecture 1 above, to state the negation of Conjecture 2 without using the symbol ¬.
(c) Complete the following input-output table and then draw a circuit diagram for a circuit that gives the appropriate outputs.
X Y Z (¬X∧¬Y)∨(Y∧Z) 111
110 101 100 011 010 001 000
Problem 2 (5 marks) (a) Give an example of a set A such that A ⊆ Q\Z and A has exactly two elements, and an example of a set B that is a subset of the English alphabet such that B has exactly three elements. Then describe each of the following sets using set-roster notation: A×B, P(B).
(b) We define a sequence by (an)n∈N by
∀n∈Nan+1 =an +(n+1)2
Use mathematical induction to prove that the following is an explicit definition of the same sequence
∀n∈N an = n(n+1)(2n+1). 6
(c) (i) Use Venn diagrams to help you decide whether the following statement is true or false: For any universal set U and for all A, B, C ∈ P(U), we have
(B \ A) ∪ (C \ A) = (B ∪ C) \ A
(ii) Use the logical equivalences below and the definitions of set operations to prove, or provide a counterexample to disprove, the statement you investigated in part (i).
Given any statement variables p, q, and r, a tautology t and a contradiction c, the following logical equivalences hold.
1. Commutativelaws: p∧q≡q∧p
2. Associativelaws: (p∧q)∧r≡p∧(q∧r)
3. Distributivelaws: p∧(q∨r)≡(p∧q)∨(p∧r) 4. Identitylaws: p∧t≡p
5. Negationlaws: p∨¬p≡t
6. Double negative law: ¬(¬p) ≡ p
7. Idempotentlaws: p∧p≡p
8. Universalboundlaws: p∨t≡t
9. DeMorgan’slaws: ¬(p∧q)≡¬p∨¬q
10. Absorptionlaws: p∨(p∧q)≡p
11. Negationsoftandc: ¬t≡c
p∨q≡q∨p (p∨q)∨r≡p∨(q∨r) p∨(q∧r)≡(p∨q)∧(p∨r) p∨c≡p
p∧c≡c ¬(p∨q)≡¬p∧¬q p∧(p∨q)≡p ¬c≡t
Problem 3 (5 marks) (a) Let A and B be sets and let R ⊆ A×B. What else must be true about R for it to be a surjective function?
(b) A relation R is defined on the set S = {Australia, China, India, Jamaica, Mali} by the rule xRy ⇔ The word x has at least as many letters as the word y.
Draw a digraph representing R.
(c) Does the function f : {1,2,3,4,5,6} → {1,2,3,4,5,6} given by f(x) = 3x mod 7 have an inverse? Justify your answer.
(d) Let A = {cat, dog, chicken}, let B = {2, 5, 6, 9} and let C = {x, y, z}. Prove or disprove the following: If f : A → B is injective, and g : B → C is surjective, then g ◦ f is surjective.
Problem 4 (5 marks) (a) Let w = 110101010010. This bit string is used to represent numbers in different ways.
(i) Write in decimal the integer x represented by w if w represents an integer in binary positional notation.
(ii) Write in decimal the integer y represented by w if w represents an integer using the 12-bit signed integer (the two’s complement) format.
(iii) Write as a decimal the rational number q represented by w if w represents a rational number q = (−1)s ×m×2n (with 1 ≤ m < 2) by using: the first bit to store s; followed by 3 bits to store a non-negative integer representing n + 3; followed by 8 bits to store the bits that appear after the binary point in the mantissa m.
(b) Describe the set A = {x ∈ Z | x mod 5 = x div 5} in set-roster notation. Justify your answer.
(c) The list (Xi)1..6 = (G,O,B,L,I,N) is to be sorted using Selection sort. The sorting is to be achieved by progressively modifying an index function π, rather than by shuffling members of the list itself. So initially (Xi)1..6 = (Xπ(i))1..6 where π(i) = i for i = 1, ..., 6, and when sorting is complete π is sufficiently changed so that (Xπ(i))1..6 is in alphabetical order. Complete the table below, or copy what is below to your page and complete it, to show the state of the index function π after each time the least element algorithm has been called by Selection Sort. For reference, the algorithm is shown on the next page.
How many times LEA
has been called π
0 1 2 3 4 5 6
123456 123456 123456
123456 123456 123456 123456 123456
← write something here ← write something here ← write something here ← write something here ← write something here ← write something here
Least Element Algorithm
Input: Sequence (xi)s..f ⊆ S, an ordering rule “≤” for S and an index function π on {s,...,f}. Output: Modification to π so that xπ(s) ≤ xπ(i) for i = s, ..., f .
i ← s + 1. m ← s.
Loop: Ifi=f+1stop.
If xπ(i) < xπ(m) then m ← i.
i←i+1 Repeat loop
Swap the values of π(s) and π(m).
Selection sort algorithm
Input: Sequence (xi)1..n ⊆ S, an ordering rule “≤” for S and an index function π on {1, . . . , n}.
Output: Modification to π so that (xπ(i))1..n is in non-decreasing order xπ(1)≤xπ(2)≤···≤xπ(n).
Loop: If s = n stop.
Run least element algorithm on (xπ(i))s..n s←s+1
Repeat loop
THIS IS THE END OF THE EXAM.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com