Hãy vẽ biểu đồ Venn và xác định từng vùng xem vùng nào thuộc biểu thức tập hợp.
Với bài toán đếm, hãy điền các vùng từ tâm ra ngoài: tất cả các tập, rồi từng cặp, rồi từng tập đơn, rồi phần bên ngoài.
Hãy dùng nguyên lý bao hàm – loại trừ để kiểm tra: |A ∪ B| = |A| + |B| − |A ∩ B|.
Với một quan hệ, hãy kiểm tra từng tính chất trên mọi cặp và đưa ra một phản ví dụ khi tính chất không đúng.
Với một hàm, hãy đếm số mũi tên đến mỗi phần tử của B: nhiều nhất một là đơn ánh, ít nhất một là toàn ánh.
Lý thuyết đồ thị
Bổ đề bắt tay
Σ deg(v) = 2|E|
Đồ thị đầy đủ
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
Đồ thị đều
|E| = n·k/2
Cây và rừng
|E| = n − 1, |E| = n − c
Lá của cây
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Euler
chu trình: mọi bậc đều chẵn; đường đi: đúng 2 bậc lẻ
Chu trình Hamilton trong Kn
(n − 1)!/2
Cập nhật Dijkstra
d(v) = min(d(v), d(u) + w(u, v))
Đường đi độ dài L
(Mᴸ)ij
Phương pháp
Hãy ghi bậc của mỗi đỉnh; tổng các bậc bằng hai lần số cạnh.
Với bài Euler, hãy kiểm tra đồ thị liên thông và đếm số đỉnh có bậc lẻ.
Với cây, hãy dùng n − 1 cạnh và bổ đề bắt tay.
Với Dijkstra, hãy lập bảng khoảng cách tạm thời và mỗi vòng chốt đỉnh chưa chốt có giá trị nhỏ nhất.
Với cây khung nhỏ nhất, hãy sắp xếp các cạnh theo trọng số và bỏ qua mọi cạnh tạo thành chu trình (Kruskal), hoặc mở rộng một cây từ một đỉnh xuất phát (Prim).
Lý thuyết số & số học đồng dư
Phép chia có dư
a = q·n + r, 0 ≤ r < n
Euclid
gcd(a, b) = gcd(b, a mod b)
Bội chung nhỏ nhất
lcm(a, b) = a·b/gcd(a, b)
Nghịch đảo
a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Đồng dư tuyến tính
a·x ≡ b → x ≡ a⁻¹·b (mod n)
Hàm phi Euler
φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
Fermat
aᵖ⁻¹ ≡ 1 (mod p)
RSA
n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n
Phương pháp
Trước hết hãy rút gọn mọi số theo modulo n; số dư nằm trong khoảng từ 0 đến n − 1.
Với ước chung lớn nhất, hãy chia liên tiếp theo thuật toán Euclid; số dư khác 0 cuối cùng chính là ước chung lớn nhất.
Với số nghịch đảo, hãy chạy thuật toán Euclid mở rộng và lấy hệ số của a; cộng n nếu nó âm.
Giải a·x ≡ b bằng cách nhân với a⁻¹; kết hợp hai đồng dư bằng cách viết x = r₁ + m₁k.
Với lũy thừa, hãy viết số mũ ở dạng nhị phân và bình phương liên tiếp; trong RSA, d = e⁻¹ mod φ(n) với φ(n) = (p − 1)(q − 1).
2Bài tập
1.Logic mệnh đề & chứng minhTrung bình
r → (r ∧ q) là hằng đúng, mâu thuẫn hay công thức ngẫu nhiên? Hãy nhấp vào đáp án của bạn.
r → (r ∧ q)
1hằng đúng
2mâu thuẫn
3công thức ngẫu nhiên
2.Logic mệnh đề & chứng minhKhó
Phát biểu nào tương đương với ¬∀x ∃y R(x, y), khi phép phủ định đã được đưa hoàn toàn vào trong? Hãy nhấp vào nó.
¬∀x ∃y R(x, y)
1∀x ∃y ¬R(x, y)
2∃x ∀y ¬R(x, y)
3∃y ∀x ¬R(x, y)
4∀x ∀y ¬R(x, y)
3.Tập hợp, quan hệ & hàmTrung bình
R = {(1, 1), (1, 2), (1, 3), (2, 3), (3, 1)} là một quan hệ trên {1, 2, 3}. Số cặp có thứ tự nhỏ nhất k phải thêm vào R để R phản xạ là bao nhiêu?
R = {(1, 1), (1, 2), (1, 3), (2, 3), (3, 1)}
k =
4.Tập hợp, quan hệ & hàmKhó
Một quan hệ tương đương R trên {1, …, 6} có các lớp {2, 3, 4, 6}, {1, 5}. R chứa bao nhiêu cặp có thứ tự? Gọi số đó là |R|.
{2, 3, 4, 6}{1, 5}
|R| =
5.Lý thuyết đồ thịTrung bình
Một cây có 2 đỉnh bậc 4, 2 đỉnh bậc 5, và mọi đỉnh khác của nó đều là lá (bậc 1). Nó có bao nhiêu lá L?
2 × deg 42 × deg 5
L =
6.Lý thuyết đồ thịKhó
Có bao nhiêu đường đi khép kín độ dài 3 bắt đầu và kết thúc tại F? Một đường đi có thể lặp lại đỉnh và cạnh. Gọi số đó là N.
M = ma trận kềL = 3
N =
7.Lý thuyết số & số học đồng dưTrung bình
Hãy tìm nghịch đảo của 39 theo modulo 41: số x với 0 < x < 41 và 39·x ≡ 1 (mod 41).
a = 39n = 41
39−1 mod 41 =
8.Lý thuyết số & số học đồng dưKhó
Một khóa RSA dùng các số nguyên tố p = 19 và q = 41 và số mũ công khai e = 13. Hãy tìm số mũ bí mật d (0 < d < φ(n)).
p = 19q = 41e = 13
d =
3Dung dịch
1.Logic mệnh đề & chứng minh
Đáp số: công thức ngẫu nhiên
Tương đương logic: hai công thức tương đương (≡) khi chúng có cùng giá trị ở mọi hàng của bảng chân trị. Hằng đúng bằng 1 ở mọi hàng, mâu thuẫn bằng 0 ở mọi hàng, còn công thức ngẫu nhiên thì không thuộc loại nào. Các luật hữu ích: De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b và ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (phản đảo); ¬(a → b) ≡ a ∧ ¬b; và các luật phân phối, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).
Bảng chân trị từng hàng
q = 1, r = 1: r ∧ q = 1, r → (r ∧ q) = 1
q = 1, r = 0: r ∧ q = 0, r → (r ∧ q) = 1
q = 0, r = 1: r ∧ q = 0, r → (r ∧ q) = 0
q = 0, r = 0: r ∧ q = 0, r → (r ∧ q) = 1
Phân loại
r → (r ∧ q): 1, 1, 0, 1
1 trong 3 của 4 dòng, 0 ở các dòng còn lại: một mệnh đề ngẫu nhiên.
Đáp số
công thức ngẫu nhiên
2.Logic mệnh đề & chứng minh
Đáp số: ∃x ∀y ¬R(x, y)
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ệ.
Đưa phép phủ định vào trong
¬∀x ∃y R(x, y) ≡ ∃x ∀y ¬R(x, y)
Đáp số
∃x ∀y ¬R(x, y)
Các phương án còn lại hoặc giữ nguyên một lượng từ, hoặc đổi thứ tự các lượng từ, hoặc phủ định sai công thức bên trong.
3.Tập hợp, quan hệ & hàm
Đáp số: k = 2
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.
Các cặp cần thêm
{(2, 2), (3, 3)}
Đếm
k = 2
Đáp số
k = 2
4.Tập hợp, quan hệ & hàm
Đáp số: |R| = 20
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.
Số cặp mỗi lớp
|R| = 4² + 2² = 20
Đáp số
|R| = 20
5.Lý thuyết đồ thị
Đáp số: L = 12
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; Kn 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.
Bổ đề bắt tay cho một cây
L + 18 = 2(L + 4) − 2
L = 12
Đáp số
L = 12
Cách nhanh: L = 2 + Σ (d − 2) trên các đỉnh có bậc d ≥ 3.
6.Lý thuyết đồ thị
Đáp số: N = 2
Bậc: bậc của một đỉnh là số cạnh gặp đỉnh đó. Mỗi cạnh có hai đầu, nên tổng các bậc bằng hai lần số cạnh: Σ deg(v) = 2|E| (bổ đề bắt tay). Do đó số đỉnh có bậc lẻ là số chẵn. Kn có n(n − 1)/2 cạnh, một đồ thị k-đều trên n đỉnh có nk/2 cạnh, và một cây trên n đỉnh có n − 1 cạnh.
Ma trận kề
A: 0 0 1 0 0 0
B: 0 0 0 1 1 0
C: 1 0 0 0 1 0
D: 0 1 0 0 1 1
E: 0 1 1 1 0 1
F: 0 0 0 1 1 0
Thêm một bước
(M³)FF = 0·0 + 2·0 + 1·0 + 1·1 + 1·1 + 2·0 = 2
Đáp số
N = 2
7.Lý thuyết số & số học đồng dư
Đáp số: 39−1 mod 41 = 20
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).
Thuật toán Euclid mở rộng
Mỗi số dư r được viết là r ≡ t·39 (mod 41).
r = 41, t = 0
r = 39, q = 1, t = 1
r = 2, q = 19, t = −1
r = 1, q = 2, t = 20
Nghịch đảo
1 ≡ 20·39 (mod 41)
x = 20
kiểm tra: 39·20 = 780 = 19·41 + 1
Đáp số
39−1 mod 41 = 20
8.Lý thuyết số & số học đồng dư
Đáp số: d = 277
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.