← COMP5511 全部讲次
Q03

Midterm 自拟练习|C 逻辑

自拟练习 C 逻辑:英文题干,逐题折叠中文解析、英文参考答案与回查页码。

手机上宽表格可左右滑动;自测答案默认收起,点击题目下方按钮查看。

使用边界:2026-11-04 课堂期中复习,非官方材料;考试安排按讲师通知整理,正式要求以讲师通知和课堂公告为准。主体覆盖 L01–L07、Tutorial 1–5 与 Assignment 1;通知列出的课件只到 Lecture 7,L08 放在第 08 节作范围存疑附节。练习题均为自拟,不是往年真题或预测卷。

复习资料:范围与搜索 · 概率与逻辑 · 机器学习与聚类 · 神经网络与 L08 附节

先做题再看解析:A 搜索 · B 概率 · C 逻辑 · D 机器学习 · E 聚类与神经网络 · F 论文与 PyTorch

怎么做:先只看题面,用英文作答,写出公式和每一步,再展开解析核对。解析里的数值都用 python 复算过;每题末尾给回查出处,页码为 PDF 页序。

C 逻辑

C1 · Satisfiable, unsatisfiable or valid

Use truth tables to classify each sentence as valid, satisfiable but not valid, or unsatisfiable. Give the number of models.

(a) (P ⇒ Q) ∨ (Q ⇒ P) (b) (P ∨ Q) ∧ ¬P ∧ ¬Q (c) (P ⇒ Q) ∧ (Q ⇒ ¬P)

C1 · 查看答案与解析

推理过程:两个符号共 4 个解释,逐行计算。

P Q (a) (b) (c)
真 真 真 假 假
真 假 真 假 假
假 真 真 假 真
假 假 真 假 真

答案:(a) valid,4 个模型;(b) unsatisfiable,0 个模型;(c) satisfiable 但不 valid,2 个模型,恰好是 P 为假的两行。

English: A sentence is valid if it is true in every interpretation, satisfiable if it has at least one model, and unsatisfiable if it has no model.

易错点:(c) 在 P 为假时两个蕴含都是空真;P 为真时 Q 必须同时为真和为假,不可能。

回查:L03b p.13–14、p.17。

C2 · Conversion to CNF

Convert each sentence into conjunctive normal form and list the clauses.

(a) ¬(P ⇒ Q) ∨ R (b) (P ∨ Q) ⇒ (R ∧ S)

C2 · 查看答案与解析

推理过程:

(a) 消 ⇒:¬(¬P ∨ Q) ∨ R;de Morgan:(P ∧ ¬Q) ∨ R;分配:(P ∨ R) ∧ (¬Q ∨ R)。

(b) 消 ⇒:¬(P ∨ Q) ∨ (R ∧ S);de Morgan:(¬P ∧ ¬Q) ∨ (R ∧ S);分配得四个子句:(¬P ∨ R) ∧ (¬P ∨ S) ∧ (¬Q ∨ R) ∧ (¬Q ∨ S)。

答案:(a) 两个子句 P ∨ R、¬Q ∨ R;(b) 四个子句 ¬P ∨ R、¬P ∨ S、¬Q ∨ R、¬Q ∨ S。两题都用真值表逐行核对过,与原式等价。

English: To convert to CNF, eliminate ⇔ and ⇒, move ¬ inwards with de Morgan’s laws, and distribute ∨ over ∧.

易错点:(a) 的 ¬ 要先推到文字上再分配;(b) 的前件是 ∨,拆开后每个子句都只有一个正文字,是 Horn 子句。

回查:L03b p.18、p.36–38;T05 p.6–7、p.9。

C3 · Forward chaining

Knowledge base: R1 A ∧ B ⇒ C; R2 C ⇒ D; R3 D ∧ E ⇒ F; R4 B ⇒ E; R5 F ∧ G ⇒ H. Facts: A, B.

Use forward chaining to decide whether F can be derived. In each round, scan the rules in order and add a conclusion immediately when all premises are known. List the known facts after each round and name any rule that is never used.

C3 · 查看答案与解析

推理过程:

轮次 触发的规则 已知事实
开始 — A, B
第 1 轮 R1 得 C,R2 得 D,R3 前件 E 未知,R4 得 E A, B, C, D, E
第 2 轮 R3 得 F A, B, C, D, E, F
第 3 轮 没有新事实,R5 缺 G 不变

答案:F 可以推出。R5 从头到尾没有触发,因为 G 不在已知里。

English: Forward chaining is data-driven: it starts from the known facts and fires every rule whose premises are all satisfied until no new fact can be added.

易错点:第 1 轮扫到 R3 时 E 还没加入,要等下一轮。扫描规则的约定不同,轮次可能不同,但最终能推出的事实相同。

回查:L03b p.22–28。

C4 · Backward chaining

Use the knowledge base and facts of C3. Prove F by backward chaining. Show the goal stack at each step.

C4 · 查看答案与解析

推理过程:

步骤 当前目标 做法
1 F 结论为 F 的规则是 R3,换成子目标 D、E
2 D R2:换成 C
3 C R1:换成 A、B,两者都是已知事实
4 E R4:换成 B,已知

答案:所有子目标都落到已知事实,F 得证。R5 没有被考虑,因为它的结论不是任何子目标。

English: Backward chaining is goal-driven: it starts from the query and replaces each goal by the premises of a rule that concludes it, until every subgoal is a known fact.

易错点:已访问过的目标不要再展开,否则在有环规则上会绕圈。

回查:L03b p.29–34;T05 p.10。

C5 · Resolution refutation

Knowledge base: P ∨ Q, P ⇒ R, Q ⇒ R. Prove R by resolution refutation.

(a) Write the clause set you start with. (b) Show each resolution step until the empty clause. (c) Why can forward chaining not be used directly on this knowledge base?

C5 · 查看答案与解析

推理过程:

(a) 子句集:P ∨ Q,¬P ∨ R,¬Q ∨ R,再加入目标的否定 ¬R。

(b) 归结:

步 参与的两个子句 结果
1 ¬P ∨ R 与 ¬R ¬P
2 ¬Q ∨ R 与 ¬R ¬Q
3 P ∨ Q 与 ¬P Q
4 Q 与 ¬Q 空子句

(c) P ∨ Q 有两个正文字,不是 Horn 子句;链接法每步只能加入一个确定的结论,用不上这条信息。

答案:推出空子句,所以 KB 蕴含 R。

English: Resolution adds the negated query to the clause set and derives the empty clause; unlike chaining, it does not require Horn clauses.

易错点:每步只消一对互补文字;不要忘记先把 ¬R 加进去。

回查:L03b p.21、p.35–43;T05 p.12。

C6 · A biconditional into CNF

Convert P ⇔ (Q ⇒ R) into conjunctive normal form and list the clauses. Check one row of the truth table.

C6 · 查看答案与解析

推理过程:

  • 拆 ⇔:(P ⇒ (Q ⇒ R)) ∧ ((Q ⇒ R) ⇒ P)
  • 前半:¬P ∨ ¬Q ∨ R
  • 后半:¬(¬Q ∨ R) ∨ P ≡ (Q ∧ ¬R) ∨ P ≡ (P ∨ Q) ∧ (P ∨ ¬R)

答案:三个子句 ¬P ∨ ¬Q ∨ R,P ∨ Q,P ∨ ¬R。抽查 P = F、Q = T、R = F:Q ⇒ R 为假,原式 F ⇔ F 为真;三个子句依次为 T、T、T,一致。八行全部核对过。

English: Replace the biconditional by two implications, eliminate the implications, push the negation inwards with de Morgan’s law, and distribute ∨ over ∧.

易错点:后半句的否定作用在整个 (¬Q ∨ R) 上,用德摩根律得 Q ∧ ¬R,不要只否定第一个文字。

回查:L03b p.18、p.36–38;T05 p.6–7。

C7 · Disjunctive normal form

A sentence is in disjunctive normal form (DNF) if it is a disjunction of conjunctions of literals.

(a) Convert (P ⇒ Q) ∧ (Q ⇒ R) into DNF. (b) Simplify your answer to two conjunctions and check it with a truth table. How many models does the sentence have?

C7 · 查看答案与解析

推理过程:

  • 消 ⇒:(¬P ∨ Q) ∧ (¬Q ∨ R)
  • ∧ 对 ∨ 分配:(¬P ∧ ¬Q) ∨ (¬P ∧ R) ∨ (Q ∧ ¬Q) ∨ (Q ∧ R)
  • Q ∧ ¬Q 恒假,删去
  • ¬P ∧ R 为真时,Q 为假则 ¬P ∧ ¬Q 为真,Q 为真则 Q ∧ R 为真,所以这一项多余

答案:(a) (¬P ∧ ¬Q) ∨ (¬P ∧ R) ∨ (Q ∧ R)。(b) (¬P ∧ ¬Q) ∨ (Q ∧ R),与原式八行真值一致;共 4 个模型,(P, Q, R) = (F, F, F)、(F, F, T)、(F, T, T)、(T, T, T)。

English: Eliminate the implications, then distribute ∧ over ∨ so that the sentence becomes a disjunction of conjunctions. Contradictory terms such as Q ∧ ¬Q are dropped. A DNF is not unique, so the answer is checked with a truth table.

易错点:化 CNF 用 ∨ 对 ∧ 分配,化 DNF 方向相反;(a) 和 (b) 两种写法都是 DNF。

回查:L03b p.14、p.18、p.36–38;T05 p.4–5。

下一页 →
Q04 Midterm 自拟练习|D 机器学习

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。