toan

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (352.88 KB, 20 trang )

(1)TRƯỜNG ĐẠI HỌC ĐAØ LẠT KHOA TOÁN - TIN HỌC Y Z. PHAÏM TIEÁN SÔN. TOÁN RỜI RẠC 1 (Baøi Giaûng Toùm Taét). -- Lưu hành nội bộ -Y Đà Lạt 2008 Z.

(2) Mu.c lu.c ˙’. D -` MO ÂU. iv. . 1 TÂ . . P HO . P VÀ ÁNH XA 1.1. 1.2. 1. Tâ.p ho..p . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 1. 1.1.1. Khái niê.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 1. 1.1.2. Các phép toán trên tâ.p ho..p . . . . . . . . . . . . . . . . . . . . . . .. 3. 1.1.3. Tı́ch Descartes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 5. Ánh xa. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 8. 1.2.1. - i.nh nghı̃a và tı́nh châ´t . . . . . . . . . . . . . . . . . . . . . . . . . D. 8. 1.2.2. Ánh xa. ha.n chê´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 10. 1.2.3. Ho..p cu̇’a các ánh xa. . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 11. 1.2.4. Ánh xa. ngu.o..c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 12. 1.2.5. Lu..c lu.o..ng cu̇’a mô.t tâ.p ho..p . . . . . . . . . . . . . . . . . . . . . . .. 12. . . . 2 LOGIC VÀ CÁC PHU O NG PHÁP CHÚ NG MINH. 17. 2.1. ` . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mê.nh d̄ê. 17. 2.2. ` có d̄iê ` u kiê.n và các mê.nh d̄ê ` tu.o.ng d̄u.o.ng . . . . . . . . . . . . . . Mê.nh d̄ê. 20. 2.3. Lu.o..ng hóa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 23. 2.4. Phu.o.ng pháp chú.ng minh . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 26. i.

(3) 2.5. Quy na.p toán ho.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 3 THUÂ . T TOÁN. 31 33. `u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mo˙’. d̄â. 33. 3.1.1. Tı̀m sô´ ló.n nhâ´t trong ba sô´ . . . . . . . . . . . . . . . . . . . . . . .. 33. 3.1.2. Tı̀m sô´ ló.n nhâ´t trong dãy hũ.u ha.n các sô´ thu..c . . . . . . . . . . . .. 33. Thuâ.t toán Euclid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 35. 3.2.1. Thuâ.t toán Euclid . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 37. Thuâ.t toán d̄ê. quy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 39. 3.3.1. Tı́nh n giai thù.a . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 39. 3.3.2. Tı̀m u.ó.c sô´ chung ló.n nhâ´t . . . . . . . . . . . . . . . . . . . . . . .. 40. 3.3.3. Thuâ.t toán xác d̄i.nh dãy Fibonacci . . . . . . . . . . . . . . . . . . .. 41. 3.4. - ô. phú.c ta.p cu̇’a thuâ.t toán . . . . . . . . . . . . . . . . . . . . . . . . . . . D. 43. 3.5. Phân tı́ch thuâ.t toán Euclid . . . . . . . . . . . . . . . . . . . . . . . . . . .. 48. 3.1. 3.2. 3.3. ´M - Ê 4 PHÉP D. 51. Các nguyên lý co. bȧ’n cu̇’a phép d̄ê´m . . . . . . . . . . . . . . . . . . . . . .. 51. 4.1.1. Nguyên lý tô˙’ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 51. 4.1.2. Nguyên lý tı́ch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 52. 4.1.3. Nguyên lý bao hàm-loa.i trù. . . . . . . . . . . . . . . . . . . . . . . .. 54. 4.2. Hoán vi. và tô˙’ ho..p . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 57. 4.3. Các thuâ.t toán sinh ra hoán vi. và tô˙’ ho..p . . . . . . . . . . . . . . . . . . . .. 62. 4.4. Hoán vi. và tô˙’ ho..p suy rô.ng . . . . . . . . . . . . . . . . . . . . . . . . . . .. 66. 4.5. ` ng nhâ´t thú.c . . . . . . . . . . . . . . . . . . . Hê. sô´ cu̇’a nhi. thú.c và các d̄ô. 73. 4.6. ` ng chim bô ` câu . . . . . . . . . . . . . . . . . . . . . . . . . . Nguyên lý chuô. 77. ` ng chim bô ` câu (da.ng thú. nhâ´t) . . . . . . . . . . . . Nguyên lý chuô. 77. 4.1. 4.6.1. ii.

(4) 4.6.2. ` ng chim bô ` câu (da.ng thú. hai) . . . . . . . . . . . . . Nguyên lý chuô. 78. 4.6.3. ` ng chim bô ` câu (da.ng thú. ba) . . . . . . . . . . . . . Nguyên lý chuô. 80. 5 QUAN HÊ .. 85. 5.1. Quan hê. hai ngôi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 85. 5.2. Quan hê. và ma trâ.n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 90. 5.3. Quan hê. thú. tu.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 96. 5.4. Quan hê. tu.o.ng d̄u.o.ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104. 5.5. Bao d̄óng cu̇’a quan hê. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110. 5.6. Lattice cu̇’a các phân hoa.ch . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 5.6.1. Thuâ.t toán xác d̄i.nh hô.i cu̇’a hai phân hoa.ch . . . . . . . . . . . . . 118. 5.6.2. Thuâ.t toán xác d̄i.nh tuyê˙’n cu̇’a hai phân hoa.ch . . . . . . . . . . . . 119. ´ -A 6 D . I SÔ BOOLE. 123. 6.1. Lattice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123. 6.2. Lattice phân bô´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132. 6.3. - a.i sô´ Boole . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 D. 6.4. Hàm Boole. 6.5. Biê˙’u diê˜n các hàm Boole qua hê. tuyê˙’n, hô.i và phu̇’ d̄i.nh . . . . . . . . . . . 149. 6.6. Biê˙’u diê˜n tô´i thiê˙’u cu̇’a hàm Boole . . . . . . . . . . . . . . . . . . . . . . . 152. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145. 6.6.1. Khái niê.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152. 6.6.2. ` Karnaugh . . . . . . . . . . . . . . . . . . . . . 153 Phu.o.ng pháp bȧ’n d̄ô. ´N TÍNH 7 MÃ TUYÊ 7.1. 159. ` u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 Mo˙’. d̄â 7.1.1. Khái niê.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 iii.

(5) 7.1.2. Mã phát hiê.n lô˜i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160. 7.1.3. Mã su˙’.a sai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161. 7.2. Các khái niê.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162. 7.3. Khoȧ’ng cách Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170. 7.4. Hô.i chú.ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 7.4.1. Giȧ’i mã dùng bȧ’ng chuâ˙’n . . . . . . . . . . . . . . . . . . . . . . . . 179. 7.5. Mã hoàn hȧ’o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182. 7.6. Mã Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184. Tài liê.u tham khȧ’o. 189. iv.

(6) ˙’. D -` ÂU MO Toán ho.c rò.i ra.c là mô.t bô. phâ.n cu̇’a Toán ho.c nhǎ` m nghiên cú.u các d̄ô´i tu.o..ng rò.i ra.c: ` có liên quan nghiên cú.u các câ´u trúc rò.i ra.c khác nhau và các phu.o.ng pháp giȧ’i các vâ´n d̄ê d̄ê´n các câ´u trúc này. Thông tin lu.u trũ. và vâ.n hành trong máy tı́nh du.ó.i da.ng các tı́n hiê.u rò.i ra.c (các máy tı́nh liên tu.c chı̇’ là các máy tı́nh tu.o.ng tu.., chuyên du.ng). Vı̀ vâ.y công cu. dùng d̄ê˙’ biê˙’u diê˜n thông tin trong máy và xu˙’. lý các thông tin này là Toán ho.c rò.i ra.c. Ngoài ra, các phu.o.ng pháp và kê´t quȧ’ cu̇’a Toán ho.c rò.i ra.c có thê˙’ dùng d̄ê˙’ giȧ’i quyê´t tru..c ` u vâ´n d̄ê ` d̄ǎ.t ra cu̇’a Tin ho.c nhu. logic, hàm d̄a.i sô´ logic, tô˙’ ho..p trên tù.... Toán tiê´p nhiê `u ho.c rò.i ra.c chuâ˙’n bi. sǎ˜n và cung câ´p các công cu., phu.o.ng pháp luâ.n d̄ê˙’ giȧ’i quyê´t nhiê ` cu̇’a Tin ho.c. Có thê˙’ nói Toán ho.c rò.i ra.c là ngành Toán ho.c co. so˙’. cho Tin ho.c. vâ´n d̄ê ` u d̄i vào Mu.c d̄ı́ch cu̇’a giáo trı̀nh nhǎ` m cung câ´p mô.t sô´ công cu. Toán ho.c d̄ê˙’ bu.ó.c d̄â . . . ´ ` cu. thê˙’. ’ Tin ho.c. Giáo trı̀nh d̄u o. c trı̀nh bày mô.t cách dàn trȧi ho n là d̄i sâu vào mô.t vâ n d̄ê . . ` n có các bài tâ.p nhǎ` m cu̇’ng cô´ nhũ ng kiê´n thú c d̄ã ho.c. Hy vo.ng rǎ` ng giáo Cuô´i mô˜i phâ ` n nào yêu câ ` u ho.c tâ.p cu̇’a các ba.n sinh viên. trı̀nh này d̄áp ú.ng d̄u.o..c phâ - à La.t, ngày 11 tháng 2 nǎm 2008 D Pha.m Tiê´n So.n. v.

(7) vi.

(8) Chu.o.ng 1 . TÂ . P VÀ ÁNH XA . . P HO 1.1 1.1.1. Tâ.p ho..p Khái niê.m. Mô.t khái niê.m co. bȧ’n cu̇’a toán ho.c hiê.n d̄a.i là khái niê.m tâ.p ho..p. Cũng giô´ng nhu. d̄iê˙’m, d̄oa.n thǎ˙’ng, mǎ.t phǎ˙’ng, ... trong hı̀nh ho.c Euclid, khái niê.m tâ.p ho..p không d̄u.o..c d̄i.nh nghı̃a mà chı̇’ d̄u.o..c mô tȧ’ bǎ` ng nhũ.ng vı́ du.. Chǎ˙’ng ha.n, tâ.p ho..p các sách trong thu. viê.n, tâ.p ho..p các sô´ thu..c, tâ.p ho..p các d̄a thú.c bâ.c hai, v.v... ` n tu˙’. cu̇’a tâ.p ho..p â´y. Có hai cách xác d̄i.nh Các vâ.t ta.o nên mô.t tâ.p ho..p go.i là các phâ . mô.t tâ.p ho. p: ` n tu˙’. cu̇’ a nó. Chǎ˙’ng ha.n, tâ.p ho..p gô ` m các phâ ` n tu˙’. a, b, c, d (a) Liê.t kê danh sách các phâ . . . . thu ò ng d̄u o. c viê´t {a, b, c, d}. ` n tu˙’. cu̇’ a tâ.p ho..p. Chǎ˙’ng ha.n, tâ.p ho..p {1, 3} (b) Nêu lên tı́nh châ´t d̄ǎ.c tru.ng cu̇’ a các phâ . . có thê˙’ mô tȧ’ là tâ.p ho. p hai sô´ tu. nhiên lė’ nhȯ’ nhâ´t hay tâ.p ho..p các nghiê.m cu̇’a phu.o.ng trı̀nh bâ.c hai x2 − 4x + 3 = 0. ` n tu˙’. cu̇’a tâ.p ho..p A. Khi x không Ký hiê.u x ∈ A (và d̄o.c là x thuô.c A) có nghı̃a x là phâ ` n tu˙’. cu̇’a tâ.p ho..p A ta viê´t x 6∈ A (và d̄o.c là x không thuô.c A). Chǎ˙’ng ha.n, nê´u phȧ’i là phâ go.i N là tâ.p các sô´ tu.. nhiên thı̀ 7 ∈ N nhu.ng 12 6∈ N. 5 - ê˙’ d̄o.n giȧ’n, d̄ôi khi ta chı̇’ dùng tù. “tâ.p” thay cho cu.m tù. “tâ.p ho..p”. Chú ý 1. (a) D (b) Ký hiê.u := thu.ò.ng dùng d̄ê˙’ d̄u.a vào d̄i.nh nghı̃a, nó thay cho cu.m tù. “d̄i.nh nghı̃a bo˙’.i”. Chǎ˙’ng ha.n, N := {0, 1, 2, . . .}. 1.

(9) (c) Ta thu.ò.ng dùng ký hiê.u | d̄ê˙’ diê˜n d̄a.t ý “sao cho” (hoǎ.c “trong d̄ó”). Chǎ˙’ng ha.n, tâ.p ho..p tâ´t cȧ’ các sô´ tu.. nhiên chǎ˜n có thê˙’ mô tȧ’ nhu. sau: {n ∈ N | n chia hê´t cho 2}. Vı́ du. 1.1.1. Mô.t vài tâ.p ho..p sô´ thu.ò.ng gǎ.p: (a) Tâ.p ho..p các sô´ tu.. nhiên N := {0, 1, 2, . . .}. (b) Tâ.p ho..p các sô´ nguyên du.o.ng P := {1, 2, . . .}. (c) Tâ.p ho..p các sô´ nguyên Z := {0, 1, −1, 2, −2, . . .}. (d) Tâ.p ho..p các sô´ hũ.u tı̇’ Q := { pq | p, q ∈ Z, q 6= 0}. (e) Tâ.p ho..p các sô´ thu..c R. √ (f) Tâ.p ho..p các sô´ phú.c C := {a + −1b | a, b ∈ R}. ` n tu˙’. nào cȧ’ go.i là tâ.p ho..p trô´ng (hay rô˜ng) và d̄u.o..c ký hiê.u là Mô.t tâ.p ho..p không có phâ . ` m các nghiê.m sô´ thu..c cu̇’a phu.o.ng trı̀nh bâ.c hai x2 + 1 = 0 là mô.t ∅. Chǎ˙’ng ha.n tâ.p ho. p gô tâ.p ho..p trô´ng. ` n tu˙’. cu̇’a tâ.p ho..p B d̄ê ` u là Tâ.p ho..p B go.i là tâ.p ho..p con cu̇’a tâ.p ho..p A nê´u mo.i phâ . . . . . ` n tu˙’ cu̇’a tâ.p ho. p A; trong tru ò ng ho. p này ta ký hiê.u B ⊆ A hay A ⊇ B. Hiê˙’n nhiên phâ A ⊆ A. Ho.n nũ.a, d̄ê˙’ thuâ.n tiê.n, ta thu.ò.ng coi tâ.p ho..p trô´ng là mô.t tâ.p ho..p con cu̇’a tâ.p ` ng nhau nê´u B ⊆ A bâ´t kỳ, tú.c là ∅ ⊆ A vó.i mo.i tâ.p ho..p A. Hai tâ.p ho..p A và B go.i là bǎ . và A ⊆ B; khi d̄ó ta viê´t A = B. Nê´u B ⊆ A nhu ng A 6= B ta nói B là tâ.p ho..p con thu..c su.. cu̇’a tâ.p ho..p A và viê´t B A. Vı́ du. 1.1.2. (a) Nê´u A := {x ∈ R | x2 + x − 6 = 0},. B := {2, −3}. thı̀ A = B. (b) Ta có các bao hàm thú.c thu..c su.. sau P. N. Z. Q. R.. ` n tu˙’. cu̇’a nó là nhũ.ng tâ.p ho..p thu.ò.ng d̄u.o..c go.i là mô.t ho. các tâ.p Mô.t tâ.p ho..p mà phâ ho..p, hoǎ.c mô.t hê. các tâ.p ho..p. Nói cách khác, “tâ.p ho..p”, “ho.”, “hê.” là nhũ.ng thuâ.t ngũ. ` ng nghı̃a. d̄ô - ê˙’ nêu lên danh sách các tâ.p ho..p cu̇’a mô.t ho. tâ.p ho..p A, ta hãy go.i mô˜i tâ.p ho..p cu̇’a A D là Ai; ký hiê.u i d̄u.o..c go.i là chı̇’ sô´ d̄ê˙’ d̄ánh dâ´u tâ.p ho..p â´y, hai tâ.p ho..p khác nhau cu̇’a ho. 2.

(10) A d̄u.o..c d̄ánh d̄ánh dâ´u các. dâ´u bo˙’.i hai chı̇’ sô´ khác nhau. Nê´u I là tâ.p ho..p tâ´t cȧ’ các chı̇’ sô´ d̄ã dùng d̄ê˙’ tâ.p ho..p cu̇’a ho. A thı̀ ta có thê˙’ viê´t A := {Ai | i ∈ I},. hay A := {Ai}i∈I . ` n tu˙’. cu̇’a mô.t tâ.p ho..p Cũng có thê˙’ su˙’. du.ng phu.o.ng pháp này d̄ê˙’ d̄ánh dâ´u tâ´t cȧ’ các phâ A tùy ý.. 1.1.2. Các phép toán trên tâ.p ho..p. Cho tru.ó.c các tâ.p A và B ta có thê˙’ thành lâ.p các tâ.p mó.i bǎ` ng các phép toán sau: - i.nh nghı̃a 1.1.1. Ho..p cu̇’a hai tâ.p A và B là mô.t tâ.p ho..p, ký hiê.u A ∪ B, gô ` m tâ´t cȧ’ các D . ` n tu˙’ hoǎ.c thuô.c A hoǎ.c thuô.c B (hoǎ.c thuô.c cȧ’ hai). phâ ` m tâ´t cȧ’ các phâ ` n tu˙’. vù.a Giao cu̇’a hai tâ.p A và B là mô.t tâ.p ho..p, ký hiê.u A ∩ B, gô thuô.c A vù.a thuô.c B. ` m tâ´t cȧ’ các phâ `n Hiê.u cu̇’a tâ.p ho..p A vó.i tâ.p ho..p B là mô.t tâ.p ho..p, ký hiê.u A \ B, gô . tu˙’ thuô.c A nhu.ng không thuô.c B. Hiê.u d̄ô´i xú.ng cu̇’a hai tâ.p ho..p A và B là tâ.p ho..p A ∆ B := (A \ B) ∪ (B \ A). Nhâ.n xét 1. (a) Mô.t cách tu.o.ng tu.., có thê˙’ d̄i.nh nghı̃a ho..p ∪i∈I Ai và giao ∩i∈I Ai cu̇’a mô.t ho. tâ.p ho..p A := {Ai | i ∈ I}. (b) Ta luôn có A ∆ B = B ∆ A. Nhu.ng nhu. vı́ du. du.ó.i d̄ây chı̇’ ra, nói chung A \ B 6= B \ A. Vı́ du. 1.1.3. Giȧ’ su˙’. A := {a, b, c, d} và B := {c, d, e}. Khi d̄ó A∪B A∩B A\B B\A A∆B. = = = = =. {a, b, c, d, e}, {c, d}, {a, b}, {e}, {a, b, e}.. Vı́ du. 1.1.4. Giȧ’ su˙’. A (tu.o.ng ú.ng, B) là tâ.p nghiê.m cu̇’a phu.o.ng trı̀nh x2 − 3x + 2 = 0 3.

(11) (tu.o.ng ú.ng, x2 − 4x + 3 = 0). Ta có A = {1, 2}, B = {1, 3} và A∪B A∩B A\B B\A A∆B. = = = = =. {1, 2, 3}, {1}, {2}, {3}, {2, 3}.. Tâ.p nghiê.m cu̇’a phu.o.ng trı̀nh (x2 − 3x + 2)(x2 − 4x + 3) = 0 là A ∪ B = {1, 2, 3}. Tâ.p nghiê.m cu̇’a hê. hai phu.o.ng trı̀nh x2 − 3x + 2 = 0, x2 − 4x + 3 = 0, là A ∩ B = {1}. Vı́ du. 1.1.5. Giȧ’ su˙’. Ai := {i, i + 1, . . .}, Khi d̄ó. [. Ai = N và. i∈N. \. i ∈ N. Ai = ∅.. i∈N. Các phép toán ho..p và giao trên các tâ.p ho..p có nhũ.ng tı́nh châ´t sau: Tı́nh châ´t 1.1.2. Tı́nh giao hoán A ∪ B = B ∪ A, A ∩ B = B ∩ A. Tı́nh kê´t ho..p (A ∪ B) ∪ C = A ∪ (B ∪ C), (A ∩ B) ∩ C = A ∩ (B ∩ C). Tı́nh phân phô´i A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). Chú.ng minh. Bài tâ.p. 2 4.

(12) Nê´u các tâ.p ho..p A và B có giao bǎ` ng trô´ng, tú.c là nê´u A ∩ B = ∅, thı̀ các tâ.p ho..p này ` n tu˙’. chung, hoǎ.c là rò.i nhau. go.i là không có phâ ` d̄ê ` u là các bô. phâ.n cu̇’a mô.t tâ.p Thu.ò.ng các tâ.p ho..p d̄u.o..c xét tó.i trong cùng mô.t vâ´n d̄ê . . `n ho. p X cô´ d̄i.nh nào d̄ó. Khi â´y, tâ.p ho. p X này go.i là “không gian”. Hiê.u X \ A go.i là phâ c c . c . ˙ ’ bù cu̇’a tâ.p A và ký hiê.u là A . Hiê n nhiên A và A là rò i nhau, A \ B = A ∩ B . Ho n nũ.a Tı́nh châ´t 1.1.3. (Công thú.c De Morgan) Giȧ’ su˙’. {Ai}i∈I là ho. các tâ.p ho..p con cu̇’ a không gian X. Khi d̄ó !c [ \ Ai = (Ai)c , i∈I. \. Ai. i∈I. !c. =. i∈I. [. (Ai)c .. i∈I. Chú.ng minh. Bài tâ.p. 2 - i.nh nghı̃a 1.1.4. Ho. các tâ.p ho..p A := {Ai | i ∈ I} go.i là phu̇’ cu̇’a tâ.p X nê´u X = ∪i∈I Ai. D Nê´u ngoài ra Ai 6= ∅ vó.i mo.i i ∈ I và Ai ∩ Aj = ∅ vó.i mo.i i, j ∈ I, i 6= j, thı̀ ta nói A là mô.t phân hoa.ch cu̇’a tâ.p X. - ǎ.t A1 (tu.o.ng ú.ng, A2) là tâ.p các sô´ nguyên chǎ˜n (tu.o.ng ú.ng, lė’). Khi d̄ó Vı́ du. 1.1.6. D {A1, A2} là mô.t phân hoa.ch cu̇’a tâ.p các sô´ nguyên Z.. 1.1.3. Tı́ch Descartes. Tı́ch Descartes, hay vǎ´n tǎ´t tı́ch, cu̇’a các tâ.p ho..p Ai , i ∈ I, là mô.t tâ.p ho..p, ký hiê.u là Y Ai , i∈I. ` n tu˙’. cu̇’a nó có da.ng x := (xi )i∈I vó.i xi ∈ Ai . Khi d̄ó, d̄u.o..c xác d̄i.nh nhu. sau: tâ´t cȧ’ các phâ . ` n (hay to.a d̄ô.) thú i cu̇’a x. xi go.i là thành phâ Tı́ch cu̇’a mô.t sô´ hũ.u ha.n các tâ.p ho..p Ai , i = 1, 2, . . . , n, thu.ò.ng d̄u.o..c ký hiê.u là n Y. Ai. hoǎ.c. A1 × A2 × · · · × An .. i=1. ` n tu˙’. cu̇’a tı́ch này là mô.t vector (x1, x2, . . . , xn ) vó.i xi ∈ Ai , i = 1, 2, . . . , n. Nói cách Mô˜i phâ khác n Y Ai = {(x1 , x2, . . . , xn ) | xi ∈ Ai, i = 1, 2, . . . , n}. i=1. 5.

(13) ` n) thu.ò.ng d̄u.o..c ký Nê´u A1 = A2 = · · · = An = A thı̀ tı́ch A × A × · · · × A (A có mǎ.t n lâ hiê.u là An . Chú ý rǎ` ng, nói chung, A × B 6= B × A. Dı̃ nhiên A × ∅ = ∅. Vı́ du. 1.1.7. Giȧ’ su˙’. A := {1, 2}, B = {a, b, c}. Khi d̄ó A × B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}, B × A = {(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)}, A × A = {(1, 1), (1, 2), (2, 1), (2, 2)}.. Bài tâ.p - ǎ.t A := {1, 4, 7, 10}, B := {1, 2, 3, 4, 5} và C := {2, 4, 6, 8}. 1. Giȧ’ su˙’. X := {1, 2, . . . , 10}. D ` n tu˙’. cu̇’a mô˜i tâ.p ho..p sau: Liê.t kê các phâ (a) A ∪ B. (b) B ∪ C. (c) A ∩ B. (d) B ∩ C. (e) A \ B. (f) Ac . (g) (B c ∩ (C \ A)). (h) (A ∩ B)c ∪ C. (i) B \ A. (j) A ∩ (B ∪ C). (k) ((A ∩ B) \ C). (l) (A ∩ B) \ (C \ B). ` n tu˙’. cu̇’a mô˜i tâ.p ho..p sau: 2. Giȧ’ su˙’. X := {1, 2, 3} và Y := {x, y}. Liê.t kê các phâ (a) X 2 . (b) X × Y. (c) Y × X. (d) Y 3. 3. Liê.t kê tâ´t cȧ’ các phân hoa.ch cu̇’a các tâ.p ho..p sau: (a) {1}. (b) {1, 2}. 6.

(14) (c) {a, b, c}. (d) {a, b, c, d}. 4. Xác d̄i.nh mô´i quan hê. giũ.a các cǎ.p tâ.p ho..p sau: (a) {1, 2, 3} và {1, 3, 2}. (b) {1, 2, 2, 3} và {1, 2, 3}. (c) {1, 1, 3} và {3, 3, 1}. (d) {x ∈ R | x2 + x = 2} và {1, −2}. (e) {x ∈ R | 0 < x ≤ 2} và {1, 2}. ` n tu˙’. cu̇’a nó là các tâ.p con cu̇’a X. Liê.t kê tâ´t cȧ’ 5. Ký hiê.u P(X) là tâ.p ho..p mà các phâ . ` n tu˙’ cu̇’a P({a, b}) và P({a, b, c}). các phâ ` n tu˙’.. Có bao nhiêu tâ.p ho..p con thu..c su.. cu̇’a tâ.p ho..p X? Tô˙’ng 6. Giȧ’ su˙’. X có 10 phâ quát? 7. Giȧ’ su˙’. X và Y là các tâ.p ho..p khác trô´ng sao cho X × Y = Y × X. Các tâ.p ho..p X và ` u kiê.n gı̀? Y phȧ’i thȯ’a nhũ.ng d̄iê 8. Chú.ng minh hoǎ.c cho phȧ’n vı́ du. các quan hê. (A, B, C là nhũ.ng tâ.p ho..p con cu̇’a tâ.p ho..p X) sau: (a) A ∩ (B \ C) = (A ∩ B) \ (A ∩ C). (b) (A \ B) ∩ (B \ A) = ∅. (c) A \ (B ∪ C) = (A \ B) ∪ C. (d) (A \ B)c = (B \ A)c . (e) (A ∩ B)c ⊆ A. (f) (A ∩ B) ∪ (B \ A) = A. (g) A × (B ∪ C) = (A × B) ∪ (A × C). (h) (A × B)c = Ac × B c . - ǎ˙’ng thú.c nào du.ó.i d̄ây là d̄úng? 9. D (a) A ∩ B = A. (b) A ∪ B = A. (c) (A ∩ B)c = B c . 10. Tı̀m hiê.u d̄ô´i xú.ng cu̇’a hai tâ.p ho..p A := {1, 2, 3} và B := {2, 3, 4, 5}. 11. Giȧ’ su˙’. C là mô.t d̄u.ò.ng tròn và A là tâ.p tâ´t cȧ’ các d̄u.ò.ng kı́nh cu̇’a d̄u.ò.ng tròn C. Xác d̄i.nh ∩A∈A A. 7.

(15) 12. Ký hiê.u P là tâ.p ho..p tâ´t cȧ’ các sô´ nguyên ló.n ho.n 1. Vó.i mô˜i sô´ tu.. nhiên i ≥ 2, d̄ǎ.t Ai := {ik | k ≥ 2, k ∈ P}. S Mô tȧ’ tâ.p ho..p P \ ∞ i=2 Ai . ` u là tâ.p con cu̇’a tâ.p X 13. Chú.ng minh các d̄ǎ˙’ng thú.c sau (giȧ’ su˙’. các tâ.p d̄u o..c xét d̄ê nào d̄ó): A ∩ (A1 ∪ A2 ∪ · · · ∪ An ) = (A ∩ A1) ∪ (A ∩ A2) ∪ · · · ∪ (A ∩ An ). (A1 ∩ A2 ∩ · · · ∩ An )c = Ac1 ∪ Ac2 ∪ · · · ∪ Acn .. 1.2 1.2.1. Ánh xa. - i.nh nghı̃a và tı́nh châ´t D. Mô.t khái niê.m co. bȧ’n khác cu̇’a toán ho.c hiê.n d̄a.i là khái niê.m ánh xa., mo˙’. rô.ng khái niê.m hàm sô´. - i.nh nghı̃a 1.2.1. Cho X và Y là hai tâ.p ho..p bâ´t kỳ. Mô.t ánh xa. (hay hàm sô´) tù. tâ.p D ` n tu˙’. cu̇’a X mô.t phâ ` n tu˙’. xác d̄i.nh cu̇’a Y. ho..p X vào tâ.p ho..p Y là mô.t tu.o.ng ú.ng mô˜i phâ Giȧ’ su˙’. f là mô.t ánh xa. tù. tâ.p ho..p X vào tâ.p ho..p Y. Khi d̄ó ta viê´t f : X → Y ; nê´u ` n tu˙’. cu̇’a Y tu.o.ng ú.ng vó.i phâ ` n tu˙’. x d̄ó và ta viê´t x 7→ f (x); phâ `n x ∈ X thı̀ f (x) chı̇’ phâ . . . ` ’ ’ ’ ˙ ’ ˙ ’ tu f (x) go.i là ȧ nh cu̇a phân tu x qua ánh xa. f, hay là giá tri. cu̇a hàm f ta.i x. Tâ.p ho. p {(x, y) ∈ X × Y | y = f (x)} ` thi. cu̇’ a ánh xa. f và ký hiê.u là graph(f ). go.i là d̄ô Vı́ du. 1.2.1. Tu.o.ng ú.ng mô˜i sô´ thu..c x vó.i mô.t sô´ thu..c x3 cho ta mô.t ánh xa. f : R → R, x 7→ x3. Cho tru.ó.c mô.t tâ.p ho..p A ⊆ X thı̀ tâ.p ho..p f (A) := {f (x) | x ∈ A} - ǎ.c biê.t, tâ.p ho..p f (X) go.i là miê ` n giá tri. cu̇’a f. go.i là ȧ’ nh cu̇’a tâ.p ho..p A qua ánh xa. f. D Dê˜ dàng chú.ng minh rǎ` ng: Tı́nh châ´t 1.2.2. Giȧ’ su˙’. f : X → Y là mô.t ánh xa. tù. tâ.p ho..p X vào tâ.p ho..p Y. Khi d̄ó (a) Nê´u A ⊂ B ⊂ X thı̀ f (A) ⊂ f (B). 8.

(16) (b) Nê´u Ai , i ∈ I, là mô.t ho. các tâ.p ho..p con cu̇’ a tâ.p ho..p X thı̀ ! [ [ = f Ai f (Ai) , i∈I. \. f. Ai. !. i∈I. \. ⊂. i∈I. f (Ai) .. i∈I. - ê˙’ ý rǎ` ng, nói chung d̄ǎ˙’ng thú.c sau D f. \. Ai. !. =. i∈I. \. f (Ai). i∈I. không d̄úng. - i.nh nghı̃a 1.2.3. Giȧ’ su˙’. f : X → Y là mô.t ánh xa. tù. tâ.p ho..p X vào tâ.p ho..p Y. D (a) Ánh xa. f go.i là mô.t-mô.t (hoǎ.c d̄o.n ánh) nê´u vó.i mo.i x, x0 ∈ X mà x 6= x0 thı̀ f (x) 6= f (x0). (b) f go.i là ánh xa. lên (hoǎ.c toàn ánh) nê´u f (X) = Y. ` ng thò.i là mô.t-mô.t và là lên; nói cách (c) f go.i là mô.t-mô.t lên (hoǎ.c song ánh) nê´u f d̄ô ` n tu˙’. y ∈ Y có duy nhâ´t mô.t phâ ` n tu˙’. x ∈ X sao cho f (x) = y. khác, vó.i mô˜i phâ Vı́ du. 1.2.2. (a) Ánh xa. f : R → R,. x 7→ sin x,. là mô.t-mô.t nhu.ng không là ánh xa. lên. (b) Ánh xa.1 g : R → N,. x 7→ [x],. là lên nhu.ng không là ánh xa. mô.t-mô.t. (c) Ánh xa. h : R → R,. x 7→ x3,. là mô.t-mô.t và lên. Vó.i mô.t ánh xa. tùy ý f : X → Y và vó.i mô.t tâ.p ho..p B ⊆ Y, tâ.p ho..p {x ∈ X | f (x) ∈ B} go.i là nghi.ch ȧ’ nh cu̇’a tâ.p ho..p B qua ánh xa. f và d̄u.o..c ký hiê.u là f −1 (B). Rõ ràng f −1 (Y ) = 6 B ⊂ Y và f −1 (B) = ∅. X và f −1 (∅) = ∅, nhu.ng có thê˙’ xȧ’y ra rǎ` ng ∅ = 1. ` n nguyên cu̇’a sô´ thu..c x, ký hiê.u [x], là sô´ nguyên ló.n nhâ´t không vu.o..t quá x. Phâ. 9.

(17) ` m có mô.t phâ ` n tu˙’. y, tú.c là B = {y}, thı̀ thay cho ký hiê.u Nê´u tâ.p ho..p B ⊂ Y chı̇’ gô f −1 ({y}) ta thu.ò.ng ký hiê.u vǎ´n tǎ´t là f −1 (y). Dê˜ dàng chú.ng minh rǎ` ng: Tı́nh châ´t 1.2.4. Giȧ’ su˙’. f : X → Y là mô.t ánh xa. tù. tâ.p ho..p X vào tâ.p ho..p Y. Khi d̄ó (a) Nê´u B ⊂ C ⊂ Y thı̀ f −1 (B) ⊂ f −1 (C). (b) Nê´u Bi , i ∈ I, là mô.t ho. các tâ.p ho..p con cu̇’ a tâ.p ho..p Y thı̀ ! [ [ = Bi f −1 (Bi ) , f −1 i∈I. f −1. \. Bi. !. i∈I. i∈I. =. \. f −1 (Bi ) .. i∈I. (c) Nê´u B, C là hai tâ.p ho..p con cu̇’ a tâ.p ho..p Y thı̀ f −1 (B \ C) = f −1 (B) \ f −1 (C). - ǎ.c biê.t D. f −1 (Y \ B) = X \ f −1 (B).. ` u có (d) Vó.i mo.i tâ.p ho..p con B ⊂ Y ta d̄ê f [f −1 (B)] ⊆ B. ` u có (e) Vó.i mo.i tâ.p ho..p con A ⊂ X ta d̄ê f −1 [f (A)] ⊇ A. - ê˙’ ý rǎ` ng các d̄ǎ˙’ng thú.c D f −1 [f (A)] = A và f [f −1 (B)] = B nói chung không d̄úng.. 1.2.2. Ánh xa. ha.n chê´. Giȧ’ su˙’. f : X → Y là mô.t ánh xa. tù. tâ.p ho..p X vào tâ.p ho..p Y và giȧ’ su˙’. Z là mô.t tâ.p ho..p con cu̇’a X. Ánh xa. f |Z : Z → Y . xác d̄i.nh bo˙’ i f |Z (x) = f (x), x ∈ Z, d̄u.o..c go.i là ha.n chê´ cu̇’ a f lên Z, còn ánh xa. f d̄u.o..c go.i là thác triê˙’n cu̇’a f |Z lên X. Hiê˙’n nhiên 10.

(18) (a) Nê´u f là mô.t-mô.t thı̀ f |Z cũng là mô.t-mô.t . ` u có (b) Vó.i mo.i tâ.p ho..p con B cu̇’a Y ta d̄ê (f |Z )−1 (B) = f −1 (B) ∩ Z.. 1.2.3. Ho..p cu̇’ a các ánh xa.. Giȧ’ su˙’. X, Y và Z là ba tâ.p ho..p và ta có các ánh xa. f : X → Y,. g : Y → Z.. Khi d̄ó có thê˙’ thiê´t lâ.p ánh xa. g ◦ f : X → Z,. x 7→ g[f (x)].. Ánh xa. g ◦ f d̄u.o..c go.i là ho..p cu̇’ a các ánh xa. f và g. Vı́ du. 1.2.3. Cho hai ánh xa. x 7→ x2, y 7→ y − 1.. f : R → R, g : R → R, Ta có ánh xa. ho..p g ◦ f : R → R,. x 7→ x2 − 1.. Tù. d̄i.nh nghı̃a dê˜ dàng suy ra Tı́nh châ´t 1.2.5. Cho hai ánh xa. f : X → Y,. g : Y → Z.. (a) Nê´u f và g là mô.t-mô.t (tu.o.ng ú.ng, lên, mô.t-mô.t lên) thı̀ ánh xa. ho..p g ◦ f cũng là mô.t-mô.t (tu.o.ng ú.ng, lên, mô.t-mô.t lên). ` u có (b) Vó.i mo.i tâ.p ho..p con A cu̇’ a X ta d̄ê (g ◦ f )(A) = g[f (A)]. ` u có (c) Vó.i mo.i tâ.p ho..p con C cu̇’ a Z ta d̄ê (g ◦ f )−1 (C) = f −1 [g −1 (C)]. 11.

(19) 1.2.4. Ánh xa. ngu.o..c. Giȧ’ su˙’. f: X →Y ` n tu˙’. y ∈ Y tô ` n ta.i duy nhâ´t mô.t phâ ` n tu˙’. x ∈ X là ánh xa. mô.t-mô.t lên. Khi d̄ó vó.i mô˜i phâ sao cho f (x) = y, và bo˙’.i vâ.y f −1 (y) = {x}. Do d̄ó ta có thê˙’ thiê´t lâ.p mô.t ánh xa. g: Y → X xác d̄i.nh bo˙’.i công thú.c: vó.i mo.i y ∈ Y, g(y) = x nê´u f (x) = y. Ánh xa. g go.i là ánh xa. ngu.o..c cu̇’a f và ký hiê.u là f −1 . Hiê˙’n nhiên f −1 : Y → X là ánh xa. mô.t-mô.t lên và (f −1 )−1 = f. ` ng nhâ´t Vı́ du. 1.2.4. (a) Ánh xa. d̄ô idX : X → X,. x 7→ x,. là ánh xa. mô.t-mô.t lên và (idX )−1 = idX . (b) Ánh xa. mô.t-mô.t và lên f : R → R, có ánh xa. ngu.o..c là f −1 : R → R,. x 7→ x3, 1. y 7→ y 3 .. Tù. d̄i.nh nghı̃a dê˜ dàng suy ra Tı́nh châ´t 1.2.6. (a) Giȧ’ su˙’. f : X → Y là ánh xa. mô.t-mô.t lên. Khi d̄ó f −1 ◦ f = idX ,. f ◦ f −1 = idY .. (b) Nê´u f : X → Y, g : Y → Z là nhũ.ng ánh xa. mô.t-mô.t lên, thı̀ ánh xa. ho..p (g ◦f ) : X → Z cũng mô.t-mô.t lên và (g ◦ f )−1 = f −1 ◦ g −1 .. 1.2.5. Lu..c lu.o..ng cu̇’ a mô.t tâ.p ho..p. - i.nh nghı̃a 1.2.7. (a) Hai tâ.p ho..p A và B go.i là có cùng lu..c lu.o..ng nê´u tô ` n ta.i ánh xa. D mô.t-mô.t và lên f : A → B. (b) Tâ.p ho..p trô´ng, tâ.p ho..p {x1 , x2, . . . , xn } và các tâ.p ho..p cùng lu..c lu.o..ng vó.i nó go.i là tâ.p ho..p hũ.u ha.n. 12.

(20) (c) Tâ.p ho..p các sô´ tu.. nhiên N và các tâ.p ho..p cùng lu..c lu.o..ng vó.i nó go.i là tâ.p ho..p d̄ê´m d̄u.o..c. (d) Tâ.p ho..p các sô´ thu..c R và các tâ.p ho..p cùng lu..c lu.o..ng vó.i nó go.i là tâ.p ho..p không d̄ê´m d̄u.o..c. (e) Tâ.p ho..p A go.i là không quá d̄ê´m d̄u.o..c, nê´u A là mô.t tâ.p ho..p hũ.u ha.n (và có thê˙’ là trô´ng), hoǎ.c nê´u A là mô.t tâ.p ho..p d̄ê´m d̄u.o..c. Giȧ’ su˙’. A := {x1 , x2, . . . , xn } là mô.t tâ.p ho..p hũ.u ha.n khác trô´ng sao cho xi 6= xj vó.i mo.i ` n tu˙’. và ký hiê.u #A := n. Tâ.p ho..p trô´ng ∅ không i 6= j. Khi d̄ó ta nói tâ.p ho..p A có n phâ . ` n tu˙’ nào cȧ’, vı̀ vâ.y d̄ǎ.t #∅ := 0. Nê´u A là tâ.p ho..p khác trô´ng và không phȧ’i tâ.p ho..p có phâ hũ.u ha.n, d̄ǎ.t #A := +∞.. Bài tâ.p 1. Giȧ’ su˙’. X := {1, 2, 3}, Y := {a, b, c, d}, Z := {w, x, y, z}. Xét các ánh xa. f : X → Y và g : Y → Z cho bo˙’.i f (1) = b, f (2) = c, f (3) = a, g(a) = x, g(b) = x, g(c) = z, g(d) = w. Xác d̄i.nh ánh xa. ho..p f ◦ g. 2. Giȧ’ su˙’. f : X → N, x 7→ x2, vó.i X := {−5, −4, . . . , 4, 5}. f là ánh xa. mô.t-mô.t? f là ánh xa. lên? 3. Có bao nhiêu ánh xa. tù. tâ.p {a, b} vào tâ.p {1, 2}. Nhũ.ng ánh xa. nào là mô.t-mô.t? Nhũ.ng ánh xa. nào là lên? 4. Giȧ’ su˙’. X := {a, b, c} và f : X → X cho bo˙’.i f (a) = b, f (b) = a, f(c) = b. - i.nh nghı̃a dãy các ánh xa. f n : X → X, n = 1, 2, . . . , bo˙’.i f 1 := f và f n := f n−1 ◦ f D vó.i mo.i n ≥ 2. Hãy xác d̄i.nh các ánh xa. f 2 , f 3 , f 9 , f 789. 5. Giȧ’ su˙’. X := {0, 1, 2, 3, 4} và ánh xa. f : X → X xác d̄i.nh bo˙’.i f (x) := 4x mod 5. f là ánh xa. mô.t-mô.t? f là ánh xa. lên? 6. Giȧ’ su˙’. m, n là các sô´ nguyên du.o.ng. Giȧ’ su˙’. X := {0, 1, 2, . . . , m − 1}. Xét ánh xa. f : X → X cho bo˙’.i f (x) := nx mod m. ` u kiê.n cu̇’a m và n d̄ê˙’ f là ánh xa. mô.t-mô.t và lên? Tı̀m nhũ.ng d̄iê 13.

(21)

toan

Tài liệu liên quan

Tài liệu bạn tìm kiếm đã sẵn sàng tải về