›
›

Giáo trình Toán ứng dụng trong tin học - Trường Sơn

pdf 30 trang phuongnguyen 4120
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Toán ứng dụng trong tin học - Trường Sơn", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfgiao_trinh_toan_ung_dung_trong_tin_hoc_truong_son.pdf

Nội dung text: Giáo trình Toán ứng dụng trong tin học - Trường Sơn

  1. GIÁO TRÌNH TOÁN ỨNG DỤNG TRONG TIN HỌC Biên Soạn: Trường Sơn 
  2. Chöông 1 – Logic meänh ñeà Toaùn öùng duïng trong Tin hoïc CHÖÔNG 1 LOGIC MEÄNH ÑEÀ I- MEÄNH ÑEÀ I.1- Khaùi nieäm: • Meänh ñeà laø moät caâu khaúng ñònh ñuùng hoaëc moät caâu khaúng ñònh sai. • Caâu khaúng ñònh ñuùng goïi laø meänh ñeà ñuùng (meänh ñeà coù chaân trò ñuùng). • Caâu khaúng ñònh sai goïi laø meänh ñeà sai (meänh ñeà coù chaân trò sai). • Kí hieäu caùc meänh ñeà: P, Q, R, . • Kí hieäu chaân trò ñuùng laø 1 (hay T – True), chaân trò sai laø 0 (hay F – False) Ví duï 1: a/ Haø Noäi laø thuû ñoâ cuûa nöôùc Vieät Nam. Laø meänh ñeà ñuùng (1). Kí hieäu mñ: P b/ Thöôïng Haûi laø thuû ñoâ cuûa AÁn Ñoä. Laø meänh ñeà sai (0). Kí hieäu mñ: Q c/ 5 + 5 = 10 Laø meänh ñeà ñuùng (1). Kí hieäu mñ: R d/ 43 chia heát cho 5 Laø meänh ñeà sai (0). Kí hieäu mñ: T e/ Hoâm nay trôøi ñeïp quaù ! Khoâng phaûi laø meänh ñeà. Caâu caûm thaùn. f/ Hoâm nay trôøi coù ñeïp khoâng? Khoâng phaûi laø meänh ñeà. Caâu hoûi nghi vaán. g/ Haõy hoïc baøi ñi! Khoâng phaûi laø meänh ñeà. Caâu meänh leänh. h/ n laø moät soá nguyeân toá Khoâng phaûi laø meänh ñeà. Laø vò töø (meänh ñeà chöùa bieán).Neáu n=3 ta ñöôïc meänh ñeà ñuùng, n= 4 ta ñöôïc meänh ñeà sai. * Bieán meänh ñeà: p goïi laø bieán meänh ñeà neáu noù nhaän giaù trò laø moät meänh ñeà naøo ñoù. Ví duï 2: p laø bieán meänh ñeà coù theå nhaän giaù trò laø caùc meänh ñeà P, Q, R, T ôû treân. I.2- Caùc pheùp toaùn loâgic: I.2.1: Pheùp phuû ñònh (NOT): Phuû ñònh cuûa meänh ñeà P kí hieäu laø P . Chaân trò cuûa P laø 0 neáu P P chaân trò cuûa P laø 1 vaø ngöôïc laïi. 0 1 Baûng chaân trò cuûa pheùp phuû ñònh: 1 0 Ví duï 3: meänh ñeà P: “ 2 laø soá höõu tæ” P : “ 2 khoâng phaûi laø soá höõu tæ” ( 2 laø soá voâ tæ) I.2.2 Pheùp hoäi (AND): Pheùp hoäi cuûa hai meänh ñeà P, Q kí hieäu laø P∧Q (ñoïc laø P vaø Q) chæ ñuùng khi caû P vaø Q cuøng ñuùng. Baûng chaân trò cuûa pheùp hoäi: P Q P∧Q 0 0 0 0 1 0 1 0 0 1 1 1 Ví duï 4: + “Chieàu nay trôøi ñeïp vaø traän boùng ñaù seõ haáp daãn”: P∧Q + “Danh saùch sinh vieân nam vaø tuoåi töø 20 trôû leân”: P∧Q Ñieàu kieän loïc danh saùch laø: (PHAI=”Nam”) AND (Year(Date())-Year(NgaySinh)>=20) Bieân soaïn: Tröôøng Sôn 1
  3. Chöông 1 – Logic meänh ñeà Toaùn öùng duïng trong Tin hoïc + “Danh saùch sinh vieân nöõ coù queâ ôû Long An”: P∧Q Ñieàu kieän loïc danh saùch laø: (PHAI=”Nöõ”) AND (QUEQUAN=”Long An”) I.2.3 Pheùp tuyeån (OR): Pheùp tuyeån cuûa hai meänh ñeà P, Q kí hieäu laø P∨Q (ñoïc laø P hoaëc Q) chæ sai khi caû P vaø Q cuøng sai. Baûng chaân trò cuûa pheùp tuyeån: P Q P∨Q 0 0 0 0 1 1 1 0 1 1 1 1 Ví duï 5: + “Danh saùch sinh vieân queâ ôû Caàn Thô hoaëc/hay/vaø Long An”: P∨Q Ñieàu kieän loïc danh saùch laø: (QUEQUAN=”Caàn Thô”) OR (QUEQUAN=”Long An”) I.2.4 Pheùp tuyeån loaïi (XOR): Pheùp tuyeån loaïi cuûa hai meänh ñeà P, Q kí hieäu laø P ∨ Q (ñoïc laø hoaëc P hoaëc Q) chæ ñuùng khi chæ moät trong 2 meänh ñeà laø ñuùng. Baûng chaân trò cuûa pheùp tuyeån loaïi: P Q P ∨ Q 0 0 0 0 1 1 1 0 1 1 1 0 Ví duï 6: + “Sinh vieân An queâ ôû Caàn Thô hoaëc Long An”: P ∨ Q + “ 2 laø soá höõu tæ hoaëc laø soá voâ tæ”: P ∨ Q + “5 giôø chieàu nay Minh ñi hoïc theâm Anh vaên hoaëc ñi döï ñaùm cöôùi baïn Lan”: P ∨ Q I.2.5 Pheùp keùo theo: Pheùp keùo theo cuûa hai meänh ñeà P, Q kí hieäu laø P ⇒ Q laø moät meänh ñeà chæ sai khi P ñuùng Q sai. Baûng chaân trò cuûa pheùp keùo theo: P Q P ⇒ Q 0 0 1 0 1 1 1 0 0 1 1 1 Ví duï 7: + “Neáu An vöôït ñeøn ñoû thì An seõ vi phaïm luaät giao thoâng”: P ⇒ Q + “Vì 50 chia heát cho 10 neân 50 chia heát cho 5” (P ñuùng, Q ñuùng: meänh ñeà ñuùng) + “202 laø soá chaün suy ra 202 chia heát cho 4” (P ñuùng, Q sai: meänh ñeà sai) Löu yù: • P goïi laø ñieàu kieän ñuû ñeå coù Q, hoaëc Q goïi laø ñieàu kieän caàn ñeå coù P • Q ⇒ P goïi laø meänh ñeà ñaûo cuûa meänh ñeà P ⇒ Q 2 Bieân soaïn: Tröôøng Sôn
  4. Chöông 1 – Logic meänh ñeà Toaùn öùng duïng trong Tin hoïc I.2.6 Pheùp töông ñöông: Pheùp töông ñöông cuûa hai meänh ñeà P, Q kí hieäu laø P ⇔ Q laø moät meänh ñeà chæ ñuùng khi caû P vaø Q cuøng ñuùng hoaëc cuøng sai. Baûng chaân trò cuûa pheùp keùo theo: P Q P ⇔ Q 0 0 1 0 1 0 1 0 0 1 1 1 Ví duï 8: + “Tam giaùc ABC coù ba goùc baèng nhau neáu vaø chæ neáu tam giaùc ñoù coù ba caïnh baèng nhau” + “36 chia heát cho 4 vaø chia heát cho 3 khi vaø chæ khi 36 chia heát cho12” + P: “Töù giaùc ABCD laø hình vuoâng” Q: “Töù giaùc ABCD laø hình chöõ nhaät coù hai ñöôøng cheùo vuoâng goùc” Ta coù P ⇔ Q I.3 Pheùp toaùn bit (NOT, AND, OR, XOR: thöïc hieän trong maùy tính) • Bit laø ñôn vò thoâng tin nhoû nhaát öùng vôùi moät trong hai kí soá nhò phaân 0 hoaëc 1. • Chuoãi bit laø chuoãi goàm caùc kí soá 0, 1. Cho 2 chuoãi 4 bit A = 0011; B = 0101. Ta thöïc hieän caùc pheùp toaùn bít nhö sau: A 0 0 1 1 B 0 1 0 1 NOT A 1 1 0 0 A AND B 0 0 0 1 A OR B 0 1 1 1 A XOR B 0 1 1 0 II- COÂNG THÖÙC MEÄNH ÑEÀ II.1 Caùc khaùi nieäm II.1.1 Coâng thöùc meänh ñeà (bieåu thöùc loâgic) Coâng thöùc meänh ñeà (coøn goïi laø bieåu thöùc loâgic) laø moät bieåu thöùc ñöôïc xaây döïng töø: • Caùc meänh ñeà P, Q, R, . • Caùc bieán meänh ñeà p, q, r, coù theå nhaän giaù trò laø caùc meänh ñeà. • Caùc pheùp toaùn treân caùc meänh ñeà vaø bieán meänh ñeà theo moät traät töï naøo ñoù. Ví duï 9: A = (p ∧q) ∨ ( r ⇒ q) E = p ∨ (q ∧ r) F = (p ∨ q) ∧ r Nhaän xeùt: Laäp baûng chaân trò cuûa E vaø F ta thaáy E ≠ F, suy ra thöù töï thöïc hieän pheùp toaùn logic laø raát quan troïng. II.1.2 Coâng thöùc töông ñöông Hai coâng thöùc E vaø F goïi laø töông ñöông logic neáu chuùng coù cuøng baûng chaân trò. Kí hieäu hai coâng thöùc töông ñöông logic laø E ≡ F hay ñôn giaûn laø E = F. Ví duï 10: E = p ⇒⇒⇒ q vaø F = p ∨∨∨ q laø hai coâng thöùc töông ñöông (c/m baèng baûng chaân trò) Bieân soaïn: Tröôøng Sôn 3
  5. Chöông 1 – Logic meänh ñeà Toaùn öùng duïng trong Tin hoïc p q p p ⇒⇒⇒ q p ∨∨∨ q (p ⇒⇒⇒ q) ⇔ ( p ∨∨∨ q) 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 0 1 1 1 (E) (F) (G) II.1.3 Coâng thöùc meänh ñeà haèng ñuùng, haèng sai Coâng thöùc meänh ñeà goïi laø coâng thöùc haèng ñuùng neáu noù luoân nhaän gía trò 1 (E ≡ 1). Coâng thöùc meänh ñeà goïi laø coâng thöùc haèng sai neáu noù luoân nhaän gía trò 0 (E ≡ 0). Ví duï 11: G = (p ⇒⇒⇒ q) ⇔ ( p ∨∨∨ q) laø coâng thöùc haèng ñuùng; G ≡ 1 (suy ra töø ví duï 9). II.1.4 Qui taéc thay theá: Qui taéc 1: Neáu trong coâng thöùc meänh ñeà E ta thay theá moät bieåu thöùc con bôûi moät coâng thöùc meänh ñeà töông ñöông thì ñöôïc moät coâng thöùc meänh ñeà môùi töông ñöông logic vôùi E. Ví duï 12: p ⇒⇒⇒ (q ⇒⇒⇒ r) ≡ p ⇒⇒⇒ ( q ∨∨∨ r) ≡ p ∨∨∨ q ∨∨∨ r Qui taéc 2: Neáu E laø coâng thöùc meänh ñeà haèng ñuùng thì khi ta thay bieán meänh ñeà p trong E bôûi moät coâng thöùc meänh ñeà tuøy yù thì ñöôïc moät coâng thöùc meänh ñeà môùi vaãn laø haèng ñuùng. Ví duï 13: G = (p ⇒⇒⇒ q) ⇔ ( p ∨∨∨ q) ≡ 1 (suy ra töø ví duï 10) suy ra G’ = ((r ∧∧∧ t) ⇒⇒⇒ q) ⇔ (( r ∧ t ) ∨∨∨ q) ≡ 1 II.2 Caùc qui luaät logic Vôùi p, q, r laø caùc bieán meänh ñeà, 1 laø haèng ñuùng, 0 laø haèng sai ta coù caùc töông ñöông logic sau: 1/ Phuû ñònh cuûa phuû ñònh: P ≡ p 2/ Qui taéc De Morgan: ( p ∧ q) ≡ p ∨ q ; ( p ∨ q) ≡ p ∧ q 3/ Luaät giao hoaùn: p ∧ q ≡ q ∧ p ; p ∨ q ≡ q ∨ p 4/ Luaät keát hôïp: p ∧ (q ∧ r) ≡ (p ∧ q) ∧ r ; p ∨ (q ∨ r) ≡ (p ∨ q) ∨ r 5/ Luaät phaân phoái: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p∧ r) ; p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p∨ r) 6/ Luaät luõy ñaúng: p ∧ p ≡ p ; p ∨ p ≡ p 7/ Luaät trung hoøa (luaät ñoàng nhaát): p ∧ 1 ≡ p ; p ∨ 0 ≡ p 8/ Luaät veà phaàn töû buø: p ∧ p ≡ 0 (Luaät baøi trung) P ∨ p ≡ 1 (Luaät maâu thuaãn) 9/ Luaät thoáng trò: p ∧ 0 ≡ 0 ; p ∨ 1 ≡ 1 10/ Luaät haáp thuï: p ∧ (p ∨ q) ≡ p ; p ∨ (p ∧ q) ≡ p * Chöùng minh caùc coâng thöùc treân baèng caùch laäp baûng chaân trò. Chaúng haïn ta chöùng minh luaät haáp thuï 10/ baèng baûng sau: p q p ∨ q p ∧ q p ∧ (p ∨ q) p ∨ (p ∧ q) 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 1 1 1 1 1 1 1 1 4 Bieân soaïn: Tröôøng Sôn
  6. Chöông 1 – Logic meänh ñeà Toaùn öùng duïng trong Tin hoïc III - QUI TAÉC SUY LUAÄN III.1 - Khaùi nieäm: Trong caùc chöùng minh toaùn hoïc, ta thöôøng xuaát phaùt töø tieàn ñeà laø caùc khaúng ñònh ñuùng p1, p2, . . . , pn vaø aùp caùc qui taéc suy luaän toaùn hoïc ñeå khaúng ñònh keát luaän q laø ñuùng. Coâng thöùc toång quaùt cuûa qui taéc suy luaän laø: (p1 ∧∧∧ p2 ∧∧∧ . . . ∧∧∧ pn) ⇒⇒⇒ q Hay vieát theo moâ hình laø: p1 p2 . Tieàn ñeà . . pn q Keát luaän III.2 - Caùc qui taéc suy luaän thöôøng duøng: III.2.1 – Qui taéc khaúng ñònh (Modus Ponens) Qui taéc naøy ñöôïc theå hieän bôûi coâng thöùc haèng ñuùng (c/m baèng caùch laäp baûng chaân trò): (( p ⇒⇒⇒ q) ∧∧∧ p) ⇒⇒⇒ q hay döôùi daïng sô ñoà p ⇒ q p q Ví duï 14: a/ Tam giaùc caân coù hai caïnh baèng nhau. (p ⇒ q) Tam giaùc ABC caân taïi A (p) KL: AB = AC (q) b/ Moïi soá chaün ñeàu chia heát cho 2 maø 2006 laø moät soá chaün. Suy ra soá 2006 chia heát cho 2. c/ Neáu hoïc gioûi seõ ñöôïc thöôûng maø Lan ñaït loaïi gioûi. Vaäy Lan seõ ñöôïc thöôûng. III.2.2 – Qui taéc tam ñoaïn luaän (Modus Syllogism) / Chöùng minh baéc caàu Qui taéc naøy ñöôïc theå hieän bôûi coâng thöùc haèng ñuùng (c/m baèng caùch laäp baûng chaân trò): (( p ⇒⇒⇒ q) ∧∧∧ ( q ⇒⇒⇒ r)) ⇒⇒⇒ (p ⇒⇒⇒ r) hay döôùi daïng sô ñoà p ⇒ q q ⇒ r p ⇒ r Ví duï 15: a/ Bình chôi Game Online thì Bình khoâng hoïc Toaùn öùng duïng. Bình khoâng hoïc Toaùn öùng duïng thì Bình thi rôùt Toaùn öùng duïng. Maø Bình ham chôi Game Online neân Bình thi rôùt Toaùn öùng duïng. Bieân soaïn: Tröôøng Sôn 5
  7. Chöông 1 – Logic meänh ñeà Toaùn öùng duïng trong Tin hoïc b/ 75 chia heát cho 15; 15 chia heát cho 5. Vaäy 75 chia heát cho 5. c/ Moät con ngöïa reû thì hieám. Caùi gì hieám thì ñaét. Suy ra moät con reû thì ñaét (!). Suy luaän treân laø hôïp logic. Nhöng keát luaän sai do döïa treân moät tieàn ñeà sai. III.2.3 – Qui taéc phuû ñònh (Modus Tollens) / Chöùng minh phaûn ñaûo Qui taéc naøy ñöôïc theå hieän bôûi coâng thöùc haèng ñuùng (c/m baèng caùch laäp baûng chaân trò): (( p ⇒⇒⇒ q) ∧∧∧ q ) ⇒⇒⇒ p hay döôùi daïng sô ñoà p ⇒ q q p Ví duï 16: a/ Neáu hoïc gioûi seõ ñöôïc thöôûng maø An khoâng ñöôïc thöôûng. Vaäy An khoâng hoïc gioûi. b/ Hai goùc ñoái ñænh thì baèng nhau. Goùc O1 khaùc goùc O2 neân hai goùc aáy khoâng ñoái ñænh. III.2.4 – Qui taéc tam ñoaïn luaän rôøi/ Chöùng minh loaïi tröø Qui taéc naøy ñöôïc theå hieän bôûi coâng thöùc haèng ñuùng (c/m baèng caùch laäp baûng chaân trò): (( p ∨∨∨ q) ∧∧∧ p ) ⇒⇒⇒ q YÙ nghóa cuûa qui taéc naøy laø khi chæ coù ñuùng hai tröôøng hôïp coù theå xaûy ra vaø moätt tröôøng hôïp ñaõ ñöôïc khaúng ñònh laø sai thì truông hôïp coøn laïi laø ñuùng. Ví duï 17: a/ Saùng nay hai baïn An vaø Bình ñöôïc phaân coâng laøm tröïc nhaät. Nhöng baïn An ñi hoïc treã. Vaäy baïn Bình laøm tröïc nhaät. b/ Tích a.b = 0 (suy ra a = 0 hoaëc b = 0) maø a ≠ 0 Vaäy b = 0. III.2.5 – Qui taéc maâu thuaãn / Chöùng minh phaûn chöùng Qui taéc naøy ñöôïc theå hieän bôûi töông ñöông logic sau: ( p ⇒⇒⇒ q) ≡≡≡ (( p ∧∧∧ q ) ⇒⇒⇒ 0) Do ñoù, neáu chöùng minh ñöôïc coâng thöùc meänh ñeà beân phaûi laø haèng ñuùng thì coâng thöùc beân traùi cuõng laø haèng ñuùng. Nghóa laø neáu ta giaû söû q laø sai vaø cuøng vôùi tieàn ñeà daãn ñeán ñieàu voâ lí thì keát luaän q laø ñuùng. Ñoù laø cô sôû cuûa phöông phaùp chöùng minh phaûn chöùng. Ví duï 18: Chöùng minh raèng 2 laø soá voâ tæ. Giaû söû 2 laø moät soá höõu tæ. Khi ñoù 2 = p/q vôùi p/q laø phaân soá toái giaûn. ⇒ 2 = p2/q2 ⇒ 2q2 =p2 ⇒ p2 ⋮ 2 ⇒ p⋮2 (vì neáu p-leû thì p2 cuõng leû maâu thuaãn vôùi p2 ⋮ 2) ⇒ p = 2k. Suy ra 2q2 = 4k2 ⇒ q2 = 2k2 ⇒ q2 ⋮ 2 ⇒ q⋮2. Do ñoù p, q coù öôùc soá chung laø 2, traùi vôùi giaû thieát p/q laø phaân soá toái giaûn. Vaäy 2 laø moät soá voâ tæ. 6 Bieân soaïn: Tröôøng Sôn
  8. Chöông 1 – Logic meänh ñeà Toaùn öùng duïng trong Tin hoïc IV- VÒ TÖØ - LÖÔÏNG TÖØ IV.1 – Vò töø: Vò töø laø moät khaúng ñònh chöùa bieán daïng P(x) vôùi x∈A sao cho: • P(x) khoâng phaûi laø meänh ñeà. • Cho x= a∈ A thì P(a) laø moät meänh ñeà. Ví duï 18: a/ P(x) = “x < 5” ; x∈ N vôùi N = {0, 1, 2, 3, 4, 5, . . . } P(0) = “ 0 < 5” laø meänh ñeà ñuùng. P(5) = “ 5 < 5” laø meänh ñeà sai. P(1) = “ 1 < 5” laø meänh ñeà ñuùng. P(6) = “ 6 < 5” laø meänh ñeà sai. P(2) = “ 2 < 5” laø meänh ñeà ñuùng. P(7) = “ 7 < 5” laø meänh ñeà sai. P(3) = “ 3 < 5” laø meänh ñeà ñuùng. P(8) = “ 8 < 5” laø meänh ñeà sai. P(4) = “ 4 < 5” laø meänh ñeà ñuùng. b/ P(n) = “n laø soá nguyeân toá” ; n∈ N (Soá nguyeân toá laø soá töï nhieân lôùn hôn 1 vaø chæ coù hai öôùc soá laø 1 vaø chính noù) P(0) = “ 0 laø soá nguyeân toá” : meänh ñeà sai. P(1) = “ 1 laø soá nguyeân toá” : meänh ñeà sai. P(2) = “ 2 laø soá nguyeân toá” : meänh ñeà ñuùng. P(3) = “ 3 laø soá nguyeân toá” : meänh ñeà ñuùng. P(4) = “ 4 laø soá nguyeân toá” : meänh ñeà sai. P(5) = “ 5 laø soá nguyeân toá” : meänh ñeà ñuùng. . . . c/ P(x, y) = “x + y laø soá nguyeân chaün” ; n∈ Z = {0, ±1, ±2, ±3, ±4, ±5, . . . } Ta thaáy P(2, 4) laø meänh ñeà ñuùng, coøn P(5,2) laø meänh ñeà sai, . . . IV.2 - Löôïng töø: • Ñeå chæ moät phaàn töû baát kì thuoäc taäp A ta vieát: ∀∀∀x∈∈∈A (löôïng töø vôùi moïi) • Ñeå chæ ít nhaát moät phaàn töû thuoäc taäp A ta vieát: ∃∃∃x∈∈∈A (löôïng töø toàn taïi) • Ñeå chæ moät phaàn töû duy nhaát thuoäc A ta vieát: ∃∃∃!∃!!!x∈∈∈A (löôïng töø toàn taïi duy nhaát) + Gheùp caùc löôïng töø vôùi vò töø ta ñöôïc caùc meänh ñeà sau: ∀∀∀x∈∈∈A, P(x) ∃∃∃x∈∈∈A, P(x) ∃∃∃!∃!!!x∈∈∈A, P(x) + Phuû ñònh caùc meänh ñeà treân ta ñöôïc caùc meänh ñeà töông logic sau: (∀∀∀x∈∈∈A, P(x)) ≡ ∃∃∃x∈∈∈A, P(x) (∃∃∃x∈∈∈A, P(x)) ≡ ∀∀∀x∈∈∈A, P(x) Ví duï 19: P(n) = “n laø soá nguyeân toá” ; n∈ N (Xem ví duï 18b) • ∀n∈N, P(n) = “Moïi soá töï nhieân n ñeàu laø soá nguyeân toá” : mñ sai. (1) • ∃n∈N, P(n) = “Coù soá töï nhieân n laø soá nguyeân toá” : mñ ñuùng. (2) • ∃!n∈N, P(n) = “Coù duy nhaát 1 soá töï nhieân n laø soá nguyeân toá” : mñ sai. Phuû ñònh cuûa (1) ta ñöôïc: ∃n∈N, P(n) = “Coù soá töï nhieân n khoâng phaûi laø soá nguyeân toá” : mñ ñuùng. Phuû ñònh cuûa (2) ta ñöôïc: ∀n∈N, P(n) = “Moïi soá töï nhieân n khoâng phaûi laø soá nguyeân toá” : mñ sai. Bieân soaïn: Tröôøng Sôn 7
  9. Chöông 1 – Logic meänh ñeà Toaùn öùng duïng trong Tin hoïc V – QUY NAÏP VAØ ÑEÄ QUY V.1 – QUY NAÏP V.1.1 – Nguyeân lí quy naïp: Nguyeân lí quy naïp döïa treân meänh ñeà haèng ñuùng sau ñaây: P(0) ∧∧∧ [∀∀∀n∈∈∈N, P(n) ⇒⇒⇒ P(n+1)] ⇒⇒⇒ ∀∀∀n∈∈∈N, P(n) V.1.2 – Caùc böôùc chöùng minh quy naïp: Nhö vaäy, ñeå chöùng minh meänh ñeà P(n) laø ñuùng ∀∀∀n∈∈∈N ta thöïc hieän caùc böôùc sau: Böôùc 1/ Khaúng ñònh P(0) laø ñuùng. Böôùc 2/ Giaû söû P(n) laø ñuùng suy ra P(n+1) cuõng ñuùng. Böôùc 3/ Keát luaän: P(n) ñuùng ,∀n∈N Löu yù: Nguyeân lyù quy naïp coù theå baét ñaàu töø n0∈ N. Töùc laø P(n) ñuùng ∀n∈N, n ≥ n0. Khi ñoù meänh ñeà P(0) trong böôùc 1 ñöôïc thay bôûi P(n0) Ví duï 20: a/ P(n) : 0 + 1 + 2 + . . . + n = n(n+1)/2 ; ∀n∈N + P(0) ñuùng vì 0 = 0(0+1)/2 + Giaû söû P(n) ñuùng, töùc laø 0 + 1 + 2 + . . . + n = n(n+1)/2 Suy ra 0 + 1 + 2 + . . . + n + (n+1) = n(n+1)/2 + (n+1) = (n+1)(n+2)/2 =(n+1)[(n+1)+1]/2 Suy ra P(n+1) ñuùng. Vaäy, P(n) ñuùng ∀n∈N. b/ Chöùng minh raèng P(n) = n3 + 5n chia heát cho 6, ∀n∈N. + Vôùi P(0) ta coù: 0 ⋮ 6. Suy ra P(0) ñuùng. + Giaû söû P(n) ñuùng, töùc laø n3 + 5n ⋮ 6 Ta xeùt P(n+1): (n+1)3 + 5(n+1) = (n3 + 3n2 + 3n + 1) + 5n + 5 = (n3 + 5n) + 3(n2 + n +2) = (n3 + 5n) + 6(n(n+1)/2 + 1) ⋮ 6 Vaäy (n+1)3 + 5(n+1) ⋮ 6, töùc laø P(n+1) laø ñuùng. + Keát luaän: n3 + 5n ⋮ 6, ∀n∈N. c/ Töông töï, haõy chöùng minh raèng 2n+2 > 2n + 5 ; ∀n∈ N, n ≥ 1. V.2 – Ñeä quy V.2.1 – Ñònh nghóa ñeä quy (ñònh nghóa quy naïp): Ñoâi khi raát khoù ñònh nghóa moät ñoái töôïng moät caùch töôøng minh, nhöng laïi deã daøng ñònh nghóa ñoái töôïng naøy thoâng qua chính noù. Ñònh nghóa nhö vaäy goïi laø ñònh nghóa ñeä quy (hay ñònh nghóa quy naïp). Ví duï 21: a/ Ñònh nghóa taäp hôïp soá töï nhieân N ñeä quy nhö sau: • 0 laø soá töï nhieân • Neáu n laø soá töï nhieân thì n+1 cuõng laø soá töï nhieân. Khi ñoù ta coù: N = {0, 1, 2, 3, 4, 5, . . . } b/ Ñònh nghóa haøm soá f ñeä quy nhö sau: • f(0) = 3 (vôùi n = 0) • f(n) = 2f(n-1) + 3 vôùi n = 1, 2, 3, 8 Bieân soaïn: Tröôøng Sôn
  10. Chöông 1 – Logic meänh ñeà Toaùn öùng duïng trong Tin hoïc Khi ñoù ta coù: f(1) = 2f(0) + 3 = 2 × 3 + 3 = 9 f(2) = 2f(1) + 3 = 2 × 9 + 3 = 21 f(3) = 2f(2) + 3 = 2 × 21 + 3 = 45 f(4) = 2f(3) + 3 = 2 × 45 + 3 = 93 V.2.2 – Thuaät toaùn ñeä quy: Moät thuaät toaùn ñöôïc goïi laø ñeä quy neáu noù giaûi baøi toùan baèng caùch ruùt goïn lieân tieáp baøi toaùn ban ñaàu tôùi chính baøi toaùn aáy nhöng coù döõ lieäu ñaàu vaøo nhoû hôn. Ví duï 22: a/ Tính giaù trò an, vôùi a laø soá thöïc khaùc 0, n laø soá töï nhieân: Ta ñònh nghóa an ñeä quy nhö sau: • Khi n = 0: a0=1 • Khi n > 0: an = a. an-1 Nhö vaäy ñeå tính an ta quy veà caùc tröôøng hôïp coù soá muõ n nhoû hôn cho ñeán khi n = 0 thì döøng. Ta coù thuaät toaùn ñeä quy tính luõy thöøa cuûa a nhö sau (maõ VB): Function LuyThua(a, n) as Double If n = 0 then LuyThua = 1 else LuyThua = a * LuyThua(a, n-1) End If End Function b/ Tính giaù trò n! = 1.2.3. . .(n-1).n = (n-1)! . n neáu n > 0 ; 0! = 1. + Thuû tuïc ñeä quy: Function GiaiThua(n) as Long If n = 0 then GiaiThua = 1 else GiaiThua = n * GiaiThua(n-1) End If End Function + Thuû tuïc laëp (Khoâng ñeä quy): Function GiaiThua(n) as Long T = 1 For i = 1 to n T = T * i Next GiaiThua = T End Function c/ Tính giaù trò: S = 1 + 2 + 3 + . . . + n Duøng caùch tính toång laëp (laëp laïi ñoái vôùi S): S = 0 For i = 1 to n S = S + i Next Bieân soaïn: Tröôøng Sôn 9
  11. Chöông 1 – Logic meänh ñeà Toaùn öùng duïng trong Tin hoïc BAØI TAÄP CHÖÔNG 1 - LOÂGIC MEÄNH ÑEÀ 1.1- Trong caùc caâu sau, cho bieát caâu naøo laø meänh ñeà: a) Traàn Höng Ñaïo laø moät vò töôùng taøi. b) x + 1 laø moät soá nguyeân döông. c) 9 laø moät soá chaün. d) Hoâm nay trôøi ñeïp laøm sao ! e) Haõy hoïc Toaùn öùng duïng. f) Neáu baïn ñeán treã thì toâi seõ ñi xem boùng ñaù tröôùc. 1.2- Goïi P vaø Q laø caùc meänh ñeà: P: "Minh gioûi Toaùn" Q: "Minh yeáu Anh vaên". (Giaû söû:khoâng gioûi laø yeáu, khoâng yeáu laø gioûi) Haõy vieát laïi caùc meänh ñeà sau döôùi daïng hình thöùc trong ñoù söû duïng caùc pheùp toaùn meänh ñeà. a) Minh gioûi toaùn nhöng yeáu Anh vaên. b) Minh yeáu caû Toaùn laãn Anh vaên. c) Minh gioûi Toaùn hay Minh vöøa gioûi Anh vaên vöøa yeáu Toaùn. d) Neáu Minh gioûi Toaùn thì Minh gioûi Anh vaên. e) Minh gioûi Toaùn vaø Anh vaên hay Minh yeáu Toaùn nhöng gioûi Anh vaên. 1.3- Goïi P, Q, R laø caùc meänh ñeà: P: "Bình ñang hoïc Toaùn". Q: "Bình ñang hoïc Tin hoïc". R: "Bình ñang hoïc Anh vaên". Haõy vieát laïi caùc meänh ñeà döôùi ñaây döôùi daïng hình thöùc trong ñoù söû duïng caùc pheùp toaùn. a) Bình ñang hoïc Toaùn vaø Anh vaên nhöng khoâng hoïc Tin hoïc. b) Bình ñang hoïc Toaùn vaø Tin hoïc nhöng khoâng hoïc cuøng moät luùc Tin hoïc vaø Anh vaên. c) Khoâng ñuùng laø Bình ñang hoïc Anh vaên maø khoâng hoïc Toaùn. d) Khoâng ñuùng laø Bình ñang hoïc Anh vaên hay Tin hoïc maø khoâng hoïc Toaùn. e) Bình khoâng hoïc Tin hoïc laãn Anh vaên nhöng ñang hoïc Toaùn. 1.4- Haõy laáy phuû ñònh caùc meänh ñeà sau: a) Ngaøy mai neáu trôøi möa hay trôøi laïnh thì toâi seõ khoâng ra ngoaøi. b) 15 chia heát cho 3 nhöng khoâng chia heát cho 4. c) Hình töù giaùc naøy khoâng phaûi laø hình chöõ nhaät maø cuõng khoâng phaûi laø hình thoi. d) Neáu An khoâng ñi laøm ngaøy mai thì seõ bò ñuoåi vieäc. e) Moïi tam giaùc ñeàu coù caùc goùc baèng 60o. 1.5- Cho bieát chaân trò cuûa caùc meänh ñeà sau: a) π = 2 vaø toång caùc goùc cuûa moät tam giaùc baèng 180o. b) π = 3,1416 keùo theo toång caùc goùc cuûa moät tam giaùc baèng 170o. c) π = 3 keùo theo toång caùc goùc cuûa moät tam giaùc baèng 170o. d) Neáu 2 > 3 thì nöôùc soâi ôû 100oC. e) Neáu 3 < 4 thì 4 < 3. f) Neáu 4 < 3 thì 3 < 4. 10 Bieân soaïn: Tröôøng Sôn
  12. Chöông 1 – Logic meänh ñeà Toaùn öùng duïng trong Tin hoïc 1.6- Giaû söû P vaø Q laø hai meänh ñeà nguyeân thuûy sao cho P →→→ Q sai. Haõy xaùc ñònh chaân trò cuûa caùc meänh ñeà sau: (Kí hieäu ¬P laø phuû ñònh cuûa P) a) P ∧ Q b) ¬ P ∨ Q c) Q → P. 1.7- Goïi P, Q, R laø caùc meänh ñeà sau: P: ABC laø moät tam giaùc caân. Q: ABC laø moät tam giaùc ñeàu. R: Tam giaùc ABC coù 3 goùc baèng nhau. Haõy vieát laïi caùc meänh ñeà sau theo ngoân ngöõ thoâng thöôøng: a) Q → P b) ¬ P → Q c) P ∧ ¬ Q d) R → P 1.8- Coù bao nhieâu caùch ñaët daáu "( )" khaùc nhau vaøo daïng meänh ñeà ¬ p ∨ q ∨ r. Laäp baûng chaân trò cho töøng tröôøng hôïp. 1.9- Laäp baûng chaân trò cho caùc daïng meänh ñeà sau vaø chæ ra caùc haèng ñuùng: a) ¬ p → (p ∨ q) b) ¬ p → (¬ q ∨ r) c) (p ∧ q) → ¬ p d) (p ∨ r) → (r ∨ ¬ p) e) (p → q) ∨ (q → p) f) (p ∨ ¬ q) ∧ (¬ p ∨ q) g) (p → ¬ q) ∨ (q → ¬ p) h) ¬ (¬ p ∧ ¬ q) 1.10- Cho bieát quy luaät logic naøo ñaõ ñöôïc aùp duïng trong moãi böôùc töông ñöông sau: Bieåu thöùc Quy luaät logic a) [(p ∨ q) ∧ (p ∨ ¬ q)] ∨ q Luaät phaân phoái ≡ [p ∨ (q ∧ ¬ q)] ∨ q Luaät baøi trung (luaät pt buø) ≡ (p ∨ 0) ∨ q Luaät trung hoøa ≡ p ∨ q b) ¬ (p ∨ q) ∨ [(¬ p ∧ q) ∨ ¬ q] . . . . . . . . . . . . . . . . . . . . . (1) ≡ ¬ (p ∨ q) ∨ [¬ q ∨ (¬ p ∧ q)] . . . . . . . . . . . . . . . . . . . . . (2) ≡ ¬ (p ∨ q) ∨ [(¬ q ∨ ¬ p) ∧ (¬ q∨ q)] . . . . . . . . . . . . . . . . . . . . . (3) ≡ ¬ (p ∨ q) ∨ [(¬ q ∨ ¬ p) ∧ 1] . . . . . . . . . . . . . . . . . . . . . (4) ≡ ¬ (p ∨ q) ∨ (¬ q ∨ ¬ p) . . . . . . . . . . . . . . . . . . . . . (5) ≡ ¬ (p ∨ q) ∨ ¬ (q ∧ p) . . . . . . . . . . . . . . . . . . . . . (6) ≡ ¬ [(p ∨ q) ∧ (q ∧p)] . . . . . . . . . . . . . . . . . . . . . (7) ≡ ¬ [(q ∧p) ∧(p ∨ q)] . . . . . . . . . . . . . . . . . . . . . (8) ≡ ¬ [q ∧[p ∧(p ∨ q)]] . . . . . . . . . . . . . . . . . . . . . (9) ≡ ¬ (q ∧ p) c*) C/minh: p→ (q → r) ≡ p ∧ q→ r ; (p→ q) ∧ [¬q ∧ (r ∨ ¬q)] ≡ ¬ (q ∨ p) 1.12- Haõy ñieàn meänh ñeà thích hôïp vaøo choã troáng ñeå cho caùc suy luaän sau ñaây theo phöông phaùp khaúng ñònh vaø phuû ñònh laø ñuùng: a) Neáu xe cuûa Minh khoâng khôûi ñoäng ñöôïc thì anh phaûi kieåm tra bugi. Maø xe cuûa Minh khoâng khôûi ñoäng ñöôïc Suy ra b) Neáu Haø laøm baøi ñuùng thì Haø ñöôïc ñieåm cao. Maø Haø khoâng ñöôïc ñieåm cao Suy ra c) Neáu chieàu nay Minh ñaù boùng thì Minh khoâng ñöôïc xem Tivi. Maø Vaäy Minh khoâng ñaù boùng chieàu nay. Bieân soaïn: Tröôøng Sôn 11
  13. Chöông 1 – Logic meänh ñeà Toaùn öùng duïng trong Tin hoïc 1.13- Cho bieát suy luaän naøo trong caùc suy luaän sau laø ñuùng vaø qui taéc suy luaän naøo ñaõ ñöôïc söû duïng? a) Ñieàu kieän ñuû ñeå Caûng SG thaéng traän laø ñoái thuû ñöøng gôõ laïi vaøo phuùt cuoái Maø Caûng SG ñaõ thaéng traän Vaäy ñoái thuû cuûa Caûng SG khoâng gôõ laïi vaøo phuùt cuoái b) Neáu Minh giaûi ñöôïc baøi toaùn thöù tö thì em ñaõ noäp baøi tröôùc giôø quy ñònh Maø Minh ñaõ khoâng noäp baøi tröôùc giôø quy ñònh Vaäy Minh khoâng giaûi ñöôïc baøi toaùn thöù tö. c) Neáu laõi suaát giaûm thì soá ngöôøi göûi tieát kieäm seõ giaûm Maø laõi suaát ñaõ khoâng giaûm Vaäy soá ngöôøi göûi tieát kieäm khoâng giaûm d) Neáu ñöôïc thöôûng cuoái naêm Haø seõ ñi Ñaø Laït Neáu ñi Ñaø Laït Haø seõ thaêm Suoái vaøng Do ñoù neáu ñöôïc thöôûng cuoái naêm Haø seõ thaêm Suoái Vaøng. 1.14- Xeùt suy dieãn: [p ∧ (p → q) ∧ (s ∨ r) ∧ (r → ¬ q)] → s Cho bieát caùc böôùc suy luaän sau ñaõ söû duïng caùc quy taéc, qui luaät naøo? Böôùc Quy taéc suy luaän p giaû thieát p → q giaû thieát ∴q tam ñoaïn luaän (Kí hieäu ∴∴∴laø keát luaän) hay ¬¬ q . . . . . . . . . . (1) maø r → ¬ q . . . . . . . . . . (2) ∴¬ r . . . . . . . . . . (3) maø s ∨ r . . . . . . . . . . (4) hay ¬ r → s . . . . . . . . . . (5) ∴s . . . . . . . . . . (6) 1.15- Xeùt suy luaän sau: (¬ p ∨ q) → r r → (s ∨ t) ¬ s ∧ ¬ u ¬ u → ¬ t ∴ p Cho bieát caùc quy taéc, quy luaät naøo ñaõ söû duïng caùc böôùc sau: Böôùc Quy taéc suy luaän ¬ s ∧ ¬ u . . . . . . . . . . . . . (1) ∴¬ u . . . . . . . . . . . . . (2) maø ¬ u → ¬ t . . . . . . . . . . . . . (3) ∴¬ t . . . . . . . . . . . . . (4) maø ¬ s . . . . . . . . . . . . . (5) neân ¬ s ∧ ¬ t . . . . . . . . . . . . . (6) hay ¬ (s ∨ t) . . . . . . . . . . . . . (7) maø r → s ∨ t . . . . . . . . . . . . . (8) ∴¬ r . . . . . . . . . . . . . (9) maø (¬ p ∨ q) → r . . . . . . . . . . . . . (10) ∴¬ (¬ p ∨ q) . . . . . . . . . . . . . (11) hay p ∧ ¬ q . . . . . . . . . . . . . (12) ∴p . . . . . . . . . . . . . (13) 12 Bieân soaïn: Tröôøng Sôn
  14. Chöông 1 – Logic meänh ñeà Toaùn öùng duïng trong Tin hoïc 1.16- Haõy kieåm tra caùc suy luaän sau, suy luaän naøo laø ñuùng / sai ? (∴kyù hieäu keát luaän) a) p → q b) p → q c) p → (q → r) ¬ q r → ¬ q ¬ q → ¬ p ¬ r r p    ∴¬ (p ∨ r) ∴¬ p ∴¬ r d) p ∧ q e ) p → (q → r) f) p ∨ q p → (r ∧ q) p ∨ s ¬ p ∨ r r → (s ∨ t) t → q ¬ r ¬ s ¬ s    ∴q ∴t ∴¬ r → ¬ t 1.17- Xeùt caùc vò töø: p(x): "x ≤ 5" q(x): "x+3 chaün" Trong ñoù x laø moät bieán nguyeân. Tìm chaân trò cuûa caùc meänh ñeà sau: a) p(1) b) q(1) c) ¬ p(2) d) q(3) e) p(6) ∨ q(6) f) ¬ (p(-1) ∨ q(-1)) 1.18- Xeùt vò töø p(x): "x2 - 3x + 2 = 0". Cho bieát chaân trò cuûa caùc meänh ñeà sau: a) p(0) b) p(1) c) p(2) d) ∃x, p(x) e) ∀x, p(x) 1.19- Xeùt vò töø theo hai bieán nguyeân lôùn hôn 0: p(x, y): "x laø öôùc cuûa y" Haõy xaùc ñònh chaân trò cuûa caùc meänh ñeà sau: a) p(2, 3) b) p(2, 6) c) ∀y, p(1, y) d) ∀x, p(x, x) e) ∀y, ∃x, p(x, y) f) ∃y∀x, p(x, y) g) ∀x∀y, (p(x, y) ∧ p(y, x)) → (x = y) h) ∀x∀y∀z, (p(x, y) ∧ p(y, z)) → p(x, z) 1.20- Haõy chöùng minh caùc coâng thöùc sau: n(n +1)(2n + )1 a) 02 + 11 + + n2 = , ∀n∈ N 6 n 2 n( + )1 2 b) 03 + 13 + + n3 = , ∀n∈ N 4 n(n +1)(n + )2 (n + 3) c) 1.2.3 + 2.3.4 + + n(n + 1)(n + 2) = , ∀n∈ N 4 1 1 1 n(n + 3) d) + +⋯ + = , ∀n∈ N 3.2.1 4.3.2 n(n +1 )(n + 2 ) 4(n +1 )(n + 2 ) e) 1.1! + 2.2! + + n.n! = (n + 1)! - 1 , ∀n∈ N 1 2 n 1 f) + + ⋯+ = 1− , ∀n∈ N !2 !3 ()n + !1 ()n + !1 g) (1 + a)n ≥ 1 + na, ∀n∈ N, a> -1. h) 2n > n ; ∀n∈ N. i) 2n+2 > 2n + 5 ; ∀n∈ N, n ≥ 1. Bieân soaïn: Tröôøng Sôn 13
  15. Chöông 1 – Logic meänh ñeà Toaùn öùng duïng trong Tin hoïc HÖÔÙNG DAÃN VAØ ÑAÙP SOÁ 1.1 Caâu a, c, f : laø meänh ñeà; Caâu b, d, e : khoâng phaûi laø meänh ñeà. 1.2 a/ P ∧ Q b/ ¬ P ∧ Q c/ P ∨ (¬ Q ∧ ¬ P) d/ P ⇒ ¬ Q e/ (P ∧ ¬ Q) ∨ (¬ P ∧ ¬ Q) 1.3 a/ P ∧ R ∧¬ Q b/ P ∧ Q ∧¬ (Q ∧ R) c/ ¬ (R ∧ ¬ P) ≡ ¬ R ∨ P d/ ¬ ((R∨ Q) ∧¬ P) e/ ¬ Q ∧ ¬ R ∧ P 1.4 a/ Khoâng ñuùng laø ngaøy mai neáu trôøi möa hay trôøi laïnh thì toâi seõ khoâng ra ngoaøi. hay : ngaøy mai duø trôøi möa hay trôøi laïnh nhöng toâi vaãn seõ ñi ra ngoaøi. b/ 15 khoâng chia heát cho 3 hoaëc 15 chia heát cho 4. c/ Hình töù giaùc naøy laø hình chöõ nhaät hay noù laø hình thoi. d/ Ngaøy mai Nam khoâng ñi laøm nhöng vaãn khoâng bò ñuoåi vieäc. e/ Coù tam giaùc maø caùc goùc khaùc 60o. 1.5 Meänh ñeà ñuùng: c, d, f. Meänh ñeà sai: a, b, e. 1.6 a) Ñuùng b) Sai c) Ñuùng 1.8 Coù 3 caùch ñaët daáu () vaøo bieåu thöùc ñaõ cho: a/ ¬ (P ∨ Q ∨ R) c/ ¬ P (∨ Q ∨ R) ≡ ¬ P ∨ Q ∨ R b/ ¬ (P ∨ Q) ∨ R 1.13 a/ Sai; b/ Ñuùng – qui taéc phuû ñònh (phaûn ñaûo) c/ Sai d/ Ñuùng – qui taéc tam ñoaïn luaän (baéc caàu) 1.16 a/ Ñuùng; b/ Ñuùng. c/ Sai. d/ Ñuùng. e/ Ñuùng. f/ Ñuùng. 1.17 a/ Ñuùng; b/ Ñuùng. c/ Sai. d/ Ñuùng. e/ Sai. f/ Sai. 1.18 a/ Sai; b/ Ñuùng. c/ Ñuùng d/ Ñuùng. e/ Sai. 1.19 a/ Sai; b/ Ñuùng. c/ Ñuùng d/ Ñuùng. e/ Ñuùng f/ Sai. g/ Ñuùng h/ Ñuùng. 1.20 a/ HD: 2k2+7k+6=(2k2+4k)+(3k+6)=(k+2)(2k+3) g/ (1+a)n ≥ 1+na, ∀n∈ N, a> -1. (*) + Vôùi n=0 ta coù (1+a)0 =1=1+0.a ⇒ (*) ñuùng vôùi n=0. + Giaû söû (*) ñuùng vôùi n=k, ta coù: (1+a)k ≥ 1+ka ⇒ (1+a)k (1+a) ≥ (1+ka)(1+a) , a> -1 ⇒ (1+a)k+1 ≥ 1+(k+1)a+ ka2 ≥ 1+(k+1)a ⇒ (1+a)k+1 ≥ 1+(k+1)a ⇒ (*) ñuùng vôùi n=k+1 Vaäy (1+a)n ≥ 1+na, ∀n∈ N, a> -1. 14 Bieân soaïn: Tröôøng Sôn
  16. Chöông 2 – Taäp hôïp, pheùp ñeám, quan heä Toaùn öùng duïng trong Tin hoïc CHÖÔNG 2 TAÄP HÔÏP – PHEÙP ÑEÁM – QUAN HEÄ I- TAÄP HÔÏP I.1- Khaùi nieäm: • Taäp hôïp laø moät soá caùc phaàn töû ñöôïc gheùp vôùi nhau theo moät caùch naøo ñoù. • Kí hieäu x laø phaàn töû thuoäc taäp A ta vieát: x ∈ A. • Kí hieäu x laø phaàn töû khoâng thuoäc taäp A ta vieát: x ∉ A. • Taäp hôïp khoâng chöùa phaàn töû naøo goïi laø taäp roãng, kí hieäu laø ∅∅∅. • Kí hieäu |A| laø soá phaàn töû cuûa taäp hôïp. o Neáu |A| = n thì taäp A ñöôïc goïi laø taäp hôïp höõu haïn. o Neáu |A| khoâng xaùc ñònh ñöôïc thì A ñöôïc goïi laø taäp hôïp voâ haïn, |A| = ∞ • Bieåu ñoàø Ven duøng bieåu dieãn taäp hôïp laø moät ñöôøng cong kín, phaúng, khoâng töï caét. Ví duï 1: 1) Taäp hôïp sinh vieân cuûa moät tröôøng ñaïi hoïc. (Taäp hôïp höõu haïn) a c b 2) Taäp hôïp caùc soá nguyeân. (Taäp hôïp voâ haïn) 3) Taäp hôïp caùc quyeån saùch trong thö vieän. (Taäp hôïp höõu haïn) Taäp hôïp A 4) Taäp hôïp caùc ñieåm treân moät ñöôøng thaúng. (Taäp hôïp voâ haïn) 5) Taäp hôïp caùc nghieäm thöïc cuûa phöông trình x2 + 1 = 0 (Taäp hôïp roãng) I.2- Caùch xaùc ñònh moät taäp hôïp: Caùch 1 – Lieät keâ caùc phaàn töû cuûa taäp hôïp. Ví duï: A = { a, b , c } ; N = {0, 1, 2, 3, .} Caùch 2 – Neâu tính chaát ñaëc tröng cuûa caùc phaàn töû thuoäc taäp hôïp. A = { x | x thoûa tính chaát p(x)}. Ví duï: + A = { m | m= 2n vôùi n laø soá nguyeân} - Taäp caùc soá nguyeân chaün. + B = { n | n laø soá töï nhieân vaø n \ 24} = {1, 2, 3, 4, 6, 8, 12, 24 } I.3- Caùc taäp hôïp soá thöôøng gaëp: 1/ Taäp hôïp soá töï nhieân: N = {0, 1, 2, 3, , n, .}; N* = {1, 2, 3, , n, .} 2/ Taäp hôïp soá nguyeân: Z = { , -n, , -3, -2, -1, 0, 1, 2, 3, , n, .} p 3/ Taäp hôïp soá höõu tyû: Q = { | p, q ∈ Z , q ≠ 0 } q Caùc soá höõu tyû coù theå vieát thaønh caùc soá thaäp phaân höõu haïn hay voâ haïn tuaàn hoaøn. 3 4 Chaúng haïn: = 0,75 ; = 1,33333 = 1,(3) 4 3 4/ Taäp hôïp soá voâ tyû: Moät soá voâ tyû coù theå vieát thaønh moät soá thaäp phaân voâ haïn khoâng tuaàn hoaøn. Chaúng haïn: 2 = 1,414213563 ; π = 3,1415926535897932384626433832795 5/ Taäp hôïp soá thöïc R: Bao goàm caùc soá höõu tyû vaø voâ tyû. 6/ Ñoaïn, khoaûng, nöûa ñoaïn (caùc taäp con cuûa taäp soá thöïc R): [a, b] = { x | x∈R, a ≤ x ≤ b} ; (a, b) = { x | x∈R, a < x < b} [a, b) = { x | x∈R, a ≤ x < b} ; (a, b] = { x | x∈R, a < x ≤ b} Bieân soaïn: Tröôøng Sôn 15
  17. Chöông 2 – Taäp hôïp, pheùp ñeám, quan heä Toaùn öùng duïng trong Tin hoïc I.4- Quan heä giöõa caùc taäp hôïp: 1/ Taäp hôïp con: Taäp A laø taäp hôïp con cuûa taäp B khi moïi phaàn töû cuûa A ñeàu thuoäc B. + Kyù hieäu: A ⊂⊂⊂ B vaø ñoïc laø • A bao haøm trong B • B chöùa A • A laø taäp con cuûa B + Quy öôùc: ∅∅∅ ⊂⊂⊂ A + Tính baéc caàu: A⊂ B  ⇒ A⊂C B ⊂C Ví duï: N ⊂ Z ⊂ Q ⊂ R 2/ Hai taäp hôïp baèng nhau: Neáu moät phaàn töû baát kyø cuûa taäp A ñeàu thuoäc veà taäp hôïp B vaø ngöôïc laïi thì A = B. A⊂ B A = B ⇔  B ⊂ A Ví duï: A = {1, 2, x, y, z } ; B = {x, 1, y, z, 2 } I.5- Caùc pheùp toaùn veà taäp hôïp: 1/ Pheùp toùan hôïp: Hôïp cuûa hai taäp hôïp A vaø B, kí hieäu laø A ∪ B, laø taäp hôïp bao goàm taát caû caùc phaàn töû thuoäc A hoaëc thuoäc B. A ∪ B = { x | x ∈ A hoaëc x ∈ B } Ví d: Cho A = [1 ; 3] vaø B = [2 ;4). A B Khi ñó A ∪ B = [1 ; 4) 2/ Pheùp toùan giao: Giao cuûa hai taäp hôïp A vaø B, kí hieäu laø A ∩ B, laø taäp hôïp bao goàm taát caû caùc phaàn töû thuoäc caû A vaø thuoäc B. A ∩ B = { x | x ∈ A vaø x ∈ B } A Ví d: Cho A = [1 ; 3] vaø B = (2 ;4). B Khi ñó A ∩ B = (2 ; 3] 3/ Pheùp toaùn tröø: Hieäu cuûa hai taäp hôïp A vaø B, kí hieäu laø A \ B, laø taäp hôïp A bao goàm taát caû caùc phaàn töû thuoäc A nhöng khoâng thuoäc B. B A \ B = { x | x ∈ A vaø x ∉ B } Ví d: Cho A = [1 ; 3] vaø B = [2 ;4). Khi ñó A \ B = [1 ; 2) 4/ Taäp hôïp buø (Hieäu hai taäp hôïp): E Cho A ⊂ E; taäp E \ A goïi laø taäp buø cuûa A trong E A vaø kyù hieäu laø C A hay A . E A Khi ñoù A = E \ A = { x | x ∈ E vaø x ∉ A } Ví d: Phaàn buø caùc soá nguyeân leû trong taäp caùc soá nguyeân laø taäp caùc soá chaün. I.6- Caùc tính chaát cuûa pheùp toaùn: Cho A⊂ E; B⊂ E; C⊂ E. 1/ A ∪ A = A; A ∩ A = A (tính chaát luõy ñaúng) 2/ A ∪ B = B ∪ A; A ∩ B = B ∩ A (tính chaát giao hoùan) 3/ (A ∪ B) ∪ C = A ∪ (B ∪ C) = A ∪ B ∪ C (tính chaát keát hôïp) (A ∩ B) ∩ C = A ∩ (B ∩ C) = A ∩ B ∩ C 16 Bieân soaïn: Tröôøng Sôn
  18. Chöông 2 – Taäp hôïp, pheùp ñeám, quan heä Toaùn öùng duïng trong Tin hoïc 4/ A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) (tính chaát phaân phoái) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) 5/ ABAB∪= ∩ ; ABAB∩= ∪ (Luaät De Morgan) 6/ A ∪ ∅ = A ; A ∩ E = A (tính chaát phaàn töû trung hoøa) 7/ A ∪ A = E ; A ∩ A = ∅ (tính chaát phaàn töû buø) 8/ A ∪ E = E ; A ∩ ∅ = ∅ (tính chaát thoáng trò) I.7- Tích Ñeà-caùc (Descartes): Tích cuûa hai taäp hôïp cuûa A vaø B kí hieäu laø A x B = {(a,b) | a∈ A; b ∈ B} Soá phaàn töû cuûa A x B : |A x B| = |A| x |B| n ∈ Toång quaùt: ∏Ai = A1x A2 x . . . x An = {(a1, a2, . . . , an) | ai Ai } y i=1 Ví duï: a/ A = { 1, 2, 3 }; B = {a, b } M(x,y) A x B = { (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) } |A x B| = 6 = 3 x 2 = |A| x |B| O x b/ R2 = R x R = { (x, y) vôùi x, y ∈ R } laø maët phaúng toïa ñoä Oxy. II - PHEÙP ÑEÁM II.1 Caùc nguyeân lyù ñeám II.1.1. Qui taéc coäng (nguyeân lyù coäng): a/ Ñònh nghóa: Moät coâng vieäc ñöôïc thöïc hieän bôûi hai caùch loïai tröø laãn nhau (coøn goïi laø hai phöông aùn khaùc nhau): Caùch thöù nhaát cho m keát quaû, caùch thöù hai cho n keát quaû. Khi aáy coâng vieäc ñöôïc thöïc hieän cho m+n keát quaû. - Môû roäng (cho n vieääc): Giaû söû vieäc V ñöôïc chia thaønh m vieäc V1, V2, .,Vn. Neáu Vi coù mi caùch thöïc hieän khoâng ñoàng thôøi vôùi vieäc thöïc hieän caùc vieäc coøn laïi. Khi ñoù soá caùch thöïc hieän V seõ laø m1+ m2 + + mn. Ngoân ngöõ taäp hôïp: Cho Ai, i=1, ,n laø caùc taäp höõu haïn, ñoâi moät rôøi nhau. Ta coù: |A1∪A2∪ ∪An| = |A1| + |A2| + + |An| b/ Ví duï: Moät sinh vieân coù theå choïn moät baøi thöïc haønh maùy vi tính töø moät trong ba danh saùch laàn löôït coù 24, 16, 20 baøi. Hoûi coù bao nhieâu caùch choïn baøi thöïc haønh? Giaûi: Roõ raøng, vieäc choïn baøi thöïc haønh töø 3 danh saùch laø khoâng ñoàng thôøi. AÙp duïng qui taéc coäng, ta thaáy: Coù 24 caùch choïn töø danh saùch thöù nhaát Coù 16 caùch choïn töø danh saùch thöù hai Coù 20 caùch choïn töø danh saùch thöù ba Nhö vaäy, coù 24 + 16 + 20 = 60 caùch choïn baøi thöïc haønh. II.1.2. Qui taéc nhaân (nguyeân lyù nhaân) a/ Ñònh nghóa: Giaû söû vieäc V ñöôïc chia thaønh hai vieäc ñöôïc thöïc hieän lieân tieáp nhau V1, V2 (coøn goïi laø hai giai ñoïan). V1 coù m caùch thöïc hieän; V2 coù n caùch thöïc hieän sau khi thöïc hieän V1. Khi ñoù soá caùch thöïc hieän xong coâng vieäc V seõ laø m.n. - Môû roäng (cho n vieääc): Giaû söû vieäc V ñöôïc chia thaønh n vieäc V1, V2, .,Vn. Neáu Vi coù mi caùch thöïc hieän sau khi thöïc hieän caùc vieäc V1, V2, Vi-1. Khi ñoù soá caùch thöïc hieän V seõ laø m1.m2. .mn. Ngoân ngöõ taäp hôïp: Cho Ai, i=1,n, laø caùc taäp höõu haïn, Ai ≠ Þ. Ta coù: |A1 x A2 x x An| = |A1|.|A2|. .|An| Bieân soaïn: Tröôøng Sôn 17
  19. Chöông 2 – Taäp hôïp, pheùp ñeám, quan heä Toaùn öùng duïng trong Tin hoïc b/ Caùc ví duï: − VD1: Coù bao nhieâu caùch ghi nhaõn cho gheá trong moät hoäi tröôøng baèng moät chöõ caùi (tieáng Anh, goàm 26 chöõ- ñöùng tröôùc) vaø moät trong caùc soá nguyeân döông khoâng quaù 100 ( ñöùng sau) Giaûi: Nhaõn (soá) gheá trong Hoäi tröôøng coù daïng mn. AÙp duïng qui taéc nhaân cho vieäc choïn soá mn trong ñoù m coù 26 caùch choïn, n coù 100 caùch choïn (sau khi choïn n). Vaäy soá mn coù 26.100= 2600 caùch choïn. − VD2: Coù bao nhieâu xaâu (chuoãi) nhò phaân coù ñoä daøi n (n∈N*)? Giaûi: Xaâu nhò phaân coù ñoä daøi n coù daïng (a1,a2, ,an) coù n thaønh phaàn; moãi thaønh phaàn laáy giaù trò 0 hoaëc 1. Roõ raøng: a1 coù 2 caùch choïn; a2 coù 2 caùch choïn; ; an coù 2 n caùch choïn. Vaäy coù 2.2 2=2 xaâu nhò phaân (a1,a2, ,an) II.1.3 Nguyeân lyù buø tröø. Khi hai coâng vieäc coù theå ñöôïc laøm ñoàng thôøi ta tính toång soá caùch laøm töøng coâng vieäc roài tröø ñi soá caùch laøm ñoàng thôøi caû hai coâng vieäc. Ví duï 1: Coù bao nhieâu daõy nhò phaân coù ñoä daøi baèng 8 hoaëc baét ñaàu baèng bit 1 hoaëc keát thuùc baèng hai bit 00 ? Giaûi : Soá daõy nhò phaân daøi 8 bit baét ñaàu baèng 1 laø 27 = 128. Soá daõy nhò phaân daøi 8 bit keát thuùc baèng 00 laø 26 = 65. Soá daõy nhò phaân daøi 8 bit baét ñaàu 1 vaø keát thuùc 00 laø 25 = 32 Vaäy toång soá daõy nhò phaân caàn tìm laø 128+64+32 = 160 Chuù yù : nguyeân lyù buø tröø coù theå phaùt bieåu döôùi daïng ngoân ngöõ taäp hôïp nhö sau: Cho A1, A2, An laø caùc taäp hôïp , ta coù: |A1 ∪ A2 | = |A1| + |A2| - | A1 ∩ A2 | |A1 ∪ A2 ∪ A3 | = |A1| + |A2| + |A3 | - | A1 ∩ A2 | - | A1 ∩ A3 | - | A2 ∩ A3 | + | A1 ∩ A2 ∩ A3 | Ví duï 2: Trong moät lôùp hoïc coù 180 sinh vieân. Trong soá naøy coù 55 sinh vieân choïn hoïc moân Anh vaên, 45 sinh vieân choïn hoïc moân Anh vaên vaø 15 sinh vieân choïn hoïc caû hai moân Anh vaên, Phaùp vaên. Hoûi coù bao nhieâu sinh vieân khoâng theo hoïc Anh vaên laãn Phaùp vaên. Giaûi : goïi A, B laàn löôït laø taäp sinh vieân choïn hoïc moân Anh vaên, Phaùp vaên. Ta coù |A| = 55, |B| = 45, |A ∩ B| = 15. Soá SV theo hoïc Anh hoaëc Phaùp vaên laø |A| + |B| - |A ∩ B| = 55+45-15 = 85 Vaäy soá SV khoâng hoïc caû Anh laãn Phaùp vaên laø 180 - 85 = 95 Ví duï 3: Giaû söû coù 1200 sinh vieân hoïc tieáng Anh, 850 sinh vieân hoïc tieáng Phaùp vaø 100 sinh vieân hoïc tieáng Ñöùc, 90 sinh vieân hoïc caû tieáng Anh vaø Phaùp, 15 sinh vieân hoïc caû tieáng Anh vaø Ñöùc, 10 sinh vieân hoïc caû tieáng Phaùp vaø Ñöùc . Neáu taát caû 2050 sinh vieân ñeàu hoïc ít nhaát moät ngoaïi ngöõ thì coù bao nhieâu sinh vieân hoïc caû ba thöù tieáng ? Giaûi : Ñaët A, B, C laàn löôït laø taäp hôïp sinh vieân hoïc tieáng Anh, Phaùp, Ñöùc. Khi ñoù: |A| = 1200, |B| = 850, |C| = 100, |A ∩ B| = 90, |A ∩ C| = 15, |B ∩ C| = 10 Maø |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C| Hay 2050 = 1200 + 850 + 100 - 90 - 15 - 10 + |A ∩ B ∩ C| Vaäy |A ∩ B ∩ C| = 15 18 Bieân soaïn: Tröôøng Sôn
  20. Chöông 2 – Taäp hôïp, pheùp ñeám, quan heä Toaùn öùng duïng trong Tin hoïc Ví duï 4: Hoûi trong taäp X = { 1, 2, , 10000 } coù bao nhieâu soá khoâng chia heát cho baát cöù soá naøo trong caùc soá 3, 4, 7 ? Giaûi : Ñaët Ai = { x ∈ X | x chia heát cho i }, i = 3, 4, 7 Vaäy soá löôïng caùc soá caàn ñeám laø N = 10000 - |A3 ∪ A4 ∪ A7 | = 10000 - |A3| - |A4| - |A7| + |A3 ∩ A4| + |A3 ∩ A7| + |A4 ∩ A7| - |A3 ∩ A4 ∩ A7| = 10000 - [10000/3] - [10000/4] - [10000/7] + [10000/12] + [10000/21] + [10000/28] - [10000/84] = 4286 II.1.4. NGUYÊN LÝ DIRICHLET II.1.4.1. M ñu: Gi s có mt ñàn chim b câu bay vào chung. Nu s chim nhiu hơn s ngăn chung thì ít nht trong mt ngăn có nhiu hơn mt con chim. Nguyên lý này dĩ nhiên là có th áp dng cho các ñi tưng không phi là chim b câu và chung chim. Mnh ñ (Nguyên lý): Nu có k+1 (hoc nhiu hơn) ñ vt ñưc ñt vào trong k hp thì tn ti mt hp có ít nht hai ñ vt. Chng minh: Gi s không có hp nào trong k hp cha nhiu hơn mt ñ vt. Khi ñó tng s vt ñưc cha trong các hp nhiu nht là bng k. ðiu này trái gi thit là có ít nht k + 1 vt. Nguyên lý này thưng ñưc gi là nguyên lý Dirichlet, mang tên nhà toán hc ngưi ðc th k 19. Ông thưng xuyên s dng nguyên lý này trong công vic ca mình. Ví d 1: a) Trong bt kỳ mt nhóm 367 ngưi th nào cũng có ít nht hai ngưi có ngày sinh nht ging nhau bi vì ch có tt c 366 ngày sinh nht khác nhau. b) Trong kỳ thi hc sinh gii, ñim bài thi ñưc ñánh giá bi mt s nguyên trong khong t 0 ñn 100. Hi rng ít nht có bao nhiêu hc sinh d thi ñ cho chc chn tìm ñưc hai hc sinh có kt qu thi như nhau? Theo nguyên lý Dirichlet, s hc sinh cn tìm là 102, vì ta có 101 kt qu ñim thi khác nhau. c) Trong s nhng ngưi có mt trên trái ñt, phi tìm ñưc hai ngưi có hàm răng ging nhau. Nu xem mi hàm răng gm 32 cái như là mt xâu nh phân có chiu dài 32, trong ñó răng còn ng vi bit 1 và răng mt ng vi bit 0, thì có tt c 232 = 4.294.967.296 hàm răng khác nhau. Trong khi ñó s ngưi trên hành tinh này là vưt quá 5 t, nên theo nguyên lý Dirichlet ta có ñiu cn tìm. II.1.4.2. Nguyên lý Dirichlet tng quát: Mnh ñ: Nu có N ñ vt ñưc ñt vào trong k hp thì s tn ti mt hp cha ít nht ]N/k[ ñ vt. ( ñây, ]x[ là giá tr ca hàm trn ti s thc x, ñó là s nguyên nh nht có giá tr ln hơn hoc bng x. Khái nim này ñi ngu vi [x] – giá tr ca hàm sàn hay hàm phn nguyên ti x – là s nguyên ln nht có giá tr nh hơn hoc bng x.) Chng minh: Gi s mi hp ñu cha ít hơn ]N/k[ vt. Khi ñó tng s ñ vt là Bieân soaïn: Tröôøng Sôn 19
  21. Chöông 2 – Taäp hôïp, pheùp ñeám, quan heä Toaùn öùng duïng trong Tin hoïc N N ≤ k (] [ − 1) < k = N. k k ðiu này mâu thun vi gi thit là có N ñ vt cn xp. Ví d 2: a) Trong 100 ngưi, có ít nht 9 ngưi sinh cùng mt tháng. Xp nhng ngưi sinh cùng tháng vào mt nhóm. Có 12 tháng tt c. Vy theo nguyên lý Dirichlet, tn ti mt nhóm có ít nht ]100/12[= 9 ngưi. b) Có năm loi hc bng khác nhau. Hi rng phi có ít nht bao nhiêu sinh viên ñ chc chn rng có ít ra là 6 ngưi cùng nhn hc bng như nhau. Gi N là s sinh viên, khi ñó ]N/5[ = 6 khi và ch khi 5 < N/5 ≤ 6 hay 25 < N ≤ 30. Vy s N cn tìm là 26. II.2. Giaûi tích toå hôïp II.2.1. Hoaùn vò cuûa n phaàn töû a/ Ñònh nghóa: Hoaùn vò cuûa n phaàn töû laø moät caùch saép xeáp coù thöù töï n phaàn töû ñoù. Ta chöùng minh ñöôïc (baèng caùch duøng quy taéc nhaân): Soá hoaùn vò laø: Pn = 1.2 .n = n! (ñoïc laø: n giai thöøa). Vôùi n! = 1.2.3 (n-1)n vaø 0! =1 b/ Ví duï: + Tìm soá hoaùn vò cuûa taäp coù 3 phaàn töû X = {1, 2, 3}. Ta coù caùc hoaùn vò laø: P3 = 3! = 6 123 132 213 231 312 321 + Soá caùch saép xeáp coù theå ñöôïc 5 hoïc sinh ngoài coù thöù töï vaøo moät baøn laø soá hoaùn vò cuûa 5 phaàn töû : P5 = 5!= 120 II.2.2. Chænh hôïp (khoâng laëp) chaäp k cuûa n phaàn töû a/ Ñònh nghóa: Chænh hôïp (khoâng laëp) chaäp k cuûa n phaàn töû laø moät caùch saép xeáp coù thöù töï k phaàn töû khaùc nhau töø n phaàn töû ñoù. Soá chænh hôïp (khoâng laëp) chaäp k cuûa n phaàn töû laø: k An = n! / (n-k)! ; k Hay An = n (n-1) (n-2) . . . (n-k+1) b/ VD: + Tìm chænh hôïp chaäp 3 cuûa taäp coù 4 phaàn töû X = {1, 2, 3, 4}. 123 124 132 134 142 143 213 214 231 234 241 243 312 314 321 324 341 342 412 413 421 423 431 432 3 A4 = 4.3.2 = 24 + Coù bao nhieâu soá töï nhieân coù 4 chöõ soá khaùc nhau (khoâng coù soá 0)? Giaûi. Soá caùc soá töï nhieân coù 4 chöõ soá khaùc nhau (khoâng coù soá 0) chính laøcaùc soá töï nhieân coù 4 chöõ soá khaùc nhau laäp töø 9 chöõ soá 1,2, ,9 (9 soá) 4 A 9 = 9! / (9-4)! = 9.8.7.6 = 3024 • Chuù yù: Chænh hôïp laëp chaäp k cuûa n phaàn töû laø moät caùch saép xeáp coù thöù töï k phaàn töû (coù theå truøng nhau) töø n phaàn töû ñoù . k k k k Soá chænh hôïp (laëp) chaäp k cuûa n phaàn töû kyù hieäu laø Fn = n hay An = n Ví duï: + Tìm chænh hôïp laëp chaäp 2 cuûa taäp coù 4 phaàn töû X = {1, 2, 3, 4}. Laäp baûng sau: 20 Bieân soaïn: Tröôøng Sôn
  22. Chöông 2 – Taäp hôïp, pheùp ñeám, quan heä Toaùn öùng duïng trong Tin hoïc 11 12 13 14 21 22 23 24 31 32 33 34 41 42 43 44 2 2 Vaäy F4 = 4 = 16 4 4 + Soá caùc soá coù 4 chöõ soá laäp töø {1,2,3,4,5,6,7,8,9} laø F 9 = 9.9.9.9 = 9 = 6561 II.2.3. Toå hôïp chaäp k cuûa n phaàn töû a/ Ñònh nghóa: Toå hôïp chaäp k cuûa n phaàn töû laø moät caùch choïn khoâng keå thöù töï k phaàn töû khaùc nhau töø n phaàn töû ñoù. (Chính laø laáy ra caùc taäp k phaàn töû töø n phaàn töû) n! Soá toå hôïp chaäp k cuûa n phaàn töû laø Ck = n k!( n− k )! Caùc ví duï: 3 Ví duï 1: Soá caùch choïn 3 hoïc sinh töø 5 h/s chính laø C 5 = 5! / 3!(5-3)! = 10 Ví duï 2: Moät lôùp hoïc 10 moân, moãi ngaøy hoïc hai moân. Hoûi coù bao nhieâu caùch saép xeáp thôøi khoùa bieåu ? Soá caùch saép xeáp thôøi khoùa bieåu laø soá chænh hôïp chaäp 2 töø 10 phaàn töû : 2 10! 10! = = = 10 9. = 90 C10 (10 − 2)! !8 Ví duï 3 : Moät toå goàm 8 nam vaø 6 nöõ . Coù bao nhieâu caùch choïn moät nhoùm 5 ngöôøi trong ñoù coù ñuùng 2 nöõ. Giaûi : 2 !6 Soá caùch choïn 2 nöõ trong soá 6 nöõ laø = =15 C6 2!.4! 3 !8 Soá caùch choïn 3 nam trong soá 8 nam laø = = 56 C8 3!.5! Vaäy soá caùch choïn laø 15.56 = 840 Ví duï 4 : Moät lôùp hoïc coù 20 sinh vieân trong ñoù 2 caùn boä lôùp. Hôûi coù bao nhieâu caùch cöû 3 ngöôøi ñi döï hoäi nghò sinh vieân cuûa tröôøng sao cho trong 3 ngöôøi ñoù coù ít nhaát moät caùn boä lôùp. Giaûi : Soá caùch choïn 3 trong soá 20 sinh vieân tuøy yù : 3 . C20 Soá caùch choïn 3 trong soá 18 sinh vieân khoâng coù caùn boä lôùp : 3 C18 3 3 20! 18! Vaäy soá caùch choïn theo ñeà baøi : - = − =1140 −816 = 324 C20 C18 3!.17! 3!15! b/ Moät soá coâng thöùc: n • n k n− k k n=0 + 1 + + n− 1 + n Nhò thöùc Niu tôn: (a+b) = ∑Cn a b ; Khi a=b=1: 2CCCCn n n n k=0 k • k i k-i Haèng ñaúng thöùc Vandermon: Cm+n = ∑CCm n i=0 k n-k • C n = C n (tính chaát ñoái xöùng) k-1 k k • C n-1 + C n-1 = C n (Coâng thöùc Pascal) Töø hai tính chaát neâu sau suy ra tam giaùc Pascal veà caùc heä soá cuûa nhò thöùc Niutôn: Bieân soaïn: Tröôøng Sôn 21
  23. Chöông 2 – Taäp hôïp, pheùp ñeám, quan heä Toaùn öùng duïng trong Tin hoïc 1 n = 0: (a+b)0 = 1 1 →+ 1 n = 1: (a+b)1 = a + b 1 →+ 2 →+ 1 n = 2: (a+b)2 = a2 + 2ab + b2 1 3 3 1 n = 3: (a+b)3 = a3 + 3a2b + 3ab2 + b3 1 4 6 4 1 n = 4: (a+b)4 = a4 + 4a3b + 6a2b2 + 4ab3+b4 . . . III- QUAN HEÄ HAI NGOÂI 1. Quan heä hai ngoâi a/ Ñònh nghóa: Cho hai taäp A≠ ∅, B≠ ∅. R goïi laø moät quan heä hai ngoâi töø A ñeán B neáu R laø taäp con cuûa AxB : R⊂ AxB Neáu (a,b) ∈ R thì ta noùi “ a coù quan heä hai ngoâi (hay quan heä) R vôùi b” vaø vieát aRb. Nhö vaäy: aRb ⇔ (a,b) ∈ R. Khi A=B=X ta noùi R laø quan heä treân X. Luùc ñoù: R⊂ X2. b/ Ví duï: - Cho A = { huyeän}; B={tænh }. Quan heä R töø A ñeán B ñöôïc xaùc ñònh: “ huyeän a quan heä R vôùi tænh b neáu huyeän a thuoäc tænh b”. Nhö vaäy: R={ (a,b) | a∈A, b∈B, “ a naèm trong b” }⊂ AxB = { (a,b) | a∈A, b∈B }. Ta coù (Bình Long, Bình Phöôùc), (Q.1, TP Hoà Chí Minh), ∈R Nhöng (Bình Long, Bình Döông), (Q.1, Taây Ninh), ∉R - Cho X = Y = N* = N\{0} (taäp caùc soá töï nhieân döông). 2 Taäp R = { (a,b) | a,b∈N*, a\b “a laø öôùc cuûa b”} ⊂ N* vaø xaùc ñònh moät quan heä hai ngoâi treân N. Ta coù: (2,6)∈R, (3,9)∈R ; coøn (2,5)∉R, (3,10)∉R Nhaän xeùt: Moät quan heä hai ngoâi laø moät moät taäp con cuûa taäp tích Ñeà caùc cuûa hai taäp hôïp vaø ngöôïc laïi moät taäp con cuûa taäp tích Ñeà caùc xaùc ñònh moät qhhn giöõa hai taäp hôïp. Môû roäng: Neáu R ⊂ A1 x A2 x . . . x An thì R laø quan heä n ngoâi. Quan heä n ngoâi thöôøng duøng trong cô sôû döõ lieäu quan heä. Ví duï, ta coù danh saùch sinh vieân sau: MASV HOSV TENSV PHAI NGAYSINH HOCBONG MAKHOA 06TH-001 Traàn Höng Chaùnh Nam 22/03/85 150000 TH 06TH-002 Traàn Thò Thuøy Lieân Nöõ 27/05/86 TH 06TH-003 Ñoaøn Chí Phaùt Nam 10/12/85 200000 TH 06KT-001 Leâ Ngoïc Thuùy Nöõ 15/05/88 KT 06KT-002 Voõ Thò Minh Nöõ 10/03/87 120000 KT . . . . . . . . . . Moãi doøng döõ lieäu laø moät phaàn töû cuûa quan heä 7 ngoâi noù löu tröõ thoâng tin cuûa moät sinh vieân naøo ñoù. 2. Caùc tính chaát cuûa quan heä Cho quan heä R treân taäp X: o R coù t/c phaûn xaï ⇔ ∀ a∈R, aRa. o R coù t/c ñoái xöùng ⇔ ∀ a,b∈R: aRb ⇒ bRa. o R coù t/c phaûn ñoái xöùng ⇔ ∀ a,b∈R: a=b &b=a ⇒ a=b o R coù t/c baéc caàu ⇔ ∀ a, b, c∈R: aRb & bRc ⇒ aRc Nhaän xeùt: Moät quan heä hai ngoâi coù theå coù caû 4 t/c, cuõng coù theå khoâng coù t/c naøo. 22 Bieân soaïn: Tröôøng Sôn
  24. Chöông 2 – Taäp hôïp, pheùp ñeám, quan heä Toaùn öùng duïng trong Tin hoïc Ví duï: - Quan heä “baèng nhau” treân taäp caùc soá nguyeân Z coù caû 4 tính chaát. - Quan heä “cuøng queâ” cuûa caùc hoïc vieân cuøng lôùp TH coù 3 tính chaát: • phaûn xaï: vì a cuøng queâ vôùi chính a; ta coù aRa • ñoái xöùng: a cuøng queâ vôùi b thì b cuõng cuøng queâ vôùi a, töùc laø aRb ⇒ bRa • baéc caàu: a cuøng queâ vôùi b, b cuøng queâ vôùi c thì a cuøng queâ vôùi c; töùc laø töø aRb vaø bRc ta coù aRc. - Quan heä: “lôùn hôn hoaëc baèng” ( ≥) treân taäp caùc soá N, Z, Q, R coù caùc t/c: phaûn xaï, phaûn ñoái xöùng, baéc caàu. - Quan heä vuoâng goùc giöõa caùc ñöôøng thaúng treân maët phaúng chæ coù tính chaát ñoái xöùng. - Quan heä song song giöõa caùc ñöôøng thaúng treân maët phaúng coù tính chaát: phaûn xaï, ñoái xöùng, baéc caàu. 3. Quan heä töông ñöông a. Ñònh nghóa: Quan heä R treân taäp A≠ Þ ñöôïc goïi laø quan heä töông ñöông treân A neáu R coù 3 tính chaát: phaûn xaï, ñoái xöùng, baéc caàu. Vôùi x, y∈A maø xRy, ta noùi “x töông ñöông vôùi y”. Kyù hieäu x ~y. Ví duï: - Quan heä “baèng nhau” treân Z, “cuøng queâ” cuûa lôùp TH laø caùc qhtd treân taäp ñang xeùt. - Quan heä “ñoàng daïng” treân taäp caùc tam giaùc phaúng laø quan heä töông ñöông. b. Lôùp töông ñöông. Giaû söû R laø quan heä töông ñöông treân A vaø a∈A. Taäp hôïp {x∈A| xRa } goïi laø moät lôùp töông ñöông cuûa a, kyù hieäu a hay [a] hay C(a). a ñöôïc goïi laø phaàn töû ñaïi dieän. Tính chaát: Trong moät lôùp töông ñöông coù theå laáy baát cöù phaàn töû naøo trong ñoù laøm phaàn töû ñaïi dieän, nghóa laø[a]= [b] , ∀b∈[a] c. Taäp thöông Ñ/n: Cho R laø qhtñ treân taäp A≠ Þ. Khi ñoù R phaân raõ treân A thaønh caùc lôùp töông ñöông. Taäp caùc lôùp töông ñöông ñoù ñöôïc goïi laø taäp thöông cuûa A theo qhtñ R, kyù hieäu laø: A/R. Luùc ñoù A/R= { a | ∀a∈R } Ví duï: - Quan heä song song giöõa caùc ñöôøng thaúng treân maët phaúng laø quan heä töông ñöông. - Quan heä R“cuøng queâ” treân taäp A caùc sinh vieân laø qhtñ vaø phaân lôùp treân A. Taäp thöông A/R goàm caùc lôùp töông ñöông maø moãi lôùp laø nhoùm caùc sinh vieân cuøng queâ. - Quan heä ñoàng dö ≅ theo modulo 3 treân Z, kyù hieäu a ≅ b (mod 3) ⇔ a-b ⋮ 3. o ∀ a∈Z ta coù a-a = 0 ⋮ 3 ⇒ a ≅ a, töùc laø quan heä ≅ coù tính chaát phaûn xaï. o ∀ a, b ∈Z, a ≅ b ⇔ a-b ⋮ 3 ⇒ - (a-b) ⋮ 3 ⇒ b-a ⋮ 3 ⇒ b ≅ a (t/c ñoái xöùng) o ∀ a, b, c ∈Z, a ≅ b vaø b ≅ c ⇒ (a-b) ⋮ 3 vaø (b-c) ⋮ 3 ⇒ (a-b) + (b-c) ⋮ 3 ⇒ (a - c) ⋮ 3 ⇒ a ≅ c (t/c baéc caàu) Vaäy quan heä ñoàng dö ≅ theo modulo 3 treân Z laø moät qhtñ. Vôùi ∀n∈Z, bao giôø cuõng vieát ñöôïc n=3q+r vôùi q∈Z, 0≤r<3 ⇔ n ≅ r (mod 3) vaø ta coù caùc lôùp töông ñöông treân Z laø 0 , 1 , 2 vaø kyù hieäu Z3 = Z/≅ = { 0 , 1 , 2 }. Toång quaùt, ta coù: Zn = Z/≅ (mod n) = { 0 , 1 , 2 , , n −1 }, n-soá nguyeân döông. 4. Quan heä thöù töï a. Ñònh nghóa: Bieân soaïn: Tröôøng Sôn 23
  25. Chöông 2 – Taäp hôïp, pheùp ñeám, quan heä Toaùn öùng duïng trong Tin hoïc • Quan heä R treân taäp A≠ Þ ñöôïc goïi laø quan heä thöù töï neáu R coù 3 tính chaát: phaûn xaï, phaûn ñoái xöùng vaø baéc caàu. Luùc ñoù taäp A ñöôïc goïi laø taäp saép thöù töï. • Quan heä thöù töï R treân A thöôøng ñöôïc kyù hieäu laø “≤” vaø cuõng ñoïc laø “nhoû hôn hoaëc baèng”. Vaäy xRy ñöôïc vieát laø x≤y. • Neáu moïi caëp phaàn töû x, y∈A ta ñeàu coù x≤y hoaëc y≤x (töùc laø x, y so saùnh ñöôïc vôùi nhau) thì R ñöôïc goïi laø quan heä thöù töï toaøn phaàn. Ngöôïc laïi, R laø quan heä thöù töï boä phaän (töùc laø coù ít nhaát moät caëp phaàn töû khoâng so saùnh ñöôïc). b.Ví duï: VD1- Quan heä “≤” (nhoû hôn hoaëc baèng thoâng thöôøng) treân N (hoaëc Z, Q, R) laø qhtt toøan phaàn. Vì vaäy caùc taäp naøy laø caùc taäp saép thöù töï toøan phaàn vôùi quan heä ≤. VD2- Taäp caùc kyù töï trong baûng maõ ASCII laø taäp saép thöù töï toaøn phaàn (thöù töï töø ñieån). VD3- Quan heä “chia heát”(\) treân N* = N \{0} laø quan heä thöù töï boä phaän. - ∀ a∈N*, ta coù a\a neân quan heä \ coù tính chaát phaûn xaï. - ∀ a, b∈N* neáu a\b vaø b\a thì a=b, suy ra quan heä \ coù tính chaát phaûn ñoái xöùng. - ∀ a, b, c∈N* neáu a\b vaø b\c thì a\c, suy ra quan heä \ coù tính chaát baéc caàu. Do N* coù hai phaàn töû 2 vaø 3 khoâng so saùnh ñöôïc theo quan heä \ neân quan heä \ laø quan heä thöù töï boä phaän. Vaäy N* laø taäp saép thöù töï boä phaän. VD4- Quan heä “bao haøm” ⊂ treân P(X) caùc taäp con cuûa X (X laø taäp cho tröôùc, X≠ Þ) laø qhtt boä phaän, neân (P(X), ⊂) laø taäp saép thöù töï boä phaän. Ta coù P(X) = { A | A ⊂⊂⊂ X, X≠ Þ}. Khi ñoù: - A ⊂ A neân quan heä bao haøm coù tính chaát phaûn xaï. - Neáu coù A ⊂ B vaø B ⊂ A thì A = B, suy ra quan heä bao haøm coù tính phaûn ñoái xöùng. - Neáu coù A ⊂ B vaø B ⊂ C thì A ⊂ C, suy ra quan heä bao haøm coù tính baéc caàu. Vaäy quan heä “bao haøm” ⊂ treân P(X) laø moät quan heä thöù töï. Maët khaùc, laáy a, b laø hai phaàn töû khaùc nhau cuûa A thì 2 taäp con {a}, {b} laø khoâng so saùnh ñöôïc vôùi nhau neân quan heä ⊂ laø quan heä thöù töï boä phaän. 5. ÖÙng duïng cuûa quan heä hai ngoâi trong truy vaán döõ lieäu: Quan heä hai ngoâi thöôøng duøng ñeå phaân nhoùm vaø saép xeáp, loïc löïa döõ lieäu. Chaúng haïn, cho baûng döõ lieäu: SINHVIEN (MASV, HO, TEN, PHAI, NGAYSINH, HOCBONG, MAKHOA) a/ Quan heä töông ñöông “cuøng maõ khoa” phaân nhoùm döõ lieäu treân SINHVIEN. Ví duï 1: Ñeám soá sinh vieân theo töøng khoa SELECT MAKHOA, Count(MASV) AS SI_SO FROM SINHVIEN GROUP BY MAKHOA b/ Quan heä thöù töï duøng ñeå saép xeáp vaø loïc löïa döõ lieäu SINHVIEN: Ví duï 2: Loïc d/s sinh vieân coù hoïc boång vaø saép xeáp taêng theo töøng khoa vaø theo teân, hoï. SELECT * FROM SINHVIEN WHERE HOCBONG>0 ORDER BY MAKHOA, TEN, HO BAØI TAÄP CHÖÔNG 2 2.1- Haõy lieät keâ ra caùc phaàn töû cuûa caùc taäp hôïp döôùi ñaây: a) A = {1 + (-1)n | n ∈ N} 1 b) B = {n + | n ∈ {1, 2, 3, 5, 7}} n c) C = {1 / (n2 + n) | n ∈ N, n laø soá leû vaø n ≤ 11} 2.2- Trong caùc soá taäp hôïp döôùi, caùctaäp naøo baèng nhau : A = {a, b, c} B = {a, b, c, a} 24 Bieân soaïn: Tröôøng Sôn
  26. Chöông 2 – Taäp hôïp, pheùp ñeám, quan heä Toaùn öùng duïng trong Tin hoïc C = {a, c, b, a} D = {a, b, b, c} 2.3- Xeùt caùc taäp hôïp con cuûa Z: A = {2m + 1 | m ∈ Z}, B = {2n + 3 | n ∈ Z} C = {2p – 3 | p ∈ Z}, D = {3r + 1 | r ∈ Z} E = {3s + 2 | s ∈ Z}, F = {3t – 2 | t ∈ Z} Haõy xaùc ñònh caùc khaúng ñònh ñuùng trong caùc soá khaúng ñònh döôùi ñaây: a) A = B b) A = C c) B = C d) D = E e) D = F f) E = F 2.4- Trong caùc soá taäp hôïp döôùi ñaây, taäp hôïp naøo khaùc taäp ΦΦΦ? a) {x ∈ N | 2x + 7 = 3} b) {x ∈ Z | 3x + 5 = 9} c) {x ∈ Q | x2 + 4 = 6} d) {x ∈ R | x2 + 4 = 6} e) {x ∈ R | x2 + 5 = 4} f) {x ∈ R | x2 + 3x + 3 = 0} 2.5- Xeùt 4 taäp hôïp con cuûa taäp hôïp cô sôû U = {1, 2, 3, . . ., 10}: A = {1, 2, 3, 4, 5}, B = {1, 2, 4, 8} C = {1, 2, 3, 5, 7}, D = {2, 4, 6, 8} Haõy xaùc ñònh caùc taäp hôïp döôùi ñaây: a) (A ∪ B) ∩ C b) A ∪ (B ∩ C) c) C ∪ D d) C ∩ D e) (A ∪ B) ∩ C f) A ∪ (B ∩ C ) g) (B ∩ C ) ∩ D h) B ∩ C ∩ D 2.6- Xeùt caùc taäp hôïp con cuûa Z: A = {2n | n ∈ Z}, B = {3n | n ∈ Z} C = {4n | n ∈ Z}, D = {6n | n ∈ Z} E = {8n | n ∈ Z} Haõy chæ ra caùc khaúng ñònh ñuùng trong soá caùc khaúng ñònh döôùi ñaây: a) E ⊂ C ⊂ A b) A ⊂ C ⊂ E c) D ⊂ B d) D ⊂ A e) B ⊂ D f) DA⊂ 2.7- Xeùt caùc taäp hôïp con A, B, C, D cuûa taäp hôïp cô sôû E Haõy cho bieát quy luaät naøo ñöôïc söû duïng trong caùc böôùc ñôn giaûn taäp hôïp döôùi ñaây: Böôùc Quy luaät (A ∩ B) ∪ [B ∩ ((C ∩ D) ∪ (C ∩ D ))] (1) = (A ∩ B) ∪ [B ∩ (C ∩ (D ∪ D ))] (2) = (A ∩ B) ∪ [B ∩ (C ∩ E)] (3) = (A ∩ B) ∪ (B ∩ C) (4) = (B ∩ A) ∪ (B ∩ C) (5) = B ∩ (A ∪ C) (6) 2.8- Duøng caùc quy luaät cuûa lyù thuyeát taäp hôïp ñeå ñôn giaûn caùc bieåu thöùc döôùi ñaây: a) A ∩ (B ∩ A ) b) A ∪ B ∪ (A ∩ B ∩ C ) c*) (A ∩ B) ∪ (A ∩ B ∩ C ∩ D) ∪ ( A ∩ B) 2.9. Vit mi tp hp sau bng cách lit kê các phn t ca nó: a) A = {x ∈R | (2x – x2)(2x2 – 3x – 2) = 0}; b) B = {n ∈ N | 3 < n2 < 30}. Bieân soaïn: Tröôøng Sôn 25
  27. Chöông 2 – Taäp hôïp, pheùp ñeám, quan heä Toaùn öùng duïng trong Tin hoïc 2.10. Vit mi tp hp sau bng cách ch rõ các tính cht ñc trưng cho các phn t ca nó: a) A = {2 ; 3 ; 5 ; 7}; c) C = {-5 ; 0 ; 5 ; 10 ; 15} b) B = {-3 ; -2 ; -1 ; 0 ; 1 ; 2 ; 3}; 2.11. Xét xem hai tp hp sau có bng nhau không: A = {x ∈R | (x – 1)(x – 2)(x – 3) = 0} và B = {5 ; 3 ; 1} 2.12. Gi s A = {2 ; 4 ; 6}, B = {2 ; 6}, C = {4 ; 6} và D = {4 ; 6 ; 8}. Hãy xác ñnh xem tp nào là tp con ca tp nào. 2.13. Cho A là tp hp các hc sinh ñang hc trưng em và B là tp hp các hc sinh ñang hc môn Ting Anh ca trưng em. Hãy ñin ñt bng li các tp hp sau: a) A ∩ B; b) A \ B c) A ∪ B d) B \ A 2.14. Gi A, B, C , D, E và F ln lưt là tp hp các t giác li, tp hp các hình thang, tp hp các hình bình hành, tp hp các hình ch nht, tp hp các hình thoi và tp hp các hình vuông. a/ Hi tp nào là tp con ca tp nào? b/ Hãy din ñt bng li tp D ∩ E. 2.15. Cho A = {1 ; 3 ; 5} và B = {1 ; 2 ; 3}. Tìm hai tp hp (A \ B) ∪ (B \ A) và (A ∪ B) \ (A ∩ B). Hai tp hp nhn ñưc là bng nhau hay khác nhau? 2.16. ðin du “x” vào ô trng thích hp. a) ∀ x ∈R, x ∈ (2,1 ; 5,4) ⇒ x ∈ (2 ; 5) ðúng Sai b) ∀ x ∈R, x ∈ (2,1 ; 5,4) ⇒ x ∈ (2 ; 6) ðúng Sai c) ∀ x ∈R, -1,2 ≤ x < 2,3 ⇒ -1 ≤ x ≤ 3 ðúng Sai d) ∀ x ∈R, -4,3 < x ≤ -3,2 ⇒ -5 ≤ x ≤ -3 ðúng Sai 2.17. Cho ñon A = [-5 ; 1] và khong B = (-3 ; 2). Tìm A ∪ B và A ∩ B. 3 2.18- Coù bao nhieâu tam giaùc ñöôïc thieát laäp töø n ñænh cuûa ña giaùc loài? (ÑS: Cn ) 2 Coù bao nhieâu ñöôøng cheùo (laø ñöôøng noái 2 ñænh khoâng keà nhau) ? (ÑS: Cn -n) 2.19- Coù bao nhieâu taäp con cuûa taäp goàm n phaàn töû? 2.20- Lôùp coù 40 hoïc sinh goàm 15 nam vaø 25 nöõ. Coù maáy caùch choïn 5 ngöôøi ñeå trong ñoù coù ít nhaát 2 nöõ ? 2.21 Hoï A goàm 9 ñöôøng thaúng song song caét heä B caùc ñöôøng thaúng song song khaùc taïo neân 540 hình bình haønh. Hoûi heä B coù bao nhieâu ñ.t song song ? 2.22- Cho 6 chöõ soá: 0, 1, 2, 3, 4, 5. a/ Hoûi coù bao nhieâu soá töï nhieân chaün coù 5 chöõ soá khaùc nhau laäp töø 6 soá treân? b/ Coù bao nhieâu soá töï nhieân goàm 5 chöõ soá trong ñoù coù hai chöõ soá 1 vaø caùc chöõ soá coøn laïi khaùc nhau ñöôïc laäp töø 6 chöõ soá treân? 2.23 Cho X = {2, 3, 5, 6}; xaùc ñònh quan heä 2 ngoâi S: aSb ⇔ a+b laø soá chaün. a/ Xaùc ñònh caùc phaàn töû cuûa S vaø moâ taû treân maët phaúng toïa ñoä Oxy. b/ Chöùng minh S laø quan heä töông ñöông treân X. Xaùc ñònh taäp thöông X/S ? 2.24- Treân X = ZxN*, R xaùc ñònh bôûi (a, b) R (c, d) ⇔ a/b = c/d. Chöùng minh R laø quan heä töông ñöông treân X. Xaùc ñònh taäp thöông X/R ? 26 Bieân soaïn: Tröôøng Sôn
  28. Chöông 2 – Taäp hôïp, pheùp ñeám, quan heä Toaùn öùng duïng trong Tin hoïc 2.25. Treân taäp X = R×R, xaùc ñònh quan heä 2 ngoâi S: (a,b)S(c,d) ⇔ a=c a/ Chöùng minh S laø quan heä töông ñöông treân X. b/ Xaùc ñònh taäp thöông X/S vaø minh hoïa treân maët phaúng toïa ñoä. HÖÔÙNG DAÃN – ÑAÙP SOÁ 5 10 26 50 n2 +1 2.1 A = {0, 2}; B = {2, , , , }; daïng vôùi n =1, 2, 3, 5, 7 2 3 5 7 n 1 1 1 1 1 1 1 C = { , , , , , }; daïng vôùi n = 1, 3, 5, 7, 9, 11 2 12 30 56 90 132 n( n + 1) 2.2 A = B = C = D 2.3 a) Ñuùng; b) Ñuùng; c) Ñuùng; d) Sai; e) Ñuùng; f) Sai 2.4 d) Ñuùng. D = {- 2 ; 2 } 2.5 a) {1, 2, 3, 5}; b) {1, 2, 3, 4, 5} = A; c) {1, 3, 4, 5, 6, 7, 8, 9, 10} d) {1, 3, 4, 5, 6, 7, 8, 9, 10} _ _ Töø c) vaø d) suy ra C ∪ D = C ∩ D 2.6 a) Ñuùng; b) Sai; c) Ñuùng; d) Ñuùng; e) Sai; f) Sai. 2.8 a) ∅ b) ()AB∩ ∩C c*) B (Tham khaûo saùch Ñaïi soá lôùp 10 – Ban A - NXBGD 2007 cho các bài t 2.9 – 2.17) 2.9. a) A = {x ∈R | (2x – x2)(2x2 – 3x – 2) = 0} = {-1/2; 0; 2 }; b) B = {n ∈ N | 3 < n2 < 30} = { 2; 3; 4; 5} 2.10. Vit mi tp hp sau bng cách ch rõ các tính cht ñc trưng cho các phn t ca nó: a) A = {2 ; 3 ; 5 ; 7} = { n là s nguyên t và 3 ≤ n ≤ 7 } c) C = {-5 ; 0 ; 5 ; 10 ; 15} = { 5n | -1 ≤ n ≤ 3 } b) B = {-3 ; -2 ; -1 ; 0 ; 1 ; 2 ; 3} = { n ∈ Z | -3 ≤ n ≤ 3 } 2.11. A = {1; 2; 3} và B = {5 ; 3 ; 1} ⇒ A ≠ B 2.12. Gi s A = {2 ; 4 ; 6}, B = {2 ; 6}, C = {4 ; 6} và D = {4 ; 6 ; 8}. Ta có: B ⊂⊂⊂ A ; C ⊂⊂⊂ A ; C ⊂⊂⊂ D 2.13. Do B ⊂ A nên: a) A ∩ B = B = { Các bn ñang hc ting Anh ca trưng em}; b) A \ B = B = { Các bn không hc ting Anh ca trưng em}; c) A ∪ B = A = { Tt c các bn hc sinh ca trưng em}; d) B \ A = ∅ = { Không có bn nào hc ting Anh ca trưng em mà không thuc trưng em} 2.14. Gi A = {tp hp các t giác li} B = { tp hp các hình thang} C = {tp hp các hình bình hành}, D = { tp hp các hình ch nht} E = {tp hp các hình thoi} F = { tp hp các hình vuông}. Bieân soaïn: Tröôøng Sôn 27
  29. Chöông 2 – Taäp hôïp, pheùp ñeám, quan heä Toaùn öùng duïng trong Tin hoïc a/ Hi tp nào là tp con ca tp nào? F ⊂⊂⊂ D ⊂⊂⊂ C ⊂⊂⊂ B ⊂⊂⊂ A; E ⊂⊂⊂ C ⊂⊂⊂ B ⊂⊂⊂ A b/ D ∩ E = F = { tp hp các hình vuông}. 2.15. Cho A = {1 ; 3 ; 5} và B = {1 ; 2 ; 3}. + (A \ B) ∪ (B \ A) = { 5 } ∪ { 2 } = {2 ; 5} + (A ∪ B) \ (A ∩ B) = {1; 2; 3; 5} \ {1; 3} = {2; 5} Suy ra (A \ B) ∪ (B \ A) = (A ∪ B) \ (A ∩ B) 2.16. ðin du “x” vào ô trng thích hp. a) ∀ x ∈R, x ∈ (2,1 ; 5,4) ⇒ x ∈ (2 ; 5) ðúng Sai [X ] b) ∀ x ∈R, x ∈ (2,1 ; 5,4) ⇒ x ∈ (2 ; 6) ðúng [X ] Sai c) ∀ x ∈R, -1,2 ≤ x < 2,3 ⇒ -1 ≤ x ≤ 3 ðúng Sai [X ] d) ∀ x ∈R, -4,3 < x ≤ -3,2 ⇒ -5 ≤ x ≤ -3 ðúng [X ] Sai 2.17. Cho ñon A = [-5 ; 1] và khong B = (-3 ; 2). + A ∪ B = [-5; 2) + A ∩ B = (-3; 1] n! (n− 3)!( n − 2)( n − 1) n (n− 2)( n − 1) n 2.18 a) C3 = = = vôùi n ≥ 3 n 3!(n − 3)! (1.2.3)(n − 3)! 6 n! (n− 1) n (n− 1) n − 2 n (n− 3) n b) C 2 - n = - n = - n = = vôùi n ≥ 4 n 2!(n − 2)! 2 2 2 k 2.19 Soá taäp con coù k phaàn töû cuûa taäp coù n phaàn töû laø Cn . Vaäy toång soá caùc taäp con laø: 0+ 1 + +n− 1 + n = n CCCCn n n n 2 2 3+ 3 2 + 4 1 + 5 2.20 CCCCCCC25 15 25 15 25 15 25 2 2 2.21 Heä B coù n ñöôøng thaúng song song thì ta coù: CC9 . n = 540 ⇒ (n-1)n = 30 ⇒ n = 6. 4 3 2.22 a) 1. A5 + 2.4. A4 = 120 + 192 = 312 1 3 2 2 b) 1. C4 .A 5 + 4.(1.C4 .A 4 ) = 240 + 288 = 528 2.23 a) S = {(2, 2), (2, 6), (3, 3), (3, 5), (5, 3), (5, 5), (6, 2), (6, 6)} b) X/S = { 2 , 3} a a 2.24 +T/c phaûn xaï: Vì = neân (a,b)R(a,b) ⇒ R coù t/c phaûn xaï. b b a c c a + T/c ñoái xöùng: (a,b) R(c,d) ⇒ = ⇒ = ⇒ (c,d) R(a,b) ⇒ R coù t/c ñx. b d d b a c c e + T/c baéc caàu: Töø (a,b) R(c,d) vaø (c,d) R(e,f) suy ra = vaø = b d d f a e do ñoù ta coù = ⇒ (a,b) R(e,f) ⇒ R coù t/c baéc caàu. b f Vaäy R laø moät quan heä töông ñöông treân X. c a a Lôùp töông ñöông (a,b) = {(c,d) ∈ X | (c,d)R(a,b)} = {(c,d) ∈ X | = } ↔ d b b 28 Bieân soaïn: Tröôøng Sôn
  30. Chöông 2 – Taäp hôïp, pheùp ñeám, quan heä Toaùn öùng duïng trong Tin hoïc a Taäp thöông X/R = { (a,b) | (a,b)∈X } ≅ { | a∈Z, b∈N*} = Q - taäp caùc soá höõu tæ. b 2.25 a) Töï chöùng minh. b) Lôùp töông ñöông laø ñöôøng thaúng song song vôùi truïc tung Oy. Vaäy X/S = {d | d// Oy} – taäp hôïp caùc ñöôøng thaúng d song song vôùi truïc tung Oy. Bieân soaïn: Tröôøng Sôn 29