intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

GIÁO TRÌNH TOÁN ỨNG DỤNG TRONG TIN HỌC

Chia sẻ: Up Up | Ngày: | Loại File: PDF | Số trang:30

Thêm vào BST
Báo xấu
433
lượt xem 117
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Những nội dung chíng đề cập trong giáo trình này là: Tập hợp và quan hệ, suy luận toán học, quy nạp và đệ quy, tính toán ma trận, đại số logic, lý thuyết đồ thị và độ phức tạp tính toán. Ngoài ra những kiến thức và phương pháp toán học không thể thiếu được trong tin học ứng dụng: Tính toán và xác suất; Phương pháp tính. Để tránh trùng lặp và cồng kềnh, giáo trình không đi sâu vào việc xét những nội dung toán học đã được trình bày ở chương trình toán phổ thông như:...

Chủ đề:

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

Lưu

Nội dung Text: GIÁO TRÌNH TOÁN ỨNG DỤNG TRONG TIN HỌC

  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 http://www.ebook.edu.vn 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) 1 Bieân soaïn: Tröôøng Sôn
  3. Chöông 1 – Logic meänh ñeà http://www.ebook.edu.vn n öùng duïng trong Toaù 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 http://www.ebook.edu.vn 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ò) 3 Bieân soaïn: Tröôøng Sôn
  5. Chöông 1 – Logic meänh ñeà http://www.ebook.edu.vn n öùng duïng trong Toaù Tin hoïc p q p⇒q p∨q (p ⇒ q) ⇔ ( p ∨ q) p 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 http://www.ebook.edu.vn 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. 5 Bieân soaïn: Tröôøng Sôn
  7. Chöông 1 – Logic meänh ñeà http://www.ebook.edu.vn n öùng duïng trong Toaù 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. Tích a.b = 0 (suy ra a = 0 hoaëc b = 0) b/ 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 http://www.ebook.edu.vn 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) : mñ ñuùng. (2) • ∃n∈N, P(n) = “Coù soá töï nhieân n laø soá nguyeân toá” : mñ sai. • ∃!n∈N, P(n) = “Coù duy nhaát 1 soá töï nhieân n laø soá nguyeân toá” Phuû ñònh cuûa (1) ta ñöôïc: : mñ ñuùng. ∃n∈N, P(n) = “Coù soá töï nhieân n khoâng phaûi laø soá nguyeân toá” Phuû ñònh cuûa (2) ta ñöôïc: : mñ sai. ∀n∈N, P(n) = “Moïi soá töï nhieân n khoâng phaûi laø soá nguyeân toá” 7 Bieân soaïn: Tröôøng Sôn
  9. Chöông 1 – Logic meänh ñeà http://www.ebook.edu.vn n öùng duïng trong Toaù 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 http://www.ebook.edu.vn 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 9 Bieân soaïn: Tröôøng Sôn
  11. Chöông 1 – Logic meänh ñeà http://www.ebook.edu.vn n öùng duïng trong Toaù 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 http://www.ebook.edu.vn 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. 11 Bieân soaïn: Tröôøng Sôn
  13. Chöông 1 – Logic meänh ñeà http://www.ebook.edu.vn n öùng duïng trong Toaù 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 (Kí hieäu ∴laø keát luaän) tam ñoaïn 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 http://www.ebook.edu.vn 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 n (n + 3) 1 1 1 d) , ∀n∈ N + +⋯+ = n (n + 1)(n + 2) 4(n + 1)(n + 2) 1.2.3 2.3.4 e) 1.1! + 2.2! + … + n.n! = (n + 1)! - 1 , ∀n∈ N 12 n 1 f) , ∀n∈ N + +⋯+ = 1− (n + 1)! (n + 1)! 2! 3! g) (1 + a)n ≥ 1 + na, ∀n∈ N, a> -1. h) 2n > n ; ∀n∈ N. i) 2n+2 > 2n + 5 ; ∀n∈ N, n ≥ 1. 13 Bieân soaïn: Tröôøng Sôn
  15. Chöông 1 – Logic meänh ñeà http://www.ebook.edu.vn n öùng duïng trong Toaù 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 http://www.ebook.edu.vn 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} 15 Bieân soaïn: Tröôøng Sôn
  17. Chöông 2 – Taäp hôïp, pheùp ñeám, quan heä http://www.ebook.edu.vn n öùng duïng trong Toaù 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 A = {1, 2, x, y, z } ; B = {x, 1, y, z, 2 } Ví duï: 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 } A 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 } A 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 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) E 4/ Taäp hôïp buø (Hieäu hai taäp hôïp): A 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 . 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 http://www.ebook.edu.vn 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 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 ∏A Toång quaùt: = A1x A2 x . . . x An = {(a1, a2, . . . , an) | ai∈ Ai } y i 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| x O 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| 17 Bieân soaïn: Tröôøng Sôn
  19. Chöông 2 – Taäp hôïp, pheùp ñeám, quan heä http://www.ebook.edu.vn n öùng duïng trong Toaù 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 caùch choïn. Vaäy coù 2.2…2=2n 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 http://www.ebook.edu.vn 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ó 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à 19 Bieân soaïn: Tröôøng Sôn
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2