ĐẠ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 KHOA HỌC MÁY TÍNH
ĐỀ TÀI
LÝ THUYẾT LOGIC VỊ TỪ
GVHD: PGS.TS. Nguyễn Phi Khứ
HVTH: Lê Thúc Quốc Anh
MSHV: CH1301002
TP HCM, 12/2013
Bài thu hoạch môn học Toán Cho Khoa Học Máy Tinh Gvhd: PGS.TS. Nguyễn Phi Khứ
MỤC LỤC
Học viên thực hiện: Lê Thúc Quốc Anh - Mã số: CH1301002 Trang 2
Bài thu hoạch môn học Toán Cho Khoa Học Máy Tinh Gvhd: PGS.TS. Nguyễn Phi Khứ
I./ MỞ ĐẦU:
Trong cuộc sống hằng ngày, mọi hoạt động của con người đều thông qua tư duy
của họ. Khác với hành động của con vật mang tính bản năng, hành động của con người
luôn mang tính tự giác. Con người, trước khi bắt tay vào hoạt động thực tiễn cải tạo thế
giới, đều đã có sẵn dự án trong đầu. Sự khác biệt ấy là vì con người có tư duy và biết vận
dụng sức mạnh của tư duy vào việc thực hiện các mục đích của mình. Trong quá trình
hoạt động đó, con người dần dần phát hiện ra các thao tác của tư duy.
Nói đến tư duy logic thì nhân loại, ở châu Phi hay ở châu Âu, ở châu Á hay ở châu
Mỹ, từ Albert Einstein cho đến mỗi người chúng ta, ai ai trong đầu cũng đều có 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 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.
Cùng với sự phát triển của thực tiễn và của nhận thức, con người càng ngày càng
có sự hiểu biết đầy đủ hơn, sâu sắc hơn, chính xác hơn về bản thân tư duy đang nhận
thức. Chính quá trình hiểu biết ấy 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.

Theo truyền thống, logic được nghiên cứu như là một nhánh của triết học. Kể từ
giữa thế kỉ 19, logic đã thường được nghiên cứu trong toán học và luật.
Ngày nay, dưới tác động của cách mạng khoa học – công nghệ hiện đại, logic học
(hình thức) phát triển hết sức mạnh mẽ 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. Sự ra đời của lôgíc vị
từ đã khắc phục những hạn chế của lôgíc mệnh đề như: thiếu việc sử dụng các lượng từ
toàn thể và bộ phận, không phân tích kết cấu của các mệnh đề. Sự khắc phục này cho
phép ta đi sâu vào phân tích ngữ nghĩa của các mệnh đề, các tư tưởng nói chung, mở ra
một khả năng nghiên cứu tính chân lý của các tư tưởng một cách sâu sắc hơn, đầy đủ
hơn. Sau đây em xin trình bày về lý thuyêt logic vị từ và một số ứng dụng của nó.
Học viên thực hiện: Lê Thúc Quốc Anh - Mã số: CH1301002 Trang 3
Bài thu hoạch môn học Toán Cho Khoa Học Máy Tinh Gvhd: PGS.TS. Nguyễn Phi Khứ
II./ NỘI DUNG:
1./ Một số khái niệm:
a./ Thế nào là Logic:
Logic hay luận lý học, nghĩa nguyên thủy là từ ngữ, hoặc điều đã được nói, (nhưng
trong nhiều ngôn ngữ châu Âu đã trở thành có ý nghĩa là suy nghĩ hoặc lập luận hay lý
trí). Logic thường được nhắc đến như là một ngành nghiên cứu về tiêu chí đánh giá các
luận cứ, mặc dù định nghĩa chính xác của logic vẫn là vấn đề còn đang được bàn cãi giữa
các triết gia. Tuy nhiên khi môn học được xác định, nhiệm vụ của nhà logic học vẫn như
cũ: làm đẩy mạnh tiến bộ của việc phân tích các suy luận có hiệu lực và suy luận ngụy
biện để người ta có thể phân biệt được luận cứ nào là hợp lý và luận cứ nào có chỗ không

hợp lý.
Theo truyền thống, logic được nghiên cứu như là một nhánh của triết học. Kể từ
giữa thế kỉ 19 logic đã thường được nghiên cứu trong toán học và luật. Gần đây nhất
logic được áp dụng vào khoa học máy tính và trí tuệ nhân tạo. Là một ngành khoa học
hình thức, logic nghiên cứu và phân loại cấu trúc của các khẳng định và các lý lẽ, cả hai
đều thông qua việc nghiên cứu các hệ thống hình thức của việc suy luận và qua sự nghiên
cứu lý lẽ trong ngôn ngữ tự nhiên. Tầm bao quát của logic do vậy là rất rộng, đi từ các đề
tài cốt lõi như là nghiên cứu các lý lẽ ngụy biện và nghịch lý, đến những phân tích
chuyên gia về lập luận, chẳng hạn lập luận có xác suất đúng và các lý lẽ có liên quan đến
quan hệ nhân quả. Ngày nay, logic còn được sử dụng phổ biến trong lý thuyết lý luận.
Qua suốt quá trình lịch sử, đã có nhiều sự quan tâm trong việc phân biệt lập luận
tốt và lập luận không tốt, và do đó logic đã được nghiên cứu trong một số dạng ít nhiều là
quen thuộc đối với chúng ta. Logic Aristotle chủ yếu quan tâm đến việc dạy lý luận thế
nào cho tốt, và ngày nay vẫn được dạy với mục đích đó, trong khi trong logic toán học và
triết học phân tích (analytical philosophy) người ta nhấn mạnh vào logic như là một đối
tượng nghiên cứu riêng, và do vậy logic được nghiên cứu ở một mức độ trừu tượng hơn.
Các quan tâm về các loại logic khác nhau giải thích rằng logic không phải là được
nghiên cứu trong chân không. Trong khi logic thường có vẻ tự cung cấp sự thúc đẩy
chính nó, môn học này phát triển tốt nhất khi lý do mà chúng ta quan tâm đến logic được
đặt ra một cách rõ ràng.
Cùng với sự phát triển mạnh mẽ của logic học, người ta tiến hành phân loại các hệ
thống Lôgíc học theo những các khác nhau và logic toán là kết quả toán học hóa logic.
Học viên thực hiện: Lê Thúc Quốc Anh - Mã số: CH1301002 Trang 4
Bài thu hoạch môn học Toán Cho Khoa Học Máy Tinh Gvhd: PGS.TS. Nguyễn Phi Khứ
b./ Logic toán là gì:
Logic toán là một ngành con của toán học nghiên cứu các hệ thống hình thức trong
việc mã hóa các khái niệm trực quan về các đối tượng toán học chẳng hạn tập hợp và số,
chứng minh toán học và tính toán. Ngành này thường được chia thành các lĩnh vực con
như lý thuyết mô hình (model theory), lý thuyết chứng minh (proof theory), lý thuyết tập
hợp và lý thuyết đệ quy (recursion theory). Nghiên cứu về logic toán thường đóng vai trò

quan trọng trong ngành cơ sở toán học (foundations of mathematics).
Các tên gọi cũ của logic toán là logic ký hiệu (để đối lập với logic triết học) hay
mêta toán học.
Logic toán không phải là logic của toán học mà là toán học của logic. Ngành này
bao gồm những phần của logic mà có thể được mô hình hóa và nghiên cứu bằng toán
học. Nó cũng bao gồm những lĩnh vực thuần túy toán học như lý thuyết mô hình và lý
thuyết đệ quy, trong đó, khả năng định nghĩa là trung tâm của vấn đề được quan tâm.
Logic toán được xây dựng trên cơ sở logic mệnh đề và logic vị từ.
 Logic mệnh đề:
Cơ sở của logic toán, thực chất bao gồm đại số mệnh đề và hệ toán mệnh đề, gọi
chung là phép tính mệnh đề.
Nhiệm vụ cơ bản của đại số mệnh đề là xây dựng hệ thống quy tắc kết cấu các
mệnh đề, cũng như thực hiện các phép biến đổi mệnh đề đúng đắn, chính xác, chặt chẽ.
Nhờ đó, quá trình lập luận logic sẽ được chuyển thành các hệ toán logic. Hệ toán mệnh
đề là một hệ thống đóng kín, bao gồm các định nghĩa, các quy tắc và một số tiên đề (nếu
là hệ toán logic tiên đề hoá), từ đó nhờ các phép biến đổi đại số mệnh đề người ta có thể
thu được các mệnh đề khác nhau, kết quả có thể đúng hoặc sai tuỳ thuộc giá trị chân lí
của các tiền đề và việc áp dụng các lập luận logic.
 Logic vị từ:
Logic mệnh đề nhờ bổ sung thêm nhiều yếu tố và thành phần mới vào ngôn ngữ
hình thức hoá của phép toán logic mệnh đề. Kết quả, đại số mệnh đề sẽ chuyển thành đại
số vị từ và hệ toán mệnh đề chuyển thành hệ toán vị từ.
Nếu logic mệnh đề cho phép tiến hành các phép biến đổi toán học chính xác và
chặt chẽ đối với các phán đoán thì LVT, hơn thế nữa, còn cho phép thực 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
Học viên thực hiện: Lê Thúc Quốc Anh - Mã số: CH1301002 Trang 5
Bài thu hoạch môn học Toán Cho Khoa Học Máy Tinh Gvhd: PGS.TS. Nguyễn Phi Khứ
hoá cơ sở logic của hệ thống phán đoán, mà còn hoàn thiện cơ sở logic của hệ thống khái
niệm.
2./ Logic vị từ:

Trong toán học hay trong chương trình của máy tính, chúng ta thường gặp những
câu có chứa các biến như sau : "x > 3", "x = y + 3", "x + y = z" Các câu này không
đúng cũng không sai vì các biến chưa được gán cho những giá trị xác định. Câu "x > 3"
có hai bộ phận: bộ phận thứ nhât là biến x đóng vai trò chủ ngữ trong câu; bộ phận thứ
hai "lớn hơn 3" đóng vai trò vị ngữ của câu, nó cho biêt tính chât mà chủ ngữ có thể có.
Có thể ký hiệu câu "x lớn hơn 3" là P(x) với P là ký hieu vị ngữ "lớn hơn 3" và x là biên.
Người ta cũng gọi P(x) là giá trị của hàm mệnh đề P tại x. Xét trong tập hợp các số thực,
một khi biến x được gán giá trị cụ thể thì câu P(x) sẽ có giá trị chân lý. Chẳng hạn P(4) là
đúng còn P(2, 5) là sai. Hàm mệnh đề cũng có thể xét trong tập các số nguyên, số thực
hay số phức, vv…Do đó, chúng ta sẽ xem xét cách tạo ra những mênh đề từ những câu
như vậy.
a./ 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:
o Bản thân P(x, y, …) không phải là mệnh đề.
o 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ụ: Các câu có liên quan tới các biến như: "Số tự nhiên n chia hết cho 5"
Về phương diện ngôn ngữ thì đây là một câu. Nhưng câu này chưa phản ánh tính
đúng hoặc sai một thực tế khách quan nào, cho nên nó chưa phải là mệnh đề. Song nếu ta
thay n bằng số tự nhiên cụ thể, chẳng hạn:
- Thay n = 100 ta được mệnh đề đúng: "Số 100 chia hết cho 5".
- Thay n = 101 ta được mệnh đề sai: "Số 101 chia hết cho 5".
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ừ.
Vi dụ: Câu {n là lẻ} là một vị từ. Nhưng khi cho n là một số cụ thể là chẵn hay là
lẻ ta được một mệnh đề:
Học viên thực hiện: Lê Thúc Quốc Anh - Mã số: CH1301002 Trang 6

Bài thu hoạch môn học Toán Cho Khoa Học Máy Tinh Gvhd: PGS.TS. Nguyễn Phi Khứ
- n = 2: {2 là lẻ}: mệnh đề sai.
- n = 5: {5 là lẻ}: mệnh đề đúng.
Vị từ {n là lẻ} có 2 phần. Phần thứ nhất là biến x là chủ ngữ của câu. Phần thứ hai
"là lẻ" cũng được gọi là vị từ, nó cho biết tính chất mà chủ ngữ có thể có.
o Ký hiệu: P(n) = {n là lẻ}.
o Tổng quát, người ta nói P(n) là giá trị của hàm mệnh đề P tại n. Một khi
biến n được gán trị thì P(n) là một mệnh đề.
Ví dụ: Cho vị từ P(x) = {x > 5}. Xác định chân trị của P(3) và P(8).
Giải:
P(3) = {3 > 5}: mệnh đề sai.
P(8) = {8 > 5}: mệnh đề đúng.
b./ 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.
c./ 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 hiện cũng như
một hàm nhiều biến, khi đó số biến được gọi là trọng lượng của vị từ.
Ví dụ: Vị từ P(a, b, c) = {a + b + c = 15} là một vị từ 3 biến trên không gian N. Ta
nói P có trọng lượng 3.
Trong vị từ P(x1, x2, , xn) có trọng lượng là n. Nếu gán giá trị xác định cho một
biến trong nhiều biến thì ta được một vị từ mới Q(x1, x2, xn) có trọng lượng là (n - 1).
Qui luật này được áp dụng cho đến khi n = 1 thì ta có một mệnh đề. Vậy, thực chất mệnh
đề là một vị từ có trọng lượng là ϕ.
Ví dụ: Cho vị từ P(x, y, z) = {x + y = z}.
- Cho x = ϕ: Q(y, z) = P(ϕ, y, z) = {ϕ + y = z}
- Cho y = ϕ: R(z) = Q(ϕ, z) = P(ϕ, ϕ, z) = {ϕ + ϕ = z}
- Cho z = 1: T = P(ϕ, ϕ, 1) = { ϕ + ϕ = 1}

Học viên thực hiện: Lê Thúc Quốc Anh - Mã số: CH1301002 Trang 7
Bài thu hoạch môn học Toán Cho Khoa Học Máy Tinh Gvhd: PGS.TS. Nguyễn Phi Khứ
là mệnh đề sai.
Câu có dạng P(x1, x2, , xn) được gọi là giá trị của hàm mệnh đề P tại (x1, x2, ,
xn) và P cũng được gọi là vị từ.
d./ Phép toán vị từ:
Phép toán vị từ sử dụng các phép toán logic mệnh đề và là sự mở rộng của phép
toán mệnh đề để thể hiện rõ hơn các tri thức.
Ví dụ: Cần viết câu "nếu hai người thích một người thì họ không thích nhau" dưới
dạng logic vịtừ.
Trước khi viết câu trên ta hãy tìm hiểu các câu đơn giản được viết như sau:
- "Nam thích Mai" được viết theo phép toán vị từ là: thích (Nam, Mai).
- "Đông thích Mai" được viết theo phép toán vị từ là: thích (Đông, Mai).
Tổng quát khẳng định trên được viết như sau:
Thích (X, Z) AND thích (Y, Z) → NOT thích (X, Y)
⇔ (Thích (X, Z) ∧ thích (Y, Z) → ¬thích (X, Y)
Ví dụ: Cho vị từ "Quả bóng màu xanh". Phép toán vị từ cho phép mô tả theo quan
hệ tri thức theo dạng: (quả bóng, xanh).
Cách thể hiện này thuận tiện đối với việc dùng biến và hàm trong xử lý tri thức.
Trong lĩnh vực trí tuệ nhân tạo, để lập trình trên các vị từ người ta sử dụng ngôn ngữ
Prolog. Đó là một ngôn ngữ cấp cao có đặc điểm gần với ngôn ngữ tự nhiên, do ông
C.Cameraller (Đại học Marseilles, Pháp) và nhóm đồng sự cho ra đời năm 1973.
 Hằng:
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.
 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ự.
Học viên thực hiện: Lê Thúc Quốc Anh - Mã số: CH1301002 Trang 8

Bài thu hoạch môn học Toán Cho Khoa Học Máy Tinh Gvhd: PGS.TS. Nguyễn Phi Khứ
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.
 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.
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.
 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 co 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).
e./ Các lượng từ:
Khi tất cả các trong một hàm mệnh đề đều được gán cho một giá trị xác định. Ta
được chân trị của hàm mệnh đề. Tuy nhiên, còn có một cách khác để biến các vị từ thành
mệnh đề mà người ta gọi là sự lượng hóa (hay lượng từ).
 Lượng từ tồn tại (∃):
Câu xác định "Tập hợp những biến x làm cho P(x) là đúng không là tập hợp rỗng"
là một mệnh đề. Hay "Tồn tại ít nhất một phần tử x trong không gian sao cho P(x) là
đúng" là một mệnh đề được gọi là lượng từ tồn tại của P(x).
o Ký hiệu: ∃x P(x)
Học viên thực hiện: Lê Thúc Quốc Anh - Mã số: CH1301002 Trang 9
Bài thu hoạch môn học Toán Cho Khoa Học Máy Tinh Gvhd: PGS.TS. Nguyễn Phi Khứ

 Lượng từ với mọi (∀):
Câu xác định "Tập hơp những x làm cho P(x) đúng là tất cả tập hợp E" là một
mệnh đề. Hay "P(x) đúng với mọi giá trị x trong không gian" cũng là một mệnh đề được
gọi là lượng từ với mọi của P(x).
o Ký hiệu: xP(x)∀
Ý nghĩa của lượng từ "với mọi" và lượng từ "tồn tại" được rút ra trong bảng sau:
Mệnh đề Khi nào đúng Khi nào sai
∀xP(x) P(x) là đúng với mọi phần tử x Có ít nhất 1 phần tử x để P(x)
∃xP(x) Có ít nhất 1 phần tử x để P(x) là
đúng
P(x) là sai với mọi phần tử x
Ví dụ: Cho vị từ P(x) = {số nguyên tự nhiên x là số chẵn}.
Xét chân trị của hai mệnh đề ∀xP(x) và ∃xP(x).
Giải:
- ∀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 đề
xP(x) là đúng khi tất cả các mệnh đề P(e1), P(e2), P(en) là đúng. Có nghĩa là∀
x P(x) P(e1) ∀ ⇔ ∧ P(e2) ∧ ∧ P(en) là đúng.
Tương tự xP(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à xP(x) P(e1) v P(e2) v v P(en) là đúng.∃ ⇔
Ví dụ: Cho P(a, b) = {cặp số nguyên tương ứng thỏa a + b = 5}
Hãy xác định chân trị của các mệnh đề sau:
∀(a,b) P(a,b) {Tất cả cặp số nguyên tượng ứng} F
∃(a,b) P(a,b) {Hiện hữu một cặp số nguyên tương ứng (a, b) sao cho a
+ b = 5}
T
∃b∀a P(a,b) {Hiện hữu một cặp số nguyên tương ứng b sao cho cho
mọi số nguyên tương ứng a ta có a + b = 5}

F
Học viên thực hiện: Lê Thúc Quốc Anh - Mã số: CH1301002 Trang 10
Bài thu hoạch môn học Toán Cho Khoa Học Máy Tinh Gvhd: PGS.TS. Nguyễn Phi Khứ
∀a∃b P(a,b) {Mọi số nguyên tương ứng a, hiện hữu một số nguyên
tưng ứng b sao cho a + b = 5}
T
∃a∀b P(a,b) {Hiện hữu một cặp số nguyên tương ứng a sao cho cho
mọi số nguyên tương ứng b ta có a + b = 5}
T
∀b∃a P(a,b) {Mọi số nguyên tương ứng b, hiện hữu một số nguyên
tương ứng a sao cho a + b = 5}
T
 Các định lý:
 Định lý 1: Cho vị từ P(a, b) có trọng lượng là 2. Khi đó:
o ∀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)
o ∃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)
o 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)
o 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:
o ¬(∀x P(x)) và ∃x (¬P(x)) là có cùng chân trị.
o ¬(∃x P(x)) và ∀x (¬P(x)) là có cùng chân trị.
Giải thích:
o 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à
tất cả tập hợp E. Vậy nói rằng hiện hữu ít nhất một phần tử x ∈ E mà ở

chúng P(x) là sai hay nói rằng hiện hữu ít nhất một phần tử x ∈ E mà ở
chúng P(x) là đúng.
o ¬∃x P(x) nói rằng tập hợp những x mà ở chúng P(x) là đúng là tập hợp
rỗng. Nghĩa là, tập hợp những phần tử x mà ở chúng P(x) là sai là tập E hay
không có phần tử nào làm P(x) đúng. Ta có∀x (¬P(x)).
Ví dụ: Phủ định của "Mọi số nguyên n là chia chẵn cho 3" là "Tồn tại ít nhất một
số nguyên n không chia chẵn cho 3"
Phương pháp ứng dụng: Để đạt được phủ định của một mệnh đề xây dựng bằng
liên kết của những biến của vi từ với phương tiện định lượng, người ta thay thế những
Học viên thực hiện: Lê Thúc Quốc Anh - Mã số: CH1301002 Trang 11
Bài thu hoạch môn học Toán Cho Khoa Học Máy Tinh Gvhd: PGS.TS. Nguyễn Phi Khứ
định lượng với mọi bởi tồn tại , tồn tại bởi với với mọi và sau cùng thay thế vị từ∀ ∃ ∃ ∀
bằng phủ định của vị từ đó.
 Định lý 3: Cho P và Q là hai vị từ có cùng không gian.
o Mệnh đề∀x (P(x) ∧ Q(x)) và (∀x (P(x) ∧ ∀x (Q(x)) là có cùng chân trị.
o Nếu mệnh đề ∃x (P(x) ∧ Q(x)) là đúng thì ta có mệnh đề:
- (∃x P(x)) ∧ (∃xQ(x)) cũng đúng.
o Mệnh đề ∃x (P(x) ∨ Q(x)) và (∃xP(x) ∨ ∃xQ(x)) là có cùng chân trị.
o 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 đúng.
Chú thích:
Nếu P và Q là hai vị từ có cùng không gian E. Ta có :
o 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.
o 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 v B là tập hợp những x của E mà ở đó mệnh đề
P(x) ∨ Q(x) là đúng.
f./ 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)
 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)
Học viên thực hiện: Lê Thúc Quốc Anh - Mã số: CH1301002 Trang 12
Bài thu hoạch môn học Toán Cho Khoa Học Máy Tinh Gvhd: PGS.TS. Nguyễn Phi Khứ
 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:
o Disjunction:
- ∀x(C ∨ A(x)) ≡ C ∨ ∀x A(x)
- ∃x(C ∨ A(x)) ≡ C ∨ ∃x A(x)
o Conjunction:
- ∀x(C ∧ A(x)) ≡ C ∧ ∀x A(x)
- ∃x(C ∧ A(x)) ≡ C ∧ ∃x A(x)
o Implication:
- ∀x (C → A(x)) ≡ C → ∀x A(x)
- ∃x (C → A(x)) ≡ C → ∃x A(x)
- ∀x (A(x) → C) ≡ ∃x A(x) → C
- ∃x (A(x) → C) ≡ ∀x A(x) → C
 Một vài điều kiện không tương đương:
- ∀x W(x) → ∃x W(x)
- ∀x A(x) ∨ ∀x B(x) → ∀x (A(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))

- ∃y ∀x W(x, y) → ∀x ∃y W(x, y)
g./ Công thức chỉnh dạng (well – formed formulas):
Một tên vị từ theo sau bởi một danh sách các biến như: P (x, y), trong đó P là tên
vị từ, và x và y là các biến, được gọi là một công thức nguyên tử.
 Công thức chỉnh dạng (wff) được xây dựng như sau:
- True (T), False (F) là wff.
- Mệnh đề hoặc biến mệnh đề là wff.
- Nếu A và B là wff thì ¬A, A ∧ B, A ∨ B, A → B, A ↔ B là wff.
- Nếu A là wff và x là một biến thì ∃xA và ∀xA là wff.
- Công thức nguyên tử là wff.
Ví dụ:
- ∀x A(x) là wff.
- "Thủ đô của Việt Nam là Hà Nội" là wff.
- ∀x B(x) ∧ ∃x R(x) là wff.
- ∀x B(x) R(x), B(∃x) không là wff.
 Từ Wff sang mệnh đề:
Ví dụ: P(x) là wff: x không âm.
Học viên thực hiện: Lê Thúc Quốc Anh - Mã số: CH1301002 Trang 13
Bài thu hoạch môn học Toán Cho Khoa Học Máy Tinh Gvhd: PGS.TS. Nguyễn Phi Khứ
- Wff này là T, nếu miền giá trị là (1, 2, 3), hoặc các số nguyên dương.
- Wff này là F, nếu miền giá trị là (- 1, 2, 3), hay các số nguyên âm.
- ∀x Q(x, y) có thể nhận giá trị T hay F tùy thuộc theo biến y (với giả thiết
Q(x, y) là "x > y").
Từ ví dụ trên ta rút ra kết luận sau:
o Đặc tả cụ thể của một miền giá trị, vị từ, và việc gán giá trị cụ thể với các
biến tự do trong wff được gọi là sự giải thích.
o Một wff là một mệnh đề khi nó được gán một giải thích.
 Sự tương đương:
o 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)), ∀x P(x) ∧ ∀x Q(x) với mọi P, Q.
 Những dạng Wff:
o Wff là thỏa mãn nếu tồn tại một giải thích làm wff T.
- Ví dụ: ∀x P(x) là thỏa mãn.
o Wff là hợp lệ nếu wff đúng với mọi giải thích.
- Ví dụ: ∀x P(x) ∨ ∃x ¬P(x) là hợp lệ với mọi P và giải thích.
o 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à wff T.
- Ví dụ: ∀x (P(x) ∧ ¬P(x))
h./ Quy tắc và mô hình suy diễn trong logic vị từ cấp 1:
 Quy tắc suy diễn 1 (rút gọn):
o Công thức cơ sở:
 (A ˄ B) → A ≡ 1
Học viên thực hiện: Lê Thúc Quốc Anh - Mã số: CH1301002 Trang 14
Bài thu hoạch môn học Toán Cho Khoa Học Máy Tinh Gvhd: PGS.TS. Nguyễn Phi Khứ
o Mô hình suy diễn:

 Quy tắc suy diễn 2 (cộng):
o Công thức cơ sở:
 A → (AB) ≡ 1
o Mô hình suy diễn:

 Quy tắc suy diễn 3 (khẳng định):
o Công thức cơ sở:
 (A ˄ (A → B)) → B ≡ 1
o Mô hình suy diễn:

 Quy tắc suy diễn 4 (phủ định):

o Công thức cơ sở:
 ((A→B) ˄ )→ ≡ 1
o Mô hình suy diễn:

 Quy tắc suy diễn 5 (bắc cầu)
o Công thức cơ sở:
 ((A → B) ˄ (B → C)) → (A → C) ≡ 1
o Mô hình suy diễn:

 Quy tắc suy diễn 6 (tam đoạn luận tuyển):
o Công thức cơ sở:
 ( ˄ (A ˅ B)) → B ≡ 1
o Mô hình suy diễn:

 Quy tắc suy diễn 7 (mâu thuẫn):
o Công thức cơ sở:
 (
o Mô hình suy diễn:
 ≡
 Quy tắc suy diễn 8 (theo từng trường hợp):
o Công thức cơ sở:
Học viên thực hiện: Lê Thúc Quốc Anh - Mã số: CH1301002 Trang 15
Bài thu hoạch môn học Toán Cho Khoa Học Máy Tinh Gvhd: PGS.TS. Nguyễn Phi Khứ
 ((A → C) ˄ (B → C)) → ((A ˅ B) → C) ≡ 1
o Mô hình suy diễn:

 Quy tắc suy diễn 9 (đặc biệt hóa phổ dụng):
Nếu mệnh đề ∀xP(x) đúng trên trường M thì khi thay x bởi phần tử a bất kỳ
trong M ta được mệnh đề a cũng đúng.
o Công thức cơ sở:

 ∀xP(x) → P(a) ≡ 1
o Mô hình suy diễn:
 với a là phần tử cố định bất kỳ trong M
 Quy tắc suy diễn 10 (tổng quát hóa phổ dụng):
Cho mệnh đề ∀xP(x) trên trường M. Khi đó, nếu P(a) đúng với mọi phần tử a
trên trường M thì mệnh đề ∀xP(x) cũng đúng trên trường M.
o Công thức cơ sở:
 P(a) → ∀xP(x) ≡ 1
o Mô hình suy diễn:
 với a là phần tử bất kỳ trong M.
 Quy tắc suy diễn 11:
o Công thức cơ sở:
 ((∀x)(P(x) → Q(x) ˄ P(a)) → Q(a) ≡ 1, aM mà P(a) đúng.
o Mô hình suy diễn:

 Quy tắc suy diễn 12:
o Công thức cơ sở:
 (∀x)(P(x) → Q(x))
o Mô hình suy diễn:

 Quy tắc suy diễn 13:
o Công thức cơ sở:
 ((∀x)(P(x) → Q(x)) ˄ ( ∀x)(Q(x) → R(x)) → (∀x)(P(x) → R(x)) ≡ 1
Học viên thực hiện: Lê Thúc Quốc Anh - Mã số: CH1301002 Trang 16
Bài thu hoạch môn học Toán Cho Khoa Học Máy Tinh Gvhd: PGS.TS. Nguyễn Phi Khứ
o Mô hình suy diễn:

Ở đây: M = , với = ϕ (I ≠ j)
i./ 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:

o F = (∀x) (p(x) → (∃x) (∀y)(q(y) ∨ r(x)))
o 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:
o Xóa toán tử "→".
o Chuyển lượng từ ra phía trước.
 Chuyển về dạng chuẩn Prenex tuyển:
F = (Q1 x 1) (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 đề.
- 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ụ 23: Cho W= xA(x) xB(x) →C(x) xC(x).∀ ∨ ∃ ∧∃
W ≡ y A(y) z B(z) →C(x) t C(t) (Đổi tên biến)∀ ∨ ∃ ∧ ∃
W ≡ ~ ( y A(y) z B(z)) (C(x) t C(t)) (Xóa "→")∀ ∨ ∃ ∨ ∧ ∃
W ≡ (~ y A(y) ~ z B(z)) (C(x) tC(t)) (Di chuyển ~)∀ ∧ ∃ ∨ ∧ ∃
W ≡ ( y~A(y) z~B(z)) (C(x) t C(t)) ∃ ∧ ∀ ∨ ∧ ∃
W ≡ y z t((~A(y) ~B(z)) (C(x) C(t))) (Di chuyển , )∃ ∀ ∃ ∧ ∨ ∧ ∃ ∀
Học viên thực hiện: Lê Thúc Quốc Anh - Mã số: CH1301002 Trang 17

Bài thu hoạch môn học Toán Cho Khoa Học Máy Tinh Gvhd: PGS.TS. Nguyễn Phi Khứ
Đây là dạng chuẩn Prenex tuyển
j./ Luật suy diễn:
Tên Luật suy diễn
Universal Instantiation xP(x) → P(c)∀
c là 1 giá trị trong universe
Universal Generalization P(c) → xP(x)∀
P(c) là T với mọi c trong một universe đang xem
xét
Existential Instantiation xP(x) ∃ → P(c)
c trong universe vá P(c) là T
Existential Generalization P(c) → xP(x)∃
c trong universe
Negation ¬ x∃ P(x) ↔ x∀ ¬P(x)
Ví dụ : Một hóa đơn là trống nếu nó chưa được thanh toán (bằng tiền mặt) cho 30
ngày. Hóa đơn A vẫn chưa được thanh toán cho 30 ngày. Vì vậy việc kiểm tra này là
trống. Bạn không thể thanh toán cho một hóa đơn trống. Do đó bạn không thể thanh toán
cho hóa đơn A. Bây giờ chúng ta đã có một hóa đơn mà không thể thanh toán.
Ta đặt:
- C(x): x là một hóa đơn
- T(x): x đã được thanh toán trong 30 ngày
- V(x): x là trống
- S(x): x có thể thanh toán
- A: một hóa đơn
Vậy ta có:
- ( x((C(x) ˄ ¬T(x)) → V(x))) ˄ ¬T(A) → V(A)∀
- x((C(x) ˄ V(x) → ¬S(x)) ˄ V(A) → ¬S(A)∀
- C(A) ˄ ¬S(A) → x(C(x) ˄ ¬S(x))∃
k./ Ví dụ:
 Diễn đạt các câu thông thường thành biểu thức logic:

Sau khi đã được giới thiệu về các lượng từ, chúng ta có thể biểu diễn được một
tập hợp rộng lớn các câu thông thường thành các biểu thức logic. Việc làm này
Học viên thực hiện: Lê Thúc Quốc Anh - Mã số: CH1301002 Trang 18
Bài thu hoạch môn học Toán Cho Khoa Học Máy Tinh Gvhd: PGS.TS. Nguyễn Phi Khứ
nhằm mục đích loại đi những điều chưa rõ ràng và người ta có thể sử dụng các
câu suy luận này trong việc lập trình logic và trí tuệ nhân tạo.
o 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ả 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))]∀ ∃ ∀ ∧
o 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ả 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). ∀ ∧ ∃
o Ví dụ: Hãy xét phủ định của câu sau đây :"Tất cả sinh viên trong lớp đều đã
học môn Toán rời rạc 2".
Câu này chính là câu sử dụng lượng từ với mọi như sau: x P(x). Trong đó∀
P(x) = { x đã học môn Toán rời rạc 2 }.
Phủ định của câu này là: "Không phải tất cả các sinh viên trong lớp đều đã học
môn Toán rời rạc 2".
Điều này có nghĩa là:" Có ít nhất một sinh viên ở lớp này chưa học Toán rời
rạc 2".
Đây chính là lượng từ tồn tại của phủ định hàm mệnh đề ban đầu được viết như
sau: x ¬P(x).∃
Ta có:
 ¬ xP(x) x¬P(x)∀ ⇔ ∃

 ¬ xP(x) x¬P(x)∃ ⇔ ∀
 Diễn đạt biểu thức logic thành các câu thông thường:
o Ví dụ: Diễn giải phát biểu sau: x(C(x)˄ y(C(y) F(x, y))))∀ ∃ ∧
Trong đó:
 C(x): x có máy tính
 F(x, y): x, y là bạn
 x, y ϵ tất cả sinh viên trong trường
Học viên thực hiện: Lê Thúc Quốc Anh - Mã số: CH1301002 Trang 19
Bài thu hoạch môn học Toán Cho Khoa Học Máy Tinh Gvhd: PGS.TS. Nguyễn Phi Khứ
Giải:
Với mọi sinh viên x trong trường, hoặc x có máy tính, hoặc tồn tại sinh viên y
có máy tính và sinh viên x, y là bạn.
3./ Ứng dụng: xét một số ứng dụng trên máy tính dưới đây,
a./ Các phép toán bit:
Các hệ thống máy tính thường dùng các bit để biểu diễn thông tin. Mỗi bit có hai
giá trị chân lý hoặc 0 hoặc 1. Vì giá trị chân lý của một biểu thức logic cũng có hai giá trị
đúng (T) hoặc sai (F), nếu ta coi giá trị đúng là 1 và giá trị sai là 0 thì các phép toán với
các bit trong máy tính được tương ứng với các liên từ logic.
Các phép toán với bit được xây dựng trên các xâu bit có cùng độ dài, bao gồm:
AND bit ( phép và cấp bit), OR ( phép hoặc cấp bit), XOR ( phép tuyển loại trừ cấp bit).
Ví dụ: Cho 2 xâu nhị phân là 01101 10110 và 11000 11101, hãy tìm xâu AND bit,
OR bit và XOR bit?
Giải:
Học viên thực hiện: Lê Thúc Quốc Anh - Mã số: CH1301002 Trang 20
Bài thu hoạch môn học Toán Cho Khoa Học Máy Tinh Gvhd: PGS.TS. Nguyễn Phi Khứ
o Phép AND

o Phép OR

o Phép XOR


b./ 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).
c./ Xét 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 2 bit tiếp 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 + . Bit cuối cùng của tồng là . Khi đó khai triển nhị phân của tổng a + b là .
d./ Bài toán nhân hai số nhị phân:
Tương tự, sử dụng qui tắc nhân 2 số nhị phân sau đó cộng kêt quả lại. Ví dụ: Tìm
tích của a = và b =
Giải:
Ta thấy:
 a = *1* =
Học viên thực hiện: Lê Thúc Quốc Anh - Mã số: CH1301002 Trang 21
Bài thu hoạch môn học Toán Cho Khoa Học Máy Tinh Gvhd: PGS.TS. Nguyễn Phi Khứ
 a = *0* =
 a = *1* =
Sử dụng thuật toán tính tổng hai số nguyên a, b có biểu diễn n bit nhị phân (có thể
thêm số 0 vào đầu mỗi toán hạng) ta được:
 =

 + = = ab
III./ KẾT LUẬN:
Mặc dù logic vị từ vẫn còn một số những hạn chế, chưa được ứng dụng nhiều như
logic mờ, chưa phải là đỉnh cao của logic học nhưng những điều mà logic vị từ đã cống
hiến thực sự là rất to lớn, nó là cơ sở logic chung của tư duy chính xác, đặc biệt là các
lĩnh vực như toán học, khoa học thực nghiệm, luật học, kĩ thuật điều khiển từ xa, Có thể
nói logic vị từ là nền tảng của logic toán học hiện đại.
Học viên thực hiện: Lê Thúc Quốc Anh - Mã số: CH1301002 Trang 22
Bài thu hoạch môn học Toán Cho Khoa Học Máy Tinh Gvhd: PGS.TS. Nguyễn Phi Khứ
Tài liệu tham khảo:
1./ />2./ Ebook Predicate Logic - The Stanford University InfoLab (Chapter 14).
3./ Ebook Predicate Logic - Richard L. Epstein.
4./ Ebook Logic in Computer Science - Michael Huth and Mark Ryan (Chapter 2).
5./ Ebook "Logic Vị từ", Nguyễn Quang Châu, khoa CNTT ĐHCN Tp.HCM.
Học viên thực hiện: Lê Thúc Quốc Anh - Mã số: CH1301002 Trang 23