Toán rời rạc Cơ Sở logic

Toán rời rạc Cơ Sở logic * Nội Dung: Mệnh đề và dạng mệnh đề Các luật logic và quy tắc thay thế Quy tắc suy diễn Vị từ và lượng từ Nguyên lý quy nạp * Phần I: Mệnh đề và dạng mệnh đề 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ụ: - mặt trời quay quanh trái đất - Buồn ngủ quá ! (ko là mệnh đề) - Học bài đi ! (ko là mệnh đề) Ký hiệu: người ta dùng các ký hiệu P, Q, R… để chỉ mệnh đề. * 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. 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) * Phần I: Mệnh đề và dạng 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”. Ví dụ: - 2 không là số nguyên tố - 2 là số nguyên tố (sơ cấp) - Hôm nay trời đẹp và 1 +1 =3 * Phần I: Mệnh đề và dạng mệnh đề Các phép nối logic: có 5 phép nối 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ố 1 >2 Phủ định : 1≤ 2 * Phần I: Mệnh đề và dạng mệnh đề * Phần I: Mệnh đề và dạng mệnh đề * Phần I: Mệnh đề và dạng mệnh đề * Phần I: Mệnh đề và dạng mệnh đề Ví dụ: Nếu 1 = 2 thì ……………….(Đ) Nếu trái đất quay quanh mặt trời thì 1 +3 =5 (S) ……………….kéo theo 6>5 (Đ) * Phần I: Mệnh đề và dạng mệnh đề * Phần I: Mệnh đề và dạng mệnh đề Ví dụ: 2=4 khi và chỉ khi 2+1=0 (Đ) 6 chia hết cho 3 khi và chi khi 6 chia hết cho 2 (Đ) London là thành phố nước Anh nếu và chỉ nếu thành phố HCM là thủ đô của VN (S) * Phần I: Mệnh đề và dạng mệnh đề * Phần I: Mệnh đề và dạng mệnh đề Với E là một dạng mệnh đề các biến mệnh đề 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 đề. * Phần I: Mệnh đề và dạng mệnh đề * Phần I: Mệnh đề và dạng mệnh đề * Phần I: Mệnh đề và dạng mệnh đề Các luật logic Các luật logic là cơ sở để ta thực hiện các biến đổi trên một biểu thức logic để có được một biểu thức logic mới tương đương logic với biểu thức logic có trước. Mỗi biểu thức logic chota một sự khẳng định về sự tương đương của 2 biểu thức logic. Ta sẽ sử dụng các qui tắc thaythế và các luật logic đã biết để thực hiện các phép biến đổi tương đương trên các biêu thức logic. Phần II: Các luật logic và quy tắc thay thế * Phần II: Các luật logic và quy tắc thay thế * Phần II: Các luật logic và quy tắc thay thế * Phần II: Các luật logic và quy tắc thay thế * Phần II: Các luật logic và quy tắc thay thế * Phần II: Các luật logic và quy tắc thay thế * Phần II: Các luật logic và quy tắc thay thế * Phần II: Các luật logic và quy tắc thay thế Quy tắc thay thế Với các quy tắc thay thế ta có thể suy ra những biểu thức logic mới hay tìm ra các biểu thức logic tương đương với một biểu thức logic đã cho trước. * Quy tắc 1. Trong một biểu thức logic E, nếu ta thay thế một biểu thức con bởi một biểu thức logic tương đương bới biểu thức con đó thì ta sẽ được một biểu thức mới E’ tương đương với biểu thức E. Ví dụ: p ^ ¬ q  ¬ ¬p ^ ¬ q Phần II: Các luật logic và quy tắc thay thế * Phần II: Các luật logic và quy tắc thay thế * Bài tập VD1.Chứng minh rằng (p→q) (¬ q →¬ p). VD2. Chứng minh các biểu thức sau là một hằng đúng. ((p →q) ^ p) →q (p ^ q) →(p ˅ q) ¬(p ^ q) ^ p → ¬ q Phần II: Các luật logic và quy tắc thay thế * Phần IIII: Quy tắc suy diễn * Phần III: Quy tắc suy diễn * Phần III: Quy tắc suy diễn * Phần III: Quy tắc suy diễn * Phần III: Quy tắc suy diễn * Phần III: Quy tắc suy diễn * Phần III: Quy tắc suy diễn * Phần III: Quy tắc suy diễn * Phần III: Quy tắc suy diễn * * Phần III: Quy tắc suy diễn Phần IV: Vị từ và lượng từ Vị từ Xét ví dụ: x = y + 5 x > 3 Vì các biến chưa có giá trị nên phát biểu chưa phải là mệnh đề. Các phát biểu dạng như trên xuất hiện rất nhiều. * Xét phát biểu x > 3, có 2 phần: - Biến x - Tính chất biến x (> 3), được gọi là vị từ (predicate) Vị từ mô tả tính chất của đối tượng (biến) hoặc quan hệ giữa các đối tượng Kí hiệu: P(x) => P(2), P(4): mệnh đề Phần IV: Vị từ và lượng từ * Đị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,… bằng những giá trị cụ thể thì p(x,y,…) trở thành mệnh đề Ví dụ: p(n) = “n là số nguyên tố”. q(x,y) = “2x+ y3 = 1” . r(x,y,z) = “2x+ 9y> z2”. Phần IV: Vị từ và lượng từ * Phần IV: Vị từ và lượng từ * Phần IV: Vị từ và lượng từ * Lưu ý: Vị từ không phải là mệnh đề. Phát biểu x > 1 không phải là mệnh đề, để biến x > 1 thành mệnh đề, có thể thực hiện 1 trong 2 cách sau: Gán giá trị cụ thể cho x Biến đổi phát biểu: “ tồn tại một số x sao cho x >1” hoặc “ với mọi số x, tồn tại x >1” Phần IV: Vị từ và lượng từ * Lượng từ Lượng hóa vị từ Quan sát các ví dụ sau: Cho tập hợp A = { 1,2,3,4,5}. Phần IV: Vị từ và lượng từ * (i) Liên kết với A vị từ: p(x) = “x là số nguyên chẵn”. Lần lượt cho x nhận giá trị trong A Ta có các mệnh đề: x = 1: p(1) = “ 1 là số nguyên chẵn” là mệnh đề sai x = 2: p(2) = “ 2 là số nguyên chẵn” là mệnh đề đúng x = 3: p(3) = “ 3 là số nguyên chẵn” là mệnh đề sai x = 4: p(4) = “ 4 là số nguyên chẵn” là mệnh đề đúng x = 5: p(5) = “ 5 là số nguyên chẵn” là mệnh đề sai Phần IV: Vị từ và lượng từ * (ii) Liên kết với A vị từ: q(y) = “ y > 0 ”. Lần lượt cho y nhận giá trị trong A ta có các mệnh đề: y = 1: q(1) = “ 1 > 0 ” là mệnh đề đúng y = 2: q(2) = “ 2 > 0 ” là mệnh đề đúng y = 3: q(3) = “ 3 > 0 ” là mệnh đề đúng y = 4: q(4) = “ 4 > 0 ” là mệnh đề đúng y = 5: q(5) = “ 5 > 0 ” là mệnh đề đúng Phần IV: Vị từ và lượng từ * (iii) Liên kết với A vị từ: r(z) = “ z2 = 10 ”. Lần lượt cho z nhận giá trị trong A ta có các mệnh đề: z = 1: r(1) = “ 12 = 10 ” là mệnh đề sai z = 2: r(2) = “ 22 = 10 ” là mệnh đề sai z = 3: r(3) = “ 32 = 10 ” là mệnh đề sai z = 4: r(4) = “ 42 = 10 ” là mệnh đề sai z = 5: r(5) = “ 52 = 10 ” là mệnh đề sai Phần IV: Vị từ và lượng từ * Qua ví dụ trên ta có nhận xét: [1]. Tìm được (ít nhất một) phần tử x = a trong A để p(a) là mệnh đề đúng. [2]. Lấy bất kỳ y = a trong A thì mệnh đề q(a) đúng. [3]. Thay bất kỳ z = a trong A thì mệnh đề r(a) sai. Nghĩa là không tìm được z0 nào trong A để mệnh đề có được tương ứng r(z0) là mệnh đề đúng. Phần IV: Vị từ và lượng từ * Các phát biểu [1], [2] và [3] cho ta một ước lượng về mức độ phổ biến của phần tử trong tập A làm cho vị từ liên kết tương ứng trở thành mệnh đề đúng. Ta gọi chúng là lượng hóa vị từ. Thông thường được viết kí hiệu dưới dạng biểu thức trong đó sử dụng các kí hiệu lượng từ hóa phổ dụng: ∀, ∃. Phần IV: Vị từ và lượng từ * Phần IV: Vị từ và lượng từ * Phần IV: Vị từ và lượng từ * Phần IV: Vị từ và lượng từ * Phần V: Nguyên lý quy nạp * Phần V: Nguyên lý quy nạp * Phần V: Nguyên lý quy nạp * Bài tập: Phần V: Nguyên lý quy nạp * Cảm ơn thầy cô và các bạn đã chú ý lắng nghe *