南京大学：《离散数学》课程教学资源（PPT课件讲稿）Lecture 11 关系的性质

1 关系的性质

关系的性质 1

回顾 口内容1：概率论 口概率函数、条件概率、独立性 口内容2：贝叶斯定理 a Pr[FIE]=P [EIF]Pr[F] Pr[E] 口内容3：随机变量及其期望与方差 口期望、条件期望、全期望公式（全概率公式）、期望的 线性性质、方差、概率化方法

 内容1：概率论  概率函数、条件概率、独立性  内容2：贝叶斯定理  Pr 𝐹 𝐸 = Pr[𝐸∣𝐹] Pr 𝐹 Pr 𝐸  内容3：随机变量及其期望与方差  期望、条件期望、全期望公式(全概率公式)、期望的 线性性质、方差、概率化方法 回顾

本节提要 口问题1：关系具有哪些重要性质？ 口问题2：如果计算关系的闭包？

 问题1：关系具有哪些重要性质？  问题2：如果计算关系的闭包？ 本节提要

关系的定义（回顾） 4 若A,B是集合，从A到B的一个关系是AxB的一个 子集。 口集合，可以是空集 口集合的元素是有序对 若A=B:称为“集合A上的（二元）关系

关系的定义（回顾）  若A, B是集合, 从A到B的一个关系是AB的一个 子集.  集合, 可以是空集  集合的元素是有序对  若A=B： 称为“集合A上的（二元）关系” 4

关系的表示（回顾） 5 假设A={a,b,c,d欧，B={%A,乃/1假设为有限集合 口集合表示：R1={(a月，(b,,(C,,(G)} 0-1矩阵 有向图 a B a 0 1 b 1 0 0 10 1 d 00 0 d A B

关系的表示（回顾）  假设A={a,b,c,d}, B={α,β,γ} // 假设为有限集合  集合表示: R1={(a, β), (b, α), (c, α),(c, γ)} 0-1矩阵 有向图 5             0 0 0 1 0 1 1 0 0 a 0 1 0 b c d    a d c b    A B

关系的性质：自反性 6 口集合A上的关系R是： 口自反的reflexive:定义为：对所有的a∈A,(a,a∈R 口反自反的irreflexive:定义为：对所有的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 是:  自反的 reflexive：定义为：对所有的aA, (a,a)R  反自反的irreflexive：定义为：对所有的aA, (a,a)R 注意区分”非”与”反”  设 A={1,2,3}, RA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)} 既不是自反的，也不是反自反的 6

关系的性质：自反性 7 A=a,b,c a I MR= 0 b c)

关系的性质：自反性 7

关系的性质：自反性 口R是A上的自反关系台I4二R 这里I4是集合A上的恒等关系，即：I4={(a,|a∈A} 直接根据定义证明： 口→只需证明：对任意(a,b),若(a,∈IA,则(a,b)∈R 口←只需证明：对任意的a,若a∈A,则(a,a)∈R

 R 是 A 上的自反关系  IAR, 这里IA是集合A上的恒等关系,即: IA={(a,a)| aA} 直接根据定义证明：   只需证明：对任意(a,b) ，若(a,b)IA, 则(a,b)R   只需证明：对任意的a, 若aA, 则(a,a)R 关系的性质：自反性

关系的性质：对称性 9 口集合A上的关系R是： 口对称的symmetric:定义为：若(a,b)∈R则(b,)∈R 口反对称的ani-~:定义为：若(a,b)∈R且(b,)∈R,则a=b 口设A={1,2,3},RcA×A ▣{(1,1)，(12)，(1,3)，(2,1)，(3,1)，(3,3)}是对称的 ▣{(1,2)，(2,3)，(2,2)，(3,1)}是反对称的

关系的性质：对称性  集合A上的关系R是:  对称的 symmetric：定义为：若(a,b)R, 则 (b,a)R  反对称的anti-~：定义为：若(a,b)R且(b,a)R ，则a=b  设 A={1,2,3}, RAA  {(1,1),(1,2),(1,3),(2,1),(3,1),(3,3)} 是对称的  {(1,2),(2,3),(2,2),(3,1)} 是反对称的 9

关系的性质：对称性 10 ● 关系R满足对称性：对任意(a,b),若(a,b)eR,则(b,a)eR 关系R是对称的台廿(∈R→∈R) 。注意：⑦是对称关系。 ·反对称并不是对称的否定： (令：A={1,2,3},RCAxA) {(1,1),(2,2)}既是对称的，也是反对称的 ⑦是对称关系，也是反对称关系

关系的性质：对称性 10