離散數(shù)學(xué) 課件 第4章 二元關(guān)系

第四章二元關(guān)系§1關(guān)系的基本概念§2關(guān)系的性質(zhì)及運(yùn)算§3特種關(guān)系§1關(guān)系的基本概念一、關(guān)系的定義二、關(guān)系的表示方法一、關(guān)系的定義1、關(guān)系的定義2、關(guān)系相等3、關(guān)系的定義域和值域1、關(guān)系的定義A1、A2、…、An是任意的n個(gè)集合,n

I＋(1)RA1A2An×××

…A1、A2、…、An間的n元關(guān)系(2)RA1×A2

從A1到A2的二元關(guān)系（3）R＝φ空關(guān)系（4）R＝A1×A2×…×An全關(guān)系A(chǔ)上的n元關(guān)系(5)RAAA×××

…對n元關(guān)系定義的解釋（1）n元關(guān)系是一個(gè)集合；（2）集合中的元素均為n重序元:n元關(guān)系是n個(gè)集合的笛卡兒乘積的一個(gè)子集；n重序元中的第1個(gè)元素屬于A1n重序元中的第i個(gè)元素屬于Ai2元關(guān)系是兩個(gè)集合的笛卡兒乘積的一個(gè)子集；關(guān)系舉例已知：A={1,2,3,4,5,6}R1={<x,y>|x+y=7},R2={<x,y>|x-y=0}R1={<1,6>,<6,1>,<2,5>,<5,2>,<3,4>,<4,3>}R2={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>}R1A×A

R2A×A

R1、R2均為A上的二元關(guān)系關(guān)系舉例已知：A={1,2,3},B={a,b}R1={<1,a>,<1,b>,<2,a>,<3,b>}A×B={<1,a>,<1,b>,<2,a>,<2,b>,<3,a>,<3,b>}R1A×B

R1是從A到B的二元關(guān)系關(guān)系舉例R2={<1,a>,<1,b>,<2,a>,<2,b>,<3,a>,<3,b>}已知：A={1,2,3},B={a,b}R2A×B=R2是從A到B的全關(guān)系R3={<1,1>,<2,2>,<3,3>}A×A={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}R3A×A

R3是從A上的二元關(guān)系關(guān)系舉例A={f,m,s,d}R1定義為A上長幼關(guān)系，則：R1<x,y>

R={<f,s>,<f,d>,<m,s>,<m,d>}<f,m>

R1f和m沒有長幼關(guān)系<d,s>

R1d和s沒有長幼關(guān)系x和y有R關(guān)系xyR<x,y>

Rx和y沒有R關(guān)系xy2、關(guān)系相等R1A1A2An×××

…R2B1B2Bm×××

…（1）m=n;（2）若1≤i≤n，則Ai=Bi;（3）集合R1=集合R2關(guān)系R1和關(guān)系R2相等R1=R2對關(guān)系相等的解釋（1）必須是同元關(guān)系; （2）對應(yīng)的集合相等；（3）集合R1=集合R2m=nAi=Bi關(guān)系相等舉例R1：A→BR2：C→BA={1,2}B={a,b}C={1,2,3}R1={<1,a>,<1,b>,<2,a>}R2={<1,a>,<1,b>,<2,a>}問：R1和R2是否相等？m=n=2集合R1=集合R2R1：A→BR2：C→BA≠C結(jié)論：R1≠R23、關(guān)系的定義域和值域R:X→Y關(guān)系R的定義域:關(guān)系R的序偶中第一元素所組成的集合D(R)D(R)={x|<x,y>R}X

關(guān)系R的值域:關(guān)系R的序偶中第二元素所組成的集合R(R)R(R)={y|<x,y>R}Y

定義域和值域舉例（1）X={x1,x2,x3}Y={y1,y2}R1={<x1,y1>,<x1,y2>,<x2,y2>,<x3,y1>}（2）A={1,2,3,4}B={a,b,c}R2={<1,a>,<1,b>,<3,a>}求：D(R1),R(R1),D(R2),R(R2)D(R1)={x1,x2,x3}X=R(R1)={y1,y2}Y=D(R2)={1,3}A

R(R2)={a,b}B

定義域和值域舉例N:非負(fù)整數(shù)集合R:N→NR={<x,y>|x+2y=10}求:D(R)=?R(R)=?R={<0,5>,<2,4>,<4,3>,<6,2>,<8,1>,<10,0>}D(R)={0,2,4,6,8,10}R(R)={0,1,2,3,4,5}二、關(guān)系的表示方法1、關(guān)系圖法2、關(guān)系矩陣法1、關(guān)系圖法注意：結(jié)點(diǎn)的位置及邊的曲直是無關(guān)緊要的關(guān)系圖：結(jié)點(diǎn)有向弧線X={x1,x2,…,xm}Y={y1,y2,…,yn}R:X→Y(1)在平面上作m個(gè)結(jié)點(diǎn)x1x2xixm(2)在平面上作n個(gè)結(jié)點(diǎn)y1y2yjyn(3)如果<xi,yj>

RXYRGR關(guān)系圖舉例(1)X={1,2,3}Y={a,b}R:X→YR={<1,a>,<1,b>,<2,a>,<3,b>}畫出關(guān)系R的關(guān)系圖。123abXYRR的關(guān)系圖關(guān)系圖舉例(2)X={1,2,3,4,5}R:X→XR={<1,5>,<1,4>,<2,3>,<3,1>,<3,4>,<4,4>}畫出關(guān)系R的關(guān)系圖。12345R的關(guān)系圖閉環(huán)(自環(huán))關(guān)系圖舉例(3)X={0,1,2,3,4}R:X→XR={<x,y>|x≥0∧y≥3}畫出關(guān)系R的關(guān)系圖R={<0,3>,<0,4>,<1,3>,<1,4>,<2,3>,<2,4>,<3,3>,<3,4>,<4,3>,<4,4>}012342、關(guān)系矩陣法X={x1,x2,…,xm}Y={y1,y2,…,yn}R:X→Y關(guān)系矩陣:rij=0∨rij=1當(dāng)<xi,yj>R時(shí),當(dāng)<xi,yj>R時(shí),rij=1rij=0布爾矩陣m×n矩陣MR關(guān)系矩陣舉例(1)X={1,2,3}Y={a,b}R:X→YR={<1,a>,<1,b>,<2,a>,<3,b>}求關(guān)系R的關(guān)系矩陣。MR=123ab111100關(guān)系矩陣舉例(2)X={1,2,3,4,5}R:X→XR={<1,5>,<1,4>,<2,3>,<3,1>,<3,4>,<4,4>}求關(guān)系R的關(guān)系矩陣。MR=12345111100123451100000000000000000關(guān)系矩陣舉例(3)X={0,1,2,3,4}R:X→XR={<x,y>|x≥0∧y≥3}畫出關(guān)系R的關(guān)系矩陣。解答R={<0,3>,<0,4>,<1,3>,<1,4>,<2,3>,<2,4>,<3,3>,<3,4><4,3>,<4,4>}MR=01234111100012341100000001000100011§2關(guān)系的性質(zhì)及運(yùn)算一、關(guān)系的性質(zhì)二、關(guān)系的運(yùn)算一、關(guān)系的性質(zhì)1、自反性2、反自反性3、對稱性4、反對稱性5、可傳遞性1、自反性R:X→XR是自反的

對于每一個(gè)x

X，都有<x,x>

RR是自反的

(

x)(→)x

X<x,x>

R自反性關(guān)系的舉例實(shí)數(shù)集合R:“≤”關(guān)系“≥”關(guān)系自反的關(guān)系(

x)(→)x

Rx≤x(

x)(→)x

Rx≥x自反性關(guān)系的舉例X={1,2,3}R1={<1,1>,<2,2>,<3,3>,<3,1>}R2={<1,1>,<2,2>,<3,1>,<2,3>}問：R1、R2是否具有自反性？R1具有自反性R2不具有自反性<3,3>R22、反自反性R:X→XR是自反的

R是自反的

(

x)(→)x

X<x,x>

R對于每一個(gè)x

X，都有<x,x>

R反自反性關(guān)系的舉例X={1,2,3}R1={<1,1>,<2,1>,<3,2>}R2={<1,2>,<1,3>,<3,1>}問：R1、R2是否具有反自反性？R1不具有反自反性<1,1>R2<2,2>R2<3,3>R2R2具有反自反性不自反的關(guān)系不是自反的不是反自反的不自反的關(guān)系X={1,2,3}R={<1,1>,<2,1>,<3,2>}R是不自反的二元關(guān)系；<2,2>R<3,3>R3、對稱性R:X→XR是對稱的

對于每一個(gè)x、y

X，如果有<x,y>

R<y,x>

RR是對稱的

(

x)(

y)(→)x

X∧y

X∧<x,y>

R<y,x>

R對稱性關(guān)系舉例實(shí)數(shù)集合R:“＝”關(guān)系:對稱關(guān)系(

x)(

y)(→)x

R∧y

R∧x=yy=x對稱性關(guān)系舉例X={1,2,3}R1={<1,2>,<2,1>,<3,2>,<1,3>}R2={<1,2>,<2,1>,<3,3>,<3,2>,<2,3>}問：R1、R2是否具有對稱性？<2,3>R1R1不具有對稱性；R2具有對稱性；4、反對稱性R:X→XR是反對稱的

對于任意的不相同的x、y

X，如果有<x,y>

R<y,x>

RR是反對稱的

(

x)(

y)(→)x

X∧y

X∧x≠y∧<x,y>

R<y,x>

RR是反對稱的

(

x)(

y)(→)x

X∧y

X∧<x,y>

R

∧<x,y>

Rx=y反對稱關(guān)系舉例實(shí)數(shù)集合R:“≤”關(guān)系:反對稱的關(guān)系(

x)(

y)(→)x

R∧y

R∧x≠y∧x≤yy?x(

x)(

y)(→)x

R∧y

R∧x≤y∧y≤xx=y反對稱關(guān)系舉例X={1,2,3}R1={<1,1>,<2,2>,<3,3>}R2={<1,3>,<2,1>,<2,3>}R3={<1,3>,<3,1>,<2,1>,<2,3>}問：R1、R2、R3是否具有反對稱性？R1具有反對稱性R1具有對稱性<3,1>R2<1,2>R2<3,2>R2R2具有反對稱性R3不具有反對稱性<1,2>R3R3不具有對稱性注意：一個(gè)關(guān)系可以即是對稱的，也是反對稱的。不對稱性不是對稱的不是反對稱的不對稱的關(guān)系5、可傳遞性R:X→XR是可傳遞的

對于任意的x、y、z

X如果有<x,y>

R和<y,z>

R<x,z>

RR是可傳遞的

(

x)(

y)(

z)(→)x

X∧y

X∧z

X∧<x,y>

R

∧

<y,z>

R<x,z>

Rxyz可傳遞關(guān)系舉例實(shí)數(shù)集合R:“＝”關(guān)系“≤”關(guān)系“≥”關(guān)系“＜”關(guān)系“＞”關(guān)系可傳遞關(guān)系(

x)(

y)(

z)(→)x

R∧y

R∧z

R∧x＜y

∧y＜zx＜z可傳遞關(guān)系舉例X={1,2,3}R1={<1,2>,<2,1>,<3,1>}R2={<1,2>,<2,3>,<1,3>},R3={<1,2>}問：R1、R2、R3是否具有可傳遞性？<1,1>R1R1不具有可傳遞性R2具有可傳遞性；R3具有可傳遞性；善意的推定可傳遞關(guān)系判斷方法<x,y>

R∧<y,z>

R

→<x,z>

R假在關(guān)系R中找不到<x,y>和<y,z>真關(guān)系為可傳遞關(guān)系關(guān)系性質(zhì)舉例自然數(shù)集合N:相等關(guān)系“=”大于關(guān)系“＞”大于等于關(guān)系“≥”各具有什么性質(zhì)?自反的、對稱的、反對稱的、可傳遞的反自反的、反對稱的可傳遞的自反的、反對稱的可傳遞的關(guān)系性質(zhì)舉例X=φX≠φX上的空關(guān)系具有什么性質(zhì)？自反的、反自反的、對稱的、反對稱的、可傳遞的反自反的、對稱的、反對稱的、可傳遞的關(guān)系性質(zhì)舉例非空集合A,ρ(A)為A的冪集各具有什么性質(zhì)？ρ(A)上的包含關(guān)系“

”ρ(A)上的真包含關(guān)系“

”自反的、反對稱的可傳遞的反自反的、反對稱的可傳遞的利用關(guān)系圖判斷關(guān)系的性質(zhì)(1)自反性:(2)反自反性:(3)對稱性:(4)反對稱性:每一個(gè)結(jié)點(diǎn)上必有一個(gè)閉環(huán)(自回路)；每一個(gè)結(jié)點(diǎn)上都沒有閉環(huán)(自回路)；兩個(gè)結(jié)點(diǎn)間如果有有向邊必成對出現(xiàn)；兩個(gè)結(jié)點(diǎn)間如果有有向邊必單根出現(xiàn)；利用關(guān)系矩陣判斷關(guān)系的性質(zhì)(1)自反性:(2)反自反性:(3)對稱性:(4)反對稱性:主對角線上的元素均為“1”；主對角線上的元素均為“0”；對稱陣rij=rji反對稱陣當(dāng)i≠j時(shí)：若rij＝1rji＝011110000二、關(guān)系的運(yùn)算1、關(guān)系的合成運(yùn)算2、關(guān)系的逆運(yùn)算3、關(guān)系的閉包運(yùn)算1、關(guān)系的合成運(yùn)算（1）合成運(yùn)算的定義（2）關(guān)系R的冪（3）合成關(guān)系的矩陣表達(dá)和圖解引例（1）a是b的父親b是c的父親a是c的祖父（2）a是b的弟弟b是c的父親a是c的叔叔父子關(guān)系祖孫關(guān)系兄弟關(guān)系父子關(guān)系叔侄關(guān)系（1）合成運(yùn)算的定義R:X→YS:Y→ZR與S的合成關(guān)系復(fù)合關(guān)系R?SX→ZR?S={<x,z>|x

X∧z

Z∧(

y)(∧)}<x,y>

R<y,z>

Sy

Y∧合成運(yùn)算的舉例X={1,2,3,4}Y={2,3,4}Z={1,2,3}R:X→

YS:Y→ZR={<x,y>|x+y=6},S={<y,z>|y-z=1}求：R?SR={<2,4>,<3,3>,<4,2>}S={<2,1>,<3,2>,<4,3>}R?S={<2,3>,<3,2>,<4,1>}x+z=5關(guān)系R、S、R?S的關(guān)系圖X4321Y234RZ123SR?SXZ4321123合成運(yùn)算的討論（1）若：R(R)∩D(S)=φR:X→YS:Y→ZR?S=φ（2）若：R(R)∩D(S)≠φR?S≠φ（3）D(R?S)X

R(R?S)Z

至少有一個(gè)序偶<x,y>

R且<y,z>

S定理：?對∪滿足分配律R1:X→Y;R2、R3:Y→Z；R4:Z→W(1)R1?(R2∪R3)=(R1?R2)∪(R1?R3)(2)(R2∪R3)?R4=(R2?R4)∪(R3?R4)(3)R1?(R2∩R3)(R1?R2)∩(R1?R3)

(4)(R2∩R3)?R4(R2?R4)∩(R3?R4)

證明：(R2∪R3)?R4

=(R2?R4)∪(R3?R4)證明：∵R2∪R3:Y→Z；R4:Z→W∴(R2∪R3)?R4

:Y→W對任意的<y,w>

(R2∪R3)?R4

(z)(<y,z>R2∪R3∧

<z,w>R4)

(z)((<y,z>R2∨<y,z>R3)∧

<z,w>R4)

(z)((<y,z>R2∧<z,w>R4)∨(<y,z>R3∧<z,w>R4))(z)(<y,z>R2∧<z,w>R4)∨(z)(<y,z>R3∧<z,w>R4)<y,w>R2?R4∨<y,w>R3?R4<y,w>(R2?R4)∪(R3?R4)證明：(R2∩R3)?R4

(R2?R4)∩(R3?R4)

證明：∵R2∩

R3:Y→Z；R4:Z→W∴(R2∩

R3)?R4

:Y→W對任意的<y,w>

(R2∩R3)?R4(z)(<y,z>R2∩R3∧

<z,w>R4)

(z)((<y,z>R2∧<y,z>R3)∧<z,w>R4)

(z)((<y,z>R2∧<z,w>R4)∧(<y,z>R3∧<z,w>R4))

(z)(<y,z>R2∧<z,w>R4)∧(z)(<y,z>R3∧<z,w>R4)<y,w>R2?R4∧<y,w>R3?R4<y,w>(R2?R4)∩R3?R4)定理：合成運(yùn)算可結(jié)合R1:X→Y;R2:Y→Z；R3:Z→W，則有：R1?(R2

?R3)==R1?R2?R3

(R1?R2)?R3證明證明：∵

R1:X→Y;R2:Y→Z；R3:Z→W∴R1?R2:X→Z;(R1?R2)?R3

:X→W;對任意的<x,w>

(R1?R2)?R3

(z)(<x,z>R1?R2

∧

<z,w>R3)

(z)((y)(<x,y>R1∧<y,z>R2)∧<z,w>R3))(z)(y)(<x,y>R1∧<y,z>R2∧<z,w>R3)(y)(<x,y>R1∧(z)(<y,z>R2∧<z,w>R3))(y)(<x,y>R1∧<y,w>R2?

R3)<x,w>R1?

(R2?

R3)合成運(yùn)算舉例R={<1,2>,<3,4>,<2,2>}S={<4,2>,<2,5>,<3,1>,<1,3>}求：R?S，S?R;

R?S={<1,5>,<3,2>,<2,5>}S?R={<4,2>,<3,2>,<1,4>}合成運(yùn)算不滿足交換律合成運(yùn)算舉例R={<1,2>,<3,4>,<2,2>}S={<4,2>,<2,5>,<3,1>,<1,3>}求：R?(S?R)，(R?S)?R;

R?(S?R)={<3,2>}(R?S)?R={<3,2>}合成運(yùn)算滿足結(jié)合律合成運(yùn)算舉例R={<1,2>,<3,4>,<2,2>}S={<4,2>,<2,5>,<3,1>,<1,3>}求：R?R,S?SR?R={<1,2>,<2,2>}S?S={<4,5>,<3,3>,<1,1>}R2S2合成運(yùn)算的推廣R1:X1→X2;X1→Xn+1R2:X2→X3；Rn:Xn→Xn+1R1?R2?…?Rn:X1=X2=…=Xn+1=XR1=R2=…=Rn=RR1?R2?…?Rn=RnR的n次冪（2）關(guān)系R的冪R:X→X;n

N，R的n次冪Rn定義為：（1）R0是X中的恒等關(guān)系IX

:R0=IX={<x,x>|xX}（2）Rn+1=Rn?R定理設(shè)：R:X→YIX：X中的恒等關(guān)系；IY：Y中的恒等關(guān)系；則：IX?R=R?IY=

R定理（1）Rm?Rn=R:X→X;m,nN（2）(Rm)nRm+n=Rmn關(guān)系R的冪舉例設(shè)：A={a,b,c,d}R是集合A中的二元關(guān)系,且：R={<a,b>,<b,a>,<b,c>,<c,d>}求：R的冪。注意：有限集合上不同關(guān)系的數(shù)目是有限的R0=IA={<a,a>,<b,b>,<c,c>,<d,d>}R1=R={<a,b>,<b,a>,<b,c>,<c,d>}R2=R?R={<a,a>,<a,c>,<b,b>,<b,d>}R3=R2?R={<a,b>,<a,d>,<b,a>,<b,c>}R4=R3?R={<a,a>,<a,c>,<b,b>,<b,d>}=R2R5=R4?R=R2?R=R3R6=R5?R=R3?R=R2R2n+1=R3R2n=R2n>=1R0RR2R3定理|X|=nR:X→X;存在s和t，使得:

Rs=Rt

(0≤s≤t≤)證明關(guān)系是笛卡爾乘積的子集|X

X|=n2|ρ(X

X)|=即：X上最多有個(gè)不同的關(guān)系；R0R1R2…

所以：至少有兩項(xiàng)是相同的（3）合成關(guān)系的矩陣表達(dá)和圖解X={x1,x2,…,xm}Y={y1,y2,…,yn}Z={z1,z2,…,zp}R:X→YMR=(aij)m

nS:Y→ZMs=(bij)n

pR?S:X→ZMR?S=(cij)m

pMR?S=MRMs?cij=(aik∧bkj)i=1,2…,mj=1,2,…,pMR中第i行第k列元素MS中第k行第j列元素MR=ai1ai2…ainMs=b1j…bnjb2jMR?S=cijai1b1jai1b1j∧()ai2b2j∧()ai2b2jainbnjainbnj∧()∨∨∨…利用關(guān)系矩陣求合成關(guān)系矩陣舉例A={1,2,3}B={1,2,3,4}C={1,2,3,4,5}R:A→BS:B→C并具體給定為：R={<1,2>,<2,1>,<2,3>,<3,3>}S={<1,2>,<1,5>,<2,3>,<3,1>,<3,2>,<4,3>,<4,5>}求MR?SMR?S=12312345001001100111000合成關(guān)系R°S的關(guān)系矩陣MR?S合成關(guān)系R°SR?SMR1°(

MR1

°

MR1)=(MR1°

MR1)°

MR1R={<1,2>,<2,1>,<2,3>,<3,3>}S={<1,2>,<1,5>,<2,3>,<3,1>,<3,2>,<4,3>,<4,5>}={<1,3>,<2,2>,<2,1>,<2,5>,<3,1>,<3,2>}定理R:X→X，則：R是可傳遞的

R2R證明：(必要性)∴R2

R已知:R是可傳遞的

R2R對任意的<x,z>

R2=R?R(由合成關(guān)系的定義）(y)(∧)<x,y>R<y,z>R(

R可傳遞)

<x,z>

R

R是可傳遞的證明：(充分性)已知:

R2RR是可傳遞的對任意的<x,y>

R∧<y,z>R(合成關(guān)系定義）

<x,z>

R2(R2

R)

<x,z>

R可傳遞關(guān)系舉例X={1,2,3}R={<1,2>,<2,3>,<1,3>}應(yīng)用定理證明R具有可傳遞性？證明：R2∴R具有可傳遞性={<1,3>}R由R的關(guān)系圖求R2關(guān)系圖R:X→X

<xi，xk>

R°R<xi，xj>

R∧

<xj

，xk>

R

=R2R的關(guān)系圖GRR2的關(guān)系圖GR2xjxixkxixjxk在R的關(guān)系圖中，如果從結(jié)點(diǎn)xi出發(fā)經(jīng)過兩條有向邊能夠到達(dá)結(jié)點(diǎn)xk，在R2的關(guān)系圖中必有一條從xi到xk的有向邊由R的關(guān)系圖求Rn關(guān)系圖R:X→X，則：Rn的關(guān)系圖的作圖原則： 在R的關(guān)系圖中，如果從結(jié)點(diǎn)xi出發(fā)經(jīng)過n條有向邊能夠到達(dá)結(jié)點(diǎn)xk， 在Rn的關(guān)系圖中必有一條從xi到xk的有向邊。由R的關(guān)系圖求Rn關(guān)系圖舉例X={a,b,c,d}R:X→XR={<a,b>,<b,a>,<b,c>,<c,d>} 試?yán)肦的關(guān)系圖，求出R2、R3、R4的關(guān)系圖。關(guān)系R、R2、

R3、R4的關(guān)系圖R2的關(guān)系圖GR2abcdabcdR3的關(guān)系圖GR3R4的關(guān)系圖GR4abcdR2=R42、關(guān)系的求逆運(yùn)算R：X→Y將R中每一序偶的前后元素互換R的逆關(guān)系R-1:Y→XR-1={<y,x>|<x,y>∈R}求逆關(guān)系的運(yùn)算逆運(yùn)算逆運(yùn)算舉例R：X→YX={1,2,3,4}Y={a,b,c}

R={<1,a>,<2,b>,<3,c>}求：R-1R-1={<a,1>,<b,2>,<c,3>}由R的關(guān)系圖和關(guān)系矩陣求R-1的關(guān)系圖和關(guān)系矩陣R關(guān)系圖上所有的邊改變方向第i行第i列R-1的關(guān)系圖R關(guān)系矩陣的轉(zhuǎn)置矩陣R-1的關(guān)系矩陣定理R:X→YS：Y→Z：(R°S)-1=S-1°R-1證明：任意的<z,x>

(R°S)-1逆關(guān)系的定義

<x,z>

R°S合成關(guān)系的定義(y)(<x,y>R∧<y,z>S)交換率(y)(<y,z>S∧<x,y>R)逆關(guān)系的定義(y)(<z,y>S-1∧<y,x>R-1)合成關(guān)系的定義

<z,x>

S-1°R-1定理設(shè)R,S:X→Y，則:(1)(R-1)-1=R(2)(R∪S)-1=R-1∪S-1(3)(R∩S)-1=R-1∩S-1(4)(X

Y)-1=Y

X(5)(~R)-1=~(R)-1~R=X

Y-R(6)(R-S)-1=R-1-S-1(7)R=S

R-1=S-1(8)R

S

R-1

S-1(9)φ-1=φ證明：(3)(R∩S)-1=R-1∩S-1證明：任意的<y,x>

(R∩S)-1

<x,y>

R∩S

<x,y>

R∧<x,y>

S

<y,x>

R-1∧<y,x>

S-1

<y,x>

R-1∩S-1定理設(shè)R:X→X,則(1)R是對稱的

R=R-1(2)R是反對稱的

R∩R-1

Ix證明：(1)必要性已知：R是對稱的R=R-1(R

R-1且R-1

R)對任意的<x,y>

R(1)

R

R-1R是對稱的

<y,x>

R逆關(guān)系定義

<x,y>

R-1

R

R-1(2)

R-1

R對任意的<y,x>

R-1

逆關(guān)系定義

<x,y>

RR是對稱的

<y,x>

R

R-1

R證明：(1)充分性已知：R=R-1R是對稱的對任意的<x,y>

R逆關(guān)系定義

<y,x>

R-1R=R-1

<y,x>

RR是對稱的3、關(guān)系的閉包運(yùn)算R:X→X關(guān)系R′滿足(1)R′是自反的(2)R

R′(3)對任何自反的關(guān)系R"

R

R"R′

R"R的自反閉包對稱的對稱的對稱可傳遞的可傳遞可傳遞r(R)s(R)t(R)對閉包運(yùn)算的解釋關(guān)系R的閉包包含關(guān)系R具有某種性質(zhì)最小的關(guān)系關(guān)系R本身已經(jīng)具有某種性質(zhì)關(guān)系R的閉包R本身閉包運(yùn)算的舉例X={a,b,c,d}R={<a,a>,<b,b>,<a,d>,<c,d>}求：r(R)、s(R)、t(R)r(R)={<a,a>,<b,b>,<a,d>,<c,d>,<c,c>,<d,d>}R={<a,a>,<b,b>,<a,d>,<c,d>}閉包運(yùn)算的舉例s(R)={<a,a>,<b,b>,<a,d>,<c,d>,<d,a>,<d,c>}t(R)={<a,a>,<b,b>,<a,d>,<c,d>}可傳遞定理設(shè)R:X→Xr(R)=Ix是X上的恒等關(guān)系∪RIx定理設(shè)R:X→Xs(R)=∪RR-1定理設(shè)R:X→Xt(R)=∪RR2R3R4…∪∪閉包運(yùn)算的舉例X={a,b,c}R:X→XR={<a,a>,<a,b>,<b,c>}求：r(R)、s(R)、t(R)r(R)=R∪Ix={<a,a>,<a,b>,<b,c>}∪{<a,a>,<b,b>,<c,c>}s(R)=R∪R-1

{<a,a>,<a,b>,<b,c>}∪{<a,a>,<b,a>,<c,b>}={<a,a>,<a,b>,<b,c>,<b,b>,<c,c>}={<a,a>,<a,b>,<b,c>,<b,a>,<c,b>}閉包運(yùn)算的舉例（續(xù)）t(R)=R∪R2∪R3∪R4…R={<a,a>,<a,b>,<b,c>}R2=R°R={<a,a>,<a,b>,<b,c>}°{<a,a>,<a,b>,<b,c>}={<a,a>,<a,b>,<a,c>}R3=R2°R={<a,a>,<a,b>,<a,c>}°{<a,a>,<a,b>,<b,c>}=R2R4=R3°R=R2°R=R3=R2t(R)=R∪R2∪R3∪R4…=R∪R2={<a,a>,<a,b>,<a,c>,<b,c>}

定理設(shè)R:X→X

(1)R是自反的

r(R)=R.(2)R是對稱的s(R)=R.(3)R是傳遞的t(R)=R.定理設(shè)R:X→X|X|=nt(R)=∪RR2R3Rn…∪∪∪可傳遞閉包舉例A={a,b,c,d}

R={<a,b>,<b,a>,<b,c>,<c,d>}R:A→A求t(R).R2=R°R={<a,b>,<b,a>,<b,c>,<c,d>}°{<a,b>,<b,a>,<b,c>,<c,d>}={<a,a>,<a,c>,<b,b>,<b,d>}R3=R2°R={<a,a>,<a,c>,<b,b>,<b,d>}°{<a,b>,<b,a>,<b,c>,<c,d>}={<a,b>,<a,d>,<b,a>,<b,c>}R4=R2t(R)=∪RR2R3∪={<a,a>,<a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c>,<b,d>,<c,d>}可傳遞閉包舉例X={1,2,3,4,5,6,7}R:X→XR={<1,1>,<1,2>,<2,4>,<3,5>,<4,2>}求t(R).R2={<1,1>,<1,2>,<1,4>,<2,2>,<4,4>}R3={<1,1>,<1,2>,<1,4>,<2,4>,<4,2>}R4={<1,1>,<1,2>,<1,4>,<2,2>,<4,4>}=R2R5=R3t(R)=R∪R2∪R3={<1,1>,<1,2>,<1,4>,<2,2>,<2,4>,<3,5>,<4,2>,<4,4>}定理設(shè)R:X→X，則：（1）如果R是自反的s(R)、t(R)也是自反的；（2）如果R是對稱的r(R)、t(R)也是對稱的；（3）如果R是可傳遞的r(R)是可傳遞的；證明（1）∵

R是自反的

IX

R

IX

R∪R-1=s(R)

∵IXs(R)s(R)是自反的∵

R是自反的

IX

R

IX

R∪R2∪…∪Rn

IXt(R)t(R)是自反的第三節(jié)特種關(guān)系一、覆蓋和劃分二、等價(jià)關(guān)系和等價(jià)類三、相容關(guān)系和相容類四、次序關(guān)系一、覆蓋和劃分1、覆蓋定義2、劃分定義3、最大劃分4、最小劃分5、加細(xì)1、覆蓋定義A:非空集合S={S1,S2,…,Sm}(1)

Si

A(2)Si≠φi=1,2,…,m(3)S1∪S2∪…∪Sm=AA的覆蓋2、劃分定義注意：是劃分一定是覆蓋，反之不然A:非空集合S={S1,S2,…,Sm}是A的覆蓋Si∩Sj=φi≠jA的劃分m為劃分的秩Si為劃分的類劃分和覆蓋的圖形表示覆蓋和劃分的舉例S={1,2,3,4,5,6}判斷下列集合是覆蓋還是劃分？(1)A1={{1,2,3},{4,5,6}}(2)A2={{1},{2,3,6},{4,5}}(3)A3={{1},{2},{3},{4},{5},{6}}(4)A4={{1,2,3},{3,4},{3,5,6}}(5)A5={{1,2,3},{4,5}}(6)A6={{1,2,3,4,5,6}}覆蓋劃分覆蓋劃分覆蓋劃分覆蓋不是覆蓋覆蓋劃分3、最大劃分由單個(gè)元素構(gòu)成的子集為元素的集合秩最大的劃分最大劃分舉例A={a,b,c,d}S1={a},S2=,S3={c},S4=qgzmgk7S={S1,S2,S3,S4}最大劃分={{a},,{c},umrxtpt}4、最小劃分秩為1的劃分集合的全部元素組成的一個(gè)子集為元素的集合最小劃分舉例A={a,b,c,d}S1={a,b,c,d}最小劃分S={S1}={{a,b,c,d}}5、加細(xì)A:非空集合{A1,A2,…,Ar}{B1,B2,…,Bs}A的劃分若對于每個(gè)Ai

均有Bj使得Ai

Bj{A1,A2,…,Ar}是{B1,B2,…,Bs}的加細(xì){A1,A2,…,Ar}{B1,B2,…,Bs}≠真加細(xì)加細(xì)舉例X={a,b,c}

給出X集合的5個(gè)不同的劃分A、B、C、D、E；問哪些劃分是哪些劃分的加細(xì)？解答A={{a,b,c}}={A1}B={{a,b},{c}}={B1,B2}C={{a},{b,c}}={C1,C2}D={{a,c},}={D1,D2}E={{a},,{c}}={E1,E2,E3}B1

A1B2

A1B是A的加細(xì)C1

A1C2

A1C是A的加細(xì)D1

A1D2

A1D是A的加細(xì)E是A、B、C、D的加細(xì)證明劃分舉例 設(shè){A1,A2,…,An}是集合A的劃分，若Ai∩B≠φ(1≤i≤n) 試證明{A1∩B,A2∩B,…,An∩B}是A∩B的劃分。證明：(1)(A1∩B)∪(A1∩B)∪…∪(An∪B)=A∩B=A∩B∵{A1,A2,…,An}是集合A的劃分∴A1∪A2∪…∪An=

A(A1∩B)∪(A2∩B)∪…∪(An∩B)=(A1∪A2∪…∪An)∪B證明：(續(xù))(2)Ai∩B

A∩B(1≤i≤n)∵{A1,A2,…,An}是集合A的劃分∴Ai

A(1≤i≤n)∴Ai∩B

A∩B證明：(續(xù))(3)(Ai∩B)∩(Aj∩B)=φ(i≠j)∵{A1,A2,…,An}是集合A的劃分∴Ai∩Aj=φ(i≠j)∴(Ai∩B)∩(Aj∩B)=Ai∩Aj∩B=φ∩B=φ 綜上：{A1∩B,A2∩B,…,An∩B}是A∩B的劃分二、等價(jià)關(guān)系和等價(jià)類1、等價(jià)關(guān)系2、模m同余關(guān)系3、等價(jià)類4、商集1、等價(jià)關(guān)系等價(jià)關(guān)系R:X→X自反的對稱的可傳遞的等價(jià)關(guān)系舉例X={1,2,3,4}R={<1,1>,<1,4>,<2,2>,<2,3>,<3,2>,<3,3>,<4,1>,<4,4>}驗(yàn)證:R是X上的等價(jià)關(guān)系.自反的對稱的可傳遞的等價(jià)關(guān)系2、模m同余關(guān)系模m同余關(guān)系是一個(gè)典型的等價(jià)關(guān)系。m

I+x,y,tI,若x-y=tmx模m等價(jià)于yx≡y(modm)x除m與y除m所得余數(shù)相同舉例：模4同余關(guān)系∵0、4、8、…、4k＋4除4所得余數(shù)均為0，∴0≡4(mod4)≡8(mod4)≡…≡4k(mod4)∵1、5、9、…、4k＋1除4所得余數(shù)均為1，∴1≡5(mod4)≡9(mod4)≡…≡(4k＋1)(mod4)∵2、6、10、…、4k＋2除4所得余數(shù)均為2，∴2≡6(mod4)≡10(mod4)≡…≡(4k＋2)(mod4)∵3、7、11、…、4k＋3除4所得余數(shù)均為3，∴3≡7(mod4)≡11(mod4)≡…≡(4k＋3)(mod4)舉例：模4同余關(guān)系(續(xù))整數(shù)集合I{…-4,0,4,8,…,4k,…}{…-3,1,5,9,…,4k+1,…}{…-2,2,6,10,…,4k+2,…}{…-1,3,7,11,…,4k+3,…}I1I2I3I4子集內(nèi)的任何兩個(gè)元素均有模4同余關(guān)系S={I1,I2,I3,I4}整數(shù)集合I的一個(gè)劃分證明：模m同余關(guān)系是等價(jià)關(guān)系（1）自反性：(a≡a(modm))對任意的元素a

I，均有：a-a=0

m0

I∴a≡a(modm)（2）對稱性：a≡b(modm)

b≡a(modm)a、b

Ia≡b(modm)

a-b=tm

b-a=(-t)mt

I-t

I

b≡a(modm)證明：(續(xù))(3)可傳遞性：a≡b(modm)∧b≡c(modm)

a≡c(modm)a、b、c

Ia≡b(modm)∧b≡c(modm)

(a-b=tm)t

I∧(b-c=sm)s

I

a-c=(s+t)ms+t

I

a≡c(modm)證明題舉例R:A→A對稱的可傳遞的 如果對于A中的每一個(gè)元素a，在A中也同時(shí)存在一個(gè)b，使得<a,b>

R證明：R是一個(gè)等價(jià)關(guān)系只需證明R是自反的證明對于任意的元素aA<a,a>

R對于任意的元素aA（已知）

<a,b>

R(R是對稱的)

<a,b>

R∧<b,a>

R(R是可傳遞的)

<a,a>

R∴R是自反的3、等價(jià)類R:X→X的等價(jià)關(guān)系對于任何x∈X[x]R

X定義為:[x]R＝{y|y∈X,xRy}由x生成的R等價(jià)類由集合X中與x有等價(jià)關(guān)系R的那些元素組成的等價(jià)類舉例X={1,2,3,4}R:X→XR={<1,1>,<1,4>,<4,1>,<4,4>,<2,2>,<2,3>,<3,2>,<3,3>}求：X中各元素的R等價(jià)類。[1]R＝{1,4}[2]R＝{2,3}[3]R＝{2,3}=[4]R＝{1,4}=等價(jià)類的性質(zhì)(1)對任意元素x

Xx

[x]R(2)xRy[x]R[y]R＝(3)xyR[x]R[y]R∩＝φ證明：性質(zhì)1∵R是等價(jià)關(guān)系∴R是自反的，即：(

x)(x

X→<x,x>

R)

由等價(jià)類的定義可知：x

[x]R證明：性質(zhì)2xRy[x]R[y]R＝([x]R

[y]R,[y]R

[x]R)①對任意的z

[x]RxRz等價(jià)類定義對稱性zRx已知xRyzRx∧xRy可傳遞性zRy對稱性yRz

z

[y]R等價(jià)類定義[x]R

[y]R同理:[y]R

[x]R證明：性質(zhì)3反證法：假設(shè)：xyR但[x]R∩[y]R

≠φ則至少有一個(gè)元素z

[x]R∩[y]R

z

[x]R∧z

[y]R等價(jià)類定義xRz∧yRz對稱性xRz∧zRy可傳遞性

xRy與假設(shè)矛盾∴結(jié)論成立由等價(jià)類的性質(zhì)(2)(3)可知對任意的x,y

X給定集合X上的等價(jià)關(guān)系R或者[x]R＝[y]R或者[x]R∩[y]R

＝φ由R可以確定集合X上的一個(gè)劃分定理則R的等價(jià)類集合是X的一個(gè)劃分R:X→X的等價(jià)關(guān)系非空集合{[x]R|x

X}定理證明 要證明{[x]R|x

X}是X的一個(gè)劃分，就要證明其滿足劃分的三個(gè)條件：（1）[x]R

X且[x]R≠φ

（2）[x1]R∪[x2]R∪…∪[xn]R=X（3）[x]R∩

[y]R＝φ（x≠y）證明（1）對任意的x

X等價(jià)類定義

[x]R

X對任意的x

X自反性

x

[x]R

[x]R≠φ證明（2）證明[x1]R∪[x2]R∪…∪[xn]R=X[x1]R∪[x2]R∪…∪[xn]R

XX

[x1]R∪[x2]R∪…∪[xn]R[x1]R∪[x2]R∪…∪[xn]R

X對任意的xi

[x1]R∪[x2]R∪…∪[xn]Rxi

[xi]R[xi]R

XxiX[x1]R∪[x2]R∪…∪[xn]R

XX

[x1]R∪[x2]R∪…∪[xn]R對任意的xiX自反性xi

[xi]Rxi

[x1]R∪[x2]R∪…∪[xn]R[xi]R

[x1]R∪[x2]R∪…∪[xn]RX

[x1]R∪[x2]R∪…∪[xn]R證明（3）由等價(jià)類的性質(zhì)(2)和(3)可知:對任意的x,y

X或者[x]R＝[y]R或者[x]R∩[y]R

＝φ{(diào)[x]R|x

X}是X的一個(gè)劃分由等價(jià)關(guān)系R確定的劃分舉例X={1,2,3,4}R:X→XR={<1,1>,<1,4>,<4,1>,<4,4>,<2,2>,<2,3>,<3,2>,<3,3>}求：由等價(jià)關(guān)系R所確定的集合X的一個(gè)劃分。[1]R=[4]R={1,4}[2]R=[3]R={2,3}S={[1]R，[2]R}={{1,4},{2,3}}劃分4、商集等價(jià)關(guān)系可以構(gòu)成集合的一個(gè)劃分，即商集。R:A→A的等價(jià)關(guān)系非空集合R的等價(jià)類集合{[a]R|a∈A}按R去劃分A的商集A/R={[a]R|a∈A}全關(guān)系所確定的劃分R=X

X全關(guān)系（1）R是等價(jià)關(guān)系（2）X中的每一個(gè)元素和X上的所有元素都有R關(guān)系按R去劃分X的商集X/R={X}最小劃分恒等關(guān)系所確定的劃分最大劃分和最小劃分均稱為平凡劃分。IX={<x,x>|x

X}（1）IX是等價(jià)關(guān)系（2）X中的每一個(gè)元素僅與自身有IX關(guān)系按IX去劃分X的商集X/IX是集合X的最大劃分舉例設(shè)：X={1,2,3}求：按集合X上的全關(guān)系R和恒等關(guān)系IX去劃分X的商集X/R和X/IX

解答R=X

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

X/R={{1,2,3}}[1]R={1,2,3}=[2]R=[3]R解答IX={<1,1>,<2,2>,<3,3>}X/IX={{1},{2},{3}}[1]R={1}[2]R={2}[3]R={3}商集舉例R:整數(shù)集合I上的模3同余關(guān)系R={<x,y>|x∈I∧y∈I∧x≡y(mod3)}求：按R去劃分I的商集I/R。解答[0]R={…,-3,0,3,6,9,…}[1]R={…,-2,1,4,7,10,…}[2]R={…,-1,2,5,8,11,…}…=[-3]R=[0]R=[3]R=……=[-2]R=[1]R=[4]R=……=[-1]R=[2]R=[5]R=…商集I/R={[0]R，[1]R，[2]R}定理X:非空集合C={C1,C2,…,Cm}是X的一個(gè)劃分xRy

(Ci)(CiC∧xCi∧yCi)由劃分C導(dǎo)出的X中的等價(jià)關(guān)系R=(C1

C1)(C2

C2)(Cm

Cm)∪∪…∪舉例S={1,2,3,4,5,6,7,8,9,10}R是由x≡y(mod5)定義的S上的等價(jià)關(guān)系。求：由R導(dǎo)出的S的劃分。R={<1,1>,<1,6>,<2,2>,<2,7>,<3,3>,<3,8>,<4,4>,<4,9>,<5,5>,<5,10>,<6,6>,<6,1>,<7,7>,<7,2>,<8,8>,<8,3>,<9,9>,<9,4>,<10,10>,<10,5>}解答[1]R={1,6}[2]R={2,7}[3]R={3,8}[4]R={4,9}[5]R={5,10}S/R={[1]R,[2]R,[3]R,[4]R,[5]R}={{1,6},{2,7},{3,8},{4,9},{5,10}}舉例 求集合X={1,2,3,4,5}中的等價(jià)關(guān)系R，使它能產(chǎn)生劃分S={{1,2},{3},{4,5}}，并畫出R的關(guān)系圖。C1C2C3R=({1,2}

{1,2})({3}

{3})({4,5}

{4,5})∪∪={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>,<4,4>,<4,5>,<5,4>,<5,5>}等價(jià)關(guān)系與集合劃分之間的對應(yīng)關(guān)系（1）給定集合X上的等價(jià)關(guān)系，一定確定集合X上的一個(gè)劃分，即商集；（2）給定集合X上的一個(gè)劃分，也一定確定集合X上的等價(jià)關(guān)系R：R=(C1

C1)∪(C2

C2)∪…∪(Cm

Cm)三、相容關(guān)系和相容類1、相容關(guān)系2、相容類3、最大相容類4、尋找最大相容類的關(guān)系圖法5、完全覆蓋相容關(guān)系R:X→X自反的對稱的1、相容關(guān)系xRyx和y有相容關(guān)系xRyx和y沒有相容關(guān)系是等價(jià)關(guān)系一定是相容關(guān)系，反之不然。簡化的相容關(guān)系圖相容關(guān)系的關(guān)系圖特點(diǎn)：（1）任意結(jié)點(diǎn)都有自回路；（2）兩個(gè)結(jié)點(diǎn)間如果有有向邊必成對出現(xiàn)；化簡原則：（1）去掉每個(gè)結(jié)點(diǎn)的自回路；（2）用一條無向邊代替方向相反的有向邊；簡化的相容關(guān)系矩陣相容關(guān)系的關(guān)系矩陣特點(diǎn)：（1）主對角線元素均為“1”；（2）關(guān)于主對角線對稱的對稱陣；化簡原則：只保留下三角陣；2、相容類由R產(chǎn)生的相容類R:X→X的相容關(guān)系S≠ΦS

X對于任意兩個(gè)元素x,y∈SxRy相容類舉例R={<x1,x1>,<x1,x2>,<x1,x4>,<x2,x1>,<x2,x2>,<x2,x3>,<x2,x4>,<x2,x5>,<x3,x2>,<x3,x3>,<x3,x5>,<x4,x1>,<x4,x2>,<x4,x4>,<x4,x5>,<x5,x2>,<x5,x3>,<x5,x4>,<x5,x5>} 試給出由相容關(guān)系R產(chǎn)生的若干個(gè)相容類和非相容類的例子。解答 {x1,

x2}、{x2,x3}、{x3}、{x1,

x2,x4}、{x2,x3,x5}、{x2,x4,x5}、{x4,x5}等，均為由相容關(guān)系R產(chǎn)生的相容類。 {x1,

x2,x3,x4}不是相容類：因?yàn)閤1和x3、x3和x4都沒有相容關(guān)系R。C1={{x1,

x2},{x3},{x4,x5}}C2={{x1,

x2},{x3},{x2,x4,x5}}C3={{x1,

x2,x4},{x2,x3,x5},{x2,x4,x5}}都是集合X的覆蓋。3、最大相容類R:X→X的相容關(guān)系S≠ΦS

XS滿足(1)任一xS，都與S中的所有其他元素有相容關(guān)系R；(2)X-S中沒有任何一個(gè)元素能與S中的所有元素都有相容關(guān)系R；由R產(chǎn)生的最大相容類最大相容類舉例 如下7個(gè)相容類中，哪些是最大相容類？哪些不是最大相容類？為什么？(1){x1,

x2}(2){x2,x3}(3){x3}(4){x1,

x2,x4}(5){x2,x3,x5}(6){x2,x4,x5}(7){x4,x5}×x4×x5×√√√×x24、尋找最大相容類的關(guān)系圖法（1）畫出相容關(guān)系R的簡化關(guān)系圖；（2）每個(gè)“最大完全多邊形”的結(jié)點(diǎn)集合，就是R的一個(gè)最大相容類；最大相容類舉例A={1,2,3,4,5,6}；R1、R2是A上的相容關(guān)系；對應(yīng)的簡化關(guān)系圖如下，求最大相容類。解答R1的最大相容類：{1,2,5}{1,3,5}{3,4}{4,6}解答R2的最大相容類：{1,2,6}{2,3,5,6}{4}5、完全覆蓋集合X的完全覆蓋R:X→X的相容關(guān)系R的最大相容類組成的集合定理 集合X上的相容關(guān)系R與完全覆蓋存在一一對應(yīng)的關(guān)系，即： R的最大相容類組成的集合確定了集合X的一個(gè)覆蓋。定理 給定集合X的覆蓋C={A1,A2,…,An},由它確定的關(guān)系:R=(A1×A1)∪(A2×A2)

∪…∪(An×An)是X中的相容關(guān)系.相容關(guān)系決定唯一的完全覆蓋，反之亦然。舉例給定集合X={a,b,c,d,e}上的一個(gè)覆蓋C：C={{a,b},{b,c},{c,d,e}}試求由此覆蓋導(dǎo)出的相容關(guān)系。A1A2A3R=({a,b}

{a,b})∪({b,c}

{b,c})∪({c,d,e}

{c,d,e})={<a,a>,<a,b>,<b,a>,<b,b>,<b,c>,<c,b>,<c,c>,<c,d>,<c,e>,<d,c>,<d,d>,<d,e>,<e,c>,<e,d>,<e,e>}R是自反的、對稱的∴R是相容關(guān)系四、次序關(guān)系1、偏序關(guān)系與哈斯圖2、擬序關(guān)系、良序關(guān)系、全序關(guān)系注意：次序關(guān)系的共同點(diǎn)：可傳遞性1、偏序關(guān)系與哈斯圖(1)偏序關(guān)系(2)蓋住關(guān)系(3)哈斯圖的作圖方法(4)最大成員和最小成員(5)極大成員和極小成員(6)上界和下界(7)上確界和下確界(1)偏序關(guān)系R:P→P自反的反對稱的傳遞的偏序關(guān)系≤序偶<P,≤>偏序集集合偏序關(guān)系對偏序關(guān)系符號“≤

”的解釋實(shí)數(shù)集上的“≤”關(guān)系自反的反對稱的傳遞的偏序關(guān)系x≤yx小于或等于yx在y之前y在x之上借用偏序關(guān)系在Hass圖中的位置偏序關(guān)系舉例 給定集合A={1,2,3,4,6,8,12,24},“≤”={<x,y>|x,y

A∧x整除y}驗(yàn)證“≤”是偏序關(guān)系.解答“≤”=