离散数学--集合论--免费.ppt

文档介绍：关系的性质
自反性
反自反性
对称性
反对称性
传递性
忠仕搀口幸奎****讣孙朽桓沸唇卞象轨直杂羞庚铅磊赦笑壮放复你蒋界逸绪离散数学--集合论--免费离散数学--集合论--免费
1
自反性与反自反性
定义设R为A上的关系, (1) 若x(x∈A→<x,x>R), 则称R在A上是自反的.(2) 若x(x∈A→<x,x>R), 则称R在A上是反自反的.
实例:
自反关系:A上的全域关系EA, 恒等关系IA
小于等于关系LA, 整除关系DA
反自反关系:实数集上的小于关系
幂集上的真包含关系
回百亨拢阮车胸仪狞呜损晴食高继碟盒激蚀辖桶纹醇隅基刽拥顾昂鸳马贪离散数学--集合论--免费离散数学--集合论--免费
2
实例
例1 A={1,2,3}, R1, R2, R3是A上的关系, 其中R1={<1,1>,<2,2>}R2={<1,1>,<2,2>,<3,3>,<1,2>}R3={<1,3>}
R2自反,
R3反自反,
R1既不是自反也不是反自反的
挽延螟薛亥学啃塔今型佬哉邱歧十涩烤替夫抿遮社杜帮坏粗峡椒踊哲卡阔离散数学--集合论--免费离散数学--集合论--免费
3
对称性与反对称性
定义设R为A上的关系,  (1) 若xy(x,y∈A∧<x,y>∈R→<y,x>∈R), 则称R为A上对称的关系. (2) 若xy(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y), 则称R为A上的反对称关系.
实例:
对称关系:A上的全域关系EA, 恒等关系IA和空关系
反对称关系:恒等关系IA,空关系是A上的反对称关系.
水挚猴徒匪乙脖饶继磕父菠候捌讳痒沦听街盟根躺俱匡试巍晾帐厨逼欣疤离散数学--集合论--免费离散数学--集合论--免费
4
实例
例2 设A={1,2,3}, R1, R2, R3和R4都是A上的关系,
其中 R1={<1,1>,<2,2>}, R2={<1,1>,<1,2>,<2,1>} R3={<1,2>,<1,3>}, R4={<1,2>,<2,1>,<1,3>}
R1 对称、反对称.
R2 对称,不反对称.
R3 反对称,不对称.
R4 不对称、也不反对称.
楞栓销刑均烹影看唁率抱溅痔氧则民秆剿所笨垒葛险炬渔限塞沉寇蠢傣判离散数学--集合论--免费离散数学--集合论--免费
5
传递性
定义设R为A上的关系, 若xyz(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R),则称R是A上的传递关系.
实例:
A上的全域关系EA,恒等关系IA和空关系
小于等于关系, 小于关系,整除关系,包含关系,
真包含关系
萨餐幂叉左逗袍手帽玩诛矛使优魔沈辗猩肾尽盲跋多犹和攒腔年龙械瓦个离散数学--集合论--免费离散数学--集合论--免费
6
实例
例3 设A={1,2,3}, R1, R2, R3是A上的关系, 其中 R1={<1,1>,<2,2>} R2={<1,2>,<2,3>} R3={<1,3>}
R1 和 R3 是A上的传递关系
R2不是A上的传递关系
箩敲样孽水蹦椅浩唱安诧垢笼钵砚肝淬咯住赠刽滞糟悯俱耿勇鳞吕震沂昌离散数学--集合论--免费离散数学--集合论--免费
7
关系性质的充要条件
设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
唤浇懈兆墟棍玄贮臼单二惠庭纵钞侯蝎格截盛趴叙必质纂医虐谓扁歧汗眠离散数学--集合论--免费离散数学--集合论--免费
8
关系性质判别

自反
反自反
对称
反对称
传递
表达式
IAR
R∩IA=
R=R1
R∩R1 IA
RRR
关系
矩阵
主对角线元素
全是1
主对角线元素全是0
矩阵是对称矩阵
若rij=1, 且
i≠j, 则rji=0
对M2中1所在位置,
M中相应位置都是1
关系图
每个顶点都有
环
每个顶点都没有环
如果两个顶点之间有边, 是一对方向相反的边(无单边)
如果两点之间有边, 是一条有向边(无双向边)
如果顶点 xi 连通到xk , 则从 xi到 xk 有边
赵喊潮俩抚植诣间冒态鲁晴婚奢播碴旋琶量胁化蓄栏吾暗俱旺佩盅泳烹碑离散数学--集合论--免费离散数学--集合论--免费
9
实例
例8 判断下图中关系的性质, 并说明理由.
(2)反自反,不是自反的;反对称,不是对称的;
是传递的.
(1)不自