代数系统
这部分内容属于近世代数的范畴,近世代数是研究具有运算的集合,它第一次揭示了数学系统的多变性与丰富性。代数结构理论可用于计算机算法的复杂性分析,研究抽象数据结构的性质及操作,同时也是程序设计语言的理论基础。我们将介绍代数系统的最基本概念和最基本理论,以及几类常用的代数系统,它们是:半群,幺半群,群,环,域,格和布尔代数。本课程在第五,六章中介绍代数系统的内容。
第五章 代数结构
二元运算及性质
重点:(1) 一元和二元运算的概念,
(2) 二元运算律 (结合律,交换律,分配律),
(3) 二元运算的特殊元素 (幺元,零元,逆元)。
1、定义:设 为集合,函数 称为 上的二元运算 (即 , ,运算封闭)
元运算, ,掌握 , ,即一元,二元运算。
2、记号:用 等符号表示二元运算,称为算符。
例如: 记为 (二元运算)
记为 (一元运算)
例1、(1) 上的加法,乘法都是二元运算,但减法,除法不是。
(2) 上的加法,乘法,减法都是二元运算,但除法不是。 上求相反数的运算是一元运算。
(3) 非零实数集 上的乘法和除法都是二元运算。但加法,减法不是,而求倒数是一元运算。
(4) 表示所有 阶实矩阵的集合 ,则矩阵的加法和乘法都是二元运算。
(5) 集合 的幂集 上的 都是二元运算,而绝对补集( 为全集)是一元运算。
(6) 表示集合 上的所有函数的集合,函数的合成运算 是 上的二元运算。
3、一元,二元运算表。
当 为有穷集时, 上的一元和二元运算都可以用运算表给出。
例2、(1) 设 ,给出 上的运算绝对补集 和对称差 的运算表。
解: ,“ ”为一元运算,“ ”为二元运算,其运算表如下:
|
|
(2) 设 ,定义 上的两个二元运算如下:
求运算 和 的运算表。
解: , 分别是 的和与积除以 的余数,运算表如下:
|
设 是 上的二元运算, ,
1、若 ,则称 在 上可交换。(或称满足交换律)
2、若 ,则称 在 上可结合。(或称满足结合律)
3、若
则称运算 对 是可分配的。(或称 对 满足分配律)
例3、(1) 普通的加法和乘法在 上都是可结合的,且是可交换的,乘法对加法是可分配的。
(2) 矩阵的加法和乘法在 上是可结合的,加法可交换,但乘法不可交换,乘法对加法是可分配的。
(3) 在幂集 上可结合,可交换,但是相对补不可结合,不可交换, 和 是互相可分配的。
设 为 上的二元运算,
1、幺元 :若 ,对 , ,则称 为运算 的幺元。
注:(1) 若幺元存在必唯一。
(2) 若只有 或只有 ,则 , 称为左幺元或右幺元。
例如:在 上,加法的幺元是 ,乘法的幺元是 。在 上,矩阵加法的幺元是 阶 矩阵,矩阵乘法的幺元是 阶单位矩阵。在幂集 上,运算 的幺元是 ,运算 的幺元是全集 。
在 上的减法运算没有幺元,只有右幺元 。
例4、在 (非零实数集)上定义运算如下:
则 中的任何元素都是右幺元,但没有左幺元 ,使 ,从而没有幺元。
2、零元 :若 ,对 ,
,则称 为运算 的零元。
注:(1) 若零元存在必唯一。
(2) 若只有 ,或只有 ,则 称为左零元或右零元。
如例4中 的任何元素都是左零元,但没有右零元 ,从而也没有零元。
例如:在 上加法没有零元,乘法的零元是 。在 上矩阵加法没有零元,矩阵乘法的零元是 阶 矩阵。在幂集 上,运算 的零元是 ,运算 的零元是 。
3、逆元:设 为 上的二元运算, 为运算 的幺元,若对 ,存在 ,使 ,则称 为 的逆元。
注:(1) 逆元是针对某个元素 而言的 (可能有些元素有逆元,有些没有)
(2) 若二元运算 满足结合律且 的逆元存在则必唯一。
(3) 若只有 或只有 ,则 称为左逆元或右逆元。
例如:普通加法运算在 上有幺元 ,仅在 上任意元素 有逆元 ,满足 ,在 上只有 有逆元 ,而其它的自然数就没有逆元。在 上矩阵的乘法只有可逆矩阵存在逆元。幂集 上关于运算 有幺元 ,但除了 外,其余元素都没有逆元。
例5、判断普通的加法和乘法运算在下列集合中是否二元运算。
(1)
(2)
(3)
(4)
(5)
解:(1) 因 , ,所以 关于加法,乘法运算不封闭,不是二元运算。
(2) 因 ,故 关于加法运算不封闭,不是二元运算。而 , , , ,故 关于乘法运算封闭,是二元运算。
(3) 因 是偶数, 是全体偶数的集合,而偶数 偶数,偶数 偶数都是偶数,故加法,乘法都是二元运算。
(4) 是全体奇数的集合,因奇数 奇数 偶数,故加法不是二元运算,奇数 奇数 奇数,故乘法是二元运算。
(5) 因 ,但 ,故加法不是二元运算,又因 ,故乘法是二元运算。
例6、在实数集 上定义运算 如下: ,
。
(1) 是 上的二元运算吗?
(2) 在 上满足交换律,结合律吗?
(3) 关于 有幺元吗?
(4) 关于 每个元素有逆元吗?
解:(1) 因 ,是二元运算。
(2) 因 ,满足交换律,
,满足结合律。
(3) 因对 , ,故 为幺元。
(4) 且 ,有 ,故 时, , 时,无逆元。
例7、设
,二元运算
和
如下表定义,问运算
和
是否可交换的;是否有零元;是否有幺元;如果有幺元,指出哪些元素有逆元;逆元是什么?
表(1)
|
表(2)
|
解:(1) 运算 可交换,没有零元, 是幺元, 都有逆元,且 , , 互为逆元。
(2) 运算 不可交换, 是左零元, 是幺元,只有 有逆元, ,由于 ,故 是 的左逆元, 是 的右逆元,但它们的逆元都不存在。
四、其它一些运算律和特殊元素。1、设 和 都是 上的可交换的二元运算,若 ,
则称 和 满足吸收律。
2、设 是 上的二元关系,若 ( 不是零元)
满足:(1) 若 ,则 ,
(2) 若 ,则 ,
就称运算 满足消去律。
3、幂等元。设 为 上的二元运算,对 ,若 ,则称 为幂等元。若 上所有元素都是幂等元,则称运算 满足幂等律。
例如: 上的运算 和 ,全体命题公式集合上的运算 和 ,都满足吸收律,又分别满足幂等律,但都不满足消去律 (如 ,不一定有 )。 上的加法运算都不满足幂等律,但它们都有幂等元,幺元就是幂等元。