離散數(shù)學(xué) 第五章 代數(shù)結(jié)構(gòu)

離散數(shù)學(xué)課件第五章代數(shù)結(jié)構(gòu)第1頁，課件共52頁，創(chuàng)作于2023年2月由于數(shù)學(xué)和其他科學(xué)的發(fā)展，人們需要對若干不是數(shù)的事物，用類似普通計(jì)算的方法進(jìn)行相似的計(jì)算。如矩陣、向量等。研究代數(shù)系統(tǒng)的學(xué)科稱為“近世代數(shù)”或“抽象代數(shù)”。第2頁，課件共52頁，創(chuàng)作于2023年2月本章主要內(nèi)容集合的概念1集合的表示方法2同態(tài)與同構(gòu)6阿貝爾群與循環(huán)群4陪集與拉格朗日定理5集合的概念1集合的表示方法2群與子群3代數(shù)系統(tǒng)與性質(zhì)1半群2第3頁，課件共52頁，創(chuàng)作于2023年2月5-1代數(shù)系統(tǒng)的引入定義5-1.1

如果

為An到B的一個(gè)函數(shù)，則稱

為集合A上的n元運(yùn)算（operater）。如果B

A，則稱該n元運(yùn)算在A上封閉。第4頁，課件共52頁，創(chuàng)作于2023年2月代數(shù)系統(tǒng)的定義定義5-1.2

一個(gè)非空集合A連同若干個(gè)定義在該集合上的運(yùn)算f1,f2,…,fk

所組成的系統(tǒng)稱為一個(gè)代數(shù)系統(tǒng)（代數(shù)結(jié)構(gòu)），記為<A,f1,f2,…,fk>。代數(shù)結(jié)構(gòu)由以下三個(gè)部分組成：非空集合S，稱為代數(shù)結(jié)構(gòu)的載體。載體S上的若干運(yùn)算。一組刻劃載體上各運(yùn)算所滿足性質(zhì)的公理。代數(shù)系統(tǒng)常用一個(gè)多元序組<S，

，

，…>來表示。第5頁，課件共52頁，創(chuàng)作于2023年2月代數(shù)系統(tǒng)舉例(1)R上的“+”、“×”運(yùn)算，構(gòu)成一個(gè)代數(shù)系統(tǒng)〈R，+，×〉；(2)ρ(S)上的“∩”、“∪”、“―”運(yùn)算，構(gòu)成代數(shù)系統(tǒng)〈ρ(S),∩,∪,―〉，稱集合代數(shù)；(3)

含有n個(gè)命題變元的命題集合A與A上的“∧”、“∨”、“┐”運(yùn)算，構(gòu)成代數(shù)系統(tǒng)〈A，∧，∨，┐〉，稱之為命題代數(shù)。第6頁，課件共52頁，創(chuàng)作于2023年2月5-2二元運(yùn)算的性質(zhì)定義可以用o、*、·、⊕、等符號(hào)表示二元或一元運(yùn)算,稱為算符。定義5-2.1設(shè)*是定義在集合A上的二元運(yùn)算，如果對于任意的x，y∈A，都有x*y∈A，則稱二元運(yùn)算*在A上是封閉的。第7頁，課件共52頁，創(chuàng)作于2023年2月二元運(yùn)算的主要算律定義設(shè)o為S上的二元運(yùn)算,

(1)如果對于任意的x,y∈S,有xoy=yox,則稱運(yùn)算o在S上滿足交換律。

(2)如果對于任意的x,y,z∈S有(xoy)oz=xo(yoz),則稱運(yùn)算o在S上滿足結(jié)合律。

(3)如果對于任意的x∈S有xox=x,則稱o運(yùn)算在S上滿足冪等律（等冪律）。第8頁，課件共52頁，創(chuàng)作于2023年2月二元運(yùn)算的主要算律（續(xù)）定義設(shè)o和*為S上兩個(gè)不同的二元運(yùn)算,

(1)如果對于任意的x,y,z∈S有(x*y)oz=(xoz)*(yoz)和zo(x*y)=(zox)*(zoy),則稱o運(yùn)算對*運(yùn)算滿足分配律。

(2)如果o和*都可交換,并且對于任意的x,y∈S有xo(x*y)=x和x*(xoy)=x,則稱o和*運(yùn)算滿足吸收律。第9頁，課件共52頁，創(chuàng)作于2023年2月特殊元素1：幺元（單位元）定義5-2.7

設(shè)<A,

>是二元代數(shù)系統(tǒng)，（1）若存在el∈A，使得對任意a∈A，都有

el

a=a，則稱el是A中關(guān)于運(yùn)算“

”的一個(gè)左幺元（左單位元）（2）若存在er∈A，使得對任意a∈A，都有

a

er=a，稱er是A中關(guān)于運(yùn)算“

”的一個(gè)右幺元（右單位元）（3）若存在e∈A，對任意a∈A，都有

a

e=e

a=a，則稱e是A中關(guān)于運(yùn)算“

”的一個(gè)幺元（單位元）第10頁，課件共52頁，創(chuàng)作于2023年2月幺元的性質(zhì)定理5-2.1設(shè)*是定義在集合A上的一個(gè)二元運(yùn)算，且在A中有關(guān)于

運(yùn)算的左幺元el和右幺元er，則el=er=e，且A中的幺元是唯一的。證明：（先證左幺元el=右幺元er=e）el=el

er=er=e

（再證幺元e是唯一的）設(shè)還有一個(gè)幺元e’

A,則

e’=e’

e=e第11頁，課件共52頁，創(chuàng)作于2023年2月特殊元素2：零元定義5-2.8

設(shè)<A,

>是一個(gè)二元代數(shù)系統(tǒng)，（1）若存在

l∈A，使得對任意a∈A，都有

l

a=

l，則稱

l是A中關(guān)于運(yùn)算“

”的一個(gè)左零元；（2）若存在

r∈A，使得對任意a∈A，都有a

r=

r，則稱

r是A中關(guān)于運(yùn)算“

”的一個(gè)右零元。（3）若存在

∈A，使得對任意a∈A，都有a

=

a=

，則稱θ是A中關(guān)于運(yùn)算“

”的一個(gè)零元；第12頁，課件共52頁，創(chuàng)作于2023年2月零元的性質(zhì)定理5-2.2設(shè)*是定義在集合A上的一個(gè)二元運(yùn)算，且在A中有關(guān)于

運(yùn)算的左零元

l和右零元

r，則

l=

r=

，且A中的零元是唯一的。證明：（先證左零元

l=右零元

r=

）

l=

l

r=

r=

（再證零元

是唯一的）設(shè)還有一個(gè)零元

’

A,則

’=

’

=

第13頁，課件共52頁，創(chuàng)作于2023年2月幺元、零元舉例例：代數(shù)A=〈{a，b，c}，?！涤孟卤矶x：。abcaabbbabccaba則b是左么元，無右么元；

a是右零元，b是右零元；無左零元;運(yùn)算：既不滿足結(jié)合律，也不滿足交換律。第14頁，課件共52頁，創(chuàng)作于2023年2月幺元、零元舉例（續(xù)）例:求出下列集合的幺元，零元。（1）〈I，×〉，I為整數(shù)集則幺元為1，零元為0（2）〈

（A）,∪,∩〉對運(yùn)算∪，

是幺元，A是零元，對運(yùn)算∩，A是幺元，

是零元。（3）〈N，+〉有幺元0，無零元。第15頁，課件共52頁，創(chuàng)作于2023年2月幺元、零元性質(zhì)定理5-2.3

如果代數(shù)結(jié)構(gòu)<A，

>有關(guān)于

運(yùn)算的零元

和幺元e

，且集合A中元素個(gè)數(shù)大于1，則

≠e

。

證明：用反證法：

設(shè)幺元e

=零元

，則對于任意x

A

，必有

x

=e

x=

x

=

=

e

于是，推出A中所有元素都是相同的，矛盾。

第16頁，課件共52頁，創(chuàng)作于2023年2月特殊元素3：逆元定義5-2.9

設(shè)<A,

>是二元代數(shù)系統(tǒng)，e是幺元，a∈A，若存在一個(gè)元素b∈A，（1）使得：b

a=e，則稱b是a的一個(gè)左逆元，記為al

1；（2）使得：a

b=e，則稱b是a的一個(gè)右逆元，記為ar

1。（3）使得：a

b=b

a=e，則稱a可逆，并稱b是a的一個(gè)逆元，記為a

1；第17頁，課件共52頁，創(chuàng)作于2023年2月逆元的性質(zhì)注：一般地，一個(gè)元素的左逆元不一定等于它的右逆元。一個(gè)元素左、右逆元不一定同時(shí)存在。甚至一個(gè)元素的左（右）逆元不一定是唯一的。定理

設(shè)*為S上可結(jié)合的二元運(yùn)算,e為該運(yùn)算的單位元,對于x∈S如果存在左逆元yl和右逆元yr,則有yl

=yr=y，且y是x的唯一的逆元。第18頁，課件共52頁，創(chuàng)作于2023年2月證明：因?yàn)閥l*x=e，x*yr=e，故

yl=yl*e=yl*(x*yr)=(yl*x)*yr=e*yr=yr令yl=yr=y,則y是x的逆元。設(shè)y＇∈S也是x的逆元,則

y'=y'*e=y'*(x*y)=(y'*x)*y=e*y=y所以y是x唯一的逆元。第19頁，課件共52頁，創(chuàng)作于2023年2月通過運(yùn)算表觀察二元運(yùn)算的性質(zhì)1）封閉性：表中的每個(gè)元素都屬于A。2）可交換性：運(yùn)算表關(guān)于主對角線是對稱的。3）等冪性：運(yùn)算表的主對角線上的每一元素與它所在行（列）的表頭元素相同。4）A中關(guān)于運(yùn)算

具有零元：該元素所對應(yīng)的行和列中的元素都與該元素相同。5）A中關(guān)于運(yùn)算

具有幺元：該元素所對應(yīng)的行和列依次與運(yùn)算表的首行和首列相一致。6）A中關(guān)于運(yùn)算

具有幺元，a和b互逆：位于a行b列的元素以及b行a列的元素都是幺元。第20頁，課件共52頁，創(chuàng)作于2023年2月例：P182例題9，10，11，12第21頁，課件共52頁，創(chuàng)作于2023年2月例：設(shè)X={e,a,b,c,d}，*是X上的二元運(yùn)算，*的運(yùn)算表如下。

從本例還可以看到a的逆元也是c,d。運(yùn)算*滿足可交換性，但不滿足等冪性。*eabcdeeabcdaaaaeebbaaeecceeccddeecc從表中可知，<X，*>是代數(shù)系統(tǒng)，e是關(guān)于*的幺元。X中無零元。表中b*c=c*b=e；b*d=d*b=e，故c和d均為b的逆元，即b的逆元不唯一。原因在于運(yùn)算*不滿足結(jié)合律。第22頁，課件共52頁，創(chuàng)作于2023年2月練習(xí)：指出下面運(yùn)算的性質(zhì)，并求出幺元,零元，可逆元素的逆元。1、在Q集合上，

x,yQ，x*y=x+y-xy2、在I+集合上,x,yI+，x*y=lcm(x,y)1、滿足交換律、結(jié)合律，不滿足冪等律，幺元為0，零元為1，x的逆元x-1=x/(x-1)(x≠1)2、滿足交換律、結(jié)合律、冪等律，幺元為1，無零元，只有1有逆元，其逆元為1。第23頁，課件共52頁，創(chuàng)作于2023年2月5-3半群定義5-3.1

如果集合S上的二元運(yùn)算

是封閉的，則稱代數(shù)系統(tǒng)<S，

>為廣群。定義5-3.2

如果集合S上的二元運(yùn)算

是封閉的并且滿足結(jié)合律，則稱代數(shù)結(jié)構(gòu)<S，

>為半群。例：P186例題1，例題2第24頁，課件共52頁，創(chuàng)作于2023年2月子半群定理5-3.1設(shè)<S,

>為一半群,B

S且在B上封閉，那么<B,>也是一個(gè)半群，稱為<S,

>的子半群。例：乘法運(yùn)算在某些集合上構(gòu)成<R,×>的子半群。第25頁，課件共52頁，創(chuàng)作于2023年2月含幺半群（獨(dú)異點(diǎn)）定義5-3.3

設(shè)代數(shù)結(jié)構(gòu)<S,

>為半群，若<S,

>含有關(guān)于

運(yùn)算的幺元,則稱它為獨(dú)異點(diǎn)，或含幺半群，有時(shí)也記為<S,

,e>。第26頁，課件共52頁，創(chuàng)作于2023年2月獨(dú)異點(diǎn)的性質(zhì)——運(yùn)算表中任兩行兩列不相同定理5-3.3

設(shè)<S,

,e>是一個(gè)獨(dú)異點(diǎn),則在關(guān)于運(yùn)算

的運(yùn)算表中任何兩行或兩列都是不相同的。例:設(shè)I是整數(shù)集合，m是任意正整數(shù)，Zm是由模m的同余類組成的同余類集，在Zm上定義兩個(gè)二元運(yùn)算+m和×m分別如下：對于任意的[i]，[j]

Zm，有

[i]+m[j]=[(i+j)(modm)][i]×m[j]=[(i×j)(modm)]

試證明在這兩個(gè)二元運(yùn)算的運(yùn)算表中任何兩行或兩列都是不相同的。第27頁，課件共52頁，創(chuàng)作于2023年2月證明思路：1、證明運(yùn)算的封閉性；

Zm＝｛[0],[1],[2],…,[m－1]｝,

任意[x],[y]∈Zm,

顯然[x]+m[y]∈Zm,[x]×m[y]∈Zm,

所以+m、×m運(yùn)算封閉性成立。2、證明運(yùn)算滿足結(jié)合律；任意[x],[y],[z]∈Zm,有([x]＋m[y])＋m[z]

＝([x]＋[y]+[z])(modm)＝[x]＋m([y]＋m[z])所以+m滿足結(jié)合律，同理可證×m滿足結(jié)合律。3、顯然，[0]、[1]分別為+m和×m的幺元。第28頁，課件共52頁，創(chuàng)作于2023年2月綜上所述，<Zm,+m>和<Zm,×m>都是獨(dú)異點(diǎn)。由定理5-3.3可知，這兩個(gè)運(yùn)算的運(yùn)算表中任兩行或兩列都不相等。第29頁，課件共52頁，創(chuàng)作于2023年2月獨(dú)異點(diǎn)的性質(zhì)定理5-3.4

設(shè)<S,

,e>是一個(gè)獨(dú)異點(diǎn),如果對于任意a,b

S，且a,b均有逆元，則a)(a-1)-1=ab)ab有逆元，且(ab)-1=b-1

a-1。證明:a)因a-1和a為互為逆元，直接得到結(jié)論。b)必須證明兩種情況：(ab)(b-1

a-1)

=e

和(b-1

a-1)

(ab)=e利用結(jié)合律容易得出。第30頁，課件共52頁，創(chuàng)作于2023年2月子獨(dú)異點(diǎn)定義5-3.3

設(shè)代數(shù)結(jié)構(gòu)<S,

>為半群，若B

S且在B上封閉，B含有<S,

>關(guān)于

運(yùn)算的幺元,那么<B,>稱為子獨(dú)異點(diǎn)，或子幺半群。第31頁，課件共52頁，創(chuàng)作于2023年2月獨(dú)異點(diǎn)舉例設(shè)Σ是一個(gè)非空有限集合，稱為字母表，由Σ中有限個(gè)字母組成的有序集合（即字符串）稱為Σ上的一個(gè)字，串中的字母個(gè)數(shù)m稱為字長，m=0時(shí)，稱為空字，即為單位元，記為e。Σ?表示Σ上的字的集合，Σ?上的連接運(yùn)算·定義為α，β∈Σ?，α·β=αβ，則<Σ?，·>是一個(gè)代數(shù)系統(tǒng)，而且是一個(gè)獨(dú)異點(diǎn),是在計(jì)算機(jī)科學(xué)中自動(dòng)機(jī)理論及形式語言中最基本的結(jié)構(gòu)。Σ?的任一子集就稱為語言。第32頁，課件共52頁，創(chuàng)作于2023年2月5-4群與子群定義5-4.1

稱代數(shù)結(jié)構(gòu)<G,

>為群(groups),如果（1）<G，

>中運(yùn)算

是封閉的；（2）<G，

>中運(yùn)算

是可結(jié)合的；（3）<G，

>中有幺元e；（4）<G，

>中每一元素x都有逆元x-1。第33頁，課件共52頁，創(chuàng)作于2023年2月群舉例例題1R={0°,60°,120°,180°,240°,300°},*是R上的二元運(yùn)算，a*b表示先旋轉(zhuǎn)a再旋轉(zhuǎn)b的角度，并規(guī)定旋轉(zhuǎn)360°等于原來的狀態(tài)。運(yùn)算表如表5-4.1所示。驗(yàn)證代數(shù)結(jié)構(gòu)<R,*>為群。解題思路：需證明<R,*>：（1）運(yùn)算*封閉；（2）運(yùn)算*是可結(jié)合的；（3）有幺元0°;（4）每一元素x都有逆元x-1。第34頁，課件共52頁，創(chuàng)作于2023年2月典型的群1、<Z,+>

2、<R+,×>

3、<Z6，+6>,其中Z6={0，1，2，3，4，5}，單位元是0；1、5互為逆元，2、4互為逆元，3的逆元為3，0的逆元為0。注：<Z+,+>不是群，其不存在幺元，且每個(gè)元素也不存在逆元。而<N,+>存在幺元，除0以外，均不存在逆元，故其只是半群。第35頁，課件共52頁，創(chuàng)作于2023年2月代數(shù)結(jié)構(gòu)總圖封閉<G,

>廣群半群獨(dú)異點(diǎn)群結(jié)合含幺可逆

<G,

>廣群半群獨(dú)異點(diǎn)群第36頁，課件共52頁，創(chuàng)作于2023年2月有限群與無限群定義5-4.2

設(shè)<G,

>為一群。若G為無限集，則稱<G,

>為無限群；否則，稱<G,

>為有限群，此時(shí)G的元素個(gè)數(shù)稱為G的階,記為|G|。第37頁，課件共52頁，創(chuàng)作于2023年2月有限群舉例第38頁，課件共52頁，創(chuàng)作于2023年2月Klein四元群*eabceeabcaaecbbbceaccbaeKlein四元群:e為G中的單位元；運(yùn)算是可交換的；

G中任何元素的逆元就是它自己；在a,b,c三個(gè)元素中,任何兩個(gè)元素運(yùn)算的結(jié)果都等于另一個(gè)元素。第39頁，課件共52頁，創(chuàng)作于2023年2月群的性質(zhì)1——階數(shù)大于1的群中無零元定理5-4.1

設(shè)<G，

>為群，那么當(dāng)G

{e}時(shí),G無零元。證明:

設(shè)|G|>1

且群有零元。那么群中任何元素x

G，都有

x

=

x=

≠

e，所以，零元

就不存在逆元，與<G，

>是群的假設(shè)矛盾。第40頁，課件共52頁，創(chuàng)作于2023年2月群的性質(zhì)2——群方程存在唯一解定理5-4.2

設(shè)<G，

>為群，對于a,bG，必存在xG，使得關(guān)于x的方程a

x＝b有唯一解。證明:1）先證解存在性；

設(shè)a的逆元a-1，令x=a-1

b（構(gòu)造一個(gè)解）

a

x＝a(a-1

b)＝（a

a-1）

b

＝e

b＝b

2）再證解唯一性;

若另有解x1滿足a

x1

＝b，則

x1

＝（

a-1

a

）*x1

＝a-1

（a

*x1）＝a-1

b＝x第41頁，課件共52頁，創(chuàng)作于2023年2月群的性質(zhì)3——群滿足消去律定理5-4.3

設(shè)<G，

>為群，那么，對任意a,x,y

G

如果a

x=a

y，則x=y；（左乘a-1可證）如果x

a=y

a，則x=y

。（右乘a-1可證）

第42頁，課件共52頁，創(chuàng)作于2023年2月群的性質(zhì)4——幺元是群中唯一等冪元定義5-4.4設(shè)<G，

>為群，如果存在a

G，有a

a=a，則稱a為等冪元。定理5-4.5

在群<G，

>中，除幺元e之外，不可能有任何別的等冪元。證明:因?yàn)閑

e=e，所以e是等冪元?，F(xiàn)設(shè)a

G，a≠e且a

a=a則有a=e

a=(a-1

a)

a=a-1(a

a)=a-1

a=e

與假設(shè)a≠e矛盾。第43頁，課件共52頁，創(chuàng)作于2023年2月子群及子群的性質(zhì)定義5-4.5設(shè)<G，

>為群。如果S

G，且<S，

>為一群，則稱<S，

>為<G，

>的子群；若S真包含于G，則為真子群。定理5-4.6

設(shè)<G,

>為群，<S,

>為G的子群，那么，<G,

>中的幺元e必定也是<S,

>中的幺元。證明:設(shè)<G,

>中的幺元為e1，對于任意一個(gè)元素xSG,必有e1

x=e

x，因?yàn)槿簼M足消去律，所以e1=e。第44頁，課件共52頁，創(chuàng)作于2023年2月子群舉例<Z6,+6>是群，H1={0,2,4},H2={0,1,5},H3={0,3},問：<H1,+6>,<H2,+6>,<H3,+6>是<Z6,+6>的子群嗎？解：<H1,+6>是<Z6,+6>的子群；

<H2,+6>不是<Z6,+6>的子群；（因?yàn)檫\(yùn)算不封閉）

<H3,+6>是<Z6,+6>的子群。第45頁，課件共52頁，創(chuàng)作于2023年2月平凡子群定義5-4.6對任何群G都存在子群。G和{e}都是G的子群,稱為G的平凡子群。第46頁，課件共52頁，創(chuàng)作于2023年2月子群的判定定理定理5-4.7

設(shè)<G,

>為群，B為G的非空子集，如果B是一個(gè)有限集,那么,只要運(yùn)算

在B上封閉（即任意a,bB有a*bB),<B,

>必定是<G,

>的子群。定理5-4.8

設(shè)<G,△>為群,S為G的非空子集,如果對于任意元素a,bS有a△b-1S,那么,<S,△>必定是<G,△>的子群。第47頁，課件共52頁，創(chuàng)作于2023年2月典型子群：生成子群定義設(shè)G為群,a∈G,令H={ak|k∈Z}，即a的所有的冪構(gòu)成的集合,則H是G的子群,稱為由a生成的子群,記作<a>。

例1：整數(shù)加群,由2生成的子群是：

<2>={2k|k∈Z}

例2：群<Z6,+6>中,由2生成的子群是：20