离散数学08群

8.1 群及其性质
如果H是G的子群， 1）G的单位元与H的单位元关系？； 2）a∈H， a作为子群H的元素，其逆元？ a作为G的元素，其逆元？
8.1 群及其性质
如果H是G的子群，则容易得到如下结论： 1）若a，b∈H，则ab∈H； 2）G的单位元e也是H的单位元； 3）a∈H，则a-1∈H。 结论1）是由于H在G的运算下满足封闭性，2） 成立是因为：设e为G单位元，e′为H单位元，则在 G中，ee′=e′，在H中有e′=e′e′,于是 ee′=e′e′,从而由群G的消去律有e′=e。 3） 可按2）同样方式得到结论，或按如下方法讨论： 设a∈H在H中的逆元为b，则ab=e，于是，在G中变 换此式可得b=a-1。从而a-1∈H。
8.1 群及其性质
2）由ab=ba有(ab)nm=anmbnm=(an)m(bm)n=e， 于是，可令|ab|=s，且有s|nm。
由(ab)s=e有e=(ab)sn=asnbsn=bsn。
于是m|sn，而(n,m)=1，因此m|s。 同理n|s。 又由(n,m)=1，可得nm|s。 综上得，s=nm。
8.1 群及其性质
进一步，证明G的每一个元素存在逆元。 对任意aG，方程a*x=e有解c，则c即为a的 右逆元。 类似地，a有左逆元。 综上，半群<G; *>存在单位元，且G中每一 个元素可逆， 故G是一个群。
8.1 群及其性质
定理8.1 设<G; *>是一个群， 1）运算*满足消去律； 即对于任意a,b,c∈G， 则有：(1) 若a*b=a*c 则b=c； (2) 若b*a=c*a 则b=c。 2）对于任意a，b∈G，方程a*x=b, y*a=b对于未知量x、 y皆有惟一解；
LOGO
第8章 群
Group
群是抽象代数中发展最早、内容最广泛、 应用最充分的一部分，是建立其它代数结构的 基础。 群论的研究起源于对置换群的研究， 随后，发现大多数问题中，重要的不是构成群 的置换本身，而应该是集合在代数运算下的性 质，因而提出了一般群的概念，这扩大了群论 研究的对象与应用，丰富了群论研究的方法。 群论在包括计算机科学在内的自然科学中具有 重要的应用，如组合计数、编码理论、信息安 全等领域。 本章将结合群在计算机科学中的 应用，重点讨论群及其性质。
8.1 群及其性质
例8.3 下面是一些常见数集及其上运算是否构成 群的例子。 1) 整数集Z关于数的加法均构成群，常称为整数 加群。是交换群。
2) 整数集Z对于数的乘法不构成群。
3) 实数集R对普通乘法不能构成群。 4) 但R-{0}对普通乘法构成群。 5) 设S为一集合，则P(S)与集合的对称差运算构 成群，为单位元，任意A∈P(S)的逆元是其 自身。
即对于任意的a,b∈G. 有： (1) 存在唯一元素 x∈G，使得a*x=b； (2) 存在唯一元素 y∈G，使得y*a=b。 3）对于任意a，b∈G，有(a-1)-1=a, (a*b)-1=b-1*a-1
8.1 群及其性质
推论： 设<G;*>是半群， <G;*> 是群↔任意a,bG,方程a*x=b,y*a=b有解
8.1 群及其性质
由于群<G；*>满足结合律， 对任意a∈G可以把n个a的乘积记为an, n∈I+，
还规定，a0 =e。
a-n = (a-1)n, n∈ I+ 。 在群中有： aman=am+n, ama-n=am-n，
(am)n=amn 这里，n,m∈Z。
8.1 群及其性质
练习1 设<G; >是一个群,uG,在G中定义新的运 算*,使得对于任意的a,bG,a*b=a u-1 b,试证明 <G;*>也是一个群。
上述代数结构之间的关系
广群 半群 独异点 群 阿贝尔群
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)。
8.1 群及其性质
A={1,3,9,7},A上模10乘法*运算表如下
* 1 3 9 7 1 1 3 9 7 3 3 9 7 1 9 9 7 1 3 7 7 1 3 9
<A,*>是群
31=3， 32=9， 33=7， 34=1， 71=7， 72=9， 73=3， 74=1， 91=9， 92=1， 93=9， 94=1， 11=1， 12=1， 13=1， 14=1，
4个元素的阶是多少？
8.1 群及其性质
定理8.2 设a是群<G；*>中的一个阶为r的元素， k是一个整数，则有 1）ak=e当且仅当r|k； 2）a与a-1的阶相同； 3）r小于或等于群<G；*>中元素的个数。
8.1 群及其性质
例 8.6 证 明 ： 若 群 G 中 元 素 a 的 阶 是 n ， 则 H ={a0,a1,a2,„,an-1}为群。 证明 0)首先注意到，H显然非空,H中任意n个元素是互 异的，且运算封闭。 1）显然群G上的运算在H上满足结合律。
ቤተ መጻሕፍቲ ባይዱ
8.3 陪集与拉格朗日定理
8.4 正规子群与群同态基本定理
8.5 群在计算机科学中的应用
代数结构
半群 独异点 循环独异点
广群
结合律？ 单位元？ gA, s.t. aA, 有 a=gm (m N)
子半群、子独异点
i) 存在单位元e ii)G中每个元素存在逆元
群(Group)
交换律？
子群 Abel群 循环群(Cyclic group)
8.1 群及其性质
练习2 设有群〈Z6；6〉,其中Z6={0,1,2,3,4,5}, 6是模6加法,试求出群〈Z6；6〉的阶和群中每 一元素的周期。
8.1 群及其性质
8.1.3 子群 定义8.3 群G的非空子集H如果对于G的运算也成 一个群，则称H为G的子群(Subgroup)。 如果|G|>1，群G的两个平凡子群： {e}（以后常记为e）， 另一个是G自身， 其它子群，则被称为非平凡子群或真子群。
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；*>是群。
对于群<G；*>任意的二元素a，b∈G，均有a*b=b*a， 则称<G；*>为交换群或称为阿贝尔群(Abel)。
8.1 群及其性质
群是抽象代数中具有简单的二元运算的代数 结构，有时为了方便，在不致混淆的情况下，也 常把群的代数运算称作“乘法”，且把a*b简记 为ab。 另外，也常用G来表示群<G；*>。 如果一个群只包含有限个元素，则称为有限 群，否则称为无限群。 若有限群G的元素个数为 n，则称n为群G的阶，并记为|G|=n。 无限群的 阶称为无限。
B={0,1,2,3,4,5},B上模6乘法*运算表如下
* 0 1 2 0 0 0 0 1 0 1 2 2 0 2 4 3 0 3 0 4 0 4 2 0 4 2 5 0 5 4 3 2 1
3
4
0
0
3
4
0
2
3
0
5
0
5
4
3
<B,*>不是群,?
8.1 群及其性质
例8.4 设<G;*>是半群，若任意a,bG，方程a*x=b， y*a=b有解，则称<G;*>是可解的，试证明：此可 解半群<G;*>是群。 证明 首先证G有单位元。 根据题意， 给定aG,方程a*x=a（aG）有解。 设它的一个解为eG，则有a*e=a。 对于任意bG，方程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 群及其性质
8.1.2 群中元素的阶 定义8.2 设a为群G的一个元素，使an=e 的最小正整数n，称为元素a的阶（Order, 或周 期）。若这样的n不存在，则称元素a的阶为无限， 常记为∞。元素a的阶常用|a|表示。 根据定义，易知，单位元的阶为1，其它元 素的阶均大于1。在群<Z;+>中，0的阶为1，其它 元素的阶皆是无限的。R-{0}对普通乘法构成群 中，1的阶为1，-1的阶为2，其它元素的阶均为 无限。
以人造卫星仪器舱布局为例，如何求解全局最 优的一种布局方案？ 可以应用图论、群对集合的作用、轨道与等价 关系等刻划各种布局方案的同构、等价类等内 在性质，从而找出一种全局优化算法。 简化为着色问题
主要内容
1 群（群性质、子群） 2 群同态定理（正规子群、商群）
8.1 群及其性质 8.2 置换群与循环群
8.1 群及其性质
B={0,1,2,3},B上模4加法+运算表如下
+
0 0
1
1
2
2
3
3
0 1
2 3
1
2 3
2
3 0
3
0 1
0
1 2
<B,+>是群 A={1,3,9,7},A上模10乘法*运算表如下