1. Trong một lớp học có 30 sinh viên, có 15 sinh viên thích Toán, 12 sinh viên thích Lý, và 8 sinh viên thích cả Toán và Lý. Hỏi có bao nhiêu sinh viên không thích môn nào trong hai môn này?
2. Trong lý thuyết đồ thị, phát biểu nào sau đây là đúng về đồ thị phẳng?
A. Mọi đồ thị đều là đồ thị phẳng.
B. Đồ thị phẳng là đồ thị có thể vẽ trên mặt phẳng sao cho không có cạnh nào cắt nhau.
C. Đồ thị phẳng là đồ thị có chu trình Euler.
D. Đồ thị phẳng là đồ thị có chu trình Hamilton.
3. Cho đồ thị $G$ có ma trận kề $A$. Phần tử $a_{ij}$ của $A^2$ biểu diễn điều gì?
A. Độ dài đường đi ngắn nhất từ đỉnh $i$ đến đỉnh $j$.
B. Số đường đi độ dài 2 từ đỉnh $i$ đến đỉnh $j$.
C. Số cạnh giữa đỉnh $i$ và đỉnh $j$.
D. Bậc của đỉnh $i$.
4. Cho bảng chân trị của mệnh đề $P \rightarrow Q$. Khi nào $P \rightarrow Q$ sai?
A. Khi $P$ đúng và $Q$ đúng.
B. Khi $P$ đúng và $Q$ sai.
C. Khi $P$ sai và $Q$ đúng.
D. Khi $P$ sai và $Q$ sai.
5. Định lý Euler phát biểu điều gì về số đỉnh, số cạnh và số mặt của một đồ thị phẳng liên thông?
A. $V - E + F = 0$
B. $V - E + F = 1$
C. $V - E + F = 2$
D. $V + E - F = 2$
6. Cho đồ thị vô hướng $G = (V, E)$ với $V = \{a, b, c, d\}$ và $E = \{(a, b), (b, c), (c, d), (d, a)\}$. Bậc của đỉnh $b$ là bao nhiêu?
7. Cho $f(x) = x^2$ và $g(x) = x + 1$. Tìm $f(g(x))$.
A. $x^2 + 1$
B. $x^2 + x + 1$
C. $x^2 + 2x + 1$
D. $x^3 + x^2$
8. 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 4 người sao cho họ quen biết lẫn nhau.
A. Bài toán không thể chứng minh.
B. Áp dụng nguyên lý Dirichlet.
C. Sử dụng quy nạp.
D. Chứng minh bằng phản chứng.
9. Cho $f(n) = n^2 + 1$ và $g(n) = n$. 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.
10. Một ngôn ngữ hình thức được định nghĩa bởi những thành phần nào?
A. Bảng chữ cái, tập các chuỗi, ngữ pháp.
B. Bảng chữ cái, tập các từ, ngữ pháp.
C. Bảng chữ cái, tập các ký tự, ngữ nghĩa.
D. Bảng chữ cái, tập các ký hiệu, cú pháp.
11. Một cây có $n$ đỉnh thì có bao nhiêu cạnh?
12. Cho quan hệ $R$ trên tập $A$. Điều kiện nào sau đây là cần và đủ để $R$ là một quan hệ thứ tự bộ phận?
A. Phản xạ, đối xứng, bắc cầu.
B. Phản xạ, phản đối xứng, bắc cầu.
C. Phản xạ, đối xứng, không bắc cầu.
D. Không phản xạ, phản đối xứng, bắc cầu.
13. Cho $A = \{1, 2, 3, 4\}$ và $R = \{(1, 2), (2, 3), (3, 4)\}$. Tìm bao đóng bắc cầu của $R$.
A. $\emptyset$
B. $\{(1, 2), (2, 3), (3, 4)\}$
C. $\{(1, 2), (2, 3), (3, 4), (1, 3), (2, 4), (1, 4)\}$
D. $\{(1, 1), (2, 2), (3, 3), (4, 4)\}$
14. Đồ thị nào sau đây có chu trình 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ẻ.
15. Số các hoán vị của tập hợp $A = \{a, b, c, d, e\}$ là bao nhiêu?
A. 5
B. 25
C. 120
D. 3125
16. Mệnh đề nào sau đây là phủ định của mệnh đề `Mọi số thực đều lớn hơn 0`?
A. Có ít nhất một số thực nhỏ hơn hoặc bằng 0.
B. Mọi số thực đều nhỏ hơn 0.
C. Có ít nhất một số thực lớn hơn 0.
D. Mọi số thực đều lớn hơn hoặc bằng 0.
17. Điều kiện cần và đủ để một đồ thị có đường đi Hamilton là gì?
A. Đồ thị phải liên thông.
B. Đồ thị phải có chu trình Euler.
C. Không có điều kiện cần và đủ đã biết.
D. Đồ thị phải có ít nhất một đỉnh bậc chẵn.
18. 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?
19. Cho $A = \{1, 2, 3\}$. Tìm số quan hệ tương đương trên $A$.
20. Trong một giải đấu có 8 đội bóng, mỗi đội phải đấu với mỗi đội còn lại đúng một trận. Hỏi có bao nhiêu trận đấu diễn ra?
21. Tìm số nghiệm nguyên dương của phương trình $x_1 + x_2 + x_3 = 10$.
22. Cho $A = \{1, 2, 3, 4, 5\}$. Có bao nhiêu cách chọn ra 3 số từ $A$ sao cho không có hai số nào liên tiếp nhau?
23. Cho hai tập hợp $A = \{1, 2, 3\}$ và $B = \{a, b\}$. Hỏi có bao nhiêu hàm từ $A$ vào $B$?
24. Tìm số nguyên dương $n$ nhỏ nhất sao cho $n!$ chia hết cho 2024.
A. 10
B. 11
C. 12
D. 2024
25. Cho $p$ và $q$ là các mệnh đề. Mệnh đề nào sau đây tương đương với $\neg (p \vee q)$?
A. $\neg p \vee \neg q$
B. $\neg p \wedge \neg q$
C. $p \wedge q$
D. $p \vee q$
26. 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!
27. Trong đại số Boole, biểu thức $A + A`$ bằng bao nhiêu?
28. Cho hàm $f: A \rightarrow B$. Hàm $f$ được gọi là đơn ánh khi nào?
A. Với mọi $x_1, x_2 \in A$, nếu $f(x_1) = f(x_2)$ thì $x_1 = x_2$.
B. Với mọi $y \in B$, tồn tại $x \in A$ sao cho $f(x) = y$.
C. Với mọi $x_1, x_2 \in A$, nếu $x_1 = x_2$ thì $f(x_1) = f(x_2)$.
D. Với mọi $x \in A$, tồn tại $y \in B$ sao cho $f(x) = y$.
29. Cho quan hệ $R = \{(1, 1), (2, 2), (3, 3), (1, 2)\}$ trên tập $A = \{1, 2, 3\}$. Quan hệ $R$ có tính chất nào sau đây?
A. Phản xạ
B. Đối xứng
C. Bắc cầu
D. Phản xạ và đối xứng
30. Cho tập hợp $A = \{a, b, c, d\}$. Tìm số quan hệ trên $A$.
