Bài giảng Luận lý toán học - Chương 2: Luận lý mệnh đề - Nguyễn Thanh Sơn

ntsơn 
 LUẬN LÝ TOÁN HỌC 
 (Mathematical Logic) 
Nguyễn Thanh Sơn 
Khoa KH&KT MT ĐH Bách Khoa TpHCM 
email : ntson@cse.hcmut.edu.vn 
http:\\www.cse.hcmut.edu.vn\~ntson 
ntsơn 
Chương 2 : Luận lý mệnh đề 
ntsơn 
Chương 1 
Nội dung 
I. Cấu trúc của luận lý mệnh đề (LLMĐ) 
II. Suy luận tự nhiên trong LLMĐ 
III. Ngữ nghĩa của LLMĐ 
ntsơn 
I. Cấu trúc của 
 luận lý mệnh đề 
ntsơn 
Chương 1 
Thuật ngữ[11] 
•  Luận lý mệnh đề (LLMĐ) có tên tiếng Anh : 
–  Propositional logic. 
–  Propositional Calculus. 
•  Từ calculus là một thuật ngữ chung cho bất kỳ 
lãnh vực toán học liên quan tới việc tính toán 
(calculating). 
Thí dụ : 
 số học được gọi là calculus of numbers. 
ntsơn 
Chương 1 
Khảo sát 1 định nghĩa LLMĐ[11] 
•  Propositional Calculus là việc tính toán trên các 
mệnh đề (propositions hoặc statement). 
Mệnh đề là câu khai báo có giá trị đúng (T) 
hoặc sai (F). 
  xuất hiện một số câu hỏi : 
 - câu khai báo là gì (định nghĩa) ? 
 - dựa vào đâu để đánh giá đúng sai ? 
ntsơn 
Chương 1 
Đối tượng của LLMĐ 
•  Các loại câu của ngôn ngữ tự nhiên (NNTN) 
được định nghĩa từ Văn Phạm của NNTN. 
•  LLMĐ chỉ khảo sát câu khai báo. 
•  Câu khai báo thỏa một số điều kiện được LLMĐ 
gọi là công thức nguyên (atom). 
•  Công thức nguyên (CTN) là phần tử cơ bản của 
LLMĐ. 
ntsơn 
Chương 1 
Câu khai báo 
Thí dụ : 
“trời sẽ mưa" là câu khai báo. 
“hãy đi ra khỏi lớp" không là câu khai báo. 
 "2+2 = 4" là câu khai báo. 
 "1 = 0" là câu khai báo. 
ntsơn 
Chương 1 
Đánh giá đúng sai 
Thí dụ : 
 * Đại số là một ngành toán học. (đ) 
 * Mọi người cần có một đức tin. (đ|s) 
 * Mặt trời là một khối vuông. (đ|s) 
 * “2+2 = 4”. (đ|s) 
 * A. Lincoln đã là tổng thống của Mỹ. (đ) 
ntsơn 
Chương 1 
Công thức nguyên 
•  Công thức nguyên (atom) là câu khai báo : 
 - được biểu diễn bằng một ký hiệu. 
 - đánh giá được đ, s. 
 - sự đánh giá đúng sai không thay đổi theo 
 không gian & thời gian. 
•  Giá trị đúng sai của 1 câu khai báo được gọi là 
thực trị (truth value). 
ntsơn 
Chương 1 
Công thức nguyên 
Thí dụ : 
 “Đoàn Thị Điểm là dịch giả của Chinh phụ ngâm” 
 → được ký hiệu là A (trong LLMĐ). 
 “Mặt trời xoay quanh trái đất”. 
 → được ký hiệu là B. 
 “Nếu hàm số f liên tục thì f khả vi”. 
 → được ký hiệu là C. 
 “Phong đi câu cá vào ngày chúa nhật”. 
 → được ký hiệu là D. 
ntsơn 
Chương 1 
Công thức 
•  Thế giới thực tạo sự liên kết giữa câu để tăng 
khả năng diễn đạt. 
•  Luận lý mệnh đề cũng mô phỏng lại sự liên kết 
này. 
(A→B)∨(C∧(¬D)) Câu + câu + câu + câu 
Thế giới thực 
Luận lý mệnh đề 
ntsơn 
Chương 1 
Toán tử 
•  Chỉ một số liên từ trong thế giới thực được mô 
phỏng lại trong LLMĐ thành các toán tử. 
∨ 
∧ 
→ 
¬ 
↔ 
hoặc, hay, 
và, 
nếu  thì  , 
không, 
tương đương, 
Thế giới thực 
Luận lý mệnh đề 
ntsơn 
Chương 1 
Công thức 
•  Công thức hoàn hảo là sự kết hợp hữu hạn lần 
các công thức nguyên bằng các toán tử 
∨, ∧, ¬, →. 
•  Công thức hoàn hảo (well-formed formula - 
WFF) được gọi tắt là công thức (CT). 
•  WFF được định nghĩa ở dạng BNF (Backus Naur 
form) 
 φ ::= π | (¬φ) | (φ ∧ φ) | (φ ∨ φ) | (φ → φ) 
 với π là công thức ngyên. 
ntsơn 
Chương 1 
Đại số Boolean 
•  Luận lý mệnh đề được biểu diễn dưới dạng một 
cấu trúc đại số. 
•  , với B là tập công thức nguyên. 
ntsơn 
Chương 1 
Cây phân tích 
•  Cây phân tích (parse tree) là biểu diễn bằng đồ 
thị của một công thức. Cây phân tích là cây nhị 
phân có gốc, đỉnh là toán tử và lá là CT nguyên. 
 Thí dụ : (¬Q → P) ∧ ((Q → R) ∨ R) 
∧ 
→ 
¬ 
Q 
P 
∨ 
→ 
Q R 
R 
ntsơn 
Chương 1 
Cây phân tích 
•  Đường (path) của một cây phân tích là một 
hành trình đi từ gốc đến đỉnh lá. 
 Thí dụ : 
∧ 
→ 
¬ 
X ∨ 
¬ 
Y 
Z 
X 
ntsơn 
Chương 1 
Cây phân tích 
•  Chiều cao của 1 cây phân tích là số cạnh của 
con đường dài nhất cộng 1. 
Thí dụ : 
∧ 
→ 
Y 
X ∨ 
¬ 
Z 
X 
Chiều cao là 4 
∧ 
→ 
X ¬ 
→ 
Y 
Z ∨ 
Chiều cao là 5 
¬ 
Z X 
ntsơn 
Chương 1 
Vấn đề của các toán tử 
•  Các liên từ “or”, “xor”. 
 Tên cướp mang súng hoặc dao : S ∨ D. 
 (có thể cả 2) 
 Con dao được làm bằng sắt hoặc gỗ : S ⊕ G. 
 (chỉ một trong hai) 
ntsơn 
Chương 1 
Vấn đề “và”[11] 
•  P : “Thiên hà này sẽ biến mất vào lỗ đen của vũ trụ" và 
Q : "2+2 = 4," cái gì là P ∧ Q? 
Giải 
 P ∧ Q : “Thiên hà này sẽ biến mất vào lỗ đen của vũ trụ 
và 2+2=4," cách diễn đạt sau sẽ làm ngạc nhiên : 
“Không những thiên hà này sẽ biến mất vào lỗ đen của 
vũ trụ mà còn có 2+2=4 " (not only  but). 
ntsơn 
Chương 1 
Vấn đề “và”[11] 
•  Đánh giá mệnh đề P ∧ (¬Q) ? 
Giải 
 P ∧ (¬Q) có nghĩa là : " Thiên hà này sẽ biến mất vào 
lỗ đen của vũ trụ" và 2+2 ≠ 4," hoặc nói cách khác : " 
Thiên hà này sẽ biến mất vào lỗ đen của vũ trụ" hơn thế 
nữa (moreover) hai cộng hai khác bốn. 
ntsơn 
Chương 1 
Hết slide 
ntsơn 
Bài tập 
Chương 2 : Luận lý mệnh đề 
ntsơn 
Chương 1 
Thảo luận nhóm 5 phút 
•  Mỗi nhóm tìm các bài toán giải được bằng logic 
(bài tập này được làm sau khi học chương 2). 
•  Hiệu chỉnh lài các bài toán logic đã trình bày lần 
trước, viết lại theo cấu trúc đã được học trong 
chương 2. Trình bày bằng slide trước lớp. 
ntsơn 
Chương 1 
Câu khai báo 
1. Phát biểu nào là câu khai báo và chỉ ra thực trị : 
 a. Không được mở máy tính. 
 b. Thành phố Mỹ Tho ở đâu ? 
 c. Ở sông Sài Gòn không có cá sấu. 
 d. Việc lập trình rất hứng thú. 
 e. A∩(B∪C) = (A∩B)∪(A∩C), A,B,C là tập hợp. 
 f. Hôm nay là ngày thứ 3. 
 g. 2 + 3 = 6. 
 h. Hà Nôi là thủ đô của VN. 
 i. Thiết kế CSDL là bắt buộc khi lập trình. 
ntsơn 
Chương 1 
Câu khai báo 
2. Tìm phủ định của các câu khai báo sau : 
 a. Ở sông Sài Gòn không có cá sấu. 
 b. A∩(B∪C) = (A∩B)∪(A∩C). 
 c. Hôm nay là ngày thứ 3. 
 d. 2 + 3 = 6 
 e. Hà Nôi là thủ đô của nước VN. 
 f. Nếu có tiền tôi sẽ mua xe phân khối lớn. 
 g. Thiết kế CSDL là bắt buộc khi lập trình. 
 h. Tôi tới lớp mỗi khi gần có kỳ thi. 
 i. Số x là nguyên tố nếu nó không có ước số khác 1, x. 
ntsơn 
Chương 1 
Câu khai báo 
3. Biểu diễn đoạn văn sau bằng luận lý mệnh đề : 
Nếu anh ta mua xe thì anh ta trúng số hoặc thừa 
hưởng gia tài. 
Anh ta không thừa hưởng gia tài. 
Vậy nếu anh ta không trúng số thì anh ta không 
mua xe. 
ntsơn 
Chương 1 
Câu khai báo 
4. Diễn tả các công thức luận lý mệnh đề bằng các 
phát biểu (câu khai báo) : 
 M = Hôm nay thứ 5, N = Đi dã ngoại 
 P = Câu cá. 
 1. M → (N ∨ P) 
 2. M ∧ N 
 3. ¬P ∧ ¬M 
 4. ¬N → ¬M 
 5. ¬M ∨ (P ∧ N) 
ntsơn 
Chương 1 
Hết slide