Đồ thị G vô hướng nào trong các đồ thị sau là tồn tại nếu các đỉnh có số bậc lần lượt là:

Cho đồ thị như hình vẽ. Hãy cho biết kết quả thực hiện thuật toán BFS(1):

Lời giải:

Đáp án đúng: A

Thuật toán BFS (Breadth-First Search) duyệt đồ thị theo chiều rộng. Bắt đầu từ đỉnh 1:

1. Đỉnh 1: Thăm đỉnh 1.
2. Các đỉnh kề với 1: Các đỉnh kề với 1 là 2, 4, 7. Thăm các đỉnh này theo thứ tự.
3. Đỉnh 2: Thăm đỉnh 2.
4. Đỉnh 4: Thăm đỉnh 4.
5. Đỉnh 7: Thăm đỉnh 7.
6. Các đỉnh kề với 2: Đỉnh kề với 2 là 3, 6. Thăm các đỉnh này theo thứ tự.
7. Đỉnh 3: Thăm đỉnh 3.
8. Đỉnh 6: Thăm đỉnh 6.
9. Các đỉnh kề với 4: Đỉnh kề với 4 là 8, 5. Thăm các đỉnh này theo thứ tự.
10. Đỉnh 8: Thăm đỉnh 8.
11. Đỉnh 5: Thăm đỉnh 5.
12. Các đỉnh kề với 7: Đỉnh kề với 7 là 9, 10. Thăm các đỉnh này theo thứ tự.
13. Đỉnh 9: Thăm đỉnh 9.
14. Đỉnh 10: Thăm đỉnh 10.

Vậy, thứ tự duyệt BFS là: 1, 2, 4, 7, 3, 6, 8, 5, 9, 10.

Câu 28:

Mệnh đề \(P \vee (P \wedge Q)\) tương đương logic với mệnh đề nào sau đây?

Lời giải:

Đáp án đúng: D

Ta có thể dùng luật hấp thụ để đơn giản biểu thức \(P \vee (P \wedge Q)\). Theo luật hấp thụ, \(P \vee (P \wedge Q) \equiv P\). Do đó, mệnh đề \(P \vee (P \wedge Q)\) tương đương logic với mệnh đề P.

Câu 29:

Hãy cho biết quy tắc (Luật) nào là cơ sở của mô hình suy diễn sau:

\(\frac{\begin{array}{l} A \to B\\ \overline B \end{array}}{{\therefore \overline A }}\)

Lời giải:

Đáp án đúng: B

Luật suy diễn được đưa ra có dạng: nếu A kéo theo B và B sai, thì A sai. Đây chính là luật phủ định (Modus Tollens). Các luật khác không phù hợp với cấu trúc này.

Câu 30:

Hãy cho biết quy tắc (Luật) nào là cơ sở của mô hình suy diễn sau:

\(\frac{\begin{array}{l} A \to B\\ B \to C \end{array}}{{\therefore A \to C}}\)

Lời giải:

Đáp án đúng: D

Luật được sử dụng trong mô hình suy diễn đã cho là luật tam đoạn luận (tiếng Anh: Hypothetical Syllogism). Luật này phát biểu rằng nếu A kéo theo B và B kéo theo C, thì A kéo theo C. Đây là một quy tắc suy luận cơ bản trong logic mệnh đề. Trong các đáp án, chỉ có "Luật tam đoạn luận" mô tả chính xác quy tắc này.

Câu 1:

Cho tập A = {1,2,a}. Hỏi tập nào là tập lũy thừa của tập A?

Lời giải:

Đáp án đúng: C

Tập lũy thừa của một tập hợp A, ký hiệu P(A), là tập hợp chứa tất cả các tập con của A, kể cả tập rỗng và chính tập A.

Trong trường hợp này, A = {1, 2, a}. Vậy các tập con của A là:

* Tập rỗng: ∅
* Các tập con có 1 phần tử: {1}, {2}, {a}
* Các tập con có 2 phần tử: {1, 2}, {1, a}, {2, a}
* Tập con có 3 phần tử: {1, 2, a}

Do đó, tập lũy thừa của A là: P(A) = {∅, {1}, {2}, {a}, {1, 2}, {1, a}, {2, a}, {1, 2, a}}.

Vậy đáp án đúng là phương án 3.

Câu 2:

Cho quy tắc f: ℝ → ℝ thỏa mãn \(f(x) = 2x^2 + 5\). Khi đó f là:

Lời giải: