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

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

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

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

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

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

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

7、映射。 例：）取整 X，求絕對(duì)值 |X|，是一元運(yùn)算 ）+,X是二元運(yùn)算,）if xyandyz then是三元運(yùn)算例：整數(shù)集，實(shí)數(shù)集，符號(hào)串集合等。87.2 運(yùn)算及其性質(zhì)一、二元運(yùn)算 1、運(yùn)算封閉性：若x，yA，有x * yA， 稱*在A上是封閉的 例： A=xx=2n，nN， 問(wèn)運(yùn)算封 閉否，呢？ 解：2r，2sA， 2r x 2s=2r+sA （） 運(yùn)算封閉 2，4A，2+4A，運(yùn)算不封閉 2，4A，2/4A， 運(yùn)算不封閉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 運(yùn)算及其性質(zhì)103、交換律 已知，若x，yA，有x*y=y*x，稱*滿足交換律。例：設(shè),*定義如下： a*b=a+b-ab ，問(wèn)*滿足交換律否？ 證：a，bA， a*b=a+b-ab=b+a-ba=b*a *滿足交換律。7.2 運(yùn)算及其性質(zhì)11設(shè)，若x，y，zA有: x*(yz)=（x*y）（x*z） ; (yz)*x=(y*x)(z*x) 稱運(yùn)算*在上可分配例：設(shè)A=，二元運(yùn) 算*，定義如左:* 問(wèn)分配律成立否？ 證明：x(y*z)=(xy)*(xz) 證：當(dāng)x=：x(y*z)= ; (x

9、y)*(xz)= 當(dāng)x=：x(y*z)=y*z ; (xy)*(xz)=y*z注: 若找不到規(guī)律,對(duì)該例則應(yīng)用8個(gè)式子進(jìn)行驗(yàn)證。 、運(yùn)算*對(duì)運(yùn)算不可分配 證：*（）=*= （*）（*）= 7.2.1 運(yùn)算及其性質(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 運(yùn)算及其性質(zhì)5.吸收律：設(shè)，若x，y，zA有: x*(x z)=x 稱運(yùn)算*滿足吸收律; x (x * y) =x；

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

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

12、e、Th2: 設(shè)*是s上的二元運(yùn)算，具有左零元ol ，右零元or，則ol=or=o 推論：二元運(yùn)算的零元若存在則唯一18 三、 逆元 1、逆元定義 設(shè)*是s上的二元運(yùn)算，e是運(yùn)算*的么元 7.2 運(yùn)算及其性質(zhì)、若x*y=e那對(duì)于運(yùn)算*，x是y的左逆元，y是 x的右逆元、若x*y=e，y*x=e，則稱x是y的逆元，y的逆 元通常記為y-1，存在逆元(左逆無(wú)，右逆元） 的元素稱為可逆的（左可逆的，右可逆的）19例： a)、代數(shù) N，+中僅有么元0，有逆元0， R，*中，除零元0外所有元素均有逆元 b)、A=a，b，c，*由下表定義： *abcaaabbabccaccb是么元,a的右逆元為c，無(wú)左逆元，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， 則有些元素存在逆元，有些元素?zé)o逆元 當(dāng)且僅當(dāng)x與k互質(zhì)時(shí)，x有逆元