2017–2018 学年第二学期期末真题

来源为课程目录中的 17-18.pdf，考试时间为 2018 年 7 月 4 日。原卷没有答案，以下解析均为补充推导，不冒充官方答案。

一、简答题（20 分）

1. 联结词完全集

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

查看第 1 小题补充解析

可取 $\{\neg,\lor\}$ ：

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

由 De Morgan 律

p\land q\equiv\neg(\neg p\lor\neg q),

所以它能定义 $\{\neg,\land,\lor\}$ ，因而完备。

2. 谓词逻辑公理系统

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

查看第 2 小题补充解析

命题部分为 A1–A3：

R\to(Q\to R),

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

(\neg Q\to\neg R)\to(R\to Q).

量词公理为

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

其中 $t$ 对 $x$ 可代入，以及

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

其中 $x$ 不在 $Q$ 中自由出现。规则为 MP 与 UG。

3. 可靠性与完备性

使用 $\vdash$ 和 $\models$ 解释公理系统的可靠性和完备性。（4 分）

查看第 3 小题补充解析

\Gamma\vdash Q\Longrightarrow\Gamma\models Q \quad\text{(soundness)},

\Gamma\models Q\Longrightarrow\Gamma\vdash Q \quad\text{(completeness)}.

4. 量词互换表示

用存在量词表示 $\forall xQ(x)$ ，用全称量词表示 $\exists xQ(x)$ 。（5 分）

查看第 4 小题补充解析

\forall xQ(x)\equiv\neg\exists x\neg Q(x),

\exists xQ(x)\equiv\neg\forall x\neg Q(x).

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

1. 命题合式公式

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

查看第 1 小题补充解析

选 $\{\neg,\to\}$ ：

每个命题变元是公式；
若 $A$ 是公式，则 $\neg A$ 是公式；
若 $A,B$ 是公式，则 $A\to B$ 是公式；
只有有限次使用这些规则得到的符号串才是公式。

2. 两个论域中的真值

在自然数论域和整数论域上分别判断：

a

\forall x(Q(x)\to0\le x).

查看第 2(a) 小题补充解析

自然数论域为真；整数论域为假。

b

\exists x\bigl(Q(x)\land\forall y(Q(y)\to x\le y)\bigr).

查看第 2(b) 小题补充解析

自然数论域为真，最小自然数作见证；整数论域为假，整数没有最小元。

c

\forall x\forall y \bigl(Q(x)\land Q(y)\to x+y=y+x\bigr).

查看第 2(c) 小题补充解析

两个论域都为真。

d

\forall x\forall y \bigl(Q(x)\land Q(y)\to x+y\le y\bigr).

查看第 2(d) 小题补充解析

两个论域都为假。例如取 $x=1,y=0$ ，则 $x+y\le y$ 不成立。

3. 命题归结法原理

给出命题逻辑归结法的基本原理。（5 分）

查看第 3 小题补充解析

要证 $\Gamma\models R$ ，把 $\Gamma\land\neg R$ 化为子句集。若能对互补文字连续应用归结规则并推出空子句 $\square$ ，则该子句集不可满足，从而原推论成立。

4. UG 规则

举例说明谓词逻辑概括规则 UG 的使用。（5 分）

查看第 4 小题补充解析

由已证公式 $Q(x)$ 可使用 UG 得 $\forall xQ(x)$ 。带前提时须检查 $x$ 不在相关前提中自由出现。

三、判断题（20 分，每题 5 分）

1

设

\not\models Q.

$Q$ 是否永假？给出理由。

查看第 1 小题补充解析

不一定。 $\not\models Q$ 只说明 $Q$ 不是永真式，即至少有一个赋值使它为假；它仍可能在其他赋值下为真。例如命题变元 $p$ 不是永真式，也不是永假式。

2

存在公式 $Q$ 使

\Gamma\not\models Q.

$\Gamma$ 是否可满足？

查看第 2 小题补充解析

可满足。逻辑推论不成立就意味着存在一个模型满足 $\Gamma$ 而不满足 $Q$ 。

3

判断

\exists xQ(x)\land\exists xR(x) \models \exists x(Q(x)\land R(x))

是否成立。

查看第 3 小题补充解析

不成立。取论域 $\{a,b\}$ ，让 $Q$ 只对 $a$ 真、 $R$ 只对 $b$ 真。前件真，后件假。

4

判断

\forall x(Q(x)\lor R(x)) \models \forall xQ(x)\lor\forall xR(x)

是否成立。

查看第 4 小题补充解析

不成立。仍取二元素论域，让两个谓词分别只对一个对象真。

四、范式题（10 分，每题 5 分）

1. 合取范式

求

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

的合取范式。

查看第 1 小题补充解析

\begin{aligned} (Q\lor R)\to(P\land Q\to R) &\equiv \neg(Q\lor R)\lor(\neg(P\land Q)\lor R)\\ &\equiv (\neg Q\land\neg R)\lor\neg P\lor\neg Q\lor R\\ &\equiv \neg P\lor\neg Q\lor R. \end{aligned}

2. 二进制加法器

根据原卷三输入二进制加法器真值表，给出和位 $S_0$ 与进位位 $C_0$ 的逻辑表达式。

查看第 2 小题补充解析

记输入为 $A_0,B_0,C_{-1}$ ：

S_0=A_0\oplus B_0\oplus C_{-1},

C_0= (A_0\land B_0) \lor(A_0\land C_{-1}) \lor(B_0\land C_{-1}).

若要求主析取范式，应按原表把每个输出为 $1$ 的真值行写成极小项后析取。

五、证明题（30 分）

1. 命题公理证明

只用公理系统的公理和规则证明：

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

查看第 1 小题补充解析

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

2. 谓词公理证明

只用公理系统的公理和规则证明：

\vdash \forall xP(x)\to\exists xP(x).

查看第 2 小题补充解析

取新常元 $c$ ：

$\forall xP(x)\to P(c)$ ，A4；
$P(c)\to\exists xP(x)$ ，存在量词引入定理；
由传递定理及 1、2 得 $\forall xP(x)\to\exists xP(x)$ 。

若按课程定义 $\exists xP(x):=\neg\forall x\neg P(x)$ ，第 2 行可由已证谓词定理展开。

3. 命题归结证明

用命题归结法证明：

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

查看第 3 小题补充解析

前提与否定结论给出子句集：

\Omega= \{\neg P\lor R,\ \neg P\lor Q,\ P,\ \neg R\lor\neg Q\}.

归结：

\neg P\lor R,\ P\Longrightarrow R,

\neg P\lor Q,\ P\Longrightarrow Q,

\neg R\lor\neg Q,\ R\Longrightarrow\neg Q,

Q,\ \neg Q\Longrightarrow\square.

所以加入否定结论后不可满足，原推论成立。

2017–2018 学年第二学期期末真题

一、简答题（20 分）

1. 联结词完全集

2. 谓词逻辑公理系统

3. 可靠性与完备性

4. 量词互换表示

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

1. 命题合式公式

2. 两个论域中的真值

a

b

c

d

3. 命题归结法原理

4. UG 规则

三、判断题（20 分，每题 5 分）

1

2

3

4

四、范式题（10 分，每题 5 分）

1. 合取范式

2. 二进制加法器

五、证明题（30 分）

1. 命题公理证明

2. 谓词公理证明

3. 命题归结证明

评论