數(shù)字電路課件

1、第三篇 代數(shù)系統(tǒng)1代數(shù)系統(tǒng)簡介人們研究和考察現(xiàn)實(shí)世界中的各種現(xiàn)象或過程，往往要借助于一些數(shù)學(xué)工具。這些現(xiàn)象或過程，就是我們的研究對象。描述時(shí)，需要建立適當(dāng)?shù)哪Ｐ?。從物理學(xué)角度考慮，就是建立該模型的運(yùn)動方程（這通常由微分方程表述，反映的是研究對象的運(yùn)動規(guī)律）。從數(shù)學(xué)角度考慮，需要建立合適的數(shù)學(xué)描述語言，或適當(dāng)?shù)臄?shù)學(xué)結(jié)構(gòu)，可以較為準(zhǔn)確地描述研究對象。 2代數(shù)系統(tǒng)簡介合適的數(shù)學(xué)結(jié)構(gòu)相當(dāng)重要。在微積分中，可以用導(dǎo)數(shù)描述質(zhì)點(diǎn)運(yùn)動的速度，可以用定積分來計(jì)算面積、體積等；在代數(shù)學(xué)中，可以用正整數(shù)集合上的加法運(yùn)算來描述工廠產(chǎn)品的累計(jì)數(shù)，用集合之間的“交”、“并”運(yùn)算來描述人和人之間的關(guān)系等。 3代數(shù)系統(tǒng)簡介我

2、們要研究的是一類特殊的數(shù)學(xué)結(jié)構(gòu)由集合上定義若干個運(yùn)算而組成的系統(tǒng)。稱為代數(shù)系統(tǒng)。4代數(shù)系統(tǒng)簡介代數(shù)系統(tǒng)的一般形式是：（A, f1, f2, , fn）。其中A是一個非空集合，f1, f2, , fn是定義在A上的運(yùn)算（close）。fi可以是一元運(yùn)算（unitary operation）、二元運(yùn)算（binary operation）、三元運(yùn)算等，即n-元運(yùn)算（n-nary operation）。5代數(shù)系統(tǒng)簡介我們將要討論的數(shù)學(xué)結(jié)構(gòu)包括：群（group，涉及到對稱性，symmetry）、環(huán)（ring）和域（field）、格（lattice，涉及到布爾代數(shù)，Boolean algebra）。實(shí)際上

3、，我們已學(xué)過一些代數(shù)結(jié)構(gòu)，如:, 等。N: set of natural number, R: set of real number, -: negation.6代數(shù)系統(tǒng)代數(shù)系統(tǒng)的運(yùn)算（運(yùn)算表）和性質(zhì) 代數(shù)系統(tǒng)之間的關(guān)系：同態(tài)和同構(gòu)典型的代數(shù)系統(tǒng)：廣群，半群，含幺半群（獨(dú)異點(diǎn)），群，環(huán)與域布爾代數(shù)7框架8引言代數(shù)系統(tǒng)-由集合上定義若干運(yùn)算而組成的系統(tǒng)：原子命題+5個聯(lián)結(jié)詞二元關(guān)系+關(guān)系的并、交、補(bǔ)、差+關(guān)系復(fù)合、關(guān)系的逆、關(guān)系的閉包代數(shù)結(jié)構(gòu)的主要研究對象就是各種典型的抽象代數(shù)系統(tǒng)這些代數(shù)系統(tǒng)中的運(yùn)算又具有某些性質(zhì)，從而確定了這些代數(shù)系統(tǒng)的數(shù)學(xué)結(jié)構(gòu)。9第五章 代數(shù)結(jié)構(gòu)代數(shù)系統(tǒng)的引入運(yùn)算及其性質(zhì)具

4、有一個二元運(yùn)算的代數(shù)系統(tǒng)半群群同態(tài)與同構(gòu)-兩個同型代數(shù)系統(tǒng)之間的聯(lián)系具有兩個二元運(yùn)算的代數(shù)系統(tǒng)環(huán)域10要求：1.掌握代數(shù)系統(tǒng)的基本概念和運(yùn)算性質(zhì)。2.掌握代數(shù)系統(tǒng)之間的同構(gòu)關(guān)系和同態(tài)關(guān)系，并能夠證明兩個代數(shù)系統(tǒng)是否同構(gòu)或同態(tài)。3.掌握廣群、半群、獨(dú)異點(diǎn)、群等基本的代數(shù)系統(tǒng)的概念 第五章 代數(shù)結(jié)構(gòu)115-1 代數(shù)結(jié)構(gòu)(系統(tǒng))的概念 所謂代數(shù)結(jié)構(gòu)(系統(tǒng))，無非是有一個運(yùn)算對象的集合，和若干個運(yùn)算，構(gòu)成的系統(tǒng)。12 所謂代數(shù)結(jié)構(gòu)(系統(tǒng))，無非是有一個運(yùn)算對象的集合，和若干個運(yùn)算，構(gòu)成的系統(tǒng)。一. n元運(yùn)算 如何定義運(yùn)算,先看幾個我們熟悉的例子：整數(shù)集合I上取相反數(shù)運(yùn)算“-”、集合的補(bǔ)運(yùn)算“” 和N上

5、的“+、” 0。1。2。-1。-2。.。0。-1。-2。1。2.P(E)P(E)a 。b 。a,b 。 。a。b。a,b。0.。1。2。3。.。II可見運(yùn)算“-”、“”、“+” “”就是個映射。N2N+。0.。1。2。3。.。N2N5-1 代數(shù)結(jié)構(gòu)(系統(tǒng))的概念131.定義：設(shè)X是個集合，f:XnY是個映射，則稱f 是X上的n元運(yùn)算。(Xn =XX.X -n個X的笛卡爾積)，如果YX，則稱運(yùn)算f 在X上是封閉的。 f:XY 是個一元運(yùn)算。前面的-、是一元運(yùn)算。 f:X2Y 是個二元運(yùn)算。+是二元運(yùn)算。思考題：下面說法是否正確？ 減法是N上封閉的二元運(yùn)算。 除法是整數(shù) I上的二元運(yùn)算。 除法是實(shí)

6、數(shù) R上的二元運(yùn)算。這里我們主要討論二元運(yùn)算。n個5-1 代數(shù)結(jié)構(gòu)(系統(tǒng))的概念通常用、 、 、+、等表示抽象的二元運(yùn)算。 如果用“”表示二元運(yùn)算f 時(shí)，通常將 f()=z 寫成 xy=z 。142.二元運(yùn)算的運(yùn)算表 有時(shí)用一個表來表示二元運(yùn)算的運(yùn)算規(guī)律。 例如令E=a,b P(E)上的運(yùn)算表如圖所示。 aaaaabbbbba,ba,ba,b上 表 頭 元 素左表頭元素運(yùn)算 從運(yùn)算表除了可以看清運(yùn)算的規(guī)律外，可以很容易地看出運(yùn)算的性質(zhì)。5-1 代數(shù)結(jié)構(gòu)(系統(tǒng))的概念15S R A LS S R A LR R A L SA A L S RL L S R A 再如令X=S,R,A,L其中 S表示開

7、始時(shí)的位置； R表示“向右轉(zhuǎn)”； A表示“向后轉(zhuǎn)”； L表示“向左轉(zhuǎn)”； “”表示轉(zhuǎn)動的復(fù)合運(yùn)算；其運(yùn)算表如圖所示。5-1 代數(shù)結(jié)構(gòu)(系統(tǒng))的概念16二.代數(shù)系統(tǒng)的概念1.代數(shù)系統(tǒng)的定義：X是非空集合，X上的m個運(yùn)算f1,f2,fm, 構(gòu)成代數(shù)系統(tǒng)U,記作U= ( m1) 注意：這m個運(yùn)算f1,f2,fm的元數(shù)可能各不相同, 比如f1是一元運(yùn)算，f2是二元運(yùn)算,fm是k元運(yùn)算。 例如 ，2.有限代數(shù)系統(tǒng)： U= 是個代數(shù)系統(tǒng)，如果X是個有限集合，則稱U是個有限代數(shù)系統(tǒng)。 例如上邊的X=S,R,A,L，是個有限代數(shù)系統(tǒng)。3. 同類型代數(shù)系統(tǒng)：給定兩個代數(shù)系統(tǒng)U= ，V= 如對應(yīng)的運(yùn)算fi和 gi

8、的元數(shù)相同(i=1,2,3,m),則稱U與V是同類型代數(shù)系統(tǒng)。 例如 5-1 代數(shù)結(jié)構(gòu)(系統(tǒng))的概念175-2 運(yùn)算及其性質(zhì)一般的二元運(yùn)算的一些性質(zhì)：封閉性交換律結(jié)合律分配律吸收律等冪律特異元素：單位元（幺元）零元逆元185-2 運(yùn)算及其性質(zhì)一般的二元運(yùn)算的一些性質(zhì)：封閉性交換律結(jié)合律分配律吸收律等冪律19封閉性定義 5-2.1 設(shè)*是定義在A上的二元運(yùn)算，若x，yA，有x*yA，稱*在A上是封閉的。 例如在N上加法+和乘法封閉，而減法不封閉。 從運(yùn)算表可以很容易看出運(yùn)算是否封閉。20封閉性P178 例題1：設(shè)A=xx=2n，nN， 問乘法運(yùn)算是否封閉？對加法運(yùn)算呢？解：對于任意的2r，2s

9、A，r,s N，因?yàn)?r2s = 2r+s A所以乘法運(yùn)算是封閉的。因?yàn)?，22 A，但2+22=6A，所以對于加法運(yùn)算是不封閉的。21交換律定義 5-2.2 設(shè)*是定義在A上的二元運(yùn)算，若x，yA，有x*y=y*x，稱*滿足交換律。（ *是可交換的）大家都知道：加法、乘法、交、并、對稱差是可交換的。22交換律從運(yùn)算表看交換性：是個以主對角線為對稱的表。aaaaabbbbba,ba,ba,bS R A LS S R A LR R A L SA A L S RL L S R A23交換律P179例題2：設(shè)Q是有理數(shù)集，是Q上的二元運(yùn)算，對于任意的a,b Q，a b=a+b-ab ，問是否可交換？

10、解：因?yàn)閍 b=a+b-ab =b+a-ba= b a所以是可交換的。24結(jié)合律定義 5-2.3 設(shè)*是定義在A上的二元運(yùn)算，若 x，y，zA，有x*（y*z）=（x*y）*z，則稱*滿足結(jié)合律（*是可結(jié)合的）可結(jié)合的：數(shù)值的加法、乘法，集合的交、并、對稱差，關(guān)系的復(fù)合、函數(shù)的復(fù)合，命題的合取、析取。是可結(jié)合的運(yùn)算的，元素x的運(yùn)算，通?？梢詫懗沙藘绲男问?。如下： xx=x2 x2x=xx2=x3 xmxn=xm+n (xm)n=xmn思考題：對于加法 +： 13 =( ) 對于乘法： 13 =( )25結(jié)合律P179例題3：設(shè)A是一個非空集合，*是A上的二元運(yùn)算，對于任意的a,b A，有a*b

11、=b，證明*是可結(jié)合運(yùn)算。證明：因?yàn)閷τ谌我獾腶,b,cA (a *b)*c= b*c=c ；a*(b*c)= a*c=c所以(a *b)*c= a *(b*c)即*是可結(jié)合運(yùn)算。26分配律定義 5-2.4 設(shè)*， 是定義在A上的兩個二元運(yùn)算，若 x，y，zA有:x*(yz)= (x*y)(x*z)(yz)*x= (y*x)(z*x) 則稱運(yùn)算*對于運(yùn)算是可分配的。 例如 乘法對加法可分配。 集合的與互相可分配。 命題的與互相可分配。27分配律P179例題4：設(shè)集合A=,，在A上定義兩個二元運(yùn)算*和， 如下表所示。運(yùn)算對于*可分配嗎？運(yùn)算*對于呢？ * 解：容易驗(yàn)證運(yùn)算對于*是可分配的。即x(

12、y*z)=(xy)*(xz)驗(yàn)證如下：當(dāng)x=：x(y*z)= ; (xy)*(xz)=*= 當(dāng)x=：x(y*z)=y*z ; (xy)*(xz)=y*z但是運(yùn)算*對于是不可分配的，因?yàn)?()= *= 而(*)(*)=28吸收律定義 5-2.5 設(shè)*， 是定義在A上的兩個可交換的二元運(yùn)算，若 x，yA有: x*(xy)=x；x(x*y)=x，稱運(yùn)算*和運(yùn)算滿足吸收律。 例如 集合的與滿足吸收律。 命題的與滿足吸收律。 29吸收律P180例題5：設(shè)集合N為自然數(shù)全體，在N上定義兩個二元運(yùn)算，如果對于任意的x,y N ,有x*y=max(x,y);x y=min(x,y)，驗(yàn)證*和的吸收律。解：對于

13、任意的a,bNa*(ab)=max(a,min(a,b)=aa(a*b)=min(a,max(a,b)=a因此*和滿足吸收律。30等冪律定義 5-2.6 設(shè)*是定義在A上的二元運(yùn)算，若xA有:x*x=x，稱運(yùn)算*滿足等冪律（*是等冪的）。從運(yùn)算表看冪等元、冪等性：看主對角線的元素與上表頭(或左表頭)元素相同。請看的運(yùn)算表，有冪等性。aaaaabbbbba,ba,ba,b31等冪律P180例題6：設(shè)(S)是集合S的冪集，在(S)上定義的兩個運(yùn)算，集合的“并”運(yùn)算和集合的“交”運(yùn)算，驗(yàn)證和是等冪的。解：對于任意的A(S),有AA=A,AA=A，因此運(yùn)算和都滿足等冪律。325-2 運(yùn)算及其性質(zhì)特異元

14、素：單位元（幺元）零元逆元33單位元（幺元）定義 5-2.7 設(shè)*是定義在A上的二元運(yùn)算若有一個元素elA,對于任意的xA有:el*x=x，稱el為A中關(guān)于運(yùn)算*的左單位元(左幺元)；若有一個元素erA,對于任意的xA有:x*er=x，稱er為A中關(guān)于運(yùn)算*的右單位元(右幺元)；若A中的一個元素e，關(guān)于*運(yùn)算既是左單位元(左幺元)又是右單位元(右幺元), 即xA有: e*x=x*e=x。則稱e為A中關(guān)于運(yùn)算*的單位元(幺元)。34單位元（幺元）例7：設(shè)集合S=,，在S上定義兩個二元運(yùn)算*和， 如下表所示。指出左幺元或右幺元。 * 解： 和都是S中關(guān)于運(yùn)算*的左幺元，而是S中關(guān)于運(yùn)算的右幺元。3

15、5關(guān)于幺元有下述的唯一性定理定理5-2.1（幺元唯一性定理）設(shè)*是定義在集合A上的一個二元運(yùn)算，且在A中具有關(guān)于運(yùn)算*的左幺元el和右幺元er，則el=er=e，且在A中的幺元是唯一的。證明： 因?yàn)閑l和er分別是A中關(guān)于運(yùn)算*的左幺元和右幺元，所以el = el* er（ er 為右幺元）；el* er =er （ el 為左幺元)，所以el=er,將這個幺元記作e。設(shè)另有一幺元e1 A,則e1=el*e = e。36零元定義 5-2.8 設(shè)*是定義在A上的二元運(yùn)算若有一個元素lA,對于任意的xA有: l*x=l，稱l為A中關(guān)于運(yùn)算*的左零元；若有一個元素rA,對于任意的xA有:x*r=r，

16、稱r為A中關(guān)于運(yùn)算*的右零元；若A中的一個元素，關(guān)于*運(yùn)算既是左零元又是右零元, 即xA有: *x=x*=。則稱為A中關(guān)于運(yùn)算*的零元。37零元例8：設(shè)集合S=淺色,深色，定義在S上的一個二元運(yùn)算*如下表所示，試指出零元和幺元。淺色 深色淺色 淺色 深色深色 深色 深色*解： 深色是S中關(guān)于運(yùn)算*的零元，而淺色是S中關(guān)于運(yùn)算*的幺元。38關(guān)于零元有下述的唯一性定理定理5-2.2 （零元唯一性定理）設(shè)*是定義在集合A上的一個二元運(yùn)算，且在A中具有關(guān)于運(yùn)算*的左零元l和右零元r，則l=r=，且在A中的零元是唯一的。證明類似于定理5-2.1 的證明。39關(guān)于幺元與零元的定理定理5-2.3設(shè)是一個代數(shù)

17、系統(tǒng)，且集合A中的元素個數(shù)大于1。如果該代數(shù)系統(tǒng)中存在幺元e和零元，則e.證明：用反證法。設(shè)=e，那么對于任意的xA,必有x=e*x=*x=e于是,A中所有的元素都是相同的，這與A中含有多個元素相矛盾。這個定理說明：幺元與零元是不同的,除非集合S只有一個元素。在這種情況下,這個唯一的元素既是幺元也是零元。40逆元定義 5-2.8 設(shè)代數(shù)系統(tǒng),*是定義在A上的一個二元運(yùn)算，且e是A中關(guān)于運(yùn)算*的單位元(幺元)。如果對于A中的一個元素a存在著A中的某個元素b，使得b*a=e，那么稱b為a的左逆元；如果a*b=e成立，那么稱b為a的右逆元；如果一個元素b，它既是a的左逆元又是a的右逆元，即 b*a=

18、 a*b=e，那么就稱b是a的一個逆元。很明顯，如果b是a的逆元，那么a也是b的逆元，簡稱a與b互逆。一個元素x的逆元記為x-1.41逆元注：一般地,一個元素的左逆元不一定等于該元素的右逆元。而且，一個元素可以有左逆元而沒有右逆元。甚至一個元素的左(右)逆元還可以不是唯一的。42逆元例9：設(shè)集合S=,，定義在S上的一個二元運(yùn)算*， 如下表所示。指出代數(shù)系統(tǒng)中各個元素的左、右逆元情況。 * 解： 是幺元。有兩個左逆元和；右逆元是的左逆元和右逆元都是，故和 互為逆元；的左逆元是都 而右逆元是；的左逆元為和 ，右逆元為和的右逆元為 ，但沒有左逆元。43關(guān)于逆元有下述的唯一性定理定理5-2.4（逆元唯

19、一性定理）設(shè)是一個代數(shù)系統(tǒng)，*是定義在A上的一個二元運(yùn)算，A中存在幺元e，且每個元素都有左逆元。如果*是可結(jié)合的運(yùn)算，那么，這個代數(shù)系統(tǒng)中的任何一個元素的左逆元必定也是該元素的右逆元，且每個元素的逆元是唯一的。44和是代數(shù)系統(tǒng), , 是二元運(yùn)算：1.封閉性：x,yA, 有 xyA。2.可交換性：x,yA, 有 xy=y x。3.冪等性： xA, 有 xx=x。4. 有幺元： eA, xA，有 ex=xe=x.5.有零元: A,xA，有x=x=.6.可結(jié)合性：x,y,zA, 有 (xy)z =x(yz)。7.有逆元： xA, 有x-1A，使得 x-1x=xx-1=e8.分配律： 對可分配：x,y,zA，有 x(yz)=(xy)(xz) 或 (xy)z =(xz)(yz) 9.吸收律：x,yA，有 x(xy)=x 和 x(xy)=x 對這些性質(zhì)要求會判斷、會證明。 小結(jié)45小結(jié)是一個代數(shù)系統(tǒng)，*是A上的一個二元運(yùn)算,那么該運(yùn)算的有些性質(zhì)可以從運(yùn)算表中直接看出。（1）運(yùn)算*具