關(guān)系與序關(guān)系

關(guān)系與序關(guān)系第1頁，共76頁，2023年，2月20日，星期三2.1關(guān)系的概念[例]設(shè)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,表示了學(xué)生集合A與課程集合B之間的選修關(guān)系。第2頁，共76頁，2023年，2月20日，星期三2.1關(guān)系的概念[二元關(guān)系的一般性描述]

一對對象之間的關(guān)系稱為二元關(guān)系。[例]

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

建立教學(xué)關(guān)系T:aTxiffaTEACHINGx用序偶集合表示為：

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

Subroutines={a,b,c,d,e}子程序間調(diào)用關(guān)系圖示為：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關(guān)系的概念[二元關(guān)系的集合定義]

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

R都確定了一種二元關(guān)系，稱為從X到Y(jié)的二元關(guān)系。

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

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

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

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

<x,y>R，二者必居其一。第6頁，共76頁，2023年，2月20日，星期三2.1關(guān)系的概念[定義域]設(shè)二元關(guān)系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關(guān)系的概念若干特殊關(guān)系：①

X到Y(jié)的全域關(guān)系：Ex,y=XY

特別地：

Ex,x=XX②空關(guān)系：

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

=<xi,yj>R0其它第9頁，共76頁，2023年，2月20日，星期三2.2關(guān)系的表示方法[例]非0行對應(yīng)元素構(gòu)成D(S)非0列對應(yīng)元素構(gòu)成R(S)第10頁，共76頁，2023年，2月20日，星期三2.2關(guān)系的表示方法(3)關(guān)系圖表示法用結(jié)點(diǎn)表示X、Y上的元素；若<x,y>R則從結(jié)點(diǎn)x到結(jié)點(diǎn)y畫一條弧。[例]上述Teaching關(guān)系的關(guān)系圖：第11頁，共76頁，2023年，2月20日，星期三2.2關(guān)系的表示方法[例]設(shè)X={1,2,3,4}，X上的關(guān)系“>”：第12頁，共76頁，2023年，2月20日，星期三2.3關(guān)系的性質(zhì)[定義]設(shè)R是X上的二元關(guān)系，則：①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關(guān)系的性質(zhì)[習(xí)題]

設(shè)X={1,2,3,4}，畫出X上的關(guān)系“>”，“”和整除“|”的關(guān)系圖和關(guān)系矩陣，并判斷其性質(zhì)。[習(xí)題]集合上的”isanelement”以及”isasubset”具有什么性質(zhì)？第14頁，共76頁，2023年，2月20日，星期三2.3關(guān)系的性質(zhì)[例]正整數(shù)集合上的若干關(guān)系及其性質(zhì)整除=≤＜自反性對稱性傳遞性反自反性反對稱性判定關(guān)系“＜”的反對稱性的前提條件總為F,反對稱性成立。第15頁，共76頁，2023年，2月20日，星期三2.3關(guān)系的性質(zhì)從關(guān)系矩陣和關(guān)系圖看關(guān)系的性質(zhì)：R是自反的：MR的對角元均為1；關(guān)系圖為自環(huán)圖。R是對稱的：MR為對稱矩陣；關(guān)系圖中弧成對出現(xiàn)。R是反自反的：MR的對角元均為0；關(guān)系圖為無自環(huán)圖。R是反對稱的：MR為反對稱矩陣；關(guān)系圖中只出現(xiàn)單向弧。第16頁，共76頁，2023年，2月20日，星期三2.3關(guān)系的性質(zhì)存在著既非自反也非反自反的關(guān)系，如：存在著既對稱又反對稱的關(guān)系，如：第17頁，共76頁，2023年，2月20日，星期三2.3關(guān)系的性質(zhì)存在著既非對稱又非反對稱的關(guān)系，如：第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}}均構(gòu)成對S的劃分。顯然有|A|>|B|>|C|

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

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

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

N上的模6同余關(guān)系

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

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

且yRz，即

xy=mL1，yz=mL2

，L1、L2

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

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

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

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

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

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

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

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

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

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

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

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不是等價關(guān)系，R是一個相容關(guān)系。第31頁，共76頁，2023年，2月20日，星期三2.6相容關(guān)系[相容類]

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

x

y)。[最大相容類]

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

設(shè)R、S是X到Y(jié)的二元關(guān)系，定義運(yùn)算如下：

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

關(guān)系的復(fù)合運(yùn)算[復(fù)合關(guān)系]

設(shè)二元關(guān)系R:XY，S:YZ，則稱

S

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

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

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關(guān)系的運(yùn)算關(guān)系的復(fù)合運(yùn)算沒有交換律。[定理]

關(guān)系復(fù)合運(yùn)算的結(jié)合律：設(shè)二元關(guān)系

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

關(guān)系復(fù)合運(yùn)算與一般運(yùn)算的結(jié)合律：設(shè)二元關(guān)系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關(guān)系的運(yùn)算[關(guān)系的冪運(yùn)算]設(shè)R為X上的二元關(guān)系，RR…R記為Rn，規(guī)定Rn=Rn1R，R0=IX第39頁，共76頁，2023年，2月20日，星期三2.7關(guān)系的運(yùn)算(3)關(guān)系的逆運(yùn)算[逆關(guān)系]

設(shè)二元關(guān)系R：XY，定義

R-1={<y,x>|xXyY<x,y>R}為R的逆關(guān)系。[性質(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關(guān)系的運(yùn)算[問題]設(shè)Ａ上關(guān)系R，S的關(guān)系矩陣分別為ＭR,MS,試求SR的關(guān)系矩陣。第41頁，共76頁，2023年，2月20日，星期三2.7關(guān)系的運(yùn)算(4)關(guān)系的閉包運(yùn)算[閉包]

設(shè)R為X上的二元關(guān)系，若另有一關(guān)系R，滿足：①

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

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

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

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

1)Rt(R)

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

2)

t(R)是傳遞的；

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

t(R)=RR1…Rn這是因?yàn)槿绻麖膞到y(tǒng)有道路相連，則存在長度不超過n的道路。求傳遞閉包的Washall算法。參閱課本。第46頁，共76頁，2023年，2月20日，星期三2.7關(guān)系的運(yùn)算容易證明：R是自反的當(dāng)且僅當(dāng)r(R)=R；R是對稱的當(dāng)且僅當(dāng)s(R)=R;R是傳遞的當(dāng)且僅當(dāng)t(R)=R.問題：設(shè)R是A上的關(guān)系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偏序關(guān)系[偏序關(guān)系(partialorder)]

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

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

“”={……..}

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

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

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

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

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

ac,cb③

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

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

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

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

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

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

對偏序集<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偏序關(guān)系[例]{2,3,6,12,24,36}上的整除關(guān)系的Hasse圖。2624361232,3為極小元24,36為極大元沒有最小元和最大元第58頁，共76頁，2023年，2月20日，星期三2.8偏序關(guān)系[例]

A的冪集上的關(guān)系的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偏序關(guān)系[上下界]

對<

A,>,BA,aA

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

a)

a是B的一個下界(x)(xBax)說明：a不一定是B的元素，即可能aA-BB的上(下)界不一定存在，存在也不一定唯一。第60頁，共76頁，2023年，2月20日，星期三2.8偏序關(guān)系[例]{2,3,6,12,24,36}上的整除關(guān)系的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偏序關(guān)系[上確界]

對<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偏序關(guān)系[例]{2,3,6,12,24,36}上的整除關(guān)系的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偏序關(guān)系[鏈與反鏈]

對<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其他序關(guān)系(1)全序關(guān)系[全序關(guān)系]

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

xyx,yAyx

集合A和關(guān)系“”仍然構(gòu)成一個偏序集<A,>。第65頁，共76頁，2023年，2月20日，星期三2.9其他序關(guān)系[拓?fù)渑判騗

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

集合A上的關(guān)系R滿足反自反性和傳遞性時，稱為A上的一個擬序關(guān)系，用二元組<A,<>表示該結(jié)構(gòu)。[定理]若R為A上的偏序關(guān)系，則R-IA為A上的擬序關(guān)系。若R為A上的擬序關(guān)系，則RIA為A上的偏序關(guān)系。第67頁，共76頁，2023年，2月20日，星期三2.9其他序關(guān)系[定理]設(shè)有擬序集<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其他序關(guān)系(4)詞典次序設(shè)字母表為X，“”為X上的自然次序。顯然

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

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

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