離散數(shù)學PPT教學 代數(shù)系統(tǒng)

1、 歡迎進入 離 散 數(shù) 學 第 七章 代 數(shù)系統(tǒng)1近世代數(shù)第七章 代數(shù)系統(tǒng)7.1 代數(shù)系統(tǒng)的引入前言 7.2 運算及其性質(zhì)結(jié)束2前言為什么要研究代數(shù)系統(tǒng)？ 代數(shù)是專門研究離散對象的數(shù)學，是對符號的操作。它是現(xiàn)代數(shù)學的三大支柱之一（另兩個為分析與幾何）。代數(shù)從19世紀以來有驚人的發(fā)展，帶動了整個數(shù)學的現(xiàn)代化。隨著信息時代的到來，計算機、信息都是數(shù)字（離散化）的，甚至電視機攝像機、照相機都在數(shù)字化。知識經(jīng)濟有人也稱為數(shù)字經(jīng)濟。這一切的背后的科學基礎(chǔ)，就是數(shù)學，尤其是專門研究離散對象的代數(shù)。代數(shù)發(fā)端于“用符號代替數(shù)”，后來發(fā)展到以符號代替各種事物。在一個非空集合上，確定了某些運算以及這些運算滿足的規(guī)

2、律，于是該非空集合中的元素就說是有了一種代數(shù)結(jié)構(gòu)?，F(xiàn)實世界中可以有許多具體的不相同的代數(shù)系統(tǒng)。但事實上，不同的代數(shù)系統(tǒng)可以有一些共同的性質(zhì)。正因為此，我們要研究抽象的代數(shù)系統(tǒng)，并假設(shè)它具有某一類具體代數(shù)系統(tǒng)共同擁有的性質(zhì)。任何在這個抽象系統(tǒng)中成立的結(jié)論，均可適用于那一類代數(shù)系統(tǒng)中的任何一個。 3抽象代數(shù)學在計算機中的應(yīng)用 代數(shù)學歷史悠久。代數(shù)的發(fā)展可分成兩個階段。19世紀這前的代數(shù)稱為古典代數(shù)，19世紀至今的代數(shù)稱為近世代數(shù)（抽象代數(shù)）。 抽象代數(shù)學的研究對象是抽象的，它不是以某一具體事物為研究對象，而是以一大類具有共同性質(zhì)的事物為研究對象。因此其研究成果適用于這一類事物中的每一個，從而收到事

3、半功倍之效。抽象代數(shù)學的主要內(nèi)容是研究各種各樣的代數(shù)系統(tǒng)。它把一些形式上很不相同的代數(shù)系統(tǒng)，用統(tǒng)一的方法描述、研究和推理，從而得到反映出它們共性的一些本質(zhì)的結(jié)論，然后再把這些結(jié)論應(yīng)用到具體的代數(shù)系統(tǒng)中。4抽象代數(shù)學在計算機中的應(yīng)用抽象代數(shù)的概念和方法也是研究計算科學的重要數(shù)學工具。有經(jīng)驗和成熟的計算科學家都知道，除了數(shù)理邏輯處，對計算科學最有用的數(shù)學分支學就是代數(shù)，特別是抽象代數(shù)。抽象代數(shù)是關(guān)于運算的學問，是關(guān)于計算規(guī)則的學問。在許多實際問題的研究中都離不開數(shù)學模型，而構(gòu)造數(shù)學模型就要用到某種數(shù)學結(jié)構(gòu)，而抽象世代數(shù)研究的中心問題就是一種很重要的數(shù)學結(jié)構(gòu)-代數(shù)系統(tǒng)：半群、群、格與布爾代數(shù)等等。計

4、算科學的研究也離不開抽象代數(shù)的應(yīng)用：半群理論在自動機理論和形式語言中發(fā)揮了重要作用；有限域理論是編碼理論的數(shù)學基礎(chǔ)，在通訊中起過重要的作用；至于格和布爾代數(shù)則更不用說了，是電子線路設(shè)計、電子計算機硬件設(shè)計和通訊系統(tǒng)設(shè)的重要工具。另外描述機器可計算的函數(shù)、研究算術(shù)計算的復雜性、刻畫抽象數(shù)據(jù)結(jié)構(gòu)、描述作為程序設(shè)計基礎(chǔ)的形式語義學，都需要抽象代數(shù)知識。 5學習本章的方法 1、要按照數(shù)學的思維方式學習, 即觀察客觀世界, 抽象出模型, 再分析、推理揭示內(nèi)在規(guī)律的過程。 2、領(lǐng)會“抽象”性：代數(shù)的抽象性不僅體現(xiàn)在元素的抽象上, 還體現(xiàn)在相應(yīng)運算的抽象上, 是在最純粹的形式下研究代數(shù)結(jié)構(gòu)中的運算的規(guī)律與性

5、質(zhì), 從運算的角度來考慮代數(shù)結(jié)構(gòu)中的元素。因此, 初等代數(shù)的相應(yīng)概念、結(jié)論不能直接應(yīng)用在抽象代數(shù)中。如何跨越從直觀到抽象是學習抽象代數(shù)的重要一步。 3、教材的基本思路是： 首先嚴格定義什么是代數(shù)結(jié)構(gòu), 并討論一般代數(shù)結(jié)構(gòu)的基本性質(zhì)。然后討論代數(shù)結(jié)構(gòu)研究的兩個方面：其一是通過一些基本性質(zhì)來規(guī)定一類特定的代數(shù)結(jié)構(gòu), 并對這類代數(shù)結(jié)構(gòu)的性質(zhì)進行研究。其二是研究代數(shù)結(jié)構(gòu)之間的各種關(guān)系, 通過對代數(shù)結(jié)構(gòu)之間關(guān)系的研究, 就可以把一個代數(shù)結(jié)構(gòu)中的某些性質(zhì)推廣到另一個代數(shù)結(jié)構(gòu)中。6學習本章的方法4、結(jié)合具體例子與應(yīng)用來理解抽象代數(shù)的概念與結(jié)論, 特別是“抽象”的概念, 在理解的基礎(chǔ)上熟悉基本概念與重要結(jié)論,

6、 掌握基本推理方法, 領(lǐng)會抽象代數(shù)的研究方法,并嘗試去解決具體問題。 5、抽象代數(shù)以代數(shù)結(jié)構(gòu)為研究對象，集合論是研究代數(shù)結(jié)構(gòu)的基礎(chǔ)。而群是抽象代數(shù)所研究的最為重要、最為基礎(chǔ)的代數(shù)結(jié)構(gòu), 也是抽象代數(shù)部分的學習重點, 學習好群的相關(guān)知識, 習慣了代數(shù)的“抽象”思維, 環(huán)、域的學習也就相對容易了。 6、閱讀教材、課堂聽講、反復思考, 并獨立完成一定數(shù)量的習題, 只有如此, 才能理解抽象代數(shù)的概念, 掌握有關(guān)理論, 從而提高分析問題的能力。77.1 代數(shù)系統(tǒng)的引入 代數(shù)系統(tǒng)是由一個集合（此集合稱為代數(shù)的載體）和定義在集合上的運算構(gòu)成。注：載體一般是非空集合， 定義在載體上的n元運算是一個從An到B的

7、映射。 例：）取整 X，求絕對值 |X|，是一元運算 ）+,X是二元運算,）if xyandyz then是三元運算例：整數(shù)集，實數(shù)集，符號串集合等。87.2 運算及其性質(zhì)一、二元運算 1、運算封閉性：若x，yA，有x * yA， 稱*在A上是封閉的 例： A=xx=2n，nN， 問運算封 閉否，呢？ 解：2r，2sA， 2r x 2s=2r+sA （） 運算封閉 2，4A，2+4A，運算不封閉 2，4A，2/4A， 運算不封閉92、結(jié)合律 證：a，b，cA， a*（b*c）=a*c=c ( a*b）*c=b*c=c a*（b*c）=（a*b）*c *滿足結(jié)合律 已知，若x，y，zA，有x*（

8、y*z）=（x*y）*z，稱*滿足結(jié)合律。 例：，若a，bA，有a*b=b 證明：*滿足結(jié)合律 7.2 運算及其性質(zhì)103、交換律 已知，若x，yA，有x*y=y*x，稱*滿足交換律。例：設(shè),*定義如下： a*b=a+b-ab ，問*滿足交換律否？ 證：a，bA， a*b=a+b-ab=b+a-ba=b*a *滿足交換律。7.2 運算及其性質(zhì)11設(shè)，若x，y，zA有: x*(yz)=（x*y）（x*z） ; (yz)*x=(y*x)(z*x) 稱運算*在上可分配例：設(shè)A=，二元運 算*，定義如左:* 問分配律成立否？ 證明：x(y*z)=(xy)*(xz) 證：當x=：x(y*z)= ; (x

9、y)*(xz)= 當x=：x(y*z)=y*z ; (xy)*(xz)=y*z注: 若找不到規(guī)律,對該例則應(yīng)用8個式子進行驗證。 、運算*對運算不可分配 證：*（）=*= （*）（*）= 7.2.1 運算及其性質(zhì)4.分配律12例:N為自然數(shù)集,x,yN，x*y=maxx，y, xy=minx，y 證明：x，yN， x*（xy）=maxx，minx，y=x xy =x *滿足吸收律 x x y x（x*y）=minx，maxx，y=x xy =x 滿足吸收律 x x y7.2.1 運算及其性質(zhì)5.吸收律：設(shè)，若x，y，zA有: x*(x z)=x 稱運算*滿足吸收律; x (x * y) =x；

10、 運算 滿足吸收律 試證：*，滿足吸收律13 已知A，*，若xA，x*x=x 則稱*滿足等冪律 例：已知集合s,（s）,則,滿足吸 收律，等冪律 7.2 運算及其性質(zhì)6.等冪律147.2 運算及其性質(zhì)二、么元（單位元）和零元1、定義 :設(shè)*是s上二元運算，er，eI，r，e， s ，有.若xs，有el*x=x，稱el為運算*的左么元若xs，有x*er=x，稱er為運算*的右么元 .若xs，有l(wèi)*x=l ，稱l為運算*的左零元 若xs，有x*r=r，稱r為運算*的右零元.若xs，有e*x=x，x*e=x稱e為運算*的么元 若xs，有*x=x* = ，稱為運算*的零元 15例：代數(shù)A=a，b，c，

11、 。 用下表定義：。abcaabbbabccaba則b是左么元，無右么元,a是右零元，b是右零元，無左零元;二、么元（單位元）和零元運算。既不滿足結(jié)合律，也不滿足交換律。 16 例: a）I，x， I為整數(shù)集則么元為1，零元為0 二、么元（單位元）和零元b）（s）,對運算，是么元， s是零元，對運算，s是么元 ，是零元。c）N，+有么元0，無零元。172、性質(zhì)、Th1: 設(shè)*是s上的二元運算，滿足結(jié)合律，具有左么元el，右么元er，則el=er=e證明： er = el* er = el二、么元（單位元）和零元推論：二元運算的么元若存在則唯一 證明：反證法：設(shè)有二個么元e，e ；則e=e*e=

12、e、Th2: 設(shè)*是s上的二元運算，具有左零元ol ，右零元or，則ol=or=o 推論：二元運算的零元若存在則唯一18 三、 逆元 1、逆元定義 設(shè)*是s上的二元運算，e是運算*的么元 7.2 運算及其性質(zhì)、若x*y=e那對于運算*，x是y的左逆元，y是 x的右逆元、若x*y=e，y*x=e，則稱x是y的逆元，y的逆 元通常記為y-1，存在逆元(左逆無，右逆元） 的元素稱為可逆的（左可逆的，右可逆的）19例： a)、代數(shù) N，+中僅有么元0，有逆元0， R，*中，除零元0外所有元素均有逆元 b)、A=a，b，c，*由下表定義： *abcaaabbabccaccb是么元,a的右逆元為c，無左逆元，b的逆元為b，c的右逆元為空，左逆元為a 三、 逆元20d）A=0，1，2，k-1，k 模k乘法k定義如下： x ky= x y x y k x y-n k x yk, n0, 1， 則有些元素存在逆元，有些元素無逆元 當且僅當x與k互質(zhì)時，x有逆元