Các công thức tập hợp toán rời rạc

1.
2. phép toán trên quan hª
3. phép toán trên quan hª Cho các quan hª R1 và R2 t¯ t™p hÒp A ∏n t™p hÒp B. B i vì R1 ✓ A ⇥ B và R2 ✓ A ⇥ B nên cÙng có các quan hª sau t¯ A ∏n B. I R1 S R2 I R1 T R2 I R1 R2 I R2 R1
4. các quan hª R1 và R2 t¯ t™p hÒp A = {1, 2, 4, 5, a, b} ∏n t™p hÒp B = {a, b, 3, c, d} nh˜ sau R1 = {(2, a) , (a, a) , (b, c) , (2, 3) , (4, d)} , R2 = {(5, 3) , (4, b) , (4, d) , (b, b) , (2, 3)} . Khi ó R1 [ R2 = {(2, a) , (a, a) , (b, c) , (2, 3) , (4, d) , (5, 3) , (4, b) , (b, b)} , R1 R2 = {(2, 3) , (4, d)} , R1 R2 = {(2, a) , (a, a) , (b, c)} .
5. phép toán trên quan hª Cho R1 là mÎt quan hª t¯ t™p hÒp A ∏n t™p hÒp B và R2 là mÎt quan hª t¯ t™p hÒp B ∏n t™p hÒp C. Khi ó ta ‡nh nghæa quan hª hÒp R2 R1 t¯ t™p hÒp A ∏n t™p hÒp C nh˜ sau R2 R1 = (x, y) 2 A ⇥ C : 9z 2 B, (x, z) 2 R1 và (z, y) 2 R2 .
6. các t™p hÒp A = {(1, 2, 3, 4, a, b)} , B = {2, a, c, d, e} , C = {1, 2, 3, 5, a, b, c} . Xét quan hª R1 t¯ A ∏n B; R2 t¯ B ∏n C và R3 t¯ C ∏n A nh˜ sau R1 = {(1, a) , (4, 2) , (3, d) , (a, a) , (b, c)} , R2 = {(2, 1) , (2, 2) , (a, b) , (a, 5) , (c, b) , (d, 3)} , R3 = {(1, 1) , (3, a) , (b, 2) , (5, 4)} . 1 Tìm R2 R1 và R3 R2. 2 Tìm R3 (R2 R1) . 3 Tìm (R3 R2 R1)3 .
7. các t™p hÒp A = {(1, 2, 3, 4, a, b)} , B = {2, a, c, d, e} , C = {1, 2, 3, 5, a, b, c} . Xét quan hª R1 t¯ A ∏n B; R2 t¯ B ∏n C và R3 t¯ C ∏n A nh˜ sau R1 = {(1, a) , (4, 2) , (3, d) , (a, a) , (b, c)} , R2 = {(2, 1) , (2, 2) , (a, b) , (a, 5) , (c, b) , (d, 3)} , R3 = {(1, 1) , (3, a) , (b, 2) , (5, 4)} . Tr£ lÌi R2 R1 = {(1, b) , (1, 5) , (4, 1) , (4, 2) , (3, 3) , (a, b) , (a, 5) , (b, b)} , R3 R2 = {(2, 1) , (a, 2) , (a, 4) , (c, 2) , (d, a)} .
8. các t™p hÒp A = {(1, 2, 3, 4, a, b)} , B = {2, a, c, d, e} , C = {1, 2, 3, 5, a, b, c} . Xét quan hª R1 t¯ A ∏n B; R2 t¯ B ∏n C và R3 t¯ C ∏n A nh˜ sau R1 = {(1, a) , (4, 2) , (3, d) , (a, a) , (b, c)} , R2 = {(2, 1) , (2, 2) , (a, b) , (a, 5) , (c, b) , (d, 3)} , R3 = {(1, 1) , (3, a) , (b, 2) , (5, 4)} . Tr£ lÌi R3 (R2 R1) = {(1, 2) , (1, 4) , (4, 1) , (3, a) , (a, 2) , (a, 4) , (b, 2)} .
9. các t™p hÒp A = {(1, 2, 3, 4, a, b)} , B = {2, a, c, d, e} , C = {1, 2, 3, 5, a, b, c} . Xét quan hª R1 t¯ A ∏n B; R2 t¯ B ∏n C và R3 t¯ C ∏n A nh˜ sau R1 = {(1, a) , (4, 2) , (3, d) , (a, a) , (b, c)} , R2 = {(2, 1) , (2, 2) , (a, b) , (a, 5) , (c, b) , (d, 3)} , R3 = {(1, 1) , (3, a) , (b, 2) , (5, 4)} . Tr£ lÌi (R3 R2 R1)3 = {(1, 2) , (1, 4) , (4, 1) , (3, 1) , (a, 2) , (a, 4)} .
10. quan hª
11. quan hª b¨ng ma tr™n Cho R là mÎt quan hª t¯ t™p hÒp A = {a1, a2, . . . , am} ∏n t™p hÒp B = {b1, b2, . . . , bn}. Khi ó ma tr™n MR, bi∫u diπn cho quan hª R là mij = ( 1 n∏u (ai, bj) 2 R, 0 n∏u (ai, bj) /2 R. mij là ph¶n t˚ n¨m hàng i cÎt j cıa M
12. quan hª R t¯ t™p hÒp A = {a1, a2, a3, a4, a5} ∏n t™p hÒp B = {b1, b2, b3, b4} nh˜ sau R = {(a2, b3) , (a4, b4) , (a1, b2) , (a5, b4) , (a2, b1) , (a1, b1)} . Ma tr™n bi∫u diπn cho quan hª này là: MR = 2 6 6 6 6 4 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 3 7 7 7 7 5 5⇥4 .
13. ∫ l™p ma tr™n bi∫u diπn mÎt quan hª ta c¶n ph£i chø rõ th˘ t¸ các ph¶n t˚. Ví dˆ, muËn l™p ma tr™n bi∫u diπn quan hª t¯ t™p hÒp A = {a, 2, c, 1, e} ∏n t™p hÒp B = {1, 2, d, f, e}, ta c¶n chø rõ các ph¶n t˚ cıa A và B, âu là a1, a2, . . . âu là b1, b2, . . . t˜Ïng ˘ng. Chú ˛, vÓi các th˘ t¸ ßn ‡nh khác nhau thì ma tr™n bi∫u diπn quan hª có th∫ khác nhau. I Ma tr™n bi∫u diπn cho mÎt quan hª trên t™p hÒp A luôn là ma tr™n vuông.
14. hª R trên t™p hÒp A có ma tr™n bi∫u diπn 2 6 6 4 1 0 1 1 0 1 0 0 1 0 1 1 1 0 1 0 3 7 7 5 . Ph˜Ïng án nào sau ây úng cho quan hª R? 1 Ph£n x§ 2 Ëi x˘ng 3 Ph£n Ëi x˘ng 4 B≠c c¶u 5 V¯a ph£n x§ v¯a b≠c c¶u
15. các ma tr™n bi∫u diπn quan hª R1 và R2 trên t™p hÒp A (vÓi cùng mÎt th˘ t¸ ßn ‡nh cıa các ph¶n t˚ trên A), MR1 = 2 6 6 4 1 0 1 1 0 0 0 1 0 1 0 1 1 0 1 1 3 7 7 5 và MR2 = 2 6 6 4 0 1 0 0 1 0 1 0 0 1 0 0 1 1 1 1 3 7 7 5 . Ma tr™n 2 6 6 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 7 7 5 là ma tr™n bi∫u diπn quan hª nào trong các quan hª: R1 S R2; R1 T R2; R1 R2; R2 R1; R2 1?
16. quan hª b¨ng Á th‡ có h˜Óng Có th∫ bi∫u diπn mÎt quan hª trên t™p hÒp A b¨ng Á th‡ có h˜Óng. Ví dˆ. Bi∫u diπn quan hª R = {(a, b) , (a, c) , (a, d) , (b, b) , (b, c) , (b, d) , (c, d)} trên t™p hÒp A = {a, b, c, d, e} . a b c d e
17. Á th‡ bi∫u diπn mÎt quan hª trên t™p hÒp A nh˜ sau: a b c d e Quan hª này tho£ mãn tính chßt nào d˜Ói ây? 1 Ph£n x§ 2 Ëi x˘ng 3 Ph£n Ëi x˘ng 4 B≠c c¶u 5 Không ph£n x§, không Ëi x˘ng, không b≠c c¶u
18. cıa quan hª
19. ph£n x§ Cho R là mÎt quan hª trên t™p hÒp A (R có th∫ không ph£n x§). Bao óng ph£n x§ cıa R là mÎt quan hª R⇤ trên A, tho£ mãn Áng thÌi hai i∑u kiªn I R⇤ là ph£n x§ và R ✓ R⇤. I VÓi bßt k˝ quan hª R0 trên A, n∏u R0 cÙng ph£n x§ và R ✓ R0 thì ta ph£i có R⇤ ✓ R0. Nói mÎt cách khác, bao óng ph£n x§ cıa mÎt quan hª R là quan hª ph£n x§ nh‰ nhßt trong sË tßt c£ các quan hª ph£n x§ ch˘a R.
20. bao óng ph£n x§ cıa quan hª R = {(1, 2) , (2, 3) , (3, 4)} trên t™p hÒp A = {1, 2, 3, 4, 5} .
21. Ëi x˘ng Cho R là mÎt quan hª trên t™p hÒp A (R có th∫ không Ëi x˘ng). Bao óng Ëi x˘ng cıa R là mÎt quan hª R⇤ trên A, tho£ mãn Áng thÌi hai i∑u kiªn I R⇤ là Ëi x˘ng và R ✓ R⇤. I VÓi bßt k˝ quan hª R0 trên A, n∏u R0 cÙng Ëi x˘ng và R ✓ R0 thì ta ph£i có R⇤ ✓ R0. Nói mÎt cách khác, bao óng Ëi x˘ng cıa mÎt quan hª R là quan hª Ëi x˘ng nh‰ nhßt trong sË tßt c£ các quan hª Ëi x˘ng ch˘a R.
22. bao óng Ëi x˘ng cıa quan hª R = {(1, 2) , (2, 3) , (3, 4)} trên t™p hÒp A = {1, 2, 3, 4, 5} .
23. b≠c c¶u Cho R là mÎt quan hª trên t™p hÒp A (R có th∫ không b≠c c¶u). Bao óng b≠c c¶u cıa R là mÎt quan hª R⇤ trên A, tho£ mãn Áng thÌi hai i∑u kiªn I R⇤ là b≠c c¶u và R ✓ R⇤. I VÓi bßt k˝ quan hª R0 trên A, n∏u R0 cÙng b≠c c¶u và R ✓ R0 thì ta ph£i có R⇤ ✓ R0. Nói mÎt cách khác, bao óng b≠c c¶u cıa mÎt quan hª R là quan hª b≠c c¶u nh‰ nhßt trong sË tßt c£ các quan hª b≠c c¶u ch˘a R.
24. bao óng b≠c c¶u cıa quan hª R = {(1, 2) , (2, 3) , (3, 4)} trên t™p hÒp A = {1, 2, 3, 4, 5} .
25. quan hª R trên t™p hÒp A = {a, b, c, d} vÓi ma tr™n bi∫u diπn 2 6 6 4 a b c d a 1 1 0 0 b 1 0 0 1 c 0 0 1 0 d 0 1 1 0 3 7 7 5. Tìm bao óng b≠c c¶u cıa R.
26. th˘ t¸
27. th˘ t¸ MÎt quan hª R trên t™p hÒp A gÂi là quan hª th˘ t¸ n∏u nó tho£ mãn Áng thÌi I Ph£n x§. I Ph£n Ëi x˘ng. I B≠c c¶u.
28. t™p sË nguyên d˜Ïng Z+ xét quan hª R = n (x, y) 2 Z+ ⇥ Z+ : y x 2 Z o . Ta thßy R là mÎt quan hª th˘ t¸ trên Z+.
29. chú ˛ I N∏u R là mÎt quan hª th˘ t¸ trên t™p hÒp A, khi ó ng˜Ìi ta th˜Ìng thay th∏ k˛ hiªu a R b b i k˛ hiªu a b. I Khi R là mÎt quan hª th˘ t¸ trên t™p hÒp A, ng˜Ìi ta th˜Ìng nói t™p hÒp A cùng vÓi quan hª th˘ t¸ R (t˘c c∞p (A, R)) là mÎt poset. I N∏u (A, R) là mÎt poset và hai ph¶n t˚ bßt k˝ a, b 2 A ta ∑u có: (a, b) 2 R ho∞c (b, a) 2 R, thì t™p A ˜Òc gÂi là s≠p th˘ t¸ toàn ph¶n b i quan hª th˘ t¸ R.
30. t™p sË nguyên d˜Ïng Z+ xét các quan hª th˘ t¸ sau R1 = n (x, y) 2 Z+ ⇥ Z+ : y x 2 Z o , R2 = (x, y) 2 Z+ ⇥ Z+ : x y 0 . Khi ó poset (Z+, R1) không s≠p th˘ t¸ toàn ph¶n, poset (Z+, R2) s≠p th˘ t¸ toàn ph¶n.
31. ph¶n t˚ ∞c biªt trong poset Gi£ s˚ (A, R) là mÎt poset. I Ph¶n t˚ x 2 A gÂi là ph¶n t˚ tËi §i (maximal) cıa t™p hÒp A n∏u: không tÁn t§i a 2 A sao cho a 6= x và x a. I Ph¶n t˚ x 2 A gÂi là ph¶n t˚ tËi ti∫u (minimal) cıa t™p hÒp A n∏u: không tÁn t§i a 2 A sao cho a 6= x và a x.
32. t™p hÒp A = {2, 3, 4, 6, 7, 9, 13} và quan hª th˘ t¸ R trên t™p hÒp A nh˜ sau: R = n (x, y) 2 A ⇥ A : y x 2 Z o . Ph¶n t˚ nào là ph¶n t˚ tËi §i, ph¶n t˚ nào là ph¶n t˚ tËi ti∫u trên t™p hÒp A?
33. t™p hÒp A = {2, 3, 4, 6, 7, 9, 13} và quan hª th˘ t¸ R trên t™p hÒp A nh˜ sau: R = n (x, y) 2 A ⇥ A : y x 2 Z o . Ph¶n t˚ nào là ph¶n t˚ tËi §i, ph¶n t˚ nào là ph¶n t˚ tËi ti∫u trên t™p hÒp A? Tr£ lÌi I Ph¶n t˚ tËi §i là: 4, 6, 7, 9, 13. I Ph¶n t˚ tËi ti∫u là: 2, 3, 7, 13.
34. ph¶n t˚ ∞c biªt trong poset Gi£ s˚ (A, R) là mÎt poset. I Ph¶n t˚ x 2 A gÂi là ph¶n t˚ lÓn nhßt cıa t™p hÒp A n∏u: vÓi mÂi a 2 A, ta luôn có a x. I Ph¶n t˚ x 2 A gÂi là ph¶n t˚ nh‰ nhßt cıa t™p hÒp A n∏u: vÓi mÂi a 2 A, ta luôn có x a.
35. t™p hÒp A = {2, 3, 4, 6, 7, 9, 252} và quan hª th˘ t¸ R trên t™p hÒp A nh˜ sau: R = n (x, y) 2 A ⇥ A : y x 2 Z o . Ph¶n t˚ nào là ph¶n t˚ lÓn nhßt, ph¶n t˚ nào là ph¶n t˚ nh‰ nhßt trên t™p hÒp A?
36. t™p hÒp A = {2, 3, 4, 6, 7, 9, 252} và quan hª th˘ t¸ R trên t™p hÒp A nh˜ sau: R = n (x, y) 2 A ⇥ A : y x 2 Z o . Ph¶n t˚ nào là ph¶n t˚ lÓn nhßt, ph¶n t˚ nào là ph¶n t˚ nh‰ nhßt trên t™p hÒp A? Tr£ lÌi I Ph¶n t˚ lÓn nhßt là: 252. I Không tÁn t§i ph¶n t˚ nh‰ nhßt.
37. ph¶n t˚ ∞c biªt trong poset Gi£ s˚ (A, R) là mÎt poset và B ✓ A. I Ph¶n t˚ x 2 A gÂi là c™n trên cıa t™p hÒp B n∏u: vÓi mÂi b 2 B, ta luôn có b x. I Ph¶n t˚ x 2 A gÂi là c™n d˜Ói cıa t™p hÒp B n∏u: vÓi mÂi b 2 B, ta luôn có x b.
38. t™p hÒp A = {2, 3, 4, 6, 7, 9, 252} và quan hª th˘ t¸ R trên t™p hÒp A nh˜ sau: R = n (x, y) 2 A ⇥ A : y x 2 Z o . Các ph¶n t˚ nào là c™n trên, c™n d˜Ói cıa t™p hÒp B = {2, 4, 7}?
39. t™p hÒp A = {2, 3, 4, 6, 7, 9, 252} và quan hª th˘ t¸ R trên t™p hÒp A nh˜ sau: R = n (x, y) 2 A ⇥ A : y x 2 Z o . Các ph¶n t˚ nào là c™n trên, c™n d˜Ói cıa t™p hÒp B = {2, 4, 7}? Tr£ lÌi I C™n trên cıa t™p hÒp B là: 252. I Không có c™n d˜Ói cıa t™p hÒp B.
40. ph¶n t˚ ∞c biªt trong poset Gi£ s˚ (A, R) là mÎt poset và B ✓ A. I Ph¶n t˚ x 2 A gÂi là c™n trên nh‰ nhßt cıa t™p hÒp B n∏u: x là c™n trên cıa t™p hÒp B và vÓi mÂi c™n trên y bßt k˝ cıa B ta ∑u có x y. I Ph¶n t˚ x 2 A gÂi là c™n d˜Ói lÓn nhßt cıa t™p hÒp B n∏u: x là c™n d˜Ói cıa t™p hÒp B và vÓi mÂi c™n d˜Ói y bßt k˝ cıa B ta ∑u có y x.
41. t™p hÒp A = {2, 4, 6, 7, 12, 30, 60, 90, 100, 360, 540} và quan hª th˘ t¸ R trên t™p hÒp A nh˜ sau: R = n (x, y) 2 A ⇥ A : y x 2 Z o . Ph¶n t˚ nào là c™n trên nh‰ nhßt, c™n d˜Ói lÓn nhßt cıa t™p hÒp B = {60, 90} .
42. t™p hÒp A = {2, 4, 6, 7, 12, 30, 60, 90, 100, 360, 540} và quan hª th˘ t¸ R trên t™p hÒp A nh˜ sau: R = n (x, y) 2 A ⇥ A : y x 2 Z o . Ph¶n t˚ nào là c™n trên nh‰ nhßt, c™n d˜Ói lÓn nhßt cıa t™p hÒp B = {60, 90} . Tr£ lÌi I Không có c™n trên nh‰ nhßt cıa t™p hÒp B. I C™n d˜Ói lÓn nhßt cıa t™p hÒp B là 30.
43. chú ˛ I Ph¶n t˚ lÓn nhßt, ph¶n t˚ nh‰ nhßt cıa mÎt poset có th∫ không tÁn t§i. Tuy nhiên nó là duy nhßt n∏u tÁn t§i, t˘c là không th∫ có hai ph¶n t˚ khác nhau Áng thÌi là ph¶n t˚ lÓn nhßt, cÙng v™y cho ph¶n t˚ nh‰ nhßt. I N∏u mÎt poset có ph¶n t˚ lÓn nhßt thì ph¶n t˚ này cÙng là ph¶n t˚ tËi §i. T˜Ïng t¸, n∏u mÎt poset có ph¶n t˚ nh‰ nhßt thì ph¶n t˚ này cÙng là ph¶n t˚ tËi ti∫u. I Ph¶n t˚ tËi §i hay ph¶n t˚ tËi ti∫u cıa mÎt poset có th∫ không duy nhßt. Tuy nhiên n∏u poset có ph¶n t˚ lÓn nhßt thì nó chø có duy nhßt mÎt ph¶n t˚ tËi §i, t˜Ïng t¸ n∏u poset ch˘a ph¶n t˚ nh‰ nhßt thì nó chø có duy nhßt mÎt ph¶n t˚ tËi ti∫u. I C™n trên, c™n d˜Ói cıa mÎt t™p hÒp B trong mÎt poset có th∫ không tÁn t§i, không duy nhßt. I C™n trên nh‰ nhßt, c™n d˜Ói lÓn nhßt cıa mÎt t™p hÒp B trong mÎt poset có th∫ không tÁn t§i, nh˜ng n∏u tÁn t§i thì duy nhßt.
44. chú ˛ I MÎt poset có h˙u h§n ph¶n t˚ thì luôn tÁn t§i ít nhßt mÎt ph¶n t˚ tËi §i và ít nhßt mÎt ph¶n t˚ tËi ti∫u trong poset ó. I MÎt poset có h˙u h§n ph¶n t˚, n∏u có úng mÎt ph¶n t˚ tËi §i thì nó tÁn t§i ph¶n t˚ lÓn nhßt (ph¶n t˚ lÓn nhßt là ph¶n t˚ tËi §i ó). T˜Ïng t¸, mÎt poset có h˙u h§n ph¶n t˚, n∏u có úng mÎt ph¶n t˚ tËi ti∫u thì nó tÁn t§i ph¶n t˚ nh‰ nhßt (ph¶n t˚ nh‰ nhßt là ph¶n t˚ tËi ti∫u ó).
45. chú ˛ I MÎt poset có h˙u h§n ph¶n t˚ thì luôn tÁn t§i ít nhßt mÎt ph¶n t˚ tËi §i trong poset ó. Ch˘ng minh Lßy ph¶n t˚ x1 2 A tu˝ ˛. N∏u x1 là ph¶n t˚ tËi §i thì ta có i∑u ph£i ch˘ng minh. N∏u x1 không tËi §i thì ph£i tÁn t§i x2 2 A sao cho: x2 6= x1 và x1 x2. N∏u x2 là ph¶n t˚ tËi §i thì ta có i∑u ph£i ch˘ng minh, ng˜Òc l§i ph£i tÁn t§i ph¶n t˚ x3 2 A sao cho: x3 6= x2 và x2 x3. Chú ˛, ta cÙng có x3 6= x1 vì n∏u không thì d®n ∏n x1 = x2. C˘ nh˜ v™y, n∏u ta không tìm ˜Òc ph¶n t˚ tËi §i thì ta xây d¸ng ˜Òc dãy x1 x2 . . . và xi 6= xj n∏u i 6= j. Mâu thu®n vÓi tính chßt h˙u h§n cıa t™p A.
46. chú ˛ I MÎt poset có h˙u h§n ph¶n t˚, n∏u có úng mÎt ph¶n t˚ tËi §i thì nó tÁn t§i ph¶n t˚ lÓn nhßt (ph¶n t˚ lÓn nhßt là ph¶n t˚ tËi §i ó). Ch˘ng minh Gi£ s˚ x 2 A là ph¶n t˚ tËi §i duy nhßt cıa A. Ta ch˘ng minh x là ph¶n t˚ lÓn nhßt cıa A. Gi£ s˚ ng˜Òc l§i, khi ó tÁn t§i x1 2 A sao cho x1 6 x. D®n ∏n x1 6= x, v™y x1 không là ph¶n t˚ tËi §i cıa A. Do ó tÁn t§i x2 2 A sao cho: x2 6= x1 và x1 x2. Lúc này ta cÙng thßy x2 6= x. Do ó x2 không là ph¶n t˚ tËi §i cıa A, i∑u này d®n ∏n tÁn t§i x3 2 A sao cho: x3 6= x2 và x2 x3. Ta cÙng thßy x3 6= x, vì n∏u không thì d®n ∏n x1 x. C˘ nh˜ v™y, ta xây d¸ng ˜Òc dãy x1 x2 . . . và xi 6= xj n∏u i 6= j. Mâu thu®n vÓi tính chßt h˙u h§n cıa t™p A.

Các công thức tập hợp toán rời rạc

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Toplist được quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội