离散数学08群课件.pptVIP

第8章 群 Group 群是抽象代数中发展最早、内容最广泛、应用最充分的一部分，是建立其它代数结构的基础。 群论的研究起源于对置换群的研究，随后，发现大多数问题中，重要的不是构成群的置换本身，而应该是集合在代数运算下的性质，因而提出了一般群的概念，这扩大了群论研究的对象与应用，丰富了群论研究的方法。 群论在包括计算机科学在内的自然科学中具有重要的应用，如组合计数、编码理论、信息安全等领域。 本章将结合群在计算机科学中的应用，重点讨论群及其性质。 以人造卫星仪器舱布局为例，如何求解全局最优的一种布局方案？ 可以应用图论、群对集合的作用、轨道与等价关系等刻划各种布局方案的同构、等价类等内在性质，从而找出一种全局优化算法。 ?简化为着色问题 主要内容 1 群（群性质、子群） 2 群同态定理（正规子群、商群） 上述代数结构之间的关系 8.1 群及其性质 8.1.1 群及其性质 定义8.1 设G；*为代数结构，其中G是一个非空集合，*是G上的一个二元运算，若 1）运算*满足结合律，即?a，b，c∈G， (a*b)*c=a*(b*c)， 2）运算*存在单位元e∈G：e*a=a*e=a，?a∈G， 3）对任意a∈G，存在逆元a-1∈G，使得a*a-1=a-1*a=e， 则称代数结构G；*是一个群(Group)。 对于群G；*任意的二元素a，b∈G，均有a*b=b*a，则称G；*为交换群或称为阿贝尔群(Abel)。 8.1 群及其性质 群是抽象代数中具有简单的二元运算的代数结构，有时为了方便，在不致混淆的情况下，也常把群的代数运算称作“乘法”，且把a*b简记为ab。 另外，也常用G来表示群G；*。 如果一个群只包含有限个元素，则称为有限群，否则称为无限群。 若有限群G的元素个数为n，则称n为群G的阶，并记为|G|=n。 无限群的阶称为无限。 8.1 群及其性质 例8.2 设S=R-{-1}，S上定义运算*： a*b=a+b+ab，试证明S; *是群。 证明 从以下几方面进行证明： 0) 运算*在S上封闭,即S; * 是代数结构： 任意a，b∈S，有a*b=a+b+ab∈R，且a≠-1， b≠-1。 若a*b=-1即a+b+ab=-1，则a=-1或b=-1，与题 设矛盾，故a*b≠-1. 所以a*b∈S，即运算*在S上封闭。 8.1 群及其性质 1) 运算*满足结合律： 任意a，b，c∈S，有 (a*b)*c=(a+b+ab)*c=a+b+ab+c+(a+b+ab)c =a+b+c+ab+ac+bc+abc,且 a*(b*c)=a*(b+c+bc)=a+b+c+bc+a(b+c+bc) =a+b+c+ab+ac+bc+abc, 所以，(a*b)*c=a*(b*c)，即*满足结合律。 2) 存在单位元： 对任意a，b∈S，若a*b=a即a+b+ab=a， b（1+a）=0，注意到a≠-1，故b=0∈S，从而有a*0=a。又0*a=0+a+0·a=a,所以0为单位元。 8.1 群及其性质 3) 每个元素存在逆元： 对于任意a∈S, 若a*b=0即a+b+ab=0, b=(-a)/(1+a)∈S，即 有a*(-a)/(1+a)=0 又(-a)/(1+a)*a=(-a)/(1+a)+a+(-a)·a/(1+a) –a(1+a)/(1+a)+a=0 故(-a)/(1+a)为a之逆元。 综上知S；*是群。 8.1 群及其性质 例8.3 下面是一些常见数集及其上运算是否构成群的例子。 整数集Z关于数的加法均构成群，常称为整数加群。是交换群。 整数集Z对于数的乘法不构成群。 实数集R对普通乘法不能构成群。 但R-{0}对普通乘法构成群。 设S为一集合，则P(S)与集合的对称差运算构成群，?为单位元，任意A∈P(S)的逆元是其自身。 8.1 群及其性质 例8.4 设G;*是半群，若任意a,b?G，方程a*x=b，y*a=b有解，则称G;*是可解的，试证明：此可解半群G;*是群。 证明 首先证G有单位元。 根据题意， 给定a?G,方程a*x=a（a?G）有解。 设它的一个解为e?G，则有a*e=a。 对于任意b?G，方程y*a=b有解，设解为c，则有c*a=b。 于是，b*e=(c*a)*e=c*(a*e)=c*a=b。因此e为G的右单位元。 类似地，G有左单位元 。 所以，G存在单位元，不妨设为e。 8.1 群及其性质 进一步，证明G的每一个元素存在逆元。 对任意a?G，方程a*x=e