离散完整ppt课件6.1.ppt

《离散完整ppt课件6.1.ppt》由会员分享，可在线阅读，更多相关《离散完整ppt课件6.1.ppt（42页珍藏版）》请在第壹文秘上搜索。

1、1第第6章章 几个典型的代数系统几个典型的代数系统n6.1 半群与群半群与群n6.2 环与域环与域n6.3 格与布尔代数格与布尔代数2n半群与独异点半群与独异点半群定义与性质半群定义与性质交换半群与独异点交换半群与独异点半群与独异点的子代数和积代数半群与独异点的子代数和积代数半群与独异点的同态半群与独异点的同态n群群群的定义与性质群的定义与性质子群与群的直积子群与群的直积循环群循环群置换群置换群6.1 半群与群半群与群3半群的定义与实例半群的定义与实例定义定义 设设 V=是代数系统，是代数系统，o为二元运算，如果为二元运算，如果 运算是可结合的，则称运算是可结合的，则称 V 为为半群半群.实例

2、实例（1）,都是半群，都是半群，+是是 普通加法普通加法.（2）设）设 n 是大于是大于1的正整数，的正整数，和和都是半都是半 群，其中群，其中+和和 分别表示矩阵加法和矩阵乘法分别表示矩阵加法和矩阵乘法.（3）为半群，其中为半群，其中 为集合的对称差运算为集合的对称差运算.（4）为半群，其中为半群，其中 Zn=0,1,n 1，为模为模 n 加法加法.（5）为半群，其中为半群，其中 为函数的复合运算为函数的复合运算.（6）为半群，其中为半群，其中R*为非零实数集合，为非零实数集合，运算定义运算定义 如下：如下：x,yR*,x y=y4元素的幂运算性质元素的幂运算性质元素的元素的幂运算定义幂运算

3、定义 设设V=为半群，对任意为半群，对任意 xS，规定：，规定：x1=xxn+1=xn x,nZ+幂运算规则：幂运算规则：xn xm=xn+m(xn)m=xnm m,nZ+证明方法：数学归纳法证明方法：数学归纳法5特殊的半群特殊的半群定义定义 设设V=是半群是半群(1)若若 运算是可交换的，则称运算是可交换的，则称V 为为交换半群交换半群.(2)若若 eS 是关于是关于 运算的单位元，则称运算的单位元，则称 V 是是含幺含幺半群半群，也叫做，也叫做 独异点独异点.独异点独异点 V 记作记作 V=6独异点的幂独异点的幂独异点的幂运算定义独异点的幂运算定义 x0=e xn+1=xn x,nN幂运算

4、规则幂运算规则 xn xm=xn+m(xn)m=xnm m,nN 7交换半群和独异点的实例交换半群和独异点的实例例例1（1）,都是交都是交 换半群，也是独异点，换半群，也是独异点，+是普通加法是普通加法.（2）设）设 n 是大于是大于 1 的正整数，的正整数，和和都是都是 独异点，其中独异点，其中+和和 分别表示矩阵加法和矩阵乘法分别表示矩阵加法和矩阵乘法.加加 法构成交换半群，乘法不是交换半群法构成交换半群，乘法不是交换半群.（3）为交换半群和独异点，其中为交换半群和独异点，其中 为集合的对为集合的对 称差运算称差运算.（4）为交换半群与独异点，其中为交换半群与独异点，其中 Zn=0,1,n

5、 1，为模为模 n 加法加法.（5）为独异点，不是交换半群，其中为独异点，不是交换半群，其中 为函数的为函数的 复合运算复合运算.8半群与独异点的子代数半群与独异点的子代数定义定义 半群的子代数称为半群的子代数称为子半群子半群，独异点的子代数称，独异点的子代数称为为子独异点子独异点判断方法判断方法 设设 V=为半群，为半群，T 是是 V 的子半群当且仅当的子半群当且仅当 T 对对 o 运算封闭运算封闭.设设 V=为独异点，为独异点，T 是是 V 的的子独异点当且仅当子独异点当且仅当 T 对对 o 运算封闭，且运算封闭，且 e T 实例：实例：,是是的子半群，的子半群，是是的子独异点，的子独异点

6、，不是不是的子独异点的子独异点.9半群与独异点的积代数半群与独异点的积代数定义定义 设设 V1=，V2=是半群是半群(或独异或独异点点)，令，令S=S1S2，定义，定义 S 上的上的 运算如下：运算如下：,S，=称称 为为 V1 和和 V2 的的 积半群积半群（直积直积），记作），记作 V1V2.若若 V1=和和 V2=是是独独异点，则异点，则 V1V2 =S1S2,也是独异也是独异点点,称为独异点的称为独异点的 积独异点积独异点(直积直积).10半群和独异点的同态半群和独异点的同态定义定义 (1)设设V1=，V2=是半群，是半群，：S1S2.若对任意的若对任意的 x,yS1有有 (x y)=

7、(x)(y)则称则称 为半群为半群 V1 到到 V2 的的同态映射同态映射，简称，简称 同态同态.(2)设设V1=，V2=是独异点，是独异点，:S1S2.若对任意的若对任意的 x,yS1有有 (x y)=(x)(y)且且 (e1)=e2,则称则称 为独异点为独异点 V1 到到 V2 的的同态映射同态映射，简称，简称 同态同态.11同态的实例同态的实例例例2 设半群设半群 V1=，独异点，独异点 V2=.其中其中 为为矩阵乘法，矩阵乘法，e 为为 2 阶单位矩阵阶单位矩阵,令令 ：SS,是半群是半群 V1 的自同的自同态态,不是独异点不是独异点 V2 的自同态，因为它没有将的自同态，因为它没有将

8、 V2 的单的单位元映到位元映到 V2 的单位元的单位元.R,|00dadaS 00000ada 12群的定义与性质群的定义与性质n群的定义与实例群的定义与实例n群中的术语群中的术语有限群、无限群与群的阶有限群、无限群与群的阶Abel群群群中元素的幂群中元素的幂元素的阶元素的阶n群的性质群的性质幂运算规则、幂运算规则、群方程的解群方程的解消去律消去律群的运算表的排列群的运算表的排列13群的定义与实例群的定义与实例定义定义 设设是代数系统，是代数系统，为二元运算为二元运算.如果如果 运算是可结合的，存在单位元运算是可结合的，存在单位元 eG，并且对，并且对 G 中中的任何元素的任何元素 x 都有

9、都有 x 1G，则称，则称 G 为为 群群.群的实例群的实例(1),是群；是群；,不是群不是群.(2)是群，而是群，而不是群不是群.(3)是群，是群，为对称差运算为对称差运算.(4)，是群，是群.Zn=0,1,n 1，为模为模 n 加加.14Klein四元群四元群设设G=e,a,b,c，G上的运算由下表给出，上的运算由下表给出，称为称为 Klein四元群四元群 e a b c e a b c e a b c a e c b b c e a c b a e 运算表特征：运算表特征：对称性对称性-运算可交换运算可交换 主对角线元素都是幺元主对角线元素都是幺元 -每个元素是自己的逆元每个元素是自己的

10、逆元 a,b,c 中任两个元素运算中任两个元素运算 都等于第三个元素都等于第三个元素.15群中的术语群中的术语若群若群 G 是有穷集，则称是有穷集，则称 G 是是有限群有限群，否则称为，否则称为无限群无限群.群群 G 的基数称为群的基数称为群G的的 阶阶有限群有限群 G 的阶记作的阶记作|G|.若群若群G中的二元运算是可交换的，则称中的二元运算是可交换的，则称G为为交换交换群群 或或 阿贝尔阿贝尔(Abel)群群.16实例实例 和和 是无限群是无限群 是有限群，也是是有限群，也是 n 阶群阶群 Klein四元群四元群 G=e,a,b,c是是 4 阶群阶群 上述群都是交换群上述群都是交换群 n

11、阶阶(n2)实可逆矩阵集合关于矩阵乘法构成的群实可逆矩阵集合关于矩阵乘法构成的群是非交换群是非交换群.17群中的术语（续）群中的术语（续）实例实例 在在中有中有 2 3=(2 1)3=13=1 1 1=0 在在 中有中有 (2)3=23=2+2+2=6 定义定义 设设G是群，是群，xG，nZ，则，则 x 的的 n 次幂次幂 xn 定义为定义为 Z0,)(0011 nnnmxnxxnexmnn18设设G是群，是群，xG，使得等式，使得等式 xk=e 成立的最小正成立的最小正整数整数 k 称为称为 x 的的阶（或周期）阶（或周期），记作，记作|x|=k，称，称 x为为 k 阶元阶元.若不存在这样的

12、正整数若不存在这样的正整数 k，则称，则称 x 为为无限阶元无限阶元.群中的术语（续）群中的术语（续）在在中，中，2 和和 4 是是 3 阶元，阶元，3 是是 2 阶元，阶元，1 和和 5 是是 6 阶元，阶元，0 是是 1 阶元阶元 在在中，中，0 是是 1 阶元，其它整数的阶都不存在阶元，其它整数的阶都不存在.19群的性质群的性质-幂运算规则幂运算规则定理定理1 设设 G 为群为群,则则 G 中的幂运算满足：中的幂运算满足：(1)xG，(x 1)1=x.(2)x,yG，(xy)1=y 1x 1.(3)xG，xnxm=xn+m，n,mZ.(4)xG，(xn)m=xnm，n,mZ.注意注意 (

13、xy)n=(xy)(xy)(xy),是是 n 个个xy 运算，运算，G为为 交换群，才有交换群，才有(xy)n=xnyn.1112111121.).(xxxxxxxnnn20群的性质群的性质-群方程存在唯一解群方程存在唯一解定理定理2 G为群，为群，a,bG，方程，方程 ax=b 和和 ya=b 在在G中有解且仅有惟一解中有解且仅有惟一解.a 1b 是是 ax=b的解的解.ba 1 是是 ya=b 的唯一解的唯一解.例例 设设 G=，其中，其中 为对称差为对称差.群方程群方程a X=，Y a,b=b的解的解 X=a 1=a=a，Y=b a,b 1=b a,b=a 21群的性质群的性质-消去律消

14、去律定理定理3 G 为群，则为群，则G适合消去律，即适合消去律，即 a,b,cG 有有(1)若若 ab=ac，则，则 b=c.(2)若若 ba=ca，则，则 b=c.例例 设设 G=a1,a2,an 是是 n 阶群，令阶群，令 aiG=ai aj|j=1,2,n 证明证明 aiG=G.证证 由群中运算的封闭性有由群中运算的封闭性有 aiG G.假设假设aiG G，即，即|aiG|n.必有必有aj,akG使得使得 ai aj=ai ak（jk）由消去律得由消去律得 aj=ak,与与|G|=n 矛盾矛盾.22群的性质群的性质-运算表排列规则运算表排列规则定理定理4 设设 G 为有限群，则为有限群，

15、则 G 的运算表中每行每列的运算表中每行每列都是都是 G 中元素的一个置换，且不同的行（或列）中元素的一个置换，且不同的行（或列）的置换都不相同的置换都不相同.注意：必要条件，用于判断一个运算表不是群注意：必要条件，用于判断一个运算表不是群.a b c d a b c d b c d a b a c d c d b a d b a c a b c d a b c d a b c d c d a b b c d a d a b c 23子群的定义子群的定义定义定义 设设 G 是群，是群，H 是是 G 的非空子集，如果的非空子集，如果 H 关关于于 G 中的运算构成群，则称中的运算构成群，则称 H

16、 是是 G 的的子群子群,记作记作 HG.若若 H 是是 G 的子群，且的子群，且 H G，则称，则称 H 是是 G 的的真子群真子群，记作，记作 HG.实例实例 nZ（n是自然数）是整数加群是自然数）是整数加群 的子的子群群.当当 n1 时时,nZ 是是 Z 的真子群的真子群.对任何群对任何群 G 都存在子群都存在子群.G 和和 e 都是都是 G 的子群，的子群，称为称为 G 的的平凡子群平凡子群.24子群判定定理子群判定定理判定定理判定定理 设设 G 为群，为群，H 是是 G 的非空子集的非空子集.H 是是 G 的子群当的子群当且仅当且仅当 x,yH 有有 xy 1H.证明证明 H 为为 G 的子群的步骤：的子群的步骤：通过给出通过给出 H 中的元素说明中的元素说明 H 是是 G 的非空子集的非空子集 任取任取 x,y属于属于 H，证明，证明 xy-1属于属于H25重要子群重要子群生成子群生成子群定义定义 设设 G 为群，为群，aG，令，令 H=ak|kZ，则则 H 是是 G 的子群，称为的子群，称为由由 a 生成的子群，记作生成的子群，记作.证证 首先由首先由 a 知道知道.任取