Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán DFS(C) là:
Đáp án đúng: B
Câu hỏi liên quan
Công thức có dạng chuẩn tắc hội (CNF - Conjunctive Normal Form) là một công thức logic mệnh đề được biểu diễn dưới dạng hội của các mệnh đề tuyển. Mỗi mệnh đề tuyển là một tuyển của các literal (biến hoặc phủ định của biến). Biểu thức hội cơ bản còn được gọi là mệnh đề tuyển (clause). Như vậy, một công thức được gọi là có dạng chuẩn tắc hội nếu nó là hội của các biểu thức tuyển cơ bản.
Ta có P → Q sai khi và chỉ khi P đúng và Q sai.
Khi đó, P Λ Q sai (vì Q sai) và Q → P đúng (vì Q sai).
Vậy, chân trị của P Λ Q là 0 và của Q → P là 1.
* Đáp án A: Quy bài toán ban đầu về bài toán con đơn giản hơn là phương pháp chia để trị hoặc quy nạp.
* Đáp án B: Giả sử điều cần chứng minh là sai để từ đó suy ra mâu thuẫn là định nghĩa chính xác của phương pháp phản chứng.
* Đáp án C: Liệt kê tất cả các khả năng để từ đó đưa ra quyết định là phương pháp vét cạn hoặc duyệt.
* Đáp án D: Biểu diễn nghiệm của bài toán bằng các dữ kiện ban đầu là một cách giải bài toán, nhưng không phải là phương pháp phản chứng.
Phương án A: (P∧(P→Q)) → Q là quy tắc Modus Ponens (khẳng định). Nếu P đúng và P suy ra Q đúng, thì Q đúng.
Phương án B: ((P→Q) ∨ (Q→R)) → (P→R) không phải là quy tắc tam đoạn luận. Vế trái sử dụng phép "hoặc", và kết luận không chắc chắn.
Phương án C: ((P→Q) ∨ (Q→R)) → (Q→R) cũng không phải là quy tắc tam đoạn luận. Tương tự như phương án B, vế trái sử dụng phép "hoặc" và kết luận không hợp lý.
Phương án D: ((P→Q) ∧ (Q→R)) → (P→R) chính là quy tắc tam đoạn luận. Nếu "P suy ra Q" và "Q suy ra R" đồng thời đúng (phép "và"), thì có thể suy ra "P suy ra R".
Vậy đáp án đúng là D.
Câu hỏi này kiểm tra kiến thức về các quy tắc suy luận cơ bản trong logic toán học. Ta có thể biểu diễn suy luận đã cho như sau:
- P: Là sinh viên CNTT của trường ĐHCN Việt Hung
- Q: Học Toán rời rạc
- Suy luận: P -> Q. ¬Q suy ra ¬P.
Đây chính là dạng của luật Modus Tollens, hay còn gọi là luật phủ định. Luật này phát biểu rằng nếu P kéo theo Q là đúng, và Q sai, thì P cũng phải sai.
- Luật khẳng định (Modus Ponens) có dạng: P -> Q, P suy ra Q.
- Luật tam đoạn luận có dạng: P -> Q, Q -> R suy ra P -> R.
- Luật tam đoạn luận rời không liên quan trực tiếp đến suy luận này.
Vì vậy, đáp án đúng là B. Luật phủ định.
