Bài giảng Luận lý toán học - Chương 2: Luận lý mệnh đề (Phần 2) - Nguyễn Thanh Sơn

ntsơn 
II. Suy luận tự nhiên trong 
 luận lý mệnh đề 
ntsơn 
Chương 2 
Chứng minh 
Thí dụ : 
 Tam giác ABC có các cạnh là AB = 3, BC = 4, 
CA = 5. Chứng minh ABC vuông. 
Chứng minh : 
 (1) cạnh AB = 3. 
 (2) cạnh BC = 4. 
 (3) cạnh CA = 5. 
 (4) CA2 = BC2 + AB2. 
 (5) Từ định lý Pythagore, tam giác ABC vuông. 
ntsơn 
Chương 2 
Chứng minh 
•  Chuỗi 5 phát biểu : 
 (1) cạnh AB = 3 
 (2) cạnh BC = 4 
 (3) cạnh CA = 5 
 (4) CA2 = BC2 + AB2 
 (5) Từ đlý Pythagore, tam giác ABC vuông 
 được gọi là một “chứng minh” theo nghĩa thông 
thường trong toán học. 
ntsơn 
Chương 2 
Chứng minh 
Hệ thồng : Mã hóa 
 {cạnh AB = 3, {F1, 
 cạnh BC = 4, F2, 
 cạnh CA = 5}. F3} 
Chứng minh : 
 {tam giác ABC vuông}. H 
ntsơn 
Chương 2 
Chứng minh 
•  Công thức H được gọi là “được chứng minh” từ 
hệ thống F nếu viết ra được một “chứng minh” 
mà công thức cuối cùng trong chứng minh là H. 
•  Chứng minh là chuỗi các công thức được viết 
ra dựa vào hệ thống và các qui tắc suy luận. 
•  Qui tắc suy luận gồm : 
 các qui tắc suy luận tự nhiên và 
 các suy luận đã được chứng minh. 
ntsơn 
Chương 2 
Qui tắc viết chuỗi công thức 
•  Viết ra một công thức (trong chuỗi công thức) 
trên 1 dòng bằng cách : 
 lấy một công thức từ hệ thống hoặc 
 áp dụng các qui tắc suy luận. 
 Với 2 cách trên, khi viết được dòng có nội dung 
là công thức cần chứng minh thì dừng. 
ntsơn 
Chương 2 
Chứng minh 
•  H được chứng minh từ F được ký hiệu là : 
 (F ├─ H). 
•  Ký hiệu (F ├─ H) được gọi là một sequent. 
F được gọi là tiền đề và H là kết luận. 
•  Nếu sequent không có tiền đề thì kết luận H 
được gọi là định lý (├─ H). 
•  Nếu F├─ G và F ─┤G thì ký hiệu là 
 F ─┤├─ G hay 
 F ≡ G 
ntsơn 
Chương 2 
Suy luận tự nhiên[3] 
•  Qui tắc giao i (∧i) 
 dòng m : F 
 dòng k : G 
 dòng p : F ∧ G 
 Nếu có dòng m với nội dung F và dòng k với nội 
dung G thì có thể viết ra dòng mới p có nội 
dung là (F ∧ G). 
Ghi chú : 
 Ký hiệu i có nghĩa là introduction. 
ntsơn 
Chương 2 
Suy luận tự nhiên[3] 
•  Qui tắc giao e (∧e) 
 dòng m : F ∧ G 
 dòng k : F 
 dòng p : G 
 Nếu đã có một dòng là (F ∧ G) thì có thể viết ra 
dòng mới là F (hoặc G). 
Ghi chú : 
 Ký hiệu e có nghĩa là elimination. 
ntsơn 
Chương 2 
Suy luận tự nhiên[3] 
•  Qui tắc điều kiện e (Modus ponens) (→e) 
 dòng m : F → G 
 dòng k : F 
 dòng p : G 
 Nếu có dòng F và dòng F → G thì viết được 
dòng mới G. 
* Từ modus ponens (MP) có nghĩa là affirming 
method. 
ntsơn 
Chương 2 
Suy luận 
Chứng minh : P, Q, (P ∧ Q) → (R ∧ S) ├─ S. 
 1 P tiền đề 
 2 Q tiền đề 
 3 P ∧ Q ∧i 1, 2 
 4 P ∧ Q → R ∧ S tiền đề 
 5 R ∧ S →e 3, 4 
 6 S ∧e 5 
ntsơn 
Chương 2 
Suy luận tự nhiên[3] 
•  Qui tắc điều kiện i (→i) 
 dòng m : if F 
 dòng m+k : nif G 
 dòng m+k+1 : F→G 
 Dòng m có nội dung là F (được chọn tùy ý), và 
thêm từ khóa ‘if’ trước công thức F. 
 (dòng này có nghĩa là giả sử có F). 
 Các dòng kế (m+1, , m+k) có thể sử dụng 
hay không sử dụng dòng m đều được coi như 
phụ thuộc vào sự hiện diện của giả thiết F. 
ntsơn 
Chương 2 
Suy luận tự nhiên[3] 
•  Qui tắc điều kiện i (tt) 
 Để chấm dứt ảnh hưởng của giả thiết F ở dòng 
k thêm từ khóa ‘nif’ trước nội dung của dòng 
này. Việc đặt từ khoá nif trước dòng nào là tùy 
thuộc người chứng minh. 
 Các dòng trong cấu trúc ‘if-nif’ có thể được xây 
dựng nhờ cả các dòng trên dòng m. 
ntsơn 
Chương 2 
Suy luận tự nhiên[3] 
•  Qui tắc điều kiện i (tt) 
 Các dòng trong cấu trúc ‘if-nif’ không được sử 
dụng để xây dựng cho các dòng ngoài cấu trúc 
‘if-nif’. 
 Công thức trên dòng “nif” (ngay sau từ khóa nif) 
được qui ước là thuộc cấu trúc “if  nif”. 
 Sau cấu trúc ‘if-nif’ viết dòng kết hợp dòng ‘if’ và 
dòng ‘nif’ : F → G. 
 Cấu trúc ‘if-nif’ có thể lồng vào nhau. 
ntsơn 
Chương 2 
Suy luận[3] 
Chứng minh : F├─ G → F 
 1 if G 
 2 nif F tiền đề 
 3 G → F →i 1, 2 
ntsơn 
Chương 2 
Suy luận tự nhiên[3] 
•  Qui tắc bản sao (id) 
 dòng m : F 
 dòng k : F 
 chép lại công thức đã xuất hiện, nếu dòng k 
nằm trong phạm vi ảnh hưởng của dòng m. 
ntsơn 
Chương 2 
Suy luận[3] 
Chứng minh ├─ F → F 
 1 if F 
 2 nif F bản sao của 1 
 3 F → F →i 1-2 
ntsơn 
Chương 2 
Suy luận[3] 
Chứng minh : ├─ (F → (G → F) 
 1 if F 
 2 if G 
 3 nif F bản sao 1 
 4 nif G → F →i 2, 3 
 5 F → (G → F) →i 1, 4 
ntsơn 
Chương 2 
Suy luận tự nhiên[3] 
•  Qui tắc hội i (∨i) 
 dòng m : F 
 dòng k : F ∨ G 
 Nếu có dòng F thì viết được dòng mới F ∨ G 
với G là công thức bất kỳ. 
ntsơn 
Chương 2 
Suy luận tự nhiên[3] 
•  Qui tắc hội e (∨e) 
 dòng m : F ∨ G 
 dòng n : if F 
 dòng n+p : nif H 
 dòng k : if G 
 dòng k+q : nif H 
 dòng k+q+1 : H 
 Nếu F sinh ra H và G cũng sinh ra H thì 
F ∨ G cũng sinh ra H. 
ntsơn 
Chương 2 
Suy luận[3] 
Chứng minh (G → H) ├─ (F ∨ G) → (F ∨ H) 
 1 G → H tiền đề 
 2 if F ∨ G 
 3 if F 
 4 nif F ∨ H ∨i 3 
 5 if G 
 6 H →e 1, 5 
 7 nif F ∨ H ∨i 6 
 8 nif F ∨ H ∨e 2, 3, 5 
 9 (F ∨ G) → (F ∨ H) →i 2-8 
ntsơn 
Chương 2 
Suy luận tự nhiên[3] 
•  Qui tắc phủ định (¬e) 
 dòng m : F ∧ ¬F 
 dòng k : ⊥ 
 Dạng (F∧¬F) được gọi là công thức mâu thuẫn. 
 Công thức mâu thuẫn được biểu diễn bằng ký 
hiệu ⊥. 
 Đây là công thức “mạnh” nhất. 
•  Dạng (F ∨ ¬F) được ký hiệu Ť. 
 Đây là công thức “yếu” nhất. 
ntsơn 
Chương 2 
Suy luận tự nhiên[3] 
•  Qui tắc phủ định (¬i) 
 dòng m : if F 
 dòng k : nif ⊥ 
 dòng k+1 : ¬F 
 Giả sử có dòng F và dẫn ra mâu thuẫn thì có 
thể viết ra dòng ¬F. 
ntsơn 
Chương 2 
Suy luận 
•  Qui tắc mâu thuẫn (⊥e) 
 dòng k : ⊥ 
 dòng m : F 
 Nếu có dòng (k) ⊥ thì có thể viết ra dòng (m) F 
với F là bất kỳ công thức nào. 
Nhận xét : 
 Mọi công thức có thể được dẫn xuất từ công 
thức mâu thuẫn. Nói cách khác, công thức mâu 
thuẫn chứng minh được mọi công thức. 
ntsơn 
Chương 2 
Suy luận 
Chứng minh : ¬F ∨ G ├─ F → G 
 1 ¬F ∨ G tiền đề 
 2 if ¬F 
 3 if F 
 4 ⊥ ¬e 2, 3 
 5 nif G ⊥e 4 
 6 nif F → G →i 3, 5 
 7 if G 
 8 if F 
 9 nif G bản sao 7 
 10 nif F → G →i 8, 9 
 11 F → G ∨e 1, 2-10 
ntsơn 
Chương 2 
Suy luận[3] 
Chứng minh F→G, F→¬G├─ ¬F 
 1 F→G tiền đề 
 2 F→¬G tiền đề 
 3 if F 
 4 G →e 1, 3 
 5 ¬G →e 2, 3 
 6 nif ⊥ ¬e 4, 5 
 7 ¬F ¬i 3, 6 
ntsơn 
Chương 2 
Suy luận[3] 
Chứng minh F ├─ ¬¬F 
 1 F tiền đề 
 2 if ¬F 
 3 nif ⊥ ¬e 1, 2 
 4 ¬¬F ¬i 2, 3 
ntsơn 
Chương 2 
Suy luận[3] 
Chứng minh Modus tolens F→G, ¬G├─ ¬F 
 1 F→G tiền đề 
 2 ¬G tiền đề 
 3 if F 
 4 G →e 1, 3 
 5 nif ⊥ ¬e 2, 4 
 6 ¬F ¬i 3, 5 
•  Từ modus tolens (MT) có nghĩa là denying 
method. 
ntsơn 
Chương 2 
Suy luận[3] 
Chứng minh F → (G→H), F, ¬H├─ ¬G 
 1 F → (G→H) tiền đề 
 2 F tiền đề 
 3 G→H →e 1, 2 
 4 ¬H tiền đề 
 5 ¬G MT 3, 4 
ntsơn 
Chương 2 
Suy luận[3] 
Chứng minh F→G├─ ¬G→¬F 
 1 F→G tiền đề 
 2 if ¬G 
 3 nif ¬F MT 1, 2 
 4 ¬G → ¬F (→i) 
ntsơn 
Chương 2 
Suy luận tự nhiên[3] 
•  Qui tắc phủ định kép e (¬¬e) 
 dòng m : ¬¬F 
 dòng k : F 
 Nếu có dòng ¬¬F thì có thể viết được dòng F. 
ntsơn 
Chương 2 
Suy luận[3] 
Chứng minh Reductio ad absurrdum (RAA) : 
 ¬F → ⊥ ├─ F 
 1 ¬F → ⊥ tiền đề 
 2 if ¬F 
 3 nif ⊥ ¬e 1, 2 
 4 ¬¬F ¬i 2, 3 
 5 F ¬¬e 4 
ntsơn 
Chương 2 
Suy luận[3] 
Nhận xét : 
 RAA còn gọi là Proof by contradiction (PBC), 
được viết dưới dạng qui tắc như sau : 
•  Qui tắc PBC 
 dòng m : if ¬ F 
 dòng k : nif ⊥ 
 dòng k+1 : F 
 Nếu giả sử có dòng ¬F và dẫn ra mâu thuẫn thì 
có thể viết ra dòng F. 
ntsơn 
Chương 2 
Suy luận[3] 
Chứng minh LEM (the law of the excluded middle) : 
 ├─ F ∨ ¬F 
 1 if ¬(F ∨ ¬F) 
 2 if F 
 3 F ∨ ¬F ∨i 2 
 4 nif ⊥ ¬e 1, 3 
 5 ¬F ¬i 2-4 
 6 F ∨ ¬F ∨i 5 
 7 nif ⊥ ¬e 1, 6 
 8 ¬¬(F ∨ ¬F) ¬i 1-7 
 9 F ∨ ¬F ¬¬e 8 
ntsơn 
Chương 2 
Suy luận[3] 
Chứng minh F → G├─ ¬F ∨ G 
 1 F ∨ ¬F LEM 
 2 if ¬F 
 3 nif ¬F ∨ G ∨i 2 
 4 if F 
 5 F → G tiền đề 
 6 G →e 4, 5 
 7 nif ¬F ∨ G ∨i 6 
 8 ¬F ∨ G ∨e 1, 2, 4 
ntsơn 
Chương 2 
Suy luận[3] 
Chứng minh ¬F ∨ ¬G├─ ¬(F ∧ G) 
 1 if F ∧ G 
 2 F ∧e 1 
 3 G ∧e 1 
 4 ¬F ∨ ¬G tiền đề 
 5 if ¬F 
 6 nif ⊥ ¬e 2,5 
 7 if ¬G 
 8 nif ⊥ ¬e 3,7 
 9 nif ⊥ ∨e 4-8 
 10 ¬(F ∧ G) ¬i 1-9 
ntsơn 
Chương 2 
Ứng dụng của chứng minh[7] 
•  Có các phản ứng hóa học sau : 
 HCl + NaOH → NaCl + H2O 
 C + O2 → CO2 
 CO2 + H2O → H2CO3 
 Chỉ rằng có thể có H2CO3 khi có HCl, NaOH, O2 
và C. 
ntsơn 
Chương 2 
Ứng dụng của chứng minh[7] 
•  Các phân tử HCl, NaOH, O2 và C được hình 
thức hóa như là một hệ thống và chứng minh 
rằng H2CO3 được chứng minh từ hệ thống này. 
•  Các phản ứng hóa học được hình thức hóa như 
sau : 
 HCl ∧ NaOH → NaCl ∧ H2O 
 C ∧ O2 → CO2 
 CO2 ∧ H2O → H2CO3. 
ntsơn 
Chương 2 
Ứng dụng của chứng minh 
Bài toán trở thành chứng minh : 
 HCl ∧ NaOH → NaCl ∧ H2O, 
 C ∧ O2 → CO2, 
 CO2 ∧ H2O → H2CO3, 
 HCl, ├─ H2CO3. 
 NaOH, 
 O2, 
 C 
ntsơn 
Chương 2 
Ứng dụng của chứng minh 
Chứng minh : 
 1 HCl tiền đề 
 2 NaOH tiền đề 
 3 HCl ∧ NaOH ∧i 1, 2 
 4 HCl ∧ NaOH → NaCl ∧ H2O tiền đề 
 5 NaCl ∧ H2O →e 3, 4 
 6 H2O ∧e 5 
 7 C tiền đề 
 8 O2 tiền đề 
 9 C ∧ O2 ∧i 7, 8 
 10 C ∧ O2 → CO2 tiền đề 
 11 CO2 →e 9, 10 
 12 CO2 ∧ H2O ∧i 6, 11 
 13 CO2 ∧ H2O → H2CO3 tiền đề 
 14 H2CO3 →e 12, 13 
ntsơn 
Chương 2 
Chứng minh bằng phản chứng 
•  Một số công thức khó chứng minh được bằng 
cách trực tiếp. 
•  Logic cổ điển chấp nhận cách chứng minh gián 
tiếp - chứng minh ¬F để dẫn đến mâu thuẫn. 
•  Nhưng logic trực giác (intuitionistic logic) không 
đồng ý hai qui tắc : 
 ├─ F ∨ ¬F (LEM) và 
 ├─ ¬¬F → F (¬¬e) 
ntsơn 
Bài tập 
Chương 2 : Luận lý mệnh đề 
ntsơn 
Chương 2 
Suy luận 
Chứng minh 
1. ¬G → ¬F├─ F → ¬¬G 
2. ├─ (G→H) → ((¬G→ ¬F) → (F→H)) 
3. (F ∧ G) → H├─ F → (G → H) 
4. F → (G → H) ├─ (F ∧ G) → H 
5. F → G ├─ (F ∧ H) → (G ∧ H) 
ntsơn 
Chương 2 
Suy luận 
6. (F ∨ G) ∨ H ├─ F ∨ (G ∨ H) 
7. F ∧ (G ∨ H) ├─ (F ∧ G) ∨ (F ∧ H) 
8. F→¬F├─ ¬F 
9. F→(G→H), F, ¬H├─ ¬G (không dùng luật MT) 
10. (F ∧ ¬G) → H, ¬H, F├─ G. 
ntsơn 
Chương 2 
Hết slide