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

1第1頁，課件共38頁，創(chuàng)作于2023年2月環(huán)的定義定義

設(shè)<R,+,·>是代數(shù)系統(tǒng)，+和·是二元運(yùn)算.如果滿足以下條件:

（1）<R,+>構(gòu)成交換群

（2）<R,·>構(gòu)成半群

（3）·運(yùn)算關(guān)于+運(yùn)算適合分配律則稱<R,+,·>是一個(gè)環(huán).

2第2頁，課件共38頁，創(chuàng)作于2023年2月環(huán)中的術(shù)語通常稱+運(yùn)算為環(huán)中的加法，·運(yùn)算為環(huán)中的乘法.環(huán)中加法幺元記作0.乘法幺元（如果存在）記作1.環(huán)中加法幺元0恰好是乘法的零元.對(duì)任何元素x，稱x的加法逆元為負(fù)元，記作

x.若x存在乘法逆元的話，則稱之為逆元，記作x

1.3第3頁，課件共38頁，創(chuàng)作于2023年2月環(huán)的實(shí)例

(1)整數(shù)集、有理數(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(n≥2)階實(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è)Zn＝{0,1,...,n－1}，

和

分別表示模n的加法和乘法，則<Zn,

,

>構(gòu)成環(huán)，稱為模n的整數(shù)環(huán).

4第4頁，課件共38頁，創(chuàng)作于2023年2月特殊的環(huán)定義

設(shè)<R,+,·>是環(huán)，

(1)若環(huán)中乘法·適合交換律，則稱R是交換環(huán).

(2)若環(huán)中乘法·存在幺元，則稱R是含幺環(huán).

(3)若

a,b∈R，ab=0

a=0∨b=0，則稱R是無零因子環(huán).

(4)若R既是交換環(huán)、含幺環(huán)，也是無零因子環(huán)，則稱R是整環(huán).(5)若R為整環(huán)，|R|>1,且

a

R*=R-{0}，a-1

R,則稱R為域.5第5頁，課件共38頁，創(chuàng)作于2023年2月

零因子的定義與存在條件設(shè)<R,+,>是環(huán)，若存在ab=0,且a0,b0,稱a為左零因子，b為右零因子，環(huán)R不是無零因子環(huán).實(shí)例<Z6,,>，其中23=0，2和3都是零因子.無零因子環(huán)的條件：可以證明：ab=0a=0b=0消去律6第6頁，課件共38頁，創(chuàng)作于2023年2月特殊環(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)、無零因子環(huán)和整環(huán).其中除Z之外都是域(2)令2Z={2z|z∈Z}，則<2Z,+,·>構(gòu)成交換環(huán)和無零因子環(huán).但不是含幺環(huán)和整環(huán).(3)設(shè)n

Z,n

2,則n階實(shí)矩陣的集合Mn(R)關(guān)于矩陣加法和乘法構(gòu)成環(huán)，它是含幺環(huán)，但不是交換環(huán)和無零因子環(huán)，也不是整環(huán).(4)<Z6,

,

>構(gòu)成環(huán)，它是交換環(huán)、含幺環(huán)，但不是無零因子環(huán)和整環(huán).注意：對(duì)于一般的n,Zn是整環(huán)且是域

n是素?cái)?shù).7第7頁，課件共38頁，創(chuàng)作于2023年2月例題判斷下列集合和給定運(yùn)算是否構(gòu)成環(huán)、整環(huán)和域.(1)A={a+bi|a,b

Q},i2=

1,運(yùn)算為復(fù)數(shù)加法和乘法.(2)A={2z+1|z

Z},運(yùn)算為普通加法和乘法

(3)A={2z|z

Z},運(yùn)算為普通加法和乘法

(4)A={x|x≥0∧x

Z},運(yùn)算為普通加法和乘法.(5)，運(yùn)算為普通加法和乘法解(2),(4),(5)不是環(huán).為什么？

(1)是環(huán),是整環(huán),也是域.(3)是環(huán),不是整環(huán)和域.

8第8頁，課件共38頁，創(chuàng)作于2023年2月環(huán)的性質(zhì)定理設(shè)<R,+,·>是環(huán)，則

(1)

a∈R，a·0=0·a=0

(2)

a,b∈R，(

a)b=a(

b)=

ab

(3)

a,b∈R，(

a)(

b)=ab

(4)

a,b,c∈R，a(b

c)=ab

ac，

(b

c)a=ba

ca9第9頁，課件共38頁，創(chuàng)作于2023年2月環(huán)中的運(yùn)算環(huán)中加法的交換律、結(jié)合律；乘法的結(jié)合律；乘法對(duì)加法的分配律.例在環(huán)中計(jì)算(a+b)3,(a

b)2解(a+b)3=(a+b)(a+b)(a+b)

=(a2+ba+ab+b2)(a+b)

=a3+ba2+aba+b2a+a2b+bab+ab2+b3

(a

b)2=(a

b)(a

b)=a2

ba

ab+b2注：在初等代數(shù)中的加法和乘法運(yùn)算都是在實(shí)數(shù)域中進(jìn)行，乘法可交換10第10頁，課件共38頁，創(chuàng)作于2023年2月6.3格與布爾代數(shù)格的定義與實(shí)例格的性質(zhì)對(duì)偶原理交換律、結(jié)合律、冪等律、吸收律格的等價(jià)定義子格格的同構(gòu)特殊的格：分配格、有界格、有補(bǔ)格、布爾格11第11頁，課件共38頁，創(chuàng)作于2023年2月格的定義定義設(shè)<S,?>是偏序集，如果

x,y?S，{x,y}都有最小上界和最大下界，則稱S關(guān)于偏序?構(gòu)成一個(gè)格。

由于最小上界和最大下界的惟一性，可以把求{x,y}的最小上界和最大下界看成x與y的二元運(yùn)算∨和∧，即x∨y和x∧y分別表示x與y的最小上界和最大下界.注意：這里出現(xiàn)的∨和∧符號(hào)只代表格中的運(yùn)算，而不再有其他的含義.

12第12頁，課件共38頁，創(chuàng)作于2023年2月格的實(shí)例例設(shè)n是正整數(shù)，Sn是n的正因子的集合.D為整除關(guān)系，則偏序集<Sn,D>構(gòu)成格.

x,y∈Sn，x∨y是lcm(x,y)，即x與y的最小公倍數(shù).x∧y是gcd(x,y)，即x與y的最大公約數(shù).下圖給出了格<S8,D>，<S6,D>和<S30,D>.13第13頁，課件共38頁，創(chuàng)作于2023年2月例判斷下列偏序集是否構(gòu)成格，并說明理由.(1)<P(B),

>，其中P(B)是集合B的冪集.(2)<Z,≤>，其中Z是整數(shù)集，≤為小于等于關(guān)系.(3)偏序集的哈斯圖分別在下圖給出.格的實(shí)例（續(xù)）解(1)是格.稱<P(B),>為B的冪集格.

(2)是格.

(3)都不是格.14第14頁，課件共38頁，創(chuàng)作于2023年2月格的性質(zhì)：對(duì)偶原理定義設(shè)f是含有格中元素以及符號(hào)=,?,?,∨和∧的命題.令f*是將f中的?替換成?,?替換成?,∨替換成∧,∧替換成∨所得到的命題.稱f*為f的對(duì)偶命題.例如,在格中：f是(a∨b)∧c?c,f*是(a∧b)∨c?c.格的對(duì)偶原理：設(shè)f是含格中元素以及符號(hào)=,?,?,∨和∧等的命題.若f對(duì)一切格為真,則f的對(duì)偶命題f*也對(duì)一切格為真.

例如,若對(duì)一切格L都有

a,b∈L,a∧b?a，那么對(duì)一切格L都有

a,b∈L,a∨b?a

15第15頁，課件共38頁，創(chuàng)作于2023年2月格的性質(zhì)：算律定理設(shè)<L,?>是格,則運(yùn)算∨和∧適合交換律、結(jié)合律、冪等律和吸收律,即

(1)

a,b∈L

有

a∨b=b∨a,a∧b=b∧a

(2)

a,b,c∈L

有

(a∨b)∨c=a∨(b∨c),(a∧b)∧c=a∧(b∧c)

(3)

a∈L

有

a∨a=a,a∧a=a

(4)

a,b∈L

有

a∨(a∧b)=a,a∧(a∨b)=a

16第16頁，課件共38頁，創(chuàng)作于2023年2月算律的證明證(1)交換律.

a∨b是{a,b}的最小上界

b∨a是{b,a}的最小上界

{a,b}={b,a}

a∨b=b∨a.

由對(duì)偶原理,a∧b=b∧a得證.17第17頁，課件共38頁，創(chuàng)作于2023年2月算律的證明（續(xù)）

(2)結(jié)合律.由最小上界的定義有

(a∨b)∨c?a∨b?a(I)(a∨b)∨c?a∨b?b(II)

(a∨b)∨c?c(III)

由式(II)和(III)有

(a∨b)∨c?b∨c(IV)

由式(I)和(IV)有(a∨b)∨c?a∨(b∨c).同理可證

(a∨b)∨c?a∨(b∨c).根據(jù)偏序的反對(duì)稱性得到

(a∨b)∨c=a∨(b∨c).由對(duì)偶原理,(a∧b)∧c=

a∧(b∧c)得證.

18第18頁，課件共38頁，創(chuàng)作于2023年2月算律的證明（續(xù)）

(3)

冪等律.顯然a?a∨a,又由a?a得a∨a?a.由反對(duì)稱性a∨a=a.用對(duì)偶原理,a∧a=a得證.

(4)吸收律.顯然有

a∨(a∧b)?a(V)由a?a,a∧b?a可得

a∨(a∧b)?a(VI)由式(V)和(VI)可得a∨(a∧b)=a根據(jù)對(duì)偶原理,a∧(a∨b)=a得證.19第19頁，課件共38頁，創(chuàng)作于2023年2月格作為代數(shù)系統(tǒng)的定義定理設(shè)<S,?,°>是具有兩個(gè)二元運(yùn)算的代數(shù)系統(tǒng),若對(duì)于?和

運(yùn)算適合交換律、結(jié)合律、吸收律,則可以適當(dāng)定義S中的偏序?,使得<S,?>構(gòu)成格,且

a,b∈S有

a∧b=a?b,a∨b=a

°

b.根據(jù)定理,可以給出格的另一個(gè)等價(jià)定義.

定義設(shè)<S,?,°>是代數(shù)系統(tǒng),?和

°是二元運(yùn)算,如果?和

°

運(yùn)算滿足交換律、結(jié)合律和吸收律,則<S,?,°>構(gòu)成格.20第20頁，課件共38頁，創(chuàng)作于2023年2月子格的定義及判別定義設(shè)<L,∧,∨>是格,S是L的非空子集,若S關(guān)于L中運(yùn)算∧和∨仍構(gòu)成格,則稱S是L的子格.

例設(shè)格L如圖所示.令

S1={a,e,f,g},S2={a,b,e,g}S1不是L的子格,S2是L的子格.因?yàn)閷?duì)于

e,f

S1，e∧f

S1.

21第21頁，課件共38頁，創(chuàng)作于2023年2月格同態(tài)定義設(shè)L1和L2是格,f:L1→L2,若

a,b∈L1有

f(a∧b)=f(a)∧f(b),f(a∨b)=f(a)∨f(b)成立,則稱f為格L1到L2的同態(tài)映射,簡(jiǎn)稱格同態(tài).

22第22頁，課件共38頁，創(chuàng)作于2023年2月分配格定義定義設(shè)<L,∧,∨>是格,若

a,b,c∈L,有

a∧(b∨c)=(a∧b)∨(a∧c)

a∨(b∧c)=(a∨b)∧(a∨c)則稱L為分配格.注意：以上條件互為充分必要條件這兩個(gè)等式中只要有一條成立，另一條一定成立.在證明L為分配格時(shí),只須證明其中的一個(gè)等式即可.23第23頁，課件共38頁，創(chuàng)作于2023年2月分配格的定義（續(xù)）L1和L2是分配格,L3和L4不是分配格.在L3中,b∧(c∨d)=b，(b∧c)∨(b∧d)=a

在L4中,c∨(b∧d)=c，(c∨b)∧(c∨d)=d

稱L3為鉆石格,L4為五角格.24第24頁，課件共38頁，創(chuàng)作于2023年2月分配格的判定及其性質(zhì)定理設(shè)L是格,則L是分配格當(dāng)且僅當(dāng)L不含有與鉆石格或五角格同構(gòu)的子格.

證明省略.定理格L是分配格當(dāng)且僅當(dāng)

a,b,c∈L,

a∧b=a∧c且a∨b=a∨c

b=c.

推論

(1)小于五元的格都是分配格.

(2)任何一條鏈都是分配格.

25第25頁，課件共38頁，創(chuàng)作于2023年2月分配格的判定（續(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頁，課件共38頁，創(chuàng)作于2023年2月全上界與全下界定義設(shè)L是格,若存在a∈L使得

x∈L有a?x,則稱a為L的全下界；若存在b∈L使得

x∈L有x?b,則稱b為L的全上界.

說明：格L若存在全下界或全上界,一定是惟一的.

一般將格L的全下界記為0,全上界記為1.

27第27頁，課件共38頁，創(chuàng)作于2023年2月有界格定義及其性質(zhì)定義設(shè)L是格,若L存在全下界和全上界,則稱L為有界格,全下界記為0，全上界記為1.有界格L記為<L,∧,∨,0,1>.注意：有限格L={a1,a2,…,an}是有界格,a1∧a2∧…∧an是L的全下界,a1∨a2∨…∨an是全上界.0是關(guān)于∧運(yùn)算的零元,∨運(yùn)算的單位元.1是關(guān)于∨運(yùn)算的零元,∧運(yùn)算的單位元.

對(duì)于涉及有界格的命題,如果其中含有全下界0或全上界1,求其對(duì)偶命題時(shí),必須將0與1互換.28第28頁，課件共38頁，創(chuàng)作于2023年2月補(bǔ)元的定義定義設(shè)<L,∧,∨,0,1>是有界格,a∈L,若存在b∈L

使得

a∧b=0和a∨b=1成立,則稱b是a的補(bǔ)元.

注意：若b是a的補(bǔ)元,那么a也是b的補(bǔ)元.a和b互為補(bǔ)元.29第29頁，課件共38頁，創(chuàng)作于2023年2月實(shí)例:求補(bǔ)元解：L1中a,c互補(bǔ),b沒補(bǔ)元.

L2中a,d互補(bǔ),b,c

互補(bǔ).

L3中a,e互補(bǔ),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頁，課件共38頁，創(chuàng)作于2023年2月有界分配格中補(bǔ)元惟一性定理設(shè)<L,∧,∨,0,1>是有界分配格.若L中元素a存在補(bǔ)元,則存在惟一的補(bǔ)元.

證假設(shè)b,c是a的補(bǔ)元,則有

a∨c=1,a∧c=0,

a∨b=1,a∧b=0從而得到a∨c=a∨b,a∧c=a∧b,由于L是分配格,b=c.31第31頁，課件共38頁，創(chuàng)作于2023年2月有補(bǔ)格的定義定義設(shè)<L,∧,∨,0,1>是有界格,若L中所有元素都有補(bǔ)元存在,則稱L為有補(bǔ)格.例如,下圖中的L2,L3和L4是有補(bǔ)格,L1不是有補(bǔ)格.

32第32頁，課件共38頁，創(chuàng)作于2023年2月布爾代數(shù)的定義定義

如果一個(gè)格是有補(bǔ)分配格,則稱它為布爾格或布爾代數(shù).在布爾代數(shù)中，如果一個(gè)元素存在補(bǔ)元,則是惟一的.可以把求補(bǔ)元的運(yùn)算看作是布爾代數(shù)中的一元運(yùn)算.布爾代數(shù)標(biāo)記為<B,∧,∨,’,0,1>,其中’為求補(bǔ)運(yùn)算33第33頁，課件共38頁，創(chuàng)作于2023年2月布爾代數(shù)的實(shí)例例設(shè)S110={1,2,5,10,11,22,55,110}是110的正因子集合.gcd表示求最大公約數(shù)的運(yùn)算

lcm表示求最小公倍數(shù)的運(yùn)算.則<S110,gcd,lcm>是否構(gòu)成布爾代數(shù)？

34第34頁，課件共38頁，創(chuàng)作于2023年2月布爾代數(shù)的等價(jià)定義定義設(shè)<B,?,°>是代數(shù)系統(tǒng),?和°是二元運(yùn)算.若?和°運(yùn)算滿足交換律、結(jié)合律、冪等律、吸收律,即

(1)

a,b∈B有a?b=b?a,a°b=b°a

(2)

a,b,c∈B有

a?(b°c)=(a?b)°(a?c),

a°(b?c)=(a°b)?(