集合非空，且它的元素都是有序對（見9-3-4；如果x,yRxRy。定義 A到B的二元關 設A,B為集合，AB的任一子集所定義的二元關系ABABAAA上的一個二定義 n元關系（n元組的集合）若nN且n1,A1,A2,,An是n個集合A1A2AnA1An上的一個n 設是集合族，上的包含關系可定義為Rx,

x,yxyRx,

x,yxyAAPARx,

xP(A)yP(A)xy定義 A A

xAA上的全域關系（全關系）EAAEx,A

xAyA空集是AA的子集，定義為A上的空關系。定義10.1.4 設R是A到B的二元關系RR的定義域，記作dom(R

dom(R)

(y)(x,yRRRran(R)

ran(R)

(x)(x,yRRRfld(R)fld(R)dom(R)定義 關系矩陣設集合Xx1,x2,,xm

Yy1,y2,ynR到YR的關系矩陣是mn矩陣，矩陣元素是rijM(R)[rijrij

當xi,yj當xi,yj

(1im,1

jRXR的關系矩陣是mm定義 關系 設集合Xx1,x2,,xm，Yy1,y2,,yn。若R是到YR的關系圖是一個有向圖G(R)V,EVXYExiyj的有向邊eijE，當且僅當xi,yjR。RXR的關系圖是上述情形的特例。定義 關系的逆、合成、限制和象對X到Y的關系R，Y到Z的關系S，定RR1為YXR1x,yy,xRS的合成SR（有些書中稱之為關系的左復合）XZSRx,y(z)(x,zRz,yARARAA到YRAx,yx,yRxARRAR[A]y(x)(xAx,y10-3-

SR的關系矩 設A是有限集合，S

nRSAM(R)[rij M(S)[sij都是nnRS的合成SRM(SR)[wijM(SR)M(R)M(Sn其 wij(rikskjk定理 關系R的逆關系的性 對X到Y的關系R和Y到Z的關系Sdom(R1)ran(R1)(R1)1(SR)1R1S定理10.3.2 對X到Y的關系Q，Y到Z的關系S，Z到W的關系R，(RS)QR(S定理 對X到Y的關系R2，R3，Y到Z的關系R1（1）R1(R2R3)R1R2R1（2）R1(R2R3)R1R2R1X到YR3，YZR1（3）(R1R2)R3R1R3R2（4）(R1R2)R3R1R3R2定理 對X到Y的關系R和集合A、B（1）R[AB]R[A]

R[A]

B（3）R[AB]R[A]

R[A]

B

A（5）R[A]R[B]R[A定義 設R為集合A上的關系RA上是自反的(x)(xAx,xRA上是非自反的(x)(xAx,x定義 設R為集合A上的關系RA上是對稱的x)(yxAyAx,yRy,xR在A上是稱的(x)(y)((xAyAx,yRy,xR)xR在A上是稱的

定義 傳遞 設R為集合A上的關系RA上是傳遞的((xAyAzAx,yRy,zR)x,z定理 設R、R是A上的自反關系則R1、RR R1R2A定理 設R、R是A上的對稱關系則R1、RR R1R2A定理 設R、R是A上的傳遞關系，則R1、R AR1R2定理 設RR是A上的傳遞關系則R1R 是A上的 稱關系。但R1R2不一定是 定理10.4.5 設R是A上的關系，R是對稱的RRAR是稱的RR1AA定義 設R為A上的關系，nN，關系R的n次冪定義為A

R0x,

Rn1Rn

(n定理 設A是有限集合，

nRAs和t,stRsRt定理10.5.2 設A是有限集合，R是A上的關系，m和n是非

RmRn(Rm)nRmn定理10.5.3 設A是有限集合，R是A上的關系，若存在自然數s和t，使得RsRt，則

Rtk，其中kNRskpiRsi，其中kiNptsBR0R1,Rt1RB的元素，即對任意qNRqB。定義 閉包的定義設R是非空集合A上的關系，如果A上有另一個關系R'滿足RR'A上任何自反的（對稱的或傳遞的）RR'R。R'R的自反（對稱或傳遞）閉包。R的自反閉包記作r(R，對稱閉包記作s(R，傳遞閉包記作t(R。它們分別是具有自反性（對稱性或傳遞性）R的“最小”超集合。定理 閉包的性質 對非空集合A上的關系RR是自反的r(R)RR是對稱的s(R)RR是傳遞的t(R)R定理 閉包的性質 對非空集合A上的關系R1,R2，若R1R2，（1）r(R1)r(R2（2）s(R1)s(R2（3）t(R1)t(R2定理 閉包的性質 對非空集合A上的關系R1,R2（1）r(R1)r(R2)r(R1R2（2）s(R1)s(R2)s(R1R2（3）t(R1)t(R2)t(R1R2定理 對非空集合A上的關系Rr(R)R定理 對非空集合A上的關系Rs(R)R定理 對非空集合A上的關系Rt(R)RR2R3定理 傳遞閉包的有限構造方法A為非空有限集合，則存在正整數kn

RAt(R)RRR2定理 對非空集合A上的關系RR是自反的，則s(R和t(R)R是對稱的，則r(R)和t(RR是傳遞的，則r(R定理 對非空集合A上的關系Rrs(R)rt(R)st(R)其中rs(R)r(s(R定義10.6.1 設R為非空集合A上的關系，如果R是自反的、對稱的和傳遞的，則稱R為A上的等價關系。定義 等價 設R為非空集合A上的等價關系，對任意的xA，R[x]yyAxRyR稱集合[x]R為x關于R的等價類，簡稱x的等價類，也可簡記作[x]或x。定理10.6.1 R是非空集合A上的等價關系，對任意的x,yA，

[x]R

且[x]RA，即，[x]RAxRy，則[x]R若x,yR，則[x]Ry]R

xA定義 商 設R為非空集合A上的關系，以R的所有等價類為元素的集合稱AARRAR xAR定義 劃 設A為非空集合，若存在A的非空子集構成的集合滿足下列條件（1）(x)(xx（2）（3）（4）(x)(y)((xyxy)xy則稱A的一個劃分，稱A定理 等價關系R誘導出的A的劃 對非空集合A上的等價關系R，A的商ARARA的劃分，記作R定理10.6.3 劃分誘導出的A上的等價關系 對非空集合A上的一個劃分，令A上的關系R為Rx,y(z)(zxzyRA上的等價關系，它稱為劃分A定理10.6.4 劃分和A上的等價關系R 對非空集合A上的一個劃分，和A上的等價關系R，誘導R當且僅當R誘導。10.7.1（相容關系）ARR10.7.2（相容類）AR，若CA，且CxyxRy，則稱CR產生的相容類，簡稱相容類。定義10.7.3 （最大相容類）對非空集合A上的相容關系R，一個相容類若不是任何相容類的真子集，就稱為最大相容類，記作CR。對最大相容類CR(x)(y)((xCRyCR) 10.7.1（最大相容類的存在性）AR，若C是一個相容類，則存在一個最大相容類CR，使CCR。定義 （覆蓋）對非空集合A，若存在集合滿足下列條件(x)(xxA)A則稱A的一個覆蓋，稱中的元素為定理10.7.2（完）對非空集合A上的相容關系R，最大相容類的集合是A的一個覆蓋，稱為A的完，記作CR(A)。而且CR(A)是唯一的。10.7.3（覆蓋與相容關系）A的一個覆蓋A1A2An確RA1A1A2A2AnAnA定義10.8.1 （偏序關系半序關系）對非空集合A上的關系R，如果R是自反的、稱的和傳遞的，則稱R為A上的偏序關系。R通常記作xRyxy10.8.2（）ARR是非自反的和R為A上的擬序關系。R通常記作xRyxy讀作x“小于”y。擬序關系又稱強偏序關系。定理10.8.1 R為A上的擬序關系，則R是稱的。定理10.8.2 對A上的擬序關系R，RR0是A上的偏序關系。定理 對A上的偏序關系R，RR0是A上的擬序關系10.8.3（偏序集）AARAAR一起稱為一個偏序結構，或稱偏序集，并記作AR10.8.4（蓋住關系）對偏序集A,xyAxyxy，且不存在元zAxzzyyxA上的蓋住關系covA定義為covAxy|xAyAy蓋住x10.8.5（）對偏序集A,BA，若(yyBx)(xByxyB若(yyBx)(xBxyyB若(yyBxxBxyxyyB若(yyBxxByx)xy))yB的極大元。10.8.6（上界下界上確界下確界）對偏序集A,BA，若(yyAx)(xBxyyB若(yyBx)(xByxyB若集合Cy|y是B的上界，則CB若集合Cy|y是B的下界，則CB的下確界或最大下界。10.8.7（可比）對偏序集A,xyAxyyxxy10.8.8（全序關系與全序集）對偏序集A,xyA，xy都可比，則稱A上的全序關系，或稱線序關系。并稱A,為全序集。10.8.9（鏈反鏈）對偏序集A,BxyBxyBAB中元10.8.4（偏序集的分解定理）對偏序集A,A中最長鏈的長度是nA元素分成不相交的反鏈，反鏈個數至少是n定理10.8.5 對偏序集A,，若A中元素為mn1，則A中或者存在一條長度為m1的反鏈，或者存在一條長度為n1的鏈。10.8.10（良序關系與良序集）對偏序集A,A的任何非空子集都有最小元則稱為良序關系,稱A,為良序集。定理10.8.6 定理 10.8