Bỏ qua tới nội dung chính
Toán học

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

Toán rời rạc

Cơ bảnkhoảng 40 giờ5 bước

Logic, tập hợp, quy nạp, đếm cơ bản, quan hệ truy hồi, nhập môn đồ thị và số học modulo.

Bắt đầu học

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

Giáo trình chính

Discrete Mathematics: An Open Introduction

Oscar Levin · 2025 · Bản thứ 4

CC BY-NC-SACơ bảnTiếng Anh

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

Mathematics for Computer Science

Eric Lehman, F. Thomson Leighton, Albert R. Meyer · 2018

CC BY-SATrung bìnhTiếng Anh

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.

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

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

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

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

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

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.

Chọn nguồn tự học

Nên chọn nguồn có nhiều ví dụ gắn với tin học (đếm, đồ thị, quy nạp trên chương trình); không cần giải tích nên có thể học rất sớm.