12-13高等数理逻辑期末试卷（附答案）

2012-2013第一季度期末考试试题 一、填空题（30分，每空3分）

1.判断下列命题公式的类型

（1）?(p?q)?q为___矛盾式____ （2）((p?q)?p)?q为___重言式____ （3）(p?q)?q为___可满足式____

（4）?x(F(x)?G(X))?(?xF(x)??xG(x))为__可满足式_____ （5）(?xF(x)??xG(x))??x(F(x)?G(X))为____重言式___

2.设R为非空集合A上的关系，如果R是自反的、对称的和传递的，则称R为A上等价关系。如果R是__自反的、反对称的和传递的__，则称R为A上的偏序关系，简称偏序。记做?

3.凡是形式推演性所反映的前提和结论之间的关系，在非形式的推理中都是成立的。因此形式可推演性并不超出非形式推理的范围。这称为___可靠性___定理。 4.公式A中，原子公式出现的数目为n；?,?,?,?出现的总数是m，那么n和m的关系是___m=n-1_______。

5.??,?,??，??,??，??,??和??,??是联结符号完备集，这样看来，好像在联结符号的完备集中不能缺少否定符号，实际上并非如此。在我们讨论过的8个常用联结符号中，有___2____个联结符号单独具有完备性。 6.在第1题的5个公式中，有____4___个公式是协调的。

二、计算证明题（70分）

1.构造下面推理的证明。（10分） 前提：?(p??q)，?q?r，?r 结论：?p

2.证明Lp的公式的长度不能是2,3,或6，但其他的长度都是可能的。（10分） 3.写出公式(A?B)?[(?A?C)?(B?C)]的合取范式。（10分） 4.证明以下两道题目。（10分）

（1）(A?B)?C A?(B?C) （5分） （2）(A?C)?(B?C) (A?B)?C （5分）

5.证明：设?是极大协调集。那么，对于任何A，?A当且仅当A??。（10分） 6.设??Form(Lp)。证明存在唯一的真假赋值满足?，当且仅当对于任何A，?A和??A中恰好有一个成立。（10分）

7设?1??2是不可满足的公式集，其中的?1和?2是不空集。证明存在公式A，使得?1A，?2A。（10分）

2011-2012第一季度期末考试试题 一、填空题（30分，每空3分）

1.如果p是真，q是假，r是真，则

（a）?(p?q?r)?(?p??q??r)真值是_1______。 （b）(?p?q)?(?q?p)的真值是____1___。

2.如果个体域为自然数集合，A(x,y)表示x?y?y，B(x,y)表示xy?x，则 （a）?x?yA(x,y)的真值是____0___。 （b）?x?yB(x,y)的真值是___1____。

3.1和200之间不能被5或6，也不能被8整除的数的个数是__120_____。 4.设A?{0,1,2,3}，R是A上的关系，且有 R??0,0,0,3,2,0,2,2,2,3,3,2?，则 （a）R的自反闭包是___

R??0,0,0,3,2,0,2,2,2,3,3,21,1,3,3?______ R??0,0,0,3,3,02,0,0,22,2,2,3,3,2?_____ （b）R的对称闭包是____

5.讨论问题是在某个语言中进行的，如果所讨论的对象本身是语言，则要涉及两个不同层次的语言。被讨论的语言称为_对象语言__，比如形式语言。讨论问题时所用的语言称为__元语言____，比如自然语言汉语。 6.LP中的公式长度不能是（2,3或6），但其他长度是可能的。

二、计算证明题（70分）

1.在命题逻辑中，将下列命题符号化，或者写出推理的形式结构。（10分） （a）只有诚信参加考试，你才能得之坦然。

解：q?p,其中p：诚信参加考试，q：你得之坦然 （b）不经历风雨，不能见彩虹

解：?p??q，其中，p：经历风雨，q：见到彩虹

（c）如果中国队去南非参加世界杯，我就去南非。中国队没去南非参加世界杯，所以我没去南非。

解：((p?q)??p)??q，其中p：中国队去南非参加世界杯，q：我去南非 2.在一阶逻辑中，将下列命题符号化，或者写出推理的形式结构。（10分） （a）不存在正方形的足球。

解：?(?x(F(x)?G(x)))，其中F（x）：x是足球，G(x):x是正方形的 （b）有重因子的自然数全是正数。

解：?x(F(x)?G(x)?H(x))，其中F(x):x是自然数，G(x):x有重因子，H(x):x是正数

（c）凡人都是要死的。苏格拉底诗人，所以苏格拉底是要死的。

解：?x(F(x)?G(x))?F(a)?G(a)，其中，F(x):x是人，G(x):x是要死的，a：苏格拉底

3.设A?4，P(B)?32，P(A?B)?128，求 （a）A?B （b）A?B （c）|A?B| 解：因为P(B)?32，所以B?5 因为P(A?B)?128，所以A?B?7

A?B=A+B-A?B=3+5-7=1 A?B=A-A?B=3-1=2

|A?B|=A?B-A?B=7-1=6

4.证明{?,?}是全功能集。（10分）

证明：根据范式存在定理，在一命题公式都存在着与之等值的析取范式和合取范式，而范式里面只含有?,?,?，因此只需证明?可由{?,?}定义，就可以证明{?,?}是全功能集了。事实上，p?q??(?p??q)。这样就完成了证明。

?,?,?,?出现的总数是n，5. 公式A中，原子公式出现的数目为m；证明m=n+1.

（注意：同一个原子公式和?等都可以在A中有多次出现。）（10分） 证明：对公式的生成过程的结构做归纳证明即可。

6.判断并说明，对于怎样的n，含有n个A的公式??(?A?A??A)???A是重言式。（10分） 解：n=2k。

7.设?封闭于形式可推演性。证明?是极大可协调的，当且仅当对于任何A，?含并只含A和?A中之一。（10分）

证明：先证充分性。用反证法，假设?不是极大可协调的，那么又分别为两种情况：第一种，?是协调的，但不是极大协调的；第二种，?不是协调的。先说第一种，存在公式A??，使得??{A}也是协调的。那么?A??，这样就有

??{A}A并且??{A}?A，矛盾。再说第二种，存在公司A，使得?A并

且??A，由于?封闭于形式可推演性，就有?同时含有A和?A，矛盾。

再证必要性 也用反证法。假设不是对于任何A，?含并且只含A和?A中之一，那么又分两种情况：第一种，存在A，?不含A也不含?A；第二种：?同时含有A和?A。先说第一种，因为?是协调的，那么?成立，不妨设?A和??A至少有一个不

?A，从而

A并且

?A不成立，那么??{A}A并且没有??{A}??{A}也是协调的，这与?是极大协调的相矛盾。第二种，就有???A，与?是协调的相矛盾。

本文来源：https://www.bwwdw.com/article/rqa2.html