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

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

第5章代数系统概述例如f：N×N→N,f(<x,y>)=x+y就是自然数集合N上的二元运算,即普通的加法运算普通的乘法也是N上的二元运算，但减法、除法不是N上的二元运算集合的交、并、差、对称差运算都是某幂集P（A）上的二元运算命题逻辑中求∧、∨、→、是命题公式全体所成集合上的二元运算

例如f：N×N→N,f(<x,y>)=x+例设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对加法运算不封闭.例设A={x︱x=2n,nN},则在集合A上通常的乘对于一元运算f：S→S，如果x的运算结果是y,则f(x)=y,利用运算符，如⊕，简记为⊕

x=y

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

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

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

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

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

°abcdaadccbcabdcaacbdddab

（2）、运算表法二元运算的性质设＊为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上满足幂等律.二元运算的性质(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）(4)、设°和＊为S上两个不同的二元运算,

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

都有e

＊

x=x＊e=

x，则称e

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

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

二元运算中的特殊元素例考虑非零实数全体所成集合R*，如下定义的二元运算°

：对任意的a,b∈R*,a°b=a则运算没有单位元定理设＊为S上的二元运算,则S中关于运算＊至多有一个幺元.例考虑非零实数全体所成集合R*，如下定义的二元运算2、零元设＊为S上的二元运算,θ∈S(书上是z,要改)

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

=θ则称θ

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

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

是零元，则对任意的A∈P(S)2、零元A⊕θ=θ⊕A=θ由A⊕θ=θ

，两边同时右运算θ,

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

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

A⊕Φ=Φ，

A

=Φ，与A的任意性矛盾.A⊕θ=θ⊕A=θ定理设＊为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关于＊至多有一个逆元.

定理设＊为S上的二元运算,则S中关于运算＊至多有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的幺元、零元、可逆元4、消去律（书上有错P.100)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,

所以＊满足交换律.

P.100例5.10（题目及解法有改）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)所以，＊满足结合律.x,y,z∈Z,（＊不满足幂等律）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.由于运算可交换,所以,运算满足消去律.（＊不满足幂等律）xZ,假设x有逆元，设逆元为y,则x＊y=y＊x=0即x+y–xy=0要使yZ，只有x=2,此时y=2所以，只有2才是可逆元，其逆元为2(书中有错）xZ,假设x有逆元，设逆元为y,则把书中的整数集Z改成有理数集Q，则除了可逆元和逆元外，其它不变.把书中的整数集Z改成有理数集Q，则除了可逆元和逆元外从运算表检验运算的性质和特殊元素.交换律、消去律、结合律、幺元、零元、逆元等（P.105.习题3)关于结合律有如下结论：从运算表检验运算的性质和特殊元素.

abcd

aabcdbbadcccdabddcba

abcd

.

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

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

幺元为结合元.

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

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

x是结合元L(x)表与R(x)表中对应元素相同

.

为检验x是否结合元,作表L(x),R(x),其中L解:上例中a是幺元,只要检验b,c,d

L(b)badcabadcbabcdcdcbadcdab解:上例中a是幺元,只要检验b,c,d

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

（2）（xn）m=xn·m

设*是集合S上可结合二元运算，xS5.2代数系统1、代数系统的定义与实例

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

离散的第三篇代数系统课件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}。2、子代数系统(不做要求)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中的运算.5.3代数系统的同态与同构（与书中提法不同）单同态、满同态、同构设f是V1=<S1，°>到V2=<S2，＊>的同态映射，(1)若f是满射,则称为满同态.(2)若f是单射的,则称为单同态.(3)若f是双射的,则称为同构,记作V1≌V2.(4)若V1=V2=V,则称是群V的自同态.类似的可以定义满自同态,单自同态和自同构.单同态、满同态、同构例设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上的自同构例设V1=<R，+>，V2=<R+，×>，P.104例5.26证明：P.104例5.26证明：离散的第三篇代数系统课件离散的第三篇代数系统课件

同态映射的性质(P.104定理5.6)此定理说明：满同态映射保持运算性质不变和保持元素的对应同态映射的性质(P.104定理5.6)此定理说明第6章几种典型的代数系统6.1半群、幺半群与群

一、定义

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

第6章几种典型的代数系统例<Z+,+>,<N,+>,<R,+>都是半群,+是普通加法.这些半群中除<Z+,+>外都是幺半群.<P(B),⊕>是半群，也是幺半群，其中⊕是集合的对称差运算.<Zn,⊕>是半群，也是幺半群，其中Zn={0,1,2,…,n-1},⊕是模n加法事实上,例<Z+,+>,<N,+>,<R,+>都是半群,+是普离散的第三篇代数系统课件证得<Zn,⊕>是半群.显然,0是幺元,所以,<Zn,⊕>是幺半群.证得<Zn,⊕>是半群.显然,0是幺元,所以,<Zn设R*为非零实数集合,其上二元运算°定义如下：对任意x,y∈R*,x°y=y，则<R*,°>为半群.设R*为非零实数集合,其上二元运算°定义如下：对任意x,y离散的第三篇代数系统课件P.108例6.10和6.14综合设∑是字母的有穷集，称为字母表，∑中的有限个字母组成的序列称为∑上的串.对任意串ω，串中字母的个数叫做串的长度，记作︱ω︱.长度为0的串叫空串，记作.令∑*是∑上所有串的集合.∑+=∑*-{}P.108例6.10和6.14综合如下定义∑*上的二元运算·

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

ω2=vi1vi2…vimvj1vj2…vjn

令V1=<∑*,·

,>,V2=<N,+，0

>,定义h：∑*

→N如下：ω

∑*h（ω)=︱ω︱则h是V1到V2的同态.是满同态，但不是单同态.如下定义∑*上的二元运算·(称为连接运算)例如，设∑={a，b},则h(a)=1,h(b)=1,不是单射.若∑={a},则h是同构.P.109例6.19实数集合R上全体函数所成集合RR,关于函数加法<RR,+>成群P.109例6.21例如，设∑={a，b},则h(a)=1,h(b)=1,不是单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上定义二元运算。如下P.109例6.22Klein四元群离散的第三篇代数系统课件离散的第三篇代数系统课件有限群、无限群、交换群(阿贝尔群）、平凡群二．群的性质1．群中元素的幂

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

有限群、无限群、交换群(阿贝尔群）、平凡群例在群<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为无限阶元.例在群<R*，×>和<R，+>中分别求0.5-1，0.5-例求<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.例求<Z6,⊕>中各元素的阶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=c4、群中方程有唯一解。即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}

6.3格和布尔代数P.111—P.115的例6.38即子群、环、域不做要求

P.111—P.115的例6.38例（2）偏序集<z+,D>构成格，其中z+是正整数集合，D为整除关系。事实上,x,y∈z+,x∨y=lcm(x,y),即x与y的最小公倍数x∧y=gcd(x,y),即x与y的最大公约数。

例（2）偏序集<z+,D>构成格，其中z+是正整数

说明:

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

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

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

说明:本章中出现的∨和∧符号只代表格中的运算，而不再有

例(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}没有最大下界例(3).<Z,≤>,是格.其中Z是整数下列哈斯图所表示的偏序集都不是格abcdef(a)ecbda(b)下列哈斯图所表示的偏序集都不是格abcdef(a)ecbdacabdef(c)abcde

。fg(d)cabdef(c)abcde。fg(d)二．格的性质

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

例如,在格中令f是命题:(a∨b)∧c≤c,则f*为:(a∧b)∨c≥c.二．格的性质格的对偶原理

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

a,b∈L,a∧b≤a

那么对一切格L都有

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

x∨y={x,y}的最小上界则∧和∨满足交换律，结合律，幂等律和吸收律。性质2.运算性质即：（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,

即：证明:(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)②

证明:(1)a∨b和b∨a分别是{a,b}和{b,a}的另一方面,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)由对偶原理可得另一等式.另一方面,a≤a∨(b∨c),(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.再由对偶原理,可得另一等式.(3)显然a≤a∨a,又a≤a,所以a∨a≤a,

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

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

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

以后我们不再区别是偏序集定义的格,还是代数系统定义的格,而统称为格L.注意:四、特殊格（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)

四、特殊格由此说明,在格中运算∨和∧一般不满足分配律.由对偶原理可得a∧(b∨c)≥(a∧b)∨(a∧c)分配格的定义(P.116定义6.11):设<L,∧,∨>是格,若

a,b,c∈L

a∧(b∨c)=(a∧b)∨(a∧c)

a∨(b∧c)=(a∨b)∧(a∨c)

则称L为分配格.易见上面两个等式互为对偶式.在证明L为分配格时,只须证明其中的一个等式即可.由此说明,在格中运算∨和∧一般不满足分配律.（2）有界格如果格L有最大元和最小元，则称格L为有界格.例<Z,≤>是格，但不是有界格。其中≤是整数集合上的小于或等于关系。例集合S的幂集格<P（S）,>是有界格。其最大元是S，最小元是。通常把有界格记为<L,∧,∨，0，1>

，其中0，1分别是格中最小元和最大元.（2）有界格（3）有补格元素的补元设<L,∧,∨,0,1>是有界格,x∈L，若y∈L使得x∧y=0,

x∨y=1，则称y是x的补元。有补格的定义设L是有界格，如果L中每个元素都有补元，则称L是有补格（3）有补格说明:

若y是x的补元,则x也是y的补元，称x,y互为补元

有界格中,元素的补元可能存在,也可能不存在,补元可能是唯一的,也可能不唯一.例如，离散的第三篇代数系统课件L1中a与c互为补元，b没有补元。cbaL1L2中b的补元是c,d，不唯一。eabcdL2cbaL1eabcdL2

有界分配格若有补元，则补元是唯一的，即有如下定理：设<L,∧,∨,0,1>是有界分配格,a∈L，若a有补元b,则b是唯一的。证明：(略）

有界分配格若有补元，则补元是唯一的，即有如下定理6.13设<L,∧,∨，0，1>是有补分配格，则L中每一个元素都有唯一的补元.证明：xL，设y和z都是x的补元，则

x∧y=0,x∨y=1,x∧z=0,x∨z=1

x∨y=x∨z因此，y=y∨0=y∨(x∧z)=(y∨x)∧(y∨z)=(x∨z)∧(y∨z)=(x∧y)∨z=0∨z=z定理6.13（4）布尔格（布尔代数）定义6.14有补分配格称为布尔格或布尔代数在有界分配格中,如果一个元素存在补元,则是唯一的。因此,在布尔代数中,每个元素都存在着唯一的补元,可以把求补元的运算看作是布尔代数中的一元运算。从而可以把一个布尔代数标记为<B,∧,∨,＇,0,1>,其中∧,∨,0,1和有界格一样,＇为求补运,a∈B,a＇是a的补元。（4）布尔格（布尔代数）布尔代数的实例例6.47<{0,1},∧,∨,﹁,0,1>是只有两个元素的布尔代数，称电路代数例6.48设n是正整数，<{0,1}n,⊙,＋,＇,0n,,1n>是有个元素的布尔代数，称开关代数其中{0,1}n是由0，1构成的n元有序组即布尔代数的实例第5章代数系统概述5.1二元运算、一元运算及其性质二元运算设S为集合,函数f：S×S→S称为S上的二元运算,简称为二元运算.一个运算是否为集合S上的二元运算主要考虑两点：(1)、S中任何两个元素都可以进行这种运算,且运算的结果是唯一的.(2)、S中任何两个元素的运算结果都属于S,即S对该运算是封闭的.

第5章代数系统概述例如f：N×N→N,f(<x,y>)=x+y就是自然数集合N上的二元运算,即普通的加法运算普通的乘法也是N上的二元运算，但减法、除法不是N上的二元运算集合的交、并、差、对称差运算都是某幂集P（A）上的二元运算命题逻辑中求∧、∨、→、是命题公式全体所成集合上的二元运算

例如f：N×N→N,f(<x,y>)=x+例设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对加法运算不封闭.例设A={x︱x=2n,nN},则在集合A上通常的乘对于一元运算f：S→S，如果x的运算结果是y,则f(x)=y,利用运算符，如⊕，简记为⊕

x=y

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

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

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

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

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

°abcdaadccbcabdcaacbdddab

（2）、运算表法二元运算的性质设＊为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上满足幂等律.二元运算的性质(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）(4)、设°和＊为S上两个不同的二元运算,

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

都有e

＊

x=x＊e=

x，则称e

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

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

二元运算中的特殊元素例考虑非零实数全体所成集合R*，如下定义的二元运算°

：对任意的a,b∈R*,a°b=a则运算没有单位元定理设＊为S上的二元运算,则S中关于运算＊至多有一个幺元.例考虑非零实数全体所成集合R*，如下定义的二元运算2、零元设＊为S上的二元运算,θ∈S(书上是z,要改)

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

=θ则称θ

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

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

是零元，则对任意的A∈P(S)2、零元A⊕θ=θ⊕A=θ由A⊕θ=θ

，两边同时右运算θ,

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

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

A⊕Φ=Φ，

A

=Φ，与A的任意性矛盾.A⊕θ=θ⊕A=θ定理设＊为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关于＊至多有一个逆元.

定理设＊为S上的二元运算,则S中关于运算＊至多有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的幺元、零元、可逆元4、消去律（书上有错P.100)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,

所以＊满足交换律.

P.100例5.10（题目及解法有改）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)所以，＊满足结合律.x,y,z∈Z,（＊不满足幂等律）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.由于运算可交换,所以,运算满足消去律.（＊不满足幂等律）xZ,假设x有逆元，设逆元为y,则x＊y=y＊x=0即x+y–xy=0要使yZ，只有x=2,此时y=2所以，只有2才是可逆元，其逆元为2(书中有错）xZ,假设x有逆元，设逆元为y,则把书中的整数集Z改成有理数集Q，则除了可逆元和逆元外，其它不变.把书中的整数集Z改成有理数集Q，则除了可逆元和逆元外从运算表检验运算的性质和特殊元素.交换律、消去律、结合律、幺元、零元、逆元等（P.105.习题3)关于结合律有如下结论：从运算表检验运算的性质和特殊元素.

abcd

aabcdbbadcccdabddcba

abcd

.

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

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

幺元为结合元.

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

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

x是结合元L(x)表与R(x)表中对应元素相同

.

为检验x是否结合元,作表L(x),R(x),其中L解:上例中a是幺元,只要检验b,c,d

L(b)badcabadcbabcdcdcbadcdab解:上例中a是幺元,只要检验b,c,d

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

（2）（xn）m=xn·m

设*是集合S上可结合二元运算，xS5.2代数系统1、代数系统的定义与实例

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

离散的第三篇代数系统课件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}。2、子代数系统(不做要求)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中的运算.5.3代数系统的同态与同构（与书中提法不同）单同态、满同态、同构设f是V1=<S1，°>到V2=<S2，＊>的同态映射，(1)若f是满射,则称为满同态.(2)若f是单射的,则称为单同态.(3)若f是双射的,则称为同构,记作V1≌V2.(4)若V1=V2=V,则称是群V的自同态.类似的可以定义满自同态,单自同态和自同构.单同态、满同态、同构例设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上的自同构例设V1=<R，+>，V2=<R+，×>，P.104例5.26证明：P.104例5.26证明：离散的第三篇代数系统课件离散的第三篇代数系统课件

同态映射的性质(P.104定理5.6)此定理说明：满同态映射保持运算性质不变和保持元素的对应同态映射的性质(P.104定理5.6)此定理说明第6章几种典型的代数系统6.1半群、幺半群与群

一、定义

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

第6章几种典型的代数系统例<Z+,+>,<N,+>,<R,+>都是半群,+是普通加法.这些半群中除<Z+,+>外都是幺半群.<P(B),⊕>是半群，也是幺半群，其中⊕是集合的对称差运算.<Zn,⊕>是半群，也是幺半群，其中Zn={0,1,2,…,n-1},⊕是模n加法事实上,例<Z+,+>,<N,+>,<R,+>都是半群,+是普离散的第三篇代数系统课件证得<Zn,⊕>是半群.显然,0是幺元,所以,<Zn,⊕>是幺半群.证得<Zn,⊕>是半群.显然,0是幺元,所以,<Zn设R*为非零实数集合,其上二元运算°定义如下：对任意x,y∈R*,x°y=y，则<R*,°>为半群.设R*为非零实数集合,其上二元运算°定义如下：对任意x,y离散的第三篇代数系统课件P.108例6.10和6.14综合设∑是字母的有穷集，称为字母表，∑中的有限个字母组成的序列称为∑上的串.对任意串ω，串中字母的个数叫做串的长度，记作︱ω︱.长度为0的串叫空串，记作.令∑*是∑上所有串的集合.∑+=∑*-{}P.108例6.10和6.14综合如下定义∑*上的二元运算·

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

ω2=vi1vi2…vimvj1vj2…vjn

令V1=<∑*,·

,>,V2=<N,+，0

>,定义h：∑*

→N如下：ω

∑*h（ω)=︱ω︱则h是V1到V2的同态.是满同态，但不是单同态.如下定义∑*上的二元运算·(称为连接运算)例如，设∑={a，b},则h(a)=1,h(b)=1,不是单射.若∑={a},则h是同构.P.109例6.19实数集合R上全体函数所成集合RR,关于函数加法<RR,+>成群P.109例6.21例如，设∑={a，b},则h(a)=1,h(b)=1,不是单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上定义二元运算。如下P.109例6.22Klein四元群离散的第三篇代数系统课件离散的第三篇代数系统课件有限群、无限群、交换群(阿贝尔群）、平凡群二．群的性质1．群中元素的幂

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

有限群、无限群、交换群(阿贝尔群）、平凡群例在群<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为无限阶元.例在群<R*，×>和<R，+>中分别求0.5-1，0.5-例求<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.例求<Z6,⊕>中各元素的阶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=c4、群中方程有唯一解。即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}

6.3格和布尔代数P.111—P.115的例6.38即子群、环、域不做要求

P.111—P.115的例6.38例（2）偏序集<z+,D>构成格，其中z+是正整数集合，D为整除关系。事实上,x,y∈z+,x∨y=lcm(x,y),即x与y的最小公倍数x∧y=gcd(x,y),即x与y的最大公约数。

例（2）偏序集<z+,D>构成格，其中z+是正整数

说明:

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

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

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

说明:本章中出现的∨和∧符号只代表格中的运算，而不再有

例(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}没有最大下界例(3).<Z,≤>,是格.其中Z是整数下列哈斯图所表示的偏序集都不是格abcdef(a)ecbda(b)下列哈斯图所表示的偏序集都不是格abcdef(a)ecbdacabdef(c)abcde

。fg(d)cabdef(c)abcde。fg(d)二．格的性质

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

例如,在格中令f是命题:(a∨b)∧c≤c,则f*为:(a∧b)∨c≥c.二．格的性质格的对偶原理

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

a,b∈L,a∧b≤a

那么对一切格L都有

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

x∨y={x,y}的最小上界则∧和∨满足交换律，结合律，幂等律和吸收律。性质2.运算性质即：（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,

即：证明: