ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
ĐẠ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:

LOGIC VỊ TỪ MỘT SỐ VẤN ĐỀ
LÝ THUYẾT & ỨNG DỤNG

Giảng viên hướng dẫn : PGS.TS. Nguyễn Phi Khứ
Học viên thực hiện : Đào Tấn Ngọc
Mã số : CH1301043
TP. Hồ Chí Minh, ngày 27 tháng 12 năm 2013
MỤC LỤC
MỤC LỤC 1
Lời nói đầu 1
Phần I Một Số Khái Niệm 1
I. Lập luận và Logic 1
II. Vị từ - Predicate 2
III. Mệnh đề (Proposition) là gì? 2
IV. Logic mệnh đề 3
Phần II Logic Vị Từ 6
I. Giới thiệu Logic vị từ 6
II. Các phép toán trên Logic vị từ 11
III. Các lượng từ: ∃, ∀ 12
IV. Quy tắc và mô hình suy diễn trong logic vị từ 15
V. Các luật suy diễn 17
VI. Công thức tương đương 18
VII. Công thức chỉnh dạng (well – formed formulas) 20
VIII. Dạng chuẩn tắc của công thức logic vị từ - dạng chuẩn Prenex 21

Trân trọng!
Phần I Một Số Khái Niệm
I. Lập luận và Logic
1. Lập luận
Loài người thông minh vì biết lập luận. Liệu máy tính có khả năng lập luận
được (như con người) không? Để trả lời câu hỏi này, chúng ta trước hết hãy cho biết
thế nào là lập luận.
Lập luận là hành động sinh ra một phát biểu đúng mới từ các phát biểu đúng
có trước. Hay nói cách khác, một người hoặc một hệ thống được gọi là biết lập luận
nếu nó chỉ ra rằng một phát biểu nào đó có đúng (true) khi cho trước một tập các
phát biểu đúng hay không? Các phát biểu phải tuân theo một tập các qui tắc nhất
định (ngữ pháp) và cách xác định một phát biểu là đúng (true) hay là sai (false).
2. Logic là gì?
Logic hay luận lý học từ tiếng Hy Lạp cổ điển λόγος (logos), 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ĩa 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 hoặ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 và
toán học nghiên cứu về nguyên tắc, phương pháp và tiêu chuẩn hình thức cho sự
hợp lệ của suy luận, và kiến thức
Là khoa học ước lượng các suy luận
Các luật của logic xác định ý nghĩa chính xác của một lý luận.
Logic dùng để làm gì?
 Suy luận toán học
 Khoa học máy tính: vi mạch, xây dựng chương trình, kiểm chứng

…, x
n
) là một vị từ theo n biến (xác định trên A
1
x A
2
x… A
n
)
Ký hiệu
Một phát biểu có n biến x
1
, x
2
, …, x
n
, biểu diễn là P(x
1
, x
2
, …, x
n
), được gọi là
hàm mệnh đề (proposition function)
P được gọi là vị từ
Ví dụ 1:
Xét p(n) = “n > 6”, là một vị từ một biến xác định trên tập các số tự nhiên N
 Ta thấy với n = 7 ; 8 ta được các mệnh đề đúng p(7), p(8), còn n = 0, 1
ta được mệnh đề sai p(0), p(1)
Ví dụ 2 :

4. Bảng chân lý của các toán tử logic
P Q
¬p p ∧ q p ∨ q p ⊕ q
p → q
p ↔ q
T T F T T F T T
T F F T T F F
F T T F T T T F
F F F F F T T
IV. Logic mệnh đề
Logic đơn giản nhất là logic mệnh đề. Các phát biểu trong logic mệnh đề được
hình thành từ các ký hiệu mệnh đề (mỗi ký hiệu có nghĩa là một mệnh đề và vì vậy
có thể nhận giá trị đúng hoặc sai tùy theo mệnh đề đó là đúng hay sai trong thế giới
thực) và các ký hiệu liên kết ¬ (với ngữ nghĩa là phủ định), ∧ (và), ∨ (hoặc), ⇒
(kéo theo), ⇔ (tương đương). Cú pháp và ngữ nghĩa của logic mệnh đề như sau :
1. Cú pháp
a) Các ký hiệu
Hằng : true, false
Ký hiệu : P, Q,… Mỗi ký hiệu gọi là ký hiệu mệnh đề hoặc mệnh đề.
Các kết nối logic : ¬, ∧, ∨
HV: Đào Tấn Ngọc CH1301043 Trang 3
Các ký hiệu “(“ và “)”
b) Quy tắc xây dựng câu
Có hai loại câu : câu đơn và câu phức
True và false là các câu (true là câu đơn hằng đúng, false là câu hằng sai)
Mỗi ký hiệu mệnh đề là một câu, ví dụ P, Q là các câu (Câu đơn)
Nếu A và B là các câu thì các công thức sau cũng là câu (các câu phức) :
 ¬A
 (A ∧ B)
 (A ∨ B)

• (A ⇒ B) biểu diễn mối quan hệ “A kéo theo B”, chỉ nhận giá trị false
khi A là true và B là false, nhận giá trị true trong các trường hợp khác
• (A ⇔ B) biểu diễn mối quan hệ “A kéo theo B” và “B kéo theo A”
Như vậy, việc xác định tính đúng/sai của một ký hiệu mệnh đề (mệnh đề đơn)
là dựa trên tính đúng sai của sự kiện hoặc thông tin mà nó ám chỉ, còn việc xác định
tính đúng sai của mệnh đề phức phải tuân theo các qui tắc trên. Trong nhiều trường
hợp, chúng ta (cần chỉ) biết tính đúng/sai của các câu phúc, còn tính đúng/sai của
các câu đơn là không cần biết hoặc có thể lập luận ra từ các câu phức đã biết
đúng/sai và các qui tắc chuyển đổi tính đúng/sai giữa các câu đơn và câu phức theo
các qui tắc trên.
3. Các ví dụ
Gọi là mệnh đề “tôi chăm học”, B là mệnh đề “tôi thông minh”, C là mệnh đề
“tôi thi đạt điểm cao môn Toán cho khoa học máy tính”; Ta có thể biểu diễn các câu
sau trong logic mệnh đề:
− “Nếu tôi chăm học thì tôi thi đạt điểm cao môn Toán cho khoa học máy
tính”: A ⇒ C
− “Tôi vừa chăm học lại vừa thông minh”: A ∧ B
− “Nếu tôi chăm học hoặc tôi thông minh thì tôi thi đạt điểm cao môn
Toán cho khoa học máy tính”: A ∨ B ⇒ C
4. Các câu hằng đúng
Trong logic mệnh đề, ta có:
 ¬¬A ⇔ A (luật phủ định kép)
 A ∨ ¬A (luật loại trừ)
 (A ⇔ b) ⇔ (A ⇒ B) ∧ (B ⇒ A)
 (A ⇒ B) ⇔ ¬A ∨ B
 ¬(A ∨ B) ⇔ ¬A ∧ ¬B (luật Demorgan đối với ghép ∨)
 ¬(A ∧ B) ⇔ ¬A ∨ ¬B (luật Demorgan đối với phép ∧)
 C ∨ (A ∧ B) ⇔ (C ∨ A) ∧ (C ∨ B) (luật phân phối phép ∨ đối với phép
∧)
HV: Đào Tấn Ngọc CH1301043 Trang 5

nối logic (¬, ∧, ∨, ⇒, ⇔) biểu diễn mệnh đề phức, mô tả quan hệ hoặc liên kết các
mệnh đề đơn. Như vậy, logic mệnh đề chỉ có thể biểu diễn được các MỆNH ĐỀ và
các liên kết hoặc quan hệ giữa các MỆNH ĐỀ. Vì vậy sức mạnh biểu diễn của logic
mệnh đề chỉ giới hạn trong thế giới các mệnh đề. Nó không quan tâm đến nội dung
các mệnh đề như thế nào. Vì thế mà logic mệnh đề có những hạn chế trong việc biểu
diễn và suy diễn.
Logic mệnh đề thiếu các câu mô tả đặc trưng cho một lớp các đối tượng (cũng
giống như nếu một ngôn ngữ lập trình mà thiếu các câu lệnh lặp như for, while mà
chỉ cỏ các kiểu lệnh đơn lẻ và rẽ nhánh), vì thế mà sức mạnh biểu diễn của nó rất
hạn chế.
Trong chương này, chúng ta sẽ xem xét logic cấp một, hay logic vị từ, một mở
rộng của logic mệnh đề mà cho phép biểu diễn những mệnh đề mang tính phổ quát
(“với mọi”) và những mệnh đề mang tính đặc thù (“tồn tại”) một cách dễ dàng. Để
làm được điều đó, chúng ta phân tích mệnh đề thành dạng (chủ ngữ - vị từ) hoặc
(chủ ngữ - vị từ - tân ngữ) và chuyển chủ ngữ và tân ngữ thành đối tượng (hoặc
biến) của vị từ. Vì vậy mà câu đơn của logic cấp một có dạng Vị_từ(chủ_ngữ) hoặc
Vị_từ(chủ_ngữ, tân ngữ); chẳng hạn “An là sinh viên” biểu diễn là Sinhvien(An);
“An yêu Bình” biểu diễn là Yeu(An,Binh). Chính vì thế mà ta gọi nó là logic vị từ.
Từ các câu đơn như vậy ta xây dựng các câu phức sử dụng các ký hiệu (¬, ∧, ∨, ⇒,
⇔) và ∀, ∃ (hai ký hiệu này không có trong logic mệnh đề). Quan trọng hơn, làm
thế nào chúng ta xây dựng các thuật giải lập luận tự động, giải thuật cài đặt cho máy
tính để nó có thể chứng minh được KB ╞ q, với KB và q là các câu trong logic vị từ
cấp một, tương tự như các giải thuật phân giải, giải thuật suy diễn tiến, lùi trong
logic mệnh đề.
Trong logic vị từ, một mệnh đề được cấu tạo bởi hai thành phần là các đối
tượng tri thức và mối liên hệ giữa chúng (gọi là vị từ)
Vị từ (<đối tượng 1>, <đối tượng 2>, …, <đối tượng n>)
Như vậy để biểu diễn vị của các trái cây, các mệnh đề sẽ được viết lại thành:
Cam có vị Ngọt Vị (Cam, Ngọt) ⇒
Cam có màu Xanh Màu (Cam, Xanh)⇒

câu hằng sai).
 Câu đơn : Ký_hiệu_vị_từ(hạng_thức_1, hạng_thức_2, …,
hạng_thức_k)
là một câu (câu đơn), trong đó hạng_thức_i là biểu thức của các đối tượng,
cú pháp của hạng thức được xây dựng từ các ký hiệu hằng, biến và hàm
như sau:
 Các ký hiệu hằng và các ký hiệu biến là một hạng thức
 Nếu t1, t2, ,tn là các hạng thức và f là một ký hiệu hàm gồm
n tham số thì f(t1, t2, ,tn) cũng là một hạng thức
Ví dụ về các câu đơn là:
• love(An,Binh)
HV: Đào Tấn Ngọc CH1301043 Trang 8
• father(An,Nhan)
• sinhvien(Hoa)
 Câu phức: Nếu A, B là các câu và x là một ký hiệu biến thì các công
thức sau cũng là câu:
 ¬A
 (A ∧ B)
 (A ∨ B)
 (A ⇒ B)
 (A ⇔ B)
 ∀x, A
 ∃x, A
c) Các khái niệm và qui ước khác
 Nếu một hạng thức không chứa biến thì gọi là hạng thức nền
 Một câu đơn cũng có tên gọi là câu phân tử hay công thức phân tử
 Một câu đơn hoặc phủ định của một câu đơn thì gọi là literal
 Trong công thức có ký hiệu lượng tử ( x, A hoặc x, A) các biến x∀ ∃
trong A gọi là biến buộc (biến lượng tử), biến nào trong A không phải
là biến lượng tử thì gọi là biến tự do. Các câu mà không có biến tự do

Như vậy, việc xác định tính đúng/sai của một câu đơn (vị từ) là dựa trên tính
đúng sai của sự kiện hoặc thông tin mà nó ám chỉ, còn việc xác định tính đúng sai
của câu phức phải tuân theo các qui tắc trên. Trong nhiều trường hợp, chúng ta (cần
chỉ) biết tính đúng/sai của các câu phức, còn tính đúng/sai của các câu đơn là không
cần biết hoặc có thể lập luận ra từ các các câu phức đã biết đúng/sai và các qui tắc
chuyển đổi tính đúng/sai giữa các câu đơn và câu phức theo các qui tắc trên.
4. Các ví dụ
Các câu trong ngôn ngữ tự nhiên có thể biểu diễn trong logic vị từ cấp một:
 “An là sinh viên” Sinhvien(An)
 “Nam là cha của Hoàn” Cha(Nam,Hoàn)
 “Mọi sinh viên đều học giỏi” x Sinhvien(x) Hocgioi(x)∀ ⇒
(chú ý thường đi với . Khác với x Sinhvien(x) Hocgioi(x))∀ ⇒ ∀ ∧
 “Trong sinh viên có bạn học giỏi” x Sinhvien(x) Hocgioi(x)∃ ∧
(chú ý thường đi với . Khác với x Sinhvien(x) Hocgioi(x).∃ ∧ ∃ ⇒
5. 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ử x 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.
HV: Đào Tấn Ngọc CH1301043 Trang
10
6. 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ụ1: Vị từ P(a,b) = {a + b = 5} là một vị từ 2 biến trên không gian N. Ta nói
P có trong lượng 2.
Trong một 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 đề.

ký hiệu thay cho các đối tượng của bài toán.
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))
III. Các lượng từ:
∃
,
∀
1. 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).
Ký hiệu: ∃ x P(x).
Ví dụ : ∀ X likes(X, ice-cream).
2. 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).
Ký hiệu: ∀ x P(x).
Ví dụ : ∃ Y friends(Y, tom).
3. Bảng tóm tắt ý nghĩa của lượng từ
Phát biểu Khi nào đúng ? Khi nào sai ?
HV: Đào Tấn Ngọc CH1301043 Trang
12
∀

y,
∀
x P(x ,y)
Tồn tại một cặp x, y sao
cho P(x, y) là T
P(x, y) là F với mọi x, y
Ví dụ : Xét trong không gian các số thực, ta có :
Cho P(x) := "x + 1>x ", khi đó có thể viết :
∀
x P(x)
Cho P(x) := "2x = x + 1", khi đó có thể viết :
∃
x P(x)
Các định lý :
a) Định lý 1
Cho vị từ P(a, b) có trọng lượng là 2. Khi đó:

∀
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)

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)
 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à:

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ữa í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 ¬∃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ụ 1: 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”
Ví dụ 2 : 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 cho khoa học máy tính”
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 cho khoa học máy tính}.
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 cho khoa học máy tính ”. Đ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 môn Toán cho khoa học máy tính”. Đâ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ó :
¬∀x P(x) ⇔ ∃x ¬P(x)
¬∃x P(x) ⇔ ∀x ¬P(x)
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 vị từ với phương tiện định lượng, người ta thay thế
những định lượng ∀ bởi ∃, và ∃ bởi ∀ và sau cùng thay thế vị từ bằng phủ định của
vị từ đó.
c) Định lý 3
Cho P và Q là hai vị từ có cùng không gian.
 Mệnh đề
∀
x (P(x)
∧
Q(x)) và (

∀
x (P(x)
∨

∀
x Q(x)
là đúng, nhưng điều ngược lại không luôn luôn đúng.
HV: Đào Tấn Ngọc CH1301043 Trang
14
IV. Quy tắc và mô hình suy diễn trong logic vị từ
1. Quy tắc suy diễn 1 (rút gọn)
 Công thức cơ sở : (A ∧ B)  A ≡ 1
 Mô hình suy diễn:
A
B
∴A
2. Quy tắc suy diễn 2 (cộng)
 Công thức cơ sở: A  (AB) ≡ 1
 Mô hình suy diễn:
A
∴A ∨ B
3. Quy tắc suy diễn 3 (khẳng định)
 Công thức cơ sở: (A ∧ (A  B)  B ≡ 1
 Mô hình suy diễn:
A
A  B
∴B
4. Quy tắc suy diễn 4 (phủ định)
 Công thức cơ sở: ((A  B) ∧¬B)  ¬A ≡ 1
 Mô hình suy diễn:

với a là phần tử cố định bất kỳ trong M.
9. Quy tắc suy diễn 9 (tổng quát hóa phổ dụng)
Cho mệnh đề ∀x P(x) đúng 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 đề ∀x P(x) cũng đúng trên trường M.
 Công thức cơ sở: P(a)  ∀x P(x) ≡ 1
 Mô hình suy diễn:
P(a)
∴∀x P(x)
HV: Đào Tấn Ngọc CH1301043 Trang
16
với x là phần tử bất kỳ trong M.
10. Quy tắc suy diễn 10
 Công thức cơ sở: ((∀x) (P(x)  Q(x) ∧ P(a)) ≡1, aM mà P(a) đúng
 Mô hình suy diễn:
(∀x) (P(x)  Q(x))
P(a)
∴Q(a)
11.Quy tắc suy diễn 11
 Công thức cơ sở: (∀x) (P(x)  Q(x))
 Mô hình suy diễn:
(∀x) (P(x)  Q(x))
(∀x) (Q(x)  R(x))
∴(∀x) (P(x)  Q(x))
12.Quy tắc suy diễn 12
 Công thức cơ sở: ((∀x) (P(x)  Q(x)) ∧ (∀x)(Q(x)  R(x))  (∀x)
(P(x)  R(x)) ≡ 1
 Mô hình suy diễn:
(∀x ∈ M
1
) P(x)

Cho trước: (1) ∀ X (man(X) ⇒ mortal(X))
(2) man(socrates)
⇒ (3) man(socrates) ⇒ mortal(socrates) từ (1),(2) bằng luật UI.
(4) mortal(socrates) từ (3) và (2) bằng luật MP.
VI.Công thức tương đương
A tương đương B nếu và chỉ nếu (A  B) ∧ (B  A)
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)
HV: Đào Tấn Ngọc CH1301043 Trang
18
 ∀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)
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)
− Conjunction
 ∀x (C ∧ A(x)) ≡ C ∧∀x A(x)
 ∃x (C ∧ A(x)) ≡ C ∧∃x A(x)
− 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
3. Một vài điều kiện không tương đương

Ví dụ 2: ∀x P(x) là thỏa mãn.
Wff là hợp lệ (valid) nếu nó là đúng với mọi giải thích.
HV: Đào Tấn Ngọc CH1301043 Trang
20
Ví dụ 3 : ∀x P(x) ∨ ∃x ¬P(x) hợp lệ với mọi P và giải thích.
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 là T.
3. Sự tương đương
Hai Wff W1, W2 là tương đương (equivalence) 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
VIII. 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)))
Quy tắc chuyển một công thức về dạng Prenex :
Xóa toán tử “”
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 x
n
)(D
1

Ví dụ: Cho W = ∀x A(x) ∨ ∃x B(x)  C(x) ∧ ∃x C(x).
W = ∀y A(y) ∨ ∃z B(z)  C(x) ∧ ∃t C(t) (Đổi tên biến)
≡ ∼(∀y A(y) ∨ ∃z B(z)) ∨ (C(x) ∧ ∃t C(t)) (Xóa “

”)
≡ (∼∀y A(y) ∧ ∼∃z B(z)) ∨ (C(x) ∧ ∃t C(t)) (Di chuyển “
∼
”)
≡ (∃y∼A(y) ∧ ∀z∼B(z)) ∨ (C(x) ∧ ∃t C(t))
≡∃y∀z∃t ((∼A(y) ∧ ∼B(z)) ∨ (C(x) ∧ C(t))) (Di chuyển ∃, ∀)
Đây là dạng chuẩn Prenex tuyển
HV: Đào Tấn Ngọc CH1301043 Trang
22