离散数学 半群和独异点
- 格式:pptx
- 大小:336.20 KB
- 文档页数:12
离散结构半群与独异点教学目标基本要求(1)掌握半群、独异点的定义(2)熟悉半群与独异点的性质(3)了解子系统和直积的概念重点难点(1)判断或证明给定集合和运算是否构成半群、独异点半群、独异点的定义定义:(1)设V=<S, ∘ >是代数系统,∘为二元运算,如果∘运算是可结合的,则称V为半群(semi-group)(2)设V=<S, ∘ >是半群,若e∈S是关于∘运算的单位元,则称V是含幺半群,也叫做独异点(monoid),有时也将独异点V记作V=<S,∘,e>实例(1) <Z+,+>,<N,+>,<Z,+>,<Q,+>,<R,+>都是半群,+是普通加法. 这些半群中除<Z+,+>外都是独异点(2) 设n是大于1的正整数,<M n(R),+>和<M n(R),×>都是半群,也都是独异点,其中+和×分别表示矩阵加法和矩阵乘法(3) <P(B),⊕>为半群,也是独异点,其中⊕为集合对称差运算(4) <Z n, ⊕>为半群,也是独异点,其中Z n={0,1,…,n−1},⊕为模n加法(5) <A A, ∘ >为半群,也是独异点,其中◦为函数的复合运算(6) <R*, ∘ >为半群,其中R*为非零实数集合,∘运算定义如下:∀x, y∈R*, x∘y=y实例例设R*为非零实数集合, 对任意∀x, y∈R*, 规定x∘y =y, 则<R*, ∘ >为半群。
证明: ∀x, y, z∈R*,有(x∘y) ∘z = y∘z = z,x∘ (y∘z)= x∘z= z所以 (x∘y) ∘z = x∘ (y∘z), 运算∘满足结合律故 <R*, ∘ >为半群。
实例例:设Σ是一个非空有限集合,称为字母表,由Σ中有限个字母组成的有序集合(即字符串)称为Σ上的一个字,串中的字母个数m 称为字长,m=0 时,称为空字,记为ε。
16.半群与独异点1)在R中定义二元运算:* ,a*b=a+b+ab,对于任意a,b 属于 R,证明1)是半群2)是独异点1)证明:对于任意 a,b,c属于R(a*b)*c=(a+b+ab)*c=a+b+ab+c+(a+b+ab)c=a+b+c+ab+ac +bc+abca*(b*c)=a*(b+c+bc)=a+b+c+bc+a(b+c+bc)=a+b+c+ab+ac +bc+abc得:(a*b)*c=a*(b*c)所以是半群2)证明:当e=0,那么对于任意 a属于Re*a=0+a+0xb=aa*e=a +0 +b x0=a所以e是该半群的单位元,所以是独异点。
2)设V=是半群,若存在a∈S,使得对于任意的x∈S,有u,v∈S,满足a*u=v*a=x证明V是独异点证明:由题设可知,存在u_0和v_0,使得:a*u_0=v_0*a=a现证明u_0为右单位元:对任意的x∈S,有v∈S,满足x = v*a= v*a*u_0= x*u_0故得,u_0为右单位元。
同理可证v_0为左单位元。
由单位元的性质知 u_0=v_0=e 为单位元。
3 S={a,b,c},*是S上的二元运算,且x*y=x ,对于x,y∈S1. 证明是半群2. 将扩充为一个独异点证明 (x*y)*z=x*z=xx*(y*z)=x*y=x,所以是半群(2)任取e不属于S。
令W = S∪{e},且定义W上的二元运算*1 如下:任意x,y∈S,x *1 y = x;任意x∈S,x *1 e = e *1 x = x;e *1 e = e;则是独异点。
4, V=是半群,a,b,c属于S,若a和c是可交换的,b和c也是可交换的,证明a*b 和c也是可交换的证明 (a*b)*c=a*(b*c)=a*(c*b)=(a*c)*b=(c*a)*b=c*(a*b)得证5 设V=<{a,a},*>是半群,且a*a=b,证明 1)a*b=b*a 2)b*b=b证明1) a*a=b => (a*a)*a=b*a =>a*(a*a)=b*aè a*b=b*a2)当a*b=a,b*b=a*a*b=a*(a*b)=a*a=b 得证当a*b=b, b*b=(a*a)*(a*a)=a*(a*a)*a=(a*b)*a=b*a=b得证6.设V=是半群,任取a=!b,则有a*b=!b*a,证明1)任取a∈S, 有a*a=a证明如果 a*a=c,c=!a,那么 c*a=a*a*a=c*a矛盾2)对于任意a,b,c ∈S,那么a*b*a=a证明如果a*b*a=c,c=!a,那么c*a=a*b*a*a=a*b*a a*c=a*a*b*a=a*b*a,所以a*c=c*a矛盾3) 对于任意a,b,c ∈S,那么a*b*c=a*c证明:c*a*b*c=càa*c*a*b*c=a*cè(a*c*a)*b*c=a*c ->a*b*c=a*c7. V=是可交换半群,若a,b ∈S是V中得幂等元,证明a*b也是V 中的幂等元证明:(a*b)*(a*b)=(b*a)*(a*b)=b*(a*a)*b=b*a*b=(b*a)*b=(a*b)*b=a*(b *b)=a*b8.设V=是半群,e∈S是一个左零元,证明对于任意x∈S,x*e也是一个左零元证明:任意y∈S,(x*e)*y=x*(e*y)=x*e 得证9,证明每个有限半群都有幂等元证明: 任取b∈S 则b,b^2,…皆属于 S,而S是有限的,必存在k>j,b^j=b^k令p=k-j>=1 ,b^k=b^j*b^p=b^k*b^p 从而对于q>k恒有b^q=b^q*b^p因为 p>=1,故存在正整数 n使得np>k,于是b^np=b^np*b^p=(b^np*b^p)*b^p=…=b^np*b^n p.取 a=b^bp, a^2=a10.V= 其中*表示模4乘法,找出V的所有子半群,并说明哪些子半群是V的子独异点。