离散数学总结.pptx

第一级,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,离散数学总结,主要内容,命题逻辑,一阶逻辑,集合,关系与函数,图与特殊图,代数系统,2,命题逻辑,3,范式：,析取范式：,合取范式：,主析取范式：,析取范式中，每一项都是极小项,极小项的编码,两种方法求主析取范式：真值表、等值演算,主合取范式：,合取范式中，每一项都是极大项,极大项的编码,两张方法求主合取范式：真值表、等值演算,4,命题推理,析取三段论、假言推理、拒取、假言三段论,组合电路设计（了解）,5,一阶逻辑,谓词及符号化命题,特性谓词符号化命题，如：,不是所有四川人都喜欢吃辣椒,有的火车比所有汽车都跑得慢,论域有限域上的谓词公式消去量词的方法,6,大家有疑问的，可以询问和交流,可以互相讨论下，但要小声点,集合,8,关系及函数,9,关系的性质,自反、反自反、对称、反对称、传递,如何从关系图、关系矩阵判断关系具有的性质,特殊关系具有的性质：,空关系：反自反、对称、反对称、传递,全域关系：自反、对称、传递,恒等关系：自反、对称、反对称、传递,关系的运算：逆、合成（左复合）,求关系的闭包,自反闭包,r(R),、对称闭包,s(R),、传递闭包：,t(R),10,等价关系：,定义：自反、对称、传递,（,、,E,A,、,I,A,哪些是等价关系）,等价类：,x,Ry,|,y,A,xRy,商集：,A,/,R,=,x,R,|,x,A,集合的一种划分,(A),集合上的一种等价关系,R,若,(A)=,A,1,A,2,A,m,，则其诱导的等价关系,R=,(A,1,A,1,),(A,2,A,2,)(A,m,A,m,),集合上的不同等价关系个数,=,集合的不同划分数,偏序关系：,记作,定义：自反、反对称、传递（,、,E,A,、,I,A,，哪些是偏序关系,）,常见偏序关系：,、,、,Hase,图（正确画出）,全序关系的,Hase,图是一条线（线序关系）,11,极大元、极小元、最大元、最小元、上界、上确界、下界、下确界,格：偏序集中任两元素都有上确界、下确界,函数定义：特殊的关系,B,A,：所有从,A,到,B,的函数的集合记作,B,A,=,f,|,f,:,A,B,函数的计数：,|,A,|=,m,|,B,|=,n,且,m,n,0,|,B,A,|=,n,m,.,函数的复合（合成）：左复合,12,图与特殊图,术语：,有向图、无向图、完全图,顶点的度、出度、入度、握手定理,图的阶：图中顶点的个数,图的表示：邻接矩阵,Euler,图：,定义：,经过图中所有边一次且仅一次的回路。（,一笔画问题，简单回路）,无向,Euler,图充要条件：无奇度点,无向半,Euler,图充要条件：,2,个或,0,个奇数度点,有向,Eluer,图：所有点入度,=,出度,有向半,Eluer,图：,除两个结点，每个结点入度等于出度，一个结点的入度比出度大,1,，另一个结点的入度比出度小,1,13,Hamiliton,图：,定义：,经过图中所有顶点一次且仅一次的回路。（点不重复，初级回路）,充分条件：,若任意一对不相邻的顶点的度数之和,n,，,则,G,中存在,Hamilton,回路，即,G,为,Hamilton,图,必要条件：,若无向图,G,=,是哈密顿图，则对于,V,的任意非空真子集,V,1,均有,p,(,G,V,1,),|,V,1,|.,二部图：,定义：,判定：无向图,G,=,是二部图当且仅当,G,中无奇数长度的回路,14,平面图：,定义：,判定：,极大平面图、极小非平面图,N(3),的极大平面图,连通且各个面的次数均为,3,欧拉公式：,连通平面图,:,点数,-,边数,+,面数,=2,非联通平面图,:,点数,-,边数,+,面数,=p+1,对偶图：也是平面图。同构的平面图，其对偶图不一定同构,顶点着色问题,15,代数系统,二元运算：封闭性,二元运算的特殊元素：,幺元（单位元）、零元、逆元,|S|1,时，,e,幺元、零元唯一性,逆元：存在幺元时，元素的逆元不唯一。若运算可结合，则逆元也有唯一性,代数系统：,、,，,，,、,、,的幺元、零元，有逆元的元素的逆元,半群：可结合的代数系统,封闭性,结合性,16,独异点：含幺半群,封闭性,结合性,幺元存在,群：,判定：封闭性、结合性、有幺元、可逆,术语：,群的阶,元素的阶,元素的幂,17,性质：,G,是群,|G|1,时，除幺元外，无其他幂等元,群中无零元,群中可解方程,消去律,有限群的运算表中，每行（列）为群中元素的一个置换，无两行（列）相同,子群：,定义,判定：,Lagrange,定理：,HG,，,|H|=m,，,|G|=n,，则,n|m,有限群，子群的阶是父群阶的因子,素数阶群，无非平凡子群,有限群中任意元素,a,的阶，必为,n,的因子，且,a,n,=e,Ex,：,16,阶群,18,19,环：,定义：,是阿贝尔群,是半群,#,对,*,可分配,性质：,的幺元是,的零元,、,整环、除环,域：既是整环，又是除环,是域、,不是域,20,