离散数学(第15章)陈瑜.ppt
《离散数学(第15章)陈瑜.ppt》由会员分享,可在线阅读,更多相关《离散数学(第15章)陈瑜.ppt(224页珍藏版)》请在三一办公上搜索。
1、陈瑜,Email:,离散数学,计算机学院,2023/11/16,计算机科学与工程学院,2,第15章:半群与群15.1 半群,2023/11/16,计算机科学与工程学院,3,群是一种特殊的代数系统,是最重要的代数系统之一。群的理论广泛应用于数学、物理、化学以及很多人们不太熟悉的领域如社会学等。对计算机科学而言,群在自动化理论、形式语言、语法分析、编码理论等方面都有直接应用,并显示出其强大功能。上一章中已经给出了半群的定义,它要求运算是可结合的。许多常见的代数系统都是半群,甚至是含幺半群。下面是一些典型的半群例子。,2023/11/16,计算机科学与工程学院,4,群是一种特殊的代数系统,是最重要的
2、代数系统之一。群的理论广泛应用于数学、物理、化学以及很多人们不太熟悉的领域如社会学等。对计算机科学而言,群在自动化理论、形式语言、语法分析、编码理论等方面都有直接应用,并显示出其强大功能。上一章中已经给出了半群的定义,它要求运算是可结合的。许多常见的代数系统都是半群,甚至是含幺半群。下面是一些典型的半群例子。,2023/11/16,计算机科学与工程学院,5,例:满足封闭、可结合、有幺元0的条件,因而是含幺半群。另外,它还满足可换性,每个元xR都有加法逆元-x,因此,也是一个可换群。满足封闭、可结合、有幺元1,因此是含幺半群。注意,因为0无乘法逆元,所以只能是含幺半群。,2023/11/16,计
3、算机科学与工程学院,6,例 设Mm,n表示全休m行n列矩阵构成的集合,+是矩阵加法,那么满足封闭、可结合的条件,元素全为0的m行n列矩阵是幺元,因此是含幺半群。此外,Mm,n中每个矩阵Am,n都有加法逆矩阵-Am,n,因而还满足逆元条件。,2023/11/16,计算机科学与工程学院,7,例 设F是由定义在非空集合S上的全体函数构成的集合,即F=f:SS。对于函数的复合运算“”,满足封闭性和可结合性,所以是半群。此外,定义在S上的恒等函数Is是的幺元,所以又是含幺半群。,2023/11/16,计算机科学与工程学院,8,例 设是非空有限字母表,*是由定义在上的全体有限长字母串构成的集合,或叫做上全
4、体字的集合。在*上定义运算为字的连接“”,则满足封闭和可结合的条件,并且空字 是系统的幺元,所以是一个含幺半群。半群或含幺半群在计算机科学中有广泛的应用,尤其在从编译技术发展起来的形式语言与自动机理论领域,含幺半群是很重要的的内容之一。下面是半群的一个简单的应用例子。,2023/11/16,计算机科学与工程学院,9,例 设一个简单的液晶显示电子表仅有显示时、分的两个功能,有0、1两个按键。按1键时由正常状态转入调分状态,此时按0键m次可以调增分数m;再按1键则转入调时状态,此时按0键n次,则时数增加n;最后再按1键回复到正常状态。这一调节过程如图(b)所示。,(a),(b),2023/11/1
5、6,计算机科学与工程学院,10,上面的调分和调时过程可表示为:,或由符号1和0组成的形如10m10n1的字符串集,即字母表=0,1上的一个语言L=10m10n1|m,n0。这种字母串可以被电子表中的微处理器(可以看成是一个小小的计算机)识别并执行,其动作原理就是图15-1.1(b)所示的状态图,称为一个有限自动机,它反映了电子表依令而行的规则。语言L被相应地称为这个自动机所识别的语言。,2023/11/16,计算机科学与工程学院,11,幂,设是一个半群,由于*满足结合律,可定义幂运算,即对xS,可定义:x=x,x=x*x,x=x*x=x*x=x*x*x,xn=xn-1*x=x*xn-1=x*x
6、*x*x。如果有单位元e,可以定义:x0=e幂运算有如下的公式:(见下页),2023/11/16,计算机科学与工程学院,12,定理15.1 设是半群,aS,m和n是正整数,则:am*an=am+n;(am)n=amn。当是含幺半群时,上述结论对任意非负整数m和n都成立。证明:设m是一个固定的正整数,对n进行归纳。对于:当n=1时,由幂的定义可知结论成立;设结论对n=k时成立,则 am*ak+1=am*(ak*a)(由幂的定义)=(am*ak)*a(可结合性)=(am+k)*a(归纳假设)=am+(k+1)由归纳法可知,结论成立。,2023/11/16,计算机科学与工程学院,13,定理15.1
7、设是半群,aS,m和n是正整数,则:am*an=am+n;(am)n=amn。当是含幺半群时,上述结论对任意非负整数m和n都成立。证明:设m是一个固定的正整数,对n进行归纳。对于:当n=1时,由幂的定义可知结论成立;设结论对n=k时成立,则 am*ak+1=am*(ak*a)(由幂的定义)=(am*ak)*a(可结合性)=(am+k)*a(归纳假设)=am+(k+1)由归纳法可知,结论成立。,2023/11/16,计算机科学与工程学院,14,定理15.1 设是半群,aS,m和n是正整数,则:am*an=am+n;(am)n=amn。当是含幺半群时,上述结论对任意非负整数m和n都成立。证明:设m
8、是一个固定的正整数,对n进行归纳。对于:当n=1时,由幂的定义可知结论成立;设结论对n=k时成立,则 am*ak+1=am*(ak*a)(由幂的定义)=(am*ak)*a(可结合性)=(am+k)*a(归纳假设)=am+(k+1)由归纳法可知,结论成立。,对于可以类似的进行归纳证明。,2023/11/16,计算机科学与工程学院,15,注意:当运算为加法“+”时,上述定理应写成:ma+na=(m+n)a n(ma)=(mn)a,2023/11/16,计算机科学与工程学院,16,定理15.2 有限半群 S,必有幂等元,即 存在 a S,a2=a。(参见教材p183),注意此处的a2的正确含义!a*
9、a=a2,不是数学中的乘法!,2023/11/16,计算机科学与工程学院,17,定理15.2 有限半群 S,必有幂等元,即 存在 a S,a2=a。,证明:如果S中有幺元 e,则 e 就是幂等元。如果S中没有幺元,任取 bS。由集合S的有限性,必有:bi=bj=bj-i bi(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=bt bt即 bt是幂等元。,2023/11/16,计算机科学与工程学院,18,定理15.2 有限半群 S,必
10、有幂等元,即 存在 a S,a2=a。,证明:如果S中有幺元 e,则 e 就是幂等元。如果S中没有幺元,任取 bS。由集合S的有限性,必有:bi=bj=bj-i bi(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=bt bt即 bt是幂等元。,2023/11/16,计算机科学与工程学院,19,定理15.2 有限半群 S,必有幂等元,即 存在 a S,a2=a。,证明:如果S中有幺元 e,则 e 就是幂等元。如果S中没有幺元,任取
11、 bS。由集合S的有限性,必有:bi=bj=bj-i bi(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=bt bt即 bt是幂等元。,2023/11/16,计算机科学与工程学院,20,定理15.2 有限半群 S,必有幂等元,即 存在 a S,a2=a。,证明:如果S中有幺元 e,则 e 就是幂等元。如果S中没有幺元,任取 bS。由集合S的有限性,必有:bi=bj=bj-i bi(j i),所以,对任何t i 都有:bt=bj-
12、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=bt bt即 bt是幂等元。,注意,若S不是有限集,则不一定有幂等元。例如,正整数集关于加法运算是一个半群,但是不存在幂等元。含幺半群至少含有一个幂等元,那就是幺元。一个半群甚至含幺半群也可以含有多个幂等元。不难验证是以S为幺元的含幺半群。由于集合交运算是幂等的,所以中每个元都是幂等元。,2023/11/16,计算机科学与工程学院,21,子半群,定义15.1如果是半群,T是S的非空子集,且T对运算*是封闭的,则称是半群的子半群;如
13、果是含幺半群,TS,eT,且T对运算*是封闭的,则称是含幺半群的子含幺半群。例:半群的子代数,都是的子半群。,2023/11/16,计算机科学与工程学院,22,子半群,定义15.1如果是半群,T是S的非空子集,且T对运算*是封闭的,则称是半群的子半群;如果是含幺半群,TS,eT,且T对运算*是封闭的,则称是含幺半群的子含幺半群。例:半群的子代数,都是的子半群。,2023/11/16,计算机科学与工程学院,23,子半群,定义15.1如果是半群,T是S的非空子集,且T对运算*是封闭的,则称是半群的子半群;如果是含幺半群,TS,eT,且T对运算*是封闭的,则称是含幺半群的子含幺半群。例:半群的子代数
14、,都是的子半群。,2023/11/16,计算机科学与工程学院,24,例 设是一个可换的含幺半群,M是它的所有的等幂元构成的集合,则是的一个子含幺半群。证明:(1)显然,MS;(2)是含幺半群,所以幺元e存在,又e*ee,则e是一个等幂元,即有eM,所以M是非空的;(3)eM;(4)对任意a,bM,有(a*b)*(a*b)a*(b*a)*ba*(a*b)*b(a*a)*(b*b)a*b,即运算“*”关于集合M是封闭的运算。由(1)、(2)、(3)、(4)知:是的一个子含幺半群。,2023/11/16,计算机科学与工程学院,25,例 设是一个可换的含幺半群,M是它的所有的等幂元构成的集合,则是的一
15、个子含幺半群。证明:(1)显然,MS;(2)是含幺半群,所以幺元e存在,又e*ee,则e是一个等幂元,即有eM,所以M是非空的;(3)eM;(4)对任意a,bM,有(a*b)*(a*b)a*(b*a)*ba*(a*b)*b(a*a)*(b*b)a*b,即运算“*”关于集合M是封闭的运算。由(1)、(2)、(3)、(4)知:是的一个子含幺半群。,2023/11/16,计算机科学与工程学院,26,例 设是一个可换的含幺半群,M是它的所有的等幂元构成的集合,则是的一个子含幺半群。证明:(1)显然,MS;(2)是含幺半群,所以幺元e存在,又e*ee,则e是一个等幂元,即有eM,所以M是非空的;(3)e
16、M;(4)对任意a,bM,有(a*b)*(a*b)a*(b*a)*ba*(a*b)*b(a*a)*(b*b)a*b,即运算“*”关于集合M是封闭的运算。由(1)、(2)、(3)、(4)知:是的一个子含幺半群。,2023/11/16,计算机科学与工程学院,27,例 设是一个可换的含幺半群,M是它的所有的等幂元构成的集合,则是的一个子含幺半群。证明:(1)显然,MS;(2)是含幺半群,所以幺元e存在,又e*ee,则e是一个等幂元,即有eM,所以M是非空的;(3)eM;(4)对任意a,bM,有(a*b)*(a*b)a*(b*a)*ba*(a*b)*b(a*a)*(b*b)a*b,即运算“*”关于集合
17、M是封闭的运算。由(1)、(2)、(3)、(4)知:是的一个子含幺半群。,2023/11/16,计算机科学与工程学院,28,例 设是一个可换的含幺半群,M是它的所有的等幂元构成的集合,则是的一个子含幺半群。证明:(1)显然,MS;(2)是含幺半群,所以幺元e存在,又e*ee,则e是一个等幂元,即有eM,所以M是非空的;(3)eM;(4)对任意a,bM,有(a*b)*(a*b)a*(b*a)*ba*(a*b)*b(a*a)*(b*b)a*b,即运算“*”关于集合M是封闭的运算。由(1)、(2)、(3)、(4)知:是的一个子含幺半群。,2023/11/16,计算机科学与工程学院,29,习题,P19
18、3 2、4、6,2023/11/16,计算机科学与工程学院,30,15.2 群和子群,2023/11/16,计算机科学与工程学院,31,主要内容,一个非常重要的代数系统群。主要从以下几个方面来介绍:群的概念和基本性质。群的子群和性质。群中元素的周期和性质。特殊群及其性质,如交换群(Abel群)、循环群。陪集和拉格郎日定理。,2023/11/16,计算机科学与工程学院,32,在14.2中已经为群下了定义,把群看成是在含幺半群的基础上加上每元有逆元的条件,其核心内容可用“闭、结、幺、逆”四个字予以概括。下面是一些典型的群的例子。,2023/11/16,计算机科学与工程学院,33,例:我们已经知道是
19、含幺半群,由于每个整数a都有加法逆元-a,所以是群,一般叫做整数加群。同理,是实数加群,是有理数加群。对于数的乘法,是含幺半群而不是群,因为整数一般无Z中的乘法逆元。是实数乘群,它的幺元是1,每元的乘法逆元为1/a。,2023/11/16,计算机科学与工程学院,34,例:设Zk表示整数集Z上的模k剩余类集合,即:Zk=0,1,2,k-1。在Zk上定义运算 和 如下:那么,是群。这是因为封闭性和可结合性是明显成立的,0是幺元,每元i的逆元是k-i。群 习惯上又称为剩余类加群。,2023/11/16,计算机科学与工程学院,35,例 设n个元素的集合A上的全体置换构成集合Sn。由第6章中关于置换的讨
20、论,Sn中两个置换的复合仍然是A上的一个置换,因而运算是封闭的;其次,由于函数的复合是可结合的,因而置换的复合也是可结合的;在Sn中存在幺置换=(1),使对任何Sn中的置换 均有,因而=(1)是幺元;把每个元素的x变成y的置换,其逆置换则把元素y变成x,因而每个置换都有逆。由此可知,构成群,这个群一般称为n次对称群,是一类重要的群。群尽管是用“闭、结、幺、逆”四个条件来定义的,但是它还可以用别的形式等价地定义。,2023/11/16,计算机科学与工程学院,36,例 设n个元素的集合A上的全体置换构成集合Sn。由第6章中关于置换的讨论,Sn中两个置换的复合仍然是A上的一个置换,因而运算是封闭的;
21、其次,由于函数的复合是可结合的,因而置换的复合也是可结合的;在Sn中存在幺置换=(1),使对任何Sn中的置换 均有,因而=(1)是幺元;把每个元素的x变成y的置换,其逆置换则把元素y变成x,因而每个置换都有逆。由此可知,构成群,这个群一般称为n次对称群,是一类重要的群。群尽管是用“闭、结、幺、逆”四个条件来定义的,但是它还可以用别的形式等价地定义。,2023/11/16,计算机科学与工程学院,37,群,定理15-2.1 如果是半群,并且对a,bG,都存在x,yG 使x*a=b,a*y=b,则是群。群中元素的数目称为群的阶。证明:设 aG,方程 x*a=a 的解为e1,对tG,方程 a*y=t
22、有解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有逆元。所以,是群。,2023/11/16,计算机科学与工程学院,38,群,定理15.3 如果是半群,并且对a,bG,都存在x,yG 使x*a=b,a*y=b,则是群。群中元素的数目称为群的阶。证明:设 aG,方程 x*a=a 的解为e1,对tG,方程 a*y=t 有解y0,e1*t=e1*(a*y0)=(e1*a)*y0=a*y
23、0=t 即对tG,必有e1*t=t,e1是G中的左幺元。同样可以证明G中有右幺元e2,所以G中有幺元e。同理,对bG,方程x*b=e有解x0,这个x0是b的左逆元,方程b*y=e的解是b的右逆元,从而b有逆元。所以,是群。,2023/11/16,计算机科学与工程学院,39,群,定理15.3 如果是半群,并且对a,bG,都存在x,yG 使x*a=b,a*y=b,则是群。群中元素的数目称为群的阶。证明:设 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中的左幺元。同样可以证
24、明G中有右幺元e2,所以G中有幺元e。同理,对bG,方程x*b=e有解x0,这个x0是b的左逆元,方程b*y=e的解是b的右逆元,从而b有逆元。所以,是群。,2023/11/16,计算机科学与工程学院,40,群,定理15.3 如果是半群,并且对a,bG,都存在x,yG 使x*a=b,a*y=b,则是群。群中元素的数目称为群的阶。证明:设 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
25、有解x0,这个x0是b的左逆元,方程b*y=e的解是b的右逆元,从而b有逆元。所以,是群。,2023/11/16,计算机科学与工程学院,41,群,定理15.3 如果是半群,并且对a,bG,都存在x,yG 使x*a=b,a*y=b,则是群。群中元素的数目称为群的阶。证明:设 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的右逆元,从
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 15 陈瑜
链接地址:https://www.31ppt.com/p-6595587.html