1、1,離散數(shù)學(xué)（二）,數(shù)學(xué)是科學(xué)之王。 高斯 數(shù)學(xué)支配著宇宙。畢達(dá)哥拉斯 自然界的書是用數(shù)學(xué)的語言寫成的。伽利略 數(shù)學(xué)是一切知識中的最高形式。柏拉圖 數(shù)學(xué)是打開科學(xué)大門的鑰匙。 培根 一門科學(xué)，只有當(dāng)它成功地運(yùn)用數(shù)學(xué)時，才能達(dá)到真正完善的地步。馬克思 一個國家只有數(shù)學(xué)蓬勃的發(fā)展，才能展現(xiàn)它國力的強(qiáng)大。數(shù)學(xué)的發(fā)展和至善和國家繁榮昌盛密切相關(guān)。拿破侖,數(shù)學(xué),研究離散量的結(jié)構(gòu)及其相互關(guān)系的數(shù)學(xué)學(xué)科，是現(xiàn)代數(shù)學(xué)的一個重要分支 在計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域有著廣泛的應(yīng)用，是計(jì)算機(jī)必不可少的先行課程、核心課程 數(shù)字電子計(jì)算機(jī)是一個離散結(jié)構(gòu)，它只能處理離散化的數(shù)量關(guān)系。因此，無論計(jì)算機(jī)科學(xué)本身，還是與計(jì)算機(jī)科學(xué)密切

2、相關(guān)的現(xiàn)代科學(xué)研究領(lǐng)域，都面臨著如何對離散結(jié)構(gòu)建立相應(yīng)的數(shù)學(xué)模型；又如何將已用連續(xù)數(shù)量關(guān)系建立起來的數(shù)學(xué)模型離散化，從而可由計(jì)算機(jī)加以處理。,離散數(shù)學(xué),教材：方世昌編著 西安電子科技大學(xué)出版社2009.8,1.離散數(shù)學(xué)左孝凌、李為鑑、劉永才編著 上?？萍嘉墨I(xiàn)出版社,參考書,2. 離散數(shù)學(xué)-理論分析題解，左孝凌等著 上海科技文獻(xiàn)出版社,3.離散數(shù)學(xué)習(xí)題集 數(shù)理邏輯與集合論分冊 耿素云 北京大學(xué)出版社,離散數(shù)學(xué)課程的學(xué)習(xí)特點(diǎn)及方法,特點(diǎn): 強(qiáng)調(diào)：邏輯性、抽象性； 注重：概念、方法與應(yīng)用 方法: 1該課程概念名詞多，定義多，公式多，要求記憶準(zhǔn)確。 2認(rèn)真/仔細(xì)做好課堂筆記。 3完成大量習(xí)題。,離散數(shù)

3、學(xué)課程的學(xué)習(xí)目標(biāo),培養(yǎng)抽象推理、邏輯思維和歸納構(gòu)造等能力，提高利用數(shù)學(xué)方法解決問題的技能，為進(jìn)一步學(xué)習(xí)奠定計(jì)算機(jī)數(shù)學(xué)的基礎(chǔ)。 通過離散數(shù)學(xué)的學(xué)習(xí)，不但可以掌握處理離散結(jié)構(gòu)的描述工具和方法，為后續(xù)課程的學(xué)習(xí)創(chuàng)造條件，而且可以提高抽象思維和嚴(yán)格的邏輯推理能力，為將來參與創(chuàng)新性的研究和開發(fā)工作打下堅(jiān)實(shí)的基礎(chǔ)。,離散數(shù)學(xué)教學(xué)內(nèi)容,考核方式,總成績構(gòu)成: 平時成績占15% 期末成績占85% 平時成績構(gòu)成: 課堂練習(xí)+課后作業(yè)+考勤,第六章 代數(shù),代數(shù)系統(tǒng): 集合和定義在集合上的若干運(yùn)算所組成的系統(tǒng)。用抽象方法研 究各種代數(shù)系統(tǒng)性質(zhì)的理論學(xué)科叫“近世代數(shù)”或“抽象代數(shù)”。 “抽象方法”是指 (1)不關(guān)注組

4、成代數(shù)系統(tǒng)的具體集合是什么，也不關(guān)注集合上的運(yùn)算如何定義 (2)研究抽象的數(shù)學(xué)結(jié)構(gòu)，研究抽象數(shù)學(xué)結(jié)構(gòu)的一般性質(zhì) 線性代數(shù)： 命題代數(shù)： 集合代數(shù)：,特別地，半群在形式語言和自動機(jī)理論中有著重要的應(yīng)用，有限域理論是差錯控制編碼理論的數(shù)學(xué)基礎(chǔ)，在通訊中發(fā)揮了重要作用。而電子線路設(shè)計(jì)、電子計(jì)算機(jī)硬件設(shè)計(jì)和通訊系統(tǒng)設(shè)計(jì)更是離不開布爾代數(shù)。,第六章 代數(shù),代數(shù)的概念和方法是研究計(jì)算機(jī)科學(xué)和工程的重要數(shù)學(xué)工具。 眾所周知，在各種數(shù)學(xué)問題及許多實(shí)際問題的研究中都離不開數(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)的重要概念和基本

5、方法。,第六章 代數(shù),第一講 代數(shù)結(jié)構(gòu),主要內(nèi)容:,重點(diǎn)和難點(diǎn):,一、代數(shù)的構(gòu)成與分類,代數(shù)的構(gòu)成: 運(yùn)算的定義：函數(shù) f: SmS稱為集合S上的m元運(yùn)算，mN叫 運(yùn)算的元數(shù)(或階)。 m=1, 一元運(yùn)算，SS, RR, f(x)=|x|+1； m=2, 二元運(yùn)算，S2S, R2R,f()=x+y； 一般地，n元運(yùn)算，SnS。 代數(shù)系統(tǒng)的定義：1. 一個非空集合A(代數(shù)的載體)；2. 定義 的若干在A上封閉的運(yùn)算f1,f2,fm；3.代數(shù)常數(shù)。 代數(shù)系統(tǒng)常用一個n重組來表示, 其中A稱為 代數(shù)結(jié)構(gòu)的載體，為各種運(yùn)算。有時為了強(qiáng)調(diào)S有某些元 素地位特殊,也可將它們列入n重組的末尾，即。,代數(shù)的分

6、類: 1. 要有相同的構(gòu)成成分 2. 服從一組相同的稱為公理的性質(zhì),例: 考慮具有形式構(gòu)成成分和下述公理的代數(shù)類(這里“-”是一元運(yùn)算)。 (1) a+b=b+a (2) ab=ba (3) (a+b)+c=a+(b+c) (4) (ab)c=a(bc) (5) a(b+c)=ab+ac (6) a+(-a)=0 (7) a+0=a (8) a1=a 那么 和是同類代數(shù), 但是不同類的, 因?yàn)楣?6)對這個代數(shù)不成立 (這里“-” 表示集合的絕對補(bǔ))。,二、子代數(shù),封閉性定義： 設(shè)與是S上的二元與一元運(yùn)算, S S， 若對任意a,bS，蘊(yùn)含著abS，稱S關(guān)于運(yùn)算是封閉的； 若對任意aS，蘊(yùn)含

7、著aS，稱S關(guān)于運(yùn)算是封閉的 。,子代數(shù)的定義： 設(shè)A=是一代數(shù), 如果 (1) S S (2) S對S上的運(yùn)算和封閉 (3) kS 那么A= 是A的子代數(shù)。 例如：(1) 是的子代數(shù)； (2) 是的一個子代數(shù)。,三、幺元、零元,么元定義： 設(shè)*是S上的二元運(yùn)算, (1)若存在elS，對所有xS，都有el * x =x，則稱el是關(guān)于運(yùn)算*的左么元(Left Identity Element)，或稱左單位元(Left Unit Element)。 (2)若存在元素erS，對所有xS，都有x* er =x，則稱er是關(guān)于運(yùn)算*的右么元(Right Identity Element)，或稱右單位元

8、(Right Unit Element)。 (3)若存在eS，它既是左么元也是右么元，則稱e是關(guān)于運(yùn)算*的一個么元(Identity Element)，或稱單位元(Unit Element)，即對所有xS，都有x* e =e * x= x，則e是關(guān)于運(yùn)算*的么元。,三、幺元、零元,么元示例： 例2 代數(shù)A=如下表所示： 可以看出，代數(shù)A左么元為b，沒有右么元。 例3 中么元為1；中么元為0。,三、幺元、零元,零元定義： 設(shè)*是S上的二元運(yùn)算, (1)若存在lS，對所有xS，都有l(wèi) * x=l，則稱l是為關(guān)于運(yùn)算*的左零元(Left Zero Element)。 (2)若存在rS，對所有xS，都

9、有x*r=r，則稱r是關(guān)于運(yùn)算*的右零元(Right Zero Element)。 (3)若存在S，它既是左零元也是右零元，則稱是關(guān)于運(yùn)算*的零元，即對任意xS，都有*x=x*=，則是關(guān)于運(yùn)算*的零元(Zero Element)。,在例2中代數(shù)A=的右零元為a, b；沒有左零元。,三、幺元、零元,例4：(1) 么元：1, 零元：0； (2) S非空有限集，代數(shù) 么元 零元 對： S 對：S ,例2的代數(shù)中： 右零元：a, b；左零元：無；右么元：無；左么元：b,可以看出： 左(右)零元不一定存在； 左(右)零元存在時也不一定唯一； 左零元與右零元可能同時存在。,三、幺元、零元,定理1：設(shè)*是定

10、義在集合A上的二元運(yùn)算，且A中關(guān)于運(yùn)算*的左么元為el，右么元為er，則el = er=e，且A中的么元是唯一的。 證明：因?yàn)閑l和er分別為左么元和右么元，所以el = el *er=er=e。設(shè)另有一么元e,則e=e*e=e，所以么元唯一。 定理2：設(shè)*是定義在集合A上的二元運(yùn)算，且A中關(guān)于運(yùn)算*的左零元為l，右零元為r，則l=r=，且A中的零元是唯一的。 定理3：設(shè)是一個代數(shù)系統(tǒng),且集合A中元素的個數(shù)大于1.如果該代數(shù)系統(tǒng)中存在么元e和零元,則e。 證明：用反證法，假如么元e =零元，那么對于任意xA,必有x=e*x=*x=e。于是，A中所有元素都是相同的，這與A中含有多個元素相矛盾。,

11、四、逆元,逆元定義： 設(shè)*是A上的二元運(yùn)算,e是A中關(guān)于*的么元， (1) 若對元素aA，存在bA，使b*a=e，則稱b是a的左逆元； (2) 若對元素aA，存在bA，使a*b=e，則稱b是a的右逆元； (3)若對元素aA，存在bA，使a*b=b*a=e，則稱b是a的逆元，記為a-1。,例如中么元為0，x 的逆元為-x。 一般來說，一個元素的左逆元不一定等于該元素的右逆元； 一個元素可以有左逆元而無右逆元，甚至一個元素的左（右）逆 元還可以不唯一。,四、逆元,例6(1)：么元為0，僅0有逆元; 么元為1,僅零元0無逆元,其它元素x均有逆元。 例6(2)：設(shè)Nk是前k個自然數(shù)的集, 這里k0,

12、Nk =0, 1, 2, ,k-1，定義模k加法+k如下: 對每一x、yNk， 么元為0； Nk的每一元素有逆元，0的逆元是0，每一非0元素x的逆元是k-x。 例6(3)：設(shè)Nk是前k個自然數(shù)的集, 這里k2, 定義模k乘法k如下:x k y = z，這里zNk,且對某一n, xy-z=nk,即 1是么元，元素xNk在Nk中有逆元僅當(dāng)x和k互質(zhì)。,四、逆元,1是么元，逆元是它本身 0,2無逆元，3的逆元為3,0無逆元， 1的逆元為1， 2的逆元為3， 3的逆元為2， 4的逆元為4,四、逆元,定理4：對于可結(jié)合運(yùn)算, 如果一個元素x有左逆元l和右 逆元r,那么l=r=x1(即逆元是唯一的)。 證

13、明 : 設(shè)e對運(yùn)算*是么元, 于是l * x = x * r = e 根據(jù)運(yùn)算*的可結(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上的二元運(yùn)算, aS, 如果對于每一x、yS有(a * x=a * y)(x * a=y * a) (x=y)，則稱a是可約的或可消去的。,四、逆元,定理5：若代數(shù)中 運(yùn)算滿足結(jié)合律,且aS有逆元,那么a必定是可約的。 證明

14、 :設(shè)a的逆元為a-1，對x、yS， (1)當(dāng)ax = ay時可得a-1 (ax) = a-1 (ay)， 即 (a-1 a)x = (a-1 a)y，可推得x = y。 (2)當(dāng)xa = ya時可得(xa) a-1 = (ya) a-1 , 即x(a a-1) = y(a a-1) ,也可推得x = y。 因此，a是可約的。 Note：上述定理的逆不成立。例如中，aI且a0, a是可約的,但除了1外其他元素都不存在逆元。,五、代數(shù)系統(tǒng)：例題,例: 在整數(shù)集合I上， 定義二元運(yùn)算。為 a*bab2 請回答： (1) 集合I和運(yùn)算*是否構(gòu)成代數(shù)系統(tǒng)? (2) 運(yùn)算*在I上可交換嗎？ (3) 運(yùn)算*在I上可結(jié)合嗎？ (4) 運(yùn)算*在I上有無單位元？ (5)對運(yùn)算*是否所有的元素都有逆元？若有，逆元是什么？,五、代數(shù)系統(tǒng)：例題,解答: (1) 集合I和運(yùn)算*是否構(gòu)成代數(shù)系統(tǒng)? 任取a，bI，則ab2I，即a * bI，所以*在I上封閉，即集合I和運(yùn)算*構(gòu)成代數(shù)系統(tǒng)。 (2) 運(yùn)算*在I上可交換嗎？ 因?yàn)閍*bab2ba2b*a，所以 *在I上可交換。 (3) 運(yùn)算。在I上可結(jié)合嗎？ 任取a，b，c I ， 因?yàn)?(a*b)*c(ab2)*c(ab2)c2abc4 a*(b*c)a*(bc2)a(bc2)2abc4 所以(a * b) * ca *(b * c)，故*在I上可結(jié)合。,