課程名稱︰離散數學 課程性質︰資訊系選修 課程教師︰陳健輝 開課學院：電資學院 開課系所︰資訊系 考試日期（年月日）︰2012/05/28 考試時限（分鐘）：120 是否需發放獎勵金：是 （如未明確表示，則不予發放） 試題 : Examination #2 (範圍: Algebra) 1. Prove that if n^2 is even, then n is even, based on the logic of p→q <=> ┐q → ┐p. (10%) 2. The following are some binary relations on A = {1, 2, 3, 4}. R_1 = {(1,1), (2,2), (3,3), (4,4), (1,2), (1,3), (1,4), (4,2), (4,3)}. R_2 = {(1,1), (2,2), (3,3), (4,4), (1,2), (2,1), (1,4), (2,3), (4,2)}. R_3 = {(1,1), (4,4), (1,2), (1,3), (1,4), (2,3), (4,2), (4,3)}. R_4 = {(1,2), (1,3), (1,4), (2,3), (4,2), (4,3)}. R_5 = {(1,1), (2,2), (3,3), (4,4), (1,2), (1,3), (1,4), (2,3), (4,2), (4,3)}. (a) Which are total orderings? (3%) (b) Which are partial orderings, but not total orderings? (3%) (c) For each of (b), list all topological orders on A. (4%) 3. Let A = {1,2,3,4,5,6,7}, and define a binary relation R as follows: (x,y)∈R if and only if 3 | (x-y). (a) Show that R is an equivalence relation on A. (6%) (b) Determine the equivalence classes induced by R. (4%). 4. Show that the following two logic circuits are functionally equivalent, i.e., they produce the same output, when fed with the same input. (10%) _ _ _ _ _ _ _ _ _ f(w,x,y,z) = w x y z + w x y z + w x y z + w x y z + w x y z _ _ _ + w x y z _ _ _ _ _ _ f(w,x,y,z) = w x z + w x y + w x y + w x z (原圖請參閱老師講義 p.67 以及 p.69 上圖) http://inrg.csie.ntu.edu.tw/discrete2012/course/Part_2_Algebra.pdf 5. The following two tables make (R, + .‧) into a ring, where R = {s,t,x,y}. (a) What is the zero of R? (2%) (b) What is the additive inverse of t? (2%) (c) Is R communicative? Why? (2%) (d) Does R have a unity? Why? (2%) (e) Find all proper zero divisors of R. (2%) + | s t x y ‧| s t x y ----+-------------- ----+-------------- s | y x s t s | y y x x t | x y t s t | y y x x x | s t x y x | x x x x y | t s y x y | x x x x | | 6. The following is a proof for the fact that a finite integral domain (R, + ,‧) is a field. Suppose R = {d_1, d_2, ..., d_n}, where d_i's are distinct. Let a∈R and a≠z. We have a‧d_1, a‧d_2, ..., a‧d_n all distinct, and hence {a‧d_1, a‧d_2, ..., a‧d_n} = R. Since u∈R, we have u = a‧d_k = d_k‧a for some k, i.e. a^{-1} = d_k∈R. (1) Why is R = {d_1, d_2, ..., d_n} supposed? (2%) (2) Why are a‧d_1, a‧d_2, ..., a‧d_n all distinct? (3%) (3) Why {a‧d_1, a‧d_2, ..., a‧d_n} = R? (2%) (4) Why is the proof complete, as a^{-1} = d_k∈R is derived? (3%) 7. Find (1) [21]^{-1} in Z_{65} and (2) 1 <= x <= 64 so that [40]‧[x] = [0] in Z_{145}. (10%) ┌ a 0 ┐ | 8. Let S = { │ │ | a∈R }, where R is the set of real numbers. Then, └ 0 a ┘ | S is a ring under matrix addition and multiplication. Prove that R is isomorphic to S. (10%) 9. Suppose that ( G ,‧) is a group with a generator a and |G| = n. The following is an incomplete proof for that a^k is also a generator for G if and only if gcd(k,n) = 1, where k is a positive integer. Please provide the missing parts, i.e., "--- (1) ---" and "--- (2) ---". (10%) (if) For any b∈G. Suppose b = a^r for some integer r. gcd(k,n) = 1 => ks + nt = 1 for some integers s and t => b = a^4 = a^{r(ks+nt)} = --- (1) --- i.e., b can be generated by a^k. (only if) G = <a^k> => a = (a^k)^s for some integer s => a^{1 - ks} = e => --- (2) --- => gcd(k,n) = 1 10. Let G be a group with subgroups H and K. If |G| = 660, |K| = 66, and K ⊂ H ⊂ G, what are the possible values for |H|? (10%) --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.30.81 用pietty打字好蛋疼... ※ 編輯: suhorng 來自: 61.217.33.159 (05/28 19:41)