1. Cho tập hợp $A = \{1, 2, 3\}$ và $B = \{a, b\}$. Tính lực lượng của tích Descartes $A \times B$.
2. Tìm số nghiệm nguyên dương của phương trình $x_1 + x_2 + x_3 = 7$.
3. Xác định số lượng hàm khác nhau từ tập $A$ có lực lượng 2 đến tập $B$ có lực lượng 3.
4. Cho quan hệ $R = \{(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)\}$ trên tập hợp $A = \{1, 2, 3\}$. Quan hệ $R$ có tính chất nào sau đây?
A. Phản xạ, đối xứng và bắc cầu
B. Phản xạ và đối xứng
C. Đối xứng và bắc cầu
D. Phản xạ và bắc cầu
5. Đồ thị vô hướng $G = (V, E)$ có bậc của mỗi đỉnh đều bằng 3. Nếu $|V| = 10$, tính số cạnh của đồ thị.
6. Một ngôn ngữ hình thức được định nghĩa bởi một bộ $\langle V, T, S, P \rangle$. $V$ đại diện cho gì?
A. Tập các biến
B. Tập các ký tự kết thúc
C. Ký hiệu bắt đầu
D. Tập các luật sản xuất
7. Tìm số các số nguyên dương nhỏ hơn 100 và chia hết cho 2 hoặc 3.
8. Cho quan hệ thứ tự bộ phận $R$ trên tập $A$. Phát biểu nào sau đây là đúng?
A. $R$ phản xạ, đối xứng và bắc cầu.
B. $R$ phản xạ, phản đối xứng và bắc cầu.
C. $R$ đối xứng và bắc cầu.
D. $R$ phản xạ và đối xứng.
9. Cho hàm $f(x) = x^2 + 1$ và $g(x) = 2x - 3$. Tính $f(g(x))$.
A. $4x^2 - 12x + 10$
B. $2x^2 - 1$
C. $4x^2 - 12x + 8$
D. $4x^2 - 12x + 11$
10. 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}$. Quan hệ $R$ có tính chất nào?
A. Phản xạ
B. Đối xứng
C. Bắc cầu
D. Phản xạ và đối xứng
11. Cho mệnh đề $P$: `Hôm nay trời mưa` và $Q$: `Tôi ở nhà`. Mệnh đề `$P \rightarrow Q$` có nghĩa là gì?
A. Nếu hôm nay trời mưa thì tôi ở nhà.
B. Hôm nay trời mưa và tôi ở nhà.
C. Hôm nay trời mưa hoặc tôi ở nhà.
D. Nếu tôi ở nhà thì hôm nay trời mưa.
12. Tìm số các hoán vị của các chữ cái trong từ `MISSISSIPPI`.
A. 34650
B. 12000
C. 16800
D. 20000
13. Cho đồ thị $K_n$ là đồ thị đầy đủ với $n$ đỉnh. Hỏi đồ thị $K_n$ có bao nhiêu cạnh?
A. $n$
B. $n^2$
C. $\frac{n(n-1)}{2}$
D. $n!$
14. Cho $f(n) = n^2 + 3n + 1$. Tính $f(n+1) - f(n)$.
A. $2n + 4$
B. $2n + 3$
C. $2n + 5$
D. $2n + 6$
15. Trong một nhóm 100 người, có 40 người thích bóng đá, 30 người thích bóng chuyền và 10 người thích cả hai môn. Hỏi có bao nhiêu người không thích môn nào trong hai môn này?
16. Định nghĩa nào sau đây là đúng về đồ thị Hamilton?
A. Đồ thị có chu trình đi qua tất cả các cạnh.
B. Đồ thị có chu trình đi qua tất cả các đỉnh.
C. Đồ thị có đường đi đi qua tất cả các cạnh.
D. Đồ thị có đường đi đi qua tất cả các đỉnh.
17. Đồ thị nào sau đây là đồ thị Euler?
A. Đồ thị có một đỉnh bậc lẻ
B. Đồ thị có hai đỉnh bậc lẻ
C. Đồ thị có tất cả các đỉnh bậc chẵn
D. Đồ thị có tất cả các đỉnh bậc lẻ
18. Cho $A = \{1, 2, 3, 4, 5\}$. Hỏi có bao nhiêu tập con của $A$ chứa phần tử 1?
19. Cho đồ thị phẳng liên thông có 10 đỉnh và 15 cạnh. Hỏi đồ thị có bao nhiêu miền?
20. Cho $A = \{1, 2, 3\}$. Tìm số quan hệ hai ngôi trên $A$.
21. Trong logic mệnh đề, luật De Morgan phát biểu rằng $\neg (P \vee Q)$ tương đương với:
A. $\neg P \vee \neg Q$
B. $\neg P \wedge \neg Q$
C. $P \wedge Q$
D. $P \vee Q$
22. Số các xâu nhị phân có độ dài 8 mà bắt đầu bằng `11` hoặc kết thúc bằng `00` là bao nhiêu?
A. 128
B. 64
C. 192
D. 96
23. Cho $A = \{1, 2, 3, 4\}$. Tìm số quan hệ tương đương trên $A$.
24. Trong một nhóm 10 người, có bao nhiêu cách chọn ra một nhóm 3 người để tham gia một dự án?
A. 120
B. 720
C. 360
D. 240
25. Tìm số nghiệm nguyên không âm của phương trình $x_1 + x_2 + x_3 + x_4 = 10$.
A. 286
B. 120
C. 364
D. 220
26. Cho đồ thị $G$ có ma trận kề $A$. Phần tử $a_{ij}$ của ma trận $A^2$ biểu diễn đ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ố đỉnh kề với đỉnh $i$.
27. Trong đại số Boolean, biểu thức $A + A`B$ tương đương với biểu thức nào?
28. Trong logic vị từ, lượng từ $\forall$ có nghĩa là gì?
A. Tồn tại
B. Với mọi
C. Không tồn tại
D. Có duy nhất
29. Số cạnh tối thiểu trong một đồ thị liên thông có $n$ đỉnh là bao nhiêu?
A. $n-1$
B. $n$
C. $n+1$
D. $n/2$
30. Phát biểu nào sau đây là đúng về cây (tree)?
A. Cây chứa chu trình.
B. Cây là đồ thị liên thông không có chu trình.
C. Cây là đồ thị không liên thông.
D. Cây có thể có nhiều hơn một gốc.
