Bài giảng Logic Toán - Nguyên Lý kế toán | Trường Đại học Quy Nhơn

BÀI GIẢNG TOÁN LOGIC
HỒ ANH MINH – LÊ THỊ KIM NGA
KHOA CNTT – TRƯỜNG ĐH QUY NHƠN 1
Chương 1. Mệnh đề và các phép toán logic 1.1. Mệnh đề.
Mệnh đề là khái niệm không định nghĩa (gọi là khái niệm nguyên thủy), có thể mô tả
mệnh đề như là một phát biểu mà có thể khẳng định được tính đúng hoặc sai một cách khách quan.
Khi nói tới mệnh đề là ta quan tâm tới những phát biểu chỉ có thể có một trong hai
khả năng là đúng hoặc sai. Như vậy mệnh đề là một khẳng định hoặc đúng hoặc sai
nhưng không thể vừa đúng vừa sai. - Ví dụ mệnh đề
 Mỗi số nguyên chẵn lớn hơn 2 là tổng của hai số nguyên tố (giả thuyết Goldbach).
Cho đến nay vẫn chưa biết đây là mệnh đề đúng hay sai. Giả thuyết này đã được
kiểm tra là đúng đối với các số nguyên chẵn nhỏ hơn 4.1014
 10 > 25. Đây là mệnh đề sai.
 Bội số chung nhỏ nhất của 4 và 6 là 12. Đây là mệnh đề đúng.
- Ví dụ không là mệnh đề
Anh đã học môn Logic chưa? Đẹp quá! Cô ấy hát rất hay.
 Tại sao chúng ta nghiên cứu logic?
Ngày nay, logic mệnh đề được ứng dụng nhiều trong các lĩnh vực khác nhau, chẳng hạn như:
- Suy luận giải quyết tình huống - Toán học
- Viết chương trình máy tính (logic in programming)
Do dó, hiểu biết các qui tắc để sử dụng logic là rất hữu ích. Sau đây là một vài ví dụ
để chỉ ra các ứng dụng đó.
Ví dụ 1: Logic trong lập trình (Logic in programming)
Ðặt vấn đề: Bạn muốn đặt điều kiện là: nếu 0Cách giải quyết: Bạn có thể viết câu lệnh như sau if ( x>0 AND x < = 10 ) x++; 2
Khi điều kiện là: nếu 0Ví dụ 2: Logic trong suy luận đời thường
Ðặt vấn đề: Giả sử giáo viên biết rằng xảy ra 3 điều sau đây:
 Nếu A không mắc lỗi thì B và C đều không mắc lỗi
 Trong 2 người B và C nhất định phải có người mắc lỗi  A không mắc lỗi h oặc B có mắc lỗi.
Giáo viên cần tìm xem ai là người có mắc lỗi.
Ví dụ 3: Logic trong toán học
Ðặt vấn đề: Tìm số tự nhiên a biết rằng trong 3 mệnh đề dưới dây có 2 mệnh đề là
đúng và 1 mệnh đề là sai.
1/ a + 51 là số chính phương
2/ Chữ số tận cùng của a là 1
3/ a - 38 là số chính phương
Cách giải quyết: Trước hết, chúng ta sẽ phải xác định xem 2 mệnh đề đúng và 1
mệnh đề sai là mệnh đề nào? Sau đó từ 2 mệnh đề đúng dể tìm ra số tự nhiên a. Số
chính phương là số nguyên dương khi lấy căn bậc hai. Do đó, số chính phương có các
chữ số tận cùng là 0, 1, 4, 5, 6, 9.
- Nhận thấy giữa mệnh đề 1 và 2 có mâu thuẫn. Bởi vì, giả sử 2 mệnh đề này đồng
thời là đúng thì a+51 có chữ số tận cùng là 2 nên không thể là số chính phương. Vậy
trong 2 mệnh đề này phải có một mệnh đề là đúng và một mệnh đề là sai.
- Tương tự, nhận thấy giữa mệnh đề 2 và 3 cũng có mâu thuẫn. Bởi vì, giả sử hai
mệnh đề này đồng thời là đúng thì a-38 có chữ số tận cùng là 3 nên không thể là số
chính phương. Vậy trong 3 mệnh đề trên thì mệnh đề 1 và 3 là đúng, còn mệnh đề 2 là sai.
Từ đó tính được a = 1974.
Tính đúng hoặc sai của mệnh đề được gọi là giá trị chân lý của mệnh đề. Ta thường
dùng ký hiệu 1 để chỉ giá trị đúng, 0 để chỉ giá trị sai .
Logic hình thức không quan tâm tới nội dung của mệnh đề mà chỉ quan tâm tới giá trị 3
chân lý của mệnh đề 1.2.
Bảng giá trị chân lý (bảng chân trị).
Bảng chân trị của một mệnh đề liệt kê tất cả các trường hợp đúng hoặc sai có thể xảy
ra với mệnh đề. Khi xét một mệnh đề được tạo nên từ những mệnh đề khác, bảng
chân trị cho ta biết tính đúng sai của mệnh đề đang xét dựa vào tính đúng sai của các mệnh đề cấu thành. 1.3.
Các phép toán logic.
Từ một tập hợp các mệnh đề ban đầu ta có thể tạo ra các mệnh đề mới (gọi là các
mệnh đề phức) nhờ các liên từ (như “và”, “hoặc”, “nếu… thì”,…) hay còn gọi là các phép toán logic.
Giả sử p, q là hai mệnh đề cho trước. Ta nói mệnh đề có giá trị chân lý đúng là mệnh
đề đúng và nói mệnh đề có giá trị chân lý sai là mệnh đề sai.
1.3.1. Phép Phủ định
Phủ định của mệnh đề p là mệnh đề (ký hiệu là p, đọc là “không p”) có giá trị chân
lý đúng nếu p là mệnh đề sai và là mệnh đề sai nếu p là mệnh đề đúng. Phép Phủ định là phép toán 1 ngôi. Bảng chân trị: p p T F F T
Lưu ý: Vì ta chỉ quan tâm tới giá trị chân lý của mệnh đề nên với một mệnh đề p cho
trước có nhiều mệnh đề là phủ định của p. Tuy nhiên trong thực tế (ngôn ngữ tự nhiên
sử dụng hàng ngày) thường ta lấy phủ định của p là mệnh đề có liên quan về mặt ý nghĩa với p.
Ví dụ: p = “30 chia hết cho 5”, q = “30 không chia hết cho 5”,
r = “30 chia hết cho 7”, s = “100 là số nguyên tố”.
Cả q, r, s đều là các mệnh đề phủ định của p vì đều sai trong khi p đúng. Tuy nhiên
trong thực tế ta thường lấy q làm phủ định của p vì có liên quan chặt chẽ với p về mặt 4 ý nghĩa.
1.3.2. Phép Hội
Hội của hai mệnh đề p và q là mệnh đề (ký hiệu pq, đọc là “p hội q” hoặc “p và q”)
có giá trị chân lý đúng nếu cả hai mệnh đề p và q đều là mệnh đề đúng và có giá trị
chân lý sai nếu ngược lại. Bảng chân trị: p q pq T T T T F F F T F F F F
Ví dụ: p = “30 chia hết cho 5”, q = “3 > 7”, r = pq là mệnh đề sai.
1.3.3. Phép Tuyển
Tuyển của hai mệnh đề p và q là mệnh đề (ký hiệu pq, đọc là “p tuyển q” hay “p
hoặc q”) có giá trị chân lý sai nếu cả hai mệnh đề p và q đều là mệnh đề sai và có giá
trị chân lý đúng nếu ngược lại. Bảng chân trị: p q pq T T T T F T F T T F F F
Ví dụ: p = “30 chia hết cho 5”, q = “3 > 7”, r = pq là mệnh đề đúng.
1.3.4. Phép Kéo theo
Mệnh đề kéo theo của p và q (ký hiệu p  q, đọc là “p kéo theo q” hay “nếu p thì q”)
là mệnh đề sai nếu p đúng đồng thời q sai và là mệnh đề đúng nếu ngược lại. Trong
mệnh đề kéo theo này p được gọi là giả thiết và q được gọi là kết luận. 5 Bảng chân trị: p q p  q T T T T F F F T T F F T
Ví dụ: p = “30 chia hết cho 5”, q = “3 > 7”, r = p  q là mệnh đề sai,
nhưng s = q  p lại là mệnh đề đúng.
1.3.5. Phép Tương đương
Mệnh đề tương đương của p và q (ký hiệu p  q, đọc là “p tương đương q”) là mệnh
đề đúng nếu p và q cùng là các mệnh đề đúng hoặc cùng là các mệnh đề sai và là
mệnh đề sai nếu p và q có giá trị chân lý khác nhau. Bảng chân trị: p q p  q T T T T F F F T F F F T
Ví dụ: p = “30 chia hết cho 5”, q = “3 > 7”, r = p  q là mệnh đề sai
1.3.6. Phép Hoặc loại trừ
Hoặc loại trừ của p và q (viết p XOR q hoặc pq, đọc “p hoặc loại trừ q”) là một
mệnh đề đúng nếu p và q có giá trị chân lý khác nhau và là mệnh đề sai nếu p và q có
giá trị chân lý giống nhau.
Nói cách khác p XOR q chính là mệnh đề phủ định của p  q. Bảng chân trị: p q P XOR q 6 T T F T F T F T T F F F
Ví dụ: p = “30 chia hết cho 5”, q = “3 > 7”, r = p XOR q là mệnh đề đúng.
Lưu ý: Khi coi giá trị chân lý đúng là 1, sai là 0, các phép toán logic nói trên có thể
mở rộng áp dụng trên các xâu bit bằng cách thực hiện chúng với từng cặp bit tương
ứng trong hai xâu. Lúc đó các phép toán Phủ định, Hội, Tuyển, XOR được ký hiệu
tương ứng là NOT, AND, OR, XOR Ví dụ:
p = 1010110100, q = 1110001001, r = NOT p, s = p AND q, t = p OR q, v = p XOR q.
Khi đó r = 0101001011, s = 1010000000, t = 1110111101, v = 0100111101. 7 Bài 2. Công thức
Khái niệm công thức của logic mệnh đề được xây dựng theo cách kiến thiết (tức là được
xây dựng từ đơn giản đến phức tạp). Ta sẽ xuất phát từ những mệnh đề đơn giản nhất và
sử dụng các phép toán logic để tạo ra tất cả các mệnh đề có thể. Lưu ý rằng khái niệm
công thức trong logic mệnh đề có sự tương tự với khái niệm biểu thức trong ngôn ngữ lập trình.
1. Các định nghĩa
Bảng chữ cái: bảng chữ cái là một tập hợp S bao gồm:
- Các ký hiệu như p, q, r, …, p1, q1,… (là các chữ cái thường hoặc các chữ cái
thường có thêm chỉ số) được gọi là các mệnh đề sơ cấp (tính đúng sai của các
mệnh đề này được xác định khi thay bằng một mệnh đề cụ thể nào đó).
- Các ký hiệu phép toán logic: , , , , , 
- Các dấu ngoặc tròn: (, )
Một dãy hữu hạn các ký hiệu của bảng chữ cái S được gọi là một từ, các từ được ký
hiệu bằng các chữ cái in như A, B, P, Q,... Hai từ A, B được gọi là như nhau nếu hai
dãy ký tự tương ứng giống hệt nhau và ta ký hiệu là A = B.
Ví dụ: A = p  q  r, B = s   t) là các từ Công thức:
1) Các mệnh đề sơ cấp là những công thức
2) Nếu A là công thức thì A là công thức
3) Nếu A, B là các công thức thì (AB), (AB), (AB), (AB), (A  B) là các công thức
4) Chỉ những từ được xác định theo các quy tắc 1), 2), 3) mới là công thức Ví dụ :
A = p  (q  r), A là công thức
B = s   t), B không là công thức
Lưu ý : Khi viết các công thức, để thuận tiện ta có thể bỏ đi các dấu ngoặc ngoài cùng 8
(ngầm hiểu là vẫn có dấu ngoặc cho phù hợp với định nghĩa)
Độ sâu của công thức: giả sử A là một công thức, độ sâu của A, ký hiệu là s(A), được định nghĩa như sau :
1) Nếu A = p (mệnh đề sơ cấp) thì s(A) = 0.
2) Nếu A = B thì s(A) = s(B) + 1.
3) Nếu A = (B*C) với * là một phép toán logic 2 ngôi thì s(A)=max(s(B),s(C))+1.
Độ sâu của công thức cho biết mức độ phức tạp của công thức được hình thành từ các
mệnh đề sơ cấp và thường được sử dụng để chứng minh bằng quy nạp các tính chất
liên quan tới công thức.
Công thức con: giả sử A là một công thức
- Nếu s(A) = 0 thì A là công thức con duy nhất của A
- Nếu s(A) > 0 thì A có dạng B hoặc (B*C) với s(B) và S(C) < s(A). Nếu A=B
thì các công thức của A gồm A và các công thức con của B. Nếu A=(B*C) thì các
công thức con của A gồm A và các công thức con của B và của C. Ví dụ:
A = p  (q  (r  s)).
Các công thức con của gồm: A, p, q, r, s, s, r  s, q  (r  s)
Phép thế trong công thức: Giả sử A là một công thức và B là công thức con của A.
Khi đó A có dạng A = XBY với X, Y là các từ (có thể rỗng). Ta nói B xuất hiện trong
A (B có thể xuất hiện nhiều lần trong A).
Giả sử C là một công thức, phép thế B bởi C trong A, ký hiệu SA(B,C), được xác định
như sau: nếu B không xuất hiện trong A thì SA(B,C)=A. Nếu B xuất hiện trong A thì
thay mỗi xuất hiện của B trong A bằng C theo quy tắc SXBY(B,C)=XCY. Ví dụ:
A = (p  q)  ((p  s)  (p  q)). B = (p  q). C = (p  q)  r. Khi đó S       A(B,C) = ((p q) r) ((p s)  ((p q) r)).
2. Giá trị của công thức 9
Cơ sở của công thức: Cho công thức A, một dãy các mệnh đề sơ cấp {p1,…, pn} được
gọi là cơ sở của A nếu thỏa mãn:
- pi ≠ pj với mọi i ≠ j
- mỗi mệnh đề sơ cấp xuất hiện trong A đều có trong dãy (với mỗi p xuất hiện trong
A tồn tại i sao cho p = pi)
Khi đó dãy e = (e1, …, en) với ei = 0 hoặc 1, được gọi là một dãy giá trị ứng với cơ sở
của A. Thực chất có thể coi e là một phép gán giá trị chân lý cho các mệnh đề sơ cấp
xuất hiện trong A. Nếu cơ sở của công thức A có n mệnh đề sơ cấp thì có 2n dãy giá
trị e khác nhau ứng với cơ sở này.
Ví dụ: A = (p  q)  ((p  s)  (p  q)). Khi đó {p, q, s} là một cơ sở của A và
e=(1,0,1) là một dãy giá trị ứng với cơ sở của A tương ứng với p=1, q=0, s=1 hay p đúng, q sai, s đúng
Giá trị của công thức: Giả sử A là một công thức, {p1,…, pn} là cơ sở của công thức
A, e = (e1, …, en) là một dãy giá trị ứng với cơ sở của A, giá trị của công thức A ứng
với dãy giá trị e (giá trị của A ứng với e), ký hiệu A|e, được xác định như sau: 1) Nếu A = pi thì A|e = ei
2) Giả sử mọi công thức có độ sâu nhỏ hơn A đã xác định giá trị ứng với e, khi đó
- Nếu A = B thì A|e = 0 nếu B|e = 1, A|e = 1 nếu B|e = 0
- Nếu A = BC thì A|e = 1 nếu B|e = 1 = C|e, A|e = 0 nếu ngược lại
- Nếu A = BC thì A|e = 0 nếu B|e = 0 = C|e, A|e = 1 nếu ngược lại
- Nếu A = BC thì A|e = 0 nếu B|e = C|e, A|e = 1 nếu B|e ≠ C|e
- Nếu A = BC thì A|e = 0 nếu B|e = 1 và C|e = 0, A|e =1 nếu ngược lại
- Nếu A = B  C thì A|e = 1 nếu B|e = C|e, A|e = 0 nếu B|e ≠ C|e
Ví dụ: A = (p  q)  ((p  s)  (p  q)). ứng với e=(1,0,1) ta có A|e = 1.
3. Hằng đúng, hằng sai, thỏa được
Định nghĩa: Cho A là công thức.
A được gọi là Hằng Đúng nếu A|e = 1 với mọi dãy giá trị e ứng với cơ sở của A. 10
A được gọi là Hằng Sai nếu A|e = 0 với mọi dãy giá trị e ứng với cơ sở của A.
A được gọi là Thỏa được nếu A không là Hằng Sai. Ví dụ:
A = p  (p  q) là Hằng Đúng. Kiểm chứng dựa vào bảng chân trị
B = (p  p) là Hằng Sai.
C = p  (q  r) là Thỏa được vì với e=(0,1,1) có C|e = 1 vậy C không là Hằng Sai.
Để ký hiệu A là Hằng Đúng ta viết |=A. Các công thức Hằng Đúng còn được gọi là
các Luật logic. Công thức Hằng Sai còn được gọi là Mâu thuẫn.
Định lý: Giả sử A là một công thức có chứa các xuất hiện của mệnh đề sơ cấp p, C là
một công thức tùy ý. Khi đó nếu |=A thì |=SA(p,C).
Chứng minh: Giả sử SA(p,C) không là Hằng Đúng, khi đó tìm được dãy giá trị e sao
cho SA(p,C)|e = 0. Ta xác định dãy giá trị e’ ứng với cơ sở của A như sau: với các
mệnh đề sơ cấp khác p lấy giá trị như trong dãy e còn giá trị ứng với mệnh đề sơ cấp p
lấy giá trị là C|e. Khi đó A|e’ = SA(p,C)|e = 0, mâu thuẫn với giả thiết |=A. 11
Bài 3. Hệ quả logic. Tương đương logic.
1. Hệ quả logic
Định nghĩa: Giả sử A, B là hai công thức. B được gọi là Hệ quả logic của A (ký hiệu
là A|=B) nếu với mọi dãy giá trị e sao cho A|e = 1 thì B|e = 1. Ví dụ: Lưu ý:
- Mọi công thức là Hệ quả logic của công thức Hằng Sai
- Công thức Hằng Đúng là Hệ quả logic của một công thức bất kỳ
Định nghĩa: Giả sử A1, …, An, B là các công thức. B được gọi là Hệ quả logic của các công thức A 
1, …, An (ký hiệu là A1, …, An |=B) nếu A1 …An |= B
Định lý: Nếu A|=B thì |= (AB) và ngược lại. Chứng minh:
- Giả sử A|=B ta chứng tỏ |=AB. Lấy một dãy giá trị e bất kỳ, nếu B|e = 0 thì vì B là
hệ quả logic của A nên A|e= 0, khi đó (AB)|e = 1. Nếu B|e=1 thì (AB)|e = 1. Vậy |= (AB).
- Ngược lại nếu |= (AB), giả sử e là dãy giá trị bất kỳ mà A|e=1. Khi đó (AB)|e=1 và ta có B|e = 1 Hệ quả: Nếu A 
1, …, An |=B thì A1, …, An-1 |= (An B)
2. Tương đương logic
Định nghĩa: Hai công thức A và B được gọi là tương đương logic (ký hiệu AB) nếu
A|e = B|e với mọi dãy giá trị e ứng với cơ sở chung của A và B.
Về mặt ý nghĩa, hai công thức tương đương logic thực chất là hai thể hiện khác nhau
của cùng một mệnh đề.
(Nhớ lại rằng phủ định của một mệnh đề p là một mệnh đề bất kỳ có giá trị chân lý
khác p, các mệnh đề là phủ định của p này đều tương đương logic với nhau.)
Nếu AB thì ta nói A có thể biểu diễn dưới dạng B 12
Ví dụ: A = p  q, B = p  q. Ta có AB, điều này dễ dàng kiểm tra dựa vào bảng chân trị.
Lưu ý: Nếu A và B không chứa mệnh đề sơ cấp giống nhau nào thì AB khi và chỉ khi
A, B cùng là Hằng Đúng hoặc Hằng Sai. Định lý:
a) Nếu AB thì AB b) Nếu A   
1 A2 và B1 B2 thì A1*B1 A2*B2 với * là một trong các phép toán logic hai
ngôi , , , , .
c) Nếu AB thì |= (AB)
d) Giả sử A là công thức chứa công thức con B, A 
1 A2, khi đó SA(B,A1) SA(B,A2)
e) Giả sử A và B là những công thức cùng chứa mệnh đề sơ cấp p, C là công thức bất
kỳ. Khi đó nếu AB thì SA(p,C) SB(p,C)
Chứng minh quy nạp theo độ sâu của công thức A và dựa vào định nghĩa quan hệ tương đương logic.
3. Các luật logic
Quan hệ tương đương logic có rất nhiều tính chất, ở đây ta chỉ liệt kê ra và để lại
chứng minh coi như bài tập
Giả sử A, B, C là các công thức tùy ý, T là công thức Hằng Đúng, F là công thức Hằng Sai  ABBA, ABBA Giao hoán  AAA, AAA Lũy đẳng
 (AB)CA(BC), (AB  ) CA(BC) Kết hợp
 (AB)C(AC)(BC), (AB  ) C(AC)(BC) Phân phối  AB(AB) AB(AB) Đối ngẫu  AA Phủ định kép  ATA, AFA, Đồng nhất  AAT, Loại trừ trung gian 13  AAF, Phi mâu thuẫn  ATT, AFF Nuốt  AB  (AB), Kéo theo
 AB  (AB)(BA)
Để chứng minh hai công thức đã cho là tương đương logic ta có thể dùng các cách sau:
- dựa vào bảng chân trị.
- áp dụng các luật logic đã nêu và sử dụng tính bắc cầu của quan hệ tương đương
logic (tức là nếu AB và BC thì AC, khi đó ta nói rằng có thể dùng các phép biến
đổi tương đương logic để biến A thành C).
- áp dụng định nghĩa kết hợp với lập luận.
Ví dụ: Cho A = (p  q)  r, B = (r  q)  (r  p), chứng minh rằng AB.
Cách 1: Lập bảng giá trị chân lý
Cách 2: Áp dụng luật AB  (AB) ta có (p  q)  (p  q)  (q  p) theo luật
giao hoán. Khi đó A  (q  p)  r  (q  r)  (p  r) theo luật Phân phối, do đó sử
dụng luật giao hoán ta có AB.
Cách 3: Ta sẽ chứng tỏ với bất kỳ e=(p,q,r) thì A|e = B|e. Thật vậy, nếu A|e=1 thì ta
có (p  q)|e=1 và r|e=1 hay r=1 và (p,q)≠(1,0). Khi đó ta có hoặc q=1 hoặc p=0 và vì
vậy có hoặc (r  q)|e=1 hoặc (r  p)|e=1 hay B|e=1. Nếu A|e=0 thì hoặc r=0, lúc đó
dễ thấy B|e=0 hoặc (p  q)|e=0 hay p=1,q=0, lúc đó cũng dễ dàng thấy rằng B|e=0. 14
Bài 4. Dạng chuẩn tắc Tuyển và dạng chuẩn tắc Hội của công thức.
1. Các định nghĩa
Dạng rút gọn: Một công thức ở dạng rút gọn nếu trong công thức chỉ chứa các phép
toán phủ định, tuyển và hội. Ví dụ:
A = (p  q)  r là công thức ở dạng rút gọn
B = (p  q)  (p  r) không ở dạng rút gọn vì có chứa phép kéo theo
Định lý: Mọi công thức đều đưa được về dạng rút gọn (tức là tìm được công thức ở
dạng rút gọn tương đương logic với nó)
Chứng minh: áp dụng các luật sau: (AB)(AB)(BA) và (AB)(AB ) Ví dụ:
Đưa công thức B = (p  q)  (p  r) về dạng rút gọn.
Ta có B  (p  q)  (p  r)
Hội sơ cấp, Tuyển sơ cấp: Một Hội (Tuyển) sơ cấp là hội (tuyển) của các mệnh đề sơ
cấp hoặc phủ định của mệnh đề sơ cấp.
Ví dụ: P = p  q  r là một Tuyển sơ cấp, Q = p  q  q là một Hội sơ cấp. Lưu ý:
- Một mệnh đề sơ cấp hoặc phủ định của mệnh đề sơ cấp vừa là Tuyển sơ cấp vừa là Hội sơ cấp.
- Nếu A là một Tuyển sơ cấp thì A tương đương logic với một Hội sơ cấp
- Nếu A là một Hội sơ cấp thì A tương đương logic với một Tuyển sơ cấp Dạng chuẩn tắc:
- Một công thức ở dạng Chuẩn tắc Hội nếu nó là hội của các tuyển sơ cấp.
- Một công thức ở dạng Chuẩn tắc Tuyển nếu nó là tuyển của các hội sơ cấp. Ví dụ:
A = (p  q  r)  (p  q) ở dạng Chuẩn tắc Hội.
B = (p  q  r)  (p  r) ở dạng Chuẩn tắc Tuyển. 15 Lưu ý:
- Một Hội sơ cấp vừa có dạng Chuẩn tắc Hội vừa có dạng Chuẩn tắc Tuyển
- Một Tuyển sơ cấp vừa có dạng Chuẩn tắc Hội vừa có dạng Chuẩn tắc Tuyển
2. Định lý về dạng chuẩn tắc Định lý 1:
a) Giả sử A là một công thức. Khi đó A có thể biểu diễn dưới dạng Chuẩn tắc Hội
(Tồn tại công thức B ở dạng Chuẩn tắc Hội và AB)
b) Giả sử A là một công thức. Khi đó A có thể biểu diễn dưới dạng Chuẩn tắc Tuyển
(Tồn tại công thức B ở dạng Chuẩn tắc Tuyển và AB)
Ta cũng nói rằng có thể dùng các phép biến đổi tương đương logic đưa A về dạng
Chuẩn tắc (Hội hoặc Tuyển) Chứng minh:
Ta chứng minh đồng thời cả hai khẳng định a) và b). Xét A ở dạng rút gọn. Ta chứng
minh quy nạp theo độ sâu của A, s(A). Nếu s(A)=0 thì A là mệnh đề sơ cấp nên theo
lưu ý ở trên A có dạng Chuẩn tắc Hội và Chuẩn tắc Tuyển. Giả sử khẳng định là đúng
với mọi công thức có độ sâu nhỏ hơn s(A), ta chứng minh khẳng định đúng với A.
Nếu A=B thì s(B)Hội và B2 có dạng Chuẩn tắc Tuyển sao cho BB1 và BB .
2 Khi đó AB1 có dạng
Chuẩn tắc Tuyển và AB2 có dạng Chuẩn tắc Hội.
Nếu A=BC thì s(B) và s(C) đều nhỏ hơn s(A) nên B và C thỏa mãn giả thiết quy
nạp. Khi đó tìm được B1B và C1C sao cho B1 và C1 đều có dạng Chuẩn tắc
Tuyển. Lúc đó AB1C1 có dạng Chuẩn tắc Tuyển. Tương tự, B2B và C2C sao
cho B2 và C2 đều có dạng Chuẩn tắc Hội. Áp dụng luật phân phối ta có thể biến đổi
B2C2 về dạng Chuẩn tắc Hội.
Nếu A=BC, chứng minh tương tự.
Ví dụ: Đưa công thức A = (p  q)  (p  r) về dạng Chuẩn tắc Tuyển và dạng Chuẩn tắc Hội. 16
a) Ta có A  (p  q)  (p  r) (chưa phải dạng Chuẩn tắc Tuyển vì thành phần thứ
nhất không phải là Hội sơ cấp)  (p  q)  (p  r)  (p  q)  (p  r) ở dạng Chuẩn tắc Tuyển.
b) Áp dụng luật Phân phối từ dạng Chuẩn tắc Tuyển ta biến đổi về dạng Chuẩn tắc
Hội. Ta có A  (p  q)  (p  r)  (p  (p r))  (q  (p  r))
 ((p  p)  (p  r))  ((q  p)  (q  r)) ở dạng Chuẩn tắc Hội. Định lý 2:
a) Điều kiện cần và đủ để một công thức A là Hằng Sai là: trong dạng Chuẩn tắc
Tuyển của A mỗi Hội sơ cấp đều có chứa một mệnh đề sơ cấp p nào đó cùng với phủ định của nó p.
b) Điều kiện cần và đủ để một công thức A là Hằng Đúng là: trong dạng Chuẩn tắc
Hội của A mỗi Tuyển sơ cấp đều có chứa một mệnh đề sơ cấp p nào đó cùng với phủ định của nó p Chứng minh:
Sử dụng bổ đề sau: Một Hội sơ cấp là Hằng Sai khi và chỉ khi có chứa một mệnh sơ
cấp p nào đó cùng với phủ định của nó p. Một Tuyển sơ cấp là Hằng Đúng khi và
chỉ khi có chứa một mệnh sơ cấp p nào đó cùng với phủ định của nó p.
Dễ thấy một Hội sơ cấp chứa mệnh đề sơ cấp p nào đó cùng với phủ định của nó p
là một Hằng Sai. Ngược lại giả sử P là một Hằng Sai nhưng lại không chứa mệnh đề
sơ cấp p nào cùng với phủ định của nó p. Khi đó xét dãy giá trị e ứng với cơ sở của
P như sau: ei = 1 nếu pi xuất hiện trong P không có dấu phủ định và ei = 0 nếu pi xuất
hiện trong P với dấu phủ định. Lúc này P|e = 0 mâu thuẫn với giả sử P là Hằng Sai.
Chứng minh hoàn toàn tương tự với Tuyển Sơ cấp là Hằng Đúng.
Chứng minh định lý: ta sẽ chứng minh khẳng định a) còn khẳng định b) được chứng
minh hoàn toàn tương tự.
Giả sử trong dạng Chuẩn tắc Tuyển của A mỗi Tuyển sơ cấp đều có chứa một mệnh
đề sơ cấp p nào đó cùng với phủ định của nó p. Theo bổ đề mỗi Tuyển sơ cấp đều là 17
Hằng Đúng vì vậy A là Hằng Đúng.
Ngược lại, giả sử A là Hằng Đúng và A ở dạng Chuẩn tắc Hội. Giả sử trong A có một
Tuyển sơ cấp P không chứa mệnh đề sơ cấp p nào cùng với phủ định của nó p. Ta
xét dãy giá trị e như sau: với các pi xuất hiện trong P không có dấu phủ định ta lấy ei =
0, với các pi xuất hiện trong P có dấu phủ định ta lấy ei = 1. Khi đó rõ ràng P|e =0. Do
đó A|e=0, mâu thuẫn với giả thiết A là Hằng Đúng.
Ví dụ áp dụng: Chứng minh công thức sau là Hằng Đúng
A = (p(qq))  p.
Ta biến đổi A về dạng Chuẩn tắc Hội. Ta có
A ((p(qq)))  p  (p(qq))  p  (p p )(qq p)
Vì mỗi Tuyển sơ cấp trong công thức ở dạng cuối cùng đều là Hằng Đúng nên A là Hằng Đúng.
3. Định lý về dạng chuẩn tắc hoàn toàn Định nghĩa:
a) Giả sử A là công thức, ta nói A ở dạng Chuẩn tắc Hội Hoàn toàn nếu A thỏa mãn các điều kiện sau:
 A ở dạng Chuẩn tắc Hội
 Mỗi Tuyển sơ cấp trong A không chứa mệnh đề sơ cấp nào xuất hiện hơn 1 lần
 Các Tuyển sơ cấp là khác nhau (không tương đương logic với nhau)
 Các Tuyển sơ cấp chứa các mệnh đề sơ cấp như nhau
b) Giả sử A là công thức, ta nói A ở dạng Chuẩn tắc Tuyển Hoàn toàn nếu A thỏa mãn các điều kiện sau:
 A ở dạng Chuẩn tắc Tuyển
 Mỗi Hội sơ cấp trong A không chứa mệnh đề sơ cấp nào xuất hiện hơn 1 lần
 Các Hội sơ cấp là khác nhau (không tương đương logic với nhau)
 Các Hội sơ cấp chứa các mệnh đề sơ cấp như nhau Ví dụ: 18
A = (pqr)  (pqr) ở dạng Chuẩn tắc Hội Hoàn toàn
B = (pqp)  (qpr) không ở dạng Chuẩn tắc Hội Hoàn toàn vì Tuyển sơ cấp
đầu tiên có p xuất hiện hơn 1 lần
C = (pqr)  (qr) không ở dạng Chuẩn tắc Hội Hoàn toàn vì Hội sơ cấp thứ hai
không có mệnh đề sơ cấp p. Lưu ý:
- Mỗi Hội sơ cấp không chứa mệnh đề sơ cấp xuất hiện hơn 1 lần là công thức ở dạng
Chuẩn tắc Tuyển Hoàn toàn.
- Mỗi Tuyển sơ cấp không chứa mệnh đề sơ cấp xuất hiện hơn 1 lần là công thức ở
dạng Chuẩn tắc Hội Hoàn toàn.
Định lý 1: Giả sử A là công thức
a) Tìm được công thức B ở dạng Chuẩn tắc Hội Hoàn toàn và AB.
b) Tìm được công thức B ở dạng Chuẩn tắc Tuyển Hoàn toàn và AB.
Ta cũng nói rằng có thể đưa A về dạng Chuẩn tắc Hội (Tuyển) Hoàn toàn. Chứng minh:
Ta sẽ chứng minh phần a), phần b) chứng minh hoàn toàn tương tự (xem như bài tập).
Theo Định lý về dạng Chuẩn tắc ta có thể giả thiết A ở dạng Chuẩn tắc Hội. Ta sẽ sử
dụng một số phép biến đổi (nếu cần) để các Tuyển sơ cấp trong A thỏa mãn các điều
kiện của định nghĩa dạng Chuẩn tắc Hội Hoàn toàn.
- Nếu trong A có Tuyển sơ cấp P thiếu mệnh đề sơ cấp q thì áp dụng phép biến đổi
P  P  (qq)  (Pq)  (Pq) thành Hội của hai Tuyển sơ cấp đều có chứa mệnh
đề sơ cấp q. Như vậy có thể đảm bảo các Tuyển sơ cấp có chứa các mệnh đề sơ cấp như nhau.
- Nếu trong A có chứa hai Tuyển sơ cấp giống nhau thì chỉ giữ lại một, áp dụng luật
logic PP  P. Như vậy có thể đảm bảo A không chứa hai Tuyển sơ cấp giống nhau.
- Nếu trong A có Tuyển sơ cấp chứa mệnh đề sơ cấp p xuất hiện hơn 1 lần thì hoặc là
loại bỏ P (nếu p và p cùng xuất hiện) vì P là Hằng Đúng, hoặc loại bỏ bớt các mệnh
đề sơ cấp giống nhau chỉ giữ lại một. 19
Áp dụng các phép biến đổi này một số lần ta sẽ nhận được dạng Chuẩn tắc Hội Hoàn
toàn tương đương logic với A.
Ví dụ: A = (pq)  (qr)  (ppr)  (qqr).
Ta có A  (pq)  (qr)  (qr)  (pq)  (qr)  ((pq) (rr))((qr) (pp)
 (pqr)  (pqr)  (qrp)  (qrp)
 (pqr)  (pqr)  (qrp) ở dạng Chuẩn tắc Hội Hoàn toàn.
Định lý 2: Nếu hai công thức A và B chứa các mệnh đề sơ cấp như nhau mà có dạng
Chuẩn tắc Tuyển Hoàn toàn (hoặc Chuẩn tắc Hội Hoàn toàn) không giống nhau (tức
là chứa các Hội sơ cấp (hoặc Tuyển sơ cấp) khác nhau thì A và B không tương đương logic. Chứng minh:
Giả sử dạng Chuẩn tắc Tuyển Hoàn toàn của A và B là: A = A   1 A2 ... An, B = B1 B2 ... Bm.
Giả sử trong A có Hội sơ cấp Ak không xuất hiện trong B, tức là Ak ≠ Bj với j=1..m
Xét dãy giá trị e như sau: với mỗi mệnh đề sơ cấp pi xuất hiện trong Ak không có dấu
phủ định  thì ei=1, ngược lại thì ei=0. Khi đó Ak| =
e 1 và do đó A|e=1. Mặt khác với
Bj bất kỳ, vì Bj ≠ Ak nên tồn tại pt sao cho nếu pt xuất hiện trong Ak có dấu phủ định
thì pt xuất hiện trong Bj không có dấu phủ đinh, hoặc nếu pt xuất hiện trong Ak không
có dấu phủ định thì pt xuất hiện trong Bj phải có dấu phủ định. Khi đó dễ thấy Bj|e=0
với mọi j=1..m, do đó B|e=0. Vậy A không tương đương logic với B.
Chứng minh hoàn toàn tương tự cho trường hợp A và B có dạng Chuẩn tắc Hội Hoàn toàn. Hệ quả:
a) Mọi công thức không là Hằng Sai chỉ có một dạng Chuẩn tắc Tuyển Hoàn toàn duy nhất.
b) Mọi công thức không là Hằng Đúng chỉ có một dạng Chuẩn tắc Hội Hoàn toàn duy nhất. 20