Bài giảng Toán học sơ cấp - Phần I: Mệnh đề - Nguyễn Viết Đông
Mệnh đề và chân trị
• Khái niệm về mệnh đề:
Mệnh đề toán học là khái niệm cơ bản của toán
học không được định nghĩa mà chỉ được mô tả.
Mệnh đề toán học(gọi tắt là mệnh đề) là một
khẳng định có giá trị chân lý xác định(đúng
hoặc sai, nhưng không thể vừa đúng vừa sai).
Mệnh đề và chân trị
• Ví dụ:
– “Số 123 chia hết cho 3” là 1 mệnh đề đúng
– “Thành phố Hồ Chí Minh là thủ đô của nước Việt
Nam” là một mệnh đề sai.
– “Bạn có khỏe không ? ” không phải là một mệnh
đề toán học vì đây là một câu hỏi không thể phản
ánh một điều đúng hay một điều sai
below. p q p pq pq pq pq pq F F T F F F T T F T T F T T T F T F F F T T F F T T F T T F T T 39 Some Alternative Notations Name: not and or xor implies iff Propositional logic: Boolean algebra: p pq + C/C++/Java (wordwise): ! && || != == C/C++/Java (bitwise): ~ & | ^ Logic gates: 11 Dạng mệnh đề • Daïng meänh ñeà laø moät bieåu thöùc ñöôïc caáu taïo töø: - Caùc haèng meänh ñeà, töùc laø caùc meänh ñeà ñaõ xeùt ôû trên. - Caùc bieán meänh ñeà, töùc laø caùc bieán laáy giaù trò laø caùc meänh ñeà, thoâng qua caùc pheùp toaùn meänh ñeà ñaõ xeùt ôû muïc trên theo moät trình töï nhaát ñònh naøo ñoù, thöôøng ñöôïc chæ roõ bôûi caùc daáu ngoặc. 41 Dạng mệnh đề • Với E là một dạng mệnh đề các biến mệnh đề p, q, r ứng với mỗi giá trị cụ thể P, Q, R (là các mệnh đề) của p, q, r thì ta có duy nhất một mệnh đề E(P, Q, R). Ta viết E = E(p, q, r). • Bảng chân trị là bảng ghi tất cả các trường hợp chân trị có thể xảy ra đối với dạng mệnh đề E theo chân trị của các biến mệnh đề p, q, r. Nếu có n biến, bảng này sẽ có 2n dòng, chưa kể dòng tiêu đề. 42 Dạng mệnh đề 43 Tautologies and Contradictions A tautology is a compound proposition that is true no matter what the truth values of its atomic propositions are! Ex. p p [What is its truth table?] A contradiction is a compound proposition that is false no matter what! Ex. p p [Truth table?] Other compound props. are contingencies. 44 12 Logical Equivalence Compound proposition p is logically equivalent to compound proposition q, written pq, IFF the compound proposition pq is a tautology. Compound propositions p and q are logically equivalent to each other IFF p and q contain the same truth values as each other in all rows of their truth tables. 45 Ex. Prove that pq (p q). p q pq p q p q (p q) F F F T T F T T Proving Equivalence via Truth Tables F T T T T T T T T T F F F F F F F F T T 46 Dạng mệnh đề 1. Quy tắc thay thế thứ 1 Trong dạng mệnh đề E, nếu ta thay thế biểu thức con F bởi một dạng mệnh đề tương đương logic thì dạng mệnh đề thu được vẫn còn tương đương logic với E. 2. Quy tắc thay thế thứ 2 Giả sử dạng mệnh đề E(p,q,r) là một hằng đúng. Nếu ta thay thế những nơi p xuất hiện trong E bởi một F(p‟,q‟,r‟) thì dạng mệnh đề nhận được theo các biến q,r,p‟,q‟,r‟, vẫn còn là 1 hằng đúng. 47 Dạng mệnh đề Các luật logic : Với p, q, r là các biến mệnh đề, 1 là một hằng đúng và 0 là một hằng sai, ta có các tương đương logic sau đây: 1) Luật luỹ đẳng p p p p p p 48 13 Dạng mệnh đề 49 50 51 52 14 53 Dạng mệnh đề 16) Luật rút gọn: p q p 1 p (p q) p q (p q) q p q p (p q) 1 54 Equivalence Laws - Examples • Identity: pT p pF p • Domination: pT T pF F • Idempotent: pp p pp p • Double negation: p p • Commutative: pq qp pq qp • Associative: (pq)r p(qr) (pq)r p(qr) 55 More Equivalence Laws • Distributive: p(qr) (pq)(pr) p(qr) (pq)(pr) • De Morgan’s: (pq) p q (pq) p q • Trivial tautology/contradiction: p p T p p F Augustus De Morgan (1806-1871) 15 Defining Operators via Equivalences Using equivalences, we can define operators in terms of other operators. • Exclusive or: pq (pq)(pq) pq (pq)(qp) • Implies: pq p q • Biconditional: pq (pq) (qp) pq (pq) 57 An Example Problem • Check using a symbolic derivation whether (p q) (p r) p q r. (p q) (p r) [Expand definition of ] (p q) (p r) [Defn. of ] (p q) ((p r) (p r)) [DeMorgan’s Law] (p q) ((p r) (p r)) [associative law] cont. 58 Example Continued... (p q) ((p r) (p r)) [ commutes] (q p) ((p r) (p r)) [ associative] q (p ((p r) (p r))) [distrib. over ] q (((p (p r)) (p (p r))) [assoc.] q (((p p) r) (p (p r))) [trivail taut.] q ((T r) (p (p r))) [domination] q (T (p (p r))) [identity] q (p (p r)) cont. 59 End of Long Example q (p (p r)) [DeMorgan’s] q (p (p r)) [Assoc.] q ((p p) r) [Idempotent] q (p r) [Assoc.] (q p) r [Commut.] p q r Q.E.D. (quod erat demonstrandum) (Which was to be shown.) 60 16 Dạng mệnh đề • Để chứng minh một dạng mệnh đề là hằng đúng, hằng sai, các dạng mệnh đề là tương đương lôgic, dạng mệnh đề này là hệ quả logic của dạng mệnh đề kia, ta có các cách sau: - Lập bảng chân trị. - Sử dụng phép thay thế. 61 Ví dụ Cho p, q, r laø caùc bieán meänh ñeà. Chöùng minh raèng: (p r) (q r) (p q) r (1) Chuùng ta có thể chöùng minh (1) baèng hai caùch. Caùch 1: Laäp baûng chaân trò . 62 63 Qui tắc suy diễn • Trong các chứng minh toán học, xuất phát từ một số khẳng định đúng p, q, r(tiền đề), ta áp dụng các qui tắc suy diễn để suy ra chân lí của một mệnh đề h mà ta gọi là kết luận. • Nói cách khác, dùng các qui tắc suy diễn để chứng minh: ( p q r ) có hệ quả logic là h . 64 17 Qui Tắc Suy Diễn Ta thường mô hình hóa phép suy luận đó dưới dạng: p q r . : ___ h 65 Qui Tắc Suy Diễn • QUI TẮC MODUS PONENS(Phƣơng pháp khẳng định) Qui tắc này được thể hiện bằng hằng đúng: Hoặc dưới dạng sơ đồ p q p q p q p q •Nếu An học chăm thì An học tốt. •Mà An học chăm Suy ra An học tốt •Hình vuông là hình bình hành •Mà hình bình hành có hai đường chéo cắt nhau tại trung điểm mỗi đường. Suy ra hình vuông có hai đường chéo cắt nhau tại trung điểm mỗi đường 67 Qui Tắc Suy Diễn • QUI TẮC TAM ĐOẠN LUẬN(Syllogism) Qui tắc này được thể hiện bằng hằng đúng: Hoặc dưới dạng sơ đồ p q q r p r p q q r p r 18 •Hai tam giác vuông có cạnh huyền và 1 cặp góc nhọn bằng nhau thì chúng ta có một cạnh bằng nhau kèm giữa hai góc bằng nhau. •Nếu hai tam giác có cạnh bằng nhau kèm giữa hai góc bằng nhau thì chúng bằng nhau Suy ra hai tam giác vuông có cạnh huyền và 1 cặp góc nhọn bằng nhau thì bằng nhau. •Một con ngựa rẻ là một con ngựa hiếm •Cái gì hiếm thì đắt Suy ra một con ngựa rẻ thì đắt () 69 Qui Tắc Suy Diễn • QUI TẮC MODUS TOLLENS PHƢƠNG PHÁP PHỦ ĐỊNH Qui tắc này được thể hiện bằng hằng đúng: Hoặc dưới dạng sơ đồ p q q p p q q p • Xét chứng minh • Ta suy luận p r r s t s t u u p p r r s s t t u u p Aristotle (ca. 384-322 B.C.) 71 Qui Tắc Suy Diễn • QUI TẮC TAM ĐOẠN LUẬN RỜI Qui tắc này được thể hiện bằng hằng đúng: Ý nghĩa của qui tắc: nếu trong hai trường hợp có thể xảy ra, chúng ta biết có một trường hợp sai thì chắc chắn trường hợp còn lại sẽ đúng p q q p p q p q 19 Qui Tắc Suy Diễn • QUI TẮC MÂU THUẪN CHỨNG MINH BẰNG PHẢN CHỨNG Ta có tương đương logic • Để chứng minh vế trái là một hằng đúng ta chứng minh nếu thêm phủ định của q vào các tiền đề thì được một mâu thuẫn. 1 2 1 2... ... 0n np p p q p p p q VÍ DỤ • Hãy chứng minh: • Cm bằng phản chứng. p r p q q s r s 0 p r p q q s r s 74 Qui Tắc Suy Diễn • CHỨNG MINH THEO TRƢỜNG HỢP Dựa trên hằng đúng: • Ý nghĩa: nếu p suy ra r và q suy ra r thì p hay q cũng có thể suy ra r. p r q r p q r VÍ DỤ • Chứng minh rằng: 3 4 3n n 20 Một số luật thêm p Rule of Addition(Phép thêm) pq pq Phép đơn giản nối liền p p q pq Luật về phép nối lền 77 VÍ DỤ TỔNG HỢP 1. Nếu nghệ sĩ Trương Ba không trình diễn hay số vé bán ra ít hơn 100 thì đêm diễn sẽ bi hủy bỏ và ông bầu sẽ rất buồn. 2. Nếu đêm diễn bị hủy bỏ thì tiềnvé phải trả lại cho người xem. 3. Nhưng tiềnvé đã không trả lại cho người xem. Vậy nghệ sỹ TB đã trình diễn • p:Nghệ sĩ Trương Ba đã trình diễn. • q:số vé bán ra ít hơn 100. • r:đêm diễn bị hủy bỏ. • s: ông bầu buồn. • t:trả lại tiền vé cho người xem p q r s r t t p 78 Qui Tắc Suy Diễn • PHẢN VÍ DỤ Để chứng minh một phép suy luận là sai hay không là một hằng đúng. Ta chỉ cần chỉ ra một phản ví dụ. 1 2 ... np p p q VÍ DỤ • Ông Minh nói rằng nếu không được tăng lương thì ông ta sẽ nghỉ việc. Mặt khác, nếu ông ấy nghỉ việc và vợ ông ấy bị mất việc thì phải bán xe. Biết rằng nếu vợ ông Minh hay đi làm trễ thì trước sau gì cũng sẽ bị mất việc và cuối cùng ông Minh đã được tăng lương. • Suy ra nếu ông Minh không bán xe thì vợ ông ta đã không đi làm trễ • p:ông Minh được tăng lương. • q: ông Minh nghỉ việc. • r: vợ ông Minh mất việc. • s: gia đình phải bán xe. • t: vợ ông hay đi làm trễ. p q q r s t r p s t s=0 t=1 p=1 q=0 r=1 80 21 Formal Proof Example • Suppose we have the following premises: “It is not sunny and it is cold.” “Only if We will swim is it sunny.” “If we do not swim, then we will canoe.” “If we canoe, then we will be home early.” • Given these premises, prove the theorem “We will be home early” using inference rules. 81 Proof Example cont. • Let us adopt the following abbreviations: – sunny = “It is sunny”; cold = “It is cold”; swim = “We will swim”; canoe = “We will canoe”; early = “We will be home early”. • Then, the premises can be written as: (1) sunny cold (2) swim sunny (3) swim canoe (4) canoe early 82 Proof Example cont. Step Proved by 1. sunny cold Premise #1. 2. sunny Simplification of 1. 3. swimsunny Premise #2. 4. swim Modus tollens on 2,3. 5. swimcanoe Premise #3. 6. canoe Modus ponens on 4,5. 7. canoeearly Premise #4. 8. early Modus ponens on 6,7. 83 Qui Tắc Suy Diễn • VD1 84 22 85 Qui Tắc Suy Diễn • VD2 86 • Giải Qui Tắc Suy Diễn 87 Qui Tắc Suy Diễn 88 23 Qui Tắc Suy Diễn 89 à 90
File đính kèm:
- bai_giang_toan_hoc_so_cap_phan_i_menh_de_nguyen_viet_dong.pdf