Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán DFS(I) là:

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.

Luật tam đoạn luận (hay còn gọi là quy tắc bắc cầu) có dạng: Nếu P suy ra Q và Q suy ra R, thì P suy ra R. Trong câu hỏi, P là "An học giỏi", Q là "An tốt nghiệp loại A", và R là "An sẽ có nhiều cơ hội tìm việc làm khi ra trường". Do đó, suy luận trên tuân theo luật tam đoạn luận.

Với X = Y = Z = 1, ta có:

- Biểu thức (¬X → Y) ∨ (¬Y → Z) trở thành (¬1 → 1) ∨ (¬1 → 1). Vì ¬1 = 0, biểu thức trở thành (0 → 1) ∨ (0 → 1). Do 0 → 1 = 1, biểu thức trở thành 1 ∨ 1 = 1.

- Biểu thức (¬X → Z) trở thành (¬1 → 1). Vì ¬1 = 0, biểu thức trở thành (0 → 1) = 1.

Vậy, chân trị của hai biểu thức lần lượt là 1 và 1.