Cấu trúc rời rạc - Cơ sở logic

GIỚI THIỆU VỀ NHÓM 1 Cơ sở Logic Nguyễn Đức Duy 1 Nguyễn Văn Thái 2 Nguyễn Quang Thái 3 Nguyễn Lê Huy 4 Võ Đình Phú 5 Phan Đình Phong 6 2 Cơ sở Logic CẤU TRÚC RỜI RẠC CƠ SỞ LOGIC 3 Cơ sở Logic CƠ SỞ LOGIC V. QUY NẠP TOÁN HỌC IV. VỊ TỪ, LƯỢNG TỪ III. QUY TẮC SUY DIỄN II. DẠNG MỆNH ĐỀ I. MỆNH ĐỀ 4 Cơ sở Logic CƠ SỞ LOGIC 5 Cơ sở Logic Cơ sở Logic 6 Mệnh đề là gì?  Mệnh đề là một khẳng định có giá trị chân lý xác định, đúng hoặc sai (khách quan).  Tính đúng sai này được gọi là chân trị của mệnh đề.  Kí hiệu: ta dùng các kí hiệu P, Q, R… để chỉ các mệnh đề. Đúng: Đ, T (True) hay 1. Sai: S, F (False) hay 0.  Câu hỏi, câu cảm thán, mệnh lệnh… không là mệnh đề. Cơ sở Logic 7 Ví dụ Các khẳng định sau là mệnh đề:  Nước sôi ở 100oC  1+1=3  Việt Nam ở Đông Nam Á Các khẳng định sau không phải mệnh đề: × Trời lạnh quá! (chủ quan) × Hãy đọc sách! (mệnh lệnh) × Tam giác đều là tam giác có 3 cạnh bằng nhau. (mệnh đề) × 𝑥 là số không âm. (chân trị phụ thuộc vào biến 𝑥) Cơ sở Logic 8 Phân loại mệnh đề  Mệnh đề sơ cấp: 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ụ: “Nước đóng sôi ở 100oC”  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, NẾU … THÌ …, SUY RA, KÉO THEO, KHI VÀ CHỈ KHI,…) hoặc trạng từ “KHÔNG”. Ví dụ: “Nếu 1+1=2 thì 1+2>2” Cơ sở Logic 9 Các phép toán với mệnh đề 1. Phép phủ định  Phủ định của mệnh đề 𝑃 được kí hiệu 𝑃� hay ¬𝑃.  Bảng chân trị: Ví dụ:  𝑃 = “3 là số nguyên tố”; ¬𝑃 = “3 không là số nguyên tố”  𝑄 = "4 ≥ 3“ ¬𝑄 = "4 < 3” 𝑃 𝑷� 0 1 1 0 Cơ sở Logic 10 Các phép toán với mệnh đề 2. Phép hội (nối liền, giao)  Hội của hai mệnh đề 𝑃 và 𝑄 được kí hiệu 𝑃 ∧ 𝑄.  𝑃 ∧ 𝑄 đúng khi và chỉ khi 𝑃 và 𝑄 đều đúng.  Bảng chân trị: 𝑃 𝑄 𝑷 ∧ 𝑸 0 0 0 0 1 0 1 0 0 1 1 1 Cơ sở Logic 11 Các phép toán với mệnh đề 2. Phép hội (nối liền, giao) Ví dụ  𝑃 = “7 là số lẻ” 𝑄 = “7 là số nguyên tố” 𝑃 ∧ 𝑄 = "7 là số lẻ và là số nguyên tố” (Đúng) Cơ sở Logic 12 Các phép toán với mệnh đề 3. Phép tuyển (nối rời, hợp)  Tuyển của hai mệnh đề 𝑃 và 𝑄 được kí hiệu 𝑃 ∨ 𝑄.  𝑃 ∨ 𝑄 sai khi và chỉ khi 𝑃 và 𝑄 đều sai.  Bảng chân trị: 𝑃 𝑄 𝑷 ∨ 𝑸 0 0 0 0 1 1 1 0 1 1 1 1 Cơ sở Logic 13 Các phép toán với mệnh đề 3. Phép tuyển (nối rời, hợp) Ví dụ  𝑃 = “𝜋 > 3” 𝑄 = “𝜋 = 3” 𝑃 ∨ 𝑄 = "𝜋 ≥ 3“ (Đúng) Cơ sở Logic 14 Các phép toán với mệnh đề 4. Phép kéo theo (suy ra)  Mệnh đề “𝑃 kéo theo 𝑄” của hai mệnh đề 𝑃 và 𝑄 (hay “Nếu 𝑃 thì 𝑄” hay “𝑃 là điều kiện đủ của 𝑄” hay “𝑄 là điều kiện cần của 𝑃”) kí hiệu là 𝑃 ⟶ 𝑄.  𝑃 ⟶ 𝑄 sai khi và chỉ khi 𝑃 đúng và 𝑄 sai.  Bảng chân trị: 𝑃 𝑄 𝑃 ⟶ 𝑄 0 0 1 0 1 1 1 0 0 1 1 1 Cơ sở Logic 15 Các phép toán với mệnh đề 4. Phép kéo theo (suy ra) Ví dụ  𝑃 = “ sin 𝜋 > 1” 𝑄 = “𝜋 ≥ 4” 𝑃 → 𝑄 = "𝑠𝑠𝑠 𝜋 > 1 khi và chỉ khi 𝜋 ≥ 4“ (Đúng) Cơ sở Logic 16 Các phép toán với mệnh đề 5. Phép kéo theo hai chiều (phép tương đương)  Mệnh đề “𝑃 kéo theo 𝑄 và ngược lại” (hay “𝑃 nếu và chỉ nếu 𝑄” hay “𝑃 khi và chỉ khi 𝑄” hay “𝑃 là điều kiện cần và đủ của 𝑄”) kí hiệu là 𝑃 ⟷ 𝑄.  𝑃 ⟷ 𝑄 đúng khi và chỉ khi 𝑃 và 𝑄 có cùng chân trị.  Bảng chân trị: 𝑃 𝑄 𝑃 ⟷ 𝑄 0 0 1 0 1 0 1 0 0 1 1 1 Cơ sở Logic 17 Các phép toán với mệnh đề 5. Phép kéo theo hai chiều (phép tương đương) Ví dụ  𝑃 = “𝜋 > 3” 𝑄 = “5 = 3” 𝑃 ↔ 𝑄 = "𝜋 > 3 kéo theo 5 = 3“ (Sai) CƠ SỞ LOGIC 18 Cơ sở Logic 19 Cơ sở Logic Dạng mệnh đề là gì?  Dạng mệnh đề 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 ¬(phủ định), ∧(hội),∨(tuyển), ⟶(kéo theo), ⟷(kéo theo hai chiều) và dấu đóng mở ngoặc (). Ví dụ  E(p,q) = p ∧ ¬p  F(p,q)= ¬(¬p ∨ q)  F(p,q,r) = (p ∧ q) → ¬(q ∨ r) 20 Cơ sở Logic Độ ư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: →, ↔ 21 Cơ sở Logic Bảng chân trị của dạng mệnh đề  Bảng chân trị của dạng mệnh đề 𝐸(𝑝, 𝑞, 𝑟) 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 đề 𝐸 theo chân trị của các biến mệnh đề 𝑝, 𝑞, 𝑟.  Nếu có 𝒏 biến, bảng này sẽ có 𝟐𝒏 dòng, chưa kể dòng tiêu đề. 22 Cơ sở Logic Ví dụ  Lập bảng chân trị dạng mệnh đề 𝐸(𝑝, 𝑞, 𝑟) = (𝑝 ∨ 𝑞) → 𝑟 Bảng chân trị 𝑝 𝑞 𝑟 𝑝 ∨ 𝑞 (𝒑 ∨ 𝒒) → 𝒓 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 23 Cơ sở Logic Hệ quả logic – tương đương logic  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ị (là đúng).  Ký hiệu: E⟺ 𝐹. • 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. Ví dụ  ¬(p ∨ q) ⇔ ¬p ∧ ¬q  p ∧ (p ∧ q) ⇔ p 24 Cơ sở Logic Định lí  Hai dạng mệnh đề 𝐸 và 𝐹 tương đương với nhau khi và chỉ khi 𝐸 ↔ 𝐹 là hằng đúng. Hệ quả logic  𝐹 được gọi là hệ quả logic của 𝐸 nếu 𝐸 → 𝐹 là hằng đúng. Ký hiệu: 𝐸 ⇒ 𝐹 25 Cơ sở Logic Ví dụ: Chứng minh dạng mệnh đề ( (p ∨ q) ∧ ¬p) → q là hằng đúng. 𝒑 𝒒 ¬𝑝 𝒑 ∨ 𝒒 𝒑 ∨ 𝒒 ∧¬𝒑 𝒑 ∨ 𝒒 ∧¬𝒑 → 𝒒 0 0 1 0 0 1 0 1 1 1 1 1 1 0 0 1 0 1 1 1 0 1 0 1 26 Cơ sở Logic Các qui tắc thay thế 1. Qui tắc thay thế 2:  Giả sử dạng mệnh đề 𝐸(𝑝, 𝑞, 𝑟… ) là một hằng đúng. Nếu ta thay thế những nơi 𝑝 xuất hiện trong 𝐸 bởi một 𝐹(𝑝𝑝,𝑞𝑝, 𝑟𝑝) thì dạng mệnh đề nhận được theo các biến 𝑞, 𝑟… ,𝑝𝑝,𝑞𝑝, 𝑟𝑝, … vẫn còn là một hằng đúng. Ví dụ :  E( p, q ) = ( ( p ∨ q ) ∧ ¬ p) → q là hằng đúng nên E( r ∨ t, q ) = ( ( (r ∨ t) ∨ q) ∨ ¬ (r ∨ t) ) → q cũng là hằng đúng. 27 Cơ sở Logic Các luật logic Tên luật logic Biểu diễn Phủ định của phủ định ¬¬p⇔p Qui tắc De Morgan ¬ (p∨q)⇔¬p∧¬q ¬ (p∧q)⇔¬p∨¬q Luật giao hoán p∨q⇔q∨p p∧q⇔q∧ p Luật kết hợp (p ∨ q) ∨ r ⇔ p ∨ (q ∨ r) (p ∧ q) ∧ r ⇔ p ∧ (q ∧ r) Luật phân phối p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r) p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r) Luật lũy đẳng p ∧ p ⇔ p p ∨ p ⇔ p 28 Cơ sở Logic Các luật logic Tên luật logic Biểu diễn Luật trung hòa 𝑝∨0 ⇔ 𝑝 𝑝∧1 ⇔ 𝑝 Luật về phần tử bù 𝑝∨¬𝑝⇔1 𝑝∧¬𝑝⇔0 Luật thống trị 𝑝∧0 ⇔ 0 𝑝∨1 ⇔ 1 Luật hấp thu p∨(p ∧ q) ⇔p p∧(p ∨ q) ⇔p Luật về phép kéo theo p → q ⇔ ¬p ∨ q ⇔ ¬ q → ¬ p 29 Cơ sở Logic Các luật logic 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 Cách 1:(¬p → r) ∧ (q → r) ⇔ (p ˅ r) ∧ (¬q ˅ r) ⇔ (p ∧ ¬ q) ˅ r ⇔ ¬ (¬ p ˅ q) ˅ r ⇔ ¬ (p → q) ˅ r ⇔ (p → q) → r Cách 2: (p → q) → r ⇔ (¬ p ˅ q) → r ⇔ ¬ (¬ p ˅ q) ˅ r ⇔ (p ∧ ¬ q) ˅ r ⇔ (p ˅ r) ∧ (¬q ˅ r) ⇔ (¬p → r) ∧ (q → r) CƠ SỞ LOGIC 30 Cơ sở Logic 31 Cơ sở Logic Áp dụng quy tắc suy diễn để làm gì?  Trong các chứng minh toán học, xuất phát từ một số khẳng định đúng 𝑝, 𝑞, 𝑟…(tiền đề), ta áp dụng các quy tắc suy diễn để suy ra chân lí của một mệnh đề ℎ mà ta gọi là kết luận.  Nói cách khác, dùng các quy tắc suy diễn để chứng minh: (𝑝 ∧ 𝑞 ∧ 𝑟. . ) có hệ quả logic là ℎ.  Ta thường mô hình hóa phép suy luận đó dưới dạng: 𝑝 𝑞 𝑟 ∴ ℎ 32 Cơ sở Logic Các quy tắc suy diễn 1. Qui tắc khẳng định (Modus Ponens):  Dạng hằng đúng [(p → q) ∧ p] → q [(p ∨ q) ∧ ¬p] → q  Dạng sơ đồ: 𝑝→𝑞 𝑝 ∴𝑞 ; 𝑝∨𝑞¬𝑝 ∴𝑞 33 Cơ sở Logic Các quy tắc suy diễn 1. Qui tắc khẳng định (Modus Ponens): Ví dụ:  Nếu An học giỏi thì An sẽ đạt kết quả cao An học giỏi Suy ra: An đạt kết quả cao.  Trời đẹp thì ta đi dã ngoại Trời đẹp Suy ra: đi dã ngoại. 34 Cơ sở Logic Các quy tắc suy diễn 2. Qui tắc phủ định  Dạng hằng đúng [(p → q) ∧ ¬q ] → ¬ p  Dạng sơ đồ: 𝑝→𝑞¬𝑞 ∴¬𝑝 35 Cơ sở Logic Các quy tắc suy diễn 2. Qui tắc phủ định Ví dụ:  Nếu hôm nay là ngày lễ thì cả lớp được nghỉ Mà hôm nay không được nghỉ Suy ra: hôm nay không phải là ngày lễ  Nếu Dũng đi học đầy đủ thì sẽ đậu môn Toán. Mà Dũng rớt môn Toán Suy ra: Dũng không đi học đầy đủ 36 Cơ sở Logic Các quy tắc suy diễn 3. Qui tắc tam đoạn luận  Dạng hằng đúng [(p → q) ∧ (p → r)] → (p → r)  Dạng sơ đồ: 𝑝→𝑞 𝑞→𝑟 ∴(𝑝→𝑟) 37 Cơ sở Logic Các quy tắc suy diễn 3. Qui tắc tam đoạn luận Ví dụ • Nếu siêng năng thì sẽ học giỏi Nếu học giỏi thì sẽ đạt kết quả cao. Suy ra: Nếu siêng năng thì sẽ đạt kết quả cao • Nếu tập luyện thể dục thì sẽ tăng cường sức khỏe Nếu sức khỏe được tăng cường thì tuổi thọ sẽ tăng theo Suy ra: Nếu tập thể thì tuổi thọ sẽ tăng 38 Cơ sở Logic Các quy tắc suy diễn 4. Qui tắc phản chứng (qui tắc mâu thuẫn)  Dạng hằng đúng (𝑝1 ∧ 𝑝2 ∧ ⋯∧ 𝑝𝑠) → 𝑞 ⇔ 𝑝1 ∧ 𝑝2 ∧ ⋯∧ 𝑝𝑠 ∧¬𝑞 → 0  Ta có hai mênh đề trên tương đương logic với nhau cho nên nếu mệnh đề bên phải là hằng đúng thì mệnh đề bên trái cũng là một hằng đúng. Ta chứng minh phản chứng bằng cách thêm phủ định của kết luận q vào tiền đề, từ đó suy ra được một mâu thuẫn, vậy mệnh đề bên phải là một hằng đúng. 39 Cơ sở Logic Các quy tắc suy diễn 4. Qui tắc phản chứng (qui tắc mâu thuẫn) Ví dụ: để chứng minh mệnh đề 𝑝 → 𝑟¬𝑝 → 𝑞 𝑞 → 𝑠 ∴ ¬𝑟 → 𝑠 ta chứng minh mệnh đề sau là hằng đúng: 𝑝 → 𝑟¬𝑝 → 𝑞 𝑞 → 𝑠¬𝑟¬𝑠 ∴ 0 `` 40 Cơ sở Logic Các quy tắc suy diễn 5. Qui tắc chứng minh theo trường hợp  Dạng hằng đúng 𝑝 → 𝑞 ∧ (𝑞 → 𝑟) → (𝑝 → 𝑟)  Ý nghĩa: Nếu 𝑝 suy ra 𝑟 và q suy ra 𝑟 thì 𝑝 hay 𝑞 cũng có thể suy ra 𝑟. 41 Cơ sở Logic Các quy tắc suy diễn 5. Qui tắc chứng minh theo trường hợp Ví dụ: Chứng minh f(n)=n3+2n luôn chia hết cho 3 với n là số nguyên tùy ý. Ta xét 2 trường hợp có thể xảy ra: • 𝑠 chia hết cho 3, lúc này thì hiển nhiên 𝑓(𝑠) chia hết cho 3 • 𝑠 không chia hết cho 3 nên 𝑠 được viết dưới dạng 𝑠 = 3𝑘 ± 1 với k là một số nguyên bất kỳ Thay vào ta được: 𝑠3 + 2𝑠 = (3𝑘 ± 1)3 + 2(3𝑘 ± 1) =3(3𝑘2 ± 2𝑘 + 1) chia hết cho 3 Vậy 𝑓(𝑠) chia hết cho 3. 42 Cơ sở Logic Các quy tắc suy diễn 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ụ. 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 sẽ đượ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ễ 43 Cơ sở Logic Các quy tắc suy diễn 6. Phản ví dụ Ví dụ 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ể. ¬𝑝 → 𝑞 𝑞 ∧ 𝑟 → 𝑠 𝑡 → 𝑟 𝑝 ∴ ¬𝑠 → ¬𝑡 𝑠 = 0; 𝑡 = 1;𝑝 = 1;𝑞 = 0; 𝑟 = 1 44 Cơ sở Logic Các quy tắc suy diễn Bài tập: Chứng minh 𝒑� ∨ 𝒒 ⟹ 𝒓 ∧ 𝒔 (𝟏) �̅� (𝟐) 𝒓 ⟹ 𝒕 (𝟑) ∴ 𝒔 ⟹ 𝒑 (𝟒) Cách 1: (2),(3) :�̅� (5) (5) : 𝑟 ∧ 𝑠 (6) (6),(1) : �̅� ∨ 𝑞 (7) (8) : 𝑝 ∧ 𝑞� (9) (9) : 𝑝 (10) (10) : �̅� ∨ 𝑝 (11) (11) : 𝑠 ⟹ 𝑝 (4) Cách 2: ta chứng minh 𝒑� ∨ 𝒒 ⟹ 𝒓 ∧ 𝒔 (𝟏) �̅� (𝟐) 𝒓 ⟹ 𝒕 (𝟑) 𝒔 ⟹ 𝒑 (𝟒) ∴ 𝟎 (𝟓) CƠ SỞ LOGIC 45 Cơ sở Logic 46 Cơ sở Logic Vị từ là gì? Cho A là một tập hợp khác rỗng. Giả sử, ứng với mỗi x=a∈A ta có một mệnh đề p(a). Khi đó, ta nói p=p(x) là một vị từ theo một biến (xác định trên A). Ví dụ • 𝑝(𝑥) = “𝑥 là số chính phương” • 𝑞(𝑦) = “𝑦2 là một số dương” 47 Cơ sở Logic Dạng tổng quát  Tổng quát, cho 𝐴1,𝐴2,𝐴3… là 𝑠 tập hợp khác trống. Giả sử rằng ứng với mỗi 𝑥1, 𝑥2, … , 𝑥𝑛 = 𝑎1,𝑎2, … ,𝑎𝑛 ∈ 𝐴1 × 𝐴2 ×. . .× 𝐴𝑛, ta có một mệnh đề 𝑝 𝑎1,𝑎2, … ,𝑎𝑛 . Khi đó ta nói 𝑝 = 𝑝 𝑥1, 𝑥2, … , 𝑥𝑛 là một vị từ theo 𝑠 biến (xác định trên 𝐴1 × 𝐴2 ×. . .× 𝐴𝑛). Lưu ý  Bản thân 𝑥1, 𝑥2, … , 𝑥𝑛không phải là mệnh đề  Nếu thay 𝑥1, 𝑥2, … , 𝑥𝑛 bằng các giá trị cụ thể thì 𝑝(𝑥1, 𝑥2, … , 𝑥𝑛) trở thành mệnh đề. Ví dụ: • 𝑝 𝑥,𝑦 = " 𝑥2 + 𝑦 = 1" • 𝑞 𝑥,𝑦, 𝑧 = “𝑥 + 𝑦 + 𝑧 là một số chẳn” 48 Cơ sở Logic Các phép toán trên vị từ Cho các vị từ 𝑝(𝑥), 𝑞(𝑥) theo một biến 𝑥∈𝐴. Khi ấy, ta có các phép toán tương ứng như trên mệnh đề: Phủ định ¬𝑝(𝑥) Phép nối liền (hội, giao) 𝑝 𝑥 ∧ 𝑞(𝑥) Phép nối rời (tuyển, hợp) 𝑝 𝑥 ∨ 𝑞(𝑥) Phép kéo theo 𝑝 𝑥 → 𝑞(𝑥) Phép kéo theo hai chiều 𝑝 𝑥 ↔ 𝑞(𝑥) 49 Cơ sở Logic Lượng từ 1. Lượng từ phổ biến (với mỗi, với mọi, tất cả) Kí hiệu: ∀ Mệnh đề “Với mọi x thuộc A 𝑝(𝑥)”, kí hiệu bởi “∀𝑥 ∈ 𝐴,𝑝(𝑥)”, là mệnh đề được định bởi “∀𝑥 ∈ 𝐴,𝑝(𝑥)” đúng khi và chỉ khi 𝑝(𝑎) luôn đúng với mọi giá trị 𝑎 ∈ 𝐴 2. Lượng từ tồn tại Kí hiệu: ∃ Mệnh đề “Tồn tại (ít nhất) (hay có (ít nhất) một 𝑥 thuộc 𝐴,𝑝(𝑥))” kí hiệu bởi: “∃𝑥 ∈ 𝐴,𝑝(𝑥)”, là mệnh đề được định bởi “∃𝑥 ∈ 𝐴,𝑝(𝑥)” đúng khi và chỉ khi có ít nhất một giá trị 𝑥 = 𝑎0 nào đó sao cho mệnh đề 𝑝(𝑎0) đúng. 50 Cơ sở Logic Mệnh đề lượng từ Cho A là một tập hợp khác rỗng. Giả sử, ứng với mỗi x=a∈A ta có một mệnh đề p(a). Khi đó, ta nói p=p(x) là một vị từ theo một biến (xác định trên A). Ví dụ • 𝑝(𝑥) = “𝑥 là số chính phương” • 𝑞(𝑦) = “𝑦2 là một số dương” 51 Cơ sở Logic Mệnh đề lượng từ hóa 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))” 52 Cơ sở Logic Ví dụ Các mệnh đề sau đúng hay sai? • “∀𝑥 ∈ 𝑅, 𝑥2 + 6𝑥 + 5 ≤ 0” • “∃𝑥 ∈ 𝑅, 𝑥2 + 6𝑥 + 5 ≤ 0” • “∀𝑥 ∈ 𝑅,∀𝑦 ∈ 𝑅, 2𝑥 + 𝑦 < 1“ • “∀𝑥 ∈ 𝑅, ∃𝑦 ∈ 𝑅, 2𝑥 + 𝑦 < 1” • “∃𝑥 ∈ 𝑅,∀𝑦 ∈ 𝑅, 𝑥 + 2𝑦 < 1” • “∃𝑥 ∈ 𝑅, ∃𝑦 ∈ 𝑅, 𝑥 + 2𝑦 < 1” 53 Cơ sở Logic Đị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 đó: • “∀𝑥∈𝐴,∀𝑦∈𝐵,𝑝(𝑥,𝑦)” ⇔ “∀𝑦∈𝐵,∀𝑥∈𝐴,𝑝(𝑥,𝑦)” • “∃𝑥∈𝐴, ∃𝑦∈𝐵,𝑝(𝑥,𝑦)” ⇔ “∃𝑦∈𝐵, ∃𝑥∈𝐴,𝑝(𝑥,𝑦)” • “∃𝑥∈𝐴,∀𝑦∈𝐵,𝑝(𝑥,𝑦)” ⇒ “∀𝑦∈𝐵, ∃𝑥∈𝐴,𝑝(𝑥,𝑦)” Phủ định của mệnh đề lượng từ hóa vị từ 𝑝(𝑥,𝑦, . . ) có được bằng cách: thay ∀ thành ∃, thay ∃ thành ∀, và 𝑝(𝑥,𝑦, . . ) thành ¬ 𝑝(𝑥,𝑦, . . ). 54 Cơ sở Logic Phủ định của mệnh đề lượng từ hóa Với vị từ theo 1 biến ta có Với vị từ theo 2 biến 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∃ ∈ ∀ ∈ ⇔ ∀ ∈ ∃ ∈ CƠ SỞ LOGIC 55 Cơ sở Logic 56 Cơ sở Logic Chứng minh quy nạp?  Ta có một dãy mệnh đề 𝑃𝑛0 ,𝑃𝑛0+1,𝑃𝑛0+2 (n là các số nguyên không âm)  Để chứng minh tất cả đều đúng ta dùng phép quy nạp. Phép chứng minh này thường dùng để chứng minh mệnh đề dạng ∀𝑠 𝑃(𝑠). Hai bước chứng minh  Bước 1: (Bước cơ sở) Chỉ ra 𝑃𝑛0 đúng.  Bước 2: (B ước quy nạp) Xét 𝑘tổng quát (𝑘 ≥ 𝑠0). Chứng minh nếu 𝑃 𝑘 đúng thì 𝑃 𝑘 + 1 cũng đúng. Trong đó 𝑃(𝑘) được gọi là giả thiết quy nạp. 57 Cơ sở Logic Ví dụ 1: Chứng minh 1 + 3 + 5 +⋯+ 2𝑠 − 1 = 𝑠2,∀𝑠 ≥ 1  B1: Chỉ ra 𝑃𝑛0 đúng Xét 𝑠 = 1, khi đó 𝑃1 = 1 = 12. Suy ra 𝑃𝑛0 đúng!  B2: Chứng minh quy nạp Xét 𝑘tổng quát ≥ 1. Giả sử 𝑃𝑘 đúng (đúng tới 𝑘), nghĩa là 1 + 3 + 5 +⋯+ 2𝑘 − 1 = 𝑘2,∀𝑘 ≥ 1 Ta chứng minh 𝑃𝑘+1 cũng đúng, nghĩa là 1 + 3 + 5 +⋯+ 2(𝑘 + 1)− 1 = (𝑘 + 1)2,∀𝑘 ≥ 1 𝑉𝑉 = 1 + 3 + 5 +⋯+ 2(𝑘 + 1)− 1 𝑉𝑉 = 1 + 3 + 5 +⋯+ 2𝑘 + 1 𝑉𝑉 = 1 + 3 + 5 +⋯+ 2𝑘 − 1 + 2𝑘 + 1 𝑉𝑉 = 𝑘2 + 2𝑘 + 1 = 𝑘 + 1 2 = 𝑉𝑃 Vậy, 𝑃𝑘+1 đúng. Kết luận: 1 + 3 + 5 +⋯+ 2𝑠 − 1 = 𝑠2,∀𝑠 ≥ 1 58 Cơ sở Logic Ví dụ 2: Chứng minh 12 + 22 +⋯+ 𝑠2 = 𝑠 𝑠 + 1 2𝑠 + 16 ∀𝑠 ≥ 1,𝑠0 = 1  B1: Chỉ ra 𝑃𝑛0 đúng Xét 𝑠 = 1 𝑃1 = 12 = 1 1 + 1 2 + 16 = 1 𝑃𝑛0 đúng!  B2: Chứng minh quy nạp Xét 𝑘 tổng quát ≥ 1. Giả sử 𝑃𝑘 đúng (đúng tới 𝑘), nghĩa là 12 + 22 +⋯+ 𝑘2 = 𝑘 𝑘 + 1 𝑘 + 26 Ta chứng minh 𝑃𝑘+1 cũng đúng, nghĩa là 𝑃𝑘+1 = 12 + 22 +⋯+ 𝑘2 + 𝑘 + 1 2 = 𝑘 + 1 𝑘 + 1 + 1 2 𝑘 + 1 + 16 59 Cơ sở Logic Ví dụ 2 (tt): 𝑉𝑉 = 12 + 22 +⋯+ 𝑘2 + 𝑘 + 1 2 𝑉𝑉 = 𝑘 𝑘 + 1 𝑘 + 26 + 𝑘 + 1 2 𝑉𝑉 = 𝑘 + 16 𝑘 2𝑘 + 1 + (𝑘 + 1) 𝑉𝑉 = 𝑘 + 16 2𝑘2 + 7𝑘 + 6 𝑉𝑃 = 𝑘 + 1 𝑘 + 1 + 1 2 𝑘 + 1 + 16 𝑉𝑃 = 𝑘+1 6 2𝑘2 + 7𝑘 + 6 = 𝑉𝑉Vậy, 𝑃𝑘+1 cũng đúng. Kết luận: 12 + 22 +⋯+ 𝑠2 = 𝑠 𝑠 + 1 2𝑠 + 16 ∀𝑠 ≥ 1,𝑠0 = 1 XIN CẢM ƠN Mọi người đã chú ý quan tâm theo dõi 60 Cơ sở Logic