Toán rời rạc, logic và chứng minh: thứ toán mà máy tính thật sự dùng
Vì sao người học khoa học máy tính cần logic, quy nạp, đếm, đồ thị và số học đồng dư — và vì sao 'chạy thử thấy đúng' không bao giờ đủ.
Ban biên tập OpenER
Cập nhật 09/11/2026 · 16 phút đọc · CC BY 4.0
Nhiều người vào ngành công nghệ thông tin với một nỗi lo: "Mình học toán không giỏi, liệu có theo được không?" Thường thì nỗi lo đó đến từ ký ức về đạo hàm, tích phân, những đường cong trơn tru trên mặt phẳng. Tin vui là phần lớn toán mà máy tính dùng hằng ngày không phải loại đó.
Máy tính không biết tới đường cong. Nó chỉ biết những thứ đếm được từng cái một: bit 0 và 1, ô nhớ thứ 1, thứ 2, thứ 3, bước lặp thứ n, máy chủ nối với máy chủ. Thứ toán học về những đối tượng tách rời nhau như vậy gọi là toán rời rạc (discrete mathematics) — logic, chứng minh, quy nạp, đếm, đồ thị, số nguyên. Nó ít công thức hơn bạn tưởng, và nhiều suy nghĩ hơn bạn tưởng. Nó cũng là nền của gần như mọi môn còn lại trong lộ trình này.
Trước khi có toán rời rạc trong khoa học máy tính
Phần lớn toán rời rạc già hơn máy tính hàng trăm, hàng nghìn năm — chỉ là ngày xưa nó bị coi như những câu đố lẻ tẻ.
- Khoảng năm 300 trước Công nguyên, Euclid chứng minh có vô số số nguyên tố, và mô tả cách tìm ước chung lớn nhất.
- Năm 1654, Pascal và Fermat trao đổi thư từ về cách chia tiền cược khi một ván bài bị bỏ dở giữa chừng — những lá thư thường được coi là khởi đầu của lý thuyết xác suất.
- Năm 1736, Euler giải bài toán bảy cây cầu ở thành phố Königsberg: có cách nào đi qua mỗi cây cầu đúng một lần rồi quay về không? Ông chứng minh là không, và để làm vậy, ông vứt bỏ mọi chi tiết của bản đồ, chỉ giữ lại "vùng đất" và "cây cầu nối hai vùng". Đó là khởi đầu của lý thuyết đồ thị.
- Năm 1854, George Boole viết về một thứ "đại số của tư duy", trong đó biến chỉ nhận hai giá trị đúng và sai. Gần một trăm năm, nó gần như chỉ là chuyện của triết học và logic.
Bước ngoặt đến năm 1937. Claude Shannon, khi đó là sinh viên cao học ở MIT, viết một luận văn chỉ ra rằng đại số Boole mô tả chính xác mạch điện gồm các công tắc: hai công tắc nối tiếp là phép "và", nối song song là phép "hoặc". Từ đó, thiết kế mạch không còn là mò mẫm mà thành tính toán trên giấy. Một nhánh toán "vô dụng" bỗng thành nền móng của mọi con chip.
Khi máy tính ra đời, người làm phần mềm cũng nhanh chóng nhận ra: họ cần một kiểu toán khác với giải tích. Họ cần đếm xem có bao nhiêu trường hợp, chứng minh một vòng lặp luôn dừng, hiểu cấu trúc của mạng lưới. Dần dần, toán rời rạc thành một môn bắt buộc riêng trong chương trình khoa học máy tính ở các trường đại học.
Thiếu cách suy nghĩ của môn này, người ta làm phần mềm bằng cách chạy thử và hy vọng. Edsger Dijkstra từng tóm lại giới hạn của cách đó bằng một ý nổi tiếng: kiểm thử chỉ cho thấy có lỗi, không bao giờ chứng minh được không có lỗi. Năm 1994, người ta phát hiện bộ xử lý Pentium của Intel chia sai trong một số rất ít trường hợp, do vài ô bị thiếu trong một bảng tra cứu bên trong chip. Lỗi hiếm tới mức hầu như không ai gặp — nhưng Intel phải thu hồi, đổi chip và chịu khoản chi phí khoảng 475 triệu đô la. Sau sự cố này, ngành chip đầu tư mạnh vào kiểm chứng hình thức: chứng minh bằng toán rằng mạch đúng, thay vì chỉ chạy thử.
Đặt cạnh nhau:
Không có toán rời rạc | Có toán rời rạc | |
|---|---|---|
Biết chương trình đúng | Chạy thử vài trường hợp, hy vọng | Chứng minh nó đúng với mọi trường hợp |
Thiết kế mạch số | Mò mẫm, thử từng cách nối | Tính trên giấy bằng đại số Boole |
Ước lượng số trường hợp | Đoán | Đếm chính xác, biết trước bài toán có "nổ" không |
Mạng lưới, quan hệ, phụ thuộc | Mô tả bằng lời, rối | Mô hình bằng đồ thị, dùng lại được hàng trăm định lý |
Bảo mật | Giấu cách làm và hy vọng không ai đoán ra | Dựa trên định lý số học, công khai mà vẫn an toàn |
Ngày nay, thiếu toán rời rạc vẫn để lại dấu vết quen thuộc: một hàm đệ quy chạy mãi không dừng vì quên trường hợp cơ sở; một mật khẩu "rất khó đoán" mà thật ra chỉ có vài triệu khả năng; một hệ thống sinh mã giảm giá ngẫu nhiên rồi bất ngờ phát hiện hai khách hàng nhận trùng mã. Mỗi lỗi đó là một bài trong giáo trình môn này.
Môn này trả lời câu hỏi gì
Môn Toán rời rạc, logic và chứng minh trả lời câu hỏi: làm sao suy luận chặt chẽ về những đối tượng rời rạc — bit, số nguyên, chương trình, mạng lưới — để biết chắc một điều là đúng, thay vì chỉ thấy nó "có vẻ đúng"?
Câu hỏi đó gồm ba phần:
- Ngôn ngữ: viết một nhận định sao cho chính xác, không mơ hồ — đó là logic.
- Công cụ: các cách chứng minh — trực tiếp, phản chứng, quy nạp — và các cách đếm.
- Đối tượng: những cấu trúc mà khoa học máy tính dùng mãi — tập hợp, hàm, quan hệ, đồ thị, số nguyên và phép chia lấy dư, xác suất trên các tập hữu hạn.
Vì sao cần học? Vì đây là môn dạy cách nghĩ, không chỉ dạy kiến thức. Người đã quen chứng minh viết code khác hẳn: họ nghĩ về trường hợp biên trước khi viết, hỏi "điều gì luôn đúng sau mỗi vòng lặp", và nhận ra một lập luận có lỗ hổng trước khi lỗ hổng đó thành lỗi. Và vì gần như mọi môn sau — thuật toán, lý thuyết tính toán, mật mã, học máy — đều nói bằng ngôn ngữ của môn này.
Năm ý tưởng cốt lõi
1. Logic và chứng minh: nói cho chính xác
Câu "mọi số nguyên tố đều là số lẻ" nghe có vẻ đúng. Nhưng số 2 là số nguyên tố và là số chẵn — một phản ví dụ (counterexample) là đủ để bác bỏ cả câu. Ngược lại, để khẳng định một câu bắt đầu bằng "mọi", thử một nghìn ví dụ cũng không đủ; ta cần một chứng minh.
Logic cho ta ngôn ngữ để nói cho chính xác: "và", "hoặc", "không", "nếu… thì…", "với mọi", "tồn tại". Những chữ đó có mặt trong mọi câu lệnh if, mọi điều kiện while, mọi truy vấn cơ sở dữ liệu. Một lỗi kinh điển của người mới học: phủ định của "mọi sinh viên đều qua môn" không phải là "mọi sinh viên đều trượt", mà là "có ít nhất một sinh viên trượt".
Một chứng minh đẹp của Euclid cho thấy sức mạnh của phản chứng (proof by contradiction): giả sử chỉ có hữu hạn số nguyên tố, nhân tất cả chúng lại rồi cộng thêm 1. Số mới này chia cho số nguyên tố nào trong danh sách cũng dư 1, nên nó hoặc là một số nguyên tố mới, hoặc chia hết cho một số nguyên tố nằm ngoài danh sách. Dù trường hợp nào, danh sách cũng thiếu — mâu thuẫn. Vậy có vô số số nguyên tố. Không cần máy tính, không cần thử số nào — và đúng mãi mãi.
2. Quy nạp: anh em sinh đôi của đệ quy và vòng lặp
Hãy tưởng tượng một hàng quân domino vô tận. Nếu bạn chắc chắn hai điều: quân đầu tiên đổ, và quân nào đổ thì quân kế tiếp cũng đổ — thì mọi quân đều đổ. Đó là chứng minh quy nạp (proof by induction).
Ví dụ: tổng 1 + 2 + … + n bằng n(n + 1)/2.
- Bước cơ sở: với n = 1, tổng là 1, và 1 × 2 / 2 = 1. Đúng.
- Bước quy nạp: giả sử công thức đúng với n. Thì tổng tới n + 1 bằng n(n + 1)/2 + (n + 1) = (n + 1)(n + 2)/2 — chính là công thức với n + 1.
Quy nạp quan trọng với người lập trình vì nó chính là cách đệ quy hoạt động. Một hàm đệ quy đúng khi trường hợp cơ sở đúng, và lời gọi nhỏ hơn đúng thì lời gọi lớn hơn cũng đúng:
def tong(n):
if n == 0: # bước cơ sở
return 0
return tong(n - 1) + n # tin rằng tong(n - 1) đúng, rồi dựng tiếpQuên bước cơ sở là quên quân domino đầu tiên: hàm gọi mãi không dừng. Với vòng lặp, ý tưởng tương tự có tên bất biến vòng lặp (loop invariant) — một điều luôn đúng trước và sau mỗi lần lặp, dùng để chứng minh vòng lặp cho kết quả đúng. Người viết thuật toán giỏi nghĩ về bất biến trước khi viết dòng code đầu tiên.
3. Đếm: biết trước bài toán lớn tới đâu
Một mật khẩu 8 ký tự chỉ gồm chữ thường có bao nhiêu khả năng? Mỗi vị trí có 26 lựa chọn, nên có 26⁸ — khoảng 209 tỷ. Nghe nhiều, nhưng một máy đoán mật khẩu mạnh thử được hàng tỷ lần mỗi giây với một số kiểu lưu mật khẩu yếu, nên chỉ mất vài phút. Thêm chữ hoa, chữ số và ký hiệu, dài 12 ký tự, con số nhảy lên khoảng 95¹² — khoảng 540 nghìn tỷ tỷ (5,4 × 10²³). Quy tắc nhân trong tổ hợp là thứ cho bạn biết chính xác mật khẩu cần dài bao nhiêu.
Môn học dạy các công cụ đếm: hoán vị, tổ hợp, nguyên lý bù trừ — và một nguyên lý đơn giản tới mức buồn cười mà mạnh tới bất ngờ: nguyên lý chuồng bồ câu (pigeonhole principle), ở Việt Nam thường gọi là nguyên lý Dirichlet. Nhét 11 con bồ câu vào 10 cái chuồng thì ít nhất một chuồng có hai con. Hệ quả cho người lập trình: một hàm băm (hash function) biến dữ liệu dài tùy ý thành một chuỗi độ dài cố định thì chắc chắn có hai dữ liệu khác nhau cho cùng kết quả — va chạm là điều không tránh được, chỉ có thể làm cho nó hiếm.
Đếm dẫn thẳng tới xác suất. Một câu hỏi nổi tiếng: một lớp cần bao nhiêu người để có hơn 50% khả năng có hai người trùng ngày sinh? Câu trả lời chỉ là 23 — ít hơn nhiều so với trực giác. Đây là nghịch lý ngày sinh (birthday paradox), và nó giải thích vì sao hai khách hàng nhận trùng mã giảm giá sớm hơn bạn nghĩ:
def xac_suat_trung(so_nguoi, so_ngay=365):
khong_trung = 1.0
for i in range(so_nguoi):
khong_trung *= (so_ngay - i) / so_ngay # người thứ i tránh được i ngày đã có
return 1 - khong_trung
print(round(xac_suat_trung(23), 3)) # 0.5074. Đồ thị: bỏ chi tiết, giữ cấu trúc
Bước nhảy của Euler ở Königsberg là bỏ hết bản đồ, chỉ giữ đỉnh (vertex) và cạnh (edge). Ông nhận ra: để đi qua mỗi cây cầu đúng một lần rồi quay về, mỗi vùng đất phải có số cầu chẵn — vào bằng một cầu thì phải ra bằng một cầu khác. Ở Königsberg, cả bốn vùng đều có số cầu lẻ, nên không thể. Một lập luận đếm đơn giản giải quyết bài toán mà thử bao nhiêu đường đi cũng không chắc chắn được.
Đồ thị là cấu trúc dữ liệu mà khoa học máy tính dùng nhiều nhất sau mảng: mạng xã hội, bản đồ, Internet, quan hệ "môn này phải học trước môn kia", lời gọi giữa các hàm trong một chương trình. Môn học dạy những khái niệm và định lý nền: đường đi, chu trình, cây, đồ thị có hướng, tô màu đồ thị. Ví dụ, xếp lịch thi sao cho không sinh viên nào thi hai môn cùng giờ chính là bài toán tô màu đồ thị: mỗi môn là một đỉnh, hai môn có chung sinh viên thì nối cạnh, mỗi màu là một ca thi. Những thuật toán chạy trên đồ thị được học ở môn Thiết kế và phân tích thuật toán; môn này cho bạn ngôn ngữ và các chứng minh để hiểu vì sao chúng đúng.
5. Số học đồng dư: toán của mật mã
Đồng hồ treo tường là một ví dụ quen thuộc của số học đồng dư (modular arithmetic): 10 giờ cộng 5 tiếng là 3 giờ, vì ta chỉ quan tâm phần dư khi chia cho 12. Máy tính làm việc với phần dư suốt: số nguyên 32 bit thực chất là số học theo modulo 2³², phép băm dùng phần dư để chia dữ liệu vào các ô, ngày trong tuần là phần dư khi chia cho 7.
Ứng dụng đẹp nhất là mật mã khóa công khai. Năm 1977, Ron Rivest, Adi Shamir và Leonard Adleman công bố hệ RSA, dựa trên những định lý số học có từ thế kỷ XVII–XVIII của Fermat và Euler. Ý tưởng: nhân hai số nguyên tố lớn thì dễ, nhưng từ tích tách ngược ra hai số đó thì được tin là cực kỳ khó. Với số nhỏ, bạn tự thử được:
p, q = 61, 53 # hai số nguyên tố (thật ngoài đời: mỗi số dài hàng trăm chữ số)
n = p * q # 3233 — công khai
e, d = 17, 2753 # e công khai; d giữ bí mật, tính được nhờ biết p và q
tin = 65
ma_hoa = pow(tin, e, n) # ai cũng mã hóa được bằng (n, e)
giai_ma = pow(ma_hoa, d, n) # chỉ người có d mới giải được
print(ma_hoa, giai_ma) # 2790 65Mỗi lần bạn thấy ổ khóa trên thanh địa chỉ trình duyệt, những định lý về phần dư ba trăm năm tuổi đang làm việc.
Toán rời rạc nằm ở đâu trong chồng tầng
Nếu bạn đã đọc Từ electron đến ứng dụng, máy tính là một chồng tầng trừu tượng. Toán rời rạc không nằm ở một tầng — nó là ngôn ngữ chung của mọi tầng:
- Ở tầng mạch: đại số Boole mô tả cổng logic, bộ cộng, bộ nhớ.
- Ở tầng hệ thống: hệ điều hành và mạng máy tính dùng lý thuyết đồ thị, xác suất và hàng đợi; chứng minh rằng một thuật toán khóa không bao giờ gây bế tắc.
- Ở tầng thuật toán: quy nạp để chứng minh đúng, đếm và công thức truy hồi để phân tích thời gian chạy.
- Ở tầng lý thuyết: lý thuyết tính toán được viết hoàn toàn bằng logic, tập hợp và chứng minh.
Môn này thường học sớm nhất.
Học trước và học sau
· 10 mônCấu trúc dữ liệu và giải thuật
Data Structures and Algorithms
Học sau, dùng lại liên tục.
Thiết kế và phân tích thuật toán
Design and Analysis of Algorithms
Học sau, dùng lại liên tục.
Lý thuyết tính toán
Theory of Computation
Học sau, dùng lại liên tục.
Logic cho khoa học máy tính
Logic for Computer Science
Học sau, dùng lại liên tục.
Phương pháp hình thức
Formal Methods for Software Engineering
Học sau, dùng lại liên tục.
Xem chủ đề trên OpenER: Formal Methods for Software Engineering
Đại số tuyến tính
Linear Algebra
Môn toán "liên tục" bạn sẽ cần thêm cho Machine Learning.
Xác suất và thống kê
Probability and Statistics
Môn toán "liên tục" bạn sẽ cần thêm cho Machine Learning.
Học máy
Machine Learning
Học sau, cần thêm Đại số tuyến tính và Xác suất và thống kê.
Ứng dụng thật và nghề nghiệp
Toán rời rạc hiếm khi là tên một công việc, nhưng nó có mặt trong rất nhiều công việc:
- Kỹ sư phần mềm: viết điều kiện logic đúng, thiết kế đệ quy, ước lượng số trường hợp kiểm thử, hiểu vì sao một cấu trúc dữ liệu nhanh.
- Bảo mật và mật mã: độ mạnh của mật khẩu, hàm băm, chữ ký số, giao thức an toàn — tất cả là đếm, xác suất và số học.
- Thiết kế chip và kiểm chứng hình thức: đại số Boole, logic và chứng minh tự động — nghề có nhu cầu tăng mạnh từ sau sự cố Pentium.
- Cơ sở dữ liệu: ngôn ngữ truy vấn SQL dựa trên logic và lý thuyết tập hợp.
- Dữ liệu và AI: xác suất, đồ thị tri thức, mạng lưới quan hệ.
- Lập trình thi đấu và phỏng vấn kỹ thuật: rất nhiều bài là bài đếm, bài đồ thị hay bài quy nạp đội lốt bài lập trình.
- Nghiên cứu khoa học máy tính lý thuyết.
Học xong làm được gì, bắt đầu từ đâu
Sau môn này bạn có thể:
- đọc và viết chứng minh — trực tiếp, phản chứng, quy nạp — và tìm ra chỗ sai trong một lập luận "có vẻ đúng";
- dùng quy nạp để viết và kiểm tra hàm đệ quy, bất biến để kiểm tra vòng lặp;
- đếm số trường hợp của một bài toán, ước lượng độ mạnh của mật khẩu hay khả năng va chạm của mã ngẫu nhiên;
- mô hình một bài toán thực tế bằng đồ thị;
- hiểu vì sao RSA hoạt động, và tự tính được một ví dụ nhỏ.
Nên biết trước: đại số ở mức phổ thông, và quan trọng hơn, kiên nhẫn. Không cần giỏi giải tích. Nhiều người "không giỏi toán" ở phổ thông lại thích môn này, vì nó cần suy luận nhiều hơn tính toán.
Bắt đầu trên OpenER: trang chủ đề Mathematics 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. Lời khuyên cho môn này: tự viết chứng minh, rồi cho người khác đọc. Một chứng minh chỉ thật sự đúng khi một người khác — hoặc chính bạn ba ngày sau — đọc mà không thấy chỗ nào phải "tin".
Tài liệu tham khảo
- Eric Lehman, F. Thomson Leighton, Albert R. Meyer — Mathematics for Computer Science, giáo trình của MIT, đọc miễn phí.
- MIT 6.042J / 6.1200J Mathematics for Computer Science — bài giảng mở trên MIT OpenCourseWare.
- Kenneth H. Rosen — Discrete Mathematics and Its Applications.
- Daniel J. Velleman — How to Prove It: A Structured Approach — dành riêng cho việc học cách chứng minh.
- UC Berkeley CS 70 Discrete Mathematics and Probability Theory; Stanford CS 103 Mathematical Foundations of Computing.