幾個典型的代數(shù)系統(tǒng)離散數(shù)學(xué)

1、幾個典型的代數(shù)系統(tǒng)離散數(shù)學(xué)9/3/20221第1頁，共61頁，2022年，5月20日，9點2分，星期一1 半群與群DEFINITION 1. 設(shè)V=是代數(shù)系統(tǒng)，為二元運算，如果是可結(jié)合的，則稱V為半群。如： (1) , , , , 都是半群，其中+表示普通加法。(2) 是半群，其中表示矩陣乘法。9/3/20222第2頁，共61頁，2022年，5月20日，9點2分，星期一可交換半群：半群V中的二元運算可交換。含幺半群（獨異點）：半群V中的二元運算含有幺元。子半群：半群的子代數(shù)。子獨異點：獨異點的子代數(shù)。積半群：若V1, V2是半群，則V1V2是積半群。積獨異點：若V1, V2是獨異點，則V1V2

2、是積獨異點。9/3/20223第3頁，共61頁，2022年，5月20日，9點2分，星期一(1) , , , , 都是可交換半群。(2) 不是可交換半群，因為矩陣乘法不適合交換律。(1)中除了外都是獨異點，其中普通加法的幺元是0。(2) 是獨異點，矩陣乘法的幺元是n階單位矩陣E。, 都是的子半群，且 也是的子獨異點，但不是的子獨異點，因為幺元0Z，但0Z+。9/3/20224第4頁，共61頁，2022年，5月20日，9點2分，星期一DEFINITION 2. 設(shè)V1=, V2=為半群，: S1S2，且x, yS1，有：(x y)= (x) * (y)，則稱為半群V1到V2的同態(tài)。設(shè)V1=, V2

3、=為獨異點，: S1S2，且x, yS1，有：(x y)= (x) * (y)， (e1)= e2，則稱為獨異點V1到V2的同態(tài)。9/3/20225第5頁，共61頁，2022年，5月20日，9點2分，星期一EXAMPLE 1 設(shè)半群V1=，獨異點V2=，其中 ，為矩陣乘法。令： ，則TS，且T對矩陣乘法是封閉的。 是V1=的子半群。9/3/20226第6頁，共61頁，2022年，5月20日，9點2分，星期一在中存在自己的幺元 ，因為也構(gòu)成一個獨異點，但它不是V2=的子獨異點。V2中的幺元9/3/20227第7頁，共61頁，2022年，5月20日，9點2分，星期一令有： 是半群V1的自同態(tài)，但不

4、是滿自同態(tài)，且同態(tài)象為9/3/20228第8頁，共61頁，2022年，5月20日，9點2分，星期一對于獨異點V2=，還是同一個映射，根據(jù)前面的證明，對x, yS都有：(x y)= (x) (y)，但是而 不是獨異點V2的幺元， 不是獨異點V2的自同態(tài)。9/3/20229第9頁，共61頁，2022年，5月20日，9點2分，星期一DEFINITION 3. 設(shè)是代數(shù)系統(tǒng)，為二元運算。如果是可結(jié)合的，存在幺元eG，并且對G中的任意元素x都有x-1G，則稱G為群。如，(1) , , 都是群，而 , 不是群，因為中的元素都沒有逆元，而在中只有0有逆元0。(2) 不是群，因為不是所有的實矩陣都有逆矩陣。9

5、/3/202210第10頁，共61頁，2022年，5月20日，9點2分，星期一EXAMPLE 2 設(shè)G=a, b, c, e，為G上的二元運算，由下表給出，不難證明G是一個群。e a b ceabce a b ca e c bb c e ac b a e該運算的特點：e為G中的幺元；是可交換的；G中的任何元素的逆元就是它自己；在a, b, c三個元素中，任何兩個元素運算的結(jié)果都等于另一個元素。稱這個群為Klein四元群。9/3/202211第11頁，共61頁，2022年，5月20日，9點2分，星期一一些特殊的群：交換群：群G中的二元運算可交換。也叫阿貝爾(Abel)群。無限群：群G中有無限多個

6、元素。有限群：群G中有有限個元素。有限群G中的元素個數(shù)叫做G的階，記作|G|。9/3/202212第12頁，共61頁，2022年，5月20日，9點2分，星期一如，(1) , , 都是阿貝爾群，Klein四元群也是阿貝爾群。(2) , 都是無限群， 是有限群，其階是n，Klein四元群也是有限群，其階是4。9/3/202213第13頁，共61頁，2022年，5月20日，9點2分，星期一定理1：設(shè)G為群，則G中的冪運算滿足(1) 對xG，(x-1)-1=x.(2) 對x, yG，(xy)-1=y-1x-1.(3) 對xG，xnxm=xn+m.(4) 對xG，(xn)m=xnm. m, n是整數(shù)。9

7、/3/202214第14頁，共61頁，2022年，5月20日，9點2分，星期一定理2： 設(shè)G為群，對a, bG，方程ax=b和ya=b在G中有解，且有唯一解。 易證方程ax=b的唯一解是x=a-1b，而方程ya=b的唯一解是y=ba-1。9/3/202215第15頁，共61頁，2022年，5月20日，9點2分，星期一如，S=1, 2, 3，在群中有方程1, 2 x=1, 3，由定理2有x=a-1b=1,2-1 1,3=1,2 1,3=2,3。即為原方程的解。 1 2 3 1,2 1,3 2,3 1,2,31231,21,32,31,2,3 1 2 3 1,2 1,3 2,3 1,2,31 1,

8、2 1,3 2 3 1,2,3 2,32 1,2 2,3 1 1,2,3 3 1,33 1,3 2,3 1,2,3 1 2 1,2 1,2 2 1 1,2,3 2,3 1,3 31,3 3 1,2,3 1 2,3 1,2 22,31,2,33 2 1,3 1,2 11,2,32,31,31,2 3 2 1 同理可知，方程y1=2,3 的解是y=1,2,3。abab9/3/202216第16頁，共61頁，2022年，5月20日，9點2分，星期一定理3：設(shè)G為群，則G中適合消去律，即對a, b, cG，有：(1) 若ab=ac，則b=c.(2) 若ba=ca，則b=c.9/3/202217第17頁

9、，共61頁，2022年，5月20日，9點2分，星期一定理4： 設(shè)G為有限群，則G的運算表中的每一行（每一列）都是G中元素的一個置換，且不同的行（或列）的置換都不相同。 這就是說，在G的運算表的每一行里。G的每個元素都出現(xiàn)且僅出現(xiàn)一次，行不同，元素的排列順序也不同。使用這個定理可以通過運算表很快地判斷出哪些代數(shù)系統(tǒng)G=不是群。9/3/202218第18頁，共61頁，2022年，5月20日，9點2分，星期一DEFINITION 4. 設(shè)群，H是G的非空子集。如果H關(guān)于G中的運算*構(gòu)成群，則稱H為G的子群，記作HG。如，在群中，取2Z=2z|zZ，則2Z關(guān)于加法運算構(gòu)成的子群。同樣，0也是的子群。9

10、/3/202219第19頁，共61頁，2022年，5月20日，9點2分，星期一定理5：設(shè)G為群，H是G的非空子集，如果對x, yH，都有xy-1H，則H是G的子群。子群判定定理如，對xG，G為群，令H=xk | kZ，即x的所有次冪的集合。則H是G的子群。xm, xlH，有：xm(xl)-1=xmx-l=xm-lH。稱這個子群是由元素x生成的子群，記作。9/3/202220第20頁，共61頁，2022年，5月20日，9點2分，星期一EXAMPLE 3 群（其中表示模6加法）中由2生成的子群包含2的各次冪，21=2，22=22=4，23=222=0 =0, 2, 4。同理有：=0，=0, 1,

11、2, 3, 4, 5，=0, 3， =0, 2, 4。9/3/202221第21頁，共61頁，2022年，5月20日，9點2分，星期一又如，設(shè)G為群，令C是與G中所有的元素都可交換的元素構(gòu)成的集合，即C=a | aGxG(ax=xa)，則C是G的子群。 a, bC，要證明ab-1C，只要證明ab-1與G中所有的元素都可交換就行了。 xG，有：(ab-1)x =ab-1x =ab-1(x-1)-1)=a(x-1b)-1=a(bx-1)-1 =a(xb-1)=(ax)b-1=(xa)b-1 =x(ab-1) 。 C是G的子群。稱C為群G的中心9/3/202222第22頁，共61頁，2022年，5月

12、20日，9點2分，星期一DEFINITION 5. 在群G中如果存在aG使得G=ak | kZ，則稱G為循環(huán)群，記作G=，稱a為G的生成元。如，是循環(huán)群，其生成元是1或-1，因為任何整數(shù)都可以由若干個1或若干個-1相加而得到。 也是循環(huán)群，其生成元是1或5，因為0, 1, 5中的每個數(shù)都可以由1或5作若干次模6加法而得到。 循環(huán)群都是阿貝爾群，但阿貝爾群不一定都是循環(huán)群。9/3/202223第23頁，共61頁，2022年，5月20日，9點2分，星期一循環(huán)群生成元的判定方法： 對無限階循環(huán)群G=，G的生成元是a和a-1。 對n階循環(huán)群G=e, a, a2, , an-1，G的生成元是at當(dāng)且僅當(dāng)

13、t與n是互質(zhì)的。 是無限階循環(huán)群，生成元是1和-1，-1是1的加法逆元。 是6階循環(huán)群，1和5都與6互質(zhì)，所以1和5是生成元。 12階循環(huán)群G=e, a, , a11中，與12互質(zhì)的數(shù)有1, 5, 7, 11，則G的生成元就是a, a5, a7, a11。9/3/202224第24頁，共61頁，2022年，5月20日，9點2分，星期一循環(huán)群G=的子群仍是循環(huán)群。若G是無限階循環(huán)群，則G的子群除了e外都是無限階；N階循環(huán)群G=的子群的階都是n的正因子。對于n的每個正因子d，G中只有一個d階子群，就是由an/d生成的子群。9/3/202225第25頁，共61頁，2022年，5月20日，9點2分，星

14、期一DEFINITION 6. 設(shè)S=1, 2, , n，S上的任何雙射函數(shù): SS構(gòu)成了S上n個元素的置換，稱為n元置換。如，S=1, 2, 3，令: SS，且有(1)=2, (2)=3, (3)=1, 則將1, 2, 3分別置換成2, 3, 1。此置換常被記為：9/3/202226第26頁，共61頁，2022年，5月20日，9點2分，星期一一般的n元置換可記為：n個不同元素有n!種排列方法。所以S上有n!個置換。如，1, 2, 3上有3!=6種不同的置換，即9/3/202227第27頁，共61頁，2022年，5月20日，9點2分，星期一簡記法： 設(shè)n元置換=(a1a2am), mn，則的映

15、射關(guān)系是：(a1)=a2, (a2)=a3, , (am-1)=am, (am)=a1，而其它的元素a都有(a)=a，稱為m次輪換。任何n元置換都可表成不交的輪換之積。如，是1, 2, , 6上的置換，且除了3和4這兩個保持不變的元素外，其它元素的映射關(guān)系為： (1)=6, (6)=1, (2)=5, (5)=2。 =(1 6)(2 5)9/3/202228第28頁，共61頁，2022年，5月20日，9點2分，星期一又如，也是1, 2, , 6上的置換，且則有=(1 4 3 2 5)。根據(jù)這種表法，1, 2, 3上的置換可記為：1=(1), 2=(1 2), 3=(1 3), 4=(2 3),

16、 5=(1 2 3), 6=(1 3 2)9/3/202229第29頁，共61頁，2022年，5月20日，9點2分，星期一 設(shè)S=1, 2, , n，S上的n!個置換構(gòu)成集合Sn，其中恒等置換IS=(1)Sn，在Sn上規(guī)定二元運算，對任意n元置換, Sn，表示與的復(fù)合。 證明Sn關(guān)于置換的復(fù)合構(gòu)成一個群。證明：(1) 設(shè), Sn，與的復(fù)合顯然也是S上的n元置換，即 Sn， Sn對運算是封閉的。(2) , , Sn，顯然()=()，Sn對運算是可結(jié)合的。(3) , Sn，有IS = IS =，則恒等置換IS 是Sn中的幺元，且的逆置換 就是的逆元。 Sn關(guān)于置換的復(fù)合構(gòu)成一個群。S上的n元對稱群

17、9/3/202230第30頁，共61頁，2022年，5月20日，9點2分，星期一 n元對稱群的任何子代數(shù)稱為n元置換群。 如：S3=(1), (1 2), (1 3), (2 3), (1 2 3), (1 3 2)就是3元對稱群。因為S3關(guān)于置換的復(fù)合運算不能交換，所以S3不是阿貝爾群。 S3有6個子群，即有6個3元置換群。 見P135。9/3/202231第31頁，共61頁，2022年，5月20日，9點2分，星期一2 環(huán)與域DEFINITION 7. 設(shè)是代數(shù)系統(tǒng)，R為集合，+, 為二元運算，如果(1) 為阿貝爾群；(2) 為半群；(3) 乘法對加法+適合分配律。則稱是環(huán)。+可結(jié)合、可交換

18、，存在幺元，且任何元素都有逆元。可結(jié)合9/3/202232第32頁，共61頁，2022年，5月20日，9點2分，星期一如：(1) , , 都是環(huán)。(2) 是環(huán)。(3) 是模n的整數(shù)環(huán)。其中Zn =0, 1, , n-1，和分別表示模n的加法和乘法，即x, yZn，有：x y =(x+y) mod nx y =(xy) mod n9/3/202233第33頁，共61頁，2022年，5月20日，9點2分，星期一交換環(huán)：在環(huán)中，適合交換律。含幺環(huán)：在環(huán)中，有幺元。此時，通常把+幺元記作0，幺元記作1?？梢宰C明+的幺元恰好是的零元。左（右）零因子：在環(huán)中，若a,bR, a0, b0，但ab=0，則a為

19、R中的左零因子。b為R中的右零因子。無零因子環(huán)：環(huán)R中既不含左零因子，也不含右零因子，即a,bR, ab=0a=0b=0.0為的零元9/3/202234第34頁，共61頁，2022年，5月20日，9點2分，星期一如：(1) , , , 都是交換環(huán)。不是交換環(huán)，因為矩陣乘法運算不可交換。(2) 它們都是含幺環(huán)。因為1是的幺元，也是的幺元。n階單位矩陣E是環(huán)Mn(R)的乘法幺元。(3) , , 都是無零因子環(huán)。而不一定是無零因子環(huán)。如中有23=0，但2和3都不是0，所以不是無零因子環(huán)，而是無零因子環(huán)。9/3/202235第35頁，共61頁，2022年，5月20日，9點2分，星期一DEFINITIO

20、N 8. 若環(huán)是交換、含幺、和無零因子的，則稱R為整環(huán)。 若環(huán)至少含有2個元素且是含幺和無零因子的，并且aR(a0)有a-1R，則稱R為除環(huán)。 若環(huán)既是整環(huán)，又是除環(huán)，則稱R是域。（至少含有2個元素、交換、含幺、無零因子、除0外都有逆元）9/3/202236第36頁，共61頁，2022年，5月20日，9點2分，星期一如：(1) 是整環(huán)但不是域。因為乘法可交換，1是幺元，且不含零因子，所以是整環(huán)。但除了1之外，任何整數(shù)都沒有乘法的逆元，所以不是域。(2) 是域，即實數(shù)域。因為xR，x0，有：x-1=1/xR.9/3/202237第37頁，共61頁，2022年，5月20日，9點2分，星期一EXAM

21、PLE 4 設(shè)S為下列集合，+和為普通加法和乘法。(1) S=x | x=2nnZ.(2) S=x | x=2n+1nZ.(3) S=x | xZx0=N.(4)問S和+, 能否構(gòu)成整環(huán)？能否構(gòu)成域？為什么？9/3/202238第38頁，共61頁，2022年，5月20日，9點2分，星期一解：(1) 不是整環(huán)，也不是域。因為乘法幺元是1，而1S.(2) 不是整環(huán)，也不是域。因為不是群，S當(dāng)然就不是環(huán)，+的幺元是0，而0S.(3) 不是群，因為除0以外任何正整數(shù)x的加法逆元是-x，而-xS. S當(dāng)然就不是環(huán)，更不是整環(huán)和域。9/3/202239第39頁，共61頁，2022年，5月20日，9點2分，

22、星期一(4) S是域。x1, x2S，有：S對+和是封閉的。又乘法幺元1S，易證是整環(huán)。是域。9/3/202240第40頁，共61頁，2022年，5月20日，9點2分，星期一定理6：設(shè)是環(huán)，則：(1) aR，a0=0a=0.(2) a, bR，(-a)b=a(-b)=-(ab).(3) a, bR，(-a)(-b)=ab.(4) a, b, cR，a(b-c)=ab-ac. (b-c)a=ba-ca.在環(huán)中做加法和乘法只能遵從加法的交換律和結(jié)合律、乘法的結(jié)合律、乘法對加法的分配律，以及此定理中所給出的算律。9/3/202241第41頁，共61頁，2022年，5月20日，9點2分，星期一EXAM

23、PLE 5 設(shè)是環(huán)，a, bR，計算(a-b)2和(a+b)3.解：(a-b)2=(a-b)(a-b) =a2-ba-ab-b(-b) =a2-ba-ab+b2.(a+b)3=(a+b)(a+b)(a+b) =(a2+ba+ab+b2)(a+b) =a3+ba2+aba+b2a+a2b+bab+ab2+b3.冪運算分配律及定理6(2)定理6(3)及冪運算冪運算分配律及冪運算分配律及冪運算注：乘法沒有交換律注：乘法沒有交換律9/3/202242第42頁，共61頁，2022年，5月20日，9點2分，星期一3 格與布爾代數(shù) 格有兩種等價的定義：一種是從偏序集的角度給出格的定義，這種定義可以借助哈斯(

24、Hasse)圖來表示，因而比較直觀、易于理解，這樣定義的格稱為偏序格；另一種是從代數(shù)系統(tǒng)的角度來給出格的定義，這種定義方法我們在上幾節(jié)的群、環(huán)的定義中已有所體會，用代數(shù)系統(tǒng)的方法定義的格稱為代數(shù)格。9/3/202243第43頁，共61頁，2022年，5月20日，9點2分，星期一 布爾代數(shù)是計算機科學(xué)最重要的基礎(chǔ)理論之一，它在開關(guān)網(wǎng)絡(luò)及數(shù)字電路的設(shè)計上有廣泛深入的應(yīng)用。 布爾代數(shù)是計算機科學(xué)工作者必備的基礎(chǔ)知識，應(yīng)掌握格與布爾代數(shù)的一般理論和方法。9/3/202244第44頁，共61頁，2022年，5月20日，9點2分，星期一DEFINITION 7. 設(shè)是偏序集，如果x, yS，x, y都有最

25、小上界和最大下界，則稱S關(guān)于構(gòu)成一個格。 可將求x, y的最小上界和最大下界看成x與y的二元運算和，即xy和xy。偏序格9/3/202245第45頁，共61頁，2022年，5月20日，9點2分，星期一EXAMPLE 6 設(shè)n為正整數(shù)，Sn為n的正因子的集合，D為整除關(guān)系，則構(gòu)成格。 x, ySn，xy是x與y的最小公倍數(shù)，xy是x與y的最大公約數(shù)。 8421123612356101530如：9/3/202246第46頁，共61頁，2022年，5月20日，9點2分，星期一EXAMPLE 7 判斷下圖中偏序集是否構(gòu)成格，為什么？abcdefabdeceabdfc解：都不是格。(1)中的a, b沒有

26、下界。(2)中的b, d有上界c和e，但沒有最小上界。(3)中的b, c有上界d, e, f，但沒有最小上界。(1) (2) (3)9/3/202247第47頁，共61頁，2022年，5月20日，9點2分，星期一格的對偶原理： 設(shè)f 是含有格中的元素以及符號=, , , , 的命題，令f *是將f 中的改寫成，改寫成，改寫成，改寫成所得到的命題，稱為f 的對偶命題。若f 對一切格為真，則f *也對一切格為真。9/3/202248第48頁，共61頁，2022年，5月20日，9點2分，星期一定理7： 設(shè)為格，則運算和適合交換律、結(jié)合律、冪等律和吸收律，即：(1) a, bL，有ab=ba, ab=

27、ba.(2) a, b, cL，有(ab)c=a(bc), (ab)c=a(bc).(3) aL，有aa=a, aa=a.(4) a, bL，有a(ab)=a, a(ab)=a.9/3/202249第49頁，共61頁，2022年，5月20日，9點2分，星期一證明：(1) ab和ba分別是a, b和b, a的最小上界，由于a, b=b, a，所以ab=ba。同理可證ab=ba.(2) 由最小上界的定義有： aa(bc), bbca(bc), cbca(bc). 由式和有： aba(bc). 再由式和有： (ab)ca(bc).同理可證： (ab)ca(bc).根據(jù)偏序關(guān)系的反對稱性有：(ab)c

28、=a(bc).類似地可以證明：(ab)c=a(bc).9/3/202250第50頁，共61頁，2022年，5月20日，9點2分，星期一(3) 顯然aaa，又由aa可得aaa。根據(jù)偏序關(guān)系的反對稱性有：aa=a.同理可證：aa=a.(4) 顯然a(ab)a。 又由aa, aba，可得： a(ab)a. 由式和可得：a(ab)=a.同理可證：a(ab)=a.9/3/202251第51頁，共61頁，2022年，5月20日，9點2分，星期一DEFINITION 8. 設(shè)是具有兩個二元運算的代數(shù)系統(tǒng)，且對于*和適合交換律、結(jié)合律、吸收律，則可以適當(dāng)定義S中的偏序，使得構(gòu)成一個格，且a, bS，有ab=a

29、*b, ab=a b.代數(shù)格只要吸收律成立，則冪等律就一定成立。證： aS，有aa=a(a*(aa)=a. 同理可證a*a=a.9/3/202252第52頁，共61頁，2022年，5月20日，9點2分，星期一DEFINITION 9. 設(shè)是格，若a, b, cL，有a(bc)=(ab)(ac) a(bc)=(ab)(ac)成立，則稱L為分配格。9/3/202253第53頁，共61頁，2022年，5月20日，9點2分，星期一DEFINITION 10. 在格中存在一個元素a，bL, ab(或ba)，則稱a為格L的全下界（或全上界），記為0（或1）。 具有全上界和全下界的格稱為有界格。記作.9/3/202254第54頁，共61頁，2022年，5月20日，9點2分，星期一DEFINITION 11. 設(shè)是有界格，aL，若存在bL，使得ab=0, ab=1，則稱b為a的補元。 若格中每個元素都至少有一個補元，則稱這個格為有補格。對分配格L來說，若aL有補元，