Chương 1: Ngôn ngữ Logic

Chia sẻ: Bach Thanh Trung | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST

Báo xấu

227
lượt xem 18
download

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

Mệnh đề-bảng chân trị: một mệnh đề là một câu phát biểu mà có thể nói ngay ra câu đó đúng hoặc sai

Chủ đề:

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

Lưu

Nội dung Text: Chương 1: Ngôn ngữ Logic

Chöông 1. Ngoân ngöõ Logic 1. NGOÂN NGÖÕ LOGIC. 1.1. Meänh ñeà - Baûng chaân trò. 1.1.1. Ñònh nghóa. Moät Meänh ñeà laø moät caâu phaùt bieåu (ñoái töôïng Toaùn hoïc) maø ta coù theå noùi ngay raèng caâu ñoù ñuùng hoaëc sai. Thí duï. “8 laø moät soá chaún” laø moät Meänh ñeà ñuùng. “3 < 2 “ laø moät Meänh ñeà sai. “x laø moät soá nguyeân, x
Chöông 1. Ngoân ngöõ Logic n meänh ñeà caàn xeùt cuøng luùc thì baûng chaân trò goàm 2n Toång quaùt neáu coù tröôøng hôïp. 1.2. Phuû ñònh cuûa moät Meänh ñeà. Phuû ñònh cuûa Meänh ñeà p laø moät meänh ñeà, kyù hieäu p coù giaù trò SAI neáu p ÑUÙNG vaø coù giaù trò ÑUÙNG neáu p SAI. Thí duï. Neáu p : “2 + 2 = 4” thì phuû ñònh cuûa p laø meänh ñeà p :” 2 + 2 ≠ 4”. p p 1 0 1 0 1.3. Caùc pheùp noái logic. Caùc meänh ñeà coù theå ñöôïc keát hôïp laïi ñeå ñöôïc moät Meänh ñeà hôïp baèng caùch söû duïng caùc pheùp noái logic. Caùc pheùp noái logic goàm coù: Pheùp noái lieàn (tuyeån) (“vaø”). q Pheùp hôïp (“hay”). q Pheùp keùo theo. q Pheùp töông ñöông. q Pheùp hôïp coù loaïi tröø. q 1.3.1. Pheùp Noái lieàn (tuyeån). Tuyeån hai meänh ñeà p vaø q kyù hieäu p ∧ q (ñoïc laø “p vaø q”) hoaëc p.q chæ coù giaù trò ÑUÙNG khi caû hai cuøng ÑUÙNG. Baûng chaân trò cuûa p ∧ q nhö sau : p q p∧ q 1 1 1 1 0 0 0 1 0 0 0 0 Thí duï: p :”3 < 5”; q : “4 ≠ 2 + 2”. Ta coù : p ∧ q :”3 < 5” vaø “4 ≠ 2 + 2” laø Meänh ñeà sai. 1.3.2. Pheùp hôïp. Hôïp cuûa hai meänh ñeà p vaø q laø meänh ñeà p∨ q (ñoïc laø “p hay q”) hoaëc p+q, coù giaù trò ÑUÙNG neáu ít nhaát moät trong hai meänh ñeà treân ÑUÙNG vaø coù giaù trò SAI neáu caû hai cuøng SAI. Tröông Myõ Dung 5
Chöông 1. Ngoân ngöõ Logic Baûng chaân trò cuûa p ∨ q nhö sau : Pp q p∨ q 1 1 1 1 0 1 0 1 1 0 0 0 Thí duï: p :”3 < 5”; q : “4 ≠ 2 + 2”. Ta coù : p∨ q :”3 < 5” vaø q : “4 ≠ 2 + 2” laø Meänh ñeà ÑUÙNG. 1.3.3. Caùc tính chaát cuûa pheùp tuyeån, pheùp hôïp. a. Luõy ñaúng p∧ p =p p∨ p =p Ñoái xöùng p∧ q = q∧ p p∨ q = q∨ p Keát hôïp p∧ ( q∧ r ) = (p∧ q) ∧ r p ∨ (q ∨ r)= (p∨ q) ∨ r p∧ p =∅ p ∨ p =I p∧ I =p p∨ I =I p∧ =∅ p∨ ∅ =p ∅ ∅ kyù hieäu meänh ñeà luoân luoân coù giaù trò SAI goïi laø NGHÒCH ÑEÀ. I kyù hieäu meänh ñeà luoân luoân coù giaù trò ÑUÙNG goïi laø CHAÂN ÑEÀ. b. Tính phaân phoái. p ∧ (q ∨ r) = (p ∧ q) ∨ (p ∧ q). p ∨ (q ∧ r) = (p ∨ q) ∧ (p ∨ q). c. Qui luaät DE MORGAN. ( p∧ q) = p ∨ q (p∨ q) = p ∧ q Chuù yù. Taäp hôïp caùc meänh ñeà vôùi caùc pheùp noái ∧ , ∨ vaø pheùp phuû ñònh thoûa caùc tính chaát neâu treân goïi laø moät heä ñaïi soá BOOLE. 1.3.4. Pheùp keùo theo logic. Pheùp keùo theo logic cuûa meänh ñeà p vaø meänh ñeà q kyù hieäu p ⇒ q (ñoïc laø “neáu p thì q”) chæ SAI khi p ÑUÙNG vaø q SAI. Baûng chaân trò cuûa p ⇒ q nhö sau : p q p⇒q 1 1 1 1 0 0 0 1 1 0 0 1 Tröông Myõ Dung 6
Chöông 1. Ngoân ngöõ Logic Thí duï: ”3 < 5” ⇒ “3 < 7” laø Meänh ñeà ÑUÙNG. “4:soá nguyeân toá”⇒ø “TP.HCM laø thuû ñoâ cuûa VN” laø Meänh ñeà ÑUÙNG. “5:soá nguyeân toá” vaø “TP.HCM laø thuû ñoâ cuûa VN” laø Meänh ñeà SAI. Chuù yù. a. Pheùp keùo theo logic khoâng coù yù nghóa gì veà nguyeân nhaân vaø haäu quaû ñoái vôùi p vaø q. b. Neáu (p ⇒ q) ÑUÙNG vaø p ÑUÙNG thì q phaûi ÑUÙNG. Neáu (p ⇒ q) ÑUÙNG vaø q SAI thì p phaûi SAI. c. Neáu p ÑUÙNG, muoán chöùng minh (p ⇒ q) ÑUÙNG thì ta phaûi chöùng minh q ÑUÙNG. CAÙC TÍNH CHAÁT CUÛA PHEÙP KEÙO THEO LOGIC. (p⇒ p) = I (p ⇒q) = (q ⇒ p) [ (p⇒q) vaø (q⇒r)] ⇒ ( p⇒r) laø moät chaân ñeà. (p⇒q) = (p ∨ q). 1.3.5. Pheùp töông ñöông Logic. Pheùp töông ñöông cuûa hai meänh ñeà p vaø q laø meänh ñeà kyù hieäu p⇔q (ñoïc laø “p töông ñöông q” hoaëc “p neáu vaø chæ neáu q” xaùc ñònh bôûi (p⇒q) vaø (q⇒p). Baûng chaân trò cuûa p ⇔ q nhö sau : p q p⇒q q⇒p p⇔q 1 1 1 1 1 1 0 0 1 0 0 1 1 0 0 0 0 1 1 1 Nhö vaäy: + Neáu p = q thì (p ⇔q) ÑUÙNG vaø ngöôïc laïi. + Neáu (p ⇔ q) ÑUÙNG thì p = q. Tính chaát: + p ⇔ p laø moät chaân ñeà. + p⇔q = q⇔p + (p⇔q) vaø (q⇔r) ⇒ ( p⇔r) laø moät chaân ñeà. 1.3.6. Pheùp hôïp coù loaïi tröø. Ta goïi pheùp hôïp coù loaïi tröø cuûa hai meänh ñeà p vaø q laø meänh ñeà p⊕q (ñoïc laø “p chæ hoaëc q”) coù giaù trò ÑUÙNG neáu chæ moät trong hai meänh ñeà ñoù ÑUÙNG vaø coù giaù trò sai neáu caû hai cuøng SAI hoaëc cuøng ÑUÙNG. Tröông Myõ Dung 7
Chöông 1. Ngoân ngöõ Logic Baûng chaân trò cuûa p ⊕ q nhö sau : p qP p p ⊕ q 1 1 0 1 0 1 0 1 1 0 0 0 Tính chaát: p⊕p =I p⊕q = q⊕p p⊕q = p⊕q = (p⊕q) = (p⇔q). p⊕(q⊕r) = (p⊕q) ⊕r = p⊕q⊕r. 1.4. Xaùc ñònh moät meänh ñeà hôïp coù baûng chaân trò cho tröôùc. Giaû söû ta coù hai meänh ñeà p, q cho saún. Ta muoán tìm moät meänh ñeà R do p, q (vaø caû p, q) hôïp thaønh baèng caùc töø noái ∨ , ∧ sao cho giaù trò ÑUÙNG, SAI cuûa R ñöôïc cho bôûi baûng: p qP p R 1 1 0 1 0 1 0 1 1 0 0 0 Phöông Phaùp. 1. Chuù yù tröôøng hôïp R coù giaù trò ÑUÙNG (haøng 2 vaø 3). 2. Trong moãi tröôøng hôïp ôû böôùc 1, ta tìm Meänh ñeà (M.Ñ) Tuyeån ÑUÙNG trong moãi tröôøng hôïp ñoù vaø SAI trong caùc tröôøng hôïp khaùc. Haøng 2 cho M.Ñ tuyeån p ∧ q. Haøng 3 cho M.Ñ tuyeån p ∧ q. 3. Hôïp caùc meänh ñeà tuyeån ôû Böôùc 2, ta ñöôïc meänh ñeà R phaûi tìm laø: R = (p ∧ q) ∨ ( p ∧ q) Ñeå kieåm tra laïi, ta laäp baûng chaân trò: p q p q p ∧ q p∧ q ( p∧q) ∨ ( p∧ q) 1 1 0 0 0 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 0 0 1 1 0 0 0 Thí duï. Moät ngöôøi tuø bò giam ñöôïc cho moät cô hoäi ñeå thoaùt. Phoøng giam coù hai cöûa: Moät cöûa thoaùt vaø moät cöûa daãn ñeán chuoàng coïp. Moãi cöûa coù moät ngöôøi canh, nhöng ngöôøi naøy chæ traû lôøi caâu hoûi baèng ÑUÙNG hay SAI. Moät trong hai ngöôøi ñoù thì luoân luoân noùi thaät, vaø ngöôøi kia thì luoân luoân noùi doái. Ngöôøi tuø khoâng bieát ai laø ngöôøi noùi thaät, cöûa naøo laø cöûa thoaùt vaø anh chæ ñöôc pheùp ñaët moät caâu hoûi. Vaäy anh phaûi ñaët caâu hoûi nhö theá naøo ñeå thoaùt ra ñöôïc? Tröông Myõ Dung 8
Chöông 1. Ngoân ngöõ Logic Giaûi. Ta xeùt hai meänh ñeà sau: p: “Cöûa Anh giöõ laø cöûa ra” q:”Anh laø ngöôøi noùi thaät”. Nhö vaäy coù 4 tình huoáng toùm taét trong baûng sau: p q 1 1 1 0 0 1 0 0 Ta muoán raèng khi choïn moät trong hai cöûa vaø ñaët caâu hoûi cho ngöôøi giöõ cöûa: q Neáu traû lôøi ÑUÙNG theo cöûa ñoù ra. q Neáu traû lôøi SAI thì ra cöûa kia. Goïi R laø meänh ñeà hôïp töø p vaø q muoán tìm. Caâu traû lôøi vaø giaù trò cuûa R trong moãi tröôøng hôïp seõ nhö hình sau ñaây: Ppp p q Traû lôøi R 1 1 ÑUÙNG 1 1 0 SAI 0 0 1 SAI 0 0 0 ÑUÙNG 1 Nhö vaäy meänh ñeà R phaûi tìm coù daïng R = (p∧ q) ∨ ( p∧q) vaø ñöôïc phaùt bieåu nhö sau: “Cöûa anh giöõ laø cöûa ra vaø anh noùi thaät” Hay “Cöûa anh giöõ khoâng phaûi laø cöûa ra vaø anh noùi doái”. Caên cöù treân baûng chaân trò treân ta thaáy R ÑUÙNG khi p vaø q cuøng ÑUÙNG hoaëc cuøng SAI, do ñoù cuõng coù theå vieát R = (p ⇔ q) vaø ñöôïc phaùt bieåu nhö sau: “Cöûa anh giöõ laø cöûa ra neáu vaø chæ neáu anh noùi thaät”. 1.5. ÖÙng duïng cuûa ngoân ngöõ logic. 1.5.1. Pheùp suy luaän ñuùng. Moät pheùp suy luaän laø moät caâu phaùt bieåu trong ñoù moät meänh ñeà q ñöôïc suy töø caùc meänh ñeà p1 ,p2,…, pn. Caùc meänh ñeà p1 ,p2,…, pn goïi laø giaû thieát, Meänh ñeà q goïi laø keát luaän. Tröông Myõ Dung 9
Chöông 1. Ngoân ngöõ Logic Pheùp suy luaän ñöôïc kyù hieäu: p1 p2 Kyù hieäu KL ñoïc laø “vaäy”, “do ñoù”, “suy ra” . pn KL q Moät pheùp suy luaän treân goïi laø ÑUÙNG neáu meänh ñeà: (p1 ,p2,…, pn ⇒ q) laø moät chaân ñeà. Thí duï 1. Ta xem suy luaän sau: Neáu baïn truùng soá thì baïn seõ giaøu coù Neáu baïn giaøu coù thì baïn seõ haïnh phuùc. KL Neáu baïn truùng soá thì baïn coù haïnh phuùc. Suy luaän treân coù daïng: p⇒q q⇒r KL p ⇒ r Maø ta bieát meänh ñeà: {(p ⇒ q) ∧ (q ⇒ r)} ⇒ (p ⇒ r) laø moät chaân ñeà. Vaäy suy luaän treân laø suy luaän ñuùng. Thí duï 2. Ta xem suy luaän sau: Huùt thuoác coù lôïi cho söùc khoûe Neáu Huùt thuoác coù lôïi cho söùc khoûe thì thaày thuoác khuyeân neân huùt thuoác. KL Thaày thuoác khuyeân neân huùt thuoác. Suy luaän treân coù daïng: p p⇒q KL q Suy luaän treân laø moät suy luaän ñuùng vì meänh ñeà: {p ∧ (p ⇒ q)} ⇒ q laø moät chaân ñeà. Vaäy suy luaän treân laø suy luaän ñuùng, maëc duø keát luaän sai. Thí duï 3. Suy luaän sau ñaây coù ñuùng khoâng? Neáu thueá giaûm thì lôïi töùc taêng Lôïi töùc taêng . KL Thueá giaûm. Suy luaän treân coù daïng: p⇒q q . KL p Tröông Myõ Dung 10
Chöông 1. Ngoân ngöõ Logic Laäp baûng chaân trò meänh ñeà treân vaø {(p ⇒ q) ∧ q} ⇒ p. p q p⇒q (p⇒q) ∧ q {(p⇒q) ∧ q}⇒ p 1 1 1 1 1 1 0 0 0 1 0 1 1 1 0 0 0 1 0 1 Vaäy suy luaän treân khoâng ñuùng. 1.5.2. Maïch (Ñoùng/ môû) Ñieän. A• L • Moät nuùt ngaét coù theå ñöôïc bieåu dieãn baèng moät meänh ñeà vaø ngöôïc laïi. Söï töông öùng 1-1 nhö vaäy ñöôïc aùp duïng ñeå thieát keá caùc maïch ñieän môû trong maïch ñieän môû trong maïch ñieän cuõng nhö trong ñieän thoaïi. Caùc pheùp noái logic AND, OR, NOT ñöôïc bieåu dieãn baèng caùc maïch ñoùng môû nhö sau: A• OR B AND A • • • • B• NOT A‘ • • A Tröông Myõ Dung 11
Chöông 1. Ngoân ngöõ Logic Thí duï 1. Thieát keá moät maïch ñoùng môû coù 2 coâng taéc ñeå ñieàu khieån moät boùng ñeøn. Giaû söû P vaø Q ñöôïc thieát keá : • 1 1 1 1 • • • 0 0 0 0 Q P Q P Saùng Saùng • 1 1 • 1 1 • 0 0 • 0 0 Q P P Q Toái Toái Caùc coâng taéc P vaø Q ñöôïc bieåu dieãn baèng caùc meänh ñeà : p : nuùt P ôû vò trí 1 ‘’ q : nuùt Q ôû vò trí 1 ‘’ Ta seõ tìm meänh ñeà S sao cho baûng chaân trò cuûa S cho bôûi : p q S Theo phöông phaùp ôû ñoaïn 4 ta tìm ñöôïc S : 1 1 1 S = (p∧ q) ∨ ( p∧q). 1 0 0 0 1 0 0 0 1 Maïch ñieän ñöôc thieát keá nhö sau: • • • • • • Thí duï 2: Ba ngöôøi baïn A, B, C cuøng bieåu quyeát mua moät moùn quaø giaù trò 80000, A coù 5000 ñ, B coù 4000 ñ vaø C coù 3000 ñ. Moãi ngöôøi seõ bieåu quyeát coù hoaëc khoâng. Bieåu quyeát coù seõ ñoùng soá tieàn mình coù. Neáu toång soá tieàn ñaït ñöôïc trong cuoäc bieåu quyeát baèng hay vöôït 8000 ñ thì hoï seõ mua moùn quaø ñoù. Haõy tìm moät meänh ñeà cho bieát trong tröôøng hôïp Tröông Myõ Dung 12
Chöông 1. Ngoân ngöõ Logic naøo thì bieåu quyeát thaønh coâng. Neáu cuoäc bieåu quyeát ñöôïc thöïc hieän baèng caùch moãi ngöôøi aán moät nuùt ñieän neáu ñoàng yù, thì maïch ñieän seõ ñöïôc thieát keá nhö theá naøo? Ta coù baûng caùc tröôøng hôïp cuûa cuoäc bieåu quyeát coù theå xaûy ra nhö sau: Nhö vaäy meänh ñeà S seõ laø: A B C S S= (A∧B∧ C) ∨ ( A ∧ B∧ C) ∨ ( A ∧ B∧C) 0 0 1 0 Meänh ñeà S coù theå ñöôïc ruùt goïn: 0 0 0 0 S=(A∧B∧ C) ∨ ( A ∧ B∧ C) ∨ ( A ∧ B∧C) ∨ ( A ∧ B∧ C) 0 1 1 0 = [A ∧ C ∧ ( B ∨ B) ] ∨ [ A ∧ B ∧ ( C ∨ C)] 0 1 0 0 = (A∧ C ) ∨ ( A ∧ B) 1 0 1 1 S= A ∧ (C ∨ B) 1 0 0 0 Vaäy cuoäc bieåu quyeát seõ thaønh coâng neáu A bieåu quyeát 1 1 1 1 coù vaø B hay C bieåu quyeát coù . 1 1 0 1 1.5.3 Maïch logic (Logic Circuits). P∪Q A A∩ B P B OR NOT AND Thí duï 1 – Thieát keá maïch logic ñeå so saùnh 2 bít vôùi nhau - Neáu 2 bit gioáng nhau keát quaû laø 0. - Neáu 2 bit khaùc nhau keát quaû laø 1. Ta coù baûng chaân trò cho maïch so saùnh 2 bit : Vaøo Ra A B K 0 0 0 Nhö vaäy K = (A. B) + (A. B) 0 1 1 1 0 1 1 1 0 Tröông Myõ Dung 13
Chöông 1. Ngoân ngöõ Logic Vaø maïch logic thöïc hieän vieäc so saùnh nhö sau: A . B A • B A . B + A. B Comparator A . B B B Thí duï 2. Maïch logic ñeå thöïc hieän pheùp coäng vaø nhaân 2 bit. Ta coù baûng coäng vaø nhaân nhö sau : Vaøo Ra A B S P 0 0 0 0 Nhö vaäy S = A. B + A .B 0 1 1 0 P= A.B 1 0 1 0 1 1 0 1 Maïch logic ñeå thöïc hieän pheùp coäng vaø nhaân nhö sau : A A .B A B B S =A . B+ A . B B A .B P=A.B Tröông Myõ Dung 14