12-13高等数理逻辑期末试卷(附答案)
更新时间:2023-11-04 23:32:01 阅读量: 综合文库 文档下载
- 中山大学数理逻辑期末试卷推荐度:
- 相关推荐
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,与?是协调的相矛盾。
正在阅读:
12-13高等数理逻辑期末试卷(附答案)11-04
离心脱水机操作保养规程04-22
七年级语文第三次月考试卷01-07
单自由度体系列运动方程习题11-19
2013-2014年宁夏海原关桥中学九年级数学第三次模拟试卷06-14
uv平板打印机喷头维修方法及费用04-06
观科普知识讲座有感04-06
第5讲不等式与线性规划(学生)04-09
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 数理逻辑
- 期末
- 试卷
- 高等
- 答案
- 12
- 13