《(1.5.3)--ch3—第三讲离散数学离散数学.pdf》由会员分享，可在线阅读，更多相关《(1.5.3)--ch3—第三讲离散数学离散数学.pdf（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离离 散散 数数 学学 Discrete MathematicsDiscrete Mathematics 3-6 关系的性质关系的性质(The properties of Relations)定义定义3.6.1 设设 R 为集合为集合 X 上的二元关系上的二元关系,若若对于对于每一个每一个 x X,有有xRx,即即 R 在在 X 上自反上自反(x)(x X xRx)例如例如:1)A上的全域关系上的全域关系EA和恒等关系和恒等关系IA都是都是 A上的自反关系上的自反关系;2)小于等于关系小于等于关系LA,整除关系整除关系DB分别是分别是 A 和和B上的自反关系上的自反关系;3)包含关系包含关系R
2、 是给定集合族上的自反关系是给定集合族上的自反关系;4)平面上三角形的全等关系也是自反的平面上三角形的全等关系也是自反的.则称二元关系则称二元关系 R 在在 X 上是上是自反的自反的.定义定义3.6.2 设设 R 为集合为集合 X 上的二元关系上的二元关系,若若对于对于每一个每一个 x X,有有 R,即即 R 在在 X 上反自反上反自反(x)(x X R)例如例如:1)小于关系和真包含关系小于关系和真包含关系及及是给定集合上的是给定集合上的反反自反关系自反关系;2)生活中的父子关系是反自反的生活中的父子关系是反自反的.注意注意:不是自反的关系不是自反的关系,不一定就是反自反的关系不一定就是反自
3、反的关系.例例 A=1,2,3,S=,S不是自反也不是反自反的不是自反也不是反自反的.则称二元关系则称二元关系 R 在在 X 上是上是反自反的反自反的.例例1.设设 A=0,1,2,3 R1=,R2=,R3=,R4=,自反自反 自反自反 既不是自反也不是反自反既不是自反也不是反自反 21000011000110001RM 40100001000010100RM 定理定理(补补).设设R 为为 A上的二元关系上的二元关系,则则 R自反自反 IA R R 反自反反自反 RIA=反自反反自反 定义定义3.6.3 设设 R 为集合为集合 X 上的二元关系上的二元关系,每当有每当有xRy,就有就有yRx
4、,若若对于每一个对于每一个x,y X,则称二元关系则称二元关系R 在在 X 上是上是对称的对称的.即即 R 在在 X 上对称上对称(x)(y)(x,y XxRyyRx)例如例如:1)A上的全域关系上的全域关系EA和恒等关系和恒等关系IA及及都是都是 A上的对称关系上的对称关系.2)同一班级里学生之间的同学关系是对称的同一班级里学生之间的同学关系是对称的.3)三角形集合中三角形的相等关系是对称的三角形集合中三角形的相等关系是对称的.定义定义3.6.4 设设 R 为集合为集合 X 上的二元关系上的二元关系,每当有每当有xRy 和和 yRx,必有必有x=y,若若对于每一个对于每一个x,y X,则称关
5、系则称关系R 在在 X 上是上是反对称的反对称的.即即 R在在X上反对称上反对称(x)(y)(x,y XxRyyRx x=y)(x)(y)(x,y X xy xRy yRx)例如例如:3)集合的集合的 关系也是反对称的关系也是反对称的.2)恒等关系恒等关系IA及空关系及空关系 是是A上的反对称关系上的反对称关系;1)小于等于关系小于等于关系,整除关系是相应集合上的反对称关系整除关系是相应集合上的反对称关系;例例2.设设 A=0,1,2,3 R1=,R2=,R3=,R4=,对称对称 反对称反对称 对称对称 既不是对称也不是反对称既不是对称也不是反对称 反对称反对称 100000110010100
6、10RM 20010011000000100RM 注意注意:(1)不是对称的不是对称的,并非是反对称的并非是反对称的.也就是说也就是说,对于某种关系对于某种关系,可能既不是对称关系可能既不是对称关系,又不是反对称关系又不是反对称关系.例例 A=a,b,c,S=,S不是对称也不是反对称的不是对称也不是反对称的.(2)对于某种关系对于某种关系,可能既是对称的可能既是对称的,又是反对称的又是反对称的.例例 A=1,2,3,S=,S是对称是对称,也是反对称的也是反对称的.定义定义3.6.5 设设 R 为集合为集合 X 上的二元关系上的二元关系,每当有每当有xRy,yRz 时时,就有就有xRz,若若对于
7、每一个对于每一个x,y X,则称关系则称关系R 在在 X 上是上是传递的传递的.即即 R在在X上传递上传递(x)(y)(z)(x,y,z XxRyyRzxRz)例如例如:1)A上的全域关系上的全域关系EA和恒等关系和恒等关系IA及及 都是都是 A上的传递关系上的传递关系;2)小于等于关系小于等于关系,整除关系是相应集合上的传递整除关系是相应集合上的传递关系关系.3)集合的集合的 关系也是传递关系关系也是传递关系.例例3.设设 A=0,1,2,3 R9=,R10=,R11=,可传递可传递 不可传递不可传递 可传递可传递 例例4 设集合设集合A=2,3,5,7,2xyRx y 试证明试证明R在在A
8、上是自反的、对称的和传递的上是自反的、对称的和传递的.证证 对于任意的对于任意的xA,有有 02xx 是整数是整数.即即R，故，故R是自反的是自反的.对于任意的对于任意的x,yA,若若R,即即 2xy 是整数是整数.则则 2yx 也是整数也是整数.即即R,因此因此 R是对称的是对称的.对于任意的对于任意的x,y,zA,若若R,R,即即 是整数是整数.则则()()22xzxyyz 也是整数也是整数.即即R,因此因此 R 是传递的是传递的.,22xy yz Z 2.由关系图、关系矩阵判别关系的性质由关系图、关系矩阵判别关系的性质(1)若关系若关系R具有自反性具有自反性,当且仅当关系矩阵中当且仅当关
9、系矩阵中,主对角线上主对角线上 的元素全为的元素全为1;在关系图中每个结点都有一条回路在关系图中每个结点都有一条回路.(2)若关系若关系R具有反自反性具有反自反性,当且仅当关系矩阵中当且仅当关系矩阵中,主对角线上主对角线上 的元素皆为的元素皆为0；在关系图上每个结点都没有自回路在关系图上每个结点都没有自回路.在关系图上两个不同结点间的有向弧不可能成对出现在关系图上两个不同结点间的有向弧不可能成对出现,结结点可以有自回路点可以有自回路.(4)若关系若关系R具有反对称性具有反对称性,当且仅当关系矩阵中以主对角线当且仅当关系矩阵中以主对角线 对称的元素不能同时为对称的元素不能同时为1,(可以同时为零
10、可以同时为零),而主对角线上的而主对角线上的元素是元素是1或者是零或者是零;(3)若关系若关系R具有对称性具有对称性,当且仅当关系矩阵是对称矩阵当且仅当关系矩阵是对称矩阵;在关系图中在关系图中,若两个结点间存在有向弧若两个结点间存在有向弧,必须是成对的必须是成对的.(5)若结点若结点a 有有向弧指向有有向弧指向b又有有向弧指向又有有向弧指向c,则结点则结点a 一定一定有有向弧指向有有向弧指向c,特别特别,若结点若结点a 有有向弧指向有有向弧指向b同时同时b又有有又有有向弧指向向弧指向a,则结点则结点a,b上一定各有一条自回路上一定各有一条自回路.例例5 设设A=1,2,3,下面分别给出集合下面
11、分别给出集合A上三个关系的关系图上三个关系的关系图,试判断它们的性质试判断它们的性质.解解:1 是自反的是自反的,2 非自反非自反,3 是自反的是自反的,1,1 但但 1 非对称非对称,非反对称非反对称,不可传递不可传递 可传递可传递.反对称反对称,非对称非对称,非反自反非反自反,非反对称非反对称,可传递的可传递的.对称的对称的,练习练习下图给出了下图给出了1,2,3上三个关系的关系图上三个关系的关系图,试对每一个图所试对每一个图所表示的关系的性质作出判别表示的关系的性质作出判别,并将选中的性质的代号填入相应并将选中的性质的代号填入相应的括号内的括号内.若若 A.自反的自反的 B.对称的对称的
12、 C.反对称的反对称的 D.可传递可传递 E.反自反反自反 则则 是是()则则 是是()则则 是是()1 2 3 AB A E 例例6.判断下图中关系的性质判断下图中关系的性质,并说明理由并说明理由.解解(a)该关系不是自反的也不是反自反的该关系不是自反的也不是反自反的,因为有的顶点有环因为有的顶点有环,有的顶点没有环有的顶点没有环;它是对称的它是对称的,因为无单向边因为无单向边;它不是反对称的它不是反对称的,因为图中有双向边因为图中有双向边;它也不是传递的它也不是传递的,因为图中有边因为图中有边和和,但没有边但没有边.例例6.判断下图中关系的性质判断下图中关系的性质,并说明理由并说明理由.(
13、b)该关系是反自反的该关系是反自反的,但不是自反的但不是自反的,因为每个顶点都没因为每个顶点都没有环有环;它是反对称的它是反对称的,不是对称的不是对称的,因为图因为图(b)中只有单向边中只有单向边;它是传递的它是传递的,因为不存在顶点因为不存在顶点x,y和和 z,使得使得:有边有边 和和,但没有边但没有边.解解 例例6.判断下图中关系的性质判断下图中关系的性质,并说明理由并说明理由.(c)该关系是自反的该关系是自反的,不是反自反的不是反自反的,因为每个顶点都有环因为每个顶点都有环;它是反对称的它是反对称的,不是对称的不是对称的,因为图因为图(c)中只有单向边中只有单向边;它不是传递的它不是传递的,因为边因为边和和,但没有边但没有边.解解 重点：掌握关系的基本性质及其判别方法重点：掌握关系的基本性质及其判别方法 小结小结:本节介绍了关系的基本性质及其判别方法本节介绍了关系的基本性质及其判别方法 例例5.设设 A=1,2,3,4,5,A 上的关系上的关系 R=a-b 是偶数是偶数 则则R具有哪些性质？具有哪些性质？R=,R是自反、是自反、对称、对称、不是反对称、不是反对称、可传递的可传递的.