離散數(shù)學第4章代數(shù)系統(tǒng).ppt

1 離散數(shù)學 西安交通大學電子與信息工程學院計算機系 2 離散數(shù)學 5 環(huán) 環(huán)的基本概念 環(huán)的基本性質(zhì) 無零因子環(huán)和含零因子環(huán) 整環(huán)與除環(huán) 3 離散數(shù)學 5 環(huán)定義1 環(huán) ring 設 R 是代數(shù)系統(tǒng) 和 是R上的兩個二元運算 若 1 R 是交換群 2 R 是半群 3 對 滿足分配律 對任何a b c R 都有a b c a b a c b c a b a c a 則稱 R 是環(huán) 注 在環(huán)中 由于 R 是群 故關于 有幺元存在 將關于 的么元記為0 稱為環(huán)的零元 在環(huán)中 由于 R 是群 故R中每個元素有逆元 設a R 將a關于 的逆元記為 a 稱為a的負元 且將a b 簡記為a b 4 離散數(shù)學 即在環(huán)中可定義減法運算 在環(huán)中 對于 運算 若有幺元 則記為1或e 在環(huán)中 設a R 若a關于 有逆元 則記為a 1 以后談到環(huán) 只討論 R 2的情況 即不討論一個元素的環(huán) 在環(huán)的定義中 不要求 對 滿足分配律 只要求 對 滿足分配律 例1 I 是環(huán) 我們稱此環(huán)為整數(shù)環(huán) 這里 I是整數(shù)集合 和 是整數(shù)的普通加法運算和普通乘法運算 由前兩節(jié)知 1 I 是交換群 2 I 是半群 3 對 滿足分配律 由算術(shù)知識知整數(shù)乘法對整數(shù)加法滿足分配律 即 a b c I有a b c a b a c 由 的交換律知 對 滿足分配律 由環(huán)的定義知 I 是環(huán) 5 離散數(shù)學 例2 Mn n 是環(huán) 我們稱此環(huán)為矩陣環(huán) 這里 Mn n是n n階實矩陣的全體 與 是矩陣的加法運算和乘法運算 由前兩節(jié)知 1 Mn n 是交換群 2 Mn n 是半群 3 對 滿足分配律 由線性代數(shù)知 矩陣乘法對矩陣加法滿足分配律 即 A B C Mn n 有 A B C A B A C B C A B A C A 由環(huán)的定義知 Mn n 是環(huán) 6 離散數(shù)學 例3 Nm m m 是環(huán) 我們稱此環(huán)為整數(shù)模環(huán) 這里 Nm 0 m 1 m m 1 m m和 m是Nm上的模加運算和模乘運算 由前兩節(jié)知 1 Nm m 是交換群 2 Nm m 是半群 3 m對 m滿足分配律 由于 i m j m k m Nm 有 i m m j m m k m i m m j k modm m i j k modm m i j i k modm m i j modm m m i k modm i m m j m m i m m k m 由 m的交換律知 m對 m滿足分配律 由環(huán)的定義知 Nm m m 是環(huán) 7 離散數(shù)學 例4 2X 是環(huán) 我們稱此環(huán)為X的子集環(huán)這里 X是一個非空集合 2X是X的冪集 是集合的對稱差運算 是集合的交運算 由前兩節(jié)知 1 2X 是交換群 2 2X 是半群 3 對 滿足分配律 由第一章 2定理6 8 知集合的交運算對對稱差運算滿足分配律 即 a b c 2X 有A B C A B A C 由 的交換律知 對 滿足分配律 由環(huán)的定義知 2X 是環(huán) 8 離散數(shù)學 例5 P x 是環(huán) 我們稱此環(huán)為多項式環(huán) 這里 P x 是實系數(shù)多項式的全體 和 是多項式的加法運算和乘法運算 由前兩節(jié)知 1 P x 是交換群 2 P x 是半群 3 對 滿足分配律 由于實數(shù)乘法對實數(shù)加法滿足分配律 故多項式乘法對多項式加法滿足分配律 即 h x p x q x P x 有h x p x q x h x p x h x q x 由 的交換律知 對 滿足分配律 由環(huán)的定義知 P x 是環(huán) 9 離散數(shù)學 定義2 交換環(huán)含幺環(huán)交換含幺環(huán)設 R 是環(huán) 1 若 運算滿足交換律 則我們稱 R 是交換環(huán) 2 若關于 運算有幺元 則我們稱 R 是含幺環(huán) 3 若 運算滿足交換律又關于 運算有幺元 則我們稱 R 是交換含幺環(huán) 10 離散數(shù)學 例8 在前面的例子中 1 整數(shù)環(huán) I 是交換含幺環(huán) 關于 運算的幺元是1 2 矩陣環(huán) Mn n 是含幺環(huán) 但不是交換環(huán) 關于 運算的幺元是單位矩陣E 矩陣乘法沒有交換律 3 整數(shù)模環(huán) Nm m m 是交換含幺環(huán) 關于 m運算的幺元是 1 m 4 X的子集環(huán) 2X 是交換含幺環(huán) 關于 運算的幺元是X 5 多項式環(huán) P x 是交換含幺環(huán) 關于 運算的幺元是零次多項式1 11 離散數(shù)學 定理1 環(huán)的基本性質(zhì)設 R 是環(huán) 則 a b c R 有 1 零元 0 a a 0 0 加法幺元是乘法的零元 2 正負 負正得負 a b a b a b 3 負負得正 a b a b 4 1 a a 1是乘法幺元1的負元 5 1 1 1 1的乘法逆元是其本身 即 1 1 1 6 左分配律 a b c a b a c 乘法對減法的 右分配律 b c a b a c a 乘法對減法的 注 由定理1 1 的結(jié)論知 在環(huán) R 中 關于 運算的幺元就是關于 運算的零元 由于 R 是交換群 故關于 運算的幺元一定存在 因此關于 運算的零元也一定存在 由于在一個代數(shù)系統(tǒng)中 零元是沒有逆元的 因此在環(huán) R 中 R 不能構(gòu)成群 12 離散數(shù)學 證 1 只證a 0 0a 0 a 0 0 a 0 a 0 a 0 a 0 a 0 a 0 a 0 a 0 a 0 結(jié)合律 a 0 0 a 0 分配律 a 0 a 0 0 0 0 a 0 a 0 0 13 離散數(shù)學 2 只證a b a b a b a b 0 a b a b a b a b a b a b a b a b a b 結(jié)合律 a b b a b 分配律 a 0 a b b b 0 0 a b 根據(jù) 1 a 0 0 a b 14 離散數(shù)學 3 a b a b 根據(jù) 2 a b 根據(jù) 2 a b 反身律 4 1 a 1 a 根據(jù) 2 a 5 1 1 1 1 根據(jù) 3 1 6 只證a b c a b a c a b c a b c a b a c 分配律 a b a c 根據(jù) 2 a b a c 15 離散數(shù)學 定義3 含零因子環(huán)無零因子環(huán)設 R 是環(huán) 若在環(huán) R 中 1 a R b R a 0 b 0 a b 0 則稱環(huán) R 是含零因子環(huán) 稱a是環(huán)中的左零因子 稱b是環(huán)中的右零因子 2 a R b R a 0 b 0 a b 0 即環(huán)中無零因子 nonil factor 則稱環(huán) R 是無零因子環(huán) 注 所謂含零因子 就是環(huán)中的兩個元素 它們本身不是關于 運算的零元 但它們的 運算結(jié)果卻是零元 于是就稱此環(huán)為含零因子環(huán) 當一個環(huán)是交換環(huán)時 左零因子也就是右零因子 反之亦然 在這種情況下 左零因子 右零因子統(tǒng)稱為零因子 如果在環(huán)中 不存在滿足上述條件的元素 就稱此環(huán)為無零因子環(huán) 16 離散數(shù)學 例9 整數(shù)環(huán) I 是無零因子環(huán)已知 I 是環(huán) 由于任意兩個不為零的整數(shù)相乘 其積不為零 故由定義3知 I 是無零因子環(huán) 例10 矩陣環(huán) Mn n 是含零因子環(huán)已知 Mn n 是環(huán) n 2 不妨設n 2 于是有即兩個不為零的矩陣相乘其積為零矩陣 由定義3知是 Mn n 含零因子環(huán) 17 離散數(shù)學 例11 整數(shù)模環(huán) Nm m m 當m為素數(shù)時 是無零因子環(huán) 當m不是素數(shù)時 是含零因子環(huán) 1 當m為素數(shù)時 對任意的 i m j m Nm i m 0 m 即i pm j m 0 m 即j qm 從而有i j km 否則 i j km 由m是素數(shù) 則必有m i或m j 于是有i pm或j qm 矛盾 即有 i m m j m i j modm m 0 m即兩個不為零的元素經(jīng)過 m運算后不為零 由定義3知 Nm m m 是無零因子環(huán) 2 當m不是素數(shù)時 必存在著 i m j m Nm i m 0 m j m 0 m 使得m i j 即有 i m m j m i j modm m 0 m即 i m j m是Nm中的零因子 由定義3知 Nm m m 是含零因子環(huán) 18 離散數(shù)學 例12 X的子集環(huán) 2X 是含零因子環(huán)已知 2X 是環(huán) 其零元是空集 設 X 2 任取a b X 且a b 于是有 a b 2X且 a b 使得 a b 即兩個不為零的元素相交后為零元 由定義3知 2X 是含零因子環(huán) 例13 多項式環(huán) P x 是無零因子環(huán)已知 P x 是環(huán) 由于兩個非零多項式相乘其積仍為一非零多項式 由定義3知 P x 是無零因子環(huán) 19 離散數(shù)學 定義4 整環(huán) integraldomain 交換含幺的無零因子環(huán)稱為整環(huán) 注 整環(huán)又稱為整區(qū) 定義4 除環(huán) divisionring 每個非零元都有 乘法 逆元的含幺環(huán)稱為除環(huán) 即 若含幺環(huán) R 滿足 a R a 0 a 1 R 則稱其為除環(huán) 20 離散數(shù)學 例16 在前面的例子中 1 整數(shù)環(huán) I 是整環(huán) 因為整數(shù)環(huán) I 是交換含幺環(huán) 例8 1 又是無零因子環(huán) 例9 但整數(shù)環(huán) I 不是除環(huán) 因為在整數(shù)環(huán) I 中 除幺元1及其負元 1外 其它非零整數(shù)a I a 0 都沒有 乘法 逆元 a 1 1 a I 2 矩陣環(huán) Mn n 不是整環(huán) 因為矩陣環(huán) Mn n 不是交換環(huán) 矩陣的乘法沒有交換律 例8 2 而且還是含零因子環(huán) 例10 矩陣環(huán) Mn n 也不是除環(huán) 因為矩陣環(huán) Mn n 中一些非零矩陣 行列式是零 關于矩陣乘法沒有逆元 逆矩陣 21 離散數(shù)學 3 整數(shù)模環(huán) Nm m m 當m是素數(shù)時是整環(huán) 因為整數(shù)模環(huán) Nm m m 是交換含幺環(huán) 例8 3 并且當m為素數(shù)時 又是無零因子環(huán) 例11 并且也是除環(huán) 見下面注 整數(shù)模環(huán) Nm m m 當m不是素數(shù)時不是整環(huán) 因為整數(shù)模環(huán) Nm m m 當m不是素數(shù)時是含零因子環(huán) 例11 并且也不是除環(huán) 見下面注 4 X的子集環(huán) 2X 不是整環(huán) 因為X的子集環(huán) 2X 是含零因子環(huán) 例12 并且也不是除環(huán) 22 離散數(shù)學 5 多項式環(huán) P x 是整環(huán) 因為多項式環(huán) P x 是交換含幺環(huán) 例8 5 又是無零因子環(huán) 例13 但多項式環(huán) P x 不是除環(huán) 因為有非零多項式ax P x a 0 關于多項式乘法沒有逆元 否則 若ax q x 1 則用比較系數(shù)法 可得q x 0 于是又有ax q x 0 矛盾 注 在下面定理4中 將可證 在有限含幺環(huán)中無零因子 非零元 有逆元 23 離散數(shù)學 定理2 在環(huán) R 中 無零因子 消去律 即 a b c R且a 0 都有a b a c b c b a c a b c 證 先證 a b c R且a 0 a b a c a b a c 0 兩邊同時 上 a c a b c 0 分配律 b c 0 a 0及無零因子 b c次證 用反證法 假設環(huán)中有零因子 因此 必有一對元素a b R a 0且b 0 使得a b 0 但是a 0 0 于是我們有a b a 0 由a 0及消去律可得b 0 這與已知b 0矛盾 這個矛盾說明假設錯誤 環(huán)中無零因子 24 離散數(shù)學 定理3 除環(huán)是含幺的無零因子環(huán) 注 因此 除環(huán)未必是整環(huán) 整環(huán)也未必是除環(huán) 除環(huán)要成為整環(huán) 差乘法交換律 整環(huán)要成為除環(huán) 差 非零元 有乘法逆元 證 除環(huán)是含幺環(huán) 因此只須證環(huán)無零因子即可 假設環(huán)中有零因子a b R a 0且b 0 使得a b 0 則有a b 0 0 b a b b 1 0 b b 1 兩邊同時乘上b 1 因a 0b 0 a 0與a 0矛盾 所以環(huán)中無零因子 25 離散數(shù)學 定理4 在有限含幺環(huán)中 無零因子 非零元 有逆元 證 先證 因環(huán)無零因子 故 運算對R 0 是封閉的 因此 R 0 是代數(shù)系統(tǒng) 于是 在代數(shù)系統(tǒng) R 0 中 因R有限 故對任何r R 0 必有i j N j i 1 j i 1 使得ri rj rj ri rj i ri e ri 指數(shù)律 環(huán)含幺 rj i e 消去律 r 1 rj i 1即 非零元有逆元 次證 同定理3 26 離散數(shù)學 注 關于消去律 無零因子 非零元有逆元之間的關系 見下圖 27 離散數(shù)學 6 域 域的基本概念 有限域 28 離散數(shù)學 6 域定義1 域 field 設 F 是代數(shù)系統(tǒng) 和 是R上的兩個二元運算 若 1 F 是交換群 2 F 0 是交換群 3 對 滿足分配律 對任何a b c F 都有a b c a b a c 則稱 F 是域 注 在域 F 中 由于 F 0 是交換群 以及 a F 0 a a 0 0因此 運算有交換律 所以 對 的分配律只寫一條 29 離散數(shù)學 例1 Q 是域 我們稱為有理數(shù)域 這里 Q是有理數(shù)集 分別是普通的有理數(shù)的加法運算和乘法運算 則 Q 是域 例2 R 是域 我們稱為實數(shù)域 這里 R是實數(shù)集 分別是普通的實數(shù)的加法運算和乘法運算 則 R 是域 例3 C 是域 我們稱為復數(shù)域 這里 C是復數(shù)集 分別是普通的復數(shù)的加法運算和乘法運算 則 C 是域 例4 X1 是域 我們稱為算術(shù)分類域 這里 X1 a b a b Q 分別是普通數(shù)的加法運算和乘法運算 包含性 X1 X1 0 非空性 X1 因0 0 0 X1 X1 0 因1 1 0 X1 0 30 離散數(shù)學 1 X1 是交換群 只須證它是交換群 R 的子群即可 封閉性 a b c d X1 a b c d a c b d X1 有逆元 a b X1 有 a b a b X1 使 a b a b 0 故根據(jù) 6定理14可知 X1 是交換群 R 的子群 因此 X1 是交換群 2 X1 0 是交換群 只須證它是交換群 R 0 的子群即可 封閉性 a b c d X1 0 于是a b至少有一不為零 c d至少有一不為零 從而 a b c d ac 2bd ad bc X1 0 否則ac 2bd 0 ad bc 0 由a b至少有一不為零可反解出c 0 d 0 因為齊次線性方程組 31 離散數(shù)學 否則a b全為零與a b至少有一不為零矛盾 或者全不為零且 a b是有理數(shù) 與其是無理數(shù)矛盾 而這與c d至少有一不為零矛盾 有逆元 a b X1 0 有 a b 1 a b a2 2b2 X1 0 使 a b a b a2 2b2 1 故根據(jù) 6定理14可知 X1 0 是交換群 R 0 的子群 因此 X1 0 是交換群 3 對 滿足分配律 由代數(shù) R 遺傳 所以按定義1知則 X1 是域 注 實際上易證 Xk 都是域 這里Xk a b a b Q 其中pk是第k個素數(shù) 這正是我們?yōu)槭裁捶Q此類域為算術(shù)分類域 32 離散數(shù)學 定理1 可交換的除環(huán)是域 證 除環(huán)是每個非零元都有 乘法 逆元的含幺環(huán) 它與域概念僅差 乘法 交換律 現(xiàn)在正好補齊 所以 可交換的除環(huán)是域 定理2 有限整環(huán)是域 證 整環(huán)是交換含幺的無零因子環(huán) 它與域概念僅差每個非零元都有 乘法 逆元 但在有限環(huán)的情況下 上節(jié)定理4已經(jīng)證明 無零因子 每個非零元都有 乘法 逆元因此 有限整環(huán)是域 例5 在上節(jié)的例子中 參見上節(jié)例16 1 整數(shù)環(huán) I 不是域 因為整數(shù)環(huán) I 雖是整環(huán) 33 離散數(shù)學 但不是有限環(huán) 實際上 它的非零整數(shù)a I a 0 除幺元1及其負元 1外 都沒有 乘法 逆元 a 1 1 a