離散數(shù)學(xué) 第1講 代數(shù)

1離散數(shù)學(xué)（二）數(shù)學(xué)是科學(xué)之王?！咚箶?shù)學(xué)支配著宇宙?！呥_哥拉斯自然界的書是用數(shù)學(xué)的語言寫成的。——伽利略數(shù)學(xué)是一切知識中的最高形式?！乩瓐D數(shù)學(xué)是打開科學(xué)大門的鑰匙?！喔婚T科學(xué)，只有當它成功地運用數(shù)學(xué)時，才能達到真正完善的地步?！R克思一個國家只有數(shù)學(xué)蓬勃的發(fā)展，才能展現(xiàn)它國力的強大。數(shù)學(xué)的發(fā)展和至善和國家繁榮昌盛密切相關(guān)?！闷苼鰯?shù)學(xué)研究離散量的結(jié)構(gòu)及其相互關(guān)系的數(shù)學(xué)學(xué)科，是現(xiàn)代數(shù)學(xué)的一個重要分支在計算機科學(xué)與技術(shù)領(lǐng)域有著廣泛的應(yīng)用，是計算機必不可少的先行課程、核心課程數(shù)字電子計算機是一個離散結(jié)構(gòu)，它只能處理離散化的數(shù)量關(guān)系。因此，無論計算機科學(xué)本身，還是與計算機科學(xué)密切相關(guān)的現(xiàn)代科學(xué)研究領(lǐng)域，都面臨著如何對離散結(jié)構(gòu)建立相應(yīng)的數(shù)學(xué)模型；又如何將已用連續(xù)數(shù)量關(guān)系建立起來的數(shù)學(xué)模型離散化，從而可由計算機加以處理。離散數(shù)學(xué)教材：

方世昌編著

西安電子科技大學(xué)出版社

2009.81.《離散數(shù)學(xué)》左孝凌、李為鑑、劉永才編著上?？萍嘉墨I出版社參考書2.《離散數(shù)學(xué)》--理論?分析?題解，左孝凌等著上?？萍嘉墨I出版社3.《離散數(shù)學(xué)習(xí)題集》數(shù)理邏輯與集合論分冊耿素云北京大學(xué)出版社離散數(shù)學(xué)課程的學(xué)習(xí)特點及方法特點:強調(diào)：邏輯性、抽象性；注重：概念、方法與應(yīng)用方法:1．該課程概念名詞多，定義多，公式多，要求記憶準確。2．認真/仔細做好課堂筆記。3．完成大量習(xí)題。離散數(shù)學(xué)課程的學(xué)習(xí)目標培養(yǎng)抽象推理、邏輯思維和歸納構(gòu)造等能力，提高利用數(shù)學(xué)方法解決問題的技能，為進一步學(xué)習(xí)奠定計算機數(shù)學(xué)的基礎(chǔ)。通過離散數(shù)學(xué)的學(xué)習(xí)，不但可以掌握處理離散結(jié)構(gòu)的描述工具和方法，為后續(xù)課程的學(xué)習(xí)創(chuàng)造條件，而且可以提高抽象思維和嚴格的邏輯推理能力，為將來參與創(chuàng)新性的研究和開發(fā)工作打下堅實的基礎(chǔ)。離散數(shù)學(xué)(二)四、代數(shù)系統(tǒng)離散數(shù)學(xué)教學(xué)內(nèi)容

一、數(shù)理邏輯

集合

二、關(guān)系

函數(shù)

三、圖論

離散數(shù)學(xué)(一)考核方式總成績構(gòu)成:平時成績占15%期末成績占85%平時成績構(gòu)成:課堂練習(xí)+課后作業(yè)+考勤第六章代數(shù)代數(shù)系統(tǒng):

集合和定義在集合上的若干運算所組成的系統(tǒng)。用抽象方法研究各種代數(shù)系統(tǒng)性質(zhì)的理論學(xué)科叫“近世代數(shù)”或“抽象代數(shù)”?！俺橄蠓椒ā笔侵?1)不關(guān)注組成代數(shù)系統(tǒng)的具體集合是什么，也不關(guān)注集合上的運算如何定義(2)研究抽象的數(shù)學(xué)結(jié)構(gòu)，研究抽象數(shù)學(xué)結(jié)構(gòu)的一般性質(zhì)線性代數(shù)：<Mn(R)，+，?>命題代數(shù)：<X，﹁，∧，∨>集合代數(shù)：<ρ(A)，∩，∪，—>計算機安全，網(wǎng)絡(luò)安全，密碼學(xué)的基礎(chǔ)程序設(shè)計學(xué)中的形式語義學(xué)基礎(chǔ)刻畫抽象數(shù)據(jù)結(jié)構(gòu)關(guān)系數(shù)據(jù)庫理論研究可計算性與計算復(fù)雜性差錯控制編碼理論都需要代數(shù)知識特別地，半群在形式語言和自動機理論中有著重要的應(yīng)用，有限域理論是差錯控制編碼理論的數(shù)學(xué)基礎(chǔ)，在通訊中發(fā)揮了重要作用。而電子線路設(shè)計、電子計算機硬件設(shè)計和通訊系統(tǒng)設(shè)計更是離不開布爾代數(shù)。第六章代數(shù)代數(shù)的概念和方法是研究計算機科學(xué)和工程的重要數(shù)學(xué)工具。眾所周知，在各種數(shù)學(xué)問題及許多實際問題的研究中都離不開數(shù)學(xué)模型，要構(gòu)造一個現(xiàn)象或過程的數(shù)學(xué)模型，就需要某種數(shù)學(xué)結(jié)構(gòu)，而代數(shù)結(jié)構(gòu)就是最常用的數(shù)學(xué)結(jié)構(gòu)之一。因此，我們有必要掌握代數(shù)系統(tǒng)的重要概念和基本方法。第六章代數(shù)第一講代數(shù)結(jié)構(gòu)代數(shù)的構(gòu)成與分類11子代數(shù)2主要內(nèi)容:代數(shù)定義，么元和零元重點:

幺元、零元和逆元難點:重點和難點:幺元、零元和逆元3一、代數(shù)的構(gòu)成與分類代數(shù)的構(gòu)成:

運算的定義：函數(shù)f:Sm→S稱為集合S上的m元運算，m∈N叫運算的元數(shù)(或階)。

m=1,一元運算，S→S,R→R,f(x)=|x|+1；m=2,二元運算，S2→S,R2→R,f(<x,y>)=x+y；一般地，n元運算，Sn→S。

代數(shù)系統(tǒng)的定義：1.一個非空集合A(代數(shù)的載體)；2.定義的若干在A上封閉的運算f1,f2,…,fm；3.代數(shù)常數(shù)。代數(shù)系統(tǒng)常用一個n重組<A，，，…，>來表示,其中A稱為代數(shù)結(jié)構(gòu)的載體，，，…為各種運算。有時為了強調(diào)S有某些元素地位特殊,也可將它們列入n重組的末尾，即<A，，，…，k1，…，km>。代數(shù)的分類:1.要有相同的構(gòu)成成分

2.服從一組相同的稱為公理的性質(zhì)

運算的個數(shù)相同常數(shù)的個數(shù)相同對應(yīng)運算元數(shù)(階)相同例:考慮具有<I,+,·,-,0,1>形式構(gòu)成成分和下述公理的代數(shù)類(這里“-”是一元運算)。

(1)a+b=b+a

(2)a·b=b·a

(3)(a+b)+c=a+(b+c)

(4)(a·b)·c=a·(b·c)

(5)a·(b+c)=a·b+a·c

(6)a+(-a)=0

(7)a+0=a

(8)a·1=a那么<Q,+,·,-,0,1>和<R,+,·,-,0,1>是同類代數(shù),但<ρ(S),∪,∩,ˉ,?,S>是不同類的,因為公理(6)對這個代數(shù)不成立

(這里“-”表示集合的絕對補)。二、子代數(shù)封閉性定義：設(shè)?與?是S上的二元與一元運算,S′?S，若對任意a,b∈S′，蘊含著a?b∈S′，稱S′關(guān)于運算?是封閉的；若對任意a∈S′，蘊含著?a∈S′，稱S′關(guān)于運算?是封閉的。子代數(shù)的定義：設(shè)A=<S,?,△,k>是一代數(shù),如果

(1)S′?S

(2)S′對S上的運算?和△封閉

(3)k∈S′那么A′=<S′,?,△,k>是A的子代數(shù)。

例如：(1)<I,+,0>是<R,+，0>的子代數(shù)；

(2)<{0,2},+4,0>是<{0,1,2,3},+4,0>的一個子代數(shù)。三、幺元、零元么元定義：設(shè)*是S上的二元運算,(1)若存在el∈S，對所有x∈S，都有el*

x=x，則稱el是關(guān)于運算*的左么元(LeftIdentityElement)，或稱左單位元(LeftUnitElement)。(2)若存在元素er∈S，對所有x∈S，都有x*

er=x，則稱er是關(guān)于運算*的右么元(RightIdentityElement)，或稱右單位元(RightUnitElement)。(3)若存在e∈S，它既是左么元也是右么元，則稱e是關(guān)于運算*的一個么元(IdentityElement)，或稱單位元(UnitElement)，即對所有x∈S，都有x*

e

=e

*

x=x，則e是關(guān)于運算*的么元。三、幺元、零元么元示例：例2代數(shù)A=<{a,b,c},*>如下表所示：

可以看出，代數(shù)A左么元為b，沒有右么元。例3<R,×>中么元為1；<R,+>中么元為0。

三、幺元、零元零元定義：設(shè)*是S上的二元運算,

(1)若存在θl∈S，對所有x∈S，都有θl*x=θl，則稱θl是為關(guān)于運算*的左零元(LeftZeroElement)。

(2)若存在θr∈S，對所有x∈S，都有x*θr=θr，則稱θr是關(guān)于運算*的右零元(RightZeroElement)。(3)若存在θ∈S，它既是左零元也是右零元，則稱θ是關(guān)于運算*的零元，即對任意x∈S，都有θ*x=x*θ=θ，則θ是關(guān)于運算*的零元(ZeroElement)。在例2中代數(shù)A=<{a,b,c},*>的右零元為a,b；沒有左零元。三、幺元、零元例4：(1)<I,×>么元：1,零元：0；

(2)S非空有限集，代數(shù)<ρ(S),∪,∩,ˉ,?

,S>

么元零元對∪：?S

對∩：S?例2的代數(shù)中：

右零元：a,b；左零元：無；右么元：無；左么元：b可以看出：左(右)零元不一定存在；左(右)零元存在時也不一定唯一；左零元與右零元可能同時存在。三、幺元、零元定理1：設(shè)*是定義在集合A上的二元運算，且A中關(guān)于運算*的左么元為el，右么元為er，則el=er=e，且A中的么元是唯一的。證明：因為el和er分別為左么元和右么元，所以el=el*er=er=e。設(shè)另有一么元e′,則e′=e′*e=e，所以么元唯一。定理2：設(shè)*是定義在集合A上的二元運算，且A中關(guān)于運算*的左零元為θl，右零元為θr，則θl=θr=θ，且A中的零元是唯一的。定理3：設(shè)<A,*>是一個代數(shù)系統(tǒng),且集合A中元素的個數(shù)大于1.如果該代數(shù)系統(tǒng)中存在么元e和零元θ,則θ≠e。證明：用反證法，假如么元e

=零元，那么對于任意xA,必有x=e*x=θ*x=θ=e。于是，A中所有元素都是相同的，這與A中含有多個元素相矛盾。四、逆元逆元定義：設(shè)*是A上的二元運算,e是A中關(guān)于*的么元，

(1)若對元素a∈A，存在b∈A，使b*a=e，則稱b是a的左逆元；

(2)若對元素a∈A，存在b∈A，使a*b=e，則稱b是a的右逆元；

(3)若對元素a∈A，存在b∈A，使a*b=b*a=e，則稱b是a的逆元，記為a-1。

例如<I,+>中么元為0，x的逆元為-x。

一般來說，一個元素的左逆元不一定等于該元素的右逆元；一個元素可以有左逆元而無右逆元，甚至一個元素的左（右）逆元還可以不唯一。四、逆元例6(1)：<N,+>么元為0，僅0有逆元;

<R,·>么元為1,僅零元0無逆元,其它元素x均有逆元。例6(2)：設(shè)Nk是前k個自然數(shù)的集,這里k＞0,Nk={0,1,2,…,k-1}，定義模k加法+k如下:對每一x、y∈Nk，

么元為0；Nk的每一元素有逆元，0的逆元是0，每一非0元素x的逆元是k-x。例6(3)：設(shè)Nk是前k個自然數(shù)的集,這里k≥2,定義模k乘法×k如下:x×ky=z，這里z∈Nk,且對某一n,xy-z=nk,即

1是么元，元素x∈Nk在Nk中有逆元僅當x和k互質(zhì)。四、逆元1是么元，逆元是它本身0,2無逆元，3的逆元為30無逆元，1的逆元為1，2的逆元為3，3的逆元為2，4的逆元為4四、逆元定理4：對于可結(jié)合運算,如果一個元素x有左逆元l和右逆元r,那么l=r=x－1(即逆元是唯一的)。證明

:設(shè)e對運算*是么元,于是l*x=x*r=e根據(jù)運算*的可結(jié)合性,得到l=l*e=l*(x*r)=(l*x)*r=e*r=r

設(shè)x有兩個逆元a,b,那么a=a*e=a*(x*b)=(a*x)*b=e*b=b

所以逆元是唯一的。

可約性定義：設(shè)*是S上的二元運算,a∈S,如果對于每一x、y∈S有(a*x=a*y)∨(x*a=y*a)(x=y)，則稱a是可約的或可消去的。四、逆元定理5：若代數(shù)<S,>中運算滿足結(jié)合律,且a∈S有逆元,那么a必定是可約的。證明

:設(shè)a的逆元為a-1，對?x、y∈S，

(1)當ax=ay時可得a-1(ax)=a-1(ay)，即(a-1a)x=(a-1a)y，可推得x=y。

(2)當xa=ya時可得(xa)a-1=(ya)a-1,即x(aa-1)=y(aa-1),也可推得x=y。因此，a是可約的。

Note：上述定理的逆不成立。例如<I,·>中，?a∈I且a≠0,a是可約的,但除了1外其他元素都不存在逆元。五、代數(shù)系統(tǒng)：例題

例:在整數(shù)集合I上，定義二元運算。為a*b＝a＋b－2

請回答：

(1)集合I和運算*是否構(gòu)成代數(shù)系統(tǒng)?(2)運算*在I上可交換嗎？

(3)運算*在I上可結(jié)合嗎？

(4)運算*在I上有無單位元？

(5)對運算*是否所有的元素都有逆元？若有，逆元是什么？五、代數(shù)系統(tǒng)：例題

解答:

(1)集合I和運算*是否構(gòu)成代數(shù)系統(tǒng)?

任取a，b∈I，則a＋b－2∈I，即a*b∈I，所以*在I上封閉，即集合I和運算*構(gòu)成代數(shù)系統(tǒng)。

(2)運算