Giáo trình Toán ứng dụng trong tin học

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 m eänh ñeà sau: a) pi = 2 vaø toång caùc goùc cuûa moät tam giaùc baèng 180o. b) pi = 3,1416 keùo theo toång caùc goùc cuûa moät tam giaùc baèng 170o. c) pi = 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. 1 – Logic meänh ñeà Toaùn öùng duïng trong Tin hoïc Bieân soaïn: Tröôøng Sôn 11 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- Ch o bieát q u y lu aä t lo g ic n aø o ñ aõ ñ ö ôï c aù p d uï n g tr o n g moã i b ö ôù c t ö ô n g ñ ö ô n g s a u : 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. 1 – Logic meänh ñeà Toaùn öùng duïng trong Tin hoïc Bieân soaïn: Tröôøng Sôn 12 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) 1 – Logic meänh ñeà Toaùn öùng duïng trong Tin hoïc Bieân soaïn: Tröôøng Sôn 13 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: a) 02 + 11 + … + n2 = 6 )1n2)(1n(n ++ , ∀n∈ N b) 03 + 13 + … + n3 = 4 )1n(n 22 + , ∀n∈ N c) 1.2.3 + 2.3.4 + … + n(n + 1)(n + 2) = ( ) 4 3n)2n)(1n(n +++ , ∀n∈ N d) ( )( ) ( ) ( )( )2n1n4 3nn 2n1nn 1 4.3.2 1 3.2.1 1 ++ + = ++ +++ ⋯ , ∀n∈ N e) 1.1! + 2.2! + … + n.n! = (n + 1)! - 1 , ∀n∈ N f) ( ) ( )!1n 11 !1n n !3 2 !2 1 + −= + +++ ⋯ , ∀n∈ N g) (1 + a)n ≥ 1 + na, ∀n∈ N, a> -1. h) 2n > n ; ∀n∈ N. i) 2n+2 > 2n + 5 ; ∀n∈ N, n ≥ 1. 1 – Logic meänh ñeà Toaùn öùng duïng trong Tin hoïc Bieân soaïn: Tröôøng Sôn 14 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. 2 – T aäp h ôïp, pheùp ñeá m, qu an heä Toaùn öùng duïng trong Tin hoïc Bieân soaïn: Tröôøng Sôn 15 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 p haàn töû ñöôïc gheùp vôùi nh au 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) 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 t reâ n moät ñöôøng thaúng. (Taäp hôïp voâ haïn) 5) Taäp hôïp caùc nghieäm t höïc cuûa phöông trình x 2 + 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, ….} 3/ Taäp hôïp soá höõu tyû: Q = { q p | p, q ∈ Z , q ≠ 0 } Caùc soá höõu tyû coù theå vieá t thaønh caùc soá th aäp phaân höõu haïn hay voâ haïn tuaàn hoaøn. Chaúng haïn: 4 3 = 0,75 ; 3 4 = 1,33333… = 1,(3) 4/ Taäp hôïp soá voâ tyû: Moät soá voâ tyû coù theå vieát thaønh moät soá t haäp phaân voâ haïn khoâng tuaàn hoaøn. Chaúng haïn: 2 = 1,414213563… ; pi = 3,141592653 5897932384626433832795… 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} a b c 2 – T aäp h ôïp, pheùp ñeá m, qu an heä Toaùn öùng duïng trong Tin hoïc Bieân soaïn: Tröôøng Sôn 16 I.4- Quan heä giöõa caùc taäp hôïp: 1/ Taäp hôïp con: Taäp A l aø 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: CA CB BA ⊂⇒    ⊂ ⊂ 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à t aäp hôïp B vaø ngöôïc laïi thì A = B. A = B ⇔    ⊂ ⊂ AB BA 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). 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 } Ví dụ: Cho A = [1 ; 3] vaø B = (2 ;4). 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 bao goàm taát caû caùc phaàn töû thuoäc A nhöng khoâng thuoäc 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): Cho A ⊂ E; taäp E \ A goïi laø taäp buø cuûa A trong E vaø kyù hieäu laø CEA hay 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 s o á 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 A B A B A B A E A 2 – T aäp h ôïp, pheùp ñeá m, qu an heä Toaùn öùng duïng trong Tin hoïc Bieân soaïn: Tröôøng Sôn 17 4/ A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) (tính chaát phaân phoái ) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) 5/ A B A B=∪ ∩ ; A B A B=∩ ∪ (Luaät De Mo rgan) 6/ A ∪ ∅ = A ; A ∩ E = A (tính chaát phaàn töû t rung 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 t rò) 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| Toång quaùt: i 1 A n i= ∏ = A1x A2 x . . . x An = {(a1, a2, . . . , an) | ai∈ Ai } Ví duï: a/ A = { 1, 2, 3 }; B = {a, b } 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| b/ R2 = R x R = { (x, y) vôùi x, y ∈ R } laø maët ph aú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ø m 1+ 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 dan h 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 V 1, V2 (coøn goïi laø hai giai ñ oïan). V 1 coù m caùch thöïc hieän; V 2 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 V 1, 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, A i ≠ Þ. Ta coù: |A1 x A2 x … x An| = |A1|.|A2|.….|An| O y x
M(x,y) 2 – T aäp h ôïp, pheùp ñeá m, qu an heä Toaùn öùng duïng trong Tin hoïc Bieân soaïn: Tröôøng Sôn 18 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 t ro ng 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 c hoïn (sau khi choïn n). V aä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 (a 1,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: a 1 coù 2 caùch choïn; a 2 coù 2 caùch choïn; …; a n coù 2 caùch choïn. Vaäy coù 2.2…2=2 n xaâu nhò phaân (a 1,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 d aøi 8 bit baét ñaàu ba èng 1 l aø 27 = 128. Soá daõy nhò phaân daøi 8 bi t keát thuùc baèng 00 l aø 26 = 65. Soá daõy nhò phaân daøi 8 bi t baét ñaàu 1 vaø keát thuùc 0 0 laø 25 = 32 Vaäy toång soá daõy nhò phaân caàn tìm laø 128+64+3 2 = 160 Chuù yù : nguyeân lyù buø t röø 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 l aãn Phaùp vaên. Giaûi : goïi A, B laàn löôït l aø taäp sinh vieân ch oï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ø 18 0 - 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 s inh v ieâ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 h oï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 2 – T aäp h ôïp, pheùp ñeá m, qu an heä Toaùn öùng duïng trong Tin hoïc Bieân soaïn: Tröôøng Sôn 19 Ví duï 4: Hoûi trong taäp X = { 1, 2, … , 10000 } coù bao n hieâ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 ∩ A 4 ∩ A7| = 10000 - [10000/3 ] - [10000/4] - [10000/7] + [10000/12] + [10000/2 1] + [10000/28 ] - [10000 /84] = 4286 II.1.4. NGUYÊN LÝ DIRICHLET II.1.4.1. Mở ñầu: Giả sử có một ñàn chim bồ câu bay vào chuồng. Nếu số chim nhiều hơn số ngăn chuồng thì ít nhất trong một ngăn có nhiều hơn một con chim. Nguyên lý này dĩ nhiên là có thể áp dụng cho các ñối tượng không phải là chim bồ câu và chuồng chim. Mệnh ñề (Nguyên lý): Nếu có k+1 (hoặc nhiều hơn) ñồ vật ñược ñặt vào trong k hộp thì tồn tại một hộp có ít nhất hai ñồ vật. Chứng minh: Giả sử không có hộp nào trong k hộp chứa nhiều hơn một ñồ vật. Khi ñó tổng số vật ñược chứa trong các hộp nhiều nhất là bằng k. ðiều này trái giả thiết là có ít nhất k + 1 vật. Nguyên lý này thường ñược gọi là nguyên lý Dirichlet, mang tên nhà toán học người ðức ở thế kỷ 19. Ông thường xuyên sử dụng nguyên lý này trong công việc của mình. Ví dụ 1: a) Trong bất kỳ một nhóm 367 người thế nào cũng có ít nhất hai người có ngày sinh nhật giống nhau bởi vì chỉ có tất cả 366 ngày sinh nhật khác nhau. b) Trong kỳ thi học sinh giỏi, ñiểm bài thi ñược ñánh giá bởi một số nguyên trong khoảng từ 0 ñến 100. Hỏi rằng ít nhất có bao nhiêu học sinh dự thi ñể cho chắc chắn tìm ñược hai học sinh có kết quả thi như nhau? Theo nguyên lý Dirichlet, số học sinh cần tìm là 102, vì ta có 101 kết quả ñiểm thi khác nhau. c) Trong số những người có mặt trên trái ñất, phải tìm ñược hai người có hàm răng giống nhau. Nếu xem mỗi hàm răng gồm 32 cái như là một xâu nhị phân có chiều dài 32, trong ñó răng còn ứng với bit 1 và răng mất ứng với bit 0, thì có tất 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ó ñiều cần tìm. II.1.4.2. Nguyên lý Dirichlet tổng quát: Mệnh ñề: Nếu có N ñồ vật ñược ñặt vào trong k hộp thì sẽ tồn tại một hộp chứa ít nhất ]N/k[ ñồ vật. (Ở ñây, ]x[ là giá trị của hàm trần tại số thực x, ñó là số nguyên nhỏ nhất có giá trị lớn hơn hoặc bằng x. Khái niệm này ñối ngẫu với [x] – giá trị của hàm sàn hay hàm phần nguyên tại x – là số nguyên lớn nhất có giá trị nhỏ hơn hoặc bằng x.) Chứng minh: Giả sử mọi hộp ñều chứa ít hơn ]N/k[ vật. Khi ñó tổng số ñồ vật là 2 – T aäp h ôïp, pheùp ñeá m, qu an heä Toaùn öùng duïng trong Tin hoïc Bieân soaïn: Tröôøng Sôn 20 ≤ k (] N k [ − 1) < k N k = N. ðiều này mâu thuẩn với giả thiết là có N ñồ vật cần xếp. Ví dụ 2: a) Trong 100 người, có ít nhất 9 người sinh cùng một tháng. Xếp những người sinh cùng tháng vào một nhóm. Có 12 tháng tất cả. Vậy theo nguyên lý Dirichlet, tồn tại một nhóm có ít nhất ]100/12[= 9 người. b) Có năm loại học bổng khác nhau. Hỏi rằng phải có ít nhất bao nhiêu sinh viên ñể chắc chắn rằng có ít ra là 6 người cùng nhận học bổng như nhau. Gọi N là số sinh viên, khi ñó ]N/5[ = 6 khi và chỉ khi 5 < N/5 ≤ 6 hay 25 < N ≤ 30. Vậy số N cần 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 c aù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 nh aân): Soá hoaùn vò laø: Pn = 1.2… .n = n! (ñoïc laø: n g iai 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ø: P 3 = 3! = 6 123 132 213 231 312 321 + Soá caùch saép xeáp coù th eå ñöôïc 5 hoïc sinh ng oài c où 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 nA = n! / (n -k)! ; Hay knA = 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 34A = 4.3.2 = 24 + Coù bao nhieâu soá töï nhi eâ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á) A49 = 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öû l aø 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ù . Soá chænh hôïp (laëp ) chaäp k cuûa n phaàn töû kyù hieäu l aø knF = n k hay k nA = nk 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: 2 – T aäp h ôïp, pheùp ñeá m, qu an heä Toaùn öùng duïng trong Tin hoïc Bieân soaïn: Tröôøng Sôn 21 11 12 13 14 21 22 23 24 31 32 33 34 41 42 43 44 Vaäy 24F = 4 2 = 16 + Soá caùc soá coù 4 chöõ soá laäp töø {1,2,3,4,5,6 ,7,8,9} laø 4 9F = 9.9.9.9 = 9 4 = 6561 II.2.3. Toå hôïp chaäp k cuûa n phaàn töû a/ Ñònh nghóa: Toå hôïp c haäp k cuûa n phaàn töû laø moät caùch choïn khoâng keå thöù töï k