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

1、第五章 代數(shù)結(jié)構(gòu)5-1 代數(shù)系統(tǒng)引入授課人：李朔Email:chn.nj.1algebraic system代數(shù)也叫代數(shù)結(jié)構(gòu)，是指定義有若干運(yùn)算的集合例如整數(shù)集合，在其上定義了加法、乘法就構(gòu)成了一個(gè)代數(shù)系統(tǒng)。代數(shù)學(xué)的歷史悠久。但是從上世紀(jì)初以來，代數(shù)學(xué)的研究對(duì)象和研究方法發(fā)生了重大變革，形成了抽象代數(shù)學(xué)，這一變化可以追溯到伽羅瓦(Galois)提出群的概念。人們發(fā)現(xiàn)許多不同對(duì)象上的運(yùn)算可以有共同的性質(zhì)，這些發(fā)現(xiàn)將代數(shù)學(xué)研究引導(dǎo)到更高的層次 抽象代數(shù)系統(tǒng)研究。2抽象代數(shù)：不關(guān)心代數(shù)系數(shù)的具體集合是什么也不關(guān)心集合的運(yùn)算如何定義只根據(jù)假設(shè)這些運(yùn)算的某些規(guī)則（如結(jié)合律，分配律等）來討論系統(tǒng)應(yīng)具有的性

2、質(zhì)，使所得結(jié)論具有普遍意義。3algebraic system抽象代數(shù)學(xué)不同于以代數(shù)方程求根和根的分布情況為研究中心的古典代數(shù)學(xué)。在抽象代數(shù)系統(tǒng)中，對(duì)象是抽象的而不是具體的，對(duì)象上的運(yùn)算也是抽象的，其含義由一組給定公理規(guī)定。抽象代數(shù)系統(tǒng)在計(jì)算機(jī)科學(xué)研究中始終占有重要的地位和作用：毫無疑問，沒有抽象代數(shù)結(jié)構(gòu)研究和數(shù)理邏輯研究的先行發(fā)展，圖靈就不可能在1936年提出圖靈機(jī)這樣的代數(shù)結(jié)構(gòu)作為計(jì)算的模型，從而第一次精確地定義了計(jì)算的概念和證明了計(jì)算機(jī)在理論上的存在性。4algebraic system在上世紀(jì)4050年代，格和布爾代數(shù)成為計(jì)算機(jī)硬件設(shè)計(jì)以及通信系統(tǒng)設(shè)計(jì)中的重要工具，半群理論在形式語(yǔ)言與

3、自動(dòng)機(jī)的研究中發(fā)揮重要的作用。上世紀(jì)70年代在數(shù)據(jù)庫(kù)研究中，人們發(fā)現(xiàn)關(guān)系代數(shù)理論能夠作為數(shù)據(jù)庫(kù)的理論模型。代數(shù)的概念與方法是研究計(jì)算機(jī)科學(xué)和工程的重要數(shù)學(xué)工具。眾所周知，在許多實(shí)際問題的研究中都離不開數(shù)學(xué)模型，而構(gòu)造數(shù)學(xué)模型就要用到某種數(shù)學(xué)結(jié)構(gòu)。我們這里所要研究的是一類特殊的數(shù)學(xué)結(jié)構(gòu)由集合上定義若干個(gè)運(yùn)算而組成的系統(tǒng)。我們通常稱它為代數(shù)系統(tǒng)。它在計(jì)算機(jī)科學(xué)中有著廣泛的應(yīng)用。5一、運(yùn)算本章將從一般代數(shù)系統(tǒng)的引入出發(fā)，研究一些特殊的代數(shù)系統(tǒng)，而這些代數(shù)系統(tǒng)中的運(yùn)算具有某些性質(zhì)，從而確定了這些代數(shù)系統(tǒng)的數(shù)學(xué)結(jié)構(gòu)?？疾煲粋€(gè)非空集合上運(yùn)算的概念 （1）將有理數(shù)集合Q上的每一個(gè)數(shù) a 的映射成它的整數(shù)部分

4、a （2）將Q上的每一個(gè)數(shù)a 映射成它的相反數(shù)-a以上兩個(gè)映射可以稱為集合Q上的一元運(yùn)算 （3）在集合Q上，對(duì)任意兩個(gè)數(shù)所進(jìn)行的普通加法和乘法都是集合Q上的二元運(yùn)算 （也可以看作是將Q中的每?jī)蓚€(gè)數(shù)映射成一個(gè)數(shù) ）6一、運(yùn)算（4）對(duì)集合Q上的任意三個(gè)數(shù)x，x2 ，x3 ，代數(shù)式x12+x22+x32和x1+x2+x3分別給出了Q上的兩個(gè)三元運(yùn)算 （分別將Q中三個(gè)數(shù)映射成Q中的一個(gè)數(shù) ）上述這些例子有一個(gè)共同的特征，那就是其運(yùn)算的結(jié)果都是在原來的集合中，我們稱那些具有這種特征的運(yùn)算是封閉的，簡(jiǎn)稱閉運(yùn)算。 相反地，沒有這種特征的運(yùn)算就是不封閉的。很容易舉出不封閉運(yùn)算的例子 ：設(shè)N是自然數(shù)集，Z是整數(shù)

5、集，普通的減法是N-N到Z的運(yùn)算*因?yàn)閮蓚€(gè)自然數(shù)相減可以不是自然數(shù)，所以減法運(yùn)算不是自然數(shù)集N上的閉運(yùn)算。 7一、運(yùn)算又如：一架自動(dòng)貨機(jī)，能接受一角硬幣和二角五分硬幣，而所對(duì)應(yīng)的商品是桔子水（瓶）、可口可樂（瓶）和冰淇淋（杯）。當(dāng)人們投入上述硬幣的任何兩枚時(shí)，自動(dòng)售貨機(jī)將按下表所示的供應(yīng)相應(yīng)的商品。表格左上角的記號(hào)*可理解為一個(gè)二元運(yùn)算符。 *一角硬幣 二角伍分硬幣一角硬幣二解伍分硬幣桔子水 可口可樂可口可樂 冰淇淋二元運(yùn)算*是在集合一角硬幣，二角伍分硬幣上的不封閉運(yùn)算。8一、運(yùn)算定義5-1.1 對(duì)于集合A，一個(gè)從An到B的映射，稱為 集合A上的n元運(yùn)算。如果 BA，則稱該n元運(yùn)算在A上封閉。

6、 如 AAB稱為集A上的一個(gè)二元運(yùn)算，若BS,，稱該運(yùn)算是封閉的。例1：R上求一個(gè)數(shù)的相反數(shù)是一元運(yùn)算，非0實(shí)數(shù)集上求倒數(shù)為一元運(yùn)算，空間上點(diǎn)(x, y, z)投影到x軸為三元運(yùn)算。 例2：判定下列在給定集上的二元運(yùn)算的封閉性： 1）自然數(shù)集N上乘法，除法。 2）整數(shù)集Z上的加法，減法，乘法，除法。 3）非零實(shí)數(shù)集上加法，減法，乘法，除法。 4）S為任意集，S的冪集P（S）上， ，運(yùn)算。*通常用，*，等表示二元運(yùn)算 9二代數(shù)系統(tǒng) 定義5-1.2 一個(gè)非空集合A連同若干個(gè)定義在該集合上的運(yùn)算 f1，f2，f k 所組成的系統(tǒng)稱為一個(gè)代數(shù)系統(tǒng)，記作 。例如：（1）正整數(shù)集I及定義在該集合上的普通加

7、法“”組成一個(gè)代數(shù)系統(tǒng)I，（2）有限集S上冪集及其上運(yùn)算， 組成代數(shù)系統(tǒng) .10二代數(shù)系統(tǒng) 定義5-1.2 代數(shù)結(jié)構(gòu)是由以下三個(gè)部分組成的數(shù)學(xué)結(jié)構(gòu)： （1）非空集合S，稱為代數(shù)結(jié)構(gòu)的載體。 （2）載體S上的若干運(yùn)算。 （3）一組刻劃載體上各運(yùn)算所滿足性質(zhì)的公理。 *代數(shù)結(jié)構(gòu)常用一個(gè)多元序組來表示，其中 S是載體，、為各種運(yùn)算。有時(shí)為了強(qiáng)調(diào)S有某些元素地位特殊，也可將它們列入這種多元序組的末尾。雖然代數(shù)系統(tǒng)具有不同的形式，但它們之間可能有一些共同的運(yùn)算規(guī)律。11二代數(shù)系統(tǒng) 例如，考察代數(shù)系統(tǒng)I，+。很明顯，在這個(gè)代數(shù)系統(tǒng)中，關(guān)于加法運(yùn)算，具有以下三個(gè)運(yùn)算規(guī)律，即對(duì)于任意的x，I，有： (1) x+y I (封閉性） (2) x+y=y+x (交換律) (3) (x+y)+z=x+(y+z) （結(jié)合律）又如，設(shè)S是集合，P（S）是S的冪集，則代數(shù)系統(tǒng) P（S），和P（S），中的、都適合交換律，結(jié)合律，即他們與I，+有類似的運(yùn)算性質(zhì)。12由前例可看出，雖然集