2013–2014 学年期末真题（残卷）

来源为 13-14.doc。源文件只留下第一、第五和第六大题，第二至第四大题没有题面，我不据前后年份补造。源文件自注第五题与上一届相同，并附了部分证明。

一、简答题（20 分）

1. 命题联结词真值表

用真值表给出命题逻辑的与、或、非。

查看第 1 小题补充答案

$p$	$q$	$p\land q$	$p\lor q$	$\neg p$
0	0	0	0	1
0	1	0	1	1
1	0	0	1	0
1	1	1	1	0

2. 谓词逻辑公理系统

给出谓词逻辑公理系统。

查看第 2 小题补充答案

系统由命题公理 A1–A3、两个量词公理以及 MP、UG 两条规则组成。量词公理是

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

和

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

分别要求 $t$ 对 $x$ 可代入，以及 $x$ 不在 $Q$ 中自由出现。

3. 可靠性与完备性

解释可靠性与完备性。

查看第 3 小题补充答案

\Gamma\vdash Q\Longrightarrow\Gamma\models Q

称为可靠性；

\Gamma\models Q\Longrightarrow\Gamma\vdash Q

称为完备性。

4. 连续性的谓词表达

给出函数连续的谓词逻辑表达式。

查看第 4 小题补充答案

原文件未规定具体点。函数 $f$ 在 $a$ 处连续可写成

\forall\varepsilon>0\; \exists\delta>0\; \forall x\left( |x-a|<\delta\to|f(x)-f(a)|<\varepsilon \right).

二至四、源文件缺页

课程目录没有留下这些题的题面，故不还原。

五、公理方法（20 分）

1

证明：

P\to(Q\to R),\quad Q\vdash P\to R.

查看第 1 小题源证明

源证明整理如下：

$P\to(Q\to R)$ ，前提；
$(P\to(Q\to R))\to((P\to Q)\to(P\to R))$ ，A2；
$(P\to Q)\to(P\to R)$ ，1、2 使用 MP；
$Q\to(P\to Q)$ ，A1；
$Q$ ，前提；
$P\to Q$ ，4、5 使用 MP；
$P\to R$ ，3、6 使用 MP。

2（源卷二选一）

证明（ $y$ 不在 $Q$ 中出现）：

\vdash\forall xQ(x)\to\forall yQ(y).

源文件还列出另一选项：

\vdash\forall x\forall yR(x,y)\to\forall xR(x,x),

但没有留下其证明。

查看第 2 小题源证明

$\forall xQ(x)\to Q(y)$ ，量词公理；
$\forall y(\forall xQ(x)\to Q(y))$ ，UG；
$\forall y(\forall xQ(x)\to Q(y))\to(\forall xQ(x)\to\forall yQ(y))$ ，量词公理；
$\forall xQ(x)\to\forall yQ(y)$ ，2、3 使用 MP。

另一选项可先两次使用全称实例化得到 $\forall x\forall yR(x,y)\to R(x,x)$ ，再概括 $x$ 。

六、归结法（10 分）

用归结法证明：

\vdash Q\to(P\to(Q\land P)).

查看补充归结证明

源文件没有留下答案。否定待证公式：

\neg(Q\to(P\to(Q\land P))) \equiv Q\land P\land\neg(Q\land P).

其子句集为

\{Q, P, \neg Q\lor\neg P\}.

先用 $Q$ 与 $\neg Q\lor\neg P$ 归结得 $\neg P$ ，再与 $P$ 归结得空子句 $\square$ ，所以原公式永真。