离散数学第五章第二节.ppt

第5-2讲 半群与群 1. 半群 2. 独异点 3. 群的定义 4. 群的性质 5. 子群 6. 子群判定定理 7. 第5-2讲 作业 1、半群（1） 半群是一种代数系统。在形式语言、自动机中有应用。 1、半群（2） 1、半群（3） 2、独异点(1) 2、独异点(2) 2、独异点(3) 3、群的定义（1） 3、群的定义（2） 3、群的定义（3） 3、群的定义（4） 4、群的性质（1） 4、群的性质（2） 4、群的性质（3） 4、群的性质（4） 5、子群（1） 5、子群（2） 6、子群判定定理（1） 6、子群判定定理（2） 第5-2讲 作业 P190 1，3 P197 1，3 * * 定义2 如果代数系统S,*为广群，二元运算*可结合，则称代数系统S,*为半群。 定义1 一个代数系统S,*，S是非空集合，*是S上的二元运算,如果运算*是封闭的,则称代数系统S,*为广群。 例1 设S={a,b,c},定义S上的运算*如右表： 验证S，*是否为半群。 代数系统I+,-和R,/是半群吗？这里I+为正整数集，R为实数集，-和/是通常数的减法和除法。 解：从运算可看出运算*是封闭的。 另外a、b、c皆为左幺元，所以，对任意x,y,z?S，均有x*(y*z)=y*z=(x*y)*z 所以*运算是可结合的。从而S，*是半群。 定理2 设S,*是半群，如果S为有限集，则存在a?S，使得a*a=a。 定理1 设S,*是半群，集合B?S，且*在B是封闭的，则B,*也是半群，称之为S,*的子半群。 证：因S,*是半群，运算封闭且可结合，所以可定义半群中任意元素b的幂： b2=b*b, b3=b2*b=b*b*b, ...。 因S为有限集，在幂的序列中，必存在ji,使 bi=bj。 令p=j-i?1,则bi=bp*bi，此式两边不断右*b,可使 bkp =bp*bkp（k?1为正整数） 这样bkp=bp*bkp =bp*(bp*bkp)=b2p*bkp =b2p*(bp*bkp)=…=bkp*bkp 这说明S中存在等幂元素a=bkp，a*a=a。 可取定理2证明中的b=2,i=5,j=9。p=j-i=9-5=4。那么 2i=2p*2i,即25=24*25,三次右*2得：28=24*28(p=4,k=2) 即22p=2p*22p=2p*(2p*22p)=22p*22p,令a=22p=28=1,a*a=a。 例如：设N5={0,1,2,3,4}，运算*定义如下表，则Nk,*是半群。 从运算表可以看出： 0*0=0，0是等幂元； 1*1=1，1是等幂元； 21=2 26=2*2=4 22=2*2=4 27=4*2=3 23=4*2=3 28=3*2=1 24=3*2=1 29=1*2=2 25=1*2=2 210=2*2=4 例如，Z+,+，N，+，Q，+都是半群，其中+是普通加法。 Z+、N、Q分别是正整数集、自然数集和有理数集。这些半群中除Z+,+外都是独异点 定义3 含有幺元的半群叫独异点。也称为含幺半群。 定理3 设S,*是独异点，则运算*的运算表中任何两行或两列都不相同。 证明：设S中的幺元为e。那么对任意a,b?S且a?b时,有 e*a=a?b=e*b; a*e=a?b=b*e。 前式说明e所在行的任意两个元素都是不同的，从而任意两列至少有一个元素是不同的，从而任意两行不同(参考右图)。 后式说明e所在列的任意两个元素都不相同，从而任意两行是不同的。 例2 设I为整数集合，Z6是同余模6的等价类构成的集合(参看P132)，即Z6={[0],[1],[2],[3],[4],[5]}。在Z6上定义运算?6如下表： 对任意[i],[j]?Z6，[i]?6[j]=[(i?j)(mod6)]。 验证Z6,?6是独异点。 解:(1)由定义运算?6显然是封闭的。 (2)可验证运算?6是可结合的： ([i]?6[j])?6[k]=[i]?6([j]?6[k]) =[(i?j?k)(mod6)]。 例如:([4]?6[5])?6[3]=[2]?6[3]=[0] [4]?6([5]?6[3])=[4]?6[3]=[0] [(4?5?3)(mod6)]=[60(mod6)]=[0] (3)[1]是幺元。因为 [1]?6[i]=[i]?6[1]= [(1?i)(mod6)] = [i(mod6)]=[i]。 定理4 设S,*是独异点，且对任意a,b?S均有逆元。则 (1) (a-1)-1=a; (2)(a*b)-1=b-1*a-1。 证明： (1) 可按定义验证