离散数学-二元关系与运算-专业数学教材
- 格式：ppt
- 大小：395.00 KB
- 文档页数：62
下载文档原格式
合集下载
《离散数学》课件-第四章 二元关系
则关系R的各次幂为： R0 =A ={<1,1> ， <2,2> ， <3,3> ， <4,4> ， <5,5>} R1=R
R2= R • R={<1,1>，<2,2>，<1,3>，<2,4>， <3,5>}
R3=R2 • R={<1,2>，<2,1>，<1,4>，<2,3>， <2,5>}
R4= R3 • R={<1,1>，<2,2>，<1,5>，<2,4>，
从关系图来看关系的n次幂
R：
1
2
3
4
5
R2：
1
2
3
4
5
R2就是从R的关系图中的任何一个结点x出发，长 为2的路径，如果路径的终点是y，则在R2 的关系 图中有一条从x到y的有向边。其他以次类推：
R3：
1
2
3
4
5
R4：
1
2
3
4
5
定理 设|A|=n，R A×A，则必有i，j∈N， 0≤i＜j≤2n2，使得Ri=Rj。
＝R5，R7＝R6•R＝R5，…，Rn＝R5 (n＞5) 故Rn{R0,R1,R2,R3,R4,R5}。
S0=IA,S1＝S,
S2＝S•S＝{<a,c>,<b,d>,<c,e>,<d,f>}， S3＝S•S•S＝S2•S＝{<a,d>,<b,e>,<c,f>}， S4＝S3•S＝{<a,e>,<b,f>}， S5＝S4•S＝{<a,f>}， S6＝S5•S＝Φ， S7＝Φ， …， 故，Sn{S0,S1,S2,S3,S4,S5,S6}
R2= R • R={<1,1>，<2,2>，<1,3>，<2,4>， <3,5>}
R3=R2 • R={<1,2>，<2,1>，<1,4>，<2,3>， <2,5>}
R4= R3 • R={<1,1>，<2,2>，<1,5>，<2,4>，
从关系图来看关系的n次幂
R：
1
2
3
4
5
R2：
1
2
3
4
5
R2就是从R的关系图中的任何一个结点x出发，长 为2的路径，如果路径的终点是y，则在R2 的关系 图中有一条从x到y的有向边。其他以次类推：
R3：
1
2
3
4
5
R4：
1
2
3
4
5
定理 设|A|=n，R A×A，则必有i，j∈N， 0≤i＜j≤2n2，使得Ri=Rj。
＝R5，R7＝R6•R＝R5，…，Rn＝R5 (n＞5) 故Rn{R0,R1,R2,R3,R4,R5}。
S0=IA,S1＝S,
S2＝S•S＝{<a,c>,<b,d>,<c,e>,<d,f>}， S3＝S•S•S＝S2•S＝{<a,d>,<b,e>,<c,f>}， S4＝S3•S＝{<a,e>,<b,f>}， S5＝S4•S＝{<a,f>}， S6＝S5•S＝Φ， S7＝Φ， …， 故，Sn{S0,S1,S2,S3,S4,S5,S6}
4-5 二元关系与函数 离散数学 教学课件
f ：R→Z, f (x)= x 满射, 但不单射, 例如 f (1.5)=f (1.2)=1.
f ：R→R, f (x)=2x+1 满射、单射、双射, 因为它是单调并且ranf =R.
f ：R+→R +, f (x)=x /(x2+1) 有极大值f (1)=1/2. 该函数既不单射也不满射.
当A1=A时，称f (A1)=f (A)=ran f 是函数的像。
注意：函数值 f(x)∈B, 而像 f [A1]B. 例：设f：{1,2,3}→{a,b}，
f={1,a,2,a,3,b}，A1={1,2}， 试求A1在f 下的像f (A1)和函数f 的像f (A)。 解：
f (A1)={f (x) |xA1} ={f (1), f (2)}
f (A)={f (x) |xA}
={f (1), f (2), f (3)}
={a}
={a,b}
函数的性质——满射
定义 设 f ：X→Y, （1）若ranf = Y, 则称 f ：X→Y是满射的.
X
Y
x1
y1
x2
x3
y2
满射(到上映射)
X
Y
x1
y1
x2
y2
x3
y3
到内法：直线方程
解1： 令 f：[0,1]→[1/4,1/2]
f (x)=-x/4+1/4
解2： 令 f ：[1, 0]→[1/4,1/2]
f (x)=-x/4+1/2=-(x-2)/4
构造从A到B的双射函数（续）
三、A 与自然数集合之间构造双射
方法：将A中元素排成有序图形，然后从第一个元素开始 按照次序与自然数对应
f(x)
f ：R→R, f (x)=2x+1 满射、单射、双射, 因为它是单调并且ranf =R.
f ：R+→R +, f (x)=x /(x2+1) 有极大值f (1)=1/2. 该函数既不单射也不满射.
当A1=A时，称f (A1)=f (A)=ran f 是函数的像。
注意：函数值 f(x)∈B, 而像 f [A1]B. 例：设f：{1,2,3}→{a,b}，
f={1,a,2,a,3,b}，A1={1,2}， 试求A1在f 下的像f (A1)和函数f 的像f (A)。 解：
f (A1)={f (x) |xA1} ={f (1), f (2)}
f (A)={f (x) |xA}
={f (1), f (2), f (3)}
={a}
={a,b}
函数的性质——满射
定义 设 f ：X→Y, （1）若ranf = Y, 则称 f ：X→Y是满射的.
X
Y
x1
y1
x2
x3
y2
满射(到上映射)
X
Y
x1
y1
x2
y2
x3
y3
到内法：直线方程
解1： 令 f：[0,1]→[1/4,1/2]
f (x)=-x/4+1/4
解2： 令 f ：[1, 0]→[1/4,1/2]
f (x)=-x/4+1/2=-(x-2)/4
构造从A到B的双射函数（续）
三、A 与自然数集合之间构造双射
方法：将A中元素排成有序图形，然后从第一个元素开始 按照次序与自然数对应
f(x)
mathchap44离散数学二元关系
基本的集合运算
庄伯金
bjzhuang@
16
关系的运算规律
定理1：设F是任意关系，则
(F-1)-1=F domF-1=ranF, ranF-1=domF
定理2：设F、G和H是任意的关系，则
(F∘G)∘H=F∘(G∘H) (F∘G)-1=G-1∘F-1
定理3：设R为A上的关系，则
庄伯金
bjzhuang@
9
常见关系
小于等于关系：
LA={<x,y>|x,y∈A∧x≤y}，其中A⊆R
整除关系：
DB={<x,y>|x,y∈B∧x整除y}，其中B⊆Z*
包含关系：
R⊆={<x,y>|x,y∈A∧x⊆y}，其中A为集合族
例：B={a,b}，A=P(B)，求R⊆。
庄伯金
bjzhuang@
8
二元关系的概念
有限集合上的关系总数也是有限的
|A|=m，|B|=n，则|A×B|=mn，所以，A到B上的关系共有2mn种。
A上的特殊关系
空关系：A×A的空集 全域关系：EA={<x,y>|x∈A∧y∈A}=A×A； 恒等关系：IA={<x,x>| x∈A}。
A×(B∪C)=(A×B)∪(A×C) (B∪C)×A=(B×A)∪(C×A) A×(B∩C)=(A×B)∩(A×C) (B∩C)×A=(B×A)∩(C×A)
子集的笛卡儿积仍为子集
A⊆C∧B⊆D⇒A×B⊆C×D
庄伯金
bjzhuang@
5
笛卡儿积
例：A={1,2}，求P(A)×A。
15
关系的运算
限制：设R为二元关系，A为集合，R在A上的限制记作 R↾A，其中R↾A={<x,y>|<x,y>∈R∧x∈A}。 R↾A的值域 称为A在R下的像，记作R[A]，其中R[A]=ran(R↾A)。
庄伯金
bjzhuang@
16
关系的运算规律
定理1：设F是任意关系，则
(F-1)-1=F domF-1=ranF, ranF-1=domF
定理2：设F、G和H是任意的关系，则
(F∘G)∘H=F∘(G∘H) (F∘G)-1=G-1∘F-1
定理3：设R为A上的关系，则
庄伯金
bjzhuang@
9
常见关系
小于等于关系：
LA={<x,y>|x,y∈A∧x≤y}，其中A⊆R
整除关系：
DB={<x,y>|x,y∈B∧x整除y}，其中B⊆Z*
包含关系：
R⊆={<x,y>|x,y∈A∧x⊆y}，其中A为集合族
例：B={a,b}，A=P(B)，求R⊆。
庄伯金
bjzhuang@
8
二元关系的概念
有限集合上的关系总数也是有限的
|A|=m，|B|=n，则|A×B|=mn，所以，A到B上的关系共有2mn种。
A上的特殊关系
空关系：A×A的空集 全域关系：EA={<x,y>|x∈A∧y∈A}=A×A； 恒等关系：IA={<x,x>| x∈A}。
A×(B∪C)=(A×B)∪(A×C) (B∪C)×A=(B×A)∪(C×A) A×(B∩C)=(A×B)∩(A×C) (B∩C)×A=(B×A)∩(C×A)
子集的笛卡儿积仍为子集
A⊆C∧B⊆D⇒A×B⊆C×D
庄伯金
bjzhuang@
5
笛卡儿积
例：A={1,2}，求P(A)×A。
15
关系的运算
限制：设R为二元关系，A为集合，R在A上的限制记作 R↾A，其中R↾A={<x,y>|<x,y>∈R∧x∈A}。 R↾A的值域 称为A在R下的像，记作R[A]，其中R[A]=ran(R↾A)。
离散数学ch2.二元关系(5、6、7节)
VS
详细描述
关系的对称差运算可以用符号表示为 R△S，其中 R 和 S 是两个关系。它包括 属于 R 但不属于 S，以及属于 S 但不属 于 R 的所有有序对。如果 (a, b) 在 R△S 中，那么 (a, b) 或者只属于 R，或者只属 于 S。
04
CATALOGUE
关系的闭包
闭包的定义
1 2
关系的交运算可以用符号表示为 R ∩ S，其中 R 和 S 是两个关系 。它包括同时属于 R 和 S 的所有 有序对。如果 (a, b) 在 R ∩ S 中 ，那么 (a, b) 同时是 R 和 S 的差是一种集合差集操作，它从第一个 关系中去除与第二个关系共有的元素。
中可以推导出的新事实。
数据完整性
03
在数据库设计中，闭包的概念用于确保数据的完整性和准确性
，防止出现冗余和不一致的情况。
05
CATALOGUE
关系的类型
函数关系
总结词
函数关系是一种特殊的二元关系，它满足每 个自变量都有唯一的因变量与之对应。
详细描述
在函数关系中，对于定义域中的每一个元素 ，在值域中都有唯一一个元素与之对应。这 种关系具有明确性、确定性和无重复性。常 见的函数关系有数学函数、映射函数等。
离散数学ch2.二元 关系(5、6、7节)
contents
目录
• 引言 • 二元关系的性质 • 关系的运算 • 关系的闭包 • 关系的类型 • 关系在数据库中的应用 • 关系在人工智能中的应用
01
CATALOGUE
引言
定义与概念
定义
二元关系是集合论中的一个基本概念 ，它描述了两个元素之间的联系。
在设计关系型数据库时，需要考虑数据结构、数据完整性、数据冗余和数 据安全性等方面。
离散数学 第七章 二元关系
举例
A表示某大学所有学生的集合，B表示大学开设的 表示某大学所有学生的集合， 表示大学开设的 表示某大学所有学生的集合 所有课程的集合， 所有课程的集合， 则A×B可以用来表示该校学生选课的所有可能情 × 可以用来表示该校学生选课的所有可能情 况。 是直角坐标系中x轴上的点集 令A是直角坐标系中 轴上的点集，B是直角坐标 是直角坐标系中 轴上的点集， 是直角坐标 系中y轴上的点集 轴上的点集， 系中 轴上的点集， 于是A× 就和平面点集一一对应 就和平面点集一一对应。 于是 ×B就和平面点集一一对应。
17
其它常用的关系
小于或等于关系： 小于或等于关系：LA={<x,y>|x,y∈A∧x≤y}，其中 A⊆R。 ∈ ∧ ， ⊆ 。 整除关系： 整除y}， 整除关系：DB={<x,y>|x,y∈B∧x整除 ，其中 B⊆Z* ∈ ∧ 整除 ⊆ Z*是非零整数集 包含关系： ⊆ 包含关系：R⊆＝{<x,y>|x,y∈A∧x⊆y}，其中 是集合族 ∈ ∧ ⊆ ，其中A是集合族
6
笛卡尔积举例
举例
设A={a,b}, B={0,1,2}，则 ， A×B={<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2>} × B×A={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>} ×
举例
设 A={ x | 0<x<2 } ,B={ y |0<y<1 },则 则 A × B={ <x,y>| 0<x<2且0<y<1 } 且 1 y
A表示某大学所有学生的集合，B表示大学开设的 表示某大学所有学生的集合， 表示大学开设的 表示某大学所有学生的集合 所有课程的集合， 所有课程的集合， 则A×B可以用来表示该校学生选课的所有可能情 × 可以用来表示该校学生选课的所有可能情 况。 是直角坐标系中x轴上的点集 令A是直角坐标系中 轴上的点集，B是直角坐标 是直角坐标系中 轴上的点集， 是直角坐标 系中y轴上的点集 轴上的点集， 系中 轴上的点集， 于是A× 就和平面点集一一对应 就和平面点集一一对应。 于是 ×B就和平面点集一一对应。
17
其它常用的关系
小于或等于关系： 小于或等于关系：LA={<x,y>|x,y∈A∧x≤y}，其中 A⊆R。 ∈ ∧ ， ⊆ 。 整除关系： 整除y}， 整除关系：DB={<x,y>|x,y∈B∧x整除 ，其中 B⊆Z* ∈ ∧ 整除 ⊆ Z*是非零整数集 包含关系： ⊆ 包含关系：R⊆＝{<x,y>|x,y∈A∧x⊆y}，其中 是集合族 ∈ ∧ ⊆ ，其中A是集合族
6
笛卡尔积举例
举例
设A={a,b}, B={0,1,2}，则 ， A×B={<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2>} × B×A={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>} ×
举例
设 A={ x | 0<x<2 } ,B={ y |0<y<1 },则 则 A × B={ <x,y>| 0<x<2且0<y<1 } 且 1 y
离散数学第四章 - 二元关系和函数-4
哈斯图：
a, b
a
b
7
例3、画出 (A), R 的哈斯图，其中A 分别为
(2) A a,b,c
解：P(A) ,a,b,c,a,b, a, c ,b, c ,a, b, c
8
例3、画出 (A), R
(2) A a,b,c
解：哈斯图：
的哈斯图，其中A 分别为
a, b, c
a, b
a,c b,c
上确界——最小的上界 下确界——最大的下界
不一定存在， 若存在必唯一
18
例5、A a,b, c，偏序集 (A), R ， a,b,c
求 B的最大、小元，极大、小元，
上、下界，上、下确界。
a, b
a,c b,c
(1) B a,c,b,c
a
b c
解：B 的最大元：无，最小元：无， 极大元：a,b,c ，极小元：a,c，
则称 y为B的下界。
15
二、偏序集中极小元，极大元，最小元，
最大元，上界，下界，上确界，下确界。 2、上、下界，上、下确界。
定义：设 A, 为偏序集，B A ，
(3) 令 C y y为B的上界，称 C 中最小元
为B 的上确界(最小上界)。（记为lub)
(4) 令D y y为B的下界，称 D 中最大元
2
定义2：设 A, 是一偏序集合， x, y A,若x y或y x，则称x与y是可比的。
例1、偏序集合的常见例子。 整数集上的小于等于关系
A 的幂集( A)上的包含关系
集合 A 上的恒等关系
正整数集上的整除关系
Q, R
( A), R
A, I A
Z , R整除
3
2、哈斯图 (Hasse) 。（偏序集合的简化的关系图）
离散数学第四章-二元关系和函数
注意：(1) 若 A 是 m元集，B是 n 元集， 则 A B为 mn 元集。
(2) 笛卡儿积是集合，有关集合的运算都适合。
(3) 一般，A B B A 。
5
3、笛卡儿积运算对 或 满足分配律
(1) A(B C) (A B) (AC) (2) (B C) A (B A) (C A) (3) A(B C) (A B) (AC) (4) (B C) A (B A) (C A)
解： (A) ,{a},{b}, A ，
R , , ,{a} , ,{b} ,
, A , {a},{a} , {a}, A ,
{b},{b} , {b}, A , A, A
14
4、A 上二元关系的表示法。
集合表示法 有三种 矩阵表示法
图形表示法
15
一般：设 A {x1, x2, , xn}
1、定义：
(1) 若集合R为空集或它的元素都是有序对， 则称 R 为二元关系。 若 x, y R ，则记作 xRy ，
否则，记作 xRy 。 (2) A B的任何一个子集都称作从A到B的一个二元关系。
特别地，当 A B 时，称作 A上的二元关系。
例、 A {a,b} ，B {0,1, 2}
设 R1 a, 0 , b, 0 , b, 2 R2 R3 A B
传递的。
26
例6、判断下图中的关系分别具有哪些性质。
解：R5 既不是自反也不是反自反的，
反对称的，传递的。
27
例6、判断下图中的关系分别具有哪些性质。
解：R6 是反自反的，既不是对称
又不是反对称，不是传递的。
28
例7：设 R1, R2 为 A上的对称关系， 证明R1 R2 也是 A上的对称关系。 证明：对任意 x, y
(2) 笛卡儿积是集合，有关集合的运算都适合。
(3) 一般，A B B A 。
5
3、笛卡儿积运算对 或 满足分配律
(1) A(B C) (A B) (AC) (2) (B C) A (B A) (C A) (3) A(B C) (A B) (AC) (4) (B C) A (B A) (C A)
解： (A) ,{a},{b}, A ，
R , , ,{a} , ,{b} ,
, A , {a},{a} , {a}, A ,
{b},{b} , {b}, A , A, A
14
4、A 上二元关系的表示法。
集合表示法 有三种 矩阵表示法
图形表示法
15
一般：设 A {x1, x2, , xn}
1、定义：
(1) 若集合R为空集或它的元素都是有序对， 则称 R 为二元关系。 若 x, y R ，则记作 xRy ，
否则，记作 xRy 。 (2) A B的任何一个子集都称作从A到B的一个二元关系。
特别地，当 A B 时，称作 A上的二元关系。
例、 A {a,b} ，B {0,1, 2}
设 R1 a, 0 , b, 0 , b, 2 R2 R3 A B
传递的。
26
例6、判断下图中的关系分别具有哪些性质。
解：R5 既不是自反也不是反自反的，
反对称的，传递的。
27
例6、判断下图中的关系分别具有哪些性质。
解：R6 是反自反的，既不是对称
又不是反对称，不是传递的。
28
例7：设 R1, R2 为 A上的对称关系， 证明R1 R2 也是 A上的对称关系。 证明：对任意 x, y
离散数学第四章 二元关系和函数
y, x
x, y R
LA 为 A 上小于等于关系， 例5、 A {2,3,6} ，
1 L 解： A 2, 2 , 3,3 , 3, 2 , 6, 2 , 6,3 , 6, 6
1 1 DA 为 A 上整除关系，分别求出 L 。 ， D A A
x, y
x, y A x y
第四章 二元关系和函数 第一节 二元关系及其运算 内容： 二元关系，关系图，关系矩阵，关系的运算 重点： (1)二元关系的定义及三种表示法，
(2) 一些特殊的二元关系。
（3）二元关系的逆、复合、幂运算
了解：关系的复合运算性质，矩阵法求幂运算
一、二元关系。 1、定义： (1) 若集合 R 为空集或它的元素都是有序对， 则称 R 为二元关系。 若 x, y R ，则记作 xRy ， 否则，记作 xRy 。 (2) A B的任何子集都称作从 A 到 B 的关系， 特别，当 A B 时，称作 A 上关系。
则 A A n2 ，
A A 的子集共有 2 个，
n2
n 元集 A 上不同的关系共有 2 个。
n2
3、特殊的关系。 空关系 ，全域关系 EA ，恒等关系 I A 。 对任意集合 A ， 空关系 ， 全域关系 E A x, y | x A y A A A， 恒等关系 I A x, x | x A 。
一般：设 A {x1 , x2 ,
, xn }
1 xi Rx j M R (rij )nn ，其中 rij 0 xi Rx j
点( n 个顶点)
关系图表示
边(每个有序对对应一条有向弧)
二、逆关系，复合关系。 1、关系的逆。 (1) 定义：关系 R 的逆关系定义为
离散数学第4章 集合与关系-二元关系 -4.1-4.2
证明：x,w(R∘S)∘T(z)(x,zR∘S∧z,wT)
(z)((y)(x,yR∧y,zS)∧z,wT)
(z)(y)((x,yR∧y,zS)∧z,wT)
(y)(z)(x,yR∧(y,zS∧z,wT))
(y)(x,yR∧(z)(y,zS∧z,wT))
(y)(x,yR∧y,wS∘T)x,wR∘(S∘T)
【例4.7】X=1,2,3,4,5，X上的二元关系R和S定义如下：
R=1,2,3,4,2,2
S=4,2,2,5,3,1,1,3
试求R∘S，S∘R，R∘(S∘R)，(R∘S)∘R，R∘R，S∘S，R∘R∘R
解：R∘S=1,5,3,2,2,5， S∘R=4,2,3,2,1,4
(R∘S)∘R=3,2，
R∘(S∘R)=3,2
都是用列举法表示的。 2.用描述法表示二元关系 设R是实数集，LR= x,y | xR∧yR∧x≤y， LR是
实数集R上的小于等于关系，是一个二元关系。
3.用矩阵表示二元关系 如果A，B是有限集，
A=a1, a2,„, am， B=b1, b2,„, bn，
R是A到B的二元关系，R的关系矩阵定义为： MR= rij mn
第4章 二元关系
4.2.2二元关系的复合运算（也叫合成运算）
定义4.2.2 （R与S的复合） 设X，Y，Z是集合，RX×Y，
SY×Z，则R与S的复合为：
R∘S = |<x, z> | y (<x,y>R<y,z>S) }
= x, zxX∧zZ∧(y)(yY∧x, yR∧y, zS)
[注]: R∘S 是从X到Z的二元关系，即R∘S X ×Z 。
<{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>} 类似的还可以定义A上的大于等于关系, 小于关系, 大于关 系, 真包含关系等等.
离散数学课件07二元关系
闭包的定义
对于给定的二元关系R，其闭包记作R+， 是指在R的基础上，通过自反、对称和传递 三种扩展运算后得到的最小关系集合。
闭包的具体计算方法
通过自反、对称和传递三种扩展运算，将 R中的元素进行逐一处理，最终得到R+。
对称扩展
将R中的每一对元素(a, b)和(b, a)添加到 R+中，如果它们不在R+中。
02
CHAPTER
二元关系的性质
自反性
总结词
自反性是指一个元素与自己有某种关系。
详细描述
在二元关系中，如果任意元素x都与自己有关系R，则称该关系为自反关系。例 如，在一个班级中，如果任意一个学生都是自己的朋友，则“朋友”关系是自 反的。
ห้องสมุดไป่ตู้ 对称性
总结词
对称性是指如果元素x和元素y有关系R，且元素y和元素x也有关 系R，则称该关系是对称的。
03
CHAPTER
二元关系的运算
并运算
总结词
并运算是一种二元关系的组合方式，表示两个关系中至少有一个对应的元素是相同的。
详细描述
在二元关系中，并运算是将两个关系组合在一起，形成一个新的关系。具体来说，如果存在一个元素在两个关系 中都出现，则新关系中该元素对应的值为1（表示存在），否则为0（表示不存在）。
自反扩展
将R中的所有空元素添加到R+中。
闭包的性质
闭包的自反性
对于任意关系R，其闭包R+总是包含自反关 系。
闭包的对称性
对于任意关系R，其闭包R+总是包含对称关 系。
闭包的传递性
对于任意关系R，其闭包R+总是包含传递关 系。
闭包的运算性质
1 2
离散数学(第二版)第4章二元关系和函数
第四章 二元关系和函数
定义4.2.3 设R是A到B的二元关系。 (1) 用xRy表示 <x，y>∈R，意为x，y有R关系(为使可读 性好，我们将分场合使用这两种表达方式中的某一种)。 xy 表示<x，y> R。 (2) 由<x,y>∈R的所有x组成的集合称为关系R的定义域 (domain),记作Dom R，即
显然A×B与 B×A所含元素的个数相同(A，B是有限集 合)，但A×B≠B×A。
定理4.1.1 若A，B是有穷集合，则有 |A×B|=|A|·|B|(·为数乘运算)
该定理由排列组合的知识不难证明。 定理4.1.2 对任意有限集合A1，A2，…，An，有 |A1×A2×…×An|＝|A1|·|A2|·… ·|An|(·为数乘运算)
第四章 二元关系和函数
本节主要介绍关系的基本概念以及关系的表示方法。 定义4.2.1 任何序偶的集合，确定了一个二元关系，并 称该集合为一个二元关系，记作R 。 二元关系也简称关系。 对于二元关系R，如果<x，y>∈R，也可记作xRy。 定义并不要求R中的元素<x，y> 中的x，y取自哪个个体 域。 因此，R={<2，a>，<u，狗>，<钱币，思想>}也是一 个二元关系。
若R={<x，y>|x∈A∧y∈B∧ x|y }，则称R为整除关系， 常记为|，其中x|y表示x整除y。
若A是任意集合，R是A上的二元关系，下面的关系也常 见：
若R={<x，y>|x∈P(A)∧y∈P(A)∧x y}，则称R为包含
若R={<x，y>|x∈P(A)∧y∈P(A)∧x y}，则称R为真包
第四章 二元关系和函数
离散数学(第13讲)二元关系
4 6 3
例:A＝{1,2,3,4,5,6}，D是整 :A＝{1,2,3,4,5,6}， 除关系，哈斯图为： 除关系，哈斯图为
则 若 B ＝{2,3,4,5} 3,4,5为 的极大元。 3,4,5为B的极大元。 2,3,5为 的极小元。 2,3,5为B的极小元。
5
2 1
12
A={1,2,3,4,5,6,8,12,15,24,30,60,120}， 例 A={1,2,3,4,5,6,8,12,15,24,30,60,120}， R)是一个偏序集 是一个偏序集。 R是整除关系。则(A, R)是一个偏序集。 是整除关系。 哈斯图为： 哈斯图为： ={2,4,6,12}， (1). B1={2,4,6,12}， 则12是B1最大元，也是极大元； 12是 最大元，也是极大元； 最小元，也是极小元。 2是B1最小元，也是极小元。 (2).B ={1,2,3,4,6,15}， (2).B2={1,2,3,4,6,15}， 最大元不存在，极大元是4 最大元不存在，极大元是4、6、15。 15。 最小元，也是极小元； 1是B2最小元，也是极小元；
5
画出下列偏序集的哈斯图。 例1 画出下列偏序集的哈斯图。 ({1,2,3,4,5,6})， 其中D 为整除关系。 (1). ({1,2,3,4,5,6})，DA)， 其中DA为整除关系。 (1)：显然： 解 (1)：显然： DA={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<1,2>, <1,3>,<1,4>,<1,5>,<1,6>,<2,4>,<2,6>,<3,6>} 先画出D 的关系图，然后按规则简化： 先画出DA 的关系图，然后按规则简化：
例:A＝{1,2,3,4,5,6}，D是整 :A＝{1,2,3,4,5,6}， 除关系，哈斯图为： 除关系，哈斯图为
则 若 B ＝{2,3,4,5} 3,4,5为 的极大元。 3,4,5为B的极大元。 2,3,5为 的极小元。 2,3,5为B的极小元。
5
2 1
12
A={1,2,3,4,5,6,8,12,15,24,30,60,120}， 例 A={1,2,3,4,5,6,8,12,15,24,30,60,120}， R)是一个偏序集 是一个偏序集。 R是整除关系。则(A, R)是一个偏序集。 是整除关系。 哈斯图为： 哈斯图为： ={2,4,6,12}， (1). B1={2,4,6,12}， 则12是B1最大元，也是极大元； 12是 最大元，也是极大元； 最小元，也是极小元。 2是B1最小元，也是极小元。 (2).B ={1,2,3,4,6,15}， (2).B2={1,2,3,4,6,15}， 最大元不存在，极大元是4 最大元不存在，极大元是4、6、15。 15。 最小元，也是极小元； 1是B2最小元，也是极小元；
5
画出下列偏序集的哈斯图。 例1 画出下列偏序集的哈斯图。 ({1,2,3,4,5,6})， 其中D 为整除关系。 (1). ({1,2,3,4,5,6})，DA)， 其中DA为整除关系。 (1)：显然： 解 (1)：显然： DA={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<1,2>, <1,3>,<1,4>,<1,5>,<1,6>,<2,4>,<2,6>,<3,6>} 先画出D 的关系图，然后按规则简化： 先画出DA 的关系图，然后按规则简化：
离散数学第四章二元关系和函数
rn2 ... rnn
ri,j =是关系矩阵
第十三页，共66页
例题
• 设A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>} 的关系图和关系矩阵为:
1 100 0 01 1 0 00 0
01 00
第十四页，共66页
关系图
• 设V是顶点的集合,E是有向边的集合,令V={x1, x2,..., xn},如果xiRxj, 则有< xi,xj >E,那么 G=<V,E>就是R的关系图.
• 判断下列命题的真假
• 若AC且BD,则有AxBCxD;(真) • 若AxBCxD,则有AC且BD.(假)
第八页，共66页
n阶笛卡儿积
• 定义4.4 设A1, A2,…, An,是集合(n2),它们的n阶 笛卡儿积记作A1x A2x… xAn,其中 A1x A2x… xAn＝{<x1, x2,…, xn>| x1 A1, x2 A2,..., xn An }
• 例如平面直角的坐标:<1,-1>,<2,0>,<1,1>,他的特性是 : 当x≠y时,<x,y>≠<y,x> <x,y>=<u,v>等充分必要条件是x=u,y=v.
• 序偶与集合的关系, <x,y>≠<y,x>,但{x,y}={y,x}
第三页，共66页
有序n元组
• 定义4.2 :一个有序n元组(3≤n)是一个有序对,其中 第一个元素是一个有序n-1元组，一个有序n元组 记作＜x1, x2,…, xn,>,即 ＜x1, x2,…, xn,>=<< x1, x2,…, xn-1,>, xn >
离散数学二元关系与函数2
性
有极小值f(1)=2. 该函数既不单射也不满射.
质
构造从A到B的双射函数
有穷集之间的构造
例5 A=P({1,2,3}), B={0,1}{1,2,3}
4.6 函 数
解 A={,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}. B={ f0, f1, … , f7 }, 其中
定 (3) f：R→Z, f(x) = x
义 (4) f：R→R, f(x) = 2x+1
与 性
(5) f：R+→R+, f(x)=(x2+1)/x, 其中R+为正实数集.
质
实例〔续〕
解 (1) f：R→R, f(x)=x2+2x1
在x=1取得极大值0. 既不单射也不满射.
4.6 (2) f：Z+→R, f(x)=lnx
数
B=[1/4,1/2]
的 定
构造双射 f :A→B
义
与
性解
质 令 f：[0,1]→[1/4,1/2]
f(x)=(x+1)/4
构造从A到B的双射函数〔续〕
A 与自然数集合之间构造双射
4.6 方法：将A中元素排成有序图形，然后从第一个元素开始
函
按照次序与自然数对应
数 例7 A=Z, B=N，构造双射 f：A→B
的
f2={<1,a>,<2,b>,<3,a>}，
定 义 与
f3={<1,a>,<2,b>,<3,b>} f4={<1,b>,<2,a>,<3,a>}，
性 f5={<1,b>,<2,a>,<3,b>}
《离散数学》 二元关系
数据结构、情报检索、数据库、算法分析、计算机理论等计算机学科很好的数
学工具。
3
第 4章 二元关系
1
历史人物
学习要求
内容导航
CONTENTS
4.1
二元关系及其表示
4.2
关系的运算
4.3
关系的性质
4.4
关系的闭包
4.5
关系的应用
4.6
作业
4
历史人物
第 4章 二元关系
5
1868-1942，德国数学家，
20
定义4.5 设A,B为两个非空集合，称A×B的任何子集R为从A到B的二元关系，简称
关系(Relation)，记作R：A→B；
如A＝B，则称R为A上的二元关系，记作R：A→A。
若<x,y>∈R，则记为xRy，读作“x对y有关系R”；
若<x,y>R，则记为xRy，读作“x对y没有关系R”。
解题小贴士—给定集合是否为从A到B的一个关系的判断方法
所以
（1）S1不是A×B的子集，从而S1不是A到B上的一个关系。
（2）S2是A×B的子集，从而S2是A到B上的一个二元关系。
第 4章 二元关系
4.1.2 关系的定义
例4.4 设A = {1,2}，试判断下列集合是否为A上的关系。
（1）T1＝ Φ ；
是，空关系
（2）T2＝A×A；
是，全关系
（3）T3＝{<1，1>，<2，2>}；
（2）序偶中的两个元素具有确定的次序。即<a,b>≠<b,a>，但{a,b}={b,a}。
定义4.2 给定序偶<a,b>和<c,d>，
离离散数学 第7章 二元关系
关于AC∧BD A×BC×D的讨论
该性质的逆命题不成立，可分以下情况讨论。 （1）当A=B=时，显然有AC 和 BD 成立。 （2）当A≠且B≠时，也有AC和BD成立，证明如下：
任取x∈A，由于B≠,必存在y∈B,因此有 x∈A∧y∈B
<x,y>∈A×B <x,y>∈C×D x∈C∧y∈D x∈C 从而证明了 AC。 同理可证 BD。
<x,y>AC xAyC xByD <x,y>BD （2) 不一定.反例如下：
A={1}，B={2}, C = D = , 则 AC = BD 但是 A B.
第二节 二元关系
一、二元关系的定义 1．定义 7.3 如果一个集合满足以下条件之一： （1）集合非空, 且它的元素都是有序对 （2）集合是空集 则称该集合为一个二元关系, 简称为关系，记作 R. 如果<x,y>∈R, 可记作 xRy；如果<x,y>R, 则记作 x y 2．实例：R={<1,2>,<a,b>}, S={<1,2>,a,b}. R 是二元关系, 当 a,b 不是有序对时，S 不是二元关系 根据上面的记法，可以写 1R2, aRb, a c 等.
关于AC∧BD A×BC×D的讨论
该性质的逆命题不成立，可分以下情况讨论。 （3）当A＝而B≠时，有AC成立，但不一定有
BD成立。 反例：令A＝,B＝{1},C＝{3},D＝{4}。
（4）当A≠而B＝时，有BD成立，但不一定有 AC成立。 反例略。
例 设 A={1,2},求 P(A)×A。 解 P(A)×A ={ ,{1},{2},{1,2}}×{1,2}
4．关系的表示 表示一个关系的方式有三种：关系的集合表达式、关系矩阵、关系图. 关系矩阵和关系图的定义 关系矩阵 若 A={x1, x2, …, xm}，B={y1, y2, …, yn}，R 是从 A 到 B 的关系， R 的关系矩阵是布尔矩阵 MR = [ rij ] mn, 其中 rij = 1 < xi, yj> R. 关系图 若 A= {x1, x2, …, xm}，R 是从 A 上的关系， R 的关系图是 GR=<A, R>,其中 A 为结点集，R 为边集. 如果<xi,xj>属于关系 R，在图中就有一条从 xi 到 xj 的有向边. 注意： 关系矩阵适合表示从 A 到 B 的关系或者 A 上的关系（A,B 为有穷集） 关系图适合表示有穷集 A 上的关系
(完整版)离散数学二元关系
6
二、从A到B的关系与A上的关系 定义7.4 设A,B 为集合,A×B 的任何子集所定义的二 元关系叫做从A 到B 的二元关系,当A=B 时则叫做A 上 的二元关系. 例 A={0,1}, B={1,2,3}, 那么R1={<0,2>}, R2=A×B, R3=∅, R4={<0,1>} R1, R2, R3, R4 是从A 到B 的二元关系, R3和R4同时 也是A 上的二元关系.
{<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>
,<3,c>} B×A =
{<a,1>,<b,1>,<c,1>,<a,2>,<b,2>,<c,2>,<a,3>,<b,3>
,<c,3>}
2
注:笛卡儿积的性质 （1）不适合交换律 A×B ≠ B×A (A≠B, A≠∅, B≠∅) （2）不适合结合律 (A×B)×C ≠ A×(B×C) (A≠∅, B≠∅, C≠∅) （3）对于并或交运算满足分配律 A×(B∪C) = (A×B)∪(A×C) (B∪C)×A = (B×A)∪(C×A) A×(B∩C) = (A×B)∩(A×C) (B∩C)×A = (B×A)∩(C×A) （4）若A 或B 中有一个为空集，则A×B 就是空集. A×∅ = ∅×B = ∅ （5）若 |A| = m, |B| = n, 则 |A×B| = mn
这些性质是二元集{x,y}所不具备的.例如当x≠y 时 有{x,y}={y,x}.
1
二、笛卡儿积 定义7.2 设A,B 为集合，用A中元素为第一元素,B中 的元素为第二元素构成有序对.所有这样的有序对组 成的集合叫做A 与B 的笛卡儿积,记作A×B. 笛卡儿积的符号化表示为
二、从A到B的关系与A上的关系 定义7.4 设A,B 为集合,A×B 的任何子集所定义的二 元关系叫做从A 到B 的二元关系,当A=B 时则叫做A 上 的二元关系. 例 A={0,1}, B={1,2,3}, 那么R1={<0,2>}, R2=A×B, R3=∅, R4={<0,1>} R1, R2, R3, R4 是从A 到B 的二元关系, R3和R4同时 也是A 上的二元关系.
{<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>
,<3,c>} B×A =
{<a,1>,<b,1>,<c,1>,<a,2>,<b,2>,<c,2>,<a,3>,<b,3>
,<c,3>}
2
注:笛卡儿积的性质 （1）不适合交换律 A×B ≠ B×A (A≠B, A≠∅, B≠∅) （2）不适合结合律 (A×B)×C ≠ A×(B×C) (A≠∅, B≠∅, C≠∅) （3）对于并或交运算满足分配律 A×(B∪C) = (A×B)∪(A×C) (B∪C)×A = (B×A)∪(C×A) A×(B∩C) = (A×B)∩(A×C) (B∩C)×A = (B×A)∩(C×A) （4）若A 或B 中有一个为空集，则A×B 就是空集. A×∅ = ∅×B = ∅ （5）若 |A| = m, |B| = n, 则 |A×B| = mn
这些性质是二元集{x,y}所不具备的.例如当x≠y 时 有{x,y}={y,x}.
1
二、笛卡儿积 定义7.2 设A,B 为集合，用A中元素为第一元素,B中 的元素为第二元素构成有序对.所有这样的有序对组 成的集合叫做A 与B 的笛卡儿积,记作A×B. 笛卡儿积的符号化表示为
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
公司的演示文稿软件。用户可以在投影仪或
者计算机上进行演示，也可以将演示文稿打
印出来，制作成胶片，以便应用到更广泛的
领域中。利用Microsoft Office PowerPoint不
仅可以创建演示文稿，还可以在互联网上召
开面对面会议、远程会议或在网上给观众展
示演示文稿。
Microsoft Office
PowerPoint做出来的东西叫演示文稿，其格
式后缀名为：ppt、pptx；或者也可以保存为：pdf、图片格式等202 Nhomakorabea/4/4
16
卡盟排行榜 卡盟
例4.4 设A={1,2,3,4}， R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}是A上的 关系，试写出R的关系矩阵并画出关系图：
2021/4/4
8
证明： 用第一种方法
对于任意的<x,y> A ( B∪C ) xAy(B∪C)
xA(yByC )
(xAyB)(xAyC)
<x, y>AB<x, y>AC <x, y>(AB)∪(AC) A(B∪C)=(AB)∪(AC)
2021/4/4
9
例4.2 设A={1,2}，求P(A)A
2021/4/4
6
(4) A(B∪C) = (AB)∪(AC) (对∪的分配律)
(B∪C)A = (BA)∪(CA)
(?)
A(B∩C) = (AB)∩(AC)
(?)
(B∩C)A = (BA)∩(C A)
(?)
我们证明：
A(B∪C) = (AB)∪(AC)
2021/4/4
7
证明思想
要证明两个集合相等，通常有两种方法：
记作：A B 符号化：A B = {<x,y> | xA y B}
2021/4/4
4
例4.1 设A={a,b}，B={0,1,2} ，求AB，BA 解：根据笛卡儿积的定义知
A B = {<a,0>, <a,1>, <a,2>, <b,0>, <b,1>, <b,2> }
B A = {<0, a>, <0, b>, <1,a>, <1,b>, <2,a>, <2,b>} 一般地：如果|A|=m，|B|=n，则 |AB|=|BA|=m n
10
3、二元关系的数学定义
二元关系：如果一个集合的元素都是二元有 序组，则这个集合称为一个二元 关系，记作：R 。
如果<x, y> R ，记作 x R y
如果<x, y> R ，记作 x R y
2021/4/4
11
从A到B的二元关系：设A，B为集合，A B的任 何子集所定义的二元关系叫做从 A到B的二元关系。
2021/4/4
1
§4.1 二元关系的概念
一、二元关系的概念
1. 二元有序组：由两个元素x和y按一定顺序 排成二元组，记作：<x，y> 。
如： 平面直角坐标系中点的坐标
2021/4/4
2
二元有序组的性质 (1) 当x y时，<x，y> <y，x> (2) <x，y> = <u，v>，当且仅当x = u，y = v
若A=B，叫做 A上的二元关系； 若|A|＝n，则|AA|＝n2。
2021/4/4
AA的所有子集有2 n 2 个。
就是说，A上有2 n 2个不同的二元 关系，其中包括空关系、全域 关系UA和恒等关系IA。
12
例4.3 设A = {a,b}，写出P(A)上的包含关系R ：
解： P(A) = {,{a},{b}{a,b}} R = {<, >, < ,{a}>, <{,{b}>,<{a, b}>, <{a},{a}>,<{a},{a, b}>, <{b},{b}>, <{b},{a, b}>, <{a, b},{a, b}>}
解： P(A)A
= {，{1}，{2}，{1,2}} {1,2}
= {<,1>，<,2>，<{1},1>，<{1},2>，
<{2},1>，<{2},2>， <{1,2},1>，<{1,2},2>}
n阶笛卡儿积：
A1 A2 …An
= {(x1,x2,… xn) | x1A1x2A2 …xnAn}
2021/4/4
(1)、(2)说明有序组区别于集合
n元有序组：由n个元素x1，x2，…，xn， 按一定顺序排成的n元组，记 作：(x1，x2，…，xn) 。
2021/4/4
3
2. 一种新的集合运算 ––– 积运算 ： 设A、B为两集合，用A中元素为第一
元素，B中元素作为第二元素构成的二元有 序组的全体叫做A和B的笛卡儿积。
一是证两个集合相互包含； 二是利用已有的
集合运算的性质(算律和已证明过的公式)，仿
照代数恒等式的证明方法，一步步从左(右)边
推出右(左)边，或从左、右边分别推出同一个
集合式子。一般说来，最基本的集合相等关
系要用第一种证法，比较复杂的集合相等关
系用第二种方法更好，但第二种方法的使用
取决于我们对算律和常用公式的熟练程度。
解： 关系矩阵 ：
2021/4/4
1100 0011 0000 0100
关系图 ：
1
2
4
3
17
§4.2 关系的运算
一、关系的定义域与值域
关系R的定义域： domR = {x | (y)<x, y>R} (即R中有序组的第一个元 素构成的集合)
是R的关系矩阵
2021/4/4
rn1
rn 2
rnn
14
2. 关系图：
以V=A={x1, x2,…, xn} 为顶点集， 以E = {<xi, xj> | xiAxjAxiRxj}为有向 边集组成的有向图G = <V, E>
2021/4/4
15
Microsoft Office PowerPoint，是微软
2021/4/4
13
二、二元关系的表示方法
A上关系的表示法
1. 关系矩阵： 设A={x1, x2, …, xn)，R是A上的关系， 令：
1 rij =
0
若xi R xj 若xi R xj
(i, j = 1,2,…, n)
r11 r12 r1n
则 (rij)nxn = r21
r22
r2 n
2021/4/4
5
积运算的性质
(1) 若A，B中有一个空集，则笛卡儿积是空集， 即： B = A =
(2) 当AB，且A，B都不是空集时，有ABBA
(3) 当A，B，C都不是空集时，有(AB)C A(BC)
因为(AB)C中的元素< <x,y>, z>，而A(BC)中 的元素为< x, <y, z> > 。