離散數(shù)學(xué)（第二版） 課件 鄒麗娜 5 二元關(guān)系4

離散數(shù)學(xué)關(guān)系的閉包不自反不對稱不傳遞自反閉包對稱閉包傳遞閉包擴(kuò)充擴(kuò)充擴(kuò)充自反閉包定義自反閉包定義對稱閉包定義練習(xí)：練習(xí)

閉包構(gòu)造(關(guān)系圖法)例：設(shè)集合A={1，2，3，4}，R={<1，2>

，<2，2>

，<2，3>

，<3，4>}是定義在A上的二元關(guān)系。(1)畫出R的關(guān)系圖；(2)求出r(R)，s(R)，t(R)，并畫出其相應(yīng)的關(guān)系圖。關(guān)系上的閉包運(yùn)算解(1)2413關(guān)系上的閉包運(yùn)算r(R)={<1，2>，<2，2>

，<2，3>

，<3，4>

，<1，1>

，

<3，3>，<4，4>}；s(R)={<1，2>

，<2，2>

，<2，3>

，<2，1>

，<3，2>

，

<3，4>

，<4，3>}t(R)={<1，2>

，<2，2>

，<2，3>

，<1，3>

，<3，4>

，

<1，4>

，<2，4>}。r(R)，s(R)，t(R)的關(guān)系圖分別如下：r(R)s(R)t(R)123412341234關(guān)系上的閉包運(yùn)算利用關(guān)系圖求關(guān)系R閉包的方法：(1)檢查R的關(guān)系圖，在沒有自環(huán)的結(jié)點(diǎn)處加上自環(huán)，可得r(R)的關(guān)系圖；(2)檢查R的關(guān)系圖，將每條單向邊全部改成雙向邊，可得s(R)的關(guān)系圖；(3)檢查R的關(guān)系圖，從每個(gè)結(jié)點(diǎn)出發(fā)，找到其終點(diǎn)，如果該結(jié)點(diǎn)到其終點(diǎn)沒有邊相連，就加上此邊，可得t(R)的關(guān)系圖。利用關(guān)系圖求閉包求閉包的公式：對應(yīng)的關(guān)系矩陣：,，練習(xí)：用矩陣法求R的傳遞閉包傳遞閉包t（R）Warshall算法不講等價(jià)關(guān)系與等價(jià)類x～y全域關(guān)系EA和恒等關(guān)系IA是等價(jià)關(guān)系例如A={1,2,3}，則R1={<1,1>,<2,2>,<3,3>,<2,3>,<3,2>}為等價(jià)關(guān)系。等價(jià)關(guān)系與等價(jià)類x,y關(guān)于3同余證明：(1)對

x

A，有x-x可被3整除，所以<x,x>

R，即R是自反的。(2)對

x，y

A，若<x，y>

R，即x-y可被3整除，則y-x亦可被3整除，所以，<y，x>

R，即R是對稱的。(3)對

x，y，z

A，若<x，y>

R且<y，z>

R，有x-y=3m，y-z=3n，則(x-z)=(z-y)+(y-z)=3(m+n)亦可被3整除，所以，<x，z>

R，即R是傳遞的。由(1)、(2)、(3)知，R是A上的等價(jià)關(guān)系。例

設(shè)A={1,2…,8},定義A上的關(guān)系R如下：驗(yàn)證R是A上的等價(jià)關(guān)系。注：一個(gè)等價(jià)類是A中在等價(jià)關(guān)系R下彼此等價(jià)的所有元素的集合，等價(jià)類中各元素的地位是平等的，每個(gè)元素都可以作為其所在等價(jià)類的代表元。xy1471472582583636等價(jià)類的性質(zhì)集合A上的等價(jià)關(guān)系R所構(gòu)成的等價(jià)類，倆倆互不相交，且覆蓋整個(gè)集合A，故它們構(gòu)成A的一個(gè)劃分，而每個(gè)類是這個(gè)劃分的塊。集合的劃分

1

2

m

3…A

={

1，

2，…

m}是A的一個(gè)劃分集合上的等價(jià)關(guān)系導(dǎo)出的集合的劃分例集合的劃分是劃分不是劃分例：給出A＝{1,2,3}上的劃分。123

1

123

5123

2123

4123

3集合的劃分導(dǎo)出集合上的等價(jià)關(guān)系根據(jù)A的劃分求A={1,2,3}上的等價(jià)關(guān)系。

1={{1},{2,3}}；

2={{2},{1,3}};

3={{1,2,3}};

4={{1},{2},{3}}。

R1={<1,1>,<2,2>,<3,3>,<2,3>,<3,2>}R2={<1,1>,<2,2>,<3,3>,<1,3>,<3,1>}全域關(guān)系EA恒等關(guān)系IA練習(xí)偏序關(guān)系R滿足自反的、反對稱的和傳遞的，所以R是一個(gè)偏序關(guān)系其中有也有4與6是不可比的2,4.6,81.集合A上的恒等關(guān)系IA是A上的偏序關(guān)系，但全域關(guān)系EA不是A上的偏序關(guān)系。2.實(shí)數(shù)域上的小于等于關(guān)系（大于等于關(guān)系），自然數(shù)域上的整除關(guān)系，集合的包含關(guān)系等都是偏序關(guān)系。設(shè)A=

1,2,3,4

,試列出下列關(guān)系R的元素。(1)R=

<x,y>

x是y的倍數(shù)

(2)R=

<x,y>

x/y是素?cái)?shù)

(3)R=

<x,y>

x

y

(4)R=

<x,y>

x

y

解:(1)R={<4,4>,<4,2>,<4,1>,<3,3>,<3,1>,<2,2>,<2,1>,<1,1>}(2)R={<2,1>,<3,1>,<4,2>}(3)R={<1,2>,<1,3>,<1,4>,<2,1>,<2,3>,<2,4>,<3,1>,<3,2>,<3,4>,<4,1>,<4,2>,<4,3>}(4)R={<1,2>,<1,3>,<1,4>,<2,3>,<2,4>,<3,4>}偏序集偏序集一個(gè)集合A和A上的一個(gè)偏序關(guān)系共同組成的二元結(jié)構(gòu)稱為偏序集，記為<A,?>。實(shí)際上，偏序集就是把一個(gè)集合及該集合上的一個(gè)偏序關(guān)系打包成一個(gè)整體，它同時(shí)展現(xiàn)了一個(gè)集合和一個(gè)關(guān)系。例設(shè)A={1,2,3}?

是A上的整除關(guān)系，則：1?2,1?3,1＝1,2＝2,3＝3，

2和3不可比；(2)?是A上的大于等于關(guān)系，則:2?1,3?1,3?2,1＝1,2＝2，3＝3。

(1)每個(gè)x,y

A,x?y當(dāng)且僅當(dāng)x?y且x≠y

(2)每個(gè)x,y

A,x與y可比當(dāng)且僅當(dāng)x?y或y?x例：大于等于關(guān)系（小于等于關(guān)系）是全序集，但整除關(guān)系一般不是全序集。全序關(guān)系：設(shè)R為非空集合A上的偏序關(guān)系，如果每個(gè)x,y

A,x與y都是可比的，則稱R為A上的全序（線序）關(guān)系。全序關(guān)系偏序關(guān)系的哈斯圖

4、6是2的覆蓋，但8不是2的覆蓋。

A={1,2,4,6}上的整除關(guān)系有2覆蓋1，4和6都覆蓋2，但4不覆蓋1，6不覆蓋4。利用偏序關(guān)系的自反性、反對稱性和傳遞性可簡化偏序關(guān)系的關(guān)系圖，得到偏序集的哈斯圖。例：集合X={2，3，6，12，24，36}上的整除關(guān)系R是偏序的，它可用哈斯圖表示。233624612次序關(guān)系次序關(guān)系P(A)={Ф,{a},,{c},{a,b},{a,c},{b,c},{a,b,c}}次序關(guān)系圖4.8是關(guān)系R的哈斯圖，寫出R的元素但2和3都是B1的極小元。若存在最?。ù螅┰瑒t是唯一的，有可能不存在。極小元一定存在，且可以有多個(gè)。最小元一定是極小元，反之不然。最小元與的其他元素都是可比的，但極小元與其他元素不一定是可比的。也是B的極小元。最大元、最小元、極大元、極小元定義:設(shè)集合X上有一偏序關(guān)系“≤”，且設(shè)Y是X的一個(gè)子集(1)最大元素:如果存在一元素y

Y，對每個(gè)y'

Y均有y'≤y

。(2)極大元素:如果存在一元素y

Y，且在Y中不存在元素y‘有y≠y'且y≤y'

。上界、下界、上確界、下確界上界：