离散数学屈婉玲第十四章.ppt

1第五部分第五部分 代数系统简介代数系统简介主要内容主要内容l二元运算及其性质二元运算及其性质 二元运算和一元运算、二元运算性质、特异元素二元运算和一元运算、二元运算性质、特异元素l代数系统的概念代数系统的概念l几个典型的代数系统几个典型的代数系统 半群、独异点、群半群、独异点、群 环与域环与域 格与布尔代数格与布尔代数l代数系统的同构与同态代数系统的同构与同态2第十四章第十四章 代数系统简介代数系统简介主要内容主要内容二元运算及其性质二元运算及其性质l一元和二元运算定义及其实例一元和二元运算定义及其实例l二元运算的性质二元运算的性质代数系统代数系统l代数系统定义及其实例代数系统定义及其实例l子代数子代数l积代数积代数代数系统的同态与同构代数系统的同态与同构314.1代数系统的基本概念代数系统的基本概念定义定义14.1设设S为集合，函数为集合，函数f：S SS 称为称为S上的上的二元运算二元运算，简称为二元运算函数简称为二元运算函数f:SS 称为称为S上的上的一元运算一元运算，简，简称一元运算称一元运算.lS 中任何元素都可以进行运算，且运算的结果惟一中任何元素都可以进行运算，且运算的结果惟一lS 中任何元素的运算结果都属于中任何元素的运算结果都属于S，即，即S 对该运算封闭对该运算封闭例例1(1)自然数集合自然数集合N上的加法和乘法是上的加法和乘法是N上的二元运算，但上的二元运算，但减法和除法不是减法和除法不是(2)整数集合整数集合Z上的加法、减法和乘法都是上的加法、减法和乘法都是Z上的二元运算，上的二元运算，而除法不是求一个数的相反数是而除法不是求一个数的相反数是Z上的一元运算上的一元运算.(3)非零实数集非零实数集R*上的乘法和除法都是上的乘法和除法都是R*上的二元运算，而上的二元运算，而加法和减法不是求倒数是加法和减法不是求倒数是R*上的一元运算上的一元运算.4实例实例(4)设设Mn(R)表示所有表示所有n 阶阶(n2)实矩阵的集合，即实矩阵的集合，即矩阵加法、乘法是矩阵加法、乘法是Mn(R)上的二元运算上的二元运算.转置是一元运算转置是一元运算.(5)S为任意集合，则为任意集合，则、为为P(S)上二元运算上二元运算.运算运算为一元运算为一元运算.(6)SS为为S上的所有函数的集合，则合成运算上的所有函数的集合，则合成运算 为为SS上二元运算上二元运算.求反函数不一定是一元运算求反函数不一定是一元运算.5二元与一元运算的表示二元与一元运算的表示1算符算符可以用可以用,等符号表示二元或一元运算，称为算符等符号表示二元或一元运算，称为算符.对二元运算对二元运算，如果，如果x 与与y 运算得到运算得到z，记做，记做xy=z对一元运算对一元运算,x的运算结果记作的运算结果记作 x.2表示二元或一元运算的方法表示二元或一元运算的方法:解析公式和运算表解析公式和运算表公式表示公式表示例例设设R为实数集合，如下定义为实数集合，如下定义R上的二元运算上的二元运算：x,yR,x y=x.那么那么3 4=3，0.5(3)=0.56运算表：表示有穷集上的一元和二元运算运算表：表示有穷集上的一元和二元运算 运算表运算表 二元运算的运算表二元运算的运算表一元运算的运算表一元运算的运算表7 例例2 设设S=P(a,b)，S上的上的 和和 运算运算的运算表如下的运算表如下 运算表的实例运算表的实例8二元运算的性质二元运算的性质定义定义14.2-4设设为为S上的二元运算上的二元运算,(1)若对任意若对任意x,yS 有有xy=yx,则称运算在则称运算在S上满足上满足交换律交换律.(2)若对任意若对任意x,y,zS有有(xy)z=x(yz),则称运算在则称运算在S上满足上满足结结合律合律.(3)若对任意若对任意xS 有有xx=x,则称运算在则称运算在S上满足上满足幂等律幂等律.定义定义14.5-6设设和和 为为S上两个不同的二元运算上两个不同的二元运算,(1)若对任意若对任意x,y,zS有有(x y)z=(xz)(yz)，z(x y)=(zx)(zy),则称则称运算对运算对 运算满足运算满足分配律分配律.(2)若若 和和 都可交换都可交换,且对任意且对任意x,yS有有x(x y)=x，x(xy)=x,则称则称和和 运算满足运算满足吸收律吸收律.9实例实例Z,Q,R分别为整数、有理数、实数集；分别为整数、有理数、实数集；Mn(R)为为n阶实阶实矩阵集合矩阵集合,n 2；P(B)为幂集；为幂集；AA为从为从A到到A的函数集，的函数集，|A|2集合集合运算运算交交换换律律结结合律合律幂幂等律等律Z,Q,R普通加法普通加法+普通乘法普通乘法 有有有有有有有有无无无无Mn(R)矩矩阵阵加法加法+矩矩阵阵乘法乘法 有有无无有有有有无无无无P(B)并并 交交 相对补相对补 对称差对称差 有有有有无无有有有有有有无无有有有有有有无无无无AA函数复合函数复合 无无有有无无10集合集合运算运算分配律分配律吸收律吸收律Z,Q,R普通加法普通加法+与乘法与乘法 对对+可分配可分配+对对 不分配不分配无无Mn(R)矩矩阵阵加法加法+与乘法与乘法 对对+可分配可分配+对对 不分配不分配无无P(B)并并 与交与交 对对 可分配可分配 对对 可分配可分配有有交交 与与对对称差称差 对对 可分配可分配无无实例实例Z,Q,R分别为整数、有理数、实数集；分别为整数、有理数、实数集；Mn(R)为为n阶实阶实矩阵集合矩阵集合,n 2；P(B)为幂集；为幂集；AA为从为从A到到A的函数集，的函数集，|A|211特异元素：单位元、零元特异元素：单位元、零元定义定义14.7-9设设为为S上的二元运算上的二元运算,(1)如果存在如果存在el(或或er)S，使得对任意，使得对任意xS 都有都有 elx=x(或或xer=x)，则称则称el(或或er)是是S中关于中关于运算的运算的左左(或或右右)单位元单位元.若若eS关于关于运算既是左单位元又是右单位元，则称运算既是左单位元又是右单位元，则称e为为S上上关于关于运算的运算的单位元单位元.单位元也叫做单位元也叫做幺元幺元.(2)如果存在如果存在 l(或或 r)S，使得对任意，使得对任意xS 都有都有 l x=l(或或x r=r)，则称则称 l(或或 r)是是S 中关于中关于运算的运算的左左(或或右右)零元零元.若若 S 关于关于运算既是左零元又是右零元，则称运算既是左零元又是右零元，则称 为为S上关上关于运算于运算的的零元零元.12可逆元素和逆元可逆元素和逆元(3)设设为为S上的二元运算上的二元运算,令令e为为S中关于运算中关于运算 的单位元的单位元.对于对于xS，如果存在，如果存在yl(或或yr)S使得使得 ylx=e（或（或xyr=e）则称则称yl(或或yr)是是x的的左逆元左逆元（或（或右逆元右逆元）.关于关于运算，若运算，若yS 既是既是x 的左逆元又是的左逆元又是x 的右逆元，则称的右逆元，则称y为为x的的逆元逆元.如果如果x 的逆元存在，就称的逆元存在，就称x 是是可逆的可逆的.可以证明：可以证明：l对于给定二元运算，单位元或零元如果存在，则是唯一的对于给定二元运算，单位元或零元如果存在，则是唯一的.l对于可结合的二元运算，给定元素若存在逆元，则是唯一对于可结合的二元运算，给定元素若存在逆元，则是唯一的逆元的逆元13实例实例集合集合运算运算单位元单位元零元零元逆元逆元Z,Q,R普通加法普通加法+普通乘法普通乘法 01无无0 x逆元逆元 xx逆元逆元x 1(x 1 给定集合给定集合)Mn(R)矩矩阵阵加法加法+矩矩阵阵乘法乘法 n阶全阶全0矩阵矩阵n阶单位矩阵阶单位矩阵无无n阶全阶全0矩阵矩阵X逆元逆元 XX的逆元的逆元X 1（X可逆）可逆）P(B)并并 交交 对称差对称差 BB无无的逆元为的逆元为B的逆元为的逆元为BX的逆元为的逆元为X消去律消去律定定义义14.10设设 为为S上的二元运算，如果上的二元运算，如果对对于任意的于任意的x,y,z S满满足以下条件：足以下条件：(1)若若x y=x z且且x，则则y=z；(2)若若y x=z x且且x，则则y=z；称称运算运算满满足足消去律消去律，其中，其中(1)为为左消去律左消去律，(2)为为右消去律右消去律l注意被消去的注意被消去的x 不能是运算的零元不能是运算的零元 整数集合上的加法和乘法整数集合上的加法和乘法满满足消去律足消去律P(S)上的并和交一般不上的并和交一般不满满足消去律足消去律.对对称差运算称差运算 满满足消去律足消去律,A,B,C P(S)，都有，都有 A B=A CB=C B A=C AB=C1415代数系统代数系统定义定义14.11非空集合非空集合S和和S上上k个一元或二元运算个一元或二元运算f1,f2,fk组组成的系统称为成的系统称为代数系统代数系统,简称代数，记做简称代数，记做.实例：实例：(1),是代数系统，是代数系统，+和和分别表示普通分别表示普通加法和乘法加法和乘法.(2)是代数系统，和是代数系统，和分别表示分别表示n 阶阶(n2)实矩实矩阵的加法和乘法阵的加法和乘法.(3)是代数系统，是代数系统，Zn0,1,n-1，和和 分别表示分别表示模模n的加法和乘法，对于的加法和乘法，对于x,yZn，x y=(xy)modn，x y=(xy)modn(4)是代数系统，是代数系统，和和 为并和交，为并和交，为绝对补为绝对补16代数系统的成分与表示代数系统的成分与表示构成代数系统的成分：构成代数系统的成分：l集合（也叫载体，规定了参与运算的元素）集合（也叫载体，规定了参与运算的元素）l运算（这里只讨论有限个二元和一元运算）运算（这里只讨论有限个二元和一元运算）l代数常数（通常是与运算相关的特异元素：如单位元等）代数常数（通常是与运算相关的特异元素：如单位元等）研究代数系统时，如果把运算具有它的特异元素也作为系统研究代数系统时，如果把运算具有它的特异元素也作为系统的性质之一，那么这些特异元素可以作为系统的成分，叫做的性质之一，那么这些特异元素可以作为系统的成分，叫做代数常数代数常数.例如：代数系统例如：代数系统：集合：集合Z,运算运算+,代数常数代数常数0代数系统代数系统：集合：集合P(S),运算运算和和，无代数常数，无代数常数17代数系统的表示代数系统的表示(1)列出所有的成分：集合、运算、代数常数（如果存在）列出所有的成分：集合、运算、代数常数（如果存在）如如,(2)列出集合和运算，在规定系统性质时不涉及具有单位元列出集合和运算，在规定系统性质时不涉及具有单位元的性质（无代数常数）的性质（无代数常数）如如,(3)用集合名称简单标记代数系统用集合名称简单标记代数系统在前面已经对代数系统作了说明的前提下使用在前面已经对代数系统作了说明的前提下使用如代数系统如代数系统Z,P(B)18同类型与同种代数系统同类型与同种代数系统定义定义14.12(1)如果两个代数系统中运算的个数相同，对应运算的元数相如果两个代数系统中运算的个数相同，对应运算的元数相同，且代数常数的个数也相同，则称它们是同，且代数常数的个数也相同，则称它们是同类型的同类型的代数代数系统系统.(2)如果两个同类型的代数系统规定的运算性质也相同，则称如果两个同类型的代数系统规定的运算性质也相同，则称为为同种的同种的代数系统代数系统.例如例如V1=,V2=,为为n 阶全阶全0矩阵，矩阵，E为为n 阶单位矩阵阶单位矩阵,V3=lV1,V2,V3是同类型的代数系统，它们都含有是同类型的代数系统，它们都含有2个二元运算个二元运算,2个代数常数个代数常数.lV1,V2是同种的代数系统，是同种的代数系统，V1,V2与与V3不是同种的代数系统不是同种的代数系统19V1V2V3+可交可交换换、可、可结结合合可交可交换换、可、可结结合合+满足消去律满足消去律满足消去律满足消去律对对+可分配可分配+对对不可分配不可分配+与与没有吸收律没有吸收律+可交可交换换、可、可结结合合可交可交换换、可、可结结合合+满足消去律满足消去律不满足消去律不满足消去律对对+可分配可分配+对对不可分配不可分配+与与没有吸收律没有吸收律可交可交换换、可、可结结合合可交换、可结合可交换、可结合不满足消去律不满足消去律不满足消去律不满足消去律对对可分配可分配对对可分配可分配与与满足吸收律满足吸收律运算性质比较运算性质比较2014.2几个典型的代数系统几个典型的代数系统主要内容主要内容l半群、独异点与群半群、独异点与群l环与域环与域l格与布尔代数格与布尔代数21半群、独异点与群的定义半群、独异点与群的定义定义定义14.13(1)设设V=是代数系统，是代数系统，为二元运算，如果为二元运算，如果 运算是可运算是可结合的，则称结合的，则称V为为半群半群.(2)设设V=是半群，若是半群，若eS是关于是关于 运算的单位元，则称运算的单位元，则称V 是是含幺半群含幺半群，也叫做，也叫做独异点独异点.有时也将独异点有时也将独异点V 记作记作V=.(3)设设V=是独异点，是独异点，e S关于关于 运算的单位元，若运算的单位元，若 a S，a 1 S，则称，则称V是是群群.通常将群记作通常将群记作G.22实例实例例例1(1),都是半群，都是半群，+是普通加是普通加法法.这些半群中除这些半群中除外都是独异点外都是独异点(2)设设n是大于是大于1的正整数，的正整数，和和都是半都是半群，也都是独异点，其中群，也都是独异点，其中+和和分别表示矩阵加法和矩阵分别表示矩阵加法和矩阵乘法乘法(3)为半群，也是独异点，其中为半群，也是独异点，其中 为集合对称差运算为集合对称差运算(4)为半群，也是独异点，其中为半群，也是独异点，其中Zn=0,1,n 1，为模为模n加法加法(5)为半群，也是独异点，其中为半群，也是独异点，其中为函数的复合运算为函数的复合运算(6)为半群，其中为半群，其中R*为非零实数集合，为非零实数集合，运算定义如运算定义如下：下：x,y R*,xy=y半群：半群：上的上的字代数和语言字代数和语言例例2设设 是有是有穷穷字母表，字母表，k N，定，定义义下述集合：下述集合：k=a1a2ak|ai 是是 上所有上所有长长度度为为k的串的集合的串的集合.当当k=0时时，0=，表示空表示空串串.令令表示表示 上所有有限上所有有限长长度的串的集合，度的串的集合，+=*则则表示表示 上所有上所有长长度至少度至少为为1的有限串的集合的有限串的集合.在在*上可以定上可以定义义串的串的连连接运算，接运算，1,2 *，1=a1a2am,2=b1b2bn有有 1 2=a1a2amb1b2bn显显然然*关于关于连连接运算构成一个独异点接运算构成一个独异点,称称为为 上的字代数上的字代数.上上的的语语言言L就是就是*的一个子集的一个子集.23群码群码例例3某二某二进进制制码码的的码码字字x=x1x2x7由由7位构成，位构成，其中其中x1,x2,x3和和x4为为数据位数据位,x5,x6和和x7为为校校验验位，且位，且满满足：足：x5=x1 x2 x3 x6=x1 x2 x4x7=x1 x3 x4这这里的里的 是模是模2加法加法.设设G为为所有所有码码字构成的集合，在字构成的集合，在G上定上定义义二元运算如下：二元运算如下：x,y G,x y=z1z2.z7,zi=xi yi,i=1,2,7.那么那么构成群构成群.这样这样的的码码称称为为群群码码2425群的相关概念及子群群的相关概念及子群有限群有限群：若群：若群G是有是有穷穷集，集，则则称称G是有限群，否是有限群，否则则称称为为无限群无限群群群G的的阶阶：群：群G含有的元素数，有限群含有的元素数，有限群G的的阶记阶记作作|G|.交交换换群群或或阿阿贝贝尔尔(Abel)群群：群中运算可交：群中运算可交换换实实例：例：和和是无限群，是无限群，是是n阶阶群群上述所有的群都是交上述所有的群都是交换换群，但群，但n阶阶（n 2）实实可逆矩可逆矩阵阵的集合的集合（是（是Mn(R)的真子集）关于矩的真子集）关于矩阵阵乘法构成的群是非交乘法构成的群是非交换换群群子群子群：群：群G的非空子集的非空子集H关于群的运算构成群，称关于群的运算构成群，称为为G的子群的子群.实实例：例：H=nZ=nk|k Z，n为给为给定自然数，是定自然数，是的子群的子群.当当n=0和和1时时，子群分子群分别别是是0和和Z，称，称为为平凡子群平凡子群；2Z由能被由能被2整除的全体整数构成，也是子群整除的全体整数构成，也是子群.群的直积群的直积定定义义14.14设设G1=和和G2=是群，是群，和和 分分别为别为它它们们的二元运算，在集合的二元运算，在集合A B上定上定义义新的二元运算新的二元运算，,A B，有，有=称称G=为为G1与与G2的的直直积积，记记作作G1 G2.例例4G1,G2分分别为别为模模2加和模加和模3加群，它加群，它们们的直的直积积运算运算26 27环与域环与域 定义定义10.15设设是代数系统，是代数系统，+和和是二元运算是二元运算.如果满足如果满足以下条件以下条件:(1)构成交换群构成交换群(2)构成半群构成半群(3)运算关于运算关于+运算适合分配律运算适合分配律则称则称是一个是一个环环.通常称通常称+运算为环中的运算为环中的加法加法，运算为环中的运算为环中的乘法乘法.定义定义14.16设设是环，若是环，若(1)环中乘法环中乘法可交换；可交换；(2)R中至少含有两个元素中至少含有两个元素.且且 aR 0，都有，都有a1R；则称则称R是是域域.l0指加法单位元，指加法单位元，a1指指a的乘法逆元的乘法逆元28环与域的实例环与域的实例例例5(1)整数集、有理数集、实数集和复数集关于普通的加法和整数集、有理数集、实数集和复数集关于普通的加法和乘法构成环，分别称为乘法构成环，分别称为整数环整数环Z，有理数环有理数环Q，实数环实数环R 和和复数环复数环C.Q、R和和C也称为有理数域、也称为有理数域、实数域实数域、复数复数域域.(2)n(n2)阶实矩阵的集合阶实矩阵的集合Mn(R)关于矩阵的加法和乘法构关于矩阵的加法和乘法构成环，称为成环，称为n 阶实矩阵环阶实矩阵环.(3)集合的幂集集合的幂集P(B)关于集合的对称差运算和交运算构成环关于集合的对称差运算和交运算构成环.(4)设设Zn0,1,.,n1，和和 分别表示模分别表示模n的加法和乘的加法和乘法，则法，则构成环，称为构成环，称为模模n的整数环的整数环.当当n为素数为素数时时Zn构成域构成域.29格的定义与性质格的定义与性质 定义定义14.17设设是偏序集，如果是偏序集，如果 x,y S，x,y都有最小上都有最小上界和最大下界，则称界和最大下界，则称S关于偏序关于偏序 作成一个作成一个格格.求求x,y最小上界和最大下界看成最小上界和最大下界看成x 与与y 的二元运算的二元运算和和，例例6设设n是正整数，是正整数，Sn是是n的正因子的集合的正因子的集合.D为整除关系，则为整除关系，则偏序集偏序集构成格构成格.x,ySn，xy是是lcm(x,y)，即，即x与与y的的最小公倍数最小公倍数.xy是是gcd(x,y)，即，即x与与y的最大公约数的最大公约数.30图2例例7判断下列偏序集是否构成格，并说明理由判断下列偏序集是否构成格，并说明理由.(1)，其中，其中P(B)是集合是集合B的幂集的幂集.(2)，其中，其中Z是整数集，是整数集，为小于或等于关系为小于或等于关系.(3)偏序集的哈斯图分别在下图给出偏序集的哈斯图分别在下图给出.实例实例(1)幂集格幂集格.x,yP(B)，xy就是就是xy，xy就是就是xy.(2)是格是格.x,yZ，xy=max(x,y)，xy=min(x,y)，(3)都不是格都不是格.可以找到两个结点缺少最大下界或最小上界可以找到两个结点缺少最大下界或最小上界31格的性质：算律格的性质：算律设设是格是格,则运算则运算和和适合交换律、结合律、幂等律适合交换律、结合律、幂等律和吸收律和吸收律,即即(1)a,bL有有 ab=ba,ab=ba(2)a,b,cL有有(ab)c=a(bc),(ab)c=a(bc)(3)aL有有aa=a,aa=a(4)a,bL有有a(ab)=a,a(ab)=a32格作为代数系统的定义格作为代数系统的定义设设是具有两个二元运算的代数系统是具有两个二元运算的代数系统,若对于若对于 和和运算运算适合交换律、结合律、吸收律适合交换律、结合律、吸收律,则可以适当定义则可以适当定义S中的偏序中的偏序,使得使得构成格构成格,且且 a,bS 有有ab=a b,ab=ab.格的等价定义：设格的等价定义：设是代数系统是代数系统,和和是二元运算是二元运算,如如果果 和和满足交换律、结合律和吸收律满足交换律、结合律和吸收律,则则构成格构成格.33分配格、有补格与布尔代数分配格、有补格与布尔代数 定义定义14.18设设是格是格,若若 a,b,cL,有有a(bc)=(ab)(ac)a(bc)=(ab)(ac)则称则称L为为分配格分配格.l注意：可以证明以上两个条件互为充分必要条件注意：可以证明以上两个条件互为充分必要条件L1和和L2是分配格是分配格,L3和和L4不是分配格不是分配格.称称L3为为钻石格钻石格,L4为为五角格五角格.实例实例34分配格的判别分配格的判别分配格的判别：设分配格的判别：设L 是格是格,则则L 是分配格当且仅当是分配格当且仅当L 不含有不含有与钻石格或五角格同构的子格与钻石格或五角格同构的子格.l小于五元的格都是分配格小于五元的格都是分配格.l任何一条链都是分配格任何一条链都是分配格.例例6 说明图中的格是否为分配格说明图中的格是否为分配格,为什么？为什么？解解都不是分配格都不是分配格.a,b,c,d,e 是是L1的子格的子格,同构于钻石格同构于钻石格a,b,c,e,f 是是L2的子格的子格,同构于五角格；同构于五角格；a,c,b,e,f 是是L3的子格的子格同构于钻石格同构于钻石格.35有补格的定义有补格的定义定义定义14.19设设L是格是格,(1)若存在若存在aL使得使得 xL有有a x,则称则称a为为L的的全下界，全下界，记记为为0；若存在；若存在bL使得使得 xL有有x b,则称则称b为为L的的全上界全上界，记为，记为1.(2)若若L存在全下界和全上界存在全下界和全上界,则称则称L 为为有界格有界格,一般将有界一般将有界格格L记为记为.定义定义14.20设设是有界格是有界格,aL,若存在若存在bL使得使得ab=0和和ab=1成立成立,则称则称b是是a的的补元补元.定义定义14.21设设是有界格是有界格,若若L中所有元素都有补中所有元素都有补元存在元存在,则称则称L为为有补格有补格.36补元的性质补元的性质注意：注意：l在任何有界格中在任何有界格中,全下界全下界0与全上界与全上界1互补互补.l对于一般元素对于一般元素,可能存在补元可能存在补元,也可能不存在补元也可能不存在补元.l如果存在补元如果存在补元,可能是惟一的可能是惟一的,也可能是多个补元也可能是多个补元.l对于有界分配格对于有界分配格,如果元素存在补元如果元素存在补元,一定是惟一的一定是惟一的.37有界格中的补元及实例有界格中的补元及实例例例7L1：a 与与c 互补互补,a 为全下界为全下界,c为全上界为全上界,b 没有补元没有补元.L2：a 与与d 互补互补,a 为全下界为全下界,d 为全上界为全上界,b与与c互补互补.L3：a 与与e 互补互补,a 为全下界为全下界,e 为全上界为全上界,b 的补元是的补元是c 和和d;c 的补元是的补元是b 和和d;d 的补元是的补元是b 和和c.L4：a 与与e 互补互补,a 为全下界为全下界,e 为全上界为全上界,b 的补元是的补元是c 和和d;c 的补元是的补元是b;d 的补元是的补元是b.L2,L3和和L4是有补格是有补格,L1不是有补格不是有补格.38布尔代数的定义与实例布尔代数的定义与实例定义定义14.22 如果一个格是有补分配格如果一个格是有补分配格,则称它为布尔格或布则称它为布尔格或布尔代数尔代数.布尔代数标记为布尔代数标记为,为求补运算为求补运算.例例8设设S110=1,2,5,10,11,22,55,110是是110的正因子集合，的正因子集合，gcd表示求最大公约数的运算，表示求最大公约数的运算，lcm表示求最小公倍数的运算，表示求最小公倍数的运算，问问是否构成布尔代数？为什么？是否构成布尔代数？为什么？解解(1)不难验证不难验证S110关于关于gcd和和lcm运算构成格运算构成格.(略略)(2)验证分配律验证分配律 x,y,zS110有有gcd(x,lcm(y,z)=lcm(gcd(x,y),gcd(x,z)(3)验证它是有补格验证它是有补格,1作为作为S110中的全下界中的全下界,110为全上界为全上界,1和和110互为补元互为补元,2和和55互为补元互为补元,5和和22互为补元互为补元,10和和11互为补元互为补元,从而证明了从而证明了为布尔代数为布尔代数.39实例实例例例9设设B为任意集合为任意集合,证明证明B的幂集格的幂集格构成布尔代数构成布尔代数,称为集合代数称为集合代数.证证(1)P(B)关于关于和和构成格构成格,因为因为和和运算满足交换律运算满足交换律,结合律和吸收律结合律和吸收律.(2)由于由于和和互相可分配互相可分配,因此因此P(B)是分配格是分配格.(3)全下界是空集全下界是空集,全上界是全上界是B.(4)根据绝对补的定义根据绝对补的定义,取全集为取全集为B,xP(B),x是是x的补元的补元.从而证明从而证明P(B)是有补分配格是有补分配格,即布尔代数即布尔代数.l有限布尔代数含有有限布尔代数含有2n个元素个元素.代数系统的同构与同态代数系统的同构与同态定定义义14.23设设V1=和和V2=是同是同类类型的代数系型的代数系统统，f：AB，且，且 x,y A有有f(x y)=f(x)f(y)，则则称称f是是V1到到V2的的同同态态映射映射，简简称同称同态态.f若是若是单单射，称射，称为为单单同同态态；若是；若是满满射，称射，称为为满满同同态态(V2是是V1的的同同态态像，像，记记作作V1 V2）；若是双射，称）；若是双射，称为为同构同构，记记作作V1 V2.V到到V的同的同态态f 称称为为自同自同态态.类类似地可以定似地可以定义单义单自同自同态态、满满自自同同态态和自同构和自同构.同同态态性性质质：设设f 是是V1=到到V2的同的同态态映射，映射，(1)若若 运算具有交运算具有交换换律、律、结结合律、合律、幂幂等律等，那么在等律等，那么在f(V1)中中 运算也具有相同的算律（注意，消去律可能有例外）运算也具有相同的算律（注意，消去律可能有例外）.(2)f(e1)=e2，f(1)=2，f(x 1)=f(x)140实例实例例例10(1)V1=,V2=Z为为整数集合，整数集合，+为为普通加普通加法；法；Zn=0,1,n 1，为为模模n加加.令令 f：ZZn，f(x)=(x)modn f 是是V1到到V2的的满满同同态态(2)设设V1=,V2=，R和和R*分分别为实别为实数集与非零数集与非零实实数集，数集，+和和分分别别表示普通加法与乘法令表示普通加法与乘法令f：RR*，f(x)=ex f 是是V1到到V2的的单单同同态态.(3)设设V=，Z为为整数集，整数集，+为为普通加法普通加法.a Z，令，令 fa：ZZ，fa(x)=ax，fa是是V的自同的自同态态.f0为为零同零同态态；当；当a=1时时，称，称fa为为自同构；自同构；除此之外其他的除此之外其他的fa都是都是单单自同自同态态.4142第十四章第十四章 习题课习题课主要内容主要内容l代数系统的构成：非空集合、封闭的二元和一元运算、代代数系统的构成：非空集合、封闭的二元和一元运算、代数常数数常数 l二元运算性质和特异元素：交换律、结合律、幂等律、分二元运算性质和特异元素：交换律、结合律、幂等律、分配律、吸收律、单位元、零元、可逆元和逆元配律、吸收律、单位元、零元、可逆元和逆元l同类型的与同种的代数系统、积代数同类型的与同种的代数系统、积代数l半群、独异点与群、环与域、格与布尔代数的定义半群、独异点与群、环与域、格与布尔代数的定义l代数系统的同态与同构代数系统的同态与同构43基本要求基本要求l判断给定集合和运算能否构成代数系统判断给定集合和运算能否构成代数系统l判断给定二元运算的性质判断给定二元运算的性质l求二元运算的特异元素求二元运算的特异元素l计算积代数计算积代数l判断或证明给定集合和运算是否构成半群、独异点、群、判断或证明给定集合和运算是否构成半群、独异点、群、环、域、格、布尔代数环、域、格、布尔代数l判断函数是否为同态映射和同构映射判断函数是否为同态映射和同构映射44练习练习11设设 运算为运算为Q上的二元运算，上的二元运算，x,y Q,x y=x+y+2xy,(1)判断判断 运算是否满足交换律和结合律，并说明理由运算是否满足交换律和结合律，并说明理由.(2)求出求出 运算的单位元、零元和所有可逆元素的逆元运算的单位元、零元和所有可逆元素的逆元.(1)运算可交换，可结合运算可交换，可结合.任取任取x,y Q,x y=x+y+2xy=y+x+2yx=y x,任取任取x,y,z Q,(x y)z=(x+y+2xy)+z+2(x+y+2xy)z=x+y+z+2xy+2xz+2yz+4xyz x(y z)=x+(y+z+2yz)+2x(y+z+2yz=x+y+z+2xy+2xz+2yz+4xyz45(2)设设 运算的单位元和零元分别为运算的单位元和零元分别为e 和和 ，则，则对于任对于任意意x 有有x e=x 成立，即成立，即 x+e+2xe=x e=0由于由于 运算可交换，所以运算可交换，所以0是幺元是幺元.对于任意对于任意x 有有x =成立，即成立，即x+2x=x+2x =0=1/2给定给定x，设，设x 的逆元为的逆元为y,则有则有x y=0成立，即成立，即 x+y+2xy=0(x 1/2)因此当因此当x 1/2时时，是是x的逆元的逆元.解答解答462下面是三个运算表下面是三个运算表(1)说说明那些运算是可交明那些运算是可交换换的、可的、可结结合的、合的、幂幂等的等的.(2)求出每个运算的单位元、零元、所有可逆元素的逆元求出每个运算的单位元、零元、所有可逆元素的逆元练习练习247解解答解答(1)*满足交换律，满足结合律，不满足幂等律满足交换律，满足结合律，不满足幂等律.不满足交换律，满足结合律，满足幂等律不满足交换律，满足结合律，满足幂等律.满足交换律，满足结合律，不满足幂等律满足交换律，满足结合律，不满足幂等律.(2)*的单位元为的单位元为b，没有零元，没有零元，a 1=c,b 1=b,c 1=a 的单位元和零元都不存在，没有可逆元素的单位元和零元都不存在，没有可逆元素.的单位元为的单位元为a，零元为，零元为c，a 1=a，b,c不是可逆元素不是可逆元素.说明：关于结合律的判断说明：关于结合律的判断需要针对运算元素的每种选择进行验证，若需要针对运算元素的每种选择进行验证，若|A|=n，一般需要，一般需要验证验证n3个等式个等式.单位元和零元不必参与验证单位元和零元不必参与验证.通过对具体运算性质的分析也可能简化验证的复杂性通过对具体运算性质的分析也可能简化验证的复杂性.48练习练习33.判断下列集合和运算是否构成半群、独异点和群判断下列集合和运算是否构成半群、独异点和群.(1)a是正整数，是正整数，G=an|n Z,运算是普通乘法运算是普通乘法.(2)Q+是正有理数集，运算为普通加法是正有理数集，运算为普通加法.(3)一元实系数多项式的集合关于多项式加法一元实系数多项式的集合关于多项式加法.解解(1)是半群、独异点和群是半群、独异点和群(2)是半群但不是独异点和群是半群但不是独异点和群(3)是半群、独异点和群是半群、独异点和群方法：根据定义验证，注意运算的封闭性方法：根据定义验证，注意运算的封闭性494.判断下列集合和给定运算是否构成环和域判断下列集合和给定运算是否构成环和域,如果不构成如果不构成,说说明理由明理由.(1)A=a+bi|a,bQ,其中其中i2=1,运算为复数加法和乘法运算为复数加法和乘法.(2)A=2z+1|zZ,运算为实数加法和乘法运算为实数加法和乘法(3)A=2z|zZ,运算为实数加法和乘法运算为实数加法和乘法(4)A=x|x0 xZ,运算为实数加法和乘法运算为实数加法和乘法.(5),运算为实数加法和乘法解解(1)是环是环,也是域也是域.(2)不是环不是环,因为关于加法不封闭因为关于加法不封闭.(3)是环是环,但不是域但不是域,因为乘法没有么元因为乘法没有么元.(4)不是环不是环,因为正整数关于加法的负元不存在因为正整数关于加法的负元不存在.(5)不是环不是环,因为关于乘法不封闭因为关于乘法不封闭.练习练习450图135判别下述格判别下述格L是否为分配格是否为分配格.L1不是分配格不是分配格,因为它含有与钻石格同构的子格因为它含有与钻石格同构的子格.L2和和L3不是分配格不是分配格,因为它们含有与五角格同构的子格因为它们含有与五角格同构的子格.L1L2 L3练习练习551L1L2 L3图126针对下图，求出每个格的补元并说明它们是否为有补格针对下图，求出每个格的补元并说明它们是否为有补格L1中中,a与与h互为补元互为补元,其他元素没补元其他元素没补元.L2中中,a与与g互为补元互为补元.b的补元为的补元为c,d,f；c的补元为的补元为b,d,e,f；d的补元为的补元为b,c,e；e的补元为的补元为c,d,f；f的补元为的补元为b,c,e.L3中中,a与与h互为补元互为补元,b的补元为的补元为d；c的补元为的补元为d；d的补元为的补元为b,c,g；g的补元为的补元为d.L2与与L3是有补格是有补格.练习练习6527对于以下各题给定的集合和运算判断它们是哪一类代数对于以下各题给定的集合和运算判断它们是哪一类代数系统（半群、独异点、群、环、域、格、布尔代数）系统（半群、独异点、群、环、域、格、布尔代数）,并说并说明理由明理由.(1)S1=1,1/2,2,1/3,3,1/4,4,为普通乘法为普通乘法.(2)S2=a1,a2,.,an,ai,ajS2,ai aj=ai,这里的这里的n 为给定为给定正整数正整数,n1.(3)S3=0,1,为普通乘法为普通乘法.(4)S4=1,2,3,6,x,yS4,x y与与x y分别表示分别表示x 与与y 的最的最小公倍数和最大公约数小公倍数和最大公约数.(5)S5=0,1,为模为模2加法加法,为模为模2乘法乘法.练习练习753解：解答解答(1)不是代数系统不是代数系统,因为乘法不封闭因为乘法不封闭,例如例如4 4=16.(2)是半群但不是独异点是半群但不是独异点,因为因为 运算满足结合律运算满足结合律,但是没有单但是没有单位元位元.(3)是独异点但不是群是独异点但不是群.因为因为 运算满足结合律运算满足结合律,单位元是单位元是1,可可是是0没有乘法逆元没有乘法逆元.(4)是格是格,也是布尔代数也是布尔代数.因为这两个运算满足交换律和分配因为这两个运算满足交换律和分配律；求最小公倍数运算的单位元是律；求最小公倍数运算的单位元是1,求最大公约数运算求最大公约数运算的单位元是的单位元是6,满足同一律；两个运算满足补元律满足同一律；两个运算满足补元律.(5)是域是域.对于模对于模n 的环的环Zn,当当n为素数时构成域为素数时构成域.54练习练习88.设设G为非为非0实数集实数集R*关于普通乘法构成的代数系统，关于普通乘法构成的代数系统，判断下述函数是否为判断下述函数是否为G的自同态？如果不是，说明理由的自同态？如果不是，说明理由.如果是，判别它们是否为单同态、满同态、同构如果是，判别它们是否为单同态、满同态、同构.(1)f(x)=|x|+1(2)f(x)=|x|(3)f(x)=0(4)f(x)=255解答解答解解 (1)不是同态不是同态,因为因为f(2 2)=f(4)=5,f(2)f(2