關系與序關系

關系與序關系第1頁，共76頁，2023年，2月20日，星期三2.1關系的概念[例]設A={Alice,Bob,Tom},B={Algebra,Graphs,Sets}Alice選修了Graphs,Bob選修了Algebra,Graph和Sets;Tom選修了Algebra,Graphs;R={<Alice,Graphs>,<Bob,Algebra>,<Bob,Graphs>,<Bob,Sets>,<Tom,Algrbra>,<Tom,Graphs>}AB,表示了學生集合A與課程集合B之間的選修關系。第2頁，共76頁，2023年，2月20日，星期三2.1關系的概念[二元關系的一般性描述]

一對對象之間的關系稱為二元關系。[例]

teachers={a,b,c}，students={x,y,z}

建立教學關系T:aTxiffaTEACHINGx用序偶集合表示為：

T={<a,x>,<a,z>,<b,y>,<c,y>,<c,z>}Tteachersstudents圖示為：第3頁，共76頁，2023年，2月20日，星期三2.1關系的概念[例]

Subroutines={a,b,c,d,e}子程序間調(diào)用關系圖示為：Calling={<a,a>,<a,b>,<a,d>,<b,a>,<b,c>,<c,c>,<c,e>,<d,d>}CallingSubroutinesSubroutines第4頁，共76頁，2023年，2月20日，星期三2.1關系的概念[二元關系的集合定義]

設X,Y是兩個集合，XY的任何一個子集

R都確定了一種二元關系，稱為從X到Y的二元關系。

<x,y>R可記為xRy，顯然RXY

<x,y>R可記為xRy當X=Y即X與Y同一時，稱R為X上的一個二元關系。第5頁，共76頁，2023年，2月20日，星期三2.1關系的概念[例]

F={<x,y>|x是y的父親}

S={<x,y>|x,y為正整數(shù)且x可整除y}T={<y2,y>|y為實數(shù)}對上述的：x，y，R，有<x,y>R或

<x,y>R，二者必居其一。第6頁，共76頁，2023年，2月20日，星期三2.1關系的概念[定義域]設二元關系S。由<x,y>S的所有對象x組成的集合稱為S的定義域，記為Dom(S)。[值域]由<x,y>S的所有對象y組成的集合稱為S的值域，記為Ran(S)(Range(S))。記

F(S)=D(S)R(S)，稱為S的域。描述：Dom(S)={x|(y)(<x,y>S)}Ran(S)={y|(x)(<x,y>S)}第7頁，共76頁，2023年，2月20日，星期三2.1關系的概念若干特殊關系：①

X到Y的全域關系：Ex,y=XY

特別地：

Ex,x=XX②空關系：

③恒等關系：Ix={<xi,xi>|xiX}[例]設X={1,2,3,4}，求X上的關系“>”(大于)及其定義域、值域。第8頁，共76頁，2023年，2月20日，星期三2.2關系的表示方法(1)集合表示法借用集合的各種描述方法對表示關系的序偶集合進行描述(2)關系矩陣設X={x1,x2,…,xm}，Y={y1,y2,…,yn}，m,n<+R是X到Y的二元關系。構造矩陣MR=[mij]mn，mij

=<xi,yj>R0其它第9頁，共76頁，2023年，2月20日，星期三2.2關系的表示方法[例]非0行對應元素構成D(S)非0列對應元素構成R(S)第10頁，共76頁，2023年，2月20日，星期三2.2關系的表示方法(3)關系圖表示法用結點表示X、Y上的元素；若<x,y>R則從結點x到結點y畫一條弧。[例]上述Teaching關系的關系圖：第11頁，共76頁，2023年，2月20日，星期三2.2關系的表示方法[例]設X={1,2,3,4}，X上的關系“>”：第12頁，共76頁，2023年，2月20日，星期三2.3關系的性質(zhì)[定義]設R是X上的二元關系，則：①R是自反的(x)(xXxRx)②R是對稱的(x)(y)(x,yXxRyyRx)③R是傳遞的(x)(y)(z)(x,y,zXxRyyRz

xRz)④R是反自反的(x)(xX?(xRx))⑤R是反對稱的(x)(y)(x,yXxRyyRx

x=y)第13頁，共76頁，2023年，2月20日，星期三2.2關系的性質(zhì)[習題]

設X={1,2,3,4}，畫出X上的關系“>”，“”和整除“|”的關系圖和關系矩陣，并判斷其性質(zhì)。[習題]集合上的”isanelement”以及”isasubset”具有什么性質(zhì)？第14頁，共76頁，2023年，2月20日，星期三2.3關系的性質(zhì)[例]正整數(shù)集合上的若干關系及其性質(zhì)整除=≤＜自反性對稱性傳遞性反自反性反對稱性判定關系“＜”的反對稱性的前提條件總為F,反對稱性成立。第15頁，共76頁，2023年，2月20日，星期三2.3關系的性質(zhì)從關系矩陣和關系圖看關系的性質(zhì)：R是自反的：MR的對角元均為1；關系圖為自環(huán)圖。R是對稱的：MR為對稱矩陣；關系圖中弧成對出現(xiàn)。R是反自反的：MR的對角元均為0；關系圖為無自環(huán)圖。R是反對稱的：MR為反對稱矩陣；關系圖中只出現(xiàn)單向弧。第16頁，共76頁，2023年，2月20日，星期三2.3關系的性質(zhì)存在著既非自反也非反自反的關系，如：存在著既對稱又反對稱的關系，如：第17頁，共76頁，2023年，2月20日，星期三2.3關系的性質(zhì)存在著既非對稱又非反對稱的關系，如：第18頁，共76頁，2023年，2月20日，星期三2.4集合的劃分與覆蓋[定義]給定集合S，A={A1,A2,…,An}，AiS，i=1..n。②若①成立且AiAj=(若ij)，則說A是S的一個劃分，并稱A1,A2,…,An為此劃分的塊。第19頁，共76頁，2023年，2月20日，星期三2.4集合的劃分與覆蓋[例]

N={0,1,2,3,4,……}自然數(shù)集合。取A0={0,6,12,18,……}A1={1,7,13,19,……}A2={2,8,14,20,……}……A5={5,11,17,23,……}則A={A0，A1，A2，A3，A4，A5}是N的一個劃分。第20頁，共76頁，2023年，2月20日，星期三2.4集合的劃分與覆蓋[例]

S={a,b,c}取A={{a},,{c}}B={{a,b},{c}}C={{a,b,c}}均構成對S的劃分。顯然有|A|>|B|>|C|

可以將A稱為最大劃分；將C稱為最小劃分。第21頁，共76頁，2023年，2月20日，星期三關系IX

具有自反、對稱和傳遞性；設X={1,2,3,4}，寫出X上的模２同余關系，并判斷其是否具有自反、對稱和傳遞等性質(zhì)。具有自反、對稱和傳遞性的關系稱為等價關系。第22頁，共76頁，2023年，2月20日，星期三2.5等價關系[等價關系]

集合X上的關系R若具有自反性、對稱性和傳遞性，則稱R為X上的一個等價關系。[例]

N上的模6同余關系

R={<x,y>|x,yN(xy)=6L，L為整數(shù)}自反性：對稱性：傳遞性：第23頁，共76頁，2023年，2月20日，星期三2.5等價關系[定理]N上的模m同余關系是等價關系。[證明]自反性：xx=0，故xx=mL，這里L=0。對稱性：設xRy

即xy=mL，L為整數(shù)則yx=mL，故yRx。傳遞性：設xRy

且yRz，即

xy=mL1，yz=mL2

，L1、L2

為整數(shù)則xz=mL1+mL2=m(L1+L2)

故xRz第24頁，共76頁，2023年，2月20日，星期三2.5等價關系[等價類]

設R為X上的一個等價關系，對任何xX，所有與x有關系R的元素的集合，稱為X上由x生成的R–等價類。記為[x]R。

[x]R={y|yXxRy}[例]

X={1,2,3,4,5,6,7}，R為X上的模3同余關系。則[1]R={1,4,7}，[2]R={2,5}，[3]R={3,6}第25頁，共76頁，2023年，2月20日，星期三2.5等價關系[性質(zhì)]設R為X上的一個等價關系，則①

X中的任何一個元素，至少屬于一個等價類。②若x,yX，則x,y或?qū)偻坏葍r類，或?qū)賰蓚€不同等價類但此兩個不同等價類的交集為（不相交）。[證明]第26頁，共76頁，2023年，2月20日，星期三2.5等價關系[結論]對X上的等價關系R，①任意xX屬于且只屬于一個等價類；②若xRy，則[x]R=[y]R，否則

[x]R[y]R=。第27頁，共76頁，2023年，2月20日，星期三2.5等價關系[定理]

集合X上的一個等價關系R產(chǎn)生對此集合的一個劃分，該劃分的塊對應于R的等價類。[證明]由上述結論得到。將該劃分記作：X/R={[x]R|xX}第28頁，共76頁，2023年，2月20日，星期三2.5等價關系[定理]X上的任意劃分均可確定一個等價關系。[證明]設X上的一個劃分為A={A1,A2,…,An}，定義

R={<x,y>|x,yX(Ai)(AiAxAiyAi)}

可以證明R具有自反性：對稱性：傳遞性：第29頁，共76頁，2023年，2月20日，星期三2.5等價關系[問題]X上由不同方法定義的等價關系R1、R2，若產(chǎn)生的等價類相同，則R1=R2。不等價關系也能產(chǎn)生劃分。第30頁，共76頁，2023年，2月20日，星期三2.6相容關系[相容關系]

X上的二元關系R，若R是自反的、對稱的，則稱R為X上的一個相容關系，記作。[例]

X={2661,243,315,648,455}R={<x,y>|x,yX，x與y至少含有一個相同數(shù)字}容易看出，R具有自反性、對稱性。

R不具有傳遞性：如<2661,243>,<243,455>R但<2661,455>R因此R不是等價關系，R是一個相容關系。第31頁，共76頁，2023年，2月20日，星期三2.6相容關系[相容類]

設AX，是X上的一個相容關系。稱A是X上的一個相容類當且僅當A中任二元素相容。即(x)(y)(x,yA

x

y)。[最大相容類]

設A是X上的一個相容類，若X-A中不存在與A中所有元素相容的元素，則稱A為X的一個最大相容類。在相容關系的關系圖中，最大相容類對應于一個最大完全子圖。第32頁，共76頁，2023年，2月20日，星期三2.6相容關系例如，在上圖表示的相容關系中，最大相容類為:{a,b,d,f},{d,c,f},{d,e},{g}[問題]相容類與覆蓋的關系。第33頁，共76頁，2023年，2月20日，星期三2.7關系的運算(1)關系的一般運算[定義]

設R、S是X到Y的二元關系，定義運算如下：

RS={<x,y>|xRyxSy}RS={<x,y>|xRyxSy}RS={<x,y>|xRyxSy}~R=XYR第34頁，共76頁，2023年，2月20日，星期三2.7關系的運算(2)

關系的復合運算[復合關系]

設二元關系R:XY，S:YZ，則稱

S

R={<x,z>|xXzZ(y)(yYxRyySz)}

為R和S的復合關系。注意,關系的復合運算定義和函數(shù)復合保持了一致。在某些課本上，以上關系的復合記作RS。第35頁，共76頁，2023年，2月20日，星期三2.7關系的運算[例]

X={x1,x2,x3}，Y={y1,y2,y3,y4}，Z={z1,z2,z3}R={<x1,y1>,<x2,y3>,<x2,y4>}S={<y1,z3>,<y2,z1>,<y4,z2>}顯然有：Dom(SR)Dom(R)Ran(SR)Ran(S)SR={<x1,z3>,<x2,z2>}第36頁，共76頁，2023年，2月20日，星期三2.7關系的運算關系的復合運算沒有交換律。[定理]

關系復合運算的結合律：設二元關系

R：XY，S：YZ，P：ZW，則有(PS)R=P(SR)[證明]第37頁，共76頁，2023年，2月20日，星期三2.7關系的運算[定理]

關系復合運算與一般運算的結合律：設二元關系R1,R2

：XY，S1,S2：YZ，則有(S1S2)R1=(S1

R1)(S2

R1)(S1S2)R1

(S1R1)(S2R1)S1

(R1R1)=(S1R1)(S1R2)S1(R1R2)

(S1R1)(S1R2)[證明]第38頁，共76頁，2023年，2月20日，星期三2.7關系的運算[關系的冪運算]設R為X上的二元關系，RR…R記為Rn，規(guī)定Rn=Rn1R，R0=IX第39頁，共76頁，2023年，2月20日，星期三2.7關系的運算(3)關系的逆運算[逆關系]

設二元關系R：XY，定義

R-1={<y,x>|xXyY<x,y>R}為R的逆關系。[性質(zhì)](R-1)-1=R，-1= (RS)-1=R-1S-1

，(RS)-1=R-1S-1

(~R)-1=~(R-1)(SR)-1=R-1S-1

R=SR-1=S-1 RSR-1S-1 第40頁，共76頁，2023年，2月20日，星期三2.7關系的運算[問題]設Ａ上關系R，S的關系矩陣分別為ＭR,MS,試求SR的關系矩陣。第41頁，共76頁，2023年，2月20日，星期三2.7關系的運算(4)關系的閉包運算[閉包]

設R為X上的二元關系，若另有一關系R，滿足：①

R是自反的（對稱/傳遞）；②

RR；③對于任何自反（對稱/傳遞）的關系R，若

RR，則RR。則稱R為R的自反（對稱/傳遞）閉包，記為r(R)(s(R)/t(R))。第42頁，共76頁，2023年，2月20日，星期三2.7關系的運算[例]整數(shù)集上的“＜”關系的自反閉包是“≤”，對稱閉包是“≠”，傳遞閉包仍然是“＜”。[例]整數(shù)“=”的自反、對稱、傳遞閉包都是它本身。[例]有關系矩陣求Mr(R)、Ms(R)、Mt(R)第43頁，共76頁，2023年，2月20日，星期三2.7關系的運算第44頁，共76頁，2023年，2月20日，星期三2.7關系的運算[定理]設R為X上的二元關系，則①

r(R)=RIx②s(R)=RR-1[證明]③

1)Rt(R)

(t(R)表示右式無窮并）

2)

t(R)是傳遞的；

3)如果R’是包含R的傳遞關系，則對于任意n,RnR’,所以，t(R)是包含R的最小傳遞關系。第45頁，共76頁，2023年，2月20日，星期三2.7關系的運算問題：如何求傳遞閉包呢？設R是A上的關系，|A|=n,則

t(R)=RR1…Rn這是因為如果從x到y(tǒng)有道路相連，則存在長度不超過n的道路。求傳遞閉包的Washall算法。參閱課本。第46頁，共76頁，2023年，2月20日，星期三2.7關系的運算容易證明：R是自反的當且僅當r(R)=R；R是對稱的當且僅當s(R)=R;R是傳遞的當且僅當t(R)=R.問題：設R是A上的關系r(RS)=r(R)r(S)?s(RS)=s(R)s(S)?t(RS)=t(R)t(S)?如果將并換成交呢？第47頁，共76頁，2023年，2月20日，星期三2.8偏序關系[偏序關系(partialorder)]

集合A上的一個關系R滿足自反性、反對稱性和傳遞性時，稱R是A上的一個偏序關系，記為“”，用二元組〈A,〉表示該偏序結構，或稱之為偏序集。[例]

A={2,3,6,8},“”={<x,y>|x,yA(x整除y)}

“”={……..}

容易驗證，上述關系為偏序關系。第48頁，共76頁，2023年，2月20日，星期三2.8偏序關系x、y之間存在偏序關系時，說x、y（在該關系下）可比較，否則說x、y

不可比較。上例中，2和3不可比較（在上述定義的“”下）。[蓋住]

蓋?。ňo鄰遮蓋）。設〈A,〉，x，yA，

y蓋住xxyxy(z)((xzzy)(x=zy=z))

記covA={<x,y>|x,yA(y蓋住x)}第49頁，共76頁，2023年，2月20日，星期三2.8偏序關系表達偏序關系的Hasse圖設有偏序關系<A,>①用結點表示集合元素②若<x,y>covA，則用線段連接結點x,y，且令x(小者)在y的下方。第50頁，共76頁，2023年，2月20日，星期三2.8偏序關系Hasse圖如右圖①默認aa,bb,cc自反性②

ac,cb③

ab傳遞性acbHasseDiagram[例]集合A={a,b,c}上的偏序關系為：

{<a,a>,<b,b>,<c,c>,<a,c>,<c,b>,<a,b>}

covA＝{<a,c>,<c,b>}第51頁，共76頁，2023年，2月20日，星期三2.8偏序關系上述Hasse圖表示的對應關系集合為：

{<a,a>,<b,b>,<c,c>,<a,c>,<c,b>,<a,b>}對應關系圖如下：acbHasseDiagramacb關系圖第52頁，共76頁，2023年，2月20日，星期三2.8偏序關系[例]由偏序關系的關系圖構造相應的Hasse圖cab關系圖dabcHasseDiagramd第53頁，共76頁，2023年，2月20日，星期三2.8偏序關系[例]{2,3,6,12,24,36,17}上的整除關系的Hasse圖。HasseDiagram26243612317第54頁，共76頁，2023年，2月20日，星期三2.8偏序關系[例]

A的冪集上的關系的Hasse圖。A={a}{a}{a,b}A={a,b}{a}第55頁，共76頁，2023年，2月20日，星期三2.8偏序關系[例]

A的冪集上的關系的Hasse圖。{a,b,c}A={a,b,c}{a}{c}{a,b}{a,c}{b,c}第56頁，共76頁，2023年，2月20日，星期三2.8偏序關系[最大最小元]

對偏序集<A,>y0A為最小元(x)(xAy0x)y0A為最大元(x)(xAxy0)[定理]

<

A,>中最大(最小)元若存在則唯一。[證明][極大極小元]

對<

A,>y0A為極小元(x)(xAxy0?(x

y0))y0A為極大元(x)(xAxy0?(y0x))第57頁，共76頁，2023年，2月20日，星期三2.8偏序關系[例]{2,3,6,12,24,36}上的整除關系的Hasse圖。2624361232,3為極小元24,36為極大元沒有最小元和最大元第58頁，共76頁，2023年，2月20日，星期三2.8偏序關系[例]

A的冪集上的關系的Hasse圖。{a,b,c}A={a,b,c}{a}{c}{a,b}{a,c}{b,c}

為最小元{a,b,c}為最大元第59頁，共76頁，2023年，2月20日，星期三2.8偏序關系[上下界]

對<

A,>,BA,aA

a是B的一個上界(x)(xBx

a)

a是B的一個下界(x)(xBax)說明：a不一定是B的元素，即可能aA-BB的上(下)界不一定存在，存在也不一定唯一。第60頁，共76頁，2023年，2月20日，星期三2.8偏序關系[例]{2,3,6,12,24,36}上的整除關系的Hasse圖。262436123令B1={2,3,6}B1的上界是6,12,24,366B1，而12,24,36B1

B1沒有下界令B2={2,6,12,24}

B2的上界是24，下界是2第61頁，共76頁，2023年，2月20日，星期三2.8偏序關系[上確界]

對<A,>,BA,aA是B的一個上界。

a是B的上確界(y)(y是B的上界a

y)上確界若存在則唯一。[下確界]

對<A,>,BA,bA是B的一個下界。

b是B的下確界(x)(x是B的下界xb)下確界若存在則唯一。第62頁，共76頁，2023年，2月20日，星期三2.8偏序關系[例]{2,3,6,12,24,36}上的整除關系的Hasse圖。262436123令B1={2,3,6}B1的上界是6,12,24,36

B1的上確界是6

B1沒有下界也沒有下確界令B2={2,6,12,24}

B2的上界和上確界是24

B2的下界和下確界是2第63頁，共76頁，2023年，2月20日，星期三2.8偏序關系[鏈與反鏈]

對<A,>,BA,若B中任兩個元素之間都是可比較的，則稱B是A中的一條鏈。若B中任兩個元素之間都是不可比較的，則稱B是A中的一條反鏈。262436123[例]右邊所示Hasse圖中，

{2,6,12,24}是一條鏈{2,3}和{24,36}是反鏈注意：{2,3,24,36}并非反鏈第64頁，共76頁，2023年，2月20日，星期三2.9其他序關系(1)全序關系[全序關系]

設偏序集<A,>，若A是一條鏈，則稱“”為A上的一個全序關系，此時稱<A,>是一個全序集合。(2)偏序關系的逆關系[定義]設偏序集<A,>，定義A上的關系“”

xyx,yAyx

集合A和關系“”仍然構成一個偏序集<A,>。第65頁，共76頁，2023年，2月20日，星期三2.9其他序關系[拓撲排序]

一個偏序集可以表示一個工程中各個任務之間的依賴關系。如果一個時刻只能進行一個任務，那么整個工程的流程是一個與原偏序協(xié)調(diào)的全序。找出這個全序的過程稱為拓撲排序。[定義]設有偏序集<A,>,如果存在一個全序*使得xy蘊含x*y,則稱*是A上的一個拓撲排序。[拓撲排序算法][問題]是否每個偏序集都存在拓撲排序？第66頁，共76頁，2023年，2月20日，星期三2.9其他序關系(3)擬序關系（strictpartialorder）[擬序關系]

集合A上的關系R滿足反自反性和傳遞性時，稱為A上的一個擬序關系，用二元組<A,<>表示該結構。[定理]若R為A上的偏序關系，則R-IA為A上的擬序關系。若R為A上的擬序關系，則RIA為A上的偏序關系。第67頁，共76頁，2023年，2月20日，星期三2.9其他序關系[定理]設有擬序集<A,<>，對任何x,y,zA,①

x<y,x=y,y<x

中至多有一種情況成立(三分律)；②

xyx

則x=y，這里xy

表示x<y

或x=y。[證明]利用擬序集的反自反性和傳遞性。第68頁，共76頁，2023年，2月20日，星期三2.9其他序關系(4)詞典次序設字母表為X，“”為X上的自然次序。顯然

<X,>為全序集合。①長度為2的詞庫A=XX在A上定義全序關系S：

<x1,y1>S<x2,y2>(x1<x2)(x1=x2y1y2)

第69頁，共76頁，2023年，2月20日，星期三2.9其他序關系②長度不大于n的詞庫A=XX2…..X