Giáo trình Toán rời rạc - Phạm Tiến Sơn (ĐH Đà Lạt)

Chia sẻ: Nguyen Minh Phung | Ngày: | Loại File: PDF | Số trang:197

Thêm vào BST

Báo xấu

2.055
lượt xem 268
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung Giáo trình Toán rời rạc - Phạm Tiến Sơn trình bày nội dung kiến thức về tập hợp và ánh xạ, logic và các phương pháp chứng minh, thuật toán, phép đếm,... Hãy tham khảo để nắm bắt nội dung chi tiết nhất.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình Toán rời rạc - Phạm Tiến Sơn (ĐH Đà Lạt)

TRÖÔØNG ÑAÏI HOÏC ÑAØ LAÏT KHOA TOAÙN - TIN HOÏC PHAÏM TIEÁN SÔN TOAÙN RÔØI RAÏC 1 (Baøi Giaûng Toùm Taét) -- Löu haønh noäi boä -- Ñaø Laït 2008
Muc luc . . ˙. - A MO D` U ’ ˆ iv . ˆ `´ 1 TAP HO P VA ANH XA 1 . . . Tˆp ho.p . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 a 1 . . 1.1.1 Kh´i niˆm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ae 1 . C´c ph´p to´n trˆn tˆp ho.p . . . . . . . . . . . . . . . . . . . . . . . 1.1.2 a e a ea 3 . . 1.1.3 T´ Descartes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ıch 5 ´ 1.2 Anh xa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 . -. ´ 1.2.1 Dinh ngh˜ v` t´ chˆ t . . . . . . . . . . . . . . . . . . . . . . . . . ıa a ınh a 8 ´ ´ 1.2.2 Anh xa han chˆ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . e 10 .. Ho.p cua c´c ´nh xa . . . . . . . . . . . . . . . . . . . . . . . . . . . . ˙ aa ’ 1.2.3 11 . . Anh xa ngu.o.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ 1.2.4 12 . . Lu.c lu.o.ng cua mˆt tˆp ho.p . . . . . . . . . . . . . . . . . . . . . . . ˙ ’ 1.2.5 oa 12 . . .. . .. ´. `´ ´ 2 LOGIC VA CAC PHU O NG PHAP CHU NG MINH 17 Mˆnh d` . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 e ¯ˆ e 17 . Mˆnh d` c´ d iˆu kiˆn v` c´c mˆnh d` tu.o.ng d .o.ng . . . . . . . . . . . . . . ¯ˆ o ¯ ` 2.2 e e e e aa e ¯ˆ e ¯u 20 . . . Lu.o.ng h´a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 o 23 . Phu.o.ng ph´p ch´.ng minh . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 a u 26 i
2.5 Quy nap to´n hoc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a 31 . . ˆ ´ 3 THUAT TOAN 33 . Mo. d` u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ˙ ¯ˆ ’a 3.1 33 T` sˆ l´.n nhˆ t trong ba sˆ . . . . . . . . . . . . . . . . . . . . . . . ´ ´ ´ 3.1.1 ım o o a o 33 T` sˆ l´.n nhˆ t trong d˜y h˜.u han c´c sˆ thu.c . . . . . . . . . . . . ´ ´ ´ 3.1.2 ım o o a au .ao. 33 3.2 Thuˆt to´n Euclid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a a 35 . 3.2.1 Thuˆt to´n Euclid . . . . . . . . . . . . . . . . . . . . . . . . . . . . a a 37 . 3.3 Thuˆt to´n dˆ quy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a a ¯e 39 . . T´ n giai th`.a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 ınh u 39 T` u.´.c sˆ chung l´.n nhˆ t . . . . . . . . . . . . . . . . . . . . . . . ´ ´ 3.3.2 ım o o o a 40 3.3.3 Thuˆt to´n x´c d .nh d˜y Fibonacci . . . . . . . . . . . . . . . . . . . a a a ¯i a 41 . Dˆ ph´.c tap cua thuˆt to´n . . . . . . . . . . . . . . . . . . . . . . . . . . . -o u . ˙ ’ 3.4 a a 43 . . 3.5 Phˆn t´ thuˆt to´n Euclid . . . . . . . . . . . . . . . . . . . . . . . . . . . a ıch a a 48 . ´ ´ -ˆ 4 PHEP DEM 51 C´c nguyˆn l´ co. ban cua ph´p d e m . . . . . . . . . . . . . . . . . . . . . . ´ ˙ ’ ˙ ’ 4.1 a ey e ¯ˆ 51 Nguyˆn l´ tˆ’ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ˙ 4.1.1 e yo 51 4.1.2 Nguyˆn l´ t´ e y ıch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Nguyˆn l´ bao h`m-loai tr`. . . . . . . . . . . . . . . . . . . . . . . . 4.1.3 ey a .u 54 Ho´n vi v` tˆ’ ho.p . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ˙ 4.2 a .ao . 57 C´c thuˆt to´n sinh ra ho´n vi v` tˆ’ ho.p . . . . . . . . . . . . . . . . . . . . ˙ 4.3 a a a a .ao . 62 . Ho´n vi v` tˆ’ ho.p suy rˆng . . . . . . . . . . . . . . . . . . . . . . . . . . . ˙ 4.4 a .ao . o 66 . Hˆ sˆ cua nhi th´.c v` c´c d` ng nhˆ t th´.c . . . . . . . . . . . . . . . . . . . .´’ ´ eo ˙ 4.5 . u a a ¯ˆ o a u 73 ` `a 4.6 Nguyˆn l´ chuˆng chim bˆ cˆu . . . . . . . . . . . . . . . . . . . . . . . . . . ey o o 77 Nguyˆn l´ chuˆng chim bˆ cˆu (dang th´. nhˆ t) . . . . . . . . . . . . ` `a ´ 4.6.1 ey o o u a 77 . ii
Nguyˆn l´ chuˆng chim bˆ cˆu (dang th´. hai) . . . . . . . . . . . . . ` `a 4.6.2 ey o o u 78 . Nguyˆn l´ chuˆng chim bˆ cˆu (dang th´. ba) . . . . . . . . . . . . . ` `a 4.6.3 ey o o u 80 . ˆ 5 QUAN HE 85 . 5.1 Quan hˆ hai ngˆi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . e o 85 . 5.2 Quan hˆ v` ma trˆn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ea a 90 . . Quan hˆ th´. tu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 eu. 96 . Quan hˆ tu.o.ng d u.o.ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 5.4 e ¯ . ˙ ’ 5.5 Bao d ´ng cua quan hˆ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 ¯o e . ˙a ’ 5.6 Lattice cua c´c phˆn hoach . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 a . o˙ .’ 5.6.1 Thuˆt to´n x´c d .nh hˆi cua hai phˆn hoach . . . . . . . . . . . . . 118 a a a ¯i a . . Thuˆt to´n x´c d .nh tuyˆ’n cua hai phˆn hoach . . . . . . . . . . . . 119 ˙˙ ’ 5.6.2 a a a ¯i e a . . ´ ˆ -. 6 DAI SO BOOLE 123 6.1 Lattice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 ´ 6.2 Lattice phˆn bˆ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 ao -. o ´ 6.3 Dai sˆ Boole . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 6.4 H`m Boole a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 Biˆ’u diˆn c´c h`m Boole qua hˆ tuyˆ’n, hˆi v` phu d inh . . . . . . . . . . . 149 ˙ ˙ ˜aa ˙ ¯. ’ 6.5 e e e e oa . . Biˆ’u diˆn tˆi thiˆ’u cua h`m Boole . . . . . . . . . . . . . . . . . . . . . . . 152 ˙ ˙˙a ˜o e´ ’ 6.6 e e 6.6.1 Kh´i niˆm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 ae . Phu.o.ng ph´p ban d` Karnaugh . . . . . . . . . . . . . . . . . . . . . 153 ˙ ¯ˆ ’o 6.6.2 a ´ 7 MA TUYEN T´ ˜ ˆ INH 159 Mo. d` u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 ˙ ¯ˆ ’a 7.1 7.1.1 Kh´i niˆm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 ae . iii
.˜ 7.1.2 M˜ ph´t hiˆn lˆi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 aa eo M˜ su.a sai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 a˙ ’ 7.1.3 7.2 C´c kh´i niˆm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 a ae . ˙ ’ 7.3 Khoang c´ch Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 a Hˆi ch´.ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 7.4 o u . Giai m˜ d`ng bang chuˆ’n . . . . . . . . . . . . . . . . . . . . . . . . 179 ˙ ˙ ’ au ˙ ’ 7.4.1 a ˙ ’ 7.5 M˜ ho`n hao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 aa 7.6 M˜ Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 a ˙ ’ T`i liˆu tham khao ae 189 . iv
˙. - A MO D` U ’ ˆ To´n hoc r`.i rac l` mˆt bˆ phˆn cua To´n hoc nhˇ m nghiˆn c´.u c´c d oi tu.o.ng r`.i rac: ` ´ ˙ ’ a .o.aoo a a a e u a ¯ˆ o. . . . . . .u c´c cˆ u tr´c r`.i rac kh´c nhau v` c´c phu.o.ng ph´p giai c´c vˆ n d` c´ liˆn quan ´ ´e ˙ a a ¯ˆ o e ’ nghiˆn c´ a a eu uo. a aa a ´ ´ dˆn c´c cˆ u tr´c n`y. ¯e a a ua Thˆng tin lu.u tr˜. v` vˆn h`nh trong m´y t´nh du.´.i dang c´c t´n hiˆu r`.i rac (c´c m´y o uaa a aı o. aı eo. a a . . t´nh liˆn tuc chı l` c´c m´y t´nh tu.o.ng tu., chuyˆn dung). V` vˆy cˆng cu d`ng dˆ’ biˆ’u diˆn ˙˙ ˜ ˙a a ’ ı e. aı e. ıa o u ¯e e e . . . thˆng tin trong m´y v` xu. l´ c´c thˆng tin n`y l` To´n hoc r`.i rac. a a ˙ya’ o o aaa o. . Ngo`i ra, c´c phu.o.ng ph´p v` kˆt qua cua To´n hoc r`.i rac c´ thˆ’ d`ng dˆ’ giai quyˆt tru.c ˙ ˙’ ´ ´. ˙˙ ’’ a . o . o e u ¯e ˙ a a a ae e . logic, h`m d ai sˆ logic, tˆ’ ho.p trˆn t`.... To´n ˙ tiˆp nhiˆu vˆ n d` d ˇt ra cua Tin hoc nhu ´ ` ´ e. ´ ˙ ’ e e a ¯ˆ ¯a a ¯. o o. eu a . .i rac chuˆ’n bi sˇn v` cung cˆ p c´c cˆng cu, phu.o.ng ph´p luˆn d e’ giai quyˆt nhiˆu ˜ ˙ .a a ˙˙ ´ ´ ` a ¯ˆ ’ hoc r` . .o a aao a e e . . vˆ n d` cua Tin hoc. C´ thˆ’ n´i To´n hoc r`.i rac l` ng`nh To´n hoc co. so. cho Tin hoc. ˙ ´ e’ a ¯ˆ ˙ ˙ ’ o eo a o.aa a . . . . Muc d´ch cua gi´o tr` nhˇ m cung cˆ p mˆt sˆ cˆng cu To´n hoc dˆ’ bu.´.c d` u d i v`o ˙ o ¯ˆ ¯ a ınh ` ´ .´ ˙ ’ . ¯ı a a a o oo a . ¯e a . .o.c tr` b`y mˆt c´ch d`n trai ho.n l` d i sˆu v`o mˆt vˆ n d` cu thˆ’. ˙ ´ ¯ˆ . e ˙ ’ Tin hoc. Gi´o tr` d u . a ınh ¯ ınh a oa a a¯ a a oae . . . .ng kiˆn th´.c d ˜ hoc. Hy vong rˇ ng gi´o ´˜ ` ` ` oa aa ´ ´ ˙ ’ Cuˆi mˆi phˆn c´ c´c b`i tˆp nhˇ m cung cˆ nh˜ oo a a ou e u ¯a . a a . . .ng d u.o.c phˆn n`o yˆu cˆu hoc tˆp cua c´c ban sinh viˆn. `aae` ˙a. ’ tr` n`y d ´p u ınh a ¯a ´ ¯. a .a e . -a . D` Lat, ng`y 11 th´ng 2 nˇm 2008 a a a .n ´ Pham Tiˆn So e . v
vi
Chu.o.ng 1 ˆ P HO.P VA ANH XA `´ TA . . . Tˆp ho.p 1.1 a . . 1.1.1 Kh´i niˆm a e . Mˆt kh´i niˆm co. ban cua to´n hoc hiˆn d . i l` kh´i niˆm tˆp ho.p. ˙ ’ ˙ ’ o ae a e ¯a a a e a . . . . . . . C˜ng giˆng nhu. d iˆ’m, d . n thˇng, mˇt phˇng, ... trong h`nh hoc Euclid, kh´i niˆm tˆp ˙ ¯oa ˙ ’ ˙ ’ ´ u o ¯e a a a ı ae a . . . . .p khˆng d u.o.c d inh ngh˜ m` chı d .o.c mˆ ta bˇ ng nh˜.ng v´ du. Chˇng han, tˆp ho.p c´c ’` ˙’ ıa a ˙ ¯u . ’ o˙a ho o ¯ . ¯. u ı. a a .a . . . . viˆn, tˆp ho.p c´c sˆ thu.c, tˆp ho.p c´c d a th´.c bˆc hai, v.v... ´ s´ch trong thu e a a .ao. a . a¯ ua . . . . C´c vˆt tao nˆn mˆt tˆp ho.p goi l` c´c phˆn tu. cua tˆp ho.p ˆ y. C´ hai c´ch x´c d inh ` ´ a˙˙a ’’. aa. e oa .aa .a o a a ¯. . .. . .p: mˆt tˆp ho oa .. . (a) Liˆt kˆ danh s´ch c´c phˆn tu. cu a n´. Chˇng han, tˆp ho.p gˆm c´c phˆn tu. a, b, c, d ˙ ’ ` .` ` a˙˙ ’’o a˙ ’ ee a a a a o a . . . .`.ng d u.o.c viˆt ´ thu o ¯. e {a, b, c, d}. (b) Nˆu lˆn t´nh chˆ t d ˇc tru.ng cu a c´c phˆn tu. cu a tˆp ho.p. Chˇng han, tˆp ho.p {1, 3} ˙’ ´. ` ˙a ’ a˙˙a. ’’. eeı a ¯a a a . . . .p hai sˆ tu. nhiˆn le nho nhˆ t hay tˆp ho.p c´c nghiˆm cua c´ thˆ’ mˆ ta l` tˆp ho ˙ ´ ´ o e o˙aa ’ e˙ ’ ˙ ’ ˙ ’ o. a a a e . . . . . .o.ng tr`nh bˆc hai x2 − 4x + 3 = 0. phu ı a . K´ hiˆu x ∈ A (v` d . c l` x thuˆc A) c´ ngh˜a x l` phˆn tu. cua tˆp ho.p A. Khi x khˆng a` a˙˙a’’. ye a ¯o a o o ı o . . . . cua tˆp ho.p A ta viˆt x ∈ A (v` d c l` x khˆng thuˆc A). Chˇng han, nˆu ˙ ’ ˙a ` ´ ´ phai l` phˆn tu ˙ a ’ a˙’.’ e a ¯o a o o a e . . . . ´ tu. nhiˆn th` 7 ∈ N nhu.ng 12 ∈ N. goi N l` tˆp c´c sˆ . aa a o e ı . . 5 .n gian, d oi khi ta chı d`ng t`. “tˆp” thay cho cum t`. “tˆp ho.p”. -e ¯ Ch´ y 1. (a) Dˆ’ d o ˙ ˙ ¯ˆ ’ ˙u ’ u´ ua ua . . . . (b) K´ hiˆu := thu.`.ng d`ng dˆ’ d u.a v`o d .nh ngh˜a, n´ thay cho cum t`. “d .nh ngh˜a bo.i”. ˙ ı˙ ’ ye o u ¯e ¯ a ¯i ı o u ¯i . . ˙ ng han, N := {0, 1, 2, . . .}. ’ Chˇ a . 1
(c) Ta thu.`.ng d`ng k´ hiˆu | dˆ’ diˆn d . t y “sao cho” (hoˇc “trong d o”). Chˇng han, tˆp ˙e ¯e ˜ ¯a ´ ˙ ’ o u ye a ¯´ a a . . . . .p tˆ t ca c´c sˆ tu. nhiˆn chˇn c´ thˆ’ mˆ ta nhu. sau: ˜ ˙ ´’ ´ ho a ˙ a o . a o e o˙ ’ e . ´ {n ∈ N | n chia hˆt cho 2}. e V´ du 1.1.1. Mˆt v`i tˆp ho.p sˆ thu.`.ng gˇp: ´ ı. oaa .o o a . . . (a) Tˆp ho.p c´c sˆ tu. nhiˆn N := {0, 1, 2, . . .}. ´ a . ao. e . (b) Tˆp ho.p c´c sˆ nguyˆn du.o.ng P := {1, 2, . . .}. ´ a .ao e . (c) Tˆp ho.p c´c sˆ nguyˆn Z := {0, 1, −1, 2, −2, . . .}. ´ a .ao e . (d) Tˆp ho.p c´c sˆ h˜.u tı Q := { p | p, q ∈ Z, q = 0}. ´ . aou ˙ ’ a . q (e) Tˆp ho.p c´c sˆ thu.c R. ´ a .ao. . √ (f) Tˆp ho.p c´c sˆ ph´.c C := {a + −1b | a, b ∈ R}. ´ a .aou . Mˆt tˆp ho.p khˆng c´ phˆn tu. n`o ca goi l` tˆp ho.p trˆng (hay rˆng) v` d .o.c k´ hiˆu l` ˜ o` ´ a ˙ a ˙ . aa ’ ’ oa o o o a ¯u . y e a .. . . . . .p gˆm c´c nghiˆm sˆ thu.c cua phu.o.ng tr`nh bˆc hai x2 + 1 = 0 l` mˆt ˙’ ∅. Chˇng han tˆp ho ` ´ ˙ ’ a a o a e o. ı a ao .. . . . . tˆp ho.p trˆng. ´ a o . . Tˆp ho.p B goi l` tˆp ho.p con cua tˆp ho.p A nˆu moi phˆn tu. cua tˆp ho.p B d` u l` ´ ` ˙a ’. ˙˙a ’’. a . aa e a ¯ˆ a e . . . . . . . . cua tˆp ho.p A; trong tru.`.ng ho.p n`y ta k´ hiˆu B ⊆ A hay A ⊇ B. Hiˆ’n nhiˆn ˙ ` phˆn tu ˙ a a˙’. ’ o a ye e e . . . .n n˜.a, d e’ thuˆn tiˆn, ta thu.`.ng coi tˆp ho.p trˆng l` mˆt tˆp ho.p con cua tˆp ˙ ´ ˙a ’. A ⊆ A. Ho u ¯ˆ a e o a o aoa . . . . .. . bˆ t k`, t´.c l` ∅ ⊆ A v´.i moi tˆp ho.p A. Hai tˆp ho.p A v` B goi l` bˇ ng nhau nˆu B ⊆ A a` ´ ´ a yua o a a a a e .. . . . . v` A ⊆ B ; khi d ´ ta viˆt A = B. Nˆu B ⊆ A nhu.ng A = B ta n´i B l` tˆp ho.p con thu.c ´ ´ a ¯o e e o aa . . . . cua tˆp ho.p A v` viˆt B A. ´ ˙a ’. su ae . . ´ V´ du 1.1.2. (a) Nˆu ı. e A := {x ∈ R | x2 + x − 6 = 0}, B := {2, −3} th` A = B. ı (b) Ta c´ c´c bao h`m th´.c thu.c su. sau oa a u .. P N Z Q R. Mˆt tˆp ho.p m` phˆn tu. cua n´ l` nh˜.ng tˆp ho.p thu.`.ng d .o.c goi l` mˆt ho c´c tˆp a` a ˙ ˙ oa u ’’ oa a o ¯u . .a o .a a .. . . . . . .p, hoˇc mˆt hˆ c´c tˆp ho.p. N´i c´ch kh´c, “tˆp ho.p”, “ho”, “hˆ” l` nh˜.ng thuˆt ng˜. ho a o ea a oa a a eau a u . . .. . . . . . . . d` ng ngh˜a. ¯ˆ o ı Dˆ’ nˆu lˆn danh s´ch c´c tˆp ho.p cua mˆt ho tˆp ho.p A, ta h˜y goi mˆi tˆp ho.p cua A -e e e ˙ ˜. ˙ ’ ˙ ’ a aa o .a a. oa . . . . . . .o.c goi l` chı’ sˆ dˆ’ d anh dˆ u tˆp ho.p ˆ y, hai tˆp ho.p kh´c nhau cua ho ´˙ ´. ´ ˙ o ¯e ¯´ ˙ ’. l` Ai; k´ hiˆu i d u . . a a ye ¯ aa .a a a . . . 2
A d u.o.c d ´nh dˆ u bo.i hai chı sˆ kh´c nhau. Nˆu I l` tˆp ho.p tˆ t ca c´c chı sˆ d ˜ d`ng d e’ ˙ ´˙ ’´ ´ ´’ ’´ ’ ˙o a . a ˙a ˙ o ¯a u ¯ˆ ¯ . ¯a a e aa . .p cua ho A th` ta c´ thˆ’ viˆt ˙´ ´ ˙ ’. d ´nh dˆ u c´c ¯a aa tˆp ho a ı oee . . A := {Ai | i ∈ I }, hay A := {Ai}i∈I . C˜ng c´ thˆ’ su. dung phu.o.ng ph´p n`y dˆ’ d anh dˆ u tˆ t ca c´c phˆn tu. cua mˆt tˆp ho.p ˙’ ˙ ´´’ ` o e˙ . a a ˙a a˙˙ ’’ u a a ¯e ¯´ oa .. . A t`y y. u´ C´c ph´p to´n trˆn tˆp ho.p 1.1.2 a e a ea . . Cho tru.´.c c´c tˆp A v` B ta c´ thˆ’ th`nh lˆp c´c tˆp m´.i bˇ ng c´c ph´p to´n sau: ˙ ` oaa a oea aaa oa a e a . . . Dinh ngh˜ 1.1.1. Ho.p cua hai tˆp A v` B l` mˆt tˆp ho.p, k´ hiˆu A ∪ B, gˆm tˆ t ca c´c -. ` ´’ ˙ ’ o a ˙a ıa a a aoa ye . . .. . . . hoˇc thuˆc A hoˇc thuˆc B (hoˇc thuˆc ca hai). ` a˙ ’ o˙ .’ phˆn tu a o a o a . . . . . Giao cua hai tˆp A v` B l` mˆt tˆp ho.p, k´ hiˆu A ∩ B, gˆm tˆ t ca c´c phˆn tu. v`.a ` ´’ ` ˙ ’ a ˙a a ˙u ’ a a aoa ye o . .. . . .a thuˆc B. thuˆc A v` o u o . . Hiˆu cua tˆp ho.p A v´.i tˆp ho.p B l` mˆt tˆp ho.p, k´ hiˆu A \ B, gˆm tˆ t ca c´c phˆn ` ´’ ` ˙a ’. a ˙a e oa aoa ye o a . . . . .. . . . thuˆc A nhu.ng khˆng thuˆc B. ˙ ’ tu o o o . . Hiˆu d ˆi x´.ng cua hai tˆp ho.p A v` B l` tˆp ho.p ´ ˙ ’ e ¯o u a a aa . . . . . A ∆ B := (A \ B ) ∪ (B \ A). Nhˆn x´t 1. (a) Mˆt c´ch tu.o.ng tu., c´ thˆ’ d inh ngh˜ ho.p ∪i∈I Ai v` giao ∩i∈I Ai cua ˙ ˙ ’ a e oa . o e ¯. ıa . a . . .p A := {A | i ∈ I }. mˆt ho tˆp ho o .a . . . i (b) Ta luˆn c´ A ∆ B = B ∆ A. Nhu.ng nhu. v´ du du.´.i d ˆy chı ra, n´i chung A \ B = B \ A. ˙ ’ oo ı. o ¯a o V´ du 1.1.3. Gia su. A := {a, b, c, d} v` B := {c, d, e}. Khi d o ˙˙ ’’ ı. a ¯´ A∪B = {a, b, c, d, e}, A∩B = {c, d}, A\B = {a, b}, B\A = {e}, A∆B = {a, b, e}. V´ du 1.1.4. Gia su. A (tu.o.ng u.ng, B ) l` tˆp nghiˆm cua phu.o.ng tr`nh x2 − 3x + 2 = 0 ˙˙ ’’ ˙ ’ ı. ´ aa e ı . . 3
(tu.o.ng u.ng, x2 − 4x + 3 = 0). Ta c´ A = {1, 2}, B = {1, 3} v` ´ o a A∪B = {1, 2, 3}, A∩B = {1}, A\B = {2}, B\A = {3}, A∆B = {2, 3}. Tˆp nghiˆm cua phu.o.ng tr`nh ˙ ’ a e ı . . (x2 − 3x + 2)(x2 − 4x + 3) = 0 l` A ∪ B = {1, 2, 3}. Tˆp nghiˆm cua hˆ hai phu.o.ng tr`nh ˙e ’. a a e ı . . x2 − 3x + 2 = 0, x2 − 4x + 3 = 0, l` A ∩ B = {1}. a V´ du 1.1.5. Gia su. ˙˙ ’’ ı. i ∈ N. Ai := {i, i + 1, . . .}, Khi d ´ ¯o Ai = N v` a Ai = ∅. i∈N i∈N C´c ph´p to´n ho.p v` giao trˆn c´c tˆp ho.p c´ nh˜.ng t´ chˆ t sau: ´ a e a a eaa .ou ınh a . . ´ T´ chˆt 1.1.2. T´ giao ho´n ınh a ınh a A ∪ B = B ∪ A, A ∩ B = B ∩ A. T´ kˆt ho.p ´ ınh e . (A ∪ B ) ∪ C = A ∪ (B ∪ C ), (A ∩ B ) ∩ C = A ∩ (B ∩ C ). ´ T´ phˆn phˆi ınh a o A ∩ (B ∪ C ) = ( A ∩ B ) ∪ (A ∩ C ), A ∪ (B ∩ C ) = ( A ∪ B ) ∩ (A ∪ C ). Ch´.ng minh. B`i tˆp. 2 u aa . 4
Nˆu c´c tˆp ho.p A v` B c´ giao bˇ ng trˆng, t´.c l` nˆu A ∩ B = ∅, th` c´c tˆp ho.p n`y ` ´ ´ ´ eaa a o a o uae ıa a a . . . . . chung, hoˇc l` r`.i nhau. o` a˙ ’ goi l` khˆng c´ phˆn tu ao a ao . . Thu.`.ng c´c tˆp ho.p d .o.c x´t t´.i trong c`ng mˆt vˆ n d` d` u l` c´c bˆ phˆn cua mˆt tˆp . ´ ee o a ¯ˆ ¯ˆ a a o a ˙ ’ o aa . ¯u . e o u oa . . . .. .p X cˆ d inh n`o d ´. Khi ˆ y, tˆp ho.p X n`y goi l` “khˆng gian”. Hiˆu X \ A goi l` phˆn ´ ´. a` ho o ¯. a ¯o aa a .a o e a . . . . ˙n nhiˆn A v` Ac l` r`.i nhau, A \ B = A ∩ B c . Ho.n n˜.a ’ c u˙ a’. b` cua tˆp A v` k´ hiˆu l` A . Hiˆ ay e a e e a ao u . T´ chˆt 1.1.3. (Cˆng th´.c De Morgan) Gia su. {Ai}i∈I l` ho c´c tˆp ho.p con cu a khˆng ´ ˙˙ ’’ ˙ ’ ınh a o u a.aa . o . gian X. Khi d ´ ¯o c (Ai)c , Ai = i∈I i∈I c (Ai)c . Ai = i∈I i∈I Ch´.ng minh. B`i tˆp. 2 u aa . Dinh ngh˜ 1.1.4. Ho c´c tˆp ho.p A := {Ai | i ∈ I } goi l` phu cua tˆp X nˆu X = ∪i∈I Ai. -. ´ .a ˙˙a ’’. ıa .a a e . . .i moi i ∈ I v` A ∩ A = ∅ v´.i moi i, j ∈ I, i = j, th` ta n´i A l` mˆt ´ Nˆu ngo`i ra Ai = ∅ v´ e a o ai o ı o ao . . . j ˙ a tˆp X. ’a phˆn hoach cu . a . V´ du 1.1.6. Dˇt A1 (tu.o.ng u.ng, A2) l` tˆp c´c sˆ nguyˆn chˇn (tu.o.ng u.ng, le). Khi d o ˜ -a ´ ˙ ’ ı. ´ aa a o e a ´ ¯´ . . ´ ˙ a tˆp c´c sˆ nguyˆn Z. ’aao {A1, A2} l` mˆt phˆn hoach cu . ao a e . . 1.1.3 T´ Descartes ıch T´ Descartes, hay vˇn tˇt t´ch, cua c´c tˆp ho.p Ai , i ∈ I, l` mˆt tˆp ho.p, k´ hiˆu l` ´´ ˙aa ’ ıch aaı aoa yea . . .. . . Ai , i∈I d u.o.c x´c d .nh nhu. sau: tˆ t ca c´c phˆn tu. cua n´ c´ dang x := (xi )i∈I v´.i xi ∈ Ai . Khi d ´, ´’ ` a ˙a a ˙ ˙ oo. ’’ ¯ . a ¯i o ¯o xi goi l` th`nh phˆn (hay toa d ˆ) th´. i cua x. ` ˙ ’ aa a ¯o u . . . T´ cua mˆt sˆ h˜.u han c´c tˆp ho.p Ai , i = 1, 2, . . . , n, thu.`.ng d .o.c k´ hiˆu l` .´ ıch ˙ ’ oou .aa o ¯u . y e a . . . n Ai hoˇc a A1 × A2 × · · · × An . . i=1 Mˆi phˆn tu. cua t´ch n`y l` mˆt vector (x1, x2, . . . , xn ) v´.i xi ∈ Ai , i = 1, 2, . . . , n. N´i c´ch ˜ ` a˙˙ı ’’ o aao o oa . kh´c a n Ai = {(x1 , x2, . . . , xn ) | xi ∈ Ai, i = 1, 2, . . . , n}. i=1 5
Nˆu A1 = A2 = · · · = An = A th` t´ch A × A × · · · × A (A c´ mˇt n lˆn) thu.`.ng d u.o.c k´ ´ ` e ıı oa a o ¯. y . n hiˆu l` A . ea . u´ ` Ch´ y rˇ ng, n´i chung, A × B = B × A. D˜ nhiˆn A × ∅ = ∅. a o ı e 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)}. B`i tˆp aa . 1. Gia su. X := {1, 2, . . . , 10}. Dˇt A := {1, 4, 7, 10}, B := {1, 2, 3, 4, 5} v` C := {2, 4, 6, 8}. -a ˙˙ ’’ a . ` n tu. cua mˆi tˆp ho.p sau: ˜a ˙˙ ’’ Liˆt kˆ c´c phˆ e ea a o. . . (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 ). 2. Gia su. X := {1, 2, 3} v` Y := {x, y }. Liˆt kˆ c´c phˆn tu. cua mˆi tˆp ho.p sau: ˜. ` ˙˙ ’’ a˙˙ ’’ a e ea oa . . (a) X 2 . (b) X × Y. (c) Y × X. (d) Y 3. 3. Liˆt kˆ tˆ t ca c´c phˆn hoach cua c´c tˆp ho.p sau: ´’ e ea ˙a ˙aa ’ a . . . . (a) {1}. (b) {1, 2}. 6
(c) {a, b, c}. (d) {a, b, c, d}. 4. X´c d inh mˆi quan hˆ gi˜.a c´c cˇp tˆp ho.p sau: ´ a ¯. o euaaa . .. . (a) {1, 2, 3} v` {1, 3, 2}. a (b) {1, 2, 2, 3} v` {1, 2, 3}. a (c) {1, 1, 3} v` {3, 3, 1}. a (d) {x ∈ R | x2 + x = 2} v` {1, −2}. a (e) {x ∈ R | 0 < x ≤ 2} v` {1, 2}. a 5. K´ hiˆu P (X ) l` tˆp ho.p m` c´c phˆn tu. cua n´ l` c´c tˆp con cua X. Liˆt kˆ tˆ t ca ` ´’ a ˙ ˙ oaa a ’’ ˙ ’ e ea ˙ ye aa aa . . . . . c´c phˆn tu. cua P ({a, b}) v` P ({a, b, c}). ` a˙˙ ’’ a a 6. Gia su. X c´ 10 phˆn tu.. C´ bao nhiˆu tˆp ho.p con thu.c su. cua tˆp ho.p X ? Tˆ’ng ˙ ` ˙˙ ’’ a˙ ’ .˙a ’. o o ea o . . . . qu´t? a 7. Gia su. X v` Y l` c´c tˆp ho.p kh´c trˆng sao cho X × Y = Y × X. C´c tˆp ho.p X v` ´ ˙˙ ’’ a aa a a o aa a . . . . ˙ i thoa nh˜.ng d ` u kiˆn g` ’ ˙ ’ Y pha u ¯iˆ e e ı? . 8. Ch´.ng minh hoˇc cho phan v´ du c´c quan hˆ (A, B, C l` nh˜.ng tˆp ho.p con cua tˆp ˙ ı.a ’ ˙a ’. u a e au a . . . . .p X ) sau: ho . (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 . 9. Dˇng th´.c n`o du.´.i d ay l` dung? -a ˙ ’ ua o ¯ˆ a ¯´ (a) A ∩ B = A. (b) A ∪ B = A. (c) (A ∩ B )c = B c . 10. T` hiˆu d oi x´.ng cua hai tˆp ho.p A := {1, 2, 3} v` B := {2, 3, 4, 5}. ´ ˙ ’ ım e ¯ˆ u a a . . . 11. Gia su. C l` mˆt d u.`.ng tr`n v` A l` tˆp tˆ t ca c´c d u.`.ng k´nh cua d .`.ng tr`n C. ´’ ˙˙ ’’ aa a ˙ a ¯o ˙ ¯u o ’ a o ¯o oa ı o . . X´c d .nh ∩A∈A A. a ¯i 7
12. K´ hiˆu P l` tˆp ho.p tˆ t ca c´c sˆ nguyˆn l´.n ho.n 1. V´.i mˆi sˆ tu. nhiˆn i ≥ 2, d ˇt ˜´ ´’ ´ . a ˙a o ye aa eo o oo. e ¯a . . . Ai := {ik | k ≥ 2, k ∈ P}. Mˆ ta tˆp ho.p P \ ∞ Ai . o˙a’. . i=2 13. Ch´.ng minh c´c d ang th´.c sau (gia su. c´c tˆp d o.c x´t d` u l` tˆp con cua tˆp X ˙ ’ ˙ ˙ a a ¯u . e ¯ˆ a a ’’ ˙a ’. u a ¯ˇ u e . . n`o d ´): a ¯o A ∩ (A1 ∪ A2 ∪ · · · ∪ An ) = (A ∩ A1) ∪ (A ∩ A2) ∪ · · · ∪ (A ∩ An ). (A1 ∩ A2 ∩ · · · ∩ An )c = Ac ∪ Ac ∪ · · · ∪ Ac . 1 2 n ´ 1.2 Anh xa . -. ´ 1.2.1 Dinh ngh˜ v` t´ chˆ t ıa a ınh a Mˆt kh´i niˆm co. ban kh´c cua to´n hoc hiˆn d . i l` kh´i niˆm ´nh xa, mo. rˆng kh´i niˆm ˙ ’ a˙ ’ ˙o ’. o ae a e ¯a a a e a ae . . . . . . . ´ h`m sˆ. a o Dinh ngh˜ 1.2.1. Cho X v` Y l` hai tˆp ho.p bˆ t k`. Mˆt ´nh xa (hay h`m sˆ) t`. tˆp -. ´ ´ ıa a a a ay oa a o ua . . . . . ho.p X v`o tˆp ho.p Y l` mˆt tu.o.ng u.ng mˆi phˆn tu. cua X mˆt phˆn tu. x´c d .nh cua Y. ˜ ` ` a˙˙ ’’ a ˙ a ¯i ’ ˙ ’ aa ao ´ o o . . . . . Gia su. f l` mˆt ´nh xa t`. tˆp ho.p X v`o tˆp ho.p Y. Khi d o ta viˆt f : X → Y ; nˆu ´ ´ ˙˙ ’’ a oa .ua aa ¯´ e e . . . . . . cua Y tu.o.ng u.ng v´.i phˆn tu. x d ´ v` ta viˆt x → f (x); phˆn ˙` ` ´ ` x ∈ X th` f (x) chı phˆn tu ˙ ’a˙’ ’ a˙ ’ ¯o a ı ´ o e a ˙. f (x) goi l` a nh cua phˆn tu. x qua ´nh xa f, hay l` gi´ tri cua h`m f tai x. Tˆp ho.p ` ’ ˙ ’ ˙ ’ ˙ ’ ˙a ’ tu .a a a aa. a . . . . {(x, y ) ∈ X × Y | y = f (x)} goi l` d` thi cu a ´nh xa f v` k´ hiˆu l` graph(f ). . a ¯ˆ . ˙ a ’ o ay e a . . V´ du 1.2.1. Tu.o.ng u.ng mˆi sˆ thu.c x v´.i mˆt sˆ thu.c x3 cho ta mˆt ´nh xa f : R → ˜´. .´. ı. ´ oo o oo oa . . 3 R, x → x . Cho tru.´.c mˆt tˆp ho.p A ⊆ X th` tˆp ho.p o oa ıa .. . . . f (A) := {f (x) | x ∈ A} goi l` a nh cua tˆp ho.p A qua ´nh xa f. Dˇc biˆt, tˆp ho.p f (X ) goi l` miˆn gi´ tri cua f. -a .a` . a˙ ’ ˙a ’. a.˙ ’ a ea e . . . . . . Dˆ d`ng ch´.ng minh rˇ ng: ˜a ` e u a T´ chˆt 1.2.2. Gia su. f : X → Y l` mˆt ´nh xa t`. tˆp ho.p X v`o tˆp ho.p Y. Khi d ´ ´ ˙˙ ’’ ınh a a oa .ua . aa. ¯o . . . ´ (a) Nˆu A ⊂ B ⊂ X th` f (A) ⊂ f (B ). e ı 8
(b) Nˆu Ai , i ∈ I, l` mˆt ho c´c tˆp ho.p con cu a tˆp ho.p X th` ´ ˙a. ’. e ao.aa . ı . . f Ai = f (Ai) , i∈I i∈I f Ai ⊂ f (Ai) . i∈I i∈I Dˆ’ y rˇ ng, n´i chung d ˇng th´.c sau -e´ ` ˙a ˙ ’ o ¯a u f Ai = f (Ai) i∈I i∈I khˆng dung. o ¯´ Dinh ngh˜ 1.2.3. Gia su. f : X → Y l` mˆt ´nh xa t`. tˆp ho.p X v`o tˆp ho.p Y. -. ˙˙ ’’ ıa a oa .ua aa . . . . . (a) Anh xa f goi l` mˆt-mˆt (hoˇc d o.n ´nh) nˆu v´.i moi x, x ∈ X m` x = x th` ´ ´o .aoo a¯ a e a ı . . . . . f ( x) = f ( x ) . ´ (b) f goi l` ´nh xa lˆn (hoˇc to`n ´nh) nˆu f (X ) = Y. . aa .e a aa e . (c) f goi l` mˆt-mˆt lˆn (hoˇc song ´nh) nˆu f d` ng th`.i l` mˆt-mˆt v` l` lˆn; n´i c´ch ´ .ao oe a a e ¯ˆo oao o aae oa . . . . . .i mˆi phˆn tu. y ∈ Y c´ duy nhˆ t mˆt phˆn tu. x ∈ X sao cho f (x) = y. ˜ ` ´o ` a˙ ’ a˙ ’ kh´c, v´ a o o o a . ´ V´ du 1.2.2. (a) Anh xa ı. . f : R → R, x → sin x, l` mˆt-mˆt nhu.ng khˆng l` ´nh xa lˆn. ao o o aa .e . . ´ (b) Anh xa1 . g : R → N, x → [x ], l` lˆn nhu.ng khˆng l` ´nh xa mˆt-mˆt. ae o aa .o o . . ´ (c) Anh xa . x → x3 , h : R → R, l` mˆt-mˆt v` lˆn. ao o ae . . V´.i mˆt ´nh xa t`y y f : X → Y v` v´.i mˆt tˆp ho.p B ⊆ Y, tˆp ho.p o oa .u´ ao oa a . .. . . . {x ∈ X | f (x) ∈ B } goi l` nghich a nh cua tˆp ho.p B qua ´nh xa f v` d .o.c k´ hiˆu l` f −1 (B ). R˜ r`ng f −1 (Y ) = .˙ ’ ˙a. ’. .a a a ¯u . y e a oa . . .ng c´ thˆ’ xay ra rˇ ng ∅ = B ⊂ Y v` f −1 (B ) = ∅. ˙’ −1 ` oe˙ X v` f (∅) = ∅, nhu a a a Phˆn nguyˆn cua sˆ thu.c x, k´ hiˆu [x], l` sˆ nguyˆn l´.n nhˆt khˆng vu.o.t qu´ x. 1 ` ’´ ´ ´ ˙o. a e ye ao eo a o a . . 9
Nˆu tˆp ho.p B ⊂ Y chı gˆm c´ mˆt phˆn tu. y, t´.c l` B = {y }, th` thay cho k´ hiˆu ´. ˙` ` ’o ˙ ’ ea oo a ua ı ye . . . .`.ng k´ hiˆu vˇn tˇt l` f −1 (y ). −1 ´´ f ({y }) ta thu o ye aaa . Dˆ d`ng ch´.ng minh rˇ ng: ˜a ` e u a T´ chˆt 1.2.4. Gia su. f : X → Y l` mˆt ´nh xa t`. tˆp ho.p X v`o tˆp ho.p Y. Khi d ´ ´ ˙˙ ’’ ınh a a oa .ua . aa. ¯o . . . (a) Nˆu B ⊂ C ⊂ Y th` f −1 (B ) ⊂ f −1 (C ). ´ e ı (b) Nˆu Bi , i ∈ I, l` mˆt ho c´c tˆp ho.p con cu a tˆp ho.p Y th` ´ ˙a. ’. e ao.aa . ı . . f −1 f −1 (Bi ) , Bi = i∈I i∈I f −1 f −1 (Bi ) . Bi = i∈I i∈I (c) Nˆu B, C l` hai tˆp ho.p con cu a tˆp ho.p Y th` ´ ˙a. ’. e a a. ı . f −1 ( B \ C ) = f −1 ( B ) \ f −1 ( C ) . -a Dˇc biˆt e . . f −1 ( Y \ B ) = X \ f −1 ( B ) . (d) V´.i moi tˆp ho.p con B ⊂ Y ta d` u c´ o .a . ¯ˆ o e . f [f −1 (B )] ⊆ B. (e) V´.i moi tˆp ho.p con A ⊂ X ta d` u c´ o .a. ¯ˆ o e . f −1 [f (A)] ⊇ A. Dˆ’ y rˇ ng c´c d ang th´.c -e´ ` ˙a ˙ ’ a ¯ˇ u f −1 [f (A)] = A v` f [f −1 (B )] = B a n´i chung khˆng dung. o o ¯´ ´ ´ 1.2.2 Anh xa han chˆ e .. Gia su. f : X → Y l` mˆt ´nh xa t`. tˆp ho.p X v`o tˆp ho.p Y v` gia su. Z l` mˆt tˆp ho.p ˙˙ ’’ a˙˙ ’’ a oa .ua aa aoa . . . . . .. . ´ ˙ ’ con cua X. Anh xa . f |Z : Z → Y .i ˙ ’ x´c d .nh bo a ¯i f |Z (x) = f (x), x ∈ Z, d u.o.c goi l` han chˆ cu a f lˆn Z, c`n ´nh xa f d u.o.c goi l` th´c triˆ’n cua f |Z lˆn X. Hiˆ’n ˙˙ ˙ ´’ e˙ ’ ¯. . a. e oa . ¯. . a a e e e nhiˆn e 10
´ (a) Nˆu f l` mˆt-mˆt th` f |Z c˜ng l` mˆt-mˆt . e ao o ı u ao o . . . . (b) V´.i moi tˆp ho.p con B cua Y ta d` u c´ ˙ ’ o .a ¯ˆ o e . . (f |Z )−1 (B ) = f −1 (B ) ∩ Z. Ho.p cu a c´c ´nh xa ˙ ’ aa 1.2.3 . . Gia su. X, Y v` Z l` ba tˆp ho.p v` ta c´ c´c ´nh xa ˙˙ ’’ a a a a oaa . . . f : X → Y, g : Y → Z. Khi d ´ c´ thˆ’ thiˆt lˆp ´nh xa ˙ eaa´. ¯o o e . g ◦ f : X → Z, x → g [f (x)]. Anh xa g ◦ f d u.o.c goi l` ho.p cu a c´c ´nh xa f v` g. ´ ˙ aa ’ ¯. .a. a . . V´ du 1.2.3. Cho hai ´nh xa ı. a . x → x2 , f : R → R, g : R → R, y → y − 1. Ta c´ ´nh xa ho.p oa .. x → x2 − 1. g ◦ f : R → R, T`. d inh ngh˜ dˆ d`ng suy ra ıa ˜ a u ¯. e ´ T´ chˆt 1.2.5. Cho hai ´nh xa ınh a a . f : X → Y, g : Y → Z. (a) Nˆu f v` g l` mˆt-mˆt (tu.o.ng u.ng, lˆn, mˆt-mˆt lˆn) th` ´nh xa ho.p g ◦ f c˜ng l` ´ e a aoo ´ e o oe ıa u a . . . . .. .o.ng u.ng, lˆn, mˆt-mˆt lˆn). mˆt-mˆt (tu oo ´ e o oe . . . . (b) V´.i moi tˆp ho.p con A cu a X ta d` u c´ ˙ ’ o .a. ¯ˆ o e . (g ◦ f )(A) = g [f (A)]. (c) V´.i moi tˆp ho.p con C cu a Z ta d` u c´ ˙ ’ o .a. ¯ˆ o e . (g ◦ f )−1 (C ) = f −1 [g −1 (C )]. 11
Anh xa ngu.o.c ´ 1.2.4 . . Gia su. ˙˙ ’’ f: X →Y l` ´nh xa mˆt-mˆt lˆn. Khi d o v´.i mˆi phˆn tu. y ∈ Y tˆn tai duy nhˆ t mˆt phˆn tu. x ∈ X ˜ ` `. ´o ` a˙ ’ a˙ ’ aa .o oe ¯´ o o o a . . . .i vˆy f −1 (y ) = {x}. Do d o ta c´ thˆ’ thiˆt lˆp mˆt ´nh xa ˙ ea ´. a˙ . ’ sao cho f (x) = y, v` bo a ¯´ oe oa . . g: Y → X x´c d .nh bo.i cˆng th´.c: v´.i moi y ∈ Y, ˙o ’ a ¯i u o . ´ g (y ) = x nˆu f (x) = y. e Anh xa g goi l` ´nh xa ngu.o.c cua f v` k´ hiˆu l` f −1 . Hiˆ’n nhiˆn f −1 : Y → X l` ´nh xa ´ ˙ ˙ ’ . aa ay e a e e aa . . . . . −1 −1 mˆt-mˆt lˆn v` (f ) = f. o oe a . . ´ V´ du 1.2.4. (a) Anh xa d` ng nhˆ t ´ ı. . ¯ˆ o a idX : X → X, x → x, l` ´nh xa mˆt-mˆt lˆn v` (idX )−1 = idX . aa .o oe a . . ´ (b) Anh xa mˆt-mˆt v` lˆn .o o ae . . x → x3 , f : R → R, c´ ´nh xa ngu.o.c l` oa .a . 1 f −1 : R → R, y → y3. T`. d inh ngh˜ dˆ d`ng suy ra ıa ˜ a u ¯. e T´ chˆt 1.2.6. (a) Gia su. f : X → Y l` ´nh xa mˆt-mˆt lˆn. Khi d ´ ´ ˙˙ ’’ ınh a aa . o oe ¯o . . f −1 ◦ f = idX , f ◦ f −1 = idY . (b) Nˆu f : X → Y, g : Y → Z l` nh˜.ng ´nh xa mˆt-mˆt lˆn, th` ´nh xa ho.p (g ◦ f ) : X → Z ´ e aua . o oe ıa . . .. c˜ng mˆt-mˆt lˆn v` u o oe a . . ( g ◦ f ) −1 = f −1 ◦ g −1 . Lu.c lu.o.ng cu a mˆt tˆp ho.p ˙ ’ 1.2.5 oa . . . . . Dinh ngh˜ 1.2.7. (a) Hai tˆp ho.p A v` B goi l` c´ c`ng lu.c lu.o.ng nˆu tˆn tai ´nh xa -. e ` .a ´o ıa a a . aou . . . . . mˆt-mˆt v` lˆn f : A → B. o o ae . . (b) Tˆp ho.p trˆng, tˆp ho.p {x1 , x2, . . . , xn } v` c´c tˆp ho.p c`ng lu.c lu.o.ng v´.i n´ goi l` ´ a o a aa a .u o o.a . . . . . . . .p h˜.u han. tˆp ho u a. . . 12
(c) Tˆp ho.p c´c sˆ tu. nhiˆn N v` c´c tˆp ho.p c`ng lu.c lu.o.ng v´.i n´ goi l` tˆp ho.p dˆm ´ ´ a . ao. e aa a .u o o . a a . ¯e . . . . . .o.c. du . ¯ (d) Tˆp ho.p c´c sˆ thu.c R v` c´c tˆp ho.p c`ng lu.c lu.o.ng v´.i n´ goi l` tˆp ho.p khˆng dˆm ´ ´ a .ao. aa a .u o o . aa . o ¯e . . . . . .o.c. du . ¯ (e) Tˆp ho.p A goi l` khˆng qu´ dˆm d u.o.c, nˆu A l` mˆt tˆp ho.p h˜.u han (v` c´ thˆ’ l` ˙ ´ ´ a .ao a ¯e ¯ . e aoa u ao ea . . .. . . .p d e m d .o.c. ´ .´ ´ trˆng), hoˇc nˆu A l` mˆt tˆp ho ¯ˆ ¯u . o ae aoa.. . Gia su. A := {x1 , x2, . . . , xn } l` mˆt tˆp ho.p h˜.u han kh´c trˆng sao cho xi = xj v´.i moi ´ ˙˙ ’’ aoa u a o o .. . . . .p A c´ n phˆn tu. v` k´ hiˆu #A := n. Tˆp ho.p trˆng ∅ khˆng ` ´ ˙aye ’ i = j. Khi d ´ ta n´i tˆp ho ¯o oa o a a o o . . . . . c´ phˆn tu. n`o ca, v` vˆy d ˇt #∅ := 0. Nˆu A l` tˆp ho.p kh´c trˆng v` khˆng phai tˆp ho.p o` ´ ´ a ˙ a ˙ ı a ¯a ’ ’ ˙a ’. e aa a o ao . . . . . .u han, d at #A := +∞. h˜u ¯ˇ . . B`i tˆp aa . 1. Gia su. X := {1, 2, 3}, Y := {a, b, c, d}, Z := {w, x, y, z }. X´t c´c ´nh xa f : X → Y v` ˙˙ ’’ e aa a . .i ˙ ’ g : Y → Z cho bo f (1) = b, f (2) = c, f (3) = a, g (a) = x, g (b) = x, g (c) = z, g (d) = w. X´c d .nh ´nh xa ho.p f ◦ g. a ¯i a .. 2. Gia su. f : X → N, x → x2, v´.i X := {−5, −4, . . . , 4, 5}. f l` ´nh xa mˆt-mˆt? f l` ˙˙ ’’ o aa .o o a . . a ´nh xa lˆn? e . 3. C´ bao nhiˆu ´nh xa t`. tˆp {a, b} v`o tˆp {1, 2}. Nh˜.ng ´nh xa n`o l` mˆt-mˆt? o ea .ua aa u a .aao o . . . . .ng ´nh xa n`o l` lˆn? Nh˜ a u . a ae 4. Gia su. X := {a, b, c} v` f : X → X cho bo.i ˙˙ ’’ ˙ ’ a f (a) = b, f (b) = a, f (c) = b. Dinh ngh˜ d˜y c´c ´nh xa f n : X → X, n = 1, 2, . . . , bo.i f 1 := f v` f n := f n−1 ◦ f -. ˙ ’ ıa a a a a . .i moi n ≥ 2. H˜y x´c d nh c´c ´nh xa f 2 , f 3 , f 9 , f 789. v´ o a a ¯i aa . . . 5. Gia su. X := {0, 1, 2, 3, 4} v` ´nh xa f : X → X x´c d .nh bo.i ˙˙ ’’ ˙ ’ aa a ¯i . f (x) := 4x mod 5. f l` anh xa mˆt-mˆt? f l` ´nh xa lˆn? a´ .o o aa .e . . 6. Gia su. m, n l` c´c sˆ nguyˆn du.o.ng. Gia su. X := {0, 1, 2, . . . , m − 1}. X´t anh xa ´ ˙˙ ’’ ˙˙ ’’ aa o e e´ . .i ˙’ f : X → X cho bo f (x) := nx mod m. T` nh˜.ng d ` u kiˆn cua m v` n dˆ’ f l` ´nh xa mˆt-mˆt v` lˆn? ˙ aa e˙ ’ ım u ¯iˆ e a ¯e .o o ae . . . 13