1. Một hàm f: A → B được gọi là đơn ánh (injective) nếu:
A. Với mọi b thuộc B, tồn tại ít nhất một a thuộc A sao cho f(a) = b.
B. Với mọi a1, a2 thuộc A, nếu f(a1) = f(a2) thì a1 = a2.
C. Với mọi a thuộc A, f(a) = a.
D. Với mọi a thuộc A, f(a) là một số nguyên.
2. Quan hệ R trên tập hợp A được gọi là quan hệ phản xạ nếu:
A. Với mọi a, b thuộc A, nếu (a, b) thuộc R thì (b, a) thuộc R.
B. Với mọi a thuộc A, (a, a) thuộc R.
C. Với mọi a, b, c thuộc A, nếu (a, b) thuộc R và (b, c) thuộc R thì (a, c) thuộc R.
D. Với mọi a, b thuộc A, nếu (a, b) thuộc R thì (a, b) không thuộc R.
3. Phát biểu nào sau đây về đồ thị Euler là đúng?
A. Đồ thị Euler luôn chứa chu trình Hamilton.
B. Đồ thị Euler là đồ thị có bậc của tất cả các đỉnh đều là số chẵn.
C. Đồ thị Euler là đồ thị có bậc của tất cả các đỉnh đều là số lẻ.
D. Đồ thị Euler không tồn tại trong thực tế.
4. Số cách chọn ra 2 học sinh từ một nhóm 5 học sinh để tham gia đội văn nghệ là:
A. 5!
B. P(5, 2)
C. C(5, 2)
D. 2^5
5. Mệnh đề nào sau đây là hằng đúng (tautology)?
A. p ∨ ¬p
B. p ∧ ¬p
C. p → q
D. p ↔ q
6. Cho hai tập hợp A = {1, 2, 3} và B = {3, 4, 5}. Giao của hai tập hợp A ∩ B là:
A. {1, 2, 3, 4, 5}
B. {1, 2}
C. {3}
D. {4, 5}
7. Trong tổ hợp, tổ hợp chập k của n phần tử (k ≤ n) khác chỉnh hợp chập k của n phần tử ở điểm nào?
A. Tổ hợp có quan tâm đến thứ tự, chỉnh hợp không quan tâm.
B. Tổ hợp và chỉnh hợp đều quan tâm đến thứ tự.
C. Tổ hợp không quan tâm đến thứ tự, chỉnh hợp có quan tâm.
D. Tổ hợp và chỉnh hợp đều không quan tâm đến thứ tự.
8. Phương pháp chứng minh nào sau đây thường được sử dụng để chứng minh một mệnh đề đúng cho tất cả các số tự nhiên?
A. Chứng minh trực tiếp
B. Chứng minh phản chứng
C. Chứng minh bằng quy nạp toán học
D. Chứng minh bằng phản ví dụ
9. Cho tập hợp A = {1, 2, 3}. Có bao nhiêu quan hệ hai ngôi khác nhau có thể xác định trên tập hợp A?
10. Mệnh đề 'Nếu trời mưa thì đường ướt' tương đương logic với mệnh đề nào sau đây?
A. Nếu trời không mưa thì đường không ướt.
B. Nếu đường ướt thì trời mưa.
C. Nếu đường không ướt thì trời không mưa.
D. Trời mưa và đường ướt.
11. Trong chứng minh bằng quy nạp toán học, bước cơ sở (base case) là gì?
A. Giả sử mệnh đề đúng cho một số tự nhiên k.
B. Chứng minh mệnh đề đúng cho số tự nhiên nhỏ nhất (thường là 0 hoặc 1).
C. Chứng minh mệnh đề đúng cho tất cả các số tự nhiên.
D. Chứng minh mệnh đề sai cho một số tự nhiên cụ thể.
12. Cho tập hợp A = {a, b, c, d}. Số hoán vị của tập hợp A là:
A. 4
B. 2^4
C. 4!
D. C(4, 2)
13. Trong lý thuyết tập hợp, phép toán nào sau đây trả về một tập hợp chứa tất cả các phần tử thuộc ít nhất một trong hai tập hợp đã cho?
A. Giao của hai tập hợp
B. Hợp của hai tập hợp
C. Hiệu của hai tập hợp
D. Tích Descartes của hai tập hợp
14. Đồ thị vô hướng được gọi là liên thông nếu:
A. Mỗi đỉnh trong đồ thị đều có bậc lớn hơn 0.
B. Có một đường đi giữa bất kỳ cặp đỉnh nào trong đồ thị.
C. Số cạnh bằng số đỉnh trừ 1.
D. Đồ thị không chứa chu trình.
15. Một đồ thị đầy đủ (complete graph) Kn là đồ thị mà:
A. Không có cạnh nào.
B. Mỗi đỉnh đều có bậc bằng 1.
C. Có cạnh nối giữa mọi cặp đỉnh phân biệt.
D. Chỉ có một chu trình duy nhất.
16. Cây khung nhỏ nhất (Minimum Spanning Tree - MST) của một đồ thị liên thông có trọng số là:
A. Một đường đi Hamilton có tổng trọng số nhỏ nhất.
B. Một chu trình Euler có tổng trọng số nhỏ nhất.
C. Một cây con liên thông bao gồm tất cả các đỉnh và có tổng trọng số các cạnh là nhỏ nhất.
D. Một đồ thị con đầy đủ có tổng trọng số nhỏ nhất.
17. Trong lý thuyết đồ thị, bậc của một đỉnh là gì?
A. Số đỉnh trong đồ thị.
B. Số cạnh trong đồ thị.
C. Số cạnh liên thuộc với đỉnh đó.
D. Độ dài đường đi ngắn nhất từ đỉnh đó đến đỉnh khác.
18. Trong toán học tổ hợp, chỉnh hợp chập k của n phần tử (k ≤ n) là gì?
A. Số cách chọn k phần tử từ n phần tử, không quan tâm đến thứ tự.
B. Số cách chọn k phần tử từ n phần tử, có quan tâm đến thứ tự.
C. Số cách chia n phần tử thành k nhóm.
D. Số cách sắp xếp n phần tử vào k vị trí.
19. Trong logic mệnh đề, luật De Morgan thứ hai phát biểu:
A. ¬(p ∧ q) ≡ ¬p ∨ ¬q
B. ¬(p ∨ q) ≡ ¬p ∧ ¬q
C. p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
D. p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
20. Trong số học mô-đun, phép toán nào sau đây là phép toán nghịch đảo mô-đun của a modulo m?
A. Tìm số x sao cho (a + x) ≡ 0 (mod m).
B. Tìm số x sao cho (a * x) ≡ 1 (mod m).
C. Tìm số x sao cho a^x ≡ 1 (mod m).
D. Tìm số x sao cho x^a ≡ 1 (mod m).
21. Tính chất bắc cầu (transitive) của một quan hệ R trên tập A được định nghĩa là:
A. Với mọi a thuộc A, (a, a) thuộc R.
B. Với mọi a, b thuộc A, nếu (a, b) thuộc R thì (b, a) thuộc R.
C. Với mọi a, b, c thuộc A, nếu (a, b) thuộc R và (b, c) thuộc R thì (a, c) thuộc R.
D. Với mọi a, b thuộc A, nếu (a, b) thuộc R thì a = b.
22. Phép toán nào sau đây KHÔNG phải là phép toán cơ bản trong đại số Boolean?
A. Phép AND
B. Phép OR
C. Phép NOT
D. Phép XOR
23. Hàm f: Z → Z được định nghĩa bởi f(x) = 2x + 1. Hàm này có phải là song ánh (bijective) không?
A. Đúng
B. Sai
C. Không xác định
D. Chỉ đúng khi x ≥ 0
24. Trong số học mô-đun, (7 mod 3) + (8 mod 3) mod 3 bằng:
25. Trong đồ thị có trọng số, thuật toán Dijkstra được sử dụng để tìm:
A. Chu trình Euler.
B. Chu trình Hamilton.
C. Đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác.
D. Cây khung nhỏ nhất.
26. Một cây (tree) là một loại đồ thị đặc biệt. Tính chất nào sau đây KHÔNG đúng với cây?
A. Liên thông.
B. Không có chu trình.
C. Có duy nhất một đường đi giữa mọi cặp đỉnh.
D. Có chứa chu trình.
27. Số cạnh tối thiểu trong một đồ thị liên thông có n đỉnh là bao nhiêu?
A. n
B. n - 1
C. n + 1
D. n^2
28. Biểu thức logic ¬(p ∨ q) ≡ ...
A. ¬p ∨ ¬q
B. ¬p ∧ ¬q
C. p ∧ q
D. p ∨ q
29. Thuật toán Euclid mở rộng (Extended Euclidean Algorithm) được sử dụng để làm gì?
A. Tìm ước số chung lớn nhất (GCD) của hai số nguyên.
B. Tìm bội số chung nhỏ nhất (LCM) của hai số nguyên.
C. Tìm nghịch đảo mô-đun của một số nguyên modulo một số nguyên khác.
D. Phân tích một số nguyên ra thừa số nguyên tố.
30. Trong logic vị từ, lượng từ '∀' được gọi là:
A. Lượng từ tồn tại.
B. Lượng từ phổ quát.
C. Lượng từ duy nhất.
D. Lượng từ phủ định.
