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

Quy tắc tam đoạn luận là một quy tắc suy luận cơ bản trong logic mệnh đề. Nó có dạng: Nếu P kéo theo Q và Q kéo theo R, thì P kéo theo R. Điều này có nghĩa là, nếu hai mệnh đề điều kiện (P → Q) và (Q → R) đều đúng, thì mệnh đề điều kiện (P → R) cũng đúng.

Xét các phương án:

• Phương án 1: \((P \wedge (P \to Q)) \to Q\): Đây là quy tắc Modus Ponens, không phải tam đoạn luận.


• Phương án 2: \(((P→Q)\vee(Q→R)) →(P→R)
  \): Đây không phải là quy tắc tam đoạn luận vì nó sử dụng phép tuyển (∨) thay vì phép hội (∧).


• Phương án 3: \(((P→Q)\vee(Q→R)) →(Q→R)\): Đây cũng không phải là quy tắc tam đoạn luận vì nó sử dụng phép tuyển (∨) thay vì phép hội (∧) và kết luận không đúng với tam đoạn luận.


• Phương án 4: \(((P→Q) \wedge (Q→R)) →(P→R)\): Đây chính là quy tắc tam đoạn luận. Nếu P kéo theo Q và Q kéo theo R, thì P kéo theo R.

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

Đề bài cho một suy luận và hỏi quy tắc suy luận nào là cơ sở cho suy diễn đó. Chúng ta có thể biểu diễn suy luận này bằng các mệnh đề logic như sau:

• P: Hôm nay trời mưa
• Q: Cô ta đến

Khi đó, các giả thiết của suy luận có thể viết lại là:

• Nếu P thì không Q: P → ¬Q
• Nếu không Q thì ngày mai cô ta đến: ¬Q → R (R: ngày mai cô ta đến)

Kết luận của suy luận là:

• Nếu hôm nay trời mưa thì ngày mai cô ta đến: P → R

Như vậy, ta thấy cấu trúc của suy luận là: P → ¬Q, ¬Q → R, do đó P → R. Đây chính là quy tắc tam đoạn luận (hay còn gọi là bắc cầu). Vì vậy, đáp án đúng là "Tam đoạn luận (Bắc cầu)".

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

• X → Y = 0 → 0 = 1 (vì mệnh đề kéo theo chỉ sai khi điều kiện đúng mà kết luận sai)
• Y → Z = 0 → 0 = 1
• (X → Y) ∨ (Y → Z) = 1 ∨ 1 = 1
• X → Z = 0 → 0 = 1

Vậy, chân trị của (X → Y) ∨ (Y → Z) là 1 và chân trị của (X → Z) là 1.