1. Biểu thức nào sau đây biểu diễn đúng quy tắc De Morgan cho hai tập hợp $A$ và $B$?
A. $\overline{A \cup B} = \overline{A} \cup \overline{B}$
B. $\overline{A \cap B} = \overline{A} \cap \overline{B}$
C. $\overline{A \cup B} = \overline{A} \cap \overline{B}$
D. $\overline{A \cap B} = A \cup B$
2. Số các số nguyên dương nhỏ hơn hoặc bằng 100 chia hết cho 2 hoặc 5 là bao nhiêu?
3. Cho quan hệ $R = \{(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)\}$ trên tập $A = \{1, 2, 3\}$. Quan hệ này có tính chất nào sau đây?
A. Phản xạ và bắc cầu
B. Đối xứng và phản xạ
C. Bắc cầu và đối xứng
D. Phản xạ, đối xứng và bắc cầu
4. Một người có 5 quyển sách Toán, 6 quyển sách Lý và 7 quyển sách Hóa. Hỏi có bao nhiêu cách xếp các quyển sách này lên một kệ sao cho các quyển sách cùng môn nằm cạnh nhau?
A. $5!6!7!$
B. $3!$
C. $3!5!6!7!$
D. $5! + 6! + 7!$
5. Trong một nhóm 10 người, mỗi người quen ít nhất 5 người khác. Chứng minh rằng có thể chọn ra 3 người sao cho họ quen lẫn nhau.
A. Đúng, vì theo nguyên lý Dirichlet.
B. Sai, vì không đủ thông tin.
C. Đúng, vì tồn tại một tam giác trong đồ thị.
D. Sai, vì số người quá ít.
6. Cho $A$ và $B$ là hai tập hợp hữu hạn. Biết $|A| = 5$, $|B| = 3$ và $|A \cup B| = 7$. Tính $|A \cap B|$.
7. Cho quan hệ $R$ trên tập $A = \{1, 2, 3\}$ được biểu diễn bởi ma trận $M_R = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix}$. Hỏi $R$ có tính chất nào sau đây?
A. Phản xạ và đối xứng
B. Phản xạ và bắc cầu
C. Đối xứng và bắc cầu
D. Phản xạ, đối xứng và bắc cầu
8. Cho hàm $f: A \rightarrow B$. Điều kiện nào sau đây là cần và đủ để $f$ là song ánh?
A. $f$ là đơn ánh.
B. $f$ là toàn ánh.
C. $f$ vừa là đơn ánh vừa là toàn ánh.
D. $f$ không là đơn ánh và không là toàn ánh.
9. Cho đồ thị có ma trận kề là ma trận đơn vị. Đồ thị này có tính chất gì?
A. Đồ thị đầy đủ.
B. Đồ thị có chu trình Hamilton.
C. Đồ thị không có cạnh.
D. Mỗi đỉnh có một khuyên.
10. Cho đồ thị vô hướng $G = (V, E)$ với $V = \{1, 2, 3, 4\}$ và $E = \{(1, 2), (2, 3), (3, 4), (4, 1)\}$. Đồ thị này có phải là đồ thị Euler không?
A. Không, vì có đỉnh bậc lẻ.
B. Có, vì tất cả các đỉnh đều có bậc chẵn.
C. Không, vì đồ thị không liên thông.
D. Có, vì đồ thị có chu trình Hamilton.
11. Cho một mạng lưới giao thông gồm các thành phố và các con đường nối giữa chúng. Để tìm đường đi ngắn nhất giữa hai thành phố, thuật toán nào sau đây thường được sử dụng?
A. Thuật toán Prim
B. Thuật toán Kruskal
C. Thuật toán Dijkstra
D. Thuật toán Ford-Fulkerson
12. Cho tập $A = \{1, 2, 3\}$ và $B = \{a, b\}$. Hỏi số lượng các hàm từ $A$ vào $B$ là bao nhiêu?
13. Cho $A$ và $B$ là hai tập hợp. Mệnh đề nào sau đây đúng?
A. $A \cup B \subseteq A \cap B$
B. $A \cap B \subseteq A \cup B$
C. Nếu $A \subseteq B$ thì $B \subseteq A$
D. $A \setminus B = B \setminus A$
14. Tìm số nghiệm nguyên không âm của phương trình $x_1 + x_2 + x_3 = 10$.
A. 66
B. 120
C. 132
D. 220
15. Giá trị của biểu thức logic $(p \rightarrow q) \lor (q \rightarrow p)$ luôn là gì?
A. Luôn đúng
B. Luôn sai
C. Phụ thuộc vào $p$ và $q$
D. Không xác định
16. Mệnh đề nào sau đây tương đương logic với $p \rightarrow q$?
A. $\neg q \rightarrow \neg p$
B. $q \rightarrow p$
C. $\neg p \rightarrow \neg q$
D. $p \land q$
17. Cho hàm $f: \mathbb{Z} \rightarrow \mathbb{Z}$ xác định bởi $f(x) = 2x$. Hàm này có phải là toàn ánh không?
A. Có, vì mọi số nguyên đều có ảnh.
B. Không, vì không phải mọi số nguyên đều có tạo ảnh.
C. Có, vì hàm số luôn tăng.
D. Không thể xác định.
18. Định nghĩa nào sau đây là đúng về quan hệ tương đương?
A. Quan hệ có tính phản xạ và đối xứng.
B. Quan hệ có tính đối xứng và bắc cầu.
C. Quan hệ có tính phản xạ và bắc cầu.
D. Quan hệ có tính phản xạ, đối xứng và bắc cầu.
19. Xét một đồ thị vô hướng liên thông $G$ với $n$ đỉnh và $m$ cạnh. Điều kiện nào sau đây là cần và đủ để $G$ là một cây?
A. $m = n$
B. $m = n + 1$
C. $m = n - 1$
D. $m < n - 1$
20. Số cạnh của một đồ thị đầy đủ $K_n$ là bao nhiêu?
A. $n$
B. $n-1$
C. $\frac{n(n-1)}{2}$
D. $n^2$
21. Cho một cây có 10 đỉnh. Hỏi cây đó có bao nhiêu cạnh?
22. Cho đồ thị phẳng liên thông có 10 đỉnh và 15 cạnh. Hỏi đồ thị này có bao nhiêu miền?
23. Cho hàm $f(x) = x^2 + 1$. Hàm này có phải là đơn ánh không?
A. Có, vì với mọi $x_1 \neq x_2$ thì $f(x_1) \neq f(x_2)$.
B. Không, vì tồn tại $x_1 \neq x_2$ mà $f(x_1) = f(x_2)$.
C. Có, vì hàm số luôn tăng.
D. Không thể xác định.
24. Cho tập hợp $A = \{1, 2, 3, 4, 5\}$. Hỏi có bao nhiêu tập con của $A$ chứa phần tử 1?
25. Trong bao nhiêu cách có thể xếp 5 người đàn ông và 4 người phụ nữ vào một hàng sao cho không có hai người phụ nữ nào đứng cạnh nhau?
A. 5! * 4!
B. 9!
C. 5! * C(6,4) * 4!
D. P(9,4)
26. Cho $A = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$. Hỏi có bao nhiêu tập con của $A$ có đúng 5 phần tử và chứa ít nhất một số chẵn?
A. 252
B. 126
C. 246
D. 150
27. Cho $f(n) = n^2 + 1$ và $g(n) = 2n$. Hàm nào tăng nhanh hơn khi $n$ tiến tới vô cùng?
A. $f(n)$
B. $g(n)$
C. Cả hai hàm tăng nhanh như nhau.
D. Không thể so sánh.
28. Trong một giải đấu bóng đá có 8 đội tham gia, mỗi đội phải đấu với mỗi đội khác đúng một trận. Hỏi có tất cả bao nhiêu trận đấu?
29. Số các xâu nhị phân độ dài 8 bắt đầu bằng 11 hoặc kết thúc bằng 00 là bao nhiêu?
A. 64
B. 128
C. 96
D. 160
30. Số các số nguyên dương nhỏ hơn 1000 và nguyên tố cùng nhau với 1000 là bao nhiêu?
A. 300
B. 400
C. 500
D. 600
