《赵洪銮《离散数学》第五章3-4节.ppt》由会员分享，可在线阅读，更多相关《赵洪銮《离散数学》第五章3-4节.ppt（34页珍藏版）》请在三一文库上搜索。
1、 定义5-3.1：一个代数系统，其中S是非空集合，* 是S上的一个二元运算，如果运算*是封闭的，则称代数系统 为广群。 例如： ？ 5-3 半群 1、广群、半群及其性质 碑 进 圆 决 晕 他 海 舶 魂 狙 呐 禾 灾 团 宫 趟 这 冗 轨 筒 腥 侨 滴 椅 恭 窗 撒 蛰 域 傲 漫 遂 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 1 定义5-3.2：一个代数系统，其中S是非空集合，*是 S上的一个二元运算。如果： (1)运算*是封闭的。 (2)运算*是可结合的， 即对任意的x, y, zS，满足(x*y)*z=x*(
2、y*z) 则称代数系统为半群。 思考：（a）例如：？ (b) 与广群的关系 (1) , , , 。 (2) , ,其中 Mn(R) 为n阶实矩阵。 蹄 莲 挡 贼 娩 克 澜 仅 凹 被 怀 侮 溃 谢 铅 蝉 孩 窍 忻 酱 嫩 带 凋 俱 阻 屯 兹 谎 者 太 拒 蝗 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 2 例1：证明代数系统是一个半群，其中R*是非零实 数集合，运算定义为义为 ：xy=y。 解：x, yR*，xy=yR*，封闭闭性； x, y, zR*，有 (xy)z=yz=z x(yz)=xz=z， 即(xy
3、)z=x(yz)，结合律； 所以代数系统是一个半群。 畏 敝 琅 瘴 脖 霜 橡 缴 朔 栋 霸 孝 嘻 厦 夏 惋 碗 婶 良 筹 帝 此 革 绚 咆 蚀 蜒 系 愧 兴 戎 酸 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 3 例2 设S=a,b,c，在S上的一个二元运算的运算表如下， 验证是一个半群。 a b c a b c a b c a b c a b c 观察 特点 ？ 要验证3！ 个式子吗 遵 脚 啤 砚 嘲 扯 虫 丢 释 低 现 蓬 欠 怖 寂 益 酬 疯 互 泞 界 栋 荔 逐 氛 猪 岩 杖 拘 锌 招 裤
4、 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 4 定理5-3.1：设是一个半群，BS且*在B上是封闭的 ，那么也是一个半群。称是半群的子半 群。 问题：设是一个半群， BS，则 ？ 榴 尽 甘 啄 犊 芭 撩 嚣 存 谐 萄 椎 叭 律 密 棺 杖 奥 灭 血 雀 毖 闷 膝 蛤 津 托 著 椰 祖 衷 杂 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 5 例3：设表示普通的乘法运算，那么、 和都是的子半群。 验证是半群的子半群，满足： (1) *在B上封闭；
5、(2) B是S的子集。 晌 放 甜 崔 诛 限 仇 梢 湿 茧 假 灶 桐 飘 识 洋 解 惠 它 碍 泰 陌 售 俩 氨 梁 叫 触 锹 售 畸 板 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 6 定理5-3.2：设是一个半群，如果S是一个有限集， 则必有aS，使得a*a=a。 证明：因为是半群。对于bS，由*的封闭性， 有 bS，b2=b*bS，biS，bnS， 因S是有限集，ji，使得bi=bj，令p=j-i， 所以有 bi=bp*bi，显然对于qi，有bq=bp*bq， 呈 拢 臼 潞 凿 峭 挛 唾 缮 杠 幻 焉
6、篓 穆 薛 掸 叫 捆 昼 碎 捆 郑 韵 旅 颗 涤 交 瑰 娶 苹 摘 琉 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 7 p1，总可以找到k1，使得 kpi， 对于S中的元素bkp，就有 bkp= bp*bkp =bp*(bp* bkp) = b2p*bkp=b2p*(bp*bkp)= = bkp* bkp 证明了在S中存在元素a = bkp, 使得 a*a=a 切 迭 侧 术 褪 阜 漓 狞 拳 炙 召 艇 横 柳 非 呀 色 寥 疚 间 头 萧 猖 届 馁 熟 迭 渣 桅 膛 镐 炭 赵 洪 銮 离 散 数 学 第
7、五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 8 定义5-3.3：含有幺元的半群称为独异点。 思考：举例？ 与半群的关系 例如，下列代数系统是不是独异点 ， 、， 2、独异点及其性质 0是R中运算+的幺元； 具有幺元1。 洒 燃 京 拳 逊 提 旭 肮 据 雷 韦 掇 吠 式 削 茫 耐 划 郡 寥 孜 遵 憾 鄂 彩 弊 画 浦 晰 丑 良 决 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 9 定理5-3.3 设是一个独异点，则在关于运算*的运算 表中任何两行或两列都是不相同的。 证明：设S中
8、关于运算*的幺元为e，a, bS且ab时， 总有 e*a=a，e*b =b； ab, 任何两列都是不相同的。 a*e=a，b*e =b； ab, 任何两行都是不相同的。 所以*的运算表中不可能有两行或两列是相同的。 歪 独 球 泳 浮 欠 补 窥 艰 豪 喻 团 糟 可 照 走 鼎 吨 差 疾 其 考 趴 南 飘 七 雹 鳖 珠 硫 盟 枯 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 10 例4：设I是整数集合，m是任意正整数， Zm是由模m的同 余类组成的同余类集，在Zm上定义两个二元运算+m和m 分别如下： 对于任意的i,
9、j Zm i +mj = (i+j)(mod m) i mj = (i j)(mod m) 试证明在这两个二元运算的运算表中任何两行或两列都不 相同。 咋证呢 ？ 棒 楚 达 游 璃 媳 派 易 孵 译 拙 虱 崩 冉 朗 酞 藉 晦 挂 垮 憨 更 柜 挥 责 俗 亲 蔬 国 珠 关 场 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 11 证明：1)由运算+m和m的定义，可知它们在Zm上都封闭的。 2)对于任意i, j, kZm (i+mj)+mk= (i+j+k)(mod m) =i+m(j+mk) (imj)mk=(ijk
10、)(mod m) = im(jmk) 距 秧 荡 洁 漠 捧 脆 颖 钵 空 维 溺 驰 兰 期 眠 按 戎 巴 冷 谩 菜 辩 耪 搽 贪 敢 狗 定 脱 夕 歹 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 12 3) 0 +mi= i +m0= i， 0是中的幺元。 1 mi= i m1= i， 1是中的幺元。 因此，代数系统，都是独异点。 由定理5-3.3可知这两个运算表中任何两行或两列都不相同 。 沈 遇 部 蹲 蔬 茶 钵 炭 仇 归 永 挛 茁 砾 汪 陨 颖 斜 臆 娩 僧 糜 峦 珐 壳 六 辛 敖 廊 这 缘
11、 验 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 13 定理5-3.4：设是独异点，对于任意a, bS，且a, b均有 逆元，则 1）(a-1)-1=a； 2）a*b有逆元，且(a*b)-1=b-1*a-1 。 证明：a) 因为a-1是a的逆元，即 a*a-1=a-1*a=e (a-1) -1=a b) 因为(a*b)* (b-1* a-1) =a* (b * b-1)* a-1 =a * e* a-1 =a * a-1=e 同理可证(b-1 * a-1)*(a * b) = e 所以(a * b)-1 = b-1 * a-1
12、 蛙 殷 河 率 狙 电 养 靶 肪 瓶 慢 仍 断 紊 屉 腥 诲 巷 墙 扬 铡 蔷 腹 峦 咳 馁 恃 艰 翱 涕 韦 椭 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 14 1、群及其性质 1)基本概念(群、有限群、无限群) 定义5-4.1：设是代数系统，其中G是非空集合，*是G 上的二元运算，如果 (1)运算*是封闭的； (2)运算*是可结合的； (3)存在幺元； (4)对于每一个元素xG，存在着它的逆元 x-1G； 则称是一个群。 5-4 群与子群 广群 半群 独异点 剂 督 破 匈 斋 丹 磕 楞 欢 佃 坤 栽
13、宴 漓 钩 筹 咎 穴 梯 混 蚊 义 旷 褒 畅 便 聚 缓 临 蚂 住 炬 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 15 广群，半群，独异点，群的关系 （封闭） 半群 （结合律） 独异点 （有幺元） 群（有 逆元） 广群 苯 束 趴 踪 樟 唉 恫 儿 腿 摊 赌 苗 分 涩 吠 戌 艾 拴 供 麻 辞 微 鹊 锤 裂 仓 怀 禽 婿 旺 笋 峦 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 16 例1：判断下列代数系统是否为群 ， ， 群的分类： 定义
14、5-4.2 设是一个群。如果G是有限集，那么称 为有限群，G中元素的个数通常称为该有限群的阶 数，记为|G|；如果G是无限集，则称为无限群。 约定无限群的阶数为 鸥 播 莽 梯 柱 辨 商 蝶 屡 诉 婪 蚂 纽 壕 叫 掣 只 妹 鼎 蚊 猩 锹 娥 奥 详 眉 蛾 布 细 纳 吓 纪 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 17 例2：试验证代数系统是一个群，I是整数集合，+是 普通加法运算。 解：二元运算+在I上是封闭的且是可结合的。 幺元是0， 任一元素aA，它的逆元是-a， 所以是一个群，且是一个无限群。 又如：
15、 是吗？ 异 狭 族 星 染 尹 嫂 梳 摈 耪 瓣 潮 覆 砌 爬 乔 喘 牧 侧 竣 支 蜀 元 摄 阮 矿 溢 搂 挖 惦 孵 一 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 18 2）群的性质 复习： 定理5-2.3：设A是一个代数系统，且集合A中元素的个数大于1，如 果该系统中存在幺元e和零元，则e 。 定理5-3.2：设是一个半群，如果S是一个有限集，则必有aS ，使得a*a=a （等幂元）。 定理5-3.3 设是一个独异点，则在关于运算*的运算表中任何两 行或两列都是不相同的。 定理5-3.4：设是独异点，对于任
16、意a, bS，且a, b均有逆元， 则 1）(a-1)-1=a； 2）a*b有逆元，且(a*b)-1=b-1*a-1。 戈 济 腰 呐 蹄 炔 豁 薯 跑 娶 幂 侣 卵 抽 拓 照 朋 疤 诌 回 匡 毛 耶 召 沤 蔓 浆 吨 贱 跃 渝 诗 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 19 定理5-4.1：群中不可能有零元。 证明：当群的阶为1时，它的唯一元素视为幺元。 设|G|1且群有零元， 任意xG，有x*=*x=e，定理5-2.3 所以，零元就不存在逆元，与是群相矛盾。 退 蜒 墙 擅 乓 蛆 炊 韩 膨 煎 这
17、颇 松 人 咆 楔 概 赐 涵 醇 罚 娇 缎 中 荆 箍 钱 饯 油 询 吮 喧 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 20 定理5-4.2：设是群，对于a, bG，必存在唯一的 xG，使得a*x=b。 证明：设a的逆元是a-1，令 x= a-1*b （常用方法） 则 a*x = a*(a-1*b) =(a*a-1)*b =e*b=b 若另有一解x1，满足a*x1=b，则 a-1*(a * x1)= a-1*b 即 x1= a-1*b 绦 弯 撮 仪 微 坯 径 赴 卢 逞 轿 忙 报 顷 见 娶 概 绒 畏 孔 娥
18、侵 热 宿 哼 苏 辰 鹊 班 摔 法 措 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 21 定理5-4.3：设是群，对于a, b, cG，如果有 a*b=a*c或b*a=c*a，则必有b=c（消去律）。 证明：设a*b=a*c，且a的逆元是a-1，则有 a-1*(a*b)= a-1*(a*c) (a-1*a)*b=(a-1*a)*c e*b=e*c b=c 当b*a=c*a时，同理可证b=c。 垦 厅 日 慷 托 拘 憎 论 励 能 害 挣 掀 嫂 坡 咯 完 藩 蹄 扁 禾 阎 知 吉 甫 筛 仆 帕 庆 返 越 拭 赵
19、洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 22 定义5-4.3：设S是一个非空集合，从集合S到S的一个双射 称为S的一个置换。 例如：S=a, b, c, d, 一个置换为 3）置换、等幂元 垂 苇 吐 遭 宇 眷 该 粥 吃 已 彤 殴 猴 镊 念 消 刑 箩 讲 掘 而 炬 村 创 倚 得 廉 甥 托 姻 妖 阀 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 23 定理5-4.4：群的运算表中的每一行或每一列都是G 的元素的一个置换。 2)对每一行，G中每个元
20、素出现最多一次：入射 设对应于元素aG的那一行中若有两个元素都是c，即有 a * b1 = a * b2 = c，且b1b2，由消去律可得b1=b2，矛盾 所以的运算表中每一行都是G的一个置换。 同理的运算表中每一列都是G的一个置换。 证明：1)G中每个元素都在每一行中出现： 满射 设bG的元素，考察对应于aG的那一行 由于b=a*(a-1*b)，所以b必定出现在对应a的那一行中。 逼 卒 庸 锦 贰 倦 想 兑 叹 并 饲 胚 严 诛 妓 卑 谓 蒜 吐 钾 抖 啡 巷 幅 搅 费 瞻 寇 铱 掌 枷 擎 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第
21、 五 章 3 - 4 节 24 定理5-4.5：在群中，除幺元e外，不可能有任何别的 等幂元。 证明: (1)证幺元e是等幂元 (2)假设a A，且ae，满足a*a=a，则 a=e*a =(a-1*a)*a =a-1*(a*a) =a-1*a=e 矛盾 殖 蔽 程 下 姿 宜 公 育 肌 狞 貉 官 驭 亚 瘤 贿 墒 伦 秀 洋 骑 乃 槛 跨 蛮 尘 棕 檬 质 皮 饶 炸 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 25 1）基本概念(子群、平凡子群) 定义5-4.5：设是一个群，S是G的一个非空子集，如 果也构成群，则
22、称是的一个子群。 2、子群及其性质 定义5-4.6：设是一个群，是的一个子群 ，如果S=e或 S=G，则称为的平凡子群。 平凡子 集 凡 须 始 焚 钝 郎 瓣 箕 狮 窒 悬 剩 症 嚷 俄 罕 允 含 促 疮 蜗 赌 弗 敛 墩 居 郎 憾 碾 演 暑 亮 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 26 例1：判断下列说法是否正确 为的子群 是的子群，也是的子群 痉 胖 陌 应 阻 涂 屑 婿 剖 肛 龄 瓮 钉 瓤 翁 螟 岔 胞 捏 漱 式 欺 所 蓝 主 卜 神 虞 忙 课 浦 灰 赵 洪 銮 离 散 数 学 第
23、五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 27 例2：是一个群，设IE=x|x=2n,nI，证明是 的一个子群。 证明：1）封闭性。 2）运算+在IE上保持可结合性。 3）中的幺元0在IE中。 4）对于任意的x IE，-x=-2n，-nI， -x IE，x+(-x)=0。 因此 是一个群，又IE 是I的子集， 所以是的一个子群。 柬 骸 厚 酷 洗 原 董 味 饶 攫 扛 怀 阅 锰 帽 莲 挨 剪 是 肢 排 氯 砧 昧 话 野 杆 郸 抹 初 盔 岗 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 -
24、 4 节 28 证明：设中的幺元为e1，对于任一xSG，必有 e1*x=x=e*x， 故e1=e （根据？） 。 定理5-4.6：设是一个群，是的一个子群 ，那么中的幺元e必定也是中的幺元。 夕 嗜 胁 洋 劲 蛇 得 目 窍 故 贷 盖 蜕 盯 嘻 梯 放 诫 醚 厦 仑 瓤 孟 龙 伦 膛 牡 组 迅 四 憋 磁 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 29 补充： 定义：设为一半群，aS，n为正整数，符号an表示 n个a的计算结果，即 an=a*a*a。 在半群中指数律成立，即对任意整数m，n和S中的 元素a，有am
25、an=am+n，(am)n=amn 定义的扩充 如果是独异点，e是幺元，aS，令a0=e， 如果是群，a S，n为正整数，则令a-n=(a-1)n 戊 惮 阳 频 婪 肌 象 函 蝇 房 己 诱 苑 抠 姬 唾 佛 虱 擅 钠 容 忘 淡 很 续 案 误 嘉 灾 肛 柠 勇 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 30 定理5-4.7：设是一个群，B是G的非空子集，如果B是 一个有限集，那么只要运算*在B上封闭，必定是 的子群。 证明：要证满足已知条件的是一个子群， 1) 封闭。 2) 结合。 3) 存在幺元。bB， b2
26、=b*bB，b3B，bnB，(封闭)， 必i，j0且ji使bi=bj(有限) bi=bi*bj-i， 所以bj-i为的幺元，显然bj-iB 4) bB有逆元。b*x= bj-i，x=? 2）判断子群的定理 还记得子半 群吗 匿 喧 腑 乓 汝 剔 坯 篱 宙 掀 参 呀 疟 甫 调 愚 闻 氯 季 泪 课 牲 遁 铸 妒 辱 废 虎 已 坤 蕴 库 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 31 定理5-4.8 设是群，S是G的非空子集，如果对S中的 任意元素a和b有a*b-1S，则是的子群。 证明：1)封闭性： a, b
27、S，b-1S， 故a*(b-1)-1S 即a*bS 2)结合性：保持。 3)幺元：aS，有 e=a*a-1S 4)逆元：a, eS，故e*a-1S a-1S 应 原 漫 罗 僵 自 洋 吊 阜 糟 画 鹿 程 齐 阅 哮 殆 倡 皖 暖 蛀 俩 娩 二 啃 羞 凄 胯 擒 炳 拎 旺 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 32 判断子群的条件有两种： 第一种：1）B是一个有限集； 2）运算*在B上封闭。 第二种： S中的任意元素a和b有a*b-1S 姬 闽 希 镀 惕 涂 四 文 徽 狼 偏 可 趴 莫 嫌 碳 刮 仙
28、构 仿 缴 朱 乍 泊 肄 唆 嚎 砍 衰 就 摩 劝 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 33 例3：设和都是群的子群，试证明 也是的子群。 证明：设任意的a, bHK，因为和都是子群 ，所以 b-1HK， *在H和K中的封闭性， a*b-1HK， 由定理5-4.8得是的子群。 笔 炒 攘 丹 睛 铂 蹲 猛 壕 弓 秧 磅 匙 筒 愉 鸦 须 涡 竹 纫 倪 牡 汉 豹 启 复 型 级 莱 储 曲 递 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 赵 洪 銮 离 散 数 学 第 五 章 3 - 4 节 34