1
HV: NGUYỄN THU THỦY GVHD: PGS.TS.NGUYỄN PHI KHỨ
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
BÀI THU HOẠCH MÔN HỌC
TOÁN CHO MÁY TÍNH
ĐỀ TÀI: TÌM HIỂU VỀ LOGIC VỊ TỪ VÀ NHỮNG ỨNG DỤNG
Trang
2
HV: NGUYỄN THU THỦY GVHD: PGS.TS.NGUYỄN PHI KHỨ
TP.HỒ CHÍ MINH – THÁNG 12 NĂM 2013
LỜI MỞ ĐẦU
Hằng ngày,trước khi bắt tay làm một việc nào đó.Chúng ta đều phải tư duy,suy
nghĩ.chúng ta so sánh, phán đoán, suy lý, trên cơ sở các ý niệm, khái niệm về các hiện
tượng, sự vật xung quanh. Nghĩa là tự nhiên ban cho con người chúng ta bộ não hoạt động
tư duy với các quy luật logic vốn có, khách quan ở tất cả mọi người và mọi dân tộc.Chính
quá trình đó là cơ sở tạo ra sự phát triển của logic học. Các quy luật của tư duy logic là
phổ biến cho toàn nhân loại.
Do đó dẫn đến sự hình thành một loạt các bộ môn logic học hiện đại, như logic học
mệnh đề, logic học vị từ, logic học đa trị, logic học tình thái, logic học xác suất, v.v Các bộ
môn đó cung cấp cho nhân loại những công cụ sắc bén giúp tư duy con người ngày càng
đi sâu hơn vào nhận thức các bí mật của thế giới khách quan.
Sự ra đời của lôgíc mệnh đề đánh dấu bước nhảy vọt trong sự phát triển của lôgíc học,
chuyển từ lôgíc học truyền thống đến lôgíc học hiện đại. Sử dụng toàn bộ những khái
niệm của lôgíc mệnh đề kết hợp với khảo sát các mệnh đề từ việc phân tích các thành phần
của mệnh đề, người ta đã xây dựng các hàm vị từ, đồng thời đưa vào sử dụng hai hằng
lôgíc quan trọng, lượng từ toàn thể và lượng từ bộ phận.
Trang
3
HV: NGUYỄN THU THỦY GVHD: PGS.TS.NGUYỄN PHI KHỨ
Tuy nhiên logic mệnh đề có một số hạn chế .Vì vậy lôgíc vị từ ra đời và đã khắc phục

3.7 Công thức chỉnh dạng (well -
formed formulas)
3.7.1 Xây dựng công thức chỉnh dạng
3.7.2 Chuyển từ Wff sang mệnh đề
3.7.3 Sự tương đương
3.8 Quy tắc suy diễn trong logic vị từ
Trang
5
HV: NGUYỄN THU THỦY GVHD: PGS.TS.NGUYỄN PHI KHỨ
cấp 1
3.9 Dạng chuẩn tắc của công thức
logic vị từ-dạng chuẩn Prenex
3.10 Luật suy diễn
3.11 Các ví dụ
3.11.1 Diễn đạt các câu thông thường
thành biểu thức logic
3.11.2 Diễn đạt biểu thức logic thành
các câu thông thường
4 Ứng dụng1
4.1 Thuật toán các phép tính số
nguyên
4.2 Bài toán cộng hai số nguyên ở
dạng nhị phân
4.3 Bài toán nhân hai số nhị phân
5 Kết luận
6 Tài liệu tham khảo　　　
Trang

hiện các phép biến đổi chính xác và chặt chẽ đối với các khái niệm.

Do đó, LVT không chỉ chính xác hoá cơ sở lôgic của hệ thống phán đoán, mà còn hoàn
thiện cơ sở lôgic của hệ thống khái niệm.
Trang
7
HV: NGUYỄN THU THỦY GVHD: PGS.TS.NGUYỄN PHI KHỨ
3.1. Khái niệm về vị từ
Một vị từ là một khẳng định P(x,y,…) trong đó có chứa một số biến x,y, …Lấy giá trị trong những
tập hợp A,B,… cho trước, sao cho:
• Bản thân P(x,y,…) không phải là mệnh đề.
• Nếu thay x,y,…bằng những giá trị cụ thể thuộc tập hợp A,B,… cho trước ta sẽ được một
mệnh đề P(x,y,…), nghĩa là khi đó chân trị của P(x,y,…) được gọi là các biến tự do của vị từ.
Ví dụ 1: Các câu có liên quan tới các biến như: " x > 3 ", " x + y = 4 " rất hay gặp trong
toán học và trong các chương trình của máy tính. Các câu này không đúng cũng không
sai vì các biến chưa được cho những giá trị xác định.
Nói cách khác, vị từ có thể được xem là một hàm mệnh đề có nhiều
biến hoặc không có biến nào, nó có thể đúng hoặc sai tùy thuộc vào giá trị của biến và lập
luận của vị từ.
Ví dụ 2 : Cho vị từ P(x) = {x>3}. Xác định chân trị của P(4) và P(2).
Giải:
P(4) = {4>3} : mệnh đề đúng.
P(2) = {2>3} : mệnh đề sai.
3.2 Không gian của vị từ
Người ta có thể xem vị từ như là một ánh xạ P, với mỗi phần tử thuộc
tập hợp E ta được một ảnh P(x)∈{ , 1}. Tập hợp E này được gọi là không ϕ
gian của vị từ. Không gian này sẽ chỉ rõ các giá trị khả dĩ của biến x làm
cho P(x) trở thành mệnh đề đúng hoặc sai.
3. 3 Trọng lượng của vị từ
Chúng ta cũng thường gặp những câu có nhiều biến hơn. Vị từ xuất

Là một giá trị xác định trong không gian của vị từ. các hằng được ký
hiệu bởi các chữ thường dùng để đặt tên các đối tượng đặc biệt hay thuộc tính.
3.4.2 Biến:
Dùng để thể hiện các lớp tổng quát của các đối tượng hay các thuộc
tính. Biến được viết bằng các ký hiệu bắt đầu là chữ in hoa. Vậy có thể dùng vị từ có biến
để thể hiện các vị từ tương tự.
Ví dụ : Vị từ "Quả bóng màu xanh" có thể viết lại: "X màu Y". Quả bóng
xanh là các hằng được xác định trong không gian của vị từ. X, Y là biến.
3.4.3 Các vị từ
Một sự kiện hay mệnh đề trong phép toán vị từ được chia thành phần.Vị từ và tham số.
Tham số thể hiện một hay nhiều đối tượng của mệnh đề, còn vị từ dùng để khẳng định về
đối tượng.
Trang
9
HV: NGUYỄN THU THỦY GVHD: PGS.TS.NGUYỄN PHI KHỨ
Ví dụ : Câu "X thích Y" có dạng thích (X, Y).
Thích là vị từ cho biết quan hệ giữa các đối tượng trong ngoặc. Đối số là
các ký hiệu thay cho các đối tượng của bài toán.
3.4.4 Hàm
Được thể hiện bằng ký hiệu, cho biết quan hệ hàm số.
Ví dụ : Hoa là mẹ của Mai, Đông là cha của Cúc. Hoa và Đông là bạn của
nhau.
- Ta có hàm số được viết để thể hiện quan hệ này.
Mẹ (Mai) = Hoa
Cha (Cúc) = Đông
Bạn (Hoa, Đông)
- Các hàm được dùng trong vị tự là: Bạn (Mẹ (Mai), Cha (Cúc)
3.5 Các lượng từ
Trong một vị từ có thể xảy ra các điều sau: vị từ đã cho đúng với mọi phần tử trong
không gian xác định của nó; cũng có thể chỉ đúng với một số phần tử nào đó trong không

∀x P(x) = {tất cả số nguyên tự nhiên x là số chẵn} là mệnh đề sai khi x = 5.
∃x P(x) = {hiện hữu một số nguyên tự nhiên x là số chẵn} là mệnh đề đúng
khi x=10.
Chú ý: Cho P là một vị từ có không gian E. Nếu E = {e1, e2, en}, mệnh
đề∀x P(x) là đúng khi tất cả các mệnh đề P(e1), P(e2), P(en) là đúng.
Nghĩa là∀x P(x) P(e1)⇔ ∧ P(e2)∧ ∧ P(en) là đúng.
Tương tự∃x P(x) là đúng nếu có ít nhất một trong những mệnh đề
P(e1), P(e2), P(en) là đúng. Nghĩa là
∃x P(x) P(e1)⇔ ∨ P(e2)∨ ∨ P(en) là đúng.
Các định lý

Định lý 1: Cho vị từ P(a, b) có trọng lượng là 2. Khi đó:
a)∀a∀b P(a,b) và∀b∀a P(a, b) là có cùng chân trị.
Nghĩa là:∀a∀b P(a,b) ↔∀b∀a P(a, b)
Trang
11
HV: NGUYỄN THU THỦY GVHD: PGS.TS.NGUYỄN PHI KHỨ
Ký hiệu:∀(a,b) P(a,b)
b)∃a∃b P(a,b) và∃b∃a P(a, b) là có cùng chân trị.
Nghĩa là:∃a∃b P(a,b) ↔∃b∃a P(a, b)
Ký hiệu:∃(a,b) P(a,b)
c) Nếu∃a∀b P(a,b) là đúng thì∀b∃a P(a,b) cũng đúng nhưng điều ngược lại chưa đúng.
Nghĩa là:∃a∀b P(a,b) →∀b∃a P(a,b)
d) Nếu∃b∀a P(a,b) là đúng thì∀a∃b P(a,b) cũng đúng nhưng điều ngược
lại chưa đúng. Nghĩa là:∃b∀a P(a,b) →∀a∃b P(a,b)
Định lý 2:
¬(∀x P(x)) và∃x (¬P(x) là có cùng chân trị.
¬(∃x P(x)) và∀x (¬P(x) là có cùng chân trị.
Giải thích:
Phủ định với∀x P(x) nói rằng tập hợp những x làm cho P(x) đúng không là

4 . Nếu mệnh đề∀x (P(x)∨Q(x)) là đúng thì ta có mệnh đề
∀xP(x)∨∀x Q(x) là đúng, nhưng điều ngược lại không luôn luôn đúng.
Chú thích:
 Nếu P và Q là hai vị từ có cùng không gian E. Ta có:
- Tập hợp A⊂E : Tập hợp những phần tử x thuộc E mà ở chúng thì P(x) là đúng.
- Tập hợp B⊂E: Tập hợp những phần tử x thuộc E mà ở chúng thì Q(x) là đúng.
 Nếu P và Q là hai vị từ có cùng không gian E. Ta có:
-Tập hợp A⊂E : Tập hợp những phần tử x thuộc E mà ở chúng thì P(x) là đúng.
-Tập hợp B⊂E: Tập hợp những phần tử x thuộc E mà ở chúng thì Q(x) là đúng.
Khi đó người ta lưu ý rằng, A∧B là tập hợp những x thuộc E mà ở chúng mệnh đề P(x)∧Q(x)
là đúng. Trong khi đó A∨B là tập hợp những x của E mà ở đó mệnh P(x)∨Q(x) là đúng.
3.6 Công thức tương đương
A tương đương B nếu và chỉ nếu (A →B)∧ (B →A)
 Ký hiệu:
A ≡ B |= (A →B)∧ (B →A)
Trang
13
HV: NGUYỄN THU THỦY GVHD: PGS.TS.NGUYỄN PHI KHỨ
3.6.1 Các phép tương đương
+ ~∀x W(x) ≡∃x ~W(x)
+ ~∃x W(x) ≡∀x ~W(x)
+∃x (A(x)∨B(x)) ≡∃x A(x)∨∃x B(x) +∀x (A(x)∧B(x)) ≡∀x
A(x)∧∀x B(x) +∃x (A(x) →B(x)) ≡∀x A(x) →∃x B(x)
+∀x∀y W(x,y) ≡∀y∀x W(x,y) +∃x∃y W(x,y) ≡∃y∃x
W(x,y)
3.6.2 Các phép tương đương có giới hạn
Các phép tương đương sau đúng khi x không xuất hiện trong biểu thức C:
-Disjunction
+∀x(C∨A(x)) ≡ C∨∀x A(x)
+∃x(C∨A(x)) ≡ C∨∃x A(x)

3.7.2 chuyển từ Wff sang mệnh đề
Ví dụ P (x) là Wff : x không âm.
+ Wff này là T, nếu miền giá trị là (1, 3, 5), (2, 4, 6) hoặc các số nguyên
dương. Nhưng nó không còn là T nếu miền giá trị là ( 1, 3, 5), hay các số
nguyên âm
+ Nếu giả thiết Q(x,y) là "x > y" thì∀xQ(x,y) có thể nhận giá trị T hay F tùy
thuộc theo biến y.
Từ ví dụ trên ta rút ra kết luận sau:
- Wff được gọi là thỏa mãn nếu tồn tại một giải thích làm cho nó T
Ví dụ:∀x P(x) là thỏa mãn.
- Wff là hợp lệ nếu nó là đúng với mọi giải thích .
Ví dụ :∀x P(x)∨∃x¬P(x) hợp lệ với mọi P và giải thich.
Wff là không hợp lệ hoặc không thỏa mãn nếu không tồn tại một
giải thích làm Wff T.
Ví dụ :∀x ( P(x)∧ ¬P(x) )
Trang
15
HV: NGUYỄN THU THỦY GVHD: PGS.TS.NGUYỄN PHI KHỨ
3.7.3 Sự tương đương
Hai Wff W1, W2 là tương đương nếu và chỉ nếu W1 ↔ W2 với mọi
giải thích.
Ví dụ
+∀x P(x) ↔∃x¬P (x) với mọi P
+∀x(P(x)∧ Q(x)) ,∀xP(x)∧∀xQ(x) với mọi P,Q
3.8 Quy tắc suy diễn trong logic vị từ cấp 1
+ Quy tắc suy diễn 1 ( rút gọn)
-Công thức cơ sở: (A B)˄ →A≡1
+ Quy tắc suy diễn 2( cộng)
-Công thức cơ sở: A → (AB) ≡ 1
- + Quy tắc suy diễn 3(khẳng

(∀x) (P(x) → R(x)) ≡ 1
3.9 Dạng chuẩn tắc của công thức logic vị từ - dạng chuẩn Prenex
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))).
Qui tắc chuyển một công thức về dạng Prenex:
1. Xóa toán tử "→"
2. Chuyển lượng từ ra phía trước.
• Chuyển về dạng chuẩn Prenex tuyển:
F = (Q1 x1) (Qn xn) (D1∨…∨Dk)
Dk là hội của một hoặc nhiều mệnh đề.
Ví dụ : F = (∀x)(∃z)(∀y)((¬p(x)∧ q(y))∨ (q(y)∧ r(z))).
• Chuyển về dạng Prenex hội :
F = (Q1 x1) (Qn xn) (D1∧…∧ Dk)
Dk là tuyển của một hoặc nhiều mệnh đề.
Ví dụ : F = (∀x)(∃z)(∀y)((¬p(x)∨ q(y))∧ (q(y)∨ r(z))).
• Giải thuật chuyển một công thức về dạng chuẩn Prenex Hội/ Tuyển
- Đổi tên biến.
- Xóa toán tử "→" dùng A → D = ~A∨ B.
- Di chuyển ¬ (~) về bên trái của mỗi mệnh đề.
Trang
17
HV: NGUYỄN THU THỦY GVHD: PGS.TS.NGUYỄN PHI KHỨ
- Chuyển các lượng từ ra bên trái của công thức.
- Dùng luật phân bố và kết hợp để chuyển về dạng tương ứng ( Hội/
Tuyển).
Ví dụ : Cho W=∀xA(x)∨∃xB(x) →C(x)∧∃xC(x).

Ví dụ

:

Biểu diễn câu "Mọi người đều có chính xác một người bạn tốt
nhất"thành một biểu thức logic.
Giải:
Giả sử B(x,y) là câu "y là bạn tốt của x". Để dịch câu trong ví dụ cần chú ý
B(x,y) muốn nói rằng đối với mỗi cá nhân x có một cá nhân khác là y sao cho y là bạn tốt
nhất của x, nếu z là một cá nhân khác y thì z không phải là
bạn tốt nhất của x. Do đó, câu trong ví dụ có thể dịch thành:
∀x∃y∀z [B(x,y)∧((z ≠y) →¬B(x, z))]
Ví dụ: Biểu diễn câu: "Nếu một người nào đó là phụ nữ và đã sinh con, thì
người đó sẽ là mẹ của một người nào khác" thành một biểu thức logic:
Giải:
Giả sử F(x) = "x là phụ nữ"P(x) = "x đã sinh con"và M(x,y) = "x là mẹ của
y"Vì trong ví dụ áp dụng cho tất cả mọi người nên ta có thể viết nó thành
biểu thức như sau:∀x (F(x)∧ P(x)) →∃y M(x,y)
Trang
19
HV: NGUYỄN THU THỦY GVHD: PGS.TS.NGUYỄN PHI KHỨ
Vi dụ
Xét các câu sau. Hai câu đầu tiên là tiền đề và câu ba là kết luận. Toàn bộ
tập hợp 3 câu này được gọi là một suy lý.
+ "Tất cả sư tử Hà Đông đều hung dữ".
+ "Một số sư tử Hà Đông không uống cà phê".
+ "Một số sinh vật hung dữ không uống cà phê".
Giải:
Gọi P(x)= {x là sư tử hà đông}
+ Q(x)= {x hung dữ}

viên y có máy tính và sinh viên x, y là bạn.
Ví dụ Diễn giải phát biểu sau:
∃x∀y∀z (((F(x, y)∧ F(x, z)∧ (y ≠ z)) → ¬F(y, z)))
Trong đó:
• F(x, y): x, y là bạn
• x, y, z ϵ tất cả sinh viên trong trường
Giải:
Tồn tại một sinh viên x, sao cho với mọi sinh viên y, với mọi sinh viên z
khác y, nếu x là bạn của y và x là bạn của z thì y, z không là bạn của nhau.
Từ các ví dụ trên, ta có thể tóm tắt ý nghĩa của lượng từ như sau:
Trang
21
HV: NGUYỄN THU THỦY GVHD: PGS.TS.NGUYỄN PHI KHỨ
4 Ứng dụng:
4.1 Thuật toán các phép tính số nguyên
Các thuật toán thực hiện các phép tính với các so nguyên khi dùng khai
triển nhị phân là hết sức quan trọng trong bộ xử lý số học của máy tính. Như ta đã biết,
thực chất các số nguyên được biểu diễn trong máy tính là các xâu bit nhị phân, do vậy
chúng ta có thể sử dụng biểu diễn nhị phân của các số để thực hiện các phép tính.
Giả sử khai triển nhị phân của các số nguyên tương ứng là:
a = và b = .Khai triển của a và b có đúng n bit( chấp nhận những bit 0 ở
đầu để làm đặc n bit).
4.2 Bài toán cộng hai số nguyên ở dạng nhị phân
Ví dụ: cộng a với b:
+ Trước hết ta cộng hai bit phải nhất ( hai bit có trọng số nhỏ nhât)
+ = *2 + ; trong đó là bit phải nhất của số nguyên tổng a + b, là số cần
nhớ, nó có thể bằng 0 hoặc 1. Sau đó ta cộng hai bit tiep theo và số nhớ:
+ + = *2 + ; là bít tiếp theo của số a + b, là số nhớ. Tiếp tục quá trình
này bằng cách cộng các bit tương ứng trong khai
triển nhị phân và số nhớ, ở giai đoạn cuối cùng :

[2], TS. Trần Văn Hoài, ebook " Predicate logic ", 2008- 2009
[3], Giáo trình logic chuyên ngành -Phạm Đình Nghiệm
Trang