《离散数学》课程教学资源（PPT课件讲稿）关系的性质、闭包和等价

关系的性质、闭包和 等价

关系的性质、闭包和 等价 1

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

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

本节提要 口问题1:关系具有哪些重要性质? 口问题2:如果计算关系的闭包? 口问题3:什么是等价关系与等价类?

 问题1：关系具有哪些重要性质？  问题2：如果计算关系的闭包？  问题3：什么是等价关系与等价类？ 本节提要

关系的定义(回顾) 口若A,B是集合,从A到B的一个关系是x硝一个 子集 口集合,可以是空集 口集合的元素是有序对 口若A=B:称为“集合A上的(二元)关系

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

关系的表示(回顾) 口假设A={bc,B={x1y}//假设为有限集合 口集合表示:R1={(月,(b,a∞,(ca,(c)} 0-1矩阵 有向图 a B r 0 abcd 100 10 000 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

关系的性质:自反性 口集合A上的关系R是: 口自反的 reflexive:定义为:对所有的a∈A,(a,4)∈R 口反自反的 irreflexive:定义为:对所有的a∈A,(2a)∈R 注意区分”非”与”反” 口设A={123},RAXA 口{(11,1,3),(2,2),(2,1),3,3)}是自反的 口{(1,2,2,3,、3,1)}是反自反的 口{(1,2,(22,(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

关系的性质:自反性 A=a,b, c) M

关系的性质：自反性 7

关系的性质:自反性 口R是A上的自反关系台IR 这里L4是集合A上的恒等关系,即:L4={(42)|a∈A} 直接根据定义证明: 口→只需证明:对任意(ab,若(42b∈LA,则(a,b∈R 口<只需证明:对任意的若a∈A则(a,2∈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 关系的性质：自反性

关系的性质:对称性 口集合A上的关系R是: 口对称的 symmetric:定义为:若(a,b)∈R则(h)∈R 口反对称的anti-~:定义为:若(a,b∈R且(h,∈R,则a=b 口设A={1,2,3}, RCAxA 口{(1),1,2,(1,3)2,1)3,1)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

关系的性质:对称性 ·关系R满足对称性:对任意(a,b),若(a,b)∈R,则(ba)∈R 关系R是对称的兮V(∈R→∈R 注意:是对称关系。 反对称并不是对称的否定: (令:A={1,2,3},RcA4) {(1,1)(2,2)}既是对称的,也是反对称的 是对称关系,也是反对称关系

关系的性质：对称性 10