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

Thuật toán DFS (Depth-First Search - Tìm kiếm theo chiều sâu) bắt đầu từ đỉnh 1, sau đó duyệt theo chiều sâu đến các đỉnh kề chưa được thăm. Thứ tự duyệt như sau:

• Bắt đầu từ đỉnh 1.


• Đỉnh 1 có các đỉnh kề 2 và 7. Ta chọn duyệt đỉnh 2 trước (vì nó nhỏ hơn).


• Từ đỉnh 2, các đỉnh kề chưa thăm là 3.


• Từ đỉnh 3, các đỉnh kề chưa thăm là 6.


• Từ đỉnh 6, các đỉnh kề chưa thăm là 9.


• Từ đỉnh 9, các đỉnh kề chưa thăm là 8.


• Quay lại đỉnh 1, đỉnh kề chưa thăm là 7.


• Từ đỉnh 7, các đỉnh kề chưa thăm là 4.


• Từ đỉnh 4, các đỉnh kề chưa thăm là 5.


• Từ đỉnh 5, đỉnh kề chưa thăm là 10.

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

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)".