Bạn sẽ học được gì
- Dùng logic mệnh đề, lượng từ và các kỹ thuật chứng minh cho mệnh đề về tập hợp, ánh xạ và số nguyên
- Mô hình hóa bài toán bằng đồ thị; nhận biết cây, đồ thị phẳng, đồ thị hai phía, đường đi và chu trình Euler
- Áp dụng quy tắc cộng, quy tắc nhân, hoán vị, tổ hợp và nhị thức Newton để giải bài toán đếm
- Dùng nguyên lý bao hàm – loại trừ và chứng minh tổ hợp cho các bài toán đếm phức tạp hơn
- Tìm công thức tổng quát của dãy từ hệ thức truy hồi và chứng minh bằng quy nạp
- So sánh tốc độ tăng của các dãy và liên hệ với độ phức tạp thuật toán
- Làm việc với ước chung lớn nhất, đồng dư và hàm sinh ở mức nhập môn
Nên học trước
Giới thiệu
Toán rời rạc nghiên cứu các đối tượng "đếm được từng cái một": số nguyên, tập hữu hạn, dãy, đồ thị, mệnh đề logic — trái với các đại lượng liên tục của giải tích. Đây là ngôn ngữ toán học của tin học: máy tính chỉ làm việc với dữ liệu rời rạc, nên thuật toán, cấu trúc dữ liệu, cơ sở dữ liệu, mạng máy tính và mật mã học đều xây trên nền toán rời rạc. Ở các trường Việt Nam đây là môn Toán rời rạc bắt buộc của khối CNTT và Toán – Tin; ở MIT là 6.1200J/18.062J Mathematics for Computer Science (trên OCW là 6.042J), ở UC Berkeley là Math 55 và CS 70.
Bốn mạch nội dung chính
Giáo trình chính của lộ trình (Levin, lần xuất bản thứ tư) chia môn học thành bốn mạch, mỗi mạch đồng thời là một dịp luyện một kiểu chứng minh:
- Logic và chứng minh: mệnh đề, phép kéo theo, các luật logic, lượng từ; chứng minh trực tiếp, phản đảo, phản chứng áp dụng cho các cấu trúc rời rạc như tập hợp và ánh xạ.
- Lý thuyết đồ thị: đỉnh, cạnh, bậc, đường đi, chu trình, cây, đồ thị phẳng và công thức Euler, đường đi và chu trình Euler, tô màu đồ thị, ghép cặp trên đồ thị hai phía. Đồ thị là mô hình của mạng xã hội, bản đồ giao thông, mạng máy tính và phụ thuộc giữa các tác vụ.
- Đếm (tổ hợp): quy tắc cộng, quy tắc nhân, hoán vị, tổ hợp, tam giác Pascal và nhị thức Newton, đếm đa tập, nguyên lý bao hàm – loại trừ, chứng minh tổ hợp (đếm cùng một tập theo hai cách) và ứng dụng vào xác suất rời rạc.
- Dãy số và quy nạp: mô tả dãy bằng công thức tổng quát và hệ thức truy hồi, tốc độ tăng của dãy (nền tảng của ký hiệu O lớn khi phân tích thuật toán), dãy đa thức và dãy mũ, quy nạp và quy nạp mạnh.
Hai chương cuối quay lại tập hợp, ánh xạ, quan hệ ở mức chặt chẽ hơn và giới thiệu hàm sinh cùng nhập môn lý thuyết số (chia hết, ước chung lớn nhất, đồng dư) — nền tảng của mật mã khóa công khai.
Vì sao cần học chứng minh trước?
Toán rời rạc ở bậc đại học không chỉ là "làm bài đếm": phần lớn bài tập yêu cầu chứng minh một công thức đếm, một tính chất của đồ thị hay tính đúng của một hệ thức truy hồi. Vì vậy lộ trình đặt Nhập môn chứng minh toán học làm điều kiện trước. Nếu đã học xong chủ đề đó, chương logic và chứng minh sẽ là phần ôn tập nhanh, và bạn có thể dồn thời gian cho đồ thị và đếm.
Cách học hiệu quả
- Tự kiểm tra bằng máy: với mỗi công thức đếm, viết một chương trình nhỏ liệt kê mọi trường hợp với n nhỏ (n = 3, 4, 5) và so với công thức — lỗi đếm trùng hay đếm sót lộ ra ngay.
- Vẽ đồ thị: gần như mọi bài đồ thị đều dễ hơn khi vẽ ra; hãy thử tìm phản ví dụ nhỏ trước khi chứng minh.
- Làm bài có lời giải: giáo trình Levin có gợi ý và lời giải cho một phần bài tập, và bản web có câu hỏi đọc nhanh cuối mỗi mục.
- Xem bài giảng: MIT 6.1200J Mathematics for Computer Science (trên MIT OpenCourseWare là 6.042J) có trọn bộ video và bài tập, đi kèm cuốn sách cùng tên trong danh sách sách của chủ đề.
Sau môn này
Toán rời rạc mở đường cho Tổ hợp và lý thuyết đồ thị, Lý thuyết tính toán, Logic toán, lý thuyết số và mật mã học, cũng như các môn tin học như cấu trúc dữ liệu và giải thuật.
Giáo trình & sách tham khảo
Xem tất cả trong tab SáchGiáo trình chính
Discrete Mathematics: An Open Introduction
Oscar Levin · 2025 · Bản thứ 4
Vì sao chọn: Giáo trình mở, miễn phí (bản web và PDF), được Viện Toán học Hoa Kỳ (AIM) chấp thuận trong chương trình giáo trình mở. Lần xuất bản thứ tư sắp xếp lại nội dung: logic và chứng minh trước, luyện chứng minh qua đồ thị, rồi đếm và dãy số — đúng thứ tự các bước của lộ trình. Văn phong thân thiện, có câu hỏi đọc nhanh và lời giải chọn lọc.
Nên đọc: Chương 0–6
Discrete Mathematics and Its Applications
Kenneth H. Rosen · 2018 · Bản thứ 8
Giáo trình toán rời rạc phổ biến nhất thế giới cho sinh viên tin học (McGraw-Hill, trả phí), hàng nghìn bài tập ở mọi mức độ. Dùng để luyện thêm hoặc tra cứu các chủ đề Levin trình bày ngắn, như quan hệ, thuật toán và lý thuyết số.
Mathematics for Computer Science
Eric Lehman, F. Thomson Leighton, Albert R. Meyer · 2018
Giáo trình miễn phí của MIT dùng cho môn 6.1200J (trên OCW là 6.042J), sâu hơn về chứng minh, lý thuyết số, đồ thị và xác suất rời rạc, kèm nhiều bài toán thú vị. Đọc song song với bài giảng của môn này trên MIT OpenCourseWare khi muốn đi xa hơn giáo trình chính.
Các bước học
Đăng nhập để đánh dấu các bước đã hoàn thành.
Bước 1: Logic, chứng minh và cấu trúc rời rạc
khoảng 7 giờToán rời rạc là gì; các cấu trúc rời rạc (tập hợp, dãy, ánh xạ); mệnh đề toán học, phép kéo theo, các luật logic, các kỹ thuật chứng minh và chứng minh về cấu trúc rời rạc. Nếu đã học Nhập môn chứng minh toán học, hãy đọc nhanh và tập trung vào bài tập. Luyện tập: viết phủ định của các định nghĩa quen thuộc và chứng minh vài mệnh đề về số nguyên chẵn lẻ, chia hết.
- Đọc: Chương 0 Introduction and Preliminaries; Chương 1 Logic and Proofs — Discrete Mathematics: An Open Introduction
Bước 2: Lý thuyết đồ thị nhập môn
khoảng 8 giờCác định nghĩa cơ bản, cây, đồ thị phẳng và công thức Euler, đường đi và chu trình Euler, tô màu đồ thị, quan hệ và đồ thị, ghép cặp trên đồ thị hai phía. Luyện tập: chứng minh cây n đỉnh có n − 1 cạnh bằng quy nạp; cài đặt biểu diễn đồ thị và duyệt theo chiều rộng (BFS) bằng Python theo tài liệu và video trên trang, rồi dùng BFS kiểm tra một đồ thị có liên thông, có phải đồ thị hai phía không.
- Đọc: Chương 2 Graph Theory — Discrete Mathematics: An Open Introduction
Bước 3: Các nguyên lý đếm
khoảng 9 giờTam giác Pascal, quy tắc cộng và quy tắc nhân, đếm khi các trường hợp chồng lấn, hoán vị và tổ hợp, đếm đa tập (bài toán chia kẹo), chứng minh tổ hợp, ứng dụng vào xác suất, đếm nâng cao bằng nguyên lý bao hàm – loại trừ. Luyện tập: giải 20 bài đếm và kiểm tra ít nhất năm đáp án bằng chương trình liệt kê vét cạn với n nhỏ; chứng minh C(n, k) = C(n − 1, k − 1) + C(n − 1, k) bằng lập luận tổ hợp.
- Đọc: Chương 3 Counting — Discrete Mathematics: An Open Introduction
Bước 4: Dãy số, hệ thức truy hồi và quy nạp
khoảng 8 giờMô tả dãy bằng công thức tổng quát và hệ thức truy hồi, tốc độ tăng của dãy, dãy đa thức (sai phân) và dãy mũ, quy nạp và quy nạp mạnh. Luyện tập: giải hệ thức truy hồi của bài toán tháp Hà Nội và của dãy Fibonacci, chứng minh công thức tìm được bằng quy nạp; sau đó đọc tài liệu về ký hiệu O lớn trên trang để thấy tốc độ tăng của dãy được dùng thế nào khi phân tích thuật toán.
- Đọc: Chương 4 Sequences — Discrete Mathematics: An Open Introduction
Bước 5: Tập hợp, ánh xạ, hàm sinh và lý thuyết số
khoảng 8 giờÔn lại tập hợp và ánh xạ ở mức chặt chẽ; hàm sinh để giải bài toán đếm và hệ thức truy hồi; nhập môn lý thuyết số: chia hết, thuật toán Euclid, đồng dư. Luyện tập: dùng hàm sinh tìm lại công thức của dãy Fibonacci; cài thuật toán Euclid mở rộng bằng Python và dùng nó giải phương trình đồng dư ax ≡ b (mod n). Muốn nghe giảng, có thể xem các bài tương ứng của MIT 6.1200J Mathematics for Computer Science (trên MIT OpenCourseWare là 6.042J).
- Đọc: Chương 5 Discrete Structures Revisited; Chương 6 Additional Topics (6.1 Generating Functions, 6.2 Introduction to Number Theory) — Discrete Mathematics: An Open Introduction
Khái niệm chính
- Logic vị từ
- Mở rộng logic mệnh đề bằng biến và lượng từ ∀, ∃; là ngôn ngữ để phát biểu chính xác các định nghĩa và định lý.
- Đồ thị
- Cặp G = (V, E) gồm tập đỉnh và tập cạnh nối các cặp đỉnh; bậc của đỉnh là số cạnh kề, và tổng các bậc bằng hai lần số cạnh.
- Cây
- Đồ thị liên thông không có chu trình; cây n đỉnh có đúng n − 1 cạnh và giữa hai đỉnh bất kỳ có đúng một đường đi.
- Đồ thị phẳng và công thức Euler
- Đồ thị vẽ được trên mặt phẳng mà các cạnh không cắt nhau; với đồ thị phẳng liên thông, số đỉnh − số cạnh + số miền = 2.
- Đường đi và chu trình Euler
- Đường đi qua mỗi cạnh đúng một lần; đồ thị liên thông có chu trình Euler khi và chỉ khi mọi đỉnh có bậc chẵn.
- Tô màu đồ thị
- Gán màu cho các đỉnh sao cho hai đỉnh kề nhau khác màu; số màu tối thiểu là sắc số, và mọi đồ thị phẳng tô được bằng 4 màu.
- Quy tắc cộng và quy tắc nhân
- Nếu một việc làm theo cách A hoặc cách B (rời nhau) thì số cách là tổng; nếu làm qua bước A rồi bước B thì số cách là tích.
- Tổ hợp và nhị thức Newton
- C(n, k) là số tập con k phần tử của tập n phần tử; (x + y)ⁿ = ∑ C(n, k) xᵏ yⁿ⁻ᵏ và các hệ số tạo thành tam giác Pascal.
- Nguyên lý bao hàm – loại trừ
- |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|; tổng quát cho n tập, dùng để đếm khi các trường hợp chồng lấn nhau.
- Chứng minh tổ hợp
- Chứng minh một đẳng thức bằng cách chỉ ra hai vế cùng đếm một tập hợp theo hai cách khác nhau.
- Hệ thức truy hồi
- Định nghĩa mỗi số hạng của dãy qua các số hạng trước, như Fₙ = Fₙ₋₁ + Fₙ₋₂; giải hệ thức tuyến tính hệ số hằng bằng phương trình đặc trưng.
- Nguyên lý Dirichlet
- Xếp n + 1 vật vào n hộp thì có hộp chứa ít nhất hai vật; còn gọi là nguyên lý chuồng bồ câu.
- Đồng dư
- a ≡ b (mod n) nếu n chia hết a − b; phép cộng và phép nhân tương thích với đồng dư, tạo nên số học modulo dùng trong mật mã học.
Học xong để làm gì
- Thiết kế và phân tích thuật toán: đếm số phép toán, hệ thức truy hồi của thuật toán chia để trị, ký hiệu O lớn
- Mạng máy tính, bản đồ và mạng xã hội: định tuyến, tìm đường, phân tích cộng đồng đều là bài toán đồ thị
- Mật mã học: RSA và chữ ký số dựa trên số học đồng dư và số nguyên tố
- Cơ sở dữ liệu và lập trình: quan hệ, logic vị từ trong truy vấn, kiểm chứng tính đúng của chương trình bằng quy nạp
- Xác suất rời rạc: tính xác suất trong trò chơi, xổ số, kiểm thử phần mềm ngẫu nhiên bằng các kỹ thuật đếm
- Lập lịch và phân công: tô màu đồ thị cho lịch thi, ghép cặp cho phân công nhiệm vụ
Câu hỏi thường gặp
Toán rời rạc có cần giải tích không?
Hầu như không. Môn này chỉ cần đại số phổ thông và kỹ năng chứng minh, nên có thể học rất sớm, song song với Giải tích một biến.
Nên chọn giáo trình Levin, Rosen hay Mathematics for Computer Science?
Levin (sách chính) ngắn gọn, thân thiện, miễn phí — hợp để tự học. Rosen dày, rất nhiều bài tập, là giáo trình phổ biến ở Việt Nam và thế giới — dùng để luyện thêm. Mathematics for Computer Science của MIT (miễn phí) sâu hơn về chứng minh và xác suất, đi kèm bài giảng MIT 6.1200J (trên OCW là 6.042J).
Toán rời rạc khác gì chủ đề Tổ hợp và lý thuyết đồ thị?
Toán rời rạc là môn nhập môn bao quát nhiều mạch (logic, đồ thị, đếm, dãy). Tổ hợp và lý thuyết đồ thị đi sâu hơn: hàm sinh, hệ thức truy hồi tổng quát, luồng trên mạng, lý thuyết Ramsey — nên học sau môn này.
Tôi là dân CNTT, phần nào quan trọng nhất?
Đếm, đồ thị, hệ thức truy hồi và quy nạp dùng trực tiếp trong phân tích thuật toán; logic dùng trong cơ sở dữ liệu và kiểm chứng phần mềm; lý thuyết số dùng trong mật mã học. Đừng bỏ qua phần chứng minh — đó là kỹ năng giúp bạn lập luận về tính đúng của thuật toán.
Mất bao lâu để học xong?
Khoảng 40 giờ, tức 6–7 tuần nếu học 6 giờ mỗi tuần. Phần đếm thường cần nhiều bài tập nhất.
