課程名稱︰離散數學 課程性質︰選修 課程教師︰陳健輝 開課學院：電機資訊學院 開課系所︰資工系 考試日期（年月日）︰2011/5/24 考試時限（分鐘）：2小時 是否需發放獎勵金：是 （如未明確表示，則不予發放） 試題 : Examination #2 (範圍:Algebra) 1. Prove that if 3|n^2 then 3|n, where n is a positive integer, by the methods of: (a) p→q <=> ┐q→┐p; (5%) (b) contradiction. (5%) 2. The following are some binary relations on A = {1, 2, 3, 4}. R1 = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (1, 3), (1, 4), (2, 3), (4, 2), (4, 3)}. R2 = {(1, 1), (2, 2), (3, 3), (4, 4), (2, 3), (3, 2)}. R3 = {(1, 2), (2, 1), (2, 3), (3, 2), (1, 4), (4, 1)}. R4 = {(1, 1), (2, 2), (2, 3), (4, 4)}. R5 = {(1, 2), (2, 1), (2, 3), (3, 3), (3, 4)}. (a) Which are reflexive? (2%) (b) Which are irreflexive? (2%) (c) Which are symmetric? (2%) (d) Which are antisymmetric? (2%) (e) Which are transitive? (2%) (f) Which are equivalence relations? (2%) (g) For each of (f), find all equivalence classes. (2%) (h) Which are partial orderings? (2%) (i) For each of (h), how many possible topological orders on A are there? (2%) (j) Which are total orderings? (2%) 3. The following is a proof for a．0 = 0 in a Boolean algebra (K,．, +), where a belongs to K. _ _ _ a．0 = (a．0) + 0 = (a．0) + (a．a) = a．(0 + a) = a．a = 0. Is it feasible to obtain a proof for a + 1 = 1 from the above by replacing all occurrences of "+", "．", and "0" with "．", "+", and "1", respectively ? That is, _ _ _ a + 1 = (a + 1)．1 = (a + 1)．(a + a) = a + (1．a) = a + a = 1. Explain your answer. (10%) 4. For the commutative ring R = (Z, ⊕, ⊙), where Z is the set of integers and a⊕b = a + b - 1, a⊙b = a + b - abfor any a, b belong to Z. (a) find the identity for ⊕; (3%) (b) find the inverse of 5 under ⊕; (3%) (c) find the unity for ⊙l (3%) (d) show that R is an integral domain; (5%) (e) show that R is not a field; (5%) (f) show that (Zodd, ⊕, ⊙) is a subring of R; where Zodd is the set of odd integers; (6%) (g) show that (Zodd, ⊕, ⊙) is an ideal; (5%) 5. Let C be the set of complex numbers and S be the set of real matrices of the form [ a b] Define f: C→S be f(a+bi) = [ a b] [-b a]. [-b a]. (a) Prove that f is a ring isomorphism from (C, +,．) to (S, ⊕, x), where + and ． (⊕ and x) are ordinaryaddition and multiplication, respectively, on complex numbers (matrices). (5%) (b) How to compute (4+5i)．(2-3i) by using x? (5%) 6. Let G = <a> with o(a) = n. Prove that a^k, k belongs to Z+, generate G if and only if gcd(k, n) = 1. (10%) 7. Prove that any group of prime order is cyclic. (10%) 8. (加分題)以下是有關本課程與課堂上發生的，何者為真？ (a) 老師的姓名是陳建輝 (2%) (b) 老師習慣站著講課，但偶爾也會坐在椅子講課 (2%) (c) 老師習慣帶一杯茶進教室，但也曾帶罐裝飲料進教室 (2%) (d) 老師曾因趕課而延後20分鐘下課 (2%) (e) 老師曾因事請助教代課 (2%) (f) 上課曾遇有感地震 (2%) (g) 上課曾遇投影設備故障 (2%) (h) 老師曾提及張愛玲與金庸的小說 (2%) (i) 老師曾提及曾國藩家訓 (2%) (j) 老師曾提及妥瑞氏症 (2%) --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.30.142