Toán học rời rạc: gói ôn nước rút

Bảng chân trị: một công thức có n biến khác nhau có 2ⁿ hàng, mỗi hàng ứng với một tổ hợp giá trị chân trị (1 = đúng, 0 = sai). Hãy làm từ trong ra ngoài và cho mỗi công thức con một cột riêng. ¬a đảo giá trị; a ∧ b bằng 1 chỉ khi cả hai đều bằng 1; a ∨ b bằng 0 chỉ khi cả hai đều bằng 0; a → b bằng 0 chỉ khi a = 1 và b = 0; a ↔ b bằng 1 khi hai vế bằng nhau.

Lượng từ và suy luận: ¬∀x P(x) ≡ ∃x ¬P(x) và ¬∃x P(x) ≡ ∀x ¬P(x). Đưa phép phủ định vào trong, đổi mọi lượng từ mà nó đi qua, và phủ định công thức bên trong bằng các luật logic mệnh đề, chẳng hạn ¬(a → b) ≡ a ∧ ¬b. Một suy luận hợp lệ khi kết luận bằng 1 ở mọi hàng mà tất cả tiền đề đều bằng 1. Chỉ một hàng có tiền đề đúng mà kết luận sai là một phản ví dụ và cho thấy suy luận không hợp lệ.

Quan hệ: một quan hệ R trên tập X là một tập các cặp có thứ tự (x, y). R phản xạ khi (x, x) ∈ R với mọi x thuộc X; đối xứng khi (x, y) ∈ R luôn đi kèm (y, x) ∈ R; phản đối xứng khi (x, y) và (y, x) cùng thuộc R chỉ nếu x = y; và bắc cầu khi (x, y) và (y, z) thuộc R kéo theo (x, z) ∈ R. Một quan hệ tương đương là phản xạ, đối xứng và bắc cầu, và chia X thành các lớp rời nhau.

Quan hệ: một quan hệ R trên tập X là một tập các cặp có thứ tự (x, y). R phản xạ khi (x, x) ∈ R với mọi x thuộc X; đối xứng khi (x, y) ∈ R luôn đi kèm (y, x) ∈ R; phản đối xứng khi (x, y) và (y, x) cùng thuộc R chỉ nếu x = y; và bắc cầu khi (x, y) và (y, z) thuộc R kéo theo (x, z) ∈ R. Một quan hệ tương đương là phản xạ, đối xứng và bắc cầu, và chia X thành các lớp rời nhau.

Euler, Hamilton và cây: một đồ thị liên thông có chu trình Euler (đi qua mỗi cạnh một lần, trở về điểm đầu) khi mọi đỉnh có bậc chẵn, và có đường đi Euler không phải chu trình khi có đúng hai đỉnh bậc lẻ; khi đó đường đi chạy từ một đỉnh lẻ đến đỉnh lẻ kia. Một chu trình Hamilton thăm mỗi đỉnh một lần; K_n có (n − 1)!/2 chu trình như vậy. Một cây trên n đỉnh có n − 1 cạnh, và một đồ thị liên thông có m cạnh còn lại một cây khung sau khi bỏ m − n + 1 cạnh.

Đường đi ngắn nhất và cây khung: thuật toán Dijkstra chốt một đỉnh mỗi vòng: đỉnh chưa chốt có khoảng cách tạm thời nhỏ nhất. Khoảng cách của nó khi đó là cuối cùng, và mỗi đỉnh kề v được d(v) = min(d(v), d(u) + w(u, v)). Thuật toán Kruskal xây dựng cây khung nhỏ nhất bằng cách lấy các cạnh từ nhẹ đến nặng và bỏ qua mọi cạnh tạo thành chu trình; thuật toán Prim mở rộng một cây từ một đỉnh xuất phát bằng cách luôn thêm cạnh nhẹ nhất đi ra khỏi cây. Một cây khung của n đỉnh có n − 1 cạnh.

Nghịch đảo và đồng dư: a có nghịch đảo theo modulo n đúng khi gcd(a, n) = 1. Thuật toán Euclid mở rộng viết 1 = s·n + t·a, và khi đó a⁻¹ ≡ t (mod n). Một đồng dư a·x ≡ b (mod n) với gcd(a, n) = 1 có nghiệm x ≡ a⁻¹·b. Hai đồng dư x ≡ r₁ (mod m₁) và x ≡ r₂ (mod m₂) với các modulo nguyên tố cùng nhau có một nghiệm theo modulo m₁·m₂ (định lý số dư Trung Hoa). φ(n) của Euler đếm các số từ 1 đến n nguyên tố cùng nhau với n: φ(n) = n·∏(1 − 1/p).

Lũy thừa modulo và RSA: tính aᵏ mod n bằng bình phương lặp: viết k ở dạng nhị phân, bình phương, rút gọn sau mỗi bước và nhân các lũy thừa có bit bằng 1. Fermat: aᵖ⁻¹ ≡ 1 (mod p) với số nguyên tố p không chia hết a, nên số mũ có thể được rút gọn theo modulo p − 1. RSA: chọn các số nguyên tố p và q, n = p·q và φ(n) = (p − 1)(q − 1); số mũ công khai e nguyên tố cùng nhau với φ(n), và số mũ bí mật là d = e⁻¹ mod φ(n). Mã hóa bằng c = mᵉ mod n và giải mã bằng m = cᵈ mod n.