Giáo trình Logic chuyên ngành

PHẠM ĐÌNH NGHIỆM 
LOGIC CHUYÊN NGÀNH 
Giáo trình dành cho sinh viên ngành triết học 
TP. HỒ CHÍ MINH 2006 
 1
Phủ định 
Chương I LOGIC MỆNH ĐỀ 
I. Mệnh đề. Các phép toán trên mệnh đề 
1. Mệnh đề 
Trong Tiếng Việt (và các ngôn ngữ khác) có những câu - thường là câu tường thuật - mô tả 
sự vật và hiện tượng. Có những câu mô tả đúng, cũng có những câu mô tả sai sự vật và hiện 
tượng. Những câu như thế, cả câu đúng và câu sai, được gọi là mệnh đề1. Ví dụ, các câu sau: 
(a) Nam là sinh viên; 
(b) Khí hậu trái đất đang nóng dần lên; 
(c) Bạn có thể thất vọng khi bị thất bại nhưng bạn sẽ không là gì cả nếu không nỗ lực hết mình 
(Beverly Silis); 
(d) Nếu người vợ đẹp mà không phải là thiên thần thì người chồng vô cùng bất hạnh (J.J. 
Rousseau); 
là các mệnh đề. 
Không phải câu nào cũng hoặc đúng hoặc sai. Các câu hỏi, câu mệnh lệnh, câu cảm thán 
không mô tả cái gì nên không đúng mà cũng không sai. Có cả những câu tường thuật không thể 
xác định là đúng hay sai. Chẳng hạn, câu “Tôi nói dối” không thể là đúng, nhưng cũng không 
sai. Những câu không đúng, không sai như thế không phải là mệnh đề. 
Các mệnh đề không thể tách ra thành các mệnh đề đơn giản hơn gọi là mệnh đề đơn. Các 
mệnh đề có thể tách thành các mệnh đề đơn giản hơn gọi là mệnh đề phức. Nói cách khác, 
mệnh đề phức được tạo thành từ các mệnh đề đơn. Các mệnh đề (a) và (b) trên đây là mệnh đề 
đơn, còn (c), (d) là các mệnh đề phức. 
2. Các phép toán logic trên mệnh đề 
Như trên kia đã nói, có thể xây dựng các mệnh đề phức tạp từ những mệnh đề đơn giản 
hơn. Việc này thực hiện được nhờ các phép toán (toán tử) logic. 
Phủ định là một trong những phép toán đơn giản nhất trên mệnh đề. Đó là phép toán 
một ngôi. Mặc dầu trong ngôn ngữ tự nhiên một mệnh đề nào đó có thể bị phủ định bằng nhiều 
cách khác nhau, ở đây ta chỉ phủ định một mệnh đề bằng một cách duy nhất, bằng cách đặt dấu 
¬ trước mệnh đề đó. Nếu A là một mệnh đề, thì ¬ A là phủ định của mệnh đề A. 
Phép toán phủ định được định nghĩa bằng bảng chân lý sau: 
 A ¬A 
1 Mệnh đề và câu, xét nghiêm ngặt, khác nhau. Nhưng trong chương trình này, để cho đơn giản, chúng tôi đồng 
nhất mệnh đề với câu tường thuật. 
 2
 T F 
 F T 
Các chữ cái T và F ở đây chỉ các giá trị chân lý “đúng” (True) và “sai” (False) tương ứng. 
Trong bảng trên, nếu A đúng thì phủ định của nó, ¬ A, sai, và ngược lại, nếu A sai thì ¬A là 
đúng. 
Hội là phép toán phổ biến thứ hai trên mệnh đề. Người ta còn gọi nó là phép liên kết. 
Liên kết của hai mệnh đề A và B được ký hiệu bằng A & B. Bảng chân lý định nghĩa phép hội 
như sau (xem bảng). Mệnh đề A & B đúng khi và chỉ khi A đúng và B đúng. Các mệnh đề A và 
B được gọi là các thành phần liên kết của mệnh đề A & B. 
A B A & B A B A ∨ B A B A ∨ B 
T 
T 
F 
F 
 T 
 F 
 T 
 F 
 T 
 F 
 F 
 F 
 T 
 T 
 F 
 F 
 T 
 F 
 T 
 F 
 T 
 T 
 T 
 F 
 T 
 T 
 F 
 F 
 T 
 F 
 T 
 F 
 F 
 T 
 T 
 F 
Lựa chọn là phép tính phổ biến thứ ba trên mệnh đề. Người ta còn gọi nó là phép tuyển. 
Trong tiếng Việt phép toán này thường được biểu thị bằng từ “hoặc”, “hoặc là”, “hay”, “hay 
là”. Lựa chọn có thể được hiểu theo hai nghĩa khác nhau. Trong nghĩa thứ nhất “A hoặc B” (ký 
hiệu là A ∨ B) được hiểu là đúng khi có ít nhất một trong hai thành phần A hoặc B đúng , hoặc 
là cả A và B cùng đúng. Trong nghĩa thứ hai “A hoặc B” (ký hiệu là A ∨ B) đúng khi A đúng, B 
sai, hoặc là khi A sai, B đúng. Nghĩa thứ nhất là phép tuyển không nghiêm ngặt, phép tuyển 
nghiêm ngặt ứng với nghĩa thứ hai. Phép tuyển nghiêm ngặt được ký hiệu là ∨ . Bảng chân lý 
của phép tuyển không nghiêm ngặt và nghiêm ngặt được dẫn ở trên. 
Kéo theo là một phép toán hai ngôi được định nghĩa bằng bảng chân lý quan trọng nữa 
trên các mệnh đề. Với các mệnh đề A và B phép toán này cho phép tạo nên mệnh đề A ⊃ B. 
Nghĩa của mệnh đề này là “Nếu A thì B”, hay là “A kéo theo B”. Nghĩa này không được xác 
định rõ ràng trong những ứng dụng thông thường. Ta chỉ biết rằng “A kéo theo B” đúng có 
nghĩa là nếu A đúng thì B phải đúng. Trong tiếng Việt phép toán này thường được diễn đạt 
bằng các cụm từ “Nếu  thì  “, “Nếu  sẽ  “,“Khi nào  thì  “, “Bao giờ  thì  “, 
“ thì “ và một số cụm từ khác. Ví dụ, các câu “Nếu không bảo vệ môi trường ngay từ bây 
giờ thì loài người sẽ không có tương lai” ; “Chuồn chuồn bay thấp thì mưa”; “Có nước thì có 
cá”; “Bao giờ chạch đẻ ngọn đa, sáo đẻ dưới nước thì ta lấy mình”  biểu đạt các mệnh đề 
dạng kéo theo. Trong ngôn ngữ thông thường, và cả trong các suy luận toán học hoặc các khoa 
học khác, nghĩa của cụm từ “nếu  thì ” và các cụm từ khác diễn đạt phép kéo theo được 
Tuyển không nghiêm ngặt Tuyển nghiêm ngặt Hội 
 3
hiểu phụ thuộc vào văn cảnh. Câu “Nếu A thì B” trong tiếng Việt thường biểu thị một mối liên 
hệ giữa A và B về nội dung. Chẳng hạn, A là điều kiện, B là hệ quả (vì vậy mệnh đề loại này 
còn được gọi là mệnh đề điều kiện), hay A là nguyên nhân, B là kết quả. Nhưng trong logic 
mệnh đề chúng ta không quan tâm đến mối liên hệ về mặt nội dung đó, mà chỉ quan tâm đến 
mối liên hệ về giá trị chân lý của chúng mà thôi. Cụ thể là ta sẽ coi là “Nếu A thì B” chỉ sai khi 
A đúng mà B sai. Trong tất cả các trường hợp khác “Nếu A thì B” đúng. 
A B A ⊃ B A B A ≡ B 
T 
T 
F 
F 
T 
F 
T 
F 
T 
F 
T 
T 
 T 
T 
F 
F 
T 
F 
T 
F 
T 
F 
F 
T 
Bảng chân lý của phép kéo theo được dẫn ở trên. 
Nếu ký hiệu cụm từ “A tương đương B” là A ≡ B thì ta có bảng chân lý cho phép tương 
đương như dẫn ở trên. A ≡ B đúng khi và chỉ khi A và B có cùng một giá trị chân lý như nhau. 
Độ ưu tiên thực hiện các phép toán được xác định theo thứ tự giảm dần như sau : ¬, &, 
∨, ⊃, ≡. Cùng một phép toán thì chúng được kết hợp về bên phải2, nghĩa là: 
p ∨ q ∨ r ⇔ p ∨ (q ∨ r) 
p & q & r ⇔ p & (q & r) 
p ⊃ q ⊃ r ⇔ p ⊃ (q ⊃ r) 
¬¬ p ⇔ ¬ (¬p) 
p ≡ q ≡ r ⇔ p ≡ (q ≡ r) 
3. Định nghĩa các phép toán logic bằng phương pháp giải tích 
Nếu ký hiệu val(A) là giá trị logic của công thức A, ký hiệu val(A) = T là val(A) = 1 thì bảng 
định nghĩa các phép toán logic cho thấy : 
 val(A ∨ B) = max (val(A), val(B))= val (A) + val (B) (với chú ý: 1 + 1 = 1); 
 val(A & B) = min (val(A), val(B)) = val (A) . val (B); 
 val(¬A) = 1 – val(A); 
 val(A ⊃ B) = val (¬A ∨ B) = max(1 - val(A), val(B)); 
4. Công thức 
2 Không thể kết hợp về bên trái như trong toán học vì nếu như thế biểu thức ¬¬A trở nên vô nghĩa. 
Tương đương Kéo theo 
 4
Ta sẽ dùng thuật ngữ công thức để chỉ một loại biểu thức được xây dựng từ các mệnh 
đề đơn và các phép toán trên mệnh đề. Chính xác hơn: 
(i) Tất cả các mệnh đề đơn p, q, r, p1, p2,  là các công thức. 
(ii) Nếu A là công thức thì (A), ¬A là công thức. 
(iii) Nếu A, B là công thức thì A & B, A ∨ B, A ⊃ B, A ≡ B là các công thức. 
(iv) Ngoài ra không còn công thức nào khác. 
Ví dụ công thức : 
• p 
• p ∨ (q & r) 
• (r & q) ⊃ (((r ∨ s) & ¬ q) ⊃ ¬ s) 
Những biểu thức sau đây không phải là công thức : 
• p &∨ q, 
• ∀p ⊃ q, 
• p & (q ∨ r) ⊃ . 
Mỗi công thức là một hàm của các biến (là các mệnh đề đơn thành phần của công thức 
đó) xác định trên tập các giá trị chân lý {T, F}. Hàm đó cũng nhận giá trị từ tập {T, F}. Mỗi sự 
phân bố các giá trị chân lý của các mệnh đề đơn cấu thành công thức A tương ứng với một giá 
trị chân lý của công thức A đó. Ví dụ, công thức (p ∨ q) & (¬ r) có giá trị tương ứng với các 
phân bố giá trị chân lý của các mệnh đề đơn thành phần của nó như sau : 
p q r p ∨ q ¬ r (p ∨ q) & (¬ r ) 
T 
T 
T 
T 
F 
F 
F 
F 
T 
T 
F 
F 
T 
T 
F 
F 
T 
F 
T 
F 
T 
F 
T 
F 
T 
T 
T 
T 
T 
T 
F 
F 
F 
T 
F 
T 
F 
T 
F 
T 
F 
T 
F 
T 
F 
T 
F 
F 
 Bảng liệt kê giá trị chân lý của công thức cùng với các phân bố giá trị của các mệnh đề 
đơn thành phần của nó như trong ví dụ trên đây gọi là bảng chân lý (hay bảng chân trị) – 
chúng ta sẽ khảo sát ở phần sau - của công thức. 
5. Các cổng logic trong kỹ thuật điện tử 
 5
Trong kỹ thuật điện tử người ta sử dụng các phần tử đặc biệt của mạch điện, gọi là các cổng 
logic. Các cổng logic thông thường là cổng AND, tương ứng với phép toán hội; cổng OR, 
tương ứng với phép tuyển không nghiêm ngặt; cổng XOR, tương ứng với phép tuyển nghiêm 
ngặt; cổng đảo NOT, tương ứng với phép phủ định; cổng NAND, tương ứng với phủ định của 
phép hội; cổng NOR, tương ứng với phủ định của phép tuyển; NXOR, tương ứng với phủ định 
của phép tuyển nghiêm ngặt. 
Cổng AND 
Output = X & Y 
(đầu ra có tín hiệu khi và chỉ khi cả hai đầu 
vào X và Y đều có tín hiệu) 
Cổng OR 
Output = X ∨ Y 
(đầu ra có tín hiệu khi và chỉ khi có ít nhất 
một đầu vào X hoặc Y có tín hiệu) 
Cổng XOR 
Output = X ∨ Y 
(đầu ra có tín hiệu khi và chỉ khi có đúng 
một đầu vào X hoặc Y có tín hiệu) 
Cổng NOT (cổng đảo) 
Output = ¬ X 
(đầu ra chỉ có tín hiệu khi đầu vào không có tín hiệu, 
và ngược lại ) 
 6
Một mạch điện tử thiết kế từ những cổng logic này sẽ tương ứng với một công thức logic, và 
ngược lại, mỗi công thức logic tương ứng với một mạch điện tử thiết kế từ các cổng này. 
Mạch điện tử trên đây tương ứng với công thức : 
Output = ¬(¬(¬(x ∨ y) ∨ ¬(y ∨ z)) ∨ ¬ (z & ¬y)) 
6. Hệ các phép toán đầy đủ 
Cổng NOR 
Output = ¬ (X ∨ Y) 
(đầu ra chỉ có tín hiệu khi không đầu vào nào có tín 
hiệu) 
Cổng NXOR 
Output = ¬ (X ∨ Y) 
(đầu ra chỉ có tín hiệu khi không đầu vào nào có tín 
hiệu hoặc tất cả các đầu vào đều có tín hiệu) 
Cổng NAND 
Output = ¬ (X & Y) 
(đầu ra chỉ không có tín hiệu khi không đầu vào nào 
có tín hiệu, các trường hợp khác đầu ra đều có tín 
hiệu) 
 7
Vì các mệnh đề chỉ có thể nhận một trong hai giá trị chân lý là T và F nên số lượng các 
phép toán hai ngôi (khác nhau) trên mệnh đề có tất cả là 24 = 16. Chúng được biểu diễn trong 
bảng sau:B 
A B 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
T 
T 
F 
F 
T 
F 
T 
F 
T 
F 
F 
F 
T 
T 
F 
F 
T 
T 
T 
F 
T 
F 
T 
T 
T 
F 
F 
T 
F 
T 
T 
T 
F 
F 
T 
T 
F 
F 
F 
T 
F 
F 
T 
F 
T 
F 
T 
F 
F 
T 
F 
T 
T 
T 
F 
T 
F 
T 
T 
F 
F 
T 
F 
F 
T 
T 
T 
T 
F 
F 
F 
F 
Trong bảng trên các phép toán 1, 3, 4, 5 chính là các phép toán &, ∨, ⊃ và ≡ tương ứng. 
Nhận xét: phép kéo theo (⊃) có thể được định nghĩa thông qua các phép phủ định và 
tuyển. Cụ thể là: 
(A ⊃ B) ⇔ (¬A ∨ B) (1) 
Phép toán 14 có thể định nghĩa thông qua phép kéo theo và phủ định: 
Ký hiệu nó bằng “|“, ta có 
 (A |B) ⇔ (¬ (A ⊃ B)) (2) 
và, từ (1), (2) ta thấy “ |” có thể được xác định thông qua phép phủ định và tuyển: 
 (A | B) ⇔ (¬ (¬A ∨ B)) 
Có một câu hỏi rất tự nhiên là với một nhóm phép toán nào thì đủ để định nghĩa tất cả 
các phép toán còn lại trong 16 phép toán nêu trên? Định lý sau đây trả lời cho câu hỏi đó. 
Định lý 1.1. Bất cứ một phép toán nào trong số 16 phép toán nêu trong bảng trên đều có thể 
được cho thông qua các phép toán ¬, & và∨. 
Chứng minh. Ta chứng minh định lý này bằng cách xác định từng phép toán trong số 16 phép 
toán trên qua các phép toán ¬, &, ∨. 
Phép toán 1 chính là phép &, phép toán 3 là phép ∨. Phép kéo theo (4) và phép toán (14) được 
biểu diễn như trên kia đã nói. Phép toán (13) chính là phép tuyển nghiêm ngặt ∨ . Như đã biết, 
 A ∨ B ⇔ (A ∨ B) & ( ¬ A ∨ ¬B) 
 Phép toán (5) chính là phép đồng nhất. Nó được biểu là : 
(A = B) ⇔ (¬A ∨ B) & (¬B ∨ A) 
Phép toán thứ 8, ta ký hiệu nó bằng dấu L, được định nghĩa như sau: 
 (A L B) ⇔ (¬A & ¬B); 
 phép toán 7, ta tạm ký hiệu nó bằng dấu ⎦, có thể định nghĩa như sau: 
 (A ⎦ B) ⇔ ((¬A1 & A2) ∨ (¬A1 & ¬A2)). 
Chúng tôi dành phần còn lại cho bạn đọc, coi như bài tập. 
Nếu cho trước một bảng chân lý thì nó còn cho phép ta xác định công thức có bảng 
chân lý đó. 
 8
Ví dụ: Có bảng chân lý 
A1 A2 A3 D 
T T T F 
T T F T 
T F T F 
T F F T 
F T T T 
F T F F 
F F T F 
F F F F 
Công thức D ở đây là D = (A1 & A2 & ¬A3) ∨ (A1 & ¬A2 & ¬A3) ∨ (¬A1 & A2 & A3). 
Công thức D thu được bằng cách : Trong bảng chân trị của D chỉ sử dụng các dòng mà D có 
giá trị đúng (T). Tại các dòng đó, nếu biến có giá trị T thì lấy nguyên biến, nếu có giá trị F thì 
ấy phủ định của biến. Mỗi dòng đúng của bảng chân trị được biểu thị bằng một công thức, là 
hội của các biến hoặc phủ định biến chọn theo cách vừa trình bày. Các công thức tương ứng 
với dòng đúng được liên kết với nhau bằng dấu toán tuyển, kết quả là D. 
Nhóm phép toán đủ để định nghĩa tất cả các phép toán khác được gọi là hệ các phép 
toán đầy đủ. Như ta thấy, định lý 1 khẳng định rằng (¬, &, ∨) là một hệ các phép toán đầy đủ. 
Các cặp phép toán (⊃, ¬); ( ¬, ∨) cũng là các hệ phép toán đầy đủ. 
II. Quy luật và mâu thuẫn logic 
1. Khái niệm quy luật và mâu thuẫn logic 
Trong logic hai giá trị mà ta đang nghiên cứu thì một mệnh đề hoặc là đúng, hoặc là sai. 
Nếu mệnh đề phù hợp với thực tiễn thì nó đúng, nếu nó không phù hợp với thực tiễn thì nó sai. 
Nói chung, để xác định xem một mệnh đề có đúng hay không ta phải đối chiếu với thực tiễn. 
Thế nhưng có một số trường hợp không cần đối chiếu trực tiếp với hiện thực khách quan ta 
cũng có thể biết được mệnh đề là đúng hay sai. Ví dụ, ở một thời điểm nhất định thì mệnh đề 
trời mưa hoặc không mưa là mệnh đề đúng. Ta biết điều đó mà không cần phải xét xem trời 
mưa hay không mưa ở thời điểm đó. Nguyên nhân ở đây là mệnh đề đã nêu đúng trong cả hai 
trường hợp trời mưa và trời không mưa ở thời điểm đó. Mà ngoài hai trường hợp đó ra thì 
không còn trường hợp nào. Như vậy mệnh đề này đúng trong mọi trường hợp. Những mệnh đề 
đúng trong mọi trường hợp như vậy ta gọi là mệnh đề hằng đúng, hay quy luật logic 
(tautology). Trái lại, ở thời điểm bất kỳ, mệnh đề trời mưa và không mưa sai. Nó sai trong 
trường hợp trên thực tế trời đang mưa, và sai cả trong trường hợp trên thực tế trời không mưa. 
Mà ngoài hai trường hợp đó ra thì không còn trường hợp nào khác. Nghĩa là mệnh đề này sai 
 9
trong mọi trường hợp. Những mệnh đề sai trong mọi trường hợp như vậy gọi là mệnh đề hằng 
sai, hay mâu thuẫn logic. 
Các khái niệm quy luật và mâu thuẫn logic vừa nêu có ý nghĩa rất quan trọng. Trong 
logic mệnh đề, một suy luận đúng và chỉ đúng khi công thức biểu thị nó là quy luật logic, và nó 
không thể nào đúng được khi công thức biểu thị nó là một mâu thuẫn logic. Quy luật logic 
cũng chính là các định lý trong các hệ tiên đề và hệ suy luận tự nhiên của logic mệnh đề mà ta 
sẽ nghiên cứu ở những phần sau. 
2. Các phương pháp xác định quy luật và mâu thuẫn logic 
a) Lập bảng chân lý 
Theo định nghĩa ơ mục trên, mệnh đề là quy luật logic nếu nó đúng trong mọi trường 
hợp. Để ý rằng mỗi trường hợp tương ứng với một phân bố giá trị chân lý của các mệnh đề 
đơn. Thật vậy, chẳng hạn, với trường hợp “trời mưa” thì các mệnh đề đơn trời mưa, đường ướt 
có giá trị đúng; trong khi đó các mệnh đề trời nắng, có giá trị sai. Nói cách khác, trường 
hợp “trời mưa” ứng với phân bố giá trị “đúng”, “đúng”, “sai”,  cho các mệnh đề đơn trời 
mưa, đường ướt, trời nắng  tương ứng. Như vậy mệnh đề là quy luật logic khi và chỉ khi tại 
tất cả các dòng trong bảng chân lý của công thức của nó đều có giá trị T (đúng). Tương tự như 
thế, mệnh đề là mâu thuẫn logic khi và chỉ khi tất cả các dòng trong bảng chân lý của công 
 ... iả 
định mà công thức đó phụ thuộc vào trong suy luận. Như vậy, mỗi bước trong suy diễn được 
viết dưới dạng A[ Γ ] (đọc là: công thức A có đặc điểm phụ thuộc Γ). 
Để ý rằng, chuỗi suy diễn trong hệ suy luận tự nhiên bao giờ cũng bắt đầu bằng giả thiết hay 
giả định. Sau đây là một số hệ logic với đặc điểm phụ thuộc do giáo sư Voisvillo e. K xây 
dựng. 
Hệ K1: Đặc điểm phụ thuộc (của công thức A nào đó trong chuỗi suy diễn vào các giả định và 
giả thiết) là một tập hợp các giả định, giả thiết (có thể là tập rỗng). Khái niệm công thức phụ 
thuộc vào giả định trong chuỗi suy diễn được định nghĩa quy nạp: 
a) Giả định (giả thiết) A phụ thuộc vào chính nó (và nghĩa là đặc điểm phụ thuộc của nó là 
tập hợp {A}); 
b) Sự phụ thuộc của các công thức khác được xác định theo các quy tắc suy luận. 
4 Voisvillo E. K. Các khía cạnh triết học – phương pháp luận của logic relevant. Moskva 1988. (Tiếng nga) 
9
9
Trong các quy tắc sau đây ta ký hiệu A, B, C, D là công thức bất kỳ; Γ, Δ là tập các công thức 
(có thể rỗng). Dấu phẩy giữa các tập hợp có nghĩa là dấu hội; “Γ \ Δ” có nghĩa là kết quả việc 
loại bỏ các thành phần thuộc Δ ra khỏi Γ : 
∧i : ],)[(
][],[
ΔΓ∧
ΔΓ
BA
BA ∧e : ( ][
])[(
Γ
Γ∧
A
BA ; 
][
])[(
Γ
Γ∧
B
BA ; 
∨i : ])[(
][
Γ∨
Γ
BA
A ; 
])[(
][
Γ∨
Γ
BA
B ; ∨e: ],,[
],[],,[
BAC
BCAC
∨ΔΓ
ΔΓ 
Trong đó A ∨ B là giả định có trước khi sử dụng quy tắc này trong chuỗi suy diễn. 
⊃i : }]{\)[(
][
ABA
B
Γ⊃
Γ với A là giả định bất kỳ trong chuỗi suy diễn. 
⊃e : ],[
][],)[(
ΔΓ
ΔΓ⊃
B
ABA ; ¬e: ][
][
Γ
⪪
A
A 
¬e : }]{\,[
][],[
AA
BB
ΔΓ¬
ΔΓ¬ với A là giả định bất kỳ trong chuỗi suy diễn. 
Chuỗi suy diễn là dãy các công thức (với đặc điểm phụ thuộc), trong đó mỗi công thức hoặc là 
một giả định, một giả thiết, hoặc là nhận được từ các công thức trước nó bằng cách sử dụng 
các quy tắc của hệ. Công thức cuối cùng được goị là kết luận. Nếu kết luận là công thức A [ Γ] 
thì : 
 Nếu Γ ≠ ∅, Γ = {B1, B2, , Bn}, ta nói A là hệ quả của các công thức B1, B2, , Bn. 
Viết Γ A. 
Nếu Γ = ∅ thì A là định lý, chuỗi suy diễn được gọi là phép chứng minh của công thức A. 
Trong hệ này các giả định có thể được sử dụng bao nhiêu lần cũng được, và chúng không bị 
loại bỏ khỏi suy luận. 
Ta nhận thấy rằng các quy tắc ∧i , ⊃i và ¬e không đảm bảo tính liên hệ về nội dung giữa tiền 
đề và kết luận. Thật vậy: 
Với ∧i , để ý rằng nếu trong chuỗi suy diễn, công thức giả định A không hề được sử 
dụng, thì kết luận của suy luận không phụ thuộc vào A. Thế nhưng bao giờ ta cũng có thể làm 
cho kết luận phụ thuộc vào một công thức bất kỳ, bằng cách sử dụng quy tắc ∧i, ∧e. Như thế 
mặc dầu không cần đến giả định A khi ta rút ra B, nhưng vẫn có thể coi là B phụ thuộc vào A. 
10
10
 Với ⊃i , nếu A ∉ Γ thì trong tiền đề B không phụ thuộc vào A, có nghĩa là B không 
được rút ra nhờ có A; còn ở kết luận Γ \ {A} = Γ, nhưng lại có B ⊃ A [Γ \ {A}}, hay A ⊃ B 
[Γ] và có nghĩa là B là hệ qủa của A trong điều kiện có Γ. Nghịch lý ở đây thể hiện khá rõ 
ràng. 
 Tương tự với ¬e. Nếu A ∉ Γ và A ∉ Δ thì B[Γ], ¬B[Δ] cho biết A không phải là 
một trong số các nguyên nhân làm xuất hiện mâu thuẫn B và ¬B. Thế nhưng từ đó quy tắc 
này lại cho phép rút ra ¬A [ Γ, Δ \ {A}], cứ như A là một trong những nguyên nhân gây ra 
mâu thuẫn B và ¬B vậy. Nghịch lý đã rõ ràng. 
2. Hệ suy luận tự nhiên relevant 
Để chuyển sang relevant logic, ta xét hệ K2 (tương đương K1), trong đó những vi phạm nguyên 
lý relevant (nguyên lý đảm bảo sự liên hệ về nội dung giữa tiền đề và kết luận) được gom về 
trong một quy tắc duy nhất. 
Hệ K2: Đặc điểm phụ thuộc bây giờ được hiểu là dãy các giả định (giả thiết); Γ, Δ là dãy bất 
kỳ của các giả định (công thức), và cũng có thể là dãy trống. 
Quy tắc: 
∧i : ])[(
][],[
Γ∧
ΓΓ
BA
BA ∧e : ( ][
])[(
Γ
Γ∧
A
BA ; 
][
])[(
Γ
Γ∧
B
BA ; 
∨i : ])[(
][
Γ∨
Γ
BA
A ; 
])[(
][
Γ∨
Γ
BA
B ; ∨e: ],[
],[],,[
BAC
BCAC
∨Γ
ΓΓ 
⊃i : ])[(
],[
Γ⊃
Γ
BA
AB ⊃e : ],[
][],)[(
ΔΓ
ΔΓ⊃
B
ABA 
¬e : 
],,[
],[],,[
*CA
CBAB
ΔΓ¬
ΔΓ¬ ¬e: ][
][
Γ
⪪
A
A 
trong đó *C là C nếu như C không trùng với A, và *C là dãy trống trong trường hợp ngược 
lại. 
],[
][
Γ
Γ
BA
A Quy tắc đơn điệu, với B là giả định bất kỳ trong chuỗi 
suy diễn. 
11
11
],,[
],,,[
ΔΓ
ΔΓ
BA
BBA Rút gọn đặc điểm phụ thuộc 
],,,[
],,,[
ΔΓ
ΔΓ
BCA
CBA Hoán vị đặc điểm phụ thuộc 
Các khái niệm chuỗi suy diễn và phép chứng minh định nghĩa như cũ. 
Nếu có chuỗi suy diễn với kết luận A [ Γ ] thì ta nói rằng A suy ra được từ tập Δ bất kỳ chứa 
tất cả các phần tử của dãy Γ. 
Bây giờ nếu ta thay khái niệm trên đây thành: Nếu có chuỗi suy diễn với kết luận A[Γ ] thì ta 
nói rằng A suy ra được từ tập công thức Δ, với Δ chứa tất cả các phần tử của Γ và Γ không 
rỗng (nghĩa là Γ chứa ít nhất một phần tử). 
Trong hệ thống này quy tắc duy hất không đảm bảo tính liên hệ về nội dung giữa tiền đề và kết 
luận (tính relevant) là quy tắc đơn điệu. Như vậy, loại bỏ quy tắc này, ta sẽ tránh được các 
nghịch lý. Hệ logic relevant thu được từ hệ K2 sau khi loại bỏ quy tắc đơn điệu được gọi là hệ 
RAO5. 
 Thay đổi chút ít hệ K2 ta được một trong những hệ logic relevant quan trọng nhất là hệ 
R6: Loại bỏ khỏi K2 quy tắc gây nghịch lý là quy tắc đơn điệu và thêm vào quy tắc phân phối 
của phép hội đối với phép tuyển 
]))[()((
]))[((
Γ∧∨∧
Γ∨∧
CABA
CBA 
Hệ En (tương đương với một hệ logic relevant nổi tiếng khác là hệ E) nhận được từ hệ trên 
bằng cách thay quy tắc hoán vị trong đặc điểm phụ thuộc bằng quy tắc hạn chế hoán vị trong 
đặc điểm phụ thuộc như sau: 
],),(,[
]),(,,[
Δ⊃Γ
Δ⊃Γ
BDCA
DCBA 
Chúng tôi cho rằng cơ sở lý luận thật sự của lập trình logic chính là logic relevant. Bởi vậy, 
việc nghiên cứu logic relevant lại càng có ý nghĩa. 
5 Giáo sư tiến sĩ Smirnov V.A. là người đưa ra thuật ngữ này, và ông cũng là người đầu tiên nghiên cứu hệ RAO. 
6 Chính xác hơn là ta được hệ suy luận tự nhiên tương đương với hệ R. 
BẢNG ĐỊNH NGHĨA CÁC PHÉP TOÁN LOGIC 
MỘT SỐ HẰNG ĐẲNG THỨC TRONG LOGIC MỆNH ĐỀ 
1. A + A = A; Luật đồng nhất, luật nuốt 
2. A . A = A; Luật đồng nhất, luật nuốt 
3. A + B = B + A Tính chất giao hoán của phép cộng 
4. A + (B + C) = (A+ B) + C Tính chất kết hợp của phép cộng 
5. A . B = B . A Tính chất giao hoán của phép nhân 
6. A . (B . C) = (A . B) . C Tính chất kết hợp của phép nhân 
7. A . (B + C) = A.B + A.C Tính phân phối của phép cộng đối với phép nhân 
8. A + (B . C) = (A + B) . (A + C ) Tính phân phối của phép nhân đối với phép cộng 
9. A + A = 1 ; Định nghĩa 1 
10. A . A = 0 ; Định nghĩa 0 
11. A = A Luật hoàn nguyên 
12. BA + = A . B Luật De Moorgan 
13. BA. = A + B Luật De Moorgan 
14. A.(A + B) = A Luật giản lược 
15. A + (A.B) = A Luật giản lược 
 A ¬A 
 T F 
 F T 
A B A & B A B A ∨ B 
T 
T 
F 
F 
 T 
 F 
 T 
 F 
 T 
 F 
 F 
 F 
 T 
 T 
 F 
 F 
 T 
 F 
 T 
 F 
 T 
 T 
 T 
 F 
A B A ⊃ B A B A ≡ B A B A ∨ B 
T 
T 
F 
F 
T 
F 
T 
F 
T 
F 
T 
T 
 T 
T 
F 
F 
T 
F 
T 
F 
T 
F 
F 
T 
 T 
 T 
 F 
 F 
 T 
 F 
 T 
 F 
 F 
 T 
 T 
 F 
Tuyển nghiêm ngặt Tương đương Kéo theo 
Tuyển không nghiêm ngặt Hội Phủ định 
CÁC KÝ HIỆU 
Ký hiệu Tên gọi Ví dụ sử dụng 
¬ Phủ định ¬ A 
& Hội A & B 
∨ Tuyển không nghiêm ngặt A ∨ B 
∨ Tuyển nghiêm ngặt A ∨ B 
⊃ Kéo theo A ⊃ B 
≡ Tương đương A ≡ B 
→ Kéo theo relevant, rút ra kết quả A → B; {p ∨ q, ¬ p ∨ r}→ q 
 Phủ định (trong đại số Boole) A 
. Hội (trong đại số Boole) A.B 
+ Tuyển (trong đại số Boole) A + B 
∀ Lượng từ toàn thể ∀xA(x) 
∃ Lượng từ tồn tại ∃xA(x) 
← , / Thế bằng x ← t, x/t 
term Hạn từ a là một term 
WFF Công thức A ∨ B là một WFF 
mgu Đồng nhất thể lớn nhất mgu(A,B) 
inf Thông tin Inf(A) 
U Toàn bộ thông tin inf(A) ≠ U 
T Đúng T(A→B)/α 
F Sai F(A→B)/α 
⊆ Là tập hợp con của hoặc bằng MA ⊆ MB 
∈ Thuộc về pi ∈ α 
∉ Không thuộc về pi ∉ α 
∅ Tập hợp rỗng MA ≠ ∅ 
|= Là quy luật logic, hệ quả |= A; Γ, A |= B 
|− Được chứng minh, định lý, rút ra |− A; Γ, A |− B 
⇔ Nghĩa là, tương đương với Inf(A) ⊆ inf (B) ⇔ MA ⊆ MB 
Fail Thất bại (trong hợp giải) fail
srqqp ¬∨∨∨ , 
 Resolvent rỗng ¬ p , p 
  
CÁC TIÊN ĐỀ VÀ QUY TẮC LOGIC MỆNH ĐỀ 
(1) Cho A, B, C là các công thức bất kỳ của hệ S . Khi đó các công thức sau đây là tiên 
đề của hệ S : 
(A1) (A ⊃ (B ⊃ A)); 
(A2) ((A ⊃ (B ⊃ C)) ⊃ ((A ⊃B) ⊃ (A ⊃ C)); 
(A3) (¬ B ⊃ ¬ A) ⊃ ((¬ B ⊃ A) ⊃ B)) 
(2) Quy tắc suy diễn duy nhất của S là Modus Ponens: 
B
ABAMP ,⊃ 
CÁC QUY TẮC CỦA HỆ SUY LUẬN TỰ NHIÊN TRONG LOGIC 
MỆNH ĐỀ 
Quy tắc nhập & (ký hiệu &i) BA
BA
&
, 
Quy tắc khử & (ký hiệu &e) A
BA & ; 
B
BA & 
Quy tắc nhập ∨ (ký hiệu ∨i) BA
A
∨ ; BA
B
∨ 
Quy tắc khử ∨ (ký hiệu ∨e) B
ABA ¬∨ , ; 
A
BBA ¬∨ , 
Quy tắc nhập ¬ (ký hiệu ¬i) A
BB
¬
¬, (*) 
Quy tắc khử ¬ (ký hiệu ¬e) A
A¬¬ 
Quy tắc nhập ⊃ (ký hiệu ⊃i) BA
B
⊃ (*) 
Quy tắc khử ⊃ (ký hiệu ⊃e) B
ABA ,⊃ 
CÁC TIÊN ĐỀ VÀ QUY TẮC LOGIC VỊ TỪ 
Các tiên đề 
Với mọi công thức A, B, C, và biến x bất kỳ, các biểu thức A1, A2, A3 sau đây là tiên đề 
của logic vị từ: 
A1. A ⊃ (B ⊃ A); 
A2. (A ⊃ (B ⊃ C)) ⊃ ((A ⊃ B) ⊃ (A ⊃ C)); 
A3. (¬A ⊃ ¬ B) ⊃ ((¬A ⊃ B) ⊃ A); 
A4. ∀x A(x) ⊃ A(t), với A(x) là công thức, t là hạn từ, tự do đối với x trong công 
thức A(x). 
A5. ∀x (A ⊃ B) ⊃ (A ⊃ ∀x B), nếu trong công thức A không có xuất hiện tự do của x. 
Các quy tắc 
1) 
B
ABAMP ,⊃ (Modus ponens) 
2) 
xA
AGen ∀ (Quy tắc tổng quát hóa) 
CÁC QUY TẮC CỦA HỆ SUY LUẬN TỰ NHIÊN LOGIC VỊ TỪ 
Các quy tắc của hệ suy luận tự nhiên logic mệnh đề 
Quy tắc nhập ∀ ( ký hiệu ∀i) )(
)(
xxA
xA
∀ x không xuất hiện tự do trong các 
giả thiết và giả định trước A(x) trong 
chuỗi suy diễn. 
Quy tắc khử ∀( ký hiệu ∀e) )(
)(
tA
xxA∀ t tự do đối với x trong A(x) 
Quy tắc nhập ∃ ( ký hiệu ∃i): )(
)(
xxA
tA
∃ t tự do đối với x trong A(x) 
Quy tắc khử ∃ (ký hiệu ∃e) )(
)(
cA
xxA∃ c là hằng đối tượng mới 
QUY TẮC HỆ SUY LUẬN TỰ NHIÊN LOGIC RELEVANT (HỆ K2) 
Đặc điểm phụ thuộc được hiểu là dãy các giả định (giả thiết), ghi trong cặp dấu ngoặc 
vuông; Γ, Δ là dãy bất kỳ của các giả định (công thức), và cũng có thể là dãy trống. 
∧i : ])[(
][],[
Γ∧
ΓΓ
BA
BA ∧e : ( ][
])[(
Γ
Γ∧
A
BA ; 
][
])[(
Γ
Γ∧
B
BA ; 
∨i : ])[(
][
Γ∨
Γ
BA
A ; 
])[(
][
Γ∨
Γ
BA
B ; ∨e: ],[
],[],,[
BAC
BCAC
∨Γ
ΓΓ 
⊃i : ])[(
],[
Γ⊃
Γ
BA
AB ⊃e : ],[
][],)[(
ΔΓ
ΔΓ⊃
B
ABA 
¬e : 
],,[
],[],,[
*CA
CBAB
ΔΓ¬
ΔΓ¬ ¬e: ][
][
Γ
⪪
A
A 
trong đó *C là C nếu như C không trùng với A, và *C là dãy trống trong trường hợp 
ngược lại. 
],[
][
Γ
Γ
BA
A Quy tắc đơn điệu, với B là giả định bất kỳ trong 
chuỗi suy diễn. 
],,[
],,,[
ΔΓ
ΔΓ
BA
BBA Rút gọn đặc điểm phụ thuộc 
],,,[
],,,[
ΔΓ
ΔΓ
BCA
CBA Hoán vị đặc điểm phụ thuộc 
MỤC LỤC 
LỜI NÓI ĐẦU 
CÁC KÝ HIỆU 
BẢNG ĐỊNH NGHĨA CÁC PHÉP TOÁN LOGIC 
MỘT SỐ HẰNG ĐẲNG THỨC TRONG LOGIC MỆNH ĐỀ 
CÁC TIÊN ĐỀ VÀ QUY TẮC LOGIC MỆNH ĐỀ 
CÁC QUY TẮC CỦA HỆ SUY LUẬN TỰ NHIÊN TRONG LOGIC MỆNH ĐỀ 
CÁC TIÊN ĐỀ VÀ QUY TẮC LOGIC VỊ TỪ 
CÁC QUY TẮC CỦA HỆ SUY LUẬN TỰ NHIÊN TRONG LOGIC VỊ TỪ 
QUY TẮC HỢP GIẢI 
QUY TẮC HỆ SUY LUẬN TỰ NHIÊN LOGIC RELEVANT (HỆ K2) 
Chương I LOGIC MỆNH ĐỀ 
I. Mệnh đề. Các phép toán trên mệnh đề 
1. Mệnh đề 
2. Các phép toán logic trên mệnh đề 
3. Định nghĩa các phép toán logic bằng phương pháp giải tích 
4. Công thức 
5. Các cổng logic trong kỹ thuật điện tử 
6. Hệ các phép toán đầy đủ 
II. Quy luật và mâu thuẫn logic 
1. Khái niệm quy luật và mâu thuẫn logic 
2. Các phương pháp xác định quy luật và mâu thuẫn logic 
III. Biến đổi tương đương 
1. Các ký hiệu và hằng đẳng thức 
2. Các ví dụ 
IV. Hệ tiên đề của logic mệnh đề 
1. Lý thuyết hình thức hóa (lý thuyết tiên đề hóa) 
2. Lý thuyết S (Hệ tiên đề S) 
3. Các hệ tiên đề khác của logic mệnh đề 
V. Hệ suy luận tự nhiên của logic mệnh đề 
1. Các quy tắc 
2. Chuỗi suy diễn và phép chứng minh 
3. Tính không mâu thuẫn và đầy đủ của các hệ S và NS 
Chương II HỢP GIẢI TRONG LOGIC MỆNH ĐỀ 
I. Công thức dạng tuyển 
1. Định nghĩa 
2. Quy trình INDO 
II. Quy tắc hợp giải 
III. Phương pháp hợp giải 
IV. Cây hợp giải. Hợp giải tuyến tính 
V. Giản lược tiền đề 
1. Giản lược tiền đề là quy luật logic 
2. Giản lược tiền đề một chiều 
3. Giản lược tiền đề yếu 
Chương 3 LOGIC VỊ TỪ 
I. Ngôn ngữ logic vị từ 
1. Phân tích ngôn ngữ tự nhiên 
2. Hệ ký tự 
3. Hạn từ (term) 
4. Công thức (WFF – Well Formed Formula) 
5. Các ví dụ 
6. Biểu thị tư tưởng bằng ngôn ngữ logic vị từ 
7. Biến tự do và biến buộc 
II. Diễn giải (Interpretation). Mô hình (Model) 
1. Diễn giải 
2. Giá trị chân lý của công thức trong diễn giải 
3. Mô hình (model). Quy luật logic 
III. Diễn giải Herbrand 
1. Miền herbrand 
2. Định nghĩa diễn giải herbrand và ví dụ 
3. Mô hình herbrand 
IV. Hệ tiên đề của logic vị từ 
1. Các tiên đề và quy tắc 
2. Chuỗi suy diễn, phép chứng minh 
3. Các tính chất cơ bản của hệ tiên đề logic vị từ 
V. Hệ suy luận tự nhiên của logic vị từ 
1. Các quy tắc 
2. Chuỗi suy diễn, phép chứng minh 
3. Một số ví dụ 
4. Tính không mâu thuẫn và đầy đủ của hệ suy luận tự nhiên 
Chương 4 HỢP GIẢI TRONG LOGIC VỊ TỪ 
I. Công thức dạng tuyển 
1. Định nghĩa 
2. Quy trình INSEADOR 
II. Phép thế 
1. Định nghĩa 
2. Áp dụng phép thế 
3. Tính bất biến của phép thế 
4. Phép thế hợp 
5. Quan hệ sắp xếp 
III. Đồng nhất thể 
1. Định nghĩa 
2. Đồng nhất thể lớn nhất 
IV. Quy tắc hợp giải 
V. Suy diễn hợp giải (chuỗi hợp giải) và phép chứng minh 
VI. Áp dụng 
1. Xác định tính mâu thuẫn của một tập công thức 
2. Trả lời câu hỏi đúng, sai 
3. Tìm kiếm câu trả lời 
VII. Giản lược tiền đề 
1. Giản lược tiền đề là quy luật logic 
2. Giản lược tiền đề một chiều 
3. Giản lược tiền đề yếu 
Chương 5 RELEVANT LOGIC 
I Dẫn nhập 
II. Nghịch lý của suy diễn logic và phép toán kéo theo 
1. Các nghịch lý 
2. Các cố gắng giải quyết nghịch lý 
III. Suy diễn logic – một quan hệ về nội dung, hay là về thông tin giữa 
các mệnh đề 
1. Các đặc điểm của quan hệ suy diễn logic 
2. Thông tin của mệnh đề. Nội dung logic là thông tin 
3. Nguyên nhân của nghịch lý suy diễn logic (cổ điển) 
IV Quan hệ suy diễn logic relevant 
V Xác định về mặt hình thức nguyên nhân nghịch lý của khái niệm 
kéo theo logic cổ điển. Hệ logic tự nhiên relevant 
1. Nguyên nhân nghịch lý của khái niệm kéo theo logic cổ điển về mặt 
hình thức 
2. Hệ suy luận tự nhiên relevant 
BÀI TẬP 
DANH MỤC TÀI LIỆU THAM KHẢO 
TÀI LIỆU THAM KHẢO 
1. Nguyễn Đức Dân. Logic và Tiếng Việt, NXB Giáo dục, Hà Nội 1996 
2. Nguyễn Đức Đồng, Nguyễn Văn Vĩnh. Logic toán, NXB Thanh Hóa 
3. Phạm Đình Nghiệm. Cơ sở phương pháp luận của lập trình logic, Luận án Phó tiến 
sĩ triết học, Moskva 1991 (Tiếng Nga). 
4. E. Mendencon. Nhập môn logic toán, NXB Khoa học, (Tiếng Nga). 
5. M. Genesereth. Computational logic .  
6. E.K. Voisvillo. Khía cạnh triết lý-nhận thức luận của logic relevant, Moskva 1988 
(Tiếng Nga). 
7. A.N. Kongomorov, A.G. Dragalin. Nhập môn logic toán, NXB Đại học Tổng hợp 
Moskva, 1982 (Tiếng Nga). 
8. Huge. Introduction to logic 
9. P. Tidman, H. Kanane. Logic and Philosophy. A modern introduction, Wadsworth 
Publishing Company.