半群和群-课件（精）.ppt

* * * * * * * * * * * * * * * 半群与群 离散数学 第11讲 上一讲内容的回顾 运算及其封闭性 运算的性质 运算的性质和运算表的特征 运算表 代数系统 系统公理 结合律、交换律、分配律 单位元、零元、逆元 半群与群 系统公理与公理化系统 半群 独异点(单元半群) 群公理 群方程及其解 群与消去律 群表 公理化系统 抽象的系统：太一般 具体的系统：太多 抽象代数的研究对象：公理化的系统 系统公理：通常是常见的性质中的1条或者多条。 “代数系统”+结合律=“半群”(Semigroup) “半群”+单位元素=单元半群(Monoid) “单元半群”+逆元素=群(Group) 半群 系统公理： 结合律 一个例子: ({1,2},*), *定义如下： 对任意x,y?{1,2}, x*y=y 证明：需证明(x*y)*z = x* (y*z)对一切x,y,z成立。 (x*y)*z=z x*(y*z)=x*z=z 满足交换律的半群称为“可换半群” 独异点（单元半群） 系统公理： 结合律 有单位元素 例子： S与矩阵乘法构成独异点，T与矩阵乘法也构成独异点。T是S的子半群，但不是子独异点。 推导半群中等式 (A,*)是半群，对任意a?b, 则a*b ?b*a, 证明： (1) a*a = a 由半群满足结合律可知 (a*a)*a = a*(a*a) (2) a*b*a = a (a*b*a)*a=(a*b)*(a*a)=a*b*a, 同样a*(a*b*a)=a*b*a (3) a*b*c = a*c (a*b*c)*(a*c)=(a*b)*(c*a*c)=a*b*c, 同样(a*c)*(a*b*c)=a*b*c 寻找单位元素 (A,*)是半群，假设存在元素a, 满足：对任意x, 总存在u,v, 使得a*u=v*a=x。证明：A含单位元素。 证明： 对于a本身，一样存在ua,va, 满足：a*ua =a; va*a=a。 则对任意x, x* ua=(v*a)* ua=v*a=x, 即ua=是右单位元素。同理可证va是左单位元素。 则： ua= va是单位元素。 乘幂 如果运算?满足结合律，则如下定义的乘幂有意义： x1 = x xn+1 = xn?x (n是正整数) 如果运算?另外还满足有单位元，则如下定义的乘幂有意义： x0 = e （e是单位元素） xn+1 = xn?x (n是非负整数) xn? xm= xn+m (xn)m= xnm 群公理 满足下列性质的代数系统称为群： 结合律 因此：群也是半群 有单位元素 因此：群也是独异点 每个元素均有逆元素 将元素a的逆元素记为a-1 幂的扩展：定义a-k =(a-1)k (k为正整数) 如果还满足交换律：可交换群(阿贝尔群) 群的例子 整数加群: (Z,+) 加法可结合；单位元素0；a的逆元素为(-a) 剩余加群: (Zn, +n) (其实这一类群，含无穷多个群) Zn={0,1,2,...,n-1}, a+nb=a+b除以n的余数 剩余加可结合；单位元素0；a的逆元素为n-a 非零实数乘法群: (R-{0},?) 乘法可结合；单位元素1；x的逆元素为1/x 注意：实数集与乘法不构成群 每行每列恰好有一个1，其它元素均为0的所有n?n阶矩阵 以及 矩阵乘法构成群 矩阵乘法可结合；单位元是主对角元素全为1而其它元素全为0的矩阵；根据线性代数知识可知这样的矩阵是可逆矩阵。 集合上的置换 在集合{1,2,3}上可以定义6个一一对应的函数： 有限集合上的一一对应的函数称为置换。 群S3 ({e,?,?,?,?,?}, ?)构成群，其中“?”是函数复合。 ? e ? ? ? ? ? e ? ? ? ? ? 运算表 例如： ? ? ?(1) = ?(?(1)) = ?(3) = 2 ? ? ?(2) = ?(?(2)) = ?(2) = 3 ? ? ?(3) = ?(?(3)) = ?(1) = 1 即： ? ? ? = ? 群的直积 给定两个群: (S, ?), (T,*), 定义笛卡儿乘积S?T上的运算?如下： s1,t1 ? s2,t2 = s1 ? s2, t1*t2 (S?T, ?)是群 结合律： (r1 ? s1) ? t1, (r2*s2)*t2 = r1 ?(s1 ? t1), r2*(s2*t2) 单位元素：1S, 1T 逆元素：s, t 的逆元素是 s-1, t-1 (其中： s, s-1?S, t, t-1?T) 又一个群的例子 已知(S, ?)是群，u是S中一个特定的元素，定义S上一个新运算*如下： a*b