离散数学(贾振华主编) 第四章 关系

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

1、第四章关系本章学习目标：在上一章讨论了集合及集合的运算，在这一章中我们将要研究集合内元素间的关系，这就是“关系”。关系是一个很重要的数学基本概念，它在计算机科学中的许多方面如数据结构、数据库、情报检索、算法分析等都有很多应用。本章主要讨论二元关系理论。通过本章学习，读者应该掌握以下内容：（1）关系的表示（2）关系的性质和运算（3）等价关系和集合的划分（4）偏序关系第四章关系4.1序偶与笛卡儿积4.2二元关系及其表示4.3关系的运算4.4关系的性质4.5关系的闭包4.6等价关系与集合的划分4.7相容关系4.8偏序关系第四章关系4.1序偶与

2、笛卡儿积4.1.1有序n元组定义4.1由两个固定次序的个体x，y组成的序列称为序偶，记为，其中x，y分别称为序偶的第一、二分量（或称第一、二元素）。定义4.2两序偶，是相等的，当且仅当a=c，b=d；记作=。第四章关系4.1序偶与笛卡儿积4.1.2笛卡儿积的概念定义4.3给定两个集合A和B，如果序偶的第一个分量是A中的一个元素，第二个分量是B中的一个元素，则所有这种序偶的集合称为集合A和B的笛卡儿积，简称为卡氏积，记为A×B，即A×B={x∈A∧y∈B}。第四章关系4.1序偶

3、与笛卡儿积4.1.2笛卡儿积的概念例4.1（1）A={a，b}，B={c，d}，求A×B。（2）A={a，b}，B={c，d}，求B×A。（3）A={a，b}，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、，2>}。第四章关系4.1序偶与笛卡儿积4.1.2笛卡儿积的概念（A×B）×C={<，c>，<，c>，<，c>，<，c>}={，，，}。B×C={1，2}×{c}={<1，c>，<2，c>}。A×（B×C）={>，>，>，>}。第四章关系4.1序偶与笛卡儿积4.1.3笛卡儿积的性质定理4.1设A，B，C为任意3个集合，则有（1）A×（B∪C）=（A×B）∪（A×C）（2）A×（B

5、∩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×D的充分必要条件是：AC且BD。定理4.2设A，B，C为任意3个集合，且C，则有AB（A×CB×C）（C×AC×B）第四章关系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

6、>∈C×D所以，A×BC×D。第四章关系4.2二元关系及其表示4.2.1二元关系的概念定义4.5设R是二元关系，由R的所有x组成的集合称为R的定义域，记作D（R），即D（R）={x׀y（yB∧R）}。由R的所有y组成的集合称为R的值域，记作R（R），即R（R）={y׀x（x∈A∧∈R）}。定义4.4设A，B是两个集合，R是笛卡儿积A×B的任一子集，则称R为从A到B的一个二元关系，简称关系。特别当A=B时，则称R为A上的二元关系（或A上的关系）。第四章关系4.2二元关系及其表示4.2.

7、1二元关系的概念例4.3设A={1，3，5，7}，R是A上的二元关系，当a，bA且aR，求R和它的定义域和值域。解R={<1，3>，<1，5>，<1，7>，<3，5>，<3，7>，<5，7>}D（R）={1，3，5}，R（R）={3，5，7}。例4.2设A={a，b，c，d，e}，B={1，2，3}，R={，，}，求R的定义域和值域。解D（R）={a，b，c}，R（R）={2，3}。第四章关系4.2二元关系及其表示4.2.1二元关系的概念定义4.6设IA为集合A上的二元关系，且满足IA

8、={xA}，则称IA为集合A上的恒等关系。第四章关系4.2二元关系及其表示4.2.2二元关系的表示1．关系矩阵表示法设给定集合A={a1，a2，…，an}，集合B={b1，b2，…，bm}，R