CẤU TRÚC RỜI RẠC - Cơ sở Logic

Chia sẻ: Lê Quảng Vàng | Ngày: | Loại File: PDF | Số trang:60

Thêm vào BST

Báo xấu

96
lượt xem 25
download

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

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 đề.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: CẤU TRÚC RỜI RẠC - Cơ sở Logic

GIỚI THIỆU VỀ NHÓM Cơ sở Logic 1
1 Nguyễn Đức Duy 2 Nguyễn Văn Thái 3 Nguyễn Quang Thái 4 Nguyễn Lê Huy 5 Võ Đình Phú 6 Phan Đình Phong Cơ sở Logic 2
CẤU TRÚC RỜI RẠC CƠ SỞ LOGIC Cơ sở Logic 3
CƠ SỞ LOGIC I. MỆNH ĐỀ II. DẠNG MỆNH ĐỀ III. QUY TẮC SUY DIỄN IV. VỊ TỪ, LƯỢNG TỪ V. QUY NẠP TOÁN HỌC Cơ sở Logic 4
CƠ SỞ LOGIC Cơ sở Logic 5
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 6
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 7
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 8
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ị: 𝑃 � 𝑷 0 1 1 0 Ví dụ:  𝑃 = “3 là số nguyên tố”; ¬𝑃 = “3 không là số nguyên tố”  𝑄 = "4 ≥ 3“ ¬𝑄 = "4 < 3” Cơ sở Logic 9
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 10
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 11
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 12
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 13
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 14
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 15
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 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) Ví dụ  𝑃 = “𝜋 > 3” 𝑄 = “5 = 3” 𝑃 ↔ 𝑄 = "𝜋 > 3 kéo theo 5 = 3“ (Sai) Cơ sở Logic 17
CƠ SỞ LOGIC Cơ sở Logic 18
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) Cơ sở Logic 19
Độ ư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: →, ↔ Cơ sở Logic 20