离散数学第151156陈瑜.ppt

《离散数学第151156陈瑜.ppt》由会员分享，可在线阅读，更多相关《离散数学第151156陈瑜.ppt（226页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

4、在*上定义运算为字的连接“”，则满足封闭和可结合的条件，并且空字 是系统的幺元，所以是一个含幺半群。n 半群或含幺半群在计算机科学中有广泛的应用，尤其在从编译技术发展起来的形式语言与自动机理论领域，含幺半群是很重要的的内容之一。下面是半群的一个简单的应用例子。5/16/2023 8 计算机科学与工程学院n 例 设是非空有限字母表，*是由定义在上的全体有限长字母串构成的集合，或叫做上全体字的集合。在*上定义运算为字的连接“”，则满足封闭和可结合的条件，并且空字 是系统的幺元，所以是一个含幺半群。n 半群或含幺半群在计算机科学中有广泛的应用，尤其在从编译技术发展起来的形式语言与自动机理论领域，含幺

5、半群是很重要的的内容之一。下面是半群的一个简单的应用例子。5/16/2023 9 计算机科学与工程学院n 例 设一个简单的液晶显示电子表仅有显示时、分的两个功能，有0、1两个按键。按1键时由正常状态转入调分状态，此时按0键m次可以调增分数m；再按1键则转入调时状态，此时按0键n次，则时数增加n；最后再按1键回复到正常状态。这一调节过程如图(b)所示。(a)(b)5/16/2023 10 计算机科学与工程学院 上面的调分和调时过程可表示为:或由符号1和0组成的形如10m10n1的字符串集，即字母表=0，1上的一个语言L=10m10n1|m，n0。这种字母串可以被电子表中的微处理器(可以看成是一个

6、小小的计算机)识别并执行，其动作原理就是图15-1.1(b)所示的状态图，称为一个有限自动机，它反映了电子表依令而行的规则。语言L被相应地称为这个自动机所识别的语言。5/16/2023 11 计算机科学与工程学院幂 设是一个半群,由于*满足结合律，可定义幂运算，即对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。如果有单位元e，可以定义：x0=e幂运算有如下的公式：（见下页）5/16/2023 12 计算机科学与工程学院n 定理15-1.1 设是半群，aS，m和n是正整数，则：am*an=am+n；(am)n=amn。当是含幺

7、半群时，上述结论对任意非负整数m和n都成立。证明：设m是一个固定的正整数，对n进行归纳。对于：当n=1时，由幂的定义可知结论成立；设结论对n=k时成立，则 am*ak+1=am*(ak*a)(由幂的定义)=(am*ak)*a(可结合性）=(am+k)*a（归纳假设）=am+(k+1)由归纳法可知，结论成立。5/16/2023 13 计算机科学与工程学院n 定理15-1.1 设是半群，aS，m和n是正整数，则：am*an=am+n；(am)n=amn。当是含幺半群时，上述结论对任意非负整数m和n都成立。证明：设m是一个固定的正整数，对n进行归纳。对于：当n=1时，由幂的定义可知结论成立；设结论对

8、n=k时成立，则 am*ak+1=am*(ak*a)(由幂的定义)=(am*ak)*a(可结合性）=(am+k)*a（归纳假设）=am+(k+1)由归纳法可知，结论成立。5/16/2023 14 计算机科学与工程学院n 定理15-1.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+(

9、k+1)由归纳法可知，结论成立。对于可以类似的进行归纳证明。5/16/2023 15 计算机科学与工程学院n 注意：当运算为加法“+”时，上述定理应写成：ma+na=(m+n)a n(ma)=(mn)a5/16/2023 16 计算机科学与工程学院n 定理15-1.2 设是半群，如果S是有限集，则必有aS，使得 a2=a。(参见教材p277）证明：因为是半群，S是有限集，对 bS，则元素b1，b2，b3，中必有重复的，设bi=bj，其中ji，由bi=bj-i*bi，则对 ti都得到bt=bj-i*bt。反复利用上式，则对任何正整数k1，有bt=bk（j-i）*bt，（ti）。特别，取k使得k(

10、j-i)i，同时令t=k(j-i)，则得到幂等元。注意此处的a2的正确含义！a*a=a2,不是数学中的乘法！5/16/2023 17 计算机科学与工程学院n 定理15-1.2 设是半群，如果S是有限集，则必有aS，使得 a2=a。(参见教材p277）证明：因为是半群，S是有限集，对 bS，则元素b1，b2，b3，中必有重复的，设bi=bj，其中ji。由bi=bj-i*bi，则对 ti都得到bt=bj-i*bt。反复利用上式，则对任何正整数k1，有bt=bk（j-i）*bt，（ti）。特别，取k使得k(j-i)i，同时令t=k(j-i)，则得到幂等元。5/16/2023 18 计算机科学与工程学

11、院n 定理15-1.2 设是半群，如果S是有限集，则必有aS，使得 a2=a。(参见教材p277）证明：因为是半群，S是有限集，对 bS，则元素b1，b2，b3，中必有重复的，设bi=bj，其中ji。由bi=bj-i*bi，则对 ti都得到bt=bj-i*bt。反复利用上式，则对任何正整数k1，有bt=bk（j-i）*bt，（ti）。特别，取k使得k(j-i)i，同时令t=k(j-i)，则得到幂等元。5/16/2023 19 计算机科学与工程学院n 定理15-1.2 设是半群，如果S是有限集，则必有aS，使得 a2=a。(参见教材p277）证明：因为是半群，S是有限集，对 bS，则元素b1，b

12、2，b3，中必有重复的，设bi=bj，其中ji。由bi=bj-i*bi，则对 ti都得到bt=bj-i*bt。反复利用上式，则对任何正整数k1，有bt=bk（j-i）*bt，（ti）。特别，取k使得k(j-i)i，同时令t=k(j-i)，则得到幂等元。5/16/2023 20 计算机科学与工程学院n 定理15-1.2 设是半群，如果S是有限集，则必有aS，使得 a2=a。(参见教材p277）证明：因为是半群，S是有限集，对 bS，则元素b1，b2，b3，中必有重复的，设bi=bj，其中ji，由bi=bj-i*bi，则对 ti都得到bt=bj-i*bt。反复利用上式，则对任何正整数k1，有bt=

13、bk（j-i）*bt，（ti）。特别，取k使得k(j-i)i，同时令t=k(j-i)，则得到幂等元。注意，若S不是有限集，则不一定有幂等元。例如，正整数集关于加法运算是一个半群，但是不存在幂等元。含幺半群至少含有一个幂等元，那就是幺元。一个半群甚至含幺半群也可以含有多个幂等元。不难验证是以S为幺元的含幺半群。由于集合交运算是幂等的，所以中每个元都是幂等元。5/16/2023 21 计算机科学与工程学院子半群n 定义15-1.1 如果是半群，T是S的非空子集，且T对运算*是封闭的，则称是半群的子半群；如果是含幺半群，TS，eT，且T对运算*是封闭的，则称是含幺半群的子含幺半群。n 例：半群的子代数，都是的子半群。5/16/2023 22 计算机科学与工程学院子半群n 定义15-1.1 如果是半群，T是S的非空子集，且T对运算*是封闭的，则称是半群的子半群；如果是含幺半群，TS，eT，且T对运算*是封闭的，则称是含幺半群的子含幺半群。n 例：半群的子代数，都是的子半群。5/16/2023 23 计算机科学与工程学院子半群n 定义15-1.1 如果是半群，T是S的非空子集，且T对运算*是封闭的，则称是半群的子半群；如果是含幺半群，TS，eT，且T对运算*是封闭的，则称是含幺半群的子含幺半群。n 例：半群的子代数，都是的子半群。5/16/2023 24 计算机科学与工程学院