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

Bảng công thức, các bước phương pháp chính cho từng chủ đề và 8 bài tập, kèm lời giải đầy đủ ở cuối.

Bài mới Quay lại môn học

Trong cửa sổ in, hãy chọn “Lưu dưới dạng PDF” để giữ một bản trên thiết bị của bạn.

1Công thức và phương pháp

Logic mệnh đề & chứng minh

Các hàng của bảng chân trị: 2ⁿ
Phép kéo theo: p → q ≡ ¬p ∨ q ≡ ¬q → ¬p
Phủ định của phép kéo theo: ¬(p → q) ≡ p ∧ ¬q
Phép tương đương: p ↔ q ≡ (p → q) ∧ (q → p)
De Morgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q
Luật phân phối: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Phủ định của lượng từ: ¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x)
Modus ponens, modus tollens: p → q, p ⊢ q; p → q, ¬q ⊢ ¬p

Phương pháp

Hãy đếm số biến khác nhau: bảng chân trị có 2ⁿ hàng, bắt đầu bằng hàng toàn số 1.
Cho mỗi công thức con một cột riêng và điền các cột từ trong ra ngoài.
Áp dụng quy tắc của từng liên kết: → chỉ bằng 0 khi 1 → 0, ↔ bằng 1 khi hai vế giống nhau.
Với các tương đương, hãy so sánh các cột cuối theo từng hàng; với một suy luận, chỉ xét những hàng mà mọi tiền đề đều bằng 1.
Để phủ định một mệnh đề có lượng từ, hãy đưa ¬ vào trong, đổi ∀ và ∃, rồi phủ định công thức bên trong.

Tập hợp, quan hệ & hàm

Hai tập hợp: |A ∪ B| = |A| + |B| − |A ∩ B|
Ba tập hợp: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|
Hiệu và phần bù: A − B = A ∩ B′, |A′| = |U| − |A|
Tập lũy thừa và tích Descartes: |𝒫(A)| = 2^|A|, |A × B| = |A|·|B|
Tập con có k phần tử: C(n, k) = n!/(k!(n − k)!)
Hàm A → B: nᵐ; injective n!/(n − m)!; surjective Σ (−1)ᵏ C(n, k)(n − k)ᵐ
Quan hệ trên n phần tử: 2^n²; reflexive 2^{n² − n}; symmetric 2^n(n+1)/2
Hợp thành: (g ∘ f)(x) = g(f(x))

Phương pháp

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(K_n)| = n(n − 1)/2, |E(K_m,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 K_n: (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

Trong bao nhiêu hàng trong 8 hàng của bảng chân trị thì (r ∧ q) ∧ ((¬p ↔ r) ∧ (p ∨ q)) đúng? Gọi số này là N.

(r ∧ q) ∧ ((¬p ↔ r) ∧ (p ∨ q))

N =

2.Logic mệnh đề & chứng minhKhó

Suy luận với các tiền đề r → p; q → p và kết luận r → q là không hợp lệ. Hãy nhấp vào hàng của bảng chân trị là một phản ví dụ.

r → pq → p∴ r → q

1p = 1, q = 1, r = 1
2p = 1, q = 1, r = 0
3p = 1, q = 0, r = 1
4p = 1, q = 0, r = 0
5p = 0, q = 1, r = 1
6p = 0, q = 1, r = 0
7p = 0, q = 0, r = 1
8p = 0, q = 0, r = 0

3.Tập hợp, quan hệ & hàmTrung bình

Trong một nhóm 49 học sinh, 10 học sinh nói tiếng Pháp (F), 29 học sinh nói tiếng Đức (G) và 33 học sinh nói tiếng Tây Ban Nha (S). 6 học sinh nói tiếng Pháp và Đức, 5 nói tiếng Pháp và Tây Ban Nha, 18 nói tiếng Đức và Tây Ban Nha, và 4 nói cả ba thứ tiếng. Có bao nhiêu không thuộc tập nào trong ba tập?

|U| = 49

|(F ∪ G ∪ S)′| =

4.Tập hợp, quan hệ & hàmKhó

Các hàm f và g trên {1, 2, 3, 4, 5} được cho bằng bảng. Hãy tìm (f ∘ g)(1).

f: 1 ↦ 2, 2 ↦ 3, 3 ↦ 4, 4 ↦ 4, 5 ↦ 3g: 1 ↦ 2, 2 ↦ 1, 3 ↦ 1, 4 ↦ 1, 5 ↦ 1

(f ∘ g)(1) =

5.Lý thuyết đồ thịTrung bình

Đồ thị đầy đủ K₄ có bao nhiêu chu trình Hamilton khác nhau H? Các chu trình chỉ khác nhau ở đỉnh xuất phát hoặc chiều đi được tính là một.

K₄

H =

6.Lý thuyết đồ thịKhó

Hãy dùng thuật toán Dijkstra để tìm độ dài d(F) của đường đi ngắn nhất từ A đến F trong đồ thị có trọng số.

bắt đầu: Akết thúc: F

d(F) =

7.Lý thuyết số & số học đồng dưTrung bình

Giải 14x ≡ 6 (mod 23). Hãy cho nghiệm x với 0 < x < 23.

14x ≡ 6 (mod 23)

x =

8.Lý thuyết số & số học đồng dưKhó

Một khóa RSA dùng p = 17, q = 43 và e = 5. Hãy giải mã bản mã c = 48: tìm thông điệp m.

p = 17q = 43e = 5c = 48

m =

3Dung dịch

1.Logic mệnh đề & chứng minh

Đáp số: N = 1

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.

Bảng chân trị từng hàng

p = 1, q = 1, r = 1: r ∧ q = 1, ¬p = 0, ¬p ↔ r = 0, p ∨ q = 1, (¬p ↔ r) ∧ (p ∨ q) = 0, (r ∧ q) ∧ ((¬p ↔ r) ∧ (p ∨ q)) = 0

p = 1, q = 1, r = 0: r ∧ q = 0, ¬p = 0, ¬p ↔ r = 1, p ∨ q = 1, (¬p ↔ r) ∧ (p ∨ q) = 1, (r ∧ q) ∧ ((¬p ↔ r) ∧ (p ∨ q)) = 0

p = 1, q = 0, r = 1: r ∧ q = 0, ¬p = 0, ¬p ↔ r = 0, p ∨ q = 1, (¬p ↔ r) ∧ (p ∨ q) = 0, (r ∧ q) ∧ ((¬p ↔ r) ∧ (p ∨ q)) = 0

p = 1, q = 0, r = 0: r ∧ q = 0, ¬p = 0, ¬p ↔ r = 1, p ∨ q = 1, (¬p ↔ r) ∧ (p ∨ q) = 1, (r ∧ q) ∧ ((¬p ↔ r) ∧ (p ∨ q)) = 0

p = 0, q = 1, r = 1: r ∧ q = 1, ¬p = 1, ¬p ↔ r = 1, p ∨ q = 1, (¬p ↔ r) ∧ (p ∨ q) = 1, (r ∧ q) ∧ ((¬p ↔ r) ∧ (p ∨ q)) = 1

p = 0, q = 1, r = 0: r ∧ q = 0, ¬p = 1, ¬p ↔ r = 0, p ∨ q = 1, (¬p ↔ r) ∧ (p ∨ q) = 0, (r ∧ q) ∧ ((¬p ↔ r) ∧ (p ∨ q)) = 0

p = 0, q = 0, r = 1: r ∧ q = 0, ¬p = 1, ¬p ↔ r = 1, p ∨ q = 0, (¬p ↔ r) ∧ (p ∨ q) = 0, (r ∧ q) ∧ ((¬p ↔ r) ∧ (p ∨ q)) = 0

p = 0, q = 0, r = 0: r ∧ q = 0, ¬p = 1, ¬p ↔ r = 0, p ∨ q = 0, (¬p ↔ r) ∧ (p ∨ q) = 0, (r ∧ q) ∧ ((¬p ↔ r) ∧ (p ∨ q)) = 0

Đếm các hàng có giá trị 1

(r ∧ q) ∧ ((¬p ↔ r) ∧ (p ∨ q)): 0, 0, 0, 0, 1, 0, 0, 0

N = 1

Đáp số

N = 1

2.Logic mệnh đề & chứng minh

Đáp số: p = 1, q = 0, r = 1

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

Tiền đề và kết luận từng hàng

p = 1, q = 1, r = 1: 1 1 | 1

p = 1, q = 1, r = 0: 1 1 | 1

p = 1, q = 0, r = 1: 1 1 | 0

p = 1, q = 0, r = 0: 1 1 | 1

p = 0, q = 1, r = 1: 0 0 | 1

p = 0, q = 1, r = 0: 1 0 | 1

p = 0, q = 0, r = 1: 0 1 | 0

p = 0, q = 0, r = 0: 1 1 | 1

Phản ví dụ

p = 1, q = 0, r = 1

Đáp số

p = 1, q = 0, r = 1

Một suy luận có dạng này trông giống một quy tắc hợp lệ, nhưng một hàng là đủ để cho thấy nó không hợp lệ.

3.Tập hợp, quan hệ & hàm

Đáp số: |(F ∪ G ∪ S)′| = 2

Tập hợp và biểu đồ Venn: A ∪ B gồm các phần tử thuộc A hoặc B (hoặc cả hai), A ∩ B gồm các phần tử thuộc cả hai, A − B gồm các phần tử của A không thuộc B, và phần bù A′ là mọi thứ trong U không thuộc A. Trong biểu đồ Venn, mọi biểu thức tập hợp là hợp của các vùng, nên hãy đếm theo từng vùng. Nguyên lý bao hàm – loại trừ: |A ∪ B| = |A| + |B| − |A ∩ B|, và |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

Phần giữa và các cặp

F ∩ G ∩ S: 4

F ∩ G chỉ: 6 − 4 = 2

F ∩ S chỉ: 5 − 4 = 1

G ∩ S chỉ: 18 − 4 = 14

Các tập đơn

F chỉ: 10 − 2 − 1 − 4 = 3

G chỉ: 29 − 2 − 14 − 4 = 9

S chỉ: 33 − 1 − 14 − 4 = 14

Đáp số

|F ∪ G ∪ S| = 47

|(F ∪ G ∪ S)′| = 49 − 47 = 2

Đáp số

|(F ∪ G ∪ S)′| = 2

4.Tập hợp, quan hệ & hàm

Đáp số: (f ∘ g)(1) = 3

Hàm và phép đếm: một hàm f: A → B cho mỗi phần tử của A đúng một ảnh trong B. f là đơn ánh (một-một) khi các phần tử khác nhau có ảnh khác nhau, toàn ánh (lên) khi mọi phần tử của B đều là một ảnh, và song ánh khi cả hai điều kiện đều đúng. Với |A| = m và |B| = n có nᵐ hàm, n!/(n − m)! hàm đơn ánh (m ≤ n), và theo nguyên lý bao hàm – loại trừ có Σ (−1)ᵏ·C(n, k)·(n − k)ᵐ hàm toàn ánh. |𝒫(A)| = 2ᵐ và |A × B| = m·n.

Hàm bên trong

g(1) = 2

Hàm bên ngoài

f(2) = 3

(f ∘ g)(1) = 3

Đáp số

(f ∘ g)(1) = 3

5.Lý thuyết đồ thị

Đáp số: H = 3

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.

Đếm

H = (4 − 1)!/2 = 6/2 = 3

Đáp số

H = 3

6.Lý thuyết đồ thị

Đáp số: d(F) = 24

Đườ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.

Dijkstra từng vòng

Mỗi dòng: đỉnh được chốt, khoảng cách cuối cùng của nó, và các đỉnh kề có khoảng cách được cải thiện.

A (0): B: 13, C: 12

C (12): E: 21

B (13): D: 27

E (21): D: 26, F: 24

F (24)

D (26)

Đường đi ngắn nhất

A → C → E → F

d(F) = 24

Đáp số

d(F) = 24

7.Lý thuyết số & số học đồng dư

Đáp số: x = 7

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

Nghịch đảo của 14

r = 23, t = 0

r = 14, q = 1, t = 1

r = 9, q = 1, t = −1

r = 5, q = 1, t = 2

r = 4, q = 1, t = −3

r = 1, q = 4, t = 5

14⁻¹ ≡ 5 (mod 23)

Giải

x ≡ 5·6 = 30 ≡ 7 (mod 23)

kiểm tra: 14·7 = 98 ≡ 6 (mod 23)

Đáp số

x = 7

8.Lý thuyết số & số học đồng dư

Đáp số: m = 243

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.

Số mũ bí mật

n = 731, φ(n) = 672

d = 5⁻¹ mod 672 = 269

Giải mã bằng bình phương lặp

269 = 256 + 8 + 4 + 1

48¹ ≡ 48 (mod 731)

48² ≡ 111 (mod 731)

48⁴ ≡ 625 (mod 731)

48⁸ ≡ 271 (mod 731)

48¹⁶ ≡ 341 (mod 731)

48³² ≡ 52 (mod 731)

48⁶⁴ ≡ 511 (mod 731)

48¹²⁸ ≡ 154 (mod 731)

48²⁵⁶ ≡ 324 (mod 731)

48²⁶⁹ ≡ 48·625·271·324 ≡ 243 (mod 731)

Tin nhắn

m = 243

kiểm tra: 243⁵ mod 731 = 48

Đáp số

m = 243

ExamProblems · examproblems.com/courses/discrete-mathematics