离散数学课件离散二总复习.pptVIP

离散二总复习 代数系统 熟练掌握二元运算性质的判断及证明。 掌握代数系统的同构定义和证明，了解同构性质的保持。 熟练掌握半群,独异点和群的概念。 熟悉群的阶、群中元素的阶以及群的基本性质。 掌握子群的证明。 熟悉陪集的定义和性质。 熟悉Lagrange定理及其推论,学会简单应用。 1、群中的简单证明 主要包括： ? 群中的等式（元素相等或集合相等） ? 与元素的阶相关的命题 ? 群的其它简单命题，如交换性等。 经常使用的工具： ????? 算律：结合律、消去律? 和特殊元素相关的等式，如单位元、逆元等。? 幂运算规则? 和元素的阶相关的性质。（如：a为2阶元的充分必要条件是a-1=a等） 1、群中的简单证明 习题1： 设G为群，任取x∈G ，有x2=e, 证明G是交换群。 1、群中的简单证明 习题2： 偶数阶群中必含2阶元。 2、子群的证明 习题3： 设G为群，a是G中的2 阶元，证明G中与a可交换的元素构成G的子群。 3、拉格朗日定理应用实例 习题4： 证明6阶群中必含有3阶元。 3、拉格朗日定理应用实例 习题5： 设H1，H2分别是群G的r, s 阶子群，若r, s互素，证明H1∩H2={e}。 4、同态与同构 习题6： 定义群G上的函数f，f(x)=x-1，x∈G ，证明f为自同构当且仅当G为交换群。 课后习题 5-1: (2) 5-2: (2) (3) 5-3: (1) (3) (5) 5-4: (1) (2) (3) (5) 5-7: (1) (2) (3) (5) (8) 5-8: (2) (3) (11) 第九章：7, 17, 18 第十章：2, 8, 18 格与布尔代数 掌握格的定义，了解格的性质及格同态。 能够证明格中的等式和不等式。 能判别格L的子集S是否构成子格。 能够判断格，分配格，有补格和布尔格。 掌握布尔代数中的运算性质。 1、格的定义与性质 偏序集构成格的条件：任意二元子集都有最大下界和最小上界。? 格的实例：正整数的因子格，幂集格，子群格。 格的性质：对偶原理，格中运算律（交换、结合、幂等、吸收），保序性，分配不等式。? 格作为代数系统的定义。 习题 1. 判断下述偏序集是否构成格？如果不是说明理由。? 习题 3. 证明题 2、子格与格同态 格L的非空子集S构成L的子格的条件：S对L的两个运算封闭。? 函数f构成格同态的条件： f(a∧b)=f(a)∧f (b), f(a∨b)=f (a)∨f (b) 格同态的保序性。 习题 1. 求格L的所有子格。 3、分配格与有补格 如果格中一个运算对另一个运算是可分配的，称这个格是分配格。? 分配格的两种判别法：不存在与钻石格或五角格同构的子格；对于任意元素a,b,c,有 a∧b= a∧c且a ∨b = a∨c ? b=c.? 有界格的定义及其实例。? 格中元素的补元及其性质（分配格中补元的唯一性）? 有补格的定义? 习题 1. 判别格L是否为分配格。 4、布尔代数 会判别一个格是布尔格。? 证明布尔代数中的等式。? 了解任意有限布尔代数都与某个幂集格同构。? 习题 1. 设B,∧,∨, -, 0, 1是布尔代数，证明对于B中任意元素a, b 习题 2. 判断下述代数系统是否为格？是不是布尔代数？ 课后习题 6-1: (1) (2) (5) (7) 6-2: (2) (5) 6-3: (1) (3) (6) 6-4: (2) (6) 第十一章：1, 8, 14, 16 图的基本概念 无向图、有向图、关联与相邻、简单图、完全图、正则图、子图、补图；握手定理与推论；图的同构 通路与回路及其分类 无向图的连通性与连通度 有向图的连通性及其分类 图的矩阵表示及基本含义 图的基本概念 无向图、有向图、关联与相邻、简单图、完全图、正则图、子图、补图；握手定理与推论；图的同构 通路与回路及其分类 无向图的连通性与连通度 有向图的连通性及其分类 图的矩阵表示及基本含义 课后习题 第十四章: 1, 3, 5, 8, 10, 14, 15, 16, 21, 23, 25, 30, 31, 35, 44, 45, 46, 47, 49 欧拉图和汉密尔顿图 掌握欧拉图、半欧拉图的定义及判别定理 掌握汉密顿图、半汉密顿图的定义 能够用汉密顿图的必要条件和充分条件分别进行判断。 要特别注意的是，不能将必要条件当作充分条件，也不要将充分条件当必要条件 掌握欧拉图和汉密尔顿图的简单应用 课后习题 第十五章: 1, 2, 8, 9, 12, 13, 14, 15, 20 树 掌握无向树的定义及性质 熟