西安电子科技大学出版社：面向21世纪高等学校计算机类专业系列教材《离散数学》课程教学资源（PPT课件讲稿）第6章 几个典型的代数系统

第6章几个典型的代数系统 第6章几个典型的代数系统 6,1半群与群 6,2子群 63循环群和置换群 64陪集与拉格朗旦定理 6.5正规子群、商群和同态基本定理 6.6环和域 6.7例题选解 习题六 dBac

第6章 几个典型的代数系统 第6章 几个典型的代数系统 6.1 半群与群 6.2 子群 6.3 循环群和置换群 6.4 陪集与拉格朗日定理 6.5 正规子群、商群和同态基本定理 6.6 环和域 6.7 例题选解 习 题 六

第6章几个典型的代数系统 61半群与群 半群与群都是具有一个二元运算的代数系统,群 是半群的特殊例子。事实上,群是历史上最早研究的 代数系统,它比半群复杂一些,而半群概念是在群的 理论发展之后才引进的。逻辑关系见图61

第6章 几个典型的代数系统 6.1 半群与群 半群与群都是具有一个二元运算的代数系统，群 是半群的特殊例子。事实上，群是历史上最早研究的 代数系统，它比半群复杂一些，而半群概念是在群的 理论发展之后才引进的。逻辑关系见图6.1.1

第6章几个典型的代数系统 半群 群 图6.1.1

第6章 几个典型的代数系统 图 6.1.1 群 半群

第6章几个典型的代数系统 定义61.1设〈S,*〉是代数系统,*是二元运算, 如果*运算满足结合律,则称它为半群( semIgroups)。 换言之,∨xyz∈S,若*是S上的封闭运算且满足 (x*y)*=x*(y*),则〈S,*)是半群。 许多代数系统都是半群。例如,(N,+〉, 〈Z×),〈P(S),,〈SS,)(SS={S→S},是复合 运算)均是半群。但〈Z-)〉不是半群

第6章 几个典型的代数系统 定义6.1.1 设〈S， *〉是代数系统， *是二元运算， 如果*运算满足结合律，则称它为半群（semigroups）。 换言之， x,y,z∈S,若*是S上的封闭运算且满足 (x*y）*z=x*（y*z），则〈S， *〉是半群。 许多代数系统都是半群。例如，〈N,+〉， 〈Z,×〉,〈P(S), ,〈SS, （SS={f|f:S→S}, 是复合 运算）均是半群。但〈Z,-〉不是半群。 

第6章几个典型的代数系统 再如,设∑是有限字母表,∑是∑中的字母串 ∑*={4}∪∑,其中λ是不含字母的空串,运算τ是字母串 的“连接”运算,则〈Σ,τ〉是半群。如 Com∈* puter∈∑*经τ运算后,得 Computer仍是字母 串

第6章 几个典型的代数系统 再如，设Σ是有限字母表，Σ +是Σ中的字母串 Σ *={λ}∪Σ +，其中λ是不含字母的空串，运算τ是字母串 的“连接”运算，则〈Σ * ,τ〉是半群。如 Com∈Σ*,puter∈Σ*,经τ运算后，得Computer仍是字母 串

第6章几个典型的代数系统 【例61.1】 b b∈R,a≠0) 则〈S;〉是半群。这里·代表普通的矩阵乘法运算 证明对任意的 a,b, ∈S ∈S因为 00 00 a2b2 6,b, 且a1a20,所以 0000 0a∈S,因此运算封闭

第6章 几个典型的代数系统 【例6.1.1】 | , , 0) 0 0 a b S a b R a     =           ,则〈S,·〉是半群。这里·代表普通的矩阵乘法运算。 证明 对任意的 1 1 2 2 , 0 0 0 0 a b a b S S               因为 1 1 2 2 1 2 1 2 0 0 0 0 0 0       a b a b a a b b =             且a1a2≠0,所以 1 2 1 2 0 0 a a b b S       ,因此·运算封闭。 ·

第6章几个典型的代数系统 【例612】S a,b∈R,2a≠0} 00 ,则〈S+〉不是半群。这里+代表普通的矩阵加法运算。 证明对任意的 ∈S ∈S取a,=a1,则 00 6,+b 且a1+a2=0,所以 +a2b1+b2 0|S因此*运算不封闭 所以〈S,+〉不是半群

第6章 几个典型的代数系统 【例6.1.2】  | , , 0} 0 0 a b S a b R a   =       ,则〈S,+〉不是半群。这里+代表普通的矩阵加法运算。 证明 对任意的 1 1 2 2 , 0 0 0 0 a b a b S S               取a2 =-a1 ,则 1 1 2 2 1 2 1 2 0 0 0 0 0 0       a b a b a a b b + + + =             且a1+a2=0，所以 1 2 1 2 0 0 a a b b S   + +     因此*运算不封闭。 所以〈S,+〉不是半群

第6章几个典型的代数系统 【例6.1.3】S= la,b,c∈R C 则〈S,〉不是半群。这里·代表普通的矩阵乘法运算 证明取 ∈S 则 所以 因此*运算不封闭 所以〈S,〉不是半群

第6章 几个典型的代数系统 【例6.1.3】 { | , , } 0 a b S a b c R c   =      ,则〈S,·〉不是半群。这里·代表普通的矩阵乘法运算。 证明 取 1 1 1 1 1 1 1 1 2 1 , , , 1 0 1 0 1 0 1 0 1 1 S S             =                     则 所以 2 1 1 1 S       ,因此*运算不封闭。 所以〈S,·〉不是半群

第6章几个典型的代数系统 对于半群中的元素,我们有一种简便的记法。 设半群〈S*〉中元素a(简记为a∈S)的n次幂记 为a,递归定义如下: an+I=an*a n∈ 即半群中的元素有时可用某些元素的幂表示出来。 因为半群满足结合律,所以可用数学归纳法证明 C 普通乘法的幂、关系的幂、矩阵乘法的幂等具体 的代数系统都满足这个幂运算规则。如果有a2=a,则 称a为半群中的幂等元

第6章 几个典型的代数系统 对于半群中的元素，我们有一种简便的记法。 设半群〈S,*〉中元素a（简记为a∈S）的n次幂记 为a n ，递归定义如下： a 1=a a n+1=a n*a 1 n∈ Z+ 即半群中的元素有时可用某些元素的幂表示出来。 因为半群满足结合律，所以可用数学归纳法证明 a m*a n=a mn ，(a m) n=a mn 。 普通乘法的幂、关系的幂、矩阵乘法的幂等具体 的代数系统都满足这个幂运算规则。如果有a2=a，则 称a为半群中的幂等元

第6章几个典型的代数系统 定理6.1.1若〈S,*〉是半群,S是有限集合,则S中 必含有幂等元。 证明因为〈S,*〉是半群,a∈S,有a2a32,∈S 因为S是有限集合,所以必定存在j>i使得a=cl 令p1,便有a==mp*a,所以a=p米a(q1) 因为≥1,所以可找到k1,使得k≥i a2p*ap=am2p*(mp米m) 即在S中存在元素b=m,使得b*b=b

第6章 几个典型的代数系统 定理6.1.1 若〈S,*〉是半群，S是有限集合，则S中 必含有幂等元。 证明 因为〈S,*〉是半群， a∈S,有a 2 ,a 3 ,…,∈S。 因为S是有限集合，所以必定存在j＞i,使得a i=a j。 令p=j-i,便有a i=a j=a p*a i ，所以a q=a p*a q (q≥i)。 因为p≥1,所以可找到k≥1,使得kp≥i a kp=a p*a kp=a p*(a p*a kp) =a 2p*a kp=a 2p*(a p*a kp)=…=a kp*a kp 即在S中存在元素b=a kp ,使得b*b=b。 