2012–2013 学年期末真题

#真题

来源为 12-13.doc。原文件含题目与作答；我忠实保留其结论。原作答没有写全或把普通合取范式当作主合取范式时，另列“补充校正”，不静默改写源答案。

一、简答题（20 分）

1. 联结词完全集

给出一组逻辑联结词完备集。

查看第 1 小题源答案

源答案列出：

{∧,∨,¬},{∧,¬},{∨,¬},{¬,→}.\{\land,\lor,\neg\},\quad \{\land,\neg\},\quad \{\lor,\neg\},\quad \{\neg,\to\}.

2. 两个论域中的真值

在自然数论域中 Q(x)Q(x) 表示“xx 是自然数”，在整数论域中表示“xx 是整数”。分别判断：

  1. ∀x(Q(x)→0≤x)\forall x(Q(x)\to0\le x)；
  2. ∃x(Q(x)∧∀y(Q(y)→x≤y))\exists x(Q(x)\land\forall y(Q(y)\to x\le y))；
  3. ∀x∀y(Q(x)∧Q(y)→x+y=y+x)\forall x\forall y(Q(x)\land Q(y)\to x+y=y+x)；
  4. ∀x∀y(Q(x)∧Q(y)→x+y≤y)\forall x\forall y(Q(x)\land Q(y)\to x+y\le y)。
查看第 2 小题源答案

按“自然数论域、整数论域”的顺序，源答案为：

  1. 真、假；
  2. 真、假；
  3. 真、真；
  4. 假、假。

3. 数列极限的谓词表达

把“对任意 ε>0\varepsilon>0，存在 N>0N>0，对任意 nn，当 n>Nn>N 时有 ∣xn−b∣<ε|x_n-b|<\varepsilon”写成谓词公式。

查看第 3 小题源答案 ∀ε(ε>0→∃N(N>0∧∀n(n>N→∣xn−b∣<ε))).\forall\varepsilon\left( \varepsilon>0\to \exists N\left( N>0\land \forall n(n>N\to|x_n-b|<\varepsilon) \right) \right).

4. 可靠性与完备性

给出可靠性和完备性定理。

查看第 4 小题源答案

可靠性：若 Γ⊢Q\Gamma\vdash Q，则 Γ⊨Q\Gamma\models Q。

完备性：若 Γ⊨Q\Gamma\models Q，则 Γ⊢Q\Gamma\vdash Q。

5. 自然数理论的完备性

在自然数理论中，仅保持等谓词、后继函数和数学归纳法，是否完备？

查看第 5 小题源答案与边界说明

源文件答案为“是”，我按原作答保留。该问法中的“仅保持”所指形式系统在源文件里没有进一步定义，因此不把它扩写成一般的一阶 Peano 算术完备性结论。

二、论述题（20 分）

1. 命题逻辑合式公式

给出命题逻辑合式公式的递归定义。

查看第 1 小题源答案

源答案：常值 0、1 与原子公式是公式；若 Q,RQ,R 是公式，则 ¬Q\neg Q 以及由二元联结词连接 Q,RQ,R 得到的式子是公式；只有有限次应用这些规则得到的符号串才是公式。

2. 谓词逻辑合式公式

给出谓词逻辑合式公式的递归定义。

查看第 2 小题源答案

谓词作用于相应个数的项得到原子公式；公式经否定、二元联结词连接仍是公式；若 QQ 是公式，则 ∀xQ\forall xQ 与 ∃xQ\exists xQ 是公式；只有有限次使用这些规则得到的符号串才是公式。

3. 谓词公式的语义

说明给定一阶语言、结构和赋值后，谓词公式如何获得语义。

查看第 3 小题源答案

先由解释和变元赋值确定每个项的对象，再由谓词解释确定原子公式真值；¬,∧,∨,→,↔\neg,\land,\lor,\to,\leftrightarrow 按相应真值函数递归计算；∀xQ(x)\forall xQ(x) 在论域每个对象代入都真时为真，∃xQ(x)\exists xQ(x) 在至少一个对象代入为真时为真。

4. 可满足性与有效性

表述公式的可满足性与有效性。

查看第 4 小题源答案

若至少存在一个模型使公式 QQ 为真，则 QQ 可满足；若每个模型都使 QQ 为真，则 QQ 有效，记作 ⊨Q\models Q。

5. 公理推演

表述“从前提集 Γ\Gamma 推演 QQ”的定义。

查看第 5 小题源答案

存在有限公式序列 A1,…,AnA_1,\ldots,A_n，末项为 QQ，而每个 AkA_k 都是公理、属于 Γ\Gamma，或由此前公式按系统推理规则得到，就称它是 QQ 从 Γ\Gamma 的推演，记作 Γ⊢Q\Gamma\vdash Q。

三、范式与译码器（10 分）

1. 主合取范式

求

((P∨Q)→R)→P((P\lor Q)\to R)\to P

的主合取范式。

查看第 1 小题源答案与补充校正

源答案化简到普通合取范式

(P∨Q)∧(P∨¬R),(P\lor Q)\land(P\lor\neg R),

但题目要求“主”合取范式。补充按公式为假的三行 (P,Q,R)=(0,0,0),(0,0,1),(0,1,1)(P,Q,R)=(0,0,0),(0,0,1),(0,1,1) 展开：

(P∨Q∨R)∧(P∨Q∨¬R)∧(P∨¬Q∨¬R).(P\lor Q\lor R) \land(P\lor Q\lor\neg R) \land(P\lor\neg Q\lor\neg R).

2. 带使能端的三位译码器

使能端 E=0E=0 时所有输出为 0；E=1E=1 时，输入 x2x1x0x_2x_1x_0 从 000000 至 111111 分别使 y0y_0 至 y7y_7 为 1。给出各输出表达式。

查看第 2 小题源答案 y0=E∧¬x2∧¬x1∧¬x0,y1=E∧¬x2∧¬x1∧x0,y2=E∧¬x2∧x1∧¬x0,y3=E∧¬x2∧x1∧x0,y4=E∧x2∧¬x1∧¬x0,y5=E∧x2∧¬x1∧x0,y6=E∧x2∧x1∧¬x0,y7=E∧x2∧x1∧x0.\begin{aligned} y_0&=E\land\neg x_2\land\neg x_1\land\neg x_0,& y_1&=E\land\neg x_2\land\neg x_1\land x_0,\\ y_2&=E\land\neg x_2\land x_1\land\neg x_0,& y_3&=E\land\neg x_2\land x_1\land x_0,\\ y_4&=E\land x_2\land\neg x_1\land\neg x_0,& y_5&=E\land x_2\land\neg x_1\land x_0,\\ y_6&=E\land x_2\land x_1\land\neg x_0,& y_7&=E\land x_2\land x_1\land x_0. \end{aligned}

四、语义方法（20 分）

1. 命题推论

判断下列推论；成立则证明，不成立则给出反例：

((p→q)∧p)⊨q,((p\to q)\land p)\models q, ((p→q)∧¬p)⊨¬q.((p\to q)\land\neg p)\models\neg q.
查看第 1 小题源答案与补全

第一条成立：前提同时给出 p=1p=1 和 p→q=1p\to q=1，故 q=1q=1。

第二条不成立。补充反例取 p=0,q=1p=0,q=1：此时 p→qp\to q 与 ¬p\neg p 都真，而 ¬q\neg q 假。

2. 谓词推论

判断：

∃x∀yQ(x,y)⊨∀y∃xQ(x,y),\exists x\forall yQ(x,y)\models\forall y\exists xQ(x,y), ∀x∃yQ(x,y)⊨∃y∀xQ(x,y).\forall x\exists yQ(x,y)\models\exists y\forall xQ(x,y).
查看第 2 小题源答案与补全

第一条成立：前提给出一个对所有 yy 都有效的固定见证，可把它用于结论中每个 yy。

第二条不成立。补充反例取整数论域并令 Q(x,y)Q(x,y) 表示 y>xy>x。每个 xx 都有更大的 yy，但不存在一个整数大于所有整数。

五、公理方法（20 分）

1

证明：

P→(Q→R),Q⊢P→R.P\to(Q\to R),\quad Q\vdash P\to R.
查看第 1 小题源证明
  1. P→(Q→R)P\to(Q\to R)，前提；
  2. (P→(Q→R))→((P→Q)→(P→R))(P\to(Q\to R))\to((P\to Q)\to(P\to R))，A2；
  3. (P→Q)→(P→R)(P\to Q)\to(P\to R)，MP；
  4. Q→(P→Q)Q\to(P\to Q)，A1；
  5. QQ，前提；
  6. P→QP\to Q，MP；
  7. P→RP\to R，MP。

2（二选一）

证明：

⊢∀xQ(x)→∀yQ(y)\vdash\forall xQ(x)\to\forall yQ(y)

（yy 不在 QQ 中出现），或证明

⊢∀x∀yR(x,y)→∀xR(x,x).\vdash\forall x\forall yR(x,y)\to\forall xR(x,x).
查看第 2 小题源证明

第一式：先由量词公理得 ∀xQ(x)→Q(y)\forall xQ(x)\to Q(y)，对 yy 使用 UG，再用量词公理把 ∀y\forall y 移到后件，即得结论。

第二式：依次实例化 xx 与 yy 得 ∀x∀yR(x,y)→R(x,x)\forall x\forall yR(x,y)\to R(x,x)，再对 xx 概括，并利用量词公理把全称量词移入后件。

六、归结法（10 分）

用归结法证明：

P∧Q→R⊢(P→R)∨(Q→R).P\land Q\to R\vdash(P\to R)\lor(Q\to R).
查看源归结证明

前提与结论的否定合取，得到子句集

{¬P∨¬Q∨R,P,Q,¬R}.\{\neg P\lor\neg Q\lor R, P, Q, \neg R\}.

依次归结：

¬P∨¬Q∨R,P⇒¬Q∨R,\neg P\lor\neg Q\lor R, P \Rightarrow\neg Q\lor R, ¬Q∨R,Q⇒R,\neg Q\lor R, Q\Rightarrow R, R,¬R⇒□.R, \neg R\Rightarrow\square.

因此原推论成立。

评论