离散数学 贾振华 第四章 关系

《离散数学 贾振华 第四章 关系》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章关系本章学习目标关系是离散数学中刻画元素之间相互联系的一个重要概念。它仍然是一个集合，以具有联系的对象组合作为其成员。在计算机科学与技术领域中有着广泛的应用，关系数据库模型就是以关系及其运算作为理论基础的。本章主要讨论二元关系的基本理论。通过本章学习，读者应该掌握以下内容：关系、关系的表示关系的性质和运算等价关系和集合的划分相容关系偏序关系学习内容4.1序偶与笛卡儿积4.2二元关系及其表示4.3关系的运算4.4关系的性质4.5关系的闭包4.6等价关系与集合的划分4.7相容关系4.8偏序关系4.

2、1序偶与笛卡儿积4.1.1有序n元组4.1.2笛卡儿积的概念4.1.3笛卡儿积的性质4.1序偶与笛卡儿积4.1.1有序n元组定义4.1.1由两个元素x和y按一定次序排列组成的二元组，称为一个有序对或序偶，记为，其中x，y分别称为序偶的第一、二分量（或称第一、二元素）。定义4.1.2两序偶，是相等的，当且仅当a=c，b=d；记作=。4.1序偶与笛卡儿积4.1.1有序n元组例4.1.1设有序对<2x+y，6>=，那么根据有序对相等的

3、充分条件有2x+y＝x-2y和6＝x+2y，因此得到x＝18，y＝－6。4.1序偶与笛卡儿积4.1.2笛卡儿积的概念定义4.1.3给定两个集合A和B，如果序偶的第一个分量是A中的一个元素，第二个分量是B中的一个元素，则所有这种序偶的集合，称为集合A和B的笛卡儿积，简称为卡氏积，记为A×B，即A×B={x∈A∧y∈B}。4.1序偶与笛卡儿积4.1.2笛卡儿积的概念例4.1.2（1）A={a，b}，B={c，d}，求A×B。（2）A={a，b}，B={c，d}，求B×A。（3）A={a，b}

4、，B={1，2}，C={c}，求（A×B）×C和A×（B×C）。4.1序偶与笛卡儿积4.1.2笛卡儿积的概念解（1）A×B={a，b}×{c，d}={，，，}。（2）B×A={c，d}×{a，b}={，，，}。（3）（A×B）={a，b}×{1，2}={，，，}。4.1序偶与笛卡儿积4.1.2笛卡儿积的概念（A×B）×C={<，c>，<，c>，<，c>

5、，<，c>}={，，，}。B×C={1，2}×{c}={<1，c>，<2，c>}。A×（B×C）={>，>，>，>}。4.1序偶与笛卡儿积4.1.2笛卡儿积的概念定义4.1.4设集合A1，A2，…，An，其中n∈N，且n>1，它们的n阶笛卡儿积记作A1×A2×…×An，定义为：A1×A2×…×An＝{x1∈A1∧x2∈A2∧…∧xn∈An}当A1

6、＝A2＝…＝An时，A1×A2×…×An简记为An。4.1序偶与笛卡儿积4.1.2笛卡儿积的概念例4.1.3设A＝{1，2}，B={a，b，c}，则（1）A2＝{<1，1>，<1，2>，<2，1>，<2，2>}（2）B2＝{，，，，，，，，}（3）R2＝{x∈R∧y∈R}，R2为笛卡儿平面，R3为笛卡儿空间。4.1序偶与笛卡儿积4.1.3笛卡儿积的性质定理4.1.1设A，B是任意有限集合，则有

7、A×

8、B

9、＝

10、A

11、·

12、B

13、定理4.1.2对任意有限集合A1，A2，…，An是有限集合，则有

14、A1×A2×…×An

15、＝

16、A1

17、·

18、A2

19、·…·

20、An

21、4.1序偶与笛卡儿积4.1.3笛卡儿积的性质定理4.1.3设A，B，C为任意集合，则有（1）A×（B∪C）=（A×B）∪（A×C）（2）A×（B∩C）=（A×B）∩（A×C）（3）（A∪B）×C=（A×C）∪（B×C）（4）（A∩B）×C=（A×C）∩（B×C）4.1序偶与笛卡儿积4.1.3笛卡儿积的性质定理4.3设A，B，C，D为任意非空集合，则A×BC×

22、D的充分必要条件是：AC且BD。定理4.1.4设A，B，C为任意集合，且C，则有AB（A×CB×C）（C×AC×B）4.1序偶与笛卡儿积4.1.3笛卡儿积的性质证明如果A×BC×D，对任意x∈A，y∈B有x∈A∧yB∈A×B∈C×Dx∈C∧y∈D即AC且BD。4.1序偶与笛卡儿积4.1.3笛卡儿积的性质反之，如果AC且BD，设任意x∈C和y∈B，有∈A×Bx∈A∧y∈Bx∈C∧y∈Dx∈C∧y∈D