离散数学第15章陈瑜

1、陈瑜,Email：,离散数学,计算机学院,2020/9/4,计算机学院,2/225,第15章： 半群与群 15.1 半群,2020/9/4,计算机学院,3/225,群是一种特殊的代数系统，是最重要的代数系统之一。群的理论广泛应用于数学、物理、化学以及很多人们不太熟悉的领域如社会学等。对计算机科学而言，群在自动化理论、形式语言、语法分析、编码理论等方面都有直接应用，并显示出其强大功能。 上一章中已经给出了半群的定义，它要求运算是可结合的。许多常见的代数系统都是半群，甚至是含幺半群。下面是一些典型的半群例子。,2020/9/4,计算机学院,4/225,群是一种特殊的代数系统，是最重要的代数系统之一

2、。群的理论广泛应用于数学、物理、化学以及很多人们不太熟悉的领域如社会学等。对计算机科学而言，群在自动化理论、形式语言、语法分析、编码理论等方面都有直接应用，并显示出其强大功能。 上一章中已经给出了半群的定义，它要求运算是可结合的。许多常见的代数系统都是半群，甚至是含幺半群。下面是一些典型的半群例子。,2020/9/4,计算机学院,5/225,例： 满足封闭、可结合、有幺元0的条件，因而是含幺半群。另外，它还满足可换性，每个元xR都有加法逆元-x，因此， 也是一个可换群。 满足封闭、可结合、有幺元1，因此是含幺半群。注意，因为0无乘法逆元，所以只能是含幺半群。,2020/9/4,计算机学院,6/

3、225,例 设Mm,n表示全休m行n列矩阵构成的集合，+是矩阵加法，那么满足封闭、可结合的条件，元素全为0的m行n列矩阵是幺元，因此是含幺半群。 此外，Mm,n中每个矩阵Am,n都有加法逆矩阵-Am,n ，因而还满足逆元条件。,2020/9/4,计算机学院,7/225,例 设F是由定义在非空集合S上的全体函数构成的集合，即F= f: SS。对于函数的复合运算“” ，满足封闭性和可结合性，所以是半群。 此外，定义在S上的恒等函数Is是的幺元，所以又是含幺半群。,2020/9/4,计算机学院,8/225,例 设是非空有限字母表，*是由定义在上的全体有限长字母串构成的集合，或叫做上全体字的集合。在*

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

5、225,上面的调分和调时过程可表示为 :,或由符号1和0组成的形如10m10n1的字符串集，即字母表=0，1上的一个语言L=10m10n1 |m，n0。 这种字母串可以被电子表中的微处理器(可以看成是一个小小的计算机)识别并执行，其动作原理就是图15-1.1(b)所示的状态图，称为一个有限自动机，它反映了电子表依令而行的规则。语言L被相应地称为这个自动机所识别的语言。,2020/9/4,计算机学院,11/225,幂,设是一个半群,由于*满足结合律，可定义幂运算，即对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。 如果

6、有单位元e，可以定义：x0=e 幂运算有如下的公式：（见下页）,2020/9/4,计算机学院,12/225,定理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) 由归纳法可知，结论成立。,2020/9/4,计算机学院,13/225,

7、定理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) 由归纳法可知，结论成立。,2020/9/4,计算机学院,14/225,定理15.1 设是半群，aS，m和n是正整数，则： am*an=am+n； (am)n=amn 。当是含幺半

8、群时，上述结论对任意非负整数m和n都成立。 证明：设m是一个固定的正整数，对n进行归纳。 对于： 当n=1时，由幂的定义可知结论成立； 设结论对n=k时成立，则 am*ak+1 = am*(ak*a) (由幂的定义) = (am*ak)*a (可结合性） = (am+k)*a （归纳假设） = am+(k+1) 由归纳法可知，结论成立。,对于可以类似的进行归纳证明。,2020/9/4,计算机学院,15/225,注意：当运算为加法“+”时，上述定理应写成： ma+na=(m+n)a n(ma)=(mn)a,2020/9/4,计算机学院,16/225,定理15.2 有限半群 S， 必有幂等元，即

9、存在 a S， a2 = a 。(参见教材p183）,注意此处的a2的正确含义！a*a=a2,不是数学中的乘法！,2020/9/4,计算机学院,17/225,定理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

10、) i） 令t=k(j-i ), 则得到 bt = bt bt 即 bt是幂等元。,2020/9/4,计算机学院,18/225,定理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

11、), 则得到 bt = bt bt 即 bt是幂等元。,2020/9/4,计算机学院,19/225,定理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

12、 bt 即 bt是幂等元。,2020/9/4,计算机学院,20/225,定理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是幂等元。,

13、注意，若S不是有限集，则不一定有幂等元。例如，正整数集关于加法运算是一个半群，但是不存在幂等元。含幺半群至少含有一个幂等元，那就是幺元。一个半群甚至含幺半群也可以含有多个幂等元。不难验证是以S为幺元的含幺半群。由于集合交运算是幂等的，所以中每个元都是幂等元。,2020/9/4,计算机学院,21/225,子半群,定义15.1 如果是半群，T是S的非空子集，且T对运算*是封闭的，则称是半群的子半群； 如果是含幺半群，TS，eT，且T对运算*是封闭的，则称是含幺半群的子含幺半群。 例：半群的子代数，都是的子半群。,2020/9/4,计算机学院,22/225,子半群,定义15.1 如果是半群，T是S的

14、非空子集，且T对运算*是封闭的，则称是半群的子半群； 如果是含幺半群，TS，eT，且T对运算*是封闭的，则称是含幺半群的子含幺半群。 例：半群的子代数，都是的子半群。,2020/9/4,计算机学院,23/225,子半群,定义15.1 如果是半群，T是S的非空子集，且T对运算*是封闭的，则称是半群的子半群； 如果是含幺半群，TS，eT，且T对运算*是封闭的，则称是含幺半群的子含幺半群。 例：半群的子代数，都是的子半群。,2020/9/4,计算机学院,24/225,例 设是一个可换的含幺半群，M是它的所有的等幂元构成的集合，则是的一个子含幺半群。 证明：(1) 显然，MS； (2) 是含幺半群，所

15、以幺元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)知：是的一个子含幺半群。,2020/9/4,计算机学院,25/225,例 设是一个可换的含幺半群，M是它的所有的等幂元构成的集合，则是的一个子含幺半群。 证明：(1) 显然，MS； (2) 是含幺半群，所以幺元e存在，又e*ee，则e是一个等幂元，即有eM，所以M是非空的； (3) eM； (4)对任意a，bM，有(a*b)*

16、(a*b)a*(b*a)*ba*(a*b)*b(a*a)*(b*b)a*b， 即运算“*”关于集合M是封闭的运算。 由(1)、(2)、(3)、(4)知：是的一个子含幺半群。,2020/9/4,计算机学院,26/225,例 设是一个可换的含幺半群，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)

17、、(2)、(3)、(4)知：是的一个子含幺半群。,2020/9/4,计算机学院,27/225,例 设是一个可换的含幺半群，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)知：是的一个子含幺半群。,2020/9/4,计算机学院,28/225,例 设是一个可换的含幺半群，M

18、是它的所有的等幂元构成的集合，则是的一个子含幺半群。 证明：(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)知：是的一个子含幺半群。,2020/9/4,计算机学院,29/225,习题,P193 2、4、6,2020/9/4,计算机学院,30/225,15.2 群和子群,2020/9/4,计算机学院,31/225,主要内容,一个非常重要的代数系统群。 主要从以下几个方面来介绍： 群的概念和基本性质。 群的子群和性质。 群中元素的周期和性质。 特殊群及其性质，如交换群（Abel群）、循环群。 陪集和拉格郎日定理。,2020/9/4,计算机学院,32/225,在14.2中已经为群下了定义，把群看成是在含幺半群的基础上加上每元有逆元的条件，其核心内容可用“闭、结、幺、逆”四个字予以概括。下面是一些典型的群的例子。,2020/9/4,计算机学院,33/2