課程名稱︰離散數學 課程性質︰選修 課程教師：呂育道 開課學院：電資學院 開課系所︰資工系 考試日期（年月日）︰2016.06.23 考試時限（分鐘）： 試題 : Discrete Mathematics Final Examination on June 23, 2016 Spring Semester, 2016 Problem 1 (10 points) Let (R, +, ·) be a ring with unity. Prove the following statements. (1) (5 points) The unity is unique. (2) (5 points) If x is a unit of R, then the multiplicative inverse of x is unique. Ans: (1) For all x ∈ R, assume that there are two unities u_1 and u_2 ∈ R where x · u_1 = u_1 · x = x and x · u_2 = u_2 · x = x. Then u_1 = u_2 and so the claim holds. (2) Let x ∈ R be a unit and u denote the unity of R. Suppose that r_1, r_2 ∈ R both satisfy the properties of multiplicative inverses of x, which are x · r_1 = r_1 · x = u and x · r_2 = r_2 · x = u. Then it is clear that r_1 = r_1 · u = r_1 · (x · r_1) = r_1 · (x · r_2) = u · r_2 = r_2. Problem 2 (10 points) Let (G, o) and (H, o') be two groups, and f : G → H be a group homomorphism onto H. If G is abelian, prove that H is a abelian. Ans: Let g_1 and g_2 in G. Then there exist h_1 and h_2 in H so that f(g_1) = h_1 and f(g_2) = h_2. Hence, h_1 o' h_2 = f(g_1) o' f(g_2) = f(g_1 o g_2) = f(g_2 o g_1) = f(g_2) o' f(g_1) = h_2 o' h_1. Problem 3 (10 points) Let S_6 be a group of all permutations of {1, 2, 3, 4, 5, 6}, and ╭ 1 2 3 4 5 6 ╮ ╭ 1 2 3 4 5 6 ╮ α = │ │, β = │ │ ╰ 2 4 3 1 6 5 ╯ ╰ 3 4 1 5 2 6 ╯ be two elements of S6. (1) (5 points) Express the cycle decomposition (product of disjoint cycles) of α. (2) (5 points) Express the cycle decomposition for αβ. Ans: (1) α = (124)(3)(56). (2) αβ = (143)(256). Problem 4 (10 points) Let h(x) = x^4 + x^3 + x^2 + x + 1 ∈ Z_2[x]. Prove that h(x) is irreducible. Ans: Since h(0) = h(1) = 1, h(x) has no first-degree factors. Now we examine the second-degree factors. Assume that (x^2 + ax + b)(x^2 + cx + d) = x^4 + x^3 + x^2 + x + 1. By expanding the aforesaid equation and comparing the coefficients, it is easy to obtain a + c = 1, ac + b + d = 1, ad + bc = 1, bd = 1, As bd = 1, it follows that b = d = 1, so ac = 1 and furthermore a = c = 1. This implies a + c = 0, a contradiction. Hence, h(x) is irreducible. Problem 5 (10 points) Let G be a group. Please explain that for all a, b ∈ G, -1 -1 (a) (a ) = a -1 -1 -1 (b) (ab) = b a Ans: -1 -1 -1 (a) As aa = e = a a, the inverse of a is a. -1 -1 -1 -1 -1 -1 (b) As (ab)(b a ) = a(bb )a = aea = aa = e, the inverse of ab -1 -1 is b a . Problem 6 (10 points) Assume that G is a group, H ⊆ G and H ≠ ψ. Prove that H is a subgroup of G if for all a, b ∈ H, ab^(-1) ∈ H. Ans: (i) Identity: Because H ≠ ψ, there exists an a ∈ H, which implies aa^(-1) = e ∈ H. (ii) Inverse: For all a ∈ H, ea^(-1) = a^(-1) ∈ H, because e ∈ H. (iii) Closure: For all a, b ∈ H, a(b^(-1))^(-1) = ab ∈ H, for b^(-1) ∈ H. (iv) Associativity: See p. 788 on the slides. Problem 7 (10 points) G is a group, H ⊆ G, H ≠ ψ and H is finite. Prove that H is a subgroup of G if for all a, b ∈ H, ab ∈ H. (Hint: Cite the theorem of the previous problem) Ans: Because H ≠ ψ, there exists an a ∈ H so that a^1, a^2, a^3, … ∈ H by the closure property. Because H is finite, there exists i < j and a^i = a^j, which implies e = a^(j-i) = aa^(j-i-1) = a^(j-i-1)a. Hence, a^(-1) = a^(j-i-1) ∈ H. Then, for all a, b ∈ H, ab^(-1) ∈ H, because of b^(-1) ∈ H and the closure property. The theorem of the previous problem then implies H is a subgroup of G. Problem 8 (10 points) Define the binary operation ⊕ and ⊙ on Z by x ⊕ y = x + y - 7, x ⊙ y = x + y - 3xy, for any x, y ∈ Z. Show that (Z, ⊕, ⊙) is not a ring. Ans: Take x = y = z = 1, x, y, z ∈ Z. Then ╭ x ⊙ (y ⊕ z) = 1 ⊙ (1 ⊕ 1) = 1 ⊙ (-5) = 11 < ╰ (x ⊙ y) ⊕ (x ⊙ z) = (1 ⊙ 1) ⊕ (1 ⊙ 1) = (-1) ⊕ (-1) = -9 Since x ⊙ (y ⊕ z) ≠ (x ⊙ y) ⊕ (x ⊙ z) disobey the distributive law, (Z, ⊕, ⊙) is not a ring. Problem 9 (10 points) Consider the following two polynomials: p(x) = 1 + 2x + x^3, q(x) = 3 + x^2 + 2x^3 over the ring (Z_4, +, ·). (a) Find p(x) + q(x). (b) Find p(x) · q(x). Ans: (a) p(x) + q(x) = (1 + 2x + x^3) + (3 + x^2 + 2x^3) = 4 + 2x + x^2 + 3x^3 = 2x + x^2 + 3x^3 (b) p(x) · q(x) = (1 + 2x + x^3) · (3 + x^2 + 2x^3) = 3 + 6x + x^2 + 7x^3 + 4x^4 + x^5 + 2x^6 = 3 + 2x + x^2 + 3x^3 + 0 + x^5 + 2x^6 = 3 + 2x + x^2 + 3x^3 + x^5 + 2x^6 Problem 10 (10 points) Find the multiplicative inverses of all elements of Z_11 and Z_13. Ans: (a) In Z_11, 1^(-1) = 1, 2^(-1) = 6, 3^(-1) = 4, 4^(-1) = 3, 5^(-1) = 9, 6^(-1) = 2, 7^(-1) = 8, 8^(-1) = 7, 9^(-1) = 5, 10^(-1) = 10. (b) In Z_13, 1^(-1) = 1, 2^(-1) = 7, 3^(-1) = 9, 4^(-1) = 10, 5^(-1) = 8, 6^(-1) = 11, 7^(-1) = 2^(-1), 8^(-1) = 5, 9^(-1) = 3, 10^(-1) = 4, 11^(-1) = 6, 12^(-1) = 12. --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.160.57.98 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1480493834.A.E4E.html ※ 編輯: rod24574575 (61.228.166.1), 12/03/2016 10:23:18