第 6章 代数系统
6.1 代数系统的概念
6.2 代数系统的同态和同构
6.3 代数系统的积代数
6.4 半群与独异点
6.5 群与交换群
6.6 环与域
6.7 格与布尔代数第 6章 代数系统代数的概念与方法是研究计算机科学和工程的重要数学工具,它属于近世代数的内容,众所周知，近世代数是研究具有运算的集合，它第一次揭示了数学系统的多变性与丰富性，而近世代数研究的中心问题是代数系统的结构：半群、群、格与布尔代数等,代数系统的结构理论可用于计算机算法的复杂度分析，研究抽象数据结构的性质及操作，同时也是程序设计语言的理论基础,本章将对代数系统的基本概念及主要的代数系统进行重点介绍,
6.1 代数系统的概念
6.1.1 代数运算的定义
6.1.2 二元运算及其性质
6.1.3 代数系统中的特殊元素
6.1.1 代数运算的定义定义 6.1-1 设 S为集合，函数
f:S→S,称为 S上的一个一元运算,
定义 6.1-2 设 S为集合，函数
f:S× S→S,称为 S上的一个二元运算,
定义 6.1-3 设 S为集合，函数
f,S× S× … × S→S,称为 S上的一个 n
元运算,
6.1.1 代数运算的定义定义 6.1-4 通常用 o,*,·等符号表示二元运算，称为算符,设 f:S× S→S 是 S上的二元运算，对任意的 x,y∈ S,x与 y的运算结果是 z,即
f(〈 x,y〉 ) = z，
可利用算符 o 简记为
x o y=z.
6.1.2 二元运算及其性质
1.二元运算二元运算是最常见的代数运算,下面是一些常见集合的二元运算：
(1)自然数集合 N上的乘法是 N上的二元运算,但除法不是,
(2)整数集合 Z上的加法、减法和乘法是 Z上的二元运算，但除法不是,
(3)非零实数集 R*上的乘法和除法都是 R*上的二元运算，但加法、减法不是,
(4)设 Mn(R)表示所有 n阶实矩阵的集合 (n≥2)，即
（见第 110页公式）
则矩阵加法和乘法都是 Mn(R)上的二元运算,
(5)S为任意集合,则 ∪,∩,-,? 为 S的幂集 P(S)上的二元运算,
(6)S为任意集合,S 是 S上的所有函数的集合,则合成运算 o 是 S 上的二元运算,
s
s
6.1.2 二元运算及其性质
2.二元运算的性质定义 6.1-5 设 o 为 S上的二元运算，如果对任意的
x,y∈ S都有
x o y=y o x,
则称运算 o 在 S上是可交换的，或者说 o 在 S上适合交换律,
定义 6.1-6 设 o 为 S上的二元运算，如果对任意的
x,y,z∈ S都有
(x o y) o z=x o (y o z),
则称运算 o 在 S上是可结合的，或者说 o 在 S上适合结合律,
6.1.2 二元运算及其性质定义 6.1-7 设 o 为 S上的二元运算，如果对任意的
x∈ S都有
x o x=x,
则称运算 o 适合幂等律，也可以说 S中的全体元素都是幂等元,
定义 6.1-8 设 o 和 *为 S上的二元运算，如果对任意的
x,y,z∈ S都有
x*(y o z)=(x*y) o (x*z),
(y o z)*x=(y*x) o (z*x)，
则称运算 *对 o 在 S上是可分配的，或者说 *对 o 在 S上适合分配律,
6.1.2 二元运算及其性质定义 6.1-9 设 o 和 *为 S上的两个可交换的二元运算，
如果对任意的 x,y∈ S都有
x*(x o y)=x，
x o (x*y)=x，
则称运算 o 和 *满足吸收律,
例如,在幂集 P(S)上 ∪ 和 ∩是满足吸收律的,
6.1.3 代数系统中的特殊元素给定集合 A上的二元运算 o,这里集合 A可以是单个元素，如：整数集合 Z，其运算为乘法，在 Z中存在元素 1，
使得? i∈ Z,i*1=i；若运算为加法,则在 Z中存在元素 0，使得? i∈ Z,i+0=i.于是，对满足这种特性的元素，应给予一个定义．
定义 6.1-10 设 o 为 S上的二元运算,如果存在元素 el
(或 er)∈ S使得对任意 x∈ S,都有
el o x=x （或 x o er=x）,
则称 el (或 er)是 S (或右幺元 ).若 e∈ S关于 o 既是左幺元,又是右幺元，则称 e为 S上关于运算 o 的幺元,
6.1.3 代数系统中的特殊元素定理 6.1-1 设 o 为 S上的二元运算,el,er分别为运算
,则有
el=er=e,
且 e为 S上关于运算 o 的唯一的幺元,
定义 6.1-11 设 o 为 S上的二元运算,若存在元素 θl(或
θr )∈ S使得对任意的 x∈ S,有
θl o x=θl,(或 θr o x=θr)
则称 θl (或 θr)是 S上关于运算 o 的左零元 (或右零元 ).
若 θ∈ S关于运算 o 既是左零元,又是右零元，则称 θ为 S上关于运算 o 的零元,
6.1.3 代数系统中的特殊元素定理 6.1-2 设 o 为 S上的二元运算,θl和 θr分别为运算
o 的左零元和右零元,如果
θl=θr=θ，
则 θ为 S上关于运算 o 的唯一的零元,
定义 6.1-12 设 o 为 S上的二元运算,e∈ S
的幺元,对于任意的 x∈ S,如果存在 yl∈ S(或 yr∈ S )使得
yl o x=e,(或 x o yr=e)
则称 yl(或 yr)是 x的左 (或右 )逆元,若 y∈ S既是 x的左逆元，又是 x的右逆元,则称 y是 x的逆元,
6.1.3 代数系统中的特殊元素定理 6.1-3 设 o 为 S上可结合的二元运算,e为该运算的幺元,对于 x∈ S,如果存在左逆元 yl和右逆元 yr，有
yl=yr=y,
则 y是 x的唯一的逆元,
定义 6.1-13 设 o 为 S上的二元运算,如果对任意的
x,y,z∈ S，满足以下条件：
(1) 若 x o y=x o z且 x不是零元,则 y＝ z；
(2) 若 y o x=z o x且 x不是零元,则 y＝ z，
就称运算 o 满足消去律,
6.2 代数系统的同态和同构
6.2.1 代数系统的同态与同构
6.2.2 特殊代数系统的同态与同构
6.2 代数系统的同态和同构代数系统的同态和同构就是在两个代数系统之间存在着一种特殊的映射 —— 保持运算的映射，它是研究两个代数系统之间关系的强有力的工具,下面先对只具有一个二元运算的代数系统给出同态映射的定义,
6.2.1 代数系统的同态与同构定义 6.2-1 设 V1=〈 S1,o 〉,V2=〈 S2,*〉
是代数系统,o和 *是二元运算，如果存在映射
φ∶ S1→S2 满足对任意的 x,y∈ S1有 φ(x o
y)=φ(x)*φ(y)，则称 φ是 V1 到 V2的同态映射,简称同态．
6.2.1 代数系统的同态与同构定义 6.2-2 设 φ是 V1=〈 S1,o 〉到 V2=
〈 S2,*〉的同态,则称〈 φ(S1),*〉是 V1在 φ下的同态像．
定义 6.2-3 设 φ是 V1=〈 S1,o 〉到 V2=
〈 S2,*〉的同态,如果 φ是满射的,则称 φ是 V1
到 V2的满同态,记作 V1～ V2.如果 φ是单射的,
则称 φ是 V1到 V2的单同态,如果 φ是双射的,则称 φ是 V1到 V2的同构,记作 V1 == V2.φ～
φ
6.2.2 特殊代数系统的同态与同构
1,具有两个二元运算代数系统的同态定义 6.2-4 二元运算代数系统的同态概念可以推广到一般的代数系统中去,先考虑具有两个二元运算的代数系统,
设 V1=〈 S1,o,* 〉,V2=〈 S2,o ′,*′〉是代数系统,其中 o,*,o ′,*′都是二元运算．如果
φ:S1→S 2满足以下条件,? x,y∈ S1，有
(1)φ(x o y)=φ(x) o ′φ(y)，
(2)φ(x*y)=φ(x)*′φ(y)，
则称 φ是 V1到 V2的同态映射,简称同态．
6.2.2 特殊代数系统的同态与同构
2.含有一元运算的代数系统中的同态定义 6.2-5 设 V1=〈 S1,o,Δ〉,V2=
〈 S2,*,Δ′〉是代数系统,其中 o,*是二元运算,Δ和
Δ′是一元运算,如果映射 φ:S1→S 2满足以下条件,
(1)? x,y∈ S1,有 φ(x o y)=φ(x)*φ(y);
(2)? x∈ S1,有 φ(Δ(x))=Δ′(φ(x)),
则称 φ是 V1到 V2的同态,
6.2.2 特殊代数系统的同态与同构
3.具有代数常数的代数系统之间的同态定义 6.2-6 设 V1=〈 S1,o,k1〉,V2=
〈 S2,*,k2〉是代数系统，其中 o,*为二元运算,k1∈ S1,k2∈ S2 是代数常数,如果 φ:S1→S 2满足以下条件,
(1)? x,y∈ S1,有 φ(x o y)=φ(x)*φ(y);
(2) φ(k1)=k2,
则称 φ是 V1到 V2的同态,
6.3 代数系统的积代数
6.3.1 代数系统
6.3.2 积代数
6.3.1 代数系统定义 6.3-1 非空集合 S和 S上的 k个运算
f1,f2,…,f k (其中 fi为 ni元运算,i=1,2,…,k) 组成的系统称为一个代数系统,简称代数,记作〈 S,f1,f2,…,f k〉,
定义 6.3-2 设 o 和 Δ是集合 S上的二元运算和一元运算,S′是 S的子集,如果 a,b∈ S′,蕴含着
a o b∈ S′,那么 S′对 o 是封闭的,如果 a∈ S′蕴含着 Δa∈ S′,那么 S′对 Δ是封闭的,
6.3.1 代数系统定义 6.3-3 设 V=〈 S,f1,f2,…,f k〉 是代数系统,
B S且 B≠φ,如果 B对 f1,f2,…,f k都是封闭的,且 B和
S含有相同的代数常数,则称 〈 B,f1,f2,…,f k〉 是 V的子代数系统,简称子代数,
定义 6.3-4 对于任何代数系统 V=〈 S,f1,f2,…,
fk〉,其子代数一定存在，最大的子代数就是 V本身,
如果令 V中所有代数常数构成的集合是 B,且 B对 V
中所有的运算都是封闭的,则 B就构成了 V的最小的子代数,这种最大和最小的子代数称为 V的平凡的子代数,若 B是 S的真子集,则 B构成的子代数称为 V
的真子代数,
6.3.2 积代数由两个代数系统 V1和 V2可以产生一个新的代数系统 V1× V2，这就是 V1和 V2的积代数,
定义 6.3-5 设 V1=〈 S1,o 〉,V2=〈 S2,*〉是代数系统,o 和 *为二元运算,V1和 V2的积代数 V1× V2
是含有一个二元运算 ·的代数系统,即 V1× V2=
〈 S,·〉，其中 S=S1× S2，且对任意的〈 x1,y1〉,
〈 x2,y2〉 ∈ S1× S2有
〈 x1,y1〉 ·〈 x2,y2〉 =〈 x1 o x2,y1*y2〉,
6.4 半群与独异点
6.4.1 半群
6.4.2 半群中元素的幂
6.4.3 子半群
6.4 半群与独异点一般地，我们限于讨论只含一个二元运算的代数系统 〈 P,o〉,如果不对这个二元运算加以限制，则得到一般的代数系统，称它为二元代数或广群,如果二元代数 〈 P,o〉 中的运算 o 满足结合律，则称 〈 P,o〉 是半群,含有幺元的半群称为含幺半群,半群是二元代数中最简单的代数系统，它在时序线路、形式语言理论、自动机理论中均有很广泛的应用,
6.4.1 半群定义 6.4-1 一个代数系统 〈 P,o〉,其中 P
是非空集合,o是 P上的一个二元运算,如果满足：
（ 1）运算 o 是封闭的,
（ 2）运算 o 是可结合的，即对任意的 a,b，
c∈ P，满足（ a o b） o c=a o （ b o c），
则称代数系统 〈 P,o 〉 为半群,
6.4.1 半群定义 6.4-2 如果 V=〈 S,o 〉中的二元运算是可交换的，
则称 V可交换半群,
定理 6.4-1 设半群 〈 S,o 〉 存在左幺元 el和右幺元 er，
则 el=er，且幺元唯一,
定义 6.4-3 如果半群 〈 S,o 〉 中的二元运算含有幺元，
则称 V为含幺半群，也可叫做独异点,为了强调幺元的存在，
有时将独异点记为 〈 S,o,e〉 (e是幺元 ).
6.4.1 半群定义 6.4-4 设 〈 S,o 〉 是含幺半群,S中的元素 a称为右可逆的，如果存在 ar,使 a o ar =e,ar 称为 a的一个右逆元,a称为左可逆的，如果存在 al ∈ S,使 ar
a=e,al 称为 a的一个左逆元,若一个元素既是 a的左逆元，
又是 a的右逆元，则称该元素为 a的逆元,
定理 6.4-2 一个有限独异点 〈 S,*,e〉 的运算表中任何两行或两列元素都不会相同,
定理 6.4-3 设 〈 S,*,e〉 是独异点,对 a,b∈ S,且 a、
b均有逆元,则
(1) (a ) =a.
(2) (a*b) =b *a,
-1-1
-1 -1 -1
-1 -1 -1
-1
-1 -1
6.4.1 半群定义 6.4-2 如果 V=〈 S,o 〉中的二元运算是可交换的，
则称 V可交换半群,
定理 6.4-1 设半群 〈 S,o 〉 存在左幺元 el和右幺元 er，
则 el=er，且幺元唯一,
定义 6.4-3 如果半群 〈 S,o 〉 中的二元运算含有幺元，
则称 V为含幺半群，也可叫做独异点,为了强调幺元的存在，
有时将独异点记为 〈 S,o,e〉 (e是幺元 ).
6.4.2 半群中元素的幂定义 6.4-5 定义运算的幂,x∈ S,x 指的是：
x = x,x =x o x (n为正整数 ),
x = e,
x o x =x,
(x ) =x (n,m为非负整数 ).
n
1 n+1 n
0
n m n+m
n m nm
6.4.3 子半群定义 6.4-6 半群的子代数叫子半群，独异点的子代数叫子独异点,
例如,〈 Z,+〉,〈 N,+〉,都是 〈 Z,+〉 的子半群，且
〈 N,+〉 是 〈 Z,+〉 的子独异点,
定义 6.4-7 设 V1=〈 S1,o 〉,V2=〈 S2,*〉 为半群，且
V1× V2=〈 S1× S2,·〉 也是半群，且对任意 〈 a,b〉,〈 c,d〉
∈ S1× S2,有
〈 a,b〉 ·〈 c,d〉 =〈 a o c,b*d〉,
则称 V1× V2为 V1和 V2的积半群,
定义 6.4-8 设 V1=〈 S1,o 〉,V2=〈 S2,*〉 为半群,φ:S1→S 2,
且对任意 x,y∈ S1有
φ(x o y)=φ(x)*φ(y),
则称 φ为半群 V1到 V2的同态,
+
6.4 群与交换群
6.5.1 群的定义
6.5.2 群的基本性质
6.5.3 子群
6.5.4 循环群
6.5.1 群的定义定义 6.5-1 设〈 G,o 〉是代数系统,o为二元运算,如果 o 运算是可结合的，存在幺元 e∈ G，并且对
G中的任何元素 x都有 x-1∈ G,则称 G为群,群〈 G,o 〉
满足以下 3个条件：
(1)对所有的 a,b,c∈ G,有
a o (b o c)=(a o b) o c;
(2)存在一个元素，对任意元素 a∈ G，有
a o e=e o a=a;
(3)对每一 a∈ G,存在一个元素 a-1，使
a-1 o a=a o a-1=e.
6.5.1 群的定义定义 6.5-2 若群 G中的二元运算是可交换的，则称 G为交换群或阿贝尔 (Abel)群,
定义 6.5-3 若群 G是有穷集,则称 G是有限群，否则称为无限群,
群 G的基数称为群 G的阶，有限群 G的阶记作 |G|.只含单位元的群称为平凡群,例如,
(1)〈 Z,+〉,〈 R,+〉是无限群,
(2)〈 Zn,? 〉是有限群，也是 n阶群,
(3) Klein四元群是 4阶群,
(4)〈 {0},+〉是平凡群,
上述所有的群都是交换群,但 n阶 (n≥2)实可逆矩阵的集合关于矩阵乘法构成的群是非交换群，因为矩阵乘法不满足交换律,
6.5.2 群的 基本性质定理 6.5-1 设 G为群,则 G中的幂运算满足：
(1) a ∈ G,(a-1) -1＝ a；
(2) a,b∈ G,(a o b) -1=b-1 o a-1.
定理 6.5-2 G为群,?a,b∈ G，方程 a*x＝
b和 y*a＝ b在 G中有解且仅有唯一解,
定理 6.5-3 幺元是群中唯一等幂元素,
6.5.2 群的 基本性质定理 6.5-4 G为群,则 G中适合消去律，即对任意 a,b,c∈ G有
(1) 若 a*b＝ a*c，则 b＝ c.
(2) 若 b*a＝ c*a，则 b＝ c.
6.5.3 子群定义 6.5-4 设群 H是 G的非空子集，如果 H关于 G
中的运算构成群，则 H是 G的子群，记作 H≤G.
例如,(1) 群〈 Z,+〉，令 2Z={2z|z∈ Z}，则
〈 2Z,+〉是〈 Z,+〉的子群，同样，〈 {0},+〉也是
〈 Z,+〉的子群,
(2)Klein四元群 G={a,b,c,e}有 5个子群分别为：
{e},{e,a},{e,b},{e,c},G,
其中 {e}和 G是平凡子群，其余均为真子群,
定理 6.5-5 设 G为群,H是 G的非空子集,H是 G的子群当且仅当 a,b∈ H有
ab-1∈ H.
6.5.3 子群定义 6.5-5 设 G为群，对任意 a∈ G,令
H={ak |k∈ Z}，
即 x所有幂的集合,不难判定 H是 G的子群,因为任意 H中的元素 am,al，都有
am(al) -1＝ ama-l=a m-l∈ H,
称这个子群是元素 x的生成子群，记作〈 x〉,
6.5.4 循环群定义 6.5-6 设 G是群，若存在 a∈ G使得
G={ak|k∈ Z},
则称 G是循环群，记作 G＝〈 a〉，称 a为 G的生成元,
定理 6.5-6 设 G=〈 a〉 是循环群,
(1)若 G是无限循环群，则 G只有两个生成元，即
a和 a-1.
(2)若 G是 n阶循环群，则含有 φ(n)1个生成元，对于任何小于 n且与 n互质的正整数 r,ar是 G的生成元,
6.5.4 循环群定义 6.5-7 设 G是群,a∈ G，使得等式
ak＝ e
成立的最小正整数 k称为 a的阶，记作 |a|＝ k，这时也称 a为 k阶元,若不存在这样的正整数 k,则称 a为无限阶元,
定理 6.5-7 设 〈 G,*〉 是由元素 a生成的有限循环群,若 G的阶为 n，即 |G|=n，则幺元 e=an，且
G={a,a2,a3,…,a n-1,an },
其中 n是使 an=e的最小正整数，为 G的阶,
6.4 环与域
6.6.1 环的概念
6.6.2 域的概念
6.4 环与域环与域都是具有两个二元运算的代数系统，
通常把这两种运算称为加法运算,+”和乘法运算,*”，并且乘法对加法满足分配律，分配律说明了两个运算之间的联系,群的理论无法描述像实数系统这样丰富的结构,因此，必须研究具有两个发生联系的二元运算的代数结构，环和域就是这样的代数系统,在计算机科学中，环和域的概念在计算机密码学中有着重要的应用,
6.6.1 环的概念定义 6.6-1〈 R,+,·〉 是代数系统,R为集合,+,· 是二元运算，如果满足
（ 1） 〈 R,+〉 是阿贝尔群 ;
（ 2） 〈 R,·〉 是半群 ;
（ 3） ·运算对 +运算适合分配律，即对任意元素 a,b,c∈ R，有
a·（ b＋ c）＝ a·b+a·c,（ b＋ c)·a=b·a+c o a,
则称 〈 R,+,·〉 是环,
6.6.1 环的概念定义 6.6-2 〈 R,+,·〉 为环,S R,S≠φ,当
〈 S,+,·〉 是环时，称它为 R的子环,特别在 S=R
或 S={0}时称它为 R的平凡子环，否则称为 R的真子环,
定义 6.6-3 设 R是环,S是 R的非空子集,若
(1)?a,b∈ S,a+b∈ S；
(2)?a,b∈ S,a·b∈ S，
则 S是 R的子环,
6.6.1 环的概念定义 6.6-4 设〈 R,+,·〉中，如果乘法 ·适合交换律，则称〈 R,+,·〉是可交换环,
定义 6.6-5 已知环 〈 R,+,·〉 与 〈 R′,,*〉,若存在映射 φ,R→R′ 对任 r1,r2∈ R有
φ(r1+r2)=φ(r1) o φ(r2)，
φ(r1·r 2)=φ(r1)*φ(r2)，
则称 φ为 R到 R′的同态映射；当 φ (R)=R′称两个环同态；当 φ为一一对应时称两个环同构；当 R′ R时称 R到 R′的同态为自同态，同构为自同构,
6.6.1 环的概念定义 6.6-6 在环 〈 R,+,·〉 中，对 a，
b∈ R,a≠0,b≠0,但 a·b＝ 0，则称 a是 R中的一个左零因子,b是 R中的一个右零因子；若一个元素既是左零因子，又是右零因子，则称它是一个零因子,如果环
R中既不含左零因子，也不含右零因子，即?a，
b∈ R,a·b＝ 0，则 a=0或 b=0,则称 R是无零因子环,
定理 6.6-1 设 〈 R,+,·〉 是环,R是无零因子环的充分必要条件是在 R中乘法适合消去律,即对任意 a，
b,c∈ R,a≠0,若有 a·b＝ a·c（或 b·a=c·a）,则有 b=c.
定义 6.6-7 若 〈 R,+,·〉 是含幺的、可交换的和无零因子的，则称 〈 R,+,·〉 是整环,
6.6.1 环的概念定义 6.6-8 设〈 R,+,·〉是一个环，且 |R|≥2，
(1)R有幺元；
(2)每个非零元有逆元，
则称这个环为除环,
定理 6.6-2 设〈 R,+,·〉是一个环，则对于任意 a,b，
c∈ R，有
(1)a·0=0·a=0;
(2)(-a)·b=a·(- b )=- (a·b) ;
(3)(-a)·(-b)=a·b ;
(4)a·(b-c)=a·b-a·c;
(5)(b-c)·a=b·a-c·a.
6.6.2 域的概念定义 6.6-9 若环〈 R,+,·〉既是整环，又是除环，则环〈 R,+,·〉称之为域,若〈 S,+,·〉也是域且 S R,则称 S是 R的子域,
6.7 格与布尔代数
6.7.1 格的概念
6.7.2 格的性质
6.7.3 几种特殊的格
6.7.4 布尔代数
6.7.1 格的概念设 I1和 I2是偏序集 〈 L； ≤〉 中的两个元素，元素 a∈ L，如果满足 a ≤ I1,a ≤ I2，则称 a为 I1和 I2的下界,如果元素 a是 I1和 I2
的下界，且对任意的 a′∈ L，若 a′是 I1和 I2的下界，便有 a′ ≤ a，
则称 a为 I1和 I2的最大下界,
设 I1和 I2是偏序集 〈 L; ≤ 〉 中的两个元素，元素 b∈ L，如果满足 I1 ≤ b,I2 ≤ b，则称 b为 I1和 I2的上界,如果元素 b是 I1和 I2的上界，且对任意的 b′∈ L，若 b′是 I1和 I2的上界，便有 b ≤ b′，则称 b为 I1和 I2的最小上界,
定义 6.7-1 设 〈 S,≤ 〉 是偏序集，如果?x,y∈ S,{x,y}都有最小上界（记 x∨ y）和最大下界（ x∧ y），则称 S
成一个格,格 〈 L,≤ 〉 也记作 〈 L,∧,∨ 〉,
6.7.1 格的概念定义 6.7-2 设〈 A,≤ 〉是一个格，由
〈 A,≤ 〉诱导的代数系统为〈 A,∨,∧ 〉,B A
且 B≠φ,如果 A中的这两个运算关于 B是封闭的，
则称〈 B,≤ 〉是〈 A,≤ 〉的子格,
6.7.2 格的性质
1.对偶原理设 f是含有格中的元素以及符号 =,≤,≥、
∨,∧ 的命题，令 f*是将 f中的 ≤ 改写成 ≥,≥
写成 ≤,∨ 写成 ∧,∧ 写成 ∨ 所得到的命题，
称为 f的对偶命题,若 f对一切格为真，则 f*也对一切格为真,
6.7.2 格的性质
2.性质设〈 L,≤〉为格，则运算 ∨ 和 ∧ 适合交换律、结合律幂等律和吸收律，即?a,b,c∈ L，有
（ 1）交换律 a∨ b=b∨ a,a∧ b=b∧ a.
（ 2）结合律 (a∨ b)∨ c=a∨ (b∨ c),
(a∧ b)∧ c=a∧ (b∧ c).
（ 3）幂等律 a∨ a=a,a∧ a=a.
（ 4）吸收律 a∨ (a∧ b)=a,
a∧ (a∨ b)=a.
6.7.3 几种特殊的格
1.分配格设 〈 A,∨,∧ 〉 是由格 〈 A,≤〉 所诱导的代数系统,如果?a,b,c∈ A，满足
a∧ (b∨ c)=(a∧ b)∨ (a∧ c)
和
a∨ (b∧ c)=(a∨ b)∧ (a∨ c)，
则称 〈 A,≤ 〉 是分配格,
6.7.3 几种特殊的格定理 6.7-1 如果在一个格中交运算对于并运算可分配，则并运算对交运算也一定是可分配的，反之亦然,
定理 6.7-2 每个链都是分配格,
6.7.3 几种特殊的格
2.格的全下界、全下界、有界格定义 6.7-3 设〈 A,≤ 〉是一个格，如果存在元素
a∈ A，对于任意 x∈ A，都有 a ≤ x，则称 a为格〈 A,
≤ 〉的全下界，记格的全下界为 0.
定义 6.7-4 设〈 A,≤ 〉是一个格，如果存在元素
b∈ A，对于任意 x∈ A，都有 x ≤ b,称 b为格〈 A,≤ 〉
的全上界，记格的全上界为 1.
定义 6.7-5 如果一个格中存在全上界和全下界，
则称该格为有界格,
6.7.3 几种特殊的格
3.有补格定义 6.7-6 有界格〈 L,∧,∨,0,1〉，若对?a∈ L存在 a的补元（记为 a′），使 a∧ a′=0，
a∨ a′=1，则称为有补格,
6.7.3 几种特殊的格
4.有补分配格如果一个格既是有补格，又是分配格，则称它为有补分配格,
6.7.4 布尔代数格和布尔代数都是具有两个二元运算的代数系统，布尔代数是格的特例．它是人们利用数学方法研究人类思维规律所得到的一个重要成果，它与数理逻辑有着极其密切的联系,
定义 6.7-7 如果格〈 L,∧,∨,0,1〉是有补分配格，则 L为布尔格，也叫做布尔代数,
6.7.4 布尔代数定理 6.7-3 (有限布尔代数的表示定理 )对于布尔代数〈 L,∧,∨,′,0,1〉，都存在一个集合 S，使得〈 P(S),∩,∪,~,,S〉与其同构，且
L含有 2n个元（ n∈ N）,其中 S是一个 n元集合,
本章小结本章主要讨论了：
（ 1）一元和二元运算的概念；二元运算律 (结合律，交换律，分配律 )；二元运算的特殊元素 (幺元，零元，逆元 ).
（ 2）代数系统的同态映射，同构映射的定义及判定,
（ 3）代数系统，子代数，积代数的有关概念,
（ 4）半群，可交换半群，独异点的定义；半群中元素幂的定义及性质；子半群，子独异点，积半群，半群同态的定义,
（ 5）群的定义及性质；交换群 (阿贝尔群 )的定义及性质；
子群的定义及性质；循环群的定义及性质,
（ 6）介绍环与域的定义及代数系统为环、域的方法,
（ 7）格与布尔代数的有关概念及例子,
6.1 代数系统的概念
6.2 代数系统的同态和同构
6.3 代数系统的积代数
6.4 半群与独异点
6.5 群与交换群
6.6 环与域
6.7 格与布尔代数第 6章 代数系统代数的概念与方法是研究计算机科学和工程的重要数学工具,它属于近世代数的内容,众所周知，近世代数是研究具有运算的集合，它第一次揭示了数学系统的多变性与丰富性，而近世代数研究的中心问题是代数系统的结构：半群、群、格与布尔代数等,代数系统的结构理论可用于计算机算法的复杂度分析，研究抽象数据结构的性质及操作，同时也是程序设计语言的理论基础,本章将对代数系统的基本概念及主要的代数系统进行重点介绍,
6.1 代数系统的概念
6.1.1 代数运算的定义
6.1.2 二元运算及其性质
6.1.3 代数系统中的特殊元素
6.1.1 代数运算的定义定义 6.1-1 设 S为集合，函数
f:S→S,称为 S上的一个一元运算,
定义 6.1-2 设 S为集合，函数
f:S× S→S,称为 S上的一个二元运算,
定义 6.1-3 设 S为集合，函数
f,S× S× … × S→S,称为 S上的一个 n
元运算,
6.1.1 代数运算的定义定义 6.1-4 通常用 o,*,·等符号表示二元运算，称为算符,设 f:S× S→S 是 S上的二元运算，对任意的 x,y∈ S,x与 y的运算结果是 z,即
f(〈 x,y〉 ) = z，
可利用算符 o 简记为
x o y=z.
6.1.2 二元运算及其性质
1.二元运算二元运算是最常见的代数运算,下面是一些常见集合的二元运算：
(1)自然数集合 N上的乘法是 N上的二元运算,但除法不是,
(2)整数集合 Z上的加法、减法和乘法是 Z上的二元运算，但除法不是,
(3)非零实数集 R*上的乘法和除法都是 R*上的二元运算，但加法、减法不是,
(4)设 Mn(R)表示所有 n阶实矩阵的集合 (n≥2)，即
（见第 110页公式）
则矩阵加法和乘法都是 Mn(R)上的二元运算,
(5)S为任意集合,则 ∪,∩,-,? 为 S的幂集 P(S)上的二元运算,
(6)S为任意集合,S 是 S上的所有函数的集合,则合成运算 o 是 S 上的二元运算,
s
s
6.1.2 二元运算及其性质
2.二元运算的性质定义 6.1-5 设 o 为 S上的二元运算，如果对任意的
x,y∈ S都有
x o y=y o x,
则称运算 o 在 S上是可交换的，或者说 o 在 S上适合交换律,
定义 6.1-6 设 o 为 S上的二元运算，如果对任意的
x,y,z∈ S都有
(x o y) o z=x o (y o z),
则称运算 o 在 S上是可结合的，或者说 o 在 S上适合结合律,
6.1.2 二元运算及其性质定义 6.1-7 设 o 为 S上的二元运算，如果对任意的
x∈ S都有
x o x=x,
则称运算 o 适合幂等律，也可以说 S中的全体元素都是幂等元,
定义 6.1-8 设 o 和 *为 S上的二元运算，如果对任意的
x,y,z∈ S都有
x*(y o z)=(x*y) o (x*z),
(y o z)*x=(y*x) o (z*x)，
则称运算 *对 o 在 S上是可分配的，或者说 *对 o 在 S上适合分配律,
6.1.2 二元运算及其性质定义 6.1-9 设 o 和 *为 S上的两个可交换的二元运算，
如果对任意的 x,y∈ S都有
x*(x o y)=x，
x o (x*y)=x，
则称运算 o 和 *满足吸收律,
例如,在幂集 P(S)上 ∪ 和 ∩是满足吸收律的,
6.1.3 代数系统中的特殊元素给定集合 A上的二元运算 o,这里集合 A可以是单个元素，如：整数集合 Z，其运算为乘法，在 Z中存在元素 1，
使得? i∈ Z,i*1=i；若运算为加法,则在 Z中存在元素 0，使得? i∈ Z,i+0=i.于是，对满足这种特性的元素，应给予一个定义．
定义 6.1-10 设 o 为 S上的二元运算,如果存在元素 el
(或 er)∈ S使得对任意 x∈ S,都有
el o x=x （或 x o er=x）,
则称 el (或 er)是 S (或右幺元 ).若 e∈ S关于 o 既是左幺元,又是右幺元，则称 e为 S上关于运算 o 的幺元,
6.1.3 代数系统中的特殊元素定理 6.1-1 设 o 为 S上的二元运算,el,er分别为运算
,则有
el=er=e,
且 e为 S上关于运算 o 的唯一的幺元,
定义 6.1-11 设 o 为 S上的二元运算,若存在元素 θl(或
θr )∈ S使得对任意的 x∈ S,有
θl o x=θl,(或 θr o x=θr)
则称 θl (或 θr)是 S上关于运算 o 的左零元 (或右零元 ).
若 θ∈ S关于运算 o 既是左零元,又是右零元，则称 θ为 S上关于运算 o 的零元,
6.1.3 代数系统中的特殊元素定理 6.1-2 设 o 为 S上的二元运算,θl和 θr分别为运算
o 的左零元和右零元,如果
θl=θr=θ，
则 θ为 S上关于运算 o 的唯一的零元,
定义 6.1-12 设 o 为 S上的二元运算,e∈ S
的幺元,对于任意的 x∈ S,如果存在 yl∈ S(或 yr∈ S )使得
yl o x=e,(或 x o yr=e)
则称 yl(或 yr)是 x的左 (或右 )逆元,若 y∈ S既是 x的左逆元，又是 x的右逆元,则称 y是 x的逆元,
6.1.3 代数系统中的特殊元素定理 6.1-3 设 o 为 S上可结合的二元运算,e为该运算的幺元,对于 x∈ S,如果存在左逆元 yl和右逆元 yr，有
yl=yr=y,
则 y是 x的唯一的逆元,
定义 6.1-13 设 o 为 S上的二元运算,如果对任意的
x,y,z∈ S，满足以下条件：
(1) 若 x o y=x o z且 x不是零元,则 y＝ z；
(2) 若 y o x=z o x且 x不是零元,则 y＝ z，
就称运算 o 满足消去律,
6.2 代数系统的同态和同构
6.2.1 代数系统的同态与同构
6.2.2 特殊代数系统的同态与同构
6.2 代数系统的同态和同构代数系统的同态和同构就是在两个代数系统之间存在着一种特殊的映射 —— 保持运算的映射，它是研究两个代数系统之间关系的强有力的工具,下面先对只具有一个二元运算的代数系统给出同态映射的定义,
6.2.1 代数系统的同态与同构定义 6.2-1 设 V1=〈 S1,o 〉,V2=〈 S2,*〉
是代数系统,o和 *是二元运算，如果存在映射
φ∶ S1→S2 满足对任意的 x,y∈ S1有 φ(x o
y)=φ(x)*φ(y)，则称 φ是 V1 到 V2的同态映射,简称同态．
6.2.1 代数系统的同态与同构定义 6.2-2 设 φ是 V1=〈 S1,o 〉到 V2=
〈 S2,*〉的同态,则称〈 φ(S1),*〉是 V1在 φ下的同态像．
定义 6.2-3 设 φ是 V1=〈 S1,o 〉到 V2=
〈 S2,*〉的同态,如果 φ是满射的,则称 φ是 V1
到 V2的满同态,记作 V1～ V2.如果 φ是单射的,
则称 φ是 V1到 V2的单同态,如果 φ是双射的,则称 φ是 V1到 V2的同构,记作 V1 == V2.φ～
φ
6.2.2 特殊代数系统的同态与同构
1,具有两个二元运算代数系统的同态定义 6.2-4 二元运算代数系统的同态概念可以推广到一般的代数系统中去,先考虑具有两个二元运算的代数系统,
设 V1=〈 S1,o,* 〉,V2=〈 S2,o ′,*′〉是代数系统,其中 o,*,o ′,*′都是二元运算．如果
φ:S1→S 2满足以下条件,? x,y∈ S1，有
(1)φ(x o y)=φ(x) o ′φ(y)，
(2)φ(x*y)=φ(x)*′φ(y)，
则称 φ是 V1到 V2的同态映射,简称同态．
6.2.2 特殊代数系统的同态与同构
2.含有一元运算的代数系统中的同态定义 6.2-5 设 V1=〈 S1,o,Δ〉,V2=
〈 S2,*,Δ′〉是代数系统,其中 o,*是二元运算,Δ和
Δ′是一元运算,如果映射 φ:S1→S 2满足以下条件,
(1)? x,y∈ S1,有 φ(x o y)=φ(x)*φ(y);
(2)? x∈ S1,有 φ(Δ(x))=Δ′(φ(x)),
则称 φ是 V1到 V2的同态,
6.2.2 特殊代数系统的同态与同构
3.具有代数常数的代数系统之间的同态定义 6.2-6 设 V1=〈 S1,o,k1〉,V2=
〈 S2,*,k2〉是代数系统，其中 o,*为二元运算,k1∈ S1,k2∈ S2 是代数常数,如果 φ:S1→S 2满足以下条件,
(1)? x,y∈ S1,有 φ(x o y)=φ(x)*φ(y);
(2) φ(k1)=k2,
则称 φ是 V1到 V2的同态,
6.3 代数系统的积代数
6.3.1 代数系统
6.3.2 积代数
6.3.1 代数系统定义 6.3-1 非空集合 S和 S上的 k个运算
f1,f2,…,f k (其中 fi为 ni元运算,i=1,2,…,k) 组成的系统称为一个代数系统,简称代数,记作〈 S,f1,f2,…,f k〉,
定义 6.3-2 设 o 和 Δ是集合 S上的二元运算和一元运算,S′是 S的子集,如果 a,b∈ S′,蕴含着
a o b∈ S′,那么 S′对 o 是封闭的,如果 a∈ S′蕴含着 Δa∈ S′,那么 S′对 Δ是封闭的,
6.3.1 代数系统定义 6.3-3 设 V=〈 S,f1,f2,…,f k〉 是代数系统,
B S且 B≠φ,如果 B对 f1,f2,…,f k都是封闭的,且 B和
S含有相同的代数常数,则称 〈 B,f1,f2,…,f k〉 是 V的子代数系统,简称子代数,
定义 6.3-4 对于任何代数系统 V=〈 S,f1,f2,…,
fk〉,其子代数一定存在，最大的子代数就是 V本身,
如果令 V中所有代数常数构成的集合是 B,且 B对 V
中所有的运算都是封闭的,则 B就构成了 V的最小的子代数,这种最大和最小的子代数称为 V的平凡的子代数,若 B是 S的真子集,则 B构成的子代数称为 V
的真子代数,
6.3.2 积代数由两个代数系统 V1和 V2可以产生一个新的代数系统 V1× V2，这就是 V1和 V2的积代数,
定义 6.3-5 设 V1=〈 S1,o 〉,V2=〈 S2,*〉是代数系统,o 和 *为二元运算,V1和 V2的积代数 V1× V2
是含有一个二元运算 ·的代数系统,即 V1× V2=
〈 S,·〉，其中 S=S1× S2，且对任意的〈 x1,y1〉,
〈 x2,y2〉 ∈ S1× S2有
〈 x1,y1〉 ·〈 x2,y2〉 =〈 x1 o x2,y1*y2〉,
6.4 半群与独异点
6.4.1 半群
6.4.2 半群中元素的幂
6.4.3 子半群
6.4 半群与独异点一般地，我们限于讨论只含一个二元运算的代数系统 〈 P,o〉,如果不对这个二元运算加以限制，则得到一般的代数系统，称它为二元代数或广群,如果二元代数 〈 P,o〉 中的运算 o 满足结合律，则称 〈 P,o〉 是半群,含有幺元的半群称为含幺半群,半群是二元代数中最简单的代数系统，它在时序线路、形式语言理论、自动机理论中均有很广泛的应用,
6.4.1 半群定义 6.4-1 一个代数系统 〈 P,o〉,其中 P
是非空集合,o是 P上的一个二元运算,如果满足：
（ 1）运算 o 是封闭的,
（ 2）运算 o 是可结合的，即对任意的 a,b，
c∈ P，满足（ a o b） o c=a o （ b o c），
则称代数系统 〈 P,o 〉 为半群,
6.4.1 半群定义 6.4-2 如果 V=〈 S,o 〉中的二元运算是可交换的，
则称 V可交换半群,
定理 6.4-1 设半群 〈 S,o 〉 存在左幺元 el和右幺元 er，
则 el=er，且幺元唯一,
定义 6.4-3 如果半群 〈 S,o 〉 中的二元运算含有幺元，
则称 V为含幺半群，也可叫做独异点,为了强调幺元的存在，
有时将独异点记为 〈 S,o,e〉 (e是幺元 ).
6.4.1 半群定义 6.4-4 设 〈 S,o 〉 是含幺半群,S中的元素 a称为右可逆的，如果存在 ar,使 a o ar =e,ar 称为 a的一个右逆元,a称为左可逆的，如果存在 al ∈ S,使 ar
a=e,al 称为 a的一个左逆元,若一个元素既是 a的左逆元，
又是 a的右逆元，则称该元素为 a的逆元,
定理 6.4-2 一个有限独异点 〈 S,*,e〉 的运算表中任何两行或两列元素都不会相同,
定理 6.4-3 设 〈 S,*,e〉 是独异点,对 a,b∈ S,且 a、
b均有逆元,则
(1) (a ) =a.
(2) (a*b) =b *a,
-1-1
-1 -1 -1
-1 -1 -1
-1
-1 -1
6.4.1 半群定义 6.4-2 如果 V=〈 S,o 〉中的二元运算是可交换的，
则称 V可交换半群,
定理 6.4-1 设半群 〈 S,o 〉 存在左幺元 el和右幺元 er，
则 el=er，且幺元唯一,
定义 6.4-3 如果半群 〈 S,o 〉 中的二元运算含有幺元，
则称 V为含幺半群，也可叫做独异点,为了强调幺元的存在，
有时将独异点记为 〈 S,o,e〉 (e是幺元 ).
6.4.2 半群中元素的幂定义 6.4-5 定义运算的幂,x∈ S,x 指的是：
x = x,x =x o x (n为正整数 ),
x = e,
x o x =x,
(x ) =x (n,m为非负整数 ).
n
1 n+1 n
0
n m n+m
n m nm
6.4.3 子半群定义 6.4-6 半群的子代数叫子半群，独异点的子代数叫子独异点,
例如,〈 Z,+〉,〈 N,+〉,都是 〈 Z,+〉 的子半群，且
〈 N,+〉 是 〈 Z,+〉 的子独异点,
定义 6.4-7 设 V1=〈 S1,o 〉,V2=〈 S2,*〉 为半群，且
V1× V2=〈 S1× S2,·〉 也是半群，且对任意 〈 a,b〉,〈 c,d〉
∈ S1× S2,有
〈 a,b〉 ·〈 c,d〉 =〈 a o c,b*d〉,
则称 V1× V2为 V1和 V2的积半群,
定义 6.4-8 设 V1=〈 S1,o 〉,V2=〈 S2,*〉 为半群,φ:S1→S 2,
且对任意 x,y∈ S1有
φ(x o y)=φ(x)*φ(y),
则称 φ为半群 V1到 V2的同态,
+
6.4 群与交换群
6.5.1 群的定义
6.5.2 群的基本性质
6.5.3 子群
6.5.4 循环群
6.5.1 群的定义定义 6.5-1 设〈 G,o 〉是代数系统,o为二元运算,如果 o 运算是可结合的，存在幺元 e∈ G，并且对
G中的任何元素 x都有 x-1∈ G,则称 G为群,群〈 G,o 〉
满足以下 3个条件：
(1)对所有的 a,b,c∈ G,有
a o (b o c)=(a o b) o c;
(2)存在一个元素，对任意元素 a∈ G，有
a o e=e o a=a;
(3)对每一 a∈ G,存在一个元素 a-1，使
a-1 o a=a o a-1=e.
6.5.1 群的定义定义 6.5-2 若群 G中的二元运算是可交换的，则称 G为交换群或阿贝尔 (Abel)群,
定义 6.5-3 若群 G是有穷集,则称 G是有限群，否则称为无限群,
群 G的基数称为群 G的阶，有限群 G的阶记作 |G|.只含单位元的群称为平凡群,例如,
(1)〈 Z,+〉,〈 R,+〉是无限群,
(2)〈 Zn,? 〉是有限群，也是 n阶群,
(3) Klein四元群是 4阶群,
(4)〈 {0},+〉是平凡群,
上述所有的群都是交换群,但 n阶 (n≥2)实可逆矩阵的集合关于矩阵乘法构成的群是非交换群，因为矩阵乘法不满足交换律,
6.5.2 群的 基本性质定理 6.5-1 设 G为群,则 G中的幂运算满足：
(1) a ∈ G,(a-1) -1＝ a；
(2) a,b∈ G,(a o b) -1=b-1 o a-1.
定理 6.5-2 G为群,?a,b∈ G，方程 a*x＝
b和 y*a＝ b在 G中有解且仅有唯一解,
定理 6.5-3 幺元是群中唯一等幂元素,
6.5.2 群的 基本性质定理 6.5-4 G为群,则 G中适合消去律，即对任意 a,b,c∈ G有
(1) 若 a*b＝ a*c，则 b＝ c.
(2) 若 b*a＝ c*a，则 b＝ c.
6.5.3 子群定义 6.5-4 设群 H是 G的非空子集，如果 H关于 G
中的运算构成群，则 H是 G的子群，记作 H≤G.
例如,(1) 群〈 Z,+〉，令 2Z={2z|z∈ Z}，则
〈 2Z,+〉是〈 Z,+〉的子群，同样，〈 {0},+〉也是
〈 Z,+〉的子群,
(2)Klein四元群 G={a,b,c,e}有 5个子群分别为：
{e},{e,a},{e,b},{e,c},G,
其中 {e}和 G是平凡子群，其余均为真子群,
定理 6.5-5 设 G为群,H是 G的非空子集,H是 G的子群当且仅当 a,b∈ H有
ab-1∈ H.
6.5.3 子群定义 6.5-5 设 G为群，对任意 a∈ G,令
H={ak |k∈ Z}，
即 x所有幂的集合,不难判定 H是 G的子群,因为任意 H中的元素 am,al，都有
am(al) -1＝ ama-l=a m-l∈ H,
称这个子群是元素 x的生成子群，记作〈 x〉,
6.5.4 循环群定义 6.5-6 设 G是群，若存在 a∈ G使得
G={ak|k∈ Z},
则称 G是循环群，记作 G＝〈 a〉，称 a为 G的生成元,
定理 6.5-6 设 G=〈 a〉 是循环群,
(1)若 G是无限循环群，则 G只有两个生成元，即
a和 a-1.
(2)若 G是 n阶循环群，则含有 φ(n)1个生成元，对于任何小于 n且与 n互质的正整数 r,ar是 G的生成元,
6.5.4 循环群定义 6.5-7 设 G是群,a∈ G，使得等式
ak＝ e
成立的最小正整数 k称为 a的阶，记作 |a|＝ k，这时也称 a为 k阶元,若不存在这样的正整数 k,则称 a为无限阶元,
定理 6.5-7 设 〈 G,*〉 是由元素 a生成的有限循环群,若 G的阶为 n，即 |G|=n，则幺元 e=an，且
G={a,a2,a3,…,a n-1,an },
其中 n是使 an=e的最小正整数，为 G的阶,
6.4 环与域
6.6.1 环的概念
6.6.2 域的概念
6.4 环与域环与域都是具有两个二元运算的代数系统，
通常把这两种运算称为加法运算,+”和乘法运算,*”，并且乘法对加法满足分配律，分配律说明了两个运算之间的联系,群的理论无法描述像实数系统这样丰富的结构,因此，必须研究具有两个发生联系的二元运算的代数结构，环和域就是这样的代数系统,在计算机科学中，环和域的概念在计算机密码学中有着重要的应用,
6.6.1 环的概念定义 6.6-1〈 R,+,·〉 是代数系统,R为集合,+,· 是二元运算，如果满足
（ 1） 〈 R,+〉 是阿贝尔群 ;
（ 2） 〈 R,·〉 是半群 ;
（ 3） ·运算对 +运算适合分配律，即对任意元素 a,b,c∈ R，有
a·（ b＋ c）＝ a·b+a·c,（ b＋ c)·a=b·a+c o a,
则称 〈 R,+,·〉 是环,
6.6.1 环的概念定义 6.6-2 〈 R,+,·〉 为环,S R,S≠φ,当
〈 S,+,·〉 是环时，称它为 R的子环,特别在 S=R
或 S={0}时称它为 R的平凡子环，否则称为 R的真子环,
定义 6.6-3 设 R是环,S是 R的非空子集,若
(1)?a,b∈ S,a+b∈ S；
(2)?a,b∈ S,a·b∈ S，
则 S是 R的子环,
6.6.1 环的概念定义 6.6-4 设〈 R,+,·〉中，如果乘法 ·适合交换律，则称〈 R,+,·〉是可交换环,
定义 6.6-5 已知环 〈 R,+,·〉 与 〈 R′,,*〉,若存在映射 φ,R→R′ 对任 r1,r2∈ R有
φ(r1+r2)=φ(r1) o φ(r2)，
φ(r1·r 2)=φ(r1)*φ(r2)，
则称 φ为 R到 R′的同态映射；当 φ (R)=R′称两个环同态；当 φ为一一对应时称两个环同构；当 R′ R时称 R到 R′的同态为自同态，同构为自同构,
6.6.1 环的概念定义 6.6-6 在环 〈 R,+,·〉 中，对 a，
b∈ R,a≠0,b≠0,但 a·b＝ 0，则称 a是 R中的一个左零因子,b是 R中的一个右零因子；若一个元素既是左零因子，又是右零因子，则称它是一个零因子,如果环
R中既不含左零因子，也不含右零因子，即?a，
b∈ R,a·b＝ 0，则 a=0或 b=0,则称 R是无零因子环,
定理 6.6-1 设 〈 R,+,·〉 是环,R是无零因子环的充分必要条件是在 R中乘法适合消去律,即对任意 a，
b,c∈ R,a≠0,若有 a·b＝ a·c（或 b·a=c·a）,则有 b=c.
定义 6.6-7 若 〈 R,+,·〉 是含幺的、可交换的和无零因子的，则称 〈 R,+,·〉 是整环,
6.6.1 环的概念定义 6.6-8 设〈 R,+,·〉是一个环，且 |R|≥2，
(1)R有幺元；
(2)每个非零元有逆元，
则称这个环为除环,
定理 6.6-2 设〈 R,+,·〉是一个环，则对于任意 a,b，
c∈ R，有
(1)a·0=0·a=0;
(2)(-a)·b=a·(- b )=- (a·b) ;
(3)(-a)·(-b)=a·b ;
(4)a·(b-c)=a·b-a·c;
(5)(b-c)·a=b·a-c·a.
6.6.2 域的概念定义 6.6-9 若环〈 R,+,·〉既是整环，又是除环，则环〈 R,+,·〉称之为域,若〈 S,+,·〉也是域且 S R,则称 S是 R的子域,
6.7 格与布尔代数
6.7.1 格的概念
6.7.2 格的性质
6.7.3 几种特殊的格
6.7.4 布尔代数
6.7.1 格的概念设 I1和 I2是偏序集 〈 L； ≤〉 中的两个元素，元素 a∈ L，如果满足 a ≤ I1,a ≤ I2，则称 a为 I1和 I2的下界,如果元素 a是 I1和 I2
的下界，且对任意的 a′∈ L，若 a′是 I1和 I2的下界，便有 a′ ≤ a，
则称 a为 I1和 I2的最大下界,
设 I1和 I2是偏序集 〈 L; ≤ 〉 中的两个元素，元素 b∈ L，如果满足 I1 ≤ b,I2 ≤ b，则称 b为 I1和 I2的上界,如果元素 b是 I1和 I2的上界，且对任意的 b′∈ L，若 b′是 I1和 I2的上界，便有 b ≤ b′，则称 b为 I1和 I2的最小上界,
定义 6.7-1 设 〈 S,≤ 〉 是偏序集，如果?x,y∈ S,{x,y}都有最小上界（记 x∨ y）和最大下界（ x∧ y），则称 S
成一个格,格 〈 L,≤ 〉 也记作 〈 L,∧,∨ 〉,
6.7.1 格的概念定义 6.7-2 设〈 A,≤ 〉是一个格，由
〈 A,≤ 〉诱导的代数系统为〈 A,∨,∧ 〉,B A
且 B≠φ,如果 A中的这两个运算关于 B是封闭的，
则称〈 B,≤ 〉是〈 A,≤ 〉的子格,
6.7.2 格的性质
1.对偶原理设 f是含有格中的元素以及符号 =,≤,≥、
∨,∧ 的命题，令 f*是将 f中的 ≤ 改写成 ≥,≥
写成 ≤,∨ 写成 ∧,∧ 写成 ∨ 所得到的命题，
称为 f的对偶命题,若 f对一切格为真，则 f*也对一切格为真,
6.7.2 格的性质
2.性质设〈 L,≤〉为格，则运算 ∨ 和 ∧ 适合交换律、结合律幂等律和吸收律，即?a,b,c∈ L，有
（ 1）交换律 a∨ b=b∨ a,a∧ b=b∧ a.
（ 2）结合律 (a∨ b)∨ c=a∨ (b∨ c),
(a∧ b)∧ c=a∧ (b∧ c).
（ 3）幂等律 a∨ a=a,a∧ a=a.
（ 4）吸收律 a∨ (a∧ b)=a,
a∧ (a∨ b)=a.
6.7.3 几种特殊的格
1.分配格设 〈 A,∨,∧ 〉 是由格 〈 A,≤〉 所诱导的代数系统,如果?a,b,c∈ A，满足
a∧ (b∨ c)=(a∧ b)∨ (a∧ c)
和
a∨ (b∧ c)=(a∨ b)∧ (a∨ c)，
则称 〈 A,≤ 〉 是分配格,
6.7.3 几种特殊的格定理 6.7-1 如果在一个格中交运算对于并运算可分配，则并运算对交运算也一定是可分配的，反之亦然,
定理 6.7-2 每个链都是分配格,
6.7.3 几种特殊的格
2.格的全下界、全下界、有界格定义 6.7-3 设〈 A,≤ 〉是一个格，如果存在元素
a∈ A，对于任意 x∈ A，都有 a ≤ x，则称 a为格〈 A,
≤ 〉的全下界，记格的全下界为 0.
定义 6.7-4 设〈 A,≤ 〉是一个格，如果存在元素
b∈ A，对于任意 x∈ A，都有 x ≤ b,称 b为格〈 A,≤ 〉
的全上界，记格的全上界为 1.
定义 6.7-5 如果一个格中存在全上界和全下界，
则称该格为有界格,
6.7.3 几种特殊的格
3.有补格定义 6.7-6 有界格〈 L,∧,∨,0,1〉，若对?a∈ L存在 a的补元（记为 a′），使 a∧ a′=0，
a∨ a′=1，则称为有补格,
6.7.3 几种特殊的格
4.有补分配格如果一个格既是有补格，又是分配格，则称它为有补分配格,
6.7.4 布尔代数格和布尔代数都是具有两个二元运算的代数系统，布尔代数是格的特例．它是人们利用数学方法研究人类思维规律所得到的一个重要成果，它与数理逻辑有着极其密切的联系,
定义 6.7-7 如果格〈 L,∧,∨,0,1〉是有补分配格，则 L为布尔格，也叫做布尔代数,
6.7.4 布尔代数定理 6.7-3 (有限布尔代数的表示定理 )对于布尔代数〈 L,∧,∨,′,0,1〉，都存在一个集合 S，使得〈 P(S),∩,∪,~,,S〉与其同构，且
L含有 2n个元（ n∈ N）,其中 S是一个 n元集合,
本章小结本章主要讨论了：
（ 1）一元和二元运算的概念；二元运算律 (结合律，交换律，分配律 )；二元运算的特殊元素 (幺元，零元，逆元 ).
（ 2）代数系统的同态映射，同构映射的定义及判定,
（ 3）代数系统，子代数，积代数的有关概念,
（ 4）半群，可交换半群，独异点的定义；半群中元素幂的定义及性质；子半群，子独异点，积半群，半群同态的定义,
（ 5）群的定义及性质；交换群 (阿贝尔群 )的定义及性质；
子群的定义及性质；循环群的定义及性质,
（ 6）介绍环与域的定义及代数系统为环、域的方法,
（ 7）格与布尔代数的有关概念及例子,
