交大数理逻辑课件数理逻辑和集合论复习提纲.ppt

数理逻辑与集合论,复习提纲,第1章 命题逻辑的基本概念,1.1 命题1.2 命题联结词及真值表1.3 合式公式1.4 重言式（三类公式的关系：P8）1.5 命题形式化1.6 波兰表达式,第2章 命题逻辑的等值和推理演算,2.1 等值定理2.2 等值公式2.4 联结词的完备集PQ=(PQ)，PQ=(PQ)2.5 对偶式2.6 范式2.7 推理形式（重言蕴涵的几个结果：P31）2.8 基本的推理公式（(1)-(11):P31）2.9 推理演算2.10 归结推理法,会运用等值式证明两个公式是否相等、判断公式的类型,求命题公式的对偶式、(主)析取范式、(主)合取范式及用途,常用推理规则、直接证明法、附加前提证明法、归结法,第4章 谓词逻辑的基本概念,4.1 谓词和个体词4.2 函数和谓词4.3 合式公式（合法性判断）4.4 自然语句的形式化（与作业结合复习）4.5 有限域下公式(x)P(x)、(x)P(x)的表示法在1,2上的量化公式、解释,谓词的定义，谓词逻辑与命题逻辑的关系,自由变元、约束变元及量词的辖域,第5章 谓词逻辑的等值和推理演算,5.1 否定型等值式（证明）5.2 量词分配等值式（证明）5.4 基本的推理公式(证明方法，(1)-(10):P77-78)5.5 推理演算(UI,EI,UG,EG和命题推理规则)5.6 谓词逻辑的归结推理法,量词否定等值式、量词辖域收缩和扩张等值式、量词分配等值式、消去量词等值式,第9章 集 合,9.1 集合的概念和表示方法9.2 集合间的关系和特殊集合9.3 集合的运算9.4 集合的图形表示法9.5 集合运算的性质和证明不包括)9.6 有限集合的基数包含排斥原理及应用（作业）,会运用集合运算的性质证明有关集合运算的命题成立与否、进行化简，定理证明主要在，而只要记住结论,第10章 关 系,10.1 二元关系重要关系(、E、I、L、D、)10.2 关系矩阵和关系图10.3 关系的逆、合成、限制和象10.4 关系的性质(性质判断和证明)10.5 关系的闭包10.6 等价关系和划分(会求商集、类、划分并会证明)10.7 相容关系和覆盖(会求类并会证明)10.8 偏序关系(会画哈斯图，求特殊元素),对称闭包、自反闭包和传递闭包的定义和构造方法,第11章 函 数,11.1 函数11.2 函数的合成和函数的逆,第12章 集合的基数,12.2 集合的等势12.3 有限集合与无限集合12.4 集合的基数,试题结构,卷面一.选择题（10%）二.填空题（20%）三.判断题（10%）四.运算题（20%）五.证明题（20%）六.应用题（20%）,各章内容比例第一、二章 命题逻辑(20%)第四、五章 谓词逻辑(20%)第九章 集合(20%)第十章 关系(25%)第十一章 函数(10%)第十二章 集合的基数(5%),数理逻辑试题样卷,一.选择题（10%）1设S、T、M为任意集合，则下列命题中，命题真值是真的是。A 是的子集B.若ST=，则S=T C若ST=E，则ST D.若ST=SM，则T=M二.填空题：（20%）1、公式(pq)r 的成真赋值是_,数理逻辑试题样卷,四.运算题：（20%）1.用等值演算法判断公式q(pq)的类型 解 q(pq)q(pq)（蕴涵等值式）q(pq)（德摩根律）p(qq)（交换律，结合律）p0（矛盾律）0（零律）由最后一步可知，该式为矛盾式.2.计算集合A=，的幂集解：P(A)=P(,)=,数理逻辑试题样卷,三.判断题（10%）设S、T为任意集合，若ST=，则S=T。（）五.证明题（20%）证明 A=B C=D AC=BD 证：任取 AC xA yC xB yD BD,数理逻辑试题样卷,六.应用题：（20%）证明苏格拉底三段论:“人都是要死的,苏格拉底是人，所以苏格拉底是要死的.”令 F(x):x是人,G(x):x是要死的,a:苏格拉底 前提：x(F(x)G(x)，F(a)结论：G(a)证明：F(a)前提引入 x(F(x)G(x)前提引入 F(a)G(a)UI G(a)假言推理,考试和答疑安排,考试时间：18周星期五(12月31日)，8:00-10:00AM考试地点：340402答疑安排：18周星期三(12月29日)，3:00-5:00答疑地点：31号楼3楼教师休息室,数理逻辑样卷,一、单选题（共10分）1下列命题公式中，是重言式的是_。A(p q)q B.(p q)(p q)C.pq D.p q2设A、B、C、D为任意集合，下面命题为真的是_。AA(BC)(AB)(AC)B.若AB，则有A BC.(AB)=AB D.(A B)=A B,3在关于二元关系性质的叙述中，正确的是_。A.若关系R、S具有自反性，则RS一定有自反性；B.存在既是对称的也是反对称的关系C.若R、S是传递的，则RS也是传递的；D.若R、S是自反的，则RS也是自反的。4含有3个元素的集合共有_种不同的划分.A.4 B.10 C.5 D.65设A、B为任意集合，下面命题为真的是_。AP(A)P(B)=P(AB)B.P(AB)=P(A)P(B)P(A-B)=P(A)-P(B)若A-B=，则B A,数理逻辑样卷,8下列一阶谓词公式中，是逻辑有效式的是_。x(F(x)G(x)xF(x)xF(x)C.(F(x,y)R(x,y)R(x,y)D.xyF(x,y)xyF(x,y)9设 f：BC,g：AB.则下面命题是错误的是_。A.若 fg是满射.则f 是满射的 B.若 fg是单射.则g是单射的 C.若 fg是双射.则f 是单射的，g 是满射的。D.若 fg是双射.则 g是单射的，f 是满射的。10下列关系的性质中，等价关系不具备的是_。A自反的 B.反对称的 C.传递的 D.对称的,6设A、B是集合，右图的文氏图的阴影部分的区域可用_表达式表示A.AB B.AB A-B D.(AB)-(AB)7集合A和B定义如下，则它们之间满足_关系。A=x|xRx2+x-2=0,B=y|yQy2+y-2=0 AA=B BBA CAB DAB,数理逻辑样卷,二、填空题（共20分）1设p、q的真值为0；r的真值为1，则命题公式：p(qr)的真值是_。2设论域为1,2，一元谓词定义为F(x):x2,G(x):x=0，则(x)(F(x)G(x)的真值为_。3设P(x)：x是正整数，Q(x)：x是偶数，R(x)：x是奇数，则公式：(x)(P(x)(Q(x)R(x)翻译成自然语句为:_。4设A=a,b,c，则A的全部子集共有_个，A的幂集P(A)共有_个元素。5在偏序关系的哈斯图中，最大元素是_，极小元素是_。,数理逻辑样卷,二、填空题（共20分）6两个集合A和B相等(A=B)用谓词形式可定义为：_。7已知集合C定义为：C=x|x Z 3x6，则集合C中的元素为：C=_。8.若|A|=n，则A上共有_ 个不同的具有自反性的二元关系。9用联系词表示公式 P Q_。10对集合A1,2,3，R是A上的关系，如 右图所示，列出它所具有的性质：_。,数理逻辑样卷,三判断题（10分）1对非空集合A上的关系R，若R是自反的，则s(R)是自反的。（）2对A上的关系R1和R2，若R1和R2是自反的，则R1R2也是自反的。（）3对任意的集合A、B，若 P(A)P(B)，则 AB（）4集合A上的等价关系与划分是一一对应的。（）5集合的最小元就是它的极小元；（）6已知：f(x)=2x+1，则f 既不是单射也不是满射。（）7若关系R是等价关系，则它必是相容关系。（）8实数R与自然数N是不等势的。（）9任给二元函数f,它的逆f 1一定是二元函数关系。（）10对公式A和B，若AB永真，必有A-B-也永真。（）,数理逻辑样卷,四运算题（20分）1求命题公式：(PQ)R 的主析取范式和成真赋值。2.已知A=1,2,3，B=1,4，求AB、A-B、AB和P(AB)。3.设A=a,b,c,d，R=,，求R的自反闭包r(R)、对称闭包s(R)和传递闭包t(R)。4.设f,g,h均为R-R的函数，f(x)=x+3,g(x)=2x+1,h(x)=x/2,求gf,gh,gfh,数理逻辑样卷,五证明题（共20分）1用等值演算法证明等值式：PQ=P(P Q)2.设q为命题变项，与个体变元x无关，证明：(x)(P(x)q)=(x)P(x)q3.设 A=1,2,3,4,5,6,7,8,A上的关系 R如下定义：R=|x,yAxy(mod 3)证明：R是一个等价关系。4使用推理规则证明：P(QR)，SP,Q S R,数理逻辑样卷,六应用题（共20分）1.甲、乙、丙、丁四人参加考试，有人问他们，谁的成绩最好，甲说：“不是我”,乙说：“是丁”,丙说：“是乙”,丁说：“不是我”.四人的回答只有一人符合实际，问是谁的成绩最好，若只有一人成绩最好，他是谁？2符号化下面命题，并用谓词逻辑构造其推证结论的过程：乌鸦都不是白色的.北京鸭是白色的.因此，北京鸭不是乌鸦.3求1到1000之间（包含1和1000在内）既不能被 5 和6 整除，也不能被 8 整除的数有多少个？4.设 A=1,2,3，求出A上所有的等价关系,