1. Cho một đồ thị phẳng liên thông có 6 đỉnh và 12 cạnh. Hỏi đồ thị này chia mặt phẳng thành bao nhiêu miền?
2. Cho $p$ và $q$ là hai mệnh đề. Biểu thức logic nào sau đây tương đương với $p \rightarrow q$?
A. $q \rightarrow p$
B. $\neg p \lor q$
C. $p \land q$
D. $\neg q \rightarrow \neg p$
3. Trong lý thuyết đồ thị, bậc của một đỉnh là gì?
A. Số lượng cạnh trong đồ thị.
B. Số lượng đỉnh trong đồ thị.
C. Số lượng cạnh liên thuộc với đỉnh đó.
D. Số lượng đường đi ngắn nhất từ đỉnh đó đến tất cả các đỉnh khác.
4. Cho $f(x) = x + 1$ và $g(x) = x^2$. Tính $(g \circ f)(x)$.
A. $x^2 + 1$
B. $x^2 + 2x + 1$
C. $x^2 + 1 + x$
D. $x^2 + 2x + 2$
5. Số các hoán vị của $n$ đối tượng trong đó $k$ đối tượng được cố định là bao nhiêu?
A. $n!$
B. $(n-k)!$
C. $k!$
D. $n! / k!$
6. Cho $p$ và $q$ là hai mệnh đề. Khi nào thì mệnh đề $p \leftrightarrow q$ là đúng?
A. Khi $p$ và $q$ đều đúng.
B. Khi $p$ và $q$ đều sai.
C. Khi $p$ và $q$ có cùng giá trị chân lý.
D. Khi $p$ và $q$ có giá trị chân lý khác nhau.
7. Định nghĩa nào sau đây là đúng về đồ thị hai phía?
A. Một đồ thị mà các đỉnh có thể được chia thành hai tập sao cho không có cạnh nào nối hai đỉnh trong cùng một tập.
B. Một đồ thị mà tất cả các đỉnh đều có bậc bằng 2.
C. Một đồ thị mà có thể vẽ trên mặt phẳng mà không có cạnh nào giao nhau.
D. Một đồ thị mà có một chu trình đi qua tất cả các đỉnh.
8. Cho quan hệ $R = \{(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)\}$ trên tập $A = \{1, 2, 3\}$. 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. Chỉ phản xạ
9. Cho một đại số Boole. Mệnh đề nào sau đây không đúng?
A. $x + x` = 1$
B. $x * x` = 0$
C. $x + 1 = 1$
D. $x + 0 = 1$
10. Cho một đồ thị có hướng. Điều kiện nào sau đây là cần và đủ để đồ thị có một đường đi Hamilton?
A. Đồ thị phải liên thông.
B. Đồ thị phải có một chu trình Euler.
C. Không có điều kiện cần và đủ đã biết.
D. Mỗi đỉnh phải có bậc ít nhất là $n/2$.
11. Cho $A = \{1, 2\}$ và $B = \{a, b, c\}$. Hỏi có bao nhiêu hàm từ $A$ vào $B$?
12. Cho $A = \{1, 2, 3\}$ và $B = \{a, b\}$. Hỏi có bao nhiêu hàm toàn ánh từ $A$ vào $B$?
13. Trong một đại số Boole, biểu thức $x + x`y$ tương đương với biểu thức nào sau đây?
A. $x`$
B. $x + y$
C. $x` + y$
D. $xy$
14. Cho tậ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?
15. Cho hàm $f: A \rightarrow B$ và $g: B \rightarrow C$. Hàm hợp $g \circ f$ là một đơn ánh khi nào?
A. Khi $f$ và $g$ đều là đơn ánh.
B. Khi $f$ là toàn ánh và $g$ là đơn ánh.
C. Khi $f$ là đơn ánh và $g$ là toàn ánh.
D. Khi $f$ và $g$ đều là toàn ánh.
16. Cho $A$ là một tập hợp có $n$ phần tử. Số lượng tập con của $A$ là bao nhiêu?
A. $n!$
B. $2^n$
C. $n^2$
D. $n$
17. Cho đồ thị vô hướng $G = (V, E)$ với $|V| = n$ đỉnh và $|E| = m$ cạnh. Điều kiện nào sau đây là cần và đủ để $G$ là một cây?
A. $G$ liên thông và $m = n$
B. $G$ không có chu trình và $m = n - 1$
C. $G$ liên thông và $m = n + 1$
D. $G$ liên thông và $m = n - 1$
18. Định nghĩa nào sau đây là đúng về đồ thị Euler?
A. Đồ thị có một chu trình đi qua tất cả các cạnh, mỗi cạnh đúng một lần.
B. Đồ thị có một đường đi qua tất cả các đỉnh, mỗi đỉnh đúng một lần.
C. Đồ thị có một chu trình đi qua tất cả các đỉnh, mỗi đỉnh đúng một lần.
D. Đồ thị có một đường đi qua tất cả các cạnh, mỗi cạnh đúng một lần.
19. Số các số nguyên dương không vượt quá 100 chia hết cho 2 hoặc 3 là:
20. Mệnh đề nào sau đây là đúng về quan hệ tương đương?
A. Quan hệ tương đương là quan hệ phản xạ, đối xứng và bắc cầu.
B. Quan hệ tương đương là quan hệ phản xạ và đối xứng.
C. Quan hệ tương đương là quan hệ đối xứng và bắc cầu.
D. Quan hệ tương đương là quan hệ phản xạ và bắc cầu.
21. Mệnh đề nào sau đây là luật De Morgan?
A. $\neg (p \land q) \equiv \neg p \land \neg q$
B. $\neg (p \lor q) \equiv \neg p \lor \neg q$
C. $\neg (p \land q) \equiv \neg p \lor \neg q$
D. $\neg (p \lor q) \equiv p \land q$
22. Cho tập $A = \{1, 2, 3, 4\}$. Hỏi có bao nhiêu quan hệ thứ tự toàn phần có thể được định nghĩa trên $A$?
23. Cho $R$ là một quan hệ trên tập $A$. Bao đóng bắc cầu của $R$ là gì?
A. Quan hệ nhỏ nhất chứa $R$ và có tính phản xạ.
B. Quan hệ nhỏ nhất chứa $R$ và có tính đối xứng.
C. Quan hệ nhỏ nhất chứa $R$ và có tính bắc cầu.
D. Quan hệ lớn nhất chứa $R$ và có tính bắc cầu.
24. 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(n-1)/2$
25. Cho hàm $f(x) = x^2 + 1$. Hàm $f$ có phải là song ánh từ tập số thực $\mathbb{R}$ vào $\mathbb{R}$ không?
A. Có
B. Không, vì $f$ không phải là đơn ánh.
C. Không, vì $f$ không phải là toàn ánh.
D. Không, vì $f$ không phải là đơn ánh và toàn ánh.
26. Cho một nhóm $(G, *)$ và $a, b \in G$. Khẳng định nào sau đây là đúng?
A. $(a * b)^{-1} = a^{-1} * b^{-1}$
B. $(a * b)^{-1} = b^{-1} * a^{-1}$
C. $(a * b)^{-1} = a * b$
D. $(a * b)^{-1} = b * a$
27. Cho $G$ là một đồ thị vô hướng liên thông. Phát biểu nào sau đây là đúng?
A. Luôn tồn tại một chu trình Euler.
B. Luôn tồn tại một đường đi Hamilton.
C. Luôn tồn tại một cây bao trùm.
D. Luôn tồn tại một đồ thị đầy đủ.
28. Cho $P(x)$ là mệnh đề `$x > 0$`. Miền xác định của $x$ là tập hợp các số thực. Mệnh đề $\exists x P(x)$ có nghĩa là gì?
A. Mọi số thực đều lớn hơn 0.
B. Không có số thực nào lớn hơn 0.
C. Có ít nhất một số thực lớn hơn 0.
D. Tất cả các số thực đều nhỏ hơn hoặc bằng 0.
29. Cho $A$ và $B$ là hai tập hợp. Mệnh đề nào sau đây là sai?
A. $A \cap B \subseteq A$
B. $A \subseteq A \cup B$
C. Nếu $A \subseteq B$ thì $A \cup B = B$
D. Nếu $A \subseteq B$ thì $A \cap B = B$
30. Trong một nhóm hữu hạn, cấp của một phần tử luôn là ước của cấp của nhóm. Đây là định lý nào?
A. Định lý Fermat nhỏ
B. Định lý Euler
C. Định lý Lagrange
D. Định lý Cauchy
