CPT 107 Discrete Mathematics and Statistics 2022/23 SEMESTER 1 – Assessment I
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CPT 107
2022/23 SEMESTER 1 – Assessment I
BACHELOR DEGREE – Year 2
Discrete Mathematics and Statistics
DEADLINE: 04 November 2022 at 5 pm
Notes:
.To obtain full marks for each question, relevant and clear steps must be included in the answers.
.Partial marks maybe awarded depending on the degree of completeness and clarity.
QUESTION 1: Proof Techniques (20 marks)
(a) Use proof by contradiction to show that there does not exist any integers x andy such that 6x + 18y = 1. (3 marks)
(b) Let a be a positive real number, and the Statement S be: “if a is not rational number, then 6 a is also not a rational number” .
1. Prove the Statement S by contradiction.
2. If you think the converse of the Statement S is true, prove it. If not, give a counter-example. (8 marks)
(c) For x, y, z ∈ ℤ, use proof by contradiction to show the following statement:
if x2 + y2 = z2, then at least one of x and y is even. (5 marks)
(d) For all integer m ≥ 1, use proof by induction to show that:
2m( )(m + 12 + 22 + 32 + … + 2m2 (4 marks)
QUESTION 2: Set Theory (32 marks)
(a) Let the universal set be ℕ, A = {x ∈ ℕ | x is even and 3 < x < 11},
B = {x ∈ ℕ x is odd and 2 < x < 10}, C = x ∈ ℕ x is odd and 3 < x < 9} and D = d ∈ ℕ d2 = 5}. Find the elements of the following expressions:
1. B ∩ (A ∪ D)
2. ~( B − D) ∩ A)
3. C ∪ D)∩ B Δ A)
4. ( D ∪ B ∩ A Δ B) ∪ B − A − D ) ∩ C (8 marks)
(b) Let X and Y be sets, then X ⊆ Y if and only if ~X ⊆ ~Y. If you think that it is true, prove it. Otherwise, give a counterexample to show that it is false. (6 marks)
(c) Prove that the following sets are equal:
1. A x (B ∪ C) = (A x B) ∪ (A x C)
(d) Let X and Y be sets, and X ⊆ Y if and only if (Y − X) ∪ X = Y. If you think that it is true, prove it. Otherwise, give a counterexample to show that it is false. (8 marks)
QUESTION 3: Relations (48 marks)
(a) Let A = a ∈ ℤ a ≠ 0 } andR be the relation on the set A defined by
R ={(a,b) a + b = 2c, where a,b,c ∈ A. Prove or disprove that R over A is an equivalence notion. (6 marks)
(b) Let A = 1,2,3,4 . What is the transitive closure of the relation 1,2 , 2,3), 03,4, 1,3 , 1,4 , 2,4 on A? Express your answer using ordered pairs. (4 marks)
(c) If A and B are both transitive relations, then their intersection is also transitive. If you think that it is true, prove it. If not, give a counter-example. (8 marks)
(d) Let R and S be two partial orders on a set X, and Tis a relation on X such that aTb (i.e. a,b ∈ X) if and only if both aRb and aSb hold. Is T also a partial order on X? Justify your answer with proofs and/or counterexamples (7 marks)
(e) Given the partial ordering on the following set A = {a, b, c, d, e} as {(a,a), (b,b), (c,c), (d,d), (e,e), (a,b), (a,c), (a,d), (a,e), (d,e)}, draw the corresponding Hasse diagram. (3 marks)
(f) Let A be the points in the plane (A = R × R). We say two points are equivalent if they are equal distance from the origin. So (x, y) ∼ (w, z) if x2+y2 = w2+z2. Show this is an equivalence relation on A and find the equivalent classes. ( 10 marks)
(g) For all a, b ∈ Z+, we define a ◎bif a/b ∈ Z+. Prove or disprove ◎ is a partial order and/or a total order on Z+. ( 10 marks)
2023-07-29