離散數(shù)學(xué).環(huán)與域

1、1第1頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五環(huán)的定義定義 設(shè)是代數(shù)系統(tǒng)，+和是二元運(yùn)算. 如果滿足以下條件:（1）構(gòu)成交換群（2）構(gòu)成半群（3）運(yùn)算關(guān)于+運(yùn)算適合分配律則稱是一個(gè)環(huán).2第2頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五環(huán)中的術(shù)語通常稱+運(yùn)算為環(huán)中的加法， 運(yùn)算為環(huán)中的乘法.環(huán)中加法幺元記作 0.乘法幺元（如果存在）記作 1. 環(huán)中加法幺元0恰好是乘法的零元.對(duì)任何元素 x，稱 x 的加法逆元為負(fù)元，記作x. 若 x 存在乘法逆元的話，則稱之為逆元，記作 x1. 3第3頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五環(huán)的實(shí)例 (1) 整數(shù)集、有

2、理數(shù)集、實(shí)數(shù)集和復(fù)數(shù)集關(guān)于普通的加法和乘法構(gòu)成環(huán)，分別稱為整數(shù)環(huán)Z，有理數(shù)環(huán)Q，實(shí)數(shù)環(huán)R 和 復(fù)數(shù)環(huán)C.(2) n(n2)階實(shí)矩陣的集合Mn(R)關(guān)于矩陣的加法和乘法構(gòu)成環(huán)，稱為n階實(shí)矩陣環(huán).(3) 集合的冪集P(B)關(guān)于集合的對(duì)稱差運(yùn)算和交運(yùn)算構(gòu)成環(huán).(4) 設(shè)Zn0,1,.,n1，和分別表示模n的加法和乘法，則構(gòu)成環(huán)，稱為模n的整數(shù)環(huán). 4第4頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五特殊的環(huán)定義 設(shè)是環(huán)， (1) 若環(huán)中乘法適合交換律，則稱 R是交換環(huán).(2) 若環(huán)中乘法存在幺元，則稱 R是含幺環(huán).(3) 若a, bR，a b=0 a=0b=0，則稱R是無零因子環(huán).(4)

3、若 R 既是交換環(huán)、含幺環(huán)，也是無零因子環(huán)，則稱 R 是整環(huán). (5) 若 R為整環(huán)，|R|1, 且aR*=R-0，a-1R, 則稱 R 為域. 5第5頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五 零因子的定義與存在條件設(shè)是環(huán)，若存在 ab =0, 且 a0, b0, 稱 a 為左零因子，b為右零因子，環(huán) R 不是無零因子環(huán). 實(shí)例 ，其中 23=0，2 和 3 都是零因子. 無零因子環(huán)的條件：可以證明：ab = 0 a=0 b=0 消去律 6第6頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五特殊環(huán)的實(shí)例(1)整數(shù)環(huán)Z、有理數(shù)環(huán)Q、實(shí)數(shù)環(huán)R、復(fù)數(shù)環(huán)C都是交換環(huán)、含幺環(huán)、無

4、零因子環(huán)和整環(huán). 其中除Z之外都是域(2)令2Z= 2z | zZ ，則構(gòu)成交換環(huán)和無零因子環(huán). 但不是含幺環(huán)和整環(huán).(3)設(shè)nZ, n2, 則 n 階實(shí)矩陣的集合 Mn(R)關(guān)于矩陣加法和乘法構(gòu)成環(huán)，它是含幺環(huán)，但不是交換環(huán)和無零因子環(huán)，也不是整環(huán).(4)構(gòu)成環(huán)，它是交換環(huán)、含幺環(huán)，但不是無零因子環(huán)和整環(huán). 注意：對(duì)于一般的 n, Zn是整環(huán)且是域 n是素?cái)?shù). 7第7頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五例題判斷下列集合和給定運(yùn)算是否構(gòu)成環(huán)、整環(huán)和域. (1) A=a+bi |a,bQ, i2= 1, 運(yùn)算為復(fù)數(shù)加法和乘法. (2) A=2z+1 | zZ, 運(yùn)算為普通加法

5、和乘法 (3) A=2z | zZ, 運(yùn)算為普通加法和乘法 (4) A= x | x0 xZ, 運(yùn)算為普通加法和乘法. (5) ，運(yùn)算為普通加法和乘法解 (2), (4), (5) 不是環(huán). 為什么？ (1) 是環(huán), 是整環(huán), 也是域. (3) 是環(huán), 不是整環(huán)和域. 8第8頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五環(huán)的性質(zhì)定理 設(shè)是環(huán)，則 (1) aR， a0 = 0a = 0(2) a,bR， (a)b = a(b) = ab(3) a,bR， (a)(b) = ab(4) a,b,cR，a(bc) = abac， (bc)a = baca9第9頁(yè)，共38頁(yè)，2022年，5月

6、20日，11點(diǎn)9分，星期五環(huán)中的運(yùn)算環(huán)中加法的交換律、結(jié)合律；乘法的結(jié)合律；乘法對(duì)加法的分配律.例 在環(huán)中計(jì)算 (a+b)3, (ab)2解 (a+b)3 = (a+b)(a+b)(a+b) = (a2+ba+ab+b2)(a+b) = a3+ba2+aba+b2a+a2b+bab+ab2+b3 (ab)2 = (ab)(ab)=a2baab+b2 注：在初等代數(shù)中的加法和乘法運(yùn)算都是在實(shí)數(shù)域中進(jìn)行，乘法可交換10第10頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五6.3 格與布爾代數(shù)格的定義與實(shí)例格的性質(zhì) 對(duì)偶原理 交換律、結(jié)合律、冪等律、吸收律 格的等價(jià)定義 子格 格的同構(gòu) 特殊

7、的格：分配格、有界格、有補(bǔ)格、布爾格 11第11頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五格的定義定義 設(shè)是偏序集，如果x,yS，x,y都有最小上界和最大下界，則稱S關(guān)于偏序構(gòu)成一個(gè)格。 由于最小上界和最大下界的惟一性，可以把求x,y的最小上界和最大下界看成 x 與 y 的二元運(yùn)算和，即 xy 和 xy 分別表示 x 與 y 的最小上界和最大下界. 注意：這里出現(xiàn)的和符號(hào)只代表格中的運(yùn)算，而不再有其他的含義.12第12頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五 格的實(shí)例例 設(shè)n是正整數(shù)，Sn是n的正因子的集合. D為整除關(guān)系，則偏序集構(gòu)成格.x,ySn，xy 是 l

8、cm(x,y)，即 x 與 y 的最小公倍數(shù). xy 是 gcd(x,y)，即 x 與 y 的最大公約數(shù). 下圖給出了格，和.13第13頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五例 判斷下列偏序集是否構(gòu)成格，并說明理由. (1) ，其中P(B)是集合B的冪集. (2) ，其中Z是整數(shù)集，為小于等于關(guān)系. (3) 偏序集的哈斯圖分別在下圖給出.格的實(shí)例（續(xù)）解 (1) 是格. 稱為B的冪集格.(2) 是格. (3) 都不是格. 14第14頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五格的性質(zhì)：對(duì)偶原理定義 設(shè) f 是含有格中元素以及符號(hào)=, , ,和的命題. 令 f*是將

9、 f 中的替換成,替換成,替換成,替換成所得到的命題. 稱 f* 為 f 的對(duì)偶命題. 例如, 在格中： f 是 (ab)cc, f* 是 (ab)cc .格的對(duì)偶原理：設(shè) f 是含格中元素以及符號(hào)=,和等的命題. 若 f 對(duì)一切格為真, 則 f 的對(duì)偶命題 f*也對(duì)一切格為真. 例如, 若對(duì)一切格L都有 a,bL, aba，那么對(duì)一切格L都有 a,bL, aba15第15頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五格的性質(zhì)：算律定理 設(shè)是格,則運(yùn)算和適合交換律、結(jié)合律、冪等律和吸收律,即(1) a,bL 有 ab=ba, ab=ba(2) a,b,cL 有 (ab)c=a(bc)

10、, (ab)c=a(bc)(3) aL 有 aa=a, aa=a(4) a,bL 有 a(ab)=a, a(ab)=a 16第16頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五算律的證明證 (1) 交換律. ab 是 a,b 的最小上界 ba 是 b,a的最小上界 a, b = b, a ab = ba. 由對(duì)偶原理, ab = ba 得證. 17第17頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五算律的證明（續(xù)） (2) 結(jié)合律. 由最小上界的定義有 (ab)caba (I) (ab)cabb (II) (ab)cc (III) 由式 (II) 和 (III) 有 (ab

11、)cbc (IV) 由式 (I) 和 (IV) 有 (ab)ca(bc). 同理可證 (ab)c a(bc). 根據(jù)偏序的反對(duì)稱性得到 (ab)c = a(bc). 由對(duì)偶原理, (ab)c = a(bc) 得證. 18第18頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五算律的證明（續(xù)） (3) 冪等律. 顯然 a aa, 又由 a a 得 aa a. 由反對(duì)稱性 aa = a. 用對(duì)偶原理, aa = a 得證. (4) 吸收律. 顯然有 a(ab) a (V)由 a a, ab a 可得 a(ab) a (VI) 由式 (V) 和 (VI) 可得 a(ab) = a根據(jù)對(duì)偶原理,

12、 a(ab) = a 得證.19第19頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五格作為代數(shù)系統(tǒng)的定義定理 設(shè)是具有兩個(gè)二元運(yùn)算的代數(shù)系統(tǒng), 若對(duì)于和運(yùn)算適合交換律、結(jié)合律、吸收律, 則可以適當(dāng)定義S中的偏序,使得構(gòu)成格, 且a,bS有 ab = ab, ab = a b.根據(jù)定理,可以給出格的另一個(gè)等價(jià)定義.定義 設(shè)是代數(shù)系統(tǒng), 和 是二元運(yùn)算, 如果和 運(yùn)算滿足交換律、結(jié)合律和吸收律, 則構(gòu)成格.20第20頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五子格的定義及判別定義 設(shè)是格, S 是 L 的非空子集, 若 S 關(guān)于L中運(yùn)算和仍構(gòu)成格,則稱S是L 的子格.例 設(shè)格

13、 L 如圖所示. 令 S1= a, e, f, g , S2= a, b, e, g S1不是 L的子格, S2是 L的子格. 因?yàn)閷?duì)于 e, fS1，efS1.21第21頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五格同態(tài)定義 設(shè) L1和 L2是格, f: L1L2, 若a,bL1有 f(ab) = f(a)f(b), f(ab) = f(a)f(b)成立, 則稱 f 為格 L1到 L2的同態(tài)映射, 簡(jiǎn)稱格同態(tài).22第22頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五分配格定義定義 設(shè)是格, 若a, b, cL, 有 a(bc) = (ab)(ac)a(bc) = (ab

14、)(ac)則稱 L 為分配格.注意：以上條件互為充分必要條件這兩個(gè)等式中只要有一條成立，另一條一定成立.在證明L為分配格時(shí), 只須證明其中的一個(gè)等式即可. 23第23頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五分配格的定義（續(xù)）L1和 L2是分配格, L3和 L4不是分配格. 在 L3中, b(cd) = b，(bc)(bd) = a在 L4中, c(bd) = c，(cb)(cd) = d稱 L3為鉆石格, L4為五角格.24第24頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五分配格的判定及其性質(zhì)定理 設(shè) L 是格, 則 L 是分配格當(dāng)且僅當(dāng) L 不含有與鉆石格或五角格

15、同構(gòu)的子格.證明省略.定理 格 L 是分配格當(dāng)且僅當(dāng) a, b, cL, ab=ac且ab=ac b=c.推論 (1) 小于五元的格都是分配格. (2) 任何一條鏈都是分配格.25第25頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五分配格的判定（續(xù)）解 L1, L2和 L3都不是分配格. a, b, c, d, e 是 L1的子格, 并且同構(gòu)于鉆石格； a, b, c, e, f 是 L2的子格, 并且同構(gòu)于五角格； a, c, b, e, f 是 L3的子格, 也同構(gòu)于鉆石格.例 說明圖中的格是否為分配格,為什么？26第26頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五全

16、上界與全下界定義 設(shè)L是格, 若存在 aL 使得 xL 有 a x, 則稱 a 為 L 的全下界；若存在 bL 使得 xL 有 x b, 則稱 b 為 L 的全上界.說明： 格 L 若存在全下界或全上界,一定是惟一的. 一般將格 L 的全下界記為 0, 全上界記為 1.27第27頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五有界格定義及其性質(zhì)定義 設(shè) L是格,若 L存在全下界和全上界, 則稱 L為有界格, 全下界記為0，全上界記為1 . 有界格 L 記為 .注意：有限格 L=a1,a2,an是有界格, a1a2 an是 L 的全下界, a1a2an是全上界. 0是關(guān)于運(yùn)算的零元,運(yùn)算

17、的單位元. 1 是關(guān)于運(yùn)算的零元,運(yùn)算的單位元.對(duì)于涉及有界格的命題, 如果其中含有全下界0或全上界1, 求其對(duì)偶命題時(shí), 必須將0與1互換. 28第28頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五補(bǔ)元的定義定義 設(shè)是有界格, aL, 若存在 bL 使得ab = 0 和 ab =1成立, 則稱 b 是 a 的補(bǔ)元.注意：若 b 是 a 的補(bǔ)元, 那么 a 也是 b 的補(bǔ)元. a 和 b 互為補(bǔ)元. 29第29頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五實(shí)例: 求補(bǔ)元 解：L1中 a, c互補(bǔ), b沒補(bǔ)元. L2中 a, d互補(bǔ), b, c 互補(bǔ). L3中 a,e互補(bǔ),

18、b 的補(bǔ)元是 c和d, c 的補(bǔ)元是 b和d, d 的補(bǔ)元是b和c. L4中的 a,e互補(bǔ), b 的補(bǔ)元是 c和d, c 的補(bǔ)元是b, d 的補(bǔ)元是 b. 30第30頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五有界分配格中補(bǔ)元惟一性定理 設(shè)是有界分配格. 若L中元素 a 存在補(bǔ)元, 則存在惟一的補(bǔ)元.證 假設(shè) b, c 是 a 的補(bǔ)元, 則有 ac = 1, ac = 0, ab = 1, ab = 0 從而得到 ac = ab, ac = ab, 由于L是分配格, b = c.31第31頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五有補(bǔ)格的定義定義 設(shè)是有界格, 若 L

19、 中所有元素都有補(bǔ)元存在, 則稱 L 為有補(bǔ)格. 例如, 下圖中的 L2, L3和 L4是有補(bǔ)格, L1不是有補(bǔ)格. 32第32頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五布爾代數(shù)的定義定義 如果一個(gè)格是有補(bǔ)分配格, 則稱它為布爾格或布爾代數(shù).在布爾代數(shù)中，如果一個(gè)元素存在補(bǔ)元, 則是惟一的. 可以把求補(bǔ)元的運(yùn)算看作是布爾代數(shù)中的一元運(yùn)算.布爾代數(shù)標(biāo)記為, 其中為求補(bǔ)運(yùn)算33第33頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五布爾代數(shù)的實(shí)例例 設(shè) S110= 1, 2, 5, 10, 11, 22, 55, 110 是110的正因子集合. gcd 表示求最大公約數(shù)的運(yùn)算 lcm表示求最小公倍數(shù)的運(yùn)算. 則 是否構(gòu)成布爾代數(shù)？ 34第34頁(yè)，共38頁(yè)，2022年，5月20日，11點(diǎn)9分，星期五布爾代數(shù)的等價(jià)定義定義 設(shè)是代數(shù)系統(tǒng), 和是二元運(yùn)算. 若和運(yùn)算滿足交換律、結(jié)合律、冪等律、吸收律, 即(1) a,bB有ab=ba, ab=ba (2)