離散數(shù)學代數(shù)結構.ppt

1,代數(shù)結構,2,代數(shù)結構部分,第5章 代數(shù)系統(tǒng)的一般性質 第6章 幾個典型的代數(shù)系統(tǒng),3,第5章 代數(shù)系統(tǒng)的一般性質,5.1 二元運算及其性質 5.2 代數(shù)系統(tǒng)及其子代數(shù)和積代數(shù) 5.3 代數(shù)系統(tǒng)的同態(tài)與同構,4,5.1 二元運算及其性質,二元運算定義及其實例 一元運算定義及其實例 運算的表示 二元運算的性質 交換律、結合律、冪等律、消去律 分配律、吸收律 二元運算的特異元素 單位元 零元 可逆元素及其逆元,5,二元運算的定義及其實例,定義 設 S 為集合,函數(shù) f：SSS 稱為 S 上的二元運算, 簡稱為二元運算. 也稱 S 對 f 封閉. (1)保證參加運算的可以是S 中任意兩個元素； (2)運算的結果也是S中的一個元素 例1 (1) N 上的二元運算：加法、乘法. f：NNN, f()=x+y (2) Z 上的二元運算：加法、減法、乘法. (3) 非零實數(shù)集 R* 上的二元運算: 乘法、除法. (4) 設 S = a1, a2, , an, ai aj = ai ， 為 S 上二 元運算.,6,二元運算的實例（續(xù)）,(5) 設 Mn(R) 表示所有 n 階 (n2) 實矩陣的集 合，即 矩陣加法和乘法都是 Mn(R) 上的二元運算. (6) 冪集 P(S) 上的二元運算：, . (7) SS 為 S 上的所有函數(shù)的集合：合成運算.,7,一元運算的定義與實例,定義 設 S 為集合，函數(shù) f：SS 稱為 S 上的一元運算，簡稱為一元運算. 例2 (1) Z, Q 和 R 上的一元運算: 求相反數(shù) (2) 非零有理數(shù)集 Q*，非零實數(shù)集 R*上的一元 運算: 求倒數(shù) (3) 復數(shù)集合 C 上的一元運算: 求共軛復數(shù) (4) 冪集 P(S) 上, 全集為 S: 求絕對補運算 (5) A 為 S 上所有雙射函數(shù)的集合，ASS: 求反 函數(shù) (6) 在 Mn(R) ( n2 )上，求轉置矩陣,8,二元與一元運算的表示,算符：, , , , 等符號 表示二元或一元運算 對二元運算 ，如果 x 與 y 運算得到 z，記做 xy = z； 對一元運算 , x 的運算結果記作 x 表示二元或一元運算的方法： 公式、 運算表 注意：在同一問題中不同的運算使用不同的算符,9,公式表示 例3 設 R 為實數(shù)集合，如下定義 R 上的二元運算 ： x, yR, x y = x. 那么 3 4 = 3 0.5 (-3) = 0.5 運算表（表示有窮集上的一元和二元運算）,二元與一元運算的表示（續(xù)）,10,運算表的形式,11,運算表的實例,例4 A = P(a, b), , 分別為對稱差和絕對補運算 （a,b為全集） 的運算表 的運算表,12,運算表的實例（續(xù)）,例5 Z5 = 0, 1, 2, 3, 4 , , 分別為模 5 加法與乘法 的運算表 的運算表,13,二元運算的性質,定義 設 為 S 上的二元運算, (1) 如果對于任意的 x, y S 有 x y = y x, 則稱運算在 S 上滿足交換律. (2) 如果對于任意的 x, y, z S 有 (x y) z = x (y z), 則稱運算在 S 上滿足結合律. (3) 如果對于任意的 x S 有 x x = x, 則稱運算在 S 上滿足冪等律. S 中的全體元素都是冪等元,14,實例分析,Z, Q, R分別為整數(shù)、有理數(shù)、實數(shù)集；Mn(R)為 n 階實矩陣集合, n2；P(B)為冪集；AA 為 A上A，|A|2.,15,二元運算的性質（續(xù)）,定義 設 和 為 S 上兩個不同的二元運算, (1) 如果 x, y, zS 有 (x y) z = (x z) (y z) z (x y) = (z x) (z y) 則稱 運算對 運算滿足分配律. (2) 如果 和 都可交換, 并且 x, yS 有 x (x y) = x x (x y) = x 則稱 和 運算滿足吸收律.,16,實例分析,Z, Q, R分別為整數(shù)、有理數(shù)、實數(shù)集；Mn(R) 為 n 階實矩陣集合, n2；P(B)為冪集；AA為 A上A，|A|2.,17,二元運算的特異元素,單位元 定義 設為S上的二元運算, 如果存在el（或er）S，使得對任意 xS 都有 el x = x ( 或 x er = x )， 則稱 el ( 或 er )是 S 中關于 運算的 左 ( 或右 )幺元元. 若 eS 關于 運算既是左單位元又是右單位元，則稱 e 為 S 上關于 運算的 幺元. 例：N上加法的幺元是0，乘法的幺元是1 Mn(R)上加法的么元是0矩陣，乘法的幺元是單位陣 P(S)上的么元是 ， 的幺元是S,18,例：R*是非零實數(shù)集，是R*上的二元運算 R*任意a,b, 有a ba 則運算不存在左幺元，存在無數(shù)個右幺元， 因此不存在幺元 定理 設 為S上的二元運算，el 和 er 分別為 S 中關于運算的左和右幺元，則 el = er = e 為 S 上關于 運算的惟一的幺元. 證 el = el er = el er = er 所以 el = er , 將這個幺元記作 e. 假設 e 也是 S 中的幺元，則有 e = e e = e. 惟一性得證.,19,二元運算的特異元素（續(xù)）,零元 設 為 S 上的二元運算, 如果存在l（或r）S，使得對任意 xS 都有 l x =l ( 或 x r =r )， 則稱l ( 或r )是 S 中關于 運算的 左 ( 或右) 零元. 若S關于運算既是左零元又是右零元，則稱為 S 上關于運算 的 零元. 類似地可以證明關于零元的惟一性定理. 例：N上乘法的零元是0，加法沒有零元 Mn(R)上乘法的零元是0矩陣，加法沒有零元 P(S)上的零元是S ， 的零元是,20,二元運算的特異元素（續(xù)）,可逆元素及其逆元 令 e 為 S 中關于運算的幺元. 對于 xS，如果存在yl（或 yr）S 使得 yl x = e（或 x yr = e）， 則稱 yl ( 或 yr )是 x 的 左逆元 ( 或右逆元 ). 關于 運算，若 yS 既是 x 的左逆元又是 x 的右逆元，則稱 y 為 x 的逆元. 如果 x 的逆元存在，就稱 x 是可逆的. 例：N上加法運算，只有0有逆元，為0 Z上加法運算，任何整數(shù)都存在逆元，為其相反數(shù) Mn(R)上乘法，只有可逆矩陣存在逆元，為其逆矩陣 P(S)上運算，只有存在逆元，為,21,實例分析,22,小結： 對于給定的集合和二元運算，幺元、零元、逆元不同。 如果幺元和零元存在，一定是唯一的。 逆元是與集合中的某個元素相關的，有的元素有逆元，有的元素沒有逆元，不同的元素對應不同的逆元。 注意：當 |S| = 1 時，這個元素既是單位元 也是零元.,23,惟一性定理（續(xù)）,定理 設 為 S 上可結合的二元運算, e 為該運算的幺元, 對于 xS 如果存在左逆元 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 的逆元. 假若 yS 也是 x 的逆元, 則 y= y e = y (x y) = (y x) y = e y = y 所以 y 是 x 惟一的逆元. 說明：對于可結合的二元運算，可逆元素 x 只有惟一的逆元，記作 x1.,24,消去律,定義 設為V上二元運算，如果 x, y, zV， 若 x y = x z，且 x不是零元，則 y = z 若 y x = z x, 且 x 不是零元，則 y = z 那么稱 運算滿足 消去律. 實例: Z, Q, R 關于普通加法和乘法滿足消去律. Mn(R) 關于矩陣加法滿足消去律 冪集P(S)上滿足消去律 Zn關于模 n 加法滿足消去律，當 n 為素數(shù)時關于 模 n乘法滿足消去律. 當 n 為合數(shù)時關于模 n 乘 法不滿足消去律.,25,例題分析,解 (1) 運算可交換，可結合. 任取x, yQ, x y = x+y+2xy = y+x+2yx = y x, 任取x, y, zQ, (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 設 運算為 Q 上的二元運算， x, yQ, xy = x+y+2xy, (1) 運算是否滿足交換和結合律? 說明理由. (2) 求 運算的幺元、零元和所有可逆元.,26,給定 x，設 x 的逆元為 y, 則有 x y = 0 成立，即 x+y+2xy = 0 (x = 1/2) 因此當 x 1/2時， 是 x 的逆元.,例題分析（續(xù)）,(2) 設運算的幺元和零元分別為 e 和 ，則對于任意 x 有 xe = x 成立，即 x+e+2xe = x e = 0 由于 運算可交換，所以 0 是幺元.,對于任意 x 有 x = 成立，即 x+2 x = x + 2 x = 0 = 1/2,27,例題分析（續(xù)）,例7 (1) 說明那些運算是交換的、可結合的、冪等的. (2) 求出運算的幺元、零元、所有可逆元素的逆元.,解 (1) 滿足交換、結合律； 滿足結合、冪等律； 滿足交換、結合律.,(2) 的幺元為 b, 沒零元， a1 = c, b1 = b, c1 = a 的幺元和零元都不存在，沒有可逆元素. 的幺元為 a，零元為c, a1=a. b, c不可逆.,28,例題分析（續(xù)）,例8 設 A = a, b, c , 構造 A 上的二元運算* 使得 a*b =c, c*b = b, 且*運算是冪等的、可交換的，給出關于*運算的一個運算表，說明它是否可結合，為什么？,c,b,根據冪等律和已知條件a*b =c, c*b = b 得到運算表,根據交換律得到新的運算表,方框 可以填入a, b, c中任一選定的符號,完成運算表,不結合，因為 (a*b)*b = c*b = b, a*(b*b) = a*b = c,2