1.2　经典代数系统

1.2.1　群

定义1.3　若代数的二元运算 “” 具有如下性质,则称为一个群.

(1) 结合律:.

(2) 零元律:称为零元,

(3) 负元律:称为的负元,使得. 元素的负元常记为.

若运算还满足交换律,则称为交换群.

例1.8　在比特集上定义运算:

称为上的异或运算. 由上面的运算表可以看到异或运算的一个有趣之处在于:,(见运算表的第1行或第1列),(见运算表的第2行或第2列). 下面说明构成一个交换群.

(1) 由运算表关于从左上角到右下角的对角线的对称性得知,运算具有交换律;

(2) 构造真值表

真值表中最后两列的值完全相同,这就验证了满足结合律;

(3)由的运算表得知0是零元;

(4)由的运算表得知0和1均为自身的负元.

交换群在计算机的位运算中扮演着重要角色.

练习1.4　例1.5中的字符串代数是否构成一个群?

(参考答案: 否. 提示: 无负元)

例1.9　代数系统中为全体整数的集合,+表示两个整数的加法运算,构成一个交换群, 称为整数群.

常将群的运算称为 “加法” 运算,根据的负元律的意义及记号,可得上的 “减法” 运算. 因此,在例1.9的整数群中既可以做加法, 也可以做减法.

例1.10　给定正整数,考虑集合. 在上定义运算

则构成交换群.

事实上,由运算表定义的+运算,就是中的两个元素之和以为模的余数,即为

(1) 根据运算表的对称性得知,+运算满足交换律

(2),即+运算满足结合律

(3)观察运算表的首行和首列可知0是+运算的零元;

(4)且的负元为.

称为模的剩余类加群.