《离散数学-第4讲-半群和独异点ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学-第4讲-半群和独异点ppt课件.ppt（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1离散数学（二）离散数学（二）半群和独异点半群和独异点半群半群11独异点独异点2主要内容主要内容: :半群和独异点半群和独异点重点重点: : 半群和独异点的性质半群和独异点的性质难点难点: :重点和难点重点和难点: :一、半群与独异点一、半群与独异点半群的定义：半群的定义： 定义定义1 设A=为代数，若 (1) 集合S关于运算 是封闭的， (2) S上运算 满足结合律，则称代数为半群半群(semigroupssemigroups)。独异点的定义独异点的定义: : 定义定义2 设代数为半群，若含有关于 运算的么元e,则称代数为独异点独异点(monoidmonoid)，或含么半群。 ! !独异点一
2、定是半群，但半群不一定是独异点。独异点一定是半群，但半群不一定是独异点。一、半群与独异点一、半群与独异点n例例1：判断下列代数是不是半群(独异点)。 (1)设k0， Sk=x|xIxk, 是半群； k=0时存在么元时存在么元0，是独异点是独异点 k0时不存在么元，时不存在么元，非独异点非独异点 k0时，时，Sk关于关于+不封闭，不封闭，非半群，非独异点非半群，非独异点 (2) 封闭，可结合，么元封闭，可结合，么元0 0，是半群，是独异点，是半群，是独异点 封闭，可结合，么元封闭，可结合，么元1 1，是半群，是独异点，是半群，是独异点 (3) 代数，Nk =0, 1, 2, , k-1，模k加法
3、+k 封闭，可结合，么元封闭，可结合，么元0 0，是半群，是独异点，是半群，是独异点 代数，Nk =0, 1, 2, , k-1，模k乘法k 封闭，可结合，么元封闭，可结合，么元1 1，是半群，是独异点，是半群，是独异点 一、半群与独异点一、半群与独异点子半群的定义：子半群的定义： 定义定义3 是半群,若 (1) TS (2) T关于运算*封闭, 则是的子代数, 称为的子半群子半群。 定理定理1 子半群是半群。 证明证明 子半群是子代数, 关于运算*封闭, 结合律是继承的,所以是半群。 证毕。一、半群与独异点一、半群与独异点子独异点的定义：子独异点的定义： 定义定义4 是独异点，若 (1) T
4、S (2) T关于运算*封闭 (3) eT, 则是的子代数，称是的子独异子独异点点。 一、半群与独异点一、半群与独异点定理定理2 子独异点是独异点。 证明证明 子独异点是子代数,关于运算 * 封闭, 含有么元,结合律是继承的, 所以是独异点。 证毕。 例例2 如果是有限非空字母表, 那么是半群, 是独异点。如果A* , 那么是的子独异点。一、半群与独异点一、半群与独异点可交换半群的定义：可交换半群的定义： 定义定义5 在半群(独异点)中, 若运算是可交换的, 则称此半群(独异点)为可交换半群可交换半群(可交换独异点可交换独异点)。 定理定理4 在任何可交换独异点中, S的等幂元素集合T=a|a
5、S,a2=a,则可构成子独异点。 证明证明 (1) T关于运算*封闭。任取x,yT,则x,yS，那么 (x*y)2=(x*y)*(x*y)=x*(y*x)*y=x*(x*y)*y =(x*x)*(y*y)= x * y， 所以, x*yT,故运算封闭； (2) T是S的子集，*在T上可结合； (3) e*e=e, e是等幂元素,所以,eT。 故是子独异点。 证毕。一、半群与独异点一、半群与独异点 定义定义6 定义独异点A=中任意元素a的幂,幂运算用归纳定义如下: (1) (基础) a0 = e， (2) (归纳) an+1=(an)*a (nN)。 由于独异点中, 运算*是可结合的, 容易证明
6、如此定义的a的幂满足以下指数定律:),()(),(NjiaaNjiaaajijijiji一、半群与独异点一、半群与独异点 定义定义7 在独异点中, 如果存在一个元素gS,使每一元素aS, 都有一个相应的hN能把a写成gh,即a=gh，则称此独异点为循环独异点循环独异点。并称元素g是此循环独异点的生成元, 又可说此循环独异点是由g生成的。 例3 (1) 是循环独异点，生成元是1，因为任取i N，当i=0时，0= 10； i0时，有 i= 1+1+1=1i。 (2) 右图是循环独异点，生成元为b, c1=b0,a=b2, b=b1,c=b3; 1=c0,a=c2, b=c3,c=c1。一、半群与独异点一、半群与独异点 定理定理5 每个循环独异点都是可交换的。 证明证明： 设是循环独异点, 其生成元是g, 对任意a、 bS, 存在m、nN, 使gm=a和gn=b, 因此 证毕。abggggggbamnmnnmnm作作业业: P1961, 4, 9, 1013谢谢同学们谢谢同学们! !