Bài giảng Luận lý toán học - Chương 3: Luận lý vị từ (Phần 2) - Nguyễn Thanh Sơn

ntsơn 
II. Suy luận tự nhiên trong 
 luận lý vị từ 
ntsơn 
Chương 3 
Cây phân tích[3’] 
•  Công thức ∀x ((p(x) → q(x)) ∧ r(x, y)) 
 có cây phân tích : 
∧ 
r 
y 
→ 
x x 
q x p 
∀x 
ntsơn 
Chương 3 
Hiện hữu[3’] 
•  Hiện hữu là ràng buộc nếu có một lượng từ 
cùng tên ở trên con đường từ nó hướng về gốc. 
Ngược lại là tự do. 
 Thí dụ : (∀x (p(x) ∧ q(x))) → (¬p(x) ∨ q(y)) 
tự do ràng buộc ràng buộc 
∧ 
∨ 
q 
→ 
x x 
q 
¬ 
p 
∀x 
x 
p y 
tự do 
ntsơn 
Chương 3 
Thay thế 
•  Chỉ những hiện hữu tự do mới được thay thế 
•  Biến là nguyên từ phải được thay bởi một 
nguyên từ. 
2 hiện hữu này có thể được thay thế 
∧ 
∨ 
q 
→ 
x x 
q 
¬ 
p 
∀x 
p y 
x 
ràng buộc ràng buộc 
tự do 
tự do 
ntsơn 
Chương 3 
Thay thế 
•  Ký hiệu F[t/x] nghĩa là tất cả hiện hữu tự do của 
x trong F được thay bởi t. 
2 hiện hữu của x thay bởi t với F[t/x] 
∧ 
∨ 
q 
→ 
y x 
q 
¬ 
p 
∀y 
p y 
x 
ràng buộc 
tự do 
tự do 
tự do 
ntsơn 
Chương 3 
Thay thế 
Thí dụ : 
∧ 
∨ 
q 
→ 
z x 
q 
¬ 
p 
∀x 
p y 
x 
ràng buộc 
 thay z bằng t ?  
 thay z bằng x ?  
 thay z bằng f(t, y) ?  
 thay z bằng g(x, t) ?  
ntsơn 
Chương 3 
Điều kiện thay thế[3’] 
•  Nguyên từ t tự do đối với biến x trong công thức 
F nếu không có hiện hữu tự do của x xuất hiện 
trong phạm vi của ∀y hoặc ∃y với mọi biến y có 
trong t. 
 Nói các khác, hiện hữu của các biến trong t 
không trở thành ràng buộc khi thế t vào tất cả 
những hiện hữu tự do của x. 
ntsơn 
Chương 3 
Điều kiện thay thế 
•  Thí dụ : 
t1 = f(y, z) không tự do đối với x vì y trở thành ràng buộc. 
t2 = g(x, x) tự do đối với x. 
t3 = h(x, z) tự do đối với x. 
∧ 
→ x 
r ∀y 
y x 
q p 
tự do 
tự do 
ràng buộc 
t1 = f(y, z) 
t2 = g(x, x) 
t3 = h(x, z) 
ntsơn 
Chương 3 
Thay thế 
Nhận xét : 
–  Một số biến cần được đổi tên để thoả mãn 
điều kiện thay thế. 
– Để F[t/x] luôn luôn được thực hiện, trước 
tiên đổi tên tất cả các biến có hiện hữu ràng 
buộc trong F xuất hiện trong t. Lúc này t tự 
do đối với x. 
ntsơn 
Chương 3 
Thay thế 
Thí dụ : 
∧ 
→ x 
r ∀y 
y x 
q p 
tự do 
tự do 
f(y, z) không tự do đối với x. 
∀t 
t 
Nếu thay biến y bằng t thì 
 f(y, z) tự do đối với x. 
ntsơn 
Chương 3 
Suy luận tự nhiên 
•  Suy luận tự nhiên trong LLVT cũng tương tự 
như trong LLMĐ, ngoại trừ các qui tắc liên quan 
đến lượng từ. 
•  Ký hiệu bằng nhau t = s với t và s là nguyên từ 
là vị từ eq(t, s). 
•  eq(t, s) có giá trị đúng khi t và s : 
 - cùng là một ký hiệu hằng 
 - là biểu thức hàm cùng giá trị trên miền đối 
tượng. 
ntsơn 
Chương 3 
Suy luận tự nhiên[3’] 
•  Qui tắc bằng nhau i (=i) 
 dòng m : eq(t, t), với t là nguyên từ. 
 Đương nhiên viết được dòng m. 
Chú thích : 
 qui tắc (=i) còn được viết là t = t. 
ntsơn 
Chương 3 
Suy luận tự nhiên[3’] 
•  Qui tắc bằng nhau e (=e) 
 dòng m : eq(t1, t2) với t1,t2 là nguyên từ 
 dòng k : F[t1/x] 
 dòng k+1 : F[t2/x] 
 với t1, t2 tự do đối với x trong F. 
 Nếu có dòng m và k thì viết được dòng k+1. 
Chú thích : 
 qui tắc (=e) còn được viết là t1 = t2. 
ntsơn 
Chương 3 
Suy luận tự nhiên[3’] 
•  Chứng minh : t1 = t2 ├─ t2 = t1. 
 Viết lại : 
 eq(t1, t2)├─ eq(t2, t1). 
 Đặt F = eq(x, t1). 
 1 eq(t1, t2) tiền đề 
 2 eq(t1, t1) (=i) (= F[t1/x]) 
 3 eq(t2, t1) (=e) 1, 2 (= F[t2/x]) 
ntsơn 
Chương 3 
Suy luận tự nhiên[3’] 
•  Chứng minh : t1 = t2 , t2 = t3 ├─ t1 = t3 
 F = eq(x, t3). 
 1 t2 = t3 tiền đề (F[t2/x]) 
 2 t1 = t2 tiền đề 
 3 t1 = t3 =e 1, 2 (F[t1/x]) 
ntsơn 
Chương 3 
Suy luận tự nhiên[3’] 
•  Qui tắc lượng từ phổ dụng e (∀e) 
 dòng m : ∀x F 
 dòng k : F[t/x] 
 với nguyên từ t tự do đối với x trong F(*). 
 Nếu có dòng m thì viết được dòng k. 
(*)Nhận xét : 
 t tự do đối với x trong F, không phải trong (∀xF), 
nghĩa là công thức đã được “gỡ bỏ” lượng từ. 
ntsơn 
Chương 3 
Suy luận tự nhiên[3’] 
•  Thí dụ : 
 p(t), ∀x (p(x)→¬q(x)) ├─ ¬q(t) 
 với mọi t (tự do đối với x) 
 1 ∀x (p(x)→¬q(x)) tiền đề 
 2 p(t)→¬q(t) ∀e 1 
 3 p(t) tiền đề 
 4 ¬q(t) →e 2, 3 
ntsơn 
Chương 3 
Suy luận tự nhiên[3’] 
•  Từ ∀x F tới F[y/x] không thể thiếu điều kiện “tự 
do đối với biến“. 
Thí dụ : 
 F = (∃y (x < y)) với x, y là số nguyên và quan hệ 
nhỏ hơn (<) thông thường. 
 ∀x F có nghĩa là mọi số nguyên x có số nguyên 
y lớn hơn. 
 Nhưng, F[y/x] là (∃y (y <y)), nghĩa là có số y lớn 
hơn chính nó. 
 Kết quả sai này là do điều kiện “tự do đối với 
biến” bị vi phạm. 
ntsơn 
Chương 3 
Suy luận tự nhiên[3’] 
•  Qui tắc lượng từ phổ dụng i (∀i) 
 dòng m : if x0  
 dòng  :  
 dòng k : nif F[x0/x] 
 dòng k+1 : ∀x F 
 với biến x0 là bất kỳ và không xuất hiện ở ngoài 
cấu trúc ifnif. 
 khi đó viết được dòng k+1. 
 Cấu trúc ifnif chỉ là qui định phạm vi của x0. 
ntsơn 
Chương 3 
Suy luận tự nhiên[3’] 
•  Thí dụ : ∀x (p(x)→q(x)), ∀x p(x)├─ ∀x q(x) 
 1 ∀x (p(x)→q(x)) tiền đề 
 2 ∀x p(x) tiền đề 
 3 if x0 (x0 không xuất hiện ở 1,2,6) 
 p(x0)→q(x0) ∀e 1 
 4 p(x0) ∀e 2 
 5 nif q(x0) →e 3, 4 
 6 ∀x q(x) ∀i 3-5 
ntsơn 
Chương 3 
Suy luận tự nhiên[3’] 
•  Qui tắc ∀i dẫn từ F[x0/x] đến ∀x F “có vẻ” như 
từ một trường hợp đặc biệt tổng quát hóa lên. 
 Điều kiện biến x0 chưa xuất hiện ở ngoài cấu 
trúc ifnif cho phép khái quát được trường hợp 
tổng quát. 
 Vì x0 là “bất kỳ”, không phải là phần tử đã được 
“chuẩn bi sẵn”. 
Nhắc lại : 
Tất cả các dòng - từ dòng có từ khóa if đến 
dòng có từ khóa nif - đều thuộc cấu trúc ifnif 
ntsơn 
Chương 3 
Suy luận tự nhiên[3’] 
•  Qui tắc lượng từ hiện hữu i (∃i) 
 dòng m : F[t/x] 
 dòng k : ∃x F 
 Nếu có dòng m thì viết được dòng k. 
Nhận xét : 
qui tắc này là đối ngẫu của ∀e. 
ntsơn 
Chương 3 
Suy luận tự nhiên[3’] 
•  Thí dụ : ∀x F ├─ ∃x F 
 1 ∀x F tiền đề 
 2 F[x/x] ∀e 1 
 3 ∃x F ∃i 2 
ntsơn 
Chương 3 
Suy luận tự nhiên[3’] 
•  Qui tắc lượng từ hiện hữu e (∃e) 
 dòng m : ∃x F 
 dòng m+1 : if x0 F[x0/x] (thế x0 vào dòng m) 
 dòng k : nif G 
 dòng k+1 : G 
 với x0 là bất kỳ và không xuất hiện ở ngoài cấu 
trúc ifnif. 
 Nếu có dòng m và cấu trúc ifnif thì viết được 
dòng k+1. 
ntsơn 
Chương 3 
Suy luận tự nhiên[3’] 
•  Qui tắc lượng từ hiện hữu e (∃e) (tt) 
 Khi có ∃x F thì “có ít nhất một” giá trị của x để 
bảo đảm sự hiện hữu của ∃x F, x0 là đại diện 
cho tất cả các giá trị này của x. 
ntsơn 
Chương 3 
Suy luận tự nhiên[3’] 
•  Thí dụ : ∀x (p(x)→q(x)), ∃x p(x)├─ ∃x q(x) 
 1 ∀x (p(x)→q(x)) tiền đề 
 2 ∃x p(x) tiền đề 
 3 if x0 p(x0)(*) 2 [x0/x] 
 4 p(x0)→ q(x0) ∀e 1 
 5 q(x0) →e 3,4 
 6 nif ∃x q(x) ∃i 5 
 7 ∃x q(x) ∃e 2, 3-6 
((*) Lý do để có dòng 3 là do qui định của qui tắc 
lượng từ hiện hữu ∃e) 
ntsơn 
Chương 3 
Suy luận tự nhiên[3’] 
•  Thí dụ : ∀x (p(x)→q(x)), ∃x p(x)├─ ∃x q(x) 
 1 ∀x (p(x)→q(x)) tiền đề 
 2 ∃x p(x) tiền đề 
 3 if x0 p(x0) 2 [x0/x] 
 4 p(x0)→ q(x0) ∀e 1 
 5 nif q(x0) →e 3,4 
 6 q(x0) ∃e 2, 3-5 
 7 ∃x q(x) ∃i 6 
* Dòng 6 không hợp lệ vì x0 thoát ra ngoài cấu trúc 
ifnif. 
ntsơn 
Chương 3 
Suy luận tự nhiên[3’] 
•  Thí dụ : ∀x (q(x)→r(x)), ∃x (p(x) ∧ q(x))├─ 
 ∃x (p(x) ∧ r(x)) 
 1 ∀x (q(x)→r(x)) tiền đề 
 2 ∃x (p(x) ∧ q(x)) tiền đề 
 3 if x0 p(x0) ∧ q(x0) 2[x0/x] 
 4 p(x0) ∧e 3 
 5 q(x0) ∧e 3 
 6 q(x0) → r(x0) ∀e 1 
 7 r(x0) →e 5,6 
 8 p(x0) ∧ r(x0) ∧i 4,7 
 9 nif ∃x (p(x) ∧ r(x)) ∃i 8 
 10 ∃x (p(x) ∧ r(x)) ∃e 2, 3-9 
ntsơn 
Chương 3 
Suy luận tự nhiên[3’] 
•  Thí dụ : ∃x p(x), ∀x∀y (p(x)→q(y))├─ ∀y q(y) 
 1 ∀x∀y (p(x)→q(y)) tiền đề 
 2 ∃x p(x) tiền đề 
 3 if y0 
 4 if x0 p(x0) 2 [x0/x] 
 5 p(x0)→ q(y0) ∀x ∀y e 1 
 6 nif q(y0) →e 4,5 
 7 nif q(y0) ∃x e 2,4-6 
 8 ∀y q(y) ∀y i 3-7 
ntsơn 
Chương 3 
Suy luận tự nhiên[3’] 
•  Định lý : 
 (a) ¬∀x F ≡ ∃x ¬F 
 (b) ¬∃x F ≡ ∀x ¬F 
ntsơn 
Chương 3 
Suy luận tự nhiên 
•  Hiện hữu tự do (của 1 biến) đối với 1 công 
thức. 
 Thí dụ : 
 G = p(x) ∧ (∃x)q(x)), x (trong p(x)) là hiện 
hữu tự do (đối với G) của biến x. 
 F = (∀x)(r(x) ∨ G), không có hiện hữu tự 
do (đối với F) của biến x. 
ntsơn 
Chương 3 
Suy luận tự nhiên[3’] 
•  Định lý : 
G không chứa hiện hữu tự do của x (trong G). 
 (a) ∀x F ∧ G ≡ ∀x (F ∧ G) 
 (b) ∀x F ∨ G ≡ ∀x (F ∨ G) 
 (c) ∃x F ∧ G ≡ ∃x (F ∧ G) 
 (d) ∃x F ∨ G ≡ ∃x (F ∨ G) 
ntsơn 
Chương 3 
Suy luận tự nhiên[3’] 
•  Định lý : 
G không chứa hiện hữu tự do của x (trong G). 
 (e) ∀x (G → F) ≡ G →∀x F 
 (f) ∃x (F → G) ≡ ∀x F → G 
 (g) ∀x (F → G) ≡ ∃x F → G 
 (h) ∃x (G → F) ≡ G → ∃x F 
ntsơn 
Chương 3 
Suy luận tự nhiên[3’] 
•  Định lý : 
(a) ∀x F ∧ ∀x G ≡ ∀x (F ∧ G) 
 (b) ∃x F ∨ ∃x G ≡ ∃x (F ∨ G) 
 (c) ∀x∀y F ≡ ∀y∀x F 
 (d) ∃x∃y F ≡ ∃y∃x F 
ntsơn 
Bài tập 
Chương 3 : Luận lý vị từ 
ntsơn 
Chương 3 
Suy luận tự nhiên[3’] 
0. Chứng minh các định lý trong phần giáo khoa. 
1. Chứng minh : 
 a. (y = 0) ∧ (y = x) ├─ 0 = x 
 b. t1 = t2 ├─ (t + t2) = (t + t1) 
 c. (x = 0) ∨ ((x + x) > 0) ├─ 
 (y = (x + x)) → ((y > 0) ∨ (y = (0 +x))) 
2. Dịch ∃x ∃y (¬(x = y) ∧ ∀z ((z = x) ∨ (z = y)))) ra 
ngôn ngữ tự nhiên. 
ntsơn 
Chương 3 
Suy luận tự nhiên[3’] 
3. Dịch ra LLVT : 
 a. Có đúng 3 phần tử phân biệt. 
 b. Có nhiều nhất 3 phần tử phân biệt. 
 c. Chỉ một số hữu hạn các phần tử phân biệt. 
4. Chứng minh : 
 F → (q1∧q2) ├─ (F→q1) ∧ (F→q2) (trong LLMĐ) 
 F → ∀x q(x) ├─ ∀x (F → q(x)) (trong LLVT) với 
x không tự do trong F. 
 ∀x (p(x) → q(x)) ├─ ∀x p(x) → ∀x q(x). 
ntsơn 
Chương 3 
Suy luận tự nhiên[3’] 
5. Chứng minh : 
 a. ∀x p(x)├─ ∀y p(y) 
 b. ∀x (p(x) → q(x)) ├─ (∀x ¬q(x)) → (∀x ¬p(x)) 
 c. ∀x (p(x) → ¬q(x)) ├─ ¬(∃x (p(x) ∧ q(x)) 
ntsơn 
Chương 3 
Hết slide