離散數(shù)學-第五-六章

第四篇圖論1.命題邏輯2.謂詞邏輯3.集合與關(guān)系

4.函數(shù)6.布爾代數(shù)5.代數(shù)結(jié)構(gòu)目錄７.圖論第一篇數(shù)理邏輯第二篇集合論第三篇代數(shù)結(jié)構(gòu)緒論

第三篇代

數(shù)

系統(tǒng)AlgebraSystem代數(shù)系統(tǒng)又稱為代數(shù)結(jié)構(gòu)(抽象代數(shù),近世代數(shù)),它是在一個抽象集合上定義了若干抽象代數(shù)運算后所組成的系統(tǒng).

不同的數(shù)學結(jié)構(gòu)常常具有相同的代數(shù)運算性質(zhì),把這些共同的性質(zhì)抽象出來加以統(tǒng)一研究就形成了代數(shù)系統(tǒng)這門學科.

代數(shù)系統(tǒng)的理論在邏輯電路設計,形式語言,自動機,數(shù)據(jù)結(jié)構(gòu),編碼理論等的研究中有廣泛的應用.第四篇圖論1.命題邏輯2.謂詞邏輯3.集合與關(guān)系

4.函數(shù)6.布爾代數(shù)5.代數(shù)結(jié)構(gòu)目錄７.圖論第一篇數(shù)理邏輯第二篇集合論第三篇代數(shù)結(jié)構(gòu)緒論代數(shù)結(jié)構(gòu)AlgebraStructure第五章本章介紹代數(shù)系統(tǒng)的一般概念及性質(zhì),并介紹幾種重要的代數(shù)結(jié)構(gòu)類型---群,環(huán),域.第五章代數(shù)結(jié)構(gòu)5-1代數(shù)系統(tǒng)的引入

5-４群與子群5-５阿貝爾群和循環(huán)群5-7陪集和拉格朗日定理5-３半群5-2運算及其性質(zhì)5-8同態(tài)與同構(gòu)代數(shù)系統(tǒng)

>代數(shù)系統(tǒng)的引入定義5-1.1

一個從集合An到A的映射(函數(shù))f,稱為集合A上的一個n元運算。1)An=A

A

...

A,f:An

A,即

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

f(a1,a2,…an)=b自變量取自A,函數(shù)值也取自A,稱運算是封閉的.2)由于運算是函數(shù),故運算的結(jié)果是唯一的.當n=1時稱為一元運算.

當n=2時稱為二元運算,通常用

,+,等表示.5-1代數(shù)系統(tǒng)的引入

如f(a,b)=c,則記作:ab=c二元運算的例子

N上+,

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

整數(shù)集I上+,-,

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

R-{0}上的

,

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

是N階實矩陣集合上的二元運算,但不是全體實矩陣集合上的二元運算.

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

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

R上的求絕對值|X|運算.P178例題1

整數(shù)I上求負運算是一元運算,但不是N上的一元運算.代數(shù)系統(tǒng)

>代數(shù)系統(tǒng)的引入

求逆矩陣是n階可逆實矩陣集合上的一元運算.A={x|x=2n,n

N}對+,*是否封閉?

實數(shù)集合上的普通加法和乘法構(gòu)成代數(shù)系統(tǒng)<R

,+,

>

有限集S的冪集P(S)對集合上的代數(shù)運算

,,構(gòu)成代數(shù)系統(tǒng)<P(S),,,>.全體原子命題的集合P對邏輯運算

,,構(gòu)成代數(shù)系統(tǒng)

<P,,,>定義5-1.2

一個非空集合A連同若干個定義在該集合上的運算f1,f2,…,fk所組成的系統(tǒng)就稱為一個代數(shù)系統(tǒng),記作<A,f1,f2,…,fk>。代數(shù)系統(tǒng)

>代數(shù)系統(tǒng)的引入例如第五章代數(shù)結(jié)構(gòu)5-1代數(shù)系統(tǒng)的引入

5-４群與子群5-５阿貝爾群和循環(huán)群5-7陪集和拉格朗日定理5-３半群5-2運算及其性質(zhì)5-8同態(tài)與同構(gòu)代數(shù)結(jié)構(gòu)

>運算性質(zhì)5-2運算性質(zhì)定義5-2.2

設

是集合A上的二元運算,如果對

x,y∈A,都有x

y=y

x,則稱該二元運算

是可交換的。例如實數(shù)集上的+,

可交換,但-,

不可交換.集合上的運算

,可交換,但-不可交換.命題集合P上的

,可交換,但不可交換.

例題2Q為有理數(shù)集.Q上的運算

:任意的x,y

Q,

x

y=x+y-x*y.

是否可交換.代數(shù)結(jié)構(gòu)

>運算性質(zhì)定義5-2.3

設

是集合A上的二元運算,若對

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

y)

z=x

(y

z),則稱該二元運算

是可結(jié)合的。例如實數(shù)集上的+,

;

集合上的運算

,;,命題集合P上的

,都是可結(jié)合的.例題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.證*可結(jié)合的.定義5-2.4

設

是定義在集合A上的一個二元運算,x∈A,若x

x=x,稱x是等冪元;若對

x∈A,都有x

x=x,則稱運算

是等冪的。例如實數(shù)集上的0是+的等冪元,1是的等冪元

;

集合上的運算

,,

命題集合P上的

,都是等冪運算代數(shù)結(jié)構(gòu)

>運算性質(zhì)定義5-2.5

設

,△是定義在集合A上的二元運算,如果對

x,y,z∈A,都有

x

(y△z)=(x

y)△(x

z)(y△z)

x=(y

x)△(z

x)則稱該運算

對于△是可分配的。例如實數(shù)集上

對+可分配,但+

對不可分配;

集合上的運算

,;,命題集合P上的

,都是相互可分配

例題4何時兩式相等?代數(shù)結(jié)構(gòu)

>運算性質(zhì)設集合A={,},A上定義的二元運算如表所示.

對*可分配嗎?*對

?定義5-2.6

設

,△是定義在集合A上的兩個二元運算,如果對

xy∈A,都有

x

(x△y)=xx△(x

y)=x則稱運算

和運算△滿足吸收律。例如集合上的運算

,;

命題集合P上的

,都是滿足吸收律的實數(shù)集上+

,

不滿足吸收律;

代數(shù)結(jié)構(gòu)

>運算性質(zhì)定義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為

的幺元例如實數(shù)集上+的幺元是,

的幺元是;

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

邏輯運算

的幺元是,

的幺元是.P180例7

E代數(shù)結(jié)構(gòu)

>運算性質(zhì)TF10*αβγδαδαβγβαβγδγαβγγδαβγδ

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

設

是集合A上的二元運算,在A中有關(guān)于

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

且幺元唯一定理5-2.3

設

是集合A上的二元運算,且|A|>1。若在A中有關(guān)于

的幺元e

和零元

,則e≠.定理5-2.2

設

是集合A上的二元運算,在A中有關(guān)于

的左零元

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

=

,稱

為

的零元

.例如實數(shù)集上的的零元是;

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

邏輯運算

的幺元是,

的幺元是.0+?無零元.ETF代數(shù)結(jié)構(gòu)

>運算性質(zhì)

定義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例整數(shù)集上的普通加法<R,+>每個元素x的逆元為-x,

實數(shù)集上的普通乘法<R,

>?

集合A關(guān)于集合運算

,的逆元?

命題P關(guān)于邏輯運算

,的逆元?代數(shù)結(jié)構(gòu)

>運算性質(zhì)定理5-2.4設

是集合A上的可結(jié)合二元運算,

e為

的幺元,若

a∈A都有左逆,則左逆=右逆=逆元,且逆元唯一。P184例題12若結(jié)合律不成立,則逆元不能保證唯一.作業(yè)5-2（2），（5）代數(shù)結(jié)構(gòu)

>運算性質(zhì)本節(jié)重點掌握的概念:運算,運算的封閉性,代數(shù)系統(tǒng),運算性質(zhì),,特別是特殊元:幺元,零元逆元.本節(jié)重點掌握的方法:判定運算的性質(zhì),是否封閉,結(jié)合,交換,等冪,是否有幺元,零元,逆元等代數(shù)結(jié)構(gòu)

>半群

交換律結(jié)合律 分配律 等冪元和等冪運算 吸收率 幺元 零元 逆元1.運算(封閉)上節(jié)要點回顧2代數(shù)系統(tǒng)3運算的性質(zhì)例題:判斷下列運算的性質(zhì)1.x*y=y2.x*y=x+2y第五章代數(shù)結(jié)構(gòu)5-1代數(shù)系統(tǒng)的引入

5-４群與子群5-５阿貝爾群和循環(huán)群5-7陪集和拉格朗日定理5-３半群5-2運算及其性質(zhì)5-8同態(tài)與同構(gòu)第五章代數(shù)結(jié)構(gòu)

法國數(shù)學家。1811-1832,群論創(chuàng)始人

方程有根式解即方程的解由該方程的系數(shù)經(jīng)過有限次加減乘除以及開整數(shù)次方等表示。

挪威數(shù)學家阿貝爾(1802～1829）：一般高于四次的方程不可能代數(shù)求解。特殊的高次方程才可用根式解。

伽羅瓦:把代數(shù)方程可解性問題轉(zhuǎn)化為置換群及其子群結(jié)構(gòu)分析的問題。群論開辟了全新的研究領域，最大貢獻在于提出了新的思維方式來研究數(shù)學,把數(shù)學的研究從原來的對數(shù),表達式的研究,擴大到了結(jié)構(gòu)。并把數(shù)學運算歸類。群論對近世代數(shù)的形成和發(fā)展產(chǎn)生巨大影響。同時對于物理學、化學的發(fā)展，對于二十世紀結(jié)構(gòu)主義哲學的產(chǎn)生和發(fā)展產(chǎn)生巨大影響。代數(shù)結(jié)構(gòu)

>半群定義5-3.2

設代數(shù)系統(tǒng)<S,

>,S

,如果運算

是可結(jié)合的二元運算,則稱<S,

>為半群。1.半群對給定集合S

及運算

,1)運算

是封閉的,即對

x,y∈S,有x

y∈S(是代數(shù)系統(tǒng))2)運算

是可結(jié)合的,即對

x,y,z∈S,有(x

y)

z=x

(y

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

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

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

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

n階矩陣關(guān)于運算+和*?5-3半群(semigroup)代數(shù)結(jié)構(gòu)

>半群P186例題2設S={a,b,c},S上的二元運算

定義如下,驗證<S,

>構(gòu)成半群.定理5-3.1

設<S,

>是一個半群,B

S,且

在B上封閉,則<B,

>也是半群。稱<B,

>是半群<S,

>的子半群(subsemigroup)。

<[0,1],

>,<I,

>

是<R,

>的子半群.定理5-3.2

設<S,

>是一個有限半群,則必有a∈S,使得a

a=a。半群的性質(zhì)有限半群必有等冪元.代數(shù)結(jié)構(gòu)

>半群

<N,+>,<I,+

>

是<R,+

>的子半群.

<N奇數(shù)

,+>是<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(是代數(shù)系統(tǒng))2)

是可結(jié)合的,即對

x,y,z∈S,有(x

y)

z=x

(y

z)3)有幺元,即

e∈S,對

x∈S,有e

x=x

e=x.

獨異點的判定:代數(shù)結(jié)構(gòu)

>半群獨異點的性質(zhì)定理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代數(shù)結(jié)構(gòu)

>半群定理條件可減弱.因為<S,*>滿足結(jié)合律,由定理3-2.4,任一元素若有左逆,則左逆=逆元.第五章代數(shù)結(jié)構(gòu)5-1代數(shù)系統(tǒng)的引入

5-４群與子群5-５阿貝爾群和循環(huán)群5-7陪集和拉格朗日定理5-３半群5-2運算及其性質(zhì)5-8同態(tài)與同構(gòu)代數(shù)結(jié)構(gòu)

>群與子群5-4群與子群定義5-4.1

若獨異點<G,

>中每個元素均有逆元,則稱<G,

>是一個群。若G為有限集,稱該群為有限群.否則為無限群.若|G|=n,稱為n階群.1群的定義對給定集合G

及運算*,1)

是封閉的,即對

x,y∈G,有x

y∈G(是代數(shù)系統(tǒng))2)

是可結(jié)合的,即對

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,+>

(整數(shù)加群),<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群的性質(zhì)

4).幺元e是唯一的等冪元。代數(shù)結(jié)構(gòu)

>群與子群非空有限集合S上的一個雙射稱為S的一個置換.課堂練習代數(shù)結(jié)構(gòu)

>群與子群1、整數(shù)加法構(gòu)成群（）2、<R,*>,x*y=1/2(x+y),則每個元素可逆（）3、對減法封閉的集合對加法也封閉嗎？4、A={n|n和5互質(zhì)}則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,*>是否為群。代數(shù)結(jié)構(gòu)

>群與子群群論半群:

封閉.

可結(jié)合.獨異點:

封閉.

可結(jié)合.有幺元.群無零元;ax=b有唯一解;e是唯一等冪元;消去律;運算表是置換.

封閉,

可結(jié)合,有幺元,有逆元.性質(zhì):判定是否為群<R,*>,x*y=x+y-2定義5-4.5

定義5-4.6

設<G,

>是群,S

G且S,如果<S,

>也構(gòu)成群,則稱<S,

>是<G,

>的一個子群.若S={

e

},或S=G,則稱<S,

>為<G,

>的平凡子群.3子群及性質(zhì)定理5-4.6

設<S,

>是群<G,

>的子群,則<G,

>的幺元e也是<S,

>的幺元。代數(shù)結(jié)構(gòu)

>群與子群

1)

對S封閉,即對

x,y∈S,有x

y∈S2)

在S上滿足結(jié)合律(顯然)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,

>的子群.代數(shù)結(jié)構(gòu)

>群與子群定理5-4.7

設S是群<G,

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

在S上封閉,則<S,

>是<G,

>的子群。子群的其他判定條件此定理顯然是充分必要的.P196例題5設<H,*>,<K,*

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

K,*>也是.作業(yè)5-3(1),（2），(3),（6）5-4(1),（3），(4),（5）代數(shù)結(jié)構(gòu)

>群與子群本節(jié)重點掌握的概念:半群,獨異點,群,子群本節(jié)重點掌握的方法:判定給定的代數(shù)結(jié)構(gòu)是群,子群

(兩種)包括有限(運算表)或無限.集合論小結(jié)要點回顧阿貝爾群:交換律3.群論半群:

封閉.

可結(jié)合.獨異點:

封閉.

可結(jié)合.有幺元.循環(huán)群:G={ai

|i

I}群子群:有限子群

在S上封閉;

一般子群

a,b∈S,有a

b-1∈S,性質(zhì):無零元;ax=b有唯一解;e是唯一等冪元;

消去律;運算表是置換.特殊群拉格朗日定理及推論:子群的階整除群的階.對給定集合S

及運算

判定:

封閉,

可結(jié)合,有幺元,有逆元.第五章代數(shù)結(jié)構(gòu)5-1代數(shù)系統(tǒng)的引入

5-４群與子群5-５阿貝爾群和循環(huán)群5-7陪集和拉格朗日定理5-３半群5-2運算及其性質(zhì)5-8同態(tài)與同構(gòu)代數(shù)結(jié)構(gòu)

>阿貝爾群和循環(huán)群定義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阿貝爾群和循環(huán)群例如<I,+>

是阿貝爾群.定義5-5.2

設<G,

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

i|i∈I},則稱G為循環(huán)群,記作G=(a),元素a稱為循環(huán)群G的生成元。2循環(huán)群定理5-5.3

設G=(a),若|G|=n,則an=e且G={a,a2,…,an}其中n是使an=e的最小正整數(shù)(稱n為元素a的周期).定理5-5.2

循環(huán)群是阿貝爾群。若<G,

>是群,對

a∈G,則(a)是G的子群.代數(shù)結(jié)構(gòu)

>阿貝爾群和循環(huán)群群滿足封閉和結(jié)合律,對

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,+>

是循環(huán)群.第五章代數(shù)結(jié)構(gòu)5-1代數(shù)系統(tǒng)的引入

5-４群與子群5-５阿貝爾群和循環(huán)群5-7陪集和拉格朗日定理5-３半群5-2運算及其性質(zhì)5-8同態(tài)與同構(gòu)代數(shù)結(jié)構(gòu)

>陪集與拉格朗日定理5-7拉格朗日定理群的階與子群的階有何關(guān)系?定理5-7.1

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

>是<G,

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

m|n推論

1)質(zhì)數(shù)階群不能有非平凡子群.2)設<G,

>是n階有限群,則

(a).

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

(b).如果n為質(zhì)數(shù),<G,

>必是循環(huán)群。P210例題1,2代數(shù)結(jié)構(gòu)

>陪集與拉格朗日定理

設k={e,a,b,c},二元運算如表所示,說明<K,*>不是一個循環(huán)群（克萊因四階群）。P210例題1*eabCeeabcaaecbbbceaccbaeP210例題2任何四階群只可能是克萊因四階群或循環(huán)群代數(shù)結(jié)構(gòu)課堂練習1.6階群不可能有4階子群.()2.若群中每個元素以自身為逆,則是交換群.()3.群的等冪元集合構(gòu)成它的子群.()4.偶數(shù)階有限群中,周期為2的元素個數(shù)一定是奇數(shù).()5.設V=<I,+>,I為整數(shù)集合,＋為普通加法.則命題為假的是A.<I,+>是群B.<I,+>是循環(huán)群C.<I,+>交換群D.不是A,B,C6.設G=<{e,a,b},*>為群,其運算表為_,單位元為_,b的逆元為_7.已知G=<P({a,b}),

>為半群,其中

為集合的并運算,判斷

G是否為群?8.設G=(a)是6階循環(huán)群,求G的所有子群.作業(yè)5-7(1),（a），(b),

(3),（5)代數(shù)結(jié)構(gòu)

>群與子群5-5(1),(3),（5)本節(jié)重點掌握的概念:生成元,循環(huán)群,元素的周期,群與子群的數(shù)量關(guān)系本節(jié)重點掌握的方法:判定給定的代數(shù)結(jié)構(gòu)是交換群,循環(huán)群(包括運算表)第五章代數(shù)結(jié)構(gòu)5-1代數(shù)系統(tǒng)的引入

5-４群與子群5-５阿貝爾群和循環(huán)群5-7陪集和拉格朗日定理5-３半群5-2運算及其性質(zhì)5-8同態(tài)與同構(gòu)定義5-8.1

設<A,

>和<B,

>是兩個代數(shù)系統(tǒng),

和

是二元運算,f是A

B的一個映射,使得

a1,a2∈A,有f(a1

a2)=f(a1)

f(a2)稱f為由<A,

>到<B,

>的一個同態(tài)映射.稱代數(shù)系統(tǒng)<A,

>同態(tài)于<B,

>記作A～B。稱代數(shù)系統(tǒng)<f(A),

>為<A,

>的同態(tài)象。代數(shù)結(jié)構(gòu)

>同態(tài)與同構(gòu)a2a1a1

a2f(a1

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

f(a2)同態(tài)方程運算的像等于像的運算.5-8同態(tài)(homomorphism)與同構(gòu)(isomorph)例1

設f:NN

為f(x)=2x則f是<N

,+

>到<N

,

+

>的同態(tài)映射.代數(shù)結(jié)構(gòu)>

同態(tài)與同構(gòu)P214例題1例2

設f:RR定義為

f(x)=5x

則f是<R

,+

>到<R

,

>的單一同態(tài).定義5-8.3

若f是<A,

>到<A,

>的同態(tài),稱f為自同態(tài);若f是<A,

>到<A,

>的同構(gòu),稱f為自同構(gòu).定義5-8.2

設f是由<A,

>到<B,

>的一個同態(tài),若

1)f滿射的,f稱為滿同態(tài)；

2)f是入射的,f稱為單一同態(tài)；

3)f是雙射的,f稱為同構(gòu)映射,并稱

<A,

>和<B,

>是同構(gòu)的,記作A

B。例3

設f:NNk

定義為f(x)=xmod

k,

則f是<N

,+

>到<Nk

,

+k

>的滿同態(tài).例4

設f:RR

為f(x)=2x則f是<R

,+

>到<R

,

+

>的同構(gòu)映射.定理5-8.2

設f是從<A,

>到<B,

>的同態(tài)映射。(a)如果<A,

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

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

>是獨異點,則<f(A),

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

>是群,則<f(A),

>也是群。定理5-8.1

代數(shù)系統(tǒng)間的同構(gòu)關(guān)系是等價關(guān)系.同態(tài)映射保持運算性質(zhì)不變.代數(shù)結(jié)構(gòu)>

同態(tài)與同構(gòu)定義5-8.5

設<A,

>是代數(shù)系統(tǒng),R是A上的一個等價關(guān)系稱R為A上關(guān)于

的同余關(guān)系。若當<a1,a2>,<b1,b2>∈R,有<a1

b1,

a2

b2>∈R同余關(guān)系確定的A等價類稱為同余類.*

正規(guī)子群,商群和同態(tài)基本定理代數(shù)結(jié)構(gòu)>

同態(tài)與同構(gòu)定理5-8.4

設<A,

>是代數(shù)系統(tǒng),R是A上同余關(guān)系,則代數(shù)系統(tǒng)<A/R,

>(商代數(shù))是<A,

>的同態(tài)像.其中定義為

:[a1]

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

[a2]=[a1

a2]

定理

設<H,

>是群<G,

>的正規(guī)子群,則關(guān)于H的左(右)陪集關(guān)系是<G,

>上的同余關(guān)系。定義

設<H,

>是群<G,

>的子群,若

a∈G,有aH=Ha

稱H為G的正規(guī)子群(normalsubgroup)定理由群<G,

>的正規(guī)子群<H,

>確定的商代數(shù)<G/H,

>是群(商群),其中G/H={aH}或{Ha}.代數(shù)結(jié)構(gòu)>

同態(tài)與同構(gòu)定義5-8.4

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

,

>的一個同態(tài),e

是G

的幺元,記ker(f

)={x|x

G且f(x)=e

},稱ker(f)為G的核

(同態(tài)核).定理5-8.3

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

>的同態(tài)映射,則同態(tài)核Kerf

是G的正規(guī)子群。同態(tài)基本定理:設f是由群<G,★>到群<G‘,

>的同態(tài)映射,則商群<G/K

,>與<f(G’),

>同構(gòu)。這里K=Kerf.代數(shù)結(jié)構(gòu)>

同態(tài)與同構(gòu)1.設V1=<R,+>,V2=<R,*>,+,*為普通加法和乘法,令

:R

R,

(x)=ex,下面四個命題為真的是()A.

是V1到V2的滿同態(tài)B.

是V1到V2的單同態(tài)

C.

是V1到V2的同構(gòu)D.

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

:N

N,

(x)=2x,下面四個命題為真的是()A.

是滿同態(tài)B.

是單自同態(tài)

C.

是自同構(gòu)D.

是到自身的映射但不是A,B,C3.設f,g是<S,+>,到<V,*>的同態(tài),*滿足結(jié)合和交換律,則

H(x)=f(x)*g(x)也是<S,+>,到<V,*>的同態(tài).課堂練習作業(yè)

(6),（11）5-8(1),(2),（4),代數(shù)結(jié)構(gòu)>

同態(tài)與同構(gòu)本節(jié)重點掌握的概念:同態(tài),同構(gòu)的定義,同態(tài)方程,群同態(tài)定理.本節(jié)重點掌握的方法:判定給定的代數(shù)系統(tǒng)是同態(tài)或同構(gòu)的.代數(shù)結(jié)構(gòu)小結(jié)代數(shù)結(jié)構(gòu)小結(jié)集合論小結(jié)1.代數(shù)系統(tǒng)<A,*>:非空集A及其上的運算組成的系統(tǒng).2.運算性質(zhì)交換律:

對

x,y∈A,有x

y=y

x,結(jié)合律:

對

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.

重點掌握的基本內(nèi)容(一)運算

是封閉的,即對

x,y∈A,有x

y∈A.集合論小結(jié)重點掌握的基本內(nèi)容(之二)阿貝爾群:交換律3.群論半群:

封閉.

可結(jié)合.獨異點:

封閉.

可結(jié)合.有幺元.循環(huán)群:G={ai

|i

I}群子群:有限子群

在S上封閉;

一般子群

a,b∈S,有a

b-1∈S,性質(zhì):無零元;ax=b有唯一解;e是唯一等冪元;

消去律;運算表是置換.特殊群拉格朗日定理及推論:子群的階整除群的階.對給定集合S

及運算

判定:

封閉,

可結(jié)合,有幺元,有逆元.集合論小結(jié)4.同態(tài)同構(gòu)重點掌握的基本內(nèi)容(之三)同態(tài)f:

a1,a2∈A,有f(a1

a2)=f(a1)

f(a2)滿同態(tài):

b∈B,

a∈A,使得b=f(a)單一同態(tài):若a1

a2則f(a1)

f(a2)同構(gòu):同態(tài)映射是滿射和入射的.性質(zhì):設f是從<A,

>到<B,

>的同態(tài)映射。

(a)如果<A,

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

>也是半群

(b)如果<A,

>是獨異點,則<f(A),

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

>是群,則<f(A),

>也是群。設f是代數(shù)系統(tǒng)<A,

>

<B,

>的一個映射集合論小結(jié)代數(shù)系統(tǒng)半群獨異點群阿貝爾群循環(huán)群同態(tài)同構(gòu)結(jié)合律幺元逆元子群生成元交換律集合論小結(jié)?？贾R點1.運算的性質(zhì)4.交換群與循環(huán)群2.群的判定3.子群的判定6.判定同態(tài)同構(gòu)5.拉格朗日定理的應用P1852),5)P1901),5)P1971),3),5)P1973),4),2111)5)P2211),2),6),11)P2128)P2001),2),3),5)補例:給出克來因四階群的所有子群第四篇圖論1.命題邏輯2.謂詞邏輯3.集合與關(guān)系

4.函數(shù)6.格與布爾代數(shù)5.代數(shù)結(jié)構(gòu)目錄７.圖論第一篇數(shù)理邏輯第二篇集合論第三篇代數(shù)結(jié)構(gòu)緒論格與布爾代數(shù)LatticeandBoole-Algebra第六章格是一種特殊偏序集,它對應于一個具有兩個二元運算的代數(shù)系統(tǒng).在這個系統(tǒng)上強調(diào)元素間的次序關(guān)系,當格滿足一定條件就稱為布爾格,布爾格對應的代數(shù)系統(tǒng)就是布爾代數(shù).本章介紹格的概念,性質(zhì)和特殊格,以及有限布爾代數(shù)的基數(shù),并討論布爾代數(shù)之間的關(guān)系.第六章格與布爾代數(shù)6-1格的概念

6-４布爾代數(shù)6-３有補格6-2分配格格與布爾代數(shù)>格的概念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整數(shù)集合上整除關(guān)系<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例如格與布爾代數(shù)>格的概念e例3

由例2知,<P(S),

>誘導的代數(shù)系統(tǒng)即<P(S),,

>.定義6-1.2

設<A,

>為格,定義A上的兩個二元運算∨和∧為:

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

>所誘導的代數(shù)系統(tǒng)。二元運算∨和∧分別稱為并運算和交運算。{

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

>中,任二元素對應唯一的上確界和下確界.故可將上下確界看作是集合A上的兩個二元運算.格與布爾代數(shù)>格的概念{

}{a}{

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

設<A,

>是格,其誘導的代數(shù)系統(tǒng)為<A,∨,∧>,設B

A且B≠

,如果運算∨和∧關(guān)于B封閉,則稱<B,

>是<A,

>的子格。子格是格,但一子集構(gòu)成格時,不一定是子格.子格通過將格和代數(shù)系統(tǒng)對應起來,使我們可將代數(shù)系統(tǒng)的有關(guān)方法和結(jié)論用于格.例如例題1格與布爾代數(shù)>格的概念aa設<S,

>是格,任取a

S,T={x|x

s,且x

a},證T是子格.對偶原理

設P是對任意格為真的一個命題,命題中僅包含∨,∧及

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

換成

∨、

換成、

換成

,就得到另一個命題P’(P的對偶命題),則P’則對任意格也成立.格的性質(zhì)定理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格與布爾代數(shù)>格的概念定理6-1.3

設<A,

>是格,其誘導的代數(shù)系統(tǒng)為<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(結(jié)合律)(3)a∨a=a,a∧a=a(冪等律)(4)a∨(a∧b)=a,a∧(a∨b)=a(吸收律)引理6-1.1

設<A,∨,∧>是一個代數(shù)系統(tǒng),其中∨,∧都是二元運算且滿足吸收,則∨和∧都滿足冪等性.格誘導的代數(shù)系統(tǒng)的性質(zhì)格與布爾代數(shù)>格的概念該定理說明格與一個代數(shù)系統(tǒng)一一對應.定理6-1.4

設<A,∨,∧>是代數(shù)系統(tǒng),∨和∧滿足交換、結(jié)合和吸收,則A上存在偏序關(guān)系

,使<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格與布爾代數(shù)>格的概念等式成立稱為分配格.等式成立稱為模格.定理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>誘導代數(shù)系統(tǒng)分別為<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>格同態(tài).稱<f(A1),

2>為<A1,

1>的格同態(tài)象。若f雙射,稱f為<A1,∨1,∧1>到<A2,∨2,∧2>的格同構(gòu).亦稱<A1,

1>和<A2,

2>這兩個格是同構(gòu)的。格與布爾代數(shù)>格的概念格同態(tài)利用格與代數(shù)系統(tǒng)的關(guān)系引入格同態(tài)概念.定理6-1.8

設f是格<A1,

1>到<A2,

2>的格同態(tài),則對

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>的格同構(gòu),iff

a,b∈A1,a

1b

f(a)

2f(b)格與布爾代數(shù)>格的概念同態(tài)映射必是保序映射,但反之不然.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不是同態(tài)映射,

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

f(b)

f(d)={d,b,e}保序映射作業(yè)6-1(1),(2),（5)格與布爾代數(shù)>格的概念第六章格與布爾代數(shù)6-1格的概念

6-４布爾代數(shù)6-５布爾表達式6-３有補格6-2分配格格與布爾代數(shù)>分配格定義6-2.1

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

>所誘導的代數(shù)系統(tǒng)如果

a,b,c∈A,滿足

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

a∨(b∧c)=(a∨b)∧(a∨c)(并對交可分配)則稱<A,

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

>誘導的代數(shù)系統(tǒng)為<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)格是分配格的充要條件是:格中不含與此五元格同構(gòu)的子格

bcadabceed如圖所示的格是分配格嗎?分配格的判定abcdfgeabcd例如

g格與布爾代數(shù)>分配格?定理6-2.2

每個鏈是分配格。定理6-2.3

設<A,

>是分配格,對

a,b,c∈A,若

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

如果在一個格中,交運算對并運算可分配,則并運算對交運算也是可分配的。反之亦然由此可方便地判定一格不是分配格.分配格的性質(zhì)bcade例如格與布爾代數(shù)>分配格第六章格與布爾代數(shù)6-1格的概念

6-４布爾代數(shù)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)格與布爾代數(shù)>有補格

x,y有上下確界不能保證

A

有上下確界.如<I,

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

設<A,

>是一個有界格,則對

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

a∧1=a(同一律)

a∨1=1a∧0=0(零一律)格與布爾代數(shù)>有補格例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)顯然,互補律成立.格與布爾代數(shù)>有補格acde01b定義6-3.5

在一個有界格中,如果每元素都至少有一個補元,則稱此格為有補格。例如<P(S),

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

在有界分配格中,若有一個元素有補元則必是唯一的。定義6-3.6

一個格如果它既是有補格,又是分配格,則稱它為有補分配格。有補分配格中任一元素a的唯一補元記為

P251例4格與布爾代數(shù)>有補格a1b0ac1d0abcd01ba,b互補a的補b,c,da,c的補b,d

又例:二元以上的鏈不是有補格.

求補可看作有補分配格上的一元運算.格與布爾代數(shù)>有補格1.有限元素的格都是有界格?()2.元素個數(shù)不超過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.至少含兩個元素的有界格中,不存在以自身為補的元素作業(yè)6-2(2),（5)6-3(1),(3),（4),(6)格與布爾代數(shù)>有補格理解分配格,有界格和有補格的概念,通過哈斯圖判斷給定偏序關(guān)系是否為格,分配格有補格,掌握各種格的結(jié)構(gòu)特征和運算性質(zhì)第六章格與布爾代數(shù)6-1格的概念

6-４布爾代數(shù)6-５布爾表達式6-３有補格6-2分配格6-4布爾代數(shù)定義6-4.1、6-4.2

一個有補分配格<A,

>稱為布爾格。由其誘導的代數(shù)系統(tǒng)<A,∨,∧,

>,稱為布爾代數(shù)。

例1

冪集格<P(S),

>誘導的代數(shù)系統(tǒng)為<P(S),,>.

則<P(S),

>是布爾格,<P(S),,,>是布爾代數(shù).

格與布爾代數(shù)>布爾代數(shù)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),,>中分配律成立,

是分配格;格與布爾代數(shù)>布爾代數(shù)定理6-4.1

對于布爾代數(shù)中的任意兩個元素a,b,必定有

=a

(對合律),(德.摩根律)定義6-4.3

設<A,∨,∧,ˉ>和<B,∨,∧,ˉ>是兩個布爾代數(shù),如果存在著雙射f:A

B,對

a,b∈A,都有

f(a∨b)=f(a)∨f(b),f(a∧b)=f(a)∧f(b),則稱<A,∨,∧,ˉ>和<B,∨,∧,ˉ>同構(gòu)。

由前面的討論已知布爾代數(shù)滿足如下性質(zhì):交換律,結(jié)合律,吸收律,等冪律,分配律,消去律,同一律,0-1律.除此之外布爾代數(shù)還滿足對合律,德.摩根律.布爾代數(shù)性質(zhì)格與布爾代數(shù)>布爾代數(shù)定義6-4.5

設<A,

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

a∈A蓋住0,則稱a為原子。具有有限個元素的布爾代數(shù)稱之.有限布爾代數(shù)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格與布爾代數(shù)>布爾代數(shù)引理6-4.2

設<A,∨,∧,ˉ>是有限布爾代數(shù),b是A中非零元,a1,a2,…,ak是A中滿足aj

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