Đường đi Hamilton là đường đi đi qua tất cả các đỉnh của đồ thị mỗi đỉnh.

Câu hỏi yêu cầu tìm định nghĩa đúng về cây khung của một đồ thị vô hướng liên thông. Cây khung của đồ thị G là một cây bao gồm tất cả các đỉnh của G và một số cạnh của G sao cho không tạo thành chu trình.

Phân tích các đáp án:

• A. T liên thông và mỗi cạnh của nó đều là cầu: Điều này đúng với một cây, nhưng chưa đủ để định nghĩa một cây khung của đồ thị G, vì nó không đề cập đến việc T phải chứa tất cả các đỉnh của G.


• B. Nếu thêm vào T một cạnh thì ta có ít nhất một chu trình: Điều này đúng với một cây, nhưng lại không liên quan trực tiếp đến định nghĩa cây khung của đồ thị G.


• C. V_T = V, E_T × E: V_T = V có nghĩa là tập đỉnh của T bằng tập đỉnh của G, E_T × E có nghĩa là E_T là tích Descartes của E, điều này không đúng. Các cạnh của cây khung phải là các cạnh của đồ thị gốc (E_T ⊆ E).


• D. T liên thông, có đúng n cạnh và E_T × E: Điều này gần đúng, nhưng sai ở chỗ E_T × E (tích Descartes) không có nghĩa, phải là E_T ⊆ E (E_T là tập con của E). Ngoài ra, một cây khung của đồ thị n đỉnh phải có n-1 cạnh, không phải n cạnh.

Tuy nhiên, không có đáp án nào hoàn toàn chính xác. Đáp án gần đúng nhất là C với lỗi sai về ký hiệu của tập cạnh. Đáp án D gần đúng, nhưng sai ở số cạnh và ký hiệu tập cạnh. Do đó, câu hỏi có thể có lỗi hoặc thiếu thông tin.

Nếu phải chọn một đáp án gần đúng nhất, ta chọn C với giả định rằng ký hiệu "×" có thể là một lỗi in ấn và nên được hiểu là "⊆" (tập con). Đáp án này đảm bảo rằng cây khung chứa tất cả các đỉnh của đồ thị gốc và các cạnh của nó là một phần của các cạnh trong đồ thị gốc.

Ta có P = Q = 1, R = 0.

- Tính (P → Q) ∧ (Q → R):

P → Q = 1 → 1 = 1

Q → R = 1 → 0 = 0

(P → Q) ∧ (Q → R) = 1 ∧ 0 = 0

- Tính (P → R):

P → R = 1 → 0 = 0

Vậy, chân trị của (P → Q) ∧ (Q → R) là 0 và của (P → R) là 0.

Ta có thể sử dụng bảng chân trị để chứng minh hoặc sử dụng các luật logic để đơn giản hóa mệnh đề:

P ∨ (P ∧ Q) ≡ P (Vì P ∨ (P ∧ Q) tương đương với P)

Vậy, mệnh đề P ∨ (P ∧ Q) tương đương logic với mệnh đề P.

Câu hỏi này kiểm tra kiến thức về các quy tắc suy luận trong logic mệnh đề.

Phân tích:

• Giả thiết 1: Nếu An học giỏi (p) thì An được khen thưởng (r). (p -> r)
• Giả thiết 2: Nếu An nhiệt tình tham gia các hoạt động Đoàn (q) thì An được khen thưởng (r). (q -> r)
• Kết luận: Nếu An học giỏi (p) hoặc tham gia nhiệt tình các hoạt động Đoàn (q) thì An được khen thưởng (r). (p v q -> r)

Quy tắc suy luận phù hợp ở đây là "Luật từng trường hợp". Luật này nói rằng nếu một kết quả xảy ra trong mọi trường hợp có thể xảy ra của một điều kiện, thì kết quả đó xảy ra khi điều kiện đó xảy ra.

Các lựa chọn khác không phù hợp vì:

• Luật khẳng định (Modus Ponens): p -> q, p suy ra q.
• Luật phủ định (Modus Tollens): p -> q, not q suy ra not p.
• Luật tam đoạn luận (Hypothetical Syllogism): p -> q, q -> r suy ra p -> r.