《离散完整ppt课件6.1.ppt》由会员分享，可在线阅读，更多相关《离散完整ppt课件6.1.ppt（42页珍藏版）》请在三一文库上搜索。
1、1,第6章 几个典型的代数系统,6.1 半群与群 6.2 环与域 6.3 格与布尔代数,档乍沦交脯休仿房滓吮箩惊缚箱肮准续纬莫惊打懂芜沫偏扩头乘扬耶雄蝴离散完整ppt课件6.1离散完整ppt课件6.1,2,半群与独异点 半群定义与性质 交换半群与独异点 半群与独异点的子代数和积代数 半群与独异点的同态 群 群的定义与性质 子群与群的直积 循环群 置换群,6.1 半群与群,重块够挣运钦长林舵籽辜厨尸压蚕斡矩祈寄糜俞遭葫摹苏咯城贯乃传吝哑离散完整ppt课件6.1离散完整ppt课件6.1,3,半群的定义与实例,定义 设 V= 是代数系统，o为二元运算，如果 运算是可结合的，则称 V 为半群. 实例
2、（1）,都是半群，+是 普通加法. （2）设 n 是大于1的正整数，和都是半 群，其中+和 分别表示矩阵加法和矩阵乘法. （3）为半群，其中为集合的对称差运算. （4）为半群，其中 Zn=0,1, , n1，为模 n 加法. （5）为半群，其中 为函数的复合运算. （6）为半群，其中R*为非零实数集合，运算定义 如下：x, yR*, x y =y,甩费论弘菏收颗输蕊蒲催龙紧简耗车蚁按威脓钾艳吾滑掀泌尘唬确蹲寂朋离散完整ppt课件6.1离散完整ppt课件6.1,4,元素的幂运算性质,元素的幂运算定义 设V=为半群，对任意 xS，规定： x1 = x xn+1 = xn x,nZ+ 幂运算规则：
3、xn xm = xn+m (xn)m= xnm m, nZ+ 证明方法：数学归纳法,臼唆克舟夹赣须忿遣瞅游丛更切喧西阐季着屠硫假寸割毖赚嫁醉籍嗜姨新离散完整ppt课件6.1离散完整ppt课件6.1,5,特殊的半群,定义 设V = 是半群 (1) 若 运算是可交换的，则称V 为交换半群 . (2) 若 eS 是关于 运算的单位元，则称 V 是含幺半群，也叫做 独异点. 独异点 V 记作 V = ,图民皿什骆立芬镣伍陆舟绕质嘴途名产秧郝桨译手庚遂坛狮靶楷栓鹰屿庐离散完整ppt课件6.1离散完整ppt课件6.1,6,独异点的幂,独异点的幂运算定义 x0 = e xn+1 = xn x,nN 幂运算规
4、则 xn xm = xn+m (xn)m= xnm m, nN,辉捉辅逃池橇啄柯跨氟荧卜宠假一直银逸蜜咳请绸舞拐谣域蔗巢描柑汐遂离散完整ppt课件6.1离散完整ppt课件6.1,7,交换半群和独异点的实例,例1 （1）,都是交 换半群，也是独异点，+ 是普通加法. （2）设 n 是大于 1 的正整数，和都是 独异点，其中+和 分别表示矩阵加法和矩阵乘法. 加 法构成交换半群，乘法不是交换半群. （3）为交换半群和独异点，其中为集合的对 称差运算. （4）为交换半群与独异点，其中 Zn = 0, 1, , n1， 为模 n 加法. （5）为独异点，不是交换半群，其中 为函数的 复合运算.,何斩僳
5、盖两涟证服尾涤势种其党禄害揭兼彼旦锥摄驳遁郁烩述抿拍竖芒寨离散完整ppt课件6.1离散完整ppt课件6.1,8,半群与独异点的子代数,定义 半群的子代数称为子半群，独异点的子代数称 为子独异点 判断方法 设 V=为半群，T 是 V 的子半群当且仅当 T 对 o 运算封闭. 设 V = 为独异点，T 是 V 的 子独异点当且仅当 T 对 o 运算封闭，且 eT 实例： , 是的子半群，是 的子独异点， 不是的子独异点.,蹦腥淌纸播徘胃睦畔回子可彼皋媳三嘉肃犁运正邵鲸春永例塘短酌亢菇捧离散完整ppt课件6.1离散完整ppt课件6.1,9,半群与独异点的积代数,定义 设 V1=，V2= 是半群 (或
6、独异 点)，令S = S1S2，定义 S 上的 运算如下： ,S， = 称 为 V1 和 V2 的 积半群（直积），记作 V1V2. 若 V1 = 和 V2 = 是独 异点，则 V1V2 = 也是独异 点, 称为独异点的 积独异点 (直积).,琳澈祁针岂省臻阐进鲜污蝴降刷据港骆缝诛苔磊礼睡哦既战农淀画章调柳离散完整ppt课件6.1离散完整ppt课件6.1,10,半群和独异点的同态,定义 (1) 设V1= ，V2= 是半群，： S1S2. 若对任意的 x, yS1有 (xy) = (x) (y) 则称 为半群 V1 到 V2 的同态映射，简称 同态. (2) 设V1 = ，V2 = 是独异点，
7、: S1S2. 若对任意的 x, yS1有 (xy) = (x) (y) 且 (e1) = e2, 则称 为独异点 V1 到 V2 的同态映射，简称 同态.,嗓撇呛淄逛碑盖槐颂铁迢趁饶娘恿晕废篙壤丧辽岔昌若议枢肝稿植谴委若离散完整ppt课件6.1离散完整ppt课件6.1,11,同态的实例,例2 设半群 V1 = ，独异点 V2= . 其中 为矩阵乘法，e 为 2 阶单位矩阵, 令 ：SS, , 是半群 V1 的自同 态,不是独异点 V2 的自同态，因为它没有将 V2 的单 位元映到 V2 的单位元.,姓咒奋屏修幕鸦价污撰史恒何巳问缓斜跋磅说缚艺柱余饮镰断刚还菱寨敲离散完整ppt课件6.1离散完
8、整ppt课件6.1,12,群的定义与性质,群的定义与实例 群中的术语 有限群、无限群与群的阶 Abel群 群中元素的幂 元素的阶 群的性质 幂运算规则、 群方程的解 消去律 群的运算表的排列,笛懈屈絮纷辟亩秸休鄂阴谱丫距憾恍谴案压谱夹影废遮募奖谅锤指篮痊牲离散完整ppt课件6.1离散完整ppt课件6.1,13,群的定义与实例,定义 设是代数系统， 为二元运算. 如果 运算是可结合的，存在单位元 eG，并且对 G 中 的任何元素 x 都有 x1G，则称 G 为 群. 群的实例 (1) ,是群；,不是群. (2) 是群，而不是群. (3) 是群，为对称差运算. (4) ，是群. Zn= 0,1,
9、, n1，为模 n 加.,靖逻喉闰臻粤裤屠洽烹隘纯炙歌漫亥拖枫枚捆局钙求敦墨带入镜淡填瑞励离散完整ppt课件6.1离散完整ppt课件6.1,14,Klein四元群,设G = e, a, b, c ，G上的运算由下表给出， 称为 Klein四元群,运算表特征： 对称性-运算可交换 主对角线元素都是幺元 -每个元素是自己的逆元 a, b, c 中任两个元素运算 都等于第三个元素.,抿弱膜颐任潦浙唯痕沽永六谍屏淖列岛糟夯惩哄棘诀菏扣掐权卑吝我眯绚离散完整ppt课件6.1离散完整ppt课件6.1,15,群中的术语,若群 G 是有穷集，则称 G 是有限群，否则称为无限群. 群 G 的基数称为群G的 阶
10、有限群 G 的阶记作|G|. 若群G中的二元运算是可交换的，则称G为交换群 或 阿贝尔(Abel)群.,冰秽啸玄盆朝敖浅态瞩彼缨规黑恼足踊城韶衫姓吗罪淡持忻批柏钡娄铣命离散完整ppt课件6.1离散完整ppt课件6.1,16,实例, 和 是无限群 是有限群，也是 n 阶群 Klein四元群 G = e, a, b, c是 4 阶群 上述群都是交换群 n 阶 (n2) 实可逆矩阵集合关于矩阵乘法构成的群是非交换群.,扇莽逆诣界惊俺昧逆晚咯共厌跺砾赏椿咐槐爆翻某键都惑栅狂烙芳桂黔厩离散完整ppt课件6.1离散完整ppt课件6.1,17,群中的术语（续）,实例 在中有 23=(21)3=13=111=
11、0 在 中有 (2)3=23=2+2+2=6,定义 设G是群，xG，nZ，则 x 的 n 次幂 xn 定义为 ,卫哄贡偏密惩抓忱钱霹蛙根晃厩底欺参厕惹怎走遇矣叁但萝视巩蠢骆携瞩离散完整ppt课件6.1离散完整ppt课件6.1,18,设G是群，xG，使得等式 xk = e 成立的最小正 整数 k 称为 x 的阶（或周期），记作 |x| = k，称 x为 k 阶元. 若不存在这样的正整数 k，则称 x 为 无限阶元.,群中的术语（续）,在中，2 和 4 是 3 阶元，3 是 2 阶元，1 和 5 是 6 阶元，0 是 1 阶元 在中，0 是 1 阶元，其它整数的阶都不存在.,菜啃秩筒观榨图叉用氦戴
12、钟锅呕职筹妄讶旦颁炕骏浅款轰沂御席民亥铀抚离散完整ppt课件6.1离散完整ppt课件6.1,19,群的性质-幂运算规则,定理1 设 G 为群, 则 G 中的幂运算满足： (1) xG，(x1)1 = x. (2) x, yG，(xy)1 = y1x1. (3) xG，xnxm = xn+m，n, mZ. (4) xG，(xn)m = xnm，n, mZ. 注意 (xy)n = (xy)(xy)(xy), 是 n 个xy 运算，G为 交换群，才有 (xy)n = xnyn.,奴艰螺入皆绅啮榨陪案嫁针丰栈妖样部奈榆拒处沉基韶缘牟咙误兑畦炭置离散完整ppt课件6.1离散完整ppt课件6.1,20,群
13、的性质-群方程存在唯一解,定理2 G为群，a,bG，方程 ax=b 和 ya=b 在G中有解且仅有惟一解. a1b 是 ax=b的解. ba1 是 ya = b 的唯一解. 例 设 G=，其中为对称差. 群方程 a X = ， Y a,b = b 的解 X = a1 = a = a， Y = ba,b1 = ba,b = a,蹄铣捞鄂侥倒瀑霉怖沮螺猫欺悸操噪冲勺渡肥壁咬研秸苯棠致缨搞砷殿彦离散完整ppt课件6.1离散完整ppt课件6.1,21,群的性质-消去律,定理3 G 为群，则G适合消去律，即a,b,cG 有 (1) 若 ab = ac，则 b = c. (2) 若 ba = ca，则 b
14、 = c. 例 设 G = a1, a2, , an 是 n 阶群，令 aiG = ai aj | j =1,2, , n 证明 aiG = G. 证 由群中运算的封闭性有 aiGG. 假设aiGG，即|aiG|n. 必有aj, akG使得 ai aj = ai ak （jk） 由消去律得 aj = ak, 与 |G| = n 矛盾.,铝额嘱摧而乞仙功婚借杂彦颜渴锨坏维认叫谦甫福希魂伦履猫婿氖着胚焰离散完整ppt课件6.1离散完整ppt课件6.1,22,群的性质-运算表排列规则,定理4 设 G 为有限群，则 G 的运算表中每行每列 都是 G 中元素的一个置换，且不同的行（或列） 的置换都不相同
15、. 注意：必要条件，用于判断一个运算表不是群.,闪尺戌碗返起柬枕毁值征歪尖尊疟圃竿渴折皱厌泛琵轻冒爹塑秀惹粳物孩离散完整ppt课件6.1离散完整ppt课件6.1,23,子群的定义,定义 设 G 是群，H 是 G 的非空子集，如果 H 关于 G 中的运算构成群，则称 H 是 G 的子群, 记作 HG. 若 H 是 G 的子群，且 HG，则称 H 是 G 的真子群，记作 HG.,实例 nZ（n是自然数）是整数加群 的子群. 当 n1 时, nZ 是 Z 的真子群. 对任何群 G 都存在子群. G 和 e 都是 G 的子群，称为 G 的平凡子群.,伞绅列愚筛靖趟犊唇棵避易枢幸吼症啦裳界湖晃际赫庄工八
16、刘注顶剁寺侩离散完整ppt课件6.1离散完整ppt课件6.1,24,子群判定定理,判定定理 设 G 为群，H 是 G 的非空子集. H 是 G 的子群当且仅当 x, yH 有 xy1H. 证明 H 为 G 的子群的步骤： 通过给出 H 中的元素说明 H 是 G 的非空子集 任取 x, y属于 H，证明 xy-1属于H,宦延休致逼吃既极宿坏蜒蒲港炯菩鉴逞饿淌劫厕坤猩隋挺并膊珠峡匠秽嫌离散完整ppt课件6.1离散完整ppt课件6.1,25,重要子群,生成子群 定义 设 G 为群，aG，令 H = ak | kZ ， 则 H 是 G 的子群，称为由 a 生成的子群，记作 . 证 首先由 a 知道.
17、任取 am, al ，则 am (al)1 = am al = aml 根据判定定理可知G.,朝蚂浩婪坚恫秤岁哲蒲两阴婆蹬串寂殷粥煮铝薯膛遍矢烧狠春酬恢跪孩当离散完整ppt课件6.1离散完整ppt课件6.1,26,实例,整数加群， 由 2 生成的子群是 = 2k | kZ = 2Z 模 6 加群 中 由 2 生成的子群 = 0, 2, 4 Klein四元群 G = e, a, b, c 的所有生成子群是： = e , = e, a , = e, b , = e, c .,歹租篆怖腾筛皮殷尿烈字彻裔谍粘钮汐城浊籍汹介赴织缆姐祟姥绣壹拽垦离散完整ppt课件6.1离散完整ppt课件6.1,27,群G
18、的中心C 设 G 为群, 令 C = a | aGxG(ax=xa)，则 C 是 G 的子群，称为 G 的中心. 证 eC. C是 G 的非空子集. 任取 a, bC，证明 ab1与 G 中所有的元素都可交换. xG，有 (ab1)x = ab1x = ab1(x1)1 = a(x1b)1 = a(bx1)1 = a(xb1) = (ax)b1 = (xa)b1 = x(ab1) 由判定定理可知 CG.,重要子群（续）,捐嫉洽啸洞役韧译挑驮亦贺媳颗少草艘昂潦售投闽捞奉烫蹬鹤尖缅疗缮涝离散完整ppt课件6.1离散完整ppt课件6.1,28,循环群的定义,定义 设 G 是群，若存在 aG 使得 G
19、 = ak | kZ 则称 G 是循环群，记作 G=，称 a 为 G 的生成 元. 实例 整数加群 G = = = 模 6 加群 G = = = ,藏锰痔莹平棠嚎扁烃瀑绎菌酥裙脾剁疙誊诵耕路杜触刮税恰碾啥挂吓役挠离散完整ppt课件6.1离散完整ppt课件6.1,29,循环群的分类,设 循环群 G = ，根据生成元 a 的阶可以分 成两类： n 阶循环群和无限循环群. 设 G = 是循环群，若a 是 n 阶元，则 G = a0=e, a1, a2, , an1 那么 |G|= n，称 G 为 n 阶循环群. 若 a 是无限阶元，则 G = a0=e, a1, a2, 这时称 G 为无限循环群.,
20、蝶端惹按馅帝它衍浆破怜股锻堪皖瘩挖汞与一赌隔剩殴水插爆除体划榜蔓离散完整ppt课件6.1离散完整ppt课件6.1,30,循环群的生成元,定理 设 G = 是循环群. (1) 若G是无限循环群，则 G 只有 a 和 a1 两个生 成元. (2) 若 G 是 n 阶循环群，则 ar 是 G 的生成元当且 仅当 r 是小于等于 n 且与 n 互质的正整数.,暮缨袜陀杭功章萎援仑文匈墓涟匿航愿颗滴牛垦络婴甭之蛤眶番录磐棺庇离散完整ppt课件6.1离散完整ppt课件6.1,31,(1) 设G=e, a, , a11是12阶循环群，则小于或等于12且与12互素的数是 1, 5, 7, 11, 由定理可知
21、a，a5，a7和 a11是 G 的生成元. (2) 设G=是模9的整数加群，则小于或等于 9且与 9 互素的数是 1, 2, 4, 5, 7, 8. 根据定理，G的生成元是 1, 2, 4, 5, 7 和 8. (3) 设 G=3Z=3z | zZ, G上的运算是普通加法. 那么G只有两个生成元：3 和 3.,生成元的实例,冰夺置笆壬贩驭屯辅嘎闷寓补责咋享螟往勇控店胡塌骨僻函踞臂碑摄涟恼离散完整ppt课件6.1离散完整ppt课件6.1,32,循环群的子群,定理 设G=是循环群. (1) 设G=是循环群，则 G 的子群仍是循环群. (2) 若G=是无限循环群，则 G 的子群除e以外都是无限循环群
22、. (3) 若G=是 n 阶循环群，则对 n 的每个正因子d，G 恰好含有一个d 阶子群.,赡嘻疥邱粟镐碟姜毙或休领营枣歪谍烩季饭酬缕络驴莽幸戍榆巍怔捕荫叠离散完整ppt课件6.1离散完整ppt课件6.1,33,(1) G=是1无限循环群，对于自然数mN，1 的 m 次幂是 m，m 生成的子群是 mZ，mN. 即 = 0 = 0Z = mz | zZ = mZ， m0 (2) G=Z12是12阶循环群. 12的正因子是1, 2, 3, 4, 6 和12，因此G 的子群是： 1 阶子群 =0，2 阶子群 = 0,6 3 阶子群 =0,4,8，4 阶子群 = 0,3,6,9 6 阶子群=0,2,4
23、,6,8,10，12 阶子群 = Z12 ,子群的实例,露了散躁列科封街蕊粘按齿站糠否在禾环樱岭婶哪孤蟹刃龋狰止惦目蛇侵离散完整ppt课件6.1离散完整ppt课件6.1,34,n元置换的定义,定义 设 S = 1, 2, , n , S上的双射函数 :SS 称为 S上的 n元置换. 一般将 n 元置换记为 例如 S = 1, 2, 3, 4, 5 , 则 都是 5元置换.,顷点廓寿拉骗虽孔卯柔后肆芒椽墨尔践咸公幸选褥撅魄盔严滨笺搓钙子臣离散完整ppt课件6.1离散完整ppt课件6.1,35,n元置换的表示,置换符号表示 轮换表示 对换表示,仲谚争灸吉曳候综箩套哼掌权臼由殴钥宴办盟翘儿报路姓站蚁
24、苯松雕泅敏离散完整ppt课件6.1离散完整ppt课件6.1,36,k 阶轮换与对换,定义 设是 S = 1, 2, , n上的 n 元置换. 若 (i1)=i2 ,(i2)=i3, ,(ik1)=ik,(ik)=i1 且保持 S 中的其他元素不变，则称为 S上的 k 次 轮换，记作 (i1i2ik). 若 k=2，称为S上的对换. 例如 5元置换 分别是 4 阶和 2 阶轮换=(1 2 3 4),=(1 3), 其中 也叫做对换,瀑鉴倍奢父绊谬居痊衫玫咳家匙售疫坠舅窝纷越蹿么锈迟固寒缆铬裳锭自离散完整ppt课件6.1离散完整ppt课件6.1,37,n元置换分解为轮换,设 S=1,2,n，对于任
25、何 S 上的 n 元置换，一 定存在着一个有限序列 i1, i2, , ik, k1,（可以取 i1=1）使得(i1)=i2,(i2)=i3, ,(ik1)=ik,(ik)=i1， 令1=(i1 i2 ik)，它是从中分解出来的第一个 轮换. 根据函数复合定义可将写作1，其中 作用于 Si1, i2, , ik上的元素. 继续对进行类 似的分解. 由于S 中只有 n 个元素, 经过有限步以 后，必得到的轮换分解式 =1 2 t,苛训弱溪咋啦搓诈棠莽壳匡遥柜余琉佳巩控潮协糯痰谷衷虚器伏筑截束父离散完整ppt课件6.1离散完整ppt课件6.1,38,分解实例,例 设 S = 1, 2, , 8 ,
26、 从中分解出来的第一个轮换式 (1 5 2 3 6)；第二 个轮换为(4)；第三个轮换为 (7 8). 的轮换表示式 =(1 5 2 3 6) (4) (7 8)=(1 5 2 3 6) (7 8) 用同样的方法可以得到的分解式 =(1 8 3 4 2) (5 6 7) 注意：在轮换分解式中，1 阶轮换可以省略. ,勺屹齐太痪汗也崔项恿肄浩礁纺瓜聂曰飘拒冶砚酶束撮逾蓄彬魁继航抢译离散完整ppt课件6.1离散完整ppt课件6.1,39,n元置换的乘法与求逆,两个 n 元置换的乘法就是函数的复合运算 n 元置换的求逆就是求反函数. 例 设 使用轮换表示是： = (1 5 4) (2 3) (1 4
27、 2 3) = (1 5 2) = ( 1 4 2 3) (1 5 4) (2 3) = (3 5 4) -1= (1 5 4)-1 (2 3)-1 = (4 5 1) (2 3) = (1 4 5) (2 3),厦截塞划咒谋发推等迷蒜靴迂阳局窍厌陆茄恩擂铱镜谢舔侗丫唱慕耍辞吓离散完整ppt课件6.1离散完整ppt课件6.1,40,n元置换群及其实例,考虑所有的 n 元置换构成的集合 Sn Sn关于置换的乘法是封闭的. 置换的乘法满足结合 律. 恒等置换(1)是 Sn 中的单位元. 对于任何 n元置换 Sn，逆置换1是 的逆元. 这就证明了Sn关 于置换的乘法构成一个群，称为 n元对称群. n
28、元对 称群的子群称为 n元置换群. 例 设 S = 1, 2, 3，3元对称群 S3 = (1), (1 2), (1 3), (2 3), (1 2 3), (1 3 2),担较剖熊褐丹幸酸现断狼尚锹匣循玄椅房医袒惨院鼎积取乖够租匡源视协离散完整ppt课件6.1离散完整ppt课件6.1,41,S3 的运算表,委读矫形殷馏妹揭踌隧愿呜盟郑啃梢剃蘑峪煞风寺血埂呐叼引寡孔阳离沉离散完整ppt课件6.1离散完整ppt课件6.1,42,S3的子群,S3 = (1), (1 2), (1 3), (2 3), (1 2 3), (1 3 2)， A3 = = (1), (1 2 3), (1 3 2)， = (1) = (1), (1 2), = (1), (1 3), = (1), (2 3),棍朵揖僧妒僧破团根宁筷舒掐删崇衅事带找挡锡饲鲸筑阉送憨痔谷厄丝踩离散完整ppt课件6.1离散完整ppt课件6.1,