离散数学及其应用 课件 马立和 第6-11章 代数系统的基本概念-几类典型图

第六章代数系统的基本概念6.1二元运算及性质6.2代数系统6.3代数系统的同态与同构6.1.1二元运算的基本概念定义6.1.1设A1,A2,…An,A是非空集合,f是从A1×A2×…×An到A的一个映射,则称f为从集合A1×A2×…×An到A的一个n元代数运算,简称n元运算。其中,n称为代数运算的阶。6.1.1二元运算的基本概念【例6.1.1】(1)整数集合Z上的加法、减法和乘法均为二元运算,而除法不是。(2)A为集合,ρ(A)为其幂集,若f:ρ(A)×ρ(A)→ρ(A)为二元运算,则f可以是∩、∪、-、⊕。(3)设Mn(R)为n阶实矩阵的集合(n≥2),即6.1.1二元运算的基本概念则矩阵加法,减法和乘法都是Mn(R)上的二元运算。(4)设A=a1,a2,…an,ai

○aj=ai,“○(复合)”是A上的二元运算。当集合A为有限集时,A上的一元运算和二元运算可以用运算表给出。表6-1-1和表6-1-2分别是A上的一元运算和二元运算的一般形式。6.1.2二元运算的性质定义6.1.2设*为S上的二元运算。(1)若对于任意的x,y∈S都有x*y=y*x,则称运算*在S上是可交换的,或者称运算*在S上满足交换律。(2)若对于任意的x,y,z∈S都有(x*y)*z=x*(y*z),则称运算*在S上是可结合的,或者说运算*在S上满足结合律。(3)若对于任意的x∈S有x*x=x,则称运算*是等幂的,或者称运算*满足幂等律。6.1.2二元运算的性质【例6.1.2】Z、Q、R分别为整数集、有理数集、实数集;Mn(R)为n阶实矩阵集合,n≥2;ρ(S)为幂集,则有如下性质,见表6-1-3。6.1.2二元运算的性质定义6.1.3

设○和*为S上两个不同的二元运算,(1)若对于任意的x,y,z∈S都有:x

○(y*z)=(x

○

y)*(x

○

z)(左分配律)(y

○z)*x=(y*x)

○(z*x)(右分配律)则称运算○对*是可分配的,也称○对*满足分配律。如果以上两式中只有一个成立,则称○对*是可左分配的或可右分配的。(2)若○和*都可交换,并且对于任意的x,y∈S都有:x

○(x*y)=x(左吸收律)(x*y)

○

x=x(右吸收律)则称○和*满足吸收律。6.1.2二元运算的性质【例6.1.3】Z、Q、R分别为整数集、有理数集、实数集;Mn(R)为n阶实矩阵集合,n≥2;ρ(S)为幂集,则有如下性质,见表6-1-4。6.1.3二元运算的特异元素定义6.1.4设*是集合S中的一种二元运算,如果S上存在er∈S(el∈S)且对任意元素x∈S均有x*er=x(el*x=x),则称元素er(el)为S中关于运算*的右幺元(左幺元)或右单位元(左单位元),可以符号化为∃er(er∈S∧∀x(x∈S→x*er=x))或∃el(el∈S∧∀x(x∈S→el*x=x))若e∈S关于运算*既是左幺元,又是右幺元,则称e为S上关于运算*的幺元或单位元。6.1.3二元运算的特异元素定理6.1.1设集合S上关于二元运算*,既存在右幺元er,又存在左幺元el,则er=el=e,且e为S上关于运算*的唯一幺元。证明(1)证明左右幺元相等:因为er和el分别是运算*的右幺元和左幺元,故有el*er=el,el*er=er,所以er=el。(2)证明幺元是唯一的:令er=el=e,假设另有一幺元为右幺元e',那么e=e*e'=e',故e是S上关于运算*的唯一幺元。证毕。显然,对于可交换的二元运算,如果存在左幺元,则必存在右幺元,所以一定存在幺元。6.1.3二元运算的特异元素【例6.1.4】(1)在实数集R中,对加法“+”运算,0是幺元。(2)在实数集R中,对于乘法“×”运算,1是幺元。(3)对于全集E的子集的并“∪”运算,⌀是幺元。(4)对于全集E的子集的交“∩”运算,E是幺元。(5)在命题集合中,对于析取“∨”运算,矛盾式是幺元。(6)在命题集合中,对于合取“∧”运算,重言式是幺元。(7)对于从集合S到S的双射函数的合成运算,恒等函数是幺元。6.1.3二元运算的特异元素定义6.1.5设*是集合S中的一种二元运算,如果存在元素θr∈S(θl∈S)且对任意元素x∈S均有x*θr=θr(θl*x=θl),则称元素θr(θl)是S中关于运算*的右零元(左零元)。符号化类似定义6.1.4,这里不再赘述。6.1.3二元运算的特异元素定理6.1.2设集合S上关于二元运算*,既存在右零元θr又存在左零元θl,则θr=θl=θ,称元素θ是S中关于运算*的唯一零元。证明(1)证明左右零元相等:因为θr

和θl分别是运算*的右零元和左零元,故有θl*θr=θl,θl*θr=θr,所以θr=θl。(2)证明零元是唯一的:令θr=θl=θ,假设另有一零元为右零元θ',那么θ=θ*θ'=θ',故θ是S上关于运算*的唯一零元。证毕。6.1.3二元运算的特异元素【例6.1.5】(1)在实数集R中,对于加法“+”运算,没有零元。(2)在实数集R中,对于乘法“×”运算,0是零元。(3)对于全集E的子集的并“∪”运算,E是零元。(4)对于全集E的子集的交“∩”运算,⌀是零元。(5)在命题集合中,对于析取“∨”运算,重言式是零元。(6)在命题集合中,对于合取“∧”运算,矛盾式是零元。6.1.3二元运算的特异元素定义6.1.6设*为集合S上的二元运算,e∈S为S关于运算*的幺元,如果存在一个元素al∈S(或ar∈S),使得对于元素a∈S,有al*a=e(或a*ar=e)成立,则称a是左可逆的(右可逆的),并称al(或ar)是a的左逆元(右逆元)。若对于a∈S,既存在左逆元又存在右逆元,则称a是可逆的。6.1.3二元运算的特异元素定理6.1.3设*为集合S上的一个可结合的二元运算,e为该运算的幺元。对于x∈S,如果存在左逆元al和右逆元ar,则al=ar=a,即a是x的逆元,且是唯一的。证明(1)证明左右逆元相等:因为e是S上关于运算*的幺元,故有al*x=e和x*ar=e,又因为运算*是可结合的,所以al*x*ar=(al*x)*ar=e*ar=ar

al*x*ar=al*(x*ar)=al*e=al显然,左右逆元相等。(2)证明逆元是唯一的:令al=ar=a,假设x有两个不同的逆元a1和a2,由逆元的定义知a1=a1*e=a1*(x*a2)=(a1*x)*a2=e*a2=a2与假设矛盾,于是x的逆元是唯一的。证毕。6.1.3二元运算的特异元素定理6.1.4设*是集合S中的一个可结合的二元运算,且e为S中对于*的幺元,x有逆元x-1,则(x-1)-1=x。证明(x-1)-1=(x-1)-1*e=(x-1)-1*(x-1*x)=((x-1)-1*x-1)*x=e*x=x。证毕。6.1.3二元运算的特异元素【例6.1.6】给定⊗是集合S上的二元运算,其中S=α,β,γ,δ,ξ表6-1-5。试指出该代数系统中各元素的左、右逆元情况。6.1.3二元运算的特异元素解α是幺元,β的左逆元和右逆元都是γ,即β与γ互为逆元。δ的左逆元是γ,而右逆元是β,β有两个左逆元γ和δ。ξ的右逆元是γ,但ξ没有左逆元。6.1.3二元运算的特异元素定义6.1.7设*为集合S上的二元运算,如果对任意的x,y,z∈S满足以下条件:(1)若x*y=x*z且x不是零元,则y=z。(2)若y*x=z*x且x不是零元,则y=z。就称运算*满足消去律。其中(1)称作左消去律,(2)称作右消去律。6.1.3二元运算的特异元素【例6.1.7】设*运算为集合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+4xyzx*(y*z)=x+(y+z+2yz)+2x(y+z+2yz)=x+y+z+2xy+2xz+2yz+4xyz所以,*运算可交换、可结合,即满足交换律和结合律。6.1.3二元运算的特异元素(2)设*运算的单位元和零元分别为e和θ,则对于任意x有x*e=x成立,即x+e+2xe=x⇒e=0由于*运算可交换,所以0是幺元。对于任意x有x*θ=θ成立,即x+θ+2xθ=θ⇒x+2xθ=0⇒θ=-1/2由于*运算可交换,所以-1/2是零元。给定x,设x的逆元为y,则有x*y=0成立,即x+y+2xy=0⇒y=-x/(1+2x)(x≠-1/2)因此当x≠-1/2时,-x/(1+2x)(是x的逆元。6.2.1代数系统的基本概念定义6.2.1

设S是非空集合,f1,f2,…,fk

是S上的k个一元或二元运算,则S称为基集,各运算组成的集合称为运算集,集合S连同其上的代数运算组成的系统称为代数系统,简称代数,记作<S,f1,f2,…,fk

>。对于代数系统<S,f1,f2,…,fk>的理解,需要注意以下几点:(1)S≠⌀。(2)f1,f2,…,fk(k>1)。(3)如果S是有限集合,则称代数系统是有限代数系统,否则称为无限代数系统。(4)代数运算fi(i=1,2,…,k)不仅限于一元或二元运算,还有其他n元n>2数运算类,但较复杂,故代数系统通常研究一元或二元运算。6.2.1代数系统的基本概念【例6.2.1】(1)以实数集R为基集,数加运算“+”为二元运算,组成一代数系统,记为<R,+>。(2)以全体n×n实数矩阵组成的集合M为基集,矩阵加“○

”为二元运算,组成一代数系统,记为<M,

○>。(3)以集合S的幂集ρ(S)为基集,以集合并、交、补为其二元运算和一元运算,组成一代数系统,记为<ρ(S),,∪,∩,~>。这个系统就是常说的幂集代数系统。以上的(1)(2)(3)均称为具体代数系统,其运算满足的性质未列出。(4)设S为一非空集合,

○为S上满足结合律、交换律的二元运算,那么<S,

○>为代数ρ(S)结构,称为一个代数抽象系统,即一类具体代数系统的抽象。例如<R,+>,<M,

○

>,<ρ(S),∪,∩,~>都是<S,

○

>的具体例子。<R,+,-,×>,<Z,+,-,×>均是代数系统,但我们不能写<Z,÷>,<R,÷>,<N,->,因为它们不是代数系统,它们的运算不封闭。6.2.1代数系统的基本概念定义6.2.2

如果两个代数系统中运算个数相同,对应运算的阶数相同,且代数常数的个数也相同,则称它们是同类型的代数系统。如果两个同类型的代数系统规定的运算性质也相同,则称为同种的代数系统。例如命题代数与幂集代数:<ρ(S),∪,∩,~,S,Φ>与<R,+,×,-,0,1>。6.2.1代数系统的基本概念定义6.2.3设V=<S,f1,f2,…,fk>是一个代数系统,B⊆S且B≠⌀,如果B在运算f1,f2,…,fk作用下都是封闭的,且B和S含有相同的代数常数,则称<B,f1,f2,…,fk>是V的子代数系统,简称子(subalgebra)。根据定义有以下几点结论:(1)对任何代数系统V=<S,f1,f2,…,fk>,其子代数一定存在。(2)最大的子代数就是V本身。(3)如果令V中所有的代数常数构成的集合是B,且对V中所有的运算都是封闭的,那么,B就构成了V的最小的子代数。(4)最大与最小的子代数称为V的平凡的子代数。(5)如果V的子代数V'=<S,f1,f2,…,fk>,其子代数一定存在。满足B⊂S,则称V'是V的真子代数。6.2.1代数系统的基本概念【例6.2.2】(1)<N,+,0>是<Z,+,0>的子代数,因为N对加法封闭,且它们都有相同的代数常数0。(2)设E为非负偶数集,M为非负奇数集,则对<N,+>而言,<E,+>为其子代数,<N,+>,<0,+>为其平凡子代数,<M,+>不构成其子代数。6.2.2代数系统的同态与同构定义6.2.4设<S,*>与<T,○

>是同类型的代数系统,如果函数f:S→T对S中任何元素a,b有f(a*b)=f(a)

○

f(b)称函数f为(代数系统S到T的)同态映射,简称同态(homomorphism),当同态f为单射时,又称f为单同态;当f为满射时,又称f为满同态;当f为双射时,又称f为同构映射,或同构(isomorphism)。当两个代数系统间存在同构映射时,也称这两个代数系统同构,记为S≅T。当f为<S,*>到<S,*>的同态(同构)时,称f为S的自同态(自同构)。f(a*b)=f(a)

○

f(b)称为同态f的同态方程。6.2.2代数系统的同态与同构【例6.2.3】(1)设f:R→R为f(x)=ex(R为实数集),那么,f为<R,+>到<R,·>的同态。因为对任意实数x,y,有f(x+y)=ex+y=ex·ey=f(x)·f(y)由f的定义还可知f为单一同态。但是当f:R→R+为f(x)=ex(R+为正实数集),那么f为<R,+>到<R+,·>的同构映射,换言之,<R,+>与<R+,·>同构。(2)设h:R→R为h(x)=2x,那么h为<R,+>到<R+,·>的自同态,因为对任何实数x,y,有h(x+y)=2(x+y)=2x+2y=h(x)+h(y)并且h为自同构。6.2.2代数系统的同态与同构定义6.2.5设f为代数系统<S,*>到<T,

○

>的同态映射,那么称f(S)的同态像(imageunderhomomorphism)。6.2.2代数系统的同态与同构定理6.2.1设f为代数系统<S,*>到<T,○>的同态,那么同态像f(S)为f与○构成<T,

○

>的一个子代数。证明只要证fS对运算○封闭即可。因此设a',b'为f(S)中任意两个元素,且f(a)=a',f(b)=b',那么a'

○

b'=f(a)

○

f(b)=f(a*b)∈f(S)故f(S)对运算○封闭,<f(S),

○

>为T的子代数。证毕。7.1半群与独异点7.2群与子群7.3拉格朗日定理与正规子群7.4特殊群7.5环和域第七章

几种典型的代数系统半群与独异点都是具有一个二元运算的代数系统。半群相关定义设<S,*>是代数系统,*是二元运算,如果*运算满足结合律,则称它为半群（semigroups）。如果半群<S,*>中二元运算*是可交换的,则称<S,*>是可交换半群(commutativesemigroups)。换言之,∀x,y,z∈S,若*是S上的封闭运算且满足(x*y)*z=x*(y*z),则<S,*>是半群。（1）<Z+,+>,<N,+>,<Z,+>,<Q,+>,<R,+>都是半群,也都是可交换半群,其中+表示普通加法。（2）<Mn(R),×>是半群,不是可交换半群,其中×表示矩阵乘法。因为矩阵乘法满足结合律,不满足交换律。7.1半群与独异点

7.1半群与独异点

7.1半群与独异点Z是整数集,对于下列二元运算*,哪些代数系统<Z,*>是独异点?(1)a*b=ab+1。(2)a*b=b。解

(1)由于a*b*c=ab+1*c=ab+1c+1=abc+c+1,a*b*c=a*bc+1=abc+1+1=abc+a+1,所以a*b*c≠a*b*c,二元运算*不是可结合运算,<Z,*>不是独异点。(2)由于a*b=b,所以二元运算*对于Z是封闭的。又由于a*b*c=b*c=c,a*b*c=a*c=c,所以*是可结合运算。而在<Z,*>中不存在幺元,由此可见<Z,*>是半群但不是独异点。7.1半群与独异点7.1半群与独异点7.2群与子群7.3拉格朗日定理与正规子群7.4特殊群7.5环和域第七章

几种典型的代数系统群是具有一个二元运算的代数系统。群的相关定义如果代数系统<S,*>满足:(1)<S,*>为一半群,(2)<S,*>中有幺元e,(3)<S,*>中每一元素x∈S都有逆元x-1。则称代数系统<S,*>为群(groups),通常记作G。或者说,群是每个元素都可逆的独异点。7.2.1群的基本概念

7.2.1群的基本概念注意

因为零元无逆元,所以含有零元的代数系统就不会是群。设G={a,b,c,e},*为G上的二元运算,它由下表给出,不难证明G是一个群。且e是G中的幺元;G中任何元素的逆元就是它本身,在a,b,c三个元素中,任何两个元素运算的结果都等于另一个元素,这个群称为Klein(克莱因)四元群。7.2.1群的基本概念*eabceeabcaaecbbbceaccbae设<G,*>是一个独异点,并且每个元素都有右逆元,证明<G,*>为群。证明

由于群是每个元素都可逆的独异点,因此只需证明<G,*>中每个元素都可逆即可。设e是<G,*>中的幺元。每个元素都有右逆元,即∀x∈G,∃y∈G使得x*y=e,而对于此y,又∃z∈G使得y*z=e。由于∀x∈G均有x*e=e*x=x,因此z=e*z=x*y*z=x*e=x,即x*y=e=y*z=y*x=e,y既是x的右逆元,又是x的左逆元,因此对∀x∈G均有逆元,<G,*>为群。证毕。7.2.1群的基本概念对群<G,*>的任意元素a,我们定义它的幂:a0=e,对任何正整数n,an+1=an*a。群的幂运算有下列性质:定理对群<G,*>的任意元素a,b,有(1)(a-1)-1=a。(2)(a*b)-1=b-1*a-1。(3)(an)-1=(a-1)n

(记为a-n,n为整数)。7.2.2群的性质证明

(1)因为a-1的逆元是a,即a*a-1=a-1*a=e,所以(a-1)-1=a。(2)因为(a*b)*(b-1*a-1)=a*(b*b-1)*a-1=e,(b-1*a-1)*(a*b)=b-1*(a-1*a)*b=e,所以a*b的逆元为b-1*a-1,即(a*b)-1=b-1*a-1。(3)对n进行归纳。群首先是独异点,所以an+1=an*a。n=1时命题显然为真。设n=k时(a-1)k是ak的逆元为真,即(ak)-1=(a-1)k,那么(ak+1)*(a-1)k+1=ak*(a*a-1)*(a-1)k=ak*(a-1)k=e,(a-1)k+1*ak+1=(a-1)k*(a-1*a)*ak=(a-1)k*ak=e,故ak+1的逆元为(a-1)k+1,即(ak+1)-1=(a-1)k+1。归纳完成。证毕。7.2.2群的性质又根据此定理,在群中可引入“负指数幂”的概念:a-n=(a-1)n,且容易证明:定理对群<G,*>的任意元素a,b及任何整数m,n,有(1)am*an=am+n。(2)(am)n=amn。证明(留给读者)7.2.2群的性质群的下列性质是明显的。定理设<G,*>为群,则(1)G有唯一的幺元,G的每个元素恰有一个逆元。(2)方程a*x=b,y*a=b都有解且解唯一。(3)当G≠{e}时,G无零元。证明

(1)显然成立。(2)先证a-1*b是方程a*x=b的解。将a-1*b代入方程左边的x,得a*(a-1*b)=(a*a-1)*b=e*b=b。所以a-1*b是该方程的解。7.2.2群的性质定理设<G,*>为群,则对*满足消去律,即对任意a,x,y∈G,有(1)a*x=a*y蕴含x=y。(2)x*y=y*a蕴含x=y。证明

在等式两边左“乘”或右“乘”a的逆元a-1,即得x=y。证毕。7.2.2群的性质阶的相关定义(1)若群G是有限集合,则称G是有限群,否则称为无限群。(2)只含有单位元的群称为平凡群。(3)设<G,*>为群,a∈G,则满足等式an=e的最小正整数n称为a的阶(order),记作|a|=n。若不存在这样的正整数n,称a是无限阶。(1)<Z,+>和<R,+>是无限群,<Zn,+>是有限群,也是n阶群。(2)<0,+>是平凡群。(3)任何群G的幺元e的阶为1,且只有幺元e的阶为1。(4)<Z,+>中幺元0的阶为1,而整数a=10时,a有无限阶。(5)<Z4,+4>中[1]的阶是4,[2]的阶是2,[3]的阶是4。7.2.3群的元素的阶定理设<G,*>为群,G中元素a的阶为r,an=e当且仅当r整除n。证明充分性:由于r整除n,必存在整数k使得n=kr,且已知a=r,所以有an=akr=(ar)k=ek=e。必要性:根据除法,存在整数m和n,使得n=mr+k,0≤k<r,从而有:e=an=amr+k=amr*ak=ak。因为|a|=r,必有k=0,r整除n。证毕。推论设a是群<G,*>中的任意元素,若an=e,其中n为正整数,e为群中的幺元且没有n的因数d(0<d<n)能使ad=e,则|a|=n。7.2.3群的元素的阶定理设<G,*>为群,a为G中任意元素,那么a=a-1。证明设a的阶为n,由(a-1)n=(an)-1=e-1=e,可知a-1的阶是存在的。只要证a具有阶n当且仅当a-1具有阶n。由于逆元是相互的,即(a-1)-1=a,因此只需证:当a具有阶n时,a-1也具有阶n。设a的阶是n,a-1的阶是k。由于(a-1)n=(an)-1=e-1=e,故k≤n。又因为ak=((a-1)k)-1=e-1=e,故n≤k。因此n=k,即a=a-1。证毕。7.2.3群的元素的阶定理设G是n阶有限群,证明:(1)G中阶大于2的元素个数一定是偶数。(2)若n是偶数,则G中阶等于2的元素个数一定是奇数。证明

(1)设A={x|x∈G,x的阶大于2},则∀a∈A,a-1≠a,否则a2=e与a∈A矛盾。因为a与a-1的阶相同,且a-1相对于a是唯一的,所以∀a∈A,a-1与a成对出现,故G中阶大于2的元素个数一定是偶数。(2)当n是偶数时,因为G中阶大于2的元素个数一定是偶数,所以G中阶小于等于2的元素个数是偶数,由于阶为1的元素是唯一的幺元e,因此G中阶等于2的元素个数一定是奇数。证毕。7.2.3群的元素的阶阿贝尔群设<G,*>为群。若*运算满足交换律,则称G为交换群或阿贝尔群(Abel

group)。阿贝尔群又称加群,常表示为<G,+>(这里的+不是数加,而泛指可交换二元运算,*常被称为乘)。加群的幺元常用0来表示,常用-x来表示x的逆元。例如:<Z,+>为一阿贝尔群;<Q,+>,<R,+>,<C,+>均为交换群;<Q+,·>为一阿贝尔群,1为其幺元;<N+,+4>为一4阶阿贝尔群。7.2.3群的元素的阶定理设<G,*>为一群,<G,*>为阿贝尔群的充分必要条件是对任意x,y∈G,有(x*y)*(x*y)=(x*x)*(y*y)。证明充分性:设对任意的x,y∈G,有(x*y)*(x*y)=(x*x)*(y*y)。因为x*(x*y)*y=(x*x)*(y*y)=(x*y)*(x*y)=x*(y*x)*y,由消去律可得(x*y)=(y*x),所以<G,*>为阿贝尔群。必要性:设<G,*>为阿贝尔群,因此对于任意的x,y∈G,有(x*y)=(y*x),所以(x*x)*(y*y)=x*(x*y)*y=x*(y*x)*y=(x*y)*(x*y),证毕。阿贝尔群满足我们上述讨论的群的所有性质。7.2.3群的元素的阶子群相关定义设<G,*>为群,<H,*>为G的非空子集:(1)如果<H,*>关于G中的运算构成群,则称<H,*>是G的子群,记作H≤G。(2)若<H,*>是G的子群,且H⊆G,则称<H,*>是G的真子群,记作H<G。<Z,+>是<Q,+>的子群;<Q,+>是<R,+>的子群;<R,+>是<C,+>的子群。E⊆Z,E为偶数集,那么<E,+>为<Z,+>的子群;M⊆Z,M为奇数集,但<M,+>不是<E,+>的子群。7.2.4子群的定义及其判定定理定理设<G,*>为群,那么<H,*>为<G,*>的子群的充分必要条件是:(1)若a,b∈H,则a*b∈H。(2)若a∈H,则a-1∈H。证明

充分性:只需证e∈H。因为H非空,必存在a∈H。由条件(2)知a-1∈H,再根据条件(1)有a*a-1∈H,即e∈H。必要性:设H为子群。(1)这是显然的。(2)设<H,*>中任意元素a在H中的逆元为b,那么a*b=b*a=e,因为H⊆G,所以a,b∈G,由逆元的唯一性,b就是a在G中的逆元,即b=a-1∈H。证毕。7.2.4子群的定义及其判定定理定理设<G,*>为群,H是G的非空子集,那么<H,*>为<G,*>的子群的充分必要条件是∀a,b∈H有a*b-1∈H。证明

必要性:任取a,b∈H,由于H是G的子群,必有b-1∈H,所以a*b-1∈H。充分性:因为H非空,必存在a∈H(取b=a),由已知条件有a*a-1∈H,即e∈H。任取a∈H,由e,a∈H有e*a-1∈H,即a-1∈H。任取a,b∈H,则b-1∈H,由已知条件有a*(b-1)-1∈H,即a*b∈H。由前一定理,<H,*>为<G,*>的子群得证。证毕。7.2.4子群的定义及其判定定理

7.2.4子群的定义及其判定定理7.1半群与独异点7.2群与子群7.3拉格朗日定理与正规子群7.4特殊群7.5环和域第七章

几种典型的代数系统群的子群反映了群的结构和性质,因此需要研究群与子群的关系和子群的性质。本节将用子群对群做一个划分,从而得到关于群和子群的一个重要的定理———拉格朗日定理。陪集相关定义设<G,*>为群,A,B⊆G,且A,B非空,则AB={a*b|a∈A,b∈B}称为A,B的乘积。设S3={(1),(12),(13),(23),(123),(132)},A={(1),(12)},B={(123),(13)},求AB,BA。解

AB={(123),(13),(12)(123),(12)(13)}={(123)(13)}7.3.1陪集与拉格朗日定理设S3={(1),(12),(13),(23),(123),(132)},A={(1),(12)},B={(123),(13)},求AB,BA。解（续）BA={(123),(13),(123)(12),(13)(12)}={(123),(13),(23),(132)}一般地,|AB|≠|A||B|,当G可交换,则AB=BA。当A={a}时,{a}B=aB。乘积的性质:设<G,*>为群,A,B,C⊆G,且A,B,C非空,则(1)(AB)C=A(BC)(因为群中所有元素都满足结合律)。(2)eA=Ae=A(因为群中所有元素乘一幺元都等于该元素本身)7.3.1陪集与拉格朗日定理陪集相关定义设<G,*>为群,A,B⊆G,且A,B非空,则AB={a*b|a∈A,b∈B}称为A,B的乘积。设<H,*>为<G,*>的子群,a是G中任意元素,则(1)aH={ah|h∈H}为子群H在群G中的一个左陪集(leftcoset)。(2)Ha={ha|h∈H}为子群H在群G中的一个右陪集(rightcoset)。a称为左陪集aH(或右陪集Ha)的代表元(representativeelement)。显然,当G是可交换群时,子群H的左、右陪集相等。7.3.1陪集与拉格朗日定理

7.3.1陪集与拉格朗日定理

7.3.1陪集与拉格朗日定理定理设<H,*>为<G,*>的子群,e是单位元,a,b∈G,则:(1)eH=H=He。(2)Ha=H⇔a∈H(aH=H⇔a∈H)。(3)a∈Hb⇔Ha=Hb⇔ab-1∈H(a∈bH⇔aH=bH⇔a-1b∈H)。(4)H的所有左陪集(或右陪集)的集合构成G的一个划分。证明（略）7.3.1陪集与拉格朗日定理求S3中子群H={(1),(12)}的左、右陪集。解

S3={(1),(12),(13),(23),(123),(132)},则H的左陪集有:(1)H=(12)H=H(13)H={(13),(132)}=(132)H(23)H={(23),(123)}=(123)HH的右陪集有:H(1)=H(12)=HH(13)={(13),(123)}=H(123)H(23)={(23),(132)}=H(132)子群H的左、右陪集不一定相等,但它们的基数相同。7.3.1陪集与拉格朗日定理定理设H是群G的子群,则对任意的a∈G,有|aH|=|Ha|=|H|证明

证明两个集合的基数相等的通常方法是在这两个集合之间建立一个双射。首先证明|H|=|Ha|。定义映射f:H→Ha,∀h∈H,f(h)=ha。下面证明f是双射。∀h1,h2∈H,h1≠h2,则h1a≠h2a(否则由消去律可知h1=h2,矛盾),即f(h1)≠f(h2),所以f是单射。由于Ha={ha|h∈H},∀ha∈Ha,有f(h)=ha,所以f是满射。因此f是双射,则|H|=|Ha|。同理可证,|H|=|aH|。综上,|aH|=|Ha|=|H|。证毕。7.3.1陪集与拉格朗日定理

可见子群H的每个左、右陪集的基数均等于H的基数,在有限群情况下,可得到著名的拉格朗日定理。定理设<G,*>为有限群,H是G的子群,那么|H|||G|(H的阶整除G的阶)。证明

设R是G中的等价关系,将G分成不同等价类,由以上讨论知G=∪i=1k[ai]R=∪i=1kaiH,由于这k个左陪集是两两不相交的,所以有|G|=|a1H|+|a2H|+…+|akH|(7.1)由前一定理可知|aiH|=|H|(i=1,2,…,k),将这些式子代入式(7.1)得|G|=k|H|其中,k为不同左(右)陪集的数目。得证。证毕。7.3.1陪集与拉格朗日定理由拉格朗日定理,可得到如下推论。推论设<G,*>为有限群,|G|=n,则:(1)若H是G的任何一个子群,|H|=m,则m|n。(2)若n为质数,则G的子群H必然是平凡子群,而非真子群。证明

(1)由拉格朗日定理直接可得。(2)设|H|=m,由(1)知m|n,若n为质数,则m=1或m=n,所以H只能是G的平凡子群,即G没有真子群。证毕。7.3.1陪集与拉格朗日定理通常而言,群G的子群H的左陪集aH不一定等于右陪集Ha,但满足aH=Ha时,就形成了一类十分重要的子群。正规子群相关定义设<G,*>为有限群,|G|=n,则:设<H,*>为群<G,*>的子群,如果对任意a∈G,有aH=Ha则称H为正规子群(normalsubgroup)。此时左陪集和右陪集简称为陪集(coset)。显然,群G的两个平凡子群{e}和G本身均为正规子群。若G是可交换群,则G的任意子群均为正规子群。7.3.2正规子群、商群

7.3.2正规子群、商群下面介绍正规子群的判定定理。定理设<G,*>为有限群,|G|=n,则:设<H,*>为群<G,*>的一个子群,则<H,*>是<G,*>的正规子群的充分必要条件是∀a∈G,h∈H,都有aha-1∈H。证明

必要性:若<H,*>为<G,*>的正规子群,则∀a∈G,∀h∈H,有ah∈aH=Ha,即存在h1∈H,使得ah=h1a,于是aha-1=h1∈H,故aha-1∈H。7.3.2正规子群、商群定理设<G,*>为有限群,|G|=n,则:设<H,*>为群<G,*>的一个子群,则<H,*>是<G,*>的正规子群的充分必要条件是∀a∈G,h∈H,都有aha-1∈H。证明（续）

充分性:∀ah∈aH,其中a∈G,h∈H,因为aha-1∈H,所以,存在h1∈H使得aha-1=h1,于是ah=h1a,从而aH⊆Ha。又∀ha∈Ha,其中a∈G,h∈H,a-1∈G,则a-1h(a-1)-1=a-1ha∈H,所以存在h2∈H,使得a-1ha=h2。于是ha=ah2,从而Ha⊆aH。综上,∀a∈G,都有aH=Ha,即H是G的正规子群。证毕。7.3.2正规子群、商群设H1和H2是群G的正规子群,证明H1∩H2也是正规子群。证明

根据定理∀a∈G,h∈H1∩H2,有h∈H1,h∈H2。由于H1和H2是群G的正规子群,则aha-1∈H1,aha-1∈H2,所以aha-1∈H1∩H2,即H1∩H2是正规子群。证毕。利用群的正规子群能够按如下方式构造出一个新的群,这个群比原来的群更简单却又保留了原来群的许多重要性质。设<H,*>为<G,*>的正规子群,令集合G/H={aH|a∈G}(G/H={Ha|a∈G}),即G/H是所有H的陪集组成的集合。在G/H上定义一种运算“·”:∀aH,bH∈G/H,aH·bH=(a*b)H7.3.2正规子群、商群定理设<H,*>为群<G,*>的正规子群,群G的商代数系统<G/H,·>构成群。证明

(1)“·”运算满足结合律。∀x,y,z∈G,有((xH)·(yH))·(zH)=((x*y)H)·(zH)=((x*y)*z)H=x*(y*z)H=(xH)·((y*z)H)=(xH)·((yH)·(zH))(2)eH=H为关于“·”运算的幺元。事实上,∀a∈G,有aH·eH=(a*e)H=aH=eH·aH(3)对每一aH有关于“·”运算的逆元。事实上,∀a∈G,有aH·a-1H=(a*a-1)H=H=a-1H·aH,所以<G/H,·>构成群。证毕。7.3.2正规子群、商群商群相关定义群G的正规子群H的所有陪集在运算aH·bH=(a*b)H下形成的群G/H称为群G关于H的商群(quotientgroup)。显然,商群G/H的阶等于H在G中的指数。当G是有限群时,有|G/H|=|G|/|H|。7.3.2正规子群、商群

7.3.2正规子群、商群

接下来我们讨论群之间的同态映射———群同态。如果存在群G1到群G2上的同态映射,则称群G1与G2同态。当同态映射是双射时,则称群G1与G2同构。定理群<G,*>与它的每个商群<G/H,·>同态。证明

做映射g:G→G/H,∀a∈G,g(a)=aH。而对于∀x,y∈G,有x*y→(x*y)H=xH·yH。因此g是G到G/H上的一个同态映射。证毕。7.3.2正规子群、商群

在介绍同态基本定理之前,我们先讨论同态核的性质。定理设f为群<G1,*1>群<G2,*2>的同态映射,那么f的核K(f)构成<G1,*1>的正规子群(为简明起见,以下用K表示K(f))。证明

不难看出<K(f),*1>为<G1,*1>的一个子群。现∀a∈G,证明aK=Ka。为此设x∈aK,那么有k∈K使得x=a*1k。考虑到f(a*1k*1a-1)=f(a)*2f(e1)*2f(a-1)。又由于f(a-1)=f(a)-1,f(e1)=e2,f(a*1k*1a-1)=f(a)*2f(a)-1=e2,故a*1k*1a-1∈K。由定理知K为G的正规子群。证毕。7.3.2正规子群、商群

下面要介绍的同态基本定理是群论中最重要的定理之一,可由群同态得到一个同构关系。定理设f为群<G1,*1>群<G2,*2>的同态映射,K=K(f),那么商群<G/K,·>与同态像<f(G1),*2>同构。证明

在G/K与f(G1)之间我们建立如下对应关系:σ:(xK)→f(x)x∈G下面表明σ为G/K与f(G1)之间的同构映射。共分四点说明,(1)~(3)说明σ是G/K与f(G1)之间的一一对应,(4)说明σ还保持群的运算关系不变。7.3.2正规子群、商群定理设f为群<G1,*1>群<G2,*2>的同态映射,K=K(f),那么商群<G/K,·>与同态像<f(G1),*2>同构。证明（续）

(1)σ把G/K中的任意元素(xK)只映射为f(G1)中的一个元素。这是因为对于(xK)中的任意代表元xK,有f(x*1k)=f(x)*2f(k)=f(x)*2e2=f(x)。所以在映射σ下G/K中的任意元素(xK)在f(G1)中只有一个像。(2)对于f(G1)中的任意元素b,由于σ是G1到f(G1)的满射,故b在G中至少有一个像源a,即f(a)=b,从而对于σ而言,b在G/K中就至少有一个像源aK,这说明σ是满射。(3)σ也是单射。如果xK≠yK,则x-1*1y∉K,从而f(x-1*1y)≠e2,于是f(x-1)*f(y)≠e2,即f(x)≠f(y)。7.3.2正规子群、商群定理设f为群<G1,*1>群<G2,*2>的同态映射,K=K(f),那么商群<G/K,·>与同态像<f(G1),*2>同构。证明（续）

(4)在映射σ之下,我们有(xK)·(yK)=(x*1y)K→f(x*1y)=f(x)*2f(y)。左面的等式是根据商群G/K中的运算,右面的等式是因为f为同态映射。该式表明σ保持群的运算关系不变。综上,σ为G/K与f(G1)之间的同构映射。证毕。7.3.2正规子群、商群7.1半群与独异点7.2群与子群7.3拉格朗日定理与正规子群7.4特殊群7.5环和域第七章

几种典型的代数系统

循环群是最简单的群之一,已经研究得比较透彻,它的结构是完全确定的。循环群相关定义在群<G,*>中,若存在一个元素a∈G,使得∀x∈G,都存在i∈Z,使得x=ai,则称<G,*>为循环群(cyclicgroup),记作G=<a>,a称为该循环群的一个生成元(generator)。G的所有生成元的集合称为G的生成集。从循环群的定义可以看出,找出群的生成元是判定一个群是不是循环群的关键。7.4.1循环群

证明整数加法群<Z,+>是一个循环群,并求其所有的生成元。证明

假设a∈Z是生成元,则由生成元的定义,∀n∈Z,存在k∈Z,使得n=ak=ka。特别地,取n=1,则有1=ka。又k,a都是整数,所以必然有a=1或a=-1。以上说明,如果a是生成元,则a必须是1或者-1,因此还需进一步验证±1是不是<Z,+>的生成元。因为∀n∈Z,有n=1+1+…+1=1n,n=1+1+…+1=(-1)-1+(-1)-1+…+(-1)-1=((-1)-1)n=(-1)-n,所以±1是生成元,故<Z,+>是循环群,其生成集为{1,-1}。证毕。7.4.1循环群

关于循环群的下列性质是明显的。定理设<G,*>为循环群,a为生成元,则G为阿贝尔群。证明

∀x,y∈G,必有m,n∈Z使得x=am,y=an,所以x*y=am*an=am+n=an+m=an*am=y*x。所以<G,*>为阿贝尔群。证毕。7.4.1循环群

7.4.1循环群

7.4.1循环群

7.4.1循环群

变换群和置换群在现实中有较广泛和非常重要的应用,任何群都可以用变换群表示,任何有限群都可以用置换群表示。置换群相关定义任意集合A上的双射函数称为变换(transformation)。对任意集合A定义集合G,即A≠⌀,G={f|f是A上的变换},∘为函数的复合运算,<G,∘>是群,称为A的全变换群(fulltransformationgroup),记作SA,SA的子群称为A的变换群(transformationgroup)。7.4.2置换群

平面上全体平移组成一个变换群。解

设σ1:α→α+β1(一个双射函数),σ2:α→α+β2,则σ2∘σ1:α→α+(β1+β2),因此∘封闭。σe:α→α是幺元。σ1的逆元为σ-1:α→α-β1。故平面上全体平移组成一个变换群。7.4.2置换群

7.4.2置换群

7.4.2置换群

下面介绍群论中一个非常重要的定理———凯莱定理。定理设G是任意一个群,则:(1)G同构于一个变换群。(2)若G是有限群,则G同构于一个置换群。证明

任取a∈G,定义G上的双射函数fa:G→G如下:fa(x)=a*x。显然fa为双射,令F={fa|a∈G}。7.4.2置换群定理设G是任意一个群,则:(1)G同构于一个变换群。(2)若G是有限群,则G同构于一个置换群。证明（续）

下证<F,∘>为群(∘为函数的复合运算)。①F对∘运算封闭。设fa∈F,fb∈F,那么a∈G,b∈G。考虑fa∘fb:对任意x∈G,有fa∘fb(x)=fb(fa(x))=b*a*x=fb*a(x),即fa∘fb=fb*a。由于b*a∈G,fb*a∈F,故fa∘fb∈F。②

∘运算显然满足结合律。③∘运算有幺元fe∈F。e为群G的幺元。7.4.2置换群定理设G是任意一个群,则:(1)G同构于一个变换群。(2)若G是有限群,则G同构于一个置换群。证明（续）

④F中每一元素fa均有逆fa-1。这是因为由a∈G知a-1∈G,从而fa-1∈F,并且对任意x∈G,有fa∘fa-1(x)=a-1*a*x=x=e*x=fe(x),即fa∘fa-1=fe。7.4.2置换群定理设G是任意一个群,则:(1)G同构于一个变换群。(2)若G是有限群,则G同构于一个置换群。证明（续）

再证<G,*>与<F,∘>同构。为此定义函数h:G→F,使得对任意x∈G,h(x)=fx。显然h为双射。与①同理可证h保持运算,即对G中任意元素x,y,有h(x*y)=fx*y=fy∘fx=h(y)∘h(x)所以<G,*>与<F,∘>同构。证毕。7.4.2置换群

7.4.2置换群

7.4.2置换群

7.4.2置换群

7.4.2置换群求3次对称群S3所有元素,指出哪些是奇置换,哪些是偶置换。解

S3={(1),(12),(13),(23),(123),(132)}。其中(1),(123),(132)为偶置换；(12),(13),(23)为奇置换。7.4.2置换群7.1半群与独异点7.2群与子群7.3拉格朗日定理与正规子群7.4特殊群7.5环和域第七章

几种典型的代数系统

下面介绍群论中一个非常重要的定理———凯莱定理。定理设G是任意一个群,则:(1)G同构于一个变换群。(2)若G是有限群,则G同构于一个置换群。证明

任取a∈G,定义G上的双射函数fa:G→G如下:fa(x)=a*x。显然fa为双射,令F={fa|a∈G}。7.4.2置换群

从这一节起我们要讨论含有两个二元运算的代数结构,首先讨论环。环相关定义设<R,+,·>是代数系统,R为集合,+和·为二元运算,如果:(1)<R,+>为交换群;(2)<R,·>为半群;(3)运算·对于运算+是可分配的,即对任意元素a,b,c∈R,有a·b+c=a·b+a·c,b+c·a=b·a+c·a则称<R,+,·>为环(ring)。7.5.1环

7.5.1环

7.5.1环环相关定义令<R,+,·>是环,若·运算可交换,称R为交换环(commutativerings),当·运算有幺元,称R为含幺环(ringwithunity)。前文(1)(3)(4)(5)是含幺交换环,(2)是含幺环,因为矩阵乘法不可交换。7.5.1环注意(1)在环中通常省略乘法运算·。(2)为了区别环中加法幺元和乘法幺元,通常把加法幺元记作0,乘法幺元记作1。可以证明加法幺元0恰好是乘法的零元。(3)环中关于加法的逆元称为负元,记为-x;关于乘法的逆元称为逆元,记为x-1。环中还可能有下述所谓的零因子。7.5.1环

7.5.1环环有下列基本性质。定理设<R,+,·>是环,0为加法幺元,对任意a,b,c∈R,有(1)a0=0a=0;(2)a(-b)=(-a)b=-ab;(3)(-a)(-b)=ab;(4)a(b-c)=ab-ac;(5)(b-c)a=ba-ca。7.5.1环证明

(1)a0=a(0+0)=a0+a0,因为<R,+>是阿贝尔群,所以满足消去律。因此a0=0。同理可证0a=0。(2)ab+(-a)b=(a+(-a))b=0b=0,因为<R,+>是阿贝尔群,由逆元的唯一性,有(-a)b=-ab。同理可证a(-b)=-ab。(3)(-a)(-b)=-(a(-b))=-(-(ab))=ab。(4)a(b-c)=a(b+(-c))=ab+a(-c)=ab+(-ac)=ab-ac。(5)由(4)同理可证。证毕。7.5.1环域相关定义设<R,+,·>是整环,且R至少含有2个元素,若∀a∈R(a≠0)有a-1∈R,则称R是域(fields)。由定义可见,一个代数系统<R,+,·>是一个域,需要满足以下条件:(1)R对运算+构成交换群。(2)R中全体非零元素组成的集合R*=R-{0}对运算·也构成交换群。(3)运算·对运算+是可分配的。7.5.2域

7.5.2域

7.5.2域

7.5.2域8.1格的概念与性质8.2布尔代数的概念与性质第八章

格与布尔代数类似于环和域,格是另外一种具有两个二元运算的特殊代数系统。关于它的定义有两种形式,一种是从代数系统角度的定义,另一种是从偏序集的角度进行定义。格的相关定义设L是非空集合,*和·是L上的两个二元运算,如果*和·满足交换律、结合律和吸收律,则称<L,*,·>构成格(lattice),也称为代数格。8.1格的概念与性质设在自然数集N上定义两个运算*和·,其中x*y=max(x,y),x·y=min(x,y),试证明<N,*,·>构成了一个代数格。证明

(1)证明*和·满足交换律。∀x,y∈Nx*y=max(x,y)=max(y,x)=y*xx·y=min(x,y)=min(y,x)=y·x所以*和·满足交换律。8.1格的概念与性质设在自然数集N上定义两个运算*和·,其中x*y=max(x,y),x·y=min(x,y),试证明<N,*,·>构成了一个代数格。证明（续）

(2)证明*和·满足结合律。∀x,y,z∈N(x*y)*z=max(max(x,y),z)=max(x,max(y,z))=x*(y*z)(x·y)·z=min(min(x,y),z)=min(x,min(y,z))=x·(y·z)所以*和·满足结合律。8.1格的概念与性质设在自然数集N上定义两个运算*和·,其中x*y=max(x,y),x·y=min(x,y),试证明<N,*,·>构成了一个代数格。证明（续）

(3)证明*和·满足吸收律。∀x,y∈Nx*(x·y)=max(x,min(x,y))=xx·(x*y)=min(x,max(x,y))=x所以*和·满足吸收律。综上,<N,*,·>是一个代数格。证毕。8.1格的概念与性质格的相关定义设<A,≼>是偏序集,如果∀a,b∈A,{a,b}都有上确界和下确界,则称<A,≼>构成格,也称为偏序格。由于上确界和下确界的唯一性,可以把求{a,b}的上确界和下确界看成a与b的二元运算∨和∧,即a与b上确界和下确界分别用a∨b,a∧b表示。8.1格的概念与性质判断下列哪些偏序集是格,并说明理由。(1)<P(A),⊆>,其中P(A)是集合A上的幂集合,⊆为包含关系。(2)<N,≽>,其中N是自然数集,≽为大于或等于关系。(3)<S,D>,其中S={2,3,6,8,12},D为整除关系。解

(1)是格。因为∀a,b∈P(B),都有a∨b=a∪b,a∧b=a∩b,又∪和∩运算在P(B)上是封闭的,即a∪b,a∩b∈P(B)。(2)是格。因为∀x,y∈N,x∨y=max(x,y),x∧y=min(x,y),其运算结果都为自然数。(3)不是格。因为在集合S中,不存在一个数既能被6整除,又能被8整除,即{6,8}没有上确界;同理,在集合S中没有一个数既能整除2,又能整除3,即{2,3}没有下确界。8.1格的概念与性质格具有以下性质。定理设<L,≼>是格,则运算∨和∧满足交换律、结合律、幂等律和吸收律,即(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。8.1格的概念与性质证明

(1)a∨b是{a,b}的上确界,b∨a是{b,a}的上确界。由于{a,b}={b,a},所以a∨b=b∨a,同理可得,a∧b=b∧a。(2)由上确界的定义有:(a∨b)∨c≽a∨b≽a (8.1)(a∨b)∨c≽a∨b≽b (8.2)(a∨b)∨c≽c (8.3)由式(8.2)和(8.3)得(a∨b)∨c≽b∨c (8.4)由式(8.1)和(8.4)得(a∨b)∨c≽a∨(b∨c) (8.5)同理可证(a∨b)∨c≼a∨(b∨c) (8.6)由式(8.5)和(8.6)得(a∨b)∨c=a∨(b∨c)。同理可证(a∧b)∧c=a∧(b∧c)8.1格的概念与性质证明（续）(3)显然a≼a∨a,又由a≼a可得a∨a≼a;根据反对称性有a∨a=a。同理可证,a∧a=a得证。(4)显然a∨(a∧b)≽a (8.7)由a≼a,a∧b≼a可得a∨(a∧b)≼a (8.8)由式(8.7)和(8.8)得a∨(a∧b)=a。同理可证a∧(a∨b)=a。证毕。这个定理说明,格的两个定义本质上是相同的。8.1格的概念与性质接下来讨论几种特殊的格。格的相关定义如果在格<L,≼>中,存在一个元素a∈L,使得∀x∈L均有a≼x(x≼a),则称a为格的全下界(全上界)(相当于偏序集中的最小元、最大元),且记全下界为0,全上界为1。8.1格的概念与性质全下界(全上界)有如下性质。定理全下(上)界如果存在则必唯一。证明

设1和1'均是全上界,则因为1是全上界,所以1'≼1;又因为1'是全上界,所以1≼1'。由≼的反对称性,所以1=1'。同理可证全下界唯一。证毕。在格<P(A),∪,∩>中,A是全上界,⌀是全下界。8.1格的概念与性质格的相关定义如果<L,∧,∨>中既有全上界1,又有全下界0。称0,1为格L的界(bound),并称格L为有界格(boundedlattice)。设<L,∧,∨>是格,如果∀a,b,c∈L,都有a∧(b∨c)=(a∧b)∨(a∧c)a∨(b∧c)=(a∨b)∧(a∨c)则称<L,∧,∨>为分配格(distributivelattice)。<P(A),∪,∩>是分配格,<Z,max,min>也是分配格。8.1格的概念与性质下面我们讨论补格。格的相关定义设<L,∧,∨>是有界格,a为L中任意元素,如果存在元素b∈L使a∨b=1,a∧b=0,则称b是a的补元或补(complements)。补元有下列性质:(1)补元是相互的,即若b是a的补,那么a也是b的补。(2)并非有界格中每个元素都有补元,而有补元也不一定唯一。(3)全下界0与全上界1互为补元且唯一。8.1格的概念与性质格的相关定义如果有界格<L,∧,∨>中每个元素都至少有一个补元,则称L为有补格(complementedlattice)。定理设<L,∧,∨>是有补分配格,若L中某个元素a存在补元,则存在唯一的补元。证明假设a有两个补元b和c,则有a∨b=1,a∧b=0,a∨c=1,a∧c=0。8.1格的概念与性质定理设<L,∧,∨>是有补分配格,若L中某个元素a存在补元,则存在唯一的补元。证明（续）故a∨b=a∨c,a∧b=a∧c。由于L是分配格,b=b∨(b∧a)=b∨(a∧c)=(a∨b)∧(b∨c)=(a∨c)∧(b∨c)=(a∧b)∨c=(a∧c)∨c=c。由此可见,假设不成立。命题得证。证毕。8.1格的概念与性质8.1格的概念与性质8.2布尔代数的概念与性质第八章

格与布尔代数布尔代数相关定义设B是至少有两个元素的有补分配格,则称B是布尔代数(Booleanalgebra)。布尔代数通常记为<B,∨,∧,',0,1>,其中“'”为求补运算。由前面的讨论可知,布尔代数<B,∨,∧,',0,1>具有如下性质:(1)交换律:∀a,b∈B,a∨b=b∨a,a∧b=b∧a。(2)结合律:∀a,b,c∈B,(a∨b)∨c=a∨(b∨c),(a∧b)∧c=a∧(b∧c)。8.2布尔代数的概念与性质（续）(3)幂等律:∀a∈B,a∨a=a,a∧a=a。(4)吸收律:∀a,b∈B,a∨(a∧b)=a,a∧(a∨b)=a。(5)分配律:∀a,b,c∈B,a∨(b∧c)=(a∨b)∧(a∨c),a∧(b∨c)=(a∧b)∨(a∧c)。(6)零一律:∀a∈B,a∨1=1,a∧0=0。(7)同一律:∀a∈B,a∨0=a,a∧1=a。(8)互补律:∀a∈B,a∨a'=1,a∧a'=0。(9)否定律:∀a∈B,(a')'=a。(10)德·摩根律:∀a,b∈B,(a∨b)'=a'∧b',(a∧b)'=a'∨b'。8.2布尔