交大數(shù)理邏輯關(guān)系市公開課一等獎(jiǎng)省賽課獲獎(jiǎng)?wù)n件

第10章關(guān)系10.1二元關(guān)系10.2關(guān)系矩陣和關(guān)系圖10.3關(guān)系逆、合成、限制和象10.4關(guān)系性質(zhì)10.5關(guān)系閉包10.6等價(jià)關(guān)系和劃分10.7相容關(guān)系和覆蓋10.8偏序關(guān)系交大數(shù)理邏輯關(guān)系第1頁關(guān)系性質(zhì)充要條件設(shè)R為A上二元關(guān)系,則

R在A上自反當(dāng)且僅當(dāng)IA

R

R在A上反自反當(dāng)且僅當(dāng)R∩IA=

R在A上對稱當(dāng)且僅當(dāng)R=R1

R在A上反對稱當(dāng)且僅當(dāng)R∩R1IA

R在A上傳遞當(dāng)且僅當(dāng)RRR

證：必要性：

R是傳遞

RRR<x,y>∈RR

(z)(x,zR∧z,yR)<x,y>R∴

RRR充分性：

RRRR是傳遞

x,zR∧z,yR<x,y>RR

<x,y>R∴R是傳遞∵R是傳遞

∵RRR

交大數(shù)理邏輯關(guān)系第2頁10.5.2關(guān)系閉包定義閉包定義

包含R最小自反關(guān)系是R自反閉包包含R最小對稱關(guān)系是R對稱閉包包含R最小傳遞關(guān)系是R傳遞閉包普通地，將

R自反閉包記作r(R),對稱閉包記作s(R),傳遞閉包記作t(R).交大數(shù)理邏輯關(guān)系第3頁10.5.3閉包性質(zhì)定理10.5.4

對非空集合A上關(guān)系R，有若R是自反

r(R)=R;若R是對稱

s(R)=R;若R是傳遞

t(R)=R.定理10.5.5

對非空集合A上關(guān)系R1、R2,若R1R2

則

r(R1)

r(R2)

s(R1)

s(R2)

t(R1)

t(R2)定理10.5.5

對非空集合A上關(guān)系R1、R2，則

r(R1)∪r(R1)=r(R1∪R2)

s(R1)∪r(R1)=s(R1∪R2)

t(R1)∪r(R1)=t(R1∪R2)交大數(shù)理邏輯關(guān)系第4頁10.5.4閉包結(jié)構(gòu)方法

設(shè)R為A上關(guān)系,則有定理10.5.7:

r(R)=R∪R0=R∪IA

定理10.5.8:

s(R)=R∪R-1定理10.5.9:

t(R)=R∪R2∪R3∪…定理10.5.10:設(shè)A為非空集合，|A|=n，則存在一個(gè)正整數(shù)k≤n，使得

t(R)=R∪R2∪R3∪…∪Rk(k≤n)

t(R)=R∪R2∪R3∪…∪Rn以上分別是自反閉包r(R)、對稱閉包s(R)和傳遞閉包t(R)結(jié)構(gòu)方法

交大數(shù)理邏輯關(guān)系第5頁證實(shí):

t(R)=R∪R2∪R3∪…先證R∪R2∪R3∪…t(R)①當(dāng)n=1時(shí)，R1=Rt(R)。②設(shè)n=k時(shí)，Rkt(R)。

下證

Rk+1t(R)

x,yRk+1

x,yRk

°R(z)(x,zR∧z,yRk)(z)(x,zt(R)∧z,yt(R))x,yt(R)

即Rk+1

t(R)(k≥0)故R∪R2∪R3∪…

t(R)交大數(shù)理邏輯關(guān)系第6頁證實(shí):

t(R)=R∪R2∪R3∪…再證t(R)R∪R2∪R3∪…

顯然

RR∪R2∪R3∪…

下證實(shí)R∪R2∪R3∪…是傳遞。x,zR∪R2∪R3∪…∧z,yR∪R2∪R3∪…

(t)(x,zRt

)∧(s)(z,yRs)(s,t≥0自然數(shù))

x,yRt°Rs

=Rt+sR∪R2∪R3∪…

x,yR∪R2∪R3∪…

依據(jù)傳遞關(guān)系定義，有

R∪R2∪R3∪…是傳遞。交大數(shù)理邏輯關(guān)系第7頁閉包結(jié)構(gòu)方法舉例設(shè)A={a,b,c}，定義A上二元關(guān)系R為：

R={a,b,b,c,c,a}

試用關(guān)系合成運(yùn)算方法求：r(R)，s(R)，t(R)解:r(R)=R∪IA={a,b,b,c,c,a,a,a,b,b,c,c}

s(R)=R∪R-1={a,b,b,c,c,a,b,a,c,b,a,c

}t(R)=R∪R2∪R3

：

R2=R°R={a,c,b,a,c,b}R3=R2°R={a,a,b,b,c,c}=IA

t(R)={a,a,a,b,a,c,b,a>,b,b,b,c,c,a,c,b,c,c}=EA交大數(shù)理邏輯關(guān)系第8頁閉包結(jié)構(gòu)方法（矩陣法）設(shè)關(guān)系R,r(R),s(R),t(R)關(guān)系矩陣分別為M,Mr,Ms和Mt,則

Mr=M+I

Ms=M+M’

Mt=M+M2+M3+…說明:I

是和M同階單位矩陣,M’是M轉(zhuǎn)置矩陣.

注意:在上述等式中矩陣元素相加時(shí)使用邏輯加.交大數(shù)理邏輯關(guān)系第9頁閉包矩陣結(jié)構(gòu)方法舉例設(shè)A={a,b,c}，定義A上二元關(guān)系R為：

R={a,b,b,c,c,a}

試求：t(R)解：用關(guān)系矩陣求t(R)方法以下：交大數(shù)理邏輯關(guān)系第10頁閉包矩陣結(jié)構(gòu)方法舉例其中，∨表示矩陣對應(yīng)元素進(jìn)行邏輯加運(yùn)算。交大數(shù)理邏輯關(guān)系第11頁閉包同時(shí)含有各種性質(zhì)定理10.5.11

對非空集合A上關(guān)系R，有若R是自反

s(R)、t(R)是自反;若R是對稱

r(R)、t(R)是對稱;若R是傳遞

r(R)是傳遞.證：∵

R是傳遞

RRR，而r(R)=R∪IA

r(R)

r(R)=(R∪IA)(R∪

IA)=R(R∪

IA)

∪IA

(R∪

IA)=RR∪R

IA

∪IA

(R∪

IA)=R∪R∪(R∪

IA)=R∪

IA=r(R)注意：若R是傳遞，s(R)是不一定是傳遞.如：A={1,2,3},R={<1,2>}是傳遞

r(R)=R∪IA

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

是傳遞但s(R)=R∪R

-1

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

不是傳遞

交大數(shù)理邏輯關(guān)系第12頁閉包同時(shí)含有各種性質(zhì)定理10.5.12

對非空集合A上關(guān)系R,有

rs(R)=sr(R)

rt(R)=tr(R)

st(R)

ts(R)

設(shè)

A={1,2},R={<1,2>}st(R)=s(t(R))=s({<1,2>})={<1,2>,<2,1>}ts(R)=t(s(R))=t({<1,2>,<2,1>})={<1,2>,<2,1>,<1,1>,<2,2>}交大數(shù)理邏輯關(guān)系第13頁10.6等價(jià)關(guān)系和劃分等價(jià)關(guān)系是最主要、最常見二元關(guān)系之一。它有良好性質(zhì)。在計(jì)算機(jī)科學(xué)和計(jì)算機(jī)技術(shù)、信息科學(xué)和信息工程中都有廣泛應(yīng)用。定義設(shè)R為非空集合上關(guān)系.假如R是自反、對稱和傳遞,則稱R為A上等價(jià)關(guān)系.等價(jià)關(guān)系關(guān)系矩陣和關(guān)系圖特點(diǎn)關(guān)系矩陣主對角線全為1且是對稱陣；關(guān)系圖每一個(gè)結(jié)點(diǎn)上都有自回路且每兩個(gè)結(jié)點(diǎn)間假如有邊，一定有方向相反兩條邊。交大數(shù)理邏輯關(guān)系第14頁等價(jià)關(guān)系實(shí)例設(shè)A={1,2,3,4,5}，R是A上等價(jià)關(guān)系，R={1,1,1,2,2,1,2,2,3,3,3,4,4,3,4,4,5,5}

則R關(guān)系矩陣M(R)以下：

A上等價(jià)矩陣可用正方形一條對角線和線上若干正方形表示。M(R)主對角線全為1且是對稱陣，所以R是自反和對稱；還能夠用二元關(guān)系傳遞性定義證實(shí)R是傳遞。故R是A上等價(jià)關(guān)系。交大數(shù)理邏輯關(guān)系第15頁等價(jià)關(guān)系實(shí)例設(shè)A={1,2,3,4,5,6,7,8},A上關(guān)系R以下定義：

R={<x,y>|x,y∈A∧x≡y(mod3)}

其中x≡y(mod3)

叫做x與y模3相等,即x除以3余數(shù)與y除以3余數(shù)相等.驗(yàn)證模3相等關(guān)系R為A上等價(jià)關(guān)系——

x∈A,x-x=3×0，所以x≡x(mod3)(R是自反)

x,y∈A,若x≡y(mod3),

x-y=3×t，(tZ)

y-x=3×(–t)，(–tZ)

y≡x(mod3)(R是對稱）x,y,z∈A,若x≡y(mod3),y≡z(mod3),

x-y=3×t1，t1Z，y-z=3×t2，t2Z

x-z=(x-y)+(y-z)=3×t1+3×t2=3×(t1+t2)，t1+t2Z，

x≡z(mod3)(R是傳遞)交大數(shù)理邏輯關(guān)系第16頁A上模3等價(jià)關(guān)系關(guān)系圖設(shè)A={1,2,3,4,5,6,7,8},

R={<x,y>|x,y∈A∧x≡y(mod3)}

1(mod3)=4(mod3)=7(mod3)=12(mod3)=5(mod3)=8(mod3)=2

3(mod3)=6(mod3)=0交大數(shù)理邏輯關(guān)系第17頁等價(jià)類定義

設(shè)R為非空集合A上等價(jià)關(guān)系,x∈A，令

[x]R

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

為x關(guān)于R等價(jià)類,簡記為[x].

實(shí)例

A={1,2,3,4,5,6,7,8}上模3等價(jià)關(guān)系等價(jià)類：

[1]R=[4]R=[7]R={1,4,7}

[2]R=[5]R=[8]R={2,5,8}[3]R=[6]R={3,6}交大數(shù)理邏輯關(guān)系第18頁等價(jià)類性質(zhì)定理10.6.1設(shè)R是非空集合A上等價(jià)關(guān)系，對x,y∈A，下面結(jié)論成立。

(1)[x]R≠

，且[x]RA

；

(2)若<x,y>∈R，則[x]R=[y]R；

(3)若<x,y>R，則[x]R∩[y]R=

；

(4)任何等價(jià)類都是A非空子集A中任取兩個(gè)元素，它們等價(jià)類或相等、或是不相交全部等價(jià)類并集就是AA中任取兩個(gè)元素，它們等價(jià)類或相等、或是不相交交大數(shù)理邏輯關(guān)系第19頁等價(jià)類性質(zhì)舉例實(shí)例:A={1,2,…,8}上模3等價(jià)關(guān)系等價(jià)類：

[1]=[4]=[7]={1,4,7}≠[2]=[5]=[8]={2,5,8}≠[3]=[6]={3,6}≠[1]∩[2]=[1]∩[3]=[2]∩[3]={1,4,7}∪{2,5,8}∪{3,6}=A交大數(shù)理邏輯關(guān)系第20頁商集定義設(shè)R為非空集合A上等價(jià)關(guān)系,以R全部不交等價(jià)類作為元素集合，稱為A在R下商集,記做A/R,A/R={[x]R

|x∈A}實(shí)例

A={1,2,3,4,5,6,7,8}，A關(guān)于模3等價(jià)關(guān)系R商集為

A/R={{1,4,7},{2,5,8},{3,6}}={[0],[1],[2]}A關(guān)于恒等關(guān)系IA商集為：

A/IA

={{1},{2},…,{8}}={{x}

|x∈A}A關(guān)于全域關(guān)系EA商集為：

A/EA

={{1,2,…,8}}={A}交大數(shù)理邏輯關(guān)系第21頁10.6.2集合劃分定義

設(shè)A為非空集合,若存在集合π

滿足下面條件：

(1)(x)(x∈π→x

A)(即π

P(A))(2)π(3)∪π=A(4)xy(x,y∈π∧x≠y→x∩y=)滿足條件(1)(2)(3)，稱π是A覆蓋.滿足全部條件稱π為A一個(gè)劃分，稱π中元素為A劃分塊.如：A關(guān)于模3等價(jià)關(guān)系R商集是A一個(gè)劃分

A/R={{1,4,7},{2,5,8},{3,6}}{{1,4,7},{1,2,5,8},{3,5,6}}為A一個(gè)覆蓋交大數(shù)理邏輯關(guān)系第22頁

商集和劃分關(guān)系定理10.6.2對非空集合A上一個(gè)等價(jià)關(guān)系R，A商集A/R就是A一個(gè)劃分。它稱為由等價(jià)關(guān)系R誘導(dǎo)出來A劃分，記作πR即由A上等價(jià)關(guān)系R能夠誘導(dǎo)出A一個(gè)劃分。定理10.6.3對非空集合A上一個(gè)劃分π，令A(yù)上關(guān)系Rπ為

Rπ={<x,y>|(z)(z∈π∧x∈z∧y∈z}則Rπ是A上等價(jià)關(guān)系，它稱為劃分π誘導(dǎo)出來A上等價(jià)關(guān)系。定理10.6.4對非空集合A上一個(gè)劃分π和A上等價(jià)關(guān)系R，π誘導(dǎo)R當(dāng)且僅當(dāng)R誘導(dǎo)π。所以，集合A上等價(jià)關(guān)系與集合A劃分是一一對應(yīng)。交大數(shù)理邏輯關(guān)系第23頁由劃分導(dǎo)出等價(jià)關(guān)系方法定理設(shè)S={S1，S2，…，Sm}是A一個(gè)劃分，

R={x,y|x和y在同一個(gè)劃分塊中}則R是A上等價(jià)關(guān)系。劃分S導(dǎo)出等價(jià)關(guān)系R能夠表示為：

R=(S1×S1)∪(S2×S2)∪…∪(Sm×Sm)例：設(shè)A={1,2,3,4}，A劃分S={{1},{2,3},{4}}，則從S導(dǎo)出等價(jià)關(guān)系R為：

R={1,1,2,2,2,3,3,2,3,3,4,4}={1}×{1}∪{2,3}×{2,3}∪{4}×{4}能夠驗(yàn)證R是A上等價(jià)關(guān)系。交大數(shù)理邏輯關(guān)系第24頁設(shè)A={1,2,3}，求出A上全部等價(jià)關(guān)系

解：先寫出集合X上全部劃分，它們是：

π1={{2,3},{1}},

π2={{1,3},{2}}

π3={{1,2},{3}}，

π4={{1,2,3}}，

π5={{1},{2},{3}}交大數(shù)理邏輯關(guān)系第25頁設(shè)A={1,2,3}，求出A上全部等價(jià)關(guān)系

對應(yīng)等價(jià)關(guān)系為：

R1={2,3}×{2,3}∪{1}×{1}

={2,2,2,3,3,2,3,3,1,1}R2={1,3}×{1,3}∪{2}×{2}

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

R3={1,2}×{1,2}∪{3}×{3}={1,1,1,2,2,1,2,2,3,3}R4={1,2,3}×{1,2,3}=A×A=EAR5={1}×{1}∪{2}×{2}∪{3}×{3}

={1,1,2,2,3,3}=IAπ1={{2,3},{1}},

π2={{1,3},{2}},

π3={{1,2},{3}}，

π4={{1,2,3}}，

π5={{1},{2},{3}}交大數(shù)理邏輯關(guān)系第26頁由等價(jià)關(guān)系求劃分實(shí)例例設(shè)A={1,2,3,4}，在A上定義二元關(guān)系R：

<<x,y>,<u,v>>Rx+y=u+v，求R導(dǎo)出劃分.解：依據(jù)<x,y>

x+y=2,3,4,5,6,7,8

將AA劃分成7個(gè)等價(jià)類：

(AA)/R={{<1,1>},{<1,2>,<2,1>},{<1,3>,<2,2>,<3,1>},{<1,4>,<2,3>,<3,2>,<4,1>},{<2,4>,<3,3>,<4,2>},{<3,4>,<4,3>},{<4,4>}}

交大數(shù)理邏輯關(guān)系第27頁10.7相容關(guān)系和覆蓋

定義

對非空集合A上關(guān)系R，假如R是自反和對稱，則稱R為A上相容關(guān)系。相容關(guān)系性質(zhì)全部等價(jià)關(guān)系都是相容關(guān)系。相容關(guān)系關(guān)系矩陣主對角線全為1且是對稱陣。相容關(guān)系關(guān)系圖每一個(gè)結(jié)點(diǎn)上都有自回路且每兩個(gè)結(jié)點(diǎn)間假如有邊，一定有方向相反兩條邊交大數(shù)理邏輯關(guān)系第28頁

相容關(guān)系舉例設(shè)A={316,347,204,678,770},A上二元關(guān)系R定義為

R={x,y|xA∧yA∧x和y有相同數(shù)碼}，∵xA，有<x,x>R，∴R是自反；∵<x,y>R，有<y,x>R，∴R是對稱。于是，R是相容關(guān)系。令a=316，b=347，c=204，d=678，e=770R={a,a,a,b,a,d,b,a,b,b,b,c,b,d,

b,e,c,b,c,c,c,e,d,a,d,b,d,d,

d,e,e,b,e,c,e,d,e,