Bỏ qua tới nội dung chính

Hướng dẫn học chủ đề

Logic cho khoa học máy tính

Logic for Computer Science

Trung bìnhkhoảng 35 giờ5 bước

Logic học ứng dụng cho khoa học máy tính: logic mệnh đề, logic vị từ — nền tảng cho chứng minh và formal methods.

Bắt đầu học

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ách

Giá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

CC BYCơ bảnTiếng Anh

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

Có phíTrung bìnhTiếng Anh440 trang

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.

  1. 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.

  2. 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ị.

  3. 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.

  4. 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.

  5. 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.

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 đủ.

Chọn nguồn tự học

Nên học sau toán rời rạc cơ bản, làm nhiều bài tập chứng minh để thành thạo.