集合非空，且它的元素都是有序?qū)Γㄒ?-3-4；如果x,yRxRy。定義 A到B的二元關(guān) 設(shè)A,B為集合，AB的任一子集所定義的二元關(guān)系A(chǔ)BABAAA上的一個(gè)二定義 n元關(guān)系（n元組的集合）若nN且n1,A1,A2,,An是n個(gè)集合A1A2AnA1An上的一個(gè)n 設(shè)是集合族，上的包含關(guān)系可定義為Rx,

x,yxyRx,

x,yxyAAPARx,

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

xAA上的全域關(guān)系（全關(guān)系）EAAEx,A

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

dom(R)

(y)(x,yRRRran(R)

ran(R)

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

Yy1,y2,ynR到Y(jié)R的關(guān)系矩陣是mn矩陣，矩陣元素是rijM(R)[rijrij

當(dāng)xi,yj當(dāng)xi,yj

(1im,1

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

SR的關(guān)系矩 設(shè)A是有限集合，S

nRSAM(R)[rij M(S)[sij都是nnRS的合成SRM(SR)[wijM(SR)M(R)M(Sn其 wij(rikskjk定理 關(guān)系R的逆關(guān)系的性 對(duì)X到Y(jié)的關(guān)系R和Y到Z的關(guān)系Sdom(R1)ran(R1)(R1)1(SR)1R1S定理10.3.2 對(duì)X到Y(jié)的關(guān)系Q，Y到Z的關(guān)系S，Z到W的關(guān)系R，(RS)QR(S定理 對(duì)X到Y(jié)的關(guān)系R2，R3，Y到Z的關(guān)系R1（1）R1(R2R3)R1R2R1（2）R1(R2R3)R1R2R1X到Y(jié)R3，YZR1（3）(R1R2)R3R1R3R2（4）(R1R2)R3R1R3R2定理 對(duì)X到Y(jié)的關(guān)系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定義 設(shè)R為集合A上的關(guān)系RA上是自反的(x)(xAx,xRA上是非自反的(x)(xAx,x定義 設(shè)R為集合A上的關(guān)系RA上是對(duì)稱的x)(yxAyAx,yRy,xR在A上是稱的(x)(y)((xAyAx,yRy,xR)xR在A上是稱的

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

R0x,

Rn1Rn

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

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

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

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

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

[x]R

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

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