离散数学第三节：半群、独异点及其性质

半群是一种特殊的代数系统，它在形式语言、自动机等领域中，都有具体的应用。

定义1 一个代数系统＜S，*＞，其中S是非空集合，*是S上的一个二元运算，如果运算*是封闭的，则称代数系统＜S，*＞为广群。

定义2 一个代数系统＜S，*＞，其中S是非空集合，*是S上的一个二元运算。如果：

（1）运算*是封闭的；

（2）运算*是可结合的，即对任意的x，y，z∈S，满足

(x*y)*z=x*(y*z)

则称代数系统＜S，*＞为半群。

例1 代数系统＜N；·＞和＜N；+＞都是半群，其中·和+分别表示通常的乘法和加法。

例2 仍用·表示通常的乘法运算，则代数系统＜[0，1]；·＞和＜（0，1）；·＞也都是半群。

例3 代数系统＜Z；+＞和＜R+；·＞是半群，但代数系统＜Z；-＞和＜R+；/＞不是半群。其中R+表示所有正实数的集合，+，-，·，/是通常的四则运算。

一个半群对于它的运算*，可以有幺元，也可以没有幺元。在例1中代数系统＜N；·＞中幺元为1，＜N；+＞中幺元为0。在例2中，代数系统＜（0，1）；·＞无幺元。

定义3 设＜S；*＞是一个半群，B⊆S。如果＜B；*＞也是一个半群，则称＜B；*＞是＜S；*＞的子半群。

定理1 设＜S；*＞是半群，B⊆S。如果运算*在B上是封闭的，则＜B；*＞是＜S；*＞的子半群。

证明 因为*在S上可结合的，而B⊆S且*在B上封闭，所以*在B上也是可结合的，因此，＜B；*＞是一个半群。

例4 设·表示普通的乘法运算，那么＜[0，1]，·＞，＜[0，1），·＞和＜I，·＞都是＜R，·＞的子半群。

解 首先，运算·在R上是封闭的，且是可结合的，所以＜R，·＞是一个半群。其次运算·在[0，1]，[0，1）和Z上都是封闭的，且[0，1]⊂R，[0，1）⊂R，Z⊂R。因此，由定理1可知＜[0，1]，·＞，＜[0，1），·＞和＜Z，·＞都是＜R，·＞的子半群。

定理2 设＜S，*＞是一个半群，如果S是一个有限集，则必有a∈S，使得a*a=a。

证明 因为＜S，*＞是半群。对于任意的b∈S，由*的封闭性可知b*b∈S，记b2=b*b，则b2*b=b*b2∈S，记b3=b2*b=b*b2，因为S是有限集，所以必定存在j＜i，使得

bi=bj

令

p=j-i

便有

bi=bp*bi

所以

bq=bp*bq q≥i

因为p≥1，所以总可以找到k≥1，使得

kp≥i

对于S中的元bkp，就有

bkp=bp*bkp

=bp*(bp*bkp)

=b2p*bkp

=b2p*(bp*bkp)

=…

=bkp*bkp

这就证明了在S中存在元素a=bkp，使得

a*a=a(www.xing528.com)

定义4 含有幺元的半群称为独异点。

例如，代数系统＜R，+＞是个独异点，因为＜R，+＞是一个半群，且0是R中关于运算+的幺元。另外，代数系统＜Z，·＞，＜Z+，·＞，＜R，·＞都是具有幺元1的半群。因此它们都是独异点。

可是，代数系统＜N-{0}，+＞虽是一个半群，但关于运算+不存在幺元，所以，这个代数系统不是独异点。

定理3 设＜S，*＞是一个独异点，则在关于运算*的运算表中任何两行或两列都是不相同的。

证明 设S中关于运算*的幺元是e。因为对于任意的a，b∈S且a≠b时，总有

e*a=a≠b=e*b

和

a*e=a≠b=b*e

所以，在*的运算表中不可能有两行或两列是相同的。

在前面我们已证明了，对于任意二元运算的幺元，如果它存在，则它是唯一的，因此独异点具有唯一的幺元。

例5 ＜Z；·＞，＜Z；+＞都是独异点，其中·和+是通常的乘法和加法运算，其单位元分别是数1和0。例1中的＜N；·＞是独异点，因为它具有单位元1。但＜N；+＞不是独异点。

例6 代数系统＜2E；∪＞和＜2E；∩＞分别是以和E为单位元的独异点。

例7 设S是一个非空集合，P（S）是S的所有子集的集合。定义集合P（S）上的二元运算*，使得对于任意的π1，π2∈P（S），π1*π2是由π1与π2的交集所组成的集合，其中去掉空集。

例如，若S={a，b，c，d，e，f}，

π1={a,b},

π2={a,b,c},

则π1*π2={a，b}。

容易证明，集合P（S）对于运算*是封闭的，即对任意的π1，π2∈P（S），π1*π2仍是集合S的一个子集。且由*的定义可知，*是可结合的，子集π=S是运算*的幺元，因此＜P（S）；*＞是一个独异点。

定义5 如果独异点＜S；*＞中的运算*是可交换的，则称独异点＜S；*＞是可交换的独异点。

我们已遇到过许多可交换的独异点，例如，＜2E；∪＞和＜2E；∩＞，＜Z；·＞和＜Z；+＞以及＜P（S）；*＞都是可交换的独异点。

例8 设RA表示集合A上所有关系的集合，·表示求复合关系的运算，则代数系统＜RA；·＞是一个独异点。恒等关系IA是其幺元。由于关系的复合不满足交换律，故＜RA；·＞不是可交换的独异点。

定理4 设＜S；*＞是独异点，对于任意a，b∈S，且a，b均有逆元，则

(1)(a-1)-1=a;

（2）a*b有逆元，且（a*b）-1=b-1*a-1。

证明（1）因为a-1是a的逆元，即

a*a-1=a-1*a=e

所以

(a-1)-1=a

（2）因为

(a*b)*(b-1*a-1)=a*(b*b-1)*a-1

=a*e*a-1=a*a-1=e

同理可证

(b-1*a-1)*(a*b)=e

所以

(a*b)-1=b-1*a-1