大连海事大学2013-2014学年第一学期硕士研究生《数理逻辑》试题及参考答案

【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《大连海事大学2013-2014学年第一学期硕士研究生《数理逻辑》试题及参考答案》，欢迎阅读！

专业班级： 学号： 姓名：

教务处试卷编号：

备注：1、试卷背面为演草区（不准用自带草纸） 装 订 线

课程编号: 20312019 考核方式：（开卷） 考核时间：2013年12月24日8:00-9:35 主考教师允许携带的用品:教科书、参考书、课件



大连海事大学2013--2014学年第一学期硕士研究生《数理逻辑》试卷及参考答案

题号

得分

一

二

三

四

五

六

七

平时分

卷面分

总分

一．（本题10分）判断下述说法是否正确，正确的在【 】中填写T，不正确的在【 】中填写F，不必说明理由。

1. 【T】如果命题公式AB是恒假的，则A是恒假的并且B是恒假的。 2. 【F】,,是逻辑连接符的极小全功能集。 3. 【T】如果m和m都是关于命题变量p1,

,pn的极小项，则mm当且仅当mmm。

4. 【T】任意命题公式都存在唯一的与之等值的主合取范式。 5. 【F】在一阶逻辑中，xPx,yxPx,z。

6. 【T】项fa,b对公式yPx,y中的自由变量x是自由的。 7. 【F】在一阶逻辑中，xPxxQxxPxQx。 8. 【F】任意一阶公式都与其所对应的子句集等值。

9. 【T】形式系统L的扩张L如果不是相容的，那么L必然是完全的。 10.【T】设A是形式系统K的公式，A是A所对应的封闭公式。则



K

AA。

二. (10分) 设A,B,C是命题公式。试回答下述问题并证明你的结论。

⑴ 如果ACBC,是否一定有AB？(4分) ⑵ 如果ACBC,是否一定有AB？（6分）

解 ⑴ 如果ACBC，不一定有AB，事实上，只要C是重言式，则一定有ACAC，但这时A A。⑵ 如果ACBC，一定有AB。事实上，根据的结合律和置换规则，有

AACCACCACCBCCBCCB。

三. (15分) 设J和J是形式系统L的两个相容完全扩张。试证明，JJ当且仅当存在公式A，使得

证明 设J和J是形式系统L的两个相容完全扩张。 首先，如果存在公式A，使得



J

J

A但

J

A。

A但

J

A，这时A是J的定理但不是J的定理，故显然有JJ，

反之，若JJ，则必存在公式A，使得A是J的定理但不是J的定理，或者A是J的定理但不是J的定理。不失一般性，设公式A是J的定理但不是J的定理，根据J是完全扩张可知，A是J的定理。于是有

综上，原命题成立。

四. (20分) 设S1和S2是两个相容的一阶系统。试判断ThS1ThS2和ThS1ThS2是否一定是相容的，并证明你的结论。

解 ⑴ ThS1ThS2是相容的。事实上，由于S1相容且ThS1ThS2ThS1，故ThS1ThS2必然相容。

1

⑵ ThS1ThS2不一定相容。例如，对于一阶系统K，由于x1A1x1和x1A11x1都不是K的定理，因此，如果S1是1将x1A1x1作为K所得到的K的扩张，S2是将x1A11x1作为K的附加公理所得到的K的扩张，虽然S1和S2都是相容的，1但因为x1A1x1ThS1而x1A11x1ThS2，这时ThS1ThS2不相容。



J

A但

J

A。

五、（本题20分）设S是一阶系统，M是S的模型。令S是将所有在M下为真的的原子公式作为附加公理所得到的S的扩张。请回答下述问题并证明你的结论。

⑴ S是否一定是相容的？（8分） ⑵ S是否一定是完全的？（12分）

解 ⑴ 由于S的公理或者是S的公理，或者是在M为真的的原子公式，而M是S的模型，因此它必然也是S的模型。由于S存在模型，故S一定是相容的。

⑵ S未必是完全的。反例可以如下：

1

如果设是一个只包含一个谓词符号A11和一个个体常量符号a1的一阶语言。对于原子A1a，显然A11a和A11a都不是


专业班级： 学号： 姓名：

教务处试卷编号：

备注：1、试卷背面为演草区（不准用自带草纸） 装 订 线



1

恒真的，故A1a和A11a都不是K的定理。由于将A11a作为附加公理所得到的K的扩张是相容的，故不妨设M是这个11相容扩张的一个模型。显然，M是K的模型，但MA1a。于是，如果令SK，由于A1a在M下为假，故仍有SK。

这时S显然不是完全的。

六．（本题15分）使用归结方法证明下述公式G是公式F的逻辑结果：

F：xPxRx；

G：xyPyQx,yzQx,zRz。

具体给出推出空子句□归结反演过程，注明每一步归结的亲本子句和mgu,并画出最后的归结反演树。

解 将FG化成前束范式：

xPxRxxyPyQx,yzQx,zRz xPxRxxyPyQx,yzQx,zRz xyuzPuRuPyQx,yQx,zRz，









将xyuzPuRuPyQx,yQx,zRz进行Skolem范式化，得子句集



SPuRu,Pb,Qa,b,Qa,zRz，

于是，从S推出空子句□的归结演绎如下，最后的归结反演树如图所示。

⑴ PuRu ⑵ Pb











S中的子句 S中的子句

⑶ Qa,b ⑸ Rb

S中的子句 S中的子句

由⑴⑵，mgu为bu 由⑶⑷，mgu为bz 由⑸⑹，mgu为

⑷ Qa,zRz



















⑹ Rb ⑺ □





PuRu

mgubu

Pb

Qa,b Qa,zRz

mgubz

Rb Rb

mgu

□

第六题图

七. (10分) 试证明，存在一阶语言，使得K是不可判定的。

证明 假定T是一个Turing机，其符号表为B,1，状态集为q0,q1,令一阶语言

的个体常量符号集合为

,qn。令AB,1q0,q1,,qnq,q,h，将T转换

成为A上的字问题SA，则Turing机T对于输入停机当且仅当字hq0h和hqh等价。

AB,1q0,q1,,qnq,q,h，

函数符号只有f22，谓词符号只有A12（等词）。记f22xi,xj为xixj。在K的基础上加入以下附加公理：

⑴ A12x1x2x3,x1x2x3 ⑵ A12x1,x2A12x1x3,x2x3 ⑶ A12x1,x2A12x3x1,x3x2

⑷ 对SA中的关系集合中的每个ww，A12w,w ⑸ A12x1,x2A12x2,x3A12x1,x3 可以得到K的有穷扩张K，显然，



K

A12t1,t2当且仅当在SA中t1和t2等价。

试卷 第 2 页 共 3 页

本文来源：https://www.wddqxz.cn/a5daf7b849fe04a1b0717fd5360cba1aa8118cbb.html