离散数学-第五-六章

第四篇图论1.命题逻辑2.谓词逻辑3.集合与关系

4.函数6.布尔代数5.代数结构目录７.图论第一篇数理逻辑第二篇集合论第三篇代数结构绪论

第三篇代

数

系统AlgebraSystem代数系统又称为代数结构(抽象代数,近世代数),它是在一个抽象集合上定义了若干抽象代数运算后所组成的系统.

不同的数学结构常常具有相同的代数运算性质,把这些共同的性质抽象出来加以统一研究就形成了代数系统这门学科.

代数系统的理论在逻辑电路设计,形式语言,自动机,数据结构,编码理论等的研究中有广泛的应用.第四篇图论1.命题逻辑2.谓词逻辑3.集合与关系

4.函数6.布尔代数5.代数结构目录７.图论第一篇数理逻辑第二篇集合论第三篇代数结构绪论代数结构AlgebraStructure第五章本章介绍代数系统的一般概念及性质,并介绍几种重要的代数结构类型---群,环,域.第五章代数结构5-1代数系统的引入

5-４群与子群5-５阿贝尔群和循环群5-7陪集和拉格朗日定理5-３半群5-2运算及其性质5-8同态与同构代数系统

>代数系统的引入定义5-1.1

一个从集合An到A的映射(函数)f,称为集合A上的一个n元运算。1)An=A

A

...

A,f:An

A,即

a1,a2,…,an∈A,b∈A,使得

f(a1,a2,…an)=b自变量取自A,函数值也取自A,称运算是封闭的.2)由于运算是函数,故运算的结果是唯一的.当n=1时称为一元运算.

当n=2时称为二元运算,通常用

,+,等表示.5-1代数系统的引入

如f(a,b)=c,则记作:ab=c二元运算的例子

N上+,

是N上二元运算,而-,不是.

整数集I上+,-,

是I上的二元运算,而不是.

R-{0}上的

,

是R-{0}上的二元运算,而+,-不是.矩阵的+,

是N阶实矩阵集合上的二元运算,但不是全体实矩阵集合上的二元运算.

,,,是真值集合{0,1}上的二元运算.

,,是幂集P(A)上的二元运算.一元运算的例子

R上的求绝对值|X|运算.P178例题1

整数I上求负运算是一元运算,但不是N上的一元运算.代数系统

>代数系统的引入

求逆矩阵是n阶可逆实矩阵集合上的一元运算.A={x|x=2n,n

N}对+,*是否封闭?

实数集合上的普通加法和乘法构成代数系统<R

,+,

>

有限集S的幂集P(S)对集合上的代数运算

,,构成代数系统<P(S),,,>.全体原子命题的集合P对逻辑运算

,,构成代数系统

<P,,,>定义5-1.2

一个非空集合A连同若干个定义在该集合上的运算f1,f2,…,fk所组成的系统就称为一个代数系统,记作<A,f1,f2,…,fk>。代数系统

>代数系统的引入例如第五章代数结构5-1代数系统的引入

5-４群与子群5-５阿贝尔群和循环群5-7陪集和拉格朗日定理5-３半群5-2运算及其性质5-8同态与同构代数结构

>运算性质5-2运算性质定义5-2.2

设

是集合A上的二元运算,如果对

x,y∈A,都有x

y=y

x,则称该二元运算

是可交换的。例如实数集上的+,

可交换,但-,

不可交换.集合上的运算

,可交换,但-不可交换.命题集合P上的

,可交换,但不可交换.

例题2Q为有理数集.Q上的运算

:任意的x,y

Q,

x

y=x+y-x*y.

是否可交换.代数结构

>运算性质定义5-2.3

设

是集合A上的二元运算,若对

x,y,z∈A,都有(x

y)

z=x

(y

z),则称该二元运算

是可结合的。例如实数集上的+,

;

集合上的运算

,;,命题集合P上的

,都是可结合的.例题3记:x

x

...

x=x

n则x

n

x

m=x

n+m

(x

n)m

=x

n·m

n

A为非空集合,*定义为:对任意的a,b

A,有

a*b=b.证*可结合的.定义5-2.4

设

是定义在集合A上的一个二元运算,x∈A,若x

x=x,称x是等幂元;若对

x∈A,都有x

x=x,则称运算

是等幂的。例如实数集上的0是+的等幂元,1是的等幂元

;

集合上的运算

,,

命题集合P上的

,都是等幂运算代数结构

>运算性质定义5-2.5

设

,△是定义在集合A上的二元运算,如果对

x,y,z∈A,都有

x

(y△z)=(x

y)△(x

z)(y△z)

x=(y

x)△(z

x)则称该运算

对于△是可分配的。例如实数集上

对+可分配,但+

对不可分配;

集合上的运算

,;,命题集合P上的

,都是相互可分配

例题4何时两式相等?代数结构

>运算性质设集合A={,},A上定义的二元运算如表所示.

对*可分配吗?*对

?定义5-2.6

设

,△是定义在集合A上的两个二元运算,如果对

xy∈A,都有

x

(x△y)=xx△(x

y)=x则称运算

和运算△满足吸收律。例如集合上的运算

,;

命题集合P上的

,都是满足吸收律的实数集上+

,

不满足吸收律;

代数结构

>运算性质定义5-2.7

设

是集合A上的二元运算,1)若

el∈A,对

x∈A,有el

x=x,称el为

的左幺元2)若

er∈A,对

x∈A,有x

er=x,

称er为

的右幺元3)若

e∈A,对

x∈A,有e

x=x

e=x,称e为

的幺元例如实数集上+的幺元是,

的幺元是;

集合运算的幺元是,的幺元是;

逻辑运算

的幺元是,

的幺元是.P180例7

E代数结构

>运算性质TF10*αβγδαδαβγβαβγδγαβγγδαβγδ

αβγδααβδγββαγδγγδαβδδδβγ定理5-2.1

设

是集合A上的二元运算,在A中有关于

的左幺元el和右幺元er,则el=er=e

且幺元唯一定理5-2.3

设

是集合A上的二元运算,且|A|>1。若在A中有关于

的幺元e

和零元

,则e≠.定理5-2.2

设

是集合A上的二元运算,在A中有关于

的左零元

l和右零元

r,则

l=

r=

且零元唯一.定义5-2.8

设

是集合A上的二元运算,1)若

l∈A,对

x∈A,有

l

x=

l,称

l为

的左零元2)若

r∈A,对

x∈A,有x

r=

r,称

r为

的右零元3)若

∈A,对

x∈A

x=x

=

,称

为

的零元

.例如实数集上的的零元是;

集合运算的零元是,的零元是;

逻辑运算

的幺元是,

的幺元是.0+?无零元.ETF代数结构

>运算性质

定义5-2.9

设

是集合A上的二元运算,e是

的幺元

1)若对a∈A,

b∈A,使得b

a=e,称b为a的左逆元;2)若对a∈A,

b∈A,使得a

b=e,称b为a的右逆元;3)若

b∈A,使得b

a=a

b=e,称b是a的逆元.a的逆元记作a-1。P183例题9例整数集上的普通加法<R,+>每个元素x的逆元为-x,

实数集上的普通乘法<R,

>?

集合A关于集合运算

,的逆元?

命题P关于逻辑运算

,的逆元?代数结构

>运算性质定理5-2.4设

是集合A上的可结合二元运算,

e为

的幺元,若

a∈A都有左逆,则左逆=右逆=逆元,且逆元唯一。P184例题12若结合律不成立,则逆元不能保证唯一.作业5-2（2），（5）代数结构

>运算性质本节重点掌握的概念:运算,运算的封闭性,代数系统,运算性质,,特别是特殊元:幺元,零元逆元.本节重点掌握的方法:判定运算的性质,是否封闭,结合,交换,等幂,是否有幺元,零元,逆元等代数结构

>半群

交换律结合律 分配律 等幂元和等幂运算 吸收率 幺元 零元 逆元1.运算(封闭)上节要点回顾2代数系统3运算的性质例题:判断下列运算的性质1.x*y=y2.x*y=x+2y第五章代数结构5-1代数系统的引入

5-４群与子群5-５阿贝尔群和循环群5-7陪集和拉格朗日定理5-３半群5-2运算及其性质5-8同态与同构第五章代数结构

法国数学家。1811-1832,群论创始人

方程有根式解即方程的解由该方程的系数经过有限次加减乘除以及开整数次方等表示。

挪威数学家阿贝尔(1802～1829）：一般高于四次的方程不可能代数求解。特殊的高次方程才可用根式解。

伽罗瓦:把代数方程可解性问题转化为置换群及其子群结构分析的问题。群论开辟了全新的研究领域，最大贡献在于提出了新的思维方式来研究数学,把数学的研究从原来的对数,表达式的研究,扩大到了结构。并把数学运算归类。群论对近世代数的形成和发展产生巨大影响。同时对于物理学、化学的发展，对于二十世纪结构主义哲学的产生和发展产生巨大影响。代数结构

>半群定义5-3.2

设代数系统<S,

>,S

,如果运算

是可结合的二元运算,则称<S,

>为半群。1.半群对给定集合S

及运算

,1)运算

是封闭的,即对

x,y∈S,有x

y∈S(是代数系统)2)运算

是可结合的,即对

x,y,z∈S,有(x

y)

z=x

(y

z)半群的判定:例如<R,+>,<R,

>都是可交换半群.<R,->不是半群.<{0,1},

>,是有限可交换半群,<{0,1},

>不是半群.<P(A),>?<R(A),º>?

n阶矩阵关于运算+和*?5-3半群(semigroup)代数结构

>半群P186例题2设S={a,b,c},S上的二元运算

定义如下,验证<S,

>构成半群.定理5-3.1

设<S,

>是一个半群,B

S,且

在B上封闭,则<B,

>也是半群。称<B,

>是半群<S,

>的子半群(subsemigroup)。

<[0,1],

>,<I,

>

是<R,

>的子半群.定理5-3.2

设<S,

>是一个有限半群,则必有a∈S,使得a

a=a。半群的性质有限半群必有等幂元.代数结构

>半群

<N,+>,<I,+

>

是<R,+

>的子半群.

<N奇数

,+>是<N,+>

的子半群?2

独异点(monoid)定义5-3.3

含有幺元的半群称为独异点。例如<R,+>是独异点,幺元为0,<I+,+>不是.<R,*>,

<I,*>都是独异点,幺元为1<{0,1},

>,<{0,1},

>都是独异点,幺元分别为0和1.<P(S),

>和<P(S),

>是独异点?

对给定集合S

及运算*,1)

是封闭的,即对

x,y∈S,有x

y∈S(是代数系统)2)

是可结合的,即对

x,y,z∈S,有(x

y)

z=x

(y

z)3)有幺元,即

e∈S,对

x∈S,有e

x=x

e=x.

独异点的判定:代数结构

>半群独异点的性质定理5-3.3

设<S,*>是独异点,则在*的运算表中,任何两行或两列都是不相同的.定理5-3.4

设<S,*>是独异点，对

a,b∈S,若a,b均有逆元，则

1)(a-1)-1=a2)a*b有逆元，且(a*b)-1=b-1*a-1代数结构

>半群定理条件可减弱.因为<S,*>满足结合律,由定理3-2.4,任一元素若有左逆,则左逆=逆元.第五章代数结构5-1代数系统的引入

5-４群与子群5-５阿贝尔群和循环群5-7陪集和拉格朗日定理5-３半群5-2运算及其性质5-8同态与同构代数结构

>群与子群5-4群与子群定义5-4.1

若独异点<G,

>中每个元素均有逆元,则称<G,

>是一个群。若G为有限集,称该群为有限群.否则为无限群.若|G|=n,称为n阶群.1群的定义对给定集合G

及运算*,1)

是封闭的,即对

x,y∈G,有x

y∈G(是代数系统)2)

是可结合的,即对

x,y,z∈G,有(x

y)

z=x

(y

z)3)有幺元,即

e∈G,对

x∈G,有e

x=x

e=x.

4)有逆元

x∈G,有x-1∈G.

群的判定:例如<I,+>

(整数加群),<NK,+K>,<R-{0},*>,<Mn

n,*>是群

<R,*>,<P(S),

>,<{0,1},

>是群?P191例题1

5).群的运算表中的每一行或每一列都是G的元素的一个置换。定理5-4.1

定理5-4.5

设<G,

>是群,1).群无零元。

2).对

a,b∈G,必存在唯一的x∈G,使得a

x=b

3).对

a,b,c∈G,若有a

b=a

c或b

a=c

a,

则b=c(消去律)2群的性质

4).幺元e是唯一的等幂元。代数结构

>群与子群非空有限集合S上的一个双射称为S的一个置换.课堂练习代数结构

>群与子群1、整数加法构成群（）2、<R,*>,x*y=1/2(x+y),则每个元素可逆（）3、对减法封闭的集合对加法也封闭吗？4、A={n|n和5互质}则A对+封闭吗？5、B={n|n整除30}则A对+封闭吗？6、已知G=<P({a,b}),

>为半群,其中P({a,b})为{a，b}的幂集，

为集合的并运算。G有幺元吗?G有零元吗?说明G为什么不是群?7、已知<R,*>,*定义为a*b=a+2b,确定<R,*>是否为群。代数结构

>群与子群群论半群:

封闭.

可结合.独异点:

封闭.

可结合.有幺元.群无零元;ax=b有唯一解;e是唯一等幂元;消去律;运算表是置换.

封闭,

可结合,有幺元,有逆元.性质:判定是否为群<R,*>,x*y=x+y-2定义5-4.5

定义5-4.6

设<G,

>是群,S

G且S,如果<S,

>也构成群,则称<S,

>是<G,

>的一个子群.若S={

e

},或S=G,则称<S,

>为<G,

>的平凡子群.3子群及性质定理5-4.6

设<S,

>是群<G,

>的子群,则<G,

>的幺元e也是<S,

>的幺元。代数结构

>群与子群

1)

对S封闭,即对

x,y∈S,有x

y∈S2)

在S上满足结合律(显然)3)e∈S.

4)

x∈S,有x-1∈S

子群的判定P194例题3<I,+>是群,IE={x|x=2n,n∈I}.证明IE是子群.定理5-4.8

设S是群<G,

>的非空子集,若

a,b∈S,有a

b-1∈S,则<S,

>是<G,

>的子群.代数结构

>群与子群定理5-4.7

设S是群<G,

>的非空有限子集,且运算

在S上封闭,则<S,

>是<G,

>的子群。子群的其他判定条件此定理显然是充分必要的.P196例题5设<H,*>,<K,*

>是群<G,*>的子群,证明<H

K,*>也是.作业5-3(1),（2），(3),（6）5-4(1),（3），(4),（5）代数结构

>群与子群本节重点掌握的概念:半群,独异点,群,子群本节重点掌握的方法:判定给定的代数结构是群,子群

(两种)包括有限(运算表)或无限.集合论小结要点回顾阿贝尔群:交换律3.群论半群:

封闭.

可结合.独异点:

封闭.

可结合.有幺元.循环群:G={ai

|i

I}群子群:有限子群

在S上封闭;

一般子群

a,b∈S,有a

b-1∈S,性质:无零元;ax=b有唯一解;e是唯一等幂元;

消去律;运算表是置换.特殊群拉格朗日定理及推论:子群的阶整除群的阶.对给定集合S

及运算

判定:

封闭,

可结合,有幺元,有逆元.第五章代数结构5-1代数系统的引入

5-４群与子群5-５阿贝尔群和循环群5-7陪集和拉格朗日定理5-３半群5-2运算及其性质5-8同态与同构代数结构

>阿贝尔群和循环群定义5-5.1

如果群<G,

>中的运算

是可交换的,则称该群为阿贝尔群,或称交换群。1阿贝尔群定理5-5.1

设<G,

>是一个群,<G,

>是阿贝尔群的充要条件是对于任意的a,b∈G,有

(a

b)

(a

b)=(a

a)

(b

b)P197例题1P198例题25-5阿贝尔群和循环群例如<I,+>

是阿贝尔群.定义5-5.2

设<G,

>是群,若存在a∈G,使得G={a

i|i∈I},则称G为循环群,记作G=(a),元素a称为循环群G的生成元。2循环群定理5-5.3

设G=(a),若|G|=n,则an=e且G={a,a2,…,an}其中n是使an=e的最小正整数(称n为元素a的周期).定理5-5.2

循环群是阿贝尔群。若<G,

>是群,对

a∈G,则(a)是G的子群.代数结构

>阿贝尔群和循环群群满足封闭和结合律,对

a∈G,记an=an-1a,n∈I+又因为e∈G,若记e＝a0,则有an∈G,n∈N又因为

a∈G,a-1∈G,若记a-n=(a-1)n.则有an∈G,n∈IP200例题3例如

<I,+>

是循环群.第五章代数结构5-1代数系统的引入

5-４群与子群5-５阿贝尔群和循环群5-7陪集和拉格朗日定理5-３半群5-2运算及其性质5-8同态与同构代数结构

>陪集与拉格朗日定理5-7拉格朗日定理群的阶与子群的阶有何关系?定理5-7.1

(拉氏定理)如果G是有限群,<H,

>是<G,

>的子群,且|G|=n,|H|=m,则

m|n推论

1)质数阶群不能有非平凡子群.2)设<G,

>是n阶有限群,则

(a).

a∈G,a的周期必是n的因子且an=e.

(b).如果n为质数,<G,

>必是循环群。P210例题1,2代数结构

>陪集与拉格朗日定理

设k={e,a,b,c},二元运算如表所示,说明<K,*>不是一个循环群（克莱因四阶群）。P210例题1*eabCeeabcaaecbbbceaccbaeP210例题2任何四阶群只可能是克莱因四阶群或循环群代数结构课堂练习1.6阶群不可能有4阶子群.()2.若群中每个元素以自身为逆,则是交换群.()3.群的等幂元集合构成它的子群.()4.偶数阶有限群中,周期为2的元素个数一定是奇数.()5.设V=<I,+>,I为整数集合,＋为普通加法.则命题为假的是A.<I,+>是群B.<I,+>是循环群C.<I,+>交换群D.不是A,B,C6.设G=<{e,a,b},*>为群,其运算表为_,单位元为_,b的逆元为_7.已知G=<P({a,b}),

>为半群,其中

为集合的并运算,判断

G是否为群?8.设G=(a)是6阶循环群,求G的所有子群.作业5-7(1),（a），(b),

(3),（5)代数结构

>群与子群5-5(1),(3),（5)本节重点掌握的概念:生成元,循环群,元素的周期,群与子群的数量关系本节重点掌握的方法:判定给定的代数结构是交换群,循环群(包括运算表)第五章代数结构5-1代数系统的引入

5-４群与子群5-５阿贝尔群和循环群5-7陪集和拉格朗日定理5-３半群5-2运算及其性质5-8同态与同构定义5-8.1

设<A,

>和<B,

>是两个代数系统,

和

是二元运算,f是A

B的一个映射,使得

a1,a2∈A,有f(a1

a2)=f(a1)

f(a2)称f为由<A,

>到<B,

>的一个同态映射.称代数系统<A,

>同态于<B,

>记作A～B。称代数系统<f(A),

>为<A,

>的同态象。代数结构

>同态与同构a2a1a1

a2f(a1

a2)f(a2)f(a1)ff(a1)

f(a2)同态方程运算的像等于像的运算.5-8同态(homomorphism)与同构(isomorph)例1

设f:NN

为f(x)=2x则f是<N

,+

>到<N

,

+

>的同态映射.代数结构>

同态与同构P214例题1例2

设f:RR定义为

f(x)=5x

则f是<R

,+

>到<R

,

>的单一同态.定义5-8.3

若f是<A,

>到<A,

>的同态,称f为自同态;若f是<A,

>到<A,

>的同构,称f为自同构.定义5-8.2

设f是由<A,

>到<B,

>的一个同态,若

1)f满射的,f称为满同态；

2)f是入射的,f称为单一同态；

3)f是双射的,f称为同构映射,并称

<A,

>和<B,

>是同构的,记作A

B。例3

设f:NNk

定义为f(x)=xmod

k,

则f是<N

,+

>到<Nk

,

+k

>的满同态.例4

设f:RR

为f(x)=2x则f是<R

,+

>到<R

,

+

>的同构映射.定理5-8.2

设f是从<A,

>到<B,

>的同态映射。(a)如果<A,

>是半群,则<f(A),

>也是半群。(b)如果<A,

>是独异点,则<f(A),

>也是独异点.(c)如果<A,

>是群,则<f(A),

>也是群。定理5-8.1

代数系统间的同构关系是等价关系.同态映射保持运算性质不变.代数结构>

同态与同构定义5-8.5

设<A,

>是代数系统,R是A上的一个等价关系称R为A上关于

的同余关系。若当<a1,a2>,<b1,b2>∈R,有<a1

b1,

a2

b2>∈R同余关系确定的A等价类称为同余类.*

正规子群,商群和同态基本定理代数结构>

同态与同构定理5-8.4

设<A,

>是代数系统,R是A上同余关系,则代数系统<A/R,

>(商代数)是<A,

>的同态像.其中定义为

:[a1]

,[a2]∈A/R,[a1]

[a2]=[a1

a2]

定理

设<H,

>是群<G,

>的正规子群,则关于H的左(右)陪集关系是<G,

>上的同余关系。定义

设<H,

>是群<G,

>的子群,若

a∈G,有aH=Ha

称H为G的正规子群(normalsubgroup)定理由群<G,

>的正规子群<H,

>确定的商代数<G/H,

>是群(商群),其中G/H={aH}或{Ha}.代数结构>

同态与同构定义5-8.4

设f是由群<G,★>到群<G

,

>的一个同态,e

是G

的幺元,记ker(f

)={x|x

G且f(x)=e

},称ker(f)为G的核

(同态核).定理5-8.3

设f是由群<G,★>到<G‘,

>的同态映射,则同态核Kerf

是G的正规子群。同态基本定理:设f是由群<G,★>到群<G‘,

>的同态映射,则商群<G/K

,>与<f(G’),

>同构。这里K=Kerf.代数结构>

同态与同构1.设V1=<R,+>,V2=<R,*>,+,*为普通加法和乘法,令

:R

R,

(x)=ex,下面四个命题为真的是()A.

是V1到V2的满同态B.

是V1到V2的单同态

C.

是V1到V2的同构D.

是V1到V2的映射,但不是A,B,C2.设V=<N,+>,

:N

N,

(x)=2x,下面四个命题为真的是()A.

是满同态B.

是单自同态

C.

是自同构D.

是到自身的映射但不是A,B,C3.设f,g是<S,+>,到<V,*>的同态,*满足结合和交换律,则

H(x)=f(x)*g(x)也是<S,+>,到<V,*>的同态.课堂练习作业

(6),（11）5-8(1),(2),（4),代数结构>

同态与同构本节重点掌握的概念:同态,同构的定义,同态方程,群同态定理.本节重点掌握的方法:判定给定的代数系统是同态或同构的.代数结构小结代数结构小结集合论小结1.代数系统<A,*>:非空集A及其上的运算组成的系统.2.运算性质交换律:

对

x,y∈A,有x

y=y

x,结合律:

对

x,y,z∈A,有(x

y)

z=x

(y

z)等幂律:

x∈A,有x

x=x消去律:若x

z=y

z,z

x=z

y,则x=y

分配律:

x,y,z∈A,有x

(y△z)=(x

y)△(x

z)(y△z)

x=(y

x)△(z

x)吸收律:

对

xy∈A,有x

(x△y)=x,x△(x

y)=x幺元:

e∈A,对

x∈A,有e

x=x

e=x.

零元:

∈A,对

x∈A

x=x

=

逆元:

x∈A,有x-1∈A.

重点掌握的基本内容(一)运算

是封闭的,即对

x,y∈A,有x

y∈A.集合论小结重点掌握的基本内容(之二)阿贝尔群:交换律3.群论半群:

封闭.

可结合.独异点:

封闭.

可结合.有幺元.循环群:G={ai

|i

I}群子群:有限子群

在S上封闭;

一般子群

a,b∈S,有a

b-1∈S,性质:无零元;ax=b有唯一解;e是唯一等幂元;

消去律;运算表是置换.特殊群拉格朗日定理及推论:子群的阶整除群的阶.对给定集合S

及运算

判定:

封闭,

可结合,有幺元,有逆元.集合论小结4.同态同构重点掌握的基本内容(之三)同态f:

a1,a2∈A,有f(a1

a2)=f(a1)

f(a2)满同态:

b∈B,

a∈A,使得b=f(a)单一同态:若a1

a2则f(a1)

f(a2)同构:同态映射是满射和入射的.性质:设f是从<A,

>到<B,

>的同态映射。

(a)如果<A,

>是半群,则<f(A),

>也是半群

(b)如果<A,

>是独异点,则<f(A),

>也是.(c)如果<A,

>是群,则<f(A),

>也是群。设f是代数系统<A,

>

<B,

>的一个映射集合论小结代数系统半群独异点群阿贝尔群循环群同态同构结合律幺元逆元子群生成元交换律集合论小结常考知识点1.运算的性质4.交换群与循环群2.群的判定3.子群的判定6.判定同态同构5.拉格朗日定理的应用P1852),5)P1901),5)P1971),3),5)P1973),4),2111)5)P2211),2),6),11)P2128)P2001),2),3),5)补例:给出克来因四阶群的所有子群第四篇图论1.命题逻辑2.谓词逻辑3.集合与关系

4.函数6.格与布尔代数5.代数结构目录７.图论第一篇数理逻辑第二篇集合论第三篇代数结构绪论格与布尔代数LatticeandBoole-Algebra第六章格是一种特殊偏序集,它对应于一个具有两个二元运算的代数系统.在这个系统上强调元素间的次序关系,当格满足一定条件就称为布尔格,布尔格对应的代数系统就是布尔代数.本章介绍格的概念,性质和特殊格,以及有限布尔代数的基数,并讨论布尔代数之间的关系.第六章格与布尔代数6-1格的概念

6-４布尔代数6-３有补格6-2分配格格与布尔代数>格的概念6-1格的概念定义6-1.1

设<A,

>是偏序集,若A中任二元素都有最小上界(LUB)和最大下界(GLB),则称<Ａ,

>为格.例如设<A,

>为偏序,

a,b∈A,上确界:若

c∈A,使得

a

c且

b

c.

若

x∈A,也有a

x且

b

x,则必有c

x.下确界:若

c∈A,使得c

a且

c

b.

若

x∈A,也有x

a且

x

b,则必有c

x.格的判定任意偏序集,其任二元素组成的子集不一定都有上下确界.例1整数集合上整除关系<I+,|>为格.

因为

a,b∈I+

LUB{a,b}=a,b的最小公倍;GLB{a,b}=a,b的最大公因子例2<P(S),

>为格.因为

S1,S2∈S,

LUB{S1,S2}=S1

S2,GLB{S1,S2}=S1

S2

1)若两点有链相连,则上层点为上确界,下层点为下确界;2)若两点无链,但有唯一共同的覆盖,该覆盖即为上确界;

若有唯一共同的下层交点,该点即为下确界.格的哈斯图判定e例如格与布尔代数>格的概念e例3

由例2知,<P(S),

>诱导的代数系统即<P(S),,

>.定义6-1.2

设<A,

>为格,定义A上的两个二元运算∨和∧为:

a,b∈A,a∨b=LUB{a,b},a∧b=GLB{a,b}称<A,∨,∧>为由格<A,

>所诱导的代数系统。二元运算∨和∧分别称为并运算和交运算。{

}{a}{b}{a,b}在格<A,

>中,任二元素对应唯一的上确界和下确界.故可将上下确界看作是集合A上的两个二元运算.格与布尔代数>格的概念{

}{a}{

}{a}{b}{c}{a,c}{c,b}{a,b}{a,b,c}定义6-1.3

设<A,

>是格,其诱导的代数系统为<A,∨,∧>,设B

A且B≠

,如果运算∨和∧关于B封闭,则称<B,

>是<A,

>的子格。子格是格,但一子集构成格时,不一定是子格.子格通过将格和代数系统对应起来,使我们可将代数系统的有关方法和结论用于格.例如例题1格与布尔代数>格的概念aa设<S,

>是格,任取a

S,T={x|x

s,且x

a},证T是子格.对偶原理

设P是对任意格为真的一个命题,命题中仅包含∨,∧及

,,如在P中把∨换成∧、∧

换成

∨、

换成、

换成

,就得到另一个命题P’(P的对偶命题),则P’则对任意格也成立.格的性质定理6-1.2

在一个格<A,

>中,对

a,b,c,d∈A,如果a

b,c

d,则

1)a∨c

b∨d2)a∧c

b∧d定理6-1.1

在一个格<A,

>中,对

a,b∈A,都有:1)a

a∨b，b

a∨b.2)a∧b

a，a∧b

b推论

在一个格<A,

>中,对

a,b,c∈A,如果b

c则 1)a∨b

a∨c2)a∧b

a∧c格与布尔代数>格的概念定理6-1.3

设<A,

>是格,其诱导的代数系统为<A,∨,∧>,则对

a,b,c,d∈A，有

(1)a∨b=b∨a,a∧b=b∧a(交换律)(2)a∨(b∨c)=(a∨b)∨ca∧(b∧c)=(a∧b)∧c(结合律)(3)a∨a=a,a∧a=a(幂等律)(4)a∨(a∧b)=a,a∧(a∨b)=a(吸收律)引理6-1.1

设<A,∨,∧>是一个代数系统,其中∨,∧都是二元运算且满足吸收,则∨和∧都满足幂等性.格诱导的代数系统的性质格与布尔代数>格的概念该定理说明格与一个代数系统一一对应.定理6-1.4

设<A,∨,∧>是代数系统,∨和∧满足交换、结合和吸收,则A上存在偏序关系

,使<A,

>是一个格。定理6-1.6

设<A,

>是格,对

a,b∈A,有

a

b

a∧b=a

a∨b=b定理6-1.7

设<A,

>是格,对

a,b,c∈A,有

a

c

a∨(b∧c)

(a∨b)∧c格与布尔代数>格的概念等式成立称为分配格.等式成立称为模格.定理6-1.5

在格<A,

>中,对

a,b,c∈A,有(分配不等式)

a∨(b∧c)

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

a∧(b∨c)推论

设<A,

>是格,对

a,b,c∈A,有

(a∧b)∨(a∧c)

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

(a∨b)∧(a∨c)定义6-1.4

设格<A1,

1>和<A2,

2>诱导代数系统分别为<A1,∨1,∧1>和<A2,∨2,∧2>,若

f:A1

A2,使得对

a,b∈A1,有

f(a∨1b)=f(a)∨2f(b),f(a∧1b)=f(a)∧2f(b)称f为从<A1,∨1,∧1>到<A2,∨2,∧2>格同态.称<f(A1),

2>为<A1,

1>的格同态象。若f双射,称f为<A1,∨1,∧1>到<A2,∨2,∧2>的格同构.亦称<A1,

1>和<A2,

2>这两个格是同构的。格与布尔代数>格的概念格同态利用格与代数系统的关系引入格同态概念.定理6-1.8

设f是格<A1,

1>到<A2,

2>的格同态,则对

x,y∈A1,若x

1y,必有f(x)

2

f(y).定理6-1.9

设<A1,

1>,<A2,

2>为格,f是从A1到A2的双射,则f是<A1,

1>到<A2,

2>的格同构,iff

a,b∈A1,a

1b

f(a)

2f(b)格与布尔代数>格的概念同态映射必是保序映射,但反之不然.ebca例如d设<S,

>为格,S={a,b,c,d,e},f:SP(S),

x∈S,f(x)={y|y∈S,y

x}则f(a)=S,f(b)={b,e},f(c)={c,e},f(d)={d,e},f(e)={e}

f是<S,

>到<P(S),

>的保序映射,

x

y时,f(x)

f(y)但f不是同态映射,

f(b∨d)=f(a)=S

f(b)

f(d)={d,b,e}保序映射作业6-1(1),(2),（5)格与布尔代数>格的概念第六章格与布尔代数6-1格的概念

6-４布尔代数6-５布尔表达式6-３有补格6-2分配格格与布尔代数>分配格定义6-2.1

设<A,∨,∧>是由格<A,

>所诱导的代数系统如果

a,b,c∈A,满足

a∧(b∨c)=(a∧b)∨(a∧c)(交对并可分配)

a∨(b∧c)=(a∨b)∧(a∨c)(并对交可分配)则称<A,

>是分配格.例1格<P(S),

>诱导的代数系统为<P(S),,>,

对

A,B,C∈P(S),都有

A

(B

C)=(A

B)

(A

C);A

(B

C)=(A

B)

(A

C)

所以<P(S),

>是分配格.在任意格中,有分配不等式:a∨(b∧c)

(a∨b)∧(a∨c);(a∧b)∨(a∧c)

a∧(b∨c)6-2分配格(Distributivelettice)格是分配格的充要条件是:格中不含与此五元格同构的子格

bcadabceed如图所示的格是分配格吗?分配格的判定abcdfgeabcd例如

g格与布尔代数>分配格?定理6-2.2

每个链是分配格。定理6-2.3

设<A,

>是分配格,对

a,b,c∈A,若

a∧b=a∧c且a∨b=a∨c,则必有b=c(消去律)定理6-2.1

如果在一个格中,交运算对并运算可分配,则并运算对交运算也是可分配的。反之亦然由此可方便地判定一格不是分配格.分配格的性质bcade例如格与布尔代数>分配格第六章格与布尔代数6-1格的概念

6-４布尔代数6-５布尔表达式6-３有补格6-2分配格6-3有补格定义6-3.1、3.2

设<A,

>是一个格,1)如果

a∈A,对

x∈A,都有a

x

则称a为格<A,

>的全下界(最小元),记为0。2)如果

b∈A,对于任意的x∈A,都有x

b

则称b为格<A,≦>的全上界(最大元)。记为1。定理6-3.1、3.2

格的全上界(全下界)若存在必唯一.定义6-3.3

若格中有全上界和全下界,则称该格为有界格.1.有界格(Boundedlettice)格与布尔代数>有补格

x,y有上下确界不能保证

A

有上下确界.如<I,

>有最大小元的格即为有界格.0是∨的幺元,∧的0元;1是∨的0元,∧的幺元.定理6-3.３

设<A,

>是一个有界格,则对

a∈A,必有:a∨0=a

a∧1=a(同一律)

a∨1=1a∧0=0(零一律)格与布尔代数>有补格例1设S为有限集,则格<P(S),

>是有界格,且0=,1=S例2如图所示bcefgahdacbdfe1)全上界:所有点均有路与该点相连且均在其下方;2)全下界:所有点均有路与该点相连且均在其上方,有界格的哈斯图判定定义6-3.4

设<A,

>是一个有界格,对于a∈A,如果

b∈A,使得

a∨b=1

且a∧b=0

则称b是a的补元。2.有补格(Complementedlettice)显然,互补律成立.格与布尔代数>有补格acde01b定义6-3.5

在一个有界格中,如果每元素都至少有一个补元,则称此格为有补格。例如<P(S),

>为有补格,且子集A的补为S-A.例30,1互为补元且唯一.定理6-3.4

在有界分配格中,若有一个元素有补元则必是唯一的。定义6-3.6

一个格如果它既是有补格,又是分配格,则称它为有补分配格。有补分配格中任一元素a的唯一补元记为

P251例4格与布尔代数>有补格a1b0ac1d0abcd01ba,b互补a的补b,c,da,c的补b,d

又例:二元以上的链不是有补格.

求补可看作有补分配格上的一元运算.格与布尔代数>有补格1.有限元素的格都是有界格?()2.元素个数不超过3的格是链.()3.R={x|X

R,0

x

1},证明<R,

>是格,其运算

,是什么?4.如图所示偏序集中,那些是格、有补格、分配格?

(a)

(b)(c)(d)4.给出所有5元格,其中哪些是有补格.哪些是分配格?5.对n=4,12,给出格<Tn,|>的哈斯图.Tn为n的因子集合.6.求出<T12,|>的所有有补元素的补元.7.画出<T12,|>的所有5元子格.8.在格中,若有abc,则必有:ab=bc9.至少含两个元素的有界格中,不存在以自身为补的元素作业6-2(2),（5)6-3(1),(3),（4),(6)格与布尔代数>有补格理解分配格,有界格和有补格的概念,通过哈斯图判断给定偏序关系是否为格,分配格有补格,掌握各种格的结构特征和运算性质第六章格与布尔代数6-1格的概念

6-４布尔代数6-５布尔表达式6-３有补格6-2分配格6-4布尔代数定义6-4.1、6-4.2

一个有补分配格<A,

>称为布尔格。由其诱导的代数系统<A,∨,∧,

>,称为布尔代数。

例1

幂集格<P(S),

>诱导的代数系统为<P(S),,>.

则<P(S),

>是布尔格,<P(S),,,>是布尔代数.

格与布尔代数>布尔代数1)是格:

a,b∈A,a,b有上下确界;2)是有界格:0,1存在.即

a∈A,有0

a和a

1;3)是有补格:

a∈A,

b∈A,使得a∨b=1,a∧b=0

4)是分配格:分配律成立

布尔格判定

在<P(S),

>中,0=

,1=S,

有界格;

又

TP(S),T的补集为S-TP(S),

有补格;

又

在<P(S),,>中分配律成立,

是分配格;格与布尔代数>布尔代数定理6-4.1

对于布尔代数中的任意两个元素a,b,必定有

=a

(对合律),(德.摩根律)定义6-4.3

设<A,∨,∧,ˉ>和<B,∨,∧,ˉ>是两个布尔代数,如果存在着双射f:A

B,对

a,b∈A,都有

f(a∨b)=f(a)∨f(b),f(a∧b)=f(a)∧f(b),则称<A,∨,∧,ˉ>和<B,∨,∧,ˉ>同构。

由前面的讨论已知布尔代数满足如下性质:交换律,结合律,吸收律,等幂律,分配律,消去律,同一律,0-1律.除此之外布尔代数还满足对合律,德.摩根律.布尔代数性质格与布尔代数>布尔代数定义6-4.5

设<A,

>是一个格,且具有全下界0,若

a∈A盖住0,则称a为原子。具有有限个元素的布尔代数称之.有限布尔代数P252例2定理6-4.2

设<A,

>是一个具有全下界的有限格,则对任一b0,至少存在一个原子a,使得a

b.对有限格,原子就是哈斯图中与零有边相连的的元素.a为原子即

0

a,且如果

x使0

x

a则0=x或

x=a.acbd0e如果a,b是原子,且a

b,则a

b=0格与布尔代数>布尔代数引理6-4.2

设<A,∨,∧,ˉ>是有限布尔代数,b是A中非零元,a1,a2,…,ak是A中满足aj

b(j=1,2,…,k)的所有原子,则: