[理学]_6_23-24_关系的表示和性质_9-27.ppt

Discrete Math. , Yanxiu Sheng 第6讲 关系表示与关系性质 内容提要 关系的表示 关系矩阵, 关系图 关系的性质 自反/ 反自反 对称/ 反对称, 传递 关系表示法 关系的表示方法: 集合 关系矩阵 关系图 关系矩阵(matrix) 设A={a1,a2,…,an}, R?A×A, 则R的关系矩阵 M(R)=(rij)n×n, 其中 关系矩阵的性质 R的集合表达式与R的关系矩阵一一对应. M(R-1) = (M(R))T. (T表示矩阵转置) M(R1 ? R2) = M(R2)?M(R1). (?表示这样的矩阵“乘法”, 其中加法使用逻辑∨, 乘法使用逻辑∧. ) 例题4 例题4 设A={a,b,c}, R1={a,a,a,b,b,a,b,c}, R2={a,b,a,c,b,c}, 用M(R1), M(R2)确定M(R1-1), M(R2-2), M(R1 ? R1), M(R1 ? R2), M(R2 ? R1), 并且求出它们的集合表达式. 例题4(解) R1={a,a,a,b,b,a,b,c}, R2={a,b,a,c,b,c}, 解: ??例题4(解,续) R1={a,a,a,b,b,a,b,c}, R2={a,b,a,c,b,c}, 解(续): ??例题4(解,续) R1={a,a,a,b,b,a,b,c}, R2={a,b,a,c,b,c}, 解(续): ??例题4(解,续) R1={a,a,a,b,b,a,b,c}, R2={a,b,a,c,b,c}, 解(续): 关系图(graph) 设A={a1,a2,…,an}, R?A×A, 则A中元素以“ ? ”表示(称为顶点), R中元素以“→”表示(称为有向边); 若xiRxj, 则从顶点xi向顶点xj引有向边xi,xj, 该图称为R的关系图G(R). 例如, A={a,b,c}, R1={a,a,a,b,b,a,b,c},R2={a,b,a,c,b,c}, 则 关系图(举例) R1-1 = {a,a,a,b,b,a,c,b} R2-1 = {b,a,c,a,c,b} 关系图(举例,续) R1 ? R1 = {a,a,a,b,a,c,b,a,b,b}. R1 ? R2 = {a,a,a,c}. R2 ? R1 = {a,b,a,c,b,b,b,c}. 关系矩阵,关系图(讨论) 当A中元素标定次序后, R?A×A的关系图G(R)与R的集合表达式一一对应。 对于R?A×B, |A|=n,|B|=m, 关系矩阵M(R)是n×m阶的. 关系图G(R)中的边都从A中元素指向B中元素. 举例 例 设 A={x1, x2, x3, x4, x5}，B={y1, y2, y3}， R={ x1, y1, x1, y3, x2, y2, x2, y3, x3, y1, x4,y1, x4,y2}，写出关系矩阵MR和关系图 关系性质 自反性(reflexivity) 反自反性(irreflexivity) 对称性(symmetry) 反对称性(antisymmetry) 传递性(transitivity) 关系的性质 对于集合上的关系，可以利用关系的性质进行分类。 下面我们将介绍几种重要的性质。 在一些关系中，一个元素总是和其自身有关系。 x ≤x，x ∈R , 例如，令R为定义在人类集合上的关系, x, y∈R当且仅当x和y有相同的母亲和父亲。 所以，对每一个x来说， x R x . 自反性(reflexivity) 设R?A×A, R是自反的(reflexive),如果 ?x( x∈A → xRx ). R是非自反的? ?x( x∈A ∧ ?xRx) 定理10: R是自反的 ? IA?R ? R-1是自反的 ? M( R )主对角线上的元素全为1 ? G( R )的每个顶点处均有环. # 自反性(举例) 反自反性(irreflexivity) 设R?A×A, 说R是反自反的(irreflexive), 如果 ?x(x∈A→ ?xRx). R是非反自反的? ?x( x∈A ∧ xRx) 定理11: R是反自反的 ? IA∩R=? ? R-1是反自反的 ? M( R )主对角线上的元素全为0 ? G( R )的每个顶点处均无环. # 反自反性(举例) 自反,自反性(分类) 自反且反自反