SEHH2241 Discrete Structures 2024–2025 Semester One Individual Assignment One
SEHH2241 Discrete Structures
2024–2025 Semester One
Individual Assignment One
Due time: Saturday 19 October 2024 23:59
-
Answer ALL questions. Each question carries 20 marks. Write all the solutions and answers on the answer sheet provided.
-
You must write your answers using the notations introduced in classes.
-
Unless otherwise specified, show your steps clearly for all questions.
-
Write your answers neatly. Unclear answers will not be marked.
-
You may use the facts and theorems introduced in the lecture notes. All other facts/theorems that are not covered must be rigorously proved before being used.
-
All answers are to be exact. Submission guidelines
-
Submit your work to the ‘SEHH2241 Individual Assignment One Submission Platform’ in the centralized Blackboard page. Email / late / computer-typed submissions and re-submissions are NOT accepted.
-
Submit your work online some time ahead of the deadline. Late submissions due to slow internet speed, for instance, will NOT be accepted.
-
SCAN the ENTIRE file and save it as ONE single PDF file. That is, even if you did not attempt some questions, you still need to scan that empty pages. Moreover, do not scan a portion of a page only—we need the ENTIRE page.
-
Scan the file IN THE ORDER OF THE PAGES. That is, page 1 should come before page 2, and page 2 should come before page 3 and so on.
-
Make sure that your work is properly scanned. Over-sized, blurred or upside-down pages will NOT be graded.
-
If you do not have access to a scanner, you may use a mobile app (e.g., CamScanner) to scan it. The scanning by a physical scanner is highly preferable, though.
-
Upload the PDF and double check the integrity of your file. Occasionally the scanned file may appear differently on the Blackboard system.
-
Name your file by your full English name. For example, if your name is Chan Tai Man, then your file name is SEHH2241 HW1 Chan Tai Man.pdf.
-
The maximum submission size is 20 MB.
IMPORTANT Each student is required to complete this assignment individually using his / her student ID number. The method is shown below.
R = the 8th digit of your student ID
Example: If your ID number is 23456789A, then R = 9.
Question 1
-
(a) Write a truth table for the statement below. Then, determine whether the statement is a tautology, contradiction or contingency. You are required to complete the three main connective columns of the truth table in the answer sheet.
[(∼ r ∧ q) ↔∼ p]⊕ ∼ [r → (p∨ ∼ q)]
-
(b) Prove the following statement by logical rules:
(p ∧ q) ↔ p ≡∼ p ∨ q
Question 2
-
(a) Let A = {−2,−1,0,1,2,3}, B = {5,8,R + 9} and C = {2,5,6,8}. Find the following. (NOTE: In this question, you are required to write down the answers only. No steps are required for this question.)
(i) (B×A×C)∩(B×C×A) (ii) |P(A×(B∪C)×C)|
(iii) P(B)∩P(C)
(iv) P(A∩C)∪{{∅}} -
(b) Let S, T, U and V be sets.
(i) Provethat(S×T)∩(U×V)=(S∩U)×(T∩V).(ii) Usetheresultof(b)(i)todeducethatS×(T∩U)=(S×T)∩(S×U).
Question 3
-
(a) Let n be an integer. Prove by contraposition that if n − 3 is divisible by 4, then n is not a square.
-
(b) Use the method of contradiction to show that there exists no rational number x for which x7 +x2 +1071 = 0.
Question 4
-
(a) Use mathematical induction to prove the following. (i) (3n+1)7n−1isdivisibleby9foralln∈Z+.
(ii) 1 + 1 +···+ 1 ≥ 7 forallintegersn≥2. n+1 n+2 2n 12
-
(b) Find all the fallacy(ies), if any, in the following ‘proof’ that 2241 = 2242.
Let P(n) : If a and b are natural numbers such that max({a,b}) = n, then a = b. We are to ‘prove’ thatP (n) holds for all n ∈ N by mathematical induction.
Basis step: Let a and b be natural numbers such that max({a,b}) = 0. Then a ≤ 0 and b ≤ 0. Sincea,b∈N,itfollowsthata=b=0. Thus,P(0)istrue.
Inductive step: Suppose that P(k) holds for some k ∈ N. Let a and b be natural numbers such that max({a, b}) = k + 1. Back-tracking one step from a and b yields max({a − 1, b − 1}) = k. Applying the induction assumption that P (k) holds, we obtain a − 1 = b − 1, i.e., a = b. Hence P (k + 1) also holds.
By the principle of mathematical induction, P (n) holds for each n ∈ N.
In particular, since max({2241, 2242}) = 2242 and P (2242) is true, we have 2241 = 2242.
Question 5
For each of the given functions, explain your answers for the following. (i) Is f one-to-one?
(ii) Is f onto?
(iii) Does f−1 exist?
(a) f:R×R→R×Risdefinedbyf(x,y)=(3x+(R+1)y,2x+(R+2)y)forevery(x,y)∈R×R.
(b) f:Z→Zisdefinedbyf(n)=lnmforeachn∈Z. 2
3/3
