1. Cho quan hệ $R$ trên tập $A$. Nếu $R$ vừa đối xứng, vừa phản đối xứng thì $R$ là:
A. Quan hệ đồng nhất
B. Quan hệ toàn phần
C. Quan hệ rỗng
D. Quan hệ bù
2. Cho $A = \{1, 2, 3\}$ và $B = \{a, b\}$. Hỏi có bao nhiêu hàm đơn ánh từ $B$ vào $A$?
3. Cho hàm $f(x) = x^2 + 1$ và $g(x) = 2x - 3$. Tìm $(f \circ g)(x)$.
A. $4x^2 - 12x + 10$
B. $2x^2 - 1$
C. $4x^2 - 12x + 8$
D. $2x^3 - 3x^2 + 2x - 3$
4. Cho tập hợp $A = \{1, 2, 3, 4\}$. Số quan hệ hai ngôi trên $A$ là:
A. $2^{16}$
B. $2^{4}$
C. 16
D. 4
5. Cho đồ thị $G$ có ma trận kề là $A$. Phần tử $a_{ij}$ của $A^2$ biểu thị điều gì?
A. Số đường đi độ dài 2 từ đỉnh $i$ đến đỉnh $j$
B. Số đường đi độ dài 1 từ đỉnh $i$ đến đỉnh $j$
C. Số đường đi độ dài 3 từ đỉnh $i$ đến đỉnh $j$
D. Số đường đi từ đỉnh $i$ đến đỉnh $j$
6. Đồ thị $G = (V, E)$ có $|V| = n$ đỉnh và $|E| = m$ cạnh. Nếu $G$ là đồ thị phẳng, phát biểu nào sau đây là đúng?
A. $m \le 3n - 6$
B. $m \ge 3n - 6$
C. $m = 3n - 6$
D. $m > 3n - 6$
7. 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?
8. Cho quan hệ $R = \{(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 1)\}$ trên tập $A = \{1, 2, 3, 4\}$. Quan hệ $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
9. Mệnh đề nào sau đây tương đương với $p \rightarrow q$?
A. $\neg p \lor q$
B. $p \lor \neg q$
C. $p \land q$
D. $\neg p \land \neg q$
10. Số các số nguyên dương nhỏ hơn hoặc bằng 100 chia hết cho 2 hoặc 3 là:
11. Cho $A = \{1, 2, 3\}$. Số quan hệ tương đương trên $A$ là:
12. Đẳng thức nào sau đây là đúng?
A. $C(n, k) = C(n, n-k)$
B. $C(n, k) = C(n, k-1)$
C. $C(n, k) = C(n-1, k)$
D. $C(n, k) = C(n-1, k-1)$
13. Trong đại số Boole, biểu thức $A + A`B$ tương đương với:
A. $A + B$
B. $AB$
C. $A`B$
D. $A` + B$
14. Cho quan hệ $R = \{(a, b), (b, c)\}$. Để $R$ có tính bắc cầu, ta cần thêm cặp nào vào $R$?
A. $(a, c)$
B. $(b, a)$
C. $(c, b)$
D. $(c, a)$
15. Một nhóm có 6 nam và 4 nữ. Cần chọn ra 3 người sao cho có ít nhất 1 nữ. Hỏi có bao nhiêu cách chọn?
A. 116
B. 120
C. 100
D. 110
16. Cho $A = \{1, 2, 3, 4, 5\}$ và $B = \{a, b, c\}$. Hỏi có bao nhiêu hàm toàn ánh từ $A$ vào $B$?
A. 150
B. 243
C. 120
D. 60
17. Cho một đồ thị đầy đủ $K_n$ có $n$ đỉnh. Số cạnh của $K_n$ là bao nhiêu?
A. $\frac{n(n-1)}{2}$
B. $\frac{n(n+1)}{2}$
C. $n-1$
D. $n$
18. Có bao nhiêu cách xếp 5 người vào một bàn tròn?
19. Cho đồ thị $G$ có 6 đỉnh và 9 cạnh. Hỏi số miền của biểu đồ phẳng của $G$ là bao nhiêu (giả sử $G$ liên thông)?
20. Cho $f(x) = x + 1$ và $g(x) = x^2$. Hỏi $(g \circ f)(x)$ là gì?
A. $x^2 + 2x + 1$
B. $x^2 + 1$
C. $x^3 + x^2$
D. $x^2 + x + 1$
21. Cho $A = \{1, 2, 3\}$. Có bao nhiêu hàm từ $A$ vào $A$?
22. Số cạnh tối thiểu trong một đồ thị liên thông có $n$ đỉnh là:
A. $n-1$
B. $n$
C. $n+1$
D. $n/2$
23. Cho $f: A \rightarrow B$ và $g: B \rightarrow C$. Nếu $f$ và $g$ đều là song ánh thì $g \circ f$ là:
A. Song ánh
B. Đơn ánh nhưng không toàn ánh
C. Toàn ánh nhưng không đơn ánh
D. Không đơn ánh và không toàn ánh
24. Cho $A = \{1, 2, 3, 4, 5, 6\}$. Quan hệ $R = \{(x, y) \in A \times A \mid x + y = 7\}$ là:
A. $\varnothing$
B. {\{ (1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1) \}}
C. {\{ (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6) \}}
D. {\{ (1, 7), (2, 7), (3, 7), (4, 7), (5, 7), (6, 7) \}}
25. Cho $G$ là đồ thị vô hướng liên thông. Điều kiện cần và đủ để $G$ có chu trình Euler là:
A. Mọi đỉnh của $G$ có bậc chẵn
B. Mọi đỉnh của $G$ có bậc lẻ
C. $G$ có ít nhất một đỉnh bậc chẵn
D. $G$ có ít nhất một đỉnh bậc lẻ
26. Cho $f(n) = 2f(n-1) + 1$ với $f(0) = 1$. Tìm $f(3)$.
27. Cho $A = \{a, b, c\}$. Hỏi có bao nhiêu quan hệ thứ tự bộ phận trên $A$ chứa quan hệ $R = \{(a, b), (a, c)\}$?
28. Phát biểu nào sau đây là đúng về cây?
A. Cây là đồ thị liên thông không có chu trình
B. Cây là đồ thị có chu trình
C. Cây là đồ thị không liên thông
D. Cây là đồ thị đầy đủ
29. Cho đồ thị vô hướng $G$ có 5 đỉnh. Bậc của mỗi đỉnh là 2. Hỏi $G$ có bao nhiêu cạnh?
30. Cho tập $A = \{1, 2, 3, 4, 5, 6, 7, 8\}$. Có bao nhiêu tập con của $A$ có đúng 3 phần tử?
A. 56
B. 21
C. 336
D. 40320
