Raymond Smullyan (1919–2017) là nhà logic toán học người Mỹ, tiến sĩ ở Princeton dưới sự hướng dẫn của Alonzo Church, và là người viết sách câu đố logic được đọc nhiều nhất thế kỷ 20. Điểm đặc biệt của ông: những câu đố hiệp sĩ – kẻ nói dối không chỉ để giải trí, mà là bậc thang dẫn người đọc tới các định lý sâu nhất của logic, nhất là định lý bất toàn của Gödel. Bài này đi theo con đường đó: từ phòng giảng tới hòn đảo câu đố.
Một cuộc đời không theo đường thẳng
Smullyan sinh ở Far Rockaway, New York. Ông học phổ thông và đại học rất thất thường, tự học toán, chơi piano đến trình độ biểu diễn và từng kiếm sống bằng nghề ảo thuật. Ông nhận bằng cử nhân ở Đại học Chicago khá muộn, rồi làm tiến sĩ ở Princeton năm 1959 với Alonzo Church — một trong những người đặt nền cho lý thuyết tính toán. Luận án của ông in thành sách Theory of Formal Systems (1961).
Ông dạy ở nhiều trường, lâu nhất ở hệ thống Đại học Thành phố New York và về sau ở Đại học Indiana. Ông làm logic chuyên nghiệp suốt đời: lý thuyết đệ quy, các định lý về sự bất toàn, phương pháp chứng minh. Cuốn sách câu đố đầu tiên ông in khi đã gần sáu mươi tuổi.
Phương pháp bảng: Smullyan trong phòng giảng
Đóng góp học thuật được trích dẫn nhiều nhất của ông là cuốn First-Order Logic (1968), trong đó ông trình bày gọn và thống nhất phương pháp bảng phân tích (analytic tableaux) — ý tưởng có từ giữa thập niên 1950 (Beth, Hintikka) nhưng nhờ Smullyan mới thành công cụ giảng dạy chuẩn.
Ý tưởng: muốn kiểm một lập luận có hợp lệ không, hãy giả sử tiền đề đều đúng mà kết luận sai, rồi tách các câu phức thành các trường hợp. Nếu mọi nhánh đều dẫn tới mâu thuẫn ("đóng"), lập luận hợp lệ. Nếu còn một nhánh không mâu thuẫn ("mở"), nhánh ấy chính là phản ví dụ. Đây chính là lối "giả sử từng trường hợp" quen thuộc của người giải câu đố nói thật – nói dối.
Ví dụ 1 — modus tollens: từ "nếu trời mưa thì sân ướt" (p → q, đọc "nếu p thì q") và "sân không ướt" (¬q, ¬ đọc "không"), suy ra "trời không mưa" (¬p).
- Giả sử: p → q đúng; q sai; và kết luận ¬p sai, tức p đúng.
- p → q đúng nghĩa là: hoặc p sai, hoặc q đúng. Tách hai nhánh.
- Nhánh trái: p sai — mâu thuẫn với p đúng ở bước 1. Đóng.
- Nhánh phải: q đúng — mâu thuẫn với q sai ở bước 1. Đóng.
- Mọi nhánh đóng: lập luận hợp lệ.
Ví dụ 2 — khẳng định hậu kiện: từ p → q và q, suy ra p?
- Giả sử: p → q đúng; q đúng; kết luận p sai.
- Tách p → q: nhánh trái p sai, nhánh phải q đúng.
- Nhánh trái: p sai, q đúng — không mâu thuẫn gì. Nhánh mở.
- Phản ví dụ đọc ra từ nhánh mở: p sai, q đúng. Thử lại: "nếu trời mưa thì sân ướt" vẫn đúng (vế trước sai), "sân ướt" đúng (vì vừa tưới cây), nhưng "trời mưa" sai. Lập luận không hợp lệ.
Từ hòn đảo tới Gödel
Năm 1978, Smullyan in What Is the Name of This Book?, nơi lần đầu xuất hiện hòn đảo của hiệp sĩ (luôn nói thật) và kẻ bịp (luôn nói dối), cùng hộp của Portia, Sư Tử và Kỳ Lân. Các dạng câu đố ấy đã có nhiều bài riêng trong danh mục Đảo hiệp sĩ & kẻ nói dối của wiki này. Điều ít người để ý là phần cuối sách: chuỗi câu đố ở đó dẫn người đọc tới ý tưởng của Kurt Gödel. Các cuốn sau đi sâu hơn nữa.
| Năm | Sách | Ý tưởng logic ẩn sau câu đố |
|---|---|---|
| 1978 | What Is the Name of This Book? | Hiệp sĩ – kẻ bịp, tự quy chiếu, phác thảo định lý Gödel |
| 1982 | The Lady or the Tiger? | Câu đố cửa phòng, máy in câu và tính bất toàn |
| 1982 | Alice in Puzzle-Land | Câu đố trong khung truyện Alice |
| 1985 | To Mock a Mockingbird | Logic tổ hợp, điểm bất động, nền của lập trình hàm |
| 1987 | Forever Undecided | Logic của niềm tin, định lý bất toàn thứ hai |
Câu đố: lời mà nhà logic không bao giờ tin được
Bản sau đây viết theo tinh thần Forever Undecided. Một nhà logic đến đảo; ông ấy chính xác: không bao giờ tin một điều sai. Một người dân đảo (hiệp sĩ hoặc kẻ bịp) nói với ông: «Ông sẽ không bao giờ tin rằng người đang nói với ông đây là hiệp sĩ.»
- Giả sử người nói là kẻ bịp. Câu nói sai, tức là đến một lúc nào đó nhà logic sẽ tin người này là hiệp sĩ. Nhưng người này là kẻ bịp, nên nhà logic tin một điều sai — trái với giả thiết ông chính xác. Loại.
- Vậy người nói là hiệp sĩ. Câu nói đúng: nhà logic không bao giờ tin người này là hiệp sĩ.
Kết luận lạ lùng: người nói là hiệp sĩ, chúng ta biết điều đó, nhưng chính nhà logic chính xác kia không bao giờ tin được. Thay "nhà logic" bằng "một hệ tiên đề nhất quán", thay "tin" bằng "chứng minh được", ta có hình ảnh của định lý bất toàn thứ nhất: có câu đúng mà hệ không chứng minh được.
Còn một tầng nữa. Lập luận trên dùng một tiền đề: "nhà logic chính xác". Nếu nhà logic tự tin rằng mình chính xác và suy luận giỏi như ta, ông sẽ đi đúng các bước trên, kết luận "người này là hiệp sĩ" — và thế là tin điều mà câu nói bảo ông không bao giờ tin. Vậy một nhà logic chính xác, suy luận tốt, không thể tin rằng chính mình chính xác. Đó là hình ảnh của định lý bất toàn thứ hai: một hệ nhất quán đủ mạnh không chứng minh được tính nhất quán của chính nó. (Định lý Gödel có bài đầy đủ ở site toán học AI của hệ.)
Cỗ máy in câu
Smullyan hay kể định lý Gödel qua hình ảnh một cỗ máy in ra các câu. Đây là một bản rút gọn. Máy chỉ dùng ba ký hiệu P, N, *. Với X là một dãy ký hiệu bất kỳ:
- "PX" nghĩa là: X được máy in ra.
- "NPX" nghĩa là: X không bao giờ được in.
- "P*X" nghĩa là: XX (X viết hai lần liền) được in ra.
- "NP*X" nghĩa là: XX không bao giờ được in.
Máy chính xác: câu nào nó in ra cũng đúng. Hãy tìm một câu đúng mà máy không bao giờ in.
Lời giải. Xét câu NP*NP*. Nó có dạng NP*X với X = NP*. Theo quy ước, nó nói: "XX không bao giờ được in", mà XX = NP*NP* — chính nó. Vậy câu này nói: "câu này không bao giờ được in".
- Nếu máy in nó, thì điều nó nói sai — máy đã in một câu sai, trái với tính chính xác. Loại.
- Vậy máy không in nó, và điều nó nói là đúng.
Ta có một câu đúng mà máy không in — lõi của lập luận Gödel, không cần một ký hiệu số học nào. Phần khó trong công trình thật của Gödel là làm cho số học "tự nói về mình" như quy ước P, N, * ở đây; Smullyan cho người đọc thấy cái lõi trước, phần kỹ thuật sau.
Những con chim của Smullyan
Trong To Mock a Mockingbird, Smullyan dựng một khu rừng chim: gọi tên chim B cho chim A nghe, A đáp lại bằng tên một con chim, ký hiệu AB. Chim nhại M là con đáp lại tên x bằng xx (gọi lại chính x trước tên x). Ta nói A "thích" B nếu AB = B. Câu đố đầu tiên: nếu rừng có chim nhại, và với hai chim A, B bất kỳ luôn có chim C sao cho Cx = A(Bx) với mọi x, thì mọi con chim đều thích ít nhất một con.
Chứng minh. Cho A bất kỳ. Lấy C sao cho Cx = A(Mx) với mọi x. Thay x = C: CC = A(MC) = A(CC), vì MC = CC. Vậy A thích con chim CC. Xong.
Đằng sau là logic tổ hợp và "định lý điểm bất động" — nền tảng của các ngôn ngữ lập trình hàm, nơi một hàm có thể gọi lại chính nó.
Mốc thời gian
- 1919: sinh ở Far Rockaway, New York.
- 1959: tiến sĩ Princeton, hướng dẫn bởi Alonzo Church.
- 1961: Theory of Formal Systems.
- 1968: First-Order Logic với phương pháp bảng.
- 1978–1987: loạt sách câu đố từ What Is the Name of This Book? tới Forever Undecided.
- 2017: mất ở tuổi 97.
Dùng vào đâu
- Học logic: phương pháp bảng là cách kiểm lập luận nhanh, có hệ thống, dùng được ngay trong bài tập Logic học đại cương.
- Hiểu Gödel: đọc hai câu đố ở trên trước khi đọc bài toán học chính thức — cái lõi sẽ không còn bí ẩn.
- Lập trình: chim nhại và điểm bất động là cửa vào đệ quy và lập trình hàm.
- Học tiếp: đọc What Is the Name of This Book? từ đầu tới cuối, đừng dừng ở các câu đố dễ; ai thích toán thì sang Forever Undecided.
Câu hỏi thường gặp
Raymond Smullyan là ai?
Raymond Smullyan (1919–2017) là nhà logic toán học người Mỹ, tiến sĩ Princeton năm 1959 dưới sự hướng dẫn của Alonzo Church. Ông nổi tiếng với các sách câu đố logic như What Is the Name of This Book? (1978) và với phương pháp bảng phân tích trong cuốn First-Order Logic (1968).
Smullyan đã liên hệ câu đố với định lý Gödel thế nào?
Ông dựng các câu đố tự quy chiếu, như người dân đảo nói «Ông sẽ không bao giờ tin rằng người đang nói với ông đây là hiệp sĩ» hay cỗ máy in câu "câu này không bao giờ được in". Lời giải cho thấy có điều đúng mà một hệ chính xác không bao giờ khẳng định được — đúng lõi của định lý bất toàn.
Phương pháp bảng phân tích là gì?
Đó là cách kiểm lập luận bằng cách giả sử tiền đề đúng, kết luận sai, rồi tách các câu phức thành nhánh. Nếu mọi nhánh mâu thuẫn, lập luận hợp lệ; nếu còn nhánh không mâu thuẫn, nhánh ấy cho phản ví dụ. Smullyan trình bày phương pháp này thành chuẩn trong First-Order Logic năm 1968.
To Mock a Mockingbird nói về gì?
Cuốn sách năm 1985 dùng hình ảnh những con chim đáp lại tên nhau để giới thiệu logic tổ hợp. Chim nhại, chim thích một con chim khác, là cách nói vui của các khái niệm như tự áp dụng và điểm bất động — nền tảng của lập trình hàm và lý thuyết tính toán.
Nên đọc sách nào của Smullyan trước?
Người mới nên bắt đầu với What Is the Name of This Book? (1978), vì sách đi từ câu đố dễ tới phác thảo định lý Gödel. Sau đó là The Lady or the Tiger? (1982). Ai muốn đi sâu vào logic của niềm tin và định lý bất toàn thứ hai thì đọc Forever Undecided (1987).