›
›

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

Download
III. Ngữ nghĩa của  
luận lý mệnh đề  
Chương 2  
ntsơn  
Gán thực trị[*]  
•ꢀ Môi trường (Environments)  
Gán thực trị là gán giá trị T (đúng) hoặc F (sai)  
cho mỗi biến mệnh đề.  
Những nhà khoa học máy tính gọi việc gán giá  
trị cho các biến là một môi trường.  
[*] Sept. 10, 2007 Copyright © Albert R. Meyer, 2007. All rights reserved. lec 2M.17  
@Nguyễn Thanh Sơn  
ntsơn  
Gán thực trị  
Thí dụ :  
công thức P → (Q ∨ R)  
Môi trường ν gán các biến P, Q, R :  
ν(P) = T, ν(Q)= T, ν(R) = F.  
Môi trường µ gán các biến P, Q, R :  
µ(P) = F, µ(Q)= T, µ(R) = F.  
@Nguyễn Thanh Sơn  
ntsơn  
Diễn dịch  
•ꢀ Diễn dịch của một công thức là thế giới thực  
cùng với cách nhúng từng yếu tố của công thức  
vào thế giới thực đó.  
•ꢀ Nói cách khác diễn dịch là “gán” cho công thức  
một ý nghĩa của thế giới thực mà công thức  
được nhúng vào.  
@Nguyễn Thanh Sơn  
ntsơn  
Diễn dịch  
•ꢀ Có tác giả định nghĩa diễn dịch là cách đánh giá  
công thức và được đặc trưng bằng hàm đánh  
giá.  
•ꢀ Một số tài liệu định nghĩa khái niệm diễn dịch  
của một lớp các công thức thay vì của một công  
thức.  
@Nguyễn Thanh Sơn  
ntsơn  
Diễn dịch  
•ꢀ Diễn dịch trong LLMĐ có hữu hạn trường hợp  
đánh giá.  
A sai, B đúng  
A sai, B sai  
(A ∧ B) → ¬A  
A sai, B sai  
A đúng, B sai  
A đúng, B đúng  
•ꢀ Số trường hợp tương ứng với với số dòng của  
bảng thực trị.  
@Nguyễn Thanh Sơn  
ntsơn  
Diễn dịch  
•ꢀ Có thể đặc trưng diễn dịch của một CT bằng 1  
hàm đánh giá ν trên các CTN có trong công  
thức.  
Thí dụ :  
Qui ước CT đúng có giá trị 1 và sai là 0.  
Công thức (P ∧ Q) → R có diễn dịch I được đặc  
trưng bằng hàm đánh giá ν như sau :  
ν(P) = 1, ν(Q) = 0, ν(R) = 1.  
•ꢀ Để tiện cho việc trình bày, còn sử dụng ký hiệu  
νF thay cho ν(F).  
@Nguyễn Thanh Sơn  
ntsơn  
Thực trị của một công thức  
•ꢀ Nếu νA = 1, νB = 0 và νC = 0 thì  
ν((A→B) ∧ (C ∨¬A)) là đúng hay sai ?.  
Nếu νA = 0, νB = 1 và νC = 0 thì  
ν((¬A ∨ B) → ¬C) là đúng hay sai ?.  
Nếu νA = 0, νB = 1, νC = 0 và νD = 1 thì  
ν(((A ∨ C) ∧ B) → ¬D) là đúng hay sai.  
Cần phải xác định qui tắc đánh giá của các toán  
tử : ∨, ∧, ¬, →.  
@Nguyễn Thanh Sơn  
ntsơn  
Bảng thực trị  
•ꢀ P, Q là các công thức nguyên.  
P Q ¬P P∨Q P∧Q P→Q  
1 1  
1 0  
0 1  
0 0  
0
0
1
1
1
1
1
0
1
0
0
0
1
0
1
1
•ꢀ Tất cả diễn dịch của một công thức trong LLMĐ  
tướng ứng với các dòng của bảng thực trị.  
@Nguyễn Thanh Sơn  
ntsơn  
Bảng thực trị  
•ꢀ P → Q, tại sao đ → đ là đ, đ → s là s,  
s → đ là đ, s → s là đ ???.  
Thí dụ :  
P = Trời mưa, Q = Vũ mang dù.  
Tình trạng 1 : Trời mưa và Vũ mang dù.  
Tình trạng 2 : Trời mưa và Vũ không mang dù.  
Tình trạng 3 : Trời không mưa và Vũ mang dù.  
Tình trạng 4 : Trời khg mưa và Vũ khg mangdù.  
Nguyên tắc không vi phạm.  
@Nguyễn Thanh Sơn  
ntsơn  
Bảng thực trị  
•ꢀ Một cách định nghĩa khác, bảng thực trị là một  
hàm trên tập 2 phần tử đúng, sai ({đ, s}).  
•ꢀ Các toán tử luận lý là các hàm :  
¬ : {đ, s} → {đ, s}  
∧ : {đ, s} × {đ, s} → {đ, s}  
∨ : {đ, s} × {đ, s} → {đ, s}  
→ : {đ, s} × {đ, s} → {đ, s}  
@Nguyễn Thanh Sơn  
ntsơn  
Thực trị của một công thức  
Thí dụ :  
Tính thực trị của công thức (X → (¬Y∨Z)) ∧ ¬X  
X Y  
1 1  
1 1  
1 0  
1 0  
0 1  
0 1  
0 0  
0 0  
Z
1
0
1
0
1
0
1
0
¬Y∨Z  
X→(¬Y∨Z) CT  
1
0
1
1
1
0
1
1
1
0
1
1
1
1
1
1
0
0
0
0
1
1
1
1
@Nguyễn Thanh Sơn  
ntsơn  
Thủ tục số học  
@Nguyễn Thanh Sơn  
ntsơn  
Thực trị của một công thức  
Thí dụ : tính thực trị của công thức (X → (¬Y ∨ Z)) ∧ ¬X  
ν((X → (¬Y ∨ Z)) ∧ ¬X)  
= ν(X → (¬Y ∨ Z))ν(¬X)  
= (1 + νX + νXν(¬Y ∨ Z))ν(¬X)  
= (1 + νX + νX.(ν(¬Y) + νZ + ν(¬Y)νZ))ν(¬X)  
= (1 + νX + νXν(¬Y) + νXνZ + νXν(¬Y)νZ)ν(¬X)  
= ν(¬X) + ν(¬X)νX + ν(¬X)νXν(¬Y) + ν(¬X)νXνZ +  
ν(¬X)νXν(¬Y)νZ  
= ν(¬X) + 0 + 0.ν(¬Y) + 0.νZ + 0.ν(¬Y)νZ  
= ν(¬X) = 1 + νX.  
@Nguyễn Thanh Sơn  
ntsơn  
Thủ tục số học  
•ꢀ Một phó sản của phương pháp số học là loại bỏ  
khỏi những công thức nguyên không ảnh hưởng  
đến việc tính thực trị.  
@Nguyễn Thanh Sơn  
ntsơn  
Cây phân tích  
•ꢀ Đánh giá công thức nhờ cây phân tích.  
Thí dụ :  
Đánh giá công thức (X → (¬Y ∨ Z)) ∧ ¬X, với  
X, Y, Z lần lượt có giá trị đ, s, đ.  
s
∧
s
đ
→
¬
đ
đ
đ
X
X
∨
đ
Z
¬
đ
s
Y
@Nguyễn Thanh Sơn  
ntsơn  
Phân loại công thức  
•ꢀ I là diễn dịch của công thức X.  
X hằng đúng ↔ (∀I) νX = 1.  
X hằng sai ↔ (∀I) νX = 0.  
X khả đúng ↔ (∃I) νX = 1.  
X khả sai ↔ (∃I) νX = 0.  
@Nguyễn Thanh Sơn  
ntsơn  
Phân loại công thức  
Nhận xét :  
–ꢀPhủ định của một công thức hằng đúng là  
công thức hằng sai.  
@Nguyễn Thanh Sơn  
ntsơn  
Công thức tương đương  
•ꢀ Công thức X và Y tương đương nếu đồng bộ  
trong việc đánh giá thực trị đối với mọi diễn dịch.  
Lấy diễn dịch I của X và Y.  
Nếu X đúng trong I thì Y cũng đúng trong I và  
ngược lại.  
Nếu X sai trong I thì Y cũng sai trong I và ngược  
lại.  
Ký hiệu X = Y.  
•ꢀ Hai CT tươngđương cócùng số CTN hay không?  
@Nguyễn Thanh Sơn  
ntsơn  
Mô hình  
•ꢀ Mô hình I của công thức F là  
diễn dịch I của F và  
νF = 1 trong I.  
Chú ý :  
Diễn dịch = interpretation, valuation (tiếng Anh).  
Mô hình = model  
(tiếng Anh).  
Một số tài liệu dùng từ model cho khái niệm diễn  
dịch.  
@Nguyễn Thanh Sơn  
ntsơn  
Tải về để xem bản đầy đủ
pdf 82 trang myanh 19700 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Luận lý toán học - Chương 2: Luận lý mệnh đề (Phần 3) - Nguyễn Thanh Sơn", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfbai_giang_luan_ly_toan_hoc_chuong_2_luan_ly_menh_de_phan_3_n.pdf