资源描述：
《离散数学第四讲半群和独异点》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、定义1：设有代数系统〈S,*〉,这里*是S上可结合的二元运算,则称〈S,*〉为半群。（2点）例1：判断下列给出的代数是不是半群。①〈E,+〉和〈E,*〉,E为正偶数集{2,4,6,…}；②〈S,*〉，其中S是不同高度的人的集合，a*b表示a,b中较高者；③〈R+,·〉〈R+,÷〉④设k≥0，SK={x
2、x∈I∧x≥k},〈SK,+〉；若k<0，〈SK,+〉；⑤〈S,*〉，S={a,b},S上的二元运算*的运算表如下图：√√√×（÷不可结合）√×（+在SK上不封闭）√6.6半群和独异点1定义2：若半群〈S,*〉对运算*有么元，则称该半群为含么
3、半群,也称独异点。（3点）例2：判断下列给出的代数是不是独异点。①〈E,+〉和〈E,*〉,E为正偶数集{2,4,6,…}；②〈S,*〉，其中S是不同高度的人的集合，a*b表示a,b中较高者；③〈R+,·〉〈R+,÷〉④〈{Rn
4、n∈N},合成运算，R0〉，其中R是S上的二元关系；×√，么元为最矮的人√×√半群和独异点2定义3：如果〈S,*〉是半群,T⊆S且关于运算*封闭,那么〈T,*〉是〈S,*〉的子代数,称〈T,*〉为〈S,*〉的子半群。如〈[0，1],*〉,〈N,*〉都是〈R,*〉的子半群.定理1：子半群是半群。证：子半群是子代数,关
5、于运算*封闭,结合律是继承的,所以是半群。证毕。半群和独异点3定义4：如果〈S,*,1〉是独异点。T⊆S,且关于运算*封闭,1∈T,那么〈T,*,1〉是〈S,*,1〉的子代数,称〈T,*,1〉是〈S,*,1〉的子独异点。如〈N,*,1〉就是〈R,*,1〉的子独异点.定理2：子独异点是独异点。证：子独异点是子代数,关于运算*封闭,含有么元,结合律是继承的,所以是独异点。证毕。半群和独异点4注：独异点一定是半群，但半群不一定是独异点。但可通过添加新元素将半群变为独异点，如半群〈[0，1),*〉添加么元1可变为独异点〈[0，1],*,1〉。定
6、理3：独异点〈S,*〉中，运算*的运算表没有两行和两列是相同的。证：设S是有限集{e,a1,a2…an}，对任何ai,aj∈S，若ai≠aj则e*ai≠e*aj,所以任意两列都不相同。又因为ai*e≠aj*e,所以任意两行都不相同。半群和独异点5定义5：在半群(独异点)中,若运算是可交换的,则称此半群(独异点)为可交换半群(可交换独异点)。定理4:在任何可交换独异点〈S,*,e〉中,S的等幂元素集合T可构成子独异点。证:i)任取x,y∈T,则x*y=(x*x)*(y*y)=x*(x*y)*y=(x*y)*(x*y)所以,x*y∈T,
7、故运算封闭；ii)T是S的子集，*在T上可结合；iii)e*e=e,e是等幂元素,所以,e∈T。故〈T,*,e〉是子独异点。证毕。本定理对可交换半群也成立。半群和独异点6下面我们定义独异点〈S,*,e〉中任意元素a的幂。用归纳定义:(1)(基础)a0=e(2)(归纳)an+1=an*a(n∈N)由于独异点中,运算*是可结合的,容易证明如此定义的a的幂满足以下指数定律:(1)(2)半群和独异点7定义6:在独异点〈S,*,e〉中,如果存在一个元素g∈S,使每一元素a∈S,都有一个相应的h∈N能把a写成gh,即a=gh，则称此独异点为循
8、环独异点。并称元素g是此循环独异点的生成元,又可说此循环独异点是由g生成的。例3：①〈N,+,0〉是循环独异点，生成元是1，因为任取i∈N，当i=0时，0=10；i≠0时，有i=1i。②是循环独异点，生成元为b,c1=b0,a=b2,b=b1,c=b3;1=c0,a=c2,b=c3,c=c1.半群和独异点8定理5：每个循环独异点都是可交换的。证：设〈S,*,e〉是循环独异点,其生成元是g,对任意a、b∈S,存在m、n∈N,使a=gm和b=gn,因此证毕。半群和独异点9作业：P1871,7,8,9,12,1310
