《数理逻辑》试卷附答案

《数理逻辑》期末试卷附答案

一、判断题（每题1分，共10分）

1.命题公式$（P'land\negP）$是永真式。（*）

2.任何命题公式都存在与之等价的析取范式。（4）

3.在自然演绎系统中，推理规则MP（ModusPonens）可以表示

为：若$\alpha\to\beta$和$\alpha$为真，则$\beta$为真。（4）

4.谓词逻辑中，全称量词$\forall$的辖域可以包含存在量词

$\exists$o（<）

5.若公式$\alpha\models\beta$，则$\alpha$是$\beta$的逻辑

后承。（X）

6.任何矛盾式在真值表中至少有一行为真。（x）

7.集合论中的ZFC公理系统是一个完备的逻辑系统。（x）

8.命题逻辑中的重言式在任意赋值下均为真。（4）

9.谓词逻辑中的替换实例规则只能应用于全称量词。（x）

10.哥德尔不完备定理表明，任何包含算术系统的形式化理论都存在

不可判定的命题。（T）

二、填空题（每题1分，共10分）

1.命题公式$（P\t。Q）'land（Q\t。R）$的等价式是（$P\toR$）。

2.谓词公式$\forallx\existsy(P(x)\toQ(y))$的否定形式是

($\existsx\forally(\negP(x)Mor\negQ(y))$)。

3.自然演绎系统中的UI规则全称是(全称量词引入规则)o

4.命题公式$(\negP\lorQ)\land(PMor\negQ)$的真值表有

(2)行。

5.集合论中，空集$\emptyset$的舞集是($\{\emptyset\}$)。

6.在谓词逻辑中，公式$\existsx\forally(P(x,y)\toQ(y))$的自由

变元是($x$)o

7.命题逻辑中的矛盾式用符号表示为(价bot$或$0$)。

8.集合$A=\{1,2\}$的笛卡尔积$A\timesA$的元素个数为

(4)。

9.命题公式$(PMeftrightarrowQ)$的等价析取范式是($(P

\landQ)\lor(\negPMand\negQ)$)。

10.自然数集$\mathbb{N}$的基数(即势)是($\aleph_0$)。

三、单选题(每题2分，共20分)

1.以下哪个命题公式是重言式？(B)

A.$P\land\negP$

B.$(P\toQ)Mor\negP$

C.$(PMorQ)\to(QMorP)$

D.$\neg(P\to\negP)$

2.谓词逻辑公式$\forallx(P(x)\to\existsyQ(x,y))$的辖域为

(C)。

A.仅$\forallx$

B.仅$\existsy$

C.$\forallx$和$\existsy$

D.无辖域

3.在自然演绎系统中，以下哪个推理是正确的？(A)

A.前提：$P\lorQ$,$P\toR$；结论：$R$

B.前提：$P\landQ$,$P\toR$；结论：$Q$

C.前提：$\negP$,$P\toQ$；结论：$Q$

D.前提：$P\toQ$,$Q\toR$；结论：$P\toR$

4.集合$A=\{\emptyset,\{\emptyset\}\}$的塞集是(D4

A.$\{\emptyset\}$

B.$\{\{\emptyset\}\}$

C.$\{\emptyset,\{\emptyset\}\}$

D.$\{\emptyset,\{\emptyset\},\{\{\emptyset\}\},\{\emptyset,

\{\emptyset\}\}\}$

5.命题公式$(PVeftrightarrowQ)$的等价合取范式是(B)。

A.$(PMandQ)Mor(\negPMand\negQ)$

B.$(PMandQ)Mor(\negPMandQ)Mor(PMand\negQ)Mor(\neg

PMand\negQ)$

C.$(P\toQ)Mand(Q\toP)$

D.$(PMorQ)Mand(\negPMor\negQ)$

6.以下哪个系统具有完备性？(A)

A.命题逻辑的自然演绎系统

B.一阶谓词逻辑的自然演绎系统

C.集合论的ZFC系统

D.希尔伯特系统

7.谓词逻辑公式$\existsx\forally(P(x,y)MandQ(y))$中,自由变

元的个数为(C)o

A.0

B.1

C.2

D.3

8.在命题逻辑中，公式$\neg（\negP\lorQ）$的等价式是（B）。

A.$P\land\negQ$

B.$P\landQ$

C.$\negP\land\negQ$

D.$\negPMorQ$

9.以下哪个命题不是哥德尔不完备定理的结论？（D）

A,存在不可判定的命题

B.系统内无法证明自身的一致性

C.一致性要求系统不完备

D.所有命题均可被证明或证伪

10.集合论中，若$A$的基数为$\aleph_0$,则$A$是（B）。

A.有限集

B,可数集

C.不可数集

D.空集

四、多选题（每题2分，共20分）

1.以下哪些公式与$P\lorQ$等价？（ACD）

A.$\neg（\negP\land\negQ）$

B.$（PMandQ）Mor（\negP\land\negQ）$

C.$（P\toQ）\lor（Q\toP）$

D.$\negP\toQ$

2.自然演绎系统中的推理规则包括（ABC）o

A.MP（ModusPonens）

B.UI（全称量词引入）

C.ES（存在量词消去）

D.CP（反证法）

3.谓词逻辑中的量词辖域规则包括（BD）。

A.量词可以嵌套任意层

B.量词的辖域从量词开始到最近的括号或句末

C.存在量词优先于全称量词

D.量词作用域内不能引入新变量

4.以下哪些系统是形式化系统？（ABC）

A.命题逻辑

B.一阶谓词逻辑

C.集合论ZFC

D.自然语言系统

5.命题公式$(P\t。Q)'land(R\toS)$的成真赋值有(ABD)。

A.$P=0,Q=1,R=0,S=1$

B.$P=1,Q=1,R=1,S=1$

C.$P=1,Q=0,R=1,S=0$

D.$P=0,Q=0,R=1,S=0$

6.集合运算的性质包括(ACD)o

A,并集交换律：$A\cupB=B\cupA$

B.交集对补集分配律：$A\cap(B\setminusC)=(A\capB)

\setminusC$

C.幕等律：$A\cupA=A$

D.德摩根律:$\neg(A\cupB)=\negA\cap\negB$

7.以下哪些命题属于逻辑悖论？(AC)

A.说谎者悖论

B.哥德尔不完备定理

C.罗素悖论

D.费马大定理

8.谓词逻辑中的推理规则包括（ABC）。

A.UG（全称量词消去）

B.EG（存在量词引入）

C.RE（替换实例）

D.RAA（归谬法）

9.命题逻辑中的等价关系满足（ABD）。

A.自反性：$\alpha\equiv\alpha$

B.对称性：若$\alpha\equiv\beta$,则$\beta\equiv\alpha$

C.传递性：若$\alpha\equiv\beta$且$\beta\equiv\gamma$,

则$\alpha\equiv\gamma$

D.可判定性：任意公式的等价性可判定

10.集合论中的公理包括（ABC）o

A.外延公理

B.空集公理

C.幕集公理

D.选择公理(但不属于ZFC核心公理)

五、问答题(每题5分，共20分)

1.简述命题逻辑中的真值表方法，并说明其作用。

答：真值表方法是通过列出所有可能的赋值组合，计算每个公式在各

赋值下的真值，从而判断公式的类型(如永真、矛盾、可满足)。其

作用包括：

(1)验证公式的等价性；

(2)判定公式的可满足性；

(3)简化复杂公式的结构。

2.解释谓词逻辑中的全称量词消去规则(UG)及其限制条件。

答：全称量词消去规则(UG)允许从前提$\forallx\alpha(x)$推出

$\alpha(t)$,其中$t$是任意项。限制条件包括:

(1)$t$必须是公式中未出现的个体常元或函数项；

(2)若$t$是变量，需保证其不在其他量词的辖域内。

违反限制可能导致推理错误，例如在存在量词辖域内引入新变量。

3.证明命题公式的分配律：$(P'land(Q\lorR))\equiv(P'landQ)

\lor(P\landR)$。

答:

(1)左推右：$(P\land(Q\lorR))\to(P\landQ)Mor(P\landR)$,

根据分配律定义展开；

(2)右推左:$(P\landQ)\lor(PMandR)\toP\land(