资源描述：
《离散数学基础(洪帆)第二章关系.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章关系本章主要内容：有序n元组（序偶）和笛卡儿积、关系的概念；关系的表示方法；关系的复合运算、关系的性质；等价关系、偏序。2.1笛卡儿积1.定义由n个具有给定次序的个体a1,a2,…,an组成的序列，称为有序n元组，记作(a1,a2,…,an)。注：有序n元组不是由n个元素组成的集合。因为前者明确了元素的排列次序，而集合没有这个要求。例如:(a,b,c)≠(b,a,c)≠(c,a,b)，但{a,b,c}={b,a,c}={c,a,b}。一、有序n元组定义假设(a1,a2,…,an)和(b1,b2,…,
2、bn)是两个有序n元组,则(a1,a2,…,an)=(b1,b2,…,bn)成立,当且仅当a1=b1,a2=b2,…,an=bn。3.序偶当n=2时，有序二元组(a,b)称为序偶。2.两有序n元组相等1.定义设A1,A2,…,An是任意集合,所有的有序n元组(a1,a2,…,an)的集合称为A1,A2,…,An的笛卡儿积,用A1×A2×…×An表示，其中a1∈A1,a2∈A2,…,an∈An,即：A1×A2×…×An={(a1,a2,…,an)
3、ai∈Ai,i=1,2,…,n}二、笛卡尔积2.集合A与集合
4、B的笛卡尔积A×B={(a,b)
5、a∈A,b∈B}则A1×A2×…×An可表示为注：若所有Ai都相同，例1设A={1,3},B={1,2,4}，求：A×B，B×A解：A×B={(1,1),(1,2),(1,4),(3,1),(3,2),(3,4)}B×A={(1,1),(1,3),(2,1),(2,3),(4,1),(4,3)}显然A×B≠B×A,即笛卡儿积不满足交换律。例2设A={0,1},B={2,3},C={3,4}则：A×B×C={(0,2,3),(0,2,4),(0,3,3),(0,3,4)(1
6、,2,3),(1,2,4),(1,3,3),(1,3,4)}(A×B)×C={((0,2),3),((0,2),4),((0,3),3),((0,3),4),((1,2),3),((1,2),4),((1,3),3),((1,3),4)}A×(B×C)={(0,(2,3)),(0,(2,4)),(0,(3,3)),(0,(3,4)),(1,(2,3)),(1,(2,4)),(1,(3,3)),(1,(3,4))}.(A×B)×C≠A×(B×C)，因此笛卡儿积不满足结合律。2.2关系1.定义笛卡儿积A1×A
7、2×…×An的任意一个子集称为A1,A2,…,An上的一个n元关系。注:当n=2时,A×B的任一子集称为由A到B的一个二元关系。一、关系的定义注：1)空集是任何集合的子集,称为空关系。2)若集合A、B的元素分别是n、m则A到B的关系共有注：若是A到B的一个关系，如果(a,b)∈,则称a与b有关系,记作ab,如果(a,b),则称a与b没有关系，记作ab。集合称为关系的值域，记作2.关系的定义域和值域定义设是由A到B的一个关系，则使得ab(b∈B)成立的所有元素a∈A的集合称为关系的定义域，记作则使得ab(a
8、∈A)成立的所有元素b∈B的例1设集合A={1,2,4,7,8},B={2,3,5,7},定义由A到B的关系:={(a,b)
9、(a+b)/5是整数}试问由哪些序偶组成？并求此关系的定义域和值域。1）定义由集合A到A自身的关系称为集合A上的关系。3.A上的关系例2设A={2,3,4,5,9,25},定义A上的关系R,对于任意的a,b∈A,当且仅当(a-b)2∈A时,有aRb,试问R由哪些序偶构成？并求关系R的定义域和值域。a)普遍关系若关系R=A2,则称R为A上的普遍关系,记作UA,即UA={(ai,ak)
10、
11、ai,ak∈A}。2）A上的普遍关系与恒等式关系b)恒等关系A上的恒等关系用IA表示，定义为:IA={(ai,ai)
12、ai∈A}令有向图G=(V,E),其中顶点集V=A,边集E按如下规定:有向边二、关系的表示方法1.列举法2.描述法3.关系图定义设A={a1,a2,…,an},是A上的关系,的关系图。则称有向图G为关系例3设集合A={1,2,3,4},R={(1,1),(1,2),(1,3),(1,4),(2,3)}S={(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)}都是A上的
13、二元关系。画出关系R与S的关系图。13243124图(1)图(2)R和S的关系图分别如下图(1)和图(2)所示：且关系矩阵的第i行、第j列的元素4.关系矩阵定义设集合A={a1,a2,…,an},B={b1,b2,…,bm}是由A到B的关系,则的关系矩阵记为定义如下：定义为一个n行、m列的矩阵，例4设集合A=2{0,1},B=2{0,1,2}-2{0},={(a,b)
14、a-b=}是一个由A到B的关系,试列出关系的定义域和值域，
