Suy diễn tự nhiên (natural deduction) là cách viết chứng minh logic thành một dãy dòng đánh số, mỗi dòng là một công thức kèm lý do: hoặc là tiền đề, hoặc là giả định tạm, hoặc được rút ra từ các dòng trước bằng một quy tắc có tên. Thay vì lập bảng chân trị hàng chục dòng, ta đi từ tiền đề tới kết luận như người làm toán, và ai đọc cũng kiểm được từng bước. Hệ này do Gerhard Gentzen và Stanisław Jaśkowski đề xuất độc lập, cùng năm 1934.
Vì sao cần một cách khác bảng chân trị
Bảng chân trị kiểm được mọi lập luận của logic mệnh đề, nhưng có hai điểm yếu. Một: số dòng tăng gấp đôi với mỗi biến — 10 câu đơn đã 1.024 dòng. Hai: bảng trả lời "hợp lệ" mà không cho thấy vì sao. Người làm toán không chứng minh định lý bằng cách liệt kê mọi trường hợp; họ đi từng bước, mỗi bước có lý do. Suy diễn tự nhiên mô phỏng đúng lối đi ấy, nên mới có chữ "tự nhiên".
Điều quan trọng: với logic mệnh đề cổ điển, hai cách cho cùng một kết quả. Mọi thứ chứng minh được bằng suy diễn tự nhiên đều hợp lệ theo bảng chân trị (tính đúng đắn), và mọi lập luận hợp lệ theo bảng đều chứng minh được (tính đầy đủ).
Bộ quy tắc: mỗi phép nối một quy tắc vào, một quy tắc ra
Ký hiệu: ¬ "không", ∧ "và", ∨ "hoặc", → "nếu… thì…". Mỗi phép nối có quy tắc nhập (cách tạo ra công thức có phép nối đó) và quy tắc khử (cách dùng nó). A, B, C dưới đây là công thức bất kỳ.
| Quy tắc | Đã có | Được viết | Tên quen gọi |
|---|---|---|---|
| Nhập ∧ | A; B | A ∧ B | Kết hợp |
| Khử ∧ | A ∧ B | A (hoặc B) | Đơn giản hoá |
| Nhập ∨ | A | A ∨ B (B tuỳ ý) | Cộng thêm |
| Khử ∨ | A ∨ B; hộp "giả định A … C"; hộp "giả định B … C" | C | Xét trường hợp (song đề) |
| Khử → | A → B; A | B | Modus ponens |
| Nhập → | hộp "giả định A … B" | A → B | Chứng minh có điều kiện |
| Nhập ¬ | hộp "giả định A … B ∧ ¬B" | ¬A | Phản chứng |
| Khử ¬¬ | ¬¬A | A | Phủ định kép |
| Lặp lại | A (ở dòng còn dùng được) | A | Nhắc lại |
Các giáo trình khác nhau có thể chọn bộ quy tắc hơi khác (thêm modus tollens, tam đoạn luận lựa chọn làm quy tắc dẫn xuất, hoặc dùng ký hiệu ⊥ cho "mâu thuẫn"), nhưng tinh thần giống nhau.
Hộp giả định — chỗ người mới hay sai
Ba quy tắc nhập →, nhập ¬ và khử ∨ dùng giả định tạm. Ta mở một "hộp", viết "giả sử A", suy luận bên trong, rồi đóng hộp và rút ra một điều không còn phụ thuộc vào giả định đó. Trong bảng chứng minh dưới đây, mỗi vạch │ đầu dòng là một tầng hộp.
Luật sống còn: dòng nằm trong hộp đã đóng không được dùng ở bên ngoài. Bên trong hộp, điều được rút ra chỉ đúng "nếu giả định đúng"; mang nó ra ngoài là lén biến giả định thành sự thật.
Bốn ví dụ viết từng dòng
Ví dụ 1: chứng minh thẳng bằng modus ponens
Câu chuyện: "Nếu xe buýt số 9 đến trễ thì Mai lỡ chuyến tàu 7 giờ. Nếu lỡ chuyến tàu 7 giờ thì Mai đến buổi phỏng vấn muộn. Sáng nay xe số 9 đến trễ." Chứng minh Mai đến muộn.
p = "xe đến trễ", q = "lỡ tàu", r = "đến muộn".
| Dòng | Công thức | Lý do |
|---|---|---|
| 1 | p → q | Tiền đề |
| 2 | q → r | Tiền đề |
| 3 | p | Tiền đề |
| 4 | q | Khử → (1, 3) |
| 5 | r | Khử → (2, 4) |
Mỗi dòng ghi rõ dùng quy tắc nào, lấy từ dòng nào. Người chấm không cần tin người viết; chỉ cần dò lại từng dòng.
Ví dụ 2: chứng minh một câu "nếu… thì…" bằng hộp giả định
Bỏ tiền đề "sáng nay xe đến trễ". Chỉ với hai câu điều kiện, có chứng minh được "nếu xe đến trễ thì Mai đến muộn" không? Cách làm: giả sử xe đến trễ, đi tới "đến muộn", rồi đóng hộp.
| Dòng | Công thức | Lý do |
|---|---|---|
| 1 | p → q | Tiền đề |
| 2 | q → r | Tiền đề |
| 3 | │ p | Giả định |
| 4 | │ q | Khử → (1, 3) |
| 5 | │ r | Khử → (2, 4) |
| 6 | p → r | Nhập → (3–5) |
Dòng 6 nằm ngoài hộp, chỉ dựa vào tiền đề 1 và 2. Ta vừa chứng minh tính bắc cầu (tam đoạn luận giả định) từ quy tắc gốc. Lưu ý: ở dòng 7 (nếu có) không được viết "r" và ghi "dòng 5" — dòng 5 đã nằm trong hộp đóng.
Ví dụ 3: phản chứng — chứng minh modus tollens từ quy tắc gốc
Tiền đề: p → q và ¬q. Cần: ¬p. Ý tưởng: giả sử p, đi tới mâu thuẫn.
| Dòng | Công thức | Lý do |
|---|---|---|
| 1 | p → q | Tiền đề |
| 2 | ¬q | Tiền đề |
| 3 | │ p | Giả định |
| 4 | │ q | Khử → (1, 3) |
| 5 | │ q ∧ ¬q | Nhập ∧ (4, 2) |
| 6 | ¬p | Nhập ¬ (3–5) |
Dòng 5 dùng dòng 2 nằm ngoài hộp — được phép, vì dòng 2 thuộc tầng ngoài, vẫn đang "mở". Chiều ngược lại mới bị cấm: dùng dòng trong hộp đã đóng.
Ví dụ 4: hai hộp lồng nhau
Câu chuyện: "Nếu có vé và có xe đưa đón thì cả nhóm đi xem chung kết." Chứng minh: "Nếu có vé thì: hễ có xe đưa đón là cả nhóm đi xem." Bằng ký hiệu: từ (p ∧ q) → r chứng minh p → (q → r).
| Dòng | Công thức | Lý do |
|---|---|---|
| 1 | (p ∧ q) → r | Tiền đề |
| 2 | │ p | Giả định |
| 3 | │ │ q | Giả định |
| 4 | │ │ p ∧ q | Nhập ∧ (2, 3) |
| 5 | │ │ r | Khử → (1, 4) |
| 6 | │ q → r | Nhập → (3–5) |
| 7 | p → (q → r) | Nhập → (2–6) |
Hộp trong phải đóng trước hộp ngoài, giống ngoặc đơn trong biểu thức. Chiến thuật chung khi kết luận có dạng A → B: giả định A, nhắm tới B. Kết luận có dạng ¬A: giả định A, nhắm tới mâu thuẫn. Kết luận có dạng A ∧ B: chứng minh riêng A và B. Còn khi tiền đề có dạng A ∨ B: chia hai hộp, mỗi hộp một trường hợp.
Bài tập
- Từ p ∧ q, chứng minh q ∧ p. Đáp án: 1. p ∧ q (tiền đề); 2. p (khử ∧, 1); 3. q (khử ∧, 1); 4. q ∧ p (nhập ∧, 3, 2).
- Từ p → (q → r) và q, chứng minh p → r. Đáp án: 1. p → (q → r) (tiền đề); 2. q (tiền đề); 3. │p (giả định); 4. │q → r (khử →, 1, 3); 5. │r (khử →, 4, 2); 6. p → r (nhập →, 3–5).
- Từ p → q, chứng minh ¬q → ¬p (luật phản đảo). Đáp án: 1. p → q (tiền đề); 2. │¬q (giả định); 3. │ │p (giả định); 4. │ │q (khử →, 1, 3); 5. │ │q ∧ ¬q (nhập ∧, 4, 2); 6. │¬p (nhập ¬, 3–5); 7. ¬q → ¬p (nhập →, 2–6).
- Từ p ∨ q, p → r, q → r, chứng minh r. Đáp án: 1. p ∨ q; 2. p → r; 3. q → r (tiền đề); 4. │p (giả định); 5. │r (khử →, 2, 4); 6. │q (giả định); 7. │r (khử →, 3, 6); 8. r (khử ∨, 1, 4–5, 6–7). Hai hộp 4–5 và 6–7 là hai hộp riêng, mở – đóng lần lượt.
- Tìm chỗ sai: 1. p → q (tiền đề); 2. │p (giả định); 3. │q (khử →, 1, 2); 4. p → q (nhập →, 2–3); 5. q (lặp lại, 3). Đáp án: Dòng 5 sai — dòng 3 nằm trong hộp đã đóng ở dòng 4. Chỉ từ p → q thì không suy ra được q.
Dùng vào đâu
- Viết lời giải toán rõ ràng: thói quen "mỗi dòng một lý do" làm bài chứng minh hình học, số học dễ chấm và khó sai hơn.
- Môn Logic học, Toán rời rạc ở đại học: dạng bài "chứng minh bằng các quy tắc suy luận" chính là suy diễn tự nhiên, có khi trình bày theo dạng cây thay cho dạng dòng.
- Máy kiểm chứng chứng minh: các công cụ trợ giúp chứng minh trên máy tính kiểm từng bước theo những quy tắc rất gần với bảng ở trên.
- Học tiếp: mở rộng sang logic vị từ (thêm quy tắc cho "mọi" và "có một"); đọc chương suy diễn tự nhiên trong cuốn Introduction to Logic của Irving Copi hoặc giáo trình Logic học đại cương.
Câu hỏi thường gặp
Suy diễn tự nhiên là gì?
Là phương pháp chứng minh trong logic, trong đó mỗi dòng là một công thức kèm lý do: tiền đề, giả định tạm, hoặc kết quả của một quy tắc áp vào các dòng trước. Nó mô phỏng cách người làm toán suy luận từng bước, do Gentzen và Jaśkowski đề xuất năm 1934.
Giả định tạm trong suy diễn tự nhiên dùng để làm gì?
Giả định tạm dùng để chứng minh câu "nếu A thì B" (giả định A, suy ra B), câu phủ định ¬A (giả định A, suy ra mâu thuẫn), hoặc xét từng trường hợp của "A hoặc B". Khi đóng hộp giả định, các dòng bên trong không được dùng tiếp ở bên ngoài.
Suy diễn tự nhiên khác bảng chân trị thế nào?
Bảng chân trị kiểm hợp lệ bằng cách liệt kê mọi trường hợp, nên dài gấp đôi với mỗi biến thêm vào. Suy diễn tự nhiên dựng một chuỗi bước có lý do, thường ngắn hơn và cho thấy vì sao kết luận đúng. Với logic mệnh đề cổ điển, hai cách cho cùng kết quả.
Quy tắc nhập và khử là gì?
Mỗi phép nối (và, hoặc, nếu… thì, không) có quy tắc nhập để tạo ra công thức chứa nó và quy tắc khử để dùng công thức đó. Ví dụ khử "nếu… thì" chính là modus ponens, còn nhập "nếu… thì" là chứng minh có điều kiện bằng hộp giả định.