离散数学--关系的性质(数学教材)

格式：ppt
大小：551.50 KB
文档页数：28

下载文档原格式

离散数学关系-PPT

离散数学关系
基本要求和重难点:
• 基本要求
了解序偶与笛卡尔积,掌握关系得性质和运算,重点掌握关系闭包运算得求法和偏序关系及哈斯图得正确画法。
• 重难点
关系5种性质得判断,关系得闭包运算和偏序关系得性质及特殊元素得判断。
引言
日常生活中,大家熟知一些常见关系, 例:家庭集合,有父子关系、夫妻关系等。全校同学作为一个集合,有同班关系,同组关系。在计算机科学中,在计算机逻辑设计中,应用了等价关系,相容关系。在编译原理、关系数据库、数据结构、数学中也有关系。
例题
返回第5、3节目录
五、传递性例题
例: A={1,2,3,4} R={<1,4>,<4,3>,<1,3>,<3,1>,<1,2>,<3,2>,<2,3>, <4,2>,<1,1>,<3,3>} R不就是传递得
返回传递性
返回第5、3节目录
六、举例
自反性反自反性对称性反对称性传递性
任何集合上得
返回总目录
一、自反性
自反性
定义: 若xA,均有xRx,那么称R就是自反得。
A上关系R就是自反得x(xA xRx)
在关系矩阵中,反映为主对角线元素均为1 在关系图中,反映为每结点都有自回路例1: A＝{1,2,3},R={<1,1>,<2,2>,<3,3>,<1,2>}
1 23
例2:“＝”关系和“≤”关系就是自反得吗？
S={<4,2>,<2,5>,<3,1>,<1,3>}

离散数学第二章关系

例9 .设A={1,2,3,4} ，B={2,4,6,8,10} 。 R={(1,2),(2,4),(3,6)}。
则 (R) = {1,2,3}A ， (R) = {2,4,6}B 。
二.关系的一些关联性质 17
离散数学
定理1. 设R1,R2 A×B是两个关系。若 R1 R2 ，则
(1)保序性： (R1) (R2) ； (2)保序性： (R1) (R2) ；
注：笛卡尔(1596-1650 )，法国数学家， 1637年发表《方法论》之一《几何学》，首次提出坐标及变量概念。这里是其概念的推广。
定义2. • 二个集合A，B的(二维或二重)叉积定义为 A×B ={(a, b): a A bB} ； •其元素——二元组(a, b)通常称为序偶或偶对(ordered
故 (R1)∩ (R2) = {1,2 }
21
离散数学
所以 (R1)∩ (R2) (R1 ∩ R2) 。
元素aA和集合A1A在关系R A×B下的关联集 (1)a的R-关联集(R-relative set of a)：
R(a)={b : bBaRb }B ；
(2) A1的R-关联集(R-relative set of A1)： R(A1)={b : bB (aA1)(aRb) }B 。
•当A=B时，即RA×A，则称R是A上的一个二元关系。
例1 . 设A是西安交通大学全体同学组成的集合。 11
离散数学
R={(a,b) : aAbAa与b是同乡}A×A 于是，R是西安交通大学同学之间的同乡关系。
例2 . 设A是某一大家庭。
R1 = {(a,b) : aAbAa是b的父亲或母亲}A×A R2 = {(a,b) : aAbAa是b的哥哥或姐姐}A×A R3 = {(a,b) : aAbAa是b的丈夫或妻子}A×A 于是，

离散数学13关系的性质

所以 RRR .
充分性。任取<x,y>,<y,z>∈R，则
<x,y>∈R∧<y,z>∈R
<x,z>∈RR
<x,z>∈R
(因为RRR)
所以 R在A上是传递的。
例 13
例13 设A是集合，R1和R2是A上的关系，证明： (1)若R1，R2是自反的和对称的，则R1∪R2也是自反的和对
称的。 (2)若R1和R2是传递的，则R1∩R2也是传递的。
例10 设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>}
说明R1，R2和R3是否为A上的自反关系和反自反关系。解答
R1既不是自反的也不是反自反的， R2是自反的， R3是反自反的。
例13 (2)的证明
(2)若R1和R2是传递的，则R1∩R2也是传递的。证明由R1和R2的传递性有
R1 R1 R1 和 R2 R2 R2 , 再使用定理7.4得
(R1∩R2)(R1∩R2) R1 R1∩R1 R2∩R2 R1∩R2 R2 ((R将1∩前R面2)∩的R包1 含 R式2∩代R入2 )R1 R1∩R2 , 从而证明了R1∩R2也是A上的传递关系。
定理9 (4)的证明
（4） R在A上反对称当且仅R∩R-1 IA .
必要性。
充分性。
任取<x,y>，有
任取<x,y>, 则有
<x,y>∈R∩R-1
<x,y>∈R ∧ <y,x>∈R

离散数学28.关系的性质1

例如，集合X上的全域关系EX、恒等关系IX都不是X上的反自反关系.
2）若关系R不是反自反的，关系R也不一定是自反的，反之也成立.
XZ-{0}时，整除关系 R2={<x,y>x,yX∧x整除y}. 都是自反关系.
(3) 数集X上的小于关系 R3= {<x,y>x,yX∧xy}. 不是自反的.
若集合X上的二元关系R是自反的充要条件： • 1） R是自反的恒等关系IX R. • 2） R是自反的关系R的关系矩阵MR的主对角线全是1. • 3） R是自反的关系R的关系图中每个结点都有上的二元关系,如果对于每个x∈X，有<x,x>R，则称二元关系R是反自反的.
R在X上反自反 (x)(xX <x,x>R ). 例如，数集X上的小于关系 R3={<x,y>x,yX∧xy} 空关系，均为反自反关系.
若集合X上的二元关系R是反自反的充要条件： • 1） R是反自反的恒等关系IX R= . • 2） R是反自反的关系R的关系矩阵MR的主对角线全是0. • 3） R是反自反的关系R的关系图中每个结点都没有自回路.
设 X={1,2,3}, R1={<1,1>,<2,2>,<3,3>,<1,2>} 是X上的自反关系; R2={<1,3>} 是X上的反自反关系; R3 ={<1,1>,<1,2>,<2,2>,<2,3>} 既不是自反的，也不是反自反的.
注意：
1）一个关系R如果是自反的，一定不是反自反的；如果是反自反的，则一定不是自反的.
关系的性质
一、关系的性质
关系的性质主要有5种：自反性、反自反性、对称性、反对称性、传递性.

关系的性质-集合与关系-离散数学

例如：朋友关系，同学关系，同乡关系，不相等关系() 是对称关系，相等关系(=)？？？。

非（不是）对称的 (x) (y) (xA∧yA∧<x,y> R ∧ <y,x> R )
第8 页
对称性的关系矩阵和关系图的特点

定义：R是集合A上的关系，若对任何x, y∈A，若有 <x,y>R，必有<y,x>R ，则称R为A中的对称关系。 R是A上对称的 (x)(y)((xA∧yA∧<x,y>R) <y,x>R) 从关系矩阵看对称性：以主对角线为对称的矩阵。从关系有向图看对称性：在两个不同的结点之间，若有边的话，则有方向相反的？ 1 0 两条边。
第2 页
一、自反性

定义：设R是集合A上的关系，若对于任意x∈A都有<x,x>∈R (xRx)，则称R是A中的自反关系。即 R是A中自反的(x)(xA<x,x>∈R ) 该定义表明在自反关系 R中，除其他序偶外，必须包括有全部由每个x ∈A所组成的相同元素的序偶。例如：设X={a,b,c}, R1={<a,a>,<b,b>,<c,c>,<a,b>} 是自反关系。 R2={<a,a>,<b,b>,<a,b>} 不是自反关系。例如：相等关系(=)，小于等于关系()，包含关系() 等是自反关系。非（不是）自反的 (x)(xA∧<x,x> R )
第7 页
三、对称性

定义：R是集合A上的关系，若对任何x, y∈A，若有 <x,y>R，必有<y,x>R ，则称R为A中的对称关系。 R是A上对称的 (x)(y)((xA∧yA∧<x,y>R) <y,x>R)

离散数学-04-关系的性质

7
4.3.1 关系性质的定义和判别
对称性与反对称性（续）
例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>} R1 对称 R2 对称 R3 对称？？？反对称反对称反对称？？？
12
4.3.1 关系性质的定义和判别
传递性（续）
例3 设A＝{a, b, c}, R1, R2, R3是A上的关系, 其中 R1＝{<a,a>,<b,b>} R2＝{<a,b>,<b,c>} R3＝{<a,c>}
R1 和 R3 是A上的传递关系, R2 不是A上的传递关系.
13
4.3.1 关系性质的定义和判别
R∘RR 对MR2中1所在位置, MR中相位置都是1
如果顶点xi到 xj有边, xj到xk 有边,则从xi到 xk也有边
20
主对角主对角线元素线元素全是1 全是0
每个顶点都有环
每个顶点都没有环
注意：IA是对称关系也是反对称关系
4.3.1 关系性质的定义和判别
实例
例8 判断下图中关系的性质, 并说明理由
18
4.3.1 关系性质的定义和判别
传递性证明
证明模式证明 R 在 A上传递任取<x, y>，<y, z> <x, y>R<y, z>R …..………. <x, z>R 前提推理过程结论

《离散数学关系》课件

表示元素之间的顺序关系，如大小关系、前后关系等。
等价关系
表示元素之间具有相同性质的关系，等价关系具有自反性、对称性和传递性。
偏序关系
表示元素之间的部分顺序关系，偏序关系具有自反性、反对
称性和传递性。
02 关系的运算
关系的并
总结词
关系的并运算是将两个关系中的所有元素组合在一起形成一个新的关系。
性质
离散数学关系具有传递性、反对称性、自反性等性质。传递性是指如果关系R(x,y)和关系R(y,z)都成立，则关系 R(x,z)也成立；反对称性是指如果关系R(x,y)和关系R(y,x)同时成立，则x=y；自反性是指对于集合中的任意元素x ，都存在关系R(x,x)。
关系的表示方法
表格法
通过表格的形式表示关系，行表示关系的起点，列表示关系的终点，表格中的元素表示起点和终点之间是否存在关系。
05 关系的应用
关系在数据库中的应用
关系数据库
关系代数
数据库规范化
关系数据库是建立在关系模型基础上的数据库，使用二维表格来表示和存储数据。关系数据库中的表通过行和列来组织数据，每一列代表一个属性，每一行代表一个记录。关系数据库中的关系是指表格之间的关系，通过主键和外键来建立表格之间的联系。
基数性质
关系的基数具有一些性质，如非负性（基数总是大于或等于0）、传递性（如果关系R中存在元素a 和b，且a和b之间有关系，那么在关系S中a和b也一定有关系）等。
基数计算
计算关系的基数需要先确定关系中所有元素的数量，然后进行计数。例如，如果一个关系是由两个集合的笛卡尔积形成的，那么它的基数就是这两个集合的元素数量的乘积。
VS
推荐系统
推荐系统是根据用户的历史行为和偏好，为其推荐相关或感兴趣的物品或服务的过程。在推荐系统中，关系是指用户和物品之间的关系，通过分析用户和物品之间的关联规则和协同过滤等技术来实现个性化推荐。

离散数学4.3-4

10
结论
R是A上的关系，则：（1）R是自反关系的主要条件是IAA （2）R是反自反关系的主要条件是R∩IA=Ф。
11
(3) 若x y(x,y∈A ∧<x,y> ∈R <y,x> ∈R),则称R 在A上是对称的。也就是说, 对RAA, 对A中每个x和y, 若xRy, 则yRx, 称 R是对称的, 即
7
例子
例3：N上的互质关系是反自反关系。证明：x∈N，x与x是不互质的， ∴<x,x>R，∴R具有反自关系。其他的例实数上的＜，＞关系,人与人的父子关系,均是反自反关系。
8
关系矩阵的特点
自反关系的关系矩阵的对角元素均为1，反自反关系的关系矩阵的对角元素均为0。
9
关系图的特点
自反关系的关系图，每个结点均有自回路，而反自反关系的关系图的每个结点均没有自回路。
22
说明:
该定义的等价说法： a,b∈A,如a≠b,<a,b>∈R, 则必有<b,a>R。即两个不同点结点间不允许有两条弧。该定义的否命题说法并不成立,如 “a≠b,<a,b>R,则<b,a>∈R”并不成立, 即反对称关系的关系图允许两个不同点间没有弧。
23
有些关系既是对称的又是反对称的
设 R 是 A 上的关系，R 的性质主要有以下 5 种 (2) 若x(x ∈A <x,x> ∈R),则称 R 在 A 上是反自反的也就是说，对RAA，若A中每个x，有xRx，则称R是反自反的，即 A上关系R是反自反的x(xAxRx) 该定义表明了，一个反自反的关系R中，不应包括有任何相同元素的有序对。例如：设A={1,2,3}，R 是 A 上的关系， R={<2,3>,<3,2>} R是反自反的

离散数学第四章课件

无对称的偶对。
表示关系矩阵的主对角线两侧各有一个1且对称，即有一个对称的偶对。
C1
n(n＋1) 2
n(n＋1) C 2 n(n＋1) 2
表示关系矩阵的主对角线两侧全为1，
C1 ＋ n(n＋＋…＋ 2
n(n＋1) C 2 n(n＋1) 2
于是
C0 n(n＋1) 2 ＝
2
n(n＋1) 2
四、反对称性 ⒈ 定义：若xy(x∈A∧y∈A∧xRy∧yRx→x=y)，称R是反对称的。例：设A={ a , b , c , d } R={ < a , b > , < a , c > , < b , b > , <b,d>,<c,c>,<c,d>, < d , d >}
⒉自反关系的关系矩阵的特征
R的关系矩阵的主对角线上的元素均为
1 ，则该关系就不具有自反性；
主对角线上有一个元素不为1，则该关
系就不具有自反性。
⒊ 自反关系的图的特征自反关系的关系图中，每个顶点都有自回路，则该关系具有自反性。
二、反自反性 ⒈ 定义：若x（x∈A xRx）则该关系是反自反的。 ⒉ 具有反自反性的关系的关系矩阵的主对角
2 t1× t2 × … ×tn
五、关系的表示法-----通常有三种表示方法
⒈ 集合表示法：因为关系也是集合，所以也可以用集合的表示方法
例：A={ 2, 3,4,6 ,9,12 }上的整除关系
用特征描述法表示为
R＝{ < x , y > | x∈A ∧ y∈A ∧ x|y }
用穷举法表示为
R={ < 2 , 2 > , < 2 , 4 > , < 2 , 6 > ,

离散数学关系的概念性质及运算

当n=3时，25(mod 3)，57(mod 3)。
例3：设X是一个集合，集合的包含于“”是2X上的二元关系。
8/25
集合与图论二元关系到n元关系的推广
定义3 设A1,A2,...,An是n个集合，一个 A1A2...An的子集R称为A1,A2,...,An间的n元关系。
每个Ai称为R的一个域。
23/25
集合与图论关系幂运算的定义及性质
定理6 设X是一个有限集合且X=n，R为X上的任一二元关系，则存在非负整数s,t使得0≤s<t≤2n2且Rs=Rt。
定理7 设R是X上的二元关系。如果存在非负整数s,t，s<t，使得Rs=Rt，则
(1)Rs+k=Rt+k，k为非负整数； (2)Rs+kp+i=Rs+i，其中p=t-s，而k,i为非负整数； (3)令S={R0,R,R2,...,Rt-1}，则对任意的非负的整数 q有RqS。
例15：设R,S是集合X上的两个传递关系，问R∪S 是否是传递关系呢？
17/25
集合与图论
运算与性质的关系
自反性反自反性对称性反对称性传递性
R11
√
√
√
√
√
R1∩R2 √
√
R1∪R2 √
√
R1R2 ×
√
√
√
√
√ ××
√
√×
R1∘R2 √
×
×
××
18/25
集合与图论 3 关系的合成
定义1 设R是A到B的二元关系，S是B到C的二元关系。R与S的合成是A到C的一个二元关系，记成RS，并且
显然：R是传递的，当且仅当？。例11： Z上的模n同余关系是不是传递关系？

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

一般将 R 的自反闭包记作 r(R), 对称闭包记作 s(R), 传递闭包记作 t(R).
18
闭包的构造方法
定理1 设R为A上的关系, 则有 (1) r(R) = R∪R0 (2) s(R) = R∪R1 (3) t(R) = R∪R2∪R3∪… 说明： • 对于有穷集合A (|A|=n) 上的关系, (3)中的并是有限的. • 若 R是自反的，则 r(R)=R; 若R是对称的，则 s(R)=R; 若R是传递的，则 t(R)=R.
(1)不自反也不反自反；对称, 不反对称；不传递.
(2)反自反，不是自反的；反对称，不是对称的；是传递的. (3)自反，不反自反；反对称，不是对称；不传递.
10
自反性证明
证明模式证明R在A上自反任取x, xA ……………..….……. <x,x>R 前提推理过程结论例4 证明若 IA R ，则 R在A上自反. 证任取x, xA <x,x> IA <x,x>R 因此 R 在 A 上是自反的.
14
运算与性质的关系
自反性反自反性对称性反对称性传递性 R11 √ √ √ √ √
R1∩R2
R1∪R2 R1R2 R1∘R2
√ √ ×
√
√ √ √
×
√ √ √
×
√ × √
×
√ × ×
×
15
Microsoft Office PowerPoint，是微软公司的演示文稿软件。用户可以在投影仪或者计算机上进行演示，也可以将演示文稿打印出来，制作成胶片，以便应用到更广泛的领域中。利用Microsoft Office PowerPoint不仅可以创建演示文稿，还可以在互联网上召开面对面会议、远程会议或在网上给观众展示演示文稿。 Microsoft Office PowerPoint做出来的东西叫演示文稿，其格式后缀名为：ppt、pptx；或者也可以保存为： pdf、图片格式等
23
闭包的构造方法（续）
设关系R, r(R), r(R), s(R), t(R)的关系图分别记为G, Gr, Gs, Gt , 则Gr, Gs, Gt 的顶点集与G 的顶点集相等. 除了 G 的边以外, 以下述方法添加新边：
(1)考察G的每个顶点, 如果没有环就加上一个环，最终得到Gr . (2)考察G的每条边, 如果有一条 xi 到 xj 的单向边, i≠j, 则在G 中加一条 xj 到 xi 的反方向边，最终得到Gs. (3)考察G的每个顶点 xi, 找从 xi 出发的每一条长度不超过n的路径，如果从 xi 到路径中任何结点 xj 没有边，就加上这条边. 当检查完所有的顶点后就得到图Gt .
1 1 0 1
0 1 1 1 1 1 0 1
1 1 1 1
1 1 1 1
1 1 1 1
27
定理7.11 设R是非空集合A上的关系，则（1）R是自反的当且仅当r(R)＝R。（2）R是对称的当且仅当s(R)＝R。（3）R是传递的当且仅当t(R)＝R。
19
（3）t(R)＝R∪R2∪R3∪…
先证R∪R2∪… t(R)成立，为此只需证明对任意的正整数n有 Rn t(R)即可。用归纳法。 n＝1时，有 R1＝R t(R)。假设Rnt(R)成立，那么对任意的<x,y>有 <x,y>∈Rn+1＝Rn R t(<x,t>∈Rn∧<t,y>∈R) t(<x,t>∈t(R)∧<t,y>∈t(R)) <x,y>∈t(R) （因为t(R)是传递的）这就证明了Rn+1 t(R)。由归纳法命题得证。
R1＝{<1,1>,<2,2>}
R2＝{<1,1>,<2,2>,<3,3>,<1,2>}
R3＝{<1,3>} R2自反,
R3反自反,
R1既不是自反也不是反自反的
4
对称性与反对称性
实例：对称关系：A上的全域关系EA, 恒等关系IA和空关系反对称关系：恒等关系IA，空关系是A上的反对称关系.
6
传递性
实例： A上的全域关系EA,恒等关系IA和空关系小于等于关系, 小于关系，整除关系，包含关系，真包含关系
7
实例
例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上的传递关系
24
实例
例1 设A={a,b,c,d}, R={<a,b>,<b,a>,<b,c>,<c,d>, <d,b>}, R和 r(R), s(R), t(R)的关系图如下图所示.
R
r(R)
s(R)
t(R)
25
R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>}, r( R ) = R ∪ R 0 ={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>}∪{<a,a>,<b,b>,<c,c>,<d,d>} ={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>,<a,a>,<b,b>,<c,c>,<d,d>} s(R)= R∪R1 ={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>}∪{<b,a>,<a,b>,<c,b>,<d,c>, <b,d>} } ={<a,b>,<b,a>,<b,c>,<c,d>,<d,b> ,<c,b>,<d,c>,<b,d>} t(R) = R1∪R2∪R3∪R4 ={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>}∪{<a,a>,<a,c>,<b,b>,<b,d>, <c,b>,<d,a>,<d,c>}∪{<a,b>,<a,d>,<b,a>,<b,b>,<b,c>,<c,a>, <c,c>,<d,b>,<d,d>} ∪{<a,a>,<a,b>,<a,c,>,<b,a>,<b,b>,<b,c>, <b,d>,<c,b>,<c,d>,<d,a>,<d,b>,<d,c>} ={<a,a>,<a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c>,<b,d>,<c,a>, <c,b>,<c,c>,<c,d>,<d,a>,<d,b>,<d,c>,<d,d>}
1 0 0 1
0 1 0 0
0 1 0 0 1 0 0 1
0 1 1 0
1 0 0 1
0 0 1 1 0 1 0 0
1 1 0 1
0 1 1 0
1 1 1 0 0 0 1 1
1 1 1 1
R2不是A上的传递关系
8
关系性质的充要条件
设R为A上的关系, 则 (1) R在A上自反当且仅当 IA R (2) R在A上反自反当且仅当 R∩IA= (3) R在A上对称当且仅当 R=R1 (4) R在A上反对称当且仅当 R∩R1IA (5) R在A上传递当且仅当 RRR
9
实例
例.判断下图中关系的性质, 并说明理由.
21
推论设R为有穷集A上的关系，则存在正整数r 使得 t(R)=R∪R2∪…∪Rr
22
闭包的构造方法（续）
设关系R, r(R), s(R), t(R)的关系矩阵分别为M, Mr, Ms 和 Mt , 则

Mr = M + E
Ms = M + M’ Mt = M + M2 + M3 + …
E 是和 M 同阶的单位矩阵, M’是 M 的转置矩阵. 注意在上述等式中矩阵的元素相加时使用逻辑加.
11
对称性证明
证明模式证明R在A上对称任取<x, y> <x,y>R ……………..….……. <y,x>R 前提推理过程结论例5 证明若 R=R1 , 则R在A上对称. 证任取<x,y> <x,y>R <y,x>R 1 < y, x >R 因此 R 在 A 上是对称的.
4.3 关系的性质

自反性反自反性

对称性
反对称性传递性
1
定义
表达式
关系矩阵
自反
反自反
对称
反对称
传递
x∈A,有 x∈A,有 <x,x>R), <x,x>R,