最新离散数学总结精品ppt课件说课材料

1、离散数学总结22022-5-8主要内容主要内容n 命题逻辑命题逻辑n 一阶逻辑一阶逻辑n 集合集合n 关系与函数关系与函数n 图与特殊图图与特殊图n 代数系统代数系统32022-5-842022-5-852022-5-862022-5-8一阶逻辑一阶逻辑n 谓词及符号化命题谓词及符号化命题v 特性谓词特性谓词符号化命题，如：符号化命题，如：v 不是所有四川人都喜欢吃辣椒不是所有四川人都喜欢吃辣椒v 有的火车比所有汽车都跑得慢有的火车比所有汽车都跑得慢v 论域论域有限域有限域上的谓词公式消去量词的方法上的谓词公式消去量词的方法72022-5-8集合集合n 82022-5-8关系关系及函数及函数n

2、 92022-5-8n 关系的性质关系的性质v 自反、反自反、对称、反对称、传递自反、反自反、对称、反对称、传递v 如何从关系图、关系矩阵判断关系具有的性质如何从关系图、关系矩阵判断关系具有的性质v 特殊关系具有的性质：特殊关系具有的性质：v 空关系：反自反、对称、反对称、传递空关系：反自反、对称、反对称、传递v 全域关系：自反、对称、传递全域关系：自反、对称、传递v 恒等关系：自反、对称、反对称、传递恒等关系：自反、对称、反对称、传递n 关系的运算：关系的运算：逆、合成（左复合）逆、合成（左复合）n 求关系的闭包求关系的闭包v 自反闭包自反闭包r(R)、对称闭包、对称闭包s(R)、传递闭包：

3、、传递闭包：t(R)102022-5-8n 等价关系：等价关系：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) 集合上的集合上的不同等价关系个数不同等价关系个数=集合的集合的不同划分数不同划分数 偏序关系：偏序关系：记作记作 定义：自反、反对称、传递（定义：自反、

4、反对称、传递（、EA、IA，哪些是偏序关系，哪些是偏序关系） 常见偏序关系：常见偏序关系：、 Hase图（正确画出）图（正确画出） 全序关系全序关系的的Hase图是一条线图是一条线（线序关系）（线序关系）112022-5-8v 极大元、极小元、最大元、最小元、上界、上确界、下极大元、极小元、最大元、最小元、上界、上确界、下界、下确界界、下确界v 格：格：偏序集中任两元素都有偏序集中任两元素都有上确界、下确界上确界、下确界n 函数：函数：v 定义：特殊的关系定义：特殊的关系v BA：所有从：所有从A到到B的的函数的集合函数的集合记作记作BA =f |f :AB v 函数的计数：函数的计数：|A|

5、=m,|B|=n,且且m,n0,|BA|=nm.v 函数的复合（合成）：左复合函数的复合（合成）：左复合122022-5-8图与特殊图图与特殊图n 术语：术语：v 有向图、无向图、完全图有向图、无向图、完全图v 顶点的度、出度、入度顶点的度、出度、入度、握手定理握手定理v 图的阶：图中顶点的个数图的阶：图中顶点的个数n 图的表示：图的表示：邻接矩阵邻接矩阵n Euler图：图：v 定义：定义：经过图中所有边一次且仅一次的回路。（经过图中所有边一次且仅一次的回路。（一笔画问一笔画问题，题，简单回路简单回路）v 无向无向Euler图充要条件图充要条件：无奇度点：无奇度点v 无向半无向半Euler图

6、充要条件图充要条件：2个或个或0个奇数度点个奇数度点v 有向有向Eluer图：图：所有点入度所有点入度=出度出度v 有向半有向半Eluer图：图：除两个结点，每个结点入度等于出度，除两个结点，每个结点入度等于出度，一个结点的入度比出度大一个结点的入度比出度大1 1，另一个结点的入度比出度小，另一个结点的入度比出度小1 1132022-5-8n Hamiliton图：图：v 定义：定义：经过图中所有经过图中所有顶点一次且仅一次顶点一次且仅一次的回路。（的回路。（点不点不重复，初级回路重复，初级回路）v 充分条件：充分条件：若任意一对不相邻的顶点的度数之和若任意一对不相邻的顶点的度数之和n， 则则

7、G中存在中存在Hamilton回路，即回路，即G为为Hamilton图图v 必要条件：必要条件：若无向图若无向图G=是哈密顿图，则对于是哈密顿图，则对于V的的任意非空真子集任意非空真子集V1均有均有p(G V1) |V1|.n 二部图：二部图：v 定义定义：v 判定：判定：无向图无向图G=是二部图当且仅当是二部图当且仅当G中无奇数长中无奇数长度的回路度的回路142022-5-8n 平面图：平面图：v 定义：定义：v 判定：判定：v 极大平面图、极小非平面图极大平面图、极小非平面图v N(3)的极大平面图的极大平面图连通且各个面的次数均为连通且各个面的次数均为3v 欧拉公式：欧拉公式：v 连通平

8、面图连通平面图:点数点数-边数边数+面数面数=2v 非联通平面图非联通平面图:点数点数-边数边数+面数面数=p+1v 对偶图：也是平面图。对偶图：也是平面图。同构的平面图，其对偶图不一定同构的平面图，其对偶图不一定同构同构v 顶点着色问题顶点着色问题152022-5-8代数系统代数系统n 二元运算：二元运算：封闭性封闭性n 二元运算的特殊元素：二元运算的特殊元素：v 幺元（单位元）、零元、逆元幺元（单位元）、零元、逆元v |S|1时，时，ev 幺元、零元唯一性幺元、零元唯一性v 逆元：存在幺元时，元素的逆元不唯一。若运算逆元：存在幺元时，元素的逆元不唯一。若运算可结合可结合，则逆元也有唯一性则

9、逆元也有唯一性n 代数系统：代数系统：v 、，、,、的幺元、零元，有逆元的元素的逆元的幺元、零元，有逆元的元素的逆元n 半群：可结合的代数系统半群：可结合的代数系统v 封闭性封闭性v 结合性结合性162022-5-8n 独异点：含幺半群独异点：含幺半群v 封闭性封闭性v 结合性结合性v 幺元存在幺元存在n 群：群：v 判定：判定：封闭性、结合性、有幺元、可逆封闭性、结合性、有幺元、可逆v 术语：术语：v 群的阶群的阶v 元素的阶元素的阶v 元素的幂元素的幂172022-5-8v 性质：性质：G是群是群v |G|1时，除幺元外，无其他幂等元时，除幺元外，无其他幂等元v 群中无零元群中无零元v 群

10、中可解方程群中可解方程v 消去律消去律v 有限群的运算表中，每行（列）为群中元素的一个置换，有限群的运算表中，每行（列）为群中元素的一个置换，无两行（列）相同无两行（列）相同v 子群：子群：v 定义定义v 判定：判定：n Lagrange定理：定理：HG，|H|=m，|G|=n，则，则n|mv 有限群，子群的阶是父群阶的因子有限群，子群的阶是父群阶的因子v 素数阶群，无非平凡子群素数阶群，无非平凡子群v 有限群中任意元素有限群中任意元素a的阶，必为的阶，必为n的因子，且的因子，且an=ev Ex：16阶群阶群182022-5-8n 192022-5-8n 环：环：v 定义：定义：v 是阿贝尔群是阿贝尔群v 是半群是半群v #对对*可分配可分配v 性质：性质：的