(第10讲)二元关系

CS|SWUSTXDC14.1.4关系的性质一、自反性和反自反性定义设A是一个集合，R是A上的二元关系，（1）若a∈A，都有a,a∈R，则称R是自反的，或称R具有自反性。（2）若a∈A，都有a,aR，则称R是反自反的，或称R具有反自反性。CS|SWUSTXDC2设A={a,b,c,d}，例1)R={a,a,a,d,b,b,b,d,c,c,d,d}。因为A中每个元素x，都有x,x∈R，所以R是自反的。R的关系图1001010100100001RMR的关系矩阵CS|SWUSTXDC32)S={a,b,a,d,b,c,b,d,c,a,d,c}。例(续1)S的关系图0101001110000010SMS的关系矩阵因为A中每个元素x，都有x,xS，所以S是反自反的。CS|SWUSTXDC43)T={a,a,a,b,a,c,b,d,c,a,c,c,d,c}。例(续2)因为A中有元素b，使b,bT，所以T不是自反的；因为A中有元素a，使a,a∈T，所以T不是反自反的。T的关系图1110000110100010TMT的关系矩阵CS|SWUSTXDC5有关说明：（1）注意定义中“任意”，“都”这两个词。（2）如果R不是自反的，则R未必一定是反自反的。一个关系可能既不是自反的，也不是反自反的。（3）表现在关系图上：关系R是自反的，当且仅当其关系图中每个结点都有环；关系R是反自反的，当且仅当其关系图中每个结点都无环。（4）表现在关系矩阵上：关系R是自反的，当且仅当其关系矩阵的主对角线上全为1；关系R是反自反的当且仅当其关系矩阵的主对角线上全为0。CS|SWUSTXDC6例1R是Z上的整除关系，则R具有自反性。证明：x∈N，x能整除x，∴x,x∈R，∴R具有自反性。例2R是Z上的同余关系，则R具有自反性。证明：x∈Z，(x-x)/k=0∈Z,∴x与x同余，∴x,x∈R，∴R具有自反性。其它≤，≥关系，倍数关系，人与人的同名关系、集合的关系，均是自反的。CS|SWUSTXDC7例3Z上的大于关系是反自反关系。证明：x∈Z，x不大于x，∴x,xR，∴N上的大于关系是反自反的。其他的如实数上的＜，＞关系,人与人的父子关系,均是反自反关系。CS|SWUSTXDC8二、对称性定义设R是A上的关系，a,b∈A，如果a,b∈R，则必有b,a∈R，则称R是对称的，或称R具有对称性。例如，A={1，2，3，4}R1＝{1,1，2,3，3,2}，则R1是对称的；R2＝{1,1，3,3}，则R2也是对称的；R3＝{2,2，2,3，3,2，3,1}，则R3不是对称的，因3,1∈R，而1,3R。CS|SWUSTXDC9有关说明:1由对称性的定义可知，如果R是对称的，则当a,bR时，必有b,aR。2对于像a,a，b,b这种序偶是否属于R对R的对称性没有影响。R1的关系图1101000100RMR1的关系矩阵是对称的例设A={a,b,c}，1)R1={a,a,a,c,c,a}CS|SWUSTXDC例R是Z上的模5同余关系,则R是对称关系；证明：R＝{x,y|x,y∈Z，(x-y)/5∈Z}x,y∈Z，如果x,y∈R，则(x-y)/5∈Z所以，(y-x)/5＝-(x-y)/5∈Z∴y,x∈R，故R具有对称性。10CS|SWUSTXDC113)R3={a,a,a,b,a,c,c,a}例(续1)4)R4={a,a,c,c}既不是对称的，也不是反对称的R3的关系图3111000100RMR3的关系矩阵既是对称的，也是反对称的R3的关系图4100000001RMR3的关系矩阵CS|SWUSTXDC12对称关系的关系矩阵和关系图的特点1.对称关系的关系矩阵是对称矩阵，即rij＝rji；因为rij＝1ai,aj∈Raj,ai∈Rrji＝1∴一切i,j，rij＝rji=12.对称关系的关系图的特点是任何两个不同的结点之间，或者是一来一回两条边（弧），或者是没有边（弧）。而是否有自回路，对对称性没有影响。显然,全域关系UA，空关系，恒等关系A，都是对称的。CS|SWUSTXDC13三、反对称性定义如果R是A上的关系，a,b∈R如果a,b∈R且b,a∈R，则必有a＝b，称R是反对称的。有关说明:1该定义的等价说法是：a,b∈A，如a≠b，a,b∈R，则必有b,aR。即两个不同点结点间不允许有两条边（弧）。2该定义的否命题说法并不成立。即“a≠b，a,bR，则b,a∈R”并不成立，即反对称关系的关系图允许两个不同点间没有弧。CS|SWUSTXDC14例2R是N上的整除关系,即R＝{x,y|x,y∈N,y/x∈N},显然，如果x能整除y，且x≠y，则y不能整除x。所以R是反对称的。例1设A={a,b,c}，R2={a,a,a,c}R2的关系图2101000000RMR2的关系矩阵是反对称的CS|SWUSTXDC15例3A是某集合，R是ρ(A)上的包含关系。因u、v∈ρ(A)，如u≠v，且uv，则必有vu,所以，包含关系R是反对称的。换一种理解，如果u,v∈ρ(A)，有uv，vu，则必有u＝v。∴集合A上的包含关系R是反对称的。其它例如≥、、关系，人与人的父子关系，领导与被领导关系均是反对称的。CS|SWUSTXDC16反对称关系的关系矩阵和关系图特点关系矩阵：R是反对称的，则其关系矩阵如果在非对角元上rij＝1，则在其对称位置上rji＝0，即rij和rji(i≠j)这两个数至多一个是1，但允许两个均为0。关系图：任何两个不同的结点之间，至多有一条边（弧），或者没有边（弧）。CS|SWUSTXDC17四、传递性定义设R是A上的关系，a,b,c∈A，如果a,b∈R，b,c∈R，则必有a,c∈R。则称R是传递的，或称R具有传递性。设A={a,b,c,d}，1)R1={a,a,a,b,b,c,a,c}是传递的R1的关系图11110001000000000RMR1的关系矩阵CS|SWUSTXDC18设A={a,b,c,d}，例（续）2)R2={a,b}是传递的R2的关系图20100000000000000RMR2的关系矩阵CS|SWUSTXDC193)R3={a,a,a,b,b,c}例(续)4)R4={a,b,b,c,a,c,c,d}不是传递的R3的关系图31100001000000000RMR3的关系矩阵不是传递的R3的关系图40110001000010000RMR3的关系矩阵CS|SWUSTXDC201)表现在关系图上：关系R是传递的当且仅当其关系图中，任何三个结点x,y,z（可以相同）之间，若从x到y有一条边存在，从y到z有一条边存在，则从x到z一定有一条边存在。2)表现在关系矩阵上：关系R是传递的当且仅当其关系矩阵中，对任意i,j,k{1,2,3,…,n}，若rij=1且rjk=1，必有rik=1。结论CS|SWUSTXDC21例整除关系DN是N上的传递关系。证明：x,y,z∈N，如x,y∈DN，y,z∈DN，即x能整除y，且y能整除z，则必有x能整除z，即x,z∈DN，所以整除关系具有传递性。例ρ(A)上的包含关系，具有传递性。因为若uv，vw，则必有uw。例实数集上的≤关系也具有传递性。因为若x≤y，y≤z，必有x≤z。其它如全域关系UA，空关系，恒关系A均是传递的。CS|SWUSTXDC关系性质的逻辑表示设R是集合A上的二元关系，1)R是自反的))Rx,x()Ax)((x(是永真的2)R不是自反的))Rx,x()Ax)((x(是永真的3)R是反自反的))Rx,x()Ax)((x(是永真的4)R不是反自反的))Rx,x()Ax)((x(是永真的5)R是对称的))Rx,y()Ry,x)((y)(x(是永真的6)R不是对称的))Rx,y()Ry,x)((y)(x(是永真的CS|SWUSTXDC23关系性质的逻辑表示(续)7)R是反对称的9)R是传递的))Rz,x())Rz,y()Ry,x)(((z)(y)(x(是永真的10)R不是传递的))Rz,x()Rz,y()Ry,x)((z)(y)(x(是永真的))Rx,y())Ry,x()yx)(((y)(x())yx())Rx,y()Ry,x)(((y)(x(是永真的8)R不是反对称的))Rx,y()Ry,x()yx)((y)(x(是永真的CS|SWUSTXDC24设A＝{1,2,3},试判断如下图所示A上关系的性质：1)图a)的关系是自反的、对称的、反对称的、传递的关系；2)图b)的关系是具备反自反的、对称的、反对称的、传递的关系；图c)的关系是具备对称的、反对称的、传递的关系；图d)的关系是不具备任何的性质关系；CS|SWUSTXDC251)图e)的关系是具备自反的、对称的、传递的关系；2)图f)的关系是具备反自反的、反对称的、传递的关系；3)图g)的关系是具备反自反的、反对称的关系；4)图h)的关系是具备反自反的、反对称的、传递的关系。例CS|SWUSTXDC26设A是任意的集合，1)A上的全关系A×A是自反的、对称的、传递的关系；2)A上的空关系Φ是反自反的、反对称的、对称的、传递的关系；3)A上的恒等关系IA是自反的、对称的、反对称的、传递的关系。例例1)朋友关系是自反的、对称的、而非传递的关系；2)父子关系是反自反的、反对称的、而非传递的关系.