离散数学(第15章)陈瑜_第1页
离散数学(第15章)陈瑜_第2页
离散数学(第15章)陈瑜_第3页
离散数学(第15章)陈瑜_第4页
离散数学(第15章)陈瑜_第5页
已阅读5页,还剩220页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

陈瑜Email:chenyu.inbox@g离散数学计算机学院2023/2/41计算机科学与工程学院第15章:半群与群15.1半群2023/2/42计算机科学与工程学院群是一种特殊的代数系统,是最重要的代数系统之一。群的理论广泛应用于数学、物理、化学以及很多人们不太熟悉的领域如社会学等。对计算机科学而言,群在自动化理论、形式语言、语法分析、编码理论等方面都有直接应用,并显示出其强大功能。上一章中已经给出了半群的定义,它要求运算是可结合的。许多常见的代数系统都是半群,甚至是含幺半群。下面是一些典型的半群例子。2023/2/43计算机科学与工程学院群是一种特殊的代数系统,是最重要的代数系统之一。群的理论广泛应用于数学、物理、化学以及很多人们不太熟悉的领域如社会学等。对计算机科学而言,群在自动化理论、形式语言、语法分析、编码理论等方面都有直接应用,并显示出其强大功能。上一章中已经给出了半群的定义,它要求运算是可结合的。许多常见的代数系统都是半群,甚至是含幺半群。下面是一些典型的半群例子。2023/2/44计算机科学与工程学院例:<R,+>满足封闭、可结合、有幺元0的条件,因而是含幺半群。另外,它还满足可换性,每个元x∈R都有加法逆元-x,因此,<R,+>也是一个可换群。<R,×>满足封闭、可结合、有幺元1,因此是含幺半群。注意,因为0无乘法逆元,所以<R,×>只能是含幺半群。2023/2/45计算机科学与工程学院例

设Mm,n表示全休m行n列矩阵构成的集合,+是矩阵加法,那么<Mm,n,+>满足封闭、可结合的条件,元素全为0的m行n列矩阵是幺元,因此<Mm,n,+>是含幺半群。此外,Mm,n中每个矩阵Am,n都有加法逆矩阵-Am,n

,因而<Mm,n,+>还满足逆元条件。2023/2/46计算机科学与工程学院例设F是由定义在非空集合S上的全体函数构成的集合,即F={f:S→S}。对于函数的复合运算“”,<F,>满足封闭性和可结合性,所以是半群。此外,定义在S上的恒等函数Is是<F,>的幺元,所以<F,>又是含幺半群。

2023/2/47计算机科学与工程学院例设∑是非空有限字母表,∑*是由定义在∑上的全体有限长字母串构成的集合,或叫做∑上全体字的集合。在∑*上定义运算为字的连接“”,则<∑*,>满足封闭和可结合的条件,并且空字是系统的幺元,所以<∑*,>是一个含幺半群。半群或含幺半群在计算机科学中有广泛的应用,尤其在从编译技术发展起来的形式语言与自动机理论领域,含幺半群是很重要的的内容之一。下面是半群的一个简单的应用例子。2023/2/48计算机科学与工程学院例设一个简单的液晶显示电子表仅有显示时、分的两个功能,有0、1两个按键。按1键时由正常状态转入调分状态,此时按0键m次可以调增分数m;再按1键则转入调时状态,此时按0键n次,则时数增加n;最后再按1键回复到正常状态。这一调节过程如图(b)所示。(a)(b)2023/2/49计算机科学与工程学院

上面的调分和调时过程可表示为:

或由符号1和0组成的形如10m10n1的字符串集,即字母表∑={0,1}上的一个语言L={10m10n1|m,n≥0}。这种字母串可以被电子表中的微处理器(可以看成是一个小小的计算机)识别并执行,其动作原理就是图15-1.1(b)所示的状态图,称为一个有限自动机,它反映了电子表依令而行的规则。语言L被相应地称为这个自动机所识别的语言。2023/2/410计算机科学与工程学院幂

设<S,*>是一个半群,由于*满足结合律,可定义幂运算,即对xS,可定义:

x¹=x,

x²=x*x,

x³=x*x²=x²*x=x*x*x,

……

xn=xn-1*x=x*xn-1=x*x*x*…*x。

……

如果<S,*>有单位元e,可以定义:x0=e幂运算有如下的公式:(见下页)2023/2/411计算机科学与工程学院定理15.1设<S,*>是半群,aS,m和n是正整数,则:①

am*an=am+n;②(am)n=amn。当<S,*>是含幺半群时,上述结论对任意非负整数m和n都成立。

证明:设m是一个固定的正整数,对n进行归纳。对于①:

当n=1时,由幂的定义可知结论成立;设结论对n=k时成立,则am*ak+1=am*(ak*a)(由幂的定义)

=(am*ak)*a(可结合性)=(am+k)*a(归纳假设)=am+(k+1)

由归纳法可知,结论成立。2023/2/412计算机科学与工程学院定理15.1设<S,*>是半群,aS,m和n是正整数,则:①

am*an=am+n;②(am)n=amn。当<S,*>是含幺半群时,上述结论对任意非负整数m和n都成立。

证明:设m是一个固定的正整数,对n进行归纳。对于①:

当n=1时,由幂的定义可知结论成立;设结论对n=k时成立,则am*ak+1=am*(ak*a)(由幂的定义)

=(am*ak)*a(可结合性)=(am+k)*a(归纳假设)=am+(k+1)

由归纳法可知,结论成立。2023/2/413计算机科学与工程学院定理15.1设<S,*>是半群,aS,m和n是正整数,则:①

am*an=am+n;②(am)n=amn。当<S,*>是含幺半群时,上述结论对任意非负整数m和n都成立。

证明:设m是一个固定的正整数,对n进行归纳。对于①:

当n=1时,由幂的定义可知结论成立;设结论对n=k时成立,则am*ak+1=am*(ak*a)(由幂的定义)

=(am*ak)*a(可结合性)=(am+k)*a(归纳假设)=am+(k+1)

由归纳法可知,结论成立。对于②可以类似的进行归纳证明。2023/2/414计算机科学与工程学院注意:当运算为加法“+”时,上述定理应写成:

ma+na=(m+n)an(ma)=(mn)a2023/2/415计算机科学与工程学院定理15.2

有限半群S,必有幂等元,即存在aS,a2=a

。(参见教材p183)

注意此处的a2的正确含义!a*a=a2,不是数学中的乘法!2023/2/416计算机科学与工程学院定理15.2

有限半群S,必有幂等元,即存在aS,a2=a

。

证明:如果S中有幺元e,则e就是幂等元。如果S中没有幺元,任取bS。由集合S的有限性,必有:

bi=bj=bj-ibi(j>i)所以,对任何t>i都有:bt=bj-ibt(注:t=i+l,bt=bi+l=bi*b1)=b2(j-i)bt=...(反复迭代)=bk(j-i)bt

(此处k(j-i)>i)令t=k(j-i),则得到bt=btbt即bt是幂等元。2023/2/417计算机科学与工程学院定理15.2

有限半群S,必有幂等元,即存在aS,a2=a

。

证明:如果S中有幺元e,则e就是幂等元。如果S中没有幺元,任取bS。由集合S的有限性,必有:

bi=bj=bj-ibi(j>i)所以,对任何t>i都有:bt=bj-ibt(例如:t=i+l,bt=bi+l=bi*b1)

=b2(j-i)bt=...(反复迭代)=bk(j-i)bt

(此处k(j-i)>i)令t=k(j-i),则得到bt=btbt即bt是幂等元。2023/2/418计算机科学与工程学院定理15.2

有限半群S,必有幂等元,即存在aS,a2=a

。

证明:如果S中有幺元e,则e就是幂等元。如果S中没有幺元,任取bS。由集合S的有限性,必有:

bi=bj=bj-ibi(j>i)所以,对任何t>i都有:bt=bj-ibt(例如:t=i+l,bt=bi+l=bi*b1)=b2(j-i)bt=...(反复迭代)

=bk(j-i)bt

(此处k(j-i)>i)令t=k(j-i),则得到bt=btbt即bt是幂等元。2023/2/419计算机科学与工程学院定理15.2

有限半群S,必有幂等元,即存在aS,a2=a

。

证明:如果S中有幺元e,则e就是幂等元。如果S中没有幺元,任取bS。由集合S的有限性,必有:

bi=bj=bj-ibi(j>i)所以,对任何t>i都有:bt=bj-ibt(例如:t=i+l,bt=bi+l=bi*b1)=b2(j-i)bt=...(反复迭代)

=bk(j-i)bt

(此处k(j-i)>i)令t=k(j-i),则得到bt=btbt即bt是幂等元。

注意,若S不是有限集,则不一定有幂等元。例如,正整数集关于加法运算是一个半群,但是不存在幂等元。含幺半群至少含有一个幂等元,那就是幺元。一个半群甚至含幺半群也可以含有多个幂等元。不难验证<2S,∩>是以S为幺元的含幺半群。由于集合交运算是幂等的,所以中每个元都是幂等元。2023/2/420计算机科学与工程学院子半群定义15.1如果<S,*>是半群,T是S的非空子集,且T对运算*是封闭的,则称<T,*>是半群<S,*>的子半群;如果<S,*,e>是含幺半群,T∈S,e∈T,且T对运算*是封闭的,则称<T,*,e>是含幺半群<S,*,e>的子含幺半群。

例:半群<R,×>的子代数<[0,1],×>,<Z,×>,<R+,×>都是<R,×>的子半群。2023/2/421计算机科学与工程学院子半群定义15.1如果<S,*>是半群,T是S的非空子集,且T对运算*是封闭的,则称<T,*>是半群<S,*>的子半群;如果<S,*,e>是含幺半群,T∈S,e∈T,且T对运算*是封闭的,则称<T,*,e>是含幺半群<S,*,e>的子含幺半群。

例:半群<R,×>的子代数<[0,1],×>,<Z,×>,<R+,×>都是<R,×>的子半群。2023/2/422计算机科学与工程学院子半群定义15.1如果<S,*>是半群,T是S的非空子集,且T对运算*是封闭的,则称<T,*>是半群<S,*>的子半群;如果<S,*,e>是含幺半群,T∈S,e∈T,且T对运算*是封闭的,则称<T,*,e>是含幺半群<S,*,e>的子含幺半群。

例:半群<R,×>的子代数<[0,1],×>,<Z,×>,<R+,×>都是<R,×>的子半群。2023/2/423计算机科学与工程学院例设<S,*>是一个可换的含幺半群,M是它的所有的等幂元构成的集合,则<M,*>是<S,*>的一个子含幺半群。证明:(1)显然,MS;(2)<S,*>是含幺半群,所以幺元e存在,又e*e=e,则e是一个等幂元,即有e∈M,所以M是非空的;(3)e∈M;(4)对任意a,b∈M,有(a*b)*(a*b)=a*(b*a)*b=a*(a*b)*b =(a*a)*(b*b)=a*b, 即运算“*”关于集合M是封闭的运算。由(1)、(2)、(3)、(4)知:<M,*>是<S,*>的一个子含幺半群。2023/2/424计算机科学与工程学院例设<S,*>是一个可换的含幺半群,M是它的所有的等幂元构成的集合,则<M,*>是<S,*>的一个子含幺半群。证明:(1)

显然,MS;(2)<S,*>是含幺半群,所以幺元e存在,又e*e=e,则e是一个等幂元,即有e∈M,所以M是非空的;(3)e∈M;(4)对任意a,b∈M,有(a*b)*(a*b)=a*(b*a)*b=a*(a*b)*b =(a*a)*(b*b)=a*b, 即运算“*”关于集合M是封闭的运算。由(1)、(2)、(3)、(4)知:<M,*>是<S,*>的一个子含幺半群。2023/2/425计算机科学与工程学院例设<S,*>是一个可换的含幺半群,M是它的所有的等幂元构成的集合,则<M,*>是<S,*>的一个子含幺半群。证明:(1)

显然,MS;(2)<S,*>是含幺半群,所以幺元e存在,又e*e=e,则e是一个等幂元,即有e∈M,所以M是非空的;(3)e∈M;(4)对任意a,b∈M,有(a*b)*(a*b)=a*(b*a)*b=a*(a*b)*b =(a*a)*(b*b)=a*b, 即运算“*”关于集合M是封闭的运算。由(1)、(2)、(3)、(4)知:<M,*>是<S,*>的一个子含幺半群。2023/2/426计算机科学与工程学院例设<S,*>是一个可换的含幺半群,M是它的所有的等幂元构成的集合,则<M,*>是<S,*>的一个子含幺半群。证明:(1)

显然,MS;(2)

<S,*>是含幺半群,所以幺元e存在,又e*e=e,则e是一个等幂元,即有e∈M,所以M是非空的;(3)e∈M;(4)对任意a,b∈M,有(a*b)*(a*b)=a*(b*a)*b=a*(a*b)*b =(a*a)*(b*b)=a*b, 即运算“*”关于集合M是封闭的运算。由(1)、(2)、(3)、(4)知:<M,*>是<S,*>的一个子含幺半群。2023/2/427计算机科学与工程学院例设<S,*>是一个可换的含幺半群,M是它的所有的等幂元构成的集合,则<M,*>是<S,*>的一个子含幺半群。证明:(1)

显然,MS;(2)

<S,*>是含幺半群,所以幺元e存在,又e*e=e,则e是一个等幂元,即有e∈M,所以M是非空的;(3)

e∈M;(4)对任意a,b∈M,有(a*b)*(a*b)=a*(b*a)*b=a*(a*b)*b =(a*a)*(b*b)=a*b, 即运算“*”关于集合M是封闭的运算。

由(1)、(2)、(3)、(4)知:<M,*>是<S,*>的一个子含幺半群。2023/2/428计算机科学与工程学院习题P1932、4、62023/2/429计算机科学与工程学院15.2群和子群2023/2/430计算机科学与工程学院主要内容一个非常重要的代数系统——群。主要从以下几个方面来介绍:群的概念和基本性质。群的子群和性质。群中元素的周期和性质。特殊群及其性质,如交换群(Abel群)、循环群。陪集和拉格郎日定理。2023/2/431计算机科学与工程学院在§14.2中已经为群下了定义,把群看成是在含幺半群的基础上加上每元有逆元的条件,其核心内容可用“闭、结、幺、逆”四个字予以概括。下面是一些典型的群的例子。2023/2/432计算机科学与工程学院例:我们已经知道<Z,+>是含幺半群,由于每个整数a都有加法逆元-a,所以<Z,+>是群,一般叫做整数加群。同理,是<R,+>实数加群,<Q,+>是有理数加群。对于数的乘法,<Z,×>是含幺半群而不是群,因为整数一般无Z中的乘法逆元。<R-{0},×>是实数乘群,它的幺元是1,每元的乘法逆元为1/a。2023/2/433计算机科学与工程学院例:设Zk表示整数集Z上的模k剩余类集合,即:Zk={[0],[1],[2],…,[k-1]}。在Zk上定义运算和如下:

那么,是群。这是因为封闭性和可结合性是明显成立的,[0]是幺元,每元[i]的逆元是[k-i]。群习惯上又称为剩余类加群。

2023/2/434计算机科学与工程学院例设n个元素的集合A上的全体置换构成集合Sn。由第6章中关于置换的讨论,Sn中两个置换的复合仍然是A上的一个置换,因而运算是封闭的;其次,由于函数的复合是可结合的,因而置换的复合也是可结合的;在Sn中存在幺置换=(1),使对任何Sn中的置换均有,因而=(1)是幺元;把每个元素的x变成y的置换,其逆置换则把元素y变成x,因而每个置换都有逆。由此可知,<Sn,

>构成群,这个群一般称为n次对称群,是一类重要的群。群尽管是用“闭、结、幺、逆”四个条件来定义的,但是它还可以用别的形式等价地定义。2023/2/435计算机科学与工程学院例设n个元素的集合A上的全体置换构成集合Sn。由第6章中关于置换的讨论,Sn中两个置换的复合仍然是A上的一个置换,因而运算是封闭的;其次,由于函数的复合是可结合的,因而置换的复合也是可结合的;在Sn中存在幺置换=(1),使对任何Sn中的置换均有,因而=(1)是幺元;把每个元素的x变成y的置换,其逆置换则把元素y变成x,因而每个置换都有逆。由此可知,<Sn,

>构成群,这个群一般称为n次对称群,是一类重要的群。群尽管是用“闭、结、幺、逆”四个条件来定义的,但是它还可以用别的形式等价地定义。2023/2/436计算机科学与工程学院群定理15-2.1如果<G,*>是半群,并且对a,bG,都存在x,yG使x*a=b,a*y=b,则<G,*>是群。群中元素的数目称为群的阶。

证明:设aG,方程x*a=a的解为e1,∵对tG,方程a*y=t有解y0,∴e1*t=e1*(a*y0)=(e1*a)*y0=a*y0=t

即对tG,必有e1*t=t,e1是G中的左幺元。同样可以证明G中有右幺元e2,所以G中有幺元e。同理,对bG,方程x*b=e有解x0,这个x0是b的左逆元,方程b*y=e的解是b的右逆元,从而b有逆元。所以,<G,*>是群。2023/2/437计算机科学与工程学院群定理15.3如果<G,*>是半群,并且对a,bG,都存在x,yG使x*a=b,a*y=b,则<G,*>是群。群中元素的数目称为群的阶。证明:

设aG,方程x*a=a的解为e1,∵对tG,方程a*y=t有解y0,∴e1*t=e1*(a*y0)=(e1*a)*y0=a*y0=t

即对tG,必有e1*t=t,e1是G中的左幺元。同样可以证明G中有右幺元e2,所以G中有幺元e。同理,对bG,方程x*b=e有解x0,这个x0是b的左逆元,方程b*y=e的解是b的右逆元,从而b有逆元。所以,<G,*>是群。2023/2/438计算机科学与工程学院群定理15.3如果<G,*>是半群,并且对a,bG,都存在x,yG使x*a=b,a*y=b,则<G,*>是群。群中元素的数目称为群的阶。证明:

设aG,方程x*a=a的解为e1,∵对tG,方程a*y=t有解y0,∴e1*t=e1*(a*y0)=(e1*a)*y0=a*y0=t

即对tG,必有e1*t=t,e1是G中的左幺元。同样可以证明G中有右幺元e2,所以G中有幺元e。

同理,对bG,方程x*b=e有解x0,这个x0是b的左逆元,方程b*y=e的解是b的右逆元,从而b有逆元。所以,<G,*>是群。2023/2/439计算机科学与工程学院群定理15.3如果<G,*>是半群,并且对a,bG,都存在x,yG使x*a=b,a*y=b,则<G,*>是群。群中元素的数目称为群的阶。证明:

设aG,方程x*a=a的解为e1,∵对tG,方程a*y=t有解y0,∴e1*t=e1*(a*y0)=(e1*a)*y0=a*y0=t

即对tG,必有e1*t=t,e1是G中的左幺元。

同样可以证明G中有右幺元e2,所以G中有幺元e。

同理,对bG,方程x*b=e有解x0,这个x0是b的左逆元,方程b*y=e的解是b的右逆元,从而b有逆元。所以,<G,*>是群。设aG,方程a*y=a的解为e2,∵对tG,方程x*a=t有解x0,∴t*e2=(x0*a)*e2=x0*(a*e2)=x0*a=t

即对tG,必有t*e2=t,e2是G中的右幺元。2023/2/440计算机科学与工程学院群定理15.3如果<G,*>是半群,并且对a,bG,都存在x,yG使x*a=b,a*y=b,则<G,*>是群。群中元素的数目称为群的阶。证明:

设aG,方程x*a=a的解为e1,∵对tG,方程a*y=t有解y0,∴e1*t=e1*(a*y0)=(e1*a)*y0=a*y0=t

即对tG,必有e1*t=t,e1是G中的左幺元。同样可以证明G中有右幺元e2,所以G中有幺元e。

同理,对bG,方程x*b=e有解x0,这个x0是b的左逆元,方程b*y=e的解是b的右逆元,从而b有逆元。所以,<G,*>是群。2023/2/441计算机科学与工程学院群定理15.3如果<G,*>是半群,并且对a,bG,都存在x,yG使x*a=b,a*y=b,则<G,*>是群。群中元素的数目称为群的阶。证明:

设aG,方程x*a=a的解为e1,∵对tG,方程a*y=t有解y0,∴e1*t=e1*(a*y0)=(e1*a)*y0=a*y0=t

即对tG,必有e1*t=t,e1是G中的左幺元。同样可以证明G中有右幺元e2,所以G中有幺元e。

同理,对bG,方程x*b=e有解x0,这个x0是b的左逆元,方程b*y=e的解是b的右逆元,从而b有逆元。所以,<G,*>是群。这个定理说明,在群的定义中幺元及逆元的条件可用方程有解来代替。另外,群定义中的幺元条件可以用存在左幺元(或右幺元)的条件代替,逆元的条件可以用左逆元(或右逆元)代替。2023/2/442计算机科学与工程学院定理15.4群G中每个元素都是可消去的,即运算满足消去律;(即如果a*b=a*c,则必有b=c)群G中除幺元e外无其它幂等元;群G的运算表中任意一行(列)都没有两个相同的元素(重复元素);2023/2/443计算机科学与工程学院定理15.4群G中每个元素都是可消去的,即运算满足消去律;(即如果a*b=a*c,则必有b=c)群G中除幺元e外无其它幂等元;群G的运算表中任意一行(列)都没有两个相同的元素(重复元素);证明:由于群G中每个元素都有逆元a-1,由a*b=a*c

a-1*a*b=a-1*a*c,即b=c2023/2/444计算机科学与工程学院定理15.4群G中每个元素都是可消去的,即运算满足消去律;(即如果a*b=a*c,则必有b=c)群G中除幺元e外无其它幂等元;群G的运算表中任意一行(列)都没有两个相同的元素(重复元素);2023/2/445计算机科学与工程学院定理15.4群G中每个元素都是可消去的,即运算满足消去律;(即如果a*b=a*c,则必有b=c)群G中除幺元e外无其它幂等元;群G的运算表中任意一行(列)都没有两个相同的元素(重复元素);证明:(反证法)假设a是群G中非幺元的幂等元,即a*a=a,且a≠e。因此a*a=a*e,由(1)知a=e,矛盾。2023/2/446计算机科学与工程学院定理15.4群G中每个元素都是可消去的,即运算满足消去律;(即如果a*b=a*c,则必有b=c)群G中除幺元e外无其它幂等元;群G的运算表中任意一行(列)都没有两个相同的元素(重复元素);2023/2/447计算机科学与工程学院定理15.4群G中每个元素都是可消去的,即运算满足消去律;(即如果a*b=a*c,则必有b=c)群G中除幺元e外无其它幂等元;群G的运算表中任意一行(列)都没有两个相同的元素(重复元素);证明:(反证法)假设群G的运算表中某一行(列)有两个相同的元素,设为a,并设它们所在的行表头元素为b,列表头元素分别为c1,c2,这时显然有c1≠c2。而a=bc1=bc2,由(1)得c1=c2,矛盾。

2023/2/448计算机科学与工程学院补充例:构造一个3阶群。

解:设e是幺元,G={e,a,b}

则可构造的3阶群如下:2023/2/449计算机科学与工程学院定理15.5

设<G,*>是群,a∈G。构造映射,使得对任意x∈G,,令

,则对于函数的复合运算“”,<H,>是群。(P185)

定理的证明留与读者练习

这个定理说明:可以由一个已知的群来构造出一个新的群。2023/2/450计算机科学与工程学院例:设X是任意集合,S={f:X→X|f是双射函数},即S是X上的所有双射函数的集合,运算“。”是函数的复合运算,证明<S,。>是群。

证明:(1)封闭性:f,g∈S,f、g是双射,则f。g也是双射,因此f。g∈S,故封闭性成立。(2)结合律:由函数的运算“。”满足结合律,因此在S中也满足结合律。

2023/2/451计算机科学与工程学院例:设X是任意集合,S={f:X→X|f是双射函数},即S是X上的所有双射函数的集合,运算“。”是函数的复合运算,证明<S,。>是群。

证明:

(1)封闭性:f,g∈S,f、g是双射,则f。g也是双射,因此f。g∈S,故封闭性成立。

(2)结合律:由函数的运算“。”满足结合律,因此在S中也满足结合律。

2023/2/452计算机科学与工程学院例:设X是任意集合,S={f:X→X|f是双射函数},即S是X上的所有双射函数的集合,运算“。”是函数的复合运算,证明<S,。>是群。

证明:

(1)封闭性:f,g∈S,f、g是双射,则f。g也是双射,因此f。g∈S,故封闭性成立。

(2)结合律:由函数的运算“。”满足结合律,因此在S中也满足结合律。

2023/2/453计算机科学与工程学院例:设X是任意集合,S={f:X→X|f是双射函数},即S是X上的所有双射函数的集合,运算“。”是函数的复合运算,证明<S,。>是群。

证明:(续)

(3)幺元:恒等映射IX∈S,且f∈S,有:

IX。f=f。IX=f,因此IX是<S,。>的幺元。

(4)f,g∈S是双射,则f的逆函数f-1存在,f-1也是双射,即f-1∈S,且有:f-1。f=f。f-1=IX,因此,f的逆函数f-1就是f关于“。”的逆元,即S的任意元素都有逆元。综合(1)(2)(3)(4)知<S,。>是群。2023/2/454计算机科学与工程学院例:设X是任意集合,S={f:X→X|f是双射函数},即S是X上的所有双射函数的集合,运算“。”是函数的复合运算,证明<S,。>是群。

证明:(续)

(3)幺元:恒等映射IX∈S,且f∈S,有:

IX。f=f。IX=f,因此IX是<S,。>的幺元。

(4)

f,g∈S是双射,则f的逆函数f-1存在,f-1也是双射,即f-1∈S,且有:f-1。f=f。f-1=IX,因此,f的逆函数f-1就是f关于“。”的逆元,即S的任意元素都有逆元。

综合(1)(2)(3)(4)知<S,。>是群。2023/2/455计算机科学与工程学院课外练习:设A=R-{0,1},在A上定义6个映射如下:对于任意x∈A有:令G={f1,f2,f3,f4,f5,f6}。试证明G关于函数的复合运算“。”构成群<G,。>。2023/2/456计算机科学与工程学院子群定义15.2

设<G,*>是一个群,S是G的一个非空子集,若S也是群,则称<S,*>是<G,*>的一个子群。

一般来说,对任意的群<G,*>,都有两个子群<{e},*>,<G,*>,我们称此两个子群为该群的平凡子群,而若有子群<S,*>,且S{e}和SG,则称<S,*>为<G,*>的真子群。另外,由群中的一个元素也可生成一个子群。定义为:a-k=(ak)-1。2023/2/457计算机科学与工程学院子群定义15.2设<G,*>是一个群,S是G的一个非空子集,若S也是群,则称<S,*>是<G,*>的一个子群。

一般来说,对任意的群<G,*>,都有两个子群<{e},*>,<G,*>,我们称此两个子群为该群的平凡子群,而若有子群<S,*>,且S{e}和SG,则称<S,*>为<G,*>的真子群。另外,由群中的一个元素也可生成一个子群。为此,需要将群中元素的幂扩充到负指数的形式,即定义为:a-k=(ak)-1。2023/2/458计算机科学与工程学院子群定义15.2设<G,*>是一个群,S是G的一个非空子集,若S也是群,则称<S,*>是<G,*>的一个子群。一般来说,对任意的群<G,*>,都有两个子群<{e},*>,<G,*>,我们称此两个子群为该群的平凡子群,而若有子群<S,*>,且S{e}和SG,则称<S,*>为<G,*>的真子群。另外,由群中的一个元素也可生成一个子群。为此,需要将群中元素的幂扩充到负指数的形式,即定义为:a-k=(ak)-1。2023/2/459计算机科学与工程学院定理15.6设<G,*>是一个群,对任意的a∈G,令S={an|n∈Z,Z是整数},则<S,*>是<G,*>的子群。

证明:因为a∈S,所以显然S是G的非空子集。 对任意的an,am∈S,则an*am=an+m, 由n,m∈Z,有n+m∈Z,所以an+m∈S,即运算是封闭的;由S是G的子集可得结合律也成立;由于e=a0S,所以S中有幺元;又∵anS有逆元a-n使an*a-n=e

∴综上所述,<S,*>是<G,*>的子群。2023/2/460计算机科学与工程学院定理15.6设<G,*>是一个群,对任意的a∈G,令S={an|n∈Z,Z是整数},则<S,*>是<G,*>的子群。

证明:

因为a∈S,所以显然S是G的非空子集。

对任意的an,am∈S,则an*am=an+m, 由n,m∈Z,有n+m∈Z,所以an+m∈S,即运算是封闭的;由S是G的子集可得结合律也成立;由于e=a0S,所以S中有幺元;又∵anS有逆元a-n使an*a-n=e

∴综上所述,<S,*>是<G,*>的子群。2023/2/461计算机科学与工程学院定理15.6设<G,*>是一个群,对任意的a∈G,令S={an|n∈Z,Z是整数},则<S,*>是<G,*>的子群。

证明:因为a∈S,所以显然S是G的非空子集。 对任意的an,am∈S,则an*am=an+m,

由n,m∈Z,有n+m∈Z,所以an+m∈S,即运算是封闭的;由S是G的子集可得结合律也成立;由于e=a0S,所以S中有幺元;又∵anS有逆元a-n使an*a-n=e

∴综上所述,<S,*>是<G,*>的子群。2023/2/462计算机科学与工程学院定理15.6设<G,*>是一个群,对任意的a∈G,令S={an|n∈Z,Z是整数},则<S,*>是<G,*>的子群。

证明:因为a∈S,所以显然S是G的非空子集。

对任意的an,am∈S,则an*am=an+m, 由n,m∈Z,有n+m∈Z,所以an+m∈S,即运算是封闭的;由S是G的子集可得结合律也成立;由于e=a0S,所以S中有幺元;又∵anS有逆元a-n使an*a-n=e

∴综上所述,<S,*>是<G,*>的子群。2023/2/463计算机科学与工程学院定理15-2.4设<G,*>是一个群,对任意的a∈G,令S={an|n∈Z,Z是整数},则<S,*>是<G,*>的子群。

证明:因为a∈S,所以显然S是G的非空子集。

对任意的an,am∈S,则an*am=an+m, 由n,m∈Z,有n+m∈Z,所以an+m∈S,即运算是封闭的;由S是G的子集可得结合律也成立;由于e=a0S,所以S中有幺元;

又∵anS有逆元a-n使an*a-n=e

∴综上所述,<S,*>是<G,*>的子群。2023/2/464计算机科学与工程学院特别把由群的一个元素a生成的子群记为(a)。例如在<Z,+>中,由元素2生成的子群(2)是由全体偶数关于加法构成的群,而由元素1生成的子群正好是Z本身。

2023/2/465计算机科学与工程学院定理15.7设<G,*>是一个群,<S,*>是<G,*>的子群,则:

1)子群<S,*>的幺元eS也是群<G,*>的幺元eG;

2)对aS,a在S中的逆元aS-1就是a在G中的逆元aG-1。证明:1)对aS,由于eS是S的幺元, 所以有:eS*a=a*eS=a ① 又SG,所以aG,由eG是G的幺元,所以有: eG*a=a*eG=a ② 由①、②有:eS*a=a*eS=a=eG*a=a*eG, 由于G满足消去律,所以有:eS=eG。2)对aS,由于SG,所以aG,即a在S中的逆元就是a在G中的逆元。2023/2/466计算机科学与工程学院定理15.7设<G,*>是一个群,<S,*>是<G,*>的子群,则:

1)子群<S,*>的幺元eS也是群<G,*>的幺元eG;

2)对aS,a在S中的逆元aS-1就是a在G中的逆元aG-1。证明:1)对aS,由于eS是S的幺元, 所以有:eS*a=a*eS=a ① 又SG,所以aG,由eG是G的幺元,所以有: eG*a=a*eG=a ② 由①、②有:eS*a=a*eS=a=eG*a=a*eG, 由于G满足消去律,所以有:eS=eG。2)对aS,由于SG,所以aG,即a在S中的逆元就是a在G中的逆元。2023/2/467计算机科学与工程学院定理15.7设<G,*>是一个群,<S,*>是<G,*>的子群,则:

1)子群<S,*>的幺元eS也是群<G,*>的幺元eG;

2)对aS,a在S中的逆元aS-1就是a在G中的逆元aG-1。证明:1)对aS,由于eS是S的幺元, 所以有:eS*a=a*eS=a ①

又SG,所以aG,由eG是G的幺元,所以有: eG*a=a*eG=a ② 由①、②有:eS*a=a*eS=a=eG*a=a*eG, 由于G满足消去律,所以有:eS=eG。2)对aS,由于SG,所以aG,即a在S中的逆元就是a在G中的逆元。2023/2/468计算机科学与工程学院定理15.7设<G,*>是一个群,<S,*>是<G,*>的子群,则:

1)子群<S,*>的幺元eS也是群<G,*>的幺元eG;

2)对aS,a在S中的逆元aS-1就是a在G中的逆元aG-1。证明:1)对aS,由于eS是S的幺元, 所以有:eS*a=a*eS=a ① 又SG,所以aG,由eG是G的幺元,所以有: eG*a=a*eG=a ②

由①、②有:eS*a=a*eS=a=eG*a=a*eG, 由于G满足消去律,所以有:eS=eG。2)对aS,由于SG,所以aG,即a在S中的逆元就是a在G中的逆元。2023/2/469计算机科学与工程学院定理15.7设<G,*>是一个群,<S,*>是<G,*>的子群,则:

1)子群<S,*>的幺元eS也是群<G,*>的幺元eG;

2)对aS,a在S中的逆元aS-1就是a在G中的逆元aG-1。证明:1)对aS,由于eS是S的幺元, 所以有:eS*a=a*eS=a ① 又SG,所以aG,由eG是G的幺元,所以有: eG*a=a*eG=a ② 由①、②有:eS*a=a*eS=a=eG*a=a*eG, 由于G满足消去律,所以有:eS=eG。

2)对aS,由于SG,所以aG,即a在S中的逆元就是a在G中的逆元。2023/2/470计算机科学与工程学院定理15.8设<G,*>是一个群,S是G的一个非空子集,则<S,*>是<G,*>的子群的充要条件是:对a,bS,有a*b-1S。

证明:“”设S是G的子群,对aS,由群的定义知,b-1S,即有a*b-1S。所以必要性成立;“”由子群的定义知,需证明如下四点:

1)S是非空的子集;2023/2/471计算机科学与工程学院定理15.8设<G,*>是一个群,S是G的一个非空子集,则<S,*>是<G,*>的子群的充要条件是:对a,bS,有a*b-1S。

证明:

“”设S是G的子群,对aS,由群的定义知,b-1S,即有a*b-1S。所以必要性成立;

“”由子群的定义知,需证明如下四点:

1)S是非空的子集;2023/2/472计算机科学与工程学院定理15.8设<G,*>是一个群,S是G的一个非空子集,则<S,*>是<G,*>的子群的充要条件是:对a,bS,有a*b-1S。证明:“”设S是G的子群,对aS,由群的定义知,b-1S,即有a*b-1S。所以必要性成立;

“”由子群的定义知,需证明如下四点:

1)

S是非空的子集;2023/2/473计算机科学与工程学院2)

幺元存在:由于SΦ,所以有aS,由对a,bS,有a*b-¹S,取a=b,有eG=a*a-¹S;3)逆元存在:对a,bS,有a*b-1S, 对bS,由eGS,有b-¹=eG*b-¹S;4)封闭性:对a,bS,由3)知:b-¹S,由条件知:a*(b-¹)-¹S,即a*bS.由1)、2)、3)、4)知:<S,*>是<G,*>的子群。2023/2/474计算机科学与工程学院2)

幺元存在:由于SΦ,所以有aS,由对a,bS,有a*b-¹S,取a=b,有eG=a*a-¹S;3)

逆元存在:对a,bS,有a*b-1S, 对bS,由eGS,有b-¹=eG*b-¹S;4)封闭性:对a,bS,由3)知:b-¹S,由条件知:a*(b-¹)-¹S,即a*bS.由1)、2)、3)、4)知:<S,*>是<G,*>的子群。2023/2/475计算机科学与工程学院2)

幺元存在:由于SΦ,所以有aS,由对a,bS,有a*b-¹S,取a=b,有eG=a*a-¹S;3)

逆元存在:对a,bS,有a*b-1S, 对bS,由eGS,有b-¹=eG*b-¹S;4)

封闭性:对a,bS,由3)知:b-¹S,由条件知:a*(b-¹)-¹S,即a*bS.由1)、2)、3)、4)知:<S,*>是<G,*>的子群。2023/2/476计算机科学与工程学院例:

设<G,*>是一个群,令:C={a|aG且对xG,有:a*x=x*a}

证明<C,*>是<G,*>的一个子群。

证明:1)非空性:对xG,由于幺元eG存在,所以有:e*x=x*e=x,即eC,所以C是非空的;

2)封闭性:对a,bC,则有:对xGa*x=x*a, b*x=x*b, ∴(a*b)*x=a*(b*x)=a*(x*b)

=(a*x)*b=(x*a)*b=x*(a*b), 即:a*bC;2023/2/477计算机科学与工程学院例:

设<G,*>是一个群,令:C={a|aG且对xG,有:a*x=x*a}

证明<C,*>是<G,*>的一个子群。证明:

1)非空性:对xG,由于幺元eG存在,所以有:e*x=x*e=x,即eC,所以C是非空的;

2)封闭性:对a,bC,则有:对xGa*x=x*a, b*x=x*b, ∴(a*b)*x=a*(b*x)=a*(x*b)

=(a*x)*b=(x*a)*b=x*(a*b), 即:a*bC;2023/2/478计算机科学与工程学院例:

设<G,*>是一个群,令:C={a|aG且对xG,有:a*x=x*a}

证明<C,*>是<G,*>的一个子群。证明:

1)非空性:对xG,由于幺元eG存在,所以有:e*x=x*e=x,即eC,所以C是非空的;

2)

封闭性:对a,bC,则有:对xGa*x=x*a, b*x=x*b, ∴(a*b)*x=a*(b*x)=a*(x*b)

=(a*x)*b=(x*a)*b=x*(a*b), 即:a*bC;2023/2/479计算机科学与工程学院3)、逆元存在:对aC,有:对xG,a*x=x*a

∵CG,∴aG,即有:a-1G,有:a-1*(a*x)*a-1=a-1*(x*a)*a-1, 即有:x*a-1=a-1*x,所以a-1C。由1)、2)、3)知:<C,*>是<G,*>的一个子群。2023/2/480计算机科学与工程学院3)、逆元存在:对aC,有:对xG,a*x=x*a ∵CG,∴aG,即有:a-1G,有:a-1*(a*x)*a-1=a-1*(x*a)*a-1,

即有:x*a-1=a-1*x,所以a-1C。由1)、2)、3)知:<C,*>是<G,*>的一个子群。2023/2/481计算机科学与工程学院3)、逆元存在:对aC,有:对xG,a*x=x*a

∵CG,∴aG,即有:a-1G,有:a-1*(a*x)*a-1=a-1*(x*a)*a-1, 即有:x*a-1=a-1*x,所以a-1C。由1)、2)、3)知:<C,*>是<G,*>的一个子群。2023/2/482计算机科学与工程学院例:设<Z,+>是一个整数加群,令:H={nk|kZ且n是一个取定的自然数},证明<H,+>是<Z,+>的一个子群。证明:

1)非空性:显然;2)封闭性: 对a,bH,有a=nk1,b=nk2

(k1,k2Z),

a+b=nk1+nk2=n(k1+k2)H

(k1+k2Z);3)逆元存在:对aH,有a=nk1

(k1Z), 则a-¹=-a=-nk1=n(-k1)H

(-k1Z)。由1),2),3)知<H,+>是<Z,+>的一个子群。2023/2/483计算机科学与工程学院例:设<Z,+>是一个整数加群,令:H={nk|kZ且n是一个取定的自然数},证明<H,+>是<Z,+>的一个子群。证明:

1)非空性:显然;2)封闭性: 对a,bH,有a=nk1,b=nk2

(k1,k2Z),

a+b=nk1+nk2=n(k1+k2)H

(k1+k2Z);3)逆元存在:对aH,有a=nk1

(k1Z), 则a-¹=-a=-nk1=n(-k1)H

(-k1Z)。由1),2),3)知<H,+>是<Z,+>的一个子群。2023/2/484计算机科学与工程学院例:设<Z,+>是一个整数加群,令:H={nk|kZ且n是一个取定的自然数},证明<H,+>是<Z,+>的一个子群。证明:

1)非空性:显然;2)封闭性:

对a,bH,有a=nk1,b=nk2

(k1,k2Z),

a+b=nk1+nk2=n(k1+k2)H

(k1+k2Z);3)逆元存在:对aH,有a=nk1

(k1Z), 则a-¹=-a=-nk1=n(-k1)H

(-k1Z)。由1),2),3)知<H,+>是<Z,+>的一个子群。2023/2/485计算机科学与工程学院例:设<G,*>是一个群,H1,H2是G的两个子群。证明H=H1∩H2是G的子群。证明1)、非空性:由于H1,H2是G的两个子群,所以有:eH1,eH2,即有eH1∩H2;2)、封闭性:对a,bH,有a,bH1∩H2, 即a,bH1,a,bH2, 由于H1,H2都是G的子群,所以有:

a*bH1,a*bH2,即有:a*bH1∩H23)、逆元存在:对aH,有aH1∩H2,即aH1,aH2,由于H1,H2都是G的子群,所以有:

a-1H1,a-1H2,即有:a-1H1∩H2。 由1)、2)、3)知:<H,*>是<G,*>的一个子群。2023/2/486计算机科学与工程学院例:设<G,*>是一个群,H1,H2是G的两个子群。证明H=H1∩H2是G的子群。证明

1)、非空性:由于H1,H2是G的两个子群,所以有:eH1,eH2,即有eH1∩H2;2)、封闭性:对a,bH,有a,bH1∩H2, 即a,bH1,a,bH2, 由于H1,H2都是G的子群,所以有:

a*bH1,a*bH2,即有:a*bH1∩H23)、逆元存在:对aH,有aH1∩H2,即aH1,aH2,由于H1,H2都是G的子群,所以有:

a-1H1,a-1H2,即有:a-1H1∩H2。 由1)、2)、3)知:<H,*>是<G,*>的一个子群。2023/2/487计算机科学与工程学院例:设<G,*>是一个群,H1,H2是G的两个子群。证明H=H1∩H2是G的子群。证明

1)、非空性:由于H1,H2是G的两个子群,所以有:eH1,eH2,即有eH1∩H2;2)、封闭性:对a,bH,有a,bH1∩H2, 即a,bH1,a,bH2, 由于H1,H2都是G的子群,所以有:

a*bH1,a*bH2,即有:a*bH1∩H23)、逆元存在:对aH,有aH1∩H2,即aH1,aH2,由于H1,H2都是G的子群,所以有:

a-1H1,a-1H2,即有:a-1H1∩H2。 由1)、2)、3)知:<H,*>是<G,*>的一个子群。2023/2/488计算机科学与工程学院例:设<G,*>是一个群,H1,H2是G的两个子群。证明H=H1∩H2是G的子群。证明

1)、非空性:由于H1,H2是G的两个子群,所以有:eH1,eH2,即有eH1∩H2;2)、封闭性:对a,bH,有a,bH1∩H2, 即a,bH1,a,bH2, 由于H1,H2都是G的子群,所以有:

a*bH1,a*bH2,即有:a*bH1∩H23)、逆元存在:对aH,有aH1∩H2,即aH1,aH2,由于H1,H2都是G的子群,所以有:

a-1H1,a-1H2,即有:a-1H1∩H2。

由1)、2)、3)知:<H,*>是<G,*>的一个子群。2023/2/489计算机科学与工程学院推广设<G,*>是一个群,H1,H2,…,Hn是G的n个子群,则有H=H1∩H2∩…∩Hn是G的子群。2023/2/490计算机科学与工程学院☆复习若整数m和n关于模d的余数相同,称m和n(关于模d)是同余的,记为:

n≡m(mod)d同余是整数之间的一种重要关系。模d同余的数的全体构成的集合称为一个同余类。这个集合可以表示成:

[n]d={x|n≡x(mod)d}n=m+kdk为整数2023/2/491计算机科学与工程学院☆复习Zk表示整数集Z上的模k剩余类集合,即

Zk={[0],[1],[2],…,[k-1]}例:n=6,则:

Zn={[0],[1],[2],[3],[4],[5]}[0]={…,-12,-6,0,6,12,18,…}[1]={…,-11,-5,1,7,13,19,…}[2]={…,-10,-4,2,8,14,20,…}…2023/2/492计算机科学与工程学院☆例:设Zk表示整数集Z上的模k剩余类集合,即Zk={[0],[1],[2],…,[k-1]}在Zk上定义运算和如下:[i][j]=[t](i+j)t(modk)[i][j]=[t]ijt(modk)<Zk,>是群(剩余类加群)。[0]是的幺元,每元[i]的逆元是[k-i]。<Zk,>不是群,因为虽然它满足封闭性和可结合性,且[1]是它的幺元,但是[0]无逆元,所以它仅仅是一个含幺半群。2023/2/493计算机科学与工程学院☆例:设Zk表示整数集Z上的模k剩余类集合,即Zk={[0],[1],[2],…,[k-1]}在Zk上定义运算和如下:[i][j]=[t](i+j)t(modk)[i][j]=[t]ijt(modk)<Zk,>是群(剩余类加群)。[0]是的幺元,每元[i]的逆元是[k-i]。<Zk,>不是群,因为虽然它满足封闭性和可结合性,且[1]是它的幺元,但是[0]无逆元,所以它仅仅是一个含幺半群。2023/2/494计算机科学与工程学院☆例:设Zk表示整数集Z上的模k剩余类集合,即Zk={[0],[1],[2],…,[k-1]}在Zk上定义运算和如下:[i][j]=[t](i+j)t(modk)[i][j]=[t]ijt(modk)<Zk,>是群(剩余类加群)。[0]是

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论