Chương 1_Logic mệnh đề

Chia sẻ: Tran Vu | Ngày: | Loại File: PDF | Số trang:14

Thêm vào BST

Báo xấu

1.417
lượt xem 376
download

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

bái giảng logic mệnh đề sưu tầm từ internet

Chủ đề:

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

Lưu

Nội dung Text: Chương 1_Logic mệnh đề

Chöông 1 – Logic meänh ñeà http://www.ebook.edu.vn 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
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
Chöông 1 – Logic meänh ñeà http://www.ebook.edu.vn 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
Chöông 1 – Logic meänh ñeà http://www.ebook.edu.vn n öùng duïng trong Toaù 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
Chöông 1 – Logic meänh ñeà http://www.ebook.edu.vn 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
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. 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
Chöông 1 – Logic meänh ñeà http://www.ebook.edu.vn 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
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
Chöông 1 – Logic meänh ñeà http://www.ebook.edu.vn 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
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
Chöông 1 – Logic meänh ñeà http://www.ebook.edu.vn 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
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 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
Chöông 1 – Logic meänh ñeà http://www.ebook.edu.vn 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 1.2.3 2.3.4 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
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

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