南京大学：《计算机问题求解》课程教学资源（课件讲稿）关系及其基本性质

问题求解论题1-9 关系 陶先平 2015年11月19日

问题求解论题1-9 关系 陶先平 2015年11月19日

有序偶的集合表示形式 问题1：“有序”的有序偶表达需求该如何用“无 序”的集合这样的数学模型来建模？ 的集合表现形式是{a,{a,b}

有序偶的集合表示形式 问题1: “有序”的有序偶表达需求该如何用“无 序”的集合这样的数学模型来建模？ 的集合表现形式是{a,{a,b}}

二元关系的论域 问题2：就二元关系RCAxB而言，其论域是什么？ 通常情况下，我们讨论A=B的一类特殊关系较多

二元关系的论域 问题2：就二元关系 而言，其论域是什么？ 通常情况下，我们讨论A=B的一类特殊关系较多

就A上的关系R而言： ·关系R可以采用集合、有向图和关系矩阵的多种表现形式 问题3： 在关系的计算机实现中，你会采用哪种形式去表达一个关系？

就A上的关系R而言： • 关系R可以采用集合、有向图和关系矩阵的多种表现形式 问题3： 在关系的计算机实现中，你会采用哪种形式去表达一个关系？

问题4： 你觉得下面的表示“奇怪”吗？ 口自然数集合上：“”=中 问题5：你如何理解、区分上述式子中的“=”和=？

问题4： 问题5：你如何理解、区分上述式子中的“=”和=？

关系的“复合”运算 ·关系的复合运算 口运算法则： 如果R1∈A×B,R2∈B×C, 则：R1与R2的复合关系R1°R2三AxC 且：R1°R2={KX,z>X∈A,Z∈C,且存在 y∈B,使得∈R1,∈R2)

关系的复合运算：例子 ■设A={a,b,c,d},R,R,为A上的关系，其中： R,={,,,,} 很容易证明：关系的复合 运算满足结合律。 ·则： “乘幂”的定义： R,°R2={,} R1=R,R=Rn1。R R,°R,={,,,,,}

问题6： 关系可以用矩阵和图来表示，关系的复合 运算在这两种表现形式下，如何解读？

问题6： 关系可以用矩阵和图来表示，关系的复合 运算在这两种表现形式下，如何解读？

自反性 ■集合A上的关系R: 口自反：定义为：对所有的a∈A,(a,a)∈R 口反自反：定义为：对所有的a∈A,(a,a)R 注意区分非”与”反” ■设A={1,2,3},RcA×A ▣{(1,1)，(1,3)，(2,2)，(2,1)，(3,3)}是自反的 ▣{(1,2)，(2,3)，(3,1)}是反自反的 ▣{(1,2)，(2,2)，(2,3)，(3,1)}既不是自反的，也不 是反自反的

对称性 ■集合A上的关系R: 口对称的：定义为：若(a,b)eR,则(b,a)eR 口反对称的：定义为：若(a,b)eR且(b,a)eR,则a=b 0 强反对称的：定义为：若(a,b)eR则(b,a)R ■设A={1,2,3},RCA×A ▣{(1,1)，(1,2)，(1,3)，(2,1)，(3,1)，(3,3)}是对称的 口(1,2)，(2,3)，(2,2)，(3,1)}是反对称的 ▣{(1,2)，(2,3)，(3,1)}既是反对称的，也是强反对称的