《离散数学》课程教学课件（PPT讲稿）7b 二元关系的性质

关系的性质

析取范式与合取范式 关系的性质

关系的性质定义7.11 设R为A上的关系,(1)若 Vx(xEA>ER),则称 R在 A 上是自反的.(2) 若 Vx(xEA>史R),则称 R在 A 上是反自反的.实例：自反：全域关系EA，恒等关系IA，小于等于关系LA整除关系D反自反：实数集上的小于关系、幂集上的真包含关系A=[1,2,3], R1, R2, R3是A上的关系,其中Ri =[,]R2 =[,,,]R3 =[]R2自反，R3反自反，R,既不是自反的也不是反自反的.2

关系的性质 定义7.11 设 R 为A上的关系, (1) 若 x(x∈A→R), 则称 R 在 A 上是自反的. (2) 若 x(x∈A→R), 则称 R 在 A 上是反自反的. 实例： 自反：全域关系EA , 恒等关系IA , 小于等于关系LA , 整除关系DA 反自反：实数集上的小于关系、幂集上的真包含关系. A={1,2,3}, R1 , R2 , R3是A上的关系, 其中 R1＝{,} R2＝{,,,} R3＝{} R2 自反 ，R3 反自反，R1既不是自反的也不是反自反的. 2

对称性与反对称性定义7.12设R为A上的关系，(1)若VxVy(x,yEAΛER>ER), 则称 R为 A上对称的关系：(2)若VxVy(x,yEA^ERΛER->x=y),则称 R为A上的反对称关系.实例：对称关系：A上的全域关系EA，恒等关系l和空关系①反对称关系：恒等关系I和空关系也是A上的反对称关系，设A=[1,2,3],R1,R2,R3和R4都是A上的关系,其中R1 =[,],R, =,,]R3 =[,],R4 =[,,}R1：对称和反对称；R2：只有对称；R3：只有反对称;3R4：不对称、不反对称

对称性与反对称性 定义7.12设 R 为 A上的关系, (1) 若xy( x,y∈A∧∈R→∈R), 则称 R 为 A上对 称的关系. (2) 若xy( x,y∈A∧∈R∧∈R→x=y), 则称 R 为 A上的反对称关系. 实例：对称关系：A上的全域关系EA , 恒等关系IA和空关系 反对称关系：恒等关系IA和空关系也是A上的反对称关系. 设A＝{1,2,3}, R1 , R2 , R3和R4都是A上的关系, 其中 R1＝{,} R2＝{,,} R3＝{,} R4＝{,,} R1：对称和反对称； R2：只有对称；R3：只有反对称； R4：不对称、不反对称 3

传递性定义7.13设R为A上的关系，若VxVyVz(x,y,zEA^ER^ER->ER),则称R是A上的传递关系实例：A上的全域关系EA恒等关系I和空关系①，小于等于和小于关系，整除关系，包含与真包含关系设A=[1,2,3], R1, R2, R3是A上的关系, 其中R1 =[,]R2 =[,]R3 =[]R和R3是A上的传递关系，R不是A上的传递关系.4

传递性 定义7.13设R为A上的关系, 若 xyz(x,y,z∈A∧∈R∧∈R→∈R), 则称 R 是A上的传递关系. 实例： A上的全域关系 EA ,恒等关系 IA和空关系 ，小于等 于和小于关系，整除关系，包含与真包含关系 设 A＝{1,2,3}, R1 , R2 , R3是A上的关系, 其中 R1＝{,} R2＝{,} R3＝{} R1和R3是A上的传递关系, R2不是A上的传递关系. 4

关系性质成立的充要条件定理7.9设R为A上的关系，则(1)R在A上自反当且仅当IA二R(2)R在A上反自反当且仅当RnIA=①(3）R在A上对称当且仅当R=R-1(4)R在A上反对称当且仅当RnR-1CIA(5）R在A上传递当且仅当RRCR5

关系性质成立的充要条件 定理7.9设R为A上的关系, 则 (1) R 在A上自反当且仅当 IA  R (2) R 在A上反自反当且仅当 R∩IA =  (3) R 在A上对称当且仅当 R=R−1 (4) R 在A上反对称当且仅当 R∩R −1  IA (5) R 在A上传递当且仅当 RR  R 5

证明(1) R在A上自反当且仅当ICR(1)必要性任取,由于R在A上自反必有EIA = x,yEA^x=y= ER从而证明了IACR充分性.任取X,有XEA=EIA=ER因此R在A上是自反的.6

证明 (1) 必要性 任取, 由于R 在A上自反必有 ∈IA  x,y∈A∧x=y  ∈R 从而证明了IAR 充分性. 任取x, 有 x∈A  ∈IA  ∈R 因此 R 在A上是自反的. (1) R 在A上自反当且仅当 IA  R 6

证明(3) R在A上对称当且仅当R=R-1(3)必要性,任取,ERERER-1所以 R= R-1充分性.任取,由R= R-1得ER =ER-1 =ER所以R在A上是对称的7

证明 (3) 必要性. 任取, ∈R  ∈R  ∈R −1 所以 R = R −1 充分性. 任取, 由R = R −1得 ∈R  ∈R −1  ∈R 所以R在A上是对称的 (3) R 在A上对称当且仅当 R=R−1 7

证明(4) R在A上反对称当且仅当 RnR-1CIA(4)必要性.任取,有ERnR-1 = ER^ER-1（反对称）=ERΛER = X=y ^x,yEA=>ElA这就证明了RnR-1IA充分性.任取,ER^ER = ER^ER-1=ERnR-1=ElA= x=y从而证明了R在A上是反对称的。8

证明 (4) 必要性. 任取, 有 ∈R∩R −1  ∈R∧∈R −1  ∈R∧∈R  x=y  x,yA （反对称）  ∈IA 这就证明了R∩R −1IA 充分性. 任取, ∈R∧∈R  ∈R∧∈R −1  ∈R∩R −1  ∈IA  x=y 从而证明了R在A上是反对称的. (4) R 在A上反对称当且仅当 R∩R −1  IA 8

证明(5)R在A上传递当且仅当RRCR(5)必要性.任取有ERR 3t (ER^ER)（传递性）=ER所以RRCR充分性.任取,ER, 则ER^ER=ER.R = ER所以R在A上是传递的9

证明 (5) 必要性. 任取有 ∈RR  t (∈R∧∈R)  ∈R （传递性） 所以 RR  R 充分性. 任取,∈R, 则 ∈R∧∈R  ∈RR  ∈R 所以 R 在 A上是传递的 (5) R 在A上传递当且仅当 RR  R 9

关系性质的三种等价条件自反性反自反性对称性反对称性传递性R=R-1集合RnR-1CAIACRRnIA=OR.RCR关系主对角主对角线矩阵是若rj= 1, 且M2中1位置,矩阵元素全是0i#j, 则ri= 0线元素对称矩阵M中相应位全是1置都是1关系每个顶每个顶点两点之间两点之问有点x,到x,有图点都有都没有环边,X,到x有有边,是边,是一条有环一对方向向边边,则x,到xk相反的边也有边10

自反性 反自反性 对称性 反对称性 传递性 集合 IAR R∩IA = R=R −1 R∩R −1IA RRR 关系 矩阵 主对角 线元素 全是1 主对角线 元素全是0 矩阵是 对称矩阵 若r ij＝1, 且 i≠j, 则r ji＝0 M2中1位置, M中相应位 置都是1 关系 图 每个顶 点都有 环 每个顶点 都没有环 两点之间 有边, 是 一对方向 相反的边 两点之间有 边,是一条有 向边 点xi到xj有 边, xj到xk有 边, 则xi到xk 也有边 关系性质的三种等价条件 10