離散數(shù)學(xué)第5章

代數(shù)系統(tǒng)簡(jiǎn)介1整理ppt這局部?jī)?nèi)容屬于近世代數(shù)的范疇，近世代數(shù)是研究具有運(yùn)算的集合，它第一次揭示了數(shù)學(xué)系統(tǒng)的多變性與豐富性。代數(shù)結(jié)構(gòu)理論可用于計(jì)算機(jī)算法的復(fù)雜性分析，研究抽象數(shù)據(jù)結(jié)構(gòu)的性質(zhì)及操作，同時(shí)也是程序設(shè)計(jì)語(yǔ)言的理論根底。我們將介紹代數(shù)系統(tǒng)的最根本概念和最根本理論，以及幾類常用的代數(shù)系統(tǒng)，它們是：半群，幺半群，群，環(huán)，域，格和布爾代數(shù)。本課程在第五，六章中介紹代數(shù)系統(tǒng)的內(nèi)容。2整理ppt第五章

代數(shù)系統(tǒng)的一般性質(zhì)

第一節(jié)

二元運(yùn)算及性質(zhì)

3整理ppt內(nèi)容：二元運(yùn)算，運(yùn)算律，特殊元素。

重點(diǎn)：(1)一元和二元運(yùn)算的概念，

(2)二元運(yùn)算律

(結(jié)合律，交換律，分配律)，(3)二元運(yùn)算的特殊元素

(幺元，零元，逆元)。一般：吸收律，消去律，冪等律。4整理ppt一、二元運(yùn)算。

1、定義：設(shè)上的二元運(yùn)算(即運(yùn)算封閉)為集合，函數(shù)稱為，，元運(yùn)算，

掌握，，即一元，二元運(yùn)算。5整理ppt一、二元運(yùn)算。

2、記號(hào)：用等符號(hào)表示二元運(yùn)算，稱為算符。例如：記為(二元運(yùn)算)記為(一元運(yùn)算)6整理ppt但減法，除法不是。

但除法不是。例1、(1)上的加法，乘法都是二元運(yùn)算，

(2)上的加法，乘法，減法都是二元運(yùn)算，上求相反數(shù)的運(yùn)算是一元運(yùn)算。

(3)非零實(shí)數(shù)集上的乘法和除法都是二元運(yùn)算。但加法，減法不是，而求倒數(shù)是一元運(yùn)算。(4)表示所有

階實(shí)矩陣的集合

則矩陣的加法和乘法都是二元運(yùn)算。

，7整理ppt都是二元運(yùn)算，(5)集合的冪集

上的

而絕對(duì)補(bǔ)集(為全集)是一元運(yùn)算。

(6)所有命題公式的集合上的

都是二元運(yùn)算，而否定

為一元運(yùn)算。

(7)表示集合上的所有函數(shù)的集合，

函數(shù)的合成運(yùn)算

是

上的二元運(yùn)算。

8整理ppt3、一元，二元運(yùn)算表。當(dāng)為有窮集時(shí)，都可以用運(yùn)算表給出。上的一元和二元運(yùn)算例2、(1)設(shè)，給出

上的運(yùn)算絕對(duì)和對(duì)稱差

的運(yùn)算表。補(bǔ)集解：，“

”為一元運(yùn)算，

“”為二元運(yùn)算，其運(yùn)算表如下：

9整理ppt10整理ppt例2、(2)設(shè)，定義

二元運(yùn)算如下：

上的兩個(gè)求運(yùn)算和的運(yùn)算表。解：

分別是

，的和與積除以5的余數(shù)，運(yùn)算表如下：

11整理ppt12整理ppt二、有關(guān)運(yùn)算律。

設(shè)是上的二元運(yùn)算，

1、若，則稱

在

(或稱滿足交換律)上可交換。2、若，則稱在(或稱滿足結(jié)合律)上可結(jié)合。13整理ppt二、有關(guān)運(yùn)算律。

設(shè)是上的二元運(yùn)算，

3、若則稱運(yùn)算對(duì)是可分配的。

(或稱對(duì)滿足分配律)14整理ppt(2)矩陣的加法和乘法在上是可結(jié)合的，加法可交換，但乘法不可交換，乘法對(duì)加法是可分配的。例3、(1)普通的加法和乘法在

上都是可結(jié)合的，且是可交換的，乘法對(duì)加法是可分配的。15整理ppt(3)在冪集上可結(jié)合，可交換，但是相對(duì)補(bǔ)不可結(jié)合，不可交換，

和是互相可分配的。(4)在全體命題公式集合上可結(jié)合，可交換，和是相互可分配的。16整理ppt三、一些特殊元素。設(shè)為上的二元運(yùn)算，

1、幺元：若，對(duì)

則稱，為運(yùn)算的幺元。注：(1)假設(shè)幺元存在必唯一。(2)若只有或只有，則，稱為左幺元或右幺元。17整理ppt在上，矩陣加法的幺元是

階0矩陣，矩陣乘法的幺元是階單位矩陣。

在冪集

上，運(yùn)算的幺元是，運(yùn)算的幺元是全集

。例如：在上，加法的幺元是0，乘法的幺元是1。在算沒(méi)有幺元，只有右幺元0上的減法運(yùn)18整理ppt例4、在(非零實(shí)數(shù)集)上定義運(yùn)算如下：則中的任何元素都是右幺元，但沒(méi)有左幺元，使，從而沒(méi)有幺元。19整理ppt2、零元：若，對(duì)，，則稱

為運(yùn)算的零元。注：(1)假設(shè)零元存在必唯一。(2)若只有，或只有，則分別稱為左零元或右零元。如例4的任何元素都是左零元，從而也沒(méi)有零元。

但沒(méi)有右零元，20整理ppt例如：在上加法沒(méi)有零元，乘法的零元是0。在上矩陣加法沒(méi)有零元，矩陣乘法的零元是階0矩陣。在冪集上，運(yùn)算的零元是

，運(yùn)算的零元是。21整理ppt3、逆元：設(shè)

為上的二元運(yùn)算，為運(yùn)算的幺元，若對(duì)，存在

，使，則稱為的逆元。注：(1)逆元是針對(duì)某個(gè)元素

而言的(可能有些元素有逆元，有些沒(méi)有)(2)若二元運(yùn)算滿足結(jié)合律且存在則必唯一。的逆元22整理ppt3、逆元：設(shè)

為上的二元運(yùn)算，為運(yùn)算的幺元，若對(duì)，存在

，使，則稱為的逆元。注：(3)若只有或只有，則

稱為左逆元或右逆元。23整理ppt例如：普通加法運(yùn)算在上有幺元0，僅在上任意元素有逆元，滿足在上只有0有逆元0，而其它的自然數(shù)就沒(méi)有逆元。在上矩陣的乘法只有可逆矩陣存在逆元。冪集上關(guān)于運(yùn)算有幺元，但除了外，其余元素都沒(méi)有逆元。24整理ppt例5、判斷普通的加法和乘法運(yùn)算在下列集合中是否二元運(yùn)算。(1)解：加法，乘法都不是二元運(yùn)算。(2)解：加法不是二元運(yùn)算，乘法是二元運(yùn)算。25整理ppt例5、判斷普通的加法和乘法運(yùn)算在下列集合中是否二元運(yùn)算。(3)解：加法，乘法都是二元運(yùn)算。(4)解：加法不是二元運(yùn)算，乘法是二元運(yùn)算。26整理ppt例5、判斷普通的加法和乘法運(yùn)算在下列集合中是否二元運(yùn)算。(5)解：加法不是二元運(yùn)算，乘法是二元運(yùn)算。27整理ppt例6、在實(shí)數(shù)集上定義運(yùn)算如下：(1)是上的二元運(yùn)算嗎？解：因，是二元運(yùn)算。(2)在上滿足交換律，結(jié)合律嗎？解：因，滿足交換律，，滿足結(jié)合律。28整理ppt例6、在實(shí)數(shù)集上定義運(yùn)算如下：(3)關(guān)于有幺元，零元嗎？解：因?qū)?，，?為幺元，因，故為零元。29整理ppt例6、在實(shí)數(shù)集上定義運(yùn)算如下：(4)關(guān)于每個(gè)元素有逆元嗎？解：，有

且時(shí)，無(wú)逆元。故

時(shí)，，30整理ppt例7、設(shè)，二元運(yùn)算和

定義，問(wèn)運(yùn)算如下表和

是否可交換的；是否有零元；是否有幺元；如果有幺元，指出哪些元素有逆元；

逆元是什么？

31整理ppt(1)沒(méi)有零元，可交換，解：運(yùn)算是幺元，都有逆元，且，互為逆元。

32整理ppt(2)不可交換，解：運(yùn)算是左零元，是幺元，只有有逆元，，由于，故是的左逆元，的右逆元，是33整理ppt(2)解：但它們的逆元都不存在。34整理ppt四、其它一些運(yùn)算律和特殊元素。(了解)1、設(shè)和都是上的可交換的二元運(yùn)算，若，則稱和滿足吸收律。35整理ppt四、其它一些運(yùn)算律和特殊元素。(了解)2、設(shè)是上的二元關(guān)系，若(不是零元)滿足：(1)若

，則

(2)若，則

就稱運(yùn)算滿足消去律。36整理ppt四、其它一些運(yùn)算律和特殊元素。(了解)3、冪等元。是上的二元運(yùn)算，對(duì)設(shè)，若，則稱

為冪等元。若上所有元素都是冪等元，則稱運(yùn)算

滿足冪等律。37整理ppt例如：上的運(yùn)算

和，全體命題公式集合上的運(yùn)算和都滿足吸收律，又分別滿足冪等律，但都不滿足消去律

(如，不一定有)。上的加法運(yùn)算都不滿足冪等律，但它們都有冪等元，幺元就是冪等元。38整理ppt第二節(jié)代數(shù)系統(tǒng)及其子代數(shù)

和積代數(shù)

39整理ppt內(nèi)容：代數(shù)系統(tǒng)，子代數(shù)，積代數(shù)。重點(diǎn)：掌握代數(shù)系統(tǒng)，子代數(shù)的有關(guān)概念。了解：積代數(shù)的概念。

40整理ppt一、代數(shù)系統(tǒng)。1、定義：非空集合和

上的個(gè)運(yùn)算

(其中為元運(yùn)算，)組成的系統(tǒng)稱為一個(gè)代數(shù)系統(tǒng)，簡(jiǎn)稱代數(shù)，記作。例如：，，，，都是代數(shù)系統(tǒng)。41整理ppt2、代數(shù)常數(shù)

(特異元素)。在某些代數(shù)系統(tǒng)中對(duì)于給定的二元運(yùn)算存在幺元或零元，它們對(duì)該系統(tǒng)的性質(zhì)起著重要作用，稱為代數(shù)常數(shù)(特異元素)。例如：的幺元0，也可記為，中和的幺元分別為和，同樣可記為。42整理ppt二、子代數(shù)系統(tǒng)。1、定義：設(shè)是代數(shù)系統(tǒng)，且，若對(duì)運(yùn)算都是封閉的，且和含有相同的代數(shù)常數(shù)，則稱為的子代數(shù)系統(tǒng)，簡(jiǎn)稱子代數(shù)。43整理ppt例如：是的子代數(shù)，是的子代數(shù)，但是的子代數(shù)，卻不是的子代數(shù)，因代數(shù)常數(shù)。44整理ppt2、平凡子代數(shù)，真子代數(shù)。設(shè)是代數(shù)系統(tǒng)的子代數(shù)，當(dāng)和時(shí)，稱為平凡子代數(shù)

(分別是最大和最小的子代數(shù))，當(dāng)時(shí)，稱為的真子代數(shù)。45整理ppt例1、設(shè)，令為自然數(shù)，，那么是的子代數(shù)。，證明：，則即對(duì)+封閉，又，所以是的子代數(shù)。46整理ppt證明：當(dāng)時(shí)，，當(dāng)時(shí)，，它們是的平凡子代數(shù)，而其它的子代數(shù)都是的非平凡的真子代數(shù)。例1、設(shè)，令為自然數(shù)，，那么是的子代數(shù)。47整理ppt例1、設(shè)，令為自然數(shù)，，那么是的子代數(shù)。當(dāng)時(shí)，，當(dāng)時(shí)，，它們是的平凡子代數(shù)，而其它的子代數(shù)都是的非平凡的真子代數(shù)。48整理ppt三、積代數(shù)。設(shè)是代數(shù)系統(tǒng)，，其中和是二元運(yùn)算，令，對(duì)則為代數(shù)系統(tǒng)，稱為的積代數(shù)，記。49整理ppt例如：和的積代數(shù)為其中運(yùn)算為二元運(yùn)算，對(duì)，，，50整理ppt例如：和的積代數(shù)為，，，有代數(shù)常數(shù)0，有代數(shù)常數(shù)，有代數(shù)常數(shù)。51整理ppt第三節(jié)

代數(shù)系統(tǒng)的同態(tài)與同構(gòu)

52整理ppt內(nèi)容：代數(shù)系統(tǒng)的同態(tài)映射，同構(gòu)映射。一般：掌握同態(tài)，單同態(tài)，滿同態(tài)，同構(gòu)的定義及判定。一、同態(tài)映射，同構(gòu)映射的概念。代數(shù)系統(tǒng)的同態(tài)和同構(gòu)是研究?jī)蓚€(gè)代數(shù)系統(tǒng)之間的關(guān)系。53整理ppt1、定義：設(shè)是代數(shù)系統(tǒng)，，其中和都是二元運(yùn)算，若存在映射

(即函數(shù))，滿足對(duì)任意的，有則稱是到的同態(tài)映射，簡(jiǎn)稱同態(tài)。滿同態(tài)，記單同態(tài)同構(gòu)，記注：若存在從到的滿同態(tài)，則稱為在下的同態(tài)象。54整理ppt例1、(1)，，其中為普通加法，為模加法，即，有，這里令，則對(duì)，55整理ppt例1、(1)，，其中為普通加法，為模加法，即，有，這里令，所以是到的同態(tài)。顯然是滿射，所以，即滿同態(tài)，但不是單同態(tài)56整理ppt例1、(2)，，則對(duì)令，，所以是到的同態(tài)。由于是雙射，所以是同構(gòu)，思考：，是同構(gòu)映射嗎？57整理ppt2、自同態(tài)，自同構(gòu)。自同態(tài)——從一個(gè)代數(shù)系統(tǒng)到自己的同態(tài)稱為自同態(tài)。

自同構(gòu)——從一個(gè)代數(shù)系統(tǒng)到自己的同構(gòu)稱為自同構(gòu)。

58整理ppt則對(duì)例2、，給定，令，所以是到的同態(tài)，即自同態(tài)。當(dāng)時(shí)，有，，稱為零同態(tài)。59整理ppt則對(duì)例2、，給定，令，所以是到的同態(tài)，即自同態(tài)。當(dāng)時(shí)，有，，即恒等映射，它是雙射的，這時(shí)是的自同構(gòu)，同理可證也是的自同構(gòu)。60整理ppt則對(duì)例2、，給定，令，所以是到的同態(tài)，即自同態(tài)。當(dāng)且時(shí)，易證是單射的，這時(shí)是的單自同態(tài)。61整理ppt3、同態(tài)，同構(gòu)概念的推廣。(1)，62整理ppt例3、，，其中為普通的加法，乘法，為模加法，乘法令，，則對(duì)，63整理ppt例3、，，其中為普通的加法，乘法，為模加法，乘法令，，所以是到的同態(tài)，且是滿同態(tài)。64整理ppt(2)，(3)，65整理ppt例4、(1)，，其中為普通加法和乘法，表示求的相反數(shù)，

表示的倒數(shù)。令，，則對(duì)，所以是到的同態(tài)。66整理ppt例4、(2)，，其中0是加法幺元，1是乘法幺元，都是代數(shù)常數(shù)，，同(1)，即則有，所以是到的同態(tài)。67整理ppt二、性質(zhì)。設(shè)是從到的滿同態(tài)，則1、若可結(jié)合，則也是可結(jié)合。2、若可交換，則也是可交換。3、若是關(guān)于的幺元，則是關(guān)于的幺元。4、若是關(guān)于的零元，則是關(guān)于的零元。68整理ppt二、性質(zhì)。設(shè)是從到的滿同態(tài)，則5、若是關(guān)于的冪等元，則是關(guān)于的冪等元。6、若是中元素關(guān)于的逆元，則是中元素關(guān)于的逆元。注：若分別有兩個(gè)二元運(yùn)算，且中分配律成立，則中分配律也成立。69整理ppt第五章

小結(jié)與例題

70整理ppt一、二元運(yùn)算及其性質(zhì)。1、根本概念。一元運(yùn)算和二元運(yùn)算；二元運(yùn)算的結(jié)合律，交換律，分配律，冪等律，吸收律，消去律；二元運(yùn)算的特殊元素：幺元，零元，逆元；一元運(yùn)算和二元運(yùn)算的運(yùn)算表。

71整理ppt一、二元運(yùn)算及其性質(zhì)。2、運(yùn)用。(1)判斷給定的二元運(yùn)算是否滿足結(jié)合律，交換律，分配律，冪等律，吸收律，消去律等。(2)求幺元，零元，逆元。(3)列出一元運(yùn)算和二元運(yùn)算的運(yùn)算表。

72整理ppt二、代數(shù)系統(tǒng)及其子代數(shù)和積代數(shù)。1、根本概念。代數(shù)系統(tǒng)；子代數(shù)；積代數(shù)。2、運(yùn)用。判斷代數(shù)系統(tǒng)的子集能否構(gòu)成子代數(shù)系統(tǒng)。

73整理ppt三、代數(shù)系統(tǒng)的同態(tài)與同構(gòu)。1、根本概念。同態(tài)，單同態(tài)，滿同態(tài)；同構(gòu)。2、運(yùn)用。判斷兩個(gè)代數(shù)系統(tǒng)是否同態(tài)，單同態(tài)，滿同態(tài)，同構(gòu)。74整理ppt例1、數(shù)的加，減，乘，除是否為下述集合上的二元運(yùn)算。(1)實(shí)數(shù)集解：加、減、乘是二元運(yùn)算，除不是二元運(yùn)算。

(2)非零實(shí)數(shù)集

解：加、減不是二元運(yùn)算，乘、除是二元運(yùn)算。75整理ppt例1、數(shù)的加，減，乘，除是否為下述集合上的二元運(yùn)算。(3)正整數(shù)集解：加、乘是二元運(yùn)算，減、除不是二元運(yùn)算。(4)解：乘是二元運(yùn)算，加、減、除都不是二元運(yùn)算。76整理ppt例1、數(shù)的加，減，乘，除是否為下述集合上的二元運(yùn)算。(5)解：乘、除是二元運(yùn)算，加、減不是二元運(yùn)算。77整理ppt例2、正整數(shù)集上的二元運(yùn)算表示兩個(gè)數(shù)

的最小公倍數(shù)。(1)求解：(2)問(wèn)在上滿足交換律，結(jié)合律，冪等律嗎？解：因?qū)θ我獾恼麛?shù)有，，故滿足交換律，結(jié)合律，冪等律。78整理ppt例2、正整數(shù)集上的二元運(yùn)算表示兩個(gè)數(shù)

的最小公倍數(shù)。(3)求幺元，零元。(4)中任意元都有逆元嗎？解：因，故1是幺元，

不存在零元。解：中只有1有逆元，其它元素都沒(méi)有逆元。79整理ppt例3、在有理數(shù)集上定義二元運(yùn)算，有(1)求，解：80整理ppt例3、在有理數(shù)集上定義二元運(yùn)算，有(2)在上滿足結(jié)合律嗎？解：對(duì)任意的故滿足結(jié)合律。81整理ppt例3、在有理數(shù)集上定義二元運(yùn)算，有(3)求幺元。解：對(duì)任意的故0是幺元。82整理ppt例3、在有理數(shù)集上定義二元運(yùn)算，有(4)中哪些元素存在逆元？解：對(duì)任意的，設(shè)是的逆元，則解得：即時(shí)，有逆元83整理ppt例4、如下定義實(shí)數(shù)集上的二元運(yùn)算，判斷是否可交換，可結(jié)合？是否有幺元？若有幺元，指出中哪些元素有逆元？(1)解：可交換；但不可結(jié)合，如：，而，即；無(wú)幺元。84整理ppt例4、如下定義實(shí)數(shù)集上的二元運(yùn)算，判斷是否可交換，可結(jié)合？是否有幺元？若有幺元，