離散數(shù)學(xué)-代數(shù)系統(tǒng)

離散數(shù)學(xué)-代數(shù)系統(tǒng)第1頁，共42頁，2023年，2月20日，星期一個(gè)人信息(Personal

Information)Instructor:焦曉鵬，副教授，工學(xué)博士

Bs.(2004)XidianUniversity

PhD(2009)XidianUniversity

RF(2010-2012)NationalUniversityofSingaporeResearchDirection:

●新型差錯(cuò)控制編碼技術(shù)●高密度存儲(chǔ)系統(tǒng)信號(hào)處理和編碼技術(shù)（高密度磁盤和閃存flashmemory）●數(shù)字噴泉碼和網(wǎng)絡(luò)編碼技術(shù)Laboratory:計(jì)算學(xué)院計(jì)算機(jī)科學(xué)系Office:主樓I-區(qū),402房間Tel/p>

Email:jiaozi1216@126.com第2頁，共42頁，2023年，2月20日，星期一關(guān)于學(xué)習(xí)和考試(1)擺正學(xué)習(xí)和考試的關(guān)系

考試是學(xué)習(xí)期間的副產(chǎn)品

以考試為目的的學(xué)習(xí)是對(duì)知識(shí)耍流氓(2)勤奮!!!

諸葛亮誡子書

夫君子之行，靜以修身，儉以養(yǎng)德。非淡泊無以明志，非寧靜無以致遠(yuǎn)。夫?qū)W須靜也，才須學(xué)也。非學(xué)無以廣才，非志無以成學(xué)。韜慢則不能勵(lì)精，險(xiǎn)躁則不能治性。年與時(shí)馳，意與歲去，遂成枯落，多不接世。悲守窮廬，將復(fù)何及？第3頁，共42頁，2023年，2月20日，星期一名人話數(shù)學(xué)數(shù)學(xué)是科學(xué)之王?！咚箶?shù)學(xué)支配著宇宙?！呥_(dá)哥拉斯自然界的書是用數(shù)學(xué)的語言寫成的?！だ詳?shù)學(xué)是一切知識(shí)中的最高形式?！乩瓐D數(shù)學(xué)是打開科學(xué)大門的鑰匙?！喔婚T科學(xué)，只有當(dāng)它成功地運(yùn)用數(shù)學(xué)時(shí)，才能達(dá)到真正完善的地步?！R克思一個(gè)國家只有數(shù)學(xué)蓬勃的發(fā)展，才能展現(xiàn)它國力的強(qiáng)大。數(shù)學(xué)的發(fā)展和至善和國家繁榮昌盛密切相關(guān)?！闷苼龅?頁，共42頁，2023年，2月20日，星期一離散數(shù)學(xué)(DiscreteMathematics)讀史使人明智,讀詩使人聰慧,演算使人精密,哲理使人深刻,倫理學(xué)使人有修養(yǎng),邏輯修辭使人善辯?！喔鶖?shù)學(xué)史的書籍:

<古今數(shù)學(xué)思想>

[美]莫里斯.克萊茵

著

<數(shù)學(xué)史>

[英]斯科特

著廣西師范大學(xué)出版社沒有一種數(shù)學(xué)的思想,以它被發(fā)現(xiàn)時(shí)的那個(gè)樣子公開發(fā)表出來。一個(gè)問題被解決后,相應(yīng)地發(fā)展為一種形式化技巧,結(jié)果把求解過程丟在一邊,使火熱的發(fā)明變成冰冷的美麗。——弗賴登塔爾:荷蘭著名數(shù)學(xué)教育家第5頁，共42頁，2023年，2月20日，星期一離散數(shù)學(xué)課程的學(xué)習(xí)特點(diǎn)及方法特點(diǎn):強(qiáng)調(diào)：邏輯性、抽象性；注重：概念、方法與應(yīng)用方法:1．該課程概念名詞多，定義多，公式多，要求記憶準(zhǔn)確。2．認(rèn)真/仔細(xì)做好課堂筆記。3．完成大量習(xí)題。考核:平時(shí)成績15%期末考試85%第6頁，共42頁，2023年，2月20日，星期一離散數(shù)學(xué)教材教材：

《離散數(shù)學(xué)》方世昌編著

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

2009.8第7頁，共42頁，2023年，2月20日，星期一離散數(shù)學(xué)教材舊版教材：

《離散數(shù)學(xué)》方世昌編著(第二版)

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

1996.11第8頁，共42頁，2023年，2月20日，星期一離散數(shù)學(xué)參考書1.《離散數(shù)學(xué)》左孝凌、李為鑑、劉永才編著上?？萍嘉墨I(xiàn)出版社第9頁，共42頁，2023年，2月20日，星期一離散數(shù)學(xué)參考書2.《離散數(shù)學(xué)》--理論?分析?題解，左孝凌等著上?？萍嘉墨I(xiàn)出版社第10頁，共42頁，2023年，2月20日，星期一離散數(shù)學(xué)參考書3.《離散數(shù)學(xué)習(xí)題集》數(shù)理邏輯與集合論分冊(cè)耿素云圖論分冊(cè)，耿素云抽象代數(shù)分冊(cè)，張立昂北京大學(xué)出版社第11頁，共42頁，2023年，2月20日，星期一離散數(shù)學(xué)參考書第12頁，共42頁，2023年，2月20日，星期一離散數(shù)學(xué)參考書第13頁，共42頁，2023年，2月20日，星期一離散數(shù)學(xué)(二)四、代數(shù)系統(tǒng)離散數(shù)學(xué)教學(xué)內(nèi)容

一、數(shù)理邏輯

集合

二、

關(guān)系

函數(shù)

三、圖論

離散數(shù)學(xué)(一)第14頁，共42頁，2023年，2月20日，星期一高次方程求解歷程(1)

埃及/古希臘一次/二次方程(2)16世紀(jì)意大利三次方程(卡當(dāng)公式),四次方程(3)17世紀(jì)四次以上方程未解出!(4)18世紀(jì)歐拉推斷:實(shí)系數(shù)多項(xiàng)式可分解為一次或二次因式乘積哥德巴赫拒絕接受歐拉推斷問題轉(zhuǎn)換:每一個(gè)此類多項(xiàng)式至少有一個(gè)實(shí)根或者復(fù)根(代數(shù)基本定理)歐拉,D’Alembert,拉格朗日分別給出證明,但并不完善高斯(1799,博士論文)證明了代數(shù)基本定理

Vandermonde和高斯研究了xn-1=0的特殊情形四次以上方程代數(shù)可解的一般情況拉格朗日:

“關(guān)于方程的代數(shù)解法的思考”,被迫得出結(jié)論用代數(shù)運(yùn)算求解一般高次方程是不可能的.

(5)19世紀(jì)阿貝爾(Abel)和伽羅瓦(Galois)徹底解決高次方程代數(shù)不可解！第15頁，共42頁，2023年，2月20日，星期一近世代數(shù)/抽象代數(shù)歷史尼爾斯·亨利克·阿貝爾(NielsHenrikAbel)1802年8月5日－1829年4月6日挪威數(shù)學(xué)家，以證明五次方程不存在根式解和對(duì)橢圓函數(shù)論的研究而聞名埃瓦里斯特·伽羅瓦(évaristeGalois)1811年10月25日－1832年5月31日法國數(shù)學(xué)家，以發(fā)現(xiàn)了n次多項(xiàng)式可以用根式解的充要條件而聞名.

伽羅瓦理論,當(dāng)代代數(shù)與數(shù)論的基本支柱之一第16頁，共42頁，2023年，2月20日，星期一近世代數(shù)/抽象代數(shù)歷史第17頁，共42頁，2023年，2月20日，星期一近世代數(shù)/抽象代數(shù)歷史第18頁，共42頁，2023年，2月20日，星期一近世代數(shù)/抽象代數(shù)歷史后人對(duì)伽羅瓦的評(píng)論:

被許多科學(xué)家和史學(xué)家認(rèn)為是人類歷史上最偉大的10位數(shù)學(xué)家之一著名數(shù)學(xué)家皮卡評(píng)價(jià):

在開創(chuàng)性和概念的深邃方面無人能及

20世紀(jì)偉大數(shù)學(xué)家外爾評(píng)價(jià):伽羅瓦的論述在好幾十年中一直被看作是天書;但是,它后來對(duì)數(shù)學(xué)的整個(gè)發(fā)展產(chǎn)生愈來愈深遠(yuǎn)的影響.如果從它所包含思想之新奇和意義之深遠(yuǎn)來判斷,也許是整個(gè)人類知識(shí)寶庫中價(jià)值最為重大的一件珍品.大數(shù)學(xué)家weil評(píng)價(jià):現(xiàn)在,大家都已充分認(rèn)識(shí)到伽羅瓦理論是一個(gè)基本分支,每一個(gè)嚴(yán)肅認(rèn)真的數(shù)學(xué)專業(yè)大學(xué)生應(yīng)該在頭幾年的教育中就了解它.第19頁，共42頁，2023年，2月20日，星期一近世代數(shù)/抽象代數(shù)歷史第20頁，共42頁，2023年，2月20日，星期一第21頁，共42頁，2023年，2月20日，星期一第六章、代數(shù)結(jié)構(gòu)代數(shù)系統(tǒng):

集合和定義在集合上的若干運(yùn)算所組成的系統(tǒng)。用抽象方法研究各種代數(shù)系統(tǒng)性質(zhì)的理論學(xué)科叫“近世代數(shù)”或“抽象代數(shù)”。

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

幺元、零元和逆元難點(diǎn):重點(diǎn)和難點(diǎn):幺元、零元和逆元3第25頁，共42頁，2023年，2月20日，星期一一、代數(shù)的構(gòu)成與分類代數(shù)的構(gòu)成:

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

m=1,一元運(yùn)算，S→S,R→R,

f(x)=|x|+1；

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

代數(shù)系統(tǒng)的定義：1.一個(gè)非空集合A(代數(shù)的載體)；2.定義的若干在A上封閉的運(yùn)算f1,f2,…,fm；3.代數(shù)常數(shù)。代數(shù)系統(tǒng)常用一個(gè)n重組<A，，，…，>來表示,其中A稱為代數(shù)結(jié)構(gòu)的載體，，，…為各種運(yùn)算。有時(shí)為了強(qiáng)調(diào)S有某些元素地位特殊,也可將它們列入n重組的末尾，即<A，，，…，k1，…，km>。第26頁，共42頁，2023年，2月20日，星期一一、代數(shù)的構(gòu)成與分類代數(shù)的分類:1.要有相同的構(gòu)成成分。2.服從一組相同的稱為公理的性質(zhì)。

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

(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>是不同類的,因?yàn)楣?6)對(duì)這個(gè)代數(shù)不成立

(這里“-”表示集合的絕對(duì)補(bǔ))。第27頁，共42頁，2023年，2月20日，星期一二、子代數(shù)封閉性定義：設(shè)?與?是S上的二元與一元運(yùn)算,S′?S，若對(duì)任意a,b∈S′，蘊(yùn)含著a?b∈S′，稱S′關(guān)于運(yùn)算?是封閉的；若對(duì)任意a∈S′，蘊(yùn)含著?a∈S′，稱S′關(guān)于運(yùn)算?是封閉的。子代數(shù)的定義：設(shè)A=<S,?,△,k>是一代數(shù),如果

(1)S′?S

(2)S′對(duì)S上的運(yùn)算?和△封閉

(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>的一個(gè)子代數(shù)。第28頁，共42頁，2023年，2月20日，星期一三、幺元、零元幺元定義：設(shè)*是S上的二元運(yùn)算,(1)若存在el∈S，對(duì)所有x∈S，都有el*

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

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

e

=e

*

x=x，則e是關(guān)于運(yùn)算*的么元。第29頁，共42頁，2023年，2月20日，星期一三、幺元、零元幺元示例：例2代數(shù)A=<{a,b,c},*>如下表所示：

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

*abcaabbbabccaba第30頁，共42頁，2023年，2月20日，星期一三、幺元、零元零元定義：設(shè)*是S上的二元運(yùn)算,

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

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

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

,S>

么元零元對(duì)∪：?S

對(duì)∩：S?*abcaabbbabccaba例2的代數(shù)中：

右零元：a,b；左零元：無；右么元：無；左么元：b可以看出：左(右)零元不一定存在；左(右)零元存在時(shí)也不一定唯一；左零元與右零元可能同時(shí)存在。第32頁，共42頁，2023年，2月20日，星期一三、幺元、零元定理1：設(shè)*是定義在集合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è)<A,*>是一個(gè)代數(shù)系統(tǒng),且集合A中元素的個(gè)數(shù)大于1.如果該代數(shù)系統(tǒng)中存在幺元e和零元θ,則θ≠e。證明：用反證法，假如幺元e

=零元，那么對(duì)于任意xA,必有x=e*x=θ*x=θ=e。于是，A中所有元素都是相同的，這與A中含有多個(gè)元素相矛盾。第33頁，共42頁，2023年，2月20日，星期一四、逆元逆元定義：設(shè)*是A上的二元運(yùn)算,e是A中關(guān)于*的么元，

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

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

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

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

一般來說，一個(gè)元素的左逆元不一定等于該元素的右逆元；一個(gè)元素可以有左逆元而無右逆元，甚至一個(gè)元素的左（右）逆元還可以不唯一。第34頁，共42頁，2023年，2月20日，星期一四、逆元例5(1)：<N,+>么元為0，僅0有逆元;

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

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

1是么元，元素x∈Nk在Nk中有逆元僅當(dāng)x和k互質(zhì)。第35頁，共42頁，2023年，2月20日，星期一四、逆元1是幺元，逆元是它本身0,2無逆元，3的逆元為30無逆元，1的逆元為1，2的逆元為3，3的逆元為2，4的逆元為4第36頁，共42頁，2023年，2月20日，星期一四、逆元

定理4：對(duì)于可結(jié)合運(yùn)算,如果一個(gè)元素x有左逆元l和右逆元r,那么l=r=x－1(即逆元是唯一的)。證明

:設(shè)e對(duì)運(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有兩個(gè)逆元a,b,那么a=a*e=a*(x*b)=(a*x)*b=e*b=b

所以逆元是唯一的。

可約性定義：設(shè)*是S上的二元運(yùn)算,a∈S,如果對(duì)于每一x、y∈S有(a*x=a*y)∨(x*a=y*a)(x=y)，則稱a是可約的或可消去的。第37頁，共42頁，2023年，2月20日，星期一四、逆元

定理5：若代數(shù)<S,>中運(yùn)算滿足結(jié)合律,且a∈S有逆元,那么a必定是可約的。證明

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

(1)當(dāng)ax=ay時(shí)可得a-1(ax)=a-1(ay)，即(a-1a)x=(a-1a)y，可推得x=y。

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

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

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

請(qǐng)回答：

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

(3)運(yùn)算*在I上可結(jié)合