離散數學（第二版） 課件 鄒麗娜 5 二元關系4

離散數學關系的閉包不自反不對稱不傳遞自反閉包對稱閉包傳遞閉包擴充擴充擴充自反閉包定義自反閉包定義對稱閉包定義練習：練習

閉包構造(關系圖法)例：設集合A={1，2，3，4}，R={<1，2>

，<2，2>

，<2，3>

，<3，4>}是定義在A上的二元關系。(1)畫出R的關系圖；(2)求出r(R)，s(R)，t(R)，并畫出其相應的關系圖。關系上的閉包運算解(1)2413關系上的閉包運算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)的關系圖分別如下：r(R)s(R)t(R)123412341234關系上的閉包運算利用關系圖求關系R閉包的方法：(1)檢查R的關系圖，在沒有自環(huán)的結點處加上自環(huán)，可得r(R)的關系圖；(2)檢查R的關系圖，將每條單向邊全部改成雙向邊，可得s(R)的關系圖；(3)檢查R的關系圖，從每個結點出發(fā)，找到其終點，如果該結點到其終點沒有邊相連，就加上此邊，可得t(R)的關系圖。利用關系圖求閉包求閉包的公式：對應的關系矩陣：,，練習：用矩陣法求R的傳遞閉包傳遞閉包t（R）Warshall算法不講等價關系與等價類x～y全域關系EA和恒等關系IA是等價關系例如A={1,2,3}，則R1={<1,1>,<2,2>,<3,3>,<2,3>,<3,2>}為等價關系。等價關系與等價類x,y關于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上的等價關系。例

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

1

2

m

3…A

={

1，

2，…

m}是A的一個劃分集合上的等價關系導出的集合的劃分例集合的劃分是劃分不是劃分例：給出A＝{1,2,3}上的劃分。123

1

123

5123

2123

4123

3集合的劃分導出集合上的等價關系根據A的劃分求A={1,2,3}上的等價關系。

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>}全域關系EA恒等關系IA練習偏序關系R滿足自反的、反對稱的和傳遞的，所以R是一個偏序關系其中有也有4與6是不可比的2,4.6,81.集合A上的恒等關系IA是A上的偏序關系，但全域關系EA不是A上的偏序關系。2.實數域上的小于等于關系（大于等于關系），自然數域上的整除關系，集合的包含關系等都是偏序關系。設A=

1,2,3,4

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

<x,y>

x是y的倍數

(2)R=

<x,y>

x/y是素數

(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>}偏序集偏序集一個集合A和A上的一個偏序關系共同組成的二元結構稱為偏序集，記為<A,?>。實際上，偏序集就是把一個集合及該集合上的一個偏序關系打包成一個整體，它同時展現了一個集合和一個關系。例設A={1,2,3}?

是A上的整除關系，則：1?2,1?3,1＝1,2＝2,3＝3，

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

(1)每個x,y

A,x?y當且僅當x?y且x≠y

(2)每個x,y

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

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

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

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

Y，對每個y'

Y均有y'≤y

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

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

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