1二元運算基本概念和性質(zhì)離散數(shù)學(xué)

1、1/55,這三大類數(shù)學(xué)構(gòu)成了整個數(shù)學(xué)的本體與核心。在這一核心的周圍，由于數(shù)學(xué)通過數(shù)與形這兩個概念，與其它科學(xué)互相滲透，而出現(xiàn)了許多邊緣學(xué)科和交叉學(xué)科。,代數(shù)學(xué)數(shù)學(xué)中研究數(shù)的部分,幾何學(xué)數(shù)學(xué)中研究形的部分,分析學(xué)數(shù)學(xué)中溝通形與數(shù)且涉及極限運算的部分,2/55,代數(shù)學(xué),算術(shù)初等代數(shù)——實數(shù)有理數(shù)無理數(shù)、加減乘除高等代數(shù)——矢量矩陣、線性變換數(shù)論抽象代數(shù)——抽象元素、代數(shù)運算,3/55,抽象代數(shù)系統(tǒng)的應(yīng)用,毫無疑問，沒有抽象代數(shù)

2、結(jié)構(gòu)研究和數(shù)理邏輯研究的先行發(fā)展，圖靈就不可能在1936年提出圖靈機(jī)這樣的代數(shù)結(jié)構(gòu)作為計算的模型。在上世紀(jì)40~50年代，格和布爾代數(shù)成為電子計算機(jī)硬件設(shè)計以及通信系統(tǒng)設(shè)計中的重要工具，而半群理論在自動機(jī)和形式語言研究中發(fā)揮了重要作用。70年代在數(shù)據(jù)庫研究中人們發(fā)現(xiàn)關(guān)系代數(shù)理論能夠作為數(shù)據(jù)庫的理論模型；泛代數(shù)和多類代數(shù)是程序設(shè)計方法學(xué)研究中的有力工具；抽象數(shù)據(jù)類型代數(shù)規(guī)范理論和技術(shù)廣泛應(yīng)用于計算機(jī)軟件形式說明和開發(fā)以及硬件體系

3、結(jié)構(gòu)設(shè)計。,4/55,11.1 代數(shù)運算的基本概念,1.二元運算定義及其實例 一元運算定義及其實例 2.運算的表示 3.二元運算的性質(zhì)交換律、結(jié)合律、冪等律、消去律分配律、吸收律 4.二元運算的特異元素單位元零元可逆元素及其逆元,5/55,代數(shù)運算,定義1：設(shè) A、B、D是三個任意的非空集。 一個A ×B到D 的函數(shù) * ， 叫做一個A 

4、5;B到D的代數(shù)運算。,對A中的任意一個元素a和B中任意一個元素b，即對A ×B中的任意元素(a,b), 存在唯一的d?D，使得 * ((a，b))=d記之為 a*b =d,,6/55,集合A上的代數(shù)運算,定義2 設(shè)A，B是兩個非空集合。 若* 是A×A到B的一個運算， 則稱

5、 * 是集合A上的一個代數(shù)運算或二元運算。,7/55,閉運算,設(shè) * 是A×A到B的一個運算，若B?A，說*是集合A上的閉運算。也說集合A對運算 * 是封閉的。,1、集合A中任意兩個元素可以進(jìn)行該運算；2、運算的結(jié)果仍然屬于集合A,8/55,閉運算的例子,例1 (1) N 上的二元運算：加法、乘法. (2) Z 上的二元運算：加法、減法、乘法.   (3) 非零實數(shù)集 R* 上的二元

6、運算: 乘法、除法. (4) 設(shè) S = { a1, a2, … , an}, ai °aj = ai ， °為 S 上二 元運算.,二元運算的實例（續(xù)）,9,(5) 設(shè) Mn(R) 表示所有 n 階 (n≥2) 實矩陣的集 合，即  矩陣加法和乘法都是 Mn(R) 上的二元運算. (6) 冪集 P(S) 上的二元運算：∪,∩,－, ?.

7、(7) SS 為 S 上的所有函數(shù)的集合：合成運算°.,10,一元運算的定義與實例（補(bǔ)）,定義 設(shè) S 為集合，函數(shù) f：S→S 稱為 S 上的一元運算，簡稱為一元運算. 例2 (1) Z, Q 和 R 上的一元運算: 求相反數(shù) (2) 非零有理數(shù)集 Q*，非零實數(shù)集 R*上的一元 運算:  求倒數(shù) (3) 復(fù)數(shù)集合 C 上的一元運算:  求共軛復(fù)數(shù) (4) 冪集 P(S) 上,

8、全集為 S: 求絕對補(bǔ)運算~  (5) A 為 S 上所有雙射函數(shù)的集合，A?SS: 求反 函數(shù) (6) 在 Mn(R) ( n≥2 )上，求轉(zhuǎn)置矩陣,11,二元與一元運算的表示,算符：°, ?, · , ?, ? 等符號 表示二元或一元運算 對二元運算 °，如果 x 與 y 運算得到 z，記做 x°y = z；

9、 對一元運算 °, x 的運算結(jié)果記作 °x 表示二元或一元運算的方法： 公式、 運算表注意：在同一問題中不同的運算使用不同的算符,12,公式表示 例3 設(shè) R 為實數(shù)集合，如下定義 R 上的二元運算 ?： ?x, y∈R, x ? y = x. 那么 3 ? 4 = 3 0.5 ? (-3) = 0.5運算表（表示有窮集上的一元

10、和二元運算）,二元與一元運算的表示（續(xù)）,13,運算表的形式,14,運算表的實例,例4 A = P({a, b}), ?, ～分別為對稱差和絕對補(bǔ)運算 （{a,b}為全集） ? 的運算表 ～ 的運算表,15,運算表的實例（續(xù)）,例5 Z5 = { 0, 1, 2, 3, 4 }, ?, ? 分別為模 5 加法與乘法

11、 ? 的運算表 ? 的運算表,16,二元運算的性質(zhì),定義 設(shè) ° 為 S 上的二元運算, (1) 如果對于任意的 x, y ?S 有 x ° y = y ° x, 則稱運算在 S 上滿足交換律. (2) 如果對于任意的 x, y, z ∈S 有

12、 (x ° y) ° z = x ° (y ° z), 則稱運算在 S 上滿足結(jié)合律.  (3) 如果對于任意的 x ∈ S 有 x ° x = x, 則稱運算在 S 上滿足冪等律.,17,實例分析,Z, Q, R分別為整數(shù)、有理數(shù)、實數(shù)集；Mn(R)為 n 階實矩陣集合, n?2；P(B)為冪集；AA

13、 為 A上A，|A|?2.,18,二元運算的性質(zhì)（續(xù)）,定義 設(shè) ° 和 ? 為 S 上兩個不同的二元運算, (1) 如果? x, y, z∈S 有 (x ? y) ° z = (x ° z) ? (y ° z) z °(x ? y) = (z ° x) ? (z ° y) 則稱 ° 運算對 ? 運算滿足分配律. (2) 如果°

14、 和 ? 都可交換, 并且? x, y∈S 有 x ° (x ? y) = x x ? (x ° y) = x 則稱 ° 和 ? 運算滿足吸收律.,19,二元運算的特異元素,單位元定義 設(shè)°為S上的二元運算, 如果存在el（或er）?S，使得對任意 x∈S 都有 el ° x = x ( 或 x ° e

15、r = x )，則稱 el ( 或 er )是 S 中關(guān)于 ° 運算的 左 ( 或右 ) 單位元. 若 e∈S 關(guān)于 ° 運算既是左單位元又是右單位元，則稱 e 為 S 上關(guān)于 ° 運算的 單位元. 單位元也叫做 幺元.,20,二元運算的特異元素（續(xù)）,零元設(shè) ° 為 S 上的二元運算, 如果存在θl（或θr）∈S，使得對任意 x∈S 都有 θl ° x =θl ( 或 x °θr =θr )，則

16、稱θl ( 或θr )是 S 中關(guān)于 ° 運算的 左 ( 或右) 零元. 若θ∈S關(guān)于°運算既是左零元又是右零元，則稱θ為 S 上關(guān)于運算 ° 的 零元.,21,二元運算的特異元素（續(xù)）,可逆元素及其逆元 令 e 為 S 中關(guān)于運算°的單位元. 對于 x∈S，如果存在yl（或 yr）∈S 使得 yl ° x = e（或 x ° yr = e），則稱 yl ( 或 yr )是 x 的 左逆元 (

17、或右逆元 ). 關(guān)于 °運算，若 y∈S 既是 x 的左逆元又是 x 的右逆元，則稱 y 為 x 的逆元. 如果 x 的逆元存在，就稱 x 是可逆的.,22,實例分析,el ° x = x,θl ° x =θl,yl ° x = e,23,惟一性定理,定理 設(shè) °為S上的二元運算，el 和 er 分別為 S 中關(guān)于運算的左和右單位元，則 el = er = e 為 S 上關(guān)于 ° 運算的惟一的單位元. 證

18、 el = el ° er = el ° er = er  所以 el = er , 將這個單位元記作 e. 假設(shè) e’ 也是 S 中的單位元，則有 e’ = e ° e’ = e. 惟一性得證.類似地可以證明關(guān)于零元的惟一性定理.注意：當(dāng) |S| ? 2，單位元與零元是不同的； 當(dāng) |S| = 1 時，這個元素既是單位元也是零元.,24,惟一性定理（續(xù)）,定理

19、 設(shè) °為 S 上可結(jié)合的二元運算, e 為該運算的單位元, 對于 x∈S 如果存在左逆元 yl 和右逆元 yr , 則有 yl = yr= y, 且 y 是 x 的惟一的逆元. 證 由 yl ° x = e 和 x ° yr = e 得 yl = yl ° e = yl °(x ° yr) = (yl ° x) ° yr = e ° yr = yr令 yl = yr = y, 則 y 是 x

20、 的逆元. 假若 y’∈S 也是 x 的逆元, 則 y'= y’ ° e = y’ °(x ° y) = (y’ ° x) ° y = e ° y = y所以 y 是 x 惟一的逆元.說明：對于可結(jié)合的二元運算，可逆元素 x 只有惟一的逆元，記作 x?1.,25,消去律,定義 設(shè)°為V上二元運算，如果? x, y, z?V， 若 x ° y = x ° z，且 x不是零元，則 y = z

21、 若 y ° x = z ° x, 且 x 不是零元，則 y = z 那么稱 ° 運算滿足 消去律. 實例: Z, Q, R 關(guān)于普通加法和乘法滿足消去律.Mn(R) 關(guān)于矩陣加法滿足消去律，但是關(guān)于矩陣乘法不滿足消去律.,26,例題分析,解 (1) ° 運算可交換，可結(jié)合. 任取x, y?Q, x ° y = x+y+2xy = y+x+2yx = y ° x, 任

22、取x, y, z?Q, (x ° y) ° z= (x+y+2xy) + z + 2(x+y+2xy) z = x+y+z+2xy+2xz+2yz+4xyz x ° (y ° z) = x + (y+z+2yz) + 2x(y+z+2yz = x+y+z+2xy+2xz+2yz+4xyz,例6 設(shè) ° 運算為 Q

23、 上的二元運算， ?x, y?Q, x°y = x+y+2xy, (1) °運算是否滿足交換和結(jié)合律? 說明理由. (2) 求 ° 運算的單位元、零元和所有可逆元.,27,給定 x，設(shè) x 的逆元為 y, 則有 x ° y = 0 成立，即 x+y+2xy = 0 ? (x ? = ?1/2) 因此當(dāng) x ? ?

24、1/2時， 是 x 的逆元.,,例題分析（續(xù)）,(2) 設(shè)°運算的單位元和零元分別為 e 和 ?，則對于任意 x 有 x°e = x 成立，即 x+e+2xe = x ? e = 0 由于 ° 運算可交換，所以 0 是幺元.,對于任意 x 有 x ° ? = ? 成立，即 x+?+2 x ? = ? ? x + 2 x ? = 0 ? ? = ?1/2,28,例題分析（續(xù)）

25、,例7 (1) 說明那些運算是交換的、可結(jié)合的、冪等的. (2) 求出運算的單位元、零元、所有可逆元素的逆元.,解 (1) ? 滿足交換、結(jié)合律；° 滿足結(jié)合、冪等律； ? 滿足交換、結(jié)合律.,(2) ? 的單位元為 b, 沒零元， a?1 = c, b?1 = b, c?1 = a ° 的單位元和零元都不存在，沒有可逆元素. ? 的單位元為 a，零元為c, a?1=a.

26、 b, c不可逆.,29,由運算表判別算律的一般方法,交換律：運算表關(guān)于主對角線對稱冪等律：主對角線元素排列與表頭順序一致單位元: 所在的行與列的元素排列都與表頭一致零元：元素的行與列都由該元素自身構(gòu)成A 的可逆元：a 所在的行中某列 (比如第 j 列) 元素為 e，且第 j 行 i 列的元素也是 e，那么 a 與第 j 個元素互逆結(jié)合律：除了單位元、零元之外，要對所有3個元素的組合驗證表示結(jié)合律的等式是否成立,30,例

27、題分析（續(xù)）,例8 設(shè) A = { a, b, c }, 構(gòu)造 A 上的二元運算* 使得 a*b =c, c*b = b, 且*運算是冪等的、可交換的，給出關(guān)于*運算的一個運算表，說明它是否可結(jié)合，為什么？,,c,b,?,?,根據(jù)冪等律和已知條件a*b =c, c*b = b 得到運算表,根據(jù)交換律得到新的運算表,方框 ? 可以填入a, b, c中任一選定的符號,完成運算表,不結(jié)合，因為 (a*b)*b = c*b = b, a

28、*(b*b) = a*b = c,小結(jié) 代數(shù)運算的基本概念,31,1.二元運算 （封閉）2.運算的表示 （運算表）3.二元運算的性質(zhì)交換律、結(jié)合律、冪等律、消去律分配律、吸收律4.二元運算的特異元素單位元零元可逆元素及其逆元,32/55,11.2 代數(shù)系統(tǒng)和半群,(一) 代數(shù)系統(tǒng)(二) 同態(tài)映射、同構(gòu)映射(三) 半群(四) 含幺半群(五) 子半群,33/55,例,（N，+）表示自然數(shù)集帶著數(shù)的加法。

29、 （N， ·）表示自然數(shù)集帶著數(shù)的乘法。 （N，－）表示自然數(shù)集和數(shù)的減法運算。（N， +, ·）表示自然數(shù)集帶著數(shù)的加法與乘法。,+是N×N到N的代數(shù)運算,·是N×N到N的代數(shù)運算,－是N×N到Z的代數(shù)運算,34/55,代數(shù)系統(tǒng),定義1 設(shè)A是一個集合，*1，*2，…，*n是A上的n個代數(shù)運算，而（A，*1，*2，…，*n）表示集合A，以及A上的n個代數(shù)運

30、算*1，*2，…，*n組成的一個代數(shù)系統(tǒng)。,主要研究內(nèi)容：只有一個代數(shù)運算的代數(shù)系統(tǒng) （A，*）,35/55,同態(tài)函數(shù),定義2：設(shè)（A，*），（A1，·）是兩個代數(shù)系統(tǒng)， *是A上的一個二元運算， ·是A1上一個二元運算。 一個函數(shù)f：A→A1是A到A1的同態(tài)函數(shù)，若對于A中的任意兩個元素a，b，有

31、 f（a*b）=f（a）·f（b）,■ 若f是單射，說f是單一同態(tài)函數(shù)；■ 若f是滿射，說f是滿同態(tài)函數(shù)；■ 若f是雙射，說f是同構(gòu)函數(shù)。,,36/55,單同態(tài)、滿同態(tài)、同構(gòu),兩個代數(shù)系統(tǒng)之間若存在單一同態(tài)函數(shù)，說這兩個代數(shù)系統(tǒng)是單同態(tài)的；兩個代數(shù)系統(tǒng)之間若存在滿同態(tài)函數(shù)，說這兩個代數(shù)系統(tǒng)是滿同態(tài)的；兩個代數(shù)系統(tǒng)之間若存在同構(gòu)函數(shù)，說這兩個代數(shù)系統(tǒng)是同構(gòu)的。,37/55,例(p176),Z是整數(shù)集，Z上的二元運算是

32、數(shù)的加法，即(Z，＋)。A={1，-1}，A上的二元運算是數(shù)的乘法，即(A，·)。分別定義三個Z到A的函數(shù)如下φ1： Z→A，對于每一個n?Z，φ1(n)=1。φ2： Z→A，對于每一個n?Z，若n是偶數(shù)，φ2(n)=1；若n是奇數(shù)，φ2(n)=-1。φ3： Z→A，對于每一個n?Z，φ3(n)=-1。則 φ1是同態(tài)函數(shù) ， φ2是滿同態(tài)函數(shù)， φ3不是同態(tài)函數(shù)。,38/55,例(p17

33、6),φ1： Z→A={1,-1}，對于每一個n?Z，φ1(n)=1。顯然，對于Z中的任意二個數(shù)n和m，有 φ1(n)=1，φ1(m)=1，φ1(n+m)=1，∴ φ1(n+m)=φ1(n) · φ1(m)故φ1是同態(tài)函數(shù)。,39/55,例(p176),φ2： Z→A，對于每一個n?Z，若n是偶數(shù)，φ2(n)=1；若n是奇數(shù)，φ2(n)=-1。顯然φ2是Z到A的滿射。對于Z中的任

34、意的二個數(shù)n和m來說： 若n和m均是偶數(shù)，那么φ2(n+m)=φ2(n)·φ2(m)。 若n和m均是奇數(shù)，那么φ2(n+m)=φ2(n)·φ2(m)。 若n和m一個奇數(shù)，一個偶數(shù)，不失一般性設(shè)n是奇數(shù)， m是偶數(shù)，那么φ2(n+m)=φ2(n)·φ2(m)。所以φ2是滿同態(tài)映射。即（Z，+）與（A，·）是兩個滿同態(tài)代數(shù)系統(tǒng)。,40/55,例(p177),φ3： Z→A={1，-1}

35、，對于每一個n?Z，φ3(n)=-1。取n=2，m=3時， φ3(n)= φ3(m)=-1， 而 φ3(n+m)= φ3(5)=-1并且有 φ3(n)· φ3(m)=1于是 φ3(n+m) ≠ φ3(n)· φ3(m)所以φ3不是同態(tài)映射。,41/55,例,設(shè)（R， － ）和（R+，÷）是兩個代數(shù)系統(tǒng)，其中R與R+分別為實數(shù)集合、正實數(shù)集合， －與

36、47;分別為算術(shù)減法、除法。證明： （R， － ）和（R+，÷）同構(gòu)。,提示: 作映射 f: R → R+?x?R, f(x)=ex 可以說明, f是同態(tài)的雙射。,42/55,定理1,（A1，*）和（A2，·）是兩個代數(shù)系統(tǒng)，且（A1，*）與（A2，·）滿同態(tài)。若“*”適合交換律，則“·”也適合交換律；若“*”適合結(jié)合律，則“·”也適合結(jié)合律。

37、,43/55,定理1的證明,因為（A1，*）與（A2，·）滿同態(tài)，所以存在f：A1→A2，是滿同態(tài)映射。對于A2中的任意二個元素a2和b2，存在a1和b1屬于A1，有 f(a1)=a2，f(b1)=b2。由*具有交換率，得到：即·適合交換律。,a2·b2 =f(a1) ·f(b1) =f(a1*b1) =f(b1*a1) =f(b1) ·f(a1)

38、=b2·a2。,44/55,定理1的證明(續(xù)),對于A2中的任意三個元素a2，b2和c2，有a1，b1，c1 ? A1，使得 f(a1)=a2，f(b1)=b2，f(c1)=c2。利用*的結(jié)合律有(a2·b2) ·c2=(f(a1) ·f(b1)) ·f(c1) =f(a1*b1) ·f(c1)=f((a1*b1)*

39、c1) =f(a1*(b1*c1))=f(a1) ·f(b1*c1) =a2·(b2·c2)即·適合結(jié)合律。,45/55,半群,定義3：設(shè)（A，*）是一個代數(shù)系統(tǒng)， A是一個非空集， *是A上的一個二元運算。 若*是A上的閉運算，

40、 且*適合結(jié)合律， 則稱（A，*）是一個半群。,46/55,例,（N，－）即自然數(shù)集和數(shù)的減法運算，就不是半群了。 （原因：既可以說是減法不封閉，也可以說是減法不適合結(jié)合律）,（N，+）表示自然數(shù)集帶著數(shù)的加法, 構(gòu)成半群。 （N， ·）表示自然數(shù)集帶著數(shù)的乘法, 構(gòu)成半群。,47/55,例,對于任意二個自然數(shù)m和n，定義“ * ”運算： m*n=m

41、+n+m·n不難驗證，（N，*）也是一個半群。,在自然數(shù)集上還可以定義許多的二元運算，使它們構(gòu)成半群。,48/55,例設(shè)f,g是(A, ?)到(B,*)的同態(tài)映射， 定義一個A到B的映射h，對?a?A，h(a)=f(a)*g(a)， 若(B,*)是一個可交換的半群, 那么h為A到B的同態(tài)映射。,h(a?b) = f(a?b)*g(a?b)

42、 定義 = (f(a)*f(b))*(g(a)*g(b)) 同態(tài) = f(a)*(f(b)*g(a))*g(b) *結(jié)合率 =f(a)*(g(a)*f(b))*g(b) *交換率 =(f(a)*g(a))*(f(b)*g(b))

43、 *結(jié)合率 =h(a)*h(b) 定義∴h為A到B的同態(tài),證明：?a,b?A,,49/55,左幺元、右幺元、幺元,定義4設(shè)（A，*）是一個代數(shù)系統(tǒng)，若存在e右?A，使得對于任意的a?A，有 a*e右=a，說e右是右幺元。若存在e左?A，使得對于任意的a?A，有e左*a=a，說e左是左幺元。一個元素e?A ，它既是

44、左幺元，又是右幺元，稱e是幺元（又稱單位元）。,50/55,例 A={1, 2, 3}, B={a, b}, AB={ f | f: A→B},△A : A→A △B: B→B 1→1 a→a 2→2 b→b 3→3,,,f°△A=f= △B°f,51/55,例 （AB，

45、°） (1) △A是右幺元嗎？ (2) △B是左幺元嗎？,例 （AA，°） △A是幺元,f°△A=f= △B°f,52/55,定理復(fù)習(xí)（關(guān)于二元關(guān)系的性質(zhì)，見教材第98頁）,設(shè) A、B、C、D是四個任意集合，R1、R2、R3分別是從A到B，從B到C，從C到D的二元關(guān)系。則有： ① R1 ?△B = △A ?R1 = R1 ② R1=R1 ③ R1?R2 = R2

46、?R1 ④ (R1 ?R2) ? R3= R1?(R2 ?R3 ),,,,,,關(guān)系復(fù)合記號的 次序≠函數(shù)復(fù)合記號的 次序,53/55,例 A={a,b,c},,* a b ca a b cb b c ac c a b,,,*

47、 a b ca a b bb a b cc a b a,,,◆ a是左幺元◆ a是右幺元◆ a是幺元,■ b是左幺元■ 無右幺元■ 無幺元,,54/55,運算表,二元運算滿足可交換性的充分必要條件是運算表關(guān)于主對角線對稱。 二元運算有左幺元的充分必

48、要條件是該元素對應(yīng)的行與該表表頭的行相一致。二元運算有右幺元的充分必要條件是該元素對應(yīng)的列與該表表頭的列相一致。二元運算有幺元的充分必要條件是該元素對應(yīng)的行和列依次與該表表頭的行、列相一致。,當(dāng)A是有窮集合時，其上的二元運算?？捎眠\算表給出，運算的一些性質(zhì)可直接由運算表看出。,55/55,定理2,設(shè)（A，*）是一個代數(shù)系統(tǒng)，若它既有左幺元，又有右幺元，則左幺元等于右幺元。若有幺元，則幺元唯一。證明：設(shè)e左，e右?A分別是左、右幺元

49、，則有： e左=e左*e右=e右。 若有e1，e2?A ，且均是么元，則也有：e1=e1*e2=e2。,注意： 我們往往用e 表示么元。,56/55,含幺半群,定義5 稱含有幺元的半群為含幺半群。例■ 0是半群（N，+）的么元， （N，+）是含幺半群?！?1是半群（N，·）的么元，（N，·）是含幺半群。,57/55,例 （2A，∪）是一個半群,設(shè)A是一個任意的

50、集合，2A是A的冪集合，集合的并運算∪是2A上的一個二元運算，由第六章集合運算的性質(zhì)知，并運算是2A上的閉運算，且滿足結(jié)合律，所以（2A，∪）是一個半群。顯然， Ø?2A是幺元，即（2A，∪）也是含幺半群。,58/55,子半群,定義6：（A，*）是一個半群，Ø≠B?A， 若（B，*）本身是一個半群， 則稱（B，*）是（A，*）的子半群。,59/55,11.