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

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

2、只能處理離散化的數(shù)量關系。因此，無論計算機科學本身，還是與計算機科學密切相關的現(xiàn)代科學研究領域，都面臨著如何對離散結構建立相應的數(shù)學模型；又如何將已用連續(xù)數(shù)量關系建立起來的數(shù)學模型離散化，從而可由計算機加以處理。 離散數(shù)學離散數(shù)學教材：教材：方世昌編著方世昌編著 西安電子科技大學出版社西安電子科技大學出版社2009.82009.81. 1.離散數(shù)學離散數(shù)學左孝凌、左孝凌、李為鑑、劉永才編著李為鑑、劉永才編著上?？萍嘉墨I出版社上?？萍嘉墨I出版社參考書參考書2. 2. 離散數(shù)學離散數(shù)學- -理論理論 分析分析 題解，左孝凌等著題解，左孝凌等著上?？萍嘉墨I出版社上?？萍嘉墨I出版社3. 3.離散數(shù)學習

3、題集離散數(shù)學習題集數(shù)理邏輯與集合論分冊數(shù)理邏輯與集合論分冊 耿素云耿素云北京大學出版社北京大學出版社離散數(shù)學課程的學習特點及方法離散數(shù)學課程的學習特點及方法特點特點: :強調(diào)：邏輯性、抽象性； 注重：概念、方法與應用 方法方法: :1該課程概念名詞多，定義多，公式多，要求記憶準確。 2認真/仔細做好課堂筆記。 3完成大量習題。 離散數(shù)學課程的學習目標離散數(shù)學課程的學習目標l 培養(yǎng)抽象推理、邏輯思維和歸納構造等能力，提高利用數(shù)學方法解決問題的技能，為進一步學習奠定計算機數(shù)學的基礎。l 通過離散數(shù)學的學習，不但可以掌握處理離散結構的描述工具和方法，為后續(xù)課程的學習創(chuàng)造條件，而且可以提高抽象思維和嚴

4、格的邏輯推理能力，為將來參與創(chuàng)新性的研究和開發(fā)工作打下堅實的基礎。離散數(shù)學(二) 四、代數(shù)系統(tǒng)離散數(shù)學教學內(nèi)容離散數(shù)學教學內(nèi)容 一、數(shù)理邏輯 集合 二、關系 函數(shù) 三、圖論 離散數(shù)學(一)考核方式考核方式總成績構成總成績構成: :平時成績占15% 期末成績占85% 平時成績構成平時成績構成: :課堂練習+課后作業(yè)+考勤第六章第六章 代數(shù)代數(shù)代數(shù)系統(tǒng)代數(shù)系統(tǒng): : 集合和定義在集合上的若干運算所組成的系統(tǒng)。用抽象方法研究各種代數(shù)系統(tǒng)性質(zhì)的理論學科叫“近世代數(shù)”或“抽象代數(shù)”。 “抽象方法抽象方法”是指 (1)不關注組成代數(shù)系統(tǒng)的具體集合不關注組成代數(shù)系統(tǒng)的具體集合是什么，也不關注集合上不關注集合

5、上的運算如何定義的運算如何定義 (2)研究抽象的數(shù)學結構抽象的數(shù)學結構，研究抽象數(shù)學結構的一般性質(zhì)一般性質(zhì)線性代數(shù)線性代數(shù)：命題代數(shù)命題代數(shù)：集合代數(shù)集合代數(shù)：計算機安全，網(wǎng)絡安全，密碼學的基礎程序設計學中的形式語義學基礎刻畫抽象數(shù)據(jù)結構關系數(shù)據(jù)庫理論研究可計算性與計算復雜性差錯控制編碼理論都需要代數(shù)知識 特別地，半群半群在形式語言和自動機理論中有著重要的應用，有限域有限域理論是差錯控制編碼理論的數(shù)學基礎，在通訊中發(fā)揮了重要作用。而電子線路設計、電子計算機硬件設計和通訊系統(tǒng)設計更是離不開布爾代數(shù)布爾代數(shù)。第六章第六章 代數(shù)代數(shù) 代數(shù)的概念和方法是研究計算機科學和工程的重要數(shù)學工具。 眾所周知，

6、在各種數(shù)學問題及許多實際問題的研究中都離不開數(shù)學模型，要構造一個現(xiàn)象或過程的數(shù)學模型，就需要某種數(shù)學結構，而代數(shù)結構就是最常用的數(shù)學結構之一。因此，我們有必要掌握代數(shù)系統(tǒng)代數(shù)系統(tǒng)的重要概念和基本方法。第六章第六章 代數(shù)代數(shù)第一講第一講 代數(shù)結構代數(shù)結構代數(shù)的構成與分類代數(shù)的構成與分類1 11 1子代數(shù)子代數(shù)2 2主要內(nèi)容主要內(nèi)容: :代數(shù)定義，么元和零元代數(shù)定義，么元和零元重點重點: : 幺元、零元和逆元幺元、零元和逆元難點難點: :重點和難點重點和難點: :幺元、零元和逆元幺元、零元和逆元3 3一、代數(shù)的構成與分類一、代數(shù)的構成與分類代數(shù)的構成代數(shù)的構成: : 運算的定義運算的定義：函數(shù) f

7、: SmS稱為集合S上的m元運算，mN叫運算的元數(shù)(或階)。 m=1, 一元運算，SS, RR, f(x)=|x|+1； m=2, 二元運算，S2S, R2R,f()=x+y； 一般地，n元運算，SnS。 代數(shù)系統(tǒng)的定義代數(shù)系統(tǒng)的定義：1. 一個非空集合A(代數(shù)的載體)；2. 定義的若干在A上封閉的運算f1,f2,fm；3.代數(shù)常數(shù)。 代數(shù)系統(tǒng)常用一個常用一個n重組重組來表示來表示, 其中A稱為代數(shù)結構的載體，為各種運算。有時為了強調(diào)。有時為了強調(diào)S有某些元有某些元素地位特殊素地位特殊,也可將它們列入也可將它們列入n重組重組的末尾，即的末尾，即。代數(shù)的分類代數(shù)的分類: :1. 要有相同的構成成

8、分 2. 服從一組相同的稱為公理的性質(zhì) 運算的個數(shù)相同常數(shù)的個數(shù)相同對應運算元數(shù)( 階)相同 例: 考慮具有形式構成成分和下述公理的代數(shù)類(這里“-”是一元運算)。 (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ù), 但但是不同類的是不同類的, 因為公理因為公理(6)對這個代數(shù)不成立對這個代數(shù)不成立 (這里“-” 表示集合的絕對補)。二、子代數(shù)二、子代數(shù)封閉性定義：封閉性定義： 設與是S上的二元與一元運算, S

9、S， 若對任意a,bS，蘊含著abS，稱S關于運算是封閉的； 若對任意aS，蘊含著aS，稱S關于運算是封閉的 。子代數(shù)的定義：子代數(shù)的定義： 設A=是一代數(shù), 如果 (1) S S (2) S對S上的運算和封閉 (3) kS那么A= 是A的子代數(shù)子代數(shù)。 例如：例如：(1) 是是的子代數(shù)；的子代數(shù)； (2) 是是的一個子代數(shù)。的一個子代數(shù)。三、幺元、零元三、幺元、零元么元么元定義：定義：設*是S上的二元運算, (1)若存在elS，對所有xS，都有el * x =x，則稱el是關于運是關于運算算*的左么元的左么元(Left Identity Element)，或稱左單位元左單位元(Left Un

10、it Element)。 (2)若存在元素erS，對所有xS，都有x* er =x，則稱er是關是關于運算于運算*的右么元的右么元(Right Identity Element)，或稱右單位元右單位元(Right Unit Element)。 (3)若存在eS，它既是左么元也是右么元，則稱e是關于運是關于運算算*的一個么元的一個么元(Identity Element)，或稱單位元單位元(Unit Element)，即對所有xS，都有x* e =e * x= x，則e是關于運算*的么元。三、幺元、零元三、幺元、零元么元么元示例：示例：例2 代數(shù)A=如下表所示： 可以看出，代數(shù)A左么元為b，沒有右

11、么元。例3 中么元為1；中么元為0。 三、幺元、零元三、幺元、零元零元零元定義：定義：設*是S上的二元運算, (1)若存在lS，對所有xS，都有l(wèi) * x=l，則稱l是為關于是為關于運算運算*的左零元的左零元(Left Zero Element)。 (2)若存在rS，對所有xS，都有x*r=r，則稱r是關于運是關于運算算*的右零元的右零元(Right Zero Element)。 (3)若存在S，它既是左零元也是右零元，則稱是關于運算*的零元，即對任意xS，都有*x=x*=，則是關于運算是關于運算*的零元的零元(Zero Element)。在在例例2中代數(shù)中代數(shù)A=的右零元為的右零元為a, b

12、；沒有左零元。；沒有左零元。三、幺元、零元三、幺元、零元例例4：(1) 么元：1, 零元：0； (2) S非空有限集，代數(shù) 么元 零元 對： S 對：S 例例2的代數(shù)中：的代數(shù)中： 右零元：右零元：a, b；左零元：無；右么元：無；左么元：；左零元：無；右么元：無；左么元：b可以看出：可以看出： 左左( (右右) )零元零元不一定存在；不一定存在； 左左( (右右) )零元零元存在時也不一定唯一；存在時也不一定唯一； 左零元與右零元可能左零元與右零元可能同時存在。同時存在。三、幺元、零元三、幺元、零元 定理定理1：設*是定義在集合A上的二元運算，且A中關于運算*的左么元為el，右么元為er，則

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

14、上的二元運算,e是A中關于*的么元， (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)：設Nk是前k個自然數(shù)的集, 這里k0, Nk =

15、0, 1, 2, ,k-1，定義模k加法+k如下: 對每一x、yNk， 么元為么元為0； Nk的每一元素有逆元，的每一元素有逆元，0的逆元是的逆元是0，每一非，每一非0元素元素x的逆的逆元是元是k-x。例例6(3)：設Nk是前k個自然數(shù)的集, 這里k2, 定義模k乘法k如下:x k y = z，這里zNk,且對某一n, xy-z=nk,即 1是么元，元素是么元，元素xNk在在Nk中有逆元僅當中有逆元僅當x和和k互質(zhì)?；ベ|(zhì)。ky xk,yxky x,y x)mod(yxkyx)mod(yxkxyky xk,yxky x,y x)mod(yxkyx四、逆元四、逆元12340424130331420

16、243210100000043210512303202023210100000321041是么元，逆元是它本身是么元，逆元是它本身0,2無逆元，無逆元，3的逆元為的逆元為30無逆元，無逆元， 1的逆元為的逆元為1，2的逆元為的逆元為3，3的逆元為的逆元為2，4的逆元為的逆元為4四、逆元四、逆元 定理定理4：對于可結合運算：對于可結合運算, 如果一個元素如果一個元素x有左逆元有左逆元l和右和右逆元逆元r,那么那么l=r=x1(即逆元是唯一的即逆元是唯一的)。 證明證明 : 設e對運算*是么元, 于是l * x = x * r = e 根據(jù)運算*的可結合性, 得到l = l * e = l *(x

17、 * r ) = (l * x) * r = e * r = r 設x有兩個逆元a,b,那么a = a * e = a * ( x * b ) = ( a * x ) * b = e * b = b 所以逆元是唯一的。 可約性定義可約性定義：設*是S上的二元運算, aS, 如果對于每一x、yS有(a * x=a * y)(x * a=y * a) (x=y)，則稱a是可約的可約的或可消可消去的去的。四、逆元四、逆元 定理定理5：若代數(shù)：若代數(shù)中中 運算滿足結合律運算滿足結合律,且且aS有逆元有逆元,那那么么a必定是可約的。必定是可約的。證明證明 :設a的逆元為a-1，對x、yS， (1)當ax

18、 = ay時可得a-1 (ax) = a-1 (ay)， 即 (a-1 a)x = (a-1 a)y，可推得x = y。 (2)當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ù)系統(tǒng)：例題 例例: 在整數(shù)集合I上， 定義二元運算。為a*bab2 請回答： (1) 集合I和運算*是否構成代數(shù)系統(tǒng)? (2) 運算*在I上可交換嗎？ (3) 運算*在I上可結合嗎？ (4) 運算*在I上有無單位元？ (5)對運算*是否所有的元素都有逆元？若有，逆元是什么？五、代數(shù)系統(tǒng)：例題五、代數(shù)系統(tǒng)：例題 解答解答: (1)