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

) =0. 
ntsơn 
Chương 3 
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. 
ntsơn 
Chương 3 
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. 
ntsơn 
Chương 3 
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. 
 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). 
• 
D0 
• 
D 
• • 
• • 
f 
• 
D0 
1 
{0, 1} 
0 p1 • 
D0 
1 
{0, 1} 
0 p0 
ntsơn 
Chương 3 
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). 
ntsơn 
Chương 3 
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(_,_,_). 
ntsơn 
Chương 3 
Công thức nguyên 
•  Nếu p là vị từ và t1, ... , tn là nguyên từ 
 thì p(t1, ... , tn) là công thức nguyên. 
•  Biểu thức vị từ là công thức nguyên. 
Thí dụ : 
 Vị từ : mẹcủa(_, _), nhỏhơn(_, _), cònsống(_). 
 mẹ_của(x, f(y)), 
 nhỏhơn(cộng(x, a), y), 
 còn_sống(z) 
 là các công thức nguyên. 
ntsơn 
Chương 3 
Công thức nguyên 
Thí dụ : 
 Các nhà thơ : Văn Cao, Xuân Diệu, Hoàng 
Cầm, Phạm Thiên Thư. 
 Sử gia : Lê Văn Hưu. Vua : QuangTrung. 
 Đặt D = {xDiệu, hCầm, vCao, pTThư, lVHưu, 
 qTrung}. 
 Đặt vị từ nt(x) = x là nhà thơ, với x ∈ D. 
  nt(x) là công thức nguyên 
  nt(xDiệu), nt(pTThư) không là CT nguyên. 
ntsơn 
Chương 3 
Công thức nguyên 
Công thức nguyên nt(x) với x ∈ D tương đương 
với 6 câu khai báo : 
 nt(xDiệu) : Xuân Diệu là nhà thơ. 
 nt(hCầm) : Hoàng Cầm là nhà thơ. 
 nt(vCao) : Văn Cao là nhà thơ. 
 nt(pTThư) : Phạm Thiên Thư là nhà thơ. 
 nt(lVHưu) : Lê Văn Hưu là nhà thơ. 
 nt(qTrung) : QuangTrung là nhà thơ. 
ntsơn 
Chương 3 
Công thức nguyên 
Nhận xét : 
•  Một công thức nguyên của LLVT tương ứng 
với một tập công thức nguyên của LLMĐ. 
•  LLMĐ là một trường hợp đặt biệt của LLVT. 
ntsơn 
Chương 3 
Công thức hoàn hảo 
•  Công thức hoàn hảo được gọi tắt là công thức. 
•  Công thức : 
 (i) Công thức nguyên là CT. 
 (ii) ⊥, Ť là CT. 
 (iii) CT kết hợp với ¬, ∧, ∨, → cũng là CT. 
 (vi) CT kết hợp với (∀x), (∃x) cũng là CT. 
 Sự kết hợp các yếu tố trên chỉ gồm hữu hạn 
phần tử. 
ntsơn 
Chương 3 
Một định nghĩa khác[15] 
•  V là tập vô hạn đếm được các biến. 
•  R tập đếm được các ký hiệu quan hệ (vị từ). 
Mỗi vị từ có arity là số nguyên không âm (non-
negative). 
•  F tập đếm được các ký hiệu hàm. Mỗi vị từ có 
arity là số nguyên không âm (non-negative). 
•  C tập đếm được các ký hiệu hằng. 
•  Σ = được gọi là first-order signature. 
ntsơn 
Chương 3 
Một định nghĩa khác[15] 
•  Σ = là first-order signature, 
tập hợp Σ-term là tập nhỏ nhất thỏa : 
–  Biến trong V là một term. 
–  Hằng trong C là một term. 
–  Nếu f là hàm n thông số và t1, ..., tn là term 
thì f(t1, ..., tn) cũng là term. 
ntsơn 
Chương 3 
Một định nghĩa khác[15] 
Thí dụ : 
“All men are mortal”. 
Định nghĩa một signature Σ = như 
sau : 
R = {man(_), mortal(_)}, F = ∅, C = ∅. 
Câu trên được biểu diễn như sau : 
 ∀x(man(x) → mortal(x)). 
ntsơn 
Chương 3 
Một định nghĩa khác[15] 
Thí dụ : 
Một signature Σ : 
R = {equal(_,_)}, F = {plus(_,_)}, C = ∅. 
Tính giao hoán được biểu diễn như sau : 
 ∀x ∀x equal(plus(x, y), plus(y, x)). 
Viết theo ngôn ngữ thông thường : 
 ∀x ∀x (x + y = y + x). 
ntsơn 
Chương 3 
Phạm vi của lượng từ 
•  Trong công thức (∀x F), F thuộc phạm vi ảnh 
hưởng của ∀x. 
•  Trong công thức (∃x F), phạm vi ảnh hưởng 
của ∃x là F. 
Thí dụ : 
 (∃y)(r(y)) ∧ (∀x)(p(x) → q(f(x), a)). 
 Phạm vi của (∃y) là r(y), 
 phạm vi của (∀x) là (p(x) → q(f(x), a)). 
ntsơn 
Chương 3 
Hiện hữu 
•  Hiện hữu của một biến là sự xuất hiện của biến 
đó trong công thức. 
Thí dụ : 
 ((∀x) p(x,y) ∧ q(t,y)) → (∃y)(r(x,y,z)) có 4 biến. 
 Biến x có 2 hiện hữu, biến y có 3 hiện hữu. 
 Biến z có 1 hiện hữu, biến t có 1 hiện hữu. 
ntsơn 
Chương 3 
Hiện hữu 
•  Hiện hữu ràng buộc là hiện hữu thuộc phạm vi 
của lượng từ có biến cùng tên với nó. 
•  Hiện hữu tự do là hiện hữu không ràng buộc. 
Thí dụ : 
((∀x)(∀y) p(x, y, z)) ∧ ((∀z) q(y, z)) 
Hiện hữu tự do Hiện hữu ràng buộc 
(∀z p(z, y)) ∧ (∀x q(x, y, z)) 
ntsơn 
Chương 3 
Công thức đóng 
•  Công thức đóng : công thức không chứa hiện 
hữu tự do. 
•  Công thức tự do : công thức chứa ít nhất 1 hiện 
hữu tự do. 
Thí dụ : 
 ((∀x)(∀y) p(x, y)) ∧ ((∀z) q(z)) : đóng. 
 ((∀x)(∀y) p(x, y, z)) ∧ ((∀z) q(y, z)) : tự do. 
 (∀z p(z, x)) ∧ (∀x q(x)) : tự do. 
ntsơn 
Chương 3 
Dịch sang Luận lý vị từ 
•  Thí dụ : 
 Every student is younger than some instructor [3’]. 
 Chọn các vị từ : sv(x) = x là SV, 
 gv(x) = x là giảng viên, 
 yg(x, y) = x trẻ hơn y. 
 For every x, if x is a student, then there is some 
y which is an instructor such that x is younger 
than y [3’]. 
 ∀x (sv(x) → ∃y (gv(y) ∧ yg(x,y))) 
ntsơn 
Chương 3 
Dịch sang Luận lý vị từ 
•  Thí dụ : 
 Not all birds can fly [3’]. 
 Chọn các vị từ : ch(x) = x là chim, 
 by(x) = x có thể bay. 
 ¬(∀x (ch(x) → by(x))) 
 Nói cách khác 
 ∃x (ch(x) ∧ ¬by(x)) 
 Nhưng, “all birds can not fly” ? 
ntsơn 
Chương 3 
Dịch sang Luận lý vị từ 
•  Thí dụ : 
 Trẻ con nói chuyện không biết lý luận. 
 Không ai làm việc chăm chỉ lại bị chế nhạo. 
 Ai nói chuyện không biết lý luận thì bị chế nhạo. 
 Vì vậy trẻ con không thể làm việc chăm chỉ. 
 Chọn các vị từ : 
 Lýluận(x) = x biết lý luận. 
 Bịchếnhạo(x) = x bị chế nhạo. 
 Chămchỉ(x) = x làm việc chăm chỉ . 
ntsơn 
Chương 3 
Dịch sang Luận lý vị từ 
•  Trẻ con nói chuyện không biết lý luận 
 ¬Lýluận(trẻcon) (1) 
•  Không ai làm việc chăm chỉ lại bị chế nhạo. 
 ∀x (Chămchỉ(x) → ¬Bịchếnhạo(x)) (2) 
 ∀x (Bịchếnhạo(x) → ¬Chămchỉ(x) ) (2') 
•  Những người không biết lý luận thì bị chế nhạo. 
 ∀x (¬Lýluận(x) → Bịchếnhạo (x)) (3) 
•  Vì vậy trẻ con không thể làm việc chăm chỉ. 
 ¬Chămchỉ(trẻcon) (4) 
ntsơn 
Chương 3 
Dịch sang Luận lý vị từ 
Giải : 
 Phân tích hệ thống thành : 
F = ¬Lýluận(trẻcon) 
G = ∀x (Bịchêbai(x) → ¬Chămchỉ(x)) 
H = ∀x (¬Lýluận(x) → Bịchêbai (x)) 
├─ ¬Chămchỉ(trẻcon) 
ntsơn 
Chương 3 
Dịch sang Luận lý vị từ 
•  Sự mơ hồ của ngôn ngữ tự nhiên. 
 Thí dụ : 
 P = “Tất cả vật màu đỏ ở trong hộp”. 
 Vị từ red(x) = x là vật màu đỏ, 
 box(x) = x ở trong hộp 
 Biểu diễn P trong LLVT ? 
ntsơn 
Chương 3 
Dịch sang Luận lý vị từ 
 P = “Tất cả vật màu đỏ ở trong hộp”. 
 Biểu diễn P trong LLVT : 
 (mã hóa lại red(x) là redx, box(x) là boxx) 
 P1 = ∀x (redx → boxx) 
 P2 = ∀x (redx ∧ boxx) 
 P3 = ∀x ((redx → boxx) ∧ (boxx → redx)) 
ntsơn 
Bài tập 
Chương 3 : Luận lý vị từ 
ntsơn 
Chương 3 
Dịch sang Luận lý vị từ 
1. Dùng các vị từ : tp(x, y) : x thán phục y. 
 td(x, y) : x tham dự y. tg(x) : x là thầy giáo. 
 sv(x) : x là sinh viên. bg(x) : x là bài giảng. 
 Dịch các câu sau thành luận lý vị từ : 
 1.1 Minh thán phục mọi thầy giáo. 
 1.2 Một số thầy thán phục Minh. 
 1.3 Minh thán phục chính mình. 
 1.4 Không SV nào tham dự mọi bài giảng. 
 1.5 Không bài giảng nào được tham dự bởi mọi SV. 
 1.6 Không bài giảng nào được tham dự bởi bất kỳ 1 SV. 
ntsơn 
Chương 3 
Dịch sang Luận lý vị từ 
2. Câu “Minh thán phục mọi thầy giáo” trong câu 1 ở trên được dịch 
thành ∀x tp(minh, tg(x)) sai vì lý do gì ?*. Có thể sửa lại để câu trên 
trở thành đúng ?. 
3. Dịch các câu vị từ sau thành câu tự nhiên : 
 3.1 ∀x∀y (td(x, y) ∧ sv(x) ∧ bg(y)) 
 3.2 ∀x∀y (¬td(x, y) ∧ sv(x) ∧ bg(y)) 
 3.3 ∀x∀y (td(x, y) ∧ ¬sv(x) ∧ bg(y)) 
 3.4 ∀x∀y (td(x, y) ∧ sv(x) ∧ ¬bg(y)) 
 3.5 ∀x∀y (¬td(x, y) ∧ ¬sv(x) ∧ bg(y)) 
 3.6 ∀x∀y (td(x, y) ∧ ¬sv(x) ∧ ¬bg(y)) 
 3.7 ∀x∀y (¬td(x, y) ∧ ¬sv(x) ∧ ¬bg(y)) 
Tương tự thay ∀∀ bằng ∀∃ hay ∃∀ hay ∃∃. 
* (về phương diện cú pháp và ngữ nghĩa) 
ntsơn 
Chương 3 
Dịch sang Luận lý vị từ 
4. Dịch các câu vị từ sau thành câu tự nhiên : 
 4.1 ∀x∀y td(x, y) ∧ ∀x sv(x) ∧ ∀y bg(y) 
 4.2 ∀x∀y td(x, y) ∧ ∀x ¬sv(x) ∧ ∀y bg(y) 
 4.3 ∀x∀y ¬td(x, y) ∧ ∀x ¬sv(x) ∧ ∀y bg(y) 
 4.4 ∀x∀y ¬td(x, y) ∧ ∀x sv(x) ∧ ∀y ¬bg(y) 
 4.5 ∀x∀y ¬td(x,y) ∧ ∀x ¬sv(x) ∧ ∀y ¬bg(y) 
 4.6 ¬ (∀x∀y td(x, y) ∧ ∀x sv(x) ∧ ∀y bg(y)) 
ntsơn 
Chương 3 
Dịch sang Luận lý vị từ 
5.  Dịch các câu sau thành luận lý vị từ : 
 5.1 Tất cả vật màu đỏ ở trong hộp. 
 5.2 Chỉ những vật màu đỏ ở trong hộp. 
 5.3 Không có con vật nào vừa là mèo và 
vừa là chó. 
 5.4 Mọi giải thưởng được giật bởi 1 đứa 
con trai. 
 5.5 Một đứa con trai giật mọi giải thưởng. 
ntsơn 
Chương 3 
Dịch sang Luận lý vị từ 
6. Dùng các vị từ sau để dịch các câu. 
 b(x, y) : x đánh bại y. 
 f(x) : x là một đội bóng đá. 
 q(x, y) : x là tiền vệ của đội bóng y. 
 l(x, y) : x thua y. 
 6.1 mọi đội bóng có một tiền vệ. 
 6.2 Nếu MU đánh bại Chelsi thì MU không thua mọi đội 
bóng (khác). 
 6.3 Chelsi đánh bại một số đội bóng mà nó đánh bại 
MU. 
ntsơn 
Chương 3 
Dịch sang Luận lý vị từ 
7. Chỉ dùng các vị từ cha(x, y), me(x, y), chồng(x, 
y), anh(x, y), chị(x, y) để dịch các câu sau : 
 7.1 Mọi người có một mẹ. 
 7.2 Mọi người có một cha và một mẹ. 
 7.3 Bất cứ ai có một mẹ thì có một cha. 
 7.4 Minh đã là ông nội. 
 7.5 Câu không phải là dì. 
ntsơn 
Chương 3 
Hết slide