1、离散数学复习提纲集合论一、基本概念集合(set)：做为整体识别的、确定的、互相区别的一些对象的总体。规定集合的三种方式：列举法、描述法、归纳法集合论的三大基本原理外延公理：两个集合A和B相等当且仅当它们具有相同的元素（无序性）概括公理：对于任意个体域U，任一谓词公式P都确定一个以该域中的对象为元素的集合S（确定性）正规公理：不存在集合A1,A2,A3,使得A3A2A1（有限可分，集合不能是自己的元素）注意：隶属、包含的判断（有时两者兼有）定理1：对于任意集合A和B，A=B当且仅当A B且B A传递性，对全集、空集的关系等定理5：空集是唯一的子集、真子集、子集个数等运算：并、交、补、差、幂集，及
2、一些运算性质、公式幂集：对任意集合A，(A)称作A的幂集，定义为：(A)=x|xA，所有子集的集合设A,B为任意集合， AB当且仅当(A) (B)集合族：如果集合C中的每个元素都是集合，称C为集合族集合族的标志集：如果集合族C可以表示为某种下标的形，C=Sd|dD，那么这些下标组成的集合称作集合族C的标志集广义并、广义交，及相关运算性质、公式归纳定义：基础条款：规定某些元素为待定义集合成员，集合其它元素可以从基本元素出发逐步确定归纳条款：规定由已确定的集合元素去进一步确定其它元素的规则终极条款：规定待定义集合只含有基础条款和归纳条款所确定的成员基础条款和归纳条款称作“完备性条款”，必须保证毫无
3、遗漏产生集合中所有成员终极条款又称“纯粹性条款”，保证集合中仅包含满足完备性条款的那些对象例：自然数的归纳定义、数学归纳法等（建议看一下课件例子了解一下思路）二、关系有序组（二元）：设a,b为任意对象，称集合族a,a,b为二元有序组，简记为称a为的第一分量，b为第二分量递归定义：n=2时，=a1,a1,a2n2时，=, an集合的笛卡儿积：对任意集合A,A2,A，A1A2称作集合A1，A2的笛卡儿积，定义如下：A1A2 = | uA1,vA2A1A2 An =(A1A2 An-1) An定理：对于任意有限集合A1,An，有|A1An|=|A1|*|An|一些运算性质关系是各个对象之间的联系和对
4、应R称为集合A1,A2,An-1到An的n元关系，如果R是A1A2An的一个子集。当A1=A2=An-1=An时，也称R为A上的n元关系几个特殊二元关系：空关系、全关系、相等关系定义：设R为A到B的二元关系(RAB)xRy表示R， xRy表示R定义域domain：Dom(R)=x|xAy(R)R的值域range：Ran(R)=y|yBx(R)称A为R的前域，B为R的陪域注意：前域与定义域，陪域与值域的差别。尤其是定义域与前域，与函数的差别关系表示法：集合表示法关系图表示法（有向箭头，主要是前域陪域相同的关系图）关系矩阵（mij=1当且仅当aiRbj；mij=0当且仅当aiRbj）关系相等：相同
5、前域陪域，且xy(xRyxSy)运算：要有相同前域、陪域。但总可以对关系的前域和陪域做适当的扩充，使之满足条件并（矩阵分量析取）交（矩阵分量合取）差（前一个关系和后一个关系的补矩阵做合取）补（矩阵做否定） 逆运算：R=|xRy，RAB，是BA上的关系，关系矩阵转置合成：RAB，SBC，R和S的合成关系RS定义为：RS=|xAzCy(yBxRyySz)，RS AC矩阵乘法，其中乘法用合取，加法用析取幂运算：定义为自身的n次合成Rn=RR（n个R合成），R0=EA幂关系有限定理：设集合A的基数为n，R是A上的二元关系，则存在自然数i,j使得0 ij2n2，有Ri=Rj（鸽笼原理，AA有n2个元素，
6、子集个数为2n2个）自反关系：（就是每个元素都和自己有关系）x(xAxRx)关系图：每个节点都有环关系矩阵：对角线全为1反自反关系：（每个元素都和自己没关系）x(xA xRx)关系图：每个节点都没有环关系矩阵：对角线全为0对称关系：（每对关系都是相互的）xy(x,yAxRyyRx)关系图：两个节点之间有边的就有反向边关系矩阵：对称矩阵反对称关系：（若有相互关系则只能是同一个元素，不同元素间不能有相互关系）xy(x,yAxRyyRxx=y)关系图：两个节点之间只能有一条单向边关系矩阵：ci,j=1(ij)时cj,i=0传递关系：xyz(x,y,zAxRyyRzxRz)关系图：如果有边v1v2,v
7、n-1vn，则有边v1vn注意：A上的空关系是反自反的，不是自反的（此外是对称的、反对称的、传递的）如果A=，那么A上的空关系就是自反的，同时也是反自反的，因为注意定义谓词的前件xA始终为假A上的相等关系EA既是对称的，又是反对称的 即对于特殊集合、关系的判断要从定义式出发，注意前件的真假R自反当且仅当EARR反自反当且仅当EARR对称当且仅当RRR反对称当且仅当RREAR传递当且仅当R2R运算的封闭性：如果关系R的某个性质经过关系运算后仍然保持，则称该性质对这个运算封闭（以上5个特性对交和求逆运算都封闭，自反对合成封闭）等价关系：等价关系R为A上的自反、对称、传递的二元关系等价类：设R为A上
8、的等价关系，对于每个aA，a的等价类记做aR(简记a)，定义为：aR=x|xA xRa，a称作aR的代表元素划分：满足下列条件的集合A的子集族B(B B) （划分单元里没有空集）=A （所有划分单元合起来是全集）B B(BBBB B B=) （划分单元两两不相交）中的元素称为划分的单元特别约定A=时只有划分A上的等价关系R的所有等价类的集合，构成A的一个划分，称作等价关系R对应的划分反过来，集合A的一个划分，也对应A上的一个等价关系R，称作划分对应的等价关系等价关系和划分的一一对应划分的“粗细”概念：如果1的每一个单元都包含于2的某个单元，称1细于2，表示为12；如果12而且12 ，则表示为1
9、2，称作“真细于”定理：1，2分别是等价关系R1，R2对应的划分，那么R1R2 12定理说明，越“小”（包含二元组较少）的等价关系对应越细的划分；最小的等价关系是相等关系EA；最大的等价关系是全关系划分的运算：（结合图来很好理解）积划分运算：划分1和2的积划分12是满足如下条件的划分：12细于1和2；如果某个划分细于1和2，则一定细于12；也就是说， 12是细于1和2的最粗划分（”最小公倍数”）积划分对应于等价关系交运算和划分运算：划分1和2的和划分1+2是满足如下条件的划分：1和2均细于1+2；如果有划分， 1和2均细于，则1+2细于。也就是说， 1+2是粗于1和2的最细划分（“最大公约数”
10、）和划分不对应于等价关系的并运算，而是对应于等价关系并运算结果的传递闭包二元关系R的传递闭包t(R)：t(R) 是传递的，Rt(R)，对于A上的任意一个具有传递性质且包含R的关系R，t(R)R商集：R是A上的等价关系，称A的划分aR|aA为A的R商集，记做A/RA/(R1R2 )=A/R1A/R2A/t(R1R2)=A/R1+A/R2序关系：R为集合A上的自反、反对称、传递的二元关系存在序关系R的集合A称作有序集（ordered set），用二元有序组表示，一般的有序集表示成哈斯图：对序关系关系图的一种简化画法由于序关系自反，各结点都有环，省去；由于序关系反对称且传递，所以关系图中任何两个不同
11、的结点直接不会有双向的边或通路，所以省去边的箭头，把向上的方向定为箭头方向由于序关系传递，所以省去所有推定的边，即ab,bc有ac，省去ac边元素排序：ab，称a先于或等于b；a小于或等于b；如果(ab)，则称a,b不可比较或者不可排序最大（小）元、极大（小）元（必须是B中元素）：为有序集，BAB的最小元b：bBx(xBbx) （必须比每个B的元素都小于或等于）B的最大元b：bBx(xBxb) （必须每个B的元素都比它小于或等于）B的极小元b：bBx(xBxbxb) （比B中每个可比元都小于或等于）B的极大元b：bBx(xBxbbx) （B中每个可比元都比它小于或等于）极大和最大的差别在于B中
12、是否包含不可比较的元素最大（小）元必为极大（小）元；最大（小）元若有则唯一；极大（小）元恒存在未必唯一上（下）界，上（下）确界（只要是A中元素）：为有序集，BAB的上界a：aAx(xBxa) （必须每个B的元素都比它小于或等于）B的下界a：aAx(xBax) （必须比每个B的元素都小于或等于）B的上确界a：a是B的所有上界的集合最小元B的下确界a：a是B的所有下界的集合最大元最大（小）元是上（下）确界；属于B的上（下）界为最大（小）元；都未必存在链、反链半序关系：R为集合A上的反自反、反对称、传递的二元关系（即序关系除去每个元素与自己的关系）三、函数定义：如果X到Y的二元关系fXY，对于每个x
13、X，都有唯一的yY，使得f，则称f为X到Y的函数，记做：f:XY前域和定义域重合；单值性：ff y=yy=f(x)，称x为自变元，y为函数在x处的值，y为x的像点，x为y的源点（基于映射）X时，空关系不是函数，当X时，空关系是函数，称作空函数函数的规定方法：列表法、图标法、解析法、递归定义函数相等与包含函数个数：如果|X|=m，|Y|=n，则f|f:XY的基数为nm，共有nm个X到Y的函数。X到Y的全体函数集合表示为YX定义域子集的映象：f(A)=y|x(xAy=f(x)（即定义域的一个子集A的值域）函数合成（恩，不写了。）单射：如果任意x1x2有f(x1)f(x2)。如果f和g都是单射函数，
14、则其合成gf也是单射函数。如果gf是单射函数，则f是单射函数满射：如果任意y都有x使得y=f(x)，即Ran(f)=Y。如果f和g都是满射函数，则其合成gf也是满射函数。如果gf是满射函数，则g是满射函数双射函数：如果f既是单射函数又是满射函数，称作双射函数。如果f和g都是双射函数，则其合成gf也是双射函数。如果gf是双射函数，则f是单射函数，g是满射函数逆函数：只有双射函数存在逆函数左逆函数：如果g f=EX，则称g为f的左逆函数右逆函数：如果f g=EY，则称g为f的右逆函数f可逆当且仅当f既有左逆函数，又有右逆函数，而且左逆函数和右逆函数相等图论图：由结点和联结结点的边所构成的离散结构G
15、=结点集V（非空），边集E（多重集，可以有多个相同边）有向边：结点的二元有序组表示无向边：结点的两元素多重集表示有限图：V,E都有限集重边：重数大于1的边有重边的为重图，否则为单图简单图：无环无重边的无向图完全图：任意两个不同结点间都有边，Kn孤立结点、零图（只有孤立结点）赋权图：G=，结点权函数：f:VW，边权函数：g:EW结点的度：d(v)定义为关联端点v的边的数目注意对有向图来说度d(v)=d+(v)+d-(v)度的总和为偶数，边数目的两倍；有向图出度等于入度悬挂点：一度的顶点正则图：所有顶点的度均相同的图称为正则图，按照顶点的度数k称作k-正则图，Kn是n-1正则图子图、真子图：边集结
16、点集都必须为子集生成子图：结点集相同的子图补图：结点集相同，边集交集为空，并集为完全图图的同构：可以将V1中所有的结点一一对应地置换为V2中的结点名后得到的图等于G2（同分异构体）拟路径：v1,e1,v2,e2,v3,vl-1,el-1,vl，其中ei=或者vi,vi+1，拟路径中的边数目称作拟路径的长度路径：拟路径中的边各不相同闭路径：v1=vl的路径通路：路径中的顶点各不相同回路：v1=vl的通路路径和通路定理：在有n个顶点的图G中，如果有顶点u到v的拟路径，那么u到v必有路径，并且必有长度不大于n-1的通路闭路径和回路定理：在有n个顶点的图G中，如果有顶点v到v的闭路径，那么必定有一条从
17、v到v的长度不大于n的回路可达：u=v，或者存在一条u到v的路径连通的无向图：无向图中任意两个顶点都是可达的强连通的有向图：有向图中任意两个顶点都是互相可达的单向连通的有向图：任意两个顶点，至少从一个顶点到另一个是可达的弱连通的有向图：将有向图看作无向图时是连通的连通分支：图G的连通子图G，而且G不是任何其它连通子图的真子图（最大性）欧拉图：如果图G上有一条经过所有顶点、所有边的闭路径（允许顶点重复） 无向图：G连通，所有顶点的度都是偶数 有向图：G弱连通，每个顶点的出度与入度相等欧拉路径：如果图G上有一条经过所有顶点、所有边的路径（非闭）（允许顶点重复） 无向图：G连通，恰有两个顶点的度是奇
18、数 有向图：G连通，恰有两个顶点出度与入度不相等，其中一个出度比入度多1，另一个入度比出度多1哈密顿图：如果图G上有一条经过所有顶点的回路（不要求经过所有边）哈密顿通路：如果图G上有一条经过所有顶点的通路（非回路）判定定理（充分非必要）：如果具有n个顶点的图G的每一对顶点的度数之和都不小于n-1，那么G中有一条哈密顿通路。如果G的每一对顶点度数之和不小于n，且n=3，则G为一哈密顿图邻接矩阵：无重边的有向图G=，其邻接矩阵AG定义为，aij=1, 当E，aij=0, 当E注意：与关系矩阵的联系。拟路径，邻接矩阵自乘L次：AL，则乘积结果矩阵中每个分量aij(L)的含义为G中顶点vi到vj的长度
19、为L的拟路径条数路径矩阵B=A A(2) A(3) A(|V|)，其中A(m)=A A AB的每个分量bij表示vi到vj是否有路径可达性矩阵：P=I B，加上顶点的自身可达性关联矩阵（简单无向图）：表示顶点和边的关联关系，n*m矩阵。通过矩阵的秩来判定图的连通分支个数二分图：满足如下条件的无向图G=有非空集合X,Y, X Y=V, X Y= 每个vi,vjE，都有viXvjY或者viYvjX可以用G=表示二分图bipartite graph如果X,Y中任意两个顶点之间都有边，则称为完全二分图。记作K|X|,|Y|二分图的等价条件：G至少要有两个顶点，而且G中所有回路的长度都是偶数匹配：将E的
20、子集M称作一个匹配，如果M中的任意两条边都没有公共端点。边数最多的匹配称作最大匹配。如果X(Y)中的所有的顶点都出现在匹配M中，则称M是X(Y)-完全匹配。如果M既是X-完全匹配，又是Y-完全匹配，称M是完全匹配*匈牙利算法：任取一个匹配，取非饱和点走交错路（边交替属于不属于已有匹配），若终点是非饱和点，则令匹配为原匹配和增广路的（即属于这两个集合但不属于交集部分）；若终点是饱和点，则将起点去掉不再考虑（我猜不会考）平面图：如果无向图G可以在一个平面上图示出来，并且各边仅在顶点处相交，称作平面图。K5和K3,3都不是平面图，K5是顶点数最少的非平面图，K3,3是边数最少的非平面图平面图等价条件
21、：G或者G的子图作任何同胚操作（在原图的边上增加或者删除二度节点）后得到的图均不能以K5及K3,3为子图树：连通无回路的无向图称为树树中的悬挂点称作树叶非树叶节点称作分支点仅有单个孤立节点的树称作空树每个连通分支都是树的图称作森林（树也是森林）性质：简单、二分、平面 顶点数比边数多1 删去任意一条边就不连通生成树：如果图T是G的生成子图，且T是树。任意连通图G都至少有一棵生成树根树rooted tree递归定义一个孤立节点v0是根树，v0称为树根如果T1,T2,Tk是根树，其树根分别是v1,v2,vk，则V=V(T1) V(T2) V(Tk) v0；E=E(T1) E(T2) E(Tk) v0
22、,v1 v0,v2 v0,vkT=也是根树，v0称为树根Tn称为T的子树subtree，树根称为父节点parent，而子树的树根称为子节点childv1,v2,vk互称兄弟节点sibling根树中每个节点都是某个子树的根n元树：每个节点都至多有n个子节点的根树称作n元树二元有序树可以用来表示任何n元有序树：左子节点表示第一个子节点，右子节点表示下一个兄弟节点二元树的遍历：先根、中根、后根应用：表达式树、排序搜索树等抽象代数算术：研究整数、有理数、实数和复数的加、减、乘、除等运算代数：算术的一般化，允许用字母等符号来代替数进行运算代数结构：在一个对象集合上定义若干运算，并设定若干公理描述运算的性
23、质 非空集合S，称作代数结构的载体 载体S上的若干运算 一组刻画载体上各运算性质的公理抽象代数：抛弃代数结构中对象集合与运算的具体意义，研究运算的一般规律（交换、结合、分配），并对代数结构进行分类，研究其一般性质运算：Sn到S的一个函数，称为n元运算，常用*表示二元运算，常用表示一元运算运算的基本性质：（必须要满足） 普遍性：S中的所有元素都可参加运算 单值性：相同的元素运算结果也相同且唯一 封闭性：任何元素参加运算的结果也是S中的元素二元运算一般性质：（可以不满足） 结合律：xyz(x,y,zS x*(y*z)=(x*y)*z) 交换律：xy(x,yS x*y=y*x) *运算对#运算满足分
24、配律：xyz(x,y,zS x*(y#z)=(x*y)#(x*z)幺元：中的元素e，如果对任意x，满足x(x*e=e*x=x)右幺元：x(x*er=x)左幺元：x(el*x=x)一般情况下，左右幺元可能是不同元素，也可能有多个如果存在幺元，那么幺元是唯一的，而且同时是左右幺元零元：中的元素o，如果对任意x，满足x(x*o=o*x=o)右零元：x(x*or=or)左零元：x(ol*x=ol)如果存在零元则唯一逆元：中有幺元e，如果x*y=e，那么x称作y的左逆元，y为x的右逆元如果x*y=y*x=e，那么x,y互称逆元多于1个元素的载体集上零元没有逆元满足结合律的代数结构中，逆元唯一可约canc
25、elable元素：中元素a，如果对任意x,yS有a*x=a*y蕴涵x=y（左可约）x*a=y*a蕴涵x=y（右可约）那么a称为可约的满足结合律的代数结构中，有逆元的元素可约同类型代数结构：|S|=|S|；运算的元数相同同构的代数结构：存在S-S的一一映射h；S中运算的像等于运算数像在S的运算结果h(x*y)= h(x)*h(y)同态映射：对于代数结构和，如果有函数h:SS，对S中任意元素a,bh(a)= (h(a)，h(a#b)=h(a)#h(b)，这个函数h就称作代数结构S到S的同态映射如果h是单射函数，称作单一同态如果h是满射函数，称作满同态如果h是双射函数，称做同构映射同余关系：代数结构
26、中S上的一个等价关系，如果满足ab蕴涵ab，称是S上关于一元运算的同余关系；ab,cd蕴涵a*cb*d，称是S上关于二元运算*的同余关系。如果是代数结构上所有的运算的同余关系，则称是上的同余关系半群：运算满足结合律的代数结构独异点：含有幺元的半群群：半群；有幺元；每个元素都有逆元交换群：满足交换律的群环：，有两个二元运算，是阿贝尔群，是半群，*对+可分配：a*(b+c)=a*b+a*c域：，是环，为交换群形式语言与自动机语言的定义：Chomsky:按照一定规律构成的句子和符号串的有限或者无限的集合形式语言主要研究语言描述的问题穷举法：只适合句子数目有限的语言语法描述：通过有限的替换规则，生成语
27、言中合格的句子自动机：对输入的句子进行检验，区别哪些是语言中的句子，哪些不是语言中的句子字符串：设V是有限集合，其中元素称为“字符”由V中字符相连而成的有限序列称为“字符串”不含任何字符的串称为“空串”，记做字符串所包含的字符个数称为“长度”，记做|s|，|=0包括空串的V上的字符串全体记做V*字符串连接：s=ab,t=gg连接st=abgg字符串n次幂：s自身连接n次，s0=字符串集合的运算：乘积：AB=st|sA,tB幂运算：A0=，An=An-1A=AAn-1闭包：A*=A0A1A2正闭包：A+=A1A2=A*-正则表达式： RE1:是正则式，正则集 RE2:xV，x是正则式，正则集x
28、RE3:如果、是正则式，则是正则式，正则集AB（字符串集合乘积） RE4:如果、是正则式，则(|)是正则式，正则集AB RE5:如果是正则式，则()*是正则式，正则集A*V上的正则表达式对应了V*的一个子集（正则子集）短语结构语法：是一个四元组G(V,S,v0,)V是字符集SV，称作终结符，N=V-S称作非终结符称作产生式关系，由ww这样的产生式构成，表示w可以替换成w，分别称为左部和右部v0N，称作初始符（句子符），是替换的起点直接导出关系（xy）：x=lwr, y=lwr, 且ww是产生式, l,rV*关系的传递闭包，wS*是语法正确的句子当且仅当v0 w导出的结果称作符合语法G的句子利用语法G产生的所有的正确构造的句子的集合称作为G的语言，记做L(G)导出树：用多元有向树表示语言导出过程。起始符v0作为树根，每个子树的树根是某个生成式的左部，子节点分别是生成式右部包含的符号，适合所有产生式的左部仅有一个非终结符情形乔姆斯基形式语法分类：0型语法：如果对产生式没有任何约束（无限制语法，短语结构语法PSG）产生递归可枚举语言，被图灵机识别1型语法：如果所有产生式形如A
