离散数学复习

第1章命题逻辑1.命题的定义2.命题的翻译，“只要就”，“只有才”，“除非”等3.公式分类与等价式（其中比较特别的公式）4.对偶式5.范式，主范式，大小项6.命题逻辑的推理理论第2章谓词逻辑1.谓词的基本概念，“存在后跟合取，全称后跟条件”2.约束变元，自由变元3.谓词逻辑中的等价式（其中比较特别的公式）第3章集合论1.集合、元素的定义（如P96习题2）2.幂集的定义3.集合自身的并、交运算第4章关系与函数1.关系的定义2.关系的运算1）基本运算2）特有运算：①复合运算；②幂运算；③逆运算；④闭包运算3.关系的三种表示：①集合，②关系矩阵，③关系图4.关系的性质：①自反性；②非自反性；③对称性；④非对称性；⑤反对称性；⑥传递性。这些性质反映在矩阵上，关系图中有什么特点？5.等价关系6.偏序关系：①定义；②最大（小）元，极大（小）元；③后面的格中涉及到的哈斯图第12章代数结构1.代数结构的定义与例2.代数结构的性质第13章半群与群1.半群和独异点的定义及性质2.群的定义及性质3.Abel群定义及性质第15章格与布尔代数1.哈斯图（内容见PPT）2.格（内容可以看PPT，或见附录）第16章图的基本概念及其矩阵表示1.图的基本概念（包括简单图，多重图，零图，完全图，正则图，生成子图，诱导子图，握手定理的灵活运用）2.链（或路）和圈（回路）①基本链（路），简单链（路），基本链（路）和圈（回路）的性质②无向图和有向图的结点的可达，无向图和有向图连通性，连通分图3.最短链（路）（包括无向图和有向图）4.图的矩阵表示：邻接矩阵，关系矩阵，可达矩阵第17章几类重要的图1.欧拉图与哈密尔顿图：定义与性质2.二部图：定义3.树1）无向树：①五个定义（性质）（注意灵活运用）；②最小生成树的定义及求法2）有向树：①最优二叉树；②哈夫曼编码附录：一、格定义：设L,≤是一个偏序集，若对任意a,bL，存在最大下界(GLB)和最小上界(LUB)，则称L,≤为格。用ab表示GLB{a,b}，ab表示LUB{a,b}，并称和分别为L上的交（或积）和并（或和）运算。这样我们由偏序关系定义了两种二元运算。有时也用∧和∨分别表示和因此，格有时也表示成L,,或L,∨,∧。二、子格定义：设L,∨,∧是一个格，S是L的非空子集，如果S关于运算∨和∧是封闭的，则称S,∨,∧是L,∨,∧的子格。显然，子格本身是一个格。例如：设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=fS3。三、分配格定义：设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)（事实上，上面是利用“最大公约数对最小公倍数是分配的，最小公倍数对最大公约数也是分配的”这个性质）链hfcbedga故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互为补元。一般说来，一个元素可以有其补元，未必唯一，也可能无补元。例：试判断下图中每个元素有无补元，若有，写出补元。1,0显然互为补元；a的补元是e，c的补元是d；b没有补元；d的补元是c和e，e的补元是a和d。有补格的定义：设L,≤是格，若L中每个元素至少有一补元，则称L,≤为有补格。例：试判断下图中哪些是有补格？√√√×性质：1.有界分配格中，若一个元素有补元，则必是唯一的。2.有补分配格中，任意一个元素的补元是唯一的。第一章1.了解命题的判断条件。陈述句；能确定真假。2.了解五个联结词的含义及真值表3.了解命题公式的翻译：(一)她喜欢运动也喜欢读书(二)他虽聪明，但不用功4.了解永真式、永假式的概念5.熟练掌握P37(,I2,I9,I11,),P38(E8,E9,E16,E18,E21,E22)公式6.重点掌握主析取范式和主合取范式7.求与以下公式逻辑等价的主合取范式和主析取范式。1acedb0a)(A→B)→(A∨C)b)┑(P∨Q)(P∧Q)c)A→(B∧C)d)将公式化成仅含∧、∨和┒的形式。去掉其他联结词e)利用摩根定律将否定号“┒”移到各个命题变元之前。f)利用结合律、分配律等将公式化成合取范式或析取范式的形式。g)若析取范式的基本积中同一命题变元出现多次，则将其化成只出现一次。h)去掉析取范式中所有为永假式的基本积，即去掉基本积中含有形式如P∧P的子公式的那些基本积。i)若析取范式中缺少某个命题变元如P，则可以用公式(P∨P)∧QQ将命题公式补充进去，并利用分配律展开。然后合并相同的基本积。8.命题演算的推理理论第二章1．掌握谓词公式的翻译1.有且只有一个太阳2.没有不范错误的人3.任何整数都是实数4.所有人都是要死的5.尽管有人聪明，但未必一切人都聪明2．了解约束变元和自由变元及量词的辖域1.(1)(x)(P(x)Q(x))2.(2)(x)(P(x)($y)R(x,y))3.(3)(x)(y)(P(x,y)ùQ(y,z))ù($y)P(x,y)4.(4)((x)(P(x)ù($x)Q(x,z))($y)R(x,y))∨Q(x,y)3．掌握量词的转换率1.┐(x)A(x)($x)┐A(x)2.┐($x)A(x)(x)┐A(x)4．掌握前束范式课本例子：(x)(y)(($z)(P(x,z)∧P(y,z))→($u)Q(x,y,u))l将公式化成仅含∧、∨和┒的形式。去掉其他联结词l利用摩根定律和量词的转换率将否定号“┒”移到各个命题函数之前。l进行约束变元的换名l量词前移5．谓词演算的推理理论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）对称、反对称2A={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,ca,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,b4．等价关系概念、划分的概念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,*到其自身