›
›

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

Download
II. Suy luận tự nhiên trong  
luận lý vị từ  
ntsơn  
[3’]  
Cây phân tích  
•ꢀ Công thức ∀x ((p(x) → q(x)) ∧ r(x, y))  
có cây phân tích :  
∀x  
∧
r
→
x
y
q
x
p
x
Chương 3  
ntsơn  
[3’]  
Hiện hữu  
•ꢀ 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))  
→
∨
∀x  
∧
¬
q
p
y
q
x
p
x
tự do  
x
tự do  
ràng buộc ràng buộc  
Chương 3  
ntsơn  
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ừ.  
→
∨
∀x  
∧
¬
q
p
y
q
x
p
tự do  
x
x
tự do  
ràng buộc  
ràng buộc  
2 hiện hữu này có thể được thay thế  
Chương 3  
ntsơn  
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.  
→
∨
∀y  
∧
¬
q
p
y
q
y
p
x
tự do  
x
tự do  
tự do ràng buộc  
2 hiện hữu của x thay bởi t với F[t/x]  
Chương 3  
ntsơn  
Thay thế  
Thí dụ :  
→
∨
∀x  
∧
¬
p
x
q
y
q
z
p
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) ?  
Chương 3  
ntsơn  
[3’]  
Điều kiện thay thế  
•ꢀ 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.  
Chương 3  
ntsơn  
Điều kiện thay thế  
•ꢀ Thí dụ :  
∧
t2 = g(x, x)  
t3 = h(x, z)  
∀y  
ràng buộc  
t1 = f(y, z)  
r
→
x
tự do  
q
y
p
x
tự do  
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.  
Chương 3  
ntsơn  
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.  
Chương 3  
ntsơn  
Thay thế  
Thí dụ :  
∧
∀t  
∀y  
r
Nếu thay biến y bằng t thì  
f(y, z) tự do đối với x.  
f(y, z) không tự do đối với x.  
→
x
tự do  
q
y
p
t
x
tự do  
Chương 3  
ntsơn  
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.  
Chương 3  
ntsơn  
[3’]  
Suy luận tự nhiên  
•ꢀ 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.  
Chương 3  
ntsơn  
[3’]  
Suy luận tự nhiên  
•ꢀ Qui tắc bằng nhau e (=e)  
dòng m :  
dòng k :  
eq(t1, t2) với t1,t2 là nguyên từ  
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.  
Chương 3  
ntsơn  
[3’]  
Suy luận tự nhiên  
•ꢀ 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)  
2 eq(t1, t1)  
3 eq(t2, t1)  
tiền đề  
(=i)  
(= F[t1/x])  
(=e) 1, 2 (= F[t2/x])  
Chương 3  
ntsơn  
[3’]  
Suy luận tự nhiên  
•ꢀ Chứng minh : t1 = t2 , t2 = t3 ├─ t1 = t3  
F = eq(x, t3).  
1 t2 = t3  
2 t1 = t2  
3 t1 = t3  
tiền đề (F[t2/x])  
tiền đề  
=e 1, 2 (F[t1/x])  
Chương 3  
ntsơn  
[3’]  
Suy luận tự nhiên  
•ꢀ Qui tắc lượng từ phổ dụng e (∀e)  
dòng m :  
dòng k :  
∀x F  
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ừ.  
Chương 3  
ntsơn  
[3’]  
Suy luận tự nhiên  
•ꢀ 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))  
2 p(t)→¬q(t)  
3 p(t)  
tiền đề  
∀e 1  
tiền đề  
→e 2, 3  
4 ¬q(t)  
Chương 3  
ntsơn  
[3’]  
Suy luận tự nhiên  
•ꢀ 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.  
Chương 3  
ntsơn  
[3’]  
Suy luận tự nhiên  
•ꢀ Qui tắc lượng từ phổ dụng i (∀i)  
dòng m :  
dòng … :  
dòng k :  
if x0 …  
…
nif F[x0/x]  
∀x F  
dòng k+1 :  
với biến x0 là bất kỳ và không xuất hiện ở ngoài  
cấu trúc if…nif.  
khi đó viết được dòng k+1.  
Cấu trúc if…nif chỉ là qui định phạm vi của x0.  
Chương 3  
ntsơn  
[3’]  
Suy luận tự nhiên  
•ꢀ Thí dụ : ∀x (p(x)→q(x)), ∀x p(x)├─ ∀x q(x)  
1
2
∀x (p(x)→q(x))  
∀x p(x)  
tiền đề  
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)  
∀x q(x)  
→e 3, 4  
∀i 3-5  
6
Chương 3  
ntsơn  
Tải về để xem bản đầy đủ
pdf 39 trang myanh 15120 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 3: Luận lý vị từ (Phần 2) - 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_3_luan_ly_vi_tu_phan_2_ngu.pdf