离散数学3-6关系的性质和3-7复合关系.ppt

第三章 集合与关系第6讲 1、序偶：记作x，y 2、笛卡尔积：记作A?B 3、关系：序偶的集合；前域、值域 4、X到Y的关系，X上的关系 5、关系的表示：关系矩阵、关系图 3-6 关系的性质 一、自反性和反自反性 1、自反性：设R是集合X上的二元关系，如果对于每一个x?X，有x，x?R，则称R是自反的。 R在X上自反?(?x)(x?X?x，x?R) 2、反自反性：设R是集合X上的二元关系，如果对于每一个x?X，有x，x?R，则称R是反自反的。 R在X上反自反?(?x)(x?X?x，x?R) 例如，在实数集合中，”?”是自反的，因为对于任意实数x?x成立。 平面上三角形的全等关系是自反的。 例：X={a，b，c}， R1={a，a，b，b，c，c，a，b，c，a} R2={a，b，b，c，c，a} R3={a，a，b，c} 注意：R不是自反的，未必一定是反自反的。一个关系可能既不是自反的，也不是反自反的。 3、关系矩阵的特点 自反关系的关系矩阵的对角元素均为1，反自反关系的关系矩阵的对角元素均为0。 4、关系图的特点 自反关系的关系图，每个结点均有自回路，而反自反关系的关系图，每个结点均没有自回路。 5、结论 (两个充要条件) R是X上的二元关系，则： (1)R是自反关系的充要条件是IX?R； (2)R是反自反关系的充要条件是R?IX=?。 1、对称性：设R是集合X上的二元关系，如果对于每一个x，y?X，每当x，y?R，就有y，x?R，则称R是对称的。 R在X上对称 ?(?x)(?y)(x?X?y?X?x,y?R?y,x?R) 2、反对称性：设R是集合X上的二元关系，如果对于每一个x，y?X，每当x，y?R和y，x?R必有x=y，则称R是反对称的。 R在X上反对称? (?x)(?y)(x?X?y?X?x,y?R?y,x?R?x=y) 例如，平面上三角形的相似关系是对称的。 例： R1={1，1，2，3，3，2} R2={1，1，3，3} R3={2，2，2，3，3，2，3，1} R4={2，2，2，3，3，1} 注意：存在关系既不是对称的，也不是反对称的。也存在关系既是对称的，也是反对称的。 3、关系矩阵和关系图的特点 对称关系的关系矩阵是对称矩阵，即对所有i，j，rij＝rji；对称关系的关系图，任何两个不同的结点之间，或者有双向两条弧，或者没有弧。 反对称关系的关系矩阵，如果在非对角元上rij＝1，则在其对称位置上rji＝0，反对称关系的关系图，任何两个不同的结点之间至多有一条弧。 1、定义：设R是集合X上的二元关系，如果对于任意x，y，z?X，每当x，y?R，y，z?R时就有x，z?R，则称R是传递的。 R在X上传递 ?(?x)(?y)(?z)(x?X?y?X?z?X?x,y?R?y,z?R?x,z?R) 例： R1={x,y,z,x,z,y}是传递的， R2={x,b,c,d}也是传递的，它没有违背定义。 R3={x,b,b,x}不是传递的。 2、定理：设R、S是A上的传递关系，则R?S也是A上的传递关系。 ◆非空集合上的空关系是反自反的，对称的，反对称的和传递的，但不是自反的。 ◆空集合上的空关系则是自反的，反自反的，对称的，反对称的和传递的。 ◆非空集合上的全域关系是自反的，对称的和传递的，但不是反自反的和反对称的。 112页 例题4 设某人有三个儿子，组成集合A={T,G,H}，在A上的兄弟关系具有哪些性质。 例题5 集合I={1,2,3,4}，I上的关系 R={1,1,1,3,2,2,3,3,3,1,3,4,4,3,4,4}讨论R的性质。 3-7 复合关系和逆关系 本节讲述关系的运算。 一、复合关系 引例： （1）若设R是兄妹关系，S是母子关系，则R与S的复合T是舅甥关系。 （2）如R是父子关系，R与R复合是祖孙关系。 1、复合关系(关系的复合运算) 定义3-7.1：设X、Y、Z是三个集合，R是X到Y的关系，S是Y到Z的关系，则R?S称为R和S的复合关系，表示为 R?S={x,z?x?X?z?Z?(?y)(y?Y?x,y?R?y,z?S)} 从R和S求R?S，称为关系的合成运算。 说明：R与S能进行复合的前提是R的值域所属集 合Y与S前域所属集合Y是同一个集合。 例：X={1，2，3，4，5}，Y={3，4，5}，Z={1，2，3}， R是X到Y的关系，S是Y到Z的关系： R={x，y|x+y=6}={1，5，2，4，3，3}， S={y，z?y-z=2}={3，1，4，2，5，3}， 则R?S={1，3，2，2，3，1} 另可以用推导：∵x+y=6，y-z=2，消去y得x+z=4 例：集合X={x