Giáo trình Toán rời rạc: Phần 1 - TS. Đỗ Văn Nhơn (biên soạn)

Chia sẻ: Hoa La Hoa | Ngày: | Loại File: PDF | Số trang:120

Thêm vào BST

Báo xấu

318
lượt xem 88
download

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

Giáo trình Toán rời rạc của TS. Đỗ Văn Nhơn gồm 6 chương, được chia thành hai phần. Phần 1 giới thiệu đến bạn đọc nội dung từ chương 1 đến chương 3 về logic, logic - các phép chứng minh và các phép đếm.

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 rời rạc: Phần 1 - TS. Đỗ Văn Nhơn (biên soạn)

Chöông 1: LOGIC I. Pheùp tính meänh ñeà 1.1 Khaùi nieäm meänh ñeà vaø chaân trò Caùc ñoái töôïng cô baûn maø chuùng ta khaûo saùt ôû ñaây laø caùc phaùt bieåu hay caùc meänh ñeà. Tuy nhieân trong chöông naày ta chæ xeùt ñeán caùc meänh ñeà toaùn hoïc, vaø chuùng ta noùi vaén taét caùc meänh ñeà toaùn hoïc laø caùc meänh ñeà. Ñoù laø nhöõng phaùt bieåu ñeå dieãn ñaït moät yù töôûng troïn veïn vaø ta coù theå khaúng ñònh moät caùch khaùch quan laø noù ñuùng hoaëc sai. Tính chaát coát yeáu cuûa moät meänh ñeà laø noù ñuùng hoaëc sai, vaø khoâng theå vöøa ñuùng vöøa sai. Giaù trò ñuùng hoaëc sai cuûa moät meänh ñeà ñöôïc goïi laø chaân trò cuûa meänh ñeà. Veà maët kyù hieäu, ta thöôøng duøng caùc maãu töï (nhö p, q, r, ...) ñeå kyù hieäu cho caùc meänh ñeà, vaø chuùng cuõng ñöôïc duøng ñeå kyù hieäu cho caùc bieán logic, töùc laø caùc bieán laáy giaù trò ñuùng hoaëc sai. Chaân trò “ñuùng” thöôøng ñöôïc vieát laø 1, vaø chaân trò “sai” ñöôïc vieát laø 0. Ví duï 1: Caùc phaùt bieåu sau ñaây laø caùc meänh ñeà (toaùn hoïc). 1. 6 laø moät soá nguyeân toá. 2. 5 laø moät soá nguyeân toá. 3. -3 < 2 4. Tam giaùc caân coù hai goùc baèng nhau. 5. H2O laø moät axít. -1-
Caùc meänh ñeà 2, 3, vaø 4 trong ví duï treân laø nhöõng meänh ñeà ñuùng. Noùi caùch khaùc chaän trò cuûa caùc meänh ñeà naày laø ñuùng. Caùc meänh ñeà 1, 5 laø nhöõng meänh ñeà sai. Ví duï 2 : Caùc phaùt bieåu sau ñaây khoâng phaûi laø caùc meänh ñeà (toaùn hoïc) vì tính ñuùng sai cuûa chuùng khoâng xaùc ñònh. 1. Ai ñang ñoïc saùch? (moät caâu hoûi) 2. Haõy ñoùng cöûa laïi ñi! 3. Anh ta raát thoâng minh. 4. Cho x laø moät soá nguyeân döông. 5. a laø moät soá chính phöông. 6. x + y = z. Trong vieäc khaûo saùt caùc meänh ñeà, ngöôøi ta coøn phaân ra laøm hai loaïi: meänh ñeà sô caáp (elementary), meänh ñeà phöùc hôïp (compound). Meänh ñeà sô caáp laø caùc “nguyeân töû” theo nghóa laø noù khoâng theå ñöôïc phaân tích thaønh moät hay nhieàu (töø hai trôû leân) meänh ñeà thaønh phaàn ñôn giaûn hôn. Coøn meänh ñeà phöùc hôïp laø meänh ñeà ñöôïc taïo thaønh töø moät hay nhieàu meänh ñeà khaùc baèng caùch söû duïng caùc lieân keát logic nhö töø “khoâng” duøng trong vieäc phuû ñònh moät meänh ñeà, caùc töø noái: “vaø”, “hay”, “hoaëc”, “suy ra”, v.v.... Ví duï: Xeùt caùc meänh ñeà sau ñaây. p = “15 chia heát cho 3”. q = “2 laø moät soá nguyeân toá vaøø laø moät soá leû”. Ta coù p laø moät meänh ñeà sô caáp. Nhöng q laø moät meänh ñeà phöùc hôïp, vì meänh ñeà q ñöôïc taïo thaønh töø hai meänh ñeà “2 laø moät soá nguyeân toá” vaø “2øø laø moät soá leû” nhôø vaøo lieân keát logic “vaø”. -2-
1.2 Caùc pheùp toaùn meänh ñeà Ñieàu maø chuùng ta quan taâm ôû ñaây khoâng phaûi laø xaùc ñònh tính ñuùng hoaëc sai cuûa moät meänh ñeà sô caáp. Bôûi vì nhöõng meänh ñeà naày thöôøng laø nhöõng phaùt bieåu noùi leân moät yù töôûng naøo ñoù trong moät phaïm vi chuyeân moân nhaát ñònh. Vaán ñeà maø ta quan taâm ôû ñaây laø laøm theá naøo ñeå tính toaùn chaân trò cuûa caùc meänh ñeà phöùc hôïp theo caùc meänh ñeà sô caáp caáu thaønh meänh ñeà phöùc hôïp ñoù nhôø vaøo caùc pheùp toaùn logic. Caùc pheùp toaùn logic ôû ñaây laø caùc kyù hieäu ñöôïc duøng thay cho caùc töø lieân keát logic nhö “khoâng”, “vaø”, “hay”, “hoaëc”, “suy ra” hay “neáu ... thì ...”, “neáu vaø chæ neáu”. Caùc pheùp toaùn logic ñöôïc ñònh nghóa baèng baûng chaân trò (truth table). Baûng chaân trò chæ ra roõ raøng chaân trò cuûa meänh ñeà phöùc hôïp theo töøng tröôøng hôïp cuûa caùc chaân trò cuûa caùc meänh ñeà sô caáp taïo thaønh meänh ñeà phöùc hôïp. Baûng chaân trò cuûa caùc pheùp toaùn logic taát nhieân laø phaûn aùnh ngöõ nghóa töï nhieân cuûa caùc töø lieân keát töông öùng. Veà maët töï nhieân cuûa ngoân ngöõ, trong nhieàu tröôøng hôïp cuøng moät töø nhöng coù theå coù nghóa khaùc nhau trong nhöõng ngöõ caûnh khaùc nhau. Do ñoù, baûng chaân trò khoâng theå dieãn ñaït moïi nghóa coù theå coù cuûa töø töông öùng vôùi kyù hieäu pheùp toaùn. Ñieàu naày cho thaáy raèng ñaïi soá logic laø roõ raøng hoaøn chænh theo nghóa laø noù cho ta moät heä thoáng logic ñaùng tin caäy. Ñaïi soá logic coøn ñaëc bieät quan troïng trong vieäc thieát keá maïch cho maùy tính. Baûng chaân trò khoâng chæ duøng ñeå keâ ra söï lieân heä chaân trò giöõa meänh ñeà phöùc hôïp vôùi chaân trò cuûa caùc meänh ñeà sô caáp caáu thaønh noù, maø baûng chaân trò coøn ñöôïc duøng vôùi muïc ñích roäng hôn: lieät keâ söï lieân heä -3-
chaân trò giöõa caùc meänh vôùi caùc meänh ñeà ñôn giaûn hôn caáu thaønh chuùng. 1.2.1 Pheùp phuû ñònh Cho p laø moät meänh ñeà, chuùng ta duøng kyù hieäu  p ñeå chæ meänh ñeà phuû ñònh cuûa meänh ñeà p. “Söï phuû ñònh” ñöôïc ñònh nghóa bôûi baûng chaân trò sau ñaây: p p 1 0 0 1 Kyù hieäu  ñöôïc ñoïc laø “khoâng” . Trong moät soá saùch khaùc, ngöôøi ta coøn duøng caùc kyù hieäu sau ñaây ñeå chæ meänh ñeà phuû ñònh cuûa moät meänh ñeà p : ~p, p . Trong coät thöù nhaát cuûa baûng chaân trò, ta lieät keâ ñaày ñuû caùc tröôøng hôïp chaân trò coù theå coù cuûa meänh ñeà p. ÔÛ coät thöù hai keâ ra chaân trò töông öùng cuûa meänh ñeà  p theo töøng tröôøng hôïp chaân trò cuûa meänh ñeà p. Ñònh nghóa naày phuø hôïp vôùi ngöõ nghóa töï nhieân cuûa söï phuû ñònh : Meänh ñeà phuû ñònh  p coù chaân trò laø ñuùng (1) khi meänh ñeà p coù chaân trò sai (0), ngöôïc laïi  p coù chaân trò sai (0) khi p coù chaân trò ñuùng (1). Ví duï 1 : Neáu ta kyù hieäu p laø meänh ñeà “5 < 3” thì p laø kyù hieäu cho meänh ñeà “5  3”. Trong tröôøng hôïp naày p sai, p ñuùng. Ta coù theå vieát p = 0, p = 1. Ví duï 2 : Chæ ra raèng (p) vaø p luoân coù cuøng chaân trò. -4-
Giaûi. Laäp baûng chaân trò cuûa meänh ñeà (p): p p (p) 0 1 0 1 0 1 Treân moãi doøng giaù trò trong baûng chaân trò ta coù chaân trò cuûa p vaø (p) ñeàu baèng nhau (so saùnh coät 1 vaø coät 3 trong baûng). Vaäy (p) vaø p coù cuøng chaân trò. Ta cuõng noùi raèng (p) töông ñöông logic vôùi p. Meänh ñeà (p) thöôøng ñöôïc vieát laø p, vì ñieàu naày khoâng coù gì gaây ra söï nhaàm laãn. 1.2.2 Pheùp hoäi Cho p vaø q laø hai meänh ñeà. Ta kyù hieäu meänh ñeà “p vaø q” laø pq. Pheùp “vaø”, kyù hieäu laø , ñöôïc ñònh nghóa bôûi baûng chaân trò sau ñaây: p q pq 0 0 0 0 1 0 1 0 0 1 1 1 Chaân trò cuûa meänh ñeà p  q phuï thuoäc vaøo caùc chaân trò cuûa 2 meänh ñeà p, q. Ta coù 4 tröôøng hôïp chaân trò cuûa p  q öùng vôùi 4 tröôøng hôïp chaân trò cuûa caëp meänh ñeà (p,q) laø (0,0), (0,1), (1,0), (1,1). Trong 4 -5-
tröôøng hôïp chæ coù moät tröôøng hôïp meänh ñeà p  q ñuùng, ñoù laø tröôøng hôïp p ñuùng vaø q ñuùng. Qua ñònh nghóa treân ta nhaän thaáy raèng caùc meänh ñeà pq vaø qp luoân luoân coù cuøng chaân trò, hay töông ñöông logic. Tuy nhieân, trong ngoân ngöõ thoâng thöôøng caùc meänh ñeà “p vaø q” vaø “q vaø p” ñoâi khi coù yù nghóa khaùc nhau theo ngöõ caûnh. Ví duï : Cho caùc meänh ñeà p = “5 > -7”, q = “2721 laø moät soá nguyeân toá”, r = “moät tam giaùc ñeàu cuõng laø moät tam giaùc caân”. Khi ñoù ta coù : p  q = 0 (p  q sai, töùc laø coù chaân trò baèng 0, vì p = 1 vaø q = 0), p  r = 1 (p  r ñuùng, töùc laø coù chaân trò baèng 1, vì p = 1 vaø r = 1). Nhaän xeùt: Baèng caùch laäp baûng chaân trò, ta coù: 1. Caùc meänh ñeà p vaø p  p luoân coù cuøng chaân trò. 2. Meänh ñeà p  p luoân coù chaân trò baèng 0 (töùc laø moät meänh ñeà luoân sai). Moät meänh ñeà phöùc hôïp luoân luoân coù chaân trò laø sai trong moïi tröôøng hôïp chaân trò cuûa caùc meänh ñeà sô caáp taïo thaønh noù seõ ñöôïc goïi laø moät söï maâu thuaån. 1.2.3 Pheùp tuyeån -6-
Cho p vaø q laø hai meänh ñeà. Ta kyù hieäu meänh ñeà “p hay q” laø p  q. Pheùp “hay”, kyù hieäu laø , ñöôïc ñònh nghóa bôûi baûng chaân trò sau ñaây: p q pVq 0 0 0 0 1 1 1 0 1 1 1 1 Chaân trò cuûa meänh ñeà p  q phuï thuoäc vaøo caùc chaân trò cuûa 2 meänh ñeà p, q. Trong 4 tröôøng hôïp chæ coù moät tröôøng hôïp meänh ñeà p  q sai, ñoù laø tröôøng hôïp p sai vaø q sai. Qua ñònh nghóa treân ta nhaän thaáy raèng caùc meänh ñeà p  q vaø q  p luoân luoân coù cuøng chaân trò, hay töông ñöông logic. Ví duï 1: Cho caùc meänh ñeà p = “5 > 7”, q = “2721 laø moät soá nguyeân toá”, r = “moät tam giaùc ñeàu cuõng laø moät tam giaùc caân”. Khi ñoù ta coù : p V q = 0, p V r = 1. Nhaän xeùt : 1. Cho p laø moät meänh ñeà. Laäp baûng chaân trò cuûa meänh ñeà p  p p p p V p 0 1 1 1 0 1 -7-
ta coù meänh ñeà p V p luoân luoân ñuùng. 2. Ngöôøi ta coøn söû duïng pheùp “hoaëc” trong vieäc lieân keát caùc meänh ñeà. Cho p vaø q laø hai meänh ñeà. Ta kyù hieäu meänh ñeà “p hoaëc q” laø p V q. Pheùp “hoaëc”, kyù hieäu laø V, ñöôïc ñònh nghóa bôûi baûng chaân trò sau ñaây: p q pVq 0 0 0 0 1 1 1 0 1 1 1 0 Pheùp “hoaëc” coøn ñöôïc goïi laø “hay loaïi tröø”. Chaân trò cuûa meänh ñeà p V q phuï thuoäc vaøo caùc chaân trò cuûa 2 meänh ñeà p, q : meänh ñeà p V q ñuùng khi trong 2 meänh ñeà p vaø q coù moät meänh ñeà ñuùng, moät meänh ñeà sai. 1.2.4 Pheùp keùo theo Pheùp keùo theo, kyù hieäu bôûi , ñöôïc ñöa ra ñeå moâ hình cho loaïi phaùt bieåu ñieàu kieän coù daïng : “neáu . . . thì . . .”. Cho p vaø q laø 2 meänh ñeà, ta seõ vieát p  q ñeå dieãn ñaït phaùt bieåu “neáu p thì q”. Pheùp toaùn keùo theo  ñöôïc ñònh nghóa bôûi baûng chaân trò sau ñaây: p q pq 0 0 1 0 1 1 1 0 0 1 1 1 -8-
Meänh ñeà p  q, ñöôïc ñoïc laø “neáu p thì q”, coøn ñöôïc phaùt bieåu döôùi caùc daïng khaùc sau ñaây: - “q neáu p”. - “p chæ neáu q”. - “p laø ñieàu kieän ñuû cho q”. - “q laø ñieàu kieän caàn cho p”. 1.2.5 Pheùp keùo theo 2 chieàu Pheùp keùo theo 2 chieàu hay pheùp töông ñöông, kyù hieäu bôûi , ñöôïc ñöa ra ñeå moâ hình cho loaïi phaùt bieåu ñieàu kieän hai chieàu coù daïng : “. . . neáu vaø chæ neáu . . .”. Cho p vaø q laø 2 meänh ñeà, ta vieát p  q ñeå dieãn ñaït phaùt bieåu “p neáu vaø chæ neáu q”. Pheùp toaùn töông ñöông  ñöôïc ñònh nghóa bôûi baûng chaân trò sau ñaây: p q pq 0 0 1 0 1 0 1 0 0 1 1 1 Meänh ñeà p  q, ñöôïc ñoïc laø “p neáu vaø chæ neáu q”, coøn ñöôïc phaùt bieåu döôùi caùc daïng khaùc sau ñaây: - “p khi vaø chæ khi q”. - “p laø ñieàu kieän caàn vaø ñuû cho q”. Meänh ñeà p  q coù chaân trò ñuùng (=1) trong caùc tröôøng hôïp p vaø q coù cuøng chaân trò. -9-
Ñoä öu tieân cuûa caùc toaùn töû logic. Töông töï nhö ñoái vôùi caùc pheùp toaùn soá hoïc, ñeå traùnh phaûi duøng nhieàu daáu ngoaëc trong caùc bieåu thöùc logic, ta ñöa ra moät thöù töï öu tieân trong vieäc tính toaùn. ÔÛ treân ta coù 5 toaùn töû logic:  (khoâng),  (vaø),  (hay),  (keùo theo),  (töông ñöông). Thöù töï öu tieân cuûa caùc toaùn töû treân ñöôïc lieät keâ theo möùc ñoä giaûm daàn nhö sau :  ,  , trong ñoù, caùc toaùn töû lieät keâ treân cuøng doøng coù cuøng ñoä öu tieân. Ví duï: 1. pq coù nghóa laø ((p)  q). 2. p q r  s coù nghóa laø (((p)  q) (r  s)). 3. p q r laø nhaäp nhaèn. Caàn phaûi duøng caùc daáu ngoaëc ñeå chæ roõ nghóa. II. Bieåu thöùc logic 2.1 Ñònh nghóa Trong ñaïi soá ta coù caùc bieåu thöùc ñaïi soá ñöôïc xaây döïng töø caùc haèng soá, caùc bieán vaø caùc pheùp toaùn. Khi thay theá caùc bieán trong moät bieåu thöùc ñaïi soá bôûi caùc haèng soá thì keát quaû thöïc hieän caùc pheùp toaùn trong bieåu thöùc seõ laø moät haèng soá. Trong pheùp tính meänh ñeà ta cuõng coù caùc bieåu thöùc logic ñöôïc xaây döïng töø : - Caùc meänh ñeà hay caùc giaù trò haèng. - Caùc bieán meänh ñeà. -10-
- Caùc pheùp toaùn logic, vaø caû caùc daáu ngoaëc "()" ñeå chæ roõ thöù töï thöïc hieän cuûa caùc pheùp toaùn. Giaû söû E, F laø 2 bieåu thöùc logic, khi aáy E, E  F, E  F, E  F cuõng laø caùc bieåu thöùc logic. Ví duï: Bieåu thöùc E(p,q,r) = (((p)  q) (r  s)). laø moät bieåu thöùc logic trong ñoù p, q, r laø caùc bieán meänh ñeà. 2.2 Baûng chaân trò Baûng chaân trò cuûa moät bieåu thöùc logic laø baûng lieät keâ chaân trò cuûa bieåu thöùc logic theo caùc tröôøng hôïp veà chaân trò cuûa taát caû caùc bieán meänh ñeà trong bieåu thöùc logic hay theo caùc boä giaù trò cuûa boä bieán meänh ñeà. Vôùi moät bieán meänh ñeà, ta coù 2 tröôøng hôïp laø 0 (sai) hoaëc 1 (ñuùng). Vôùi 2 bieán meänh ñeà p, q ta 4 tröôøng hôïp chaân trò cuûa boä bieán (p,q) laø caùc boä giaù trò (0,0), (0,1), (1,0), vaø (1,1). Trong tröôøng hôïp toång quaùt, vôùi n bieán meänh ñeà thì ta coù 2n tröôøng hôïp chaân trò cho boä n bieán ñoù. Ví duï 1: Baûng chaân trò cuûa caùc bieåu thöùc logic p  q vaø pq theo caùc bieán meänh ñeà p, q nhö sau: p q pq p p  q 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 1 0 1 -11-
Ví duï 2: Baûng chaân trò cuûa caùc bieåu thöùc logic p  (qr) theo caùc bieán meänh ñeà p, q, r nhö sau: p q r qr p  (qr) 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1 2.3 Söï töông ñöông logic Hai bieåu thöùc logic E vaø F theo caùc bieán meänh ñeà naøo ñoù ñöôïc goïi laø töông ñöông logic khi E vaø F luoân luoân coù cuøng chaân trò trong moïi tröôøng hôïp chaân trò cuûa boä bieán meänh ñeà. Khi ñoù ta vieát: EF vaø ñoïc laø "E töông ñöông vôùi F". Nhö vaäy, theo ñònh nghóa ta coù theå kieåm tra xem 2 bieåu thöùc logic coù töông ñöông hay khoâng baèng caùch laäp baûng chaân trò cuûa caùc bieåu thöùc logic. Ví duï: töø baûng chaân trò cuûa caùc bieåu thöùc logic p  q vaø pq theo caùc bieán meänh ñeà p, q ta coù: p  q  pq -12-
2.4 Bieåu thöùc haèng ñuùng, bieåu thöùc haèng sai Bieåu thöùc logic E ñöôïc goïi laø haèng ñuùng neáu chaân trò cuûa E luoân luoân baèng 1 (ñuùng) trong moïi tröôøng hôïp veà chaân trò cuûa caùc bieán meänh ñeà trong bieåu thöùc E. Noùi moät caùch khaùc, E laø moät haèng ñuùng khi ta coù: E  1. Bieåu thöùc logic E ñöôïc goïi laø haèng sai neáu chaân trò cuûa E luoân luoân baèng 0 (sai) trong moïi tröôøng hôïp veà chaân trò cuûa caùc bieán meänh ñeà trong bieåu thöùc E. Noùi moät caùch khaùc, E laø moät haèng ñuùng khi ta coù: E  0. Nhö vaäy, ta coù theå kieåm tra xem moät bieåu thöùc logic coù phaûi laø haèng ñuùng (haèng sai) hay khoâng baèng caùch laäp baûng chaân trò cuûa caùc bieåu thöùc logic. Ví duï: Bieåu thöùc p p laø haèng sai. Bieåu thöùc laø (p  q)  (pq) laø haèng ñuùng. Löu yù: - Giaû söû E vaø F laø 2 bieåu thöùc logic. Khi ñoù, E töông ñöông logic vôùi F (töùc laø ta coù E  F) khi vaø chæ khi bieåu thöùc logic E  F laø haèng ñuùng (töùc laø E  F  1). - Quan heä “töông ñöông logic vôùi”, kyù hieäu bôûi , laø moät quan heä töông ñöông treân taäp hôïp caùc bieåu thöùc logic theo caùc bieán meänh ñeà p1, p2, … , pn. Khaùi nieäm veà quan heä töông ñöông ñöôïc trình baøy trong chöông 4. ÔÛ ñaây ta chæ chuù yù ñeán tính chaát sau ñaây: Neáu E  F vaø F  G thì E  G. -13-
III. Caùc luaät logic Caùc luaät logic laø cô sôû ñeå ta thöïc hieän caùc bieán ñoåi treân moät bieåu thöùc logic ñeå coù ñöôïc moät bieåu thöùc logic môùi töông ñöông logic vôùi bieåu thöùc logic coù tröôùc. Moãi bieåu thöùc logic cho ta moät söï khaúng ñònh veà söï töông ñöông cuûa 2 bieåu thöùc logic. Ta seõ söû duïng caùc qui taéc thay theá vaø caùc luaät logic ñaõ bieát ñeå thöïc hieän caùc pheùp bieán ñoåi töông ñöông treân caùc bieâu thöùc logic. 3.1 Caùc luaät logic Döôùi ñaây, chuùng ta seõ lieät keâ ra moät soá luaät logic thöôøng ñöôïc söû duïng trong laäp luaän vaø chöùng minh. Caùc luaät naày coù theå ñöôïc suy ra tröïc tieáp töø caùc baûng chaân trò cuûa caùc bieåu thöùc logic.  Caùc luaät veà pheùp phuû ñònh: pp (luaät phuû ñònh cuûa phuû ñònh)  Luaät giao hoaùn: pqqp pqqp  Luaät keát hôïp p  (q  r)  (p  q)  r p  (q  r)  (p  q)  r  Luaät phaân boá p  (q  r)  (p  q)  (p  r) p  (q  r)  (p  q)  (p  r) -14-
 Luaät De Morgan  (p  q)   p   q  (p  q)   p   q  Luaät veà phaàn töû buø p  p  1 p  p  0  Luaät keùo theo pq  pq  Luaät töông ñöông p  q  (p  q)  (q  p)  Caùc luaät ñôn giaûn cuûa pheùp tuyeån ppp (tính luõy ñaúng cuûa pheùp tuyeån) p11 (luaät naøy coøn ñöôïc goïi laø luaät thoáng trò) p0p (luaät naøy coøn ñöôïc goïi laø luaät trung hoøa) p  (p  q)  p (luaät naøy coøn ñöôïc goïi laø luaät haáp thuï)  Caùc luaät ñôn giaûn cuûa pheùp hoäi ppp (tính luõy ñaúng cuûa pheùp hoäi) p1p (luaät naøy coøn ñöôïc goïi laø luaät trung hoøa) p00 (luaät naøy coøn ñöôïc goïi laø luaät thoáng trò) p  (p  q)  p (luaät naøy coøn ñöôïc goïi laø luaät haáp thuï) Moät soá luaät trong caùc luaät trình baøy ôû treân coù theå ñöôïc suy ra töø caùc luaät khaùc. Chuùng ta coù theå tìm ra ñöôïc moät taäp hôïp luaät logic toái thieåu maø töø ñoù ta coù theå suy ra taát caû caùc luaät logic khaùc, nhöng ñieàu naày khoâng quan troïng laém ñoái vôùi chuùng ta. Nhöõng luaät treân ñöôïc -15-
choïn löïa ñeå laøm cô sôû cho chuùng ta thöïc hieän caùc bieán ñoåi logic, suy luaän vaø chöùng minh. Taát nhieân laø coøn nhieàu luaät logic khaùc maø ta khoâng lieät keâ ra ôû ñaây. Caùc luaät keát hôïp trình baøy ôû treân coøn ñöôïc goïi laø tính chaát keát hôïp cuûa pheùp toaùn  vaø pheùp toaùn . Do tính chaát naày, ta coù theå vieát caùc bieåu thöùc logic hoäi vaø caùc bieåu thöùc tuyeån döôùi caùc daïng sau: E1  E2  …  Em E1  E2  …  Em vaø vieäc tính toaùn chaân trò coù theå ñöôïc thöïc hieän döïa treân moät söï phaân boá caùc caëp daáu ngoaëc vaøo bieåu thöùc moät caùch tuøy yù ñeå xaùc ñònh moät trình töï thöïc hieän caùc pheùp toaùn. Ví duï: Bieåu thöùc E1  E2  E3  E4 coù theå ñöôïc tính toaùn chaân trò bôûi bieåu thöùc sau: (E1  E2)  (E3  E4) hay coù theå tính toaùn theo bieåu thöùc: E1  ((E2  E3 )  E4) 3.2 Caùc qui taéc thay theá Döôùi ñaây laø caùc qui taéc ñeå cho ta coù theå suy ra nhöõng bieåu thöùc logic môùi hay tìm ra caùc bieåu thöùc logic töông ñöông vôùi moät bieåu thöùc logic cho tröôùc.  Qui taéc 1: Trong moät bieåu thöùc logic E, neáu ta thay theá moät bieåu thöùc con bôûi moät bieåu thöùc logic töông ñöông vôùi bieåu thöùc con ñoù thì ta seõ ñöôïc moät bieåu thöùc môùi E' töông ñöông vôùi bieåu thöùc E. -16-
Ví duï: Cho bieåu thöùc logic E = q  p. Thay theá q trong bieåu thöùc E bôûi bieåu thöùc q (töông ñöông vôùi q) ta ñöôïc moät bieåu thöùc môùi E' = q  p. Theo qui taéc thay theá 1 ta coù: q  p  q  p  Qui taéc 2: Giaû söû bieåu thöùc logic E laø moät haèng ñuùng. Neáu ta thay theá moät bieán meänh ñeà p bôûi moät bieåu thöùc logic tuyø yù thì ta seõ ñöôïc moät bieåu thöùc logic môùi E' cuõng laø moät haèng ñuùng. Ví duï: Ta coù bieåu thöùc E(p,q) = (pq)  ( p  q) laø moät haèng ñuùng. Thay theá bieán q trong bieåu thöùc E bôûi bieåu thöùc q  r ta ñöôïc bieåu thöùc logic môùi: E'(p,q,r) = (p (q r))  ( p  (q r)) Theo qui taéc thay theá 2 ta coù bieåu thöùc E'(p,q,r) cuõng laø moät haèng ñuùng. 3.3 Caùc ví duï aùp duïng Ví duï 1: Chöùng minh raèng (p  q)  ( q   p). Chöùng minh : (p  q)   p  q (luaät keùo theo)  qp (luaät giao hoaùn)   q   p (luaät phuû ñònh)  qp (luaät keùo theo) Ví duï 2: Chöùng minh raèng bieåu thöùc ((p  q)  p)  q laø moät haèng ñuùng. -17-
Chöùng minh. ((p  q)  p)  q   ((p  q)  p)  q (luaät keùo theo)  ( (p  q)   p)  q (luaät De Morgan)   (p  q)  ( p  q) (luaät keát hôïp)  (p  q)  (p  q) (luaät keùo theo)  1 (luaät veà phaàn töû buø) Vaäy bieåu thöùc ((p  q)  p)  q laø haèng ñuùng. Ví duï 3: Chöùng minh raèng bieåu thöùc pqp laø moät haèng ñuùng. Chöùng minh. p  q  p   ( p  q)  p (luaät keùo theo)  ( p   q)  p (luaät De Morgan)  ( q   p)  p (luaät giao hoaùn)   q  ( p  p) (luaät keát hôïp)  q1 (luaät veà phaàn töû buø) 1 (luaät ñôn giaûn) Vaäy meänh ñeà p  q  p laø haèng ñuùng. Ví duï 4: Chöùng minh raèng bieåu thöùc ppq laø moät meänh ñeà haèng ñuùng. Chöùng minh. ppq   p  (pq) (luaät keùo theo)  (p  p)  q (luaät keát hôïp) 1q (luaät veà phaàn töû buø) -18-
1 (luaät ñôn giaûn) Vaäy meänh ñeà p  p q laø haèng ñuùng. Nhaän xeùt: Caùc ví duï treân cho ta thaáy moät quan heä khaùc giöõa caùc meänh ñeà phöùc hôïp hay caùc meänh ñeà : quan heä “suy ra”. Khi meänh ñeà p  q laø haèng ñuùng, ta noùi raèng p suy ra q (veà maët logic). Chuùng ta seõ duøng kyù hieäu  ñeå chæ quan heä “suy ra”. Quan heä suy ra naày coù tính truyeàn (hay baéc caàu), nhöng khoâng coù tính chaát ñoái xöùng. IV. Caùc daïng chính taéc 4.1 Daïng chính taéc tuyeån Giaû söû p1, p2, … , pn laø caùc bieán meänh ñeà. Moät bieåu thöùc logic F theo caùc bieán meänh ñeà p1, p2, … , pn ñöôïc goïi laø moät bieåu thöùc hoäi cô baûn neáu noù coù daïng sau: F = q1  q2  …  qn vôùi qj = pj hoaëc qj =  pj (j = 1, … , n). Ví duï: Bieåu thöùc x   y  z laø moät bieåu thöùc hoäi cô baûn theo 3 bieán meänh ñeà x, y, z. Bieåu thöùc logic E(p1, p2, … , pn) theo caùc bieán meänh ñeà p1, p2, … , pn ñöôïc noùi laø coù daïng chính taéc tuyeån khi E coù daïng: E = E1  E2  …  Em Trong ñoù moãi bieåu thöùc con Ei ñeàu coù daïng chính taéc tuyeån theo caùc bieán p1, p2, … , pn. Ví duï: Caùc bieåu thöùc sau ñaây coù daïng chính taéc tuyeån: E(x,y,z) = (x   y  z)  ( x  y  z)  (x  y  z) -19-