›
›

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

Download
Chương 3. Luận lý vị từ  
ntsơn  
Nội dung  
I. Cấu trúc của luận lý vị từ  
II. Suy luận tự nhiên trong luận lý vị từ  
III. Ngữ nghĩa của luận lý vị từ  
IV. Phân giải  
Chương 3  
ntsơn  
I. Cấu trúc của  
luận lý vị từ  
ntsơn  
Hạn chế của LLMĐ  
•ꢀ Tam đoạn luận  
Nếu là người thì phải chết. (P)  
Socrates là người. (Q)  
Vậy Socrates phải chết. (R)  
•ꢀ Biểu diễn bằng LLMĐ không giữ được mối  
quan hệ ((P ∧ Q) → R) của 3 phát biểu trên.  
ꢀ Thêm khái niệm quan hệ để duy trì được sự  
liên kết.  
Chương 3  
ntsơn  
Biểu diễn bằng quan hệ  
•ꢀ Chọn các quan hệ từ các mệnh đề P, Q, R :  
* qhệ người(x) (ie, x là người).  
* qhệ chết(x) (ie, x chết).  
•ꢀ Khi đó các mệnh đề P, Q, R trở thành :  
P = nếu người(x) thì chết(x).  
Q = người(Socrates).  
R = chết(Socrates).  
{người(x) → chết(x), người(Socrates)}  
hệ thống kết luận được : chết(Socrates).  
Chương 3  
ntsơn  
Hạn chế của LLMĐ  
•ꢀ Một phỏng đoán của Goldbach :  
P = “ Mọi số nguyên chẵn ≥ 4 là tổng của hai  
số nguyên tố”.  
•ꢀ Đặt Pn = “n chẵn là tổng của hai số nguyên tố”.  
Mệnh đề P có thể được phân rã thành vô hạn  
các mệnh đề : P = P4 và P6 và P8 và ...  
•ꢀ Luận lý mệnh đề không chấp nhận dạng giao vô  
hạn P4 ∧ P6 ∧ P8 ∧ ... .  
ꢀ Khái niệm quan hệ biểu diễn được giao vô hạn.  
Chương 3  
ntsơn  
Lượng từ  
•ꢀ Logic “phục vụ” cho toán học.  
Thí dụ :  
(G, *) là một nhóm.  
Luật giao hoán được diễn tả bằng công thức  
x * y = y * x, với mọi phần tử x, y.  
Luật phần tử đơn vị được diễn tả  
có phần tử i, x * i = x, với mọi phần tử x.  
ꢀ Lý do xuất hiện khái niệm ∀, ∃.  
Chương 3  
ntsơn  
Lượng từ  
•ꢀ Xây dựng các quan hệ : nhân (mp), bằng (eq)  
- Luật giao hoán được diễn tả :  
∀x,∀y eq(mp(x, y), mp(y, x)).  
- Luật phần tử đơn vị  
∃i,∀x eq(mp(x, i), x).  
ꢀ Phân loại quan hệ : hàm, vị từ.  
Chương 3  
ntsơn  
Cấu trúc của luận lý vị từ  
•ꢀ Bảng ký tự : Tập hợp hữu hạn các ký tự.  
Thí dụ :  
a, b, c, d, …, z  
•ꢀ Ký hiệu : Chuỗi hữu hạn ký tự được dùng để  
đặt tên cho các khái niệm trong FOL.  
Thí dụ :  
tên biến : x, y, …  
tên hàm : cong, nhan, chia, …  
•ꢀ Miền đối tượng D : là một tập hợp “trừu tượng”.  
Chương 3  
ntsơn  
Cấu trúc của luận lý vị từ  
•ꢀ Tập hợp các ký hiệu biến.  
•ꢀ Lượng từ có 2 loại :  
Phổ dụng ∀ (universal quantifier)  
Hiện hữu ∃ (existential quantifier).  
Hình thức sử dụng :  
(∀x), (∃x) :với x là biến.  
Chương 3  
ntsơn  
Cấu trúc của luận lý vị từ  
Chương 3  
ntsơn  
Cấu trúc của luận lý vị từ  
•ꢀ Vị từ là quan hệ trên tập Dn, nghĩa là tập con  
của tập Dn.  
Thí dụ :  
D = {táo, đường, cam, bắpcải, chuối, mướp,  
ớt, tiêusọ, khổhoa, muối}  
p = {táo, cam, chuối} ⊆ D.  
p là quan hệ “trái cây tráng miệng”.  
q = {đường, ớt, tiêusọ, muối} ⊆ D.  
q là quan hệ “gia vị”.  
Chương 3  
ntsơn  
Cấu trúc của luận lý vị từ  
Thí dụ :  
D = {2, 3, 4, 5, 6, 7, 8, 9, 10}  
r = {2, 3, 5, 7} (⊆ D)  
là quan hệ “nguyên tố”  
s = {(2, 2), (2, 4), (2, 6), (2, 8), (2, 10),  
(3, 6), (3, 9), (4, 8), (5, 10)} ⊆ D×D  
là quan hệ “chia chẵn”.  
t = {4, 9} (⊆ D) là quan hệ chính phương.  
Chương 3  
ntsơn  
Cấu trúc của luận lý vị từ  
•ꢀ Một cách định nghĩa khác.  
Hàm là vị từ nếu  
- Chỉ kết hợp với nhau qua các toán tử logic :  
¬, ∧, ∨, →.  
- Khi sử dụng không được làm thông số của  
hàm khác.  
Chương 3  
ntsơn  
Cấu trúc của luận lý vị từ  
•ꢀ Vị từ được biểu diễn bằng hàm  
Dn → {1, 0}  
Thí dụ :  
p = {táo, cam, chuối} ⊆ D  
p : D → {1, 0},  
p(táo) = p(cam) = p(chuối) = 1,  
p(đường) = p(bắpcải) = p(mướp) = p(ớt) =  
p(tiêusọ) = p(khổhoa) = p(muối ) =0.  
Chương 3  
ntsơn  
Cấu trúc của luận lý vị từ  
Thí dụ :  
s = {(2, 2), (2, 4), (2, 6), (2, 8), (2, 10),  
(3, 6), (3, 9), (4, 8), (5, 10)} ⊆ D×D  
là quan hệ “chia chẵn”.  
s(2, 2) = s(2, 4) = s(2, 6) = s(2, 8) = s(2, 10) = s  
(3, 6) = s(3, 9) = s(4, 8) = s(5, 10) = 1,  
s(x, y) = 0 với (x, y) ∉ s.  
Chương 3  
ntsơn  
Cấu trúc của luận lý vị từ  
•ꢀ Ảnh của vị từ được gọi là biểu thức vị từ.  
Thí dụ :  
mẹ(x, y) là ảnh của vị từ mẹ,  
bạn(y, z) là ảnh của vị từ bạn.  
cha(Minh, Vũ) không phải là biểu thức  
vị từ vì Minh, Vũ là 2 giá trị trong thế giới thực,  
không phải là giá trị của miền D trừu tượng.  
Chương 3  
ntsơn  
Các vị từ đặc biệt  
•ꢀ Trường hợp đặc biệt :  
card(D0) = card({f | f : ∅ → D}) = 1.  
Hàm f : D0 → D được gọi là hằng.  
•
•
•
f
•
D0  
•
•
D
Có 2 vị từ từ : D0 → {1, 0} là p1 (luôn lấy giá trị  
đúng) và p0 (luôn lấy giá trị sai).  
p1  
p0  
0
0
•
D0  
•
D0  
1
1
{0, 1}  
{0, 1}  
Chương 3  
ntsơn  
Nguyên từ  
•ꢀ Nguyên từ (term) :  
(i) Ký hiệu hằng (constant) là nguyên từ.  
(ii) Ký hiệu biến (variable) là nguyên từ.  
(iii) Nếu t1, ... , tn là nguyên từ thì  
biểu thức hàm f(t1, ... , tn) là nguyên từ.  
(với hàm f không là vị từ).  
* Điều kiện (i) không cần thiết vì đã được bao hàm  
trong điều kiện (iii).  
Chương 3  
ntsơn  
Nguyên từ  
Thí dụ :  
Hằng a, b, c là nguyên từ.  
Biến x, y, z là nguyên từ.  
Biểu thức hàm f(a,x) là nguyên từ.  
Biểu thức hàm h(g(y),a,x) là nguyên từ.  
Biểu thức hàm g(f(h(x, y, z), c)) là nguyên từ.  
Bởi các hàm f(_,_), g(_), và h(_,_,_).  
Chương 3  
ntsơn  
Tải về để xem bản đầy đủ
pdf 48 trang myanh 17740 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 1) - 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_1_ngu.pdf