離散數(shù)學第四章

離散數(shù)學第四章1第1頁，共29頁，2023年，2月20日，星期一第三部分代數(shù)結構

代數(shù)結構是以研究數(shù)字、文字和更一般元素的運算的規(guī)律和由這些運算適合的公理而定義的各種數(shù)學結構的性質為中心問題。它對現(xiàn)代數(shù)學如撲拓學、泛函分析等以及一些其他科學領域，如計算機科學、編碼理論等，都有重要影響和廣泛地應用。2第2頁，共29頁，2023年，2月20日，星期一第三部分代數(shù)結構主要內(nèi)容:代數(shù)系統(tǒng)----二元運算及其性質、代數(shù)系統(tǒng)和子代數(shù)半群與群----半群、獨異點、群環(huán)與域-----環(huán)、整環(huán)、域格與布爾代數(shù)----格、布爾代數(shù)3第3頁，共29頁，2023年，2月20日，星期一第4章代數(shù)系統(tǒng)主要內(nèi)容:(1)二元運算及其性質一元和二元運算定義及其實例二元運算的性質(2)代數(shù)系統(tǒng)代數(shù)系統(tǒng)定義及其實例子代數(shù)積代數(shù)(3)代數(shù)系統(tǒng)的同態(tài)與同構4第4頁，共29頁，2023年，2月20日，星期一4.1二元運算及其性質定義4.1設S為集合，函數(shù)f：SSS稱為S上的二元運算，簡稱為二元運算．S中任何兩個元素都可以進行運算，且運算的結果惟一．S中任何兩個元素的運算結果都屬于S，即S對該運算封閉．例1(1)自然數(shù)集合N上的加法和乘法是N上的二元運算，但減法和除法不是．(2)整數(shù)集合Z上的加法、減法和乘法都是Z上的二元運算，而除法不是．(3)非零實數(shù)集R*上的乘法和除法都是R*上的二元運算，而加法和減法不是．5第5頁，共29頁，2023年，2月20日，星期一實例(4)

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

6第6頁，共29頁，2023年，2月20日，星期一一元運算的定義與實例定義4.2設S為集合，函數(shù)f:S→S稱為S上的一元運算，簡稱一元運算.例2(1)求相反數(shù)是整數(shù)集合Z,有理數(shù)集合Q和實數(shù)集合R上的一元運算.

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

(3)在n(n≥2)階實矩陣的集合Mn(R)上，求轉置矩陣是Mn(R)上的一元運算.7第7頁，共29頁，2023年，2月20日，星期一二元與一元運算的表示1．算符可以用?,?,·,,,等符號表示二元或一元運算，稱為算符.對二元運算?，如果x與y運算得到z，記做x?y=z對一元運算,x的運算結果記作x.2．表示二元或一元運算的方法:解析公式和運算表公式表示例設R為實數(shù)集合，如下定義R上的二元運算?：x,y∈R,x?y=x.那么3?4=3，0.5?(3)=0.58第8頁，共29頁，2023年，2月20日，星期一運算表：表示有窮集上的一元和二元運算運算表

二元運算的運算表

一元運算的運算表9第9頁，共29頁，2023年，2月20日，星期一

例3

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

～運算的運算表如下:

運算表的實例10第10頁，共29頁，2023年，2月20日，星期一二元運算的性質定義4.3設?為S上的二元運算,(1)若對任意x,y∈S有x?y=y?x,則稱運算在S上滿足交換律.(2)若對任意x,y,z∈S有(x?y)?z=x?(y?z),則稱運算在S上滿足結合律.(3)若對任意x∈S有x?x=x,則稱運算在S上滿足冪等律.11第11頁，共29頁，2023年，2月20日，星期一二元運算的性質定義4.4設?和?為S上兩個不同的二元運算,(1)若對任意x,y,z∈S有(x?y)?z=(x?z)?(y?z)，z?(x?y)=(z?x)?(z?y),則稱?運算對?運算滿足分配律.(2)若和?都可交換,且對任意x,y∈S有x?(x?y)=x，x?(x?y)=x,則稱?和?運算滿足吸收律.12第12頁，共29頁，2023年，2月20日，星期一實例Z,Q,R分別為整數(shù)、有理數(shù)、實數(shù)集；Mn(R)為n階實矩陣集合,n2；P(B)為冪集；AA為從A到A的函數(shù)集，|A|2.集合運算交換律結合律冪等律Z,Q,R普通加法+普通乘法有有有有無無Mn(R)矩陣加法+矩陣乘法有無有有無無P(B)并交相對補對稱差有有無有有有無有有有無無AA函數(shù)復合無有無13第13頁，共29頁，2023年，2月20日，星期一集合運算分配律吸收律Z,Q,R普通加法+與乘法對+可分配+對不分配無Mn(R)矩陣加法+與乘法對+可分配+對不分配無P(B)并與交對可分配對可分配有交與對稱差

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

=x)，則稱el(或er)是S中關于?運算的左(或右)單位元.若e∈S關于?運算既是左單位元又是右單位元，則稱e為S上關于?運算的單位元.單位元也叫做幺元.15第15頁，共29頁，2023年，2月20日，星期一特異元素：零元定義4.5設?為S上的二元運算,(2)如果存在

l(或

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

l?x=

l

(或x?

r

=r)，則稱

l(或

r)是S中關于?運算的左(或右)零元.若

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

設?為S上的二元運算，el和er分別為S中關于運算的左和右單位元，則el

=er=e為S上關于?運算的惟一的單位元.設?為S上的二元運算，el和er分別為S中關于運算的左和右零元，則

l=r=

為S上關于?運算的惟一的零元.注意：(1)當|S|2（元素個數(shù)多于2個），單位元與零元是不同的；(2)當|S|=1（只有1個元素）時，這個元素既是單位元也是零元.19第19頁，共29頁，2023年，2月20日，星期一定理4.2

設?為S上可結合的二元運算,e為該運算的單位元,對于x∈S如果存在左逆元yl

和右逆元yr,則有yl=yr=y,且y是x的惟一的逆元.說明：對于可結合的二元運算，可逆元素x只有惟一的逆元，記作x1.書上例12。惟一性定理20第20頁，共29頁，2023年，2月20日，星期一4.2代數(shù)系統(tǒng)定義4.6非空集合S和S上k個一元或二元運算f1,f2,…,fk組成的系統(tǒng)稱為代數(shù)系統(tǒng),簡稱代數(shù)，記做<S,f1,f2,…,fk>.實例：(1)<N,＋>,<Z,＋,·>,<R,＋,·>是代數(shù)系統(tǒng)，+和·分別表示普通加法和乘法.(2)<Mn(R),＋,·>是代數(shù)系統(tǒng)，＋和·分別表示n階(n≥2)實矩陣的加法和乘法.(3)<Zn,,>是代數(shù)系統(tǒng)，Zn＝{0,1,…,n-1}，和分別表示模n的加法和乘法，對于x,y∈Zn，xy=(x＋y)modn，xy=(xy)modn(4)<P(S),,,~>是代數(shù)系統(tǒng)，和為并和交，~為絕對補.21第21頁，共29頁，2023年，2月20日，星期一代數(shù)系統(tǒng)的成分與表示構成代數(shù)系統(tǒng)的成分：集合（也叫載體，規(guī)定了參與運算的元素）運算（這里只討論有限個二元和一元運算）代數(shù)常數(shù)（通常是與運算相關的特異元素：如單位元等）研究代數(shù)系統(tǒng)時，如果把運算具有它的特異元素也作為系統(tǒng)的性質之一，那么這些特異元素可以作為系統(tǒng)的成分，叫做代數(shù)常數(shù).例如：代數(shù)系統(tǒng)<Z,+,0>：集合Z,運算+,代數(shù)常數(shù)0代數(shù)系統(tǒng)<P(S),∪,∩>：集合P(S),運算∪和∩，無代數(shù)常數(shù).22第22頁，共29頁，2023年，2月20日，星期一代數(shù)系統(tǒng)的表示(1)列出所有的成分：集合、運算、代數(shù)常數(shù)（如果存在）如<Z,+,0>,<P(S),∪,∩>(2)列出集合和運算，在規(guī)定系統(tǒng)性質時不涉及具有單位元的性質（無代數(shù)常數(shù)）如<Z,+>,<P(S),∪,∩>(3)用集合名稱簡單標記代數(shù)系統(tǒng)在前面已經(jīng)對代數(shù)系統(tǒng)作了說明的前提下使用如代數(shù)系統(tǒng)Z,P(B)23第23頁，共29頁，2023年，2月20日，星期一同類型與同種代數(shù)系統(tǒng)定義4.7(1)如果兩個代數(shù)系統(tǒng)中運算的個數(shù)相同，對應運算的元數(shù)相同，且代數(shù)常數(shù)的個數(shù)也相同，則稱它們是同類型的代數(shù)系統(tǒng).(2)如果兩個同類型的代數(shù)系統(tǒng)規(guī)定的運算性質也相同，則稱為同種的代數(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個二元運算,2個代數(shù)常數(shù).V1,V2是同種的代數(shù)系統(tǒng)，V1,V2與V3不是同種的代數(shù)系統(tǒng).24第24頁，共29頁，2023年，2月20日，星期一V1V2V3+可交換、可結合·可交換、可結合+滿足消去律·滿足消去律·對+可分配+對·不可分配+與·沒有吸收律+可交換、可結合·可交換、可結合+滿足消去律·不滿足消去律·對+可分配+對·不可分配+與·沒有吸收律∪可交換、可結合∩可交換、可結合∪不滿足消去律∩不滿足消去律∩對∪可分配∪對∩可分配∪與∩滿足吸收律運算性質比較25第25頁，共29頁，2023年，2月20日，星期一子代數(shù)系統(tǒng)定義4.8設V=<S,f1,f2,…,fk>是代數(shù)系統(tǒng)，B是S的非空子集，如果B對f1,f2,…,fk

都是封閉的，且B和S含有相同的代數(shù)常數(shù)，則稱<B,f1,f2,…,fk>是V的子代數(shù)系統(tǒng)，簡稱子代數(shù).有時將子代數(shù)系統(tǒng)簡記為B.實例:<N,＋>是<Z,＋>的子代數(shù)，<N,＋，0>也是<Z,＋,0>的子代數(shù);<N-{0},+>是<Z,＋>的子代數(shù)，但不是<Z,＋,0>的子代數(shù)，因為代數(shù)常數(shù)不一樣。說明：(1)子代數(shù)和原代數(shù)是同種的代數(shù)系統(tǒng).(2)對于任何代數(shù)系統(tǒng)V=<S,f1,f2,…,fk>，其子代數(shù)一定存在.26第26頁，共29頁，2023年，2月20日，星期一練習11．設°運算為Q上的二元運算，x,yQ,x°y=x+y+2xy,(1)判斷°運算是否滿足交換律和結合律，并說明理由.(2)求出°運算的單位元、零元和所有可逆元素的逆元.27第27頁，共29頁，2023年，2月20日，星期一(1)°

運算可交換，可結合.任取x,yQ,

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

x,任取x,y,zQ,