离散数学总结.ppt

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