离散数学复习

第1章命题逻辑命题的定义命题的翻译，“只要就”，“只有才”，“除非”等公式分类与等价式（其中比较特别的公式）对偶式范式，主范式，大小项命题逻辑的推理理论第2章谓词逻辑谓词的基本概念，“存在后跟合取，全称后跟条件”约束变元，自由变元谓词逻辑中的等价式（其中比较特别的公式）第3章集合论集合、元素的定义（如P96习题2）幂集的定义集合自身的并、交运算第4章关系与函数关系的定义关系的运算1）基本运算2）特有运算：①复合运算；②幂运算；③逆运算；④闭包运算关系的三种表示：①集合，②关系矩阵，③关系图关系的性质：①自反性；②非自反性；③对称性；④非对称性；⑤反对称性；⑥传递性。这些性质反映在矩阵上，关系图中有什么特点？等价关系偏序关系：①定义；②最大（小）元，极大（小）元；③后面的格中涉及到的哈斯图第12章代数结构代数结构的定义与例代数结构的性质第13章半群与群半群和独异点的定义及性质群的定义及性质Abel群定义及性质第15章格与布尔代数哈斯图（内容见PPT）格（内容可以看PPT，或见附录）第16章图的基本概念及其矩阵表示图的基本概念（包括简单图，多重图，零图，完全图，正则图，生成子图，诱导子图，握手定理的灵活运用）链（或路）和圈（回路）①基本链（路），简单链（路），基本链（路）和圈（回路）的性质②无向图和有向图的结点的可达，无向图和有向图连通性，连通分图最短链（路）（包括无向图和有向图）图的矩阵表示：邻接矩阵，关系矩阵，可达矩阵第17章几类重要的图欧拉图与哈密尔顿图：定义与性质二部图：定义树1）无向树：①五个定义（性质）（注意灵活运用）；②最小生成树的定义及求法2）有向树：①最优二叉树；②哈夫曼编码附录：格定义：设<L,≤>是一个偏序集，若对任意a,bÎL，存在最大下界(GLB)和最小上界(LUB)，则称<L,≤>为格。用aÄb表示GLB{a,b}，aÅb表示LUB{a,b}，并称Ä和Å分别为L上的交（或积）和并（或和）运算。这样我们由偏序关系定义了两种二元运算。有时也用∧和∨分别表示Ä和Å因此，格有时也表示成<L,Å,Ä>或<L,∨,∧>。子格hfcbedga定义：设<L,∨,∧>是一个格，S是L的非空子集，如果S关于运算∨和∧是封闭的，则称<S,∨hfcbedga例如：设<S,≤>是一个格，其中S＝{a,b,c,d,e,f,g,h}，如图所示，取S1={a,b,d,f}S2={c,e,g,h}S3={a,b,c,d,e,g,h}问，其中哪些构成格？哪些是<S,≤>的子格？<S1,≤>,<S2,≤>是<S,≤>的子格，而<S3,≤>虽然是格，但不是<S,≤>的子格，因为b∧d=fS3。分配格定义：设<L,≤>是格，对任意的a,b,cÎL，有①aÅ(bÄc)=(aÅb)Ä(aÅc)②(aÄb)Å(aÄc)=aÄ(bÅc)则称<L,≤>为分配格，称①和②为格中分配律。性质1：如果交对并可分配，则并对交也一定是可分配的，反之亦然。只证前半部分，即由①推②：(aÄb)Å(aÄc)＝((aÄb)Åa)Ä((aÄb)Åc)（根据①）＝(aÅa)Ä(aÅb)Ä(cÅa)Ä(cÅb)（根据①，交换律）＝aÄ(aÅb)Ä(aÅc)Ä(bÅc)＝aÄ(bÅc)（吸收律）注：此性质说明，分配格的定义可以简化成只需满足①或②其中之一即可。性质2：每个链<L,≤>都是分配格。（|L|≥3）链链例：证明<Sn,≤>是一个分配格。证：设∧和∨分别为Sn上的交（或积）和并（或和）运算，对于任意a，b，c∈Sn，有a∨(b∧c)=lcm(a,gcd(b,c))=gcd(lcm(a,b),lcm(a,c))=(a∨b∧(a∨c)a∧(b∨c)=gcd(a,lcm(b,c))=lcm(gcd(a,b),gcd(a,c))=(a∧b)∨(a∧c)（事实上，上面是利用“最大公约数对最小公倍数是分配的，最小公倍数对最大公约数也是分配的”这个性质）故<Sn，|>是一个分配格。有界格定义：设<L,≤>是格，若L中有最大元和最小元，则称<L,≤>为有界格。由于最大（小）元存在必唯一，故一般把格中最大元记为1，最小元记为0。例：试判断下面哪些是有界格？×√√有补格补元的定义：设<L,≤>是有界格，对于aÎL，存在bÎL，使得aÄb=0，aÅb=1，称b为a的补元，记为a'。显然，若b是a的补元，则a也是b的补元，即a与b互为补元。一般说来，一个元素可以有其补元，未必唯一，也可能无补元。例：试判断下图中每个元素有无补元，若有，写出补元。11acedb01,0显然互为补元；a的补元是e，c的补元是d；b没有补元；d的补元是c和e，e的补元是a和d。有补格的定义：设<L,≤>是格，若L中每个元素至少有一补元，则称<L,≤>为有补格。例：试判断下图中哪些是有补格？√√√×性质：有界分配格中，若一个元素有补元，则必是唯一的。有补分配格中，任意一个元素的补元是唯一的。第一章了解命题的判断条件。陈述句；能确定真假。了解五个联结词的含义及真值表了解命题公式的翻译：她喜欢运动也喜欢读书他虽聪明，但不用功了解永真式、永假式的概念熟练掌握P37(,I2,I9,I11,),P38(E8,E9,E16,E18,E21,E22)公式重点掌握主析取范式和主合取范式求与以下公式逻辑等价的主合取范式和主析取范式。(A→B)→(A∨C)┑(P∨Q)(P∧Q)A→(B∧C)将公式化成仅含∧、∨和┒的形式。去掉其他联结词利用摩根定律将否定号“┒”移到各个命题变元之前。利用结合律、分配律等将公式化成合取范式或析取范式的形式。若析取范式的基本积中同一命题变元出现多次，则将其化成只出现一次。去掉析取范式中所有为永假式的基本积，即去掉基本积中含有形式如P∧P的子公式的那些基本积。若析取范式中缺少某个命题变元如P，则可以用公式(P∨P)∧QQ将命题公式补充进去，并利用分配律展开。然后合并相同的基本积。命题演算的推理理论第二章掌握谓词公式的翻译有且只有一个太阳没有不范错误的人任何整数都是实数所有人都是要死的尽管有人聪明，但未必一切人都聪明了解约束变元和自由变元及量词的辖域(1)("x)(P(x)Q(x))(2)("x)(P(x)($y)R(x,y))(3)("x)("y)(P(x,y)ùQ(y,z))ù($y)P(x,y)(4)(("x)(P(x)ù($x)Q(x,z))($y)R(x,y))∨Q(x,y)掌握量词的转换率┐("x)A(x)($x)┐A(x)┐($x)A(x)("x)┐A(x)掌握前束范式课本例子：("x)("y)(($z)(P(x,z)∧P(y,z))→($u)Q(x,y,u))l 将公式化成仅含∧、∨和┒的形式。去掉其他联结词l 利用摩根定律和量词的转换率将否定号“┒”移到各个命题函数之前。l 进行约束变元的换名l 量词前移谓词演算的推理理论ES,EG,US,UG规则(1) 翻译(2)证明作业 P8222题证明下列结论：鱼会游水，猴子不会游水，所以猴子不是鱼。所有的鱼都会游水，所有的猴子都不会游水，所以猴子不是鱼设：P(x):x是鱼，Q(x):x是猴子,R(x):x会游水第四章1． 掌握集合间的关系(∈,的区别)例：A={a,}判断下列结论是否正确。(1)A(2)íA(3){}íA，(4){}A(5)aA(6)aíA,(7){a}A(8){a}íA(9)(10)í(11){}{{}}(12){}í{{}}(13){}2． 掌握集合的运算(交，并，补，对称差，幂集)例子：（1） 设A={a,b,c},B={a,b,{a,b,c}}，则A∩B，AèB？|ρ(A)|?（2） A={a,{a}}，则ρ(A)?第五章1． 了解笛卡尔集的概念2． 了解关系的概念3． 熟练掌握二元关系的性质（1） 自反、反自反 R是N上的整除关系 S={1,2,3,…,10}和S中的关系R={<x,y>|x+y=10}例：R1,R2是A={a,b,c}上的二元关系，问R1，R2的性质R1={<a,a>，<b,b>，<c,c>，<a,b>，<c,a>}R2={<a,b>，<b,c>，<c,a>}R3={<a,b>，<b,c>，<c,a>,<a,a>}2 设A={1,2,3}，R是A上二元关系，R的关系图如图，则R具有什么性质？（2） 对称、反对称2 A={1，2，3}，R1，R2，R3是A上的二元关系，问其性质R1＝{<1,1>,<2,3>,<3,2>}，R2＝{<1,1>,<3,3>}R3＝{<2,2>,<2,3>,<3,1>},T＝{<1,2>,<2,1>,<1,1>}2 例:设A＝{a,b,c},A的关系R,S为:R＝{<a,a>,<b,b>}S＝{<a,b>,<a,c><a,a>}（3） 传递例:R1＝{<z,x>,<x,y>,<z,y>}是传递的，R1’={<x,y>,<y,z>}R2＝{<a,b>,<c,d>}是传递的，因为没有满足传递的前提,没有结论也可以。R3＝{<a,b>,<b,a>,<a,a>}不是传递的，因为没有<b,b>4． 等价关系概念、划分的概念X={a,b,c,d},R={<a,a>,<a,b>,<b,a>,<b,b>,<c,c>,<c,d>,<d,c>,<d,d>}试问R是否是等价关系5． 熟练掌握等价关系的证明设R是A上的自反和传递关系,如下定义A上的关系T,使得T={<x,y>|<x,y>∈R∧<y,x>∈R},证明T是等价关系。6． 了解关系的运算(合成、逆、闭包运算)设A={a,b,c}，A上的二元关系R={<a,b>,<b,a>}，求r(R)，s(R)，t(R)7． 偏序关系重点掌握哈斯图,最大、最小元，极大元、极小元，上、下界，最大下界、最小上界2 设A={a,b,c}，A上的偏序集<ρ(A),R>；(1)作出偏序关系R的哈斯图；(2)令B={{a},{c},{b,c}}，求B的最大、最小元，极大、极小元，上、下界、上、下确界。2 如图1所示给出了偏序集合<P,R>的哈斯图，这里P={x1,x2,x3,x4,x5}。(1) 试找出P的最大元，极大元，极小元，P有最小元吗？(2) 试问子集{x2,x3,x4},{x2,x4,x5}和{x1,x2,x3}，有无上界，上确界，下界，下确界？如有请求出。x1x2x3x4x5图1第六章1. 了解函数的定义2. 掌握特殊函数（满函数，单射函数，双射函数）2 设集合A={a,b,c,d},B={1,2,3,4},则从A到B的函数f={<a,2>,<b,1>,<c,3>,<d,2>}是什么函数2 设R为实数集，函数f:R→R,f(x)=x2-2x-1,则f是什么函数3. 了解反函数第八章1. 代数系统的概念，幺元的概念，零元的概念，逆元的概念2. 给出代数系统，能找出其幺元、零元、逆元3. 代数系统的同态和同构例：设U=<R,+>,V=<R,×>是两个代数系统,令映射j:RR1,j(x)=ex则j是U到V的同态映射，因为j(x+y)=ex+y,j(x)×j(y)=ex·ey=ex+y\j(x+y)=j(x)·j(y)但j不是满射,因为j(R)=R+ìR。U在j下的同态象j(R)是R的真子集R+例：设f:R→R定义为对任意x∈Rf(x)=5x，那么f是从<R,+>到<R,×>的一个单同态。因为f(x+y)=5x+y=5x×5y=f(x)×f(y)第九章1. 半群、含幺半群（独立点）的概念练习：P243,62. 群的概念3. 给定代数系统U=<G,*>，判定G是否是群的步骤：(1)验证*运算的可结合性(2)验证是否存在幺元e(3)验证对于所有x，是否存在x-1，使得x*x-1=x-1*x=e4. 群的同态和同构P24639,40给定群<G,*>，且a∈G,定义映射f(x)=a*x*a-1,x∈G.,证明：f是<G,*>到其自身的同构映射。第十二章1. 零图、平凡图、完全图、简单图、补图的概念2. 设G是含n个顶点和m条边的无(有)向完全图，则有m=(m=n(n-1))3. 图的矩阵表示作业：P32223,2第十三章1． 欧拉图的概念及其判定定理2． 哈密顿图的概念第十四章1． 树的概念及相关定理(1)-(5)2． 平面图的概念3． 欧拉公式4． 欧拉公式5个的推论5． P352第1，2题要点：命题的判定、符号化，对偶式（选择题）。小项和大项的定义（选择题）。谓词逻辑的符号化，谓词公式的等价式，n元谓词公式定义，自由