課程名稱︰離散數學
課程性質︰選修
課程教師︰陳健輝
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2015.05.15
考試時限（分鐘）：150分鐘
試題 :
Examination # 2 - "The Night Of History"
(範圍: Algebra)
1. The following are five binary relations on {1, 2, 3, 4}.
R1 = {(1, 1), (2, 2), (3, 3), (4, 4)}.
R2 = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 1)}.
R3 = {(1, 2), (2, 1), (3, 4), (4, 3)}.
R4 = {(1, 2), (1, 3), (2, 3), (3, 4)}.
R5 = {(1, 1), (2, 2), (2, 3), (3, 4), (2, 4)}.
(a) which are equivalence relation? (5%)
(b) which are partial ordering? (5%)
2. Find all x's satisfying x ≡ 5^10 mod 100. (10%)
3. For R = {s, t, x, y}, define + and ·, making R into a ring, by Table 1
for + and by the partial table for · in Table 2.
Table 1 Table 2
┌─┬────┐ ┌─┬────┐
│ +│ s t x y│ │ ·│ s t x y│
├─┼────┤ ├─┼────┤
│ s│ s t x y│ │ s│ s s s s│
│ t│ t s y x│ │ t│ s t ? ?│
│ x│ x y s t│ │ x│ s t ? y│
│ y│ y x t s│ │ y│ s ? s ?│
└─┴────┘ └─┴────┘
(a) Determine the values of the entries? in Table 2 by the aid of the
associative and distributive laws. (5%)
(b) Is the ring an integral domain or a field? Why? (5%)
4. Suppose that R_1, R_2 are two binary relations on {1, 2, ..., n} and
R_1 ⊆ R_2. Determine whether the following two statements are true or
false and give your reasons.
(a) If R_1 is reflexive, then R_2 is reflexive. (5%)
(b) If R_1 is symmetric, then R_2 is symmetric. (5%)
5. Explain why there is no equivalence relation R on {1, 2, ..., 7} with
(a) |R| = 6 and
(b) |R| = 22. (10%)
6. Suppose that (G, ·) is a cyclic group and H≠{e} is a subgroup of G.
Assume G = <a>. Find and verify a generator of H, expressed by a. (10%)
7. Let (K, ·, +) be a Boolean algebra. The following is a proof of
a·(a + b) = a for every a, b ∈ K.
a·(a + b) = (a·a) + (a·b) = a + (a·b) = (a·1) + (a·b)
= a·(1 + b) = a·1 = a.
Please prove a + (a·b) = a for every a, b ∈ K. (10%)
8. Prove that 2^(1/2) is irrational using the fact that for any positive
integer k, if k^2 is even, then k is even. (10%)
9. Suppose that G is a group and H (≠{e} and ≠G) is a subgroup of G. If
|G| = 2p, where p is a prime number, prove that H is cyclic. (10%)
10. Show that a unit in a ring R cannot be a proper divisor of zero. (10%)
11. Suppose that (R, +, ·) is a ring and S is a finite (nonempty) subset of R.
Show that (S, +, ·) is a ring, if for all a, b ∈ S, a + b ∈ S and
a · b ∈ S. (hint: you should show z ∈ S and then -a ∈ S). (10%)
12. Let f: G → H be a group homomorphism. Prove that for each a ∈ G,
|<f(a)>| divides |<a>|. (10%)