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

離散數(shù)學代數(shù)系統(tǒng)引入1第一頁，共十五頁，編輯于2023年，星期一algebraicsystem代數(shù)也叫代數(shù)結(jié)構(gòu)，是指定義有若干運算的集合例如整數(shù)集合，在其上定義了加法、乘法就構(gòu)成了一個代數(shù)系統(tǒng)。代數(shù)學的歷史悠久。但是從上世紀初以來，代數(shù)學的研究對象和研究方法發(fā)生了重大變革，形成了抽象代數(shù)學，這一變化可以追溯到伽羅瓦(Galois)提出群的概念。人們發(fā)現(xiàn)許多不同對象上的運算可以有共同的性質(zhì)，這些發(fā)現(xiàn)將代數(shù)學研究引導到更高的層次─抽象代數(shù)系統(tǒng)研究。2第二頁，共十五頁，編輯于2023年，星期一抽象代數(shù)：不關心代數(shù)系數(shù)的具體集合是什么也不關心集合的運算如何定義只根據(jù)假設這些運算的某些規(guī)則（如結(jié)合律，分配律等）來討論系統(tǒng)應具有的性質(zhì)，使所得結(jié)論具有普遍意義。3第三頁，共十五頁，編輯于2023年，星期一algebraicsystem抽象代數(shù)學不同于以代數(shù)方程求根和根的分布情況為研究中心的古典代數(shù)學。在抽象代數(shù)系統(tǒng)中，對象是抽象的而不是具體的，對象上的運算也是抽象的，其含義由一組給定公理規(guī)定。抽象代數(shù)系統(tǒng)在計算機科學研究中始終占有重要的地位和作用：毫無疑問，沒有抽象代數(shù)結(jié)構(gòu)研究和數(shù)理邏輯研究的先行發(fā)展，圖靈就不可能在1936年提出圖靈機這樣的代數(shù)結(jié)構(gòu)作為計算的模型，從而第一次精確地定義了計算的概念和證明了計算機在理論上的存在性。4第四頁，共十五頁，編輯于2023年，星期一algebraicsystem在上世紀40－50年代，格和布爾代數(shù)成為計算機硬件設計以及通信系統(tǒng)設計中的重要工具，半群理論在形式語言與自動機的研究中發(fā)揮重要的作用。上世紀70年代在數(shù)據(jù)庫研究中，人們發(fā)現(xiàn)關系代數(shù)理論能夠作為數(shù)據(jù)庫的理論模型。代數(shù)的概念與方法是研究計算機科學和工程的重要數(shù)學工具。眾所周知，在許多實際問題的研究中都離不開數(shù)學模型，而構(gòu)造數(shù)學模型就要用到某種數(shù)學結(jié)構(gòu)。我們這里所要研究的是一類特殊的數(shù)學結(jié)構(gòu)－－由集合上定義若干個運算而組成的系統(tǒng)。我們通常稱它為代數(shù)系統(tǒng)。它在計算機科學中有著廣泛的應用。5第五頁，共十五頁，編輯于2023年，星期一一、運算本章將從一般代數(shù)系統(tǒng)的引入出發(fā)，研究一些特殊的代數(shù)系統(tǒng)，而這些代數(shù)系統(tǒng)中的運算具有某些性質(zhì)，從而確定了這些代數(shù)系統(tǒng)的數(shù)學結(jié)構(gòu)?？疾煲粋€非空集合上運算的概念（1）將有理數(shù)集合Q上的每一個數(shù)a的映射成它的整數(shù)部分［a］（2）將Q上的每一個數(shù)a映射成它的相反數(shù)-a以上兩個映射可以稱為集合Q上的一元運算

（3）在集合Q上，對任意兩個數(shù)所進行的普通加法和乘法都是集合Q上的二元運算（也可以看作是將Q中的每兩個數(shù)映射成一個數(shù)）6第六頁，共十五頁，編輯于2023年，星期一一、運算（4）對集合Q上的任意三個數(shù)x１，x2，x3

，代數(shù)式x12+x22+x32和x1+x2+x3分別給出了Q上的兩個三元運算（分別將Q中三個數(shù)映射成Q中的一個數(shù)）上述這些例子有一個共同的特征，那就是其運算的結(jié)果都是在原來的集合中，我們稱那些具有這種特征的運算是封閉的，簡稱閉運算。相反地，沒有這種特征的運算就是不封閉的。很容易舉出不封閉運算的例子：設N是自然數(shù)集，Z是整數(shù)集，普通的減法是N-N到Z的運算*因為兩個自然數(shù)相減可以不是自然數(shù)，所以減法運算不是自然數(shù)集N上的閉運算。

7第七頁，共十五頁，編輯于2023年，星期一一、運算又如：一架自動貨機，能接受一角硬幣和二角五分硬幣，而所對應的商品是桔子水（瓶）、可口可樂（瓶）和冰淇淋（杯）。當人們投入上述硬幣的任何兩枚時，自動售貨機將按下表所示的供應相應的商品。表格左上角的記號*可理解為一個二元運算符。

*一角硬幣

二角伍分硬幣一角硬幣二解伍分硬幣桔子水可口可樂可口可樂冰淇淋二元運算*是在集合{一角硬幣，二角伍分硬幣}上的不封閉運算。8第八頁，共十五頁，編輯于2023年，星期一一、運算定義5-1.1對于集合A，一個從An到B的映射，稱為集合A上的n元運算。如果BA，則稱該n元運算在A上封閉。

如AAB稱為集A上的一個二元運算，若BS,，稱該運算是封閉的。例1：R上求一個數(shù)的相反數(shù)是一元運算，非0實數(shù)集上求倒數(shù)為一元運算，空間上點(x,y,z)投影到x軸為三元運算。

例2：判定下列在給定集上的二元運算的封閉性：

1）自然數(shù)集N上乘法，除法。

2）整數(shù)集Z上的加法，減法，乘法，除法。

3）非零實數(shù)集上加法，減法，乘法，除法。

4）S為任意集，S的冪集P（S）上，，，運算。*通常用о，*，?，等表示二元運算

9第九頁，共十五頁，編輯于2023年，星期一二．代數(shù)系統(tǒng)

定義5-1.2

一個非空集合A連同若干個定義在該集合上的運算

f1，f2，…，fk

所組成的系統(tǒng)稱為一個代數(shù)系統(tǒng)，記作<A，f1，f2，…，fk>。例如：（1）正整數(shù)集I＋及定義在該集合上的普通加法“＋”組成一個代數(shù)系統(tǒng)＜I＋，＋＞（2）有限集S上冪集及其上運算，，組成代數(shù)系統(tǒng)

<P(S),，，

>.10第十頁，共十五頁，編輯于2023年，星期一二．代數(shù)系統(tǒng)

定義5-1.2’

代數(shù)結(jié)構(gòu)是由以下三個部分組成的數(shù)學結(jié)構(gòu)：（1）非空集合S，稱為代數(shù)結(jié)構(gòu)的載體。（2）載體S上的若干運算。（3）一組刻劃載體上各運算所滿足性質(zhì)的公理。*代數(shù)結(jié)構(gòu)常用一個多元序組<S，，，…>來表示，其中S是載體，、、…為各種運算。有時為了強調(diào)S有某些元素地位特殊，也可將它們列入這種多元序組的末尾。雖然代數(shù)系統(tǒng)具有不同的形式，但它們之間可能有一些共同的運算規(guī)律。11第十一頁，共十五頁，編輯于2023年，星期一二．代數(shù)系統(tǒng)

例如，考察代數(shù)系統(tǒng)＜I，+＞。很明顯，在這個代數(shù)系統(tǒng)中，關于加法運算，具有以下三個運算規(guī)律，即對于任意的x，ｙ，ｚ∈I，有：

(1)x+y∈I(封閉性）

(2)x+y=y+x(交換律)(3)(x+y)+z=x+(y+z)（結(jié)合律）又如，設S是集合，P（S）是S的冪集，則代數(shù)系統(tǒng)＜P（S），∪＞和＜P（S），∩＞中的∪、∩都適合交換律，結(jié)合律，即他們與＜I，+＞有類似的運算性質(zhì)。12第十二頁，共十五頁，編輯于2023年，星期一由前例可看出，雖然集合不同，運算不同，但是它們是一些具有共同運算規(guī)律的運算，研究<I，+>就相當于研究<P(S)，∪>，<P(S