离散数学 第2版 教学课件 作者 王元元 离散第27讲 关系的特性.ppt

《离散数学 第2版 教学课件 作者 王元元 离散第27讲 关系的特性.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机专业基础课程授课人：王元元单位：计算机理论教研室理工大学指挥自动化学院PowerPointTemplate_Sub1二元关系2等价关系3序关系2第27讲关系的特性关系的特性《离散数学》第27讲Page164to167引言不研究具体某一个关系，而是研究某一类关系，对关系分类分类依据——关系的特性关系有哪些基本特性？自反性、反自反性对称性、反对称性传递性4第27讲关系的特性定义：设R是集合A上的关系，如果对任意xA，均有xRx，则称R是自反的(reflexive)。R自反当且仅当x(xA→xRx)10.1.3关系的特性自反性（reflexivity）集合I+为正整数集，

2、I+上的整除关系集合A={1,2,3}，A上的空关系相等关系全关系空集上的空关系示例判别集合A={1,2,3}，ρ(A)上的包含关系三角形的相似关系人类的父子关系集合I为整数集，I上的整除关系I上的大于关系√√√√√√××××5第27讲关系的特性A={1,2,3,4}R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>}123410.1.3关系的特性自反性与关系图6第27讲关系的特性A={1,2,3,4}R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,4>}123410.1.3关系的特性自反性与关系图7第27讲关系的特性定义：设R是集合A上

3、的关系，如果对任意xA，xRx均不成立，则称R是反自反的(irreflexive)。R反自反当且仅当x(xA→┐xRx)10.1.3关系的特性反自反性（irreflexivity）集合I+为正整数集，I+上的整除关系集合A={1,2,3}，A上的空关系相等关系全关系空集上的空关系示例判别集合A={1,2,3}，ρ(A)上的包含关系人类的父子关系集合I为整数集，I上的整除关系I上的大于关系√××××√×√√8第27讲关系的特性A={1,2,3,4}R={}123410.1.3关系的特性反自反性与关系图<1,3>,<3,1>,<3,4>,<4,4>,<2,3>9第27讲关系

4、的特性自反性与反自反性的关系自反和反自反并非互为否定有些关系既是自反的，也是反自反的上的空关系任何集合上的空关系都是反自反的非空集合上的空关系不是自反的。有些关系既不自反也不反自反整数集合上的整除关系A={1,2,3},A上关系R={<1,1>,<2,2>}10第27讲关系的特性定义：设R是集合A上的关系，如果对任意x,yA，均有xRy蕴涵yRx，则称R是对称的（symmetric）R对称当且仅当xy(x,yA∧xRy→yRx)10.1.3关系的特性对称性（symmetry）集合I+为正整数集，I+上的整除关系集合A={1,2,3}，A上的全关系相等关系空关系集合A=

5、{1,2,3}，A上的关系R={<1,1>,<2,2>}示例判别集合A={1,2,3}，ρ(A)上的包含关系三角形的相似关系人类的父子关系集合I为整数集，I上的小于等于关系不等于关系√××√√√×√√×11第27讲关系的特性A={1,2,3,4}R={<1,4>,<4,1>,<3,3>,<3,4>,<4,3>}123410.1.3关系的特性对称性与关系图12第27讲关系的特性定义：设R是集合A上的关系，如果对任意x,yA，均有xRy且yRx蕴涵x=y，则称R是反对称的（antisymmetric）R反对称当且仅当xy(x,yA∧xRy∧yRx→x=y)10.1.3关系的

6、特性反对称性（antisymmetry）集合I+为正整数集，I+上的整除关系集合A={1,2,3}，A上的全关系相等关系空关系集合A={1,2,3}，A上的关系R={<1,1>,<2,3>}示例判别集合A={1,2,3}，ρ(A)上的包含关系三角形的相似关系人的父子关系集合I为整数集，I上的整除关系小于等于关系小于关系×√√√√√√√××√13第27讲关系的特性A={1,2,3,4}R={<2,3>,<4,3>,<2,2>,<3,4>}123410.1.3关系的特性反对称性与关系图14第27讲关系的特性对称性与反对称性的关系对称和反对称也并非互为否定有些关系既是对称的，也是反对

7、称的任意集合上的相等关系、空关系A={1,2,3},A上关系R={<1,1>,<2,2>}有些关系既不对称也不反对称整数集合上的整除关系A={1,2,3},A上关系R={<1,1>,<2,3>,<3,2>,<1,3>}15第27讲关系的特性反对称性似应定义为xy(x,yA∧xRy→yRx)但注意：当x=y时上述定义是有问题的x(xA∧xRx→xRx)可以修改为：xy(x,yA∧xRy∧xy→yRx)逻辑上等价于xy(x,yA∧xRy∧yRx→x=y)关于反对称性