离散数学3_1.

第三章二元关系关系是一个基本概念，在日常生活中我们都熟悉关系这词的含义，例如兄弟关系；上下级关系；位置关系等等。在数学上关系可表达集合中元素间的联系。而我们知道，序偶可表达两个、三个或n个客体之间的联系，因此用序偶表达关系这个概念是非常自然的。第三章——二元关系3-1关系及其表示3-2关系的性质3-3复合关系和逆关系3-4关系的闭包运算3-5集合的划分和覆盖3-6等价关系与等价类3-7相容关系3-8序关系3-1关系及其表示任一序偶的集合确定了一个二元关系R，R中任一序偶x,y可记作x,y∈R或xRy。不在R中的任一序偶x,y可记作或。Ry,xyRx例如，在实数中关系可记作={x，y|x，y是实数且xy}。定义3-1.1定义3-1.2前域：令R为二元关系，由x,y∈R的所有x组成的集合domR称为R的前域，即值域：使x,y∈R的所有y组成的集合ranR称作R的值域，即域：R的前域和值域一起称作R的域，记作FLDR，即FLDR=domR∪ranR)}Ry,x)(y(|x{domR)}Ry,x)(x(|y{ranR例题1设A={1，2，3，5}，B={1，2，4}，H={1，2，1，4，2，4，3，4}求domH，ranH，FLDH。解：domH={1，2，3}，ranH={2，4}，FLDH={1，2，3，4}定义3-1.2例题定义3-1.3令X和Y是任意两个集合，直积X×Y的子集R称作X到Y的关系。X到Y的关系R，可以由下图表示：x1x2x6x7x3x4x5y1y2y3y3y5y6domRranR例题2设X={1，2，3，4}，求X上的关系及dom，Ran。解：={2,1,3,1,4,1,3,2,4,2,4,3}dom={2，3，4}ran={1，2，3}定义3-1.3例题定义3-1.4恒等关系：设Ix是X上的二元关系且满足Ix={x，x|x∈X}，则称Ix是X上的恒等关系。例如：A={1，2，3}，则IA={1,1,2,2,3,3}。定理3-1.1若Z和S是从集合X到集合Y的两个关系，则Z，S的并、交、补、差仍是X到Y的关系。简证：因为故YXS,YXZYXSZ,YXSZYX)SYX(S~YXS~ZSZ关系的三种表示方法：一、序偶集合二、关系图:用小圆圈表示元素，带单向箭头的线条连接元素，表示序偶。如：序偶a,b可画为ab三、关系矩阵0ai,bjRmij=1ai,bjR关系的三种表示法例题设X={x1,x2,x3,x4}，Y={y1,y2,y3}，R={x1,y1,x2,y3,x2,y2,x1,y3,x3,y1,x4,y1,x4,y3},写出关系矩阵MR并画出关系图。解：101011MR=100101例题3关系图：x1x2x3x4y1y2y33-2关系的性质1.自反：设R为定义在集合X上的二元关系,如果对于每个x∈X,有xRx,则称二元关系R是自反的.R在X上自反)xRxXx)(x(例如,在实数集合中,“”是自反的,因为对于任意实数xx成立.又如平面上三角形的全等关系是自反的.定义3-2.2对称：设R为定义在集合X上的二元关系，如果对于每个x,y∈X,每当xRy，就有yRx，则称集合X上关系R是对称的。R在X上对称)yRxxRyXyXx)(y)(x(定义3-2.3传递：设R为定义在集合X上的二元关系，如果对于任意x，y，z∈X，每当xRy，yRz时就有xRz，称关系R在X上是传递的。R在X上传递xRzyRzxRyXzXyXx)(z)(y)(x(定义3-2.4反自反：设R为定义在集合X上的二元关系，如果对于每一个x∈X,都有x,x∉R,则R称作反自反的。R在X上反自反)Rx,xXx)(x(例如，数的大于关系，日常生活中的父子关系等都是反自反的。应该注意：一个不是自反的关系，不一定就是反自反的。定义3-2.5反对称：设R为定义在集合X上的二元关系，对于每一个x,y∈X,每当xRy和yRx必有x=y，则称R在X上是反对称的,即是)yxyRxxRyXyXx)(y)(x(例如实数集合中≤是反对称的,集合的关系是反对称的。3-3复合关系和逆关系二元关系是序偶为元素的集合，因此对它可以进行集合的运算，如并、交、补等而产生新的集合。对于关系还可以进行一种新的运算，那就是关系的复合。定义3-3.1设R为X到Y的关系，S为从Y到Z的关系，则R◦S称为R和S的复合关系，表示为从R和S，求R◦S称为关系的合成运算。)}Sz,yRy,xYy)(y(ZzXx|z,x{SR例如，如果R1是关系“是···的兄弟”，R2是关系“是···的父亲”，那么R◦S是关系“是···的叔伯”。令R={1,2,3,4,2,2}和S={4,2,2,5,3,1,1,3}，试求R◦S，S◦R，R◦（R◦S），R◦R，S◦S，R◦R◦R。解：R◦S={1,5,3,2,2,5}S◦R={4,2,3,2,1,4}≠R◦S(R◦S)◦R={3,2}R◦(S◦R)={3,2}S◦S={4,5,3,3,1,1}R◦R={1,2,2,2}R◦R◦R={1,2,2,2}定义3-3.1例题例题1关系复合的矩阵运算方法：设MR和MS分别是关系R和关系S的关系矩阵，则MR◦S=MR◦MS，若MR和MS的元素记为uij和vij，MR◦S的元素记为wij则wij的计算公式定义为：kjiknkijvuw1∨为逻辑加，∧为逻辑乘即按布尔矩阵乘法运算关系复合运算的性质：具有结合性：即(A◦B)◦C=A◦(B◦C)mmmRRRRRR1记Rm为：有Rs◦Rt=Rs+t定义3-3.2设R为X到Y的二元关系，如将R中每一序偶的元素顺序互换，所得到的集合称为R的逆关系。记作，即={y,x|x,y∈R}。cRcR如在集合I上，关系“”的逆关系是“”。而在集合X={1，2，3，4}到Y={a，b，c}上的关系R={1,a,2,b,3,c},其逆关系为={a,1,b,2,c,3}cR定理3-3.1设R，R1和R2都是从A到B的二元关系，则下列各式成立。a)b)c)这里d)e)(A×B）C=B×Ac2c1c21RR)RR(c2c1c21RR)RR(ccR)R(RBARc2c1c21RR)RR(证明：x，y∈（R1∩R2）Cy，x∈（R1∩R2）y，x∈R1∧y，x∈R2）x，y∈R1C∧x，y∈R2Cx，y∈R1C∩R2C定理3-3.2设T为从X到Y的关系，S为从Y到Z的关系，则有关系：cccTS)ST(定理3-3.3a)R是对称的，当且仅当b）R是反对称的，当且仅当R∩RCIxcRR证明：ccccTSx,z)Sy,zTy,xYy)(y(STz,x)ST(x,zc)Sz,yTy,xYy)(y(定理3-3.2证明yx关系的性质小结性质关系图关系矩阵充要条件自反每个顶点有自环主对角线全为1RIx反自反没有顶点有自环主对角线全为0RIx=对称两个顶点有连线一定成对出现以主对角线对称R＝RC反对称没有两个顶点存在两条线没有非0元素以主角线对称RRCIx可传递RRR