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

Trước khi logic thành cỗ máy

Logic cho khoa học máy tính: khi suy luận thành cỗ máy

Logic như bộ máy làm việc của tin học: bài toán SAT và DPLL, lượng từ, hợp giải và Prolog, giới hạn của suy luận tự động — và nên bắt đầu học từ đâu.

Ban biên tập OpenER

Cập nhật 18/11/2026 · 19 phút đọc · CC BY 4.0

Bạn gõ lệnh cài một thư viện, và trình quản lý gói báo lỗi: hai thư viện bạn cần đòi hai phiên bản khác nhau của cùng một thư viện thứ ba. Trong vài giây trước đó, máy đã giải một câu đố: chọn phiên bản cho hàng trăm gói sao cho mọi điều kiện kiểu "gói A cần gói B từ bản 2 trở lên", "gói C không chạy chung với gói D" đều thỏa — hoặc chứng minh không có cách nào. Một số trình quản lý gói, như DNF của Fedora, conda hay Composer của PHP, giao việc này cho một bộ giải SAT (SAT solver): chương trình tìm cách gán đúng, sai cho các biến để một công thức logic thành đúng.

Câu đố đó không viết bằng Python hay Java, mà bằng logic. Trong bài Toán rời rạc, logic và chứng minh, logic là ngôn ngữ để người suy luận cho chặt. Môn Logic cho khoa học máy tính (Logic for Computer Science) đi thêm một bước: coi logic là thứ máy đọc, máy giải và máy chứng minh — động cơ bên trong bộ giải SAT, ngôn ngữ Prolog, công cụ kiểm chứng chip, phần suy luận kiểu (type inference) của trình biên dịch.

Trước khi logic thành cỗ máy

Hơn hai nghìn năm, từ Aristotle trở đi, logic là nghệ thuật tranh luận cho đúng. Năm 1854, Boole biến "và, hoặc, không" thành đại số — chuyện đã kể trong bài Toán rời rạc. Nhưng đại số đó chưa nói được "với mọi" hay "tồn tại", nên chưa viết nổi một câu toán học bình thường như "số nào cũng có một số lớn hơn nó". Từ đó tới bộ giải SAT trong trình quản lý gói là một chuỗi bước:

  1. Frege, 1879. Gottlob Frege công bố Begriffsschrift ("chữ viết khái niệm"): ngôn ngữ hình thức đầu tiên có biến và lượng từ (quantifier), với quy tắc suy diễn chặt tới mức kiểm một chứng minh chỉ còn là việc so ký hiệu.
  2. Hilbert, thập niên 1920. David Hilbert muốn viết cả toán học thành hệ hình thức, chứng minh hệ ấy không mâu thuẫn, và tìm một thủ tục máy móc quyết định mọi mệnh đề. Năm 1929, Kurt Gödel chứng minh tin tốt: trong logic vị từ bậc nhất (first-order logic), công thức nào luôn đúng cũng có chứng minh — định lý đầy đủ (completeness theorem). Tin xấu năm 1931 và 1936 đã kể trong bài Lý thuyết tính toán.
  3. Herbrand và Gentzen, 1930–1935. Jacques Herbrand chỉ ra rằng muốn bác bỏ một công thức có lượng từ, chỉ cần tìm hữu hạn trường hợp cụ thể làm nó mâu thuẫn — tức là quy về thứ máy thử được. Gerhard Gentzen sắp xếp chứng minh thành một cấu trúc đủ đều để dò ngược từ kết luận về giả thiết.
  4. Máy bắt tay vào chứng minh, 1960–1965. Martin Davis và Hilary Putnam (1960) dựa trên ý của Herbrand viết một thủ tục cho máy; chạy thật, nó ngốn hết bộ nhớ. Năm 1962, Davis cùng George Logemann và Donald Loveland thay bước tốn bộ nhớ bằng "đoán rồi quay lui" — thủ tục DPLL, đến nay vẫn là bộ xương của các bộ giải SAT. Năm 1965, John Alan Robinson công bố hợp giải (resolution) cùng thuật toán hợp nhất (unification): một quy tắc suy diễn duy nhất, đủ cho máy chứng minh trong logic vị từ.
  5. Prolog, 1972. Ở Marseille, Alain Colmerauer và Philippe Roussel làm ra Prolog; Robert Kowalski ở Edinburgh cho nó cách đọc: một tập công thức logic chính là một chương trình.
  6. Tin xấu, rồi tin tốt bất ngờ. Bài báo năm 1971 của Stephen Cook — tên là "Độ phức tạp của các thủ tục chứng minh định lý" — chỉ ra SAT là bài toán NP-đầy đủ (NP-complete) đầu tiên (xem bài Thiết kế và phân tích thuật toán): chưa ai biết thuật toán nhanh cho mọi trường hợp. Vậy mà GRASP (1996) rồi Chaff (2001) làm bộ giải nhanh lên hẳn; ngày nay chúng xử lý những công thức công nghiệp có khi tới hàng triệu biến. Năm 2008, Microsoft Research công bố Z3, một bộ giải SMT (satisfiability modulo theories) biết thêm cả số học.

Đặt cạnh nhau:

Lập luận bằng lời
Logic hình thức có máy giải
Một điều kiện phức tạp
Hai người đọc, hai cách hiểu
Một công thức, đúng một nghĩa
Kiểm một chứng minh
Tin người viết, hoặc đọc lại nhiều tuần
Máy kiểm từng bước
Thỏa nhiều ràng buộc cùng lúc
Thử tay, bỏ cuộc khi quá nhiều
Giao cho bộ giải, kể cả hàng triệu ràng buộc
"Có cách nào không?"
Không tìm ra thì không biết là không có hay chưa thấy
Bộ giải trả "không thỏa được": chứng minh là không có

Thế giới "chưa có logic hình thức" vẫn ở ngay quanh ta, trong mọi văn bản viết bằng lời. Tấm biển ở quầy thu ngân: "Giảm 10% cho khách là sinh viên hoặc người trên 60 tuổi có thẻ thành viên." Sinh viên không có thẻ được giảm không? Đọc là (sinh viên hoặc trên 60 tuổi) và có thẻ thì không; đọc là sinh viên hoặc (trên 60 tuổi và có thẻ) thì có. Khách và thu ngân cãi nhau mà không ai sai ngữ pháp. Quy chế, hợp đồng đều mang loại mơ hồ này; trong logic, đó là hai công thức khác nhau, và một cặp ngoặc là hết cãi.

Môn này trả lời câu hỏi gì

  1. Nói gì: viết một điều kiện, một luật, một đặc tả thành công thức chỉ có một nghĩa — cú pháp (syntax) và ngữ nghĩa (semantics) của logic mệnh đề và logic vị từ.
  2. Suy ra gì: từ những điều đã biết, điều gì chắc chắn theo sau; và một hệ quy tắc suy diễn có đúng đắn (sound) — chỉ suy ra điều đúng — và đầy đủ (complete) — suy ra được mọi điều đúng — hay không.
  3. Máy làm được tới đâu: thủ tục nào tự quyết định một công thức có thỏa được, có luôn đúng không; nhanh tới mức nào; và khi nào thì không thủ tục nào làm nổi.

Trong môn này, logic còn là đối tượng: ta chứng minh những điều về chính các hệ logic, và viết chương trình làm việc với chúng. Vì sao cần học? Vì ngày càng nhiều công cụ của lập trình viên có một bộ giải logic bên trong; hiểu nó, bạn biết cách mô tả bài toán cho nó và biết khi nào nó không thể trả lời.

Năm ý tưởng cốt lõi

1. Logic mệnh đề và bài toán SAT

Một mệnh đề (proposition) là câu chỉ có thể đúng hoặc sai: "Lan đi", "gói X được cài". Nối chúng bằng "và" (∧), "hoặc" (∨), "không" (¬), ta được công thức. Bài toán SAT (satisfiability — tính thỏa được) hỏi: có cách gán đúng, sai cho các biến để cả công thức đúng không?

Bộ giải SAT thường nhận công thức ở dạng chuẩn hội (conjunctive normal form — CNF): nhiều mệnh đề tuyển (clause) nối bằng "và", mỗi mệnh đề tuyển là vài chữ (literal) — một biến hoặc phủ định của nó — nối bằng "hoặc". Ba người bạn rủ nhau đi đám cưới: Lan đi thì Minh đi; Minh và Hùng không đi cùng; ít nhất một trong Lan, Hùng phải đi. "Nếu A thì B" chính là "không A, hoặc B", nên ta có ba mệnh đề tuyển: (¬Lan ∨ Minh), (¬Minh ∨ ¬Hùng), (Lan ∨ Hùng).

Thử hết thì n biến có 2ⁿ cách gán, mới 30 biến đã hơn một tỷ. DPLL khôn hơn nhờ hai việc. Một là lan truyền đơn vị (unit propagation): mệnh đề tuyển nào chỉ còn một chữ chưa gán mà các chữ khác đều đã sai thì chữ đó buộc phải đúng. Hai là chỉ khi hết đường suy luận mới đoán một biến; gặp mâu thuẫn thì quay lui (backtrack) thử giá trị ngược lại. Bản đồ chơi bằng Python:

python
so_lan_doan = 0

def dpll(menh_de, gan=None):
    """Mỗi mệnh đề là danh sách số nguyên: 3 nghĩa là "x3 đúng", -3 nghĩa là "x3 sai"."""
    global so_lan_doan
    gan = dict(gan or {})
    while True:                                    # lan truyền đơn vị (unit propagation)
        bat_buoc = None
        for md in menh_de:
            if any(gan.get(abs(l)) == (l > 0) for l in md):
                continue                           # mệnh đề này đã đúng
            con_lai = [l for l in md if abs(l) not in gan]
            if not con_lai:
                return None                        # mọi chữ đều sai: mâu thuẫn, quay lui
            if len(con_lai) == 1:
                bat_buoc = con_lai[0]              # chỉ còn một cách cứu mệnh đề này
                break
        if bat_buoc is None:
            break
        gan[abs(bat_buoc)] = bat_buoc > 0
    chua_gan = {abs(l) for md in menh_de for l in md} - gan.keys()
    if not chua_gan:
        return gan                                 # gán đủ mà không mâu thuẫn: thỏa được
    x = min(chua_gan)
    for gia_tri in (True, False):                  # hết đường suy luận thì mới đoán
        so_lan_doan += 1
        kq = dpll(menh_de, {**gan, x: gia_tri})
        if kq is not None:
            return kq
    return None

# 1 = Lan đi, 2 = Minh đi, 3 = Hùng đi
print(dpll([[-1, 2], [-2, -3], [1, 3]]))
print(dpll([[-1, 2], [-2, -3], [1, 3], [-1], [-3]]))   # thêm: Lan không đi, Hùng không đi

Kết quả:

text
{1: True, 2: True, 3: False}
None

Lần đầu, bộ giải tìm ra: Lan và Minh đi, Hùng ở nhà. Lần sau, thêm điều kiện cả Lan lẫn Hùng đều không đi, nó trả None — không thỏa được (unsatisfiable). Bộ giải đã loại hết mọi khả năng, nên "không" là một chứng minh rằng không có cách nào, chứ không phải "tìm chưa ra". Kiểm chứng phần cứng dùng đúng điều này: viết "tồn tại một đầu vào làm mạch tính sai" thành công thức; bộ giải trả "không thỏa được" nghĩa là mạch đúng với mọi đầu vào.

2. Mã hóa: biến bài toán của bạn thành SAT

Sức mạnh thật của SAT là rất nhiều bài toán quy về được nó: xếp lịch, chọn phiên bản gói, kiểm mạch, giải đố. Người dùng không viết thuật toán giải, mà mã hóa (encoding) bài toán thành mệnh đề tuyển, rồi để bộ giải lo phần còn lại.

Thử với sudoku 4×4: điền số 1 tới 4 sao cho không hàng, cột hay khối 2×2 nào trùng số. Mỗi biến là một câu hỏi có hoặc không: "ô hàng h, cột c có chứa số s không?" — 16 ô nhân 4 số là 64 biến. Luật chơi thành ba loại mệnh đề tuyển: ô nào cũng có ít nhất một số; không ô nào có hai số; hai ô cùng hàng, cùng cột hay cùng khối không chứa cùng một số. Dùng lại hàm dpll ở trên:

python
def bien(h, c, s):                                 # biến "ô hàng h, cột c chứa số s + 1"
    return 16 * h + 4 * c + s + 1

nhom = [[(h, c) for c in range(4)] for h in range(4)]                 # 4 hàng
nhom += [[(h, c) for h in range(4)] for c in range(4)]                # 4 cột
nhom += [[(a + i, b + j) for i in (0, 1) for j in (0, 1)]
         for a in (0, 2) for b in (0, 2)]                             # 4 khối 2×2

menh_de = []
for h in range(4):
    for c in range(4):
        menh_de.append([bien(h, c, s) for s in range(4)])             # ô nào cũng có số
        menh_de += [[-bien(h, c, s), -bien(h, c, t)]
                    for s in range(4) for t in range(s + 1, 4)]       # và chỉ một số
for g in nhom:
    for s in range(4):
        menh_de += [[-bien(*g[i], s), -bien(*g[j], s)]
                    for i in range(4) for j in range(i + 1, 4)]       # không trùng trong nhóm

de = ["1...",
      "..3.",
      ".4..",
      "...2"]
for h, dong in enumerate(de):
    for c, kt in enumerate(dong):
        if kt != ".":
            menh_de.append([bien(h, c, int(kt) - 1)])                 # ô cho sẵn

so_lan_doan = 0                                                       # đếm lại từ đầu
gan = dpll(menh_de)
print(len(menh_de), "mệnh đề, đoán", so_lan_doan, "lần")
for h in range(4):
    print(*[s + 1 for c in range(4) for s in range(4) if gan[bien(h, c, s)]])

Kết quả:

text
404 mệnh đề, đoán 0 lần
1 3 2 4
4 2 3 1
2 4 1 3
3 1 4 2

Không dòng code nào nói cách giải sudoku — chỉ có luật chơi. Với đề này, DPLL không phải đoán lần nào: riêng lan truyền đơn vị, đúng kiểu suy luận "ô này chỉ còn một khả năng" của người chơi, đã đủ điền kín lưới. Thêm một mệnh đề cấm đúng lời giải này rồi giải lại, bộ giải trả None: đề có đúng một lời giải.

Bộ giải thật khác bản đồ chơi này ở chỗ khi gặp mâu thuẫn, nó không chỉ quay lui mà còn học: lần ngược xem những lựa chọn nào gây ra mâu thuẫn, ghi lại thành một mệnh đề tuyển mới để không đi vào ngõ cụt đó lần nữa — học mệnh đề từ xung đột (conflict-driven clause learning — CDCL) của GRASP và Chaff. Năm 2016, Marijn Heule, Oliver Kullmann và Victor Marek dùng bộ giải SAT trả lời một câu hỏi Ronald Graham nêu từ thập niên 1980: tô các số 1, 2, 3… bằng hai màu sao cho không bộ ba Pythagore nào (như 3, 4, 5) cùng màu thì được tới đâu? Câu trả lời: được tới 7.824, tới 7.825 thì không — và bản chứng minh phần "không" dài khoảng 200 terabyte.

3. Logic vị từ: "với mọi" và "tồn tại"

Logic mệnh đề không nói được "mọi phòng" hay "có một chìa" nếu không liệt kê từng cái. Logic vị từ bậc nhất thêm vị từ (predicate) như mở(chìa, phòng) và hai lượng từ: ∀ ("với mọi") và ∃ ("tồn tại"). Bài Toán rời rạc đã nói cách phủ định một câu "mọi"; chỗ người học hay vấp hơn là thứ tự lượng từ.

Bà chủ nhà trọ có ba phòng và một chùm chìa. "Phòng nào cũng có chìa mở được" (∀phòng ∃chìa) và "có một chìa mở được mọi phòng" (∃chìa ∀phòng) chỉ đổi chỗ hai cụm từ, nhưng câu sau nói về một chiếc chìa vạn năng. Trên một tập hữu hạn, all và any của Python chính là ∀ và ∃:

python
phong = ["P101", "P102", "P103"]
chia = ["chìa đỏ", "chìa xanh", "chìa vàng"]
mo_duoc = {("chìa đỏ", "P101"), ("chìa xanh", "P102"),
           ("chìa vàng", "P102"), ("chìa vàng", "P103")}

def mo(ch, p):
    return (ch, p) in mo_duoc

# ∀p ∃ch mở(ch, p): phòng nào cũng có chìa mở được
print(all(any(mo(ch, p) for ch in chia) for p in phong))      # True
# ∃ch ∀p mở(ch, p): có một chìa mở được mọi phòng
print(any(all(mo(ch, p) for p in phong) for ch in chia))      # False
# phủ định câu trên: ∀ch ∃p ¬mở(ch, p) — chìa nào cũng có phòng không mở được
for ch in chia:
    print(ch, "không mở được", next(p for p in phong if not mo(ch, p)))

Kết quả:

text
True
False
chìa đỏ không mở được P102
chìa xanh không mở được P101
chìa vàng không mở được P101

Ba dòng cuối là phủ định của câu sau, theo đúng quy tắc: đổi ∃ thành ∀, ∀ thành ∃, rồi phủ định phần bên trong — ¬∃ch ∀p mở(ch, p) tương đương ∀ch ∃p ¬mở(ch, p). Vì là "tồn tại", ta còn có nhân chứng (witness): với mỗi chìa, một phòng cụ thể nó không mở được.

SQL không có chữ "với mọi"; muốn hỏi "khách nào đã mua mọi mặt hàng", người ta viết "không tồn tại mặt hàng nào mà khách này không mua" — hai tầng NOT EXISTS lồng nhau, chính là ∀x P ≡ ¬∃x ¬P. Nhưng để ý: all và any chạy được vì tập phòng hữu hạn. Với "mọi số nguyên" thì không vòng lặp nào chạy hết — mầm của giới hạn ở ý 5.

4. Hợp giải và lập trình logic

Hợp giải, quy tắc duy nhất của Robinson, nói: từ "A hoặc B" và "không B, hoặc C", suy ra "A hoặc C" — B đúng thì C phải đúng, B sai thì A phải đúng. Muốn chứng minh một điều, ta thêm phủ định của nó vào những gì đã biết rồi hợp giải liên tục; ra được mệnh đề rỗng — một mâu thuẫn — thì điều đó đúng. Với logic vị từ, cần thêm hợp nhất: tìm cách thay biến để hai câu trùng nhau, như khớp câu hỏi "ai là bà ngoại của Minh" với luật "?a là bà ngoại của ?c nếu ?a là mẹ của ?b và ?b là mẹ của ?c".

Prolog là hợp giải thu hẹp lại cho chạy nhanh. Nó chỉ dùng luật dạng "kết luận, nếu điều kiện 1 và điều kiện 2…" — mệnh đề Horn (Horn clause) — và suy diễn lùi (backward chaining) từ câu hỏi: muốn chứng minh một mục tiêu, tìm sự kiện khớp với nó, hoặc luật có kết luận khớp với nó rồi chứng minh lần lượt các điều kiện; gặp ngõ cụt thì quay lui. Đây là một Prolog tí hon chạy trên gia phả nhà Minh:

python
from itertools import count

SU_KIEN = [("cha", "ông Tư", "Hùng"), ("mẹ", "bà Năm", "Hùng"),
           ("cha", "ông Sáu", "Lan"), ("mẹ", "bà Bảy", "Lan"),
           ("cha", "Hùng", "Minh"), ("mẹ", "Lan", "Minh"),
           ("cha", "Hùng", "An"), ("mẹ", "Lan", "An")]

LUAT = [  # (kết luận, [điều kiện...]) — chữ bắt đầu bằng "?" là biến
    (("ông nội", "?a", "?c"), [("cha", "?a", "?b"), ("cha", "?b", "?c")]),
    (("bà ngoại", "?a", "?c"), [("mẹ", "?a", "?b"), ("mẹ", "?b", "?c")]),
    (("cha mẹ", "?a", "?b"), [("cha", "?a", "?b")]),
    (("cha mẹ", "?a", "?b"), [("mẹ", "?a", "?b")]),
    (("tổ tiên", "?a", "?c"), [("cha mẹ", "?a", "?c")]),
    (("tổ tiên", "?a", "?c"), [("cha mẹ", "?a", "?b"), ("tổ tiên", "?b", "?c")]),
]

def gia_tri(x, the):                       # lần theo phép thế tới giá trị cuối cùng
    while x in the:
        x = the[x]
    return x

def hop_nhat(a, b, the):                   # hợp nhất (unification) hai câu
    the = dict(the)
    for x, y in zip(a, b):
        x, y = gia_tri(x, the), gia_tri(y, the)
        if x == y:
            continue
        if x.startswith("?"):
            the[x] = y
        elif y.startswith("?"):
            the[y] = x
        else:
            return None                    # hai hằng khác nhau: không khớp
    return the

def doi_ten(cau, n):                       # mỗi lần dùng luật, gắn số mới vào tên biến
    return tuple(f"{x}{n}" if x.startswith("?") else x for x in cau)

dem = count()
def chung_minh(muc_tieu, the):             # suy diễn lùi: giải lần lượt từng mục tiêu
    if not muc_tieu:
        yield the
        return
    dau, con_lai = muc_tieu[0], muc_tieu[1:]
    for sk in SU_KIEN:
        t = hop_nhat(dau, sk, the)
        if t is not None:
            yield from chung_minh(con_lai, t)
    for ket_luan, dieu_kien in LUAT:
        n = next(dem)
        t = hop_nhat(dau, doi_ten(ket_luan, n), the)
        if t is not None:
            yield from chung_minh([doi_ten(d, n) for d in dieu_kien] + con_lai, t)

def hoi(cau):
    bien = [x for x in cau if x.startswith("?")]
    return [tuple(gia_tri(b, t) for b in bien) for t in chung_minh([cau], {})]

print(hoi(("bà ngoại", "?ai", "Minh")))    # bà ngoại của Minh là ai?
print(hoi(("ông nội", "ông Tư", "?chau"))) # ông Tư là ông nội của những ai?
print(hoi(("tổ tiên", "?ai", "An")))

Kết quả:

text
[('bà Bảy',)]
[('Minh',), ('An',)]
[('Hùng',), ('Lan',), ('ông Tư',), ('ông Sáu',), ('bà Năm',), ('bà Bảy',)]

Chương trình không có hàm "tìm bà ngoại" hay "tìm cháu" nào, chỉ có quan hệ và luật. Cùng một luật "ông nội" trả lời được cả hai chiều: biết ông tìm cháu như trên, còn hỏi ngược "ông nội của Minh là ai" thì ra ông Tư. Luật "tổ tiên" gọi lại chính nó như hàm đệ quy, và tìm ra đủ sáu người. Chiều ngược lại — từ sự kiện đi tới kết luận, như các hệ chuyên gia — là chuyện của bài Biểu diễn tri thức và suy luận. Còn phép hợp nhất sống ở một chỗ bất ngờ: trình biên dịch Haskell hay OCaml dùng nó để suy luận kiểu, giải một hệ phương trình giữa các kiểu dữ liệu.

5. Thứ logic không làm được — và cách sống chung

Đổi thứ tự hai điều kiện trong luật "tổ tiên" — về logic, "A và B" với "B và A" là một — rồi hỏi lại:

python
LUAT[-1] = (("tổ tiên", "?a", "?c"), [("tổ tiên", "?a", "?b"), ("cha mẹ", "?b", "?c")])
try:
    print(hoi(("tổ tiên", "?ai", "An")))
except RecursionError:
    print("Không dừng: Python báo RecursionError")

Kết quả: Không dừng: Python báo RecursionError. Để chứng minh "tổ tiên", chương trình đòi chứng minh "tổ tiên" trước, rồi lại "tổ tiên"… mãi mãi. Logic không sai; chiến lược tìm theo chiều sâu mới sai. Người viết Prolog phải để ý thứ tự — Kowalski tóm lại bằng công thức "thuật toán = logic + điều khiển" (1979) — còn Datalog, một dạng Prolog thu hẹp dùng nhiều trong cơ sở dữ liệu và phân tích code, đổi chiến lược để luôn dừng.

Nhưng có một giới hạn không chiến lược nào vượt qua được: bài toán quyết định của Hilbert không có lời giải (Church và Turing, 1936 — bài Lý thuyết tính toán), tức không thuật toán nào luôn trả lời đúng một công thức logic vị từ có luôn đúng hay không. Ghép với định lý đầy đủ của Gödel: nếu công thức luôn đúng, cứ tìm chứng minh có hệ thống thì sẽ thấy; nếu không, việc tìm có thể kéo dài mãi. Logic vị từ là nửa quyết định được (semi-decidable): chữ "có" chắc chắn đến, chữ "không" có thể không bao giờ đến.

Ngành sống chung với giới hạn đó bằng cách chọn những mảnh logic nhỏ hơn mà vẫn quyết định được: logic mệnh đề (dù NP-đầy đủ), số học chỉ có phép cộng trên số nguyên (số học Presburger, 1929), bất đẳng thức tuyến tính, số nguyên cố định số bit. Bộ giải SMT như Z3 ghép một bộ giải SAT kiểu CDCL với thủ tục quyết định cho từng "lý thuyết" ấy, nên trả lời được câu như "có cặp số nguyên 32 bit nào làm phép cộng tràn số mà điều kiện kiểm tra vẫn cho qua không?" — loại câu Dafny, Why3 trong bài Phương pháp hình thức hỏi nó hằng ngày. Ra ngoài những mảnh đó, bộ giải được phép trả lời "không biết" — thật thà hơn là chạy mãi.

Logic nằm ở đâu trong chồng tầng

Trong chồng tầng của bài Từ electron đến ứng dụng, logic có mặt ở cả hai đầu. Ở dưới cùng, mỗi cổng AND, OR, NOT là logic mệnh đề đúc thành silicon — bài Cấu trúc tính toán xây cả bộ xử lý từ đó. Ở trên cao, logic là ngôn ngữ để nói về các tầng: đặc tả cần chứng minh, truy vấn trong hệ cơ sở dữ liệu, hệ thống kiểu trong ngôn ngữ lập trình và trình biên dịch. Ở giữa, bộ giải SAT và SMT thành một tầng dịch vụ: nhiều công cụ dịch câu hỏi của mình thành công thức rồi chuyển xuống.

Đưa lên

Một ngôn ngữ để nói chính xác "điều gì phải đúng", cùng những động cơ — bộ giải SAT, SMT, Prolog — tự tìm lời giải hoặc chứng minh không có lời giải. Tầng trên chỉ cần mô tả bài toán, không phải viết cách giải.

Giấu đi

Cây tìm kiếm khổng lồ phía sau mỗi câu trả lời. Nhưng không giấu được giới hạn: có câu bộ giải mất rất lâu, và có câu nó không bao giờ trả lời được.

Học trước và học sau

· 5 môn

Toán rời rạc, logic và chứng minh

Mathematics for Computer Science

Logic mệnh đề, lượng từ, cách viết chứng minh — ngôn ngữ mà môn này lấy làm đối tượng. Học trước.

Xem chủ đề trên OpenER: Mathematics for Computer Science

Lý thuyết tính toán

Theory of Computation

Máy Turing, bài toán dừng, NP-đầy đủ: vì sao logic vị từ không quyết định được và vì sao SAT khó. Học song song hoặc sau.

Xem chủ đề trên OpenER: Theory of Computation

Phương pháp hình thức

Formal Methods for Software Engineering

Bộ giải SAT, SMT và logic thời gian đem ra chứng minh phần mềm, phần cứng đúng đặc tả. Hướng đi tự nhiên sau môn này.

Xem chủ đề trên OpenER: Formal Methods for Software Engineering

Ngôn ngữ lập trình và trình biên dịch

Programming Languages and Compilers

Hệ thống kiểu, suy luận kiểu bằng hợp nhất, và lập trình logic như một kiểu ngôn ngữ khác hẳn lập trình mệnh lệnh.

Xem chủ đề trên OpenER: Programming Languages and Compilers

Biểu diễn tri thức và suy luận

Knowledge Representation and Reasoning

Dùng logic để máy lưu và suy luận trên tri thức về thế giới: luật, bản thể học (ontology), suy diễn tiến.

Xem chủ đề trên OpenER: Knowledge Representation and Reasoning

Ứng dụng thật và nghề nghiệp

  • Kiểm chứng phần cứng: kiểm hai phiên bản mạch có tương đương không, kiểm tra mô hình có giới hạn (bounded model checking) bằng bộ giải SAT — việc hằng ngày ở các công ty thiết kế chip.
  • Công cụ phần mềm: trình quản lý gói như ở đầu bài; công cụ thực thi ký hiệu (symbolic execution) như KLEE hỏi bộ giải "đầu vào nào đi vào được nhánh này" để tự sinh ca kiểm thử.
  • Đám mây và bảo mật: Amazon Web Services dùng bộ giải SMT (công cụ Zelkova) để kiểm một chính sách phân quyền có vô tình mở dữ liệu cho người ngoài hay không.
  • Phân tích code: CodeQL của GitHub cho viết truy vấn tìm lỗ hổng bằng một ngôn ngữ logic gốc Datalog.

Nghề gắn với môn này: kỹ sư kiểm chứng hình thức, kỹ sư công cụ (trình biên dịch, phân tích tĩnh, bộ giải), kỹ sư bảo mật làm phân tích chương trình, và nghiên cứu về suy luận tự động (automated reasoning).

Học xong làm được gì, bắt đầu từ đâu

Sau môn này bạn có thể:

  • dịch điều kiện đời thường, luật, đặc tả thành công thức logic mệnh đề và logic vị từ, không nhầm thứ tự lượng từ;
  • mã hóa một bài toán tổ hợp thành SAT và giải bằng bộ giải có sẵn;
  • giải thích DPLL và CDCL làm gì, và vì sao bộ giải chạy nhanh trên bài toán thật dù SAT là NP-đầy đủ;
  • chứng minh bằng hợp giải, viết chương trình Prolog nhỏ và hiểu vì sao nó có thể không dừng;
  • phân biệt câu hỏi logic trả lời được với câu hỏi không thuật toán nào trả lời được.

Nên biết trước: logic và chứng minh ở mức môn Toán rời rạc, lập trình Python vững, quen với đệ quy.

Bắt đầu trên OpenER: trang chủ đề Logic for Computer Science có các khóa học đã chọn lọc, và hướng dẫn học gợi ý thứ tự đi qua chúng. Khóa chính là Logic for CS của S. Arun Kumar (IIT Delhi) trên NPTEL: logic mệnh đề, logic vị từ cùng hai định lý đúng đắn và đầy đủ. Introduction to Logic của Stanford trên Coursera có nhiều bài tập tương tác; Logic and Proof của Đại học Cambridge đi thẳng tới SAT, hợp giải, Prolog và SMT. Bước tiếp theo bằng tiếng Việt là khóa Phương pháp hình thức trong Kỹ thuật phần mềm. Lời khuyên: cài một bộ giải thật — Z3 có gói Python z3-solver — rồi mã hóa một bài toán của chính bạn, như lịch trực nhóm hay sơ đồ chỗ ngồi đám cưới.

Tài liệu tham khảo

  • Michael Huth, Mark Ryan — Logic in Computer Science: Modelling and Reasoning about Systems, ấn bản 2, Cambridge University Press.
  • Daniel Kroening, Ofer Strichman — Decision Procedures: An Algorithmic Point of View, Springer — SAT, SMT và các thủ tục quyết định.
  • Armin Biere, Marijn Heule, Hans van Maaren, Toby Walsh (chủ biên) — Handbook of Satisfiability, IOS Press.
  • Leon Sterling, Ehud Shapiro — The Art of Prolog, MIT Press.
  • IIT Delhi — Logic for CS (S. Arun Kumar), khóa học trên NPTEL.
  • Stanford University — Introduction to Logic (Michael Genesereth), khóa học trên Coursera.
  • University of Cambridge — Logic and Proof, ghi chú bài giảng của khoa Khoa học máy tính.
  • J. A. Robinson — "A Machine-Oriented Logic Based on the Resolution Principle", Journal of the ACM, 1965.
  • M. Davis, G. Logemann, D. Loveland — "A Machine Program for Theorem-Proving", Communications of the ACM, 1962.

Ban biên tập OpenER, “Logic cho khoa học máy tính: khi suy luận thành cỗ máy”, OpenER, 2026. Phát hành theo CC BY 4.0: được chia sẻ, chỉnh sửa, kể cả thương mại, miễn ghi công tác giả và dẫn link bài gốc.