《离散数学复习》PPT课件.ppt

1,各章核心内容,数理逻辑部分深刻理解各联结词的逻辑关系,熟练地将命题符号化会求复合命题的真值深刻理解合式公式及重言式、矛盾式、可满足式等概念熟练地求公式的真值表，并用它求公式的成真赋值与成假赋值及判断公式类型深刻理解等值式的概念牢记基本等值式的名称及它们的内容,2,熟练地应用基本等值式及置换规则进行等值演算理解文字、简单析取式、简单合取式、析取范式、合取范式的概念深刻理解极小项、极大项的概念、名称及下角标与成真、成假赋值的关系，并理解简单析取式与极小项的关系,3,熟练掌握求主范式的方法（等值演算、真值表等）会用主范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等值会将公式等值地化成指定联结词完备集中的公式会用命题逻辑的概念及运算解决简单的应用问题掌握消解规则及其性质会用消解算法判断公式的可满足性理解并记住推理形式结构的两种形式：(A1A2Ak)B 前提：A1,A2,Ak 结论：B,4,熟练掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等）牢记 P 系统中各条推理规则熟练掌握构造证明的直接证明法、附加前提证明法和归谬 法会解决实际中的简单推理问题准确地将给定命题符号化理解一阶语言的概念深刻理解一阶语言的解释熟练地给出公式的解释记住闭式的性质并能应用它,5,深刻理解永真式、矛盾式、可满足式的概念,会判断简单公式的类型深刻理解并牢记一阶逻辑中的重要等值式,并能准确而熟练地应用它们熟练正确地使用置换规则、换名规则、代替规则熟练地求出给定公式的前束范式深刻理解自然推理系统NL 的定义，牢记NL 中的各条推理规则，特别是注意使用、+、+、4条推理规则的条件能正确地给出有效推理的证明,6,练习题：1、38页3，72、65页2，63、66页104、79页3，5，75、80页12，15，176、81页197、81页的2025再检查一遍作业，如果没做就再做一遍。,7,练习题,1、已知公式A含n个命题变元p1,p2,pn,并且无成假赋值，求A的主合取范式。解：该公式是永真式，没有主合取范式，2n个极小项均出现在其主析取范式中。2、判断下列公式的属性：(pq)r p(p q r),8,(1)解：通过求主范式的方法来判定。(pq)r=(pq r)(pq r)(p r)(p r)=(pq r)(pq r)(pq r)(p q r)(p q r)(p q r)=M0M1M2M4M6该公式是可满足的(2)p(p q r)=p p q r=T该公式是永真式，含有p p 因子，所以其主析取范式为：m0m1m2m3m4m5m6m7其中代表析取。,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规则和13、x(N(x)E(x)T规则和24、N(a)E(a)ES规则和35、N(a)T规则和4 6、E(a)T规则和47、x(N(x)I(x)P规则 8、N(a)I(a)US规则和79、I(a)T规则5和8,13,10、x(I(x)(Q(x)E(x)P规则11、I(a)(Q(a)E(a)US规则和1012、Q(a)E(a)T规则9和1113、Q(a)T规则6和1214、N(a)Q(a)T规则5和1315、x(N(x)Q(x)EG规则和14问题得证。请大家看第5章课件关于这方面的最后练习。,14,集合理论部分,熟练掌握集合的基本运算（普通运算和广义运算）掌握证明集合等式或者包含关系的基本方法熟练掌握关系的三种表示法 能够判定关系的性质（等价关系或偏序关系）掌握含有关系运算的集合等式掌握等价关系、等价类、商集、划分、哈斯图、偏序集等概念计算AB,dom R,ranR,fldR,R1,RS,Rn,r(R),s(R),t(R),15,集合理论部分,求等价类和商集A/R 给定A的划分，求出 所对应的等价关系求偏序集中的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界掌握基本的证明方法证明涉及关系运算的集合等式证明关系的性质、证明关系是等价关系或偏序关系给定 f,A,B,判别 f 是否为从A到B的函数判别函数 f:AB的性质（单射、满射、双射）,16,熟练计算函数的值、像、复合以及反函数证明函数 f:AB的性质（单射、满射、双射）给定集合A,B，构造双射函数 f:AB 能够证明两个集合等势能够证明一个集合优势于另一个集合知道什么是可数集与不可数集会求一个简单集合的基数,17,复习及练习,练习题：1、100页32，101页452、130页6，131页10，11，12，13，143、132页224、133页25，34，355、134页38，39，40，6、135页487、161页5，78、162页11，18，199、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+yR是对称的：因为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,现在来求由此等价关系导致的划分：为此先求AXAAXA=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,4C=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如下：a1,b1,a2,b2AXB a1,b1Ta2,b2 a1Ra2 b1Sb2证明T是偏序关系。解：只要证T是自反的，反对称的和可传递的即可。显然对任何 ai,bi AXB有aiRai biSbi因为R和S都是偏序关系，是自反的，所以 ai,bi T ai,bi 即T是自反的。对任意a1,b1,a2,b2AXB若a1,b1Ta2,b2 a2,b2T a1,b1a1Ra2 b1Sb2 a2Ra1 b2Sb1(a1Ra2 a2Ra1)(b1Sb2 b2Sb1)a1=a2 b1=b2即a1,b1=a2,b2于是T是反对称的,22,再来证T是可传递的。对任意a1,b1,a2,b2，a3,b3AXB若a1,b1Ta2,b2 a2,b2T a3,b3a1Ra2 b1Sb2 a2Ra3 b2Sb3（a1Ra2 a2Ra3）(b1Sb2 b2Sb3)a1Ra3 b1Sb3即a1,b1T a3,b3综上T是AXA上的偏序关系。,23,4、设R是NXN上二元关系，对任意的a,b,c,dNXN,a,bRc,d b=d证明R是NXN上的等价关系，并求出其商集NXN/R解：我们只来求NXN/R，为此先来求NXNNXN=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、给定T12上的整除关系D，试证明D是偏序关系，画出D的哈斯图。T12是12的因子的集合。解：整除关系是自反的，反对称的，可传递的，它是偏序关系，我们只画它的哈斯图12的因子=1，2，3，4，6，12 12 6 4 3 2 1,25,5、下图给出了偏序集P，R的哈斯图，其中P=x1,x2,x3,x4,x5(1)下列关系中哪一个是真的？x1Rx2，x4Rx1，x3Rx5，x2Rx5，x1Rx1，x2Rx3，x4Rx5(2)求出P中的最大元、最小元，极大元、极小元，如果存在的话。(3)求出子集x2,x3,x4，x3,x4,x5，x1,x2,x3的上界、下界和上下确界如果它们存在的话。x1 x2 x3 x4 x5,26,解：这道题主要是注意哈斯图的画法，是下面的元素和上面的元素有偏序关系，还有偏序关系的性质，自反、反对称，可传递。及子集的极大、极小、最大、最小元是在子集里找，而上下界及上下确界均是在P上找。(1)中的答案顺序为：F，T，F，F，T，F，F(2)P中有极大元也是最大元为x1,没有最小元，极小元是X4,x5(3)x2,x3,x4的上界是x1也是上确界，下界是x4也是下确界x3,x4,x5的上界是x3和x1，x3还是上确界，没有下界和下确界x1,x2,x3 的上界和上确界是x1，下界和下确界是x4,27,6、关系图中行上1的个数和列上1的个数所代表的含义是什麽？解：行上1的个数代表对应结点的出度，列上1的个数代表对应结点的入度。7、设f和g是ZZ的函数，Z是整数集合，f,g的定义如下：0 x是奇数 f(x)=1 x是偶数 g(x)=3x试求(1)fog(x)(2)gof(x)(3)f2(x)(4)f500(x)(5)f和g是否是满射的，是否是双射函数？规定0是偶数函数的复合运算为左复合。,28,解:0 x是奇数(1)fog(x)=f(g(x)=f(3x)=3x x是偶数 0 x是奇数(2)gof(x)=g(f(x)=3 x是偶数 1(3)f2(x)=fof(x)=f(f(x)0(4)f500(x)=f2(x)(5)f和g都不是满射的，当然不是双射的。,29,8、设A=1，2，3，B=a,bf:AB的满射函数有多少个？解：由A到B的函数个数为BA=23其中内射的有2个，于是满射函数为8-2=6个。9、设f：AB，t,g:BC的二元关系证明：fo(gt)=(fog)(fot)解：对任意a,c fo(gt)=b(a,bfb,cgt)=b(a,bf(b,cgb,ct)=b(a,bfb,cg)(a,bfb,c t)=b(a,bfb,cg)b(a,bfb,ct)=a,cfoga,cfot=a,c(fog)(fot)问题得证。,30,代数系统判断给定集合和运算能否构成代数系统判断给定二元运算的性质求而二元运算的特异元素了解同类型和同种代数系统的概念了解子代数的基本概念计算积代数判断函数是否为同态映射和同构映射判断或证明给定集合和运算是否构成半群、独异点和群熟悉群的基本性质能够证明G的子集构成G的子群熟悉陪集的定义和性质熟悉拉格朗日定理及其推论，学习简单应用,31,会用Polya定理进行计数会求循环群的生成元及其子群熟悉n元置换的表示方法、乘法以及n元置换群能判断给定代数系统是否为环和域能够判别给定偏序集或者代数系统是否构成格能够确定一个命题的对偶命题能够证明格中的等式和不等式能判别格L的子集S是否构成子格能够判别给定的格是否为分配格、有补格能够判别布尔代数并证明布尔代数中的等式,32,练习题：1、179页82、180页143、202页34、203页15，16，17，185、219页9,33,练习题,1、设S3是S=1，2，3上所有双射函数（也叫置换）构成的集合，o是S3上的复合运算，(1)给出其复合运算的运算表，(2)证明它是否是群(3)证明它和Z6，+6是否同构(4)若是群给出其所有子群解：S3上能够构成3！个双射函数，F=f1,f2,f3,f4,f5,f6,34,其中：f1=1,1,2,2,3,3 f2=1,1,2,3,3,2 f3=1,3,2,2,3,1 f4=1,2,2,1,3,3 f5=1,2,2,3,3,1 f6=1,3,2,1,3,2运算表见下页。,35,o f1 f2 f3 f4 f5 f6 f1 f1 f2 f3 f4 f5 f6 f2 f2 f1 f5 f6 f3 f4 f3 f3 f6 f1 f5 f4 f2 f4 f4 f5 f6 f1 f2 f3 f5 f5 f4 f2 f3 f6 f1 f6 f6 f3 f4 f2 f1 f5 函数的复合运算是可结合的，表中第1行和第1列和定义域的排列顺序一致，因此f1是幺元，从表中可以看出每个元素均有逆元，f2，f3，f4均是自身的逆元，f5 和f6互为逆元。因此该系统是群。,36,作出 Z6，+6的运算表如下+6 0 1 2 3 4 5 0 0 1 2 3 4 5 1 1 2 3 4 5 0 2 2 3 4 5 0 1 3 3 4 5 0 1 2 4 4 5 0 1 2 3 5 5 0 1 2 3 4这是个6阶群，幺元是0，1和5互逆，2和4互逆，3是3的逆。它和 S3，o不同构因为在该系统中只有3是3的逆，而在 S3，o中有3个元素是自身的 逆元。,37,S3，o是群，根据拉哥朗日定理，它有1，2，3，6阶子群，其中1阶子群是G1=f1，o 2阶子群是G2=f1，f2，o G3=f1，f3，o G4=f1，f4，o 3阶子群是G5=f1，f5,f6，o 6阶子群是G6=S3，o而 Z6，+6的真子群是：2阶子群为0,3，+6 3阶子群是0,2,4,+6,38,可以证明 Z6，+6的2阶子群0,3，+6和 S3，o的任何2阶子群都同构，其3阶子群相互同构。,39,图论部分,深刻理解握手定理及推论的内容并能灵活地应用它们深刻理解图同构、简单图、完全图、正则图、子图、补图、二部图的概念以及它们的性质及相互之间的关系记住通路与回路的定义、分类及表示法深刻理解与无向图连通性、连通度有关的诸多概念会判别有向图连通性的类型熟练掌握用邻接矩阵及其幂求有向图中通路与回路数的方法，会求可达矩阵,40,深刻理解欧拉图、半欧拉图的定义及判别定理深刻理解哈密顿图、半哈密顿图的定义.会用哈密顿图的必要条件判断某些图不是哈密顿图.会用充分条件判断某些图是哈密顿图.要特别注意的是，不能将必要条件当作充分条件，也不要将充分条件当必要条件.,41,深刻理解本部分的基本概念：平面图、平面嵌入、面、次数、极大平面图、极小非平面图、对偶图牢记极大平面图的主要性质和判别方法熟记欧拉公式及推广形式，并能用欧拉公式及推广形式证明有关定理与命题会用库拉图斯基定理证明某些图不是平面图 记住平面图与它的对偶图阶数、边数、面数之间的关系深刻理解与支配集、点覆盖集、边覆盖集、点独立集、边独立集(匹配)、,42,点着色、边着色、面着色、色数等概念会求阶数 n 较小或特殊图的 0,0,0,1,1会用二部图中匹配的理论解简单问题理解并记住地图面着色与它的对偶图点着色之间的关系会用点色数及边色数解决一些实际问题.,43,练习题：1、292页4，5，6，7，82、293页233、294页44，45，46，474、295页49，50,