离散数学-第4讲-半群和独异点

1离散数学（二）半群和独异点半群11独异点2主要内容:半群和独异点重点:半群和独异点的性质难点:重点和难点:一、半群与独异点半群的定义：定义1设A=S，为代数，若(1)集合S关于运算是封闭的，(2)S上运算满足结合律，则称代数S，为半群(semigroups)。独异点的定义:定义2设代数S,为半群，若S,含有关于运算的么元e,则称代数S,为独异点(monoid)，或含么半群。!独异点一定是半群，但半群不一定是独异点。一、半群与独异点例1：判断下列代数是不是半群(独异点)。(1)设k≥0，Sk={x|x∈I∧x≥k},Sk,+是半群；k=0时存在么元0，Sk,+是独异点k0时不存在么元，Sk,+非独异点k0时，Sk关于+不封闭，Sk,+非半群，非独异点(2)I,+,0封闭，可结合，么元0，是半群，是独异点I,·,1封闭，可结合，么元1，是半群，是独异点(3)代数Nk,+k,0，Nk=｛0,1,2,…,k-1｝，模k加法+k封闭，可结合，么元0，是半群，是独异点代数Nk,×k,1，Nk={0,1,2,…,k-1}，模k乘法×k封闭，可结合，么元1，是半群，是独异点一、半群与独异点子半群的定义：定义3S,*是半群,若(1)T⊆S(2)T关于运算*封闭,则T,*是S,*的子代数,称T,*为S,*的子半群。定理1子半群是半群。证明子半群是子代数,关于运算*封闭,结合律是继承的,所以是半群。证毕。一、半群与独异点子独异点的定义：定义4S,*,e是独异点，若(1)T⊆S(2)T关于运算*封闭(3)e∈T,则T,*,e是S,*,1的子代数，称T,*,e是S,*,e的子独异点。一、半群与独异点定理2子独异点是独异点。证明子独异点是子代数,关于运算*封闭,含有么元,结合律是继承的,所以是独异点。证毕。例2如果Σ是有限非空字母表,那么Σ+,连结是半群,Σ*,连结,Λ是独异点。如果A⊆Σ*,那么A*,连结,Λ是Σ*,连结,Λ的子独异点。一、半群与独异点可交换半群的定义：定义5在半群(独异点)中,若运算是可交换的,则称此半群(独异点)为可交换半群(可交换独异点)。定理4在任何可交换独异点S,*,e中,S的等幂元素集合T={a|a∈S,a2=a},则T,*,e可构成子独异点。证明(1)T关于运算*封闭。任取x,y∈T,则x,y∈S，那么(x*y)2=(x*y)*(x*y)=x*(y*x)*y=x*(x*y)*y=(x*x)*(y*y)=x*y，所以,x*y∈T,故运算封闭；(2)T是S的子集，*在T上可结合；(3)e*e=e,e是等幂元素,所以,e∈T。故T,*,e是子独异点。证毕。一、半群与独异点定义6定义独异点A=S,*,e中任意元素a的幂,幂运算用归纳定义如下:(1)(基础)a0=e，(2)(归纳)an+1=(an)*a(n∈N)。由于独异点中,运算*是可结合的,容易证明如此定义的a的幂满足以下指数定律:),()(),(NjiaaNjiaaajijijiji一、半群与独异点定义7在独异点S,*,e中,如果存在一个元素g∈S,使每一元素a∈S,都有一个相应的h∈N能把a写成gh,即a=gh，则称此独异点为循环独异点。并称元素g是此循环独异点的生成元,又可说此循环独异点是由g生成的。例3(1)N,+,0是循环独异点，生成元是1，因为任取i∈N，当i=0时，0=10；i≠0时，有i=1+1+…+1=1i。(2)右图是循环独异点，生成元为b,c1=b0,a=b2,b=b1,c=b3;1=c0,a=c2,b=c3,c=c1。一、半群与独异点定理5证明：设S,*,e是循环独异点,其生成元是g,对任意a、b∈S,存在m、n∈N,使gm=a和gn=b,证毕。abggggggbamnmnnmnm作业:P1961,4,9,1013谢谢同学们!