2021年2021年离散数学二元关系和函数知识点总结.doc

集合论部分
第四章、二元关系和函数
集合笛卡儿积和二元关系有序对
定义 由两个客体 x 和 y，根据一定次序组成
二元组称为有序对，记作<x,y>
实例：点直角坐标(3,-4)
有序对性质
有序性 <x,y>¹<y,x> （当x¹ y时）
<x,y> 和 <u,v> 相等充足必需条件是<x,y>=<u,v> Û x=u Ù y=v
例1 <2, x+5> = <3y- 4, y>，求 x, y.
解 3y- 4 = 2, x+5 = y Þ y = 2, x = - 3
定义 一个有序 n (n³3) 元组 <x1, x2, …, xn> 是一个
有序对，其中第一个元素是一个有序 n-1元组，即
<x1, x2, …, xn> = < <x1, x2, …, xn-1>, xn>
当 n=1时, <x> 形式上能够看成有序 1 元组.
实例 n 维向量是有序 n元组.
笛卡儿积及其性质
定义 设A,B为集合，A和B 笛卡儿积记作A´B， 即 A´B ={ <x,y> | xÎA Ù yÎB }
例2 A={1,2,3}, B={a,b,c}
A´B ={<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>}
A={Æ}, P(A)´A={<Æ,Æ>, <{Æ},Æ>}
性质：
不适合交换律 A´B¹B´A (A¹B, A¹Æ, B¹Æ)
不适合结合律 (A´B)´C¹A´(B´C) (A¹Æ, B¹Æ)
对于并或交运算满足分配律
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或B中有一个为空集，则A´B就是空集.
A´Æ=Æ´B=Æ
若|A|=m, |B|=n, 则 |A´B|=mn
证实 A´(BÈC)=(A´B)È(A´C)
证 任取<x,y>
<x,y>∈A×(B∪C)
 Û x∈A∧y∈B∪C
Û x∈A∧(y∈B∨y∈C)
 Û (x∈A∧y∈B)∨(x∈A∧y∈C)
 Û <x,y>∈A×B∨<x,y>∈A×C
 Û <x,y>∈(A×B)∪(A×C)
所以有A×(B∪C) = (A×B)∪(A×C).
例3 (1) 证实 A=B Ù C=D Þ A´C=B´D
(2) A´C=B´D是否推出 A=B Ù C=D ? 为何？
解 (1) 任取<x,y>
<x,y>ÎA´C Û xÎA Ù yÎC
Û xÎB Ù yÎD Û <x,y>ÎB´D
(2) 不一定. 反例以下：
A={1}，B={2}, C=D=Æ, 则 A´C=B´D 不过 A¹B.
二元关系定义
定义 设A,B为集合, A×B任何子集所定义二元
关系叫做从A到B二元关系, 当A=B时则叫做 A上
二元关系.
例4 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上二元关系.
计数
|A|=n, |A×A|=n2, A×A子集有 个. 所以 A上有
个不一样二元关系.
比如 |A|=3, 则 A上有=512个不一样二元关系.
设 A 为任意集合，
Æ是 A 上关系，称为空关系
EA, IA 分别称为全域关系和恒等关系，定义以下：
 EA={<x,y>|x∈A∧y∈A}=A×A
 IA={<x,x>|x∈A}
比如, A={1,2}, 则
 EA={<1,1>,<1,2>,<2,1>,<2,2>}

IA={<1,1>,<2,2>}
小于等于关系 LA, 整除关系DA, 包含关系