第二版)
阮传概孙伟编著
北京邮电大学出版社·北京·
内容提要
本书介绍了集合与映射、格、布尔代数、半群、群、环、有限域的基本内容和它们在逻辑电路与编码理论中的一些应用,以及与上述内容有关的一些多项式和线性同余式等知识。
全书比较注重应用,条理清晰,论证详细,例题较多,每章末均附有习题。
为了便于自学与参考,在本书的最后附有习题解答。
本书可作为通信理论、计算机科学、系统工程等有关专业的近世代数课程的教材,也可供从事工科有关各专业以及应用数学、应用物理等科技人员参考。
图书在版编目(CIP)数据 近世代数及其应用/阮传概,孙伟编著.—2版.北京:北京邮电大学出版社,2001.8 ISBN7-5635-0533-4Ⅰ.近...Ⅱ.①阮...②孙...Ⅲ.抽象代数Ⅳ.O153中国版本图书馆CIP数据核字(2001)第045092号 书 名:近世代数及其应用 编 著:阮传概孙伟 责任编辑:徐夙琨 出版者:北京邮电大学出版社(北京市海淀区西土城路10号) 邮编:100876电话:6228218562283578 网址: 经 销:各地新华书店 印 刷:北京源海印刷厂 印 数:6001—9000 开 本:850mm×1168mm1/32印张:13.625字数:351千字 版 次:2001年9月第1版2005年2月第3次印刷 ISBN:7-5635-0533-4/O·30 定价:25.00元 再版前言 近世代数的内容,不但在数学的各分支有很多应用,而且随着科学技术的发展,它在通信理论、计算机科学、系统工程等许多领域中也有广泛的应用。
本书是为上述各专业的工科学生编写的,所以比较注重应用,例题较多,出版后受到读者的欢迎。
这次再版时,根据读者的意见与建议,做了修改与补充。
为了便于自学,增加了习题解答,可供读者做完习题后,作为参考。
习题解答中的证明方法也不一定是唯一的,读者还可以想出更好的证明方法。
本书可作为通信理论、计算机科学、系统工程等有关专业的本科高年级学生或研究生的近世代数课程的教材,也可供从事工科各专业、应用数学、应用物理等科技人员参考。
我们向所有关心与支持本书的老师与读者表示衷心的感谢。
在编写过程中,得到了北京邮电大学信息工程学院信息与计算中心的全体老师的支持与帮助,在此表示衷心的感谢。
这次再版一定还有不妥之处,殷切希望读者指出。
作者2001年5月 目 录 再版前言……………………………………………………………1第1章集合与映射………………………………………………
1 §1-1集合的概念…………………………………………1§1-2集合的运算集合元素的个数……………………3§1-3关系与等价关系……………………………………12§1-4映射映射的计数代数运算……………………17§1-5同态与同构…………………………………………23习题1………………………………………………………29第2章格………………………………………………………33§2-1偏序集………………………………………………33§2-2格的概念……………………………………………36§2-3有补格与分配格……………………………………46§2-4模格………………………………………………51习题2………………………………………………………60第3章布尔代数与开关函数…………………………………65§3-1布尔代数的概念……………………………………65§3-2布尔代数的原子表示………………………………73§3-3布尔表达式与布尔函数……………………………77§3-4布尔函数的析取范式与极小乘积和………………81§3-5素蕴涵一致法……………………………………85§3-6开关函数……………………………………………90§3-7逻辑门………………………………………………98 —1— 习题3………………………………………………………103第4章半群与群………………………………………………108 §4-1半群与含幺半群…………………………………108§4-2群的定义及其性质………………………………113§4-3子群群同态……………………………………120§4-4循环群……………………………………………126§4-5变换群与置换群…………………………………131习题4………………………………………………………142第5章正规子群与商群………………………………………146§5-1陪集拉格朗日定理……………………………146§5-2正规子群商群…………………………………150§5-3群同态基本定理…………………………………157§5-4群的直积低阶群的构造………………………162§5-5群对集合的作用…………………………………169习题5………………………………………………………177第6章群码…………………………………………………182§6-1数字通信与编码…………………………………182§6-2线性码的生成矩阵与校验矩阵…………………186§6-3群码………………………………………………192习题6………………………………………………………197第7章环………………………………………………………200§7-1环的定义及其性质………………………………200§7-2整环除环布尔环……………………………205§7-3子环环同态……………………………………211§7-4矩阵环与多项式环………………………………214§7-5分式域……………………………………………221习题7………………………………………………………225第8章商环与欧氏环…………………………………………229—2— §8-1商环环同态基本定理…………………………229§8-2素理想与极大理想………………………………235§8-3唯一分解环与主理想环…………………………237§8-4欧氏环……………………………………………243§8-5域上的既约多项式………………………………251§8-6线性同余式与孙子定理…………………………258习题8………………………………………………………269第9章有限域…………………………………………………274§9-1扩域………………………………………………274§9-2极小多项式多项式的分裂域…………………280§9-3域的特征有限域的构造………………………284§9-4本原元与本原多项式……………………………292§9-5有限域上既约多项式的个数……………………296§9-6循环码……………………………………………300§9-7有限域中的计算与伽罗瓦环……………………305习题9………………………………………………………309附录……………………………………………………………312Ⅰ习题解答………………………………………………312Ⅱ所用符号………………………………………………423参考文献…………………………………………………………426 —3— 第1章集合与映射 近世代数的研究对象,主要是代数系统,即具有n元运算的集合.作为预备知识,在这章中,我们讨论数学中最基本的概念———集合与映射. §1-1集合的概念 集合的概念是数学中最基本的概念之
一,是现代数学的重要基础,并且已深入到各种科学与技术的领域中.集合就是一些不同对象的总体.集合也简称集,通常用大写的英文字母
A,B,
C,D,…表示.例如,全体中国人是一个集合;所有整数也是一个集合,简称整数集,记为
Z.以后我们把所有有理数所组成的集合,简称有理数集,记为Q;把所有实数所组成的集合和所有复数所组成的集合分别记为
R,C.组成一个集合的对象称为这个集合的元素,通常用小写的英文字母a,b,c,d,…表示.如果a是集A的元素,称为a属于
A,或A包含a,记为a∈A;如果a不是集合A的 元素,称为a不属于
A,记为a∈|
A.确定一个集合
A,就是要确 定,哪些元素属于
A,哪些元素不属于
A.如果两个集合
A,B包含的元素完全一样,则称A和B相等, 记为A=
B.集合的表示方法主要有两种:列举法和构造法.所谓列举法, 就是列出集合的元素.例如A={a,b,c,d,e}是表示集合A由元素a,b,c,d,e组成.所谓构造法,就是描述出集合中元素适合的 —1— 条件.例如,A=x|x∈Z,x>0表示集合A是由所有正整数组成. 例1-1-1A=x|x∈Z,x2-3x+2=
0,表示A的元素只有两个,即x2-3x+2=0的两个根x=1,x=
2.A= x|x∈Z,x2-3x+2=0=1,
2.设有两个集合
A,B,如果A的每个元素也是B的元素,则称 A为B的子集,或称B包含
A,记为AB.如果A不是B的子集,则记为AB.例如,A={a,b,c}是B={a,b,c,d}的子集,集合A是自己的子集.如果AB并且A≠
B,则称A是B的真子集,记为AB.显然,A=B当且仅当AB并且BA.我们把没有 元素的集合称为空集,记为/○;只有一个元素的集合称为单点集. 例如,A={x|x∈Q,x2=-1}是空集;A={x|x=3}={3}是单点集.我们规定:空集是任何集的子集. 如果一个集合包含了所要讨论的每一个集合,则称这个集合为全集,记为
U.例如,在人口研究中,全集就是包含全世界所有人的集合.在研究平面上的点中,全集就是包含平面上的所有点的集合. 定义1-1-1设A是给定的一个集合,A的所有子集构成的集合,称为A的幂集,记为P(A)或2A,即 P(A)={x|xA}.例1-1-2设A={a,b},则 例1-1-
3 P(A)={/○,{a},{b},A}. 设A={a,b,c},则 P(A)={/○,{a},{b},{c},{a,b},{a,c},{b,c},A}. 从上面例子可以看出:2个元素的集合的幂集有4=22个元素,3个元素的集合的幂集有8=23个元素.可以推出:n个元素的集合的幂集有2n个元素(见习题1-11). —2— §1-2集合的运算集合元素的个数 集合的运算就是以给定集合为对象,按照确定的规则,产生另 外一些集合.例如,A表示“上数学课的学生集合”;B表示“上物理课的学生集合”.如果这两门课安排在同一时间进行期终考试,那 么参加这两门课考试发生冲突的学生集合是什么?
显然,该集合是同时上这两门课的学生的集合.如果在上数学课时和上物理课 时分别宣布同一通知,那么知道这个消息的学生集合是什么?
显然,这个集合是由 上数学课或上物理课的学生组成；＃￣.Ｕ为ｐ了使这些概念一般化,我们定义集合的运算. 定义1-2-1设
A,B是全集U的子集,由A和B的所有共同 元素构成的集,称为A和B的交集,记为A∩
B,即A∩B={x|x∈U,x∈A并且x∈B}. 两个集合的交可用所谓文氏图表示,见图1-2-
1,其中阴影部分就是A∩
B. 例1-2-1设A={a,b,c,
U d},B={a,b,c,e,f},则A∩
B ={a,b,c}.定理1-2-
1 集合的交运
A B 算满足下面性质,这里
A,B,
C 是全集U的子集,/○是空集. 图1-2-
1
(1)A∩A=A;
(3)A∩U=A;
(2)A∩/○=/○;
(4)A∩B=B∩A;
(5)A∩(B∩C)=(A∩B)∩
C.下面证明
(5). 证(A∩B)∩C={x|x∈(A∩B)并且x∈C}={x|(x∈A并 —3— 且x∈B)并且x∈C}={x|x∈A并且(x∈B并且x∈C)}={x|x∈A并且x∈(B∩C)}={x|x∈A∩(B∩C)}=A∩(B∩C). 如果集合
A,B没有共同的元素,则称
A,B不相交,记为A∩ B=/○. 定义1-2-2设
A,B是全集U的子集,所有属于A或属于
B 的元素构成的集,称为A和B的并集,记为A∪
B,即 A∪B={x|x∈U,x∈A或x∈B}. 两个集的并集的文氏图为图1-2-
2. 例1-2-2设A={a,b,c},
B U ={b,c,d,e},则
A B A∪B={a,b,c,d,e}.定理1-2-2集合的并运算满 足下面性质,这里
A,B,C是全集 图1-2-
2 U的子集,/○是空集.
(1)A∪A=A;
(2)A∪U=U;
(3)A∪/○=A;
(4)A∪B=B∪A;
(5)A∪(B∪C)=(A∪B)∪
C. 证这些性质的证明,容易从定义得出. 定理1-2-3集合的交、并运算满足下面性质,这里
A,B,
C 是全集U的子集.
(1)A∩(B∪C)=(A∩B)∪(A∩C);
(2)A∪(B∩C)=(A∪B)∩(A∪C);(分配律)
(3)A∪(A∩B)=A;(吸收律)
(4)A∩(A∪B)=A;
(5)若AC,则A∪(B∩C)=(A∪B)∩
C.(模律)下面证明
(5).证设x∈A∪(B∩C),则x∈A或x∈B∩
C.当x∈A时,x —4— ∈A∪
B.又因为AC,故x∈
C,即x∈(A∪B)∩C;当x∈(B∩C)时,则x∈A∪B并且x∈
C,即x∈(A∪B)∩
C.因此,A∪(B∩C)(A∪B)∩C;反之,设x∈(A∪B)∩
C,则x∈(A∪B)并且x∈
C.若x∈
A,则x∈A∪(B∩C);若x∈
B,则x∈B∩
C,从而x∈A∪(B∩C).于是A∪(B∩C)(A∪B)∩
C.因此,在
A C的条件下,有A∪(B∩C)=(A∪B)∩
C. 集合的交与并的概念还可以推广到全集U的任意多个集合上去. 定义1-2-3设
A,B是全集U的子集,所有属于A而不属于B的一切元素构成的集,称为B关于A的余集或补集,记为A-
B,即 A-B={x|x∈U,x∈A并且x∈|B}. A-B也称为集合A和B的差,文氏图为图1-2-
3.例1-2-3设A表示“上数学课的学生集合”,B表示“这门课考试及格的学生集合”,则A-B表示“上数学课的学生中考试不及格的学生集合”.例1-2-4设A是素数集合,B是奇数集合,则A-B={2}.例1-2-5设A={a,b,c,d},B={a,e},则A-B={b,c,d},B-A={e}.上面例子说明:A-B≠B-
A.定义1-2-4设A是全集U的子集,集合A关于U的余集U-
A,称为集合A的余,记为A′或珔
A,即 A′={x|x∈U并且x∈|A}. 集合A的余的文氏图为图1-2-
4.显然,A-B=A∩B′.定理1-2-4集合的余的运算满足下面性质,这里
A,B是全 集U的子集,/○是空集. —5—
U ＆A＆
B UA 图1-2-
3 图1-2-
4
(1)(A′)′=A;
(2)U′=/○;
(3)/○′=U;
(4)A∪A′=U;
(5)A∩A′=/○;
(6)(A∪B)′=A′∩B′;
(7)(A∩B)′=A′∪B′. 下面证明
(6). 证(A∪B)′={x|x∈(A∪B)′}={x|x∈|A并且x∈|B} ={x|x∈ｉA′并ｉ且ｗ＿＾５Ｍ｝x∈B′}=A′∩B′. 定义1-2-5设
A,B是全集U的子集,A和B的对称差为集 合
S,其元素属于A或属于
B,但不能既属于A又属于
B,记为
A B或A△
B,即 S=AB=(A∪B)-(A∩B).两个集的对称差的文氏图为图1-2-
5.
U A ｑBｑ 例1-2-
6 图1-2-
5 设A表示“主机有故障的计算机集合”,B表示“外 —6— 部设备有故障的计算机集合”,则AB表示“主机有故障与外部设备有故障中,只有一种故障的计算机集合”. 定理1-2-5集合的对称差满足下面性质,这里
A,B,C是全 集U的子集,/○是空集.
(1)AB=BA;
(2)A/○=A;
(3)A
(4)
A A=/○; B=(A∩B′)∪(A′∩B)=(A-B)∪(B-A);
(5)(AB)C=A(BC).下面证明
(4),
(5).证
(4)
A B=(A∪B)-(A∩B)=(A∪B)∩(A∩B)′=(A∪B)∩(A′∪B′)=(A∩A′)∪(A∩B′)∪(B∩A′)∪(B∩B′)=(A∩B′)∪(A′∩B)=(A-B)∪(B-A);
(5)A(BC)=[A∩(BC)′]∪[A′∩(BC)]={A∩[(B∩C′)∪(B′∩C)]′}∪{A′∩[(B∩C′)∪(B′∩C)]}={A∩[(B′∪C)∩(B∪C′)]}∪[(A′∩B∩C′)∪(A′∩B′∩C)]=(A∩B′∩B)∪(A∩B′∩C′)∪(A∩B∩C)∪(A∩C∩C′)∪(A′∩B∩C′)∪(A′∩B′∩C)=(A∩B∩C)∪(A∩B′∩C′)∪(A′∩B∩C′)∪(A′∩B′∩C). 这表示
A,B,C是对称的,于是 —7— A(BC)=(AB)
C.下面讨论集合的元素的个数问题.集合A中不同元素的个数,称为集合A的阶或基,记为#A或|A|.如果#A是有限的,称A为有限集;如果#A是无限的,称A为无限集.如果A和B都是有限集,并且不相交.显然, #(A∪B)=#A+#
B.定理1-2-6设任意两个有限集
A,B,则 #(A∪B)=#A+#B-#(A∩B).证从图1-2-6中看出:A∪B可表为不相交的A和B-A的并.B可表为不相交的B-A和A∩B的并.于是 #(A∪B)=#A+#(B-A),#B=#(B-A)+#(A∩B).由此可得#(A∪B)=#A+#B-#(A∩B).
U A BB-
A 图1-2-
6 例1-2-7假设在12本书的集合中,其中有6本小说.2001年出版的有7本书,其中有3本小说.设A为小说的集合,B为2001年出版的书的集合,即#A=
6,#B=
7,于是A∪B表示或是小说或是2001年出版的书的集合. #(A∪B)=#A+#B-#(A∩B)=6+7-3=10,即有10本书或是小说或是2001年出版的书. —8— 定理1-2-7设任意三个有限集
A,B,
C,则#(A∪B∪C)=#A+#B+#C-#(A∩B)-#(A∩C) -#(B∩C)+#(A∩B∩C).证#(A∪B∪C)=#[(A∪B)∪C] =#(A∪B)+#C-#[(A∪B)∩C]=#A+#B+#C-#(A∩B) -#[(A∩C)∪(B∩C)]=#A+#B+#C-#(A∩B) -#(A∩C)-#(B∩C)+#(A∩B∩C).定理1-2-8设任意n个有限集合A1,A2,…,An,则 #(A1∪A2∪…∪An) n ∑∑=#A1- #(Ai∩Aj) i=
1 1≤i1
∑∑=#Ai-
#(Ai∩Aj)
i=
1 1≤i1
∑+
#(Ai∩Aj∩Ak)
1≤i1
-…(-1)n#(A1∩A2∩…∩An-1).
—9—
#(A1∪A2∪…∪An-1∪An)=#[(A1∪A2∪…∪An-1)∪An]=#(A1∪A2∪…∪An-1)+#An
-#[(A1∪A2∪…∪An-1)∩An],但
(A1∪A2∪…∪An-1)∩An=(A1∩An)∪(A2∩An)∪…∪(An-1∩An),于是
#[(A1∪A2∪…∪An-1)∩An]
=#[(A1∩An)∪(A2∩An)∪…∪(An-1∩An)]
=#(A1∩An)+#(A2∩An)+…+#(An-1∩An)
-#(A1∩A2∩An)-#(A1∩A3∩An)-…
-#(An-2∩An-1∩An)+…+(-1)n#(A1∩A2∩…∩An)
n-
1 ∑∑=#(Ai∩An)- #(Ai∩Aj∩An)+… i=
1 1≤i1
+(-1)n#(A1∩A2∩…∩An).
因此
#(A1∪A2∪…∪An-1∪An)
n
∑∑=#Ai-
#(Ai∩Aj)
i=
1 1≤iA.一般有
—10—
推论1-2-
1 # ( ′ A1 ∩ ′ A2 ∩ … ∩ ′ An) = u- #(A1∪A2∪…∪An) n ∑∑=u- #Ai+ #(Ai∩Aj) i=
1 1≤i1,α2,…,αm为正整数.设1～n的n个正整数中为pi倍数的数构成集Ai,i=1,
2,…,m,则 #Ai=n,i=1,
2,…,m;pi #(Ai∩Aj)=n,i,j=1,
2,…,m,j>i;pipj #(Ai∩Aj∩Ak)=n,i,j,k=1,
2,…,m,k>j>i;pipjpk …… 因此, φ(n) = # ( ′ A1 ∩ ′ A2 ∩ … ∩ ′ Am) m ∑∑=n- #Ai+ #(Ai∩Aj) i=
1 1≤i1
p2
pm
=
pα11
1 pα22 - 1… pαmm
1 ( p1 - 1)(p2 - 1)…(pm - 1) ∏mα-
1 =pii(pi-1). i=
1 例如,求n=20的欧拉函数φ(20).因为n=20=22×
5,于是φ(20)=φ(22×5)=2×(5-1)=
8,即比20小且与20互素的正整数有1,3,7,9,11,13,17,19. §1-3关系与等价关系 定义1-3-1设
A,B是两个非空集,如果有序对的第1个元素是A的元素,第2个元素是B的元素,则所有这样的有序对的集,称为集A和B的笛卡尔积,记为A×
B,即 A×B={(x,y)|x∈A,y∈B}.两个有序对相等(a,b)=(c,d)当且仅当a=c,b=d.例1-3-1设A={a,b},B={1,2,3},求A×
B,B×
A,A×
A.解A×B={(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)};B×A={(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)};A×A={(a,a),(a,b),(b,a),(b,b).—12— 例1-3-2设A=B=
R,则R×R={(x,y)|x,y∈R}, 这就是笛卡尔坐标平面的点集.两个集合的笛卡尔积可以推广到n个集合.设A1,A2,…,An 是任意n个集合,集合{(a1,a2,…,an)|ai∈Ai,i=1,
2,…,n}称为A1,A2,…,An的 笛卡尔积,记为A1×A2×…×An,即A1×A2×…×An={(a1,a2,…,an)|ai∈Ai,i=1,
2,…,n}.A×A记为A2,A×A×A记为A3,n个A的笛卡尔积记为An.定义1-3-2A×B的子集
R,称为
A,B间的一个二元关系, 当(a,b)∈R时,称a与b具有关系
R,记为aRb;当(a,b)∈|
R 时,称a与b不具有关系
R,记为aR′b.对于任意a∈A,b∈
B,(a,b)在R中或不在R中,故aRb或 aR′b二者有
一,且仅有一种情形成立.一个二元关系只是把A中的某些元素与B中的某些元素相关 的直观概念,给以形式化.例如,设A表示4个学生的集合,A={a,b,c,d}.B表示6门课程的集合,B={1,2,3,4,5,6}.A×B给出学生和课程之间所有可能的配对,共有24种配对的方法.设关系 R={(a,1),(b,2),(b,4),(c,2),(c,3),(c,5),(d,3),(d,6)}为学生们所选读的课程.这就是说:学生a选读1课程,学生b选读2,4课程,学生c选读2,3,5课程,学生d选读3,6课程. 例1-3-3在实数集R中,大于关系“>”可记为“>”={(x,y)|x,y∈R,x大于y}. 当集合A=B时,关系R是A×A的子集,这时R称为在A上的二元关系,或简称关系. 一个二元关系,除了用列出的有序对的方式表示之外,还可以用关系表或关系图的形式来表示,也可以用关系矩阵表示.例如, —13— 令关系 A={a,b,c,d},B={1,2,3}, R={(a,1),(b,3),(c,1),(c,3),(d,2)}是A与B的一个二→←＇ 元关系.R可表示为表1-3-
1,这里表的行对应于A中的元素,列对应于B中的元素,方格中的符号“”表示对应行的元素相关于对应列的元素.二元关系R也可以表示为图的形式,如图1-3-
1,其中左边一列的点表示A的元素,右边一列的点表示B的元素.从左边的一个点到右边的一个点,画一条有向线段或有向弧,来表示A中元素相关于B中的对应元素. 表1-3-1 123abcd a
1 b2 c d
3 图1-3-
1 二元关系R还可以用关系矩阵表示.矩阵的行对应于A的元素,矩阵的列对应于B的元素.如果对应行i的元素相关于对应列j的元素,则矩阵的第i行j列为
1,否则为
0.如上例对应的关系矩阵为 100 001 MR= . 101 010定义1-3-3设R是集A上的二元关系,那么
(1)如果对于任何a∈
A,均有aRa,则称R具有反身性;
(2)如果对于任何a,b∈
A,当aRb时,恒有bRa,则称R具—14— 有对称性;
(3)如果对于任何a,b,c∈
A,当aRb并且bRc时,恒有aRc, 则称R具有传递性;
(4)如果对于任何a,b∈
A,当aRb并且bRa时,恒有a=b, 则称R具有反对称性.例1-3-4设非零整数集Z*上的二元关系为R={(a,b)|a,b∈Z*,a|b}, 这里a|b为a整除b.则R具有反身性,传递性.但不具有对称性 和反对称性.例如,2|
4,但4/|2;3|(-3),(-3)|
3,但-3≠
3. 定义1-3-4设R是集A上的二元关系,如果R满足反身性,对称性和传递性,则称R为A上的等价关系,记为～. 如果～是A上的等价关系,对于任意a,b∈
A,若有a～b,则称a与b是等价的.称[a]={x∈A|x～a}为包含a的等价类. 例如,设A是学生集合,R是A上的二元关系,规定:对于所有a,b∈A(记为"a,b∈A),aRb当且仅当a与b同住一宿舍.显然,R是等价关系.又如,集A={1,2,3,4},关系 R={(1,1),(1,4),(4,1),(4,4),(2,2),(2,3),(3,2),(3,3)}也是等价关系. 例1-3-5设R是Z上的二元关系,规定:如果Z中的数a,b用固定正整数n除,余数相等,则(a,b)∈
R,即aRb当且仅当a-b是n的倍数,记为a≡b(modn),证明:R是等价关系,这个等价关系称为模n的剩余关系. 证"a,b∈Z
(1)因为a-a=
0,于是(a,a)∈R;
(2)如果a≡b(modn),即a-b=kn(k∈Z),于是b-a=-kn.所以,b≡a(modn);
(3)如果a≡b(modn),b≡c(modn),即 a-b=k1n,b-c=k2n(k1,k2∈Z) 于是 —15— a-c=a-b+b-c=(k1+k2)n, 即 a≡c(modn). 因此,R是Z上的等价关系. 定理1-3-1设～是集A的等价关系,那么
(1)如果"a,b∈A,a～b,则[a]=[b];
(2)如果"a,b∈A,aｙb,则[a]∩[b]=/○,这里ｙ表示不 等价;
(3)A能写成所有不同等价类的并. 证
(1)如果a～b,"x∈[a],于是x～a,由传递性,x～b, 从而x∈[b],即[a][b].同理可证:[b][a].因此,[a]= [b].
(2)如果aｙb,假定A中存在一个元x∈[a]∩[b],于是x ∈[a],x∈[b],即x～a,x～b,从而a～b,这与假设矛盾.因此, [a]∩[b]=/○.
(3)从
(1)、
(2)知道:两个等价类或是相同或是不相交.由于等价关系～的反身性,"a∈
A,有a∈[a].因此,A是所有不同等价类的并. 从上面定理可看出,等价类可由这个等价类中的任一元素作代表,即等价类与其代表的选择无关. 下面讨论集合A上的等价关系与A的一个划分之间的联系.集合A的一个划分是集合A的非空子集A1,A2,…,Ak的集合{A1,A2,…,Ak},使得这些非空子集Ai的并等于
A,并且对于任意 两个不同的Ai,Aj,它们的交是空集,即A=A1∪A2∪…∪Ak;并 且当i≠j时,Ai∩Aj=/○.Ai就称为划分的块.例如,把一副扑克 52张牌,可按花色划分为4套,也可按数字大小划分为13个等级.我们可以由集合A上的等价关系来确定A的一个划分,使得 在A中任意有关系的元素,放在同一块中,而没有关系的元素,放 —16— 在不同的块中.这样的划分,称为由等价关系导出的划分,而这划分中的块就是等价类.反之,可由集合A的一个划分来确定A上的一个等价关系,使得在划分的同一块中的A的任意两个元素是相关的,而在不同块中的A的任意两个元素是不相关的.例如,A是中国人的集合,R是A上的一个二元关系,使得(a,b)∈R当且仅当a和b的姓相同.显然,R是一个等价关系.由这个等价关系,可以导出A的一个划分,其中等价类是由同姓的人组成.又如,设n是一个固定的正整数,令R是整数集Z上的一个二元关系,R={(a,b)|a,b∈Z,a≡b(modn)}.在例1-3-5中,我们已证明了这个模n剩余关系是等价关系.这个等价关系可将Z划分成n个等价类,这些等价类分别是整数除以n其余数为0的数构成的等价类[0];余数为1的数构成的等价类[1];…;余数为n-1的数构成的等价类[n-1],共有n个等价类,这样的等价类称为模n剩余类. 例1-3-6设R是Z上的模3剩余关系,即R={(a,b)|a,b∈Z,a≡b(mod3)} 确定由Z的元素所产生的剩余类.解模3剩余类是[0]={…,-
6,-3,0,3,
6,…},[1]={…,-
5,-2,1,4,
7,…},[2]={…,-
4,-1,2,5,
8,…}. [0],[1],[2]分别表示0,1,2所在的剩余类,从上面可看出[0]=[3]=[-3]=[6]=[-6]=…, 即0,
3,-3,
6,-6,…所在的剩余类是相同的. §1-4映射映射的计数代数运算 映射是数学的基本概念.在高等数学中,我们讨论的函数y=—17— f(x)是在实数集中进行的,现在我们将把函数的概念推广.定义1-4-1设A和B是两个非空集合,f是A与B的一个 二元关系,如果对于每一个x∈
A,都有唯一的y∈
B,使得(x,y)∈f,则称关系f为A到B的映射(或函数),记为f:AB或 f AB.我们经常用符号y=f(x)来代替(x,y)∈f.如果(x,y)∈f,则称x为自变元,y为在f作用下x的像,x 称为y的原像.A称为映射f的定义域,B称为映射f的定值域.一个映射必须联系两个集合和一个关系.两个映射f:A→
B, g:A1→B1,当且仅当A=A1,B=B1,且对于任何x∈
A,均有f(x)=g(x)时,才认为是相等,记为f=g. 例1-4-1设A=整数集
Z,B=实数集
R,规定f:Z→R为f(x)=x2,"x∈
Z,则f是Z到R的一个映射. 例1-4-2设A=B=正整数集Z+,规定f:Z+→Z+为f(n)=n-
1,"n∈Z+,则f不是Z+到Z+的映射.因为,当n=1时, n-1∈|Z+. 例1-4-3设A={a,b,c,d},B={1,2,3},规定f:A→B为f(a)=1,f(b)=2,f(c)=2,f(d)=
2,则f是A到B的一个映射. 如果A到A的映射f,使f(a)=a,"a∈
A,则称f为A上的恒等映射. 定义1-4-2设f是集A到B的一个映射,如果对于任何b∈
B,均有a∈
A,使f(a)=b,则称f为A到B的一个满射(或映上的). 例1-4-4设A={a,b,c,d},B={1,2,3},规定f:A→B为a→1,b→2,c→2,d→
3,则f是A→B的一个满射. 定义1-4-3设f是集A到B的一个映射,如果a≠b有f(a)≠f(b),"a,b∈
A,则称f为A到B的一个单射(或1—1的). 例1-4-5设A={a,b,c},B={1,2,3,4},规定f:A→B为—18— f(a)=2,f(b)=1,f(c)=
4,则f是A→B的一个单射.如果f是A到B的一个映射,令f(A)={f(x)|x∈A},称 f(A)为映射f的像→←＇ ,通常记为Imf,即Imf=f(A)={f(x)|x∈A}. 因此,A到B的映射f,若Imf=
B,则f是A到B的满射.定义1-4-4设f是集A到B的一个映射,如果f既是满射, 又是单射,则称这个映射为A到B的一个双射(或一一对应).例1-4-6设A=B=实数集
R,规定f:R→R为f(x)=x3, "x∈
R,则f是R到R的一个双射. h=gf 定义1-4-5设集
A,B,
C,映射
A C f:A→B,g:B→
C,由f,g确定的
A 到C的映射h,h(x)=g(f(x)),"x f g ∈
A,称为映射f,g的合成,或复合, 记为h=gf,h可用图1-4-1表示.例1-4-7设A={1,2,3},B= {p,q},C={a,b}.若f:A→B为 B图1-4-
1 f
(1)=p,f
(2)=p,f
(3)=q;g:B→C为g(p)=b,g(q)=b,则 (gf):A→C为(gf)
(1)=b,(gf)
(2)=b,(gf)
(3)=b. 定理1-4-1设映射f:A→B,g:B→C,h:C→
D,则 h(gf)=(hg)f,即映射合成满足结合律. 证按照映射相等的定义,首先必须证明:映射h(gf)与(hg)f的定义域与定值域都相同,这是显然成立的.其次还需证明:对于任何x∈
A,有[h(gf)](x)=[(hg)f](x).这是因为 [h(gf)](x)=h[(gf)(x)]=h[g(f(x))] =(hg)(f(x))=[(hg)f](x), 即 h(gf)=(hg)f. —19— 定理1-4-2设映射f:A→B,g:B→
C,那么
(1)如果f,g都是单射,则gf也是单射;
(2)如果f,g都是满射,则gf也是满射;
(3)如果f,g都是双射,则gf也是双射. 证
(1)要证明gf为单射,由定义必须证明:对于任何x1, x2∈
A,如果x1≠x2,有(gf)(x1)≠(gf)(x2),或证明:如果 (gf)(x1)=(gf)(x2),有x1=x2. 如果(gf)(x1)=(gf)(x2),即g(f(x1))=g(f(x2)),由于 g是单射,于是f(x1)=f(x2),由于f是单射,于是x1=x2.因此, gf是单射.
(2)令z∈
C,由于g是满射,所以存在y∈
B,使g(y)=z.由 于f是满射,所以存在x∈
A,使f(x)=y.因此,(gf)(x)= g(f(x))=g(y)=z.即gf是满射.
(3)由
(1),
(2)可得.定义1-4-6设映射f:A→
B,如果存在映射g:B→
A,使gf =IA,fg=IB,这里IA,IB分别是A和B上的恒等映射,则g称为 f的逆映射.如果映射f的逆映射存在,则称f为可逆映射. 定理1-4-3的,记为f-
1. 映射f:A→
B,如果f的逆映射存在,则是唯
一 证假定f有两个逆映射,g:B→A,h:B→
A,于是gf= IA,fg=IB,hf=IA,fh=IB.因此 h=IAh=(gf)h=g(fh)=gIB=g.定理1-4-4映射f:A→B有逆当且仅当f是双射.证设h:B→A是f的逆映射,如果对于任何x1,x2∈A,f(x1)=f(x2),于是(hf)(x1)=(hf)(x2),从而x1=x2.因此,f为单射.对于任何y∈
B,如果h(y)=x,于是f(x)=f(h(y))=y.因此,f是满射.所以f是双射.—20— 反之,如果f是双射,对于任何y∈
B,有唯一的x∈
A,使f(x)=y.我们定义映射g:B→A为g(y)=x,于是(fg)(y)=f(g(y))=f(x)=y,即fg=IB.对于任何x∈
A,(gf)(x)=g(f(x))=g(y)=x,即gf=IA.因此,g是f的逆映射. 定理1-4-5设有限集合
A,B,且#A=n,#B=m,则
(1)映射f:A→B的个数为mn;
(2)当m≥n时,单射g:A→B的个数为m(m-1)…(m-n +1);
(3)当m=n时,双射h:A→B的个数为m!
.证
(1)由映射的定义,A的每个元素在B中一定存在且唯
一 的像.我们把A中的元素排成1～n.第1个元素在B中的像有m种选择法,第2个元素在B中的像也有m种选择法,……,第n个元素在B中的像同样有m种选择法.因此,f:A→B的个数为mn.
(2)由单射的定义,A的不同元素在B中的像不同.从而,A中第1个元素在B中的像有m种选择法,第2个元素在B中的像 只有m-1种选择法,……,第n个元素在B中的像有m-n+1种选择法.因此,g:A→B的个数为m(m-1)…(m-n+1).
(3)由双射的定义和
(2)得出.定理1-4-6设有限集合
A,B,且#A=n,#B=m,当n≥m时,则满射f:A→B的个数为 mn-m(m-1)n+m(m-2)n-…+(-1)m-1m.
1 2 m-
1 证设A={x1,x2,…,xn},B={y1,y2,…,ym},并设A到
B, 但yi不是A中任何一个元素的像的映射构成的集为Ai,i=
1,
2,…,m,即 Ai={f:A→B|yi∈|Imf}. 由推论1-2-
1,A到B的所有满射个数 —21— s=mn-#(A1∪A2∪…∪Am) m ∑∑=mn- #Ai+ #(Ai∩Aj) i=
1 1≤i1
2
l
而#(A1∩A2∩…∩Am)=
0.而且,我们在B中去掉l个元素有 m种选择法,因此l s=mn- m(m-1)n+
1 m(m-2)n2 -…+(-1)m-1m.m-
1 推论1-4-
1 n!
=nn-n(n-1)n+n(n-2)n-…+(-1)n-1n.
1 2 n-
1 证由定理1-4-6和定理1-4-5的
(3)得出. 定义1-4-7集A到A的映射,称为A的变换;A到A的双 射,称为A的一一变换;A的所有变换构成的集记为AA. 下面讨论代数运算的概念. 定义1-4-8设A是一个非空集合,A×A到A的一个映射f, 称为A的一个代数运算,即对于A中的任意两个元素a,b,通过f 唯一地确定一个c∈
A,使f(a,b)=c,记为ab=c. 如果是A的一个代数运算,也称A对于代数运算是封闭 的.A的代数运算也称为A的结合法. 由于(a,b)和(b,a)一般是A×A中的不同元素,故ab不 —22— 一定等于ba.例如,有理数集中的加法、减法、乘法都是代数运算,而除法不 是代数运算,因为零不能当除数.又如,给定非空集合
A,A的幂集P(A),对于任何x,y∈P(A),x∩y,x∪y和xy都属于P(A), 于是集的交、并与对称差都是P(A)的代数运算.例1-4-8设B={0,1},规定0*0=0,1*0=0,0*1=0,1* 1=
1.显然,*是B的代数运算.B的代数运算也可用运算表来表示,如表1-4-
1.在表中写在垂线左边的是B×B中前面B的元 素,横线上边的是B×B后面B的元素.例1-4-9设A={a,b,c,d},代数运算由表1-4-2给出,这 里dc=a,cd=d,ab=b,等等. 表1-4-
2 表1-4-
1 0 a b c d *
0 1 a a b c d
0 0
0 b b d a c
1 0
1 c c a b d d d c a b 定义
1-4-9设A是一个非空集合,n是自然数,A×A×…×A(n个A的笛卡尔积)到A的映射f,称为A的一个n元运算. 上面所说的代数运算就是二元运算.例1-4-10设Q*为非零有理数集,每个非零有理数的倒数还是有理数.因此,倒数运算是Q*的一元运算. §1-5同态与同构 我们已知道近世代数的主要研究对象是代数系统,即具有一些n元运算的集合.设集合A的二元运算,这个代数系统记为 —23— (
A,).下面讨论与二元运算发生关系的映射.定义1-5-1设(
S,)和(
T,*)是两个代数系统,这里,*分 别是集S和T的二元运算.如果存在S到T的映射f,并且保持运算,即 f(ab)=f(a)*f(b)"a,b∈
S. 则称f是(
S,)到(
T,*)的同态映射,简称f是S到T的同态映射. 例1-5-1设(
Z,+)和(R+,·)这里Z与R+分别为整数集和正实数集,+与·分别为数的加法和乘法.规定f:Z→R+为f(x)=ex,"x∈
Z.显然,f是Z→R+的映射,并且对于任何x,y∈Z,f(x+y)=ex+y=ex·ey=f(x)·f(y).因此,f是Z到R+的同态映射. 例1-5-2设(
Z,+)和(
A,·),这里A={
1,-1},·为数的乘法.规定映射f:Z→A为对于任何x∈
Z, 1,当x为偶数(包括负偶数)时;f(x)=-
1,当x为奇数(包括负奇数)时,证明:f是Z→A的同态映射. 证对于任何x,y∈
Z,
(1)如果x,y都是偶数,则 于是 f(x)=1,f(y)=
1, f(x+y)=1=1·1=f(x)·f(y).
(2)如果x,y都是奇数,则 于是 f(x)=-1,f(y)=-
1, f(x+y)=1=(-1)·(-1)=f(x)·f(y).
(3)如果x是奇数,y是偶数,则 f(x)=-1,f(y)=
1, —24— 于是f(x+y)=-1=(-1)·1=f(x)·f(y). 同理可证:x是偶数,y是奇数时,f(x+y)=f(x)·f(y).因此,f是Z→A的同态映射. 例1-5-3在例1-5-2中,如果规定映射f:Z→A为f(x)=-
1,"x∈
Z,问f是Z到A的同态映射吗?
解"x,y∈Z,f(x)=-1,f(y)=-1,f(x+y)=-1≠f(x)·f(y), 于是f不是Z到A的同态映射.例1-5-4实数集R关于数的乘法·的代数系统(
R,·),规定 映射f:R→R为f(x)=x2,"x∈
R,问f是R→R的同态映射吗?
解对于任何x,y∈R,f(x·y)=(x·y)2=x2·y2=f(x)·f(y). 因此,f是R→R的同态映射.定义1-5-2如果集S到T的同态映射f是S到T的单射,则 称f为S到T的单一同态.定义1-5-3如果集S到T的同态映射f是S到T的满射,则 称f为S到T的满同态.如果集S到T存在满同态,则称S和T是同态的,记为S～
T.定义1-5-4如果集S到T的同态映射f是S到T的双射,则 称f为S到T的同构映射(或简称同构).如果S和T之间存在同构映射,则称S和T是同构的,记为 Sǖ
T.例如,例1-5-1中的f是Z→R+的单一同态;例1-5-2中的f 是Z→A的满同态.例1-5-5(
R,+)和(R+,·),这里·,+分别为数的乘法和加 法.规定映射f:R→R+为f(x)=10x,"x∈
R,问映射f是R→—25— R+的同构映射吗?
解对于任何y∈R+,存在x=lgy使f(x)=y,所以f是
R →R+的满射;"x,y∈
R,如果10x=10y,得x=y,所以f为R→R+的单射.因此,f是R→R+的双射.又由于f(x+y)=10x+y=10x·10y=f(x)·f(y),所以f是R到R+的同构映射,即RǖR+. 定理1-5-1代数系统(
S,)和(
T,*),这里,*分别是集S和T的二元运算,设f是S→T的满同态,则
(1)如果适合结合律,则*也适合结合律;
(2)如果适合交换律,则*也适合交换律.证
(1)设珔a,珋b,珋c为T的任意三个元素,由于f是S→T的满同态,于是存在a,b,c∈
S,使f(a)=珔a,f(b)=珋b,f(c)=珋c,有 f[a(bc)]=f(a)*f(bc)=f(a)*[f(b)*f(c)]=珔a*(珋b*珋c),而 由假设 f[(ab)c]=f(ab)*f(c)=[f(a)*f(b)]*f(c)=(珔a*珋b)*珋c. a(bc)=(ab)c,这样珔a*(珋b*珋c)和(珔a*珋b)*珋c是S中同一元素的像,于是珔a*(珋b*珋c)=(珔a*珋b)*珋c.
(2)设珔a,珋b为T的任意两个元素,存在a,b∈
S,使f(a)=珔a,f(b)=珋b, 因为f(ab)=f(a)*f(b)=珔a*珋b, 而 由假设 f(ba)=f(b)*f(a)=珋b*珔a. —26— ab=ba,于是 珔a*珋b=珋b*珔a.定理1-5-2代数系统(
S,,*)和(
T,,*),这里,*是S的二元运算,,*是T的二元运算,设存在一个S到T的满射f,使得S与T对于,同态,对于*,*同态.如果运算对于*适合左(右)分配律,则运算对于*也适合左(右)分配律.证设珔a,珋b,珋c为T的任意三个元,由于f是S→T的满射,于是存在a,b,c∈
S,使f(a)=珔a,f(b)=珋b,f(c)=珋c,有 f[a(b*c)]=f(a)f(b*c) =f(a)[f(b)*f(c)]=珔a(珋b*珋c), f[(ab)*(ac)]=f(ab)*f(ac) =[f(a)f(b)]*[f(a)f(c)]=(珔a珋b)*(珔a珋c).由假设a(b*c)=(ab)*(ac),可得 珔a(珋b*珋c)=(珔a珋b)*(珔a珋c).另一种分配律证明方法类似.定义1-5-5如果f是(
S,)到(
S,)的同构映射,则称f为S的自同构映射(或自同构).例1-5-6设M(n×n;R)={实数上的全体n阶矩阵},规定映射f:M(n×n;R)→M(n×n;R)为f(A)=AT(AT为A的转置矩阵),"A∈M(n×n;R),问
(1)关于矩阵的加法,f是否是M(n×n;R)的自同构?
(2)关于矩阵的乘法,f是否是M(n×n;R)的自同构?
解
(1)不难证明:f是M(n×n;R)到M(n×n;R)的双射;对于任何
A,B∈M(n×n;R),(A+B)T=AT+BT,即 f(A+B)=f(A)+f(B). —27— 因此,f是M(n×n;R)的自同构.
(2)当n>1时,(AB)T=BTAT≠ATBT,即f(AB)≠f(A)f(B). 因此,f不是M(n×n;R)的自同构. —28— 习题
1 1-1设A={1,2,3},B={2,4,6},求A∪
B,A∩
B,A-
B,B-A.1-2设A={x|x∈
R,|x|≥4},B={x|x∈
R,-5≤x<0},求 A∪
B,A∩
B,A-
B,B-A.1-3设A是B的真子集,即AB,问A∩B=?
A∪B=?
1-4证明:A=B当且仅当A∪B=A∩B.1-5证明:A∪B=AB(A∩B).1-6求下面各题中集合M与N的交与并:
(1)Q=有理数集,N=无理数集;
(2)M={全体实数上的n阶对称矩阵},N={全体实数上 的n阶反对称矩阵}.1-7证明:如果对于三个集
A,B,
C,有A∪B=A∪
C,A∩B= A∩
C,则C=
B. 1-81-91-101-11 1-12 1-13 证明:AB当且仅当A∩B′=/○. 证明:(A∪B′)∩(A′∪B)=(A∩B)∪(A′∩B′).设A={x|x∈Z,x2-3x+2=0},求A的幂集P(A).对n用归纳法证明:如果#A=n(n为有限正整数),则A的幂集P(A)具有2n个元素.求用a,b,c,d,e,f六个字母作不重复,并且不出现ace和df的排列的个数.下面哪些关系是等价关系?
(1)设Z+是正整数集,Z+×Z+上的关系R定义为:(a,b) R(c,d)当且仅当a+d=b+c;
(2)设C是实数集到实数集的所有连续函数的集合,C上 的关系R定义为:f(x)Rg(x)当且仅当f
(3)=g
(3);
(3)设Z+是正整数集,Z+上的关系R为数的小于或等于. —29— 1-141-151-16 1-17 1-181-191-20 1-211-221-231-24 — 证明:实数上n阶矩阵间的合同关系、相似关系都是等价关系.设S=非负实数集,B={0,1},试给出S到B的一个映射.设S=非负实数集,R=实数集,对于任何x∈
S,(1)f1:S→R为f1(x)=lnx;(2)f2:S→R为f2(x)=2x-1; (3)f3:S→R为f3(x)=±x;(4)f4:S→R为f4(x)=tanx.问f1,f2,f3,f4是否是S→R的映射,满射,单射?
设R+=正实数集,R=实数集, f:R+→R为f(x)=lnx,"x∈
S.问f是双射吗?
如果是,求出f的逆映射.对下面Z→Z的映射f,g,h,规定为:对于任何x∈
Z, f:x→3x;g:x→3x+1;h:x→3x+
2,计算fg,gf,gh,hg,fgh.设A是坐标平面上所有点的集合,B是x轴上所有点的集合,对于每一个a∈
A,规定f:A→B为f(a)是a向x轴所作垂线的垂足,问f是否是A→B的映射,单射,满射?
设A=B=Z,m是取定的正整数,对于每一个a∈
A,规定f:A→B为f(a)=r,这里r是a除以m所得的余数,即a=qm+r,0≤r设满射f:A→
A,并且ff=f,证明:f=IA. 设
A,B,C是集E的三个子集,并且A=B∪
C,B∩C=/○, 找出P(A)到P(B)×P(C)的一个双射.试在实闭区间[0,1]与[a,b](a
问下面各集S所规定的法则是否是S的二元运算?
(1)S=
Z,法则:ab=ab;
(2)S={所有负整数},法则:ab=-ab;
(3)S= ab00 a,b∈
Z,法则:矩阵乘法. 设A={a,b,c},对于A最多能规定多少种不同的二元 运算?
设R的二元运算为数的乘法,问下面映射是否是R到R的 同态映射?
(1)f(x)=|x|; 1-291-30 1-311-32 1-33 (2)f(x)=2x; (3)f(x)=-x.设代数系统(
A,),(珔
A,),(珕
A,),这里,,分别是
A,珔A,珕A的代数运算,证明:如果A～珔
A,珔A～珕
A,则A～珕
A.设有理数集
Q,代数运算为数的加法,Q*为非零有理数集,代数运算为数的乘法,证明:(
Q,+)与(Q*,·)不存在同构映射.设(
Q,+),这里+为数的加法,找出Q的一个自同构(除恒等映射外).设(
A,*),这里A={a,b,c},x*y=c,"x,y∈
A,规定f:A→A为f(a)=a,f(b)=c,f(c)=b,问f是A的自同构吗?
设(
A,),(
B,*),这里A={1,2,3},B={4,5,6},与*由题表1-1和1-2给出,规定f:A→B为f
(1)=4,f
(2)=5,f
(3)=
6,问f是同构映射吗?
—31— 题表1-
1 1
2 3
1 3
3 3
2 3
3 3
3 3
3 3 题表1-
2 *
4 5
6 4
6 6
6 5
6 6
6 6
6 6
6 1-34 设A={a,b,c},代数运算.由题表1-3给定. 题表1-
3 a b c a c c c b c c c c c c c 找出所有A的一一变换,对于代数运算来说,这些一一变换是否都是A的自同构?
—32— 第2章格 近世代数研究的主要对象是代数系统,这章将讨论一种类型的代数系统,即格.格不仅在代数本身,而且在开关理论,计算理论和逻辑设计都有应用. §2-1偏序集 定义2-1-1设P是任一集合,P上的一个二元关系记为“≤”,满足:
(1)"a∈P,a≤a(反身性);
(2)"a,b∈P,a≤b并且b≤a则a=b(反对称性);
(3)"a,b,c∈P,a≤b并且b≤c则a≤c(传递性).则称≤是P的一个偏序关系或半序关系,具有偏序关系≤的集合
P,称为偏序集或半序集,记为(
P,≤).例2-1-1在R中,≤表示实数间的小于或等于关系,则≤为偏序关系,(
R,≤)是一个偏序集.例2-1-2设A是任意集合,A的幂集P(A),≤表示P(A)中元素间的包含关系,即"
B,C∈P(A),B≤C表示BC,则是偏序关系,(P(A),)是偏序集.例2-1-3在Z+中,≤表示两个正整数间的整除关系,即a,b∈Z+,a≤b表示a|b,则≤为偏序关系,(Z+,≤)是偏序集.对于有限集
P,偏序关系可以用图形表示,规定图形中线段联结的两个点,具有关系≤.如果a≤b,则a为线段下端的点,b为 —33— ３ ＨＩＷ Ｇ 上端的点.这种图称为偏序集合图. 例2-1-4设P={1,2,3,4,6,8,9,12,18,24},如果偏序关系 ≤为整除关系,那么(
P,≤)的偏序集合图为图2-1-
1. 例2-1-5设A={a,b},A的幂集P(A)={/○,{a},{b},A},如 果偏序关系为包含关系,那么(P(A),)的偏序集合图为图2-1-
2. 24 84 1218 69
2 3
A {a} ￥{b}
1 图2-1-
1 图2-1-
2 定义2-1-2设集P的偏序关系≤.如果≤还具有"x,y∈
P 均有x≤y或y≤x,则称≤是P的一个顺序关
8 系或全序关系,具有顺序关系的集,称为有序集或全序集. 例如,例2-1-1中的(
R,≤)是有序集.例2-1-6设P={1,2,4,8},偏序关系≤为整除关系,则(
P,≤)是有序集,偏序集合图 421图2-1-
3 为图2-1-
3. 一个有限的有序集的偏序集合图是由一条有限链组成,即由 一条通路组成.例如,例2-1-
6. 定义2-1-3设(
P,≤)是偏序集,如果P的元素m,对于任何 x∈
P,有m≤x,则称m为P的最小元;如果P的元素n,对于任 何x∈
P,有x≤n,则称n为P的最大元. 例如,例2-1-4中,P的最小元为
1,没有最大元;例2-1-5中, —34— P(A)的最小元为/○,最大元为
A. 定理2-1-1设(
P,≤)为偏序集,如果P的最小元(最大元)存在,则是唯一的. 证假定x,y都是P的最小元,由于x是P的最小元,于是x≤y.另一方面,y也是最小元,于是y≤x.因此,x=y.同理可证最大元情况. 设(
P,≤)为偏序集,如果T是P的子集,P的元素u称为T的一个上界,假如"x∈
T,有x≤u;P的元素v称为T的一个下界,假如"x∈
T,有v≤x. 定义2-1-4设(
P,≤)是偏序集,如果T是P的子集,T的一个上界u称为最小上界,假如对于T的任意上界x,均有u≤x,记为l.u.b.T;T的一个下界v称为最大下界,假如对于T的任意下界x均有x≤v,记为g.l.b.T. 偏序集P的子集T不一定有最小上界,如果最小上界存在,则是唯一的;如果最大下界存在,也是唯一的. 例2-1-7设集P={2,3,6,12,24,36},偏序关系≤为数的整除关系,则偏序集(
P,≤)的偏序集合图为图2-1-
4.如果取P的子集T={2,3,6},于是l.u.b.T=6,g.l.b.T不存在;如果取P的子集T={2,3},于是l.u.b.T=6,g.l.b.T不存在;如果取P的子集T={6,12},于是l.u.b.T=12,g.l.b.T=
6. 例2-1-8设集A={a,b,c},A的幂集P(A),偏序关系为集合的包含关系,则偏序集(P(A),)的偏序集合图为图2-1-
5. P(A)的最小元为/○,最大元为
A.如果取P(A)的子集T= {{b,c},{b},{c}},则A与{b,c}是T的上界,而l.u.b.T={b, c}.○/是T的下界,也是最大下界.如果取P(A)的子集T={{a},{b}},则l.u.b.T={a,b},g.l.b.T=/○. 定义2-1-5一个偏序集(
P,≤)称为良序集,假如P的任意—35— 一个非空子集
T,在T中都有最小元.
A 24 36 12
6 {a,b}{a} {a,c}{b} {b,c}{c}
2 3 图2-1-
4 图2-1-
5 例2-1-9设集Z+为正整数集,偏序关系≤为数的小于或等于关系,则(Z+,≤)为良序集. 由良序集的定义可知,一个良序集(
P,≤)一定是有序集,因为任取x,y∈
P,则{x,y}作成P的子集T有最小元.若x为最小元,则有x≤y;若y为最小元,则y≤x.总之,P中任意两个元都是可比较的,即P是有序集. §2-2格的概念 一个偏序集的子集不一定有最大下界或最小上界,但是有些偏序集,它们的任意两个元素组成的子集均有最小上界和最大下界.这是一类特殊的偏序集. 定义2-2-1设(
L,≤)是一个偏序集,如果L中任意两个元素在L中均有最小上界与最大下界,则称L关于偏序关系≤作成一个格. 例2-2-1设L为实数集
R,偏序关系为数的小于或等于关系≤,则(
R,≤)是格.因为R中任意两个数x,y的最小上界 —36— l.u.b.{x,y}=max{x,y},最大下界g.1.b.{x,y}=min{x,y}. 例2-2-2设B={0,1},在图2-2-1中给出了格(
B,≤1), ＜ ， ） (B2,≤2)和(B3,≤3)的偏序集合图.一般说,(Bn,≤ōn)的偏序 集合图是一个n维立方体.(Bn,≤n)的每一个元素可写成(a1, a2,…,an),这里ai是0或
1,对于任何a,b∈Bn,规定偏序关系 ≤n为(a1-a2,…,an)≤n(b1,b2,…,bn)当且仅当ai≤bi(i=
1,
2,…,n),这里≤为对{0,1}的小于或等于关系.显然(Bn,≤n)是 格,称为0和1的n重序元格. 1(1,1) (1,1,0) (1,1,1) (0,1,1) (1,0,1) (1,0) (0,1) (1,0,0)(0,1,0) (0,0,1)
0 (0,0) (a) (b) (0,0,0)(c) 图2-2-
1 例2-2-3设A是任意集,A的幂集P(A),偏序关系为集合 的包含关系,则(P(A),)是格.因 110 为对于任何
S,T∈P(A),l.u.b.{
S, T}=S∪T,g.l.b.{
S,T}=S∩
T. 10 例2-2-4110的正整数因子集 5522 L={1,2,5,10,11,22,55,110},偏序关系≤为整除关系,即"a,b∈L,a2 511 ≤b当且仅当a|b.从(
L,≤)的偏序集合图(见图2-2-2),可看出L中任意 1图2-2-
2 —37— 两个数都有最小上界和最大下界.因此,(
L,≤)是格.在格(
L,≤)中,任意两个元素a,b,用a∨b表示a,b的最小 上界,a∧b表示a,b的最大下界,即a∨b=l.u.b.{a,b},a∧b=g.l.b.{a,b}.因为由a,b可唯一确定a∨b∈L,a∧b∈
L.因此,∨,∧可看作格L的两个二元运算. 定理2-2-1设(
L,≤)是格,对于任何a,b∈
L,满足:(1)a≤a∨b,a∧b≤a;(2)a≤b当且仅当a∨b=b;(3)a≤b当且仅当a∧b=a.证
(1)从∧,∨的定义立即可得;
(2)如果a∨b=b,于是b=l.u.b.{a,b}.因此,a≤b;反之,如果a≤b,又有b≤b,于是a∨b≤b.由
(1),a∨b≥b.因此,a∨b=b;
(3)与
(2)的证明方法相同.定理2-2-2设(
L,≤)是一个格,对于任何a,b,c∈
L,满足:(L1)a∧a=a,a∨a=a(幂等律);(L2)a∧b=b∧a,a∨b=b∨a(交换律);(L3)(a∧b)∧c=a∧(b∧c)(结合律); (a∨b)∨c=a∨(b∨c)(L4)a∧(a∨b)=a,a∨(a∧b)=a(吸收律).证(L1)从∧与∨的定义立即可得.(L2)因为偏序集的任意两个元素的最大下界和最小上界与元素的顺序无关,即 g.1.b.{a,b}=g.1.b.{b,a},于是(L2)成立.1.u.b.{a,b}=1.u.b.{b,a}, (L3)由定理2-2-1的
(1), —38— (a∧b)∧c≤a∧b≤a,(a∧b)∧c≤(a∧b)≤b, 故有 (a∧b)∧c≤c,(a∧b)∧c≤b∧c, 从而同样地,有因此, (a∧b)∧c≤a∧(b∧c).a∧(b∧c)≤(a∧b)∧c.(a∧b)∧c=a∧(b∧c). 同理可证:(a∨b)∨c=a∨(b∨c).(L4)由定理2-2-1,a≤a∨b,a≤a,于是 又有 a≤a∧(a∨b),a∧(a∨b)≤a 因此,同理可证: a∧(a∨b)=a.a∨(a∧b)=a. 定理2-2-2的逆也成立,先证明引理.引理2-2-1在一个集L中定义两个二元运算∧与∨,使满足(L1)～(L4),则a∨b=a当且仅当a∧b=b. 证设a∨b=a,于是a∧b=(a∨b)∧b=b∧(b∨a)=b; 反之,设a∧b=b,于是a∨b=a∨(a∧b)=a. 定理2-2-3在一个集L上定义两个二元运算∧与∨,使满足(L1)～(L4),则(
L,∧,∨)是一个格. 证我们定义L上的关系≤为a≤b当且仅当a∨b=b, "a,b∈
L.首先证明(
L,≤)是偏序集.由(L1),a∨a=a,于是a≤a,即≤满足反身性;如果a≤b,并且b≤a,于是a∨b=b,并 且b∨a=a,由(L2),a∨b=b∨a,于是a=b,即≤满足反对称性;如果a≤b,并且b≤c(c也是L的任意元),于是a∨b=b,并且b∨c=c,由(L3),a∨c=a∨(b∨c)=(a∨b)∨c=b∨c= —39— c,从而a≤c,即≤满足传递传.因此,(
L,≤)是偏序集.下面证明:L中任意两个元均有最小上界和最大下界.由 (L3)与(L1),a∨(a∨b)=(a∨a)∨b=a∨b,于是a≤a∨b,同 理可证,b≤a∨b.因此,a∨b是{a,b}的上界,令u是{a,b}的任何上界,a≤u并且b≤u,于是a∨u=u并且b∨u=u.由 (L3),(a∨b)∨u=a∨(b∨u)=a∨u=u.因此,a∨b≤u,从而a∨b是{a,b}的最小上界.由(L4)的a∨(a∧b)=a,得a∧b≤ a.由(L4)的b∨(b∧a)=b,得b∧a≤b.由(L2),a∧b≤b,从而 a∧b是{a,b}的下界.令v是{a,b}的任何下界,v≤a并且v≤b,于是v∧(a∧b)=(v∧a)∧b=v∧b=v.由引理2-2-1,v∨ (a∧b)=a∧b,即v≤a∧b.因此,a∧b是{a,b}的最大下界.由定理2-2-2和定理2-2-
3,可得与定义2-2-1等价的另一个 格的定义. 定义2-2-2集L具有两个满足(L1)～(L4)的二元运算∧,∨,则称(
L,∧,∨)是一个格,∧,∨分别称为积(或交)与和 (或并).例2-2-5在Z+中,对于任何a,b,c∈Z+,规定a∧b=GCD (a,b),即a,b的最大公约数.a∨b=LCM(a,b),即a,b的最小 公倍数.由于两个任意正整数a,b都有唯一的最大公约数与最小公倍数,故∧,∨是Z+的两个二元运算. 由于 GCD(a,a)=a,LCM(a,a)=a, 于是(L1)成立; 由于 GCD(a,b)=GCD(b,a), LCM(a,b)=LCM(b,a), 于是(L2)成立; 由于 GCD[GCD(a,b),c]=GCD[a,GCD(b,c)], LCM[LCM(a,b),c]=LCM[a,LCM(b,c)],于是(L3)成立; —40— 由于a|LCM(a,b),故GCD[a,LCM(a,b)]=a, 由于GCD(a,b)|a,故 LCM[a,GCD(a,b)]=a,于是(L4)成立.因此,(Z+,GCD,LCM)是一个格. 例2-2-6设A是任意集,A的幂集P(A),规定∧,∨分别为集的交∩和并∪.由于二元运算∩,∪满足(L1)～(L4),于是(P(A),∩,∪)是格. 例2-2-7在例2-2-2中,我们知道Bn={(a1,a2,…,an)|ai=0或1},对于任何(a1,a2,…,an),(b1,b2,…,bn)∈Bn,规定∧,∨分别为(a1,a2,…,an)∧(b1,b2,…,bn)=(c1,c2,…,),这里ci为ai,bi较小的一个.(a1,a2,…,an)∨(b1,b2,…,bn)=(d1,d2,…,dn),这里di为ai,bi较大的一个.显然,二元运算∨,∧满足(L1)～(L4),于是(Bn,∧,∨)是格. 例2-2-8设V为数域P上的线性空间,L(V)表示V的所有子空间构成的集合,因为"T1,T2∈L(V),T1∩T2与T1+T2={t1+t2|t1∈T1,t2∈T2}仍是V的子空间,所以T1∩T2,T1+T2∈ L(V).我们规定:∧与∨分别为T1∧T2=T1∩T2,T1∨T2=T1+T2,由于二元运算∧,∨满足(L1)～(L4),于是(L(V),∧,∨)是格,称为子空间格. 定理2-2-4设(
L,≤)是一个格,对于任何a,b,c∈
L,如果b≤c,则a∧b≤a∧c,a∨b≤a∨c. 证(a∧b)∧(a∧c)=(a∧a)∧(b∧c)=a∧(b∧c)=a∧b,于是a∧b≤a∧c. 同理可证:a∨b≤a∨c.定理2-2-5设(
L,≤)是一个格,对于任何a,b,c,d∈
L,
(1)如果a≤b,c≤d,则a∨c≤b∨d,a∧c≤b∧d; —41—
(2)如果a≤b≤c,并且d∧c=a,则d∧b=a;
(3)如果a≥b≥c,并且d∨c=a,则d∨b=a.证
(1)因为b≤b∨d,d≤b∨d,由传递性,a≤b∨d,c≤b∨d,即b∨d是a和c的一个上界,但a∨c是a和c的最小上界.因此,a∨c≤b∨d.同理可证:a∧c≤b∧d.
(2)因为b≤c,即b∧c=b,于是d∧b=d∧(b∧c)=d∧(c∧b)=(d∧c)∧b=a∧b=a.
(3)与
(2)的证明方法相同.定理2-2-6设(
L,≤)是一个格,a,b,c∈
L,证明:如果c≤a,则a∧(b∨c)≥c∨(a∧b).证因为c≤a,a∧b≤a,所以c∨(a∧b)≤a.又由c≤c∨b,a∧b≤b≤c∨b,可得c∨(a∧b)≤c∨b.因此, c∨(a∧b)≤a∧(c∨b).设N是对任何偏序集为真的一个命题,N′是把N中所有≤与≥对换,得到的对偶命题,可以得出:N′对于任何偏序集也是真的,这称为对偶原理.在格(
L,≤)中将偏序关系反转后,得到另一个格(
L,≤′),这时(
L,≤)中的a∧b,a∨b恰好是(
L,≤′)中的a∨b,a∧b.如定理2-2-2中的(L1)～(L4),每一条都包含互为对偶的两个命题.我们只要证明一个命题,利用对偶原理,立即可得其对偶命题.对偶概念在电信中也会经常遇到,如电压与电流,电阻与电导,电感与电容等概念分别都是对偶概念.上面我们把格定义为代数系统,这样自然可以引入子格的概念.定义2-2-3设(
L,∧,∨)是一个格,L的非空子集
T,如果T关于∧,∨封闭,即"a,b∈
T,有a∧b∈T,a∨b∈
T,则称(
T,∧,∨)是(
L,∧,∨)的子格.例2-2-9设Z+为正整数集,对于任何a,b∈Z+,规定a∧b=GCD(a,b),a∨b=LCM(a,b).由例2-2-
5,(Z+,∧,∨)是格,—42— 令Z+的子集T为偶数集.由于两个偶数的最大公约数与最小公倍数还是偶数,于是T关于∧,∨是封闭的,即(
T,∧,∨)是(Z+,∧,∨)的子格. 例2-2-10如图2-2-3表示的格(
L,∧,∨),L={a0,a1,a2, a3,a4,a5,a6,a7},设L的子集S1={a1,a3,a5,a7};S2={a0,a1, a3,a7};S3={a1,a3,a6,a7},不难 a7 看出:关于∧,∨下S1是封闭的,故(S1,∧,∨)是(
L,∧,∨)的子a1 a3a2 格;子集S2中a1∧a3=a5∈|S2, 故(S2,∧,∨)不是(
L,∧,∨)的子 a4 a5 a6 格,但是它本身构成格;子集S3不但不能构成子格,而且它本身也不构成格. a0图2-2-
3 由子格的定义,不难证明:子格本身也构成格,但反之不一定成立. 注设一个格的子集构成格,但还不一定是子格.定义2-2-4设(
L,∧,∨)和(
S,*,)是两个格,给定(L×
S,,+),这里和+分别是L×S的二元运算,对于任何(a1,b1,),(a2,b2)∈L×
S,有(a1,b1)(a2,b2)=(a1∧a2,b1*b2), (a1,b1)+(a2,b2)=(a1∨a2,b1b2),则称代数系统(L×
S,, +)为格(
L,∧,∨)和(
S,*,)的直积.不难证明:两个格的直积也是一个格.例2-2-11设两个格A={1,2,4,8},B={1,2,3,6},两者偏序关 系均为整除关系.A,B的直积的偏序集合图,如图2-2-4所示.下面讨论两个格之间的关系.定义2-2-5设(
L,∧,∨)与(
S,,+)是两个格,如果存在L—43— 8 42 2
1 (a) (8,6)
6 (8,2)(4,6) (4,2)
3 (2,6) (2,2) (1,6) (1,2)
1 (8,3) (8,1)(4,3) (4,1)(2,3) (2,1)(1,3) (1,1) (b) (c) 图2-2-
4 到S的映射f,使得对于任何a,b∈
L,有f(a∧b)=f(a)f(b),f(a∨b)=f(a)+f(b), 则称f是L到S的同态映射.当L到S的同态映射f是单射时,则称f是L到S的单一同 态;当f是满射时,则称f是L到S的满同态;当f是双射时,则称f是L到S的同构映射(简称同构).如果格L和S之间存在同构映射则称L和S同构,记为Lǖ
S.同构格具有相同的特性.例如,它们的偏序集合图除了元素的符号外是相同的. 格(
L,∧,∨)到(
L,∧,∨)的同态映射与同构映射分别称为自同态映射与自同构映射. 例2-2-12设A={a,b},A的幂集P(A)={/○,{a},{b}, A},两个二元运算分别为集合的交∩和并∪.(P(A),∩,∪)和例 2-2-7中的(B2,∧,∨)同构,因为规定f:P(A)→B2为f(/○)= (0,0),f({a})=(1,0),f({b})=(0,1),f(A)=(1,1).不难证明:f是P(A)到B2的同构映射,即P(A)ǖB2.(
P,∩,∪)和(B2,∧,∨)的偏序集合图在图2-2-5表示. —44—
A (1,1) {a} {b} (1,0) (0,1) (0,0) 图2-2-
5 定理2-2-7设f是格(
L,∧,∨)到(
S,,+)的同态映射,则 f是偏序集L到S的保序映射,即对于任何x,y∈
L,当x≤y时, 在S中也有f(x)≤′f(b),这里≤与≤′分别是L和S的偏序关系. 证当x≤y时,有x∧y=x,于是f(x∧y)=f(x).由于f 是L→S的同态映射,从而f(x∧y)=f(x)f(y).因此,f(x) f(y)=f(x),于是f(x)≤′f(y). 定理2-2-8设f是格L到S的双射,则f是L到S的同构映 射的充分必要条件是:对于任何a,b∈L,a≤b当且仅当f(a)≤ f(b)(这里把L与S的偏序关系都记为≤). 证设f是L到S的同构映射,对于任何a,b∈L,a≤b,由 定理2-2-7,f(a)≤f(b);反之,设f(a)≤f(b),于是 f(a)∧f(b)=f(a∧b)=f(a), 由于f是双射,于是a∧b=a,即a≤b(这里把L与S的积的符 号都记为∧). 设a≤b当且仅当f(a)≤f(b),令a∧b=c,于是 c≤a,c≤b. 因此 f(a∧b)=f(c),f(c)≤f(a),f(c)≤f(b), 得 f(c)≤f(a)∧f(b). 令f(a)∧f(b)=f(d).于是f(c)≤f(d),而 —45— f(d)≤f(a),f(d)≤f(b), 从而 d≤a,d≤b, 于是 d≤a∧b=c, 得f(d)≤f(c),故f(d)=f(c).因此, f(a∧b)=f(a)∧f(b). 同理可证:f(a∨b)=f(a)∨f(b). §2-3有补格与分配格 下面讨论具有附加条件的某些格.在一个格中,任意两个元素都有最小上界和最大下界.由数学归纳法不难证明:格中的每一个有限子集也都有一个最小上界和最大下界.但是对于格的无限子集来说,就不一定有最小上界和最大下界.例如,(Z+,≤),这里≤为数的小于或等于关系,那么(Z+,≤)是格,令T是偶数集,T是Z+的子集,但T没有最小上界.定义2-3-1格L称为完全格,假如L的任意非空子集都有最大下界和最小上界. 例2-3-1设集A的幂集P(A),为集合的包含关系, (P(A),)是格.设T={A1,A2,…}为P(A)的子集,则T的最大下界为A1∩A2∩…,最小上界为A1∪A2∪…. 显然,每一个有限格都是完全格.定义2-3-2设(
L,∧,∨)是一个格,如果L中存在元素
0,对于任何x∈L均有x∨0=x,则称0是L的零元或泛下界;如果在L中,存在元素
1,对于任何x∈L均有x∧1=x,则称1是L的单位元或泛上界.显然,格的零元和单位元如果存在时,都是唯一的. 例2-3-2设A={a,b,c},(P(A),),这里为集的包含 关系,则P(A)的零元为/○,单位元为
A.见图2-3-
1. —46— 例2-3-3在例2-2-5中, A=
1 Z+的零元是
1,没有单位元. 例2-3-4整数集关于数的小于或等于关系≤构成的格,既没有零元也没有单位元. 定义2-3-3如果一个格 {a,b}{a} {a,c} {b} {b,c}{c} (
L,∧,∨),具有零元和单位元,则称此格为有界格,有时记为(
L,∧,∨,0,1). =0图2-3-
1 由格的零元和单位元的定义可知,含有零元和单位元的格的 偏序集合图中,在最上面总有标记为1的单位元的单个结点,在最 下面总有标记为0的零元的单个结点.从任何其他结点出发,沿着 一条递升路径,都能达到
1,沿着一条递降路径都能达到
0. 定理2-3-1设(
L,∧,∨,0,1)是有界格,则对于任何x∈
L, 有x∨1=1,x∧0=
0. 证由于1≤a∨
1,但1为单位元,故有a∨1≤
1.因此,a∨
1 =1;由于x∧0≤
0,但0是零元,故有0≤x∧
0.因此,x∧0=
0. 定义2-3-4设(
L,∧,∨,0,1)是有界格,如果对于任何a,b ∈
L,具有a∧b=0,a∨b=
1,则称元素b是a的补元或补,记 为a′. 不难看出,补元是相互的,如果a是b的补元,则b也是a的 补元. 格L中的一个元素可能没有补元,也可能有多个补元.但
1 是0的唯一补元,0是1的唯一补元. 例2-3-5如图2-3-2所表示的格,a是e的补元,d也是e的 补元,b没有补元. 定义2-3-5设(
L,∧,∨,0,1)是一个有界格,如果L中每
一 个元素都至少有一个补元,则称(
L,∧,∨,0,1)是一个有补格. —47— 例2-3-6如图2-3-3所表示的格,这里a2的补是a1,a3的补也是a1,于是这个格是有补格.
1 1 d e b a2 a c a1 a3
0 0 图2-3-
2 图2-3-
3 例2-3-7在例2-2-7中的n重序元格(Bn,∧,∨)是一个有补格.它的零元是(0,
0,…,0),单位元是(1,
1,…,1).Bn的任意元素(a1,a2,…,an)的补元为(a′1,a2′,…,a′n),这里当ai为0时,a′i为1;ai为1时,a′i为
0. 例2-3-8设A={a,b,c},A的幂集P(A),∨和∧分别为集的并和交,则(P(A),∩,∪)是有补格,从图2-3-1可看出{a}与{b,c}互补,{b}与{a,c}互补,{c}与{a,b}互补. 定义2-3-6设(
L,∧,∨)是一个格,如果对于任何a,b,c∈
L,有 (L5)a∧(b∨c)=(a∧b)∨(a∧c),a∨(b∧c)=(a∨b)∧(a∨c), 则称(
L,∧,∨)是一个分配格.例2-3-9在例2-3-8中的(P(A),∩,∪)是分配格.例2-3-10问图2-3-4表示的格是否是分配格?
解因为b∧(c∨d)=b∧1=b, 而 —48— (b∧c)∨(b∧d)=0∨0=
0.
1 因此, b∧(c∨d)≠(b∧c)∨(b∧d), b 所以这个格不是分配格. c d 例2-3-11问图2-3-3表示的格 是否是分配格?
解因为a2∧(a1∨a3)=a2∧
1 =a2,而 0图2-3-
4 (a2∧a1)∨(a2∧a3)=0∨a3=a3. 因此, a2∧(a1∨a3)≠(a2∧a1)∨(a2∧a3), 所以这个格不是分配格. 定理2-3-2在定义2-3-6中,格的两个分配律,如果一个成 立,则另一个也成立. 证设对于任何a,b,c∈
L,若 a∧(b∨c)=(a∧b)∨(a∧c), 于是 (a∨b)∧(a∨c) =[(a∨b)∧a]∨[(a∨b)∧c] =a∨[(a∨b)∧c]=a∨[(a∧c)∨(b∧c)] =[a∨(a∧c)]∨(b∧c)=a∨(b∧c). 反之,同理可证. 定理2-3-3任何有序集(
L,≤)都是分配格. 证
(1)证明:(
L,≤)是格. 因为(
L,≤)是有序集,"a,b∈
L,有a≥b或b≤a.当a≥b时,a,b的最小上界为a,最大下界为b;当b≥a时,a,b的最小上界为b,最大下界为a.因此,(
L,≤)是格.
(2)证明:(
L,≤)是分配格,即证明;"a,b,c∈
L,有 —49— a∧(b∨c)=(a∧b)∨(a∧c).关于a,b,c可分成两种情况讨论:(ⅰ)a≥b,a≥c;(ⅱ)a≤b 或a≤c. 在(ⅰ)的情况下,有a∧(b∨c)=b∨c,而(a∧b)∨(a∧c)=b∨c, 于是 a∧(b∨c)=(a∧b)∨(a∧c); 在(ⅱ)的情况下,有a∧(b∨c)=a,而(a∧b)∨(a∧c)=a, 于是 a∧(b∨c)=(a∧b)∨(a∧c). 因此,在两种情况下,分配律都成立. 例2-3-12设P={1,2,4,8},偏序关系≤为整除关系,问(
P,≤)是分配格吗?
解由例2-1-
6,(P,≤)是有序集,于是(
P,≤)是分配格. 定理2-3-4一的. 在分配格中,如果一个元素有补,则它是唯 证假定元素a有两个补元b,c,即 于是 a∧b=0,a∨b=1,a∧c=0,a∨c=
1, b=b∧1=b∧(a∨c)=(b∧a)∨(b∧c) =0∨(b∧c)=(a∧c)∨(b∧c)=(a∨b)∧c=1∧c=c. 利用定理2-3-4可以比较方便地判断一个格不是分配格.例 如,图2-3-4表示的格中,因为b的补元有c和d,所以这个格不是 分配格.定理2-3-
5 设(
L,∧,∨)是分配格,对于任何a,x,y∈
L, 如果a∧x=a∧y,并且a∨x=a∨y,则x=y. 证x=x∨(x∧a)=x∨(y∧a)=(x∨y)∧(x∨a)=(x∨y)∧(y∨a)=(y∨x)∧(y∨a) =y∨(x∧a)=y∨(y∧a)=y. —50— 利用定理2-3-5也可以判断一个格不是分配格.例如,图2-3-3表示的格中,a1∧a2=a1∧a3=0,a1∨a2=a1∨a3=
1,但a2≠a3,所以这个格不是分配格. 定理2-3-6在有单位元和零元的分配格中,所有有补元所构成的集为一个子格. 证设(
L,∧,∨)是有单位元和零元的分配格,并设A为所有有补元所组成的集.我们证明:A关于∧,∨是封闭的.设a,a′与b,b′是L中的两对互补元,下面证明:a∧b,a′∨b′与a∨b,a′∧b′是L中的两对互补元. (a∧b)∧(a′∨b′)=[(a∧b)∧a′]∨[(a∧b)∧b′]=[(a∧a′)∧b]∨[(b∧b′)∧a]=(0∧b)∨(0∧a)=0; (a∧b)∨(a′∨b′)=[a∨(a′∨b′)]∧[b∨(a′∨b′)
全书比较注重应用,条理清晰,论证详细,例题较多,每章末均附有习题。
为了便于自学与参考,在本书的最后附有习题解答。
本书可作为通信理论、计算机科学、系统工程等有关专业的近世代数课程的教材,也可供从事工科有关各专业以及应用数学、应用物理等科技人员参考。
图书在版编目(CIP)数据 近世代数及其应用/阮传概,孙伟编著.—2版.北京:北京邮电大学出版社,2001.8 ISBN7-5635-0533-4Ⅰ.近...Ⅱ.①阮...②孙...Ⅲ.抽象代数Ⅳ.O153中国版本图书馆CIP数据核字(2001)第045092号 书 名:近世代数及其应用 编 著:阮传概孙伟 责任编辑:徐夙琨 出版者:北京邮电大学出版社(北京市海淀区西土城路10号) 邮编:100876电话:6228218562283578 网址: 经 销:各地新华书店 印 刷:北京源海印刷厂 印 数:6001—9000 开 本:850mm×1168mm1/32印张:13.625字数:351千字 版 次:2001年9月第1版2005年2月第3次印刷 ISBN:7-5635-0533-4/O·30 定价:25.00元 再版前言 近世代数的内容,不但在数学的各分支有很多应用,而且随着科学技术的发展,它在通信理论、计算机科学、系统工程等许多领域中也有广泛的应用。
本书是为上述各专业的工科学生编写的,所以比较注重应用,例题较多,出版后受到读者的欢迎。
这次再版时,根据读者的意见与建议,做了修改与补充。
为了便于自学,增加了习题解答,可供读者做完习题后,作为参考。
习题解答中的证明方法也不一定是唯一的,读者还可以想出更好的证明方法。
本书可作为通信理论、计算机科学、系统工程等有关专业的本科高年级学生或研究生的近世代数课程的教材,也可供从事工科各专业、应用数学、应用物理等科技人员参考。
我们向所有关心与支持本书的老师与读者表示衷心的感谢。
在编写过程中,得到了北京邮电大学信息工程学院信息与计算中心的全体老师的支持与帮助,在此表示衷心的感谢。
这次再版一定还有不妥之处,殷切希望读者指出。
作者2001年5月 目 录 再版前言……………………………………………………………1第1章集合与映射………………………………………………
1 §1-1集合的概念…………………………………………1§1-2集合的运算集合元素的个数……………………3§1-3关系与等价关系……………………………………12§1-4映射映射的计数代数运算……………………17§1-5同态与同构…………………………………………23习题1………………………………………………………29第2章格………………………………………………………33§2-1偏序集………………………………………………33§2-2格的概念……………………………………………36§2-3有补格与分配格……………………………………46§2-4模格………………………………………………51习题2………………………………………………………60第3章布尔代数与开关函数…………………………………65§3-1布尔代数的概念……………………………………65§3-2布尔代数的原子表示………………………………73§3-3布尔表达式与布尔函数……………………………77§3-4布尔函数的析取范式与极小乘积和………………81§3-5素蕴涵一致法……………………………………85§3-6开关函数……………………………………………90§3-7逻辑门………………………………………………98 —1— 习题3………………………………………………………103第4章半群与群………………………………………………108 §4-1半群与含幺半群…………………………………108§4-2群的定义及其性质………………………………113§4-3子群群同态……………………………………120§4-4循环群……………………………………………126§4-5变换群与置换群…………………………………131习题4………………………………………………………142第5章正规子群与商群………………………………………146§5-1陪集拉格朗日定理……………………………146§5-2正规子群商群…………………………………150§5-3群同态基本定理…………………………………157§5-4群的直积低阶群的构造………………………162§5-5群对集合的作用…………………………………169习题5………………………………………………………177第6章群码…………………………………………………182§6-1数字通信与编码…………………………………182§6-2线性码的生成矩阵与校验矩阵…………………186§6-3群码………………………………………………192习题6………………………………………………………197第7章环………………………………………………………200§7-1环的定义及其性质………………………………200§7-2整环除环布尔环……………………………205§7-3子环环同态……………………………………211§7-4矩阵环与多项式环………………………………214§7-5分式域……………………………………………221习题7………………………………………………………225第8章商环与欧氏环…………………………………………229—2— §8-1商环环同态基本定理…………………………229§8-2素理想与极大理想………………………………235§8-3唯一分解环与主理想环…………………………237§8-4欧氏环……………………………………………243§8-5域上的既约多项式………………………………251§8-6线性同余式与孙子定理…………………………258习题8………………………………………………………269第9章有限域…………………………………………………274§9-1扩域………………………………………………274§9-2极小多项式多项式的分裂域…………………280§9-3域的特征有限域的构造………………………284§9-4本原元与本原多项式……………………………292§9-5有限域上既约多项式的个数……………………296§9-6循环码……………………………………………300§9-7有限域中的计算与伽罗瓦环……………………305习题9………………………………………………………309附录……………………………………………………………312Ⅰ习题解答………………………………………………312Ⅱ所用符号………………………………………………423参考文献…………………………………………………………426 —3— 第1章集合与映射 近世代数的研究对象,主要是代数系统,即具有n元运算的集合.作为预备知识,在这章中,我们讨论数学中最基本的概念———集合与映射. §1-1集合的概念 集合的概念是数学中最基本的概念之
一,是现代数学的重要基础,并且已深入到各种科学与技术的领域中.集合就是一些不同对象的总体.集合也简称集,通常用大写的英文字母
A,B,
C,D,…表示.例如,全体中国人是一个集合;所有整数也是一个集合,简称整数集,记为
Z.以后我们把所有有理数所组成的集合,简称有理数集,记为Q;把所有实数所组成的集合和所有复数所组成的集合分别记为
R,C.组成一个集合的对象称为这个集合的元素,通常用小写的英文字母a,b,c,d,…表示.如果a是集A的元素,称为a属于
A,或A包含a,记为a∈A;如果a不是集合A的 元素,称为a不属于
A,记为a∈|
A.确定一个集合
A,就是要确 定,哪些元素属于
A,哪些元素不属于
A.如果两个集合
A,B包含的元素完全一样,则称A和B相等, 记为A=
B.集合的表示方法主要有两种:列举法和构造法.所谓列举法, 就是列出集合的元素.例如A={a,b,c,d,e}是表示集合A由元素a,b,c,d,e组成.所谓构造法,就是描述出集合中元素适合的 —1— 条件.例如,A=x|x∈Z,x>0表示集合A是由所有正整数组成. 例1-1-1A=x|x∈Z,x2-3x+2=
0,表示A的元素只有两个,即x2-3x+2=0的两个根x=1,x=
2.A= x|x∈Z,x2-3x+2=0=1,
2.设有两个集合
A,B,如果A的每个元素也是B的元素,则称 A为B的子集,或称B包含
A,记为AB.如果A不是B的子集,则记为AB.例如,A={a,b,c}是B={a,b,c,d}的子集,集合A是自己的子集.如果AB并且A≠
B,则称A是B的真子集,记为AB.显然,A=B当且仅当AB并且BA.我们把没有 元素的集合称为空集,记为/○;只有一个元素的集合称为单点集. 例如,A={x|x∈Q,x2=-1}是空集;A={x|x=3}={3}是单点集.我们规定:空集是任何集的子集. 如果一个集合包含了所要讨论的每一个集合,则称这个集合为全集,记为
U.例如,在人口研究中,全集就是包含全世界所有人的集合.在研究平面上的点中,全集就是包含平面上的所有点的集合. 定义1-1-1设A是给定的一个集合,A的所有子集构成的集合,称为A的幂集,记为P(A)或2A,即 P(A)={x|xA}.例1-1-2设A={a,b},则 例1-1-
3 P(A)={/○,{a},{b},A}. 设A={a,b,c},则 P(A)={/○,{a},{b},{c},{a,b},{a,c},{b,c},A}. 从上面例子可以看出:2个元素的集合的幂集有4=22个元素,3个元素的集合的幂集有8=23个元素.可以推出:n个元素的集合的幂集有2n个元素(见习题1-11). —2— §1-2集合的运算集合元素的个数 集合的运算就是以给定集合为对象,按照确定的规则,产生另 外一些集合.例如,A表示“上数学课的学生集合”;B表示“上物理课的学生集合”.如果这两门课安排在同一时间进行期终考试,那 么参加这两门课考试发生冲突的学生集合是什么?
显然,该集合是同时上这两门课的学生的集合.如果在上数学课时和上物理课 时分别宣布同一通知,那么知道这个消息的学生集合是什么?
显然,这个集合是由 上数学课或上物理课的学生组成；＃￣.Ｕ为ｐ了使这些概念一般化,我们定义集合的运算. 定义1-2-1设
A,B是全集U的子集,由A和B的所有共同 元素构成的集,称为A和B的交集,记为A∩
B,即A∩B={x|x∈U,x∈A并且x∈B}. 两个集合的交可用所谓文氏图表示,见图1-2-
1,其中阴影部分就是A∩
B. 例1-2-1设A={a,b,c,
U d},B={a,b,c,e,f},则A∩
B ={a,b,c}.定理1-2-
1 集合的交运
A B 算满足下面性质,这里
A,B,
C 是全集U的子集,/○是空集. 图1-2-
1
(1)A∩A=A;
(3)A∩U=A;
(2)A∩/○=/○;
(4)A∩B=B∩A;
(5)A∩(B∩C)=(A∩B)∩
C.下面证明
(5). 证(A∩B)∩C={x|x∈(A∩B)并且x∈C}={x|(x∈A并 —3— 且x∈B)并且x∈C}={x|x∈A并且(x∈B并且x∈C)}={x|x∈A并且x∈(B∩C)}={x|x∈A∩(B∩C)}=A∩(B∩C). 如果集合
A,B没有共同的元素,则称
A,B不相交,记为A∩ B=/○. 定义1-2-2设
A,B是全集U的子集,所有属于A或属于
B 的元素构成的集,称为A和B的并集,记为A∪
B,即 A∪B={x|x∈U,x∈A或x∈B}. 两个集的并集的文氏图为图1-2-
2. 例1-2-2设A={a,b,c},
B U ={b,c,d,e},则
A B A∪B={a,b,c,d,e}.定理1-2-2集合的并运算满 足下面性质,这里
A,B,C是全集 图1-2-
2 U的子集,/○是空集.
(1)A∪A=A;
(2)A∪U=U;
(3)A∪/○=A;
(4)A∪B=B∪A;
(5)A∪(B∪C)=(A∪B)∪
C. 证这些性质的证明,容易从定义得出. 定理1-2-3集合的交、并运算满足下面性质,这里
A,B,
C 是全集U的子集.
(1)A∩(B∪C)=(A∩B)∪(A∩C);
(2)A∪(B∩C)=(A∪B)∩(A∪C);(分配律)
(3)A∪(A∩B)=A;(吸收律)
(4)A∩(A∪B)=A;
(5)若AC,则A∪(B∩C)=(A∪B)∩
C.(模律)下面证明
(5).证设x∈A∪(B∩C),则x∈A或x∈B∩
C.当x∈A时,x —4— ∈A∪
B.又因为AC,故x∈
C,即x∈(A∪B)∩C;当x∈(B∩C)时,则x∈A∪B并且x∈
C,即x∈(A∪B)∩
C.因此,A∪(B∩C)(A∪B)∩C;反之,设x∈(A∪B)∩
C,则x∈(A∪B)并且x∈
C.若x∈
A,则x∈A∪(B∩C);若x∈
B,则x∈B∩
C,从而x∈A∪(B∩C).于是A∪(B∩C)(A∪B)∩
C.因此,在
A C的条件下,有A∪(B∩C)=(A∪B)∩
C. 集合的交与并的概念还可以推广到全集U的任意多个集合上去. 定义1-2-3设
A,B是全集U的子集,所有属于A而不属于B的一切元素构成的集,称为B关于A的余集或补集,记为A-
B,即 A-B={x|x∈U,x∈A并且x∈|B}. A-B也称为集合A和B的差,文氏图为图1-2-
3.例1-2-3设A表示“上数学课的学生集合”,B表示“这门课考试及格的学生集合”,则A-B表示“上数学课的学生中考试不及格的学生集合”.例1-2-4设A是素数集合,B是奇数集合,则A-B={2}.例1-2-5设A={a,b,c,d},B={a,e},则A-B={b,c,d},B-A={e}.上面例子说明:A-B≠B-
A.定义1-2-4设A是全集U的子集,集合A关于U的余集U-
A,称为集合A的余,记为A′或珔
A,即 A′={x|x∈U并且x∈|A}. 集合A的余的文氏图为图1-2-
4.显然,A-B=A∩B′.定理1-2-4集合的余的运算满足下面性质,这里
A,B是全 集U的子集,/○是空集. —5—
U ＆A＆
B UA 图1-2-
3 图1-2-
4
(1)(A′)′=A;
(2)U′=/○;
(3)/○′=U;
(4)A∪A′=U;
(5)A∩A′=/○;
(6)(A∪B)′=A′∩B′;
(7)(A∩B)′=A′∪B′. 下面证明
(6). 证(A∪B)′={x|x∈(A∪B)′}={x|x∈|A并且x∈|B} ={x|x∈ｉA′并ｉ且ｗ＿＾５Ｍ｝x∈B′}=A′∩B′. 定义1-2-5设
A,B是全集U的子集,A和B的对称差为集 合
S,其元素属于A或属于
B,但不能既属于A又属于
B,记为
A B或A△
B,即 S=AB=(A∪B)-(A∩B).两个集的对称差的文氏图为图1-2-
5.
U A ｑBｑ 例1-2-
6 图1-2-
5 设A表示“主机有故障的计算机集合”,B表示“外 —6— 部设备有故障的计算机集合”,则AB表示“主机有故障与外部设备有故障中,只有一种故障的计算机集合”. 定理1-2-5集合的对称差满足下面性质,这里
A,B,C是全 集U的子集,/○是空集.
(1)AB=BA;
(2)A/○=A;
(3)A
(4)
A A=/○; B=(A∩B′)∪(A′∩B)=(A-B)∪(B-A);
(5)(AB)C=A(BC).下面证明
(4),
(5).证
(4)
A B=(A∪B)-(A∩B)=(A∪B)∩(A∩B)′=(A∪B)∩(A′∪B′)=(A∩A′)∪(A∩B′)∪(B∩A′)∪(B∩B′)=(A∩B′)∪(A′∩B)=(A-B)∪(B-A);
(5)A(BC)=[A∩(BC)′]∪[A′∩(BC)]={A∩[(B∩C′)∪(B′∩C)]′}∪{A′∩[(B∩C′)∪(B′∩C)]}={A∩[(B′∪C)∩(B∪C′)]}∪[(A′∩B∩C′)∪(A′∩B′∩C)]=(A∩B′∩B)∪(A∩B′∩C′)∪(A∩B∩C)∪(A∩C∩C′)∪(A′∩B∩C′)∪(A′∩B′∩C)=(A∩B∩C)∪(A∩B′∩C′)∪(A′∩B∩C′)∪(A′∩B′∩C). 这表示
A,B,C是对称的,于是 —7— A(BC)=(AB)
C.下面讨论集合的元素的个数问题.集合A中不同元素的个数,称为集合A的阶或基,记为#A或|A|.如果#A是有限的,称A为有限集;如果#A是无限的,称A为无限集.如果A和B都是有限集,并且不相交.显然, #(A∪B)=#A+#
B.定理1-2-6设任意两个有限集
A,B,则 #(A∪B)=#A+#B-#(A∩B).证从图1-2-6中看出:A∪B可表为不相交的A和B-A的并.B可表为不相交的B-A和A∩B的并.于是 #(A∪B)=#A+#(B-A),#B=#(B-A)+#(A∩B).由此可得#(A∪B)=#A+#B-#(A∩B).
U A BB-
A 图1-2-
6 例1-2-7假设在12本书的集合中,其中有6本小说.2001年出版的有7本书,其中有3本小说.设A为小说的集合,B为2001年出版的书的集合,即#A=
6,#B=
7,于是A∪B表示或是小说或是2001年出版的书的集合. #(A∪B)=#A+#B-#(A∩B)=6+7-3=10,即有10本书或是小说或是2001年出版的书. —8— 定理1-2-7设任意三个有限集
A,B,
C,则#(A∪B∪C)=#A+#B+#C-#(A∩B)-#(A∩C) -#(B∩C)+#(A∩B∩C).证#(A∪B∪C)=#[(A∪B)∪C] =#(A∪B)+#C-#[(A∪B)∩C]=#A+#B+#C-#(A∩B) -#[(A∩C)∪(B∩C)]=#A+#B+#C-#(A∩B) -#(A∩C)-#(B∩C)+#(A∩B∩C).定理1-2-8设任意n个有限集合A1,A2,…,An,则 #(A1∪A2∪…∪An) n ∑∑=#A1- #(Ai∩Aj) i=
1 1≤i
1 1≤i
1 ∑∑=#(Ai∩An)- #(Ai∩Aj∩An)+… i=
1 1≤i
1 1≤i
1 # ( ′ A1 ∩ ′ A2 ∩ … ∩ ′ An) = u- #(A1∪A2∪…∪An) n ∑∑=u- #Ai+ #(Ai∩Aj) i=
1 1≤i
2,…,m,则 #Ai=n,i=1,
2,…,m;pi #(Ai∩Aj)=n,i,j=1,
2,…,m,j>i;pipj #(Ai∩Aj∩Ak)=n,i,j,k=1,
2,…,m,k>j>i;pipjpk …… 因此, φ(n) = # ( ′ A1 ∩ ′ A2 ∩ … ∩ ′ Am) m ∑∑=n- #Ai+ #(Ai∩Aj) i=
1 1≤i
1 pα22 - 1… pαmm
1 ( p1 - 1)(p2 - 1)…(pm - 1) ∏mα-
1 =pii(pi-1). i=
1 例如,求n=20的欧拉函数φ(20).因为n=20=22×
5,于是φ(20)=φ(22×5)=2×(5-1)=
8,即比20小且与20互素的正整数有1,3,7,9,11,13,17,19. §1-3关系与等价关系 定义1-3-1设
A,B是两个非空集,如果有序对的第1个元素是A的元素,第2个元素是B的元素,则所有这样的有序对的集,称为集A和B的笛卡尔积,记为A×
B,即 A×B={(x,y)|x∈A,y∈B}.两个有序对相等(a,b)=(c,d)当且仅当a=c,b=d.例1-3-1设A={a,b},B={1,2,3},求A×
B,B×
A,A×
A.解A×B={(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)};B×A={(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)};A×A={(a,a),(a,b),(b,a),(b,b).—12— 例1-3-2设A=B=
R,则R×R={(x,y)|x,y∈R}, 这就是笛卡尔坐标平面的点集.两个集合的笛卡尔积可以推广到n个集合.设A1,A2,…,An 是任意n个集合,集合{(a1,a2,…,an)|ai∈Ai,i=1,
2,…,n}称为A1,A2,…,An的 笛卡尔积,记为A1×A2×…×An,即A1×A2×…×An={(a1,a2,…,an)|ai∈Ai,i=1,
2,…,n}.A×A记为A2,A×A×A记为A3,n个A的笛卡尔积记为An.定义1-3-2A×B的子集
R,称为
A,B间的一个二元关系, 当(a,b)∈R时,称a与b具有关系
R,记为aRb;当(a,b)∈|
R 时,称a与b不具有关系
R,记为aR′b.对于任意a∈A,b∈
B,(a,b)在R中或不在R中,故aRb或 aR′b二者有
一,且仅有一种情形成立.一个二元关系只是把A中的某些元素与B中的某些元素相关 的直观概念,给以形式化.例如,设A表示4个学生的集合,A={a,b,c,d}.B表示6门课程的集合,B={1,2,3,4,5,6}.A×B给出学生和课程之间所有可能的配对,共有24种配对的方法.设关系 R={(a,1),(b,2),(b,4),(c,2),(c,3),(c,5),(d,3),(d,6)}为学生们所选读的课程.这就是说:学生a选读1课程,学生b选读2,4课程,学生c选读2,3,5课程,学生d选读3,6课程. 例1-3-3在实数集R中,大于关系“>”可记为“>”={(x,y)|x,y∈R,x大于y}. 当集合A=B时,关系R是A×A的子集,这时R称为在A上的二元关系,或简称关系. 一个二元关系,除了用列出的有序对的方式表示之外,还可以用关系表或关系图的形式来表示,也可以用关系矩阵表示.例如, —13— 令关系 A={a,b,c,d},B={1,2,3}, R={(a,1),(b,3),(c,1),(c,3),(d,2)}是A与B的一个二→←＇ 元关系.R可表示为表1-3-
1,这里表的行对应于A中的元素,列对应于B中的元素,方格中的符号“”表示对应行的元素相关于对应列的元素.二元关系R也可以表示为图的形式,如图1-3-
1,其中左边一列的点表示A的元素,右边一列的点表示B的元素.从左边的一个点到右边的一个点,画一条有向线段或有向弧,来表示A中元素相关于B中的对应元素. 表1-3-1 123abcd a
1 b2 c d
3 图1-3-
1 二元关系R还可以用关系矩阵表示.矩阵的行对应于A的元素,矩阵的列对应于B的元素.如果对应行i的元素相关于对应列j的元素,则矩阵的第i行j列为
1,否则为
0.如上例对应的关系矩阵为 100 001 MR= . 101 010定义1-3-3设R是集A上的二元关系,那么
(1)如果对于任何a∈
A,均有aRa,则称R具有反身性;
(2)如果对于任何a,b∈
A,当aRb时,恒有bRa,则称R具—14— 有对称性;
(3)如果对于任何a,b,c∈
A,当aRb并且bRc时,恒有aRc, 则称R具有传递性;
(4)如果对于任何a,b∈
A,当aRb并且bRa时,恒有a=b, 则称R具有反对称性.例1-3-4设非零整数集Z*上的二元关系为R={(a,b)|a,b∈Z*,a|b}, 这里a|b为a整除b.则R具有反身性,传递性.但不具有对称性 和反对称性.例如,2|
4,但4/|2;3|(-3),(-3)|
3,但-3≠
3. 定义1-3-4设R是集A上的二元关系,如果R满足反身性,对称性和传递性,则称R为A上的等价关系,记为～. 如果～是A上的等价关系,对于任意a,b∈
A,若有a～b,则称a与b是等价的.称[a]={x∈A|x～a}为包含a的等价类. 例如,设A是学生集合,R是A上的二元关系,规定:对于所有a,b∈A(记为"a,b∈A),aRb当且仅当a与b同住一宿舍.显然,R是等价关系.又如,集A={1,2,3,4},关系 R={(1,1),(1,4),(4,1),(4,4),(2,2),(2,3),(3,2),(3,3)}也是等价关系. 例1-3-5设R是Z上的二元关系,规定:如果Z中的数a,b用固定正整数n除,余数相等,则(a,b)∈
R,即aRb当且仅当a-b是n的倍数,记为a≡b(modn),证明:R是等价关系,这个等价关系称为模n的剩余关系. 证"a,b∈Z
(1)因为a-a=
0,于是(a,a)∈R;
(2)如果a≡b(modn),即a-b=kn(k∈Z),于是b-a=-kn.所以,b≡a(modn);
(3)如果a≡b(modn),b≡c(modn),即 a-b=k1n,b-c=k2n(k1,k2∈Z) 于是 —15— a-c=a-b+b-c=(k1+k2)n, 即 a≡c(modn). 因此,R是Z上的等价关系. 定理1-3-1设～是集A的等价关系,那么
(1)如果"a,b∈A,a～b,则[a]=[b];
(2)如果"a,b∈A,aｙb,则[a]∩[b]=/○,这里ｙ表示不 等价;
(3)A能写成所有不同等价类的并. 证
(1)如果a～b,"x∈[a],于是x～a,由传递性,x～b, 从而x∈[b],即[a][b].同理可证:[b][a].因此,[a]= [b].
(2)如果aｙb,假定A中存在一个元x∈[a]∩[b],于是x ∈[a],x∈[b],即x～a,x～b,从而a～b,这与假设矛盾.因此, [a]∩[b]=/○.
(3)从
(1)、
(2)知道:两个等价类或是相同或是不相交.由于等价关系～的反身性,"a∈
A,有a∈[a].因此,A是所有不同等价类的并. 从上面定理可看出,等价类可由这个等价类中的任一元素作代表,即等价类与其代表的选择无关. 下面讨论集合A上的等价关系与A的一个划分之间的联系.集合A的一个划分是集合A的非空子集A1,A2,…,Ak的集合{A1,A2,…,Ak},使得这些非空子集Ai的并等于
A,并且对于任意 两个不同的Ai,Aj,它们的交是空集,即A=A1∪A2∪…∪Ak;并 且当i≠j时,Ai∩Aj=/○.Ai就称为划分的块.例如,把一副扑克 52张牌,可按花色划分为4套,也可按数字大小划分为13个等级.我们可以由集合A上的等价关系来确定A的一个划分,使得 在A中任意有关系的元素,放在同一块中,而没有关系的元素,放 —16— 在不同的块中.这样的划分,称为由等价关系导出的划分,而这划分中的块就是等价类.反之,可由集合A的一个划分来确定A上的一个等价关系,使得在划分的同一块中的A的任意两个元素是相关的,而在不同块中的A的任意两个元素是不相关的.例如,A是中国人的集合,R是A上的一个二元关系,使得(a,b)∈R当且仅当a和b的姓相同.显然,R是一个等价关系.由这个等价关系,可以导出A的一个划分,其中等价类是由同姓的人组成.又如,设n是一个固定的正整数,令R是整数集Z上的一个二元关系,R={(a,b)|a,b∈Z,a≡b(modn)}.在例1-3-5中,我们已证明了这个模n剩余关系是等价关系.这个等价关系可将Z划分成n个等价类,这些等价类分别是整数除以n其余数为0的数构成的等价类[0];余数为1的数构成的等价类[1];…;余数为n-1的数构成的等价类[n-1],共有n个等价类,这样的等价类称为模n剩余类. 例1-3-6设R是Z上的模3剩余关系,即R={(a,b)|a,b∈Z,a≡b(mod3)} 确定由Z的元素所产生的剩余类.解模3剩余类是[0]={…,-
6,-3,0,3,
6,…},[1]={…,-
5,-2,1,4,
7,…},[2]={…,-
4,-1,2,5,
8,…}. [0],[1],[2]分别表示0,1,2所在的剩余类,从上面可看出[0]=[3]=[-3]=[6]=[-6]=…, 即0,
3,-3,
6,-6,…所在的剩余类是相同的. §1-4映射映射的计数代数运算 映射是数学的基本概念.在高等数学中,我们讨论的函数y=—17— f(x)是在实数集中进行的,现在我们将把函数的概念推广.定义1-4-1设A和B是两个非空集合,f是A与B的一个 二元关系,如果对于每一个x∈
A,都有唯一的y∈
B,使得(x,y)∈f,则称关系f为A到B的映射(或函数),记为f:AB或 f AB.我们经常用符号y=f(x)来代替(x,y)∈f.如果(x,y)∈f,则称x为自变元,y为在f作用下x的像,x 称为y的原像.A称为映射f的定义域,B称为映射f的定值域.一个映射必须联系两个集合和一个关系.两个映射f:A→
B, g:A1→B1,当且仅当A=A1,B=B1,且对于任何x∈
A,均有f(x)=g(x)时,才认为是相等,记为f=g. 例1-4-1设A=整数集
Z,B=实数集
R,规定f:Z→R为f(x)=x2,"x∈
Z,则f是Z到R的一个映射. 例1-4-2设A=B=正整数集Z+,规定f:Z+→Z+为f(n)=n-
1,"n∈Z+,则f不是Z+到Z+的映射.因为,当n=1时, n-1∈|Z+. 例1-4-3设A={a,b,c,d},B={1,2,3},规定f:A→B为f(a)=1,f(b)=2,f(c)=2,f(d)=
2,则f是A到B的一个映射. 如果A到A的映射f,使f(a)=a,"a∈
A,则称f为A上的恒等映射. 定义1-4-2设f是集A到B的一个映射,如果对于任何b∈
B,均有a∈
A,使f(a)=b,则称f为A到B的一个满射(或映上的). 例1-4-4设A={a,b,c,d},B={1,2,3},规定f:A→B为a→1,b→2,c→2,d→
3,则f是A→B的一个满射. 定义1-4-3设f是集A到B的一个映射,如果a≠b有f(a)≠f(b),"a,b∈
A,则称f为A到B的一个单射(或1—1的). 例1-4-5设A={a,b,c},B={1,2,3,4},规定f:A→B为—18— f(a)=2,f(b)=1,f(c)=
4,则f是A→B的一个单射.如果f是A到B的一个映射,令f(A)={f(x)|x∈A},称 f(A)为映射f的像→←＇ ,通常记为Imf,即Imf=f(A)={f(x)|x∈A}. 因此,A到B的映射f,若Imf=
B,则f是A到B的满射.定义1-4-4设f是集A到B的一个映射,如果f既是满射, 又是单射,则称这个映射为A到B的一个双射(或一一对应).例1-4-6设A=B=实数集
R,规定f:R→R为f(x)=x3, "x∈
R,则f是R到R的一个双射. h=gf 定义1-4-5设集
A,B,
C,映射
A C f:A→B,g:B→
C,由f,g确定的
A 到C的映射h,h(x)=g(f(x)),"x f g ∈
A,称为映射f,g的合成,或复合, 记为h=gf,h可用图1-4-1表示.例1-4-7设A={1,2,3},B= {p,q},C={a,b}.若f:A→B为 B图1-4-
1 f
(1)=p,f
(2)=p,f
(3)=q;g:B→C为g(p)=b,g(q)=b,则 (gf):A→C为(gf)
(1)=b,(gf)
(2)=b,(gf)
(3)=b. 定理1-4-1设映射f:A→B,g:B→C,h:C→
D,则 h(gf)=(hg)f,即映射合成满足结合律. 证按照映射相等的定义,首先必须证明:映射h(gf)与(hg)f的定义域与定值域都相同,这是显然成立的.其次还需证明:对于任何x∈
A,有[h(gf)](x)=[(hg)f](x).这是因为 [h(gf)](x)=h[(gf)(x)]=h[g(f(x))] =(hg)(f(x))=[(hg)f](x), 即 h(gf)=(hg)f. —19— 定理1-4-2设映射f:A→B,g:B→
C,那么
(1)如果f,g都是单射,则gf也是单射;
(2)如果f,g都是满射,则gf也是满射;
(3)如果f,g都是双射,则gf也是双射. 证
(1)要证明gf为单射,由定义必须证明:对于任何x1, x2∈
A,如果x1≠x2,有(gf)(x1)≠(gf)(x2),或证明:如果 (gf)(x1)=(gf)(x2),有x1=x2. 如果(gf)(x1)=(gf)(x2),即g(f(x1))=g(f(x2)),由于 g是单射,于是f(x1)=f(x2),由于f是单射,于是x1=x2.因此, gf是单射.
(2)令z∈
C,由于g是满射,所以存在y∈
B,使g(y)=z.由 于f是满射,所以存在x∈
A,使f(x)=y.因此,(gf)(x)= g(f(x))=g(y)=z.即gf是满射.
(3)由
(1),
(2)可得.定义1-4-6设映射f:A→
B,如果存在映射g:B→
A,使gf =IA,fg=IB,这里IA,IB分别是A和B上的恒等映射,则g称为 f的逆映射.如果映射f的逆映射存在,则称f为可逆映射. 定理1-4-3的,记为f-
1. 映射f:A→
B,如果f的逆映射存在,则是唯
一 证假定f有两个逆映射,g:B→A,h:B→
A,于是gf= IA,fg=IB,hf=IA,fh=IB.因此 h=IAh=(gf)h=g(fh)=gIB=g.定理1-4-4映射f:A→B有逆当且仅当f是双射.证设h:B→A是f的逆映射,如果对于任何x1,x2∈A,f(x1)=f(x2),于是(hf)(x1)=(hf)(x2),从而x1=x2.因此,f为单射.对于任何y∈
B,如果h(y)=x,于是f(x)=f(h(y))=y.因此,f是满射.所以f是双射.—20— 反之,如果f是双射,对于任何y∈
B,有唯一的x∈
A,使f(x)=y.我们定义映射g:B→A为g(y)=x,于是(fg)(y)=f(g(y))=f(x)=y,即fg=IB.对于任何x∈
A,(gf)(x)=g(f(x))=g(y)=x,即gf=IA.因此,g是f的逆映射. 定理1-4-5设有限集合
A,B,且#A=n,#B=m,则
(1)映射f:A→B的个数为mn;
(2)当m≥n时,单射g:A→B的个数为m(m-1)…(m-n +1);
(3)当m=n时,双射h:A→B的个数为m!
.证
(1)由映射的定义,A的每个元素在B中一定存在且唯
一 的像.我们把A中的元素排成1～n.第1个元素在B中的像有m种选择法,第2个元素在B中的像也有m种选择法,……,第n个元素在B中的像同样有m种选择法.因此,f:A→B的个数为mn.
(2)由单射的定义,A的不同元素在B中的像不同.从而,A中第1个元素在B中的像有m种选择法,第2个元素在B中的像 只有m-1种选择法,……,第n个元素在B中的像有m-n+1种选择法.因此,g:A→B的个数为m(m-1)…(m-n+1).
(3)由双射的定义和
(2)得出.定理1-4-6设有限集合
A,B,且#A=n,#B=m,当n≥m时,则满射f:A→B的个数为 mn-m(m-1)n+m(m-2)n-…+(-1)m-1m.
1 2 m-
1 证设A={x1,x2,…,xn},B={y1,y2,…,ym},并设A到
B, 但yi不是A中任何一个元素的像的映射构成的集为Ai,i=
1,
2,…,m,即 Ai={f:A→B|yi∈|Imf}. 由推论1-2-
1,A到B的所有满射个数 —21— s=mn-#(A1∪A2∪…∪Am) m ∑∑=mn- #Ai+ #(Ai∩Aj) i=
1 1≤i
0.而且,我们在B中去掉l个元素有 m种选择法,因此l s=mn- m(m-1)n+
1 m(m-2)n2 -…+(-1)m-1m.m-
1 推论1-4-
1 n!
=nn-n(n-1)n+n(n-2)n-…+(-1)n-1n.
1 2 n-
1 证由定理1-4-6和定理1-4-5的
(3)得出. 定义1-4-7集A到A的映射,称为A的变换;A到A的双 射,称为A的一一变换;A的所有变换构成的集记为AA. 下面讨论代数运算的概念. 定义1-4-8设A是一个非空集合,A×A到A的一个映射f, 称为A的一个代数运算,即对于A中的任意两个元素a,b,通过f 唯一地确定一个c∈
A,使f(a,b)=c,记为ab=c. 如果是A的一个代数运算,也称A对于代数运算是封闭 的.A的代数运算也称为A的结合法. 由于(a,b)和(b,a)一般是A×A中的不同元素,故ab不 —22— 一定等于ba.例如,有理数集中的加法、减法、乘法都是代数运算,而除法不 是代数运算,因为零不能当除数.又如,给定非空集合
A,A的幂集P(A),对于任何x,y∈P(A),x∩y,x∪y和xy都属于P(A), 于是集的交、并与对称差都是P(A)的代数运算.例1-4-8设B={0,1},规定0*0=0,1*0=0,0*1=0,1* 1=
1.显然,*是B的代数运算.B的代数运算也可用运算表来表示,如表1-4-
1.在表中写在垂线左边的是B×B中前面B的元 素,横线上边的是B×B后面B的元素.例1-4-9设A={a,b,c,d},代数运算由表1-4-2给出,这 里dc=a,cd=d,ab=b,等等. 表1-4-
2 表1-4-
1 0 a b c d *
0 1 a a b c d
0 0
0 b b d a c
1 0
1 c c a b d d d c a b 定义
1-4-9设A是一个非空集合,n是自然数,A×A×…×A(n个A的笛卡尔积)到A的映射f,称为A的一个n元运算. 上面所说的代数运算就是二元运算.例1-4-10设Q*为非零有理数集,每个非零有理数的倒数还是有理数.因此,倒数运算是Q*的一元运算. §1-5同态与同构 我们已知道近世代数的主要研究对象是代数系统,即具有一些n元运算的集合.设集合A的二元运算,这个代数系统记为 —23— (
A,).下面讨论与二元运算发生关系的映射.定义1-5-1设(
S,)和(
T,*)是两个代数系统,这里,*分 别是集S和T的二元运算.如果存在S到T的映射f,并且保持运算,即 f(ab)=f(a)*f(b)"a,b∈
S. 则称f是(
S,)到(
T,*)的同态映射,简称f是S到T的同态映射. 例1-5-1设(
Z,+)和(R+,·)这里Z与R+分别为整数集和正实数集,+与·分别为数的加法和乘法.规定f:Z→R+为f(x)=ex,"x∈
Z.显然,f是Z→R+的映射,并且对于任何x,y∈Z,f(x+y)=ex+y=ex·ey=f(x)·f(y).因此,f是Z到R+的同态映射. 例1-5-2设(
Z,+)和(
A,·),这里A={
1,-1},·为数的乘法.规定映射f:Z→A为对于任何x∈
Z, 1,当x为偶数(包括负偶数)时;f(x)=-
1,当x为奇数(包括负奇数)时,证明:f是Z→A的同态映射. 证对于任何x,y∈
Z,
(1)如果x,y都是偶数,则 于是 f(x)=1,f(y)=
1, f(x+y)=1=1·1=f(x)·f(y).
(2)如果x,y都是奇数,则 于是 f(x)=-1,f(y)=-
1, f(x+y)=1=(-1)·(-1)=f(x)·f(y).
(3)如果x是奇数,y是偶数,则 f(x)=-1,f(y)=
1, —24— 于是f(x+y)=-1=(-1)·1=f(x)·f(y). 同理可证:x是偶数,y是奇数时,f(x+y)=f(x)·f(y).因此,f是Z→A的同态映射. 例1-5-3在例1-5-2中,如果规定映射f:Z→A为f(x)=-
1,"x∈
Z,问f是Z到A的同态映射吗?
解"x,y∈Z,f(x)=-1,f(y)=-1,f(x+y)=-1≠f(x)·f(y), 于是f不是Z到A的同态映射.例1-5-4实数集R关于数的乘法·的代数系统(
R,·),规定 映射f:R→R为f(x)=x2,"x∈
R,问f是R→R的同态映射吗?
解对于任何x,y∈R,f(x·y)=(x·y)2=x2·y2=f(x)·f(y). 因此,f是R→R的同态映射.定义1-5-2如果集S到T的同态映射f是S到T的单射,则 称f为S到T的单一同态.定义1-5-3如果集S到T的同态映射f是S到T的满射,则 称f为S到T的满同态.如果集S到T存在满同态,则称S和T是同态的,记为S～
T.定义1-5-4如果集S到T的同态映射f是S到T的双射,则 称f为S到T的同构映射(或简称同构).如果S和T之间存在同构映射,则称S和T是同构的,记为 Sǖ
T.例如,例1-5-1中的f是Z→R+的单一同态;例1-5-2中的f 是Z→A的满同态.例1-5-5(
R,+)和(R+,·),这里·,+分别为数的乘法和加 法.规定映射f:R→R+为f(x)=10x,"x∈
R,问映射f是R→—25— R+的同构映射吗?
解对于任何y∈R+,存在x=lgy使f(x)=y,所以f是
R →R+的满射;"x,y∈
R,如果10x=10y,得x=y,所以f为R→R+的单射.因此,f是R→R+的双射.又由于f(x+y)=10x+y=10x·10y=f(x)·f(y),所以f是R到R+的同构映射,即RǖR+. 定理1-5-1代数系统(
S,)和(
T,*),这里,*分别是集S和T的二元运算,设f是S→T的满同态,则
(1)如果适合结合律,则*也适合结合律;
(2)如果适合交换律,则*也适合交换律.证
(1)设珔a,珋b,珋c为T的任意三个元素,由于f是S→T的满同态,于是存在a,b,c∈
S,使f(a)=珔a,f(b)=珋b,f(c)=珋c,有 f[a(bc)]=f(a)*f(bc)=f(a)*[f(b)*f(c)]=珔a*(珋b*珋c),而 由假设 f[(ab)c]=f(ab)*f(c)=[f(a)*f(b)]*f(c)=(珔a*珋b)*珋c. a(bc)=(ab)c,这样珔a*(珋b*珋c)和(珔a*珋b)*珋c是S中同一元素的像,于是珔a*(珋b*珋c)=(珔a*珋b)*珋c.
(2)设珔a,珋b为T的任意两个元素,存在a,b∈
S,使f(a)=珔a,f(b)=珋b, 因为f(ab)=f(a)*f(b)=珔a*珋b, 而 由假设 f(ba)=f(b)*f(a)=珋b*珔a. —26— ab=ba,于是 珔a*珋b=珋b*珔a.定理1-5-2代数系统(
S,,*)和(
T,,*),这里,*是S的二元运算,,*是T的二元运算,设存在一个S到T的满射f,使得S与T对于,同态,对于*,*同态.如果运算对于*适合左(右)分配律,则运算对于*也适合左(右)分配律.证设珔a,珋b,珋c为T的任意三个元,由于f是S→T的满射,于是存在a,b,c∈
S,使f(a)=珔a,f(b)=珋b,f(c)=珋c,有 f[a(b*c)]=f(a)f(b*c) =f(a)[f(b)*f(c)]=珔a(珋b*珋c), f[(ab)*(ac)]=f(ab)*f(ac) =[f(a)f(b)]*[f(a)f(c)]=(珔a珋b)*(珔a珋c).由假设a(b*c)=(ab)*(ac),可得 珔a(珋b*珋c)=(珔a珋b)*(珔a珋c).另一种分配律证明方法类似.定义1-5-5如果f是(
S,)到(
S,)的同构映射,则称f为S的自同构映射(或自同构).例1-5-6设M(n×n;R)={实数上的全体n阶矩阵},规定映射f:M(n×n;R)→M(n×n;R)为f(A)=AT(AT为A的转置矩阵),"A∈M(n×n;R),问
(1)关于矩阵的加法,f是否是M(n×n;R)的自同构?
(2)关于矩阵的乘法,f是否是M(n×n;R)的自同构?
解
(1)不难证明:f是M(n×n;R)到M(n×n;R)的双射;对于任何
A,B∈M(n×n;R),(A+B)T=AT+BT,即 f(A+B)=f(A)+f(B). —27— 因此,f是M(n×n;R)的自同构.
(2)当n>1时,(AB)T=BTAT≠ATBT,即f(AB)≠f(A)f(B). 因此,f不是M(n×n;R)的自同构. —28— 习题
1 1-1设A={1,2,3},B={2,4,6},求A∪
B,A∩
B,A-
B,B-A.1-2设A={x|x∈
R,|x|≥4},B={x|x∈
R,-5≤x<0},求 A∪
B,A∩
B,A-
B,B-A.1-3设A是B的真子集,即AB,问A∩B=?
A∪B=?
1-4证明:A=B当且仅当A∪B=A∩B.1-5证明:A∪B=AB(A∩B).1-6求下面各题中集合M与N的交与并:
(1)Q=有理数集,N=无理数集;
(2)M={全体实数上的n阶对称矩阵},N={全体实数上 的n阶反对称矩阵}.1-7证明:如果对于三个集
A,B,
C,有A∪B=A∪
C,A∩B= A∩
C,则C=
B. 1-81-91-101-11 1-12 1-13 证明:AB当且仅当A∩B′=/○. 证明:(A∪B′)∩(A′∪B)=(A∩B)∪(A′∩B′).设A={x|x∈Z,x2-3x+2=0},求A的幂集P(A).对n用归纳法证明:如果#A=n(n为有限正整数),则A的幂集P(A)具有2n个元素.求用a,b,c,d,e,f六个字母作不重复,并且不出现ace和df的排列的个数.下面哪些关系是等价关系?
(1)设Z+是正整数集,Z+×Z+上的关系R定义为:(a,b) R(c,d)当且仅当a+d=b+c;
(2)设C是实数集到实数集的所有连续函数的集合,C上 的关系R定义为:f(x)Rg(x)当且仅当f
(3)=g
(3);
(3)设Z+是正整数集,Z+上的关系R为数的小于或等于. —29— 1-141-151-16 1-17 1-181-191-20 1-211-221-231-24 — 证明:实数上n阶矩阵间的合同关系、相似关系都是等价关系.设S=非负实数集,B={0,1},试给出S到B的一个映射.设S=非负实数集,R=实数集,对于任何x∈
S,(1)f1:S→R为f1(x)=lnx;(2)f2:S→R为f2(x)=2x-1; (3)f3:S→R为f3(x)=±x;(4)f4:S→R为f4(x)=tanx.问f1,f2,f3,f4是否是S→R的映射,满射,单射?
设R+=正实数集,R=实数集, f:R+→R为f(x)=lnx,"x∈
S.问f是双射吗?
如果是,求出f的逆映射.对下面Z→Z的映射f,g,h,规定为:对于任何x∈
Z, f:x→3x;g:x→3x+1;h:x→3x+
2,计算fg,gf,gh,hg,fgh.设A是坐标平面上所有点的集合,B是x轴上所有点的集合,对于每一个a∈
A,规定f:A→B为f(a)是a向x轴所作垂线的垂足,问f是否是A→B的映射,单射,满射?
设A=B=Z,m是取定的正整数,对于每一个a∈
A,规定f:A→B为f(a)=r,这里r是a除以m所得的余数,即a=qm+r,0≤r
A,并且ff=f,证明:f=IA. 设
A,B,C是集E的三个子集,并且A=B∪
C,B∩C=/○, 找出P(A)到P(B)×P(C)的一个双射.试在实闭区间[0,1]与[a,b](a
(1)S=
Z,法则:ab=ab;
(2)S={所有负整数},法则:ab=-ab;
(3)S= ab00 a,b∈
Z,法则:矩阵乘法. 设A={a,b,c},对于A最多能规定多少种不同的二元 运算?
设R的二元运算为数的乘法,问下面映射是否是R到R的 同态映射?
(1)f(x)=|x|; 1-291-30 1-311-32 1-33 (2)f(x)=2x; (3)f(x)=-x.设代数系统(
A,),(珔
A,),(珕
A,),这里,,分别是
A,珔A,珕A的代数运算,证明:如果A～珔
A,珔A～珕
A,则A～珕
A.设有理数集
Q,代数运算为数的加法,Q*为非零有理数集,代数运算为数的乘法,证明:(
Q,+)与(Q*,·)不存在同构映射.设(
Q,+),这里+为数的加法,找出Q的一个自同构(除恒等映射外).设(
A,*),这里A={a,b,c},x*y=c,"x,y∈
A,规定f:A→A为f(a)=a,f(b)=c,f(c)=b,问f是A的自同构吗?
设(
A,),(
B,*),这里A={1,2,3},B={4,5,6},与*由题表1-1和1-2给出,规定f:A→B为f
(1)=4,f
(2)=5,f
(3)=
6,问f是同构映射吗?
—31— 题表1-
1 1
2 3
1 3
3 3
2 3
3 3
3 3
3 3 题表1-
2 *
4 5
6 4
6 6
6 5
6 6
6 6
6 6
6 1-34 设A={a,b,c},代数运算.由题表1-3给定. 题表1-
3 a b c a c c c b c c c c c c c 找出所有A的一一变换,对于代数运算来说,这些一一变换是否都是A的自同构?
—32— 第2章格 近世代数研究的主要对象是代数系统,这章将讨论一种类型的代数系统,即格.格不仅在代数本身,而且在开关理论,计算理论和逻辑设计都有应用. §2-1偏序集 定义2-1-1设P是任一集合,P上的一个二元关系记为“≤”,满足:
(1)"a∈P,a≤a(反身性);
(2)"a,b∈P,a≤b并且b≤a则a=b(反对称性);
(3)"a,b,c∈P,a≤b并且b≤c则a≤c(传递性).则称≤是P的一个偏序关系或半序关系,具有偏序关系≤的集合
P,称为偏序集或半序集,记为(
P,≤).例2-1-1在R中,≤表示实数间的小于或等于关系,则≤为偏序关系,(
R,≤)是一个偏序集.例2-1-2设A是任意集合,A的幂集P(A),≤表示P(A)中元素间的包含关系,即"
B,C∈P(A),B≤C表示BC,则是偏序关系,(P(A),)是偏序集.例2-1-3在Z+中,≤表示两个正整数间的整除关系,即a,b∈Z+,a≤b表示a|b,则≤为偏序关系,(Z+,≤)是偏序集.对于有限集
P,偏序关系可以用图形表示,规定图形中线段联结的两个点,具有关系≤.如果a≤b,则a为线段下端的点,b为 —33— ３ ＨＩＷ Ｇ 上端的点.这种图称为偏序集合图. 例2-1-4设P={1,2,3,4,6,8,9,12,18,24},如果偏序关系 ≤为整除关系,那么(
P,≤)的偏序集合图为图2-1-
1. 例2-1-5设A={a,b},A的幂集P(A)={/○,{a},{b},A},如 果偏序关系为包含关系,那么(P(A),)的偏序集合图为图2-1-
2. 24 84 1218 69
2 3
A {a} ￥{b}
1 图2-1-
1 图2-1-
2 定义2-1-2设集P的偏序关系≤.如果≤还具有"x,y∈
P 均有x≤y或y≤x,则称≤是P的一个顺序关
8 系或全序关系,具有顺序关系的集,称为有序集或全序集. 例如,例2-1-1中的(
R,≤)是有序集.例2-1-6设P={1,2,4,8},偏序关系≤为整除关系,则(
P,≤)是有序集,偏序集合图 421图2-1-
3 为图2-1-
3. 一个有限的有序集的偏序集合图是由一条有限链组成,即由 一条通路组成.例如,例2-1-
6. 定义2-1-3设(
P,≤)是偏序集,如果P的元素m,对于任何 x∈
P,有m≤x,则称m为P的最小元;如果P的元素n,对于任 何x∈
P,有x≤n,则称n为P的最大元. 例如,例2-1-4中,P的最小元为
1,没有最大元;例2-1-5中, —34— P(A)的最小元为/○,最大元为
A. 定理2-1-1设(
P,≤)为偏序集,如果P的最小元(最大元)存在,则是唯一的. 证假定x,y都是P的最小元,由于x是P的最小元,于是x≤y.另一方面,y也是最小元,于是y≤x.因此,x=y.同理可证最大元情况. 设(
P,≤)为偏序集,如果T是P的子集,P的元素u称为T的一个上界,假如"x∈
T,有x≤u;P的元素v称为T的一个下界,假如"x∈
T,有v≤x. 定义2-1-4设(
P,≤)是偏序集,如果T是P的子集,T的一个上界u称为最小上界,假如对于T的任意上界x,均有u≤x,记为l.u.b.T;T的一个下界v称为最大下界,假如对于T的任意下界x均有x≤v,记为g.l.b.T. 偏序集P的子集T不一定有最小上界,如果最小上界存在,则是唯一的;如果最大下界存在,也是唯一的. 例2-1-7设集P={2,3,6,12,24,36},偏序关系≤为数的整除关系,则偏序集(
P,≤)的偏序集合图为图2-1-
4.如果取P的子集T={2,3,6},于是l.u.b.T=6,g.l.b.T不存在;如果取P的子集T={2,3},于是l.u.b.T=6,g.l.b.T不存在;如果取P的子集T={6,12},于是l.u.b.T=12,g.l.b.T=
6. 例2-1-8设集A={a,b,c},A的幂集P(A),偏序关系为集合的包含关系,则偏序集(P(A),)的偏序集合图为图2-1-
5. P(A)的最小元为/○,最大元为
A.如果取P(A)的子集T= {{b,c},{b},{c}},则A与{b,c}是T的上界,而l.u.b.T={b, c}.○/是T的下界,也是最大下界.如果取P(A)的子集T={{a},{b}},则l.u.b.T={a,b},g.l.b.T=/○. 定义2-1-5一个偏序集(
P,≤)称为良序集,假如P的任意—35— 一个非空子集
T,在T中都有最小元.
A 24 36 12
6 {a,b}{a} {a,c}{b} {b,c}{c}
2 3 图2-1-
4 图2-1-
5 例2-1-9设集Z+为正整数集,偏序关系≤为数的小于或等于关系,则(Z+,≤)为良序集. 由良序集的定义可知,一个良序集(
P,≤)一定是有序集,因为任取x,y∈
P,则{x,y}作成P的子集T有最小元.若x为最小元,则有x≤y;若y为最小元,则y≤x.总之,P中任意两个元都是可比较的,即P是有序集. §2-2格的概念 一个偏序集的子集不一定有最大下界或最小上界,但是有些偏序集,它们的任意两个元素组成的子集均有最小上界和最大下界.这是一类特殊的偏序集. 定义2-2-1设(
L,≤)是一个偏序集,如果L中任意两个元素在L中均有最小上界与最大下界,则称L关于偏序关系≤作成一个格. 例2-2-1设L为实数集
R,偏序关系为数的小于或等于关系≤,则(
R,≤)是格.因为R中任意两个数x,y的最小上界 —36— l.u.b.{x,y}=max{x,y},最大下界g.1.b.{x,y}=min{x,y}. 例2-2-2设B={0,1},在图2-2-1中给出了格(
B,≤1), ＜ ， ） (B2,≤2)和(B3,≤3)的偏序集合图.一般说,(Bn,≤ōn)的偏序 集合图是一个n维立方体.(Bn,≤n)的每一个元素可写成(a1, a2,…,an),这里ai是0或
1,对于任何a,b∈Bn,规定偏序关系 ≤n为(a1-a2,…,an)≤n(b1,b2,…,bn)当且仅当ai≤bi(i=
1,
2,…,n),这里≤为对{0,1}的小于或等于关系.显然(Bn,≤n)是 格,称为0和1的n重序元格. 1(1,1) (1,1,0) (1,1,1) (0,1,1) (1,0,1) (1,0) (0,1) (1,0,0)(0,1,0) (0,0,1)
0 (0,0) (a) (b) (0,0,0)(c) 图2-2-
1 例2-2-3设A是任意集,A的幂集P(A),偏序关系为集合 的包含关系,则(P(A),)是格.因 110 为对于任何
S,T∈P(A),l.u.b.{
S, T}=S∪T,g.l.b.{
S,T}=S∩
T. 10 例2-2-4110的正整数因子集 5522 L={1,2,5,10,11,22,55,110},偏序关系≤为整除关系,即"a,b∈L,a2 511 ≤b当且仅当a|b.从(
L,≤)的偏序集合图(见图2-2-2),可看出L中任意 1图2-2-
2 —37— 两个数都有最小上界和最大下界.因此,(
L,≤)是格.在格(
L,≤)中,任意两个元素a,b,用a∨b表示a,b的最小 上界,a∧b表示a,b的最大下界,即a∨b=l.u.b.{a,b},a∧b=g.l.b.{a,b}.因为由a,b可唯一确定a∨b∈L,a∧b∈
L.因此,∨,∧可看作格L的两个二元运算. 定理2-2-1设(
L,≤)是格,对于任何a,b∈
L,满足:(1)a≤a∨b,a∧b≤a;(2)a≤b当且仅当a∨b=b;(3)a≤b当且仅当a∧b=a.证
(1)从∧,∨的定义立即可得;
(2)如果a∨b=b,于是b=l.u.b.{a,b}.因此,a≤b;反之,如果a≤b,又有b≤b,于是a∨b≤b.由
(1),a∨b≥b.因此,a∨b=b;
(3)与
(2)的证明方法相同.定理2-2-2设(
L,≤)是一个格,对于任何a,b,c∈
L,满足:(L1)a∧a=a,a∨a=a(幂等律);(L2)a∧b=b∧a,a∨b=b∨a(交换律);(L3)(a∧b)∧c=a∧(b∧c)(结合律); (a∨b)∨c=a∨(b∨c)(L4)a∧(a∨b)=a,a∨(a∧b)=a(吸收律).证(L1)从∧与∨的定义立即可得.(L2)因为偏序集的任意两个元素的最大下界和最小上界与元素的顺序无关,即 g.1.b.{a,b}=g.1.b.{b,a},于是(L2)成立.1.u.b.{a,b}=1.u.b.{b,a}, (L3)由定理2-2-1的
(1), —38— (a∧b)∧c≤a∧b≤a,(a∧b)∧c≤(a∧b)≤b, 故有 (a∧b)∧c≤c,(a∧b)∧c≤b∧c, 从而同样地,有因此, (a∧b)∧c≤a∧(b∧c).a∧(b∧c)≤(a∧b)∧c.(a∧b)∧c=a∧(b∧c). 同理可证:(a∨b)∨c=a∨(b∨c).(L4)由定理2-2-1,a≤a∨b,a≤a,于是 又有 a≤a∧(a∨b),a∧(a∨b)≤a 因此,同理可证: a∧(a∨b)=a.a∨(a∧b)=a. 定理2-2-2的逆也成立,先证明引理.引理2-2-1在一个集L中定义两个二元运算∧与∨,使满足(L1)～(L4),则a∨b=a当且仅当a∧b=b. 证设a∨b=a,于是a∧b=(a∨b)∧b=b∧(b∨a)=b; 反之,设a∧b=b,于是a∨b=a∨(a∧b)=a. 定理2-2-3在一个集L上定义两个二元运算∧与∨,使满足(L1)～(L4),则(
L,∧,∨)是一个格. 证我们定义L上的关系≤为a≤b当且仅当a∨b=b, "a,b∈
L.首先证明(
L,≤)是偏序集.由(L1),a∨a=a,于是a≤a,即≤满足反身性;如果a≤b,并且b≤a,于是a∨b=b,并 且b∨a=a,由(L2),a∨b=b∨a,于是a=b,即≤满足反对称性;如果a≤b,并且b≤c(c也是L的任意元),于是a∨b=b,并且b∨c=c,由(L3),a∨c=a∨(b∨c)=(a∨b)∨c=b∨c= —39— c,从而a≤c,即≤满足传递传.因此,(
L,≤)是偏序集.下面证明:L中任意两个元均有最小上界和最大下界.由 (L3)与(L1),a∨(a∨b)=(a∨a)∨b=a∨b,于是a≤a∨b,同 理可证,b≤a∨b.因此,a∨b是{a,b}的上界,令u是{a,b}的任何上界,a≤u并且b≤u,于是a∨u=u并且b∨u=u.由 (L3),(a∨b)∨u=a∨(b∨u)=a∨u=u.因此,a∨b≤u,从而a∨b是{a,b}的最小上界.由(L4)的a∨(a∧b)=a,得a∧b≤ a.由(L4)的b∨(b∧a)=b,得b∧a≤b.由(L2),a∧b≤b,从而 a∧b是{a,b}的下界.令v是{a,b}的任何下界,v≤a并且v≤b,于是v∧(a∧b)=(v∧a)∧b=v∧b=v.由引理2-2-1,v∨ (a∧b)=a∧b,即v≤a∧b.因此,a∧b是{a,b}的最大下界.由定理2-2-2和定理2-2-
3,可得与定义2-2-1等价的另一个 格的定义. 定义2-2-2集L具有两个满足(L1)～(L4)的二元运算∧,∨,则称(
L,∧,∨)是一个格,∧,∨分别称为积(或交)与和 (或并).例2-2-5在Z+中,对于任何a,b,c∈Z+,规定a∧b=GCD (a,b),即a,b的最大公约数.a∨b=LCM(a,b),即a,b的最小 公倍数.由于两个任意正整数a,b都有唯一的最大公约数与最小公倍数,故∧,∨是Z+的两个二元运算. 由于 GCD(a,a)=a,LCM(a,a)=a, 于是(L1)成立; 由于 GCD(a,b)=GCD(b,a), LCM(a,b)=LCM(b,a), 于是(L2)成立; 由于 GCD[GCD(a,b),c]=GCD[a,GCD(b,c)], LCM[LCM(a,b),c]=LCM[a,LCM(b,c)],于是(L3)成立; —40— 由于a|LCM(a,b),故GCD[a,LCM(a,b)]=a, 由于GCD(a,b)|a,故 LCM[a,GCD(a,b)]=a,于是(L4)成立.因此,(Z+,GCD,LCM)是一个格. 例2-2-6设A是任意集,A的幂集P(A),规定∧,∨分别为集的交∩和并∪.由于二元运算∩,∪满足(L1)～(L4),于是(P(A),∩,∪)是格. 例2-2-7在例2-2-2中,我们知道Bn={(a1,a2,…,an)|ai=0或1},对于任何(a1,a2,…,an),(b1,b2,…,bn)∈Bn,规定∧,∨分别为(a1,a2,…,an)∧(b1,b2,…,bn)=(c1,c2,…,),这里ci为ai,bi较小的一个.(a1,a2,…,an)∨(b1,b2,…,bn)=(d1,d2,…,dn),这里di为ai,bi较大的一个.显然,二元运算∨,∧满足(L1)～(L4),于是(Bn,∧,∨)是格. 例2-2-8设V为数域P上的线性空间,L(V)表示V的所有子空间构成的集合,因为"T1,T2∈L(V),T1∩T2与T1+T2={t1+t2|t1∈T1,t2∈T2}仍是V的子空间,所以T1∩T2,T1+T2∈ L(V).我们规定:∧与∨分别为T1∧T2=T1∩T2,T1∨T2=T1+T2,由于二元运算∧,∨满足(L1)～(L4),于是(L(V),∧,∨)是格,称为子空间格. 定理2-2-4设(
L,≤)是一个格,对于任何a,b,c∈
L,如果b≤c,则a∧b≤a∧c,a∨b≤a∨c. 证(a∧b)∧(a∧c)=(a∧a)∧(b∧c)=a∧(b∧c)=a∧b,于是a∧b≤a∧c. 同理可证:a∨b≤a∨c.定理2-2-5设(
L,≤)是一个格,对于任何a,b,c,d∈
L,
(1)如果a≤b,c≤d,则a∨c≤b∨d,a∧c≤b∧d; —41—
(2)如果a≤b≤c,并且d∧c=a,则d∧b=a;
(3)如果a≥b≥c,并且d∨c=a,则d∨b=a.证
(1)因为b≤b∨d,d≤b∨d,由传递性,a≤b∨d,c≤b∨d,即b∨d是a和c的一个上界,但a∨c是a和c的最小上界.因此,a∨c≤b∨d.同理可证:a∧c≤b∧d.
(2)因为b≤c,即b∧c=b,于是d∧b=d∧(b∧c)=d∧(c∧b)=(d∧c)∧b=a∧b=a.
(3)与
(2)的证明方法相同.定理2-2-6设(
L,≤)是一个格,a,b,c∈
L,证明:如果c≤a,则a∧(b∨c)≥c∨(a∧b).证因为c≤a,a∧b≤a,所以c∨(a∧b)≤a.又由c≤c∨b,a∧b≤b≤c∨b,可得c∨(a∧b)≤c∨b.因此, c∨(a∧b)≤a∧(c∨b).设N是对任何偏序集为真的一个命题,N′是把N中所有≤与≥对换,得到的对偶命题,可以得出:N′对于任何偏序集也是真的,这称为对偶原理.在格(
L,≤)中将偏序关系反转后,得到另一个格(
L,≤′),这时(
L,≤)中的a∧b,a∨b恰好是(
L,≤′)中的a∨b,a∧b.如定理2-2-2中的(L1)～(L4),每一条都包含互为对偶的两个命题.我们只要证明一个命题,利用对偶原理,立即可得其对偶命题.对偶概念在电信中也会经常遇到,如电压与电流,电阻与电导,电感与电容等概念分别都是对偶概念.上面我们把格定义为代数系统,这样自然可以引入子格的概念.定义2-2-3设(
L,∧,∨)是一个格,L的非空子集
T,如果T关于∧,∨封闭,即"a,b∈
T,有a∧b∈T,a∨b∈
T,则称(
T,∧,∨)是(
L,∧,∨)的子格.例2-2-9设Z+为正整数集,对于任何a,b∈Z+,规定a∧b=GCD(a,b),a∨b=LCM(a,b).由例2-2-
5,(Z+,∧,∨)是格,—42— 令Z+的子集T为偶数集.由于两个偶数的最大公约数与最小公倍数还是偶数,于是T关于∧,∨是封闭的,即(
T,∧,∨)是(Z+,∧,∨)的子格. 例2-2-10如图2-2-3表示的格(
L,∧,∨),L={a0,a1,a2, a3,a4,a5,a6,a7},设L的子集S1={a1,a3,a5,a7};S2={a0,a1, a3,a7};S3={a1,a3,a6,a7},不难 a7 看出:关于∧,∨下S1是封闭的,故(S1,∧,∨)是(
L,∧,∨)的子a1 a3a2 格;子集S2中a1∧a3=a5∈|S2, 故(S2,∧,∨)不是(
L,∧,∨)的子 a4 a5 a6 格,但是它本身构成格;子集S3不但不能构成子格,而且它本身也不构成格. a0图2-2-
3 由子格的定义,不难证明:子格本身也构成格,但反之不一定成立. 注设一个格的子集构成格,但还不一定是子格.定义2-2-4设(
L,∧,∨)和(
S,*,)是两个格,给定(L×
S,,+),这里和+分别是L×S的二元运算,对于任何(a1,b1,),(a2,b2)∈L×
S,有(a1,b1)(a2,b2)=(a1∧a2,b1*b2), (a1,b1)+(a2,b2)=(a1∨a2,b1b2),则称代数系统(L×
S,, +)为格(
L,∧,∨)和(
S,*,)的直积.不难证明:两个格的直积也是一个格.例2-2-11设两个格A={1,2,4,8},B={1,2,3,6},两者偏序关 系均为整除关系.A,B的直积的偏序集合图,如图2-2-4所示.下面讨论两个格之间的关系.定义2-2-5设(
L,∧,∨)与(
S,,+)是两个格,如果存在L—43— 8 42 2
1 (a) (8,6)
6 (8,2)(4,6) (4,2)
3 (2,6) (2,2) (1,6) (1,2)
1 (8,3) (8,1)(4,3) (4,1)(2,3) (2,1)(1,3) (1,1) (b) (c) 图2-2-
4 到S的映射f,使得对于任何a,b∈
L,有f(a∧b)=f(a)f(b),f(a∨b)=f(a)+f(b), 则称f是L到S的同态映射.当L到S的同态映射f是单射时,则称f是L到S的单一同 态;当f是满射时,则称f是L到S的满同态;当f是双射时,则称f是L到S的同构映射(简称同构).如果格L和S之间存在同构映射则称L和S同构,记为Lǖ
S.同构格具有相同的特性.例如,它们的偏序集合图除了元素的符号外是相同的. 格(
L,∧,∨)到(
L,∧,∨)的同态映射与同构映射分别称为自同态映射与自同构映射. 例2-2-12设A={a,b},A的幂集P(A)={/○,{a},{b}, A},两个二元运算分别为集合的交∩和并∪.(P(A),∩,∪)和例 2-2-7中的(B2,∧,∨)同构,因为规定f:P(A)→B2为f(/○)= (0,0),f({a})=(1,0),f({b})=(0,1),f(A)=(1,1).不难证明:f是P(A)到B2的同构映射,即P(A)ǖB2.(
P,∩,∪)和(B2,∧,∨)的偏序集合图在图2-2-5表示. —44—
A (1,1) {a} {b} (1,0) (0,1) (0,0) 图2-2-
5 定理2-2-7设f是格(
L,∧,∨)到(
S,,+)的同态映射,则 f是偏序集L到S的保序映射,即对于任何x,y∈
L,当x≤y时, 在S中也有f(x)≤′f(b),这里≤与≤′分别是L和S的偏序关系. 证当x≤y时,有x∧y=x,于是f(x∧y)=f(x).由于f 是L→S的同态映射,从而f(x∧y)=f(x)f(y).因此,f(x) f(y)=f(x),于是f(x)≤′f(y). 定理2-2-8设f是格L到S的双射,则f是L到S的同构映 射的充分必要条件是:对于任何a,b∈L,a≤b当且仅当f(a)≤ f(b)(这里把L与S的偏序关系都记为≤). 证设f是L到S的同构映射,对于任何a,b∈L,a≤b,由 定理2-2-7,f(a)≤f(b);反之,设f(a)≤f(b),于是 f(a)∧f(b)=f(a∧b)=f(a), 由于f是双射,于是a∧b=a,即a≤b(这里把L与S的积的符 号都记为∧). 设a≤b当且仅当f(a)≤f(b),令a∧b=c,于是 c≤a,c≤b. 因此 f(a∧b)=f(c),f(c)≤f(a),f(c)≤f(b), 得 f(c)≤f(a)∧f(b). 令f(a)∧f(b)=f(d).于是f(c)≤f(d),而 —45— f(d)≤f(a),f(d)≤f(b), 从而 d≤a,d≤b, 于是 d≤a∧b=c, 得f(d)≤f(c),故f(d)=f(c).因此, f(a∧b)=f(a)∧f(b). 同理可证:f(a∨b)=f(a)∨f(b). §2-3有补格与分配格 下面讨论具有附加条件的某些格.在一个格中,任意两个元素都有最小上界和最大下界.由数学归纳法不难证明:格中的每一个有限子集也都有一个最小上界和最大下界.但是对于格的无限子集来说,就不一定有最小上界和最大下界.例如,(Z+,≤),这里≤为数的小于或等于关系,那么(Z+,≤)是格,令T是偶数集,T是Z+的子集,但T没有最小上界.定义2-3-1格L称为完全格,假如L的任意非空子集都有最大下界和最小上界. 例2-3-1设集A的幂集P(A),为集合的包含关系, (P(A),)是格.设T={A1,A2,…}为P(A)的子集,则T的最大下界为A1∩A2∩…,最小上界为A1∪A2∪…. 显然,每一个有限格都是完全格.定义2-3-2设(
L,∧,∨)是一个格,如果L中存在元素
0,对于任何x∈L均有x∨0=x,则称0是L的零元或泛下界;如果在L中,存在元素
1,对于任何x∈L均有x∧1=x,则称1是L的单位元或泛上界.显然,格的零元和单位元如果存在时,都是唯一的. 例2-3-2设A={a,b,c},(P(A),),这里为集的包含 关系,则P(A)的零元为/○,单位元为
A.见图2-3-
1. —46— 例2-3-3在例2-2-5中, A=
1 Z+的零元是
1,没有单位元. 例2-3-4整数集关于数的小于或等于关系≤构成的格,既没有零元也没有单位元. 定义2-3-3如果一个格 {a,b}{a} {a,c} {b} {b,c}{c} (
L,∧,∨),具有零元和单位元,则称此格为有界格,有时记为(
L,∧,∨,0,1). =0图2-3-
1 由格的零元和单位元的定义可知,含有零元和单位元的格的 偏序集合图中,在最上面总有标记为1的单位元的单个结点,在最 下面总有标记为0的零元的单个结点.从任何其他结点出发,沿着 一条递升路径,都能达到
1,沿着一条递降路径都能达到
0. 定理2-3-1设(
L,∧,∨,0,1)是有界格,则对于任何x∈
L, 有x∨1=1,x∧0=
0. 证由于1≤a∨
1,但1为单位元,故有a∨1≤
1.因此,a∨
1 =1;由于x∧0≤
0,但0是零元,故有0≤x∧
0.因此,x∧0=
0. 定义2-3-4设(
L,∧,∨,0,1)是有界格,如果对于任何a,b ∈
L,具有a∧b=0,a∨b=
1,则称元素b是a的补元或补,记 为a′. 不难看出,补元是相互的,如果a是b的补元,则b也是a的 补元. 格L中的一个元素可能没有补元,也可能有多个补元.但
1 是0的唯一补元,0是1的唯一补元. 例2-3-5如图2-3-2所表示的格,a是e的补元,d也是e的 补元,b没有补元. 定义2-3-5设(
L,∧,∨,0,1)是一个有界格,如果L中每
一 个元素都至少有一个补元,则称(
L,∧,∨,0,1)是一个有补格. —47— 例2-3-6如图2-3-3所表示的格,这里a2的补是a1,a3的补也是a1,于是这个格是有补格.
1 1 d e b a2 a c a1 a3
0 0 图2-3-
2 图2-3-
3 例2-3-7在例2-2-7中的n重序元格(Bn,∧,∨)是一个有补格.它的零元是(0,
0,…,0),单位元是(1,
1,…,1).Bn的任意元素(a1,a2,…,an)的补元为(a′1,a2′,…,a′n),这里当ai为0时,a′i为1;ai为1时,a′i为
0. 例2-3-8设A={a,b,c},A的幂集P(A),∨和∧分别为集的并和交,则(P(A),∩,∪)是有补格,从图2-3-1可看出{a}与{b,c}互补,{b}与{a,c}互补,{c}与{a,b}互补. 定义2-3-6设(
L,∧,∨)是一个格,如果对于任何a,b,c∈
L,有 (L5)a∧(b∨c)=(a∧b)∨(a∧c),a∨(b∧c)=(a∨b)∧(a∨c), 则称(
L,∧,∨)是一个分配格.例2-3-9在例2-3-8中的(P(A),∩,∪)是分配格.例2-3-10问图2-3-4表示的格是否是分配格?
解因为b∧(c∨d)=b∧1=b, 而 —48— (b∧c)∨(b∧d)=0∨0=
0.
1 因此, b∧(c∨d)≠(b∧c)∨(b∧d), b 所以这个格不是分配格. c d 例2-3-11问图2-3-3表示的格 是否是分配格?
解因为a2∧(a1∨a3)=a2∧
1 =a2,而 0图2-3-
4 (a2∧a1)∨(a2∧a3)=0∨a3=a3. 因此, a2∧(a1∨a3)≠(a2∧a1)∨(a2∧a3), 所以这个格不是分配格. 定理2-3-2在定义2-3-6中,格的两个分配律,如果一个成 立,则另一个也成立. 证设对于任何a,b,c∈
L,若 a∧(b∨c)=(a∧b)∨(a∧c), 于是 (a∨b)∧(a∨c) =[(a∨b)∧a]∨[(a∨b)∧c] =a∨[(a∨b)∧c]=a∨[(a∧c)∨(b∧c)] =[a∨(a∧c)]∨(b∧c)=a∨(b∧c). 反之,同理可证. 定理2-3-3任何有序集(
L,≤)都是分配格. 证
(1)证明:(
L,≤)是格. 因为(
L,≤)是有序集,"a,b∈
L,有a≥b或b≤a.当a≥b时,a,b的最小上界为a,最大下界为b;当b≥a时,a,b的最小上界为b,最大下界为a.因此,(
L,≤)是格.
(2)证明:(
L,≤)是分配格,即证明;"a,b,c∈
L,有 —49— a∧(b∨c)=(a∧b)∨(a∧c).关于a,b,c可分成两种情况讨论:(ⅰ)a≥b,a≥c;(ⅱ)a≤b 或a≤c. 在(ⅰ)的情况下,有a∧(b∨c)=b∨c,而(a∧b)∨(a∧c)=b∨c, 于是 a∧(b∨c)=(a∧b)∨(a∧c); 在(ⅱ)的情况下,有a∧(b∨c)=a,而(a∧b)∨(a∧c)=a, 于是 a∧(b∨c)=(a∧b)∨(a∧c). 因此,在两种情况下,分配律都成立. 例2-3-12设P={1,2,4,8},偏序关系≤为整除关系,问(
P,≤)是分配格吗?
解由例2-1-
6,(P,≤)是有序集,于是(
P,≤)是分配格. 定理2-3-4一的. 在分配格中,如果一个元素有补,则它是唯 证假定元素a有两个补元b,c,即 于是 a∧b=0,a∨b=1,a∧c=0,a∨c=
1, b=b∧1=b∧(a∨c)=(b∧a)∨(b∧c) =0∨(b∧c)=(a∧c)∨(b∧c)=(a∨b)∧c=1∧c=c. 利用定理2-3-4可以比较方便地判断一个格不是分配格.例 如,图2-3-4表示的格中,因为b的补元有c和d,所以这个格不是 分配格.定理2-3-
5 设(
L,∧,∨)是分配格,对于任何a,x,y∈
L, 如果a∧x=a∧y,并且a∨x=a∨y,则x=y. 证x=x∨(x∧a)=x∨(y∧a)=(x∨y)∧(x∨a)=(x∨y)∧(y∨a)=(y∨x)∧(y∨a) =y∨(x∧a)=y∨(y∧a)=y. —50— 利用定理2-3-5也可以判断一个格不是分配格.例如,图2-3-3表示的格中,a1∧a2=a1∧a3=0,a1∨a2=a1∨a3=
1,但a2≠a3,所以这个格不是分配格. 定理2-3-6在有单位元和零元的分配格中,所有有补元所构成的集为一个子格. 证设(
L,∧,∨)是有单位元和零元的分配格,并设A为所有有补元所组成的集.我们证明:A关于∧,∨是封闭的.设a,a′与b,b′是L中的两对互补元,下面证明:a∧b,a′∨b′与a∨b,a′∧b′是L中的两对互补元. (a∧b)∧(a′∨b′)=[(a∧b)∧a′]∨[(a∧b)∧b′]=[(a∧a′)∧b]∨[(b∧b′)∧a]=(0∧b)∨(0∧a)=0; (a∧b)∨(a′∨b′)=[a∨(a′∨b′)]∧[b∨(a′∨b′)
声明：
该资讯来自于互联网网友发布，如有侵犯您的权益请联系我们。
标签： #开什么车 #crf #苹果 #construction #crack #container #cdna #关系