課程名稱︰離散數學
課程性質︰資訊系選修
課程教師︰陳健輝
開課學院：電資學院
開課系所︰資訊系
考試日期（年月日）︰2013/05/08
考試時限（分鐘）：150
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
Examination #2
(範圍: Algebra)
1. The following are two logic circuits and an incomplete proof for their
functional equivalence, i.e., they produce the same output, when fed with
the same input. Please complete the proof. (10%)
_ _ _ _ _ _ _ _ _ _ _ _
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 ( z (1 + y) + y z) + w x ( y (1 + z) + y z)
= ...
_ _ _ _ _ _
= w x z + w x y + w x y + w x z
(題目有附圖，但不影響作答。)
2. Is the following argument correct or wrong? Why? (10%)
Suppose that R is a binary relation on a non-empty set A.
If R is symmetric and transitive, then R is reflexive.
Proof. Let (x, y) ∈ R. By the symmetric property , we have (y, x) ∈ R.
Then, with (x, y), (y, x) ∈ R , it follows by the transitive
property that we have (x, x) ∈ R , As a consequence, R is reflexive.
3. Is there an equivalence relation R on A = {1,2,3, 4,5, 6, 7} with
(a) |R| = 11 and (b) |R| = 22 ?
Construct any if it exists, or explain why it does not exist. (10%)
4. Let A = {(0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0)}. Define a partial
ordering ⊂ on A as follows: (a,b) ⊂ (c,d) if a ≦ c and b ≦ d.
(a) Draw the corresponding Hasse diagram. (5%)
(b) Give a topological order of the elements of A. (5%)
5. Suppose that (R , + , ‧) is a ring with unity and x is a nonzero element
of R. Prove that
(a) the unity is unique
(b) the multiplicative inverse of x is unique. (10%)
6. Consider + the ordinary addition and ‧ the ordinary multiplication.
Which of Z, Q, R, C are (a) integral domains and (b) fields?
7. Suppose that (R, +, ‧) is a ring and S is a nonempty subset of R. With the
fact that (S, +, ‧) is a ring if and only if a + b, a‧b, - a ∈ S , S for
all a, b ∈ S , show that when S is finite, (S, +, ‧) is a ring if and only
if a + b, a‧b ∈ S for all a, b ∈ S. (Hints: show z ∈ S first). (10%)
8. Determine whether [a] has a multiplicative inverse or is a proper zero
divisor in Z_n when (a,n) = (a) (17,96) and (b) (36,96). Also find [a]^-1
if [a] has a multiplicative inverse, and find [b] (≠ [0]) with
[a]‧[b] = [0] if [a] is a proper zero divisor. (10%)
9. Suppose that (R, +, ‧) and (S, ⊕, ⊙) are two rings.
(a) What is a homomorphism from R to S ?
(b) What is the intuitive meaning of such a homomorphism ?
10. In the last night of 赤壁之戰, 諸葛亮 intended to send messages p1, p2, p3
to 風神 through the following procedure, while 周瑜 was the intruder.
Step 1: 風神 generated three relatively prime integers m1, m2, m3 (the
decryption keys).
Step 2: 風神 broadcast e1, e2, e3 (the encryption keys) and M, which were
calculated as follows.
M = m1 x m2 x m3.
(M1, M2, M3) = (M/m1, M/m2, M/m3).
M_i x x_i ≡ 1(mod mi) for i = 1,2,3
e_i = M_i x x_i for i = 1,2,3
Step 3: 諸葛亮 broadcast C, where C ≡ (p1 x e1 + p2 x e2 + p3 x e3)
(mod M) and 0 ≦ C < M.
Step 4: 風神 got p1, p2, p3 from C, where p1 ≡ C (mod m1),
p2 ≡ C (mod m2), and p3 ≡ C (mod m3)
Now that it was possible for 周瑜 to get e1, e2, e3, M, C (because they were
on the air), how did 諸葛亮 and 風神 prevent 周瑜 from finding out
p1, p2, p3? (10%)
11. Suppose that (G,．) is a cyclic group. Show that G is isomorphic to
(Z_n, +), where n = |G|. (10%)
12. Suppose that (G,．) is a group with |G| > 1. Explain why G is cyclic,
if |G| is prime. (10%)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.4.195
※ 編輯: benny9072004 來自: 140.112.4.195 (06/28 17:50)