離散數學.環(huán)與域

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

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

（1）<R,+>構成交換群

（2）<R,·>構成半群

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

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

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

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

(1)整數集、有理數集、實數集和復數集關于普通的加法和乘法構成環(huán)，分別稱為整數環(huán)Z，有理數環(huán)Q，實數環(huán)R和復數環(huán)C.

(2)n(n≥2)階實矩陣的集合Mn(R)關于矩陣的加法和乘法構成環(huán)，稱為n階實矩陣環(huán).(3)集合的冪集P(B)關于集合的對稱差運算和交運算構成環(huán).

(4)設Zn＝{0,1,...,n－1}，

和

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

,

>構成環(huán)，稱為模n的整數環(huán).

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

設<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月

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

Z,n

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

,

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

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

Q},i2=

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

Z},運算為普通加法和乘法

(3)A={2z|z

Z},運算為普通加法和乘法

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

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

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

8第8頁，課件共38頁，創(chuàng)作于2023年2月環(huán)的性質定理設<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)中的運算環(huán)中加法的交換律、結合律；乘法的結合律；乘法對加法的分配律.例在環(huán)中計算(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注：在初等代數中的加法和乘法運算都是在實數域中進行，乘法可交換10第10頁，課件共38頁，創(chuàng)作于2023年2月6.3格與布爾代數格的定義與實例格的性質對偶原理交換律、結合律、冪等律、吸收律格的等價定義子格格的同構特殊的格：分配格、有界格、有補格、布爾格11第11頁，課件共38頁，創(chuàng)作于2023年2月格的定義定義設<S,?>是偏序集，如果

x,y?S，{x,y}都有最小上界和最大下界，則稱S關于偏序?構成一個格。

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

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

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

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

(2)是格.

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

例如,若對一切格L都有

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

a,b∈L,a∨b?a

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

(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.

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

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

(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).根據偏序的反對稱性得到

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

a∧(b∧c)得證.

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

(3)

冪等律.顯然a?a∨a,又由a?a得a∨a?a.由反對稱性a∨a=a.用對偶原理,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根據對偶原理,a∧(a∨b)=a得證.19第19頁，課件共38頁，創(chuàng)作于2023年2月格作為代數系統(tǒng)的定義定理設<S,?,°>是具有兩個二元運算的代數系統(tǒng),若對于?和

運算適合交換律、結合律、吸收律,則可以適當定義S中的偏序?,使得<S,?>構成格,且

a,b∈S有

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

°

b.根據定理,可以給出格的另一個等價定義.

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

°是二元運算,如果?和

°

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

例設格L如圖所示.令

S1={a,e,f,g},S2={a,b,e,g}S1不是L的子格,S2是L的子格.因為對于

e,f

S1，e∧f

S1.

21第21頁，課件共38頁，創(chuàng)作于2023年2月格同態(tài)定義設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)映射,簡稱格同態(tài).

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

a,b,c∈L,有

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

a∨(b∧c)=(a∨b)∧(a∨c)則稱L為分配格.注意：以上條件互為充分必要條件這兩個等式中只要有一條成立，另一條一定成立.在證明L為分配格時,只須證明其中的一個等式即可.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月分配格的判定及其性質定理設L是格,則L是分配格當且僅當L不含有與鉆石格或五角格同構的子格.

證明省略.定理格L是分配格當且僅當

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的子格,并且同構于鉆石格；{a,b,c,e,f}是L2的子格,并且同構于五角格；{a,c,b,e,f}是L3的子格,也同構于鉆石格.例說明圖中的格是否為分配格,為什么？26第26頁，課件共38頁，創(chuàng)作于2023年2月全上界與全下界定義設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月有界格定義及其性質定義設L是格,若L存在全下界和全上界,則稱L為有界格,全下界記為0，全上界記為1.有界格L記為<L,∧,∨,0,1>.注意：有限格L={a1,a2,…,an}是有界格,a1∧a2∧…∧an是L的全下界,a1∨a2∨…∨an是全上界.0是關于∧運算的零元,∨運算的單位元.1是關于∨運算的零元,∧運算的單位元.

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

使得

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

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

L2中a,d互補,b,c

互補.

L3中a,e互補,b的補元是c和d,c的補元是b和d,d的補元是b和c.

L4中的a,e互補,b的補元是c和d,c的補元是b,d的補元是b.30第30頁，課件共38頁，創(chuàng)作于2023年2月有界分配格中補元惟一性定理設<L,∧,∨,0,1>是有界分配格.若L中元素a存在補元,則存在惟一的補元.

證假設b,c是a的補元,則有

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月有補格的定義定義設<L,∧,∨,0,1>是有界格,若L中所有元素都有補元存在,則稱L為有補格.例如,下圖中的L2,L3和L4是有補格,L1不是有補格.

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

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

lcm表示求最小公倍數的運算.則<S110,gcd,lcm>是否構成布爾代數？

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

(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)?(