關(guān)于我們
書單推薦
新書推薦
|
離散數(shù)學(xué)簡明教程
離散數(shù)學(xué)是研究離散量的結(jié)構(gòu)和相互間關(guān)系的學(xué)科,是計算機、軟件工程等專業(yè)的理論基礎(chǔ).
本書依據(jù)教育部計算機科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會編制的《高等學(xué)校計算機科學(xué)與技術(shù)專業(yè)規(guī)范》和《高等學(xué)校計算機科學(xué)與技術(shù)專業(yè)核心課程教學(xué)實施方案》進行編寫,簡要介紹離散數(shù)學(xué)的集合論、抽象代數(shù)、圖論和數(shù)理邏輯4個部分,主要包括集合及其運算,關(guān)系,函數(shù),代數(shù)系統(tǒng),群、環(huán)和域,格和布爾代數(shù),圖與樹,特殊圖,命題邏輯,謂詞邏輯共10章,“整數(shù)的整除與同余”一章作為預(yù)備知識供學(xué)習(xí)集合論和代數(shù)系統(tǒng)部分時參考.由于教材以集合論開頭,便于學(xué)生學(xué)習(xí)時循序漸進,同時由于教材內(nèi)容簡明扼要,例題和習(xí)題多且包含一些實際應(yīng)用問題,從而可以調(diào)動學(xué)生的學(xué)習(xí)積極性,培養(yǎng)學(xué)生的數(shù)學(xué)思維和解決實際問題的能力,為后續(xù)專業(yè)課程的學(xué)習(xí)奠定良好的基礎(chǔ).
本書可作為高等院校計算機、軟件工程及相關(guān)專業(yè)本科生“離散數(shù)學(xué)”課程的教材,也可供從事計算機、軟件工程及相關(guān)領(lǐng)域研究和應(yīng)用開發(fā)人員自學(xué)或參考.
離散數(shù)學(xué)是研究離散量的結(jié)構(gòu)和相互間關(guān)系的學(xué)科,是計算機、軟件工程等專業(yè)的理論基礎(chǔ)。本書依據(jù)教育部計算機科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會編制的《高等學(xué)校計算機科學(xué)與技術(shù)專業(yè)規(guī)范》和《高等學(xué)校計算機科學(xué)與技術(shù)專業(yè)核心課程教學(xué)實施方案》進行編寫,簡要介紹了離散數(shù)學(xué)的集合論、抽象代數(shù)、圖論和數(shù)理邏輯4個部分,主要包括集合及其運算,關(guān)系,函數(shù);代數(shù)系統(tǒng),群、環(huán)和域,格和布爾代數(shù);圖與樹,特殊圖;命題邏輯,謂詞邏輯等十章,“整數(shù)的整除與同余”一章作為預(yù)備知識供學(xué)習(xí)代數(shù)系統(tǒng)部分時參考。由于教材以集合論開頭,便于學(xué)生學(xué)習(xí)時循序漸進,同時由于教材內(nèi)容簡明扼要,例題和習(xí)題多且包含一些實際應(yīng)用問題,從而可以調(diào)動學(xué)生的學(xué)習(xí)積極性,培養(yǎng)學(xué)生的數(shù)學(xué)思維和解決實際問題的能力,為后續(xù)專業(yè)課程的學(xué)習(xí)奠定良好的基礎(chǔ)。
本書是作者根據(jù)多年從事離散數(shù)學(xué)課程教學(xué)實踐,并在參閱國內(nèi)外優(yōu)秀經(jīng)典教材的基礎(chǔ)上編寫完成的。 主要特色如下: 。1)內(nèi)容簡明扼要,便于自學(xué); 。2)符號統(tǒng)一規(guī)范; 。3)例題側(cè)重應(yīng)用實際; 。4)習(xí)題由易到難分層編排。
離散數(shù)學(xué)是相對于連續(xù)數(shù)學(xué)而言的.從數(shù)學(xué)的發(fā)展歷程來看,最開始的數(shù)學(xué)是離散的數(shù)學(xué),如計數(shù);后面出現(xiàn)微積分這樣連續(xù)的數(shù)學(xué);隨著計算機的出現(xiàn),離散數(shù)學(xué)重新找到了它應(yīng)有的位置.
廣義來講,離散數(shù)學(xué)包括兩個方面,一個是連續(xù)數(shù)學(xué)的離散化,即計算數(shù)學(xué)或數(shù)值分析的研究內(nèi)容;另一個就是離散量自身的研究內(nèi)容.一般而言,離散數(shù)學(xué)是研究離散量的結(jié)構(gòu)和相互間關(guān)系的學(xué)科.離散結(jié)構(gòu)則是離散數(shù)學(xué)和組合數(shù)學(xué)的統(tǒng)稱. 離散數(shù)學(xué)是計算機、軟件工程專業(yè)的一門核心基礎(chǔ)課程,其主要作用如下: 。1)離散數(shù)學(xué)為后繼專業(yè)課程如數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫原理、數(shù)字邏輯、信息安全、編譯原理、人工智能、操作系統(tǒng)等提供必要的數(shù)學(xué)基礎(chǔ); 。2)離散數(shù)學(xué)為從事計算機科學(xué)各方面的工作以及解決計算機科學(xué)中遇到的實際問題等提供有力的工具; 。3)離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個重要分支,通過該課程的學(xué)習(xí)可以提高邏輯思維與抽象思維能力、創(chuàng)造性思維能力以及分析和解決實際問題的能力等,培養(yǎng)出高素質(zhì)的人才. 離散數(shù)學(xué)課程的主要內(nèi)容可以分為4個部分,其導(dǎo)圖如下.課程以離散量為研究對象,內(nèi)容豐富,涉及面寬,具有4個主要的特點:以集合論為基礎(chǔ);高度的抽象性;推理的嚴密性;應(yīng)用的廣泛性. 本課程概念多、定理多、推理多,并且內(nèi)容較為抽象.但由于它是為后繼專業(yè)知識的學(xué)習(xí)做必要的數(shù)學(xué)準備的,因此它研究的內(nèi)容均比較基礎(chǔ),難度不大.在學(xué)習(xí)離散數(shù)學(xué)的過程中,不必過分關(guān)注它的用處以及它在計算機學(xué)科中所起的作用,而應(yīng)從以下幾個方面入手,力爭學(xué)好本課程的全部內(nèi)容. 。1)熟讀教材,重于細節(jié).這是學(xué)好離散數(shù)學(xué)不可缺少的一環(huán),要準確理解各個概念和定理的含義,要看懂必要的推理過程. 。2)獨立思考,加強練習(xí).在熟讀教材的基礎(chǔ)上,必須通過練習(xí)、獨立思考來真正獲取知識.(3)注重抽象思維能力的培養(yǎng).要學(xué)好這門課程,必須具有較強的抽象思維能力,才能深入掌握課程內(nèi)容.證明技巧的訓(xùn)練,可以促進推理技能的提高、邏輯抽象的深入、思維方式的嚴謹和理解能力的增強. 本教材是編者根據(jù)多年從事離散數(shù)學(xué)課程教學(xué)實踐,并在參閱國內(nèi)同行編著的多本教材的基礎(chǔ)上編寫完成的,特別是在教學(xué)中一直選用洪帆教授主編的《離散數(shù)學(xué)基礎(chǔ)》組織教學(xué),因此受到了許多潛移默化的影響,在此表示衷心的感謝.教材的編寫得到了華中科技大學(xué)教材建設(shè)項目的資助和清華大學(xué)出版社的支持,在此一并表示衷心的感謝. 講授本教材的基本部分約需64~80學(xué)時.教材習(xí)題分為A類題和B類題兩類,其中B類題多為知識拓展和難度較大的綜合題,供學(xué)習(xí)者選做.另有思考題散布于教材內(nèi)容之中.教材還配有電子教案,與教材配套的習(xí)題解答也在整理之中. 限于編者的水平,書中錯誤和疏漏之處在所難免,敬請讀者不吝指正. 編者2017年4月于武漢
盧力,博士,華中科技大學(xué)軟件學(xué)院副教授,碩士研究生導(dǎo)師。主持和參加過多項科研課題的研究工作,近幾年發(fā)表科研論文二十余篇,主要研究方向是高性能計算、圖像信號處理、信息安全等。講授過多門本科生和研究生的公共基礎(chǔ)課、專業(yè)基礎(chǔ)課和專業(yè)課。近年來主要為本科生講授“離散數(shù)學(xué)”、“數(shù)學(xué)建!钡日n程。是湖北省高等學(xué)校省級精品課程:“軟件項目管理與分析”成員。出版《線性代數(shù)學(xué)習(xí)與考試指導(dǎo)》和華中科技大學(xué)網(wǎng)絡(luò)教育視頻課件系列: 線性代數(shù)。
第0章整數(shù)的整除與同余1
0.1整除及帶余除法1
0.1.1整數(shù)1
0.1.2整除的概念與性質(zhì)2
0.1.3帶余除法3
0.1.4整數(shù)的進制表示法4
0.1.5數(shù)學(xué)歸納法7
0.2整數(shù)分解8
0.2.1最大公因數(shù)及其性質(zhì)8
0.2.2歐幾里得算法10
0.2.3因式分解法11
0.3同余15
0.3.1同余的概念和性質(zhì)15
0.3.2線性同余方程18
0.3.3中國剩余定理20
0.3.4威爾遜定理、歐拉定理與費馬小定理22
習(xí)題25
第1篇集合論27
第1章集合及其運算29
1.1集合的基本概念29
1.1.1集合和元素29
1.1.2集合的表示方法30
1.1.3集合的基數(shù)31
1.2集合間的關(guān)系31
1.2.1集合的包含31
1.2.2集合的相等32
1.2.3維恩圖32
1.2.4冪集33
1.2.5有限集合冪集元素的編碼表示341.3集合的運算和運算定律34
1.3.1集合的運算34
1.3.2集合運算的定律35
1.3.3集合恒等式的證明方法37
1.3.4包含排斥原理39
1.4集合成員表40
1.4.1并、交和補集的成員表40
1.4.2有限個集合產(chǎn)生的集合的成員表40
1.4.3利用集合成員表證明集合恒等式41
1.5集合的覆蓋與分劃42
1.6集合的標準形式43
1.6.1最小集標準形式43
1.6.2最大集標準形式46
1.6.3集合范式的說明47
1.7多重集合49
習(xí)題49
第2章關(guān)系54
2.1笛卡兒積與關(guān)系54
2.1.1笛卡兒積54
2.1.2關(guān)系的基本概念56
2.2關(guān)系的表示方法57
2.2.1集合表示法57
2.2.2矩陣表示法58
2.2.3關(guān)系圖表示法58
2.3關(guān)系的運算59
2.3.1關(guān)系的并、交、差、補運算59
2.3.2關(guān)系的逆運算60
2.3.3關(guān)系的復(fù)合運算61
2.4關(guān)系的性質(zhì)66
2.4.1關(guān)系性質(zhì)的定義66
2.4.2關(guān)系性質(zhì)的判別67
2.5關(guān)系的閉包702.5.1關(guān)系閉包的定義70
2.5.2關(guān)系閉包的性質(zhì)72
2.5.3關(guān)系閉包的求法74
2.6等價關(guān)系77
2.6.1等價關(guān)系的基本概念77
2.6.2等價類的性質(zhì)78
2.6.3等價關(guān)系與分劃79
2.6.4等價關(guān)系的其他性質(zhì)80
2.7相容關(guān)系81
2.7.1相容關(guān)系的基本概念81
2.7.2相容關(guān)系與覆蓋82
2.8偏序關(guān)系84
2.8.1偏序關(guān)系的基本概念84
2.8.2偏序關(guān)系的次序圖84
2.8.3偏序集的特殊元素85
2.8.4全序和良序87
習(xí)題88
第3章函數(shù)95
3.1函數(shù)及性質(zhì)95
3.1.1函數(shù)的基本概念95
3.1.2函數(shù)的性質(zhì)97
3.2復(fù)合函數(shù)99
3.2.1復(fù)合函數(shù)的定義99
3.2.2函數(shù)復(fù)合運算的性質(zhì)100
3.2.3復(fù)合函數(shù)的性質(zhì)101
3.3逆函數(shù)103
3.3.1逆函數(shù)的定義103
3.3.2逆函數(shù)的性質(zhì)104
3.3.3左、右逆函數(shù)105
3.4無限集的基數(shù)106
3.4.1抽屜原理106
3.4.2集合的等勢107
3.4.3可數(shù)集的基數(shù)1083.4.4不可數(shù)集的基數(shù)111
3.4.5集合基數(shù)的比較112
習(xí)題114
第2篇抽象代數(shù)119
第4章代數(shù)系統(tǒng)121
4.1代數(shù)運算121
4.1.1代數(shù)運算的概念121
4.1.2二元運算的性質(zhì)123
4.1.3特殊元素124
4.2代數(shù)系統(tǒng)與子代數(shù)128
4.2.1代數(shù)系統(tǒng)的概念128
4.2.2子代數(shù)的概念129
4.3代數(shù)系統(tǒng)的同態(tài)與同構(gòu)130
4.3.1代數(shù)系統(tǒng)的同態(tài)130
4.3.2滿同態(tài)的性質(zhì)132
4.3.3同構(gòu)的性質(zhì)132
4.4代數(shù)系統(tǒng)的積代數(shù)134
習(xí)題135
第5章群、環(huán)和域139
5.1半群和獨異點139
5.1.1半群和獨異點的基本概念139
5.1.2子半群和子獨異點142
5.1.3半群和獨異點的同態(tài)143
5.2群143
5.2.1群的基本概念143
5.2.2群的基本性質(zhì)146
5.2.3群的同態(tài)148
5.3置換群與循環(huán)群148
5.4子群及其陪集152
5.4.1子群的定義1525.4.2子群的判別153
5.4.3陪集與正規(guī)子群155
5.4.4拉格朗日定理158
5.5環(huán)和域160
5.5.1環(huán)160
5.5.2整環(huán)162
5.5.3域163
5.5.4環(huán)和域的同態(tài)165
習(xí)題166
第6章格和布爾代數(shù)170
6.1格及其性質(zhì)170
6.1.1格的偏序集定義170
6.1.2格的性質(zhì)171
6.1.3格的代數(shù)系統(tǒng)定義174
6.1.4子格175
6.1.5格的同態(tài)176
6.2分配格和有補格177
6.2.1分配格177
6.2.2有補格179
6.2.3有補分配格181
6.3布爾代數(shù)182
6.3.1布爾代數(shù)的基本概念182
6.3.2布爾代數(shù)的性質(zhì)184
習(xí)題186
第3篇圖論191
第7章圖與樹195
7.1圖的基本概念195
7.1.1圖及其圖解表示195
7.1.2完全圖與補圖197
7.1.3結(jié)點的度與握手定理1987.1.4圖的連通性199
7.1.5圖的同構(gòu)202
7.1.6子圖與分圖204
7.1.7圖的運算207
7.2圖的矩陣表示208
7.2.1圖的關(guān)聯(lián)矩陣208
7.2.2圖的鄰接矩陣209
7.2.3圖的連接矩陣211
7.3樹213
7.3.1樹的基本概念213
7.3.2樹的基本性質(zhì)213
7.3.3最小生成樹215
7.4有向樹219
7.4.1有向樹的基本概念219
7.4.2二元樹及其周游221
7.4.3有向樹中的一些數(shù)量關(guān)系222
習(xí)題223
第8章特殊圖229
8.1歐拉圖229
8.1.1歐拉圖的基本概念229
8.1.2歐拉圖的判別230
8.1.3中國郵路問題232
8.2哈密頓圖233
8.2.1哈密頓圖的基本概念233
8.2.2哈密頓圖的判別233
8.2.3流動售貨員問題235
8.3二部圖237
8.3.1二部圖的基本概念237
8.3.2二部圖的判別238
8.3.3匹配問題239
8.4平面圖240
8.4.1平面圖的基本概念240
8.4.2平面圖的判別2428.4.3地圖著色問題246
習(xí)題248
第4篇數(shù)理邏輯253
第9章命題邏輯257
9.1命題的基本概念257
9.2命題聯(lián)結(jié)詞258
9.3命題公式的基本概念262
9.4命題公式的等值關(guān)系和蘊含關(guān)系266
9.4.1命題公式的等值關(guān)系266
9.4.2基本的等值式266
9.4.3等值式的判定267
9.4.4命題公式的蘊含關(guān)系271
9.4.5基本的蘊含式271
9.4.6蘊含式的判定272
9.4.7命題公式的對偶274
9.5命題公式的范式275
9.5.1析取范式和合取范式275
9.5.2主析取范式和主合取范式277
9.6命題演算的推理理論281
9.6.1推理的概念281
9.6.2推理的方法281
習(xí)題285
第10章謂詞邏輯293
10.1個體、謂詞和量詞293
10.2謂詞公式的基本概念297
10.3謂詞公式的等值關(guān)系與蘊含關(guān)系300
10.3.1謂詞公式的類型300
10.3.2謂詞公式間的等值與蘊含關(guān)系301
10.3.3謂詞公式的對偶30510.4謂詞公式的范式305
10.4.1前束范式305
10.4.2前束合取范式與前束析取范式306
10.4.3斯柯林范式308
10.5謂詞演算的推理理論309
10.5.1推理規(guī)則310
10.5.2推理規(guī)則的應(yīng)用311
習(xí)題314
參考文獻319
第5章群、環(huán)和域
接下來的兩章將介紹常見的幾種代數(shù)結(jié)構(gòu),它們是用代數(shù)方法建立的數(shù)學(xué)模型.本章著重討論具有一個二元運算的代數(shù)系統(tǒng),包括半群、獨異點和群以及具有兩個二元運算的代數(shù)系統(tǒng),包括環(huán)和域.群、環(huán)和域在組合計數(shù)、編碼理論、形式語言與自動機理論等學(xué)科中都發(fā)揮了重要作用,而群是抽象代數(shù)中最古老且發(fā)展得最完善的代數(shù)系統(tǒng).在計算機科學(xué)中,對于代碼的查錯和糾錯、自動機理論等各個方面的應(yīng)用的研究,群是其基礎(chǔ). 本章的主要內(nèi)容為半群、獨異點和群的定義和基本性質(zhì),子群及其陪集,環(huán)和域的定義和基本性質(zhì)等. 5.1半群和獨異點〖*4/5〗5.1.1半群和獨異點的基本概念定義5.1設(shè)S是一個非空集合,是S上的一個二元運算,如果運算是可結(jié)合的,則稱代數(shù)系統(tǒng)是半群. 若在半群中,運算滿足交換律,則稱為交換半群. 例如,(1)代數(shù)系統(tǒng)和、和、和都是半群,且都是交換半群.但和不是半群,因為運算不滿足結(jié)合律. (2)代數(shù)系統(tǒng),都是半群,是交換半群,不是交換半群. (3)代數(shù)系統(tǒng)<2U;∪>和<2U;∩>都是半群,且都是交換半群. (4)設(shè)S={R|R是集合A上的關(guān)系},則對于關(guān)系的復(fù)合運算,代數(shù)系統(tǒng)是半群,但不是交換半群. 若F={f|f是A上的函數(shù)},則對于函數(shù)的復(fù)合運算,代數(shù)系統(tǒng)也是半群,但不是交換半群. 【例5.1】設(shè)S是非空集合,對任意的x,y∈S,定義xy=y,則代數(shù)系統(tǒng)是半群,但不是交換半群. 【例5.2】設(shè)代數(shù)系統(tǒng)是半群,a∈S,如果對任意的x,y∈S,每當(dāng)ax=ay都有x=y,則稱元素a是左可約的.試證明,如果a,b是左可約的,則ab也是左可約的. 證明對任意的x,y∈S,假設(shè)有(ab)x=(ab)y. 因為是半群,所以是可結(jié)合的,有(ab)x=a(bx),(ab)y=a(by)則由假設(shè)有a(bx)=a(by)因為a是左可約的,所以bx=by. 又因為b是左可約的,所以x=y. 即對任意的x,y∈S,如果(ab)x=(ab)y,則有x=y.所以由左可約的定義可知,ab也是左可約的. 因為半群中運算是可結(jié)合的,所以可以定義元素的冪. 定義5.2設(shè)是一個半群,則對任意的x∈S和任意正整數(shù)n,定義x的n次冪為x1=x,xn+1=xnx(n∈Z+)(5.1)并稱n為x的指數(shù). 對任意的正整數(shù)m,n和任意的x∈S,有xmxn=xm+n,(xm)n=xmn(5.2)定理5.1設(shè)是一個有限的半群,則必有a∈S,使得a是一個冪等元. 證明對任意的x∈S,因為是半群,故由運算的封閉性和結(jié)合律知,x2=xx∈S,x3=x2x=xx2∈S,…因為S是有限集,所以根據(jù)鴿籠原理知,必存在正整數(shù)j>i,使得xi=xj. 令p=j-i,便有xi(=xj=xp+i)=xpxi. 由此可得xq=xpxq(正整數(shù)q≥i). 因為p≥1,所以總可以找到正整數(shù)k≥1,使得kp≥i. 對于S中的元素xkp,就有xkp=xpxkp =xp(xpxkp) =x2pxkp =… =xkpxkp.此即證得,在S中存在元素a=xkp,使得aa=a.■ 定義5.3若半群中的運算有單位元,則稱該半群為含幺半群,常稱為獨異點. 若獨異點中的運算滿足交換律,則稱該獨異點為交換獨異點. 例如,(1)代數(shù)系統(tǒng)和、和、和都是獨異點,且都是交換獨異點.但和不是獨異點. (2)代數(shù)系統(tǒng),都是獨異點,是交換獨異點,不是交換獨異點. (3)代數(shù)系統(tǒng)<2U;∪>和<2U;∩>都是獨異點,且都是交換獨異點. (4)設(shè)S={R|R是集合A上的關(guān)系},則對于關(guān)系的復(fù)合運算,代數(shù)系統(tǒng)是獨異點,但不是交換獨異點. 若F={f|f是A上的函數(shù)},則對于函數(shù)的復(fù)合運算,代數(shù)系統(tǒng)也是獨異點,但不是交換獨異點. 注意: (1)獨異點中唯一的單位元常記為e. (2)設(shè)為獨異點,則關(guān)于運算的運算表中沒有兩行或兩列是相同的. 事實上,對任意的x,y∈S,當(dāng)x≠y時,總有xe=x≠y=ye和ex=x≠y=ey,所以在的運算表中不可能有兩行或兩列是相同的. 在獨異點中也可定義元素的冪. 定義5.4設(shè)是一個獨異點,則對任意的x∈S和任意非負整數(shù)n,定義x的n次冪為x0=e,xn+1=xnx(n∈N)(5.3)并稱n為x的指數(shù). 對任意的非負整數(shù)m,n和任意的x∈S,有xmxn=xm+n,(xm)n=xmn(5.4)定義5.5在獨異點中,如果存在元素g∈S,使得S中的每一元素a都能寫成gi(i∈N)的形式,則稱獨異點為循環(huán)獨異點,元素g稱為該循環(huán)獨異點的生成元. 【例5.3】試證是循環(huán)獨異點,并求其生成元. 證明是獨異點,且0是加法運算的單位元. 對任意的i∈N,若i≠0,則i=1+1+…+1(i個1相加)=1i;若i=0,則有0=10. 故為循環(huán)獨異點,其生成元為1. 【例5.4】是一個獨異點,其中S={1,a,b,c,d},是S上的二元運算,其運算表如表5.1所示.表5.1 1abcd11abcdaaabddbbbdaaccdabbdddabb因為1是單位元,a是冪等元,b3=d3=a,因此1,a,b,d的任意非負整數(shù)次冪最多只能表示S中4個不同元.而c0=1,c1=c,c2=b,c3=a,c4=d所以獨異點是一個循環(huán)獨異點,其中c是生成元. 定理5.2每一個循環(huán)獨異點都是交換獨異點. 證明設(shè)為循環(huán)獨異點且g為其生成元,則對任意的x,y∈S,存在m,n∈N,使得x=gm,y=gn.于是xy=gmgn=gm+n=gn+m=gngm=yx所以是交換獨異點.■ 定理5.3設(shè)是一個有限的獨異點,則對每一個x∈S存在正整數(shù)j,使得xj是一個冪等元. 證明見定理5.1的證明.■ 例如,例5.4中1,a,b3(=a),d3(=a),c3(=a)是冪等元. 定理5.4設(shè)是獨異點,a,b∈S且可逆,則 (1)(a-1)-1=a. (2)(ab)-1=b-1a-1. 證明(1)設(shè)a-1是a的逆元,則有aa-1=a-1a=e,因此a-1可逆,且(a-1)-1=a. (2)設(shè)a-1是a的逆元,b-1是b的逆元,因為(ab)(b-1a-1)=a(bb-1)a-1=aea-1=aa-1=e, (b-1a-1)(ab)=b-1(a-1a)b=b-1eb=b-1b=e,所以ab可逆,且(ab)-1=b-1a-1.■ 5.1.2子半群和子獨異點 定義5.6設(shè)是一個半群,若是的子代數(shù),則稱為的子半群. 設(shè)是一個獨異點,若是的子代數(shù),且單位元e∈H,則稱為的子獨異點. 由定義知,子半群(子獨異點)是一個半群(獨異點);半群(獨異點)是自身的一個子半群(子獨異點).此外,<{e};>也是獨異點的子獨異點. 【例5.5】對于半群的任一元素x∈S,令集合H={x,x2,x3,…},則是的子半群. 【例5.6】對于半群,Z+的子集A2={2n|n∈Z+},A3={3n|n∈Z+},A4={4n|n∈Z+},…都是的子半群. 【例5.7】對于獨異點,子集A2,A3,A4,…(同例5.6)均不能形成的子獨異點;而B2={2n|n∈N},B3={3n|n∈N},B4={4n|n∈N},…都能形成的子獨異點. 定理5.5設(shè)是一個交換獨異點,則S的所有冪等元的集合H形成的一個子獨異點. 證明由于S中單位元e適合e2=e,所以e∈H,于是H是S的非空子集且包含S中的單位元e. 對任意的x,y∈H,由x2=x,y2=y和運算是可交換的得知(xy)2=x2y2=xy因此xy∈H,于是H對于運算是封閉的,從而是的一個子獨異點.■ 【思考5.1】設(shè)代數(shù)系統(tǒng)和都是獨異點,若HS,則是的子獨異點嗎? 5.1.3半群和獨異點的同態(tài) 代數(shù)系統(tǒng)的同態(tài)(單同態(tài)、滿同態(tài))、同構(gòu)和積代數(shù)的概念以及一些有關(guān)的結(jié)論可以推廣到半群和獨異點中. 定理5.6設(shè)h是從代數(shù)系統(tǒng)V1=到代數(shù)系統(tǒng)V2=的滿同態(tài),其中運算和都是二元運算,則 (1)若V1是(交換)半群,則V2也是(交換)半群. (2)若V1是(交換)獨異點,則V2也是(交換)獨異點. 推論5.1(交換)半群的同態(tài)像是(交換)半群,(交換)獨異點的同態(tài)像是(交換)獨異點. 定理5.7給定代數(shù)系統(tǒng)V1=和V2=,其中運算和都是二元運算,則 (1)若V1和V2是(交換)半群,則V1×V2也是(交換)半群. (2)若V1和V2是(交換)獨異點,則V1×V2也是(交換)獨異點. 5.2群〖*4/5〗5.2.1群的基本概念〖*2〗1.群的定義定義5.7設(shè)是一個代數(shù)系統(tǒng),如果G上的二元運算滿足下列條件,則稱是一個群,簡記成群G. (1)運算是可結(jié)合的; (2)存在單位元e∈G; (3)G中所有元素都可逆. 如果群的運算是可交換的,則稱該群為交換群或阿貝爾群. 例如,代數(shù)系統(tǒng)、、、、<2U;∪>、<2U;∩>都是群,且為交換群.但、、、都不是群,因為不是所有元都可逆. 【例5.8】代數(shù)系統(tǒng)為群,且為交換群. 證明(1)先證運算滿足結(jié)合律. 對任意的a,b,c∈Nn,令a+b=nm1+resn(a+b),b+c=nm2+resn(b+c)則有 (anb)nc=resn(a+b)nc=resn(resn(a+b)+c)
你還可能感興趣
我要評論
|