离散数学复习(精品).ppt

1各章核心内容各章核心内容数理逻辑部分数理逻辑部分深刻理解各联结词的逻辑关系深刻理解各联结词的逻辑关系,熟练地将命题符号化熟练地将命题符号化会求复合命题的真值会求复合命题的真值深刻理解合式公式及重言式、矛盾式、可满足式等概念深刻理解合式公式及重言式、矛盾式、可满足式等概念熟练地求公式的真值表，并用它求公式的成真赋值与成假赋熟练地求公式的真值表，并用它求公式的成真赋值与成假赋值及判断公式类型值及判断公式类型深刻理解等值式的概念深刻理解等值式的概念牢记基本等值式的名称及它们的内容牢记基本等值式的名称及它们的内容2熟练地应用基本等值式及置换规则进行等值演算熟练地应用基本等值式及置换规则进行等值演算理解文字、简单析取式、简单合取式、析取范式、合取范式理解文字、简单析取式、简单合取式、析取范式、合取范式的概念的概念深刻理解极小项、极大项的概念、名称及下角标与成真、成深刻理解极小项、极大项的概念、名称及下角标与成真、成假赋值的关系，并理解简单析取式与极小项的关系假赋值的关系，并理解简单析取式与极小项的关系3熟练掌握求主范式的方法（等值演算、真值表等）熟练掌握求主范式的方法（等值演算、真值表等）会用主范式求公式的成真赋值、成假赋值、判断公式的类型、会用主范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等值判断两个公式是否等值会将公式等值地化成指定联结词完备集中的公式会将公式等值地化成指定联结词完备集中的公式会用命题逻辑的概念及运算解决简单的应用问题会用命题逻辑的概念及运算解决简单的应用问题掌握消解规则及其性质掌握消解规则及其性质会用消解算法判断公式的可满足性会用消解算法判断公式的可满足性理解并记住推理形式结构的两种形式：理解并记住推理形式结构的两种形式：(A1 A2 Ak)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、判断下列公式的属性：、判断下列公式的属性：(1)(p q)r(2)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)=M0M1M2M4M6该公式是可满足的该公式是可满足的(2)p(p q r)=p p q r=T该公式是永真式，含有该公式是永真式，含有 p p 因子，所以其主析取范式为：因子，所以其主析取范式为：m0m1m2m3m4m5m6m7其中其中 代表析取。代表析取。93、指出下列公式的指导变元，量词的辖域，各个变元的自、指出下列公式的指导变元，量词的辖域，各个变元的自由出现和约束出现，并求它们的前束范式。由出现和约束出现，并求它们的前束范式。(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是是自由的。自由的。104、设个体域是、设个体域是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)115、首先将下列命题符号化然后推证其结论。、首先将下列命题符号化然后推证其结论。(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和和81310、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集合理论部分集合理论部分熟练掌握集合的基本运算（普通运算和广义运算）熟练掌握集合的基本运算（普通运算和广义运算）掌握证明集合等式或者包含关系的基本方法掌握证明集合等式或者包含关系的基本方法熟练掌握关系的三种表示法熟练掌握关系的三种表示法 能够判定关系的性质（等价关系或偏序关系）能够判定关系的性质（等价关系或偏序关系）掌握含有关系运算的集合等式掌握含有关系运算的集合等式掌握等价关系、等价类、商集、划分、哈斯图、偏序集等概掌握等价关系、等价类、商集、划分、哈斯图、偏序集等概念念计算计算A B,dom R,ranR,fldR,R 1,R S,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页页2918练习题练习题1、判断书上、判断书上132页页23题中所有图的性质：题中所有图的性质：解解:(a):是自反的，不对称的，不可传递的。是自反的，不对称的，不可传递的。(b):不自反的，反对称的，可传递的不自反的，反对称的，可传递的(c):自反的，对称的，可传递的。自反的，对称的，可传递的。(d):自反的，不地称的，可传递的自反的，不地称的，可传递的(e):不自反的，不对称的，不可传递的不自反的，不对称的，不可传递的(f):不自反的，对称的，不可传递的不自反的，对称的，不可传递的(g):自反的，反对称的，不可传递的自反的，反对称的，不可传递的(h):自反的，对称的，不可传递的自反的，对称的，不可传递的(i):不自反的，对称的，不可传递的不自反的，对称的，不可传递的(j):不自反的，反对称的，不可传递的不自反的，反对称的，不可传递的(k):自反的，反对称的，可传递的自反的，反对称的，可传递的(l):不自反的，反对称的，不可传递的。不自反的，反对称的，不可传递的。192、设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,1213、设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上的偏序关系。234、设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,于是很明显的可以看出每一列是一个等价类，于是商集为以列为元素的集合。245、给定T12上的整除关系D，试证明D是偏序关系，画出D的哈斯图。T12是12的因子的集合。解：整除关系是自反的，反对称的，可传递的，它是偏序关系，我们只画它的哈斯图12的因子=1，2，3，4，6，12 12 6 4 3 2 1 255、下图给出了偏序集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 x526解：这道题主要是注意哈斯图的画法，是下面的元素和上面解：这道题主要是注意哈斯图的画法，是下面的元素和上面的元素有偏序关系，还有偏序关系的性质，自反、反对称，的元素有偏序关系，还有偏序关系的性质，自反、反对称，可传递。及子集的极大、极小、最大、最小元是在子集里可传递。及子集的极大、极小、最大、最小元是在子集里找，而上下界及上下确界均是在找，而上下界及上下确界均是在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，下界和下确界是x4276、关系图中行上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都不是满射的，当然不是双射的。298、设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页页933练习题练习题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个元素是自身的个元素是自身的 逆元。逆元。37S3，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