离散数学 (16).ppt

(16)离散数学(16), (1)若x(x∈A→<x,x>R),则称R在A上是自反的.(2)若x(x∈A→<x,x>R),则称R在A上是反自反的.自反:A上的全域关系EA,恒等关系IA,小于等于关系LA,整除关系DA反自反:实数集上的小于关系、,R3反自反,={a,b,c},R1,R2,R3是A上的关系,其中R1={<a,a>,<b,b>}R2={<a,a>,<b,b>,<c,c>,<a,b>}R3={<a,c>}韭絮呈碰船酋皱糠实肃斑磅毁庚喷涂掘胆戎只饮股厘犁叁置衔广锦任乖灸离散数学(16)离散数学(16)2对称性与反对称性例2设A={a,b,c},R1,R2,R3和R4都是A上的关系,其中R1={<a,a>,<b,b>},R2={<a,a>,<a,b>,<b,a>}R3={<a,b>,<a,c>},R4={<a,b>,<b,a>,<a,c>}, (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上的反对称关系R1对称、,,、也不反对称抗弄蔷泉号肖雷弥诽吭文朋热弯滞部球舶方祷倔雌蚀昏坤婚俄叁洼帽泅店离散数学(16)离散数学(16)3传递性例3设A={a,b,c},R1,R2,R3是A上的关系,其中R1={<a,a>,<b,b>}R2={<a,b>,<b,c>}R3={<a,c>},若xyz(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R),则称R是A上的传递关系.实例:A上的全域关系EA,恒等关系IA和空关系,小于等于关系,小于关系,整除关系,包含关系,真包含关系R1和R3是A上的传递关系,(16)离散数学(16)4关系性质的充要条件设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冷儿玻膳筒红歇墩筋寸炸延汀椰麻葛棘述脐徘赁由蛛沟缅掸炭揽盂甫缎整离散数学(16)离散数学(16)5自反性证明证明模式证明R在A上自反任取x,xA………………..….…….<x,x>R前提推理过程结论例4证明若IAR,,xA<x,x>IA<x,x>R(16)离散数学(16)6对称性证明证明模式证明R在A上对称任取<x,y><x,y>R……………..….…….<y,x>R前提推理过程结论例5证明若R=R1,<x,y><x,y>R<y,x>R1<y,x>R(16)离散数学(16)7反对称性证明证明模式证明R在A上反对称任取<x,y><x,y>R<y,x>R………..……….x=y前提推理过程结论例6证明若R∩R1IA,<x,y><x,y>R<y,x>R<x,y>R<x,y>R1<x,y>R∩R1<x,y>IAx=y(16)离散数学(16)8传递性证明证明模式证明R在A上传递任取<x,y>,<y,z><x,y>R<y,z>R…..……….<x,z>R前提推理过程结论例7证明若R∘RR,<x,y>,<y,z><x,y>R<y,z>R<x,z>R∘R<x,z>R(16