離散數(shù)學(xué) 代數(shù)系統(tǒng)

離散數(shù)學(xué)代數(shù)系統(tǒng)1第一頁，共四十四頁，編輯于2023年，星期日第三部分代數(shù)結(jié)構(gòu)

代數(shù)結(jié)構(gòu)是以研究數(shù)字、文字和更一般元素的運(yùn)算的規(guī)律和由這些運(yùn)算適合的公理而定義的各種數(shù)學(xué)結(jié)構(gòu)的性質(zhì)為中心問題。它對(duì)現(xiàn)代數(shù)學(xué)如撲拓學(xué)、泛函分析等以及一些其他科學(xué)領(lǐng)域，如計(jì)算機(jī)科學(xué)、編碼理論等，都有重要影響和廣泛地應(yīng)用。2第二頁，共四十四頁，編輯于2023年，星期日第三部分代數(shù)結(jié)構(gòu)主要內(nèi)容:代數(shù)系統(tǒng)----二元運(yùn)算及其性質(zhì)、代數(shù)系統(tǒng)和子代數(shù)半群與群----半群、獨(dú)異點(diǎn)、群環(huán)與域-----環(huán)、整環(huán)、域格與布爾代數(shù)----格、布爾代數(shù)3第三頁，共四十四頁，編輯于2023年，星期日第九章代數(shù)系統(tǒng)主要內(nèi)容:(1)二元運(yùn)算及其性質(zhì)一元和二元運(yùn)算定義及其實(shí)例二元運(yùn)算的性質(zhì)(2)代數(shù)系統(tǒng)代數(shù)系統(tǒng)定義及其實(shí)例子代數(shù)積代數(shù)(3)代數(shù)系統(tǒng)的同態(tài)與同構(gòu)4第四頁，共四十四頁，編輯于2023年，星期日9.1二元運(yùn)算及其性質(zhì)定義9.1

設(shè)S為集合，函數(shù)f：SSS稱為S上的二元運(yùn)算，簡稱為二元運(yùn)算．S中任何兩個(gè)元素都可以進(jìn)行運(yùn)算，且運(yùn)算的結(jié)果惟一．S中任何兩個(gè)元素的運(yùn)算結(jié)果都屬于S，即S對(duì)該運(yùn)算封閉．例1(1)自然數(shù)集合N上的加法和乘法是N上的二元運(yùn)算，但減法和除法不是．(2)整數(shù)集合Z上的加法、減法和乘法都是Z上的二元運(yùn)算，而除法不是．(3)非零實(shí)數(shù)集R*上的乘法和除法都是R*上的二元運(yùn)算，而加法和減法不是．5第五頁，共四十四頁，編輯于2023年，星期日實(shí)例(4)

設(shè)Mn(R)表示所有n階(n≥2)實(shí)矩陣的集合，即則矩陣加法和乘法都是Mn(R)上的二元運(yùn)算.(5)S為任意集合，則∪、∩、－、為P(S)上二元運(yùn)算.(6)SS為S上的所有函數(shù)的集合，則合成運(yùn)算為SS上二元運(yùn)算.

6第六頁，共四十四頁，編輯于2023年，星期日一元運(yùn)算的定義與實(shí)例定義9.2

設(shè)S為集合，函數(shù)f:S→S稱為S上的一元運(yùn)算，簡稱一元運(yùn)算.例2(1)求相反數(shù)是整數(shù)集合Z,有理數(shù)集合Q和實(shí)數(shù)集合R上的一元運(yùn)算.

(2)在冪集P(S)上規(guī)定全集為S，則求絕對(duì)補(bǔ)運(yùn)算~是P(S)上的一元運(yùn)算.

(3)設(shè)S為集合，令A(yù)為S上所有雙射函數(shù)的集合，ASS，求一個(gè)雙射函數(shù)的反函數(shù)為A上的一元運(yùn)算.(4)在n(n≥2)階實(shí)矩陣的集合Mn(R)上，求轉(zhuǎn)置矩陣是Mn(R)上的一元運(yùn)算.7第七頁，共四十四頁，編輯于2023年，星期日二元與一元運(yùn)算的表示1．算符可以用?,?,·,,,等符號(hào)表示二元或一元運(yùn)算，稱為算符.對(duì)二元運(yùn)算?，如果x與y運(yùn)算得到z，記做x?y=z對(duì)一元運(yùn)算,x的運(yùn)算結(jié)果記作x.2．表示二元或一元運(yùn)算的方法:解析公式和運(yùn)算表公式表示例設(shè)R為實(shí)數(shù)集合，如下定義R上的二元運(yùn)算?：x,y∈R,x?y=x.那么3?4=3，0.5?(3)=0.58第八頁，共四十四頁，編輯于2023年，星期日運(yùn)算表：表示有窮集上的一元和二元運(yùn)算

運(yùn)算表

二元運(yùn)算的運(yùn)算表

一元運(yùn)算的運(yùn)算表9第九頁，共四十四頁，編輯于2023年，星期日

例3

設(shè)S=P({a,b})，S上的和

～運(yùn)算的運(yùn)算表如下:

運(yùn)算表的實(shí)例10第十頁，共四十四頁，編輯于2023年，星期日二元運(yùn)算的性質(zhì)定義9.3設(shè)?為S上的二元運(yùn)算,(1)若對(duì)任意x,y∈S有x?y=y?x,則稱運(yùn)算在S上滿足交換律.(2)若對(duì)任意x,y,z∈S有(x?y)?z=x?(y?z),則稱運(yùn)算在S上滿足結(jié)合律.(3)若對(duì)任意x∈S有x?x=x,則稱運(yùn)算在S上滿足冪等律.11第十一頁，共四十四頁，編輯于2023年，星期日二元運(yùn)算的性質(zhì)定義9.4設(shè)?和?為S上兩個(gè)不同的二元運(yùn)算,(1)若對(duì)任意x,y,z∈S有(x?y)?z=(x?z)?(y?z)，z?(x?y)=(z?x)?(z?y),則稱?運(yùn)算對(duì)?運(yùn)算滿足分配律.(2)若和?都可交換,且對(duì)任意x,y∈S有x?(x?y)=x，x?(x?y)=x,則稱?和?運(yùn)算滿足吸收律.

12第十二頁，共四十四頁，編輯于2023年，星期日實(shí)例Z,Q,R分別為整數(shù)、有理數(shù)、實(shí)數(shù)集；Mn(R)為n階實(shí)矩陣集合,n2；P(B)為冪集；AA為從A到A的函數(shù)集，|A|2.集合運(yùn)算交換律結(jié)合律冪等律Z,Q,R普通加法+普通乘法有有有有無無Mn(R)矩陣加法+矩陣乘法有無有有無無P(B)并交相對(duì)補(bǔ)對(duì)稱差有有無有有有無有有有無無AA函數(shù)復(fù)合無有無13第十三頁，共四十四頁，編輯于2023年，星期日集合運(yùn)算分配律吸收律Z,Q,R普通加法+與乘法對(duì)+可分配+對(duì)不分配無Mn(R)矩陣加法+與乘法對(duì)+可分配+對(duì)不分配無P(B)并與交對(duì)可分配對(duì)可分配有交與對(duì)稱差

對(duì)可分配無實(shí)例Z,Q,R分別為整數(shù)、有理數(shù)、實(shí)數(shù)集；Mn(R)為n階實(shí)矩陣集合,n2；P(B)為冪集；AA為從A到A的函數(shù)集，|A|2.14第十四頁，共四十四頁，編輯于2023年，星期日特異元素：單位元定義9.5設(shè)?為S上的二元運(yùn)算,(1)如果存在el(或er)S，使得對(duì)任意x∈S都有el?x=x(或x?er

=x)，則稱el(或er)是S中關(guān)于?運(yùn)算的左(或右)單位元.若e∈S關(guān)于?運(yùn)算既是左單位元又是右單位元，則稱e為S上關(guān)于?運(yùn)算的單位元.單位元也叫做幺元.15第十五頁，共四十四頁，編輯于2023年，星期日特異元素：零元定義9.5設(shè)?為S上的二元運(yùn)算,(2)如果存在

l(或

r)∈S，使得對(duì)任意x∈S都有

l?x=

l

(或x?

r

=r)，則稱

l(或

r)是S中關(guān)于?運(yùn)算的左(或右)零元.若

∈S關(guān)于?運(yùn)算既是左零元又是右零元，則稱為S上關(guān)于運(yùn)算?的零元.16第十六頁，共四十四頁，編輯于2023年，星期日特異元素：可逆元素和逆元(3)設(shè)?為S上的二元運(yùn)算,令e為S中關(guān)于運(yùn)算的單位元.對(duì)于x∈S，如果存在yl(或yr)∈S使得yl?x=e（或x?yr=e）則稱yl(或yr)是x的左逆元（或右逆元）.關(guān)于?運(yùn)算，若y∈S既是x的左逆元又是x的右逆元，則稱y為x的逆元.如果x的逆元存在，就稱x是可逆的.17第十七頁，共四十四頁，編輯于2023年，星期日實(shí)例集合運(yùn)算單位元零元逆元Z,Q,R普通加法+普通乘法01無0x逆元xx逆元x1(x1給定集合)Mn(R)矩陣加法+矩陣乘法n階全0矩陣n階單位矩陣無n階全0矩陣X逆元XX的逆元X1（X可逆）P(B)并交對(duì)稱差BB無的逆元為B的逆元為BX的逆元為X18第十八頁，共四十四頁，編輯于2023年，星期日惟一性定理定理9.1設(shè)?為S上的二元運(yùn)算，el和er分別為S中關(guān)于運(yùn)算的左和右單位元，則el

=er=e為S上關(guān)于?運(yùn)算的惟一的單位元.注意：(1)當(dāng)|S|2，單位元與零元是不同的；(2)當(dāng)|S|=1時(shí)，這個(gè)元素既是單位元也是零元.19第十九頁，共四十四頁，編輯于2023年，星期日定理9.2設(shè)?為S上可結(jié)合的二元運(yùn)算,e為該運(yùn)算的單位元,對(duì)于x∈S如果存在左逆元yl

和右逆元yr,則有yl=yr=y,且y是x的惟一的逆元.說明：對(duì)于可結(jié)合的二元運(yùn)算，可逆元素x只有惟一的逆元，記作x1.惟一性定理20第二十頁，共四十四頁，編輯于2023年，星期日9.2代數(shù)系統(tǒng)定義9.6

非空集合S和S上k個(gè)一元或二元運(yùn)算f1,f2,…,fk組成的系統(tǒng)稱為代數(shù)系統(tǒng),簡稱代數(shù)，記做<S,f1,f2,…,fk>.實(shí)例：(1)<N,＋>,<Z,＋,·>,<R,＋,·>是代數(shù)系統(tǒng)，+和·分別表示普通加法和乘法.(2)<Mn(R),＋,·>是代數(shù)系統(tǒng)，＋和·分別表示n階(n≥2)實(shí)矩陣的加法和乘法.(3)<Zn,,>是代數(shù)系統(tǒng)，Zn＝{0,1,…,n-1}，和分別表示模n的加法和乘法，對(duì)于x,y∈Zn，xy=(x＋y)modn，xy=(xy)modn(4)<P(S),,,~>是代數(shù)系統(tǒng)，和為并和交，~為絕對(duì)補(bǔ).21第二十一頁，共四十四頁，編輯于2023年，星期日代數(shù)系統(tǒng)的成分與表示構(gòu)成代數(shù)系統(tǒng)的成分：集合（也叫載體，規(guī)定了參與運(yùn)算的元素）運(yùn)算（這里只討論有限個(gè)二元和一元運(yùn)算）代數(shù)常數(shù)（通常是與運(yùn)算相關(guān)的特異元素：如單位元等）研究代數(shù)系統(tǒng)時(shí)，如果把運(yùn)算具有它的特異元素也作為系統(tǒng)的性質(zhì)之一，那么這些特異元素可以作為系統(tǒng)的成分，叫做代數(shù)常數(shù).例如：代數(shù)系統(tǒng)<Z,+,0>：集合Z,運(yùn)算+,代數(shù)常數(shù)0代數(shù)系統(tǒng)<P(S),∪,∩>：集合P(S),運(yùn)算∪和∩，無代數(shù)常數(shù).22第二十二頁，共四十四頁，編輯于2023年，星期日代數(shù)系統(tǒng)的表示(1)列出所有的成分：集合、運(yùn)算、代數(shù)常數(shù)（如果存在）如<Z,+,0>,<P(S),∪,∩>(2)列出集合和運(yùn)算，在規(guī)定系統(tǒng)性質(zhì)時(shí)不涉及具有單位元的性質(zhì)（無代數(shù)常數(shù)）如<Z,+>,<P(S),∪,∩>(3)用集合名稱簡單標(biāo)記代數(shù)系統(tǒng)在前面已經(jīng)對(duì)代數(shù)系統(tǒng)作了說明的前提下使用如代數(shù)系統(tǒng)Z,P(B)23第二十三頁，共四十四頁，編輯于2023年，星期日同類型與同種代數(shù)系統(tǒng)定義9.7(1)如果兩個(gè)代數(shù)系統(tǒng)中運(yùn)算的個(gè)數(shù)相同，對(duì)應(yīng)運(yùn)算的元數(shù)相同，且代數(shù)常數(shù)的個(gè)數(shù)也相同，則稱它們是同類型的代數(shù)系統(tǒng).(2)如果兩個(gè)同類型的代數(shù)系統(tǒng)規(guī)定的運(yùn)算性質(zhì)也相同，則稱為同種的代數(shù)系統(tǒng).24第二十四頁，共四十四頁，編輯于2023年，星期日同類型與同種代數(shù)系統(tǒng)例如V1=<R,+,·,0,1>,V2=<Mn(R),+,·,,E>,為n階全0矩陣，E為n階單位矩陣

V3=<P(B),∪,∩,,B>.V1,V2,V3是同類型的代數(shù)系統(tǒng)，它們都含有2個(gè)二元運(yùn)算,2個(gè)代數(shù)常數(shù).V1,V2是同種的代數(shù)系統(tǒng)，V1,V2與V3不是同種的代數(shù)系統(tǒng).25第二十五頁，共四十四頁，編輯于2023年，星期日V1V2V3+可交換、可結(jié)合·可交換、可結(jié)合+滿足消去律·滿足消去律·對(duì)+可分配+對(duì)·不可分配+與·沒有吸收律+可交換、可結(jié)合·可交換、可結(jié)合+滿足消去律·不滿足消去律·對(duì)+可分配+對(duì)·不可分配+與·沒有吸收律∪可交換、可結(jié)合∩可交換、可結(jié)合∪不滿足消去律∩不滿足消去律∩對(duì)∪可分配∪對(duì)∩可分配∪與∩滿足吸收律運(yùn)算性質(zhì)比較26第二十六頁，共四十四頁，編輯于2023年，星期日子代數(shù)系統(tǒng)定義9.8設(shè)V=<S,f1,f2,…,fk>是代數(shù)系統(tǒng)，B是S的非空子集，如果B對(duì)f1,f2,…,fk

都是封閉的，且B和S含有相同的代數(shù)常數(shù)，則稱<B,f1,f2,…,fk>是V的子代數(shù)系統(tǒng)，簡稱子代數(shù).有時(shí)將子代數(shù)系統(tǒng)簡記為B.27第二十七頁，共四十四頁，編輯于2023年，星期日子代數(shù)系統(tǒng)實(shí)例:N是<Z,＋>的子代數(shù)，N也是<Z,＋,0>的子代數(shù);N{0}是<Z,＋>的子代數(shù)，但不是<Z,＋,0>的子代數(shù).說明：(1)子代數(shù)和原代數(shù)是同種的代數(shù)系統(tǒng).(2)對(duì)于任何代數(shù)系統(tǒng)V=<S,f1,f2,…,fk>，其子代數(shù)一定存在.

28第二十八頁，共四十四頁，編輯于2023年，星期日關(guān)于子代數(shù)的術(shù)語(1)最大的子代數(shù)：就是V本身(2)最小的子代數(shù)：如果令V中所有代數(shù)常數(shù)構(gòu)成的集合是B，且B對(duì)V中所有的運(yùn)算都是封閉的，則B就構(gòu)成了V的最小的子代數(shù)(3)最大和最小的子代數(shù)稱為V的平凡的子代數(shù)(4)若B是S的真子集，則B構(gòu)成的子代數(shù)稱為V的真子代數(shù).例設(shè)V=<Z,+,0>,令nZ={nz|zZ},n為自然數(shù)，則nZ是V的子代數(shù)當(dāng)n=1和0時(shí)，nZ是V的平凡的子代數(shù)，其他的都是V的非平凡的真子代數(shù).29第二十九頁，共四十四頁，編輯于2023年，星期日積代數(shù)定義9.9設(shè)V1=<A,?>和V2=<B,>是同類型的代數(shù)系統(tǒng)，?和為二元運(yùn)算，在集合AB上如下定義二元運(yùn)算?，<a1,b1>,<a2,b2>AB，有<a1,b1>?<a2,b2>=<a1?a2,b1b2>稱V=<AB,?>為V1與V2的積代數(shù)，記作V1V2.這時(shí)也稱V1和V2為V的因子代數(shù).實(shí)例Z2={0,1}，V=<Z2,>，V1V2=<Z2Z2,?>Z2Z2={<0,0>,<1,0>,<0,1>,<1,1>}<0,1>?<1,0>=<0,0>

注意：積代數(shù)的定義可以推廣到具有多個(gè)運(yùn)算的同類型的代數(shù)系統(tǒng).

30第三十頁，共四十四頁，編輯于2023年，星期日積代數(shù)的性質(zhì)定理9.3設(shè)V1=<A,?>和V2=<B,>是同類型的代數(shù)系統(tǒng)，V1V2=<AB,?>是它們的積代數(shù).(1)如果?和運(yùn)算是可交換（可結(jié)合、冪等）的，那么?運(yùn)算也是可交換（可結(jié)合、冪等）的.(2)如果e1和e2（1和2）分別為?和運(yùn)算的單位元（零元），那么<e1,e2>（<1,2>）也是?運(yùn)算的單位元（零元）.(3)如果x和y分別為?和運(yùn)算的可逆元素，那么<x,y>也是?運(yùn)算的可逆元素，其逆元就是<x1,y1>.31第三十一頁，共四十四頁，編輯于2023年，星期日9.3代數(shù)系統(tǒng)的同態(tài)與同構(gòu)定義9.10

設(shè)V1=<A,°>和V2=<B,>是同類型的代數(shù)系統(tǒng)，f:AB，且x,yA有f(x°y)=f(x)f(y),則稱f是V1到V2的同態(tài)映射，簡稱同態(tài).

同態(tài)分類：(1)f如果是單射，則稱為單同態(tài)(2)如果是滿射，則稱為滿同態(tài)，這時(shí)稱V2是V1的同態(tài)像，記作V1V2(3)如果是雙射，則稱為同構(gòu)，也稱代數(shù)系統(tǒng)V1同構(gòu)于V2，記作V1V2(4)如果V1=V2，則稱作自同態(tài)32第三十二頁，共四十四頁，編輯于2023年，星期日實(shí)例(1)設(shè)V1=<Z,+>,V2=<Zn,>．其中Z為整數(shù)集，+為普通加法；Zn={0,1,…,n1}，為模n加.令

f:Z→Zn，f(x)=(x)modn

那么f是V1到V2的滿同態(tài)．(2)設(shè)V1=<R,+>,V2=<R*,·>，其中R和R*分別為實(shí)數(shù)集與非零實(shí)數(shù)集，+和·分別表示普通加法與乘法．令f:R→R*，f(x)=ex則f是V1到V2的單同態(tài).33第三十三頁，共四十四頁，編輯于2023年，星期日實(shí)例(3)設(shè)V=<Z,+>，其中Z為整數(shù)集，+為普通加法.aZ，令fa:ZZ，fa(x)=ax，那么fa是V的自同態(tài).當(dāng)a=0時(shí)稱f0為零同態(tài)；當(dāng)a=1時(shí)，稱fa為自同構(gòu)；除此之外其他的fa都是單自同態(tài).34第三十四頁，共四十四頁，編輯于2023年，星期日練習(xí)11．設(shè)°運(yùn)算為Q上的二元運(yùn)算，x,yQ,x°y=x+y+2xy,(1)判斷°運(yùn)算是否滿足交換律和結(jié)合律，并說明理由.(2)求出°運(yùn)算的單位元、零元和所有可逆元素的逆元.35第三十五頁，共四十四頁，編輯于2023年，星期日(1)°

運(yùn)算可交換，可結(jié)合.任取x,yQ,

x°y=x+y+2xy=y+x+2yx=y°

x,任取x,y,zQ,(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解答36第三十六頁，共四十四頁，編輯于2023年，星期日(2)設(shè)°運(yùn)算的單位元和零元分別為e和，則對(duì)于任意x有x°e=x成立，即

x+e+2xe=x

e=0由于°運(yùn)算可交換，所以0是幺元.對(duì)于任意x有x°

=成立，即

x++2x=

x+2x

=0

=1/2給定x，設(shè)x的逆元為y,則有x°y=0成立，即

x+y+2xy=0(x≠1/2)因此當(dāng)x

1/2時(shí)，是x的逆元.解答37第三十七頁，共四十四頁，編輯于2023年，星期日2．下面是三個(gè)運(yùn)算表(1)說明那些運(yùn)算是可交換的、可結(jié)合的、冪等的.(2)求出每個(gè)運(yùn)算的單位元、零元、所有可逆元素的逆元。練習(xí)238第三十八頁，共四十四頁，編輯于2023年，星期日解解答(1)*滿足交換律，滿足結(jié)合律，不滿足冪等律.

°不滿足交換律，滿足結(jié)合律，滿足冪等律.

·滿足交換律，滿足結(jié)合律，不滿足冪等律.(2)*的單位元為b，沒有零元，a1=c,b1=b,c1=a

°的單位元和零元都不存在，沒有可逆元素.

·的單位元為a，零元為c，a1=a，b,c不是可逆元素.39