Cấu trúc rời rạc

CẤU TRÚC RỜI RẠC nGiảng viên: § Cao Thanh Tình (Email: tinhct@uit.edu.vn) § Bộ môn Toán Lý – ĐHCNTT – ĐHQGTPHCM PDF created with pdfFactory Pro trial version www.pdffactory.com CƠ SỞ LÔGIC ØMệnh đề ØDạng mệnh đề ØQui tắc suy diễn ØVị từ, lượng từ ØQuy nạp toán học Chương 1. Cơ sở lôgic 2 PDF created with pdfFactory Pro trial version www.pdffactory.com Mệnh đề Định nghĩa: Mệnh đề là một khẳng định có giá trị chân lý xác định, đúng hoặc sai. Câu hỏi, câu cảm thán, mệnh lệnh… không là mệnh đề. Ví dụ: - Đại học CNTT trực thuộc ĐHQG TP.HCM. - 1+7 =8. - Hôm nay em đẹp quá! (không là mệnh đề) - Hôm nay ngày thứ mấy? (không là mệnh đề) Chương 1. Cơ sở lôgic Chương 1. Cơ sở lôgic 3 PDF created with pdfFactory Pro trial version www.pdffactory.com Mệnh đề n Ký hiệu: người ta dùng các ký hiệu P, Q, R… để chỉ mệnh đề. n Chân trị của mệnh đề: Một mệnh đề chỉ có thể đúng hoặc sai, không thể đồng thời vừa đúng vừa sai. Khi mệnh đề P đúng ta nói P có chân trị đúng, ngược lại ta nói P có chân trị sai. n Chân trị đúng và chân trị sai sẽ được ký hiệu lần lượt là 1(hay Đ,T) và 0(hay S,F) Chương 1. Cơ sở lôgic 4 Chương 1. Cơ sở lôgic PDF created with pdfFactory Pro trial version www.pdffactory.com Mệnh đề Phân loại: gồm 2 loại Ø Mệnh đề phức hợp: là mệnh đề được xây dựng từ các mệnh đề khác nhờ liên kết bằng các liên từ (và, hay, khi và chỉ khi,…) hoặc trạng từ “không” Ø Mệnh đề sơ cấp (nguyên thủy): Là mệnh đề không thể xây dựng từ các mệnh đề khác thông qua liên từ hoặc trạng từ “không” Chương 1. Cơ sở lôgic 5 Chương 1. Cơ sở lôgic PDF created with pdfFactory Pro trial version www.pdffactory.com Mệnh đề Ví dụ: - 2 không là số nguyên tố - 2 là số nguyên tố - Nếu 3>4 thì trời mưa - An đang xem phim hay An đang học bài - Vấn đề này cần được xem xét cẩn thận - x + 1 = 2 - x + y = z Chương 1. Cơ sở lôgic 6 Chương 1. Cơ sở lôgic PDF created with pdfFactory Pro trial version www.pdffactory.com Các phép toán: có 5 phép toán 1. Phép phủ định: phủ định của mệnh đề P được ký hiệu là ØP hay (đọc là “không” P hay “phủ định của” P). Bảng chân trị : Ví dụ: - 2 là số nguyên tố. Phủ định: 2 không là số nguyên tố - 15 > 5 Phủ định: 15 ≤ 5 P 0 1 1 0 Mệnh đề Chương 1. Cơ sở lôgic 7 Chương 1. Cơ sở lôgic P P PDF created with pdfFactory Pro trial version www.pdffactory.com 2. Phép hội (nối liền, giao): của hai mệnh đề P, Q được kí hiệu bởi P Ù Q (đọc là “P và Q”), là mệnh đề xác định bởi : P Ù Q đúng khi và chỉ khi P và Q đồng thời đúng. Bảng chân trị Ví dụ: P: “Hôm nay là chủ nhật” Q: “Hôm nay trời mưa” P Ù Q: “ Hôm nay là chủ nhật và trời mưa” P Q PÙQ 0 0 1 1 0 1 0 1 0 0 0 1 Mệnh đề Chương 1. Cơ sở lôgic 8 Chương 1. Cơ sở lôgic PDF created with pdfFactory Pro trial version www.pdffactory.com 3. Phép tuyển (nối rời, hợp): của hai mệnh đề P, Q được kí hiệu bởi P Ú Q (đọc là “P hay Q”), là mệnh đề xác định bởi: P Ú Q sai khi và chỉ khi P và Q đồng thời sai. Bảng chân trị Ví dụ: - e > 4 hay e > 5 (S) - 2 là số nguyên tố hay là số lẻ (Đ) P Q PÚQ 0 0 1 1 0 1 0 1 0 1 1 1 Mệnh đề Chương 1. Cơ sở lôgic 9 Chương 1. Cơ sở lôgic PDF created with pdfFactory Pro trial version www.pdffactory.com 4. Phép kéo theo: Mệnh đề P kéo theo Q của hai mệnh đề P và Q, kí hiệu bởi P ® Q (đọc là “P kéo theo Q” hay “Nếu P thì Q” hay “P là điều kiện đủ của Q” hay “Q là điều kiện cần của P”) là mệnh đề xác định bởi: P ® Q sai khi và chỉ khi P đúng mà Q sai. Bảng chân trị Ví dụ e >4 kéo theo 5>6 P Q P®Q 0 0 1 1 0 1 0 1 1 1 0 1 Mệnh đề Chương 1. Cơ sở lôgic 10 Chương 1. Cơ sở lôgic PDF created with pdfFactory Pro trial version www.pdffactory.com 5. Phép kéo theo hai chiều: Mệnh đề P kéo theo Q và ngược lại của hai mệnh đề P và Q, ký hiệu bởi P « Q (đọc là “P nếu và chỉ nếu Q” hay “P khi và chỉ khi Q” hay “P là điều kiện cần và đủ của Q”), là mệnh đề xác định bởi: P « Q đúng khi và chỉ khi P và Q có cùng chân trị Bảng chân trị Ví dụ: 6 chia hết cho 3 khi và chi khi 6 chia hết cho 2 P Q P«Q 0 0 1 1 0 1 0 1 1 0 0 1 Mệnh đề Chương 1. Cơ sở lôgic 11 Chương 1. Cơ sở lôgic PDF created with pdfFactory Pro trial version www.pdffactory.com Định nghĩa: là một biểu thức được cấu tạo từ: - Các mệnh đề (các hằng mệnh đề) - Các biến mệnh đề p, q, r, …, tức là các biến lấy giá trị là các mệnh đề nào đó - Các phép toán Ø, Ù, Ú, ®, « và dấu đóng mở ngoặc (). Ví dụ: E(p,q) = Ø(Øp Ú q) F(p,q,r) = (p Ù q) ® Ø(q Ú r) Dạng mệnh đề Chương 1. Cơ sở lôgic 12 Chương 1. Cơ sở lôgic PDF created with pdfFactory Pro trial version www.pdffactory.com Độ ưu tiên của các toán tử logic: - Ưu tiên mức 1: () - Ưu tiên mức 2: Ø - Ưu tiên mức 3: Ù, Ú - Ưu tiên mức 4: ®, « Bảng chân trị của dạng mệnh đề E(p,q,r): 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ó dòng, chưa kể dòng tiêu đề. Dạng mệnh đề Chương 1. Cơ sở lôgic 13 Chương 1. Cơ sở lôgic 2n PDF created with pdfFactory Pro trial version www.pdffactory.com Độ ưu tiên của các toán tử logic: - Ưu tiên mức 1: () - Ưu tiên mức 2: Ø - Ưu tiên mức 3: Ù, Ú - Ưu tiên mức 4: ®, « Bảng chân trị của dạng mệnh đề E(p,q,r): 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ó dòng, chưa kể dòng tiêu đề. Dạng mệnh đề Chương 1. Cơ sở lôgic 14 Chương 1. Cơ sở lôgic 2n PDF created with pdfFactory Pro trial version www.pdffactory.com Ví dụ: E(p,q,r) =(p Ú q) ® r . Ta có bảng chân trị sau Dạng mệnh đề Chương 1. Cơ sở lôgic 15 Chương 1. Cơ sở lôgic p q r p Ú q (p Ú q) ® r 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 1 1 1 1 1 0 0 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 PDF created with pdfFactory Pro trial version www.pdffactory.com Tương đương logic: Hai dạng mệnh đề E và F được gọi là tương đương logic nếu chúng có cùng bảng chân trị. Ký hiệu E Û F. Ví dụ: Ø(p Ú q) Û Øp Ù Øq Dạng mệnh đề được gọi là hằng đúng nếu nó luôn lấy giá trị 1 Dạng mệnh đề gọi là hằng sai (hay mâu thuẩn) nếu nó luôn lấy giá trị 0. Dạng mệnh đề Chương 1. Cơ sở lôgic 16 Chương 1. Cơ sở lôgic PDF created with pdfFactory Pro trial version www.pdffactory.com Định lý: Hai dạng mệnh đề E và F tương đương với nhau khi và chỉ khi E « F là hằng đúng. Hệ quả logic: F được gọi là hệ quả logic của E nếu E ® F là hằng đúng. Ký hiệu E Þ F Ví dụ: Ø(p Ú q) Þ Øp Dạng mệnh đề Chương 1. Cơ sở lôgic 17 Chương 1. Cơ sở lôgic PDF created with pdfFactory Pro trial version www.pdffactory.com Các luật lôgic: 1. Phủ định của phủ định: ØØp Û p 2. Qui tắc De Morgan: Ø (p Ú q) Û Ø p Ù Ø q Ø (p Ù q) Û Ø p Ú Ø q 3. Luật giao hoán: p Ú q Û q Ú p p Ù q Û q Ù p 4. Luật kết hợp: (p Ú q) Ú r Û p Ú (q Ú r) (p Ù q) Ù r Û p Ù (q Ù r) Dạng mệnh đề Chương 1. Cơ sở lôgic 18 Chương 1. Cơ sở lôgic PDF created with pdfFactory Pro trial version www.pdffactory.com Các luật lôgic: 5. Luật phân phối: p Ú (q Ù r) Û (p Ú q) Ù (p Ú r) p Ù (q Ú r) Û (p Ù q) Ú (p Ù r) 6. Luật lũy đẳng: p Ù p Û p p Ú p Û p 7. Luật trung hòa: p Ú 0 Û p p Ù 1 Û p 8. Luật về phần tử bù: p Ù Øp Û 0 p Ú Øp Û 1 Dạng mệnh đề Chương 1. Cơ sở lôgic 19 Chương 1. Cơ sở lôgic PDF created with pdfFactory Pro trial version www.pdffactory.com 9. Luật thống trị: p Ù 0 Û 0 p Ú 1 Û 1 10. Luật hấp thu: p Ú (p Ù q) Û p p Ù (p Ú q) Û p 11. Luật về phép kéo theo: p ® q Û Øp Ú q Û Ø q ® Ø p Ví dụ: Cho p, q, r là các biến mệnh đề. Chứng minh rằng: (Øp ® r) Ù (q ® r) Û (p ® q) ® r Dạng mệnh đề Chương 1. Cơ sở lôgic 20 Chương 1. Cơ sở lôgic PDF created with pdfFactory Pro trial version www.pdffactory.com 1. Qui tắc khẳng định (Modus Ponens): [(p ® q) Ù p] ® q [(p Ú q) Ù Øp] ® q Ví dụ: · Học tốt thi đậu · Sơn học tốt Suy ra Sơn thi đậu · An hay Tuấn ăn cua biển · Tuấn ăn chay Suy ra An ăn cua biển Qui tắc suy diễn Chương 1. Cơ sở lôgic 21 Chương 1. Cơ sở lôgic p ® q p \q p Ú q Øp \q PDF created with pdfFactory Pro trial version www.pdffactory.com 2. Qui tắc tam đoạn luận: [(p ® q) Ù (p ® r)] ® (p ® r) Ví dụ: • Nếu trời mưa thì đường ướt • Nếu đường ướt thì đường trơn Suy ra nếu trời mưa thì đường trơn. Qui tắc suy diễn Chương 1. Cơ sở lôgic 22 Chương 1. Cơ sở lôgic p ® q q ® r \p ® r PDF created with pdfFactory Pro trial version www.pdffactory.com 3. Qui tắc phủ định: [(p ® q) Ù Øq ] ® Ø p Ví dụ: • Nếu Sơn đi học đầy đủ thì Sơn đậu toán rời rạc. • Sơn không đậu toán rời rạc. Suy ra: Sơn không đi học đầy đủ. Qui tắc suy diễn Chương 1. Cơ sở lôgic 23 Chương 1. Cơ sở lôgic p ® q Øq \Øp PDF created with pdfFactory Pro trial version www.pdffactory.com 4. Qui tắc phản chứng: Ví dụ: Qui tắc suy diễn Chương 1. Cơ sở lôgic 24 Chương 1. Cơ sở lôgic 1 2 1 2 [( ... ) ] [( ... ) 0] n n p p p q p p p qÙ Ù Ù ® Û Ù Ù Ù Ù Ø ® Chứng minh p ® r Øp ® q q ®s \Ør ® s Giải: CM bằng phản chứng p ® r Øp ® q q ®s Ør Øs \0 PDF created with pdfFactory Pro trial version www.pdffactory.com 5. Qui tắc chứng minh theo trường hợp : [(p ® r) Ù (q ® r)] ® [(p Ú q)®r] 6. 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ụ. Qui tắc suy diễn Chương 1. Cơ sở lôgic 25 Chương 1. Cơ sở lôgic PDF created with pdfFactory Pro trial version www.pdffactory.com 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ễ Qui tắc suy diễn Chương 1. Cơ sở lôgic 26 Chương 1. Cơ sở lôgic 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 PDF created with pdfFactory Pro trial version www.pdffactory.com Ví dụ: Giải thích các suy luận sau: Qui tắc suy diễn Chương 1. Cơ sở lôgic 27 Chương 1. Cơ sở lôgic 1. (Øp Ú q)®(r Ù s) r ® t Øt \(p Ú Øs) 4. p ® r Øs ® Ør s ® t Øt Ú u Øu \Øp 2. p ® (q ® r) p Ú s t ® p Øs \Ør ® Øt 3. p ® q Ør Ú s p Ú r \Øq ® s PDF created with pdfFactory Pro trial version www.pdffactory.com Định nghĩa: Vị từ là một khẳng định p(x,y,..), trong đó x,y...là các biến thuộc tập hợp A, B,.. cho trước sao cho: - Bản thân p(x,y,..) không phải là mệnh đề - Nếu thay x,y,.. thành giá trị cụ thể thì p(x,y,..) là mệnh đề. Ví dụ: - p(n) = “n +1 là số nguyên tố” - q(x,y) = “x + y = 1” Vị từ - Lượng từ Chương 1. Cơ sở lôgic 28 Chương 1. Cơ sở lôgic PDF created with pdfFactory Pro trial version www.pdffactory.com Các phép toán trên vị từ Cho trước các vị từ p(x), q(x) theo một biến xÎA. Khi ấy, ta cũng có các phép toán tương ứng như trên mệnh đề: v Phủ định: Øp(x) v Phép nối liền (hội, giao): p(x) Ù q(x) v Phép nối rời (tuyển, hợp): p(x) Ú q(x) v Phép kéo theo: p(x) ® q(x) v Phép kéo theo hai chiều: p(x) « q(x) Vị từ - Lượng từ Chương 1. Cơ sở lôgic 29 Chương 1. Cơ sở lôgic PDF created with pdfFactory Pro trial version www.pdffactory.com Cho p(x) là một vị từ theo một biến xác định trên A. Các mệnh đề lượng từ hóa của p(x) được định nghĩa như sau: - Mệnh đề “Với mọi x thuộc A, p(x) ”, kí hiệu: “"x Î A, p(x)” là mđ đúng khi và chỉ khi p(a) luôn đúng với mọi giá trị a Î A. " đgl lượng từ phổ dụng - Mệnh đề “Tồn tại (có ít nhất một) x thuộc A, p(x)” kí hiệu “$x Î A, p(x)” là mệnh đề đúng khi và chỉ khi có ít nhất một giá trị x= a’Î A nào đó sao cho mệnh đề p(a’) đúng. $ đgl lượng từ tồn tại Vị từ - Lượng từ Chương 1. Cơ sở lôgic 30 Chương 1. Cơ sở lôgic PDF created with pdfFactory Pro trial version www.pdffactory.com Cho p(x, y) là một vị từ theo hai biến x, y xác định trên A´B. Ta định nghĩa các mệnh đề lượng từ hóa của p(x, y) như sau: “"xÎA,"yÎB, p(x, y)” º “"xÎA, ("yÎB, p(x, y))” “"xÎA, $yÎB, p(x, y)” º “"xÎA, ($yÎB, p(x, y))” “$xÎA, "yÎB, p(x, y)” º “$xÎA, ("yÎB, p(x, y))” “$xÎA, $yÎB, p(x, y)” º “$xÎA, ($yÎB, p(x, y))” Vị từ - Lượng từ Chương 1. Cơ sở lôgic 31 Chương 1. Cơ sở lôgic PDF created with pdfFactory Pro trial version www.pdffactory.com Ví dụ: Các mệnh đề sau đúng hay sai? - “"x Î R, ” - “$x Î R, ” - “"x Î R, "y Î R, 2x + y < 1” - “"x Î R, $y Î R, 2x + y < 1” - “$x Î R, "y Î R, x + 2y < 1” - “$x Î R, $y Î R, x + 2y < 1” Vị từ - Lượng từ Chương 1. Cơ sở lôgic 32 Chương 1. Cơ sở lôgic 2x +6x+5 0£ 2x +6x+5 0£ PDF created with pdfFactory Pro trial version www.pdffactory.com Định lý Cho p(x, y) là một vị từ theo hai biến x, y xác định trên A´B. Khi đó: § “"xÎA, "yÎB, p(x, y)” Û “"yÎB, "xÎA, p(x, y)” § “$xÎA, $yÎB, p(x, y)” Û “$yÎB, $xÎA, p(x, y)” § “$xÎA, "yÎB, p(x, y)” Þ “"yÎB, $xÎA, p(x, y)” Phủ định của mệnh đề lượng từ hóa vị từ p(x,y,..) có được bằng cách: thay " thành $, thay $ thành ", và p(x,y,..) thành Ø p(x,y,..). Vị từ - Lượng từ Chương 1. Cơ sở lôgic 33 Chương 1. Cơ sở lôgic PDF created with pdfFactory Pro trial version www.pdffactory.com Với vị từ theo 1 biến ta có : Với vị từ theo 2 biến Vị từ - Lượng từ Chương 1. Cơ sở lôgic 34 Chương 1. Cơ sở lôgic x , (x) x , (x)A p A p" Î Û $ Î x , (x) x , (x)A p A p$ Î Û " Î x , y , (x, y) x , y , (x, y)A B p A B p" Î " Î Û $ Î $ Î x , y , (x, y) x , y , (x, y)A B p A B p" Î $ Î Û $ Î " Î x , y , (x, y) x , y , (x, y)A B p A B p$ Î " Î Û " Î $ Î x , y , (x, y) x , y , (x, y)A B p A B p$ Î $ Î Û " Î " Î PDF created with pdfFactory Pro trial version www.pdffactory.com Ví dụ phủ định các mệnh đề sau - “"x Î A, 2x + 1 £ 0” - “"e > 0, $d > 0, "xÎR, |x – a|<d Þ |f(x) – f(a)|<e” Vị từ - Lượng từ PDF created with pdfFactory Pro trial version www.pdffactory.com Ví dụ: Chứng minh Qui nạp ( ) 21 3 5 ... 2n 1 n+ + + + - = PDF created with pdfFactory Pro trial version www.pdffactory.com