離散數(shù)學(xué) 二元關(guān)系

2024/3/91第7章二元關(guān)系7.1有序?qū)εc笛卡兒積7.2二元關(guān)系7.3關(guān)系的運(yùn)算7.4關(guān)系的性質(zhì)7.5關(guān)系的閉包7.6等價關(guān)系和劃分7.7偏序關(guān)系2024/3/927.1有序?qū)εc笛卡爾積7.1.1有序?qū)Φ亩x7.1.2集合的笛卡爾積7.1.3有序n

元組和n

階笛卡爾積2024/3/937.1.1有序?qū)Φ亩x定義7.1：兩個元素x,y組成的有序序列＜x,y＞，稱為一個有序?qū)Γㄐ蚺?、二元組）。例：直角坐標(biāo)系中點(diǎn)的坐標(biāo)＜x,y＞日期的表示：＜y,m＞2024/3/947.1.1有序?qū)Φ亩x性質(zhì)：當(dāng)x≠y時，＜x，y＞≠＜y，x＞＜x，y＞＝＜u，v＞

x＝u∧y＝v例7.1：

<x＋2,4>＝<5,2x＋y>，求x,y。解：∵x＋2＝5,2x＋y

＝4∴x＝3,y＝22024/3/957.1.2集合的笛卡爾積定義7.2：集合A與B的笛卡兒乘積

A×B＝｛＜x,y＞|x∈A∧y∈B}例：設(shè)A＝{a,b}，B＝{0，1，2}，C＝φ， 計(jì)算A×B，B×A，A×C，A×A。解：A×B＝{＜a,0＞,＜a,1＞,＜a,2＞,＜b,0＞,＜b,1＞,＜b,2＞}B×A＝{＜0,a＞,＜0,b＞,＜1,a＞,＜1,b＞,＜2,a＞,＜2,b＞}A×C＝φA×A＝{＜a,a＞,＜a,b＞,＜b,a＞,＜b,b＞}（A×A可記作A2）例7.2：A={1，2},求P(A)

A。2024/3/967.1.2集合的笛卡爾積集合的笛卡兒積的性質(zhì)：性質(zhì)1：若|A|＝

m,|B|＝

n,則|A

B|＝

mn性質(zhì)2：對任意集合A，有：A×φ＝φ×A

＝φ性質(zhì)3：一般地A×B≠B×A，即笛卡兒乘積不滿足交換律。問題：什么情況下A×B＝B×A？（A＝B∨A＝φ

∨B＝φ）什么情況下A×B≠B×A？（A≠B∧A≠φ∧B≠φ）2024/3/977.1.2集合的笛卡爾積例3：設(shè)A＝{a，b}，B＝{1，2，3}，C＝{p，q}，計(jì)算(A×B)×C，A×(B×C)。解：

(A×B)×C＝{ ＜<a,1>,p＞,＜<a,1>,q＞, ＜<a,2>,p＞,＜<a,2>,q＞, ＜<a,3>,p＞,＜<a,3>,q＞, ＜<b,1>,p＞,＜<b,1>,q＞, ＜<b,2>,p＞,＜<b,2>,q＞, ＜<b,3>,p＞,＜<b,3>,q＞ }。2024/3/987.1.2集合的笛卡爾積A×(B×C)＝{＜a,<1,p>＞,＜a,<1,q>＞, ＜a,<2,p>＞,＜a,<2,q>＞, ＜a,<3,p>＞,＜a,<3,q>＞, ＜b,<1,p>＞,＜b,<1,q>＞, ＜b,<2,p>＞,＜b,<2,q>＞, ＜b,<3,p>＞,＜b,<3,q>＞ }集合的笛卡兒積的性質(zhì)性質(zhì)4：一般地(A×B)×C≠A×(B×C)，即集合的笛卡兒積不滿足結(jié)合律。性質(zhì)5：

A

C∧B

D

A×B

C×D2024/3/997.1.2集合的笛卡爾積性質(zhì)6：笛卡兒積對∪、∩運(yùn)算滿足分配律A×（B∪C）＝（A×B）∪（A×C）A×（B∩C）＝（A×B）∩（A×C）（A∪B）×C＝（A×C）∪（B×C）（A∩B）×C＝（A×C）∩（B×C）2024/3/9107.1.2集合的笛卡爾積證明：A×（B∪C）＝（A×B）∪（A×C）證：任?。紉，y＞＜x，y＞∈A×（B∪C）

x∈A∧y∈B∪C

x∈A∧（y∈B∨y∈C）

（x∈A∧y∈B）∨

（x∈A∧y∈C）（＜x，y＞∈A×B）∨

（＜x，y＞∈A×C）＜x，y＞∈（A×B）∪（A×C）

所以，A×（B∪C）＝（A×B）∪（A×C）成立。2024/3/9117.1.2集合的笛卡爾積證明：

（A∩B）×C＝（A×C）∩（B×C）證：任?。紉，y＞＜x，y＞∈（A∩B）×C

x∈（A∩B）

∧y∈C

x∈A∧x∈B∧y∈C（x∈A∧y∈C）∧（x∈B∧y∈C）

（＜x，y＞∈A×C）∧（＜x，y＞∈B×C）＜x，y＞∈

（A×C）∩（B×C）

所以，

（A∩B）×C＝（A×C）∩（B×C）成立。2024/3/9127.1.3有序n

元組和

n

階笛卡爾積定義：n個元素x1，x2，…，xn組成的有序序列,記做：

＜x1,x2,…,xn＞稱為n重組（n元序偶、n元組）。約定:＜x1，x2，…,xn-1,

xn＞=＜<x1，x2，…,xn-1>,xn＞性質(zhì)：＜x1,x2,…,xn＞＝＜y1,y2,…,yn＞

xi

＝y(tǒng)i(i=1,2,…,n)2024/3/9137.1.3有序n

元組和

n

階笛卡爾積定義4.4：集合A1、A2、……、An的笛卡兒乘積A1×A2×…×An＝{＜x1，x2，…，xn＞|xi∈Aii＝1,2,…,n}注意：A1×A2×……×An－1×An＝（A1×A2×……×An－1）

×An一般地：若A1＝A2＝……＝An＝

A時，上式簡記為：An2024/3/9147.2二元關(guān)系7.2.1二元關(guān)系的基本定義7.2.2二元關(guān)系的表示2024/3/9157.2.1二元關(guān)系的基本定義關(guān)系數(shù)的＞,＝,＜關(guān)系;V＝IR;計(jì)算機(jī)程序的輸入與輸出聯(lián)系；數(shù)據(jù)庫的數(shù)據(jù)特性聯(lián)系等。集合論為刻劃這種聯(lián)系提供了一種數(shù)學(xué)模型關(guān)系(Relation)。7.2.1二元關(guān)系的基本定義定義7.3如果一個集合滿足以下條件之一：（1）集合非空,且它的元素都是有序?qū)Γ?）集合是空集則稱該集合為一個二元關(guān)系,簡稱為關(guān)系，記作R.例如：R＝{<1,2>,<a,b>}S＝{<1，2>,3,4}.2024/3/9162024/3/9177.2.1二元關(guān)系的基本定義例:

(1)R＝{<x,y>|x,y

N,x＋y＜3}＝{<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<2,0>}(2)C＝{<x,y>|x,y

R,x2＋y2＝1}(3)R＝{<x,y,z>|x,y,z

R,x＋2y＋z＝3}(4)5元關(guān)系的實(shí)例—數(shù)據(jù)庫實(shí)體模型員工號姓名年齡性別工資301302303…張林王曉云李鵬宇…504347…男女男…160012501500…2024/3/9187.2.1二元關(guān)系的基本定義定義7.4設(shè)A,B為集合,R

A×B，稱R為A到B的二元關(guān)系；R

A×A，稱R為A上的關(guān)系。例：若A＝{a,b},B＝{1},則：（1）寫出A到B的所有二元關(guān)系。（2）寫出A上的所有二元關(guān)系。2024/3/9197.2.1二元關(guān)系的基本定義一般地：若|A|＝m,|B|＝n|A×B|＝mn,A×B

的子集有2mn個,從A到B有2mn個不同的二元關(guān)系.R＝φ ，稱R為空關(guān)系；R＝A×B ，稱R為全域關(guān)系

若|A|＝n|A×A|＝n2,A×A

的子集有2n2個,

A上有2n2不同的二元關(guān)系.R＝φ ，稱R為A上空關(guān)系R＝A×A ，稱R為A上的全域關(guān)系，記做EA;R＝{<x,x>|x∈A} ，稱R為A上的相等關(guān)系，記做IA;2024/3/9207.2.1二元關(guān)系的基本定義常見的幾種特殊的二元關(guān)系

≤≥＜＞＝|集合之間的關(guān)系：

＝≠2024/3/9217.2.2二元關(guān)系的表示1.集合表示法2.關(guān)系矩陣(matrixofrelation)設(shè)A＝{a1,a2,…,am}，B＝{b1,b2,…,bn}，R是A到B的一個二元關(guān)系，令：稱：MR為R的關(guān)系矩陣。2024/3/9227.2.2二元關(guān)系的表示例1：設(shè)A＝{a,b,c},B＝{0,1,2,3},R＝{<a,1>,<b,2>,<c,0>},寫出MR。0001c0100b0010a3210

MR＝2024/3/9237.2.2二元關(guān)系的表示例2：設(shè)A＝{1,2,3,4},A上的關(guān)系R＝{<1,1>,<1,2>,<2,3>,<2,4>,4,2>},寫出MR。123411100200113000040100MR＝2024/3/9247.2.2二元關(guān)系的表示例3設(shè)A＝{1,2,3,4},A上的二元關(guān)系R＝{<x,y>|x≥y},寫出MR。123411000211003111041111MR＝2024/3/9257.2.2二元關(guān)系的表示3.關(guān)系圖R為A到B的二元關(guān)系；以A∪B的每個元素為一個結(jié)點(diǎn)，對每個<x,y>∈R，均連一條從結(jié)點(diǎn)x到y(tǒng)的有向邊，得到一個有向圖，稱為R的關(guān)系圖，記為GR。2024/3/9267.2.2二元關(guān)系的表示例1設(shè)A＝{a,b,c},B＝{0,1,2,3},R＝{<a,1>,<b,2>,<c,0>},畫出GR。abc01232024/3/9277.2.2二元關(guān)系的表示例2設(shè)A＝{1,2,3,4},A上的二元關(guān)系R＝{<x,y>|x≥y},畫出GR。12432024/3/9287.2.2二元關(guān)系的表示練習(xí)：A＝{a,b,c,d},R＝{<a,a>,<a,b>,<a,c>,<b,a>,<d,b>},求R的關(guān)系矩陣MR和關(guān)系圖

GR

。2024/3/9297.2.2二元關(guān)系的表示關(guān)系的表示方法關(guān)系R的集合表達(dá)式關(guān)系矩陣MR關(guān)系圖GR三者均可以唯一相互確定。2024/3/9307.3關(guān)系的運(yùn)算7.3.1關(guān)系的定義域、值域和域7.3.2關(guān)系的逆7.3.3關(guān)系的右復(fù)合7.3.4關(guān)系運(yùn)算的性質(zhì)7.3.5關(guān)系的冪2024/3/9317.3.1關(guān)系的定義域、值域和域定義7.6：dom（R）={x|

y（xRy）}ran（R）={y|

x（xRy）}fld（R）=

dom（R）∪ran（R）

例：設(shè)R＝{＜a,1＞,＜b,2＞,＜a,3＞}計(jì)算dom（R）,ran（R）,域fld（R）2024/3/9327.3.2關(guān)系的逆運(yùn)算定義7.7關(guān)系R的逆關(guān)系R-1={<y,x>|xRy}例：R＝{<a,1>,<b,2>,<c,0>},則：R-1＝{<1,a>,<2,b>,<0,c>}問題：已知MR，如何計(jì)算MR-1?已知GR，如何計(jì)算GR-1?2024/3/9337.3.3關(guān)系的右復(fù)合定義7.8關(guān)系F,G的右復(fù)合關(guān)系復(fù)合的求解方法集合表達(dá)式圖示法關(guān)系矩陣2024/3/9347.3.3關(guān)系的右復(fù)合例：R={<1,2>,<2,3>,<1,4>,<2,2>}

S={<1,1>,<1,3>,<2,3>,<3,2>,<3,3>}法1：R°S=

S°R={<1,3>,<2,2>,<2,3>}

{<1,2>,<1,4>,<3,2>,<3,3>}法2：利用圖示方法求合成2024/3/9357.3.3關(guān)系的右復(fù)合法3：關(guān)系矩陣相乘的方法一般地：設(shè):

A={a1,a2,…,am}

B={b1,b2,…,bp}

C={c1,c2,…,cn}

R是A到B的一個二元關(guān)系，

S是B到C的一個二元關(guān)系，

RοS是A到C的一個二元關(guān)系，

2024/3/9367.3.3關(guān)系的右復(fù)合則： MR＝(rij)m×p

MS＝

(sij)p×n

MR

οS＝(tij)m×n

2024/3/937MR＝Ms＝MRS＝abc11102001pqa10b10c01pq1102017.3.3關(guān)系的右復(fù)合例1：2024/3/9387.3.4關(guān)系運(yùn)算的性質(zhì)定理7.1

設(shè)F是任意的關(guān)系,則

(1)(F

1)

1＝F(2)domF

1＝ranF,ranF

1＝domF證明：(1)任取<x,y>,由逆的定義有

<x,y>∈(F

1)

1

<y,x>∈F

1

<x,y>∈F所以有(F

1)

1＝F(2)任取

x∈domF

1

y(<x,y>∈F

1)

y(<y,x>∈F)

x∈ranF

所以有domF

1＝ranF.同理可證ranF

1

＝domF.2024/3/9397.3.4關(guān)系運(yùn)算的性質(zhì)定理7.2

設(shè)F,G,H是任意的關(guān)系,則

(1)(F。G)。H=F。(G。H)

證明：任取<x,y>,

<x,y>

(F°G)°H

t(<x,t>∈F°G∧<t,y>∈H)

t(

s(<x,s>∈F∧<s,t>∈G)∧<t,y>∈H)

t

s(<x,s>∈F∧<s,t>∈G∧<t,y>∈H)

s(<x,s>∈F∧

t

(<s,t>∈G∧<t,y>∈H))

s(<x,s>∈F∧<s,y>∈G°H)

<x,y>∈F°(G°H)

所以(F°G)°H=F°(G°H)2024/3/9407.3.4關(guān)系運(yùn)算的性質(zhì)定理7.2

設(shè)F,G,H是任意的關(guān)系,則(2)(F。G)

1=G

1

。F

1

證明：任取<x,y>,<x,y>∈(F°G)

1<y,x>∈F°G

t(<y,t>∈F∧(t,x)∈G)

t(<x,t>∈G

1∧(t,y)∈F

1)

<x,y>∈G

1°F

1所以(F°G)

1=G

1°F

1

2024/3/9417.3.4關(guān)系運(yùn)算的性質(zhì)定理7.3

設(shè)R

為A上的關(guān)系,則

R°IA=IA°R=R例：設(shè)A＝{1,2,3,4}，A上的二元關(guān)系R={<1,2>,<2,3>,<1,4>,<2,2>}，求：

R°IA

IA°R

2024/3/9427.3.5關(guān)系的冪定義7.10：若R是A上二元關(guān)系,Rn(n∈N)定義如下：R0＝IARn+1＝Rn·R問題：給定集合A和A上的關(guān)系R，如何計(jì)算Rn（n∈N）?

2024/3/9437.3.5關(guān)系的冪例：設(shè)A＝{a,b,c,d},R＝{<a,b>,<b,a>,<b,c>,<c,d>},求Rn。方法1：按照定義求解解：R0＝{<a,a>,<b,b>,<c,c>,<d,d>}R1＝{<a,b>,<b,a>,<b,c>,<c,d>}R2＝{<a,a>,<a,c>,<b,b>,<b,d>}R3＝{<a,b>,<a,d>,<b,a>,<b,c>}R4＝{<a,a>,<a,c>,<b,b>,<b,d>}R2＝R4＝R6＝……R3＝R5＝R7＝……2024/3/9447.3.5關(guān)系的冪方法2：利用關(guān)系矩陣相乘的方法由于：M4=M2,即R4=R2.于是：可以得到

R2=R4=R6=…,

R3=R5=R7=…2024/3/9457.3.5關(guān)系的冪方法3：用關(guān)系圖的方法得到R0,R1,R2,R3,…的關(guān)系圖如下圖所示從關(guān)系圖看冪Rn運(yùn)算(n≥1)：1.從R的每個結(jié)點(diǎn)x出發(fā)，凡通過數(shù)n條邊能到達(dá)的結(jié)點(diǎn)y，則有<x，y>∈Rn。2.<x，y>∈Rn，意味著關(guān)系圖中從x到y(tǒng)存在長為

n的一條路徑；2024/3/9467.3.5關(guān)系的冪冪運(yùn)算的性質(zhì)引：鴿籠原理（抽屜原理）若有n個鴿籠，n＋1只鴿子，則至少有一個鴿籠里至少有兩只鴿子。（將n＋1個物體放入n個盒子里，則至少有一個盒子里有2個或2個以上的物體。）2024/3/9477.3.5關(guān)系的冪定理7.6：設(shè)|A|＝n,

R是A上二元關(guān)系，則存在s、t,使Rs＝Rt(0≤s＜t≤2n2)。證明：

∵R是A上的關(guān)系，則對任意k∈N，Rk

A×A。又 ∵|A×A|＝n2

∴|ρ(A×A)|＝2n2，即A上共有2n2個不同的二元關(guān)系。但：序列R0，R1，……，R

2n2共有2n2＋1項(xiàng)，因此,存在s,t∈N,使Rs=Rt(0≤s＜t≤2n2)。

2024/3/9487.3.5關(guān)系的冪定理7.7：若R是A上二元關(guān)系，m,n

∈N,則：

Rm·Rn＝Rm＋n(Rm)n＝Rmn定理7.8：若R是A上二元關(guān)系，若存在自然數(shù)s,t(s＜t)，使得Rs＝Rt,則：對任意k

∈N,

Rs+k＝Rt＋k對任意k,i

∈N,

Rs+kp+i＝Rs＋i,其中p=t－s。令S={R0,R1,…,Rt-1}，則對任意q

∈N,Rq∈S.2024/3/9497.4關(guān)系的性質(zhì)7.4.1自反性和反自反性7.4.2對稱性和反對稱性7.4.3傳遞性7.4.4關(guān)系性質(zhì)的判定2024/3/9507.4.1自反性和反自反性定義7.11：設(shè)R為A上的關(guān)系,

(1)若

x(x∈A→<x,x>

R),則稱R在A上是自反的.

(2)若

x(x∈A→<x,x>

R),則稱R在A上是反自反的.例7.10：

A={1,2,3},R1,R2,R3

是A上的關(guān)系,其中

R1

={<1,1>,<2,2>}

R2

={<1,1>,<2,2>,<3,3>,<1,2>}

R3

={<1,3>}關(guān)系是自反（反自反）的

關(guān)系圖中每個結(jié)點(diǎn)均有（無）環(huán)。關(guān)系是自反（反自反）的

關(guān)系矩陣主對角線的元素全為1（0）自反性與反自反性是互斥的，但不互補(bǔ)。2024/3/9517.4.2對稱性和反對稱性定義7.12：設(shè)R為A上的關(guān)系,

(1)若

x

y(x,y∈A∧<x,y>∈R→<y,x>∈R),則稱R為A上

對稱的關(guān)系.

(2)若

x

y(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y),

x

y(x,y∈A∧<x,y>∈R∧x≠y→<y,x>

R),

則稱為A上的反對稱關(guān)系.例7.11

設(shè)A＝{1,2,3},R1,R2,R3和R4都是A上的關(guān)系,其中

R1＝{<1,1>,<2,2>}，R2＝{<1,1>,<1,2>,<2,1>}

R3＝{<1,2>,<1,3>}，R4＝{<1,2>,<2,1>,<1,3>}2024/3/9527.4.2對稱和反對稱性注意：從關(guān)系圖判斷關(guān)系是對稱的

關(guān)系圖兩結(jié)點(diǎn)若有邊，則一定是雙向的，即方向相反的一對有向邊。關(guān)系是反對稱的

關(guān)系圖中兩結(jié)點(diǎn)之間若有邊，則一定為單向的。從關(guān)系矩陣判斷關(guān)系是對稱的

關(guān)系矩陣關(guān)于主對角線對稱。關(guān)系是反對稱的

對任意的i,j,(i≠j),rij＝1→rji＝0。2024/3/9537.4.3傳遞性例7.12

設(shè)A＝{1,2,3},R1,R2,R3是A上的關(guān)系,其中

R1＝{<1,1>,<2,2>}

R2＝{<1,2>,<2,3>}

R3＝{<1,3>}定義7.13：設(shè)R為A上的關(guān)系,若

x

y

z(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R),

則稱R是A上的傳遞關(guān)系.

關(guān)系是傳遞的

關(guān)系圖中若兩結(jié)點(diǎn)之間至少有兩條邊相連，則一定存在捷徑。2024/3/9547.4.4關(guān)系性質(zhì)的判定

自反性反自反性對稱性反對稱性傳遞性表達(dá)式IA

RR∩IA=

R=R

1

R∩R

1

IA

R

R

R關(guān)系矩陣主對角線元素全是1主對角線元素全是0矩陣是對稱矩陣若rij＝1,且i≠j,則rji＝0對M2中1所在位置,M中相應(yīng)位置都是1關(guān)系圖每個頂點(diǎn)都有環(huán)每個頂點(diǎn)都沒有環(huán)如果兩個頂點(diǎn)之間有邊,一定是一對方向相反的邊(無單邊)如果兩點(diǎn)之間有邊,一定是一條單向邊(無雙向邊)如果頂點(diǎn)xi到xj有邊,xj到xk有邊,則從xi到xk也有邊2024/3/9557.4.4關(guān)系性質(zhì)的判定例7.14:

判斷下圖中關(guān)系的性質(zhì),并說明理由(3)自反，不是反自反；反對稱，不是對稱；不傳遞.(1)(2)(3)(1)不自反也不反自反；對稱,不反對稱；不傳遞.(2)不是自反；反自反；反對稱,不是對稱；傳遞.2024/3/9567.4.4關(guān)系性質(zhì)的判定思考：設(shè)A＝{a,b,c}，試給出A上的一個二元關(guān)系R，使其同時不滿足自反性、反自反性、對稱性、反對稱性和傳遞性(要求畫出R的關(guān)系圖)。2024/3/9577.5關(guān)系的閉包7.5.1閉包的定義7.5.2閉包的構(gòu)造方法2024/3/9587.5.1閉包的定義定義7.14（閉包)設(shè)R為A上的二元關(guān)系，如果A上的二元關(guān)系R’，使：R

R’

；R’是自反的（對稱的或傳遞的）；對A上的任何關(guān)系R”，如果R

R”,且R”自反（對稱或傳遞）,必有R’

R”；則稱R’為R的自反（對稱或傳遞）閉包。記做：r(R)（

s(R)或t(R)

）2024/3/9597.5.1閉包的定義例：A＝{a,b,c,d},R＝{<a,b>,<b,b>,<b,c>,<c,b>,<c,d>},求r(R),s(R),t(R)

。2024/3/9607.5.2閉包的構(gòu)造方法1.集合表達(dá)式定理7.10設(shè)R為A上的二元關(guān)系，則：(1)r（R）＝R∪R0（R0＝

IA）(2)s（R）＝R∪R-1(3)t（R）＝R∪R2∪R3∪……2024/3/9617.5.2閉包的構(gòu)造方法（1）

r（R）＝R∪IA證明：令R’＝

R∪IA顯然R

R’；對任意x∈A，有<x,x>∈

IA,當(dāng)然<x,x>∈R∪IA＝

R’，故R’自反；設(shè)另有關(guān)系R”也是自反的，且R

R”，∵R”自反∴IA

R”，又R

R”故：

R∪IA

R”，即R’

R”。所以說：r（R）＝R∪IA。2024/3/962(2)s（R）＝R∪R-1證明：令R’＝R∪R-1顯然

R

R’；對任意<x,y>∈

R’<x,y>∈R’

<x,y>∈R

∨<x,y>∈R

–1

<y,x>∈R

–1

∨<y,x>∈R

<y,x>∈R∪R

–1

＝R’

故R’對稱；7.5.2閉包的構(gòu)造方法2024/3/963設(shè)另有關(guān)系R’’也是對稱的，且R

R’’，則對任意<x,y>∈R’

<x,y>∈R∨<x,y>∈R–1若<x,y>∈R,由于R

R’’知<x,y>∈R’’若<x,y>∈R–1,則<y,x>∈R,由于R

R’’,故有<y,x>∈R’’,而R’’對稱,于是

<x,y>∈R’’?！郣’

R’’所以說：s（R）＝R∪R-1。7.5.2閉包的構(gòu)造方法2024/3/964(3)

t（R）＝R∪R2∪R3∪……證明：令R’＝R∪R2∪R3∪……顯然

R

R’；對任意<x,y>，<y,z>∈R’,必k,j（k,j≥1,使<x,y>∈Rk,<y,z>∈Rj,于是<x,z>∈RkRj＝Rk+j

R’,即<x,z>∈R’故R’傳遞；7.5.2閉包的構(gòu)造方法2024/3/965設(shè)另有關(guān)系R’’也是傳遞的，且R

R’’，則對任意<x,y>∈R’,必k(k≥1),使<x,y>∈Rk,顯然存在序列：x＝c0,c1,c2,…,ck＝y(tǒng),使：<x,c1>,<c1,c2>,…,<ck-1,y>∈R

R’’由已知：R’’傳遞，故<x,y>∈R’’

∴R’

R’’因此t（R）＝R∪R2∪R3∪……成立。即<x,y>∈R·R·R……·RK個7.5.2閉包的構(gòu)造方法2024/3/9667.5.2閉包的構(gòu)造方法

2.關(guān)系矩陣表示設(shè)關(guān)系R,r(R),s(R),t(R)的關(guān)系矩陣分別為M,Mr,Ms和Mt

,則Mr

=M+EMs

=M+MT

Mt

=M+M2+M3+…3.關(guān)系圖表示2024/3/9677.5.2閉包的構(gòu)造方法例7.15

設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>},R和r(R),s(R),t(R)的關(guān)系圖如下圖所示.2024/3/9687.6等價關(guān)系和劃分7.6.1等價關(guān)系的定義7.6.2等價類和商集7.6.3集合的劃分7.6.4等價關(guān)系與劃分的關(guān)系2024/3/9697.6.1等價關(guān)系的定義定義7.15非空集合A上的二元關(guān)系R，如果R是

(1)自反的(2)對稱的(3)傳遞的稱R為等價關(guān)系／EquivalenceRelations。若R為一個等價關(guān)系，xRy，稱為x等價于y,記作：x~y。2024/3/9707.6.1等價關(guān)系的定義例7.16A＝{1,2,3,4,5,6,7,8}上的關(guān)系RR＝{<x,y>|x,y∈A∧x≡y(mod3)}為A上的一個等價關(guān)系。2024/3/9717.6.1等價關(guān)系的定義模m相等（同余）關(guān)系設(shè)x，y∈A（A

Z），m∈Z+，如果x－y＝m·k(k∈Z)，那么x與y是模m相等，記為：x≡y(modm)（或稱x和y模m同余）。一般地非空集合A

上的模m

同余關(guān)系R＝{<x,y>|x,y∈A∧x≡y(modm)}是一個等價關(guān)系。2024/3/9727.6.2等價類和商集定義7.16：等價類設(shè)R為非空集合A上的等價關(guān)系,

x∈A，令

[x]R

＝{y|y∈A∧xRy}稱[x]R

為x關(guān)于R

的等價類,簡稱為x

的等價類,簡記為[x].

定義7.17:商集

A／R＝{[x]R|x∈A}2024/3/9737.6.2等價類和商集例：寫出A＝{1,2,3,4,5,6,7,8}上的模3等價關(guān)系的等價類和商集。則:[1]＝[4]＝[7]＝{1,4,7} [2]＝[5]＝[8]＝{2,5,8}[3]＝[6]＝{3,6}

A／R＝{{1,4,7},{2,5,8}

,{3,6}}2024/3/974例2A＝{a,b,c,d,e,f}，A上的等價關(guān)系R的關(guān)系圖如下：bcadef則：[a]＝[b]＝[c]＝{a,b,c}[d]＝[e]＝{d,e}[f]＝{f}A／R＝{[a],[d],[f]}7.6.2等價類和商集2024/3/9757.6.2等價類和商集例3R是Z上的模4等價關(guān)系，則：[0]＝{…,－8,－4,0,4,8,…}[1]＝{…,－7,－3,1,5,9,…}[2]＝{…,－6,－2,2,6,10,…}[3]＝{…,－5,－1,3，7,11,…}Z／R＝{[0],[1],[2],[3]}2024/3/9767.6.2等價類和商集等價類的性質(zhì)定理7.14：設(shè)R為非空集合A上的等價關(guān)系，則2024/3/9777.6.3集合的劃分定義7.18：設(shè)A為非空集合,若A的子集族

(

P(A))滿足下面條件：

(1)

(2)

x

y(x,y∈

∧x≠y→x∩y＝

)(3)∪

＝A稱

是A的一個劃分,稱

中的元素為A的劃分塊.

2024/3/9787.6.3集合的劃分問題1：

設(shè)A＝{a,b,c,d},給定

1,

2,

3,

4,

5,

6如下：

1＝{{a,b,c},tc7tem7 }

2＝{{a,b},{c},cnt1iaz }

3＝{{a},{a,b,c,d} }

4＝{{a,b},{c} }

5＝{

,{a,b},{c,d}}

6＝{{a,{a}},{b,c,d}}其中

1和

2是A的劃分,其他都不是A的劃分.2024/3/9797.6.3集合的劃分問題2A＝{1,2,3}，則集合A的劃分有幾個？分別是什么？

1＝{{1},{2,3}}

2＝{{2},{1,3}}

3＝{{3},{1,2}}

4＝{{1,2,3}}

5＝{{1},{2},{3}}2024/3/9807.6.4等價關(guān)系與劃分的關(guān)系等價關(guān)系與劃分是一一對應(yīng)的關(guān)系一方面：集合A上的一個等價關(guān)系R確定A的一個劃分,即A／R。另一方面：集合A的一個劃分，確定A上的一個等價關(guān)系R。任給A的一個劃分

,如下定義A

上的關(guān)系R：R＝{<x,y>|x,y∈A∧x與y在

的同一劃分塊中}R為A上的等價關(guān)系，且該等價關(guān)系確定的商集就是

.2024/3/9817.6.4等價關(guān)系與劃分的關(guān)系例：若A＝{a,b,c,d,e,f},A上的一個劃分

π＝{{a，b，c}，{d，e}，{f}}，則：π確定A上的一個等價關(guān)系

。

R＝{

<a,a>,<b,b>,<c,c>,<a,b>,<b,a>,<a,c>,<c,a>,<b,c>,<c,b>,

<d,d>,<e,e>,<d,e>,<e,d>,

<f,f>

}bcadef2024/3/9827.6.4等價關(guān)系與劃分的關(guān)系一般地：若A上的劃分π＝{A1,A2,…,Am}。則π確定A上的一個等價關(guān)系R2024/3/9837.6.4等價關(guān)系與劃分的關(guān)系問題3：設(shè)A＝{1，2，3}（1）A上共有多少個不同的二元關(guān)系；（2）給出A上所有的等價關(guān)系。分析：1~

5分別對應(yīng)于等價關(guān)系R1~R5.

其中:R1={<2,3>,<3,2>}∪IA

R2={<1,3>,<3,1>}∪IA

R3={<1,2>,<2,1>}∪IAR4=EAR5=IA2024/3/9847.6.4等價關(guān)系與劃分的關(guān)系思考練習(xí)A＝{1，2}共有多少個二元關(guān)系，其中有幾個是等價關(guān)系，請寫出來。A＝{1，2，3，4}共有多少個二元關(guān)系，其中有幾個是等價關(guān)系，請寫出來。A＝{1，2，3，4，5}共有多少個二元關(guān)系，其中有幾個是等價關(guān)系，請寫出來。2024/3/9857.7偏序關(guān)系7.7.1偏序關(guān)系及相關(guān)定義7.7.2哈斯圖7.7.3偏序集中的特殊元素7.7.4調(diào)度問題2024/3/9867.7.1偏序關(guān)系及相關(guān)定義定義7.19：R是非空集合A上的二元關(guān)系，如果R是：

(1)自反的(2)反對稱的(3)傳遞的則稱R是A上偏序關(guān)系(半序關(guān)系／部分序關(guān)系),記作?。設(shè)?為偏序關(guān)系,如果<x,y>∈?,則記作x?y,讀作x“小于或等于”y.

2024/3/9877.7.1偏序關(guān)系及相關(guān)定義實(shí)例:集合A上的恒等關(guān)系IA

是A上的偏序關(guān)系.小于或等于關(guān)系,整除關(guān)系和包含關(guān)系也是相應(yīng)集合上的偏序關(guān)系.定義7.22：集合A連同A上的偏序關(guān)系R一起稱為一個偏序集，

記為<A,R>（或：<A,?>）。2024/3/9887.7.1偏序關(guān)系及相關(guān)定義定義7.20：設(shè)R為非空集合A上的偏序關(guān)系,定義：

x,y

A，x?y

x?y∧

x≠y

x,y

A,x與y可比

x?y∨

y?x.定義7.21：

全序

R為非空集合A上的偏序,

x,y

A,x與y都可比，則稱R為全序（線序）關(guān)系。如：<{2,4,8},|><{1,2,3,…,9},≤>42682024/3/9897.7.1偏序關(guān)系及相關(guān)定義定義7.23：覆蓋設(shè)R為非空集合A上的偏序關(guān)系,

x,y∈A,如果x?y且不存在z

A使得x?z?y,則稱y覆蓋x。如：

<{2,4,6,8},|><{1,2,3,…,9},≤>42682024/3/9907.7.2哈斯圖偏序關(guān)系的表示方法1.關(guān)系矩陣不能明顯看出二元關(guān)系的特征。2.關(guān)系圖比較煩瑣3.簡化的關(guān)系圖哈斯圖（

Hasse圖）2024/3/9917.7.2哈斯圖例1：

A＝{2，4，6，8}，A上的二元關(guān)系：

R＝｛＜a，b＞｜a|b，a,b∈A｝42684268簡化2024/3/9927.7.2哈斯圖關(guān)系圖→哈斯圖：自反性：每個頂點(diǎn)都有自回路，省去。反對稱性：兩個頂點(diǎn)間只可能有一個箭頭,從下→上的方向從小到大安置頂點(diǎn)，可省略箭頭。傳遞性：若y覆蓋x，則在x和y之間連一條線2024/3/9937.7.2哈斯圖例2：

畫出＜{1,2,…,9}，R≤

＞的哈斯圖。全序關(guān)系／線序關(guān)系2024/3/9947.7.2哈斯圖例3

：畫出＜{1,2,3,4,5,6,7,8,9},R整除＞，＜

P({a,b,c}),R

＞的哈斯圖。練習(xí)1：

已