离散的课件第三篇代数系统

离散的课件第三篇代数系统第1页，共80页，2023年，2月20日，星期一第5章代数系统概述5.1二元运算、一元运算及其性质二元运算设S为集合,函数f：S×S→S称为S上的二元运算,简称为二元运算.一个运算是否为集合S上的二元运算主要考虑两点：(1)、S中任何两个元素都可以进行这种运算,且运算的结果是唯一的.(2)、S中任何两个元素的运算结果都属于S,即S对该运算是封闭的.

第2页，共80页，2023年，2月20日，星期一例如f：N×N→N,f(<x,y>)=x+y就是自然数集合N上的二元运算,即普通的加法运算普通的乘法也是N上的二元运算，但减法、除法不是N上的二元运算集合的交、并、差、对称差运算都是某幂集P（A）上的二元运算命题逻辑中求∧、∨、→、是命题公式全体所成集合上的二元运算

第3页，共80页，2023年，2月20日，星期一例设A={x︱x=2n,nN},则在集合A上通常的乘法运算是A上的二元运算？加法运算呢？解：对任意的x，yA,

设x=2r，y=2s，r,sN

x·y=2r·2s=2r+sA,所以，A对乘法封闭，且运算结果唯一，所以，此运算是A上的二元运算但加法不是A上的二元运算，事实上取x=2，y=22A,则

X+y=2+4=6A，所以，A对加法运算不封闭.第4页，共80页，2023年，2月20日，星期一对于一元运算f：S→S，如果x的运算结果是y,则f(x)=y,利用运算符，如⊕，简记为⊕

x=y

如求A的补集记成~A，或表示二元或一元运算的方法

(1)、解析公式法所谓解析公式就是使用算符和表达式给出参与运算的元素和运算结果之间的映射规则.例如：f：N×N→N，f(<m,n>)=2m+n.第5页，共80页，2023年，2月20日，星期一一元运算设S为集合,函数f：S→S称为S上的一元运算,简称为一元运算.

例如，求一个数的相反数就是R上的一个一元运算.

即f:R→R，f(x)=－x求实数的绝对值是R上的一元运算求复数的共轭复数是复数集上的一个一元运算.求集合的补集也是一元运算.命题逻辑中求﹁

是命题公式全体所成集合上的一元运算第6页，共80页，2023年，2月20日，星期一（2）、运算表法对有穷集合上的一元和二元运算，还可以有运算表给出.例S={a,b,c,d},S上的二元运算°如下表定义

°abcdaadccbcabdcaacbdddab

第7页，共80页，2023年，2月20日，星期一二元运算的性质设＊为S上的二元运算,(1)、如果对于任意的x,y∈S,有x＊y=y＊x,则称运算＊是可交换的，或称＊在S上满足交换律.(2)、如果对于任意的x,y,z∈S有(x＊y)＊z=x＊(y＊z),则称运算＊是可结合的，或称运算＊在S上满足结合律.(3)、如果对于任意的x∈S有x＊x=x,则称运算＊在S上满足幂等律.第8页，共80页，2023年，2月20日，星期一(4)、设°

和＊为S上两个不同的二元运算,如果对于任意的x,y,z∈S有

x＊(

y°z)=(x＊y)°(x＊

z)(

y°z)＊

x=(y＊

x)°

(z°x),

则称运算＊对运算°是可分配的，也称＊对°满足分配律.（书上有错P.99）

(5)、如果°和＊都可交换,并且对于任意的x,y∈S，有x＊(x°y)=xx

°(x＊

y)=x,

则称°和＊运算满足吸收律.（书上有错P.99）第9页，共80页，2023年，2月20日，星期一

二元运算中的特殊元素1、幺元（单位元）设＊为S上的二元运算,e∈S，如果对任何x∈S

都有e

＊

x=x＊e=

x，则称e

是关于运算＊的幺元.例在自然数集N上，0是加法的单位元，1是乘法的单位元。例幂集P(S)上，并运算∪的单位元是Φ

，交运算∩的单位元是S，对称差运算⊕的单位元是Φ

第10页，共80页，2023年，2月20日，星期一例考虑非零实数全体所成集合R*，如下定义的二元运算°

：对任意的a,b∈R*,a°b=a则运算没有单位元定理设＊为S上的二元运算,则S中关于运算＊至多有一个幺元.第11页，共80页，2023年，2月20日，星期一2、零元设＊为S上的二元运算,θ∈S(书上是z,要改)

如果对任意的x∈S都有θ＊x=x＊θ

=θ则称θ

是S中关于运算＊的零元例如，自然数集合上0是普通乘法的零元，而加法没有零元.

幂集P(S)上∪运算的零元是S，∩运算的零元是Φ，而对称差运算⊕没有零元.若不然，设θ

是零元，则对任意的A∈P(S)第12页，共80页，2023年，2月20日，星期一A⊕θ=θ⊕A=θ由A⊕θ=θ

，两边同时右运算θ,

得（A⊕θ）⊕θ=θ⊕θ

，即A⊕（θ⊕θ）=Φ，

A⊕Φ=Φ，

A

=Φ，与A的任意性矛盾.第13页，共80页，2023年，2月20日，星期一定理设＊为S上的二元运算,则S中关于运算＊至多有一个零元.3、逆元设＊为S上的二元运算,e是S关于运算＊的幺元，对于x∈S,若存在y

∈S使得y

＊x=x＊y=e，则称y

是x的逆元,并称x是可逆的

x的逆元记为x-1定理设＊为S上的二元运算,如果＊可结合，则对于S中每个元素x,x关于＊至多有一个逆元.

第14页，共80页，2023年，2月20日，星期一4、消去律（书上有错P.100)设°为S上的二元运算，如果对于任意的x,y,z∈S，满足以下条件：

(1)、若x°y=x°z且x≠θ，都有y=z;(2)、若y°x=z°x且x≠θ，都有y=z;则称°运算满足消去律.其中(1)称为左消去律，(2)称为右消去律.例设A={1,2,…,10},A上二元运算

°

定义如下:对任意的a,b∈A,a°b=max{a,b}.

求A的幺元、零元、可逆元第15页，共80页，2023年，2月20日，星期一P.100例5.10（题目及解法有改）整数集Z上二元运算＊定义为:x,y∈Z,x＊y=x+y－xy.指出该运算的性质，并求出它的幺元、零元、所有可逆元的逆元.解：

x,y∈Z,x＊y=x+y－xy=y+x–yx=y＊x,

所以＊满足交换律.

第16页，共80页，2023年，2月20日，星期一x,y,z∈Z,(x＊y)＊z=(x+y–xy)＊z=(x+y–xy)+z–(x+y–xy)z=x+y+z–xy–xz–yz+xyzx＊(y＊z)=x＊(y+z–yz)=x+(y+z–yz)–x(y+z–yz)=x+y+z–xy–xz–yz+xyz

即(x＊y)＊z=x＊(y＊z)所以，＊满足结合律.第17页，共80页，2023年，2月20日，星期一（＊不满足幂等律）xZ,0＊

x

=

x

＊

0=x+0–x﹒0=x,所以,0为幺元.xZ,1＊x=x＊1=x+1–x﹒1=1所以,1为零元.x,y,zZ,x≠1,若x＊y=x＊z,即x+y–xy=x+z–xzy(1–x)=z(1–x)

y=z.由于运算可交换,所以,运算满足消去律.第18页，共80页，2023年，2月20日，星期一xZ,假设x有逆元，设逆元为y,则x＊y=y＊x=0即x+y–xy=0要使yZ，只有x=2,此时y=2所以，只有2才是可逆元，其逆元为2(书中有错）第19页，共80页，2023年，2月20日，星期一把书中的整数集Z改成有理数集Q，则除了可逆元和逆元外，其它不变.第20页，共80页，2023年，2月20日，星期一从运算表检验运算的性质和特殊元素.交换律、消去律、结合律、幺元、零元、逆元等（P.105.习题3)关于结合律有如下结论：第21页，共80页，2023年，2月20日，星期一

abcd

aabcdbbadcccdabddcba

第22页，共80页，2023年，2月20日，星期一

.

为检验x是否结合元,作表L(x),R(x),其中L(x)表头行元素为运算表中元素x所在的行,

表内元素按所给运算规则算出;

幺元为结合元.

R(x)表头列元素为运算表中元素x所在的列,

表内元素按所给运算规则算出.

x是结合元L(x)表与R(x)表中对应元素相同第23页，共80页，2023年，2月20日，星期一解:上例中a是幺元,只要检验b,c,d

L(b)badcabadcbabcdcdcbadcdab第24页，共80页，2023年，2月20日，星期一

bbadcaabcdddcbaccdab所以,b是结合元.同理,检验得c,d均为结合元,所以运算满足结合律.每个元素的逆元就是自身。R(b)abcd第25页，共80页，2023年，2月20日，星期一设*是集合S上可结合二元运算，xSx的正整数次幂定义为：（1）x1=x（2）xn+1=xn*x（n≥2）可以证明，对任意的正整数n,m有（1）xn*xm=xn+m

（2）（xn）m=xn·m

第26页，共80页，2023年，2月20日，星期一5.2代数系统1、代数系统的定义与实例

设S是非空集合，S和S上k个运算f1,f2,…fk组成的系统称为一个代数系统,也称代数结构，简称代数,记做<S,f1,f2,…fk>.例如：<N,＋>,<Z,＋,·>,<R,＋,·>都是代数系统,其中+和·分别表示普通加法和乘法.<Mn(R),＋,·>是代数系统,其中＋和·分别表示n阶(n≥2)实矩阵的加法和乘法.第27页，共80页，2023年，2月20日，星期一<P(S),∪,∩,~>也是代数系统,其中含有两个二元运算∪和∩以及一个一元运算~.有限代数系统和无限代数系统

第28页，共80页，2023年，2月20日，星期一2、子代数系统(不做要求)

设V=<S,f1,f2,…fk>是代数系统,B是S的非空子集,如果B对f1,f2,…fk

都是封闭的,且B和S含有相同的代数常数,则称<B,f1,f2,…fk>是V的子代数系统,简称子代数。有时将子代数系统简记为B。例如N是<Z,＋>的子代数,因为N对加法运算＋是封闭的。N也是<Z,＋,0>的子代数,因为N对加法运算＋是封闭的,且N中含有代数常数0。N-{0}是<Z,＋>的子代数,但不是<Z,＋,0>的子代数,因为<Z,＋,0>的代数常数0N－{0}。第29页，共80页，2023年，2月20日，星期一5.3代数系统的同态与同构（与书中提法不同）

设V1=<S1，°>，V2=<S2，＊>是同类型的代数系统,如果存在映射f:S1→S2.且对任意的x，y∈S1有f(x°y)=f(x)＊f(y)

则称f是从V1到V2的同态映射,简称同态.为了书写的简便,有时经常省略上述表达式中的算符°

和＊,而简记为f(xy)=f(x)f(y)

但应该记住,该表达式中左边的xy是在V1中的运算,而右边的f(x)f(y)是在V2中的运算.第30页，共80页，2023年，2月20日，星期一单同态、满同态、同构设f是V1=<S1，°>到V2=<S2，＊>的同态映射，(1)若f是满射,则称为满同态.(2)若f是单射的,则称为单同态.(3)若f是双射的,则称为同构,记作V1≌V2.(4)若V1=V2=V,则称是群V的自同态.类似的可以定义满自同态,单自同态和自同构.第31页，共80页，2023年，2月20日，星期一例设V1=<R，+>，V2=<R+，×>

，做R到R+的映射

f:R

→R+，f(x)=3x，则f是V1到V2的同态映射.P.104例5.24V=<R,+>,h:R→R,h(x)=2x

,则h是V上的自同构第32页，共80页，2023年，2月20日，星期一P.104例5.26证明：第33页，共80页，2023年，2月20日，星期一第34页，共80页，2023年，2月20日，星期一第35页，共80页，2023年，2月20日，星期一

同态映射的性质(P.104定理5.6)此定理说明：满同态映射保持运算性质不变和保持元素的对应第36页，共80页，2023年，2月20日，星期一第6章几种典型的代数系统6.1半群、幺半群与群

一、定义

(1)、设V=<S,°>是代数系统,°为二元运算,如果运算是可结合的,则称V为半群.(2)、设V=<S,°>是半群,若e∈S是关于运算的幺元,则称V是幺半群,也叫做独异点.有时也将独异点V记作V=<S,°,e>.（3）、设V=<S,°>是独异点，若S中每一元素在S中都有逆元，则称V是群.

第37页，共80页，2023年，2月20日，星期一例<Z+,+>,<N,+>,<R,+>都是半群,+是普通加法.这些半群中除<Z+,+>外都是幺半群.<P(B),⊕>是半群，也是幺半群，其中⊕是集合的对称差运算.<Zn,⊕>是半群，也是幺半群，其中Zn={0,1,2,…,n-1},⊕是模n加法事实上,第38页，共80页，2023年，2月20日，星期一第39页，共80页，2023年，2月20日，星期一证得<Zn,⊕>是半群.显然,0是幺元,所以,<Zn,⊕>是幺半群.第40页，共80页，2023年，2月20日，星期一设R*为非零实数集合,其上二元运算°定义如下：对任意x,y∈R*,x°y=y，则<R*,°>为半群.第41页，共80页，2023年，2月20日，星期一第42页，共80页，2023年，2月20日，星期一P.108例6.10和6.14综合设∑是字母的有穷集，称为字母表，∑中的有限个字母组成的序列称为∑上的串.对任意串ω，串中字母的个数叫做串的长度，记作︱ω︱.长度为0的串叫空串，记作.令∑*是∑上所有串的集合.∑+=∑*-{}第43页，共80页，2023年，2月20日，星期一如下定义∑*上的二元运算·

(称为连接运算)ω1,ω2∑*,设ω1=vi1vi2…vim,,，ω2=vj1vj2…vjn则ω1·

ω2=vi1vi2…vimvj1vj2…vjn

令V1=<∑*,·

,>,V2=<N,+，0

>,定义h：∑*

→N如下：ω

∑*h（ω)=︱ω︱则h是V1到V2的同态.是满同态，但不是单同态.第44页，共80页，2023年，2月20日，星期一例如，设∑={a，b},则h(a)=1,h(b)=1,不是单射.若∑={a},则h是同构.P.109例6.19实数集合R上全体函数所成集合RR,关于函数加法<RR,+>成群P.109例6.21第45页，共80页，2023年，2月20日，星期一P.109例6.22Klein四元群例某二进制码的码字x=x1x2x3x4x5x6x7由7位构成,其中x1,x2,x3和x4是数据位,x5,x6,和x7是校验位,并且满足x5=x1⊕x2⊕x3,x6=x1⊕x2⊕x4

x7=x1⊕x3⊕x4,这里⊕是模2加法.设G为所有码字构成的集合,在G上定义二元运算。如下第46页，共80页，2023年，2月20日，星期一第47页，共80页，2023年，2月20日，星期一第48页，共80页，2023年，2月20日，星期一有限群、无限群、交换群(阿贝尔群）、平凡群二．群的性质1．群中元素的幂

由于群V=<G,°>中的运算是可结合的,可以定义元素的幂,对任意x∈G,n∈Z，规定：

第49页，共80页，2023年，2月20日，星期一例在群<R*，×>和<R，+>中分别求0.5-1，0.5-2，0.5-3例在<Z3,⊕>中

2-3=（2-1）3=13=1⊕1⊕1=0

而在<Z,+>中，3-5=(3-1)5=(-3)5=(-3)+(-3)+(-3)+(-3)+(-3)=-152、群的阶和群中元素的阶设G是群，G中元素的个数称为G的阶，记为|G|a∈G,使得ak=e成立的最小正整数k称为a的阶（也称为周期），记为|a|=k.这时也称a为k阶元,

若这样的k不存在,则称a为无限阶元.第50页，共80页，2023年，2月20日，星期一例求<Z6,⊕>中各元素的阶3、群中元素的幂运算规则设G为群,则G中的幂运算满足：

a∈G,(a-1)-1=a.a,b∈G,(ab)-1=b-1a-1.a∈G,anam=an+m,n,m∈Z.a∈G,(an)m=anm,n,m∈Z.

若G为交换群,则(ab)n=anbn.第51页，共80页，2023年，2月20日，星期一4、群中方程有唯一解。即设G为群,则对任意a,b∈G,方程ax=b和ya=b在G中有唯一解.5、群中消去律成立。即设G为群,对任意a,b,c∈G,有（1）若ab=ac,则b=c（2）若ba=ca,则b=c第52页，共80页，2023年，2月20日，星期一6.3格和布尔代数一、格作为偏序集的定义

设<S,≤>是偏序集,如果x,yS,{x,y}都有最小上界和最大下界,则称S关于偏序≤作成一个格。由于最小上界和最大下界的唯一性,可以把求{x,y}的最小上界和最大下界看成x与y的二元运算∨和∧,即x∨y,x∧y分别表示x与y的最小上界,最大下界。

x∨y=lub{x,y},x∧y=glb{x,y}

第53页，共80页，2023年，2月20日，星期一P.111—P.115的例6.38即子群、环、域不做要求

第54页，共80页，2023年，2月20日，星期一例（2）偏序集<z+,D>构成格，其中z+是正整数集合，D为整除关系。事实上,x,y∈z+,x∨y=lcm(x,y),即x与y的最小公倍数x∧y=gcd(x,y),即x与y的最大公约数。

第55页，共80页，2023年，2月20日，星期一

说明:

本章中出现的∨和∧符号只代表格中的运算，而不再有其它的含义。

例(1)偏序集<P(S),>是格,其中P(S)是集合S的幂集.事实上,x,y∈P(B),x∨y=x∪y,x∧y=x∩y

称此格为集合S的幂集格.

第56页，共80页，2023年，2月20日，星期一

例(3).<Z,≤>,是格.其中Z是整数集,≤为小于或等于关系.

事实上,x,y∈Z,x∨y=max(x,y),x∧y=min(x,y)

例（4）P.115例6.41

偏序集<{1,2,3,12,18,36},D>不是格.因为{2，3}没有最小上界，同样{12，18}没有最大下界第57页，共80页，2023年，2月20日，星期一下列哈斯图所表示的偏序集都不是格abcdef(a)ecbda(b)第58页，共80页，2023年，2月20日，星期一cabdef(c)abcde

。fg(d)第59页，共80页，2023年，2月20日，星期一二．格的性质

性质1．对偶原理设f是含有格中元素以及符号=,≤,≥,∨和∧的命题.令f*是将f中的≤替换成≥,≥替换成≤,∨替换成∧,∧替换成∨所得到的命题.称f*为f的对偶命题.

例如,在格中令f是命题:(a∨b)∧c≤c,则f*为:(a∧b)∨c≥c.第60页，共80页，2023年，2月20日，星期一格的对偶原理

设f是含有格中元素以及符号=,≤,≥,∨和∧等的命题。若f对一切格为真,则f的对偶命题f*也对一切格为真.例如,对一切格L都有

a,b∈L,a∧b≤a

那么对一切格L都有

a,b∈L,a∨b≥a许多格的性质都是互为对偶命题的。有了格的对偶原理,在证明格的性质时,只须证明其中的一个命题就可以了.第61页，共80页，2023年，2月20日，星期一性质2.运算性质定理6.11设<L,≤>是格，定义L上两个二元运算∧和∨如下：x,yLx∧y={x,y}的最大下界

x∨y={x,y}的最小上界则∧和∨满足交换律，结合律，幂等律和吸收律。第62页，共80页，2023年，2月20日，星期一即：（1）

a,b∈L,a∧b=b∧a，a∨b=b∨a,（2）

a,b,c∈L,(a∧b)∧c=a∧(b∧c),(a∨b)∨c=a∨(b∨c),（3）

a∈L，a∧a=a,a∨a=a（4）

a,b∈L,a∧(a∨b)=a,a∨(a∧b)=a,

第63页，共80页，2023年，2月20日，星期一证明:(1)a∨b和b∨a分别是{a,b}和{b,a}的最小上界,由于{a,b}={b,a},所以a∨b=b∨a,

由对偶原理,a∧b=b∧a(2).由最小上界的定义有

(a∨b)∨c≥a∨b≥b即(a∨b)∨c≥b

同理(a∨b)∨c≥c

所以,(a∨b)∨c≥b∨c①

又因为,(a∨b)∨c≥a∨b≥a,即(a∨b)∨c≥a再由①

,有(a∨b)∨c≥a∨(b∨c)②

第64页，共80页，2023年，2月20日，星期一另一方面,a≤a∨(b∨c),b≤b∨c≤a∨(b∨c),即b≤a∨(b∨c)所以a∨b≤a∨(b∨c)③c≤b∨c≤a∨(b∨c),即c≤a∨(b∨c)再由③,有(a∨b)∨c≤a∨(b∨c)④由②、④及偏序关系的反对称性有(a∨b)∨c=a∨(b∨c)由对偶原理可得另一等式.第65页，共80页，2023年，2月20日，星期一(3)显然a≤a∨a,又a≤a,所以a∨a≤a,根据偏序关系的反对称性有a∨a=a

再由对偶原理,可得另一等式.显然,a∨(a∧b)≥a,又由a≤a,a∧b≤a

可得a∨(a∧b)≤a,根据偏序关系的反对称性有

a∨(a∧b)=a.再由对偶原理,可得另一等式.第66页，共80页，2023年，2月20日，星期一

由格的运算性质可知，格是具有两个二元运算的代数系统<L,∧、∨>,其中运算和满足交换律、结合律、幂等律和吸收律.那么能不能像群一样，通过规定运算及其基本性质来给出格的定义呢？回答是肯定的.第67页，共80页，2023年，2月20日，星期一定理

6.12设<L,∧,∨>是具有两个二元运算∧和∨的代数系统,若对于∧和∨运算适合交换律、结合律、吸收律,则定义L中的偏序关系≤为：x,yL,x≤y当且仅当x∨y=y则<L,≤>构成一个格证明（略）第68页，共80页，2023年，2月20日，星期一三、格作为代数系统的定义根据上述定理，可以给出格的另一等价定义,即格作为代数系统的定义。定义6.10设<L,﹡,°>是具有两个二元运算的代数系统,若对于﹡和°运算适合交换律、结合律、吸收律,则称<L,﹡,°>是格.第69页，共80页，2023年，2月20日，星期一注意:

格中运算满足四条定律,交换律、结合律、吸收律和幂等律,但幂等律可以由其它三条推出,所以定义中只需要满足三条定律即可.

以后我们不再区别是偏序集定义的格,还是代数系统定义的格,而统称为格L.第70页，共80页，2023年，2月20日，星期一四、特殊格（1）分配格格的其它性质：设L是格,a,b,cL,有

a∨(b∧c)≤(a∨b)∧(a∨c)证明:由a≤a,b∧c≤ba∨(b∧c)≤a∨ba≤a,b∧c≤ca∨(b∧c)≤a∨c所以,a∨(b∧c)≤(a∨b)∧(a∨c)

第71页，共80页，2023年，2月20日，星期一由此说明,在格中运算∨和∧一般不满足分配律.由对偶原理可得a∧(b∨c)≥(a∧b)∨(a∧c)分配格的定义(P.116定义6.11):设<L,∧,∨>是格,若

a,b,c∈L

a∧(b∨c)=(