资源描述：
《12-13高等数理逻辑期末试卷(附答案)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、2012-2013第一季度期末考试试题一、填空题(30分，每空3分)1•判断下列命题公式的类型(1)-i(pTq)人q为—矛盾式一(2)((〃Tg)人〃)Tg为重言式(3)(pTq)八q为可满足式(4)V%(F(x)vG(X))t(VxF(x)vVxG(x))为一可满足式一(5)(VxF(^)vVxG(x))TVx(F(^)vG(X))为重言式2.设R为非空集合A上的关系，如果R是自反的、对称的和传递的，则称R为A上等价关系。如果R是「自反的、反对称的和传递的—,则称R为A上的偏序关系，简称偏序。记做S3.凡是形式推演性所反映的前提和结论之间的关系，
2、在非形式的推理中都是成立的。因此形式可推演性并不超出非形式推理的范围。这称为一可靠炸一定理。4.公式A中，原子公式出现的数目为n；zm出现的总数是m,那么n和m的关系是m二ml。5，h，A,v},{-"和{「,t}是联结符号完备集，这样看来，好像在联结符号的完备集中不能缺少否定符号，实际上并非如此。在我们讨论过的8个常用联结符号中，有2个联结符号单独具有完备性。6.在第1题的5个公式中，有4个公式是协调的。二、计算证明题(70分)1.构造下面推理的证明。(10分)刖提：—1(/2A—1^),—C{vr,—if结论：-ip2•证明厶"的公式的长度不能
3、是2,3,或6,但其他的长度都是可能的。(10分)3•写出公式(A㈠B)㈠tC)t(BtC)］的合取范式。(10分)4.证明以下两道题目。(10分)(1)(A^B)<-^C㈠C)(5分)(2)(AtC)v(BtC)(AvB)^C(5分)5•证明：设工是极大协调集。那么，对于任何A,ZA当且仅当AgZo(10分)6.设三wFonn(Lp)。证明存在唯一的真假赋值满足工，当U仅当对于任何A,ZA和刀「A中恰好有一个成立。(10分)7设Z.uZ,是不可满足的公式集，其中的纭和工2是不空集。证明存在公式A,使得乙A,Z2Ao(10分)2011-2012第一季
4、度期末考试试题一、填空题(30分，每空3分)1.如果是真，q是假，尸是真，贝lj(a)-1(〃vgv厂)(-1〃人一«q人一1厂)真值是。(b)(—1#—>q)T(―vp)的真值是o2.如果个体域为自然数集合，A(x,y)表示=Bgy)表示厂=兀，贝lj(a)Vx3yA(x,y)的真值是0。(b)y)的貢-值是1o3.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的自反闭包是尺二｛〈0,0〉,
5、〈0,3〉,〈2,0〉,〈2,2〉,(2,3〉,〈3,2〉〈1,1〉,〈3,3〉｝(b)R的对称闭包是只二｛〈0,0〉,〈0,3〉,〈3,0〉〈2,0〉,〈0,2〉〈2,2〉,〈2,3),〈3,2〉｝5.讨论问题是在某个语言中进行的，如果所讨论的对象本身是语言，则耍涉及两个不同层次的语言。被讨论的语言称为一对象语言,比如形式语言。讨论问题时所用的语言称为一元语言一，比如自然语言汉语。6.广中的公式长度不能是(2,3或6),但其他长度是可能的。二、计算证明题(70分)1•在命题逻辑中，将下列命题符号化，或者写出推理的形式结构。(10分)(a)只有诚信参
6、加考试，你才能得之坦然。解：qfp、其中p：诚信参加考试，q：你得之坦然(b)不经历风雨，不能见彩虹解：-ip,其屮，p：经历风雨，q：见到彩虹(C)如果中国队去南非参加世界杯，我就去南非。中国队没去南非参加世界杯,所以我没去南非。解：((〃Tg)人T-iq,其中p：中国队去南非参加世界杯，q：我去南非1.在一阶逻辑屮，将下列命题符号化，或者写岀推理的形式结构。(10分)(a)不存在正方形的足球。解：-i(3%(F(x)aG(x))),其中F(x)：x是足球,G(x):x是正方形的(b)有重因子的自然数全是正数。解：Vx(F(x)aG(x)W(x))
7、,其中F(x):x是自然数,G(x):x有重因子,H(x):x是正数(c)凡人都是要死的。苏格拉底诗人，所以苏格拉底是要死的。解：X/兀(F(x)TGCr))AF(d)TG(a),其中，F(x):x是人，G(x):x是要死的，a：苏格拉底2.设
8、A
9、=4,
10、P(B)
11、=32,
12、P(AuB)
13、=128,求(a)AnB(b)A-B(c)A®B解:因为
14、P(B)
15、=32,所以网=5因为
16、P(AuB)
17、=128,所以
18、AuB
19、=7AnB
20、=
21、A
22、+
23、B
24、-
25、AoB
26、=3+5-7=lA-B=
27、/l
28、-
29、y4nB=3-1=2A®fi
30、=
31、AoB
32、-
33、
34、AnB
35、=7-1=63.证明｛「，人｝是全功能集。(10分)证明：根据范式存在定理，在一命题公式都存在着与
