Toán rời rạc

Toán rời rạc là toán học của những thứ tách biệt, đếm được. Một mệnh đề đúng hoặc sai, một phần tử thuộc một tập hợp hoặc không, một mạng lưới có hoặc không có đường nối giữa hai điểm. Không có gì ở giữa, đó chính là ý nghĩa của chữ "rời rạc", và cũng chính là cách máy tính nhìn thế giới.

Một môn nhập môn gồm sáu chủ đề: logic, tập hợp, phép đếm, đồ thị, lý thuyết số và chứng minh. Logic đứng đầu, vì mọi chủ đề khác đều được viết bằng nó. Hãy chọn một phép nối bên dưới và bật tắt p và q.

Logic: mệnh đề và phép nối

Một mệnh đề là một câu hoặc đúng hoặc sai, chẳng hạn "7 là số nguyên tố" hay "trời đang mưa". Logic ghép các mệnh đề nhỏ thành mệnh đề lớn hơn bằng một vài phép nối, và một bảng chân trị liệt kê kết quả cho mọi tổ hợp đầu vào.

Có hai phép khiến nhiều người bất ngờ. Phép OR trong logic là bao hàm: "p hoặc q" đúng khi cả hai cùng đúng, khác với câu hỏi thường ngày "trà hay cà phê?". Phiên bản loại trừ có tên riêng là XOR.

Phép còn lại là IMPLIES. p → q chỉ sai ở đúng một hàng, khi p đúng và q sai. Hãy nghĩ về nó như một lời hứa: "nếu trời mưa, tôi sẽ mang ô". Lời hứa chỉ bị phá khi trời mưa mà không có ô. Vào một ngày khô ráo, lời hứa không bị phá dù bạn mang gì theo, nên mệnh đề được tính là đúng.

Mệnh đề tương đương

Hai mệnh đề tương đương khi bảng chân trị của chúng trùng nhau ở mọi hàng. Trong công cụ ở trên, chọn OR và phủ định p: cột của ¬p ∨ q giống hệt cột của p → q, nên hai mệnh đề nói cùng một điều.

Những phép tương đương hữu ích nhất là luật De Morgan, cho biết phép NOT đi qua AND và OR như thế nào:

¬(p ∧ q) ≡ ¬p ∨ ¬q

¬(p ∨ q) ≡ ¬p ∧ ¬q

Nói bằng lời: "không phải cả hai" cũng là "một trong hai cái sai", và "không cái nào" cũng là "cả hai đều sai". Lập trình viên dùng chúng hằng ngày để viết lại một điều kiện như "không (đã đăng nhập và đã xác minh)".

Logic và tập hợp là một ý tưởng

Đọc p là "x thuộc A" và q là "x thuộc B". Khi đó AND là phép giao, OR là phép hợp, NOT là phần bù, và mỗi bảng chân trị là một biểu đồ Venn được tô màu, đó là lý do công cụ vẽ một biểu đồ bên cạnh bảng. Luật De Morgan trở thành quy tắc về tập hợp:

(A ∩ B)′ = A′ ∪ B′

Trang ký hiệu tập hợp tô màu từng phép này trên một biểu đồ bạn có thể bấm vào.

Phép đếm

Đếm trong toán rời rạc nghĩa là đếm mà không cần liệt kê. Hai quy tắc làm phần lớn công việc.

Quy tắc nhân. Nếu một lựa chọn có m cách và lựa chọn thứ hai có n cách, thì cặp lựa chọn có m × n cách. Một mã PIN 4 chữ số có 10 lựa chọn cho mỗi chữ số, nên có 10^4 = 10000 mã PIN có thể có.

Tổ hợp. Số cách chọn k thứ từ n thứ, khi thứ tự không quan trọng, được viết là C(n, k). Chọn 3 loại topping từ 8 loại:

C(8, 3) = (8 × 7 × 6) / (3 × 2 × 1) = 56

Tử số đếm các lựa chọn có thứ tự, và chia cho 3 × 2 × 1 sẽ loại bỏ 6 thứ tự khác nhau mà cùng ba loại topping đó có thể được chọn.

Một câu lạc bộ có 6 thành viên. Có bao nhiêu cặp thành viên khác nhau có thể được chọn để tổ chức một sự kiện?

Đáp án là 6 × 5 chia 2, bằng 15. Nếu bạn ra 30 thì bạn đã đếm mỗi cặp hai lần, một lần cho mỗi thứ tự.

Đồ thị

Một đồ thị là một tập hợp các điểm, gọi là đỉnh, được nối bằng các đường, gọi là cạnh. Nó mô hình hóa mọi thứ được tạo nên từ các kết nối: đường đi giữa các thị trấn, bạn bè trên mạng xã hội, liên kết giữa các trang web.

Một kết quả đầu tiên: nếu 5 người bắt tay nhau, mỗi cặp một lần, thì có C(5, 2) = 10 cái bắt tay. Mỗi người bắt 4 bàn tay, cho ra 5 × 4 = 20 đầu bắt tay, và mỗi cái bắt tay có hai đầu, nên 20 / 2 = 10. Lập luận này là bổ đề bắt tay: tổng bậc của tất cả các đỉnh bằng hai lần số cạnh.

Lý thuyết số và chứng minh

Số học đồng dư là số học trên mặt đồng hồ. 17 mod 5 bằng 2, là số dư khi chia 17 cho 5. Chín giờ sau 8 giờ là 5 giờ, vì 17 mod 12 bằng 5. Cùng ý tưởng đó, với những số rất lớn, là cách mã hóa RSA đằng sau các trang web bảo mật hoạt động.

Chứng minh quy nạp cho thấy một mệnh đề đúng với mọi số nguyên dương n qua hai bước: kiểm tra nó với n = 1, rồi chứng minh rằng nếu nó đúng với một n nào đó thì nó cũng đúng với n + 1. Đây là cách chứng minh, chẳng hạn, rằng

1 + 2 + ... + n = n(n + 1) / 2

với mọi n, chứ không chỉ những giá trị bạn đã thử.

Toán rời rạc dùng để làm gì

• Lập trình: mỗi câu lệnh if là logic, và luật De Morgan giúp viết lại điều kiện.
• Cơ sở dữ liệu: một truy vấn nối hay lọc các bảng chính là các phép toán tập hợp.
• Thuật toán: phép đếm cho bạn biết một chương trình cần bao nhiêu bước khi đầu vào lớn dần.
• Mạng lưới và bản đồ: đường đi ngắn nhất và mạng xã hội là các bài toán đồ thị.
• Bảo mật: mã hóa dựa trên lý thuyết số và số học đồng dư.
• Phần cứng: bộ xử lý được xây từ các cổng logic, tức là các bảng chân trị trên silicon.

Toán rời rạc có khó không?

Nó khó theo một kiểu khác với đại số và giải tích. Có ít công thức phải nhớ và phần tính toán nhỏ, nhưng nhiều câu hỏi yêu cầu bạn chứng minh một điều gì đó thay vì tính ra nó, và viết một lập luận thuyết phục là kỹ năng mới với hầu hết người học.

Điều giúp ích nhất là làm các trường hợp nhỏ bằng tay trước khi tìm quy luật: vẽ biểu đồ Venn, viết bảng chân trị, liệt kê mọi trường hợp. Ký hiệu lúc đầu trông nặng nề, nhưng phần lớn chỉ là các ký hiệu trên trang này và trang ký hiệu tập hợp.