教程离散数学jingyao101 1二元关系有序对集合如果一个满足以下条件之一

集合非空，且它的元素都是有序对（见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