BÁO CÁO THU HOẠCH MÔN TOÁN CHO KHOA HỌC MÁY TÍNH
Logic mệnh đề - Logic vị từ
GVHD: P.GS-TS NGUYỄN PHI KHỨ
ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
BÁO CÁO THU HOẠCH MÔN HỌC
TOÁN CHO KHOA HỌC MÁY TÍNH
GVHD: P.GS-TS NGUYỄN PHI KHỨ
HỌC VIÊN: NGÔ HOÀNG LÊ MINH
MSSV: CH1301039
Ngô Hoàng Lê Minh - K8 - UIT
TP HCM-2013
1
UIT
BÁO CÁO THU HOẠCH MÔN TOÁN CHO KHOA HỌC MÁY TÍNH
Logic mệnh đề - Logic vị từ
GVHD: P.GS-TS NGUYỄN PHI KHỨ
LỜI CẢM ƠN
Lời đầu tiên, tôi xin gửi lời chân thành cảm ơn đến Ban Chủ nhiệm trường Đại học
công nghệ thông tin TP HCM đã tạo điều kiện cho tôi được theo học chương trình đào
tạo Thạc Sĩ Công nghệ thông tin của trường.
Tôi xin chân thành cảm ơn thầy P.GS-TS NGUYỄN PHI KHỨ và các thầy cô trong
khoa Khoa học máy tính của trường đã tận tình giảng dạy và hướng dẫn để tôi hoàn
thành tốt bài thu hoạch .
Tuy nhiên vì thời gian cũng như kiến thức của bản thân còn hạn chế, nên bài thu
hoạch không tránh khỏi những sai sót và nhầm lẫn. Rất mong nhận được mọi sự đóng
góp ý kiến từ quý thầy cô và bạn bè.
Ngô Hoàng Lê Minh
Ngô Hoàng Lê Minh - K8 - UIT
TP HCM-2013
2

Logic là gì?
Theo truyền thống, logic là một nhánh của triết học và từ giữa thế kỷ 19 thì logic trở thành
một ngành của toán học dùng để 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. 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.
Logic có quá trình lý luận từ những trường hợp cá biệt suy ra một kết luận tổng quát được
gọi là suy luận quy nạp. Nó được dùng trong các trường hợp mà ta không có đầu đủ các thông tin
ban đầu hay việc thu thập thông tin tốn quá nhiều thời gian hoặc chi phí. Ta chỉ có các kết luận
và thống kê tạm thời. Ngược lại, suy luận diễn dịch là quá trình suy luận từ một phát biểu tổng
quát để suy ra một kết luận cá biệt.
Logic cho khoa học máy tính
Là một loại ngôn ngữ hình thức có cấu trúc và ngữ nghĩa chặt chẽ có các quy luật dẫn tới
các lí luận đúng. Một logic bao gồm: cú pháp, ngữ nghĩa và suy luận. Cú pháp là cách mô tả các
câu trong ngôn ngữ, cho biết cái gì được logic chấp nhận. Ngữ nghĩa dùng để xác định nghĩa của
câu, là nghĩa thực tế của các đối tượng trong logic. Cú pháp là hình thức còn ngữ nghĩa là nội
dung của các đối tượng trong logic.
Có nhiều loại logic như: logic mệnh đề (propositional logic), logic vị từ (predicate logic),
logic vị từ cấp một (first order logic), logic theo thời gian (temporal logic), non-monotonic logic,
Markov logic…
Trong phạm vi bài báo cáo tôi xin phép giới thiệu về 2 loại logic căn bản trong lĩnh vực
logic toán học đó là logic mệnh đề (proposition logic) và logic vị từ (predicate logic).
CHƯƠNG I: LOGIC MỆNH ĐỀ (PROPOSITION LOGIC)
Ngô Hoàng Lê Minh - K8 - UIT
TP HCM-2013
4
BÁO CÁO THU HOẠCH MÔN TOÁN CHO KHOA HỌC MÁY TÍNH
Logic mệnh đề - Logic vị từ
GVHD: P.GS-TS NGUYỄN PHI KHỨ
1.Giới thiệu về mệnh đề:
Logic toán là một phân nhán trong logic học, nó là cơ sở cho mọi ngành toán học. Và cũng

BÁO CÁO THU HOẠCH MÔN TOÁN CHO KHOA HỌC MÁY TÍNH
Logic mệnh đề - Logic vị từ
GVHD: P.GS-TS NGUYỄN PHI KHỨ
4.Các phép toán:
Các công thức nguyên kết hợp với nhau bằng cách sử dụng các phép toán logic cơ bản: hội
∧, tuyển ∨, phủ định ¬, suy ra →, tương đương ↔.
4.1_Phép hội ∧:
Hội của hai mệnh đề a, b là một mệnh đề, đọc là a và b, kí hiệu a Λ b (hoặc a.b), đúng khi
cả hai mệnh đề a, b cùng đúng và sai trong các trường hợp còn lại.
Bảng chân trị:
A b a Λ b
1 1 1
1 0 0
0 1 0
0 0 0
Ví dụ khi ta nói ”ABC là tam giác vuông cân” là hội của hai mệnh đề a=”ABC là tam giác
vuông” và b=”ABC là tam giác cân”. Vì hai mệnh đề này có thể cùng đúng nên P(a Λ b) =1.
4.2_Phép tuyển ∨:
Tuyển của hai mệnh đề a, b là một mệnh đề đọc là a hoặc b, kí hiệu là a ν b (hoặc a+b), sai
khi cả hai mệnh đề cùng sai và đúng trong trường hợp còn lại.
a b
a ∨ b
1 1 1
1 0 1
0 1 1
0 0 0
Phép tuyển "hoặc a hoặc b" là phép tuyển loại trừ để chỉ a hoặc b nhưng không thể cả a lẫn
b.
Phép tuyển "a hoặc b" là phép tuyển không loại trừ để chỉ a hoặc b và có thể cả a lẫn b.
4.3_Phép phủ định ¬:

a b
a ↔ b
1 1 1
1 0 0
0 1 0
0 0 1
Ngô Hoàng Lê Minh - K8 - UIT
TP HCM-2013
7
BÁO CÁO THU HOẠCH MÔN TOÁN CHO KHOA HỌC MÁY TÍNH
Logic mệnh đề - Logic vị từ
GVHD: P.GS-TS NGUYỄN PHI KHỨ
Ta có thể hình dung các từ ngữ trong thế giới thực được mô tả lại trong logic mệnh đề qua
các phép toán trên qua hình minh họa bên dưới.
Các liên từ “nếu”, ”hay”, “và”, “không” trong ngôn ngữ tự nhiên chỉ kết hợp những câu
khai báo trong một số bối cảnh cụ thể. Trong một số bối cảnh khác thì sự kết hợp này là vô
nghĩa.
Các toán tử của logic mệnh đề có thể kết hợp được mọi công thức.
5.Công thức trong logic mệnh đề:
Các công thức được xây dựng theo các quy tắc sau đây:
Ngô Hoàng Lê Minh - K8 - UIT
TP HCM-2013
8
BÁO CÁO THU HOẠCH MÔN TOÁN CHO KHOA HỌC MÁY TÍNH
Logic mệnh đề - Logic vị từ
GVHD: P.GS-TS NGUYỄN PHI KHỨ
i.Mỗi biến mệnh đề là một công thức.
ii.Nếu A là công thức thì ¬A là công thức.
iii.Nếu A và B là công thức thì khi đó: A∧B, A∨B, A→B, A↔B là các công thức.
iiii.Chỉ có những phát biểu ở quy tắc i và iii mới được công nhận là công thức.

BÁO CÁO THU HOẠCH MÔN TOÁN CHO KHOA HỌC MÁY TÍNH
Logic mệnh đề - Logic vị từ
GVHD: P.GS-TS NGUYỄN PHI KHỨ
Vì kết quả 2 bảng chân tri giống nhau nên ta nói ¬ (p∨q) ≡ ¬p ∧ ¬q
Hai mệnh đề a, b gọi là tương đương logic, kí hiệu là a ≡ b nếu chúng cùng đúng hoặc cùng
sai.
Quan hệ P ≡ Q ta gọi là một đẳng thức.
Dưới đây là một số đẳng thức thường gặp trong logic:
6.1_Phủ định của phủ định:
¬¬a ≡ a
6.2_Luật De Morgan:
¬(a∨b) ≡¬a∧¬b
¬(a∧b) ≡¬a∨¬b
6.3_Tính kết hợp:
(a∧b)∧c ≡ a∧(b∧c)
(a∨b) ∨c ≡ a∨ (b∨c)
6.4_Tính giao hoán:
a∨b ≡ b∨a
a∧b ≡ b∧a
a↔b ≡ b↔a
6.5_Tính phân phối:
a∧(b∨c) ≡ (a∧b) ∨ (a∧c)
a∨ (b∧c) ≡ (a∨b) ∧ (a∨c)
6.6_Tính lũy đẳng:
a∧a ≡ a
a∨a ≡ a
6.7_Biểu diễn phép kéo theo:
a → b ≡ ¬a∨b
6.8_Biểu diễn phép tương đương:
a↔b ≡ (a → b) ∧ (b → a)

GVHD: P.GS-TS NGUYỄN PHI KHỨ
Là tuyển các mệnh đề, trong đó mệnh đề là hội các công thức nguyên( hay còn gọi là tổng
các tích). Dạng chuẩn tuyển tổng quát có dạng: P
1
∨ P
2
…∨ P
n
Trong đó P
i=
A
1
∧ A
2
…∧ A
m
và A
i
là công thức nguyên
8.Ngữ nghĩa của logic mệnh đề:
Ngữ nghĩa của logic mệnh đề cho phép ta xác định thiết lập ý nghĩa của các công thức
trong thế giới hiện thực nào đó. Điều đó được thực hiện bằng cách kết hợp mệnh đề với một
phát biểu cho một sự kiện nào đó trong thế giới hiện thực.
Ví dụ: Ký hiệu mệnh đề a có thể ứng với phát biểu “Hà Nội là thủ đô nước Việt Nam”
Bất kỳ một sự kết hợp các kí hiệu mệnh đề với các phát biểu sự kiện trong thế giới thực
được gọi là một minh họa (interpretation ). Một kí hiệu mệnh đề chỉ có thể mang một trong hai
giá trị là đúng(TRUE) hoặc sai(FALSE).
Ở ví dụ trên thì sự kiện “Hà Nội là thủ đô nước Việt Nam” là đúng nên a sẽ mang giá trị
đúng hay nói cách khác a có chân trị là 1, còn khi ta xét b ứng với phát biểu “Hình vuông có 5
cạnh” thì b sẽ có chân trị là 0.

Ví dụ: Khi ta xét câu “Số tự nhiên n chia hết cho 3”, ta thấy về ngôn ngữ đây là 1 câu. Tuy
nhiên nó không phản ánh một thực tế khách quan nào( không xác định được chân trị). Tuy nhiên
khi ta lần lượt thay n bằng các số 3,4 ta sẽ thu được mệnh đề đúng và mệnh đề sai. Trong thực tế
thì các phát biểu dạng như trên là rất nhiều.
Từ các ví dụ trên ta đi đến định nghĩa sau:
Những câu có chứa các biến mà bản thân nó chưa phải là mệnh đề nhưng khi ta thay các
biến đó bởi các phần tử thuộc tập xác định X thì nó trở thành mệnh đề (đúng hoặc sai) ta sẽ gọi
là hàm mệnh đề (hoặc vị từ, hàm phán đoán, mệnh đề không xác định, mệnh đề chứa biến). Tập
X gọi là miền xác định của hàm mệnh đề đó. Ta dùng kí hiệu: T(n), F(x), để chỉ các vị từ.
Nói cách khác logic vị từ bao gồm 2 phần:
i.Biến x.
ii.Tính chất của biến, được gọi là vị từ(predicate).
Theo ví dụ trên thì vị từ T(n) : "Số tự nhiên n chia hết cho 3" có miền xác định là tập các số
tự nhiên N. Tập các số tự nhiên có tổng cái chữ số chia hết cho 3 là miền đúng của T(n).
Ta có phát biểu "Số tự nhiên n chia hết cho 3" không phải là mệnh đề. Để chuyển thành
mệnh đề ta phải thực hiện một trong 2 cách sau:
i.Gán cho n một giá trị.
ii.Thay đổi phát biểu và thêm vào đó các lượng từ.
2.Lượng từ:
Khi nói đến lượng từ cho biến x ta cần đề cập đến miền giá trị (universe of discourse) cho
x. Miền giá trị là tập các đối tượng quan tâm của một biến.
2.1_Lượng từ tồn tại :
Tồn tại x X∈ sao cho T(x) là một mệnh đề tồn tại.
Kí hiệu là:
Ngô Hoàng Lê Minh - K8 - UIT
TP HCM-2013
12
BÁO CÁO THU HOẠCH MÔN TOÁN CHO KHOA HỌC MÁY TÍNH
Logic mệnh đề - Logic vị từ
GVHD: P.GS-TS NGUYỄN PHI KHỨ

H(x): x có chứng chỉ Hoa
P(x): x có chứng chỉ Pháp
Thì i và ii sẽ được phát biểu như sau:
i. x A(x)
ii. x (H(x) ∨ P(x))
3.Phạm vi lượng từ:
Được kí hiệu bởi các dấu [] hay (). Nếu không có các dấu này thì tầm ảnh hưởng là công
thức nhỏ nhất ngay sau lượng từ.
Một biến x được gọi là bound nếu nó được gán giá trị hay được lượng từ hóa. Ngược lại x
sẽ là free khi nó không bound.
Ví dụ:
x ( yP(x,y) ∨ Q(x,y)) khi đó x,y trong P(x,y) là bound và y trong Q(x,y) là free.
4.Thứ tự các lượng từ:
Ngô Hoàng Lê Minh - K8 - UIT
TP HCM-2013
14
BÁO CÁO THU HOẠCH MÔN TOÁN CHO KHOA HỌC MÁY TÍNH
Logic mệnh đề - Logic vị từ
GVHD: P.GS-TS NGUYỄN PHI KHỨ
Thứ tự của các lượng từ là rất quan trọng trong mệnh đề logic. Trừ các trường hợp mà tất
cả các lượng từ là hoặc .
Khi áp dụng thì thứ tự của lượng từ được tính từ trái sang phải và từ trong ra ngoài.
Dưới đây là bảng tóm tắt ý nghĩa của các lượng từ
5.Các luật suy diễn trong logic vị từ
Ngô Hoàng Lê Minh - K8 - UIT
TP HCM-2013
15
BÁO CÁO THU HOẠCH MÔN TOÁN CHO KHOA HỌC MÁY TÍNH
Logic mệnh đề - Logic vị từ
GVHD: P.GS-TS NGUYỄN PHI KHỨ

Ngô Hoàng Lê Minh - K8 - UIT
TP HCM-2013
17
BÁO CÁO THU HOẠCH MÔN TOÁN CHO KHOA HỌC MÁY TÍNH
Logic mệnh đề - Logic vị từ
GVHD: P.GS-TS NGUYỄN PHI KHỨ
LỜI KẾT
Ngày nay, logic đang trở nên rất phổ biến trong đời sống con người. Nó là cơ sở và nền
tảng vững chắc trong rất nhiều lĩnh vực khoa học và ứng dụng. Mặc dù logic mệnh đề, vị từ
không phải là thành tựu cao nhất của logic học và ứng dụng của nó chưa được áp dụng vào thực
tế nhiều như logic mờ nhưng những lợi ích mà nó đem lại thì vô cùng to lớn. Nó là cơ sở logic
chung cho tư duy chính xác, đặc biệt cực kì quan trọng trong các lĩnh vực toán học, khoa học
máy tính, điều khiển tự động…Vì thế logic học nên được đầu tư để trở thành một trong những
môn chủ chốt cho các môn học hiện đại, đặc biệt là khoa học máy tính.
Vì hạn chế của bản thân về môn toán cho khoa học máy tính và bản thân có tham khảo
thêm một số tài liệu được viết bằng tiếng anh nên chắc chắn bài báo cáo còn nhiều sai xót và
nhầm lẫn. Vì thế tôi mong được sự đóng góp của các thầy cô và bạn bè để bài báo các được hoàn
thiện hơn.
Xin chân thành cảm ơn !
Ngô Hoàng Lê Minh - K8 - UIT
TP HCM-2013
18
BÁO CÁO THU HOẠCH MÔN TOÁN CHO KHOA HỌC MÁY TÍNH
Logic mệnh đề - Logic vị từ
GVHD: P.GS-TS NGUYỄN PHI KHỨ
TÀI LIỆU THAM KHẢO
[1]Slide bài giảng Fundamentals of Algorithm của P.GS-TS NGUYỄN PHI KHỨ
[2]Slide bài giảng Luận lí toán học(Mathematical Logic) của Nguyễn Thanh Sơn
[3]Slide bài giảng Logic mệnh đề, Logic vị từ của TS Trần Văn Hoài
[4] />%C3%A1n_h%E1%BB%8Dc