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
II. Suy luận tự nhiên trong
luận lý mệnh đề
ntsơn
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.
Chương 2
ntsơn
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.
Chương 2
ntsơn
Chứng minh
Hệ thồng :
{cạnh AB = 3,
Mã hóa
{F1,
cạnh BC = 4,
cạnh CA = 5}.
F2,
F3}
Chứng minh :
{tam giác ABC vuông}.
H
Chương 2
ntsơn
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.
Chương 2
ntsơn
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.
Chương 2
ntsơn
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
Chương 2
ntsơn
[3]
Suy luận tự nhiên
•ꢀ Qui tắc giao i (∧i)
dòng m :
dòng k :
dòng p :
F
G
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.
Chương 2
ntsơn
[3]
Suy luận tự nhiên
•ꢀ Qui tắc giao e (∧e)
dòng m :
dòng k :
dòng p :
F ∧ G
F
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.
Chương 2
ntsơn
[3]
Suy luận tự nhiên
•ꢀ Qui tắc điều kiện e (Modus ponens) (→e)
dòng m :
dòng k :
dòng p :
F → G
F
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.
Chương 2
ntsơn
Suy luận
Chứng minh : P, Q, (P ∧ Q) → (R ∧ S) ├─ S.
1 P
tiền đề
tiền đề
∧i 1, 2
tiền đề
→e 3, 4
∧e 5
2 Q
3 P ∧ Q
4 P ∧ Q → R ∧ S
5 R ∧ S
6 S
Chương 2
ntsơn
[3]
Suy luận tự nhiên
•ꢀ Qui tắc điều kiện i (→i)
dòng m :
dòng m+k :
if F
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.
Chương 2
ntsơn
[3]
Suy luận tự nhiên
•ꢀ 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.
Chương 2
ntsơn
[3]
Suy luận tự nhiên
•ꢀ 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.
Chương 2
ntsơn
[3]
Suy luận
Chứng minh : F├─ G → F
1
2
3
if G
nif F
G → F
tiền đề
→i 1, 2
Chương 2
ntsơn
[3]
Suy luận tự nhiên
•ꢀ Qui tắc bản sao (id)
dòng m :
dòng k :
F
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.
Chương 2
ntsơn
[3]
Suy luận
Chứng minh ├─ F → F
1
2
3
if F
nif F bản sao của 1
F → F →i 1-2
Chương 2
ntsơn
[3]
Suy luận
Chứng minh : ├─ (F → (G → F)
1
2
3
4
5
if F
if G
nif F
bản sao 1
→i 2, 3
nif G → F
F → (G → F)
→i 1, 4
Chương 2
ntsơn
[3]
Suy luận tự nhiên
•ꢀ Qui tắc hội i (∨i)
dòng m :
dòng k :
F
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ỳ.
Chương 2
ntsơn
[3]
Suy luận tự nhiên
•ꢀ Qui tắc hội e (∨e)
dòng m :
dòng n :
dòng n+p :
dòng k :
F ∨ G
if F
nif H
if G
nif H
dòng k+q :
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.
Chương 2
ntsơn
Tải về để xem bản đầy đủ
45 trang
19240
Free
Bạn đang xem 20 trang mẫu của tài liệu "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", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_luan_ly_toan_hoc_chuong_2_luan_ly_menh_de_phan_2_n.pdf
