Bạn sẽ học được gì
- Dịch câu ngôn ngữ tự nhiên sang logic mệnh đề và logic vị từ, xác định đúng phạm vi lượng từ
- Xây dựng chứng minh bằng suy diễn tự nhiên (natural deduction) cho logic mệnh đề và logic vị từ
- Xác định một công thức là thỏa được, hằng đúng hay mâu thuẫn bằng bảng chân trị hoặc dạng chuẩn tắc
- Giải thích ý tưởng của SAT solver và ứng dụng logic mệnh đề vào đặc tả phần mềm
- Đọc hiểu một đặc tả bằng logic thời gian tuyến tính (LTL) và nguyên lý kiểm chứng mô hình
Nên học trước
Giới thiệu
Logic cho khoa học máy tính là ngôn ngữ chính xác để phát biểu và chứng minh: một chương trình có đúng đặc tả không, một mạch có bao giờ rơi vào trạng thái lỗi không, một câu suy ra được từ các câu khác hay không. Khác với logic học triết học, môn này luôn hướng tới ứng dụng: đặc tả phần mềm, kiểm chứng mô hình, SAT solver.
Hai tầng ngôn ngữ
- Logic mệnh đề: chỉ có các mệnh đề nguyên tử nối bằng ∧ ∨ ¬ →; đủ mạnh cho mạch số và SAT solver, nhưng không nói được "mọi x" hay "tồn tại x".
- Logic vị từ (bậc nhất): thêm lượng từ ∀/∃ và quan hệ, đủ để phát biểu hầu hết mệnh đề toán học — cái giá phải trả là mất tính quyết định được, không có thuật toán luôn dừng để kiểm tra tính hằng đúng.
Cú pháp, ngữ nghĩa và chứng minh — ba việc tách biệt
Một công thức có ba mặt: viết đúng cú pháp (là công thức hợp lệ), có ý nghĩa gì (đúng/sai trong một mô hình cụ thể), và chứng minh được từ tiên đề nào (suy diễn tự nhiên). Định lý đúng đắn (soundness) và đầy đủ (completeness) nối hai mặt sau: mọi điều chứng minh được đều đúng về mặt ngữ nghĩa, và ngược lại.
Ứng dụng kéo lý thuyết lại gần thực tế
Đừng dừng ở logic thuần túy — hãy nối mỗi khái niệm với công cụ thật: bảng chân trị dẫn tới SAT solver, suy diễn tự nhiên dẫn tới trợ lý chứng minh, và logic thời gian dẫn tới model checker như NuSMV dùng kiểm tra mạch, giao thức mạng.
Giáo trình & sách tham khảo
Xem tất cả trong tab SáchGiáo trình chính
forall x: Calgary — An Introduction to Formal Logic
Aaron Thomas-Bolduc, Richard Zach và 2 tác giả khác
Vì sao chọn: Giáo trình mở, miễn phí hoàn toàn (CC BY), trình bày rất rõ ràng và có kèm bài tập từ hệ quả/tính hợp lệ tới logic mệnh đề, logic vị từ và suy diễn tự nhiên. Chọn làm sách chính vì phù hợp người mới bắt đầu và không tốn chi phí.
Nên đọc: Phần I Truth-Functional Propositional Logic, Phần II First-Order Logic, hệ suy diễn tự nhiên kiểu Fitch
Logic in Computer Science: Modelling and Reasoning about Systems
Michael Huth, Mark Ryan · 2004 · Bản thứ 2
Sách hướng thẳng vào ứng dụng khoa học máy tính: sau mệnh đề và vị từ là các chương về SAT solver, kiểm chứng mô hình và kiểm chứng chương trình — đúng phần nâng cao của lộ trình này mà forall x không có. Bản tiếng Anh, không có bản đọc miễn phí hợp pháp.
Nên đọc: Chương 1 Propositional Logic, Chương 2 Predicate Logic, Chương 3 Verification by Model Checking, Chương 4 Program Verification
Các bước học
Đăng nhập để đánh dấu các bước đã hoàn thành.
Bước 1: Logic mệnh đề: cú pháp, ngữ nghĩa và bảng chân trị
khoảng 6 giờHọc cách dịch câu tiếng Việt/Anh sang công thức mệnh đề, xây bảng chân trị và xác định thỏa được/hằng đúng. Dịch 5 câu đặc tả phần mềm đơn giản (ví dụ điều kiện đăng nhập hợp lệ) sang logic mệnh đề rồi lập bảng chân trị kiểm tra tính nhất quán.
- Đọc: Phần Truth-Functional Propositional Logic (TFL) — forall x: Calgary — An Introduction to Formal Logic
- Đọc: Chương 1 Propositional Logic — Logic in Computer Science: Modelling and Reasoning about Systems
Bước 2: Suy diễn tự nhiên và chứng minh
khoảng 7 giờHọc hệ quy tắc suy diễn tự nhiên kiểu Fitch cho logic mệnh đề: giới thiệu/loại bỏ cho từng liên từ. Tự chứng minh 5 định lý mệnh đề cơ bản (như luật De Morgan, luật phản chứng) bằng suy diễn tự nhiên, không tra bảng chân trị.
- Đọc: Phần Fitch-style natural deduction cho TFL — forall x: Calgary — An Introduction to Formal Logic
- Đọc: Chương 1.2 Natural Deduction — Logic in Computer Science: Modelling and Reasoning about Systems
Bước 3: Logic vị từ bậc nhất
khoảng 8 giờHọc cú pháp, ngữ nghĩa (mô hình) và suy diễn tự nhiên cho logic vị từ, gồm cả biến tự do/ràng buộc và phép thế. Dịch 5 định lý toán học quen thuộc (như 'mọi số nguyên tố lớn hơn 2 đều lẻ') sang logic vị từ bậc nhất và xác định miền, vị từ cần dùng.
- Đọc: Phần First-Order Logic (FOL) with identity — forall x: Calgary — An Introduction to Formal Logic
- Đọc: Chương 2 Predicate Logic — Logic in Computer Science: Modelling and Reasoning about Systems
Bước 4: Dạng chuẩn tắc và SAT solver
khoảng 6 giờHọc cách đưa công thức về CNF, mệnh đề Horn và ý tưởng của các thuật toán SAT solver cơ bản (đơn vị lan truyền, tách trường hợp). Cài đặt một SAT solver đơn giản kiểu DPLL và chạy thử trên bài toán tô màu đồ thị 4 màu nhỏ được mã hóa thành CNF.
- Đọc: Chương 1.5–1.6 Normal Forms và SAT Solvers — Logic in Computer Science: Modelling and Reasoning about Systems
Bước 5: Máy trạng thái, bất biến và kiểm chứng mô hình
khoảng 8 giờHọc cách mô hình hóa hệ thống bằng máy trạng thái hữu hạn, viết bất biến, rồi học cú pháp/ngữ nghĩa LTL và thuật toán kiểm chứng mô hình. Mô hình hóa một giao thức loại trừ lẫn nhau (mutual exclusion) đơn giản bằng máy trạng thái, viết bất biến an toàn và kiểm tra bằng một model checker như NuSMV.
- Đọc: Chương 2.7 Micromodels of Software và Chương 3 Verification by Model Checking — Logic in Computer Science: Modelling and Reasoning about Systems
Khái niệm chính
- Logic mệnh đề (Propositional logic)
- Ngôn ngữ hình thức với các mệnh đề nguyên tử và liên từ ∧ ∨ ¬ → ↔; ngữ nghĩa cho bằng bảng chân trị.
- Logic vị từ bậc nhất (Predicate logic)
- Mở rộng logic mệnh đề với vị từ, hàm và lượng từ ∀ (mọi) / ∃ (tồn tại) trên một miền đối tượng.
- Suy diễn tự nhiên (Natural deduction)
- Hệ thống quy tắc chứng minh với luật giới thiệu/loại bỏ cho từng liên từ, mô phỏng cách con người lập luận từng bước.
- Đúng đắn & Đầy đủ (Soundness & Completeness)
- Đúng đắn: mọi công thức chứng minh được đều hằng đúng về ngữ nghĩa. Đầy đủ: mọi công thức hằng đúng đều chứng minh được.
- Dạng chuẩn tắc hội (CNF) & SAT
- Mọi công thức mệnh đề đưa được về dạng hội của các mệnh đề tuyển; bài toán SAT hỏi công thức CNF có thỏa được không — NP-đầy đủ nhưng có solver thực dụng rất nhanh.
- Logic thời gian tuyến tính (LTL)
- Mở rộng logic mệnh đề với toán tử thời gian (luôn luôn, cuối cùng, cho tới khi) để đặc tả tính chất của hệ thống chạy liên tục.
- Kiểm chứng mô hình (Model checking)
- Kỹ thuật tự động kiểm tra một hệ thống hữu hạn trạng thái có thỏa mãn đặc tả logic thời gian hay không bằng cách duyệt toàn bộ không gian trạng thái.
Học xong để làm gì
- Kiểm chứng phần cứng: các hãng chip dùng model checking để đảm bảo mạch không rơi vào trạng thái lỗi trước khi sản xuất
- SAT/SMT solver: giải bài toán lập lịch, cấu hình hệ thống, xác minh chương trình bằng cách quy về logic mệnh đề
- Cơ sở dữ liệu: logic vị từ là nền tảng của ngôn ngữ truy vấn, thể hiện qua mối liên hệ giữa SQL và logic quan hệ
- Trợ lý chứng minh (Coq, Lean, Isabelle) dùng trong nghiên cứu toán học hình thức và xác minh phần mềm quan trọng
- Đặc tả và kiểm thử giao thức mạng, hợp đồng thông minh bằng logic thời gian và model checking
Câu hỏi thường gặp
Logic này khác gì logic đã học ở phổ thông?
Phổ thông chỉ dừng ở suy luận trực giác; môn này hình thức hóa hoàn toàn: định nghĩa chính xác cú pháp, ngữ nghĩa và quy tắc chứng minh để có thể lập trình hoặc để máy kiểm tra được.
Học logic vị từ để làm gì nếu không nghiên cứu toán?
Logic vị từ là nền tảng của truy vấn cơ sở dữ liệu, đặc tả phần mềm hình thức và các ngôn ngữ lập trình logic như Prolog; hiểu nó giúp đọc đặc tả kỹ thuật chính xác hơn.
SAT là NP-đầy đủ thì học SAT solver để làm gì?
NP-đầy đủ chỉ là chặn trường hợp xấu nhất; các SAT solver hiện đại dựa trên CDCL giải được instance hàng triệu biến trong thực tế nhờ khai thác cấu trúc, nên vẫn cực kỳ hữu dụng.
Làm sao để luyện viết chứng minh suy diễn tự nhiên thành thạo?
Làm nhiều bài tập nhỏ, thuộc quy tắc giới thiệu/loại bỏ cho từng liên từ, và luôn nháp sơ đồ chứng minh trên giấy trước khi viết đầy đủ.
