Bạn sẽ học được gì
- Dịch một mệnh đề toán học sang ký hiệu logic với lượng từ ∀, ∃ và viết đúng phủ định của nó
- Chọn và áp dụng đúng chiến lược: chứng minh trực tiếp, phản đảo, phản chứng hoặc chia trường hợp
- Chứng minh các mệnh đề về số nguyên và dãy số bằng quy nạp thường và quy nạp mạnh
- Chứng minh đẳng thức và bao hàm giữa các tập hợp, bác bỏ mệnh đề sai bằng phản ví dụ
- Kiểm tra một quan hệ có phải quan hệ tương đương, một ánh xạ có phải đơn ánh, toàn ánh, song ánh
- So sánh bản số của các tập vô hạn; chứng minh ℚ đếm được và ℝ không đếm được
- Viết lời chứng minh hoàn chỉnh bằng câu văn, rõ ràng và đúng quy ước trình bày toán học
Giới thiệu
Nhập môn chứng minh toán học là môn học đưa bạn từ lối toán "tính ra đáp số" ở phổ thông sang lối toán "chứng minh vì sao đúng" ở đại học. Ở phổ thông, phần lớn bài tập yêu cầu áp dụng công thức; từ năm hai đại học trở đi — giải tích thực, đại số trừu tượng, lý thuyết đồ thị, xác suất — gần như mọi bài tập đều kết thúc bằng câu "chứng minh rằng…". Môn này trang bị bộ công cụ chung cho tất cả: đọc hiểu chính xác một mệnh đề toán học, chọn chiến lược chứng minh phù hợp và viết lời giải chặt chẽ, dễ đọc.
Ngôn ngữ trước, kỹ thuật sau
Một chứng minh chỉ đúng khi bạn hiểu chính xác mình cần chứng minh điều gì. Vì vậy môn học bắt đầu bằng tập hợp và logic: phép hội, phép tuyển, phủ định, mệnh đề kéo theo "nếu P thì Q", mệnh đề tương đương và đặc biệt là lượng từ "với mọi" (∀) và "tồn tại" (∃). Phần lớn lỗi của người mới nằm ở đây: phủ định sai một mệnh đề có lượng từ, nhầm mệnh đề đảo với mệnh đề phản đảo, hoặc kiểm tra vài ví dụ rồi tưởng đã chứng minh xong "với mọi". Hãy tập viết lại mỗi định lý bằng ký hiệu logic trước khi bắt tay chứng minh.
Các kỹ thuật chứng minh cốt lõi
- Chứng minh trực tiếp: giả sử P đúng, lập luận từng bước theo định nghĩa để suy ra Q.
- Chứng minh phản đảo: thay vì P ⇒ Q, chứng minh ¬Q ⇒ ¬P — thường dễ hơn khi kết luận Q là một phủ định.
- Chứng minh phản chứng: giả sử điều cần chứng minh sai rồi dẫn tới mâu thuẫn; hai ví dụ kinh điển là √2 là số vô tỉ và có vô hạn số nguyên tố.
- Quy nạp toán học (thường và mạnh): công cụ chính cho các mệnh đề về số tự nhiên, dãy số và thuật toán đệ quy.
- Phản ví dụ: muốn bác bỏ một mệnh đề "với mọi", chỉ cần một trường hợp sai.
- Chứng minh tồn tại (kiến thiết hoặc không kiến thiết) và chứng minh "khi và chỉ khi" bằng hai chiều.
Tập hợp, quan hệ, hàm và bản số
Nửa sau của môn áp dụng các kỹ thuật trên vào những đối tượng xuất hiện khắp toán học: quan hệ tương đương và lớp tương đương (nền tảng của số học đồng dư modulo n), ánh xạ với các tính chất đơn ánh, toàn ánh, song ánh, ánh xạ hợp và ánh xạ ngược. Phần cuối chạm tới bản số: vì sao tập số hữu tỉ đếm được còn tập số thực thì không (lập luận đường chéo Cantor) — một kết quả thường gây bất ngờ và là bài luyện chứng minh tuyệt vời. Sách chính còn có một chương chứng minh chặt chẽ các khái niệm giới hạn, liên tục bằng ngôn ngữ ε–δ, cây cầu trực tiếp sang giải tích thực.
Cách học hiệu quả
Chứng minh là kỹ năng, không phải kiến thức để học thuộc. Một chu trình học tốt: đọc định nghĩa → tự nghĩ ví dụ và phản ví dụ → thử chứng minh trên giấy nháp → viết lại bản sạch bằng câu văn hoàn chỉnh → so với lời giải mẫu. Hãy viết như đang giải thích cho một bạn cùng lớp: mỗi dòng nói rõ vì sao nó đúng (theo định nghĩa nào, giả thiết nào). Đừng ngại mất nửa giờ cho một bài — những lúc bế tắc rồi tự gỡ ra chính là lúc kỹ năng hình thành. Nếu có thể, hãy đổi bài với bạn học để đọc và bắt lỗi chứng minh của nhau.
Liên hệ với các môn khác
Học xong môn này, bạn có thể bắt đầu Toán rời rạc, Đại số tuyến tính nâng cao và các môn giải tích, đại số theo lối chứng minh. Ở các trường đại học Việt Nam, nội dung tương ứng thường nằm ở phần mở đầu của Đại số đại cương hoặc Toán rời rạc (logic, tập hợp, ánh xạ, quan hệ); ở MIT là 18.090 Introduction to Mathematical Reasoning (và phần đầu 6.1200J Mathematics for Computer Science, trên OCW là 6.042J), ở UC Berkeley là Math 74 (và phần đầu Math 55).
Giáo trình & sách tham khảo
Xem tất cả trong tab SáchGiáo trình chính
Book of Proof
Richard Hammack · 2018 · Bản thứ 3
Vì sao chọn: Giáo trình mở (CC BY-NC-ND 4.0), bản PDF miễn phí trên trang của tác giả, được chương trình giáo trình mở của Viện Toán học Hoa Kỳ (AIM) chấp thuận. Văn phong dễ đọc, chương ngắn, có lời giải cho các bài tập số lẻ — rất hợp để tự học. Các bước của lộ trình đi đúng theo thứ tự chương của sách.
Nên đọc: Chương 1–2, Chương 4–14 (Chương 3 Counting để dành cho Toán rời rạc)
Mathematical Reasoning: Writing and Proof
Ted Sundstrom · 2020 · Phiên bản 3
Giáo trình mở (CC BY-NC-SA 3.0) của Grand Valley State University. Mỗi mục mở đầu bằng hoạt động chuẩn bị để tự khám phá ý tưởng trước khi đọc lý thuyết, kèm rất nhiều bài tập viết chứng minh — dùng khi muốn luyện thêm hoặc cần một cách giải thích khác cho cùng chủ đề.
How to Prove It: A Structured Approach
Daniel J. Velleman · 2019 · Bản thứ 3
Sách trả phí của Cambridge University Press, nổi tiếng về cách lên khung cho một chứng minh: phân tích dạng logic của mệnh đề cần chứng minh rồi suy ra cấu trúc lời giải tương ứng. Đặc biệt hữu ích nếu bạn hay bế tắc ở câu hỏi “bắt đầu từ đâu”.
Các bước học
Đăng nhập để đánh dấu các bước đã hoàn thành.
Bước 1: Tập hợp và logic
khoảng 6 giờLàm quen với ký hiệu tập hợp, tích Descartes, tập lũy thừa, các phép hợp, giao, hiệu, phần bù; sau đó là bảng chân trị, mệnh đề kéo theo, tương đương logic và lượng từ. Luyện tập: viết phủ định của 10 mệnh đề có lượng từ lồng nhau (chẳng hạn định nghĩa dãy hội tụ) và kiểm tra các luật De Morgan bằng bảng chân trị. Tài liệu về logic vị từ trên trang cho thấy cùng ngôn ngữ này được dùng để đặc tả phần mềm.
- Đọc: Chương 1 Sets; Chương 2 Logic — Book of Proof
Bước 2: Chứng minh trực tiếp và chứng minh phản đảo
khoảng 6 giờPhân biệt định nghĩa, định lý, bổ đề; viết chứng minh trực tiếp, chia trường hợp và chứng minh bằng mệnh đề phản đảo; làm quen với đồng dư số nguyên và các quy ước viết toán. Luyện tập: chứng minh “nếu n² chẵn thì n chẵn” bằng phản đảo, và “nếu a ≡ b (mod n) thì a² ≡ b² (mod n)” bằng chứng minh trực tiếp.
- Đọc: Chương 4 Direct Proof; Chương 5 Contrapositive Proof — Book of Proof
Bước 3: Phản chứng, chứng minh tồn tại và phản ví dụ
khoảng 6 giờHọc chứng minh phản chứng, chứng minh “khi và chỉ khi”, chứng minh tồn tại (kiến thiết và không kiến thiết), chứng minh về tập hợp và cách bác bỏ bằng phản ví dụ. Luyện tập: chứng minh √2 vô tỉ và có vô hạn số nguyên tố; chứng minh A ∖ (B ∪ C) = (A ∖ B) ∩ (A ∖ C) bằng hai chiều bao hàm; tìm phản ví dụ cho “mọi số dạng n² + n + 41 đều là số nguyên tố”.
- Đọc: Chương 6 Proof by Contradiction; Chương 7 Proving Non-Conditional Statements; Chương 8 Proofs Involving Sets; Chương 9 Disproof — Book of Proof
Bước 4: Quy nạp toán học
khoảng 6 giờHọc quy nạp thường, quy nạp mạnh và chứng minh bằng phản ví dụ nhỏ nhất; áp dụng vào định lý cơ bản của số học và dãy Fibonacci. Luyện tập: chứng minh công thức 1 + 2 + … + n = n(n+1)/2, bất đẳng thức Bernoulli, và mọi số nguyên n ≥ 2 là tích của các số nguyên tố (quy nạp mạnh). Đọc thêm tài liệu về bất biến trên trang — bất biến là “họ hàng” của quy nạp khi chứng minh chương trình đúng.
- Đọc: Chương 10 Mathematical Induction — Book of Proof
Bước 5: Quan hệ và ánh xạ
khoảng 6 giờHọc quan hệ và các tính chất phản xạ, đối xứng, bắc cầu; quan hệ tương đương, lớp tương đương, phân hoạch và tập số nguyên modulo n; ánh xạ, đơn ánh, toàn ánh, song ánh, ánh xạ hợp, ánh xạ ngược, ảnh và nghịch ảnh. Luyện tập: chứng minh đồng dư modulo n là quan hệ tương đương và mô tả các lớp tương đương; chứng minh hợp của hai song ánh là song ánh.
- Đọc: Chương 11 Relations; Chương 12 Functions — Book of Proof
Bước 6: Bản số và chứng minh trong giải tích
khoảng 6 giờHọc so sánh bản số bằng song ánh, tập đếm được và không đếm được, lập luận đường chéo Cantor và định lý Schröder–Bernstein; sau đó dùng ε–δ để chứng minh chặt chẽ các giới hạn, tính liên tục và sự hội tụ của dãy. Luyện tập: dựng song ánh từ ℕ lên ℤ, chứng minh ℚ đếm được, và chứng minh lim (3x + 1) = 7 khi x → 2 bằng định nghĩa. Muốn xem bài giảng, có thể tham khảo khóa MIT 6.1200J Mathematics for Computer Science (trên MIT OpenCourseWare là 6.042J).
- Đọc: Chương 13 Proofs in Calculus; Chương 14 Cardinality of Sets — Book of Proof
Khái niệm chính
- Mệnh đề và lượng từ
- Mệnh đề là phát biểu chỉ nhận một trong hai giá trị đúng hoặc sai; lượng từ “với mọi” (∀) và “tồn tại” (∃) cho biết phát biểu áp dụng cho mọi phần tử hay chỉ ít nhất một. Phủ định của “∀x, P(x)” là “∃x, ¬P(x)”.
- Mệnh đề kéo theo, đảo và phản đảo
- “Nếu P thì Q” tương đương logic với mệnh đề phản đảo “nếu không Q thì không P”, nhưng không tương đương với mệnh đề đảo “nếu Q thì P”.
- Chứng minh trực tiếp
- Giả sử giả thiết P đúng rồi suy luận từng bước, dựa trên định nghĩa và các kết quả đã biết, cho tới kết luận Q.
- Chứng minh phản chứng
- Giả sử điều cần chứng minh là sai rồi suy ra một mâu thuẫn; từ đó kết luận điều cần chứng minh phải đúng.
- Quy nạp toán học
- Chứng minh P(n) đúng với mọi n ≥ n₀ bằng bước cơ sở P(n₀) và bước quy nạp P(k) ⇒ P(k+1); quy nạp mạnh cho phép dùng tất cả P(n₀), …, P(k) để suy ra P(k+1).
- Phản ví dụ
- Một trường hợp cụ thể làm một mệnh đề “với mọi” sai. Một phản ví dụ là đủ để bác bỏ, nhưng bao nhiêu ví dụ đúng cũng không đủ để chứng minh.
- Quan hệ tương đương
- Quan hệ có tính phản xạ, đối xứng và bắc cầu; nó chia tập hợp thành các lớp tương đương rời nhau, ví dụ các lớp đồng dư modulo n của số nguyên.
- Đơn ánh, toàn ánh, song ánh
- Đơn ánh: hai phần tử khác nhau có ảnh khác nhau; toàn ánh: mọi phần tử của tập đích đều là ảnh của ít nhất một phần tử; song ánh là vừa đơn ánh vừa toàn ánh và có ánh xạ ngược.
- Bản số và tập đếm được
- Hai tập có cùng bản số nếu tồn tại song ánh giữa chúng; tập đếm được là tập hữu hạn hoặc có song ánh với tập số tự nhiên ℕ.
- Lập luận đường chéo Cantor
- Kỹ thuật dựng một phần tử khác mọi phần tử của một danh sách cho trước; dùng để chứng minh tập số thực không đếm được.
Học xong để làm gì
- Nền tảng bắt buộc cho các môn toán bậc cao: giải tích thực, đại số trừu tượng, tôpô, lý thuyết xác suất
- Chứng minh tính đúng đắn của thuật toán bằng bất biến vòng lặp và quy nạp trên chương trình đệ quy
- Kiểm chứng hình thức phần mềm và phần cứng, nơi đặc tả được viết bằng logic vị từ
- Lý thuyết số và mật mã học: lập luận về số nguyên tố, đồng dư và độ an toàn của hệ mã
- Rèn tư duy lập luận chặt chẽ, hữu ích khi viết đặc tả kỹ thuật, phân tích dữ liệu hay tranh biện
Câu hỏi thường gặp
Tôi học toán phổ thông khá nhưng chưa từng viết chứng minh, có theo được không?
Được. Môn này được thiết kế đúng cho tình huống đó và không đòi hỏi giải tích; chỉ cần đại số phổ thông (biến đổi biểu thức, bất đẳng thức, số chẵn lẻ, chia hết). Khó khăn chính là thói quen viết lập luận, và nó cải thiện rõ rệt sau vài tuần luyện đều.
Làm sao biết chứng minh của mình đã đúng và đủ chặt chẽ?
Kiểm tra từng dòng: nó suy ra từ giả thiết, định nghĩa hay kết quả nào? Có vô tình dùng điều cần chứng minh làm giả thiết không? Có chỉ kiểm tra vài ví dụ không? Sau đó so với lời giải mẫu — Book of Proof có lời giải cho các bài tập số lẻ — hoặc nhờ người khác đọc thử.
Nên học môn này trước hay song song với giải tích và đại số tuyến tính?
Có thể học song song với Giải tích một biến và Đại số tuyến tính. Nhưng nên xong môn này trước Toán rời rạc, Đại số tuyến tính nâng cao hay giải tích thực — các môn đó giả định bạn đã viết được chứng minh.
Có cần học logic hình thức sâu như trong môn Logic toán không?
Không. Ở đây chỉ cần logic đủ dùng để đọc và viết chứng minh (bảng chân trị, lượng từ, phủ định). Logic toán với định lý đầy đủ và định lý bất toàn là một chủ đề riêng, nâng cao hơn trong cùng nhóm.
Mỗi tuần nên dành bao nhiêu thời gian?
Khoảng 6 giờ một tuần trong 6 tuần: chừng 2 giờ đọc và 4 giờ tự làm bài. Làm bài quan trọng hơn đọc — mỗi chương hãy chọn 6–10 bài, ưu tiên các bài có lời giải để tự đối chiếu.

