Bài giảng Toán rời rạc - Phạm Tiến Sơn

Nội dung text: Bài giảng Toán rời rạc - Phạm Tiến Sơn

1. . TOAN´ RO` I RA. C . Pha.m Tiˆe´n Son D- `aLa.t, 2005
2. Mu. c lu. c . MO˙’ D- `Aˆ U 6 1 PHEP´ D- Eˆ´M 9 1.1 C´acnguyˆenl´yco. ba˙’n cu˙’a ph´epd¯ˆe´m 9 1.1.1 Nguyˆenl´ytˆo˙’ng 9 1.1.2 Nguyˆenl´yt´ıch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 . 1.1.3 Nguyˆenl´ybao h`am-loa.i tr`u 13 . 1.2 Ho´anvi. v`atˆo˙’ ho. p 15 . 1.3 C´acthuˆa.t to´ansinh ra ho´anvi. v`atˆo˙’ ho. p 20 . 1.4 Ho´anvi. v`atˆo˙’ ho. p suy rˆo.ng 25 . . 1.5 C´achˆe. sˆo´ nhi. th´uc v`ac´acd¯ˆo`ng nhˆa´t th´uc 32 1.6 Nguyˆenl´ychuˆo`ng chim bˆo` cˆau. . . . . . . . . . . . . . . . . . . . . . . . . . 36 . 1.6.1 Nguyˆenl´ychuˆo`ng chim bˆo` cˆau(da.ng th´u nhˆa´t) . . . . . . . . . . . . 36 . 1.6.2 Nguyˆenl´ychuˆo`ng chim bˆo` cˆau(da.ng th´u hai) . . . . . . . . . . . . . 37 . 1.6.3 Nguyˆenl´ychuˆo`ng chim bˆo` cˆau(da.ng th´u ba) . . . . . . . . . . . . . 39 2 QUAN HEˆ. 43 2.1 Quan hˆe. hai ngˆoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.2 Quan hˆe. v`ama trˆa.n 48 3
3. . . 2.3 Quan hˆe. th´u tu. 54 . . . . 2.4 Quan hˆe. tuong d¯uong 62 2.5 Bao d¯´ongcu˙’a quan hˆe. 69 2.6 Lattice cu˙’a c´acphˆanhoa.ch 75 2.6.1 Thuˆa.t to´angiao c´acphˆanhoa.ch 77 2.6.2 Thuˆa.t to´antrˆo.n c´acphˆanhoa.ch 78 ´ 3 D- A. ISOˆ BOOLE 81 3.1 Lattice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 3.2 Latiice phˆanbˆo´ 90 3.3 D- a.i sˆo´ Boole . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 3.4 H`amBoole . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 3.5 Biˆe˙’u diˆe˜n c´ach`amBoole qua hˆe. tuyˆe˙’n, hˆo.i v`aphu˙’ d¯i.nh . . . . . . . . . . . 107 3.6 Biˆe˙’u diˆe˜n tˆo´i thiˆe˙’u cu˙’a h`amBoole . . . . . . . . . . . . . . . . . . . . . . . 111 3.6.1 Kh´ainiˆe.m 111 3.6.2 Phu.o.ng ph´apba˙’n d¯ˆo` Karnaugh . . . . . . . . . . . . . . . . . . . . . 112 4 MA˜ TUYEˆ´NT´INH 119 4.1 Mo˙’. d¯ˆa`u 119 4.1.1 Kh´ainiˆe.m 119 4.1.2 M˜aph´athiˆe.n lˆo˜i 120 4.1.3 M˜asu˙’.a sai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 4.2 C´ackh´ainiˆe.m 122 4.3 Khoa˙’ng c´ach Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 . 4.4 Hˆo.i ch´ung 139 4.4.1 Gia˙’i m˜ad`ungba˙’ng chuˆa˙’n . . . . . . . . . . . . . . . . . . . . . . . . 140 4
4. 4.5 M˜aho`anha˙’o 143 4.6 M˜aHamming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 ` 5 D- Oˆ THI. 149 5.1 C´ackh´ainiˆe.m 149 5.2 Dˆaychuyˆe` n v`achu tr`ınh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 . . 5.3 Chu tr`ınhHamilton v`ab`aito´anngu`oi du li.ch . . . . . . . . . . . . . . . . . 162 5.3.1 Quy tˇa´c t`ımchu tr`ınhHamilton . . . . . . . . . . . . . . . . . . . . . 164 5.3.2 M˜aGray . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 . . 5.4 D- u`ong d¯iv`ama.ch 169 5.4.1 Thuˆa.t to´an . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 5.5 Ma trˆa.n biˆe˙’u diˆe˜n d¯ˆo` thi. 173 5.5.1 Ma trˆa.n kˆe` 173 5.5.2 Ma trˆa.n liˆenthuˆo.c 175 . 5.6 D- ˇa˙’ng cˆa´u gi˜ua c´acd¯ˆo` thi. 179 5.7 D- `ˆo thi. phˇa˙’ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 6 CAYˆ 191 6.1 Mo˙’. d¯ˆa`u 191 6.1.1 C´ackh´ainiˆe.m 191 6.1.2 M˜aHuffman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 6.2 Cˆaybao tr`um. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 6.2.1 Thuˆa.t to´ant`ımkiˆe´m theo chiˆe` u rˆo.ng x´acd¯i.nh cˆaybao tr`um. . . . . 198 6.2.2 Thuˆa.t to´ant`ımkiˆe´m theo chiˆe` u sˆaux´acd¯i.nh cˆaybao tr`um . . . . . 199 6.3 Cˆaybao tr`umnho˙’ nhˆa´t 200 6.3.1 Thuˆa.t to´anKruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 5
5. 6.4 Liˆe.t kˆecˆay. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204 6.5 Cˆaynhi. phˆan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 . 6.5.1 Thuˆa.t to´anxˆaydu. ng cˆayt`ımkiˆe´m nhi. phˆan. . . . . . . . . . . . . . 210 T`ailiˆe.u tham kha˙’o 215 6
6. . MO˙’ D- `Aˆ U . . . . . To´anho.c r`oi ra.c l`amˆo.t bˆo. phˆa.n cu˙’a To´anho.c nhˇa`m nghiˆenc´uu c´acd¯ˆo´i tuo. ng r`oi ra.c: . . . . nghiˆenc´uu c´accˆa´u tr´ucr`oi ra.c kh´acnhau v`ac´acphuong ph´apgia˙’i c´acvˆa´n d¯ˆe` c´oliˆenquan d¯ˆe´n c´accˆa´u tr´ucn`ay. . . . . . Thˆongtin luu tr˜u v`avˆa.n h`anhtrong m´ayt´ınhdu´oi da.ng c´act´ınhiˆe.u r`oi ra.c (c´acm´ay . . . t´ınhliˆentu. c chı˙’ l`ac´acm´ayt´ınhtuong tu. , chuyˆendu. ng). V`ıvˆa.y cˆongcu. d`ungd¯ˆe˙’ biˆe˙’u diˆe˜n . . thˆongtin trong m´ayv`axu˙’ l´yc´acthˆongtin n`ayl`aTo´anho.c r`oi ra.c. . . . . Ngo`aira, c´acphuong ph´apv`akˆe´t qua˙’ cu˙’a To´anho.c r`oi ra.c c´othˆe˙’ d`ungd¯ˆe˙’ gia˙’i quyˆe´t tru. c . . . tiˆe´p nhiˆe` u vˆa´n d¯ˆe` d¯ˇa.t ra cu˙’a Tin ho.c nhu logic, h`amd¯a. i sˆo´ logic, tˆo˙’ ho. p trˆent`u To´an . . . ho.c r`oi ra.c chuˆa˙’n bi. sˇa˜n v`acung cˆa´p c´accˆongcu. , phuong ph´apluˆa.n d¯ˆe˙’ gia˙’i quyˆe´t nhiˆe` u . . . vˆa´n d¯ˆe` cu˙’a Tin ho.c. C´othˆe˙’ n´oiTo´anho.c r`oi ra.c l`ang`anhTo´anho.c co so˙’ cho Tin ho.c. . . Mu. c d¯´ıch cu˙’a gi´aotr`ınhnhˇa`m cung cˆa´p mˆo.t sˆo´ cˆongcu. To´anho.c d¯ˆe˙’ bu´oc d¯ˆa`u d¯iv`ao . . . Tin ho.c. Gi´aotr`ınhd¯uo. c tr`ınhb`aymˆo.t c´ach d`antra˙’i hon l`ad¯isˆauv`aomˆo.t vˆa´n d¯ˆe` cu. thˆe˙’. . . Cuˆo´i mˆo˜i phˆa`n c´oc´acb`aitˆa.p nhˇa`m cu˙’ng cˆo´ nh˜ung kiˆe´n th´uc d¯˜aho.c. Hy vo.ng rˇa`ng gi´ao . . . tr`ınhn`ayd¯´ap´ung d¯uo. c phˆa`n n`aoyˆeucˆa`u ho.c tˆa.p cu˙’a c´acba.n sinh viˆen. . . . Gi´aotr`ınhbao gˆo`m s´auchuong v´oi 20 t`ailiˆe.u tham kha˙’o tr`ınhb`ayc´acvˆa´n d¯ˆe` sau: . . . . . Chuong 1: Ph´epd¯ˆe´m. D- `ˆe cˆa.p d¯ˆe´n c´acphuong ph´apco ba˙’n cu˙’a ph´epd¯ˆe´m: Nguyˆen . l´yt´ıch, nguyˆenl´ytˆo˙’ng, nguyˆenl´ybao h`am-loa.i tr`u, nguyˆenl´yc´acchuˆo`ng chim bˆo` cˆau . . . . . . Ch´ungd¯´ongvai tr`oquan tro.ng trong Tin ho.c, chˇa˙’ng ha.n: d¯ˆe˙’ u´oc luo. ng th`oi gian thu. c hiˆe.n . . cu˙’a mˆo.t thuˆa.t to´anch´ungta cˆa`n d¯ˆe´m sˆo´ th`oi gian thi h`anht`ung d`onglˆe.nh hoˇa.c c´acv`ong lˇa.p. Ph´epd¯ˆe´m c˜ungd¯´ongvai tr`oquan tro.ng trong l´ythuyˆe´t x´acsuˆa´t. . . . . . . . . Chuong 2: Quan hˆe Tr`ınhb`ayc´acquan hˆe. th´u tu. , quan hˆe. tuong d¯uong v`acuˆo´i c`ung . . . l`aquan hˆe. tˆo˙’ng qu´attrˆennh˜ung tˆa.p h˜uu ha.n. Ch´ungta c˜ungx´etmˆo´i quan hˆe. gi˜ua c´ac . quan hˆe. v´oi ma trˆa.n hay d¯ˆo` thi. biˆe˙’u diˆe˜n n´o. . . . . . . Chuong 3: D- a. i sˆo´ Boole. Thuˆa.t ng˜u “d¯a.i sˆo´ Boole” d¯uo. c su˙’ du. ng d¯ˆe˙’ mˆota˙’ nhiˆe` u l˜ınh . . . . . . vu. c c´oliˆenquan, t`u tu duy logic v`ac´acba˙’ng chˆantri. d¯ˆe´n c´acph´epto´ansˆo´ ho.c d¯uo. c thu. c . . . . . . . . hiˆe.n bo˙’ i c´acma.ch d¯iˆe.n tu˙’ . Chuong n`aybˇa´t d¯ˆa`u v´oi mˆo´i quan hˆe. gi˜ua c´actˆa.p d¯uo. c sˇa´p . . . th´u tu. v`ac´aclattice. Kˆe´ tiˆe´p l`ad¯a.i sˆo´ Boole v`avˆa´n d¯ˆe` cu. c tiˆe˙’u ho´ah`amBoole. 7
7. . . . . . . Chuong 4: M˜atuyˆe´n t´ınh. Gi´oi thiˆe.u so luo. c vˆe` l´ythuyˆe´t m˜abao gˆo`m c´acm˜acho ph´ep . . . . . ph´athiˆe.n v`asu˙’ a sai. D- ˆayl`avˆa´n d¯ˆe` th`oi su. do su. ph´attriˆe˙’n c´accˆongnghˆe. m´oi trong viˆe.c . . . truyˆe` n v`aluu tr˜u d˜u liˆe.u. . . . . . . Chuong 5: D- `ˆo thi Chuong n`aygi´oi thiˆe.u mˆo.t sˆo´ kh´ainiˆe.m v`ab`aito´anco ba˙’n cu˙’a l´y . . . thuyˆe´t d¯ˆo` thi. nhu chu tr`ınhEuler, chu tr`ınhHamilton, d¯u`ong d¯ingˇa´n nhˆa´t, t´ınhphˇa˙’ng cu˙’a d¯ˆo` thi . . . . . . Chuong 6: Cˆay. Nˆo.i dung ch´ınhcu˙’a chuong d¯ˆe` cˆa.p d¯ˆe´n nh˜ung vˆa´n d¯ˆe` : Xˆaydu. ng m˜atˆo´i . uu Huffman, cˆaybao tr`umv`ahˆe. c´acchu tr`ınhd¯ˆo.c lˆa.p, cˆaybao tr`umtˆo´i thiˆe˙’u, liˆe.t kˆecˆay. . Tˆoid¯ˇa.c biˆe.t c´amon c´acd¯ˆo`ng nghiˆe.p, d¯ˇa.c biˆe.t Th.s. Trˆa`n Tuˆa´n Minh, c´acba.n b`ev`ac´ac . sinh viˆenv`ınh˜ung d¯´ongg´opcu˙’a ho. trong qu´atr`ınhbiˆensoa.n gi´aotr`ınhn`ay. . . . Tˆoichˆanth`anhc´amon ba.n d¯o.c vˆe` nh˜ung ´ykiˆe´n d¯ˆo´i v´oi c´acthiˆe´u s´otkhˆongthˆe˙’ tr´anh kho˙’i cu˙’a cuˆo´n s´ach. D- `aLa.t, ng`ay12 th´ang6 nˇam2003 . Pha.m Tiˆe´n Son 8
8. Chu.o.ng 1 PHEP´ D- Eˆ´M . . . . To´antˆo˙’ ho. p nghiˆenc´uu vˆe` c´ach sˇa´p xˆe´p c´acd¯ˆo´i tuo. ng, l`amˆo.t bˆo. phˆa.n quan tro.ng cu˙’a . . . . . . . . . to´anho.c r`oi ra.c. Nh˜ung vˆa´n d¯ˆe` cu˙’a tˆo˙’ ho. p d¯uo. c nghiˆenc´uu t`u Thˆe´ ky˙’ 17, liˆenquan tru´oc . . . . tiˆend¯ˆe´n c´actr`ochoi may ru˙’i. Ng`aynay to´antˆo˙’ ho. p d¯uo. c d`ungrˆo.ng r˜aitrong tin ho.c. . . . . . Mu. c d¯´ıch ch´ınhcu˙’a chuong n`ayl`athiˆe´t lˆa.p mˆo.t sˆo´ phuong ph´apd¯ˆe´m c´actˆa.p h˜uu ha.n . . phˆa`n tu˙’ m`akhˆongliˆe.t kˆec´acphˆa`n tu˙’ cu˙’a ch´ung. 1.1 C´acnguyˆenl´yco. ba˙’n cu˙’a ph´epd¯ˆe´m . . . V´oitˆa.p h˜uu ha.n phˆa`n tu˙’ S, ta k´yhiˆe.u #S l`asˆo´ phˆa`n tu˙’ cu˙’a tˆa.p S. Do d¯´o#S = #T nˆe´u . hai tˆa.p S v`a T c´oc`ungsˆo´ c´acphˆa`n tu˙’ . Ch´u´yrˇa`ng #∅ = 0, #{1, 2, . . . , n} = n v´o.i n ∈ N. . Ch´ungta bˇa´t d¯ˆa`u v´oi mˆo.t sˆo´ nguyˆenl´yd¯ˆe´m. 1.1.1 Nguyˆenl´ytˆo˙’ng . . . . . Gia˙’ su˙’ A1,A2, ,Am l`ac´acsu. kiˆe.n d¯ˆoimˆo. t loa. i tr`u nhau; v`agia˙’ su˙’ c´acsu. kiˆe.n A1,A2, ,Am . . . . c´otuong ´ung n1, n2, . . . , nm c´ach xa˙’y ra. Khi d¯´osu. kiˆe.n (hoˇa. c A1, hoˇa. c A2, , hoˇa. c Am) c´o n1 + n2 + ããã + nm c´ach xa˙’y ra. . . . . . V´ıdu. 1.1.1 Gia˙’ su˙’ l´op truo˙’ ng c´othˆe˙’ l`amˆo.t n˜u sinh, hoˇa.c l`amˆo.t nam sinh. C´obao nhiˆeu . . . . c´ach cho.n l´op truo˙’ ng kh´acnhau nˆe´u sˆo´ ho.c sinh n˜u l`a36 v`asˆo´ nam sinh l`a20? 9
9. . . . . . . . . . . . Go.i A1 (tuong ´ung, A2) l`asu. kiˆe.n l´op truo˙’ ng l`an˜u sinh (tuong ´ung, nam sinh). Ta c´o . . . . . . . 36 c´ach cho.n l´op truo˙’ ng l`an˜u sinh v`a20 c´ach cho.n l´op truo˙’ ng l`anam sinh. Theo nguyˆen . l´ytˆo˙’ng, su. kiˆe.n (A1 hoˇa.c A2) c´o(36 + 20) = 56 c´ach cho.n. . . V´ıdu. 1.1.2 Gia˙’ su˙’ mˆo.t sinh viˆenc´othˆe˙’ cho.n d¯´ungmˆo.t chuyˆend¯ˆe` tu. cho.n trong mˆo.t trong ba danh s´ach. Ba danh s´ach n`aygˆo`m 3, 5 v`a9 chuyˆend¯ˆe` tu.o.ng ´u.ng. Ho˙’i sinh viˆen . d¯´oc´obao nhiˆeuc´ach lu. a cho.n? Theo nguyˆenl´ytˆo˙’ng, c´o3 + 5 + 9 = 17 c´ach. . . . Nhˆa.n x´et1 Nguyˆenl´ytˆo˙’ng c´othˆe˙’ ph´atbiˆe˙’u theo thuˆa.t ng˜u cu˙’a l´ythuyˆe´t tˆa.p ho. p nhu . . sau. Nˆe´u c´actˆa.p T1,T2, ,Tm d¯ˆoimˆo.t r`oi nhau th`ısˆo´ c´acphˆa`n tu˙’ cu˙’a tˆa.p T1 ∪T2 ∪ã ã ã∪Tm . . bˇa`ng tˆo˙’ng sˆo´ c´acphˆa`n tu˙’ cu˙’a c´actˆa.p n`ay;t´uc l`a Xm #(T1 ∪ T2 ∪ ∪ Tm) = #Ti. i=1 1.1.2 Nguyˆenl´yt´ıch . . . . . Gia˙’ su˙’ A1,A2, ,Am l`ac´acsu. kiˆe.n d¯ˆoimˆo. t loa. i tr`u nhau; v`agia˙’ su˙’ c´acsu. kiˆe.n A1,A2, ,Am . . . . c´otuong ´ung n1, n2, . . . , nm c´ach xa˙’y ra. Khi d¯´osu. kiˆe.n (A1 v`a A2 v`a v`a Am) c´o n1 ì n2 ì ã ã ã ì nm c´ach xa˙’y ra. . V´ıdu. 1.1.3 Gia˙’ su˙’ c´ohai mˇa.t na., ba m˜u.Ho˙’i c´omˆa´y c´ach ho´atrang? D`ungnguyˆenl´yt´ıch, c´o3 ì 2 = 6 c´ach ho´atrang kh´acnhau. C˜ungc´othˆe˙’ d`ungl´ythuyˆe´t . . tˆa.p ho. p nhu sau: Mˆo˜i c´ach ho´atrang l`amˆo.t c´ach cho.n x ∈ X v`amˆo.t c´ach cho.n y ∈ Y. Do d¯´osˆo´ c´ach ho´atrang l`asˆo´ c´accˇa.p (x, y) thuˆo.c X ì Y v`ado d¯´obˇa`ng #X ì #Y = 2 ì 3 = 6. . . . . . . . . Nhˆa.n x´et2 Nguyˆenl´yn`ayc˜ungthu`ong d¯uo. c ph´atbiˆe˙’u du´oi da.ng tˆa.p ho. p nhu sau: Gia˙’ . . . . . su˙’ c´actˆa.p T1,T2, ,Tm c´oh˜uu ha.n phˆa`n tu˙’ v`ad¯ˆoimˆo.t r`oi nhau. Khi d¯´osˆo´ phˆa`n tu˙’ cu˙’a tˆa.p t´ıch Descartes T1 ì T2 ì ã ã ã ì Tm bˇa`ng #T1 ì #T2 ì ã ã ã ì #Tm. V´ıdu. 1.1.4 C´obao nhiˆeuchuˆo˜i bit kh´acnhau c´od¯ˆo. d`ai8? Mˆo˜i bit c´ohai c´ach cho.n, hoˇa.c 0 hoˇa.c 1. Do d¯´otheo nguyˆenl´yt´ıch, c´o28 = 256 chuˆo˜i bit c´od¯ˆo. d`ai8. . V´ıdu. 1.1.5 C´obao nhiˆeuba˙’ng sˆo´ xe kh´acnhau, nˆe´u mˆo˜i ba˙’ng gˆo`m ba ch˜u c´aiv`atheo . . sau l`aba con sˆo´ (gia˙’ thiˆe´t ba˙’ng ch˜u c´aigˆo`m 26 k´ytu. )? 10
10. . Mˆo˜i ch˜u c´aic´o26 c´ach cho.n; mˆo˜i sˆo´ c´o10 c´ach cho.n. Do d¯´otheo nguyˆenl´yt´ıch, sˆo´ c´ac ba˙’ng sˆo´ xe kh´acnhau l`a: 26 ì 26 ì 26 ì 10 ì 10 ì 10 = 17.576.000. . . V´ıdu. 1.1.6 C´obao nhiˆeu´anhxa. kh´acnhau t`u tˆa.p X c´o m phˆa`n tu˙’ lˆentˆa.p Y c´o n phˆa`n tu˙’.? . Mˆo˜i ´anhxa. l`amˆo.t bˆo. m c´ach cho.n mˆo.t trong n phˆa`n tu˙’ cu˙’a Y cho mˆo˜i mˆo.t trong m phˆa`n . tu˙’ cu˙’a X. Theo nguyˆenl´yt´ıch, sˆo´ ´anhxa. n`aybˇa`ng m |n ì n ì{z ã ã ã ì n} = n . m lˆa`n . . . V´ıdu. 1.1.7 C´obao nhiˆeu´anhxa. mˆo.t-mˆo.t (d¯on ´anh)kh´acnhau t`u tˆa.p X c´o m phˆa`n tu˙’ . lˆentˆa.p Y c´o n phˆa`n tu˙’ ? . . Nˆe´u m > n : khˆongc´o´anhxa. mˆo.t-mˆo.t t`u X t´oi Y. . Gia˙’ su˙’ m ≤ n v`a X := {a1, a2, . . . , am}. . . . . . . + V´oi phˆa`n tu˙’ a1 c´o n c´ach cho.n phˆa`n tu˙’ tuong ´ung trong Y. . + V`ı´anhxa. l`amˆo.t-mˆo.t, nˆend¯ˆo´i v´oi a2 chı˙’ c`on(n − 1) c´ach cho.n. . . . . . + Tuong tu. , am chı˙’ c`on(n − m + 1) c´ach cho.n. Theo nguyˆenl´yt´ıch, sˆo´ ´anhxa. mˆo.t-mˆo.t kh´acnhau bˇa`ng n(n − 1)(n − 2) ããã (n − m + 1). . V´ıdu. 1.1.8 D- ˆe´m sˆo´ tˆa.p con cu˙’a mˆo.t tˆa.p h˜uu ha.n S. . . . . . Gia˙’ su˙’ S := {a1, a2, . . . , an}. Dˆe˜ d`angthiˆe´t lˆa.p mˆo.t tuong ´ung mˆo.t-mˆo.t gi˜ua tˆa.p con P . . cu˙’a S v´oi c´acchuˆo˜i bit d¯ˆo. d`ai n : bit th´u i bˇa`ng 1 nˆe´u v`achı˙’ nˆe´u ai ∈ P. Mˇa.t kh´ac,sˆo´ c´ac chuˆo˜i bit d¯ˆo. d`ai n l`a2n nˆensˆo´ c´actˆa.p con cu˙’a S l`a2n. . . V´ıdu. 1.1.9 Cho hai d¯oa.n chuong tr`ınhsau: Chu.o.ng tr`ınh1: Chu.o.ng tr`ınh2: k := 0; k := 0; for i1 := 1 to n1 do k := k + 1; for i1 := 1 to n1 do for i2 := 1 to n2 do k := k + 1; for i2 := 1 to n2 do for im := 1 to nm do k := k + 1; for im := 1 to nm do k := k + 1; 11
11. . . . . . Ho˙’i k s˜elˆa´y gi´atri. bao nhiˆeusau khi mˆo˜i d¯oa.n chuong tr`ınhtrˆend¯uo. c thu. c hiˆe.n? . . . . . . + Chuong tr`ınh1: C´u mˆo˜i v`onglˇa.p d¯i.a phuong, k tˇanglˆenmˆo.t d¯on vi . . . Go.i Ai l`asˆo´ lˆa`n lˇa.p cu˙’a v`onglˇa.p th´u i. Ai c´o ni kha˙’ nˇang.Hon n˜ua Ai v`a Aj, i 6= j, loa.i . tr`u nhau. Do d¯´otheo nguyˆenl´ytˆo˙’ng, sˆo´ v`onglˇa.p l`a n1 + n2 + ããã + nm. . . . . + Chuong tr`ınh2: C´u mˆo˜i v`onglˇa.p to`ancu. c, k tˇanglˆenmˆo.t d¯on vi Mˆo˜i v`onglˇa.p to`an . . cu. c do m v`onglˇa.p d¯i.a phuong gh´epla.i. Theo nguyˆenl´yt´ıch sˆo´ v`onglˇa.p to`ancu. c bˇa`ng n1 ì n2 ì ã ã ã ì nm. . . . . V´ıdu. 1.1.10 Trong nhiˆe` u tru`ong ho. p cˆa`n pha˙’i phˆo´i ho. p ca˙’ hai nguyˆenl´ytˆo˙’ng v`at´ıch: . . . . . . . Gia˙’ su˙’ mˆo˜i ngu`oi su˙’ du. ng m´ayt´ınhc´omˆo.t mˆa.t m˜a,gˆo`m t`u 6 d¯ˆe´n 8 k´ytu. ; mˆo˜i k´ytu. l`a . . mˆo.t ch˜u c´aihoa hoˇa.c l`amˆo.t con sˆo´. Mˆo˜i mˆa.t m˜anhˆa´t thiˆe´t pha˙’i ch´ua ´ıtnhˆa´t mˆo.t con sˆo´. Ho˙’i c´obao nhiˆeumˆa.t m˜ac´othˆe˙’ c´o? . Go.i P l`atˆo˙’ng sˆo´ c´acmˆa.t m˜ac´othˆe˙’ c´ov`a P6,P7,P8 l`asˆo´ c´acmˆa.t m˜ac´othˆe˙’ v´oi d¯ˆo. d`ai tu.o.ng ´u.ng bˇa`ng 6, 7, 8. Theo nguyˆenl´ytˆo˙’ng: P = P6 + P7 + P8. . . Viˆe.c t´ınhtru. c tiˆe´p P6 l`akh´o.Ta t´ınhgi´antiˆe´p nhu sau: . . . . + Sˆo´ c´acxˆauc´od¯ˆo. d`ai6, gˆo`m ch˜u v`asˆo´, bao gˆo`m ca˙’ tru`ong ho. p khˆongc´ocon sˆo´ n`ao theo nguyˆenl´yt´ıch l`a(26 + 10)6 = 366. . 6 + Sˆo´ c´acxˆaud¯ˆo. d`ai6, khˆongch´ua con sˆo´ n`aol`a26 . 6 6 + Do d¯´o P6 = 36 − 26 = 1.867.866.560. . . . Tuong tu. cho P7 v`a P8 : 7 7 P7 = 36 − 26 = 70.332.353.920, 8 8 P8 = 36 − 26 = 2.612.282.842.880. Cuˆo´i c`ung P = P6 + P7 + P8 = 2.684.483.063.360. . . Nhˆa.n x´et3 Khi c´acsu. kiˆe.n A1 v`a A2 c´othˆe˙’ xa˙’y ra d¯ˆo`ng th`oi ta khˆongthˆe˙’ d`ungnguyˆen . . . . . . l´ytˆo˙’ng. Tru`ong ho. p n`aycˆa`n su˙’ a d¯ˆo˙’i nhu sau: Nˆe´u vˆa˜n cˆo.ng (n1 + n2) ta d¯˜ad¯ˆe´m th`ua, . . . . v`ıc´otru`ong ho. p d¯˜ad¯ˆe´m hai lˆa`n c`ungmˆo.t su. kiˆe.n (mˆo.t lˆa`n trong A1, mˆo.t lˆa`n trong A2). . . . . . Tru`ong ho. p n`aychı˙’ xa˙’y ra khi n´od¯ˆo`ng th`oi c´othˆe˙’ xa˙’y ra A1 v`a A2. V`ıvˆa.y cˆa`n tr`u d¯isˆo´ . . . . tru`ong ho. p dˆoith`ua n`ay. 12
12. . 1.1.3 Nguyˆenl´ybao h`am-loa.i tr`u . . . . Gia˙’ su˙’ A1 v`a A2 l`ahai su. kiˆe.n bˆa´t k`y.Nˆe´u su. kiˆe.n A1 c´othˆe˙’ xa˙’y ra n1 c´ach, su. kiˆe.n A2 c´o . thˆe˙’ xa˙’y ra n2 c´ach, th`ısu. kiˆe.n (A1 hoˇa. c A2) c´othˆe˙’ xa˙’y ra [(n1 + n2)− sˆo´ lˆa`n (A1 v`a A2)] c´ach. . . . . Bˇa`ng thuˆa.t ng˜u tˆa.p ho. p, nguyˆenl´ybao h`am-loa.i tr`u tro˙’ th`anh: #(A1 ∪ A2) = #A1 + #A2 − #(A1 ∩ A2). V´ıdu. 1.1.11 C´obao nhiˆeuchuˆo˜i bit d¯ˆo. d`ai8 hoˇa.c bˇa´t d¯ˆa`u bˇa`ng 1, hoˇa.c kˆe´t th´ucbˇa`ng 00? (C´othˆe˙’ c´ochuˆo˜i v`u.a bˇa´t d¯ˆa`u bˇa`ng 1, v`u.a kˆe´t th´ucbˇa`ng 00). . . . . . Go.i P1 l`asˆo´ c´acchuˆo˜i bit d¯ˆo. d`ai8 bˇa´t d¯ˆa`u bˇa`ng 1. Nhu vˆa.y, phˆa`n tu˙’ th´u nhˆa´t d¯˜ad¯uo. c cho.n, chı˙’ c`onla.i 7 bit. Theo nguyˆenl´yt´ıch, 7 P1 = 2 = 128. Go.i P2 l`asˆo´ c´acchuˆo˜i bit d¯ˆo. d`ai8 kˆe´t th´ucbˇa`ng 00. Theo nguyˆenl´yt´ıch 6 P2 = 2 = 64. Go.i P3 l`asˆo´ c´acchuˆo˜i bit d¯ˆo. d`ai8 bˇa´t d¯ˆa`u bˇa`ng 1 v`akˆe´t th´ucbˇa`ng 00. Theo nguyˆenl´y t´ıch 5 P3 = 2 = 32. . Ap´ du. ng nguyˆenl´ybao h`am-loa.i tr`u ta c´o P = P1 + P2 − P3 = 160. . . . . . . . . Nguyˆenl´ybao h`am-loa.i tr`u c´othˆe˙’ mo˙’ rˆo.ng cho tru`ong ho. p m su. kiˆe.n, nhung ph´uc ta.p . . hon, ta s˜ed¯ˆe` cˆa.p o˙’ phˆa`n sau. . . . Su. cˆongnhˆa.n ba nguyˆenl´ytrˆennhu l`axuˆa´t ph´atd¯iˆe˙’m cu˙’a l´ythuyˆe´t tˆo˙’ ho. p: + T´ınhd¯´ungd¯ˇa´n cu˙’a ba nguyˆenl´ytrˆenl`a“d¯´unghiˆe˙’n nhiˆen”.Quan d¯iˆe˙’m cu˙’a ch´ungta . . l`acˆongnhˆa.n 3 nguyˆenl´ytrˆen,coi nhu xuˆa´t ph´atd¯iˆe˙’m cu˙’a l´ythuyˆe´t tˆo˙’ ho. p. C´ackˆe´t qua˙’ . . . . . . kh´acs˜elˆa`n luo. t d¯uo. c suy ra tru. c tiˆe´p hoˇa.c gi´antiˆe´p t`u ba nguyˆenl´yn`ay. . . + Nˆe´u khˆongthoa˙’ m˜an,c˜ungc´othˆe˙’ t`ımc´ach ch´ung minh ba nguyˆenl´yn`ay, nhu vˆa.y ta . la.i pha˙’i cˆa`n d¯ˆe´n c´accˆongcu. kh´ac,thu. c chˆa´t ta la.i cˆongnhˆa.n mˆo.t d¯iˆe` u g`ıkh´acl`a“d¯´ung hiˆe˙’n nhiˆen”d¯ˆe˙’ rˆo`i suy luˆa.n ra ba nguyˆenl´ytrˆen. B`aitˆa.p 1. C´obao nhiˆeuchuˆo˜i 8 bit bˇa´t d¯ˆa`u bˇa`ng 1100? 13
13. 2. C´obao nhiˆeuchuˆo˜i 8 bit bˇa´t d¯ˆa`u v`akˆe´t th´ucbˇa`ng 1? . . . 3. C´obao nhiˆeuchuˆo˜i 8 bit trong d¯´ohoˇa.c bit th´u hai, hoˇa.c bit th´u tu bˇa`ng 1? 4. C´obao nhiˆeuchuˆo˜i 8 bit c´od¯´ungmˆo.t bit bˇa`ng 1? D- ´unghai bit bˇa`ng 1? C´o´ıtnhˆa´t mˆo.t bit bˇa`ng 1? . . . 5. C´obao nhiˆeuchuˆo˜i 8 bit d¯o.c xuˆoinguo. c d¯ˆe` u giˆo´ng nhu nhau? . . . . 6. C´ack´ytu. ABCDE d¯uo. c su˙’ du. ng d¯ˆe˙’ ta.o th`anhc´acchuˆo˜i d¯ˆo. d`ai3. . . (a) C´obao nhiˆeuchuˆo˜i d¯uo. c ta.o ra nˆe´u cho ph´eplˇa.p? . . (b) C´obao nhiˆeuchuˆo˜i d¯uo. c ta.o ra nˆe´u khˆongcho ph´eplˇa.p? . . (c) C´obao nhiˆeuchuˆo˜i bˇa´t d¯ˆa`u bˇa`ng A d¯uo. c ta.o ra nˆe´u cho ph´eplˇa.p? . . (d) C´obao nhiˆeuchuˆo˜i bˇa´t d¯ˆa`u bˇa`ng A d¯uo. c ta.o ra nˆe´u khˆongcho ph´eplˇa.p? . . . . (e) C´obao nhiˆeuchuˆo˜i khˆongch´ua k´ytu. A d¯uo. c ta.o ra nˆe´u cho ph´eplˇa.p? . . . . (f) C´obao nhiˆeuchuˆo˜i khˆongch´ua k´ytu. A d¯uo. c ta.o ra nˆe´u khˆongcho ph´eplˇa.p? 7. Trˆentˆa.p X := {5, 6, , 200} : (a) C´obao nhiˆeusˆo´ chˇa˜n, le˙’? (b) C´obao nhiˆeusˆo´ chia hˆe´t cho 5? . . (c) C´obao nhiˆeusˆo´ gˆo`m nh˜ung ch˜u sˆo´ phˆanbiˆe.t? (d) C´obao nhiˆeusˆo´ khˆongch´u.a ch˜u. sˆo´ 0? (e) C´obao nhiˆeusˆo´ l´o.n ho.n 101 v`akhˆongch´u.a ch˜u. sˆo´ 6? . . . . . . . (f) C´obao nhiˆeusˆo´ c´oc´acch˜u sˆo´ d¯uo. c sˇa´p theo th´u tu. tˇangthu. c su. ? . (g) C´obao nhiˆeusˆo´ c´oda.ng xyz v´oi 0 6= x z? . 8. Gia˙’ su˙’ c´o5 s´ach tin ho.c, 3 s´ach m´ayt´ınh,2 s´ach vˆa.t l´y. (a) C´obao nhiˆeuc´ach sˇa´p xˆe´p ch´unglˆengi´as´ach? . . (b) C´obao nhiˆeuc´ach sˇa´p xˆe´p sao cho 5 s´ach tin ho.c o˙’ ph´ıatr´ai,c`on2 s´ach vˆa.t l´yo˙’ bˆenpha˙’i? . . (c) C´obao nhiˆeuc´ach sˇa´p ch´unglˆengi´asao cho tˆa´t ca˙’ c´acs´ach theo c`ungnh´omd¯uo. c sˇa´p kˆe` nhau? (d) C´obao nhiˆeuc´ach sˇa´p ch´unglˆengi´asao cho hai s´ach vˆa.t l´ykhˆongkˆe` nhau? 9. C´o10 ba˙’n copy cu˙’a mˆo.t cuˆo´n s´ach v`ac´omˆo.t copy cu˙’a 10 cuˆo´n s´ach kh´ac. C´obao nhiˆeuc´ach c´othˆe˙’ cho.n 10 cuˆo´n s´ach? . . 10. C´obao nhiˆeutˆa.p con c´onhiˆe` u nhˆa´t n phˆa`n tu˙’ cu˙’a tˆa.p gˆo`m (2n + 1) phˆa`n tu˙’ ? . 11. Ap´ du. ng nguyˆenl´ybao h`am-loa.i tr`u d¯ˆe˙’ gia˙’i: . . (a) C´obao nhiˆeuchuˆo˜i 8 bit hoˇa.c bˇa´t d¯ˆa`u bˇa`ng 100 hoˇa.c c´obit th´u tu bˇa`ng 1? (b) C´obao nhiˆeuchuˆo˜i 8 bit hoˇa.c bˇa´t d¯ˆa`u bˇa`ng 1 hoˇa.c kˆe´t th´ucbˇa`ng 1? 14
14. . 1.2 Ho´anvi. v`atˆo˙’ ho. p - . . . D.inh ngh˜ıa1.2.1 Mˆo.t ho´anvi. cu˙’a n phˆa`n tu˙’ x1, x2, . . . , xn l`amˆo.t sˇa´p xˆe´p c´oth´u tu. n phˆa`n tu˙’. n`ay. . . . . V´ıdu. 1.2.1 C´os´auho´anvi. cu˙’a ba phˆa`n tu˙’ . Nˆe´u c´acphˆa`n tu˙’ d¯uo. c k´yhiˆe.u l`a A, B, C th`ı s´auho´anvi. l`a ABC, ACB, BAC, BCA, CAB, CBA. . D- .inh l´y1.2.2 C´o n! ho´anvi. cu˙’a n phˆa`n tu˙’ . . . . . . Ch´ung minh. Ta ch´ung minh theo quy na.p. Mˆo.t ho´anvi. cu˙’a n phˆa`n tu˙’ c´othˆe˙’ d¯uo. c xˆay . . . . . . du. ng theo n bu´oc liˆentiˆe´p: Cho.n phˆa`n tu˙’ d¯ˆa`u tiˆen,cho.n phˆa`n tu˙’ th´u hai, , cho.n phˆa`n . . . . . tu˙’ cuˆo´i c`ung.Phˆa`n tu˙’ d¯ˆa`u tiˆenc´othˆe˙’ cho.n n c´ach. Ngay khi phˆa`n tu˙’ d¯ˆa`u tiˆend¯uo. c cho.n, . . . . . . . . . phˆa`n tu˙’ th´u hai c´othˆe˙’ d¯uo. c cho.n n − 1 c´ach. Khi phˆa`n tu˙’ th´u hai d¯˜ad¯uo. c cho.n, phˆa`n tu˙’ . . . th´u ba c´othˆe˙’ d¯uo. c cho.n n − 2 c´ach, v`avˆanvˆan.Theo nguyˆenl´yquy na.p v`asau d¯´onguyˆen l´yt´ıch, tˆo`n ta.i n(n − 1)(n − 2) ããã 2 ã 1 = n! . ho´anvi. cu˙’a n phˆa`n tu˙’ . 2 V´ıdu. 1.2.2 C´o 10! = 10 ã 9 ã 8 ã 7 ã 6 ã 5 ã 4 ã 3 ã 2 ã 1 = 3.628.800 . ho´anvi. cu˙’a 10 phˆa`n tu˙’ . . . V´ıdu. 1.2.3 C´obao nhiˆeuho´anvi. cu˙’a c´ack´ytu. ABCDEF ch´ua chuˆo˜i con DEF ? . . C´othˆe˙’ xem chuˆo˜i con DEF nhu mˆo.t k´ytu. . Theo D- .inh l´y1.2.2 c´o4! = 24 ho´anvi. cu˙’a . . c´ack´ytu. ABCDEF ch´ua chuˆo˜i con DEF. . . . . V´ıdu. 1.2.4 C´obao nhiˆeuho´anvi. cu˙’a c´ack´ytu. ABCDEF ch´ua c´ack´ytu. DEF theo th´u . tu. bˆa´t k`y? . . . . . . Ta c´othˆe˙’ gia˙’i b`aito´anqua hai bu´oc: Cho.n mˆo.t th´u tu. cu˙’a c´ack´ytu. DEF ; v`axˆaydu. ng . . . . . . mˆo.t ho´anvi. cu˙’a ABC ch´ua th´u tu. d¯˜acho cu˙’a c´ack´ytu. DEF. Theo D- .inh l´y1.2.2, bu´oc . . . d¯ˆa`u tiˆenc´o3! = 6 c´ach; theo V´ıdu. 1.2.3 bu´oc th´u hai c´o4! = 24 c´ach. Theo nguyˆenl´y . . . . t´ıch, sˆo´ c´acho´anvi. cu˙’a ABCDEF ch´ua c´ack´ytu. DEF theo th´u tu. bˆa´t k`yl`a6 ã 24 = 144. . . . . . . . . . Trong mˆo.t sˆo´ tru`ong ho. p ta muˆo´n kha˙’o s´atmˆo.t th´u tu. cu˙’a r phˆa`n tu˙’ d¯uo. c cho.n t`u n . . . . phˆa`n tu˙’ . Mˆo.t th´u tu. nhu thˆe´ go.i l`a“r-ho´anvi.”. 15
15. - . D.inh ngh˜ıa1.2.3 Mˆo.t r-ho´anvi. cu˙’a n phˆa`n tu˙’ (phˆanbiˆe.t) x1, x2, . . . , xn l`amˆo.t sˇa´p xˆe´p . . . . . . r-phˆa`n tu˙’ c´oth´u tu. t`u n phˆa`n tu˙’ n`ay. Sˆo´ c´ac r-ho´anvi. cu˙’a tˆa.p n phˆa`n tu˙’ phˆanbiˆe.t k´y hiˆe.u l`a P (n, r). V´ıdu. 1.2.5 Ta c´omˆo.t sˆo´ 2-ho´anvi. cu˙’a a, b, c l`a ab, bc, ac. . . . . . Nˆe´u r = n trong D- .inh ngh˜ıa1.2.3, ch´ungta nhˆa.n d¯uo. c mˆo.t th´u tu. cu˙’a tˆa´t ca˙’ n phˆa`n tu˙’ . Do d¯´otheo D- .inh l´y1.2.2 P (n, n) = n!. Tˆo˙’ng qu´atta c´o . D- .inh l´y1.2.4 Sˆo´ c´ac r-ho´anvi. cu˙’a tˆa. p n phˆa`n tu˙’ phˆanbiˆe. t l`a P (n, r) = n(n − 1)(n − 2) ããã (n − r + 1), r ≤ n. . . . . . . . Ch´ung minh. Ch´ungta d¯ˆe´m sˆo´ c´acc´ach c´oth´u tu. cu˙’a r phˆa`n tu˙’ d¯uo. c cho.n t`u tˆa.p gˆo`m . . . . n phˆa`n tu˙’ . C´o n c´ach cho.n phˆa`n tu˙’ d¯ˆa`u tiˆen. Kˆe´ tiˆe´p, c´o n − 1 c´ach cho.n phˆa`n tu˙’ th´u . . . . hai, n − 2 c´ach cho.n phˆa`n tu˙’ th´u ba, , c´o n − r + 1 c´ach cho.n phˆa`n tu˙’ th´u r. Do d¯´otheo . nguyˆenl´yt´ıch, sˆo´ c´ac r-ho´anvi. cu˙’a tˆa.p n phˆa`n tu˙’ phˆanbiˆe.t l`a n(n − 1)(n − 2) ããã (n − r + 1). 2 V´ıdu. 1.2.6 Theo D- .inh l´y1.2.4, sˆo´ c´ac2-ho´anvi. cu˙’a X = {a, b, c} l`a P (3, 2) = 3 ã 2 = 6. S´auho´anvi. n`ayl`a ab, ac, ba, bc, ca, cb. . V´ıdu. 1.2.7 C´obao nhiˆeuc´ach cho.n mˆo.t chu˙’ ti.ch, mˆo.t ph´ochu˙’ ti.ch, mˆo.t thu k´yv`amˆo.t . . . thu˙’ qu˜yt`u mˆo.t nh´om10 ngu`oi? . . . . . . . Ch´ungta cˆa`n d¯ˆe´m sˆo´ c´acc´ach c´oth´u tu. cu˙’a 4 ngu`oi d¯uo. c cho.n t`u mˆo.t nh´omgˆo`m 10 . . ngu`oi. Theo D- .inh l´y1.2.4 sˆo´ c´acc´ach cho.n l`a P (10, 4) = 10 ã 9 ã 8 ã 7 = 5040. . . Ch´u´yrˇa`ng c˜ungc´othˆe˙’ suy ra kˆe´t qua˙’ tru. c tiˆe´p t`u nguyˆenl´yt´ıch (ta.i sao?). 16
16. . . ˆ V´ıdu. 1.2.8 Mˆo.t ngu`oi b´anh`angrong cˆa`n d¯iqua 7 d¯i.a d¯iˆe˙’m kh´acnhau. Ong ta c´othˆe˙’ d¯i . . theo th´u tu. bˆa´t k`y.C´obao nhiˆeuh`anhtr`ınhkh´acnhau? . . Sˆo´ c´ach`anhtr`ınhc´othˆe˙’ c´ol`asˆo´ c´acho´anvi. t`u tˆa.p gˆo`m 7 phˆa`n tu˙’ : P (7, 7) = 7! = 5040. Nˆe´u chˇa˙’ng ha.n ˆongta muˆo´n t`ımh`anhtr`ınhc´od¯ˆo. d`aingˇa´n nhˆa´t, ˆongta cˆa`n t´ınhto´anv`a so s´anh5040 h`anhtr`ınhca˙’ tha˙’y!(?). Ta c´othˆe˙’ viˆe´t P (n, r) = n(n − 1)(n − 2) ããã (n − r + 1) n(n − 1)(n − 2) ããã (n − r + 1)(n − r) ããã 2 ã 1 = (n − r) ããã 2 ã 1 n! = . (n − r)! - . . . D.inh ngh˜ıa1.2.5 X´ettˆa.p X := {x1, x2, . . . , xn} ch´ua n phˆa`n tu˙’ phˆanbiˆe.t. Mˆo.t r-tˆo˙’ ho. p . . . . . cu˙’a tˆa.p X l`amˆo.t bˆo. r phˆa`n tu˙’ , khˆongphˆanbiˆe.t th´u tu.à, lˆa´ảy t`u tˆa.p n`ay. Sˆo´ c´ac r-tˆo˙’ ho. p n cu˙’a tˆap gˆo`m n phˆa`n tu˙’. phˆanbiˆet k´yhiˆeu l`a C(n, r) hay . . . . r . Ch´ungta s˜ex´acd¯i.nh cˆongth´uc cho C(n, r) bˇa`ng c´ach d¯ˆe´m sˆo´ c´ac r-ho´anvi. cu˙’a tˆa.p gˆo`m . . . . . n phˆa`n tu˙’ theo hai c´ach. Th´u nhˆa´t, su˙’ du. ng cˆongth´uc P (n, r). C´ach th´u hai l`ad¯ˆe´m sˆo´ c´ac . . . r-ho´anvi. cu˙’a tˆa.p gˆo`m n phˆa`n tu˙’ c´oliˆenquan v´oi C(n, r). T`u d¯´os˜esuy ra kˆe´t qua˙’. . . . . Ta c´othˆe˙’ xˆaydu. ng r-ho´anvi. cu˙’a tˆa.p n phˆa`n tu˙’ phˆanbiˆe.t qua hai bu´oc liˆentiˆe´p: D- `ˆau . . . . tiˆen,cho.n mˆo.t r-tˆo˙’ ho. p cu˙’a X (tˆa.p con r phˆa`n tu˙’ khˆongphˆanbiˆe.t th´u tu. ) v`asau d¯´osˇa´p . . . . th´u tu. n´o.Chˇa˙’ng ha.n, d¯ˆe˙’ xˆaydu. ng mˆo.t 2-ho´anvi. cu˙’a {a, b, c, d} ta c´othˆe˙’ cho.n 2-tˆo˙’ ho. p . . v`asau d¯´osˇa´p th´u tu. n´o.Theo nguyˆenl´yt´ıch, sˆo´ c´ac r-ho´anvi. bˇa`ng t´ıch cu˙’a sˆo´ c´ac r-tˆo˙’ . . . . . ho. p v`asˆo´ c´acc´ach sˇa´p th´u tu. cu˙’a r phˆa`n tu˙’ . T´uc l`a P (n, r) = C(n, r)r!. Vˆa.y P (n, r) C(n, r) = . r! Do d¯´otheo D- .inh l´y1.2.4 ta c´o . D- .inh l´y1.2.6 Sˆo´ c´ac r-ho´anvi. cu˙’a tˆa. p n phˆa`n tu˙’ phˆanbiˆe. t l`a n! C(n, r) = , r ≤ n. (n − r)!r! 17
17. . ì ì ì ì ì. . . . . . . . . ì ì ì ì. ì . . . . . . . . . ì ì. ì ì ì . . . . . . . . . ì ì. ì ì ì . . . . . . . ì ì. ì ì ì H`ınh1.1: . . . . . V´ıdu. 1.2.9 C´obao nhiˆeuc´ach cho.n 5 ngu`oi t`u 10 ngu`oi d¯ˆe˙’ lˆa.p th`anhmˆo.t d¯ˆo.i b´ong(khˆong . . phˆanbiˆe.t th´u tu. )? . . . Cˆautra˙’ l`oi l`abˇa`ng sˆo´ tˆo˙’ ho. p chˆa.p 5 cu˙’a 10 phˆa`n tu˙’ 10! C(10, 5) = = 252. 5!5! . . . . . V´ıdu. 1.2.10 C´obao nhiˆeuc´ach cho.n mˆo.t hˆo.i d¯ˆo`ng gˆo`m hai ngu`oi n˜u v`aba ngu`oi nam . . . . . . t`u mˆo.t nh´omnˇamngu`oi n˜u v`as´aungu`oi nam? . . . . . . . . Sˆo´ c´ach cho.n hai ngu`oi n˜u v`aba ngu`oi nam tuong ´ung l`a C(5, 2) = 10 v`a C(6, 3) = 20. . . . . . . . . . . Hˆo.i d¯ˆo`ng d¯uo. c xˆaydu. ng qua hai bu´oc liˆentiˆe´p: Cho.n ngu`oi n˜u; cho.n ngu`oi nam. Theo nguyˆenl´yt´ıch, tˆo˙’ng sˆo´ c´achˆo.i d¯ˆo`ng l`a10 ã 20 = 200. . V´ıdu. 1.2.11 C´obao nhiˆeuchuˆo˜i t´ambit ch´ua ch´ınhx´acbˆo´n bit 1? . . . Mˆo.t chuˆo˜i t´ambit ch´ua bˆo´n bit 1 d¯uo. c x´acd¯i.nh duy nhˆa´t ngay khi ch´ungta biˆe´t c´acbit . . . n`aobˇa`ng 1. Nhung d¯iˆe` u n`ayc´othˆe˙’ thu. c hiˆe.n bo˙’ i C(8, 4) c´ach. . . . . V´ıdu. 1.2.12 C´obao nhiˆeuh`anhtr`ınht`u g´ocdu´oi bˆentr´aicu˙’a mˆo.t b`anc`o vuˆongk´ıch . . thu´oc n ì n d¯ˆe´n g´octrˆenbˆenpha˙’i nˆe´u ch´ungta chı˙’ d¯itheo c´ach sang pha˙’i v`alˆentrˆen?Mˆo.t . . . . h`anhtr`ınhnhu vˆa.y trˆenb`anc`o 4 ì 4 d¯uo. c cho trong H`ınh1.1. . . . . . Mˆo˜i h`anhtr`ınhc´othˆe˙’ d¯uo. c mˆota˙’ bo˙’ i mˆo.t chuˆo˜i d¯ˆo. d`ai2n cu˙’a n k´ytu. R v`a n k´ytu. U. . . . . Chˇa˙’ng ha.n, h`anhtr`ınhtrong H`ınh1.1 tuong ´ung chuˆo˜i RUURRURU. Mˆo.t chuˆo˜i nhu vˆa.y . . . . . c´othˆe˙’ nhˆa.n d¯uo. c bˇa`ng c´ach cho.n n vi. tr´ıd¯ˆo´i v´oi R (khˆongphˆanbiˆe.t th´u tu. ) trong sˆo´ 2n . . vi. tr´ıcho ph´epcu˙’a chuˆo˜i v`asau d¯´och`en n k´ytu. U v`aonh˜ung vi. tr´ıc`onla.i. Do d¯´osˆo´ h`anh tr`ınhl`a C(2n, n). 18
18. B`aitˆa.p 1. C´obao nhiˆeuho´anvi. cu˙’a a, b, c, d? Liˆe.t kˆec´acho´anvi. n`ay. 2. C´obao nhiˆeu3-ho´anvi. cu˙’a a, b, c, d? Liˆe.t kˆec´acho´anvi. n`ay. . . 3. C´obao nhiˆeuho´anvi., 5-ho´anvi. cu˙’a 11 d¯ˆo´i tuo. ng kh´acnhau? . . 4. C´obao nhiˆeuc´ach cho.n mˆo.t chu˙’ ti.ch, mˆo.t ph´ochu˙’ ti.ch v`amˆo.t thu k´yt`u mˆo.t nh´om 11 ngu.`o.i? . 5. C´obao nhiˆeuc´ach cho.n mˆo.t chu˙’ ti.ch, mˆo.t ph´ochu˙’ ti.ch, mˆo.t kˆe´ to´anv`amˆo.t thu k´y . . . t`u mˆo.t nh´om12 ngu`oi? . . . . . . 6. C´obao nhiˆeuchuˆo˜i c´ophˆanbiˆe.t th´u tu. d¯uo. c ta.o ra t`u c´ack´ytu. ABCDE nˆe´u: (a) Ch´u.a chuˆo˜i con ACE. . . . . (b) Ch´ua c´ack´ytu. ACE theo th´u tu. t`uy´y. (c) Ch´u.a c´acchuˆo˜i con DB v`a AE. . (d) Ch´ua hoˇa.c chuˆo˜i con AE hoˇa.c EA. . . . . (e) K´ytu. A xuˆa´t hiˆe.n tru´oc k´ytu. D. Chˇa˙’ng ha.n BCAED, BCADE. (f) Khˆongch´u.a c´acchuˆo˜i con AB, CD. . . . . . . (g) K´ytu. A xuˆa´t hiˆe.n tru´oc k´ytu. C v`a C xuˆa´t hiˆe.n tru´oc E. 7. D- ˇa.t X := {a, b, c, d}. . . (a) T`ımsˆo´ c´ac3-tˆo˙’ ho. p cu˙’a X. Liˆe.t kˆec´actˆo˙’ ho. p n`ay. . . (b) T`ımmˆo´i quan hˆe. gi˜ua c´ac3-tˆo˙’ ho. p v`a3-ho´anvi. cu˙’a X. . . . . . 8. C´obao nhiˆeuc´ach cho.n mˆo.t hˆo.i d¯ˆo`ng gˆo`m ba ngu`oi t`u nh´om11 ngu`oi? . . . . . 9. C´obao nhiˆeuc´ach cho.n mˆo.t hˆo.i d¯ˆo`ng gˆo`m bˆo´n ngu`oi t`u nh´om12 ngu`oi? . . . . . 10. Mˆo.t cˆaula.c bˆo. gˆo`m s´aungu`oi nam v`aba˙’y ngu`oi n˜u. . . (a) C´obao nhiˆeuc´ach cho.n mˆo.t hˆo.i d¯ˆo`ng gˆo`m nˇamngu`oi? . (b) C´obao nhiˆeuc´ach cho.n mˆo.t hˆo.i d¯ˆo`ng gˆo`m ba nam v`abˆo´n n˜u? . . . (c) C´obao nhiˆeuc´ach cho.n mˆo.t hˆo.i d¯ˆo`ng gˆo`m bˆo´n ngu`oi v`a´ıtnhˆa´t mˆo.t n˜u? . . . (d) C´obao nhiˆeuc´ach cho.n mˆo.t hˆo.i d¯ˆo`ng gˆo`m bˆo´n ngu`oi v´oi nhiˆe` u nhˆa´t mˆo.t nam? . . . (e) C´obao nhiˆeuc´ach cho.n mˆo.t hˆo.i d¯ˆo`ng gˆo`m bˆo´n ngu`oi c´oca˙’ nam v`an˜u? 11. (a) C´obao nhiˆeuchuˆo˜i 8 bit ch´u.a ch´ınhx´acba bit 0? (b) C´obao nhiˆeuchuˆo˜i 8 bit ch´u.a ba bit 0 v`a5 bit 1? (c) C´obao nhiˆeuchuˆo˜i 8 bit ch´u.a ´ıtnhˆa´t hai bit 0? 19
19. . 12. Mˆo.t cu˙’ a h`angc´o50 m´ayt´ınhtrong d¯´oc´obˆo´n bi. ho˙’ng. (a) C´obao nhiˆeuc´ach cho.n bˆo´n m´ayt´ınh? (b) C´obao nhiˆeuc´ach cho.n bˆo´n m´ayt´ınhkhˆongho˙’ng? (c) C´obao nhiˆeuc´ach cho.n bˆo´n m´ayt´ınhtrong d¯´oc´ohai chiˆe´c bi. ho˙’ng? (d) C´obao nhiˆeuc´ach cho.n bˆo´n m´ayt´ınhtrong d¯´oc´o´ıtnhˆa´t mˆo.t chiˆe´c bi. ho˙’ng? . . . . . . 13. X´etmˆo.t h`anhtr`ınhtrˆenb`anc`o k´ıch thu´oc m ì n t`u g´octr´aibˆendu´oi d¯ˆe´n g´octrˆen . . bˆenpha˙’i v`atheo hu´ong hoˇa.c sang pha˙’i hoˇa.c lˆentrˆen. (a) Sˆo´ h`anhtr`ınhc´othˆe˙’ l`abao nhiˆeu? . . (b) Ap´ du. ng d¯ˆe˙’ ch´ung minh d¯ˇa˙’ng th´uc Xn C(k + m − 1, k) = C(m + n, m). k=0 . . 14. Ch´ung minh rˇa`ng sˆo´ c´acchuˆo˜i bit d¯ˆo. d`ai n ≥ 4 ch´ua ch´ınhx´achai lˆa`n xuˆa´t hiˆe.n cu˙’a chuˆo˜i bit 10 l`a C(n + 1, 5). . . 15. Ch´ung minh rˇa`ng sˆo´ c´acchuˆo˜i bit d¯ˆo. d`ai n ch´ua ch´ınhx´ac k bit 0 sao cho hai bit 0 khˆongxuˆa´t hiˆe.n liˆentiˆe´p l`a C(n − k + 1, k). 16. Ch´u.ng minh rˇa`ng t´ıch cu˙’a k sˆo´ nguyˆenliˆentiˆe´p chia hˆe´t cho k!. . . . 17. Ch´ung minh rˇa`ng c´o(2n − 1)(2n − 3) ã ã 3 ã 1 c´ach cho.n n cˇa.p t`u 2n phˆa`n tu˙’ phˆan biˆe.t. . . . . . . 18. Gia˙’ su˙’ c´o n d¯ˆo´i tuo. ng trong d¯´oc´o r d¯ˆo´i tuo. ng phˆanbiˆe.t v`a n−r l`ad¯ˆo`ng nhˆa´t. Ch´ung minh cˆongth´u.c P (n, r) = r!C(n, r) . . . . bˇa`ng c´ach d¯ˆe´m sˆo´ c´ophˆanbiˆe.t th´u tu. cu˙’a n d¯ˆo´i tuo. ng theo hai c´ach: . . . . + D- `ˆau tiˆend¯ˆe´m sˆo´ c´ophˆanbiˆe.t th´u tu. c´acvi. tr´ıcu˙’a r d¯ˆo´i tuo. ng phˆanbiˆe.t. . . . . + D- `ˆau tiˆend¯ˆe´m sˆo´ c´ophˆanbiˆe.t th´u tu. c´acvi. tr´ıcu˙’a n − r d¯ˆo´i tuo. ng d¯ˆo`ng nhˆa´t. . 1.3 C´acthuˆa.t to´ansinh ra ho´anvi. v`atˆo˙’ ho. p . . Nh´omnha.c rock cu˙’a tru`ong D- a.i ho.c D- `aLa.t c´o n b`aih´atcˆa`n ghi lˆenmˆo.t d¯˜ıaCD. C´acb`ai h´atchiˆe´m th`o.i gian (t´ınhbˇa`ng giˆay)tu.o.ng ´u.ng l`a t1, t2, . . . , tn. (1.1) 20
20. . . D- ˜ıaCD c´othˆe˙’ luu tr˜u nhiˆe` u nhˆa´t l`a C giˆay. V`ıd¯ˆayl`ad¯˜ıaCD d¯ˆa`u tiˆencu˙’a nh´om,nˆenho. . . . . muˆo´n ghi c´acb`aih´atv´oi th`oi luo. ng c`angnhiˆe` u c`angtˆo´t. Do d¯´ob`aito´anl`acho.n mˆo.t tˆa.p con {i1, i2, . . . , ik} cu˙’a {1, 2, . . . , n} sao cho tˆo˙’ng Xk tij j=1 . . . khˆongvuo. t qu´a C v`al´on nhˆa´t c´othˆe˙’. C´ach tiˆe´p cˆa.n l`akiˆe˙’m tra tˆa´t ca˙’ c´actˆa.p con cu˙’a . . {1, 2, . . . , n} v`acho.n mˆo.t tˆa.p con sao cho tˆo˙’ng (1.1) l´on nhˆa´t c´othˆe˙’.D- ˆe˙’ thu. c hiˆe.n ch´ung . . ta cˆa`n mˆo.t thuˆa.t to´anta.o ra tˆa´t ca˙’ c´actˆo˙’ ho. p cu˙’a tˆa.p gˆo`m n phˆa`n tu˙’ . Phˆa`n n`aytr`ınhb`ay . c´acthuˆa.t to´ansinh ra c´acho´anvi. v`atˆo˙’ ho. p. n . . . Do c´o2 tˆa.p con cu˙’a tˆa.p gˆo`m n phˆa`n tu˙’ nˆenth`oi gian thu. c hiˆe.n cu˙’a thuˆa.t to´ankiˆe˙’m tra n . . . . tˆa´t ca˙’ c´actˆa.p con ´ıtnhˆa´t l`a O(2 ). Nh˜ung thuˆa.t to´annhu vˆa.y l`akhˆongho. p l´yngoa.i tr`u . . . v´oi nh˜ung gi´atri. n nho˙’. Tuy nhiˆenc´onh˜ung b`aito´anm`ad¯ˆe˙’ gia˙’i n´okhˆongc´oc´ach n`aotˆo´t . . . . hon l`a“liˆe.t kˆe”tˆa´t ca˙’ c´actru`ong ho. p. . . . . . . . . Phuong ph´apliˆe.t kˆetˆa´t ca˙’ c´actˆo˙’ ho. p v`ac´acho´anvi. theo “th´u tu. t`u d¯iˆe˙’n”: V´oi hai t`u . . . . . . . d¯˜acho, d¯ˆe˙’ x´acd¯i.nh t`u n`aod¯´ung tru´oc trong t`u d¯iˆe˙’n, ch´ungta so s´anhc´ack´ytu. trong t`u. C´ohai kha˙’ nˇang: . . . . . . . . . . (a) Mˆo˜i k´ytu. trong t`u ngˇa´n hon tr`ungv´oi k´ytu. tuong ´ung trong t`u d`aihon. . . (b) Ta.i mˆo.t vi. tr´ın`aod¯´o,c´ack´ytu. trong hai t`u kh´acnhau. . . . . . . . . Nˆe´u (a) d¯´ung,t`u ngˇa´n hon s˜ed¯´ung tru´oc. Chˇa˙’ng ha.n, “dog” d¯´ung tru´oc “doghouse” . . trong t`u d¯iˆe˙’n. Nˆe´u (b) d¯´ungch´ungta x´acd¯i.nh vi. tr´ıbˆentr´ainhˆa´t p m`ata.i d¯´oc´ack´ytu. . . . . . . . . . kh´acnhau. Th´u tu. cu˙’a c´act`u d¯uoc x´acd¯i.nh bo˙’ i th´u tu. cu˙’a c´ack´ytu. ta.i vi. tr´ı p. Chˇa˙’ng . . . . ha.n, “nha” d¯´ung tru´oc “nhanh” trong t`u d¯iˆe˙’n. . . . . . D- ˆe˙’ d¯on gia˙’n ta s˜ed¯i.nh ngh˜ıath´u tu. t`u d¯iˆe˙’n trˆentˆa.p c´ack´yhiˆe.u l`ac´acsˆo´ tu. nhiˆen. - . D.inh ngh˜ıa1.3.1 Gia˙’ su˙’ α = s1s2 . . . sp v`a β = t1t2 . . . tq l`ac´acchuˆo˜i trˆentˆa.p {1, 2, . . . , n}. . . . . Ta n´oi α c´oth´u tu. t`u d¯iˆe˙’n nho˙’ hon β, k´yhiˆe.u α < β, nˆe´u hoˇa.c . (a) p < q v`a si = ti v´oi i = 1, 2, . . . , p; hoˇa.c . . (b) Tˆo`n ta.i i sao cho si 6= ti, v`av´oi chı˙’ sˆo´ i nho˙’ nhˆa´t nhu vˆa.y, ta c´o si < ti. V´ıdu. 1.3.1 Trˆentˆa.p {1, 2, 3, 4} ta c´o α = 132 < β = 1324. Trˆentˆa.p {1, 2, 3, 4, 5, 6} ta c´o α = 13246 < β = 1342. . D- `ˆau tiˆenta x´etb`aito´anliˆe.t kˆetˆa´t ca˙’ c´ac r-tˆo˙’ ho. p cu˙’a tˆa.p {1, 2, . . . , n}. Trong thuˆa.t . . . . to´an,ch´ungta s˜eliˆe.t kˆe r-tˆo˙’ ho. p {x1, x2, . . . , xr} tuong ´ung chuˆo˜i s1s2 . . . sr trong d¯´o 21
21. . s1 < s2 < ããã < sr v`a {x1, x2, . . . , xr} = {s1, s2, . . . , sr}. Chˇa˙’ng ha.n, 3-tˆo˙’ ho. p {6, 2, 4} s˜e tu.o.ng ´u.ng chuˆo˜i 246. . . . . . . Ta s˜eliˆe.t kˆec´ac r-tˆo˙’ ho. p cu˙’a tˆa.p {1, 2, . . . , n} theo th´u tu. t`u d¯iˆe˙’n. Do d¯´o,c´acchuˆo˜i d¯uo. c . . . liˆe.t kˆed¯ˆa`u tiˆenv`acuˆo´i c`ungtuong ´ung l`a12 . . . r v`a(n − r + 1) . . . n. . V´ıdu. 1.3.2 Liˆe.t kˆetˆa´t ca˙’ 5-tˆo˙’ ho. p cu˙’a {1, 2, 3, 4, 5, 6, 7}. Chuˆo˜i d¯ˆa`u tiˆenl`a12345, theo sau l`a12346 v`a12347. Chuˆo˜i kˆe´ tiˆe´p l`a12356 v`asau d¯´o 12357. Chuˆo˜i cuˆo´i c`ungl`a34567. . . V´ıdu. 1.3.3 T`ımchuˆo˜i tiˆe´p theo 13467 khi ch´ungta liˆe.t kˆe5-tˆo˙’ ho. p cu˙’a tˆa.p ho. p X := {1, 2, 3, 4, 5, 6, 7}. . . . Khˆongc´ochuˆo˜i n`aobˇa´t d¯ˆa`u v´oi 134 v`ac´acbiˆe˙’u diˆe˜n cu˙’a mˆo.t tˆo˙’ ho. p 5 phˆa`n tu˙’ cu˙’a X pha˙’i l´o.n ho.n 13467. Do d¯´ochuˆo˜i tiˆe´p theo 13467 pha˙’i bˇa´t d¯ˆa`u l`a135. V`ı13567 l`achuˆo˜i . . . nho˙’ nhˆa´t bˇa´t d¯ˆa`u bˇa`ng 135 v`al`amˆo.t tˆo˙’ ho. p cu˙’a 5 phˆa`n tu˙’ cu˙’a X nˆen13567 l`atˆo˙’ ho. p pha˙’i t`ım. . . V´ıdu. 1.3.4 T`ımchuˆo˜i tiˆe´p theo 2367 khi ch´ungta liˆe.t kˆe4-tˆo˙’ ho. p cu˙’a tˆa.p ho. p X := {1, 2, 3, 4, 5, 6, 7}. . . . Khˆongc´ochuˆo˜i n`aobˇa´t d¯ˆa`u v´oi 23 v`ac´acbiˆe˙’u diˆe˜n cu˙’a mˆo.t tˆo˙’ ho. p 4 phˆa`n tu˙’ cu˙’a X pha˙’i l´o.n ho.n 2367. Do d¯´ochuˆo˜i tiˆe´p theo 2367 pha˙’i bˇa´t d¯ˆa`u l`a24. V`ı2456 l`achuˆo˜i nho˙’ . . . nhˆa´t bˇa´t d¯ˆa`u bˇa`ng 24 v`al`amˆo.t tˆo˙’ ho. p cu˙’a 5 phˆa`n tu˙’ cu˙’a X nˆen2456 l`atˆo˙’ ho. p pha˙’i t`ım. . X´etchuˆo˜i α = s1s2 . . . sr biˆe˙’u diˆe˜n tˆo˙’ ho. p {x1, x2, . . . , xr}. D- ˆe˙’ t`ımchuˆo˜i kˆe´ tiˆe´p β = . . t1t2 . . . tr ta t`ımphˆa`n tu˙’ bˆenpha˙’i nhˆa´t sm m`akhˆongpha˙’i l`agi´atri. cu. c d¯a.i cu˙’a n´ota.i d¯´o. . . (sr c´othˆe˙’ lˆa´y gi´atri. cu. c d¯a.i n, sr−1 c´othˆe˙’ lˆa´y gi´atri. cu. c d¯a.i n − 1, ). Khi d¯´o . ti = si, v´oi i = 1, 2, . . . , m − 1. . . . . Phˆa`n tu˙’ tm bˇa`ng sm + 1. Nh˜ung phˆa`n tu˙’ c`onla.i cu˙’a chuˆo˜i β x´acd¯i.nh bo˙’ i tm+1 = sm + 2, tm+2 = sm + 3, . Thuˆa.t to´ansinh c´actˆo˙’ ho. p . . . Bu´oc 1. [Kho˙’ i ta.o chuˆo˜i] D- ˇa.t si = i, i = 1, 2 . . . , r. . . . Bu´oc 2. [Xuˆa´t tˆo˙’ ho. p d¯ˆa`u tiˆen]Xuˆa´t chuˆo˜i s = s1s2 . . . sr. . . . . . . Bu´oc 3. [Lˇa.p] V´oi mˆo˜i i = 2, 3, ,C(n, r) thu. c hiˆe.n c´acbu´oc sau: 22
22. . . 3.1. T`ımphˆa`n tu˙’ bˆenpha˙’i nhˆa´t khˆongpha˙’i l`agi´atri. cu. c d¯a.i cu˙’a n´o. . . . 3.2. (Gi´atri. cu. c d¯a.i cu˙’a sk d¯uo. c d¯i.nh ngh˜ıal`a n − r + k). 3.3. D- ˇa.t sm = sm + 1. . 3.4. V´oi mˆo˜i j = m + 1, . . . , r, d¯ˇa.t sj = sj−1 + 1. 3.5. Xuˆa´t s. . V´ıdu. 1.3.5 X´ettˆa.p {1, 2, 3, 4, 5, 6, 7}. Gia˙’ su˙’ s1 = 2, s2 = 3, s3 = 4, s4 = 6, s5 = 7. . . ´ Ta c´o s3 l`aphˆa`n tu˙’ bˆenpha˙’i nhˆa´t khˆongpha˙’i l`agi´atri. cu. c d¯a.i cu˙’a n´ota.i d¯´o. Ap du. ng thuˆa.t to´antrˆen,ta c´ochuˆo˜i tiˆe´p theo 23467 l`a23567. . V´ıdu. 1.3.6 Thuˆa.t to´anta.o 4-tˆo˙’ ho. p cu˙’a {1, 2, 3, 4, 5, 6} cho ta 1234, 1235, 1236, 1246, 1256, 1345, 1346, 1356, 1456, 2345, 2346, 2356, 3456. . . . . . . Tuong tu. thuˆa.t to´ansinh c´actˆo˙’ ho. p, thuˆa.t to´ansinh c´acho´anvi. s˜eliˆe.t kˆetheo th´u tu. t`u. d¯iˆe˙’n. . V´ıdu. 1.3.7 D- ˆe˙’ xˆaydu. ng ho´anvi. cu˙’a tˆa.p {1, 2, 3, 4, 5, 6} sau ho´anvi. 163542, ch´ungta cˆa`n . cˆo´ d¯i.nh c´acch˜u sˆo´ bˆentr´ainhiˆe` u nhˆa´t c´othˆe˙’. Tˆo`n ta.i ho´anvi. tiˆe´p theo ho´anvi. 1635 ? V`ıho´anvi. c´oda.ng 1635 kh´acho´anvi. d¯˜acho . l`a163524 v`a163524 nho˙’ hon 163542 nˆenho´anvi. sau 163542 khˆongthˆe˙’ c´oda.ng 1635 . . Tˆo`n ta.i ho´anvi. tiˆe´p theo ho´anvi. 163 ? Ba ch˜u sˆo´ cuˆo´i c`ungpha˙’i l`amˆo.t ho´anvi. cu˙’a . . . {2, 4, 5}. V`ı542 l`aho´anvi. l´on nhˆa´t cu˙’a {2, 4, 5} nˆenho´anvi. bˆa´t k`yv´oi ba ch˜u sˆo´ bˇa´t d¯ˆa`u . 163 nho˙’ hon ho´anvi. 63542. Vˆa.y ho´anvi. sau ho´anvi. d¯˜acho khˆongthˆe˙’ c´oda.ng 163 . . Ho´anvi. tiˆe´p theo cu˙’a 163542 khˆongthˆe˙’ bˇa´t d¯ˆa`u l`a1635 hay 163 do hoˇa.c c´acch˜u sˆo´ c`on . . . . la.i trong ho´anvi. d¯˜acho (42 v`a542, tuong ´ung) l`a gia˙’m. Do d¯´o,bˇa´t d¯ˆa`u t`u bˆenpha˙’i, ch´ung . . . ta cˆa`n t`ımch˜u sˆo´ d¯ˆa`u tiˆen d m`alˆancˆa.n bˆenpha˙’i cu˙’a n´ol`a r thoa˙’ m˜an d < r. Trong tru`ong . . . ho. p trˆen,ch˜u sˆo´ th´u ba: 3 c´ot´ınhchˆa´t n`ay. Vˆa.y ho´anvi. tiˆe´p theo ho´anvi. d¯˜acho s˜ebˇa´t . . d¯ˆa`u l`a16. Ch˜u sˆo´ tiˆe´p theo khˆongthˆe˙’ nho˙’ hon 3. V`ıta muˆo´n ho´anvi. tiˆe´p theo nho˙’ nhˆa´t, . . . nˆench˜u sˆo´ kˆe´ tiˆe´p l`a4. Do d¯´oho´anvi. tiˆe´p theo bˇa´t d¯ˆa`u v´oi 164. C´acch˜u sˆo´ c`onla.i: 235 . cˆa`n tˇangv´oi gi´atri. nho˙’ nhˆa´t. Vˆa.y ho´anvi. tiˆe´p theo ho´anvi. d¯˜acho l`a16435. . Nhˆa.n x´etrˇa`ng d¯ˆe˙’ ta.o tˆa´t ca˙’ c´acho´anvi. cu˙’a tˆa.p {1, 2, . . . , n} ch´ungta c´othˆe˙’ bˇa´t d¯ˆa`u v´oi . . ho´anvi. 12 . . . n v`alˇa.p la.i phuong ph´apcu˙’a V´ıdu. 1.3.7 d¯ˆe˙’ ta.o ho´anvi. kˆe´ tiˆe´p. Thuˆa.t to´an kˆe´t th´uckhi ta.o ra ho´anvi. n(n − 1) 21. 23
23. ´ . . V´ıdu. 1.3.8 Ap du. ng phuong ph´apcu˙’a V´ıdu. 1.3.7, ta c´othˆe˙’ liˆe.t kˆetˆa´t ca˙’ c´acho´anvi. cu˙’a . . . . {1, 2, 3, 4} theo th´u tu. t`u d¯iˆe˙’n nhu sau: 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321. Thuˆa.t to´ansinh c´acho´anvi. . . . Bu´oc 1. [Kho˙’ i ta.o chuˆo˜i] D- ˇa.t si = i, i = 1, 2 . . . , n. . . Bu´oc 2. [Xuˆa´t ho´anvi. d¯ˆa`u tiˆen]Xuˆa´t chuˆo˜i s = s1s2 . . . sn. . . . . . . Bu´oc 3. [Lˇa.p] V´oi mˆo˜i i = 2, 3, . . . , n! thu. c hiˆe.n c´acbu´oc sau: . 3.1. T`ımchı˙’ sˆo´ l´on nhˆa´t m thoa˙’ m˜an sm sm. . 3.3. Ho´anvi. hai phˆa`n tu˙’ sm v`a sk. . . . . . 3.4. D- a˙’o nguo. c th´u tu. cu˙’a c´acphˆa`n tu˙’ sm+1, . . . , sn. 3.5. Xuˆa´t s. ´ . V´ıdu. 1.3.9 Ap du. ng thuˆa.t to´antrˆent`ımho´anvi. tiˆe´p theo 163542: Gia˙’ su˙’ s1 = 1, s2 = 6, s3 = 3, s4 = 5, s5 = 4, s6 = 2. . . Chı˙’ sˆo´ m l´on nhˆa´t thoa˙’ sm sm l`a5. Ho´anvi. sm . . . . . . . v`a sk ta c´o s3 = 4, s5 = 3. D- a˙’o nguo. c th´u tu. c´acphˆa`n tu˙’ s4, s5, s6 ta nhˆa.n d¯uo. c ho´anvi. tiˆe´p theo l`a164235. B`aitˆa.p . . . . . . . 1. T`ım r-tˆo˙’ ho. p sinh ra bo˙’ i thuˆa.t to´ansinh tˆo˙’ ho. p v´oi n = 7 sau khi r-tˆo˙’ ho. p d¯uo. c cho: 1356, 12367, 14567. . . . 2. T`ımho´anvi. sinh ra bo˙’ i thuˆa.t to´ansinh ho´anvi. sau ho´anvi. d¯uo. c cho: 12354, 625431, 12876543. . . . 3. T`ımtˆa´t ca˙’ r-tˆo˙’ ho. p t`u tˆa.p n phˆa`n tu˙’ nˆe´u (a) n = 6, r = 3. (b) n = 6, r = 2. (c) n = 7, r = 5. . 4. T`ımc´acho´anvi. cu˙’a tˆa.p hai, ba phˆa`n tu˙’ . 24
24. . 5. Viˆe´t thuˆa.t to´and¯ˆe. quy sinh ra tˆa´t ca˙’ c´ac r-tˆo˙’ ho. p cu˙’a tˆa.p {s1, s2, . . . , sn}. Chia b`ai to´anth`anhhai b`aito´ancon: . . + Liˆe.t kˆec´ac r-tˆo˙’ ho. p ch´ua s1. . . + Liˆe.t kˆec´ac r-tˆo˙’ ho. p khˆongch´ua s1. 6. Viˆe´t thuˆa.t to´and¯ˆe. quy sinh ra tˆa´t ca˙’ c´acho´anvi. cu˙’a tˆa.p {s1, s2, . . . , sn}. Chia b`ai to´anth`anh n b`aito´ancon: . + Liˆe.t kˆec´acho´anvi. bˇa´t d¯ˆa`u v´oi s1. . + Liˆe.t kˆec´acho´anvi. bˇa´t d¯ˆa`u v´oi s2. . . . + Liˆe.t kˆec´acho´anvi. bˇa´t d¯ˆa`u v´oi sn. . 1.4 Ho´anvi. v`atˆo˙’ ho. p suy rˆo.ng . . . . Trong c´acmu. c tru´oc, ch´ungta d¯˜anghiˆenc´uu c´acho´anvi. v`atˆo˙’ ho. p khˆongcho ph´eplˇa.p la.i . . . . c´acphˆa`n tu˙’ . Phˆa`n n`ayt`ımhiˆe˙’u c´acho´anvi. cu˙’a c´acd˜aych´ua nh˜ung phˆa`n tu˙’ lˇa.p la.i v`ac´ac . . . . ph´epcho.n khˆongphˆanbiˆe.t th´u tu. c´olˇa.p la.i. Tru´oc hˆe´t ta x´etv´ıdu. sau. . V´ıdu. 1.4.1 Trong nhiˆe` u vˆa´n d¯ˆe` d¯ˆe´m, c´acphˆa`n tu˙’ c´othˆe˙’ lˇa.p la.i; chˇa˙’ng ha.n c´obao nhiˆeu . . xˆaukh´acnhau c´od¯ˆo. d`ai n t`u ba˙’ng 26 ch˜u c´ai? . . . . Hiˆe˙’n nhiˆeno˙’ d¯ˆay, c´othˆe˙’ coi c´acch˜u c´aid¯uo. c r´utra c´oho`anla.i. Mˆo.t xˆaud¯ˆo. d`ai n gˆo`m . . . n ch˜u c´ai.Mˆo˜i ch˜u c´aic´o26 c´ach cho.n lu. a. Theo nguyˆenl´yt´ıch, sˆo´ xˆauc´othˆe˙’ l`a n |26 ì 26 ì{z ã ã ã ì 26} = 26 . n lˆa`n . r D- .inh l´y1.4.1 Sˆo´ c´ac r-ho´anvi. c´olˇa. p la. i cu˙’a tˆa. p n phˆa`n tu˙’ bˇa`ng n . . Ch´ung minh. C´o n c´ach cho.n cho mˆo˜i vi. tr´ıtrong r-ho´anvi. (v`ıc´olˇa.p la.i). Ap´ du. ng nguyˆen l´yt´ıch, sˆo´ c´ac r-ho´anvi. c´olˇa.p la.i bˇa`ng nr. 2 V´ıdu. 1.4.2 X´etchuˆo˜i SUCCESS. C´obao nhiˆeuchuˆo˜i kh´acnhau c´othˆe˙’ c´okhi sˇa´p xˆe´p . la.i c´ack´ytu. cu˙’a chuˆo˜i n`ay? . . . . Tru´oc hˆe´t ch´u´yrˇa`ng trong chuˆo˜i SUCCESS d¯ˆo. d`ai7 c´oba k´ytu. S, hai k´ytu. C, mˆo.t . . . . k´ytu. U v`amˆo.t k´ytu. E. Nh˜ung k´ytu. n`ayl`akhˆongphˆanbiˆe.t, nˆenho´anvi. ch´ungkhˆong . ta.o ra chuˆo˜i m´oi. 25
25. . C´otˆa´t ca˙’ 7! chuˆo˜i l`aho´anvi. cu˙’a chuˆo˜i SUCCESS. Ba k´ytu. S ho´anvi. ta.o ra 3! chuˆo˜i; . . . hai k´ytu. C ho´anvi. ta.o ra 2! chuˆo˜i; mˆo.t k´ytu. U ho´anvi. ta.o ra 1! chuˆo˜i; v`amˆo.t k´ytu. E . ho´anvi. ta.o ra 1! chuˆo˜i. Vˆa.y sˆo´ chuˆo˜i thˆa.t su. kh´acnhau l`a 7! . 3!2!1!1! V´ıdu. 1.4.3 X´etchuˆo˜i MISSISSIPPI. C´obao nhiˆeuchuˆo˜i kh´acnhau c´othˆe˙’ c´okhi sˇa´p . xˆe´p la.i c´ack´ytu. cu˙’a chuˆo˜i n`ay? X´etb`aito´and¯iˆe` n v`ao11 chˆo˜ trˆo´ng −−−−−−−−−−−, . . . v´oi c´ack´ytu. d¯˜acho. C´o C(11, 2) c´ach cho.n c´acvi. tr´ıd¯ˆo´i v´oi P. Khi d¯˜acho.n xong P, ta c´o . . C(9, 4) c´ach cho.n c´acvi. tr´ıd¯ˆo´i v´oi S. Khi d¯˜acho.n S, c´o C(5, 4) c´ach cho.n c´acvi. tr´ıd¯ˆo´i v´oi . I. Cuˆo´i c`ungchı˙’ c`onmˆo.t c´ach cho.n M. Theo nguyˆenl´yt´ıch, sˆo´ c´acc´ach d¯ˆe˙’ d¯iˆe` n c´ack´ytu. l`a 11! 9! 5! C(11, 2)C(9, 4)C(5, 4) = 2!9! 4!5! 4!1! 11! = 2!4!4!1! = 34.650. Tˆo˙’ng qu´atta c´o - . . . . . . D.inh l´y1.4.2 Gia˙’ su˙’ d˜ay n phˆa`n tu˙’ S c´o n1 d¯ˆo´i tuo. ng loa. i 1, n2 d¯ˆo´i tuo. ng loa. i 2, , v`a . . nt d¯ˆo´i tuo. ng loa. i t. Khi d¯´osˆo´ c´acc´achcho. n d˜ay S l`a n! . n1!n2! . . . nt! . . . . . Ch´ung minh. Ta g´anc´acvi. tr´ıd¯ˆo´i v´oi mˆo˜i d˜ayd¯ˆo. d`ai n c´acd¯ˆo´i tuo. ng d¯ˆe˙’ ta.o ra mˆo.t th´u . . . . tu. trong S. C´o C(n, n1) c´ach cho.n c´acvi. tr´ıd¯ˆo´i v´oi c´acd¯ˆo´i tuo. ng loa.i 1. Khi d¯˜acho.n xong . . . . . c´acd¯ˆo´i tuo. ng n`ay, ta c´o C(n − n1, n2) c´ach cho.n c´acvi. tr´ıd¯ˆo´i v´oi c´acd¯ˆo´i tuo. ng loa.i 2, v`a . vˆanvˆan.Theo nguyˆenl´yt´ıch, sˆo´ c´acc´ach d¯ˆe˙’ thu. c hiˆe.n l`a C(n, n1)C(n − n1, n2) ããã C(n − n1 − n2 − ã ã ã − nt−1, nt) v`ado d¯´oc´od¯iˆe` u cˆa`n ch´u.ng minh. 2 . . Kˆe´ tiˆe´p ch´ungta kha˙’o s´atb`aito´and¯ˆe´m c´acph´epcho.n khˆongphˆanbiˆe.t th´u tu. c´olˇa.p la.i. 26
26. . . . V´ıdu. 1.4.4 X´etba loa.i s´ach: s´ach m´ayt´ınh,s´ach vˆa.t l´yv`as´ach li.ch su˙’ . Gia˙’ su˙’ thu viˆe.n c´o´ıtnhˆa´t s´aucuˆo´n s´ach mˆo˜i loa.i. C´obao nhiˆeuc´ach c´othˆe˙’ cho.n s´aucuˆo´n s´ach? . . . . . B`aito´anl`alˆa´y s´auphˆa`n tu˙’ khˆongphˆanbiˆe.t th´u tu. t`u tˆa.p {m´ayt´ınh,vˆa.t l´y,li.ch su˙’ } cho . . . . . ph´eplˇa.p la.i. Mˆo.t ph´epcho.n d¯uo. c x´acd¯i.nh duy nhˆa´t bo˙’ i sˆo´ mˆo˜i kiˆe˙’u s´ach d¯uo. c cho.n. K´y hiˆe.u . M´ayt´ınh Vˆa.t l´y Li.ch su˙’ ì ì ì | ì ì | ì . c´ongh˜ıal`aph´epcho.n ba cuˆo´n s´ach m´ayt´ınh,hai s´ach vˆa.t l´yv`amˆo.t s´ach li.ch su˙’ . Nhˆa.n x´et . . . . . rˇa`ng mˆo˜i th´u tu. cu˙’a s´auk´yhiˆe.u ì v`ahai k´yhiˆe.u | tuong ´ung mˆo.t ph´epcho.n. Do d¯´ob`ai . . . to´anl`ad¯ˆe´m sˆo´ c´acth´u tu. . Vˆa.y c´othˆe˙’ thu. c hiˆe.n bˇa`ng C(8, 2) = 28 c´ach. . . D- .inh l´y1.4.3 Nˆe´u X l`atˆa. p gˆo`m t phˆa`n tu˙’ th`ısˆo´ ph´epcho. n k phˆa`n tu˙’ khˆongphˆanbiˆe. t . . . th´u tu. t`u X cho ph´eplˇa. p l`a C(k + t − 1, t − 1) = C(k + t − 1, k). . Ch´ung minh. D- ˇa.t X := {a1, a2, . . . , at}. X´et k + t − 1 khoa˙’ng trˇa´ng gˆo`m k k´yhiˆe.u ì v`a t − 1 k´yhiˆe.u |. Mˆo˜i vi. tr´ıcu˙’a k´yhiˆe.u n`aytrˆenc´ackhoa˙’ng trˇa´ng x´ac . . . . d¯i.nh mˆo.t ph´epcho.n. n1 k´yhiˆe.u ì d¯ˆe´n k´yhiˆe.u | d¯ˆa`u tiˆentuong ´ung ph´epcho.n n1 phˆa`n tu˙’ . . . . . a1; n2 k´yhiˆe.u ì d¯ˆe´n k´yhiˆe.u | th´u hai tuong ´ung ph´epcho.n n2 phˆa`n tu˙’ a2; v`avˆanvˆan.Ta c´o C(k + t − 1, t − 1) c´ach cho.n c´acvi. tr´ıcho | nˆenc´o C(k + t − 1, t − 1) c´ach cho.n. Gi´atri. n`aybˇa`ng C(k + t − 1, k), sˆo´ c´ach cho.n c´acvi. tr´ıcu˙’a ì; do d¯´oc´o C(k + t − 1, t − 1) = C(k + t − 1, k) . . . . c´ach cho.n k phˆa`n tu˙’ khˆongphˆanbiˆe.t th´u tu. t`u tˆa.p X cho ph´eplˇa.p la.i. 2 . . V´ıdu. 1.4.5 C´oc´achˆo.p ch´ua c´acqua˙’ b´ongm`aud¯o˙’, xanh v`av`ang.Mˆo˜i hˆo.p ch´ua ´ıtnhˆa´t t´amqua˙’ b´ong. C´obao nhiˆeuc´ach cho.n t´amqua˙’ b´ong? C´obao nhiˆeuc´ach cho.n t´amqua˙’ b´ong,mˆo˜i m`au´ıtnhˆa´t mˆo.t qua˙’ b´ong? (a) Theo D- .inh l´y1.4.3, sˆo´ c´ach cho.n t´amqua˙’ b´ongl`a C(8 + 3 − 1, 3 − 1) = C(10, 2) = 45. (b) D- `ˆau tiˆencho.n mˆo.t qua˙’ b´ongmˆo˜i m`au;sau d¯´ocho.n thˆemnˇamqua˙’ b´ong.Theo D- .inh l´y 1.4.3 ta c´o C(5 + 3 − 1, 3 − 1) = C(7, 2) = 21 c´ach. 27
27. . . V´ıdu. 1.4.6 (a) C´obao nhiˆeunghiˆe.m nguyˆenkhˆongˆamcu˙’a phuong tr`ınh x1 + x2 + x3 + x4 = 29? (1.2) . . . . . . . . Mˆo˜i nghiˆe.m cu˙’a phuong tr`ınh(1.2) tuong d¯uong v´oi ph´epcho.n 29 phˆa`n tu˙’ xi c´okiˆe˙’u i, i = 1, 2, 3, 4. Theo D- .inh l´y1.4.3 sˆo´ ph´epcho.n l`a C(29 + 4 − 1, 4 − 1) = C(32, 3) = 4960. . . (b) C´obao nhiˆeunghiˆe.m nguyˆencu˙’a phuong tr`ınh(1.2) thoa˙’ m˜an x1 > 0, x2 > 1, x3 > 2, x4 ≥ 0? . . . . . . Mˆo˜i nghiˆe.m cu˙’a (1.2) thoa˙’ d¯iˆe` u kiˆe.n d¯˜acho tuong d¯uong v´oi ph´epcho.n 29 phˆa`n tu˙’ xi . . c´okiˆe˙’u i, i = 1, 2, 3, 4, sao cho cˆa`n ´ıtnhˆa´t mˆo.t phˆa`n tu˙’ c´okiˆe˙’u 1, ´ıtnhˆa´t hai phˆa`n tu˙’ c´o . . . kiˆe˙’u 2, ´ıtnhˆa´t ba phˆa`n tu˙’ c´okiˆe˙’u 3. D- `ˆau tiˆencho.n mˆo.t phˆa`n tu˙’ c´okiˆe˙’u 1, hai phˆa`n tu˙’ c´o . . kiˆe˙’u 2 v`aba phˆa`n tu˙’ c´okiˆe˙’u 3. Sau d¯´ocho.n thˆem23 phˆa`n tu˙’ c`onla.i. Theo D- .inh l´y1.4.3 sˆo´ ph´epcho.n l`a C(23 + 4 − 1, 4 − 1) = C(26, 3) = 2600. . . . Ch´ungta kˆe´t th´ucphˆa`n n`ayv´oi viˆe.c mo˙’ rˆo.ng nguyˆenl´ybao h`am-loa.i tr`u. . . . . X´ettru`ong ho. p c´oba su. kiˆe.n A, B, C. Ta cˆa`n t´ınh#(A ∪ B ∪ C). Nhˆa.n x´etl`a . . (a) Nˆe´u lˆa´y #A + #B + #C : c´ophˆa`n d¯uo. c t´ınhmˆo.t lˆa`n, hai lˆa`n v`aba lˆa`n (H`ınh1.2(a)); . . (b) Nˆe´u lˆa´y #A + #B + #C − #(A ∩ B) − #(A ∩ C) − #(B ∩ C) : c´ophˆa`n khˆongd¯uo. c t´ınhlˆa`n n`ao(H`ınh1.2(b)); (c) Nˆe´u lˆa´y #A + #B + #C − #(A ∩ B) − #(A ∩ C) − #(B ∩ C) + #(A ∩ B ∩ C) : mˆo˜i . . phˆa`n d¯uo. c t´ınhd¯´ungmˆo.t lˆa`n (H`ınh1.2(c)). Vˆa.y #(A ∪ B ∪ C) = #A + #B + #C − #(A ∩ B) − #(A ∩ C) − #(B ∩ C) + #(A ∩ B ∩ C). Tˆo˙’ng qu´atta c´o - . . D.inh l´y1.4.4 Gia˙’ su˙’ c´o m su. kiˆe. n A1,A2, Am. Khi d¯´o Xm X X #(A1 ∪ A2 ∪ ã ã ã ∪ Am) = #Ai − #(Ai ∩ Aj) + #(Ai ∩ Aj ∩ Ak) i=1 1≤i<j≤m 1≤i<j<k≤m m+1 + ããã + (−1) #(A1 ∩ A2 ∩ ã ã ã ∩ Am). 28
28. C C C 1 1 1 . . . . . . . . . . . . . . . . . . 2 2 1 1 1 1 3 0 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 1 1 1 1 1 2 1 AB AB AB (a) (b) (c) H`ınh1.2: . . . Ch´ung minh. Ta s˜ech´ung minh rˇa`ng lˆa´y mˆo.t phˆa`n tu˙’ a bˆa´t k`ythuˆo.c tˆa.p A1 ∪ A2 ∪ ã ã ã ∪ Am . . . th`ı a c˜ungd¯uo. c kˆe˙’ d¯ˆe´n d¯´ungmˆo.t lˆa`n o˙’ vˆe´ pha˙’i. . . Gia˙’ su˙’ a thuˆo.c d¯´ung r tˆa.p, chˇa˙’ng ha.n trong A1 ∩ A2 ∩ ã ã ã ∩ Ar, r ≤ m. Phˆa`n tu˙’ n`ayd¯˜a . . d¯uo. c t´ınh Pm + C(r, 1) lˆa`n trong i=1 #Ai; Pm + C(r, 2) lˆa`n trong i=1 #(Ai ∩ Aj); P ` m + C(r, m) lˆan trong i=1 #(Ai1 ∩ Ai2 ∩ ã ã ã Aim ). . . Vˆa.y n´od¯˜ad¯uo. c t´ınhtˆo˙’ng cˆo.ng sˆo´ lˆa`n l`a C(r, 1) − C(r, 2) + C(r, 3) − ã ã ã + (−1)m+1C(r, r). Nhu.ng C(r, 0) − C(r, 1) + C(r, 2) − ã ã ã + (−1)rC(r, r) = 0 . . . v`a C(r, 0) = 1. Vˆa.y phˆa`n tu˙’ a d¯˜ad¯uo. c t´ınh C(r, 1) − C(r, 2) + C(r, 3) − ã ã ã + (−1)r+1C(r, r) = 1 lˆa`n. 2 . . V´ıdu. 1.4.7 C´obao nhiˆeunghiˆe.m nguyˆenkhˆongˆamcu˙’a phuong tr`ınh x1 + x2 + x3 = 11 29
29. . v´oi d¯iˆe` u kiˆe.n x1 ≤ 3, x2 ≤ 4 v`a x3 ≤ 6? . . . . Tuong tu. nhu V´ıdu. 1.4.6, ta c´o . . + Tˆo˙’ng sˆo´ nghiˆe.m nguyˆenkhˆongˆamcu˙’a phuong tr`ınh(1.4.7) l`a C(3 + 11 − 1, 11) = 78. . + Sˆo´ nghiˆe.m v´oi d¯iˆe` u kiˆe.n x1 ≥ 4 l`a C(3 + 7 − 1, 7) = C(9, 7) = 36. . + Sˆo´ nghiˆe.m v´oi d¯iˆe` u kiˆe.n x2 ≥ 5 l`a C(3 + 6 − 1, 6) = C(8, 6) = 28. . + Sˆo´ nghiˆe.m v´oi d¯iˆe` u kiˆe.n x3 ≥ 7 l`a C(3 + 4 − 1, 4) = C(6, 4) = 15. . + Sˆo´ nghiˆe.m v´oi d¯iˆe` u kiˆe.n x1 ≥ 4, x2 ≥ 5 l`a C(3 + 2 − 1, 2) = C(4, 2) = 6. . + Sˆo´ nghiˆe.m v´oi d¯iˆe` u kiˆe.n x1 ≥ 4, x3 ≥ 7 l`a C(3 + 0 − 1, 0) = C(2, 0) = 1. . + Sˆo´ nghiˆe.m v´oi d¯iˆe` u kiˆe.n x2 ≥ 5, x3 ≥ 7 bˇa`ng 0. . + Sˆo´ nghiˆe.m v´oi d¯iˆe` u kiˆe.n x1 ≥ 4, x2 ≥ 4, x3 ≥ 7 bˇa`ng 0. Theo D- .inh l´y1.4.4 sˆo´ nghiˆe.m d¯`oiho˙’i l`a 78 − 36 − 28 − 15 + 6 + 1 + 0 − 0 = 6. . . . D- .inh l´y1.4.5 Gia˙’ su˙’ m, n l`ac´acsˆo´ nguyˆenduong kh´acnhau, m ≤ n. Khi d¯´oc´o nm − C(n, 1)(n − 1)m + C(n, 2)(n − 2)m − ã ã ã + (−1)n−1C(n, n − 1)1m . . . ´anhxa. lˆenkh´acnhau t`u tˆa. p m phˆa`n tu˙’ d¯ˆe´n tˆa. p c´o n phˆa`n tu˙’ . . Ch´ung minh. B`aitˆa.p. 2 . . . V´ıdu. 1.4.8 Gia˙’ su˙’ c´onˇamcˆongviˆe.c v`abˆo´n ngu`oi xin viˆe.c. C´obao nhiˆeuc´ach phˆancˆong . . . . viˆe.c kh´acnhau nˆe´u mˆo˜i ngu`oi pha˙’i d¯uo. c phˆancˆong´ıtnhˆa´t mˆo.t cˆongviˆe.c? . . . . . . Mˆo˜i phuong ph´apphˆancˆongtuong ´ung mˆo.t ´anhxa. lˆent`u tˆa.p c´accˆongviˆe.c d¯ˆe´n tˆa.p . . . . . . ngu`oi. Theo gia˙’ thiˆe´t, mˆo˜i ngu`oi d¯ˆe` u d¯uo. c phˆancˆong´ıtnhˆa´t mˆo.t cˆongviˆe.c, c´ac´anhxa. l`a . lˆen. Ap´ du. ng D- .inh l´y1.4.5 v´oi m = 5, n = 4 ta c´osˆo´ c´ach phˆancˆongcˆongviˆe.c bˇa`ng sˆo´ c´ac ´anhxa. lˆenkh´acnhau v`abˇa`ng 45 − C(4, 1)35 + C(4, 2)25 − C(4, 3)15 = 1024 − 972 + 192 − 4 = 240. 30
30. B`aitˆa.p . 1. C´obao nhiˆeuchuˆo˜i kh´acnhau c´othˆe˙’ c´okhi sˇa´p xˆe´p la.i c´ack´ytu. cu˙’a c´acchuˆo˜i sau: (a) GUIDE. (b) SCHOOL. (c) SALEP ERSONS. 2. C´obao nhiˆeuc´ach chia 10 cuˆo´n s´ach cho ba sinh viˆensao cho sinh viˆenth´u. nhˆa´t c´o nˇamcuˆo´n, sinh viˆenth´u. hai c´oba cuˆo´n v`asinh viˆenth´u. ba c´ohai cuˆo´n? . . . 3. Gia˙’ su˙’ c´oc´achˆo.p ch´ua c´acqua˙’ b´ongm`auxanh, d¯o˙’ v`av`ang.Mˆo˜i hˆo.p ch´ua ´ıtnhˆa´t 10 qua˙’. (a) C´obao nhiˆeuc´ach cho.n 10 qua˙’ b´ong? . (b) C´obao nhiˆeuc´ach cho.n 10 qua˙’ b´ongv´oi ´ıtnhˆa´t mˆo.t qua˙’ m`aud¯o˙’? . (c) C´obao nhiˆeuc´ach cho.n 10 qua˙’ b´ongv´oi ´ıtnhˆa´t mˆo.t qua˙’ m`aud¯o˙’, ´ıtnhˆa´t hai qua˙’ m`auxanh v`a´ıtnhˆa´t ba qua˙’ m`auv`ang? . d. C´obao nhiˆeuc´ach cho.n 10 qua˙’ b´ongv´oi d¯´ungmˆo.t qua˙’ m`aud¯o˙’? . e. C´obao nhiˆeuc´ach cho.n 10 qua˙’ b´ongv´oi d¯´ungmˆo.t qua˙’ m`aud¯o˙’ v`a´ıtnhˆa´t mˆo.t qua˙’ m`auxanh? . . 4. T`ımsˆo´ nghiˆe.m nguyˆencu˙’a phuong tr`ınh x1 + x2 + x3 = 15 nˆe´u (a) x1 ≥ 0, x2 ≥ 0, x3 ≥ 0. (b) x1 = 1, x2 ≥ 0, x3 ≥ 0. (c) 6 ≥ x1 ≥ 0, x2 ≥ 0, x3 ≥ 0. (d) x1 ≥ 1, x2 ≥ 1, x3 ≥ 1. (e) x1 ≥ 0, x2 > 0, x3 = 1. (f) 6 > x1 ≥ 0, 9 > x2 ≥ 1, x3 ≥ 0. . . 5. T`ımsˆo´ nghiˆe.m nguyˆencu˙’a phuong tr`ınh x1 + x2 + x3 + x4 = 15 nˆe´u 0 ≤ x1 ≤ 4, 0 ≤ x2 ≤ 5, 0 ≤ x3 ≤ 9. . 6. C´obao nhiˆeusˆo´ nguyˆentrong tˆa.p {1, 2, , 1000000} c´otˆo˙’ng c´acch˜u sˆo´ bˇa`ng 15? . 7. C´obao nhiˆeusˆo´ nguyˆentrong tˆa.p {1, 2, , 1000000} c´otˆo˙’ng c´acch˜u sˆo´ bˇa`ng 20? . . . . . 8. C´obao nhiˆeuc´ach cho.n ba d¯ˆo.i: mˆo.t d¯ˆo.i bˆo´n ngu`oi, hai d¯ˆo.i hai ngu`oi t`u mˆo.t nh´om t´amngu.`o.i? 31
31. . 9. Mˆo.t t´uis´ach ch´ua 20 qua˙’ b´ong:s´aud¯o˙’, s´auxanh v`at´amt´ım. . . (a) C´obao nhiˆeuc´ach cho.n nˇamqua˙’ b´ongnˆe´u c´acqua˙’ b´ongd¯uo. c xem l`aphˆanbiˆe.t? . . (b) C´obao nhiˆeuc´ach cho.n nˇamqua˙’ b´ongnˆe´u c´acqua˙’ b´ongc`ungm`aud¯uo. c xem l`a d¯ˆo`ng nhˆa´t? 10. Ch´u.ng minh rˇa`ng (n!)k chia hˆe´t (kn)!. 11. Ch´u.ng minh rˇa`ng nX+k−2 C(i, k − 1) = C(n + k − 1, k − 1). i=k−1 . . 12. Viˆe´t thuˆa.t to´ant`ımtˆa´t ca˙’ c´acnghiˆe.m nguyˆenkhˆongˆamcu˙’a phuong tr`ınh x1 + x2 + x3 = n (n ∈ N). . . 1.5 C´achˆe. sˆo´ nhi. th´uc v`ac´acd¯ˆo`ng nhˆa´t th´uc . . . D- .inh l´y1.5.1 (D- .inh l´ynhi. th´uc) Nˆe´u a v`a b l`ac´acsˆo´ thu. c v`a n l`asˆo´ tu. nhiˆenth`ı Xn (a + b)n = C(n, k)an−kbk. k=0 . n . n−k k Ch´ung minh. Khi khai triˆe˙’n (a+b) c´act`u c´oda.ng a b , k = 0, 1, . . . , n. D- ˆe˙’ c´omˆo.t th`anh n−k k . . phˆa`n a b cˆa`n c´od¯´ung n − k ch˜u a trong tˆo˙’ng sˆo´ n vi. tr´ı(v`ak´eotheo c´od¯´ung k ch˜u b). . n−k k D- iˆe` u n`ayc´othˆe˙’ thu. c hiˆe.n bˇa`ng C(n, k) c´ach. Do d¯´o a b xuˆa´t hiˆe.n C(n, k) lˆa`n. Suy ra (a + b)n = C(n, 0)anb0 + C(n, 1)an−1b1 + ããã + C(n, n)a0bn. 2 . . . Ch´ınhv`ıl´ydo trˆenm`a C(n, r) d¯uo. c go.i l`a hˆe. sˆo´ nhi. th´uc. 5 4 9 V´ıdu. 1.5.1 T`ımhˆe. sˆo´ cu˙’a a b trong khai triˆe˙’n cu˙’a (a + b) . . 5 4 9 Theo D- .inh l´ynhi. th´uc, hˆe. sˆo´ cu˙’a a b trong khai triˆe˙’n (a + b) l`a 9! C(9, 4) = = 126. 4!5! . V´ıdu. 1.5.2 Ch´ung minh rˇa`ng Xn (−1)kC(n, k) = 0. k=0 32
32. Ta c´o Xn Xn 0 = [1 + (−1)]n = C(n, k)1n−k(−1)k = (−1)kC(n, k). k=0 k=0 . . V´ıdu. 1.5.3 Su˙’ du. ng D- .inh l´ynhi. th´uc ta c´o Xn 2n = (1 + 1)n = C(n, k). k=0 . D- .inh l´y1.5.2 (D- ˇa˙’ng th´uc Pascal) C(n + 1, k) = C(n, k − 1) + C(n, k) v´o.i 1 ≤ k ≤ n. . . . Ch´ung minh. Gia˙’ su˙’ X l`atˆa.p gˆo`m n phˆa`n tu˙’ . Cho.n a∈ / X. Ta c´o C(n + 1, k) l`asˆo´ c´actˆa.p . . con k phˆa`n tu˙’ cu˙’a tˆa.p Y := X ∪ {a}. Mˆo˜i tˆa.p con k phˆa`n tu˙’ cu˙’a Y c´othˆe˙’ chia th`anhhai l´o.p: . + C´actˆa.p con cu˙’a Y khˆongch´ua a. . + C´actˆa.p con cu˙’a Y ch´ua a. . . C´actˆa.p con thuˆo.c nh´omth´u nhˆa´t l`ac´actˆa.p con cu˙’a X gˆo`m k phˆa`n tu˙’ v`ado d¯´oc´o C(n, k) . tˆa.p con nhu vˆa.y. . . . . C´actˆa.p con thuˆo.c nh´omth´u hai l`ac´actˆa.p l`aho. p cu˙’a tˆa.p con (k − 1) phˆa`n tu˙’ cu˙’a X v´oi . . tˆa.p gˆo`m mˆo.t phˆa`n tu˙’ a v`ado d¯´oc´o C(n, k − 1) tˆa.p con nhu vˆa.y. Suy ra C(n + 1, k) = C(n, k − 1) + C(n, k). 2 . . V´ıdu. 1.5.4 Ch´ung minh d¯ˇa˙’ng th´uc Xn C(i, k) = C(n + 1, k + 1). i=k Theo D- .inh l´y1.5.2 C(i, k) = C(i + 1, k + 1) − C(i, k + 1). Vˆa.y Xn Xn Xn C(i, k) = C(i + 1, k + 1) − C(i, k + 1) i=k i=k i=k = C(n + 1, k + 1). 33
33. . . V´ıdu. 1.5.5 T`u d¯ˇa˙’ng th´uc (1.5.4) ta c´o 1 + 2 + ããã + n = C(1, 1) + C(2, 1) + ããã + C(n, 1) = C(n + 1, 2) (n + 1)n = . 2 . D- .inh l´y1.5.3 (D- ˇa˙’ng th´uc Vandermonde) Xr C(m + n, r) = C(m, k)C(n, r − k) k=0 v´o.i r ≤ min(m, n). . . . . . . Ch´ung minh. Gia˙’ su˙’ c´actˆa.p T1,T2 tuong ´ung gˆo`m m, n phˆa`n tu˙’ phˆanbiˆe.t. Lˆa´y tˆa.p S gˆo`m . . . r phˆa`n tu˙’ t`u hai tˆa.p n`ay. Sˆo´ c´actˆa.p S nhu vˆa.y bˇa`ng C(m + n, r). Mˇa.t kh´ac,tˆa.p S c´othˆe˙’ gˆo`m . . + k phˆa`n tu˙’ thuˆo.c tˆa.p T1. Sˆo´ c´actˆa.p con nhu vˆa.y bˇa`ng C(m, k); . . + (r − k) phˆa`n tu˙’ thuˆo.c tˆa.p T2. Sˆo´ c´actˆa.p con nhu vˆa.y bˇa`ng C(n, r − k); v´o.i 0 ≤ k ≤ r. Theo nguyˆenl´yt´ıch, sau d¯´onguyˆenl´ytˆo˙’ng ta c´od¯iˆe` u cˆa`n ch´u.ng minh. 2 B`aitˆa.p . . . 1. Su˙’ du. ng D- .inh l´ynhi. th´uc khai triˆe˙’n c´acbiˆe˙’u th´uc (a) (x + y)4. (b) (2c − 3d)5. . . . 2. T`ımhˆe. sˆo´ cu˙’a sˆo´ ha.ng khi biˆe˙’u th´uc d¯uo. c khai triˆe˙’n: (a) x4y7;(x + y)11. (b) x2y3z5;(x + y + z)10. (c) a2x3;(a + x + c)2(a + x + d)3. √ (d) a3x4;(a + ax + x)2(a + x)5. (e) a2x3;(a + ax + x)(a + x)4. 34
34. . 3. T`ımsˆo´ c´acsˆo´ ha.ng khi khai triˆe˙’n biˆe˙’u th´uc (a) (x + y + z)10. (b) (w + x + y + z)12. (c) (x + y + z)10(w + x + y + z)2. 4. (a) Ch´u.ng minh rˇa`ng C(n, k) < C(n, k + 1) nˆe´u v`achı˙’ nˆe´u k < (n − 1)/2. . . (b) Suy ra cu. c d¯a.i cu˙’a C(n, k) v´oi k = 0, 1, . . . , n l`a C(n, [n/2]). . . 5. Ch´ung minh D- .inh l´ynhi. th´uc bˇa`ng quy na.p to´anho.c. . . . 6. Su˙’ du. ng l´yluˆa.n tˆo˙’ ho. p ch´ung minh rˇa`ng C(n, k) = C(n, n − k). 7. T´ınhtˆo˙’ng Xn−1 k(k + 1). k=1 8. T´ınhtˆo˙’ng Xn k2. k=1 . . 9. D`ungD- .inh l´ynhi. th´uc ch´ung minh Xn 2kC(n, k) = 3n. k=0 10. Gia˙’ su˙’. n chˇa˜n. Ch´u.ng minh rˇa`ng Xn/2 Xn/2 C(n, 2k) = 2n−1 = C(n, 2k − 1). k=0 k=1 11. Ch´u.ng minh rˇa`ng Xn n! (a + b + c)n = aibjcn−i−j. i!j!(n − i − j)! 0≤i+j≤n 12. Ch´u.ng minh rˇa`ng Xn n! 3n = . i!j!(n − i − j)! 0≤i+j≤n 35
35. . . 13. D`ungl´yluˆa.n tˆo˙’ ho. p ch´ung minh rˇa`ng Xn C(n, k)2 = C(2n, n). k=0 14. (a) Ch´u.ng minh rˇa`ng Xn n(1 + x)n−1 = C(n, k)kxk−1. k=1 (b) T`u. d¯´osuy ra Xn n2n−1 = kC(n, k). k=1 1.6 Nguyˆenl´ychuˆo`ng chim bˆo` cˆau . . . Nguyˆenl´ychuˆo`ng chim bˆo` cˆau (c`ongo.i l`a nguyˆenl´yDirichlet) thu`ong d`ungnhˇa`m tra˙’ l`oi . . . cˆauho˙’i: C´otˆo`n ta.i mˆo.t phˆa`n tu˙’ thoa˙’ t´ınhchˆa´t cho tru´oc? Khi ´apdu. ng th`anhcˆong,nguyˆen . . . l´yn`aychı˙’ ra rˇa`ng d¯ˆo´i tuo. ng tˆo`n ta.i; tuy nhiˆenkhˆongchı˙’ ra c´ach t`ımn´onhu thˆe´ n`aov`ac´o . bao nhiˆeuphˆa`n tu˙’ tˆo`n ta.i. Da.ng d¯ˆa`u tiˆencu˙’a nguyˆenl´ychuˆo`ng chim bˆo` cˆaukhˇa˙’ng d¯i.nh rˇa`ng nˆe´u c´o n vˆa.t cˆa`n xˆe´p . . v`ao k hˆo.p v`a n > k th`ıc´o´ıtnhˆa´t c´omˆo.t hˆo.p ch´ua hai hoˇa.c nhiˆe` u hon hai vˆa.t. L´ydo . . khˇa˙’ng d¯i.nh n`ayd¯´ungc´othˆe˙’ ch´ung minh bˇa`ng pha˙’n ch´ung: Nˆe´u kˆe´t luˆa.n l`asai, mˆo˜i hˆo.p . . . . . ch´ua nhiˆe` u nhˆa´t mˆo.t vˆa.t v`ado d¯´otrong tru`ong ho. p n`ayc´onhiˆe` u nhˆa´t k vˆa.t. Nhung c´o n vˆa.t nˆen n ≤ k vˆol´y. . 1.6.1 Nguyˆenl´ychuˆo`ng chim bˆo` cˆau(da.ng th´u nhˆa´t) . Nˆe´u c´o n vˆa. t cˆa`n xˆe´p v`ao k hˆo. p v`a n > k th`ıc´o´ıtnhˆa´t c´omˆo. t hˆo. p ch´ua hai hoˇa. c nhiˆe` u . hon hai vˆa. t. . . Ch´u´yrˇa`ng, nguyˆenl´ychuˆo`ng chim bˆo` cˆaukhˆongchı˙’ ra hˆo.p n`aoch´ua hon hai vˆa.t. N´o . . chı˙’ khˇa˙’ng d¯i.nh su. tˆo`n ta. i cu˙’a mˆo.t hˆo.p v´oi ´ıtnhˆa´t hai vˆa.t trong d¯´o. . V´ıdu. 1.6.1 Sˆo´ c´acho.c viˆencu˙’a mˆo.t l´op ho.c ´ıtnhˆa´t l`abao nhiˆeud¯ˆe˙’ c´o´ıtnhˆa´t hai ho.c . . . viˆenc´osˆo´ d¯iˆe˙’m nhu nhau trong k`ythi mˆonTo´anho.c r`oi ra.c, nˆe´u du. d¯i.nh thang d¯iˆe˙’m l`a 0-10? C´o11 thang d¯iˆe˙’m. Theo nguyˆenl´ychuˆo`ng chim bˆo` cˆau,cˆa`n c´o´ıtnhˆa´t 11 + 1 = 12 ho.c viˆen. 36
36. . . . . . . V´ıdu. 1.6.2 Ch´ung minh rˇa`ng v´oi n + 1 sˆo´ nguyˆenduong kh´acnhau khˆongvuo. t qu´a2n th`ıpha˙’i c´ohai sˆo´ chia hˆe´t cho nhau. . . . . Gia˙’ su˙’ n + 1 sˆo´ nguyˆenduong l`a a1, a2, . . . , an+1, v´oi 0 ≤ ai ≤ 2n. Ta c´othˆe˙’ viˆe´t ki ai = 2 qi, i = 1, 2, . . . , n + 1, . . trong d¯´o ki l`asˆo´ nguyˆenkhˆongˆamv`a qi l`asˆo´ nguyˆenle˙’ khˆongˆamv`akhˆongvuo. t qu´a2n. V´ıdu. 1 = 20, 14 = 21 ì 7, 40 = 23 ì 5, . . V`ıchı˙’ c´o n sˆo´ le˙’ khˆongvuo. t qu´a2n nˆentrong n + 1 sˆo´ le˙’ q1, q2, . . . , qn+1 pha˙’i c´o´ıtnhˆa´t . hai sˆo´ bˇa`ng nhau, chˇa˙’ng ha.n qi = qj = q v´oi i 6= j. Khi d¯´o ki ki kj kj ai = 2 qi = 2 q, aj = 2 qj = 2 q, . . . v´oi ki 6= kj. Suy ra ai.aj nˆe´u ki > kj v`a aj.ai nˆe´u kj > ki. Kˆe´t qua˙’ trˆenl`atˆo´t nhˆa´t theo ngh˜ıanˆe´u ta gia˙’m nhe. gia˙’ thiˆe´t d¯ibˇa`ng c´ach thay n cho . n + 1 th`ıkˆe´t qua˙’ khˆongc`ond¯´ungn˜ua. Thˆa.t vˆa.y chı˙’ cˆa`n lˆa´y tˆa.p c´acsˆo´ {n + 1, n + 2, , 2n}. . 2 . . V´ıdu. 1.6.3 Ch´ung minh rˇa`ng trong mo.i d˜aygˆo`m n + 1 sˆo´ thu. c phˆanbiˆe.t d¯ˆe` u ch´ua mˆo.t . . . . d˜aycon d¯ˆo. d`ai n + 1 hoˇa.c tˇangthu. c su. , hoˇa.c gia˙’m thu. c su. . . 2 . . Gia˙’ su˙’ n + 1 sˆo´ thu. c phˆanbiˆe.t l`a a1, a2, . . . , an2+1. V´oi mˆo˜i sˆo´ ai ta g´ancho n´ocˇa.p sˆo´ . (ki, di) nhu sau: . + ki l`ad¯ˆo. d`aicu˙’a d˜aycon tˇangd`ainhˆa´t xuˆa´t ph´att`u ai. . + di l`ad¯ˆo. d`aicu˙’a d˜aycon gia˙’m d`ainhˆa´t xuˆa´t ph´att`u ai. . . . . Bˇa`ng pha˙’n ch´ung gia˙’ su˙’ khˆongc´od˜aycon n`aoc´od¯ˆo. d`ai n + 1 la.i tˇangthu. c su. hoˇa.c gia˙’m . . 2 thu. c su. . Khi d¯´o ki, di ≤ n, i = 1, 2, . . . , n + 1. 2 . Nhˆa.n x´etrˇa`ng c´o n cˇa.p (ki, di) kh´acnhau v´oi ki, di ≤ n. Nˆentˆo`n ta.i c´acchı˙’ sˆo´ s, t sao cho (ks, ds) = (kt, dt). . . Nhung c´acsˆo´ lˆa´y l`aphˆanbiˆe.t, nˆen as 6= at. Khˆongmˆa´t t´ınhtˆo˙’ng qu´atgia˙’ su˙’ as #Y th`ıtˆo`n ta. i x1, x2 ∈ X, x1 6= x2, sao cho f(x1) = f(x2). 37
37. . Thˆa.t vˆa.y, d¯ˇa.t X l`atˆa.p c´acvˆa.t v`a Y l`atˆa.p c´achˆo.p. G´anmˆo˜i vˆa.t x v´oi mˆo.t hˆo.p f(x). . Theo nguyˆenl´ychuˆo`ng chim bˆo` cˆauda.ng th´u nhˆa´t, c´o´ıtnhˆa´t hai vˆa.t kh´acnhau x1, x2 ∈ X . . . d¯uo. c g´anc`ungmˆo.t hˆo.p; t´uc l`a f(x1) = f(x2). . . . . . . . V´ıdu. 1.6.4 Nˆe´u 20 bˆo. vi xu˙’ l´yd¯uo. c nˆo´i v´oi nhau th`ıc´o´ıtnhˆa´t hai bˆo. vi xu˙’ l´yd¯uo. c nˆo´i . . . tru. c tiˆe´p t´oi c`ungsˆo´ c´acbˆo. vi xu˙’ l´y. . . . . . K´yhiˆe.u c´acbˆo. vi xu˙’ l´yl`a1, 2, , 20. D- ˇa.t ai l`asˆo´ c´acbˆo. vi xu˙’ l´yd¯uo. c nˆo´i tru. c tiˆe´p . . . . v´oi bˆo. vi xu˙’ l´y i. Ch´ungta cˆa`n ch´ung minh rˇa`ng ai = aj v´oi i 6= j n`aod¯´o.Miˆe` n x´acd¯i.nh . . . v`amiˆe` n gi´atri. cu˙’a A tuong ´ung l`a X := {1, 2, , 20} v`a Y := {0, 1, , 19}. Tuy nhiˆen, . #X = #{0, 1, , 19} nˆenkhˆongthˆe˙’ ´apdu. ng tru. c tiˆe´p nguyˆenl´ychuˆo`ng chim bˆo` cˆauda.ng hai. . . . Ch´u´yrˇa`ng ta khˆongthˆe˙’ c´o ai = 0 v`a aj = 19 v´oi i, j n`aod¯´o,v`ınˆe´u nguo. c la.i ta c´omˆo.t . . . . . . . bˆo. vi xu˙’ l´y(th´u i) khˆongd¯uo. c nˆo´i v´oi bˆa´t c´u bˆo. vi xu˙’ l´yn`aotrong khi la.i c´omˆo.t bˆo. vi . . . . . . . . xu˙’ l´y(th´u j) d¯uo. c nˆo´i v´oi tˆa´t ca˙’ c´acbˆo. vi xu˙’ l´ykh´ac(kˆe˙’ c´acbˆo. vi xu˙’ l´yth´u i). Do d¯´o Y l`atˆa.p con cu˙’a tˆa.p {0, 1, , 18} hoˇa.c {1, 2, , 19}. Vˆa.y #Y < 20 = #X. Theo nguyˆenl´y . chuˆo`ng chim bˆo` cˆauda.ng hai ta c´o ai = aj v´oi i 6= j n`aod¯´o. . . . V´ıdu. 1.6.5 Ch´ung minh rˇa`ng nˆe´u cho.n 151 gi´aotr`ınhm´ayt´ınhphˆanbiˆe.t d¯uo. c d¯´anhsˆo´ . . . . . th´u tu. t`u 1 d¯ˆe´n 300 th`ıc´o´ıtnhˆa´t hai gi´aotr`ınhc´osˆo´ th´u tu. liˆentiˆe´p. . . . Gia˙’ su˙’ c´acgi´aotr`ınhd¯uo. c d¯´anhsˆo´ l`a c1, c2, . . . , c151. (1.3) C´acsˆo´ n`ayc`ungv´o.i c1 + 1, c2 + 1, . . . , c151 + 1 (1.4) . . ta.o th`anh302 sˆo´ thay d¯ˆo˙’i t`u 1 d¯ˆe´n 301. Theo nguyˆenl´ychuˆo`ng chim bˆo` cˆauda.ng th´u hai c´o´ıtnhˆa´t hai gi´atri. bˇa`ng nhau. C´acsˆo´ trong (1.3) l`aphˆanbiˆe.t v`ado d¯´oc´acsˆo´ trong (1.4) c˜ungkh´acnhau. V`ıvˆa.y pha˙’i c´omˆo.t sˆo´ trong d˜ay(1.3) bˇa`ng mˆo.t sˆo´ trong d˜ay(1.4). Do d¯´o ci = cj + 1 . . (hiˆe˙’n nhiˆen i 6= j) v`ata c´ohai gi´aotr`ınh ci v`a cj d¯uo. c d¯´anhsˆo´ liˆentiˆe´p. . . . V´ıdu. 1.6.6 Ba˙’n kˆet`aikhoa˙’n gˆo`m 80 khoa˙’n mu. c, mˆo˜i khoa˙’n mu. c d¯uo. c d¯´anhdˆa´u “ho. p . . . lˆe.” hoˇa.c “khˆongho. p lˆe.”. C´o45 khoa˙’n mu. c ho. p lˆe Ch´ung minh rˇa`ng c´o´ıtnhˆa´t hai khoa˙’n mu. c trong danh s´ach c´ach nhau ch´ınhx´acch´ınkhoa˙’n mu. c. (Chˇa˙’ng ha.n c´ackhoa˙’n mu. c ta.i c´acvi. tr´ı13 v`a22 hoˇa.c ta.i vi. tr´ı69 v`a78). . . . K´yhiˆe.u ai l`avi. tr´ıcu˙’a khoa˙’n mu. c ho. p lˆe. th´u i. Ta cˆa`n chı˙’ ra ai − aj = 9 v´oi i, j n`aod¯´o. X´etc´acsˆo´ a1, a2, . . . , a45 (1.5) 38
38. v`a a1 + 9, a2 + 9, . . . , a45 + 9. (1.6) . 90 sˆo´ trong (1.5) v`a(1.6) lˆa´y c´acgi´atri. t`u 1 d¯ˆe´n 89. Do d¯´otheo nguyˆenl´ychuˆo`ng chim bˆo` . cˆauda.ng th´u hai, c´o´ıtnhˆa´t hai sˆo´ tr`ungnhau. Hiˆe˙’n nhiˆenkhˆongthˆe˙’ c´ohai sˆo´ trong d˜ay (1.5) hoˇa.c (1.6) bˇa`ng nhau; nˆentˆo`n ta.i mˆo.t sˆo´ trong d˜ay(1.5) bˇa`ng mˆo.t sˆo´ trong d˜ay(1.6). . Vˆa.y ai − aj = 9 v´oi i, j n`aod¯´o. . . K´yhiˆe.u dxe l`asˆo´ nguyˆennho˙’ nhˆa´t l´on hon x. V´ıdu. d8.3e = 9. K´yhiˆe.u [x] l`asˆo´ nguyˆen . . l´on nhˆa´t nho˙’ hon x. V´ıdu. [2.3] = 2. . 1.6.3 Nguyˆenl´ychuˆo`ng chim bˆo` cˆau(da.ng th´u ba) . . . . Cho f l`a´anhxa. t`u tˆa. p h˜uu ha. n X d¯ˆe´n tˆa. p h˜uu ha. n Y. Gia˙’ su˙’ n := #X, m := #Y, k := dn/me. Khi d¯´otˆo`n ta. i ´ıtnhˆa´t k gi´atri. a1, a2, . . . , ak sao cho f(a1) = f(a2) = ããã = f(ak). . . Ch´ung minh. D- ˇa.t Y := {y1, y2, . . . , ym}. Gia˙’ su˙’ khˇa˙’ng d¯i.nh l`asai. Khi d¯´otˆo`n ta.i nhiˆe` u nhˆa´t . . k − 1 gi´atri. x ∈ X v´oi f(x) = y1; tˆo`n ta.i nhiˆe` u nhˆa´t k − 1 gi´atri. x ∈ X v´oi f(x) = y2; ; . tˆo`n ta.i nhiˆe` u nhˆa´t k − 1 gi´atri. x ∈ X v´oi f(x) = ym. Do d¯´otˆo`n ta.i nhiˆe` u nhˆa´t m(k − 1) . . phˆa`n tu˙’ trong miˆe` n x´acd¯i.nh cu˙’a f. Nhung n m(k − 1) < m = n, m vˆol´y.Do d¯´otˆo`n ta.i ´ıtnhˆa´t k gi´atri. a1, a2, . . . , ak ∈ X sao cho f(a1) = f(a2) = ããã = f(ak). 2 . . V´ıdu. 1.6.7 Mˆo.t d¯ˇa.c trung h˜uu ´ıch cu˙’a c´aca˙’nh d¯entrˇa´ng l`ad¯ˆo. s´angtrung b`ınhcu˙’a a˙’nh. . . . . . Ta n´oirˇa`ng hai a˙’nh l`a tuong tu. nˆe´u d¯ˆo. s´angtrung b`ınhcu˙’a ch´ungkh´acnhau khˆongvuo. t . . . . qu´amˆo.t ngu˜ong n`aod¯´o. Ch´ung minh rˇa`ng trong sˆo´ s´aua˙’nh, hoˇa.c c´oba a˙’nh d¯ˆo`ng th`oi . . . . . . . tuong tu. , hoˇa.c c´oba a˙’nh d¯ˆo`ng th`oi khˆongtuong tu. . . . . K´yhiˆe.u c´aca˙’nh l`a P1,P2, ,P6. Mˆo˜i cˇa.p (P1,Pi), i = 2, 3, , 6, c´ogi´atri. “tuong tu. ” . . . . hoˇa.c “khˆongtuong tu. ”. Theo nguyˆenl´ychuˆo`ng chim bˆo` cˆauda.ng th´u ba, tˆo`n ta.i ´ıtnhˆa´t . . d5/2e = 3 cˇa.p v´oi c`unggi´atri.; t´uc l`atˆo`n ta.i c´accˇa.p (P1,Pi), (P1,Pj), (P1,Pk) . . . . . . . . . . . . . . . hoˇa.c tuong tu. , hoˇa.c khˆongtuong tu. . Gia˙’ su˙’ mˆo˜i cˇa.p l`atuong tu. (trong tru`ong ho. p nguo. c la.i, xem B`aitˆa.p 5). Nˆe´u mˆo.t trong c´accˇa.p (Pi,Pj), (Pi,Pk), (Pj,Pk) (1.7) 39
39. . . . . . . . l`atuong tu. , th`ıhai h`ınha˙’nh n`ayc`ungv´oi P1 d¯ˆoimˆo.t tuong tu. v`ado d¯´ota c´oba h`ınh . . . . . . . . . . . tuong tu. . Nguo. c la.i, nˆe´u c´accˇa.p trong (1.7) khˆongtuong tu. th`ıta c´oba a˙’nh tuong ´ung . . . khˆongtuong tu. . . . V´ıdu. 1.6.8 Sˆo´ ho.c viˆentˆo´i thiˆe˙’u l`abao nhiˆeud¯ˆe˙’ d¯a˙’m ba˙’o ´ıtnhˆa´t c´o6 ngu`oi c`ungthang d¯iˆe˙’m, nˆe´u gi´aoviˆencho d¯iˆe˙’m theo thang d¯iˆe˙’m A, B, C, D, F ? Ta c´o N l`asˆo´ nho˙’ nhˆa´t thoa˙’ dN/5e = 6. Suy ra N = 5 ì 5 + 1 = 26 ho.c viˆen. . . . . . . V´ıdu. 1.6.9 Gia˙’ su˙’ nh´omc´os´aungu`oi; c´u lˆa´y mˆo.t cˇa.p bˆa´t k`y,th`ıhai ngu`oi n`ayhoˇa.c l`a . ba.n, hoˇa.c l`ath`u.Ch´ung minh rˇa`ng s˜ec´oc´acbˆo. ba hoˇa.c d¯ˆe` u l`aba.n cu˙’a nhau, hoˇa.c d¯ˆe` u l`a th`ucu˙’a nhau. . . . . Lˆa´y x l`angu`oi bˆa´t k`ytrong nh´om;nˇamngu`oi c`onla.i lˆa.p th`anhnh´omriˆeng.Ta ta.o hai . . . . . hˆo.p B v`a T. Nˇamngu`oi n`ays˜ed¯uo. c phˆanloa.i (theo quan hˆe. v´oi x): . . . . . (a) hoˇa.c l`aba.n cu˙’a x : tuong ´ung ngu`oi trong hˆo.p B; . . . . . (b) hoˇa.c l`ath`ucu˙’a x : tuong ´ung ngu`oi trong hˆo.p T. . Theo nguyˆenl´ychuˆo`ng chim bˆo` cˆauda.ng th´u ba, s˜ec´omˆo.t hˆo.p c´o´ıtnhˆa´t d5/2e = 3 . . . . . . ngu`oi. Gia˙’ su˙’ d¯´ol`ahˆo.p B v´oi ba ngu`oi y, z, u. . . Nˆe´u tˆo`n ta.i cˇa.p trong nh´omba ngu`oi n`ayl`aba.n cu˙’a nhau, chˇa˙’ng ha.n y v`a z, khi d¯´o . . . {x, y, z} l`abˆo. ba cˆa`n t`ım.Nguo. c la.i, t´uc l`a y, z, u mˆo˜i cˇa.p d¯ˆoimˆo.t l`ath`ucu˙’a nhau, khi d¯´o {y, z, u} l`abˆo. ba cˆa`n t`ım. . . . . . . . C´actru`ong ho. p c`onla.i ch´ung minh tuong tu. . B`aitˆa.p . . . . 1. C´othˆe˙’ nˆo´i nˇamm´ayt´ınhv´oi nhau sao cho c´och´ınhx´achai m´ayt´ınhd¯uo. c nˆo´i tru. c tiˆe´p d¯ˆe´n c`ungmˆo.t sˆo´ m´ay?Gia˙’i th´ıch. . . . 2. Ba˙’n kˆet`aikhoa˙’n gˆo`m 115 khoa˙’n mu. c, mˆo˜i khoa˙’n mu. c d¯uo. c d¯´anhdˆa´u “ho. p lˆe.” hoˇa.c . . . “khˆongho. p lˆe.”. C´o60 khoa˙’n mu. c ho. p lˆe Ch´ung minh rˇa`ng c´o´ıtnhˆa´t hai khoa˙’n mu. c trong danh s´ach c´ach nhau ch´ınhx´acbˆo´n khoa˙’n mu. c. . . . 3. Ba˙’n kˆet`aikhoa˙’n gˆo`m 100 khoa˙’n mu. c, mˆo˜i khoa˙’n mu. c d¯uo. c d¯´anhdˆa´u “ho. p lˆe.” hoˇa.c . . . “khˆongho. p lˆe.”. C´o55 khoa˙’n mu. c ho. p lˆe Ch´ung minh rˇa`ng c´o´ıtnhˆa´t hai khoa˙’n mu. c trong danh s´ach c´ach nhau ch´ınhx´acch´ınkhoa˙’n mu. c. . . . 4. Ba˙’n kˆet`aikhoa˙’n gˆo`m 80 khoa˙’n mu. c, mˆo˜i khoa˙’n mu. c d¯uo. c d¯´anhdˆa´u “ho. p lˆe.” hoˇa.c . . . “khˆongho. p lˆe.”. C´o50 khoa˙’n mu. c ho. p lˆe Ch´ung minh rˇa`ng c´o´ıtnhˆa´t hai khoa˙’n mu. c trong danh s´ach c´ach nhau ch´ınhx´achoˇa.c ba hoˇa.c s´aukhoa˙’n mu. c. 40
40. 5. Ho`anchı˙’nh V´ıdu. 1.6.5 bˇa`ng c´ach chı˙’ ra rˇa`ng nˆe´u c´accˇa.p (P1,Pi), (P1,Pj), (P1,Pk) l`a . . . . . . . . . khˆongtuong tu. th`ıtˆo`n ta.i ba a˙’nh d¯ˆoimˆo.t tuong tu. hoˇa.c d¯ˆoimˆo.t khˆongtuong tu. . . 6. Kˆe´t luˆa.n cu˙’a V´ıdu. 1.6.5 nhu thˆe´ n`aonˆe´u: (a) C´o´ıtho.n s´aua˙’nh? (b) C´oho.n s´aua˙’nh? . . . 7. Gia˙’ su˙’ X gˆo`m (n + 2) phˆa`n tu˙’ l`atˆa.p con cu˙’a {1, 2, , 2n + 1} v`a m := max X. V´oi ˜ mˆoi k ∈ X \{m} d¯ˇa.t ( k nˆe´u k ≤ m , a := 2 k ´ m m − k nˆeu k > 2 . . . (a) Ch´ung minh miˆe` n gi´atri. cu˙’a a ch´ua trong {1, 2, . . . , n}. (b) Suy ra tˆo`n ta.i i 6= j sao cho ai 6= aj. . . (c) Ch´ung minh tˆo`n ta.i hai phˆa`n tu˙’ phˆanbiˆe.t i, j ∈ X sao cho m = i + j. . (d) Cho v´ıdu. tˆa.p X gˆo`m (n + 1) phˆa`n tu˙’ l`atˆa.p con cu˙’a {1, 2, , 2n + 1} c´ot´ınh chˆa´t: Khˆongtˆo`n ta.i i, j ∈ X sao cho i + j ∈ X. . . . . . 8. X´etmˆo.t nh´om10 ngu`oi v´oi c´actuˆo˙’i (d¯uo. c t´ınhl`asˆo´ nguyˆen)l`a a1, a2, . . . , a10. D- ˇa.t ri := ai mod 16 v`a ( ri nˆe´u ri ≤ 8, si := 16 − ri nˆe´u ri > 8. . . (a) Ch´ung minh rˇa`ng s1, s2, . . . , s10 thay d¯ˆo˙’i t`u 0 d¯ˆe´n 8. . (b) Ch´ung minh tˆo`n ta.i j 6= k sao cho sj 6= sk. . (c) Ch´ung minh rˇa`ng nˆe´u sj = rj v`a sk = rk hoˇa.c sj = 16 − rj v`a sk = 16 − rk th`ı16 chia hˆe´t aj − ak. . (d) Ch´ung minh rˇa`ng nˆe´u c´acd¯iˆe` u kiˆe.n trong (c) sai th`ı16 chia hˆe´t aj + ak. . . . 9. Ch´ung minh rˇa`ng trong khai triˆe˙’n thˆa.p phˆancu˙’a thuong cu˙’a hai sˆo´ nguyˆen,khˆo´i c´ac . ch˜u sˆo´ cuˆo´i c`ungl`alˇa.p la.i. V´ıdu. 1/6 = 0.1666 , 217/660 = 0.32878787 . . . . 10. Mu`oi s´aucˆa`u thu˙’ b´ongrˆo˙’ mˇa.c ´aomang c´acsˆo´ t`u 1 d¯ˆe´n 12 d¯´ung th`anhv`ongtr`ontrˆen . . . s`and¯ˆa´u theo th´u tu. tu`y´y.Ch´ung minh rˇa`ng tˆo`n ta.i ba cˆa`u thu˙’ liˆentiˆe´p c´otˆo˙’ng c´ac sˆo´´ıtnhˆa´t 26. . . k . 11. Gia˙’ su˙’ f l`a´anhxa. mˆo.t-mˆo.t lˆent`u X := {1, 2, . . . , n} lˆen X. K´yhiˆe.u f l`a´anhxa. ho. p k lˆa`n cu˙’a f : f k := f ◦ f ◦ ã ã ã ◦ f . | {z } k lˆa`n . i j . Ch´ung minh rˇa`ng tˆo`n ta.i c´acsˆo´ nguyˆenphˆanbiˆe.t i 6= j sao cho f (x) 6= f (x) v´oi mo.i . k . x ∈ X. Ch´ung minh rˇa`ng tˆo`n ta.i sˆo´ nguyˆen k sao cho f (x) = x v´oi mo.i x ∈ X. 41
41. . . . . . 12. Mˆo.t h`ınhch˜u nhˆa.t k´ıch thu´oc 3 ì 7 d¯uo. c chia th`anh21 h`ınhvuˆong;mˆo˜i h`ınhvuˆong . . . . . . d¯uo. c tˆom`aud¯enhoˇa.c trˇa´ng. Ch´ung minh rˇa`ng b`anc`o ch´ua mˆo.t h`ınhch˜u nhˆa.t khˆong . . . . . tˆa`m thu`ong (khˆongc´ok´ıch thu´oc 1 ì k hoˇa.c k ì 1) sao cho bˆo´n h`ınhvuˆongo˙’ mˆo˜i g´oc hoˇa.c tˆa´t ca˙’ tˆom`aud¯enhoˇa.c tˆa´t ca˙’ tˆom`autrˇa´ng. . . . . 13. Ch´ung minh rˇa`ng nˆe´u p bit 1 v`a q bit 0 d¯uo. c d¯ˇa.t xung quanh mˆo.t v`ongtr`ontheo th´u . . tu. tu`y´y,trong d¯´o p, q, k l`ac´acsˆo´ nguyˆenthoa˙’ p ≥ kq th`ıtˆo`n ta.i k bit 1 d¯´ung liˆen tiˆe´p. . 14. Viˆe´t thuˆa.t to´ant`ımd¯ˆo. d`aicu˙’a d˜aycon d¯on d¯iˆe.u tˇangd`ainhˆa´t cu˙’a mˆo.t d˜aysˆo´ cho tru.´o.c. 42
42. Chu.o.ng 2 QUAN HEˆ. . . . . . Nhu d¯˜abiˆe´t, tˆa´t ca˙’ c´acd¯ˆo´i tuo. ng trong thˆe´ gi´oi xung quanh ta d¯ˆe` u c´onh˜ung mˆo´i quan hˆe. . . . . nhˆa´t d¯i.nh v´oi nhau. R˜or`angkhˆongc´omˆo.t d¯ˆo´i tuo. ng n`aoc´othˆe˙’ tˆo`n ta.i t´ach r`oi (khˆong . . . . . . liˆenquan) v´oi thˆe´ gi´oi bˆenngo`ai. Mˇa.t kh´ac,mˆo˜i d¯ˆo´i tuo. ng la.i ch´ua d¯u. ng rˆa´t nhiˆe` u mˆo´i . quan hˆe. nˆo.i ta.i cu˙’a ba˙’n thˆann´o.X´etmˆo.t nh´omsinh viˆentrong c`ungmˆo.t l´op, ta c´othˆe˙’ n´oi . . rˇa`ng hai sinh viˆenc´oquan hˆe. v´oi nhau nˆe´u ho. c´oc`ungquˆe.X´etmˆo.t tˆa.p ho. p c´acsˆo´ nguyˆen . . . {1, 2, , 15}, ta c´othˆe˙’ n´oirˇa`ng ba phˆa`n tu˙’ n`aod¯´ocu˙’a tˆa.p ho. p n`ayc´oquan hˆe. v´oi nhau . . . nˆe´u tˆo˙’ng cu˙’a ch´ungchia hˆe´t cho 4. N´oimˆo.t c´ach kh´ac,c´acphˆa`n tu˙’ hay c´acd¯ˆo´i tuo. ng c´o . . . . . quan hˆe. chˇa.t ch˜ev´oi nhau, nhung mˆo´i quan hˆe. d¯uo. c hiˆe˙’u nhu thˆe´ n`aol`aphu. thuˆo.c v`ao . . . . . . . d¯i.nh ngh˜ıacu˙’a ch´ungta. Mˆoh`ınhco so˙’ d˜u liˆe.u quan hˆe., d¯uo. c d¯ua ra bo˙’ i E. F. Codd v`ao . . . nˇam1970, du. a trˆenkh´ainiˆe.m cu˙’a quan hˆe. n ngˆoil`amˆo.t trong nh˜ung ´ung du. ng cu˙’a quan hˆe. trong Tin ho.c. . . . . . . Trong chuong n`ay, ch´ungta s˜enghiˆenc´uu c´acmˆo´i quan hˆe. trˆenco so˙’ l´ythuyˆe´t tˆa.p ho. p. . . . . Tru´oc hˆe´t ta nghiˆenc´uu c´acmˆo´i quan hˆe. hai ngˆoitrˆenhai tˆa.p ho. p v`atrˆenc`ungmˆo.t tˆa.p . . ho. p, c`ungv´oi c´act´ınhchˆa´t cu˙’a c´acmˆo´i quan hˆe. d¯´o.Tiˆe´p theo, ch´ungta s˜ex´etd¯ˆe´n quan . . . . . . hˆe. th´u tu. , quan hˆe. tuong d¯uong v`ac´acmˆo´i liˆenquan. 2.1 Quan hˆe. hai ngˆoi . D- .inh ngh˜ıa2.1.1 Quan hˆe. hai ngˆoi t`u tˆa.p S lˆentˆa.p T, k´ıhiˆe.u R, l`amˆo.t tˆa.p con cu˙’a . . S ì T. Tˆa.p S d¯uo. c go.i l`a miˆe` n x´acd¯i.nh c`on T l`a d¯ˆo´i miˆe` n x´acd¯i.nh. Nˆe´u S ≡ T ta n´oi R l`aquan hˆe. hai ngˆoitrˆen S. . . . V´ıdu. 2.1.1 Gia˙’ su˙’ S l`adanh s´ach c´acsinh viˆencu˙’a tru`ong d¯a.i ho.c. T l`adanh s´ach c´ac . . ch´ung chı˙’ ho.c. Tˆa.p R ⊂ S ì T gˆo`m c´accˇa.p (a, b), trong d¯´o a l`asinh viˆenc`on b l`ach´ung . chı˙’ m`asinh viˆenghi danh ho.c. V´oi mˆo˜i a ∈ S, tˆa.p {b ∈ T | (a, b) ∈ R} l`adanh s´ach c´ac 43
43. • b 1 • b 2 a1 • • b3 a • • 2 b4 a 3 • • b5 . a4 •. • b6 H`ınh2.1: . ch´ung chı˙’ m`asinh viˆen a theo ho.c. Tˆa.p {a | (a, b) ∈ R} l`adanh s´ach c´acsinh viˆentheo ho.c ch´u.ng chı˙’ b. . . . . . . . V´ıdu. 2.1.2 Gia˙’ su˙’ P l`atˆa.p c´acchuong tr`ınhd¯uo. c thu. c hiˆe.n trˆenm´ayt´ınhv`amˆo.t d¯on . . . . . vi. C c´acchuong tr`ınhc´osˇa˜n cho ph´epd¯ˆe˙’ su˙’ du. ng. Ta d¯ˇa.t mˆo.t quan hˆe. R t`u C lˆen P nhu . . . sau: (c, p) ∈ R nˆe´u chuong tr`ınh p su˙’ du. ng thu˙’ tu. c c. V´ıdu. 2.1.3 Cho S := {a1, a2, a3, a4} l`atˆa.p c´acsinh viˆentˆo´t nghiˆe.p c`on T := {b1, b2, b3, b4, b5, b6} . l`atˆa.p c´acco quan cˆa`n nhˆa.n sinh viˆentˆo´t nghiˆe.p. Quan hˆe. R := {(a1, b2), (a2, b1), (a3, b6), (a4, b4)} . . t`u S lˆen T mˆota˙’ c´accˇa.p sˇa´p xˆe´p noi cˆongt´accho mˆo˜i sinh viˆen. . . . . . . . Trong chuong n`ay, ngoa.i tr`u nh˜ung tru`ong ho. p ngoa.i lˆe. m`as˜en´oir˜o,ta s˜eluˆonluˆongia˙’ . . . . thiˆe´t rˇa`ng c´acquan hˆe. d¯uo. c x´ettrˆenc´ac tˆa. p h˜uu ha. n. Khi d¯´oc´othˆe˙’ mˆota˙’ quan hˆe. R t`u . . . . . S lˆen T bˇa`ng phuong ph´ap d¯ˆo` thi. (xem thˆemChuong 5) nhu sau: c´acd¯ı˙’nh cu˙’a d¯ˆo` thi. biˆe˙’u . . . . . thi. c´acphˆa`n tu˙’ cu˙’a S v`a T, c`onc´accung l`ac´acd¯u`ong c´ohu´ong nˆo´i c´accˇa.p (a, b) ∈ R (c´o . . . . khi ngu`oi ta viˆe´t tˇa´t du´oi da.ng aRb); chˇa˙’ng ha.n quan hˆe. trong V´ıdu. 2.1.3 c´od¯ˆo` thi. trong H`ınh2.1. . . . . . Ngo`aira, ngu`oi ta c˜ungthu`ong d`ungma trˆa.n cˆa´p m ì n d¯ˆe˙’ biˆe˙’u thi. mˆo´i quan hˆe. R t`u . S = {a1, a2, . . . , am} lˆen T = {b1, b2, . . . , bn}, trong d¯´o m := #S, n := #T. Phˆa`n tu˙’ mij cu˙’a . . . ma trˆa.n d¯uo. c x´acd¯i.nh nhu sau ( 1 nˆe´u (ai, bj) ∈ R, mij := . . 0 nˆe´u nguo. c la.i. 44
44. V´ıdu. 2.1.4 Ma trˆa.n biˆe˙’u diˆe˜n quan hˆe. R trong V´ıdu. 2.1.3 l`a b b b b b b  1 2 3 4 5 6  a1 0 1 0 0 0 0 a  1 0 0 0 0 0  2 . a3 0 0 0 0 0 1  a4 0 0 0 1 0 1 . . . Ba˙’n thˆanc´acquan hˆe. la.i liˆenquan v´oi nhau ta.o nˆenc´acquan hˆe. m´oi. Chˇa˙’ng ha.n, ho. p . . . gi˜ua c´acquan hˆe. l`amˆo.t h`ınhth´uc ta.o nˆenc´acquan hˆe. m´oi. . . . . V´ıdu. 2.1.5 Gia˙’ su˙’ R1 l`aquan hˆe. t`u S1 lˆen S2; R2 l`aquan hˆe. t`u S2 lˆen S3. Ho. p cu˙’a hai . . quan hˆe. R1 v`a R2 l`amˆo.t quan hˆe. t`u S1 lˆen S3 x´acd¯i.nh bo˙’ i R1R2 := {(x, z) ∈ S1 ì S3 | tˆo`n ta.i y ∈ S2 d¯ˆe˙’ (x, y) ∈ R1, (y, z) ∈ R2}. . . 0 V´ıdu. 2.1.6 Gia˙’ su˙’ T l`atˆa.p c´acch´ung chı˙’, U l`atˆa.p c´ackhoa. Quan hˆe. R ⊂ S ì U gˆo`m . c´accˇa.p (b, c) sao cho ch´ung chı˙’ b ∈ T l`abˇa´t buˆo.c ghi danh ho.c khoa U. X´etquan hˆe. R . 0 . nhu trong V´ıdu. 2.1.1. Thˆe´ th`ı RR l`atˆa.p c´accˇa.p (a, c) sao cho tˆo`n ta.i ch´ung chı˙’ bˇa´t buˆo.c . . . 0 m`asinh viˆen a pha˙’i ho.c khi ghi danh v`aokhoa c. Ch´u´yrˇa`ng trong tru`ong ho. p n`ay R R l`a khˆongc´ongh˜ıa! . . . Dˆe˜ d`angch´ung minh rˇa`ng (gia˙’ su˙’ c´acph´epto´anho. p l`ac´ongh˜ıa): . T´ınhchˆa´t 2.1.2 (a) T´ınhkˆe´t ho. p (R1R2)R3 = R1(R2R3). . . (b) T´ınhphˆanbˆo´ d¯ˆo´i v´oi ph´epho. p, ngh˜ıal`a (R1 ∪ R2)R3 = (R1R3) ∪ (R2R3),R1(R2 ∪ R3) = (R1R2) ∪ (R1R3). . (c) T´ınhch´ınhquy d¯ˆo´i v´oi c´acph´epbao h`am,ngh˜ıal`anˆe´u R1 ⊂ R2 v`a R3 ⊂ R4, th`ı R1 ∪ R3 ⊂ R2 ∪ R4,R1 ∩ R3 ⊂ R2 ∩ R4. . . Hon n˜ua, nˆe´u R1 ⊂ R2 v`a R3 ⊂ R4 th`ı R1R3 ⊂ R2R4. - . V´ıdu. 2.1.7 Dˇa.t S1 := {1, 2, 3, 4, 5},S2 := {a, b, c} v`a S3 := [e, f, g, h}. X´etc´acquan hˆe. t`u . . . . . S1 lˆen S2 v`at`u S2 lˆen S3 x´acd¯i.nh tuong ´ung bo˙’ i R1 := {(1, a), (2, a), (2, c), (3, a), (3, b), (4, a), (4, b), (4, c), (5, b)}, R2 := {(a, e), (a, g), (b, f), (b, g), (b, h), (c, e), (c, g), (c, h)}. 45
45. Khi d¯´o R1R2 = {(1, e), (1, g), (2, e), (2, g), (2, h), (3, e), (3, f), (3, g), (3, h), (4, e), (4, f), (4, g), (4, h), (5, f), (5, g), (5, h)}, . . . v`ac´acma trˆa.n A1,A2 v`a A tuong ´ung c´acquan hˆe. R1,R2 v`a R1R2 l`a     1 0 0   1 0 1 0     1 0 1 1 0 1 0 1 0 1 1       A1 = 1 1 0 ,A2 = 0 1 1 1 ,A = 1 1 1 1 . 1 1 1 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 So s´anh A v`ama trˆa.n t´ıch cu˙’a A1 v`a A2   1 0 1 0   2 0 2 1   A1A2 = 1 1 2 1 , 2 1 3 2 0 1 1 1 . . . . . ta thˆa´y sˆo´ 1 trong ma trˆa.n A tuong ´ung v´oi phˆa`n tu˙’ kh´ac0 trong ma trˆa.n A1A2!D- iˆe` u n`ay . . s˜ed¯uo. c gia˙’i th´ıch trong phˆa`n sau. . . . . −1 D- .inh ngh˜ıa2.1.3 Gia˙’ su˙’ R l`aquan hˆe. t`u S lˆen T. Quan hˆe. nguo. c cu˙’a R, k´yhiˆe.u R , l`a . . mˆo.t quan hˆe. t`u T lˆen S x´acd¯i.nh bo˙’ i R−1 := {(x, y) ∈ T ì S | (x, y) ∈ R}. . T´ınhchˆa´t 2.1.4 Gia˙’ su˙’ R l`aquan hˆe. trˆen S. Khi d¯´o (a) R = R−1 nˆe´u v`achı˙’ nˆe´u R d¯ˆo´i x´u.ng, t´u.c l`a R = R−1 ⇔ xRy suy ra yRx. (b) R ∩ R−1 ⊂ E := {(x, x) | x ∈ S} nˆe´u v`achı˙’ nˆe´u R pha˙’n d¯ˆo´i x´u.ng, t´u.c l`a R ∩ R−1 ⊂ E ⇔ xRy v`a yRx th`ı x = y. . Ch´ung minh (a) Hiˆe˙’n nhiˆentheo d¯i.nh ngh˜ıa. (b) Gia˙’ su˙’. R pha˙’n d¯ˆo´i x´u.ng, v`a(x, y) ∈ R ∩ R−1. Khi d¯´o xRy v`a yRx. Suy ra xRx. Hay (x, x) ∈ E. . . . −1 −1 Nguo. c la.i gia˙’ su˙’ R ∩ R ⊂ E, xRy v`a yRx. Th`ı(x, y) ∈ R ∩ R ⊂ E. Do d¯´o(x, y) ∈ E. 2 46
46. B`aitˆa.p . 1. D- ˇa.t S := {0, 1, 2}. Mˆo˜i ph´atbiˆe˙’u sau x´acd¯i.nh mˆo.t quan hˆe. R trˆen S bo˙’ i mRn nˆe´u . . . khˇa˙’ng d¯i.nh l`ad¯´ungd¯ˆo´i v´oi m, n ∈ S. Viˆe´t mˆo˜i quan hˆe. nhu mˆo.t tˆa.p c´accˇa.p c´oth´u . tu. . (a) m ≤ n. (d) mn = 0. (g) m2 + n2 = 2. (b) m < n. (e) mn = m. (h) m2 + n2 = 3. (c) m = n. (f) m + n ∈ S. (i) m = max{n, 1}. . . . . C´acquan hˆe. n`aol`ad¯ˆo´i x´ung? pha˙’n d¯ˆo´i x´ung? Viˆe´t ma trˆa.n v`av˜ec´acd¯ˆo` thi. tuong ´u.ng. 2. C´acquan hˆe. hai ngˆoisau x´acd¯i.nh trˆen N. . . . (a) Viˆe´t quan hˆe. hai ngˆoi R1 x´acd¯i.nh bo˙’ i m + n = 5 da.ng c´accˇa.p th´u tu. . . . . (b) Nhu trˆenv´oi R2 x´acd¯i.nh bo˙’ i max{m, n} = 2. . . . (c) Quan hˆe. hai ngˆoi R3 x´acd¯i.nh bo˙’ i min{m, n} = 2 gˆo`m vˆoha.n c´accˇa.p th´u tu. . H˜ay viˆe´t nˇamcˇa.p trong d¯´o. . . 3. Nˆe´u A l`ama trˆa.n cu˙’a quan hˆe. R t`u S lˆen T (gia˙’ thiˆe´t S v`a T l`ac´actˆa.p h˜uu ha.n). . . −1 T`ımma trˆa.n cu˙’a quan hˆe. nguo. c R . . . . 4. Gia˙’ su˙’ R l`aquan hˆe. hai ngˆoitrˆentˆa.p S. Ch´ung minh rˇa`ng R l`ad¯ˆo´i x´ung nˆe´u v`achı˙’ nˆe´u R = R−1. . . 5. Gia˙’ su˙’ R1,R2 l`ac´acquan hˆe. t`u S lˆen T. . −1 −1 −1 (a) Ch´ung minh rˇa`ng (R1 ∪ R2) = R1 ∪ R2 . . −1 −1 −1 (b) Ch´ung minh rˇa`ng (R1 ∩ R2) = R1 ∩ R2 . . −1 −1 (c) Ch´ung minh rˇa`ng nˆe´u R1 ⊆ R2 th`ı R1 ⊆ R2 . . . −1 6. Gia˙’ su˙’ G l`ad¯ˆo` thi. cu˙’a quan hˆe. R trˆentˆa.p h˜uu ha.n S. Mˆota˙’ d¯ˆo` thi. cu˙’a quan hˆe. R . 7. Trˆentˆa.p S := {1, 2, 3, 4} x´etc´acquan hˆe. hai ngˆoisau: R1 := {(1, 1), (1, 2), (3, 4), (4, 2)}, R2 := {(1, 1), (2, 1), (3, 1), (4, 4), (2, 2)}. . Liˆe.t kˆec´acphˆa`n tu˙’ cu˙’a R1 ◦ R2 v`a R2 ◦ R1. . . 8. Kha˙’o s´atc´acquan hˆe. R1 v`a R2 t`u S lˆen T v`ac´acquan hˆe. R3 v`a R4 t`u T lˆen U. . (a) Ch´ung minh rˇa`ng R1(R3 ∪ R4) = R1R3 ∪ R1R4. . . (b) Ch´ung minh rˇa`ng (R1 ∩ R2)R3 ⊆ R1R3 ∩ R2R3 v`ad¯ˇa˙’ng th´uc khˆongnhˆa´t thiˆe´t d¯´ung. . (c) C´acquan hˆe. R1(R3 ∩ R4) v`a R1R3 ∩ R1R4 c´oliˆenhˆe. nhu thˆe´ n`ao? 47
47. 2.2 Quan hˆe. v`ama trˆa.n . Nhu V´ıdu. 2.1.7 chı˙’ ra, ma trˆa.n cu˙’a quan hˆe. R1R2 khˆongpha˙’i l`at´ıch A1A2 cu˙’a c´acma trˆa.n . . . . . R1 v`a R2. Tuy nhiˆench´ungc´omˆo´i liˆenhˆe.: phˆa`n tu˙’ bˇa`ng 1 trong A tuong ´ung mˆo.t-mˆo.t v´oi . phˆa`n tu˙’ kh´ackhˆongtrong A1A2. . X´et B := {0, 1} v`ahai ph´epto´anBoole ∧, ∨ d¯i.nh ngh˜ıanhu sau: ∨ 0 1 ∧ 0 1 0 0 1 0 0 0 1 1 1 1 0 1 Dˆe˜ thˆa´y rˇa`ng . T´ınhchˆa´t 2.2.1 V´oi mo. i x, y ∈ B ta c´o x ∨ y = max{x, y}, x ∧ y = min{x, y}. . . . D- .inh ngh˜ıa2.2.2 (a) A d¯uo. c go.i l`a ma trˆa. n Boole nˆe´u c´acphˆa`n tu˙’ cu˙’a n´othuˆo.c B. . . . (b) T´ıch hai ma trˆa. n Boole A1 v`a A2 cˆa´p m ì n v`a n ì p tuong ´ung l`ama trˆa.n Boole cˆa´p . m ì p, k´ıhiˆe.u A1 ∗ A2, x´acd¯i.nh bo˙’ i n (A1 ∗ A2)[i, j] := ∨k=1(A1[i, k] ∧ A2[k, j]), i = 1, 2, . . . , m, j = 1, 2, . . . , p. (c) Hˆo. i hai ma trˆa. n Boole A1 v`a A2 cˆa´p mìn l`ama trˆa.n Boole cˆa´p mìn, k´ıhiˆe.u A1 ∧A2, c´oc´acphˆa`n tu˙’. l`a (A1 ∧ A2)[i, j] := A1[i, j] ∧ A2[i, j], i = 1, 2, . . . , m, j = 1, 2, . . . , n. (d) Tuyˆe˙’n hai ma trˆa. n Boole A1 v`a A2 cˆa´p m ì n l`ama trˆa.n Boole cˆa´p m ì n, k´ıhiˆe.u . A1 ∨ A2, c´oc´acphˆa`n tu˙’ l`a (A1 ∨ A2)[i, j] := A1[i, j] ∨ A2[i, j], i = 1, 2, . . . , m, j = 1, 2, . . . , n. V´ıdu. 2.2.1 Trong V´ıdu. 2.1.7 th`ı A = A1 ∗ A2. - . . . . . D.inh l´y2.2.3 Nˆe´u A1 v`a A2 l`ac´acma trˆa. n tuong ´ung quan hˆe. R1 t`u A lˆen B v`a R2 t`u . B lˆen C th`ı A1 ∗ A2 l`ama trˆa. n cu˙’a quan hˆe. ho. p R1R2. 48
48. Ch´u.ng minh. Ta c´o (A1 ∗ A2)[i, j] = 0 ⇔ A1[i, k] ∧ A2[k, j] = 0, ∀k = 1, 2, . . . , n, ⇔ A1[i, k] = A2[k, j] = 0, ∀k = 1, 2, . . . , n. 2 . . V´ıdu. 2.2.2 Gia˙’ su˙’ R l`aquan hˆe. trˆen {1, 2, 3} v´oi ma trˆa.n   1 0 0 A = 1 0 1 . 1 1 0 Quan hˆe. R2 := RR c´oma trˆa.n   1 0 0 A ∗ A = 1 1 0 . 1 0 1 V`aquan hˆe. R3 := RR2 c´oma trˆa.n   1 0 0 A ∗ A ∗ A = 1 0 1 = A. 1 1 0 3 . . . Suy ra R = R . Hon n˜ua v´oi mo.i n ≥ 1 ta c´o Rn+2 = R(n−1)+3 = Rn−1.R3 = Rn−1.R = Rn! . . . . V´ıdu. 2.2.3 Gia˙’ su˙’ R1 v`a R2 l`ac´acquan hˆe. trˆen {1, 2} c´oc´acma trˆa.n Boole tuong ´ung à ả à ả 1 1 1 1 A = ,A = . 1 1 0 2 0 1 Do à ả à ả 1 1 1 1 A ∗ A = 6= = A ∗ A , 1 2 1 1 1 0 2 1 . . nˆen R1R2 6= R2R1. Bˆa´t d¯ˇa˙’ng th´uc n`aychı˙’ ra rˇa`ng (2, 2) ∈ R1R2 nhung (2, 2) ∈/ R2R1. . . . D- .inh l´y2.2.4 Tˆa. p P(S ì S), tˆa´t ca˙’ c´acquan hˆe. trˆen S, v´oi ph´epto´anho. p l`anu˙’ a nh´om. . . . . Ch´ung minh. Thˆa.t vˆa.y, ph´epho. p c´ot´ınhchˆa´t kˆe´t ho. p do T´ınhchˆa´t 2.1.2(a); v`ad¯on vi. l`a quan hˆe. “d¯ˆo`ng nhˆa´t”: E := {(x, x) ∈ S | x ∈ S}. 2 . . D- .inh l´ysau chı˙’ ra viˆe.c nghiˆenc´uu quan hˆe. chuyˆe˙’n vˆe` nghiˆenc´uu c´acma trˆa.n cu˙’a ch´ung. 49
49. . . . D- .inh l´y2.2.5 Gia˙’ su˙’ S l`atˆa. p n phˆa`n tu˙’ . Khi d¯´otˆo`n ta. i ´anhxa. mˆo. t-mˆo. t lˆengi˜ua tˆa. p P(S ì S) c´acquan hˆe. trˆen S v`atˆa. p c´acma trˆa. n Boole cˆa´p n ì n. Anh´ xa. n`ayba˙’o to`anc´ac . . ph´epto´annu˙’ a nh´om:nˆe´u R1,R2 v`a R l`ac´acquan hˆe. v´oi c´acma trˆa. n Boole A1,A2 v`a A tu.o.ng ´u.ng, th`ı R1R2 = R ⇔ A1 ∗ A2 = A. Ch´u.ng minh. Hiˆe˙’n nhiˆentheo c´ackˆe´t qua˙’ trˆen. 2 . . D- .inh ngh˜ıa2.2.6 Quan hˆe. hai ngˆoi R trˆen S d¯uo. c go.i l`a . (a) Pha˙’n xa. nˆe´u xRx v´oi mo.i x ∈ S; (b) Bˇa´c cˆa`u nˆe´u xRy v`a yRz th`ı xRz. . . . . V´ıdu. 2.2.4 X´etc´acquan hˆe. R1,R2,R3 v`a E trˆen S := {1, 2, 3, 4} tuong ´ung v´oi c´acma trˆa.n     0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 A :=   ,A :=   , 1 0 0 0 1 2 0 1 1 1 0 0 0 0 0 0 1 1     1 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 A :=   ,I :=   . 3 0 0 1 0 4 0 0 1 0 1 0 0 1 0 0 0 1 . . . (a) R1 l`aquan hˆe. d¯uo. c x´acd¯i.nh bo˙’ i mR1n nˆe´u m < n. Quan hˆe. R1 l`apha˙’n xa. v`abˇa´c cˆa`u. . . . (b) R2 l`aquan hˆe. d¯uo. c x´acd¯i.nh bo˙’ i mR2n nˆe´u |m − n| ≤ 1. Quan hˆe. R2 l`apha˙’n xa., d¯ˆo´i x´u.ng nhu.ng khˆongbˇa´c cˆa`u. . . . (c) R3 l`aquan hˆe. d¯uo. c x´acd¯i.nh bo˙’ i mR3n nˆe´u v`achı˙’ nˆe´u m = n (mod 3). Ta c´o R3 l`a . quan hˆe. pha˙’n xa., d¯ˆo´i x´ung v`abˇa´c cˆa`u. . (d) Quan hˆe. E := {(m, n) ∈ S ì S | m = n} trˆen S l`apha˙’n xa., d¯ˆo´i x´ung v`abˇa´c cˆa`u. . V´ıdu. 2.2.5 (a) Quan hˆe. R trˆen Z d¯i.nh ngh˜ıabo˙’ i mRn nˆe´u v`achı˙’ nˆe´u m + n = 0 (mod 3) . . l`ad¯ˆo´i x´ung, khˆongpha˙’n xa. do (1, 1) ∈/ R v`akhˆongbˇa´c cˆa`u do (4, 2), (2, 1) ∈ R nhung (4, 1) ∈/ R. . . . (b) V´oi m, n ∈ Z d¯i.nh ngh˜ıa mRn nˆe´u m − n le˙’. Quan hˆe. l`ad¯ˆo´i x´ung nhung khˆongpha˙’n xa. v`akhˆongbˇa´c cˆa`u. 50
50. . T´ınhchˆa´t 2.2.7 Gia˙’ su˙’ R l`aquan hˆe. trˆentˆa. p A. Khi d¯´o (a) R pha˙’n xa. nˆe´u v`achı˙’ nˆe´u E ⊂ R. (b) R bˇa´c cˆa`u nˆe´u v`achı˙’ nˆe´u R2 ⊂ R. Ch´u.ng minh. (a) Hiˆe˙’n nhiˆen. . 2 (b) Gia˙’ su˙’ R l`abˇa´c cˆa`u v`a(x, z) ∈ R . Khi d¯´otˆo`n ta.i y ∈ A sao cho (x, y), (y, z) ∈ R. V`ı . . . 2 2 R bˇa´c cˆa`u nˆen(x, z) ∈ R. Nguo. c la.i, gia˙’ su˙’ R ⊂ R. X´et(x, y), (y, z) ∈ R. Th`ı(x, z) ∈ R . Vˆa.y (x, z) ∈ R. 2 . Gia˙’ su˙’ A1,A2 l`ahai ma trˆa.n Boole c`ungcˆa´p m ì n. K´yhiˆe.u A1 ≤ A2 ngh˜ıal`a A1[i, j] ≤ A2[i, j] . v´oi mo.i i = 1, 2, . . . , m, j = 1, 2, . . . , n. . . . . . T´ınhchˆa´t 2.2.8 Gia˙’ su˙’ R1,R2 l`ahai quan hˆe. t`u S lˆen T tuong ´ung c´acma trˆa. n A1,A2. Ta c´o (a) R1 ⊆ R2 nˆe´u v`achı˙’ nˆe´u A1 ≤ A2. (b) R1 ∪ R2 c´oma trˆa. n Boole A1 ∨ A2. (c) R1 ∩ R2 c´oma trˆa. n Boole A1 ∧ A2. . Ch´ung minh. B`aitˆa.p. 2 . . . . Hˆe. qua˙’ 2.2.9 Gia˙’ su˙’ R l`aquan hˆe. trˆentˆa. p S tuong ´ung ma trˆa. n Boole A := (aij)nìn, n = #S. Khi d¯´o (a) R2 ⊆ R nˆe´u v`achı˙’ nˆe´u A ∗ A ≤ A. (b) R pha˙’n xa. nˆe´u v`achı˙’ nˆe´u aii = 1, i = 1, 2, . . . , n. (c) R d¯ˆo´i x´u.ng nˆe´u v`achı˙’ nˆe´u A = At. . t (d) R pha˙’n d¯ˆo´i x´ung nˆe´u v`achı˙’ nˆe´u A ∧ A ≤ In. (e) R bˇa´c cˆa`u nˆe´u v`achı˙’ nˆe´u A ∗ A ≤ A. . Ch´ung minh. B`aitˆa.p. 2 51
51. B`aitˆa.p . . . . 1. V´oi mˆo˜i ma trˆa.n Boole sau, x´etquan hˆe. tuong ´ung R trˆen {1, 2, 3}. T`ımma trˆa.n Boole cu˙’a R2 v`ax´acd¯i.nh quan hˆe. n`aol`abˇa´c cˆa`u.       1 1 0 1 0 1 0 0 1 0 1 1 , 0 1 0 , 0 1 0 . 1 0 1 1 0 1 1 0 0 V˜ed¯ˆo` thi. cu˙’a c´acquan hˆe. trˆen. . . . 2. Gia˙’ su˙’ S := {1, 2, 3},T := {a, b, c, d} v`a R1,R2 l`ac´acquan hˆe. t`u S lˆen T v´oi c´acma trˆa.n Boole     1 0 1 0 0 1 0 0 A1 := 0 1 0 0 ,A2 := 1 0 0 1 . 1 0 0 1 0 1 1 0 −1 −1 (a) T`ımc´acma trˆa.n Boole cu˙’a R1 ,R2 . −1 −1 −1 (b) T`ımc´acma trˆa.n Boole cu˙’a (R1 ∩ R2)R1 ,R1R1 ∩ R2R1 . −1 −1 −1 −1 (c) T`ımc´acma trˆa.n Boole cu˙’a R2(R1 ∪ R2 ),R2R1 ∪ R2R2 . . . (d) So s´anhc´accˆautra˙’ l`oi trong phˆa`n (b) v`a(c) v´oi c´ackhˇa˙’ng d¯i.nh trong B`aitˆa.p 10. 3. Gia˙’ su˙’. S := {1, 2, 3} v`a R := {(1, 1), (1, 2), (1, 3), (3, 2)}. (a) T`ımc´acma trˆa.n cu˙’a R, RR−1 v`a R−1R. (b) V˜ec´acd¯ˆo` thi. cu˙’a c´acquan hˆe. trong phˆa`n (a). (c) Ch´u.ng minh rˇa`ng R l`abˇa´c cˆa`u, t´u.c l`a R2 ⊆ R, nhu.ng R2 6= R. (d) R ∪ R−1 l`aquan hˆe. bˇa´c cˆa`u? Gia˙’i th´ıch. (e) T`ım Rn v´o.i n = 2, 3, 4. Gia˙’ su˙’. S := {1, 2, 3} v`a R := {(2, 1), (2, 3), (3, 2)}. (a) T`ımc´acma trˆa.n cu˙’a R, R−1 v`a R2R. (b) V˜ec´acd¯ˆo` thi. cu˙’a c´acquan hˆe. trong phˆa`n (a). (c) R l`abˇa´c cˆa`u? (d) R2 l`abˇa´c cˆa`u? (e) R ∪ R2 l`abˇa´c cˆa`u? . . 5. Gia˙’ su˙’ R l`aquan hˆe. trˆen S := {1, 2, 3} v´oi ma trˆa.n Boole   0 1 0 A := 1 1 1 . 0 1 0 (a) T`ımma trˆa.n Boole cu˙’a Rn, n ∈ Z. . (b) R l`apha˙’n xa.?D- ˆo´i x´ung? Bˇa´c cˆa`u? 52
52. . 6. Lˇa.p la.i B`aitˆa.p 5 v´oi   1 0 0 A := 0 1 1 . 1 0 1 . . . 7. Gia˙’ su˙’ P l`atˆa.p tˆa´t ca˙’ c´acngu`oi v`akha˙’o s´atquan hˆe. R, trong d¯´o pRq nˆe´u p “th´ıch” q. (a) Mˆota˙’ c´acquan hˆe. R ∩ R−1,R ∪ R−1, v`a R2. . (b) R l`apha˙’n xa.?D- ˆo´i x´ung? Bˇa´c cˆa`u? 8. Cho v´ıdu. quan hˆe. m`a . . (a) Pha˙’n d¯ˆo´i x´ung, bˇa´c cˆa`u nhung khˆongpha˙’n xa . . (b) D- ˆo´i x´ung nhung khˆongpha˙’n xa. hay bˇa´c cˆa`u. . 9. V´oi ´anhxa. f : S → T ta d¯i.nh ngh˜ıaquan hˆe. Rf := {(x, y) ∈ S ì T |y = f(x)}. . X´etc´ac´anhxa. f, g : {1, 2, 3, 4} → {1, 2, 3, 4} x´acd¯i.nh bo˙’ i f(m) := max{2, 4 − m} v`a g(m) := 5 − m. . . . . (a) T`ımc´acma trˆa.n Boole Af ,Ag cu˙’a c´acquan hˆe. Rf v`a Rg tuong ´ung v´oi c´ac´anh xa. f, g. (b) T`ımc´acma trˆa.n Boole cu˙’a Rf ,Rg, v`a Rf◦g v`aso s´anh. −1 −1 . . . . (c) T`ımc´acma trˆa.n Boole cu˙’a Rf ,Rg . C´acquan hˆe. n`aytuong ´ung v´oi c´ac´anhxa. n`ao? . 10. Kha˙’o s´atc´acquan hˆe. R1 v`a R2 trˆentˆa.p S. Ch´ung minh hoˇa.c cho pha˙’n v´ıdu. : (a) Nˆe´u R1 v`a R2 pha˙’n xa. th`ı R1R2 pha˙’n xa . . (b) Nˆe´u R1 v`a R2 d¯ˆo´i x´ung th`ı R1R2 d¯ˆo´i x´ung. (c) Nˆe´u R1 v`a R2 bˇa´c cˆa`u th`ı R1R2 bˇa´c cˆa`u. . 11. Gia˙’ su˙’ R1,R2 l`ac´acquan hˆe. hai ngˆoitrˆentˆa.p S. . (a) Ch´ung minh rˇa`ng R1 ∩ R2 l`apha˙’n xa. nˆe´u R1 v`a R2 l`apha˙’n xa . . . (b) Ch´ung minh rˇa`ng R1 ∩ R2 l`ad¯ˆo´i x´ung nˆe´u R1 v`a R2 l`ad¯ˆo´i x´ung. . (c) Ch´ung minh rˇa`ng R1 ∩ R2 l`abˇa´c cˆa`u nˆe´u R1 v`a R2 l`abˇa´c cˆa`u. . 12. Gia˙’ su˙’ R1,R2 l`ac´acquan hˆe. hai ngˆoitrˆentˆa.p S. (a) R1 ∪ R2 l`apha˙’n xa. nˆe´u R1 v`a R2 l`apha˙’n xa.? . . (b) R1 ∪ R2 l`ad¯ˆo´i x´ung nˆe´u R1 v`a R2 l`ad¯ˆo´i x´ung? (c) R1 ∪ R2 l`abˇa´c cˆa`u nˆe´u R1 v`a R2 l`abˇa´c cˆa`u? 53
53. . . . 13. Gia˙’ su˙’ R l`aquan hˆe. t`u S := {1, 2, 3, 4} lˆen T := {a, b, c} v´oi ma trˆa.n Boole a b c   1 1 0 1 2 0 0 1  A :=  . 3 1 0 0  4 0 1 0 . −1 . (a) Ch´ung minh rˇa`ng RR l`aquan hˆe. d¯ˆo´i x´ung trˆen S. . −1 . (b) Ch´ung minh rˇa`ng R R l`aquan hˆe. d¯ˆo´i x´ung trˆen S. (c) C´acquan hˆe. RR−1,R−1R l`apha˙’n xa.? Bˇa´c cˆa`u? . . 14. Gia˙’ su˙’ R l`aquan hˆe. t`u S lˆen T. . −1 . . (a) Ch´ung minh rˇa`ng RR l`aquan hˆe. d¯ˆo´i x´ung trˆen S. (Khˆongsu˙’ du. ng ma trˆa.n . Boole do S hoˇa.c T c´othˆe˙’ khˆongh˜uu ha.n). (b) Suy ra R−1R l`ad¯ˆo´i x´u.ng trˆen T. (c) Khi n`aoth`ı RR−1 l`apha˙’n xa.? . . . 15. Gia˙’ su˙’ R1 l`aquan hˆe. t`u S lˆen T,R2 l`aquan hˆe. t`u T lˆen U, trong d¯´o S, T, U l`ac´ac . . tˆa.p h˜uu ha.n. D`ungma trˆa.n Boole, ch´ung minh rˇa`ng −1 −1 −1 (R1R2) = R2 R1 . . . . . . 16. Gia˙’ su˙’ R1,R2 l`ac´acquan hˆe. t`u S := {1, 2, . . . , m} lˆen T := {1, 2, . . . , n}, tuong ´ung . . v´oi c´acma trˆa.n A1,A2. Ch´ung minh rˇa`ng R1 ⊆ R2 nˆe´u v`achı˙’ nˆe´u A1 ≤ A2. . . . 17. Su˙’ du. ng t´ınhkˆe´t ho. p cu˙’a c´acquan hˆe., ch´ung minh rˇa`ng t´ıch Boole l`amˆo.t ph´epto´an . c´ot´ınhkˆe´t ho. p. . . . . . −1 18. Gia˙’ su˙’ S l`atˆa.p, khi d¯´o P(S ì S) l`amˆo.t nh´omv´oi phˆa`n tu˙’ nguo. c R ? Gia˙’i th´ıch. . ∗ n . . 19. Gia˙’ su˙’ R l`aquan hˆe. trˆen S v`a R := ∪n≥0R l`a bao d¯´ongtruyˆe` n ´ung cu˙’a R. Ch´ung . . 0 0 minh rˇa`ng R l`apha˙’n xa. v`abˇa´c cˆa`u. Hon n˜ua, nˆe´u R ⊂ R , trong d¯´o R l`abˇa´c cˆa`u v`a d¯ˆo´i x´u.ng, th`ı R∗ ⊂ S. . . 2.3 Quan hˆe. th´u tu. . . . . . D- .inh ngh˜ıa2.3.1 Quan hˆe. hai ngˆoi R trˆentˆa.p S d¯uo. c go.i l`a quan hˆe. th´u tu. (hay r˜ohon, . . . quan hˆe. th´u tu. bˆo. phˆa. n) nˆe´u n´oc´oc´act´ınhchˆa´t: pha˙’n xa., pha˙’n d¯ˆo´i x´ung v`abˇa´c cˆa`u. Khi . . . . . . d¯´othay cho c´ach viˆe´t aRb, ngu`oi ta thu`ong viˆe´t a ≤ b hoˇa.c b ≥ a v`an´oirˇa`ng a d¯itru´oc b, . hoˇa.c b d¯isau a. Nhu vˆa.y . (a) a ≤ a v´oi mo.i a ∈ S. 54
54. (b) Nˆe´u a ≤ b v`a b ≤ a th`ı a = b. (c) Nˆe´u a ≤ b v`a b ≤ c th`ı a ≤ c. . . . . Nˆe´u a ≤ b v`a a 6= b ta k´yhiˆe.u a a v`an´oirˇa`ng a thu. c su. d¯itru´oc b hoˇa.c b . . thu. c su. d¯isau a. . . . . . K´ıhiˆe.u (S, ≤) c´ongh˜ıa ≤ l`aquan hˆe. th´u tu. trˆentˆa.p S; v`a(S, ≤) d¯uo. c go.i l`atˆa.p c´o th´u . tu. bˆo. phˆa. n. . . Nhˆa.n x´etrˇa`ng v´oi hai phˆa`n tu˙’ a, b ∈ S th`ıkhˆongnhˆa´t thiˆe´t pha˙’i c´o a ≤ b hoˇa.c b ≤ a. . . . . Nˆe´u hoˇa.c a ≤ b hoˇa.c b ≤ a th`ıc´acphˆa`n tu˙’ a v`a b go.i l`a so s´anhd¯uo. c v´oi nhau. Nˆe´u A ⊂ S . . . . v`ahai phˆa`n tu˙’ bˆa´t k`ycu˙’a A l`aso s´anhd¯uo. c v´oi nhau th`ı A go.i l`a tˆa. p con sˇa´p thˇa˙’ng cu˙’a S. . . . V´ıdu. 2.3.1 X´ettru`ong sˆo´ ph´uc C v`aquan hˆe. x ≤ y, trong d¯´o x = a + ib v`a y = c + id, i = √ . . −1, nˆe´u a ≤ c v`a b ≤ d. Hiˆe˙’n nhiˆen ≤ l`aquan hˆe. th´u tu. .D- ˇa.t A := {x ∈ C | x = a + i0, a ∈ R}. . . V´oi quan hˆe. ≤ tˆa.p A l`atˆa.p con sˇa´p thˇa˙’ng cu˙’a C. Ta c´o2 + i3 < 2 + i5. Nhung 2 + i3 khˆong . . . so s´anhd¯uo. c v´oi 1 + i5. . . D- .inh ngh˜ıa2.3.2 (a) X´etquan hˆe. th´u tu. ≤ trˆentˆa.p S. Ta n´oirˇa`ng t phu˙’ s nˆe´u s < t v`a khˆongtˆo`n ta.i u ∈ S sao cho s < u < t. . . . . . (b) Luo. c d¯ˆo` Hasse cu˙’a (S, ≤) l`amˆo.t d¯ˆo` thi. c´ohu´ong gˆo`m c´acd¯ı˙’nh l`ac´acphˆa`n tu˙’ cu˙’a S . v`anˆe´u t phu˙’ s th`ıc´omˆo.t cung nˆo´i t`u s d¯ˆe´n t. V´ıdu. 2.3.2 (a) D- ˇa.t S := {1, 2, 3, 4, 5, 6}. Ta viˆe´t m|n nˆe´u n l`abˆo.i nguyˆencu˙’a m. Khi d¯´o . . . . . . (S, |) l`atˆa.p d¯uo. c sˇa´p th´u tu. bˆo. phˆa.n. Ta c´oluo. c d¯ˆo` Hasse trong H`ınh2.2. 4 6 • • • • 3 2 • • 5 1 H`ınh2.2: . . . . (b) Trˆen S := P({a, b, c}) x´etquan hˆe. bao h`am ⊂ . Khi d¯´o(S, ⊂) l`atˆa.p d¯uo. c sˇa´p th´u tu. . . bˆo. phˆa.n v`ac´oluo. c d¯ˆo` Hasse trong H`ınh2.3. 55
55. {a, b, c} . . . . . . . . . . {a, c} . . {a, b}{ . . b, c} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . {a} . {c} . . . . {b} . . . . . . . . . . {∅} H`ınh2.3: e d c . . ••• . . . . . . . . . . . . . . . . . . . . . . . . . . . . . •• a b H`ınh2.4: . . . . (c) Luo. c d¯ˆo` trong H`ınh2.5 khˆongpha˙’i l`aluo. c d¯ˆo` Hasse (ta.i sao?): . . . . . . . . (d) C´acluo. c d¯ˆo` trong H`ınh ?? l`aluo. c d¯ˆo` Hasse cu˙’a c´actˆa.p d¯uo. c sˇa´p th´u tu. bˆo. phˆa.n . . . . (d¯uo. c suy tru. c tiˆe´p t`u biˆe˙’u d¯ˆo`). •. • • . . . . . •. . . . . . •• •• •. . . . . . • . . . • •• .• H`ınh2.5: . . . . . . . N´oichung v´oi luo. c d¯ˆo` Hasse cu˙’a tˆa.p d¯uo. c sˇa´p th´u tu. bˆo. phˆa.n, ta c´o s ≤ t nˆe´u v`achı˙’ nˆe´u . . . . . hoˇa.c s = t hoˇa.c c´omˆo.t d¯u`ong d¯id¯i.nh hu´ong t`u s d¯ˆe´n t. . . . . . Gia˙’ su˙’ (S, ≤) l`atˆa.p d¯uo. c sˇa´p th´u tu. bˆo. phˆa.n v`a A ⊂ S, A 6= ∅. . . . . D- .inh ngh˜ıa2.3.3 (a) Phˆa`n tu˙’ x ∈ S d¯uo. c go.i l`a cˆa. n trˆen cu˙’a A nˆe´u a ≤ x v´oi mo.i a ∈ A; 56
56. . . . . khi d¯´o A d¯uo. c go.i l`a bi. chˇa. n trˆen. Nˆe´u x l`acˆa.n trˆencu˙’a A v`a x ∈ A th`ı x d¯uo. c go.i l`a phˆa`n . . tu˙’ l´on nhˆa´t cu˙’a A, k´yhiˆe.u max A := max{a | a ∈ A}. . . . . . . . . (b) Phˆa`n tu˙’ y ∈ S d¯uo. c go.i l`a cˆa. n du´oi cu˙’a A nˆe´u y ≤ a v´oi mo.i a ∈ A; khi d¯´o A d¯uo. c go.i . . . . . . . l`a bi. chˇa. n du´oi. Nˆe´u y l`acˆa.n du´oi cu˙’a A v`a y ∈ A th`ı y d¯uo. c go.i l`a phˆa`n tu˙’ nho˙’ nhˆa´t cu˙’a A, k´yhiˆe.u min A := min{a | a ∈ A}. s . s . (c) K´yhiˆe.u A l`atˆa.p ho. p tˆa´t ca˙’ c´accˆa.n trˆencu˙’a A. Nˆe´u A =6 ∅ (t´uc l`anˆe´u A bi. chˇa.n s . ∗ ∗ . . trˆen)v`anˆe´u A c´ophˆa`n tu˙’ nho˙’ nhˆa´t x th`ı x d¯uo. c go.i l`a cˆa. n trˆennho˙’ nhˆa´t hoˇa.c cˆa. n trˆen d¯´ung cu˙’a A, k´yhiˆe.u sup A := sup{a | a ∈ A}. i . . . i . (d) K´yhiˆe.u A l`atˆa.p ho. p tˆa´t ca˙’ c´accˆa.n du´oi cu˙’a A. Nˆe´u A 6= ∅ (t´uc l`anˆe´u A bi. chˇa.n . . i . . ∗ ∗ . . . . . . . du´oi) v`anˆe´u A c´ophˆa`n tu˙’ l´on nhˆa´t y th`ı y d¯uo. c go.i l`a cˆa. n du´oi l´on nhˆa´t hoˇa.c cˆa. n du´oi d¯´ung cu˙’a A, k´yhiˆe.u inf A := inf{a | a ∈ A}. . . . . V´ıdu. 2.3.3 X´ettˆa.p d¯uo. c sˇa´p th´u tu. bˆo. phˆa.n trong V´ıdu. 2.3.2(a). Tˆa.p S khˆongc´ophˆa`n tu˙’. l´o.n nhˆa´t; 1 l`aphˆa`n tu˙’. nho˙’ nhˆa´t. . . Nhˆa.n x´et4 (a) Phˆa`n tu˙’ l´on nhˆa´t (nho˙’ nhˆa´t) cu˙’a A, nˆe´u tˆo`n ta.i, l`aduy nhˆa´t. . . . . . . (b) Nˆe´u tˆo`n ta.i x = max A (tuong ´ung y = min A) th`ı x = sup A (tuong ´ung y = inf A). . . D- iˆe` u nguo. c la.i khˆongd¯´ung(cho v´ıdu. ). . . . . V´ıdu. 2.3.4 (a) Trong tˆa.p d¯uo. c sˇa´p th´u tu. bˆo. phˆa.n ({1, 2, 3, 4, 5, 6}, |) tˆa.p con {2, 3} c´o . . . d¯´ungmˆo.t cˆa.n trˆenl`a6, v`ado d¯´osup{2, 3} = 6. Tuong tu. inf{2, 3} = 1. Tˆa.p con {4, 6} . . khˆongc´ocˆa.n trˆen;inf{4, 6} = 2. Tˆa.p con {3, 6} c´ocˆa.n trˆen6 v`ahai cˆa.n du´oi l`a1 v`a3; . . . do d¯´osup{3, 6} = 6 v`ainf{3, 6} = 3. Vˆa.y c´accˆa.n trˆend¯´ungv`acˆa.n du´oi d¯´ungcu˙’a A chua . chˇa´c tˆo`n ta.i, v`anˆe´u ch´ungtˆo`n ta.i chua chˇa´c ch´ungthuˆo.c tˆa.p con A. . . . . . . (b) X´ettˆa.p con d¯uo. c sˇa´p th´u tu. bˆo. phˆa.n c´oluo. c d¯ˆo` Hasse trong H`ınh 2.6. Ta c´o . sup{d, f} = h v`ainf{b, d, e, f} = a. Nhung inf{b, c} v`asup{d, e, f} khˆongtˆo`n ta.i. g h ••. . . . . . . . . e c . . ••• d . . . . . . . . ••• b a f H`ınh2.6: 57
57. . . . . . . D- .inh ngh˜ıa2.3.4 Tˆa.p d¯uo. c sˇa´p th´u tu. bˆo. phˆa.n (S, ≤) d¯uo. c go.i l`a lattice (d`an)nˆe´u tˆo`n . ta.i sup{x, y} v`ainf{x, y} v´oi mo.i x, y ∈ S. Khi d¯´ota d¯i.nh ngh˜ıahai ph´epto´an x ∨ y := sup{x, y}, x ∧ y := inf{x, y}. Hiˆe˙’n nhiˆen ∨ v`a ∧ l`ac´acph´epto´anhai ngˆoitrˆen S. Ho.n n˜u.a x ∧ y = x ⇔ x ≤ y ⇔ x ∨ y = y. . . . Bˇa`ng quy na.p, ch´ungta c´othˆe˙’ ch´ung minh mo.i tˆa.p con h˜uu ha.n phˆa`n tu˙’ A cu˙’a lattice L luˆontˆo`n ta.i sup A, inf A. . . . . V´ıdu. 2.3.5 (a) Tˆa.p d¯uo. c sˇa´p th´u tu. trong V´ıdu. 2.3.2(b) l`alattice. . . . . (b) Tˆa.p d¯uo. c sˇa´p th´u tu. trong V´ıdu. 2.3.2(a) khˆongl`alattice do tˆa.p {3, 4} khˆongc´ocˆa.n trˆentrong S. . C´acd¯i.nh ngh˜ıacu˙’a ∧ v`a ∨ chı˙’ ra c´acd¯ˇa˙’ng th´uc sau: x ∧ x = x, x ∨ x = x, x ∧ y = y ∧ x, x ∨ y = y ∨ x, (x ∧ y) ∧ z = x ∧ (y ∧ z), (x ∨ y) ∨ z = x ∨ (y ∨ z). B`aitˆa.p . . . . . . 1. V˜eluo. c d¯ˆo` Hasse cu˙’a c´actˆa.p d¯uo. c sˇa´p th´u tu. bˆo. phˆa.n sau: (a) ({1, 2, 3, 4, 6, 8, 12, 24}, |), trong d¯´o m|n ngh˜ıal`a n chia hˆe´t cho m. . (b) Tˆa.p c´actˆa.p con cu˙’a {3, 7} v´oi quan hˆe. ⊆ . . . . . . . 2. T`ımc´actˆa.p con thu. c su. cu. c d¯a.i cu˙’a tˆa.p {a, b, c}. T´uc l`at`ımc´acphˆa`n tu˙’ cu. c d¯a.i . . . . . . . cu˙’a tˆa.p con d¯uo. c sˇa´p th´u tu. bˆo. phˆa.n cu˙’a P({a, b, c}) l`anh˜ung tˆa.p con thu. c su. cu˙’a {a, b, c}. . 3. Trˆen R ì R x´etc´acquan hˆe. <, ≺, ạ x´acd¯i.nh bo˙’ i (x, y) < (z, w) nˆe´u x2 + y2 < z2 + w2, (x, y) ≺ (z, w) nˆe´u (x, y) < (z, w) hoˇa.c (x, y) = (z, w), (x, y) ạ (z, w) nˆe´u x2 + y2 ≤ z2 + w2. . . (a) Quan hˆe. n`aol`aquan hˆe. th´u tu. bˆo. phˆa.n? (b) V˜emˆo.t phˆa`n cu˙’a {(x, y) | (x, y) ≺ (3, 4)} trong R2. (c) V˜emˆo.t phˆa`n cu˙’a {(x, y) | (x, y) ạ (3, 4)} trong R2. 58