2014–2015 学年期末真题

来源为 14-15.doc。该文件同时含题目和部分作答；折叠块中优先忠实整理源答案，凡原文件没有展开的地方均明确写作“补充说明”。

一、判断题和简答题（20 分）

1. 判断题

判断下列说法。

在命题逻辑中，存在从功能真值表求逻辑表达式的一般方法。
若 $\Gamma\models\neg Q\land Q$ ，则 $\Gamma$ 一致。
在公理系统中，需要考虑具体概念的含义。
联结词集 $\{\neg,\land,\lor\}$ 是完全集。
在自然数公理系统中，若 $\Gamma\models Q$ ，则 $\Gamma\vdash Q$ 。

查看判断题源答案

源答案依次为：正确、错误、错误、正确、错误。

第 2 项中，若前提能语义推出矛盾，则前提集不可满足，因而不一致。第 5 项考查自然数理论的不完备性：可靠不自动推出完备。

2. 简答题

给出命题概念。
给出模型概念。
给出自然语言命题符号化的方法。
给出判断证明是否正确的方法。
用谓词公式表示：对任意 $\varepsilon>0$ ，存在 $\delta>0$ ，对任何增量 $\Delta x$ ，若 $|\Delta x|<\delta$ ，则 $|\Delta f(x)/\Delta x-A|<\varepsilon$ 。

查看简答题源答案

命题是有确定真假的陈述句。
模型是给定论域、非逻辑符号解释和变元赋值后，使语言中项和公式获得语义的结构。
源答案给出三步：识别陈述句；把原子陈述符号化；再把联结词和量词符号化。
源答案：证明序列每一步必须是公理、前提，或由此前步骤按推理规则得到。
源公式整理为

\forall\varepsilon\left( \varepsilon>0\to \exists\delta\left( \delta>0\land \forall\Delta x\left( |\Delta x|<\delta\to \left|\frac{\Delta f(x)}{\Delta x}-A\right|<\varepsilon \right) \right) \right).

二、论述题（20 分）

1. 判断是否为合式公式

按合式公式的递归定义说明下列符号串是否为公式：

(P\land Q\to R)\to(P\to(Q\to R)),

(\forall xP(x)\land\forall xQ(x)) \to \forall x(P(x)\land\neg Q(x)).

查看第 1 小题答案

两者均由原子公式经有限次使用联结词和量词形成，因此都是合式公式。这里只判断语法是否合规，不判断公式是否永真；第二式虽是公式，却不是普遍有效式。

2. 论域改变语义

给出一个公式 $Q$ ，使其在自然数论域和整数论域上的语义不同。

查看第 2 小题补充示例

原文件未给具体公式。可取

\forall x(x\ge0).

它在自然数论域为真，在整数论域为假。

3. 可靠是否意味着完备

给定一个公理系统是可靠的，它一定完备吗？给出理由或示例。

查看第 3 小题源答案

不一定。源答案以自然数公理系统为例：可靠性只保证“证得出的都语义为真”，并不保证“所有语义为真的都能在系统中证出”。

4. 一个模型中为真是否普遍有效

谓词合式公式 $Q$ 在某模型 $M$ 中为真， $Q$ 是否一定普遍有效？说明理由。

查看第 4 小题源答案与补充反例

不一定。普遍有效要求在所有模型中都真，而题设只给出一个模型。补充反例为 $\forall x(x\ge0)$ ：它在自然数模型为真，在整数模型为假。

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

1. 主合取范式

求

((P\to Q)\land(P\to R))\to(Q\land R)

的主合取范式。

查看第 1 小题补充解析

原文件没有写出答案。公式在 $(P,Q,R)=(0,0,0),(0,0,1),(0,1,0)$ 三个赋值下为假，所以主合取范式为

(P\lor Q\lor R) \land(P\lor Q\lor\neg R) \land(P\lor\neg Q\lor R).

2. 三位译码器

三位输入 $x_2x_1x_0$ 从 $000$ 到 $111$ 时，输出 $y_0$ 到 $y_7$ 依次仅有对应的一位为 1。给出 $y_7$ 至 $y_0$ 的表达式。

查看第 2 小题答案

\begin{aligned} y_0&=\neg x_2\land\neg x_1\land\neg x_0,& y_1&=\neg x_2\land\neg x_1\land x_0,\\ y_2&=\neg x_2\land x_1\land\neg x_0,& y_3&=\neg x_2\land x_1\land x_0,\\ y_4&=x_2\land\neg x_1\land\neg x_0,& y_5&=x_2\land\neg x_1\land x_0,\\ y_6&=x_2\land x_1\land\neg x_0,& y_7&=x_2\land x_1\land x_0. \end{aligned}

四、语义方法（20 分）

1. 命题逻辑推论

用语义方法证明：

Q\models(Q\to R)\to R.

查看第 1 小题补充解析

若赋值满足前提 $Q$ ，则 $Q=1$ 。此时 $Q\to R$ 与 $R$ 同值，所以 $(Q\to R)\to R$ 为 $R\to R$ ，恒为真。因此推论成立。

2. 谓词逻辑推论

用语义方法证明：

\exists x\forall yR(x,y)\models\forall y\exists xR(x,y).

查看第 2 小题补充解析

若前提为真，就有某个固定对象 $a$ ，使每个 $y$ 都满足 $R(a,y)$ 。于是对每个 $y$ ，都可选同一个 $x=a$ 作见证，所以结论为真。

五、公理方法（20 分）

1. 双重否定消去

只用公理和规则证明：

\vdash\neg\neg Q\to Q.

查看第 1 小题源证明脉络

源文件给出 8 步 Hilbert 推演。其核心是分别以 A1、A3 得到

\neg\neg Q\to(\neg\neg\neg\neg Q\to\neg\neg Q),

(\neg\neg\neg\neg Q\to\neg\neg Q) \to(\neg Q\to\neg\neg\neg Q),

(\neg Q\to\neg\neg\neg Q)\to(\neg\neg Q\to Q),

再由已证定理 $A\to A$ 和 A2 连续使用 MP，得到 $\neg\neg Q\to Q$ 。

2. 交换全称量词