Bài giảng Luận lý toán học - Chương 3: Luận lý vị từ (Phần 3) - Nguyễn Thanh Sơn
Diễn dịch của 1 công thức
Xác định một diễn dịch I cho công thức F là xác định các yếu tố sau :
1. Chọn miền đối tượng D.
2. Định nghĩa các hàm (gán giá trị cho hằng).
3. Định nghĩa các vị từ của F.
Tóm tắt nội dung Bài giảng Luận lý toán học - Chương 3: Luận lý vị từ (Phần 3) - Nguyễn Thanh Sơn, để xem tài liệu hoàn chỉnh bạn click vào nút "TẢI VỀ" ở trên
y = : (p( ) q( )) ( t q(t) z q(z)).
(0 1) (1 1) = 1.
Vậy công thức F đúng trong diễn dịch trên.
Đánh giá CT đóng trong 1 dd
Thí dụ :
F = x y ( (p(x) q(y)) ( t q(t) z q(z)) )
Diễn dịch I :
D = { , , },
{p( ), p( ), p( ), q( ), q( ), q( )}.
Lấy x = ,
lấy y = : (p( ) q( )) ( t q(t) z q(z)).
(1 1) ( 1 0).
Vậy công thức F sai trong diễn dịch I.
Ngữ nghĩa
Các khái niệm :
Hằng đúng
Hằng sai
Khả đúng-Khả sai
Mô hình
Tương đương (=)
Hệ quả luận lý ( ╞═ )
được định nghĩa tương tự như trong LLMĐ.
Ngữ nghĩa
Nhận xét :
Các định nghĩa hằng sai, hằng đúng, khả đúng, khả sai, mô hình, tương đương, hệ quả luận lý là working trong LLMĐ nhưng non-working trong LLVT.
Công thức tương đương
F, P là công thức và P không chứa hiện hữu tự do của x (đối với P).
1. ( x F) P = x (F P)
1'. ( x F) P = x (F P)
2. ( x F) P = x (F P)
2'. ( x F) P = x (F P)
Công thức tương đương
Chứng minh : ( x F) P = x (F P)
Tương đương với việc chứng minh 2 bài toán :
1. ( x F) P ╞═ x (F P)
2. x (F P) ╞═ ( x F) P
Các công thức tương đương khác được chứng minh tương tự.
Công thức tương đương
Chứng minh : ( x F) P ╞═ x (F P)
Lấy 1 mô hình I của ( x F) P.
Nếu ( x F) đúng thì F[ /x] P đúng D I (D I là miền đối tượng của I) .
Do đó x (F P) đúng.
Nếu ( x F) sai thì P phải đúng.
Do đó F[ /x] P đúng D I ,
hay x (F P) đúng.
Vậy ( x F) P ╞═ x (F P)
Công thức tương đương
Thí dụ :
( x p(x)) q(y) = x (p(x) q(y))
( x p(x) q(x)) r(y) = x ((p(x) q(x)) r(y) )
( x p(x)) q( x , y) x (p(x) q(x, y))
vì q chứa hiện hữu tự do của x.
q(y, z) x p(x, y) = x (q(y, z) p(x, y))
Hội giao mở rộng
Hôi, giao mở rộng.
Ký hiệu A i I = A 1 A 2 A 3 ,
A i I = A 1 A 2 A 3 , với I = {1, 2, 3}
Định nghĩa giao mở rộng :
x A i I i (x A i )
Định nghĩa hội mở rộng :
x A i I i (x A i )
Công thức tương đương
Thí dụ minh họa ứng dụng công thức
( xF) P = x (F P)
A 1 , A 2 , A 3 , B là các tập hợp.
Đặt I = {1, 2, 3} và B i = (A i B)
(A 1 A 2 A 3 ) B = (A 1 B) ( A 2 B) ( A 3 B )
viết lại A i B = B i .
Công thức tương đương
Thí dụ :
Chứng minh A i B B i .
Lấy x A i I B,
(x A i I ) (x B)
i (x A i ) (x B)
Đặt p(i) = “ x A i ”, q = “x B”
i p(i) q
i ( p(i) q) vì ( ( x F) Q = x (F Q))
x B i .
Công thức tương đương
Nhận xét :
i (x A i ) (x B) = i ((x A i ) (x B)).
Câu hỏi :
i và x có phải là biến hay không ?.
Công thức tương đương
3. ( x F) = x F
3’. ( x F) = x F
Thí dụ :
( x p(x, y)) = x p (x, y)
( x p (x)) = x p(x)
Công thức tương đương
Nhận xét :
Luật Morgan trong LLVT giống như trong LLMĐ
(F G) = F G
(F G) = F G
Thí dụ :
( x p(x) y q(y )) = ( x p(x) y q(y ))
( x p(x) y q(y )) = ( x p(x) y q(y ))
Công thức tương đương
Chú ý :
Trong thực tế khi sử dụng các lượng từ thường được viết kèm theo miền xác định của biến .
Thí dụ :
Định nghĩa giao mở rộng :
A i I = { x | ( i I ) (x A i )}
Do đó khi lấy phủ định sẽ là
( ( x I) (x A i ) ) = ( x I) (x A i )
Công thức tương đương
4. x (F H) = ( x F) ( x H)
4’. x (F H) = ( x F) ( x H)
Thí dụ :
x (x * A x * B) = x (x ** A) x (x ** B)
x (x A x B) = x (x A) x (x B)
Các hiện hữu của x tại các vị trí ( * ) phải lấy cùng 1 giá trị trong mọi lúc, nhưng các hiện hữu tại ( ** ) không cần phải lấy cùng 1 giá trị tại cùng một thời điểm.
Công thức tương đương
5. ╞═ ( x F x H) x (F H)
5’. ╞═ x (F H) ( x F x H)
Thí dụ :
A i , B i là các tập hợp lấy chỉ số trên I.
i (x A i ) i (x B i ) ╞═ i (x A i x B i ).
i (x A i x B i ) ╞/═ i (x A i ) i (x B i ).
i (x A i x B i ) ╞═ ( i, x A i ) ( i, x B i ).
i (x A i ) i (x B i ) ╞/═ ( i, x A i x B i ).
Công thức tương đương
Chứng minh (A i B i ) = ( A i ) ( B i ),
với A i , B i, là các tập hợp.
Lấy x (A i B i ) (1)
( i) (x A i B i ) (2)
( i) ( x A i x B i ) (3)
( i) (x A i ) ( i)(x B i ) (4)
x ( A i ) x ( B i ) (5)
x ( A i ) ( B i) (6)
Chứng minh có lỗi ?.
Công thức tương đương
Chứng minh (A i B i ) = ( A i ) ( B i ).
Lấy x (A i B i ) (1)
( i) (x A i B i ) (2)
( i) ( x A i x B i ) (3)
( i) (x A i ) ( i)(x B i ) (4)
x ( A i ) x ( B i ) (5)
x ( A i ) ( B i) (6)
Dòng (3) chuyển xuống (4) sai.
Vậy chỉ có : (A i B i ) ( A i ) ( B i ).
Công thức tương đương
Thí dụ minh họa :
Lấy tập chỉ số I = {1, 2}.
(A 1 B 1 ) (A 2 B 2 ) (A 1 A 2 ) (B 1 B 2 ).
Công thức tương đương
6. x ( y H) = y ( x H)
6’. x ( y H) = y ( x H)
7. ╞═ x H x H
Thí dụ :
x y p(x, y)) = y x p (x, y)
x y ( p (x) q(y) ) = y x ( p (x) q(y) )
Chú thích :
Người ta thích viết x y H thay vì x ( y H ) .
Đọc thêm [4]
Công thức tương đương
Nhận xét :
Không thể hoán vị các lượng từ và .
Thí dụ :
p(x,y) là “số nguyên x bằng số nguyên y”.
y x p(x, y) đúng, nhưng
x y p(x, y) sai.
Câu hỏi :
2 công thức trên đúng và sai trong diễn dịch nào ?.
Công thức tương đương
Nhận xét :
Có trường hợp hoán vị được lượng từ và .
Thí dụ :
F = x p(x) y q(y)
Cách 1 . Cách 2 .
F = x (p(x) y q(y)) F = y ( x p(x) q(y))
F = x y (p(x) q(y)) F = y x (p(x) q(y)).
Công thức tương đương
Nhận xét :
╞═ x y K y x K (*)
╞/═ y x K x y K (**)
Chứng minh (*) ?
(*) tương đương với x y K ╞═ y x K.
(**) tương đương với y x K ╞/═ x y K.
Công thức tương đương
╞═ x y K y x K
Chứng minh
Lấy 1 diễn dịch I.
Nếu x y K đúng.
Giả sử y x K sai, nghĩa là y 0 x K sai, hay x y 0 K sai.
Mâu thuẫn với x y K đúng.
Vậy y x K đúng.
Cục bộ > To àn bộ
Lượng từ toàn bộ không ảnh hưởng đến phạm vi của lượng từ cục bộ.
Có thể đổi tên biến của lượng từ cục bộ và các hiện hữu nằm trong phạm vi ảnh hưởng của nó.
Thí dụ :
F = x (p(x) x q(x))
= x (p(x) y q( y )).
Dạng chuẩn Prenex
Dạng chuẩn Prenex có dạng :
F = (Q 1 x 1 ) ... (Q n x n ) M
M là CT không chứa lượng từ (quantifier-free).
Q i là hoặc .
Thí dụ :
F = x y ( p(x) q(y))
G = x y (p(x) q(y))
H = x y ( p(x) q(y))
F, G, H đang ở dạng chuẩn Prenex.
Dạng chuẩn Prenex
Qui trình chuyển về dạng chuẩn Prenex :
1. Thay thế toán tử bằng , sử dụng công thức tương đương X Y = X Y.
2. Đẩy tất cả lượng từ ra phía trái (nếu cần thì đổi tên biến cục bộ).
Dạng chuẩn Prenex
Thí dụ :
Chuyển về dạng chuẩn Prenex :
F = x (p(x) x y (q(y) r(x)))
F = x ( p(x) x y (q(y) r(x)))
Đổi tên biến cục bộ.
F = x ( p(x) z y (q(y) r(z)))
F = x z y ( p(x) (q(y) r(z))).
Soundness & Completeness
Tương quan giữa 2 khái niệm ├─ và╞═ H .
Định lý (soundness).
Nếu F ├─ H thì F ╞═ H .
Định lý (completeness).
Nếu F ╞═ H thì F ├─ H .
├─
F
H
╞═
Soundness
Thủ tục để có F ├─ H được gọi là sound nếu có F ├─ H thì F ╞═ H .
Một số trường hợp, thủ tục có tính sound không tìm thấy lời giải, mặc dù lời giải tồn tại (*).
(*) Description Logics Deduction in Propositional Logic
Enrico Franconi, franconi@cs.man.ac.uk
Completeness
Thủ tục để có F ├─ H được gọi là complete nếu F ╞═ H thì có F ├─ H .
Một số trường hợp, thủ tục có tính complete nói có thể tìm thấy lời giải, mặc dù lời giải không tồn tại (*).
(*) Description Logics Deduction in Propositional Logic
Enrico Franconi, franconi@cs.man.ac.uk
Bài tập Chương 3 : Luận lý vị từ
Miền đối tượng
1. Thế giới thật có các đối tương sau :
D = { ▲ , , , }, hằng : cMinh, hàm : fnón(_).
Vị từ : ptrên(_,_), ptròn(_), pvuông(_), pthoi(_).
Cho 1 diễn dịch I :
D = { ▲ , , , }, cMinh = ▲ .
ptrên = {( , ▲ ), ( , )}. ptròn = { }.
pthoi = { , }. pvuông = { }.
fnón = {( ▲ , ), ( , ), ( , ), ( , )}
Miền đối tượng
a. Hãy đánh giá các CT sau trong diễn dịch I :
pvuông(cMinh),
ptrên(cMinh, fnón(cMinh)),
x pvu ông(x),
x y (ptrên(x, y ) ptrên(y, x)) trong dd I.
b. Chứng minh KB dẫn xuất H :
KB : x ( pvuông(x) pthoi(x)) ( x)( ptròn(x) pthoi(x)).
H = x ( ptròn(x) pthoi(x)).
Diễn dịch
2. Cho diễn dịch I có :
D = {a,b},
{p(a, a), p (a, b), p (b, a), p(b, b)}.
Đánh giá các công thức sau : a. x y p(x, y) b. x y p(x, y)
c. x y p(x, y) d. y p (a, y)
e. x y (p(x, y) p(y, x)) f. x p(x, x)
Diễn dịch
3. Tìm một diễn dịch trên D = a,b để công thức
F = x y (p(x,y) p(y,x)) có giá trị sai.
4. Cho diễn dịch I : D = {1, 2}, a = 1, b = 2, f(1) = 2, f(2) = 1,
{p(1,1), p(1,2), p (2,1), p (2,2)}.
Đánh giá công thức sau trong diễn dịch I : a. p(a, f(a)) p(b, f(b))
b. x y p(y,x)
c. x y (p(x, y) p(f(x), f(y))).
Dạng chuẩn Prenex
5. Tìm dạng chuẩn Prenex của các công thức : a. ( x p(x)) y z q(y, z) b. ( x p(x) y p(y)).
c. x y ( z p(x,y,z) ( u q(x,u) v q(y,v))).
6. Cho biết ╞═ x H H[a/x] có hằng đúng hay không với a là một hằng.
Hết slide
File đính kèm:
bai_giang_luan_ly_toan_hoc_chuong_3_luan_ly_vi_tu_phan_3_ngu.ppt
