离散数学与(第15.1-15.4)陈瑜 .ppt

计算机科学与工程学院 陈瑜 Email：yuchen@scu.edu.cn * 第15章： 半群与群 15.1 半群 群是一种特殊的代数系统，是最重要的代数系统之一。群的理论广泛应用于数学、物理、化学以及很多人们不太熟悉的领域如社会学等。对计算机科学而言，群在自动化理论、形式语言、语法分析、编码理论等方面都有直接应用，并显示出其强大功能。 上一章中已经给出了半群的定义，它要求运算是可结合的。许多常见的代数系统都是半群，甚至是含幺半群。下面是一些典型的半群例子。 群是一种特殊的代数系统，是最重要的代数系统之一。群的理论广泛应用于数学、物理、化学以及很多人们不太熟悉的领域如社会学等。对计算机科学而言，群在自动化理论、形式语言、语法分析、编码理论等方面都有直接应用，并显示出其强大功能。 上一章中已经给出了半群的定义，它要求运算是可结合的。许多常见的代数系统都是半群，甚至是含幺半群。下面是一些典型的半群例子。 例： R,+满足封闭、可结合、有幺元0的条件，因而是含幺半群。另外，它还满足可换性，每个元x∈R都有加法逆元-x，因此， R,+也是一个可换群。 R,×满足封闭、可结合、有幺元1，因此是含幺半群。注意，因为0无乘法逆元，所以R,×只能是含幺半群。 例 设Mm,n表示全休m行n列矩阵构成的集合，+是矩阵加法，那么 Mm,n，+满足封闭、可结合的条件，元素全为0的m行n列矩阵是幺元，因此 Mm,n，+是含幺半群。 此外，Mm,n中每个矩阵Am,n都有加法逆矩阵-Am,n ，因而 Mm,n，+还满足逆元条件。 例 设F是由定义在非空集合S上的全体函数构成的集合，即F={ f: S→S}。对于函数的复合运算“?” ，F，?满足封闭性和可结合性，所以是半群。 此外，定义在S上的恒等函数Is是F，?的幺元，所以F，?又是含幺半群。 例 设∑是非空有限字母表，∑*是由定义在∑上的全体有限长字母串构成的集合，或叫做∑上全体字的集合。在∑*上定义运算为字的连接“?”，则∑*, ?满足封闭和可结合的条件，并且空字 是系统的幺元，所以∑*, ?是一个含幺半群。 半群或含幺半群在计算机科学中有广泛的应用，尤其在从编译技术发展起来的形式语言与自动机理论领域，含幺半群是很重要的的内容之一。下面是半群的一个简单的应用例子。 例 设∑是非空有限字母表，∑*是由定义在∑上的全体有限长字母串构成的集合，或叫做∑上全体字的集合。在∑*上定义运算为字的连接“?”，则∑*, ?满足封闭和可结合的条件，并且空字 是系统的幺元，所以∑*, ?是一个含幺半群。 半群或含幺半群在计算机科学中有广泛的应用，尤其在从编译技术发展起来的形式语言与自动机理论领域，含幺半群是很重要的的内容之一。下面是半群的一个简单的应用例子。 例 设一个简单的液晶显示电子表仅有显示时、分的两个功能，有0、1两个按键。按1键时由正常状态转入调分状态，此时按0键m次可以调增分数m；再按1键则转入调时状态，此时按0键n次，则时数增加n；最后再按1键回复到正常状态。这一调节过程如图 (b)所示。 上面的调分和调时过程可表示为 : 幂 定理15-1.1 设S，*是半群，a?S，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) 由归纳法可知，结论成立。 定理15-1.1 设S，*是半群，a?S，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) 由归纳法可知，结论成立。 定理15-1.1 设S，*是半群，a?S，m和n是正整