北大離散數(shù)學(xué)chap6-課件

第六章

幾個(gè)典型的代數(shù)系統(tǒng)第一節(jié)

半群與群2020/10/281內(nèi)容：半群，群，子群。重點(diǎn)：1、半群，可交換半群，獨(dú)異點(diǎn)的定義，2、群，交換群

(阿貝爾群)的定義及性質(zhì)，3、群的階的定義，4、循環(huán)群，生成元的定義及例子，5、子群的定義及判定。2020/10/282精品資料2020/10/283一、半群。1、定義：滿(mǎn)足結(jié)合律的代數(shù)系統(tǒng)稱(chēng)為半群。例1、(1)，，，，都是半群。(2)是半群。(3)是半群，其中表示集合的對(duì)稱(chēng)差運(yùn)算。2020/10/284一、半群。1、定義：滿(mǎn)足結(jié)合律的代數(shù)系統(tǒng)稱(chēng)為半群。(4)是半群，其中表示模，的加法?？山粨Q半群2020/10/2852、獨(dú)異點(diǎn)

(含幺半群)：記作如例1中除了不是獨(dú)異點(diǎn)外，其余的均是獨(dú)異點(diǎn)，分別記作，，，，，。2020/10/2863、半群中元素冪。定義運(yùn)算的冪，，指的是：(為正整數(shù))(

為非負(fù)整數(shù))2020/10/2874、子半群。半群的子代數(shù)叫子半群，獨(dú)異點(diǎn)的子代數(shù)叫子獨(dú)異點(diǎn)。例如：，都是的子半群，且是的子獨(dú)異點(diǎn)。2020/10/288二、群。1、定義。代數(shù)系統(tǒng)滿(mǎn)足：①結(jié)合律，②有幺元，③任意元有逆元，則稱(chēng)為群。2020/10/289例2、(1)，，都是群，因任意元素的逆元存在，而，不是群，沒(méi)有幺元，除0外，其余元素都沒(méi)有逆元。(2)不是群，因不是所有的階矩陣都可逆。2020/10/2810(3)是群，為幺元，，(4)是群，0為幺元，，2、交換群

(也稱(chēng)阿貝爾群)。如例2中的，，，都是阿貝爾群。，2020/10/2811例3、四元群。，運(yùn)算由下表給出：2020/10/28123、群的階。有限群的階，記。例如：的階為，四元群的階為4。2020/10/28134、群中元素的冪。對(duì)于群，定義：則可以把獨(dú)異點(diǎn)中的關(guān)于的定義擴(kuò)充為：為非負(fù)整數(shù))(為正整數(shù))(有關(guān)冪的兩個(gè)公式：2020/10/28145、群中元素的階

(或周期)。群中元素的階成立的最小正整數(shù)

——使。例如：四元群中，

的階都是2，記。的階為1，記。2020/10/2815例4、，求模6的加群中各元素的階。解：因，即，所以。同理可得：，，，。2020/10/28166、群的性質(zhì)。(1)，，。(2)若，則中無(wú)零元。(3)中消去律成立，即若，則，若，則。2020/10/28176、群的性質(zhì)。(4)幺元是群中唯一的冪等元。不同行

(列)的排列不同。(5)，方程和在中有唯一解。(6)有限群的運(yùn)算表中，每一行

(每一列)都是

中元素的一個(gè)排列。2020/10/2818例5、證明是阿貝爾群當(dāng)且僅當(dāng)對(duì)，。證明：設(shè)為阿貝爾群，則，有，故2020/10/2819例5、證明是阿貝爾群當(dāng)且僅當(dāng)對(duì)，。證明：反之，設(shè)，，即，即，由消去律，得

，故為阿貝爾群。2020/10/2820例6、如果中的每一個(gè)元素都滿(mǎn)足，則是阿貝爾群。證明：，由題設(shè)知，，，從而，所以是阿貝爾群。2020/10/2821例7、設(shè)群不是阿貝爾群，則中存在兩個(gè)非幺元的元素，，使得。證明：(1)先證存在，使。事實(shí)上，若，都有，即由例6知，是阿貝爾群，與題設(shè)矛盾。(2)再證結(jié)論成立。設(shè)，，令，則非幺元，且，但。2020/10/2822三、子群。1、定義：

設(shè)群，是的非空子集，若為群，則稱(chēng)為的子群，記作。例8、(1)群，令，則是的子群，同樣，也是的子群。2020/10/2823三、子群。1、定義：

設(shè)群，是的非空子集，若為群，則稱(chēng)為的子群，記作。例8、(2)四元群，有5個(gè)子群：，，，，其余均為真子群。其中和是平凡子群，2020/10/28242、判定。定理：設(shè)為群，是的非空子集，若對(duì)任意，都有，則是的子群。2020/10/2825例9、設(shè)和都是群的子群，證明也是的子群。證明：(1)先證非空。因?yàn)榈淖尤?，故，，從而，因此，非空?020/10/2826例9、設(shè)和都是群的子群，證明也是的子群。因都是的子群，故，從而，證明：(2)，則且，由判定定理知，為的子群。思考：若為群的子群，問(wèn)是的子群?jiǎn)幔?020/10/28273、生成子群，中心。(1)生成子群：設(shè)為群，，記例10、，群中由2生成的子群同理，，，，。2020/10/28283、生成子群，中心。(1)生成子群：設(shè)為群，，記(2)中心：設(shè)為群，記，稱(chēng)為群的中心。2020/10/2829四、循環(huán)群。1、定義：群中若存在使得，則稱(chēng)為循環(huán)群，記，稱(chēng)為的生成元。在循環(huán)群中，生成元的階與群的階一樣。循環(huán)群都是阿貝爾群。循環(huán)群的子群都是循環(huán)群。2020/10/28302、循環(huán)群的典型例子。例11、是循環(huán)群，其生成元為1和－1，因?yàn)槿魏握麛?shù)都可由若干個(gè)1或者若干個(gè)－1相加而得到。是無(wú)限階循環(huán)群，其子群除了外都是無(wú)限階循環(huán)群，如，其中2020/10/2831例12、是階循環(huán)群，，中與互質(zhì)的數(shù)均可作為生成元。階循環(huán)群的子群的階都是

的正因子，對(duì)于的每個(gè)正因子，在中只有一個(gè)階子群，就是由生成的子群。如：，其生成元有(均與12互質(zhì))。即2020/10/283212的正因子有，則的子群有：1階子群2階子群3階子群2020/10/283312的正因子有，則的子群有：4階子群6階子群12階子群2020/10/2834第二節(jié)

環(huán)與域

2020/10/2835內(nèi)容：環(huán)，域。了解：環(huán)與域的定義及例子。一、環(huán)。定義：設(shè)是代數(shù)系統(tǒng)，為集合，為二元運(yùn)算，若(1)為阿貝爾群。(2)為半群。(3)乘法對(duì)加法+適合分配律。則稱(chēng)是環(huán)。2020/10/2836例1、，，都是環(huán)。是環(huán)。是模的整數(shù)環(huán)。其中表示模的加法和乘法，，。2020/10/2837二、域。定義：環(huán)滿(mǎn)足：(1)至少兩個(gè)元素，(2)含有幺元，(3)是可交換的，(4)除加法幺元外，其余元素均有逆元，則稱(chēng)為域。2020/10/2838例2、，都是域，但不是域，因?yàn)椴皇浅?外，其余元素都有逆元。不是域，因不是可交換的。是域，但不是域。，但不存在乘法的逆元，使()令，則為域。2020/10/2839第三節(jié)

格與布爾代數(shù)

2020/10/2840內(nèi)容：格，格的性質(zhì)，布爾代數(shù)。重點(diǎn)：格與布爾代數(shù)的有關(guān)概念及例子。一、格的概念。定義：設(shè)是偏序集，如果對(duì)，都有最小上界

(記)和最大下界

(記)，則稱(chēng)關(guān)于構(gòu)成一個(gè)格。格也記作。2020/10/2841例1、設(shè)為正整數(shù)，

表示的所有正因子的集合，表示整除關(guān)系，則構(gòu)成格。的最小公倍數(shù)的最大公約數(shù)如：，2020/10/2842下圖給出了格，，，2020/10/2843下圖給出了格，，，2020/10/2844例2、判斷下圖中的偏序集是否構(gòu)成格，并說(shuō)明理由。2020/10/2845二、格的性質(zhì)。1、對(duì)偶原理：設(shè)是含有格中的元素以及符號(hào)的命題，令是將中的分別改寫(xiě)成所得到的命題，稱(chēng)為切格為真。也對(duì)一對(duì)一切格為真，則的對(duì)偶命題。若2020/10/28462、性質(zhì)：設(shè)為格，則運(yùn)算和適合交換律，結(jié)合律，冪等律和吸收律，即，有(1)交換律，(2)結(jié)合律，2020/10/28472、性質(zhì)：設(shè)為格，則運(yùn)算和適合交換律，結(jié)合律，冪等律和吸收律，即，有(3)冪等律，(4)吸收律，2020/10/2848三、分配格，有界格，有補(bǔ)格。1、分配格——滿(mǎn)足分配律的格。2、有界格——有全上界，全下界的格。

全上界記為1，全下界記為0，有界格也記為2020/10/2849三、分配格，有界格，有補(bǔ)格。4、有補(bǔ)分配格——有補(bǔ)格且是分配格。3、有補(bǔ)格——有界格，若對(duì)存在的補(bǔ)元(記)，使，，則稱(chēng)為有補(bǔ)格。2020/10/2850例3、所有的有限格

(指格中的元素有限個(gè))都是有界格。如例1中，格中的全上界為，全下界為1。但和不是有補(bǔ)格

(思考：為什么？)是有補(bǔ)格，互為補(bǔ)元，互為補(bǔ)元。是有補(bǔ)格，互為補(bǔ)元，2與15，3與10，5與6互為補(bǔ)元。2020/10/2851例4、判斷下圖中所表示的格是否有補(bǔ)格。不是有補(bǔ)格是有補(bǔ)格是有補(bǔ)格2020/10/28525、有補(bǔ)分配格中任意元素的補(bǔ)元是唯一的。四、布爾代數(shù)。1、定義：有補(bǔ)分配格稱(chēng)布爾代數(shù)，記為，其中“”表示求補(bǔ)運(yùn)算。例5、(1)開(kāi)關(guān)代數(shù)是布爾代數(shù)，其中為與運(yùn)算，為或運(yùn)算，為非運(yùn)算。

2020/10/2853例5、(2)集合代數(shù)是布爾代數(shù)。以下分別是的圖2020/10/28542、性質(zhì)。設(shè)為布爾代數(shù)，則(1)，，(2)，，德摩根律2020/10/28553、有限布爾代數(shù)的表示定理。對(duì)每個(gè)有限布爾代數(shù)，都存在一個(gè)有限集合，使得與其同構(gòu)。由這個(gè)定理知，有限布爾代數(shù)的元素只能是個(gè)，即。2020/10/2856不是布爾代數(shù)是布爾代數(shù)2020/10/2857第六章

小結(jié)與例題2020/10/2858一、半群與群。1、基本概念。半群，可換半群，獨(dú)異點(diǎn)；群，阿貝爾群，循環(huán)群；有限群，無(wú)限群；群的階；子群。2、運(yùn)用。(1)判斷一個(gè)代數(shù)系統(tǒng)是否為半群，獨(dú)異點(diǎn)，群。(2)判斷群

(半群，獨(dú)異點(diǎn))的一個(gè)子集是否構(gòu)成子群

(子半群，子獨(dú)異點(diǎn))。2020/10/2859一、半群與群。1、基本概念。半群，可換半群，獨(dú)異點(diǎn)；群，阿貝爾群，循環(huán)群；有限群，無(wú)限群；群的階；子群。2、運(yùn)用。(3)求一個(gè)群的所有子群。2020/10/2860二、環(huán)與域?；靖拍睿涵h(huán)；域。三、格與布爾代數(shù)。1、基本概念。格；分配格，有界格，有補(bǔ)格；布爾代數(shù)。判斷一個(gè)代數(shù)系統(tǒng)是否為格，布爾代數(shù)。2、運(yùn)用。2020/10/2861例1、為正整數(shù)集，，定義，問(wèn)是半群?jiǎn)?？是?dú)異點(diǎn)嗎？是群?jiǎn)?？解：因是上的二元運(yùn)算，且滿(mǎn)足結(jié)合律，故是半群；1是的幺元，故是獨(dú)異點(diǎn)，

但中除1外其余元素均無(wú)逆元，故不是群。2020/10/2862例2、設(shè)是半群，且，求證：。證明：因?yàn)?，由于是半群，運(yùn)算封閉，因此或若，則若，則故不論怎樣，都有。2020/10/2863例3、舉兩個(gè)是獨(dú)異點(diǎn)，但不是群的例子。解：(1)，其中是實(shí)數(shù)集，為數(shù)的乘法，是半群，且1為幺元，故為獨(dú)異點(diǎn)，但，0無(wú)逆元，故不是群。(2)，其中為全體有理數(shù)矩陣的集合，為矩陣的乘法運(yùn)算。顯然對(duì)封閉，滿(mǎn)足結(jié)合律，幺元是階單位矩陣，因此是獨(dú)異點(diǎn)。2020/10/2864例3、舉兩個(gè)是獨(dú)異點(diǎn)，但不是群的例子。解：(1)，其中是實(shí)數(shù)集，為數(shù)的乘法，是半群，且1為幺元，故為獨(dú)異點(diǎn)，但，0無(wú)逆元，故不是群。(2)，其中為全體有理數(shù)矩陣的集合，為矩陣的乘法運(yùn)算。但中行列式值為0的矩陣都無(wú)逆矩陣，故不是群。2020/10/2865例4、定義上的二元運(yùn)算如下：其中+是實(shí)數(shù)集

上的普通加法。(1)是半群?jiǎn)?？解：運(yùn)算封閉，且滿(mǎn)足結(jié)合律，

故是半群。(2)是獨(dú)異點(diǎn)嗎？解：是幺元，故是獨(dú)異點(diǎn)。2020/10/2866例4、定義上的二元運(yùn)算如下：其中+是實(shí)數(shù)集

上的普通加法。(3)是群?jiǎn)?？解：，故是的逆元，所以是群?020/10/2867例4、定義上的二元運(yùn)算如下：其中+是實(shí)數(shù)集

上的普通加法。(4)是阿貝爾群?jiǎn)?？解：滿(mǎn)足交換律，是阿貝爾群。2020/10/2868例5、對(duì)以下定義的集合和運(yùn)算判斷它們是不是代數(shù)系統(tǒng)，若是，再判斷是不是半群，獨(dú)異點(diǎn)，

群，布爾代數(shù)？(1)為普通乘法。，解：因?yàn)閷?duì)乘法不封閉，故不構(gòu)成代數(shù)系統(tǒng)。2020/10/2869例5、對(duì)以下定義的集合和運(yùn)算判斷它們是不是代數(shù)系統(tǒng)，若是，再判斷是不是半群，獨(dú)異點(diǎn)，

群，布爾代數(shù)？(2)，，，，有。解：是代數(shù)系統(tǒng)，且可結(jié)合，故是半群。但無(wú)幺元，不是獨(dú)異點(diǎn)。20