离散数学-耿素云(第5版).ppt

, (1)若x(x∈A→<x,x>R),则称R在A上是自反的.(2)若x(x∈A→<x,x>R),则称R在A上是反自反的.实例:反关系:A上的全域关系EA,恒等关系IA小于等于关系LA,整除关系DA反自反关系:={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反自反,, (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对称、,,、也不反对称..5传递性定义设R为A上的关系,若xyz(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R),则称R是A上的传递关系.实例:A上的全域关系EA,恒等关系IA和空关系小于等于关系,小于关系,整除关系,包含关系,={1,2,3},R1,R2,R3是A上的关系,其中R1={<1,1>,<2,2>}R2={<1,2>,<2,3>}R3={<1,3>},则(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自反反自反对称反对称传递表达式IARR∩IA=R=R1R∩R1IARRR关系矩阵主对角线元素全是1主对角线元素全是0矩阵是对称矩阵若rij=1,且i≠j,则rji=0对M2中1所在位置,M中相应位置都是1关系图每个顶点都有环每个顶点都没有环如果两个顶点之间有边,是一对方向相反的边(无单边)如果两点之间有边,是一条有向边(无双向边)如果顶点xi连通到xk,,并说明理由.(b)反自反,不是自反的;反对称,不是对称的;是传递的.(a)不自反也不反自反;对称,不反对称;不传递.(c)自反,不反自反;反对称,不是对称;不传递..10