2015–2016 学年期末真题

#真题

来源为课程目录中的 15-16.pdf。原卷没有答案，以下答案均为补充推导，不冒充官方答案。原卷目录写“证明题 30 分”，题面页写“32 分”，三小题各 10 分；我保留这处源卷不一致。

一、简答题（20 分）

1. 联结词完全集

给出任意一组命题逻辑联结词完备集，并用真值表表示相应的逻辑操作。（5 分）

查看第 1 小题补充解析

可取 {¬,∧}\{\neg,\land\}：

ppqq¬p\neg pp∧qp\land q
0010
0110
1000
1101

因为 p∨q≡¬(¬p∧¬q)p\lor q\equiv\neg(\neg p\land\neg q)，所以这组联结词可以定义任意真值函数。

2. 谓词逻辑公理系统

给出谓词逻辑公理系统。（5 分）

查看第 2 小题补充解析

课程使用的 Hilbert 系统包括命题公理 A1–A3：

R→(Q→R),R\to(Q\to R), (P→(Q→R))→((P→Q)→(P→R)),(P\to(Q\to R))\to((P\to Q)\to(P\to R)), (¬Q→¬R)→(R→Q),(\neg Q\to\neg R)\to(R\to Q),

量词公理

∀xQ(x)→Q[x/t],\forall xQ(x)\to Q[x/t],

其中 tt 对 xx 可代入，以及

∀x(Q→R(x))→(Q→∀xR(x)),\forall x(Q\to R(x))\to(Q\to\forall xR(x)),

其中 xx 不在 QQ 中自由出现。推理规则为 MP 与 UG。

3. 可靠性与完备性

使用符号 ⊢\vdash 和 ⊨\models 解释公理系统的可靠性和完备性。

查看第 3 小题补充解析

可靠性是

Γ⊢Q⟹Γ⊨Q;\Gamma\vdash Q\Longrightarrow\Gamma\models Q;

完备性是

Γ⊨Q⟹Γ⊢Q.\Gamma\models Q\Longrightarrow\Gamma\vdash Q.

4. 前束范式与 Skolem 范式

定义一阶逻辑的前束范式与 Skolem 范式。（5 分）

查看第 4 小题补充解析

前束范式把所有量词移到公式最前面：

Q1x1⋯Qnxn,M,Q_1x_1\cdots Q_nx_n,M,

其中 Qi∈{∀,∃}Q_i\in\{\forall,\exists\}，而母式 MM 不含量词。

Skolem 化继续消去存在量词：若 ∃y\exists y 前没有全称变量，就用新常元替换 yy；若它前面有 x1,…,xkx_1,\ldots,x_k，就用新 Skolem 函数 f(x1,…,xk)f(x_1,\ldots,x_k) 替换。所得全称公式称为 Skolem 范式。Skolem 化保持可满足性，不保证与原式逻辑等价。

二、论述题（20 分，每题 5 分）

1. 命题逻辑合式公式

任意选用一组完备的逻辑联结词，给出命题逻辑合式公式定义。

查看第 1 小题补充解析

选 {¬,→}\{\neg,\to\}：命题变元是合式公式；若 A,BA,B 是合式公式，则 ¬A\neg A 与 (A→B)(A\to B) 是合式公式；只有有限次应用这些规则得到的符号串才是合式公式。

2. 谓词逻辑合式公式

任意选用一组完备的逻辑联结词，给出谓词逻辑合式公式定义。

查看第 2 小题补充解析

先递归定义项。谓词作用于相应个数的项得到原子公式；若 A,BA,B 是公式，则 ¬A\neg A 与 A→BA\to B 是公式；若 AA 是公式，则 ∀xA\forall xA 是公式；只有有限次使用这些规则得到的符号串才是公式。其余联结词和 ∃\exists 都可作为缩写定义。

3. 两个论域中的真值

在自然数论域和整数论域上分别解释并求下式的逻辑真值：

∃x(Q(x)∧∀y(Q(y)→x≤y)).\exists x\bigl(Q(x)\land\forall y(Q(y)\to x\le y)\bigr).
查看第 3 小题补充解析

它说“论域中存在一个最小的 QQ 对象”。在自然数论域为真，最小自然数可作见证；在整数论域为假，因为整数没有最小元。

4. UG 规则

举例说明谓词逻辑的概括规则 UG。

查看第 4 小题补充解析

UG 规则是由已证公式 Q(x)Q(x) 推出 ∀xQ(x)\forall xQ(x)。例如从定理

∀uP(u)→P(x)\forall uP(u)\to P(x)

可概括得到

∀x(∀uP(u)→P(x)).\forall x\bigl(\forall uP(u)\to P(x)\bigr).

在带前提的推演中，必须确认被概括变量不在相关未解除前提中自由出现。

三、判断题（18 分，每题 6 分）

1

判断推论

(P→Q)→(P→R)⊨P→(Q→R)(P\to Q)\to(P\to R)\models P\to(Q\to R)

是否成立；成立则证明，不成立则给出反例。

查看第 1 小题补充解析

成立。前提与结论都等价于

¬P∨¬Q∨R.\neg P\lor\neg Q\lor R.

因此每个使前提为真的赋值都使结论为真。

2

判断

∃x(Q(x)∧R(x))↔(∃xQ(x)∧∃xR(x))\exists x(Q(x)\land R(x)) \leftrightarrow (\exists xQ(x)\land\exists xR(x))

是否成立；不成立则给出反例。

查看第 2 小题补充解析

不成立。取论域 {a,b}\{a,b\}，令 QQ 只在 aa 上为真，RR 只在 bb 上为真。右边为真，但没有同一个对象同时满足 QQ 与 RR，所以左边为假。

3

判断

∀x(Q(x)∨R(x))↔(∀xQ(x)∨∀xR(x))\forall x(Q(x)\lor R(x)) \leftrightarrow (\forall xQ(x)\lor\forall xR(x))

是否成立；不成立则给出反例。

查看第 3 小题补充解析

不成立。仍取论域 {a,b}\{a,b\}，让 QQ 只在 aa 上为真、RR 只在 bb 上为真。每个对象都至少满足一个谓词，左边为真；但两个谓词都不是处处为真，右边为假。

四、范式题（12 分，每题 6 分）

1. 主合取范式

求

(S∧R→P)→(R∨P)(S\land R\to P)\to(R\lor P)

的主合取范式。

查看第 1 小题补充解析

公式仅在 (S,R,P)=(0,0,0)(S,R,P)=(0,0,0) 和 (1,0,0)(1,0,0) 时为假，所以主合取范式为

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

2. 多路选择器

已知真值表：

X1X_1X2X_2X3X_3Y1Y_1Y2Y_2
00001
00110
01001
01101
10010
10101
11000
11110

给出 Y1Y_1 和 Y2Y_2 的逻辑表达式。

查看第 2 小题补充解析

按输出为 1 的行写最小项：

Y1=(¬X1∧¬X2∧X3)∨(X1∧¬X2∧¬X3)∨(X1∧X2∧X3),Y_1=(\neg X_1\land\neg X_2\land X_3) \lor(X_1\land\neg X_2\land\neg X_3) \lor(X_1\land X_2\land X_3), Y2=(¬X1∧¬X2∧¬X3)∨(¬X1∧X2∧¬X3)∨(¬X1∧X2∧X3)∨(X1∧¬X2∧X3).\begin{aligned} Y_2={}&(\neg X_1\land\neg X_2\land\neg X_3) \lor(\neg X_1\land X_2\land\neg X_3)\\ &\lor(\neg X_1\land X_2\land X_3) \lor(X_1\land\neg X_2\land X_3). \end{aligned}

五、证明题（题面页标 32 分）

1. 命题公理证明

只用命题逻辑公理系统的公理和规则证明：

P→R,R→S⊢P→S.P\to R,\quad R\to S\vdash P\to S.
查看第 1 小题补充解析

补充推导可调用系统中已证出的假言三段论：

⊢(P→R)→((R→S)→(P→S)).\vdash(P\to R)\to((R\to S)\to(P\to S)).

依次对前提 P→RP\to R、R→SR\to S 使用两次 MP，得到 P→SP\to S。若考场要求把派生定理完全展开，就要用 A1、A2 先证明该假言三段论，再做这两次 MP。

2. 谓词公理证明

只用谓词逻辑公理系统的公理和规则证明（yy 不在 QQ 中出现）：

⊢∀xQ(x)→∀yQ(y).\vdash\forall xQ(x)\to\forall yQ(y).
查看第 2 小题补充解析

令 A=∀xQ(x)A=\forall xQ(x)：

  1. A→Q(y)A\to Q(y)，量词公理实例；
  2. ∀y(A→Q(y))\forall y(A\to Q(y))，由 1 使用 UG；
  3. ∀y(A→Q(y))→(A→∀yQ(y))\forall y(A\to Q(y))\to(A\to\forall yQ(y))，量词公理实例，因为 yy 不在 AA 中自由出现；
  4. A→∀yQ(y)A\to\forall yQ(y)，由 2、3 使用 MP。

3. 命题归结法

用命题逻辑归结法证明：

P→(R∧Q)⊢(P→R)∧(P→Q).P\to(R\land Q)\vdash(P\to R)\land(P\to Q).
查看第 3 小题补充解析

把前提与结论的否定合取。前提化为

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

结论的否定为

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

后者分两支即可看出：若取 P∧¬RP\land\neg R，它与子句 ¬P∨R\neg P\lor R 归结出空子句；若取 P∧¬QP\land\neg Q，它与 ¬P∨Q\neg P\lor Q 归结出空子句。故前提与结论之否定不可满足，原推论成立。

评论