- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
2),(2,3),(3,1),(3,2),(3,3)}
5.1.1 笛卡尔积
5.1 关 系
例5.2 设A=，B={1,2,3}，求AB ，BA。
解 AB=B=， BA=B=
及
其
表
示
5.1.1 笛卡尔积
5.1 关 系
定理5.1 设A,B为任意两个有限集， 则
|AB|=|A|•|B|
及 推论5.1 设A1,A2,…,An为任意n个有
关
记 作 ( a1,a2,…,an)。 其 中 ai（i=1,2,…,n
系
）叫做该有序n元组的第i个坐标。
及
有序n元组与前面所讲的n个元素的集
其
合这两个概念是两个不同的概念，不同在 于集合中这n个元素是无序的，而在有序n
表
元组中，必须对这n个元素指定一个次序
示
。因此对任意给定的n个个体，他们只能
组成一个n元素的集合，但却可以组成n!
其 表
(2)(A∪B)C=(AC)∪(BC) (3)A(B∩C)=(AB)∩(AC) (4)(A∩B)C=(AC)∩(BC)
示 (5)A(B-C)=(AB)-(AC)
(6)(A-B)C=(AC)-(BC)
5.1.1 笛卡尔积
5.1
例5.3 设A,B,C和D是任意的集合，试问 下列等式是否成立？wk.baidu.com什么？
关
(1)(A∩B)(C∩D)=(AC)∩(BD)
系
解 成立。因为对于任意的（x,y），设
及
(x,y)(A∩B)(C∩D)
其 xA∩ByC∩D
表 xAxByCyD
示 (x,y)A×C(x,y)B×D
(x,y)(AC)∩(BD)
5.1.1 笛卡尔积
5.1 (2)(A∪B)(C∪D)=(AC)∪(BD)
关 系 及
解 不成立。举一反例如下：设 A=D=，B=C={1}，则 (A∪B)(C∪D)=BC={(1,1)}， (AC)∪(BD)=∪=，显然等式
其 不成立。
表
示
5.1.2 关系的基本概念
定义5.4 设nI+，A1,A2,…,An为任意n个集
5.1
合，A1A2…An，则
关
(1)称为A1,A2,…,An间的n元关系；
5.1.2 关系的基本概念
5.1 关 系
例5.4 设A={1,2,4,7,8}， B={2,3,5,7}，定义由A到B的关系 ={(a,b)|(a+b)/5是整数}，求关系 。
及 解 根据的定义，中的序偶(a,b) 其 应满足如下三个条件：（1）aA；
表 （2）bB；（3）a+b能被5整除，于
示 是={(2,3),(7,3),(8,2),(8,7)}。
个不同的有序n元组。
5.1.1 笛卡尔积
5.1
另外，有序n元组的一种常见的特殊情 形是n=2。有序n元组（a,b）又被称为序
关
偶。序偶的一个熟悉的例子是平面上点的
系
笛卡尔坐标表示。例如，序偶（1,3），
及 其
（2,4），（5,3）等均表示平面上不同的 点。
表 示
定义5.2 设(a1,a2,…,an)和(b1,b2,…,bn) 两个有序n元组，如果ai=bi(i=1,2,…,n) ，则称这两个有序n元组相等，记为
系
(2)若n=2，则称为从A1到A2的二元关系； (3)若=，则称为空关系；
及
(4)若=A1A2…An，则称为普遍关系；
其 表
( 5 ) 若 A1=A2=…=An=A， 则 称 为 A 上 的 n 元 关 系； (6)若={(x,x)|xA}，则称为A上的恒等
示
关系。
若是由A到B的一个关系，且 (a,b)，则a对b有关系，记作ab。
例5.1 设A={a,b}，B={1,2,3}，求 AB，BA，AA，BB。
关解
系 AB={(a,1),(a,2),(a,3),(b,1),(b,
及 2),(b,3)}
其 表 示
BA={(1,a),(1,b),(2,a),(2,b),(3, a),(3,b)}
AA={(a,a),(a,b),(b,a),(b,b)} BB={(1,1),(1,2),(1,3),(2,1),(2,
第5
Relation
关系是在集合的基础上定义的
第
一个重要的概念，与集合的概念一样 ，关系的概念在计算机科学中也是最
5
基本的。它主要反映元素之间的联系
章 和性质，在计算机科学中有重要的意
义，如有限自动机和形式语言，编译
关 程序设计，信息检索，数据结构以及
系
算法分析和程序设计的描述中经常出 现。
内容提要：
(a1,a2,…,an)=(b1,b2,…,bn)。
5.1.1 笛卡尔积
5.1 定义5.3 设A1,A2,…,An是任意集
关 合，则称集合
系
{(a1,a2,…,an)|aiAi,i=1,2,…,
及 n}
其 为集合A1,A2,…,An的笛卡尔积，
表 记为A1A2…An。
示
5.1.1 笛卡尔积
5.1
5.1.2 关系的基本概念
5.1 关 系
例5.5 设A={2,3,4,5,9,25}，定义A 上的关系，对于任意的a,bA，当 且仅当(a-b)² A时，有ab，试问 由哪些序偶组成？
及 解 根据的定义，中的序偶(a,b) 其 应满足以下三个条件：（1）aA；
表 （2）bB；（3）(a-b)²A。因此
示 ={(2,4),(4,2),(2,5),(5,2),(3,5),
(5,3),(4,9),(9,4)}。
5.1.2 关系的基本概念
5.1 关 系 及
例5.6 设A={0,1,2}，求A上的普遍 关系UA和A上的恒等关系IA。
解 由普遍关系和恒等关系的定义知 UA=AA={(0,0),(0,1),(0,2),(1,0), (1,1),(1,2),(2,0),(2,1),(2,2)}，
其 限集，则
表
|A1A2…An|=|A1|•|A2|• … •|An|
示
5.1.1 笛卡尔积
定理5.2 设A,B,C,D为任意四个非空集合，则
5.1 (1)ABCD当且仅当AC,BD； 关 (2)AB=CD当且仅当A=C,B=D。
系 定理5.3 设A,B,C为任意三个集合，则
及 (1)A(B∪C)=(AB)∪(AC)
第
1.笛卡尔积及关系的概念
5
2.关系的性质
章
3.关系矩阵和关系图 4.复合关系与逆关系
关
5.关系的闭包 6.等价关系及证明
系
7.分划、覆盖、等价类、商集的概念
8.偏序与哈斯图
9.关系在计算机科学中的应用
5.1.1 笛卡尔积
5.1
定 义 5.1 由 n 个 具 有 给 定 次 序 的 个 体 a1,a2,…,an组成的序列，叫做有序n元组，
