交大数理逻辑课件数理逻辑和集合论复习提纲.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.5.3不包括)9.6有限集合的基数包含排斥原理及应用（作业）,会运用集合运算的性质证明有关集合运算的命题成立与否、进行化简，定理证明主要在9.5.1，9.5.4，而9.5.2只要记住结论,第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=TC若ST=E，则STD.若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=BC=DAC=BD证：任取ACxAyCxByDBD,数理逻辑试题样卷,六.应用题：（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)UIG(a)假言推理,考试和答疑安排,考试时间：18周星期五(12月31日)，8:00-10:00AM考试地点：340402答疑安排：18周星期三(12月29日)，3:00-5:00答疑地点：31号楼3楼教师休息室,数理逻辑样卷,一、单选题（共10分）1下列命题公式中，是重言式的是_。A(pq)qB.(pq)(pq)C.pqD.pq2设A、B、C、D为任意集合，下面命题为真的是_。AA(BC)(AB)(AC)B.若AB，则有ABC.(AB)=ABD.(AB)=AB,3在关于二元关系性质的叙述中，正确的是_。A.若关系R、S具有自反性，则RS一定有自反性；B.存在既是对称的也是反对称的关系C.若R、S是传递的，则RS也是传递的；D.若R、S是自反的，则RS也是自反的。4含有3个元素的集合共有_种不同的划分.A.4B.10C.5D.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=，则BA,数理逻辑样卷,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.ABB.ABA-BD.(AB)-(AB)7集合A和B定义如下，则它们之间满足_关系。A=x|xRx2+x-2=0,B=y|yQy2+y-2=0AA=BBBACABDAB,数理逻辑样卷,二、填空题（共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|xZ3x6，则集合C中的元素为：C=_。8.若|A|=n，则A上共有_个不同的具有自反性的二元关系。9用联系词表示公式PQ_。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,它的逆f1一定是二元函数关系。（）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(PQ)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(mod3)证明：R是一个等价关系。4使用推理规则证明：P(QR)，SP,QSR,数理逻辑样卷,六应用题（共20分）1.甲、乙、丙、丁四人参加考试，有人问他们，谁的成绩最好，甲说：“不是我”,乙说：