离散数学复习(精品)

单击此处编辑母版标题样式,*,1,各章核心内容,数理逻辑部分,深刻理解各联结词的逻辑关系,熟练地将命题符号化,会求复合命题的真值,深刻理解合式公式及重言式、矛盾式、可满足式等概念,熟练地求公式的真值表，并用它求公式的成真赋值与成假赋值及判断公式类型,深刻理解等值式的概念,牢记基本等值式的名称及它们的内容,2,熟练地应用基本等值式及置换规则进行等值演算,理解文字、简单析取式、简单合取式、析取范式、合取范式的概念,深刻理解极小项、极大项的概念、名称及下角标与成真、成假赋值的关系，并理解简单析取式与极小项的关系,3,熟练掌握求主范式的方法（等值演算、真值表等）,会用主范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等值,会将公式等值地化成指定联结词完备集中的公式,会用命题逻辑的概念及运算解决简单的应用问题,掌握消解规则及其性质,会用消解算法判断公式的可满足性,理解并记住推理形式结构的两种形式：,(,A,1,A,2,Ak,),B,前提：,A,1,A,2,Ak,结论：,B,4,熟练掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等）,牢记,P,系统中各条推理规则,熟练掌握构造证明的直接证明法、附加前提证明法和归谬 法,会解决实际中的简单推理问题,准确地将给定命题符号化,理解一阶语言的概念,深刻理解一阶语言的解释,熟练地给出公式的解释,记住闭式的性质并能应用它,5,深刻理解永真式、矛盾式、可满足式的概念,会判断简,单公式的类型,深刻理解并牢记一阶逻辑中的重要等值式,并能准确而熟练地应用它们,熟练正确地使用置换规则、换名规则、代替规则,熟练地求出给定公式的前束范式,深刻理解自然推理系统,NL,的定义，牢记,NL,中的各条推理规则，特别是注意使用,、,+,、,+,、,4,条推理规则的条件,能正确地给出有效推理的证明,6,练习题：,1,、,38,页,3,，,7,2,、,65,页,2,，,6,3,、,66,页,10,4,、,79,页,3,，,5,，,7,5,、,80,页,12,，,15,，,17,6,、,81,页,19,7,、,81,页的,2025,再检查一遍作业，如果没做就再做一遍。,7,练习题,1,、已知公式,A,含,n,个命题变元,p,1,p,2,p,n,并且无成假赋值，求,A,的主合取范式。,解：该公式是永真式，没有主合取范式，,2,n,个极小项均出现在其主析取范式中。,2,、判断下列公式的属性：,(p,q),r,p,(p,q r,),8,(1),解：通过求主范式的方法来判定。,(p,q),r=(p,q,r,),(p,q,r,),(p,r,)(p,r,),=,(p,q,r,),(p,q,r,),(p,q,r,),(p,q,r,),(p q,r,)(p q,r,),=M,0,M,1,M,2,M,4,M,6,该公式是可满足的,(2)p,(p,q r,)=,p p q r=T,该公式是永真式，含有,p p,因子，所以其主析取范式为：,m,0,m,1,m,2,m,3,m,4,m,5,m,6,m,7,其中代表析取。,9,3,、指出下列公式的指导变元，量词的辖域，各个变元的自由出现和约束出现，并求它们的前束范式。,(1),x(F(x)G(x,y),(2)xF(x,y)yG(x,y),解,(1):x,是指导变元，量词的辖域是,(F(x)G(x,y),，,x,有两处约束出现，,y,是自由变元，有一次自由出现，它已经是前束范式,解,(2),先求其前束范式,xF(x,y)yG(x,y)=xF(x,z)yG(u,y),=x y(F(x,z)G(u,y),于是,x,y,是指导变元,并且,x,y,是约束的，它们的辖域是,(F(x,z)G(u,y),；,u,z,是自由的。,10,4,、设个体域是,a,b,消去下式的量词：,xF(x)yG(y),解,:,首先将其变成前束范式,xF(x)yG(y)=(xF(x)y G(y),=(x F(x)y G(y),=x y(F(x)G(y),=,y,(F(a)G(y)y,(F(b)G(y),=(F(a)G(a)(F(a)G(b),(F(b)G(a),(F(b)G(b),11,5,、首先将下列命题符号化然后推证其结论。,(1),所有的自然数都是整数，任何整数不是奇数就是偶数，并非每个自然数都是偶数，所以，某些自然数是奇数。,解：首先定义谓词如下：,N(x):x,是自然数，,I(x):x,是整数，,E(x):x,是偶数,Q(x):x,是奇数，于是问题可描述成：,x(N(x)I(x),x(I(x)(Q(x)E(x),x(N(x)E(x)x(N(x)Q(x).,12,推理证明过程如下：,注意首先检查有没有带存在量词的前提，如果有首先对其使用,P,规则。,1,、,x(N(x)E(x)P,规则,2,、,x(N(x)E(x)T,规则和,1,3,、,x(N(x)E(x)T,规则和,2,4,、,N(a)E(a)ES,规则和,3,5,、,N(a)T,规则和,4,6,、,E(a)T,规则和,4,7,、,x(N(x)I(x)P,规则,8,、,N(a)I(a)US,规则和,7,9,、,I(a)T,规则,5,和,8,13,10,、,x(I(x)(Q(x)E(x)P,规则,11,、,I(a)(Q(a)E(a)US,规则和,10,12,、,Q(a)E(a)T,规则,9,和,11,13,、,Q(a)T,规则,6,和,12,14,、,N(a)Q(a)T,规则,5,和,13,15,、,x(N(x)Q(x)EG,规则和,14,问题得证。,请大家看第,5,章课件关于这方面的最后练习。,14,集合理论部分,熟练掌握集合的基本运算（普通运算和广义运算）,掌握证明集合等式或者包含关系的基本方法,熟练掌握关系的三种表示法,能够判定关系的性质（等价关系或偏序关系）,掌握含有关系运算的集合等式,掌握等价关系、等价类、商集、划分、哈斯图、偏序集等概念,计算,A,B,dom,R,ran,R,fld,R,R,1,R,S,R,n,r,(,R,),s,(,R,),t,(,R,),15,集合理论部分,求等价类和商集,A,/,R,给定,A,的划分,，求出,所对应的等价关系,求偏序集中的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界,掌握基本的证明方法,证明涉及关系运算的集合等式,证明关系的性质、证明关系是等价关系或偏序关系,给定,f,A,B,判别,f,是否为从,A,到,B,的函数,判别函数,f,:,A,B,的性质（单射、满射、双射）,16,熟练计算函数的值、像、复合以及反函数,证明函数,f,:,A,B,的性质（单射、满射、双射）,给定集合,A,B,，构造双射函数,f,:,A,B,能够证明两个集合等势,能够证明一个集合优势于另一个集合,知道什么是可数集与不可数集,会求一个简单集合的基数,17,复习及练习,练习题：,1,、,100,页,32,，,101,页,45,2,、,130,页,6,，,131,页,10,，,11,，,12,，,13,，,14,3,、,132,页,22,4,、,133,页,25,，,34,，,35,5,、,134,页,38,，,39,，,40,，,6,、,135,页,48,7,、,161,页,5,，,7,8,、,162,页,11,，,18,，,19,9,、,164,页,29,18,练习题,1,、判断书上,132,页,23,题中所有图的性质：,解,:(a):,是自反的，不对称的，不可传递的。,(b):,不自反的，反对称的，可传递的,(c):,自反的，对称的，可传递的。,(d):,自反的，不地称的，可传递的,(e):,不自反的，不对称的，不可传递的,(f):,不自反的，对称的，不可传递的,(g):,自反的，反对称的，不可传递的,(h):,自反的，对称的，不可传递的,(i):,不自反的，对称的，不可传递的,(j):,不自反的，反对称的，不可传递的,(k):,自反的，反对称的，可传递的,(l):,不自反的，反对称的，不可传递的。,19,2,、设,A=1,，,2,，,3,，,4,，在,AXA,上定义二元关系,R,为,u,v,x,yAXA,u,vRx,yu+y=x+v,证明,R,是,AXA,上的等价关系并确定由,R,引起的,AXA,的划分。,解：,R,是自反的：因为,x,yRx,yx+y=x+y,R,是对称的：因为,u,vRx,y,时一定有,x,yR u,v,；,R,是可传递的：假设,x,yRu,v,和,u,v R l,m,我们来证,x,yRl,m,因为,x+v=y+u,及,u+m=v+l,两式两边相加得,x+v+u+m=y+u+v+l,整理得,x+m=y+l,问题得证。即,R,是等价关系。,20,现在来求由此等价关系导致的划分：为此先求,AXA,AXA=,1,1,1,2,1,3,1,4,2,1,2,2,2,3,2,4,3,1,3,2,3,3,3,4,4,1,4,2,4,3,4,4,C=,1,1,2,2,3,3,4,4,1,2,2,3,3,4,2,1,3,2,4,3,1,3,2,4,3,1,4,2,1,4,4,1,21,3,、,设,A,R,和,B,S,为偏序集，在集合,AXB,上定义关系,T,如下：,a,1,b,1,a,2,b,2,AXB,a,1,b,1,Ta,2,b,2,a,1,Ra,2,b,1,Sb,2,证明,T,是偏序关系。,解：只要证,T,是自反的，反对称的和可传递的即可。,显然对任何,a,i,b,i,AXB,有,a,i,Ra,i,b,i,Sb,i,因为,R,和,S,都是偏序关系，是自反的，所以,a,i,b,i,T a,i,b,i,即,T,是自反的。,对任意,a,1,b,1,a,2,b,2,AXB,若,a,1,b,1,Ta,2,b,2,a,2,b,2,T a,1,b,1,a,1,Ra,2,b,1,Sb,2,a,2,Ra,1,b,2,Sb,1,(a,1,Ra,2,a,2,Ra,1,)(b,1,Sb,2,b,2,Sb,1,)a,1,=a,2,b,1,=b,2,即,a,1,b,1,=a,2,b,2,于是,T,是反对称的,22,再来证,T,是可传递的。,对任意,a,1,b,1,a,2,b,2,，,a,3,b,3,AXB,若,a,1,b,1,Ta,2,b,2,a,2,b,2,T a,3,b,3,a,1,Ra,2,b,1,Sb,2,a,2,Ra,3,b,2,Sb,3,（,a,1,Ra,2,a,2,Ra,3,）,(b,1,Sb,2,b,2,Sb,3,),a,1,Ra,3,b,1,Sb,3,即,a,1,b,1,T a,3,b,3,综上,T,是,AXA,上的偏序关系。,23,4,、设,R,是,NXN,上二元关系，对任意的,a,b,c,dNXN,a,bRc,d b=d,证明,R,是,NXN,上的等价关系，并求出其商集,NXN/R,解：我们只来求,NXN/R,，为此先来求,NXN,NXN=0,1,2,n,.X0,1,2,n,.,=0,0,0,1,0,n,1,0,1,1,1,n,2,0,2,1,2,n,n,0,n,1,n,n,于是很明显的可以看出每一列是一个等价类，于是商集为以列为元素的集合。,24,5,、,给定,T,12,上的整除关系,D,，试证明,D,是偏序关系，画出,D,的哈斯图。,T,12,是,12,的因子的集合。,解：整除关系是自反的，反对称的，可传递的，它是偏序关系，我们只画它的哈斯图,12,的因子,=1,，,2,，,3,，,4,，,6,，,12,12,6 4,3 2,1,25,5,、下图给出了偏序集,P,，,R,的哈斯图，其中,P=x,1,x,2,x,3,x,4,x,5,(1),下列关系中哪一个是真的？,x,1,Rx,2,，,x,4,Rx,1,，,x,3,Rx,5,，,x,2,Rx,5,，,x,1,Rx,1,，,x,2,Rx,3,，,x,4,Rx,5,(2),求出,P,中的最大元、最小元，极大元、极小元，如果存在的话。,(3),求出子集,x,2,x,3,x,4,，,x,3,x,4,x,5,，,x,1,x,2,x,3,的上界、下界和