第4章关系 4.1集合的笛卡儿积 4.2二元关系的概念及其特性 4.3二元关系的运算 4.4关系的闭包运算 4.5等价关系与集合的划分 4.6偏序关系
第4章 关系 4.1 集合的笛卡儿积 4.2 二元关系的概念及其特性 4.3 二元关系的运算 4.4 关系的闭包运算 4.5 等价关系与集合的划分 4.6 偏序关系
第4章关系 关系是离散数学中刻画元素之间相互联 系的一个重要的概念,在计算机科学与技 术鈑域中有着鐸的宓用关系数据库模 在诸多的关系中,最基本的涉及两个事 物之间的关系,即二元关系本章主要讨论 元关系,先给出二元关系的定义和特性 后给出義奎要的完关系的团馨桥吴系 和偏序关系
第4章 关系 关系是离散数学中刻画元素之间相互联 系的一个重要的概念，在计算机科学与技 术领域中有着广泛的应用，关系数据库模 型就是以关系及其运算作为理论基础的. 在诸多的关系中，最基本的涉及两个事 物之间的关系，即二元关系.本章主要讨论 二元关系，先给出二元关系的定义和特性， 然后讨论关系的运算及关系的闭包运算， 最后给出最重要的二元关系——等价关系 和偏序关系
4.1集合的笛卡儿积 4.1.1有序对的概念 41.2笛卡儿积
4.1 集合的笛卡儿积 4.1.1 有序对的概念 4.1.2 笛卡儿积
4.1.1有序对的概念 给定一个集合,其成员之间往往存在某种关系例如, 某,家庭集合:{父 ,媳,孙}这种成员的关系可 以有多种,夫妻、上下辈份等对于不同的两个集合,其 成员之间也可能存在某种关系例如,这个家庭集合中的成 个家庭集合中的某成员是兄弟关系,两家的儿媳 妇为姊妹关系等 总之,可以将事物之间的结构联系抽象概括为集合中 元素之间的关系例如A=abc表示男教师,B=XM2表 示女教师集合如果A、B的元素之间有夫妻关系,是a和y, C和z,那么 (1)a和y是成对出现,c和z是成对出现 2)根据谓词概念,这对元素具有一定顺序 (3)应该给出特定的表示方法表达这种关系
4.1.1 有序对的概念 给定一个集合，其成员之间往往存在某种关系.例如， 某一家庭集合：{父，母，儿，媳，孙}这种成员的关系可 以有多种，夫妻、上下辈份等.对于不同的两个集合，其 成员之间也可能存在某种关系.例如,这个家庭集合中的成 员与另一个家庭集合中的某成员是兄弟关系，两家的儿媳 妇为姊妹关系等. 总之，可以将事物之间的结构联系抽象概括为集合中 元素之间的关系.例如,A={a,b,c,d}表示男教师,B={x,y,z}表 示女教师集合.如果A、B的元素之间有夫妻关系，是a和y， c和z，那么 （1）a和y是成对出现，c和z是成对出现. （2）根据谓词概念，这对元素具有一定顺序. （3）应该给出特定的表示方法表达这种关系
4.1.1有序对的概念 定义41-1由两个元素,比如x和y,按照一定顺序构 成的序列称为有序对,也称序偶或二元组,记作(Xy (也可记作(Xy)),其中x是它的第一元素,y是它的 第二元素,且xy,可以相同 例如,坐标系中点的坐标(3,4) 1,2)就是 有序对 般说来有序对具有以下特点: (1)当xy时,(Xy)≠(y,x),即在一个有序对中, 如果两个元素不相等,那么它们是不能交换次序的例如, 0,1〉与(1,0)代表不同的有序对 2)两个有序对相等,即〈Xy)=〈u,v)的充分必 要条件是x=u且y=v
4.1.1 有序对的概念 定义4.1-1 由两个元素，比如x和y，按照一定顺序构 成的序列称为有序对，也称序偶或二元组，记作〈x,y〉 （也可记作（x,y）），其中x是它的第一元素，y是它的 第二元素,且x,y, 可以相同. 例如，坐标系中点的坐标（3，4），（-1，2）就是 有序对. 一般说来有序对具有以下特点： （1） 当x≠y时，〈x,y〉≠〈y,x〉,即在一个有序对中， 如果两个元素不相等，那么它们是不能交换次序的.例如， 〈0,1〉与〈1,0〉代表不同的有序对. （2） 两个有序对相等，即〈x,y〉=〈u,v〉的充分必 要条件是x=u且y=v
4.1.1有序对的概念 定义412一个有序n元组m23是一个有序对,其中 第一个元素是一个有序n1元组.一个有序n元组记作 〈X1x2,…xn〉,即 n-1 有序3元组〈Xy,z)可以表示为(〈x,y〉,z〉,同样 具有特点(〈xy)〉,z)=〈(u,v),W)的充分必要条件是 xy)={u,v),z=W,即xu,y=V,z=W例如,空间直 角坐标系中点的坐标〈1,-1,3〉,〈2,4.5,0〉等都是有序3 元组n维空间中点的坐标或n维向量都是有序n元组 形式上也可以把〈x)看成有序1元组,只不过这里的 顺序性没有什么实际意义以后提到有序n元组,其中的n 可以看成任何的正整数
4.1.1 有序对的概念 定义4.1-2 一个有序n元组(n≥3)是一个有序对，其中 第一个元素是一个有序n-1元组.一个有序n元组记作 〈x1 ,x2 ,…,xn〉，即 〈x1 ,x2 ,…,xn〉=〈〈x1 ,…,xn-1〉,xn〉. 有序3元组〈x,y,z〉可以表示为〈〈x,y〉,z〉，同样 具有特点〈〈x,y〉,z〉=〈〈u,v〉,w〉的充分必要条件是 〈x,y〉=〈u,v〉,z=w，即x=u，y=v，z=w.例如，空间直 角坐标系中点的坐标〈1,-1,3〉,〈2,4.5,0〉等都是有序3 元组.n维空间中点的坐标或n维向量都是有序n元组. 形式上也可以把〈x〉看成有序1元组，只不过这里的 顺序性没有什么实际意义.以后提到有序n元组，其中的n 可以看成任何的正整数
4.1.2笛卡儿积 定义4.1-3设A、B为两个集合,称由 A中元素为第一个元素,B中元素为第二个 元素的所有有序对组成的集合为A与B的笛 卡儿积,记作A×B符号化表示为 A×B={Xy〉|∈AAy∈B}
4.1.2 笛卡儿积 定义4.1-3 设A、B为两个集合，称由 A中元素为第一个元素，B中元素为第二个 元素的所有有序对组成的集合为A与B的笛 卡儿积，记作A×B.符号化表示为 A×B={〈x,y〉|x∈A∧y∈B}
4.1.2笛卡儿积 有穷集合的笛卡儿积运算满足下述性质 1)若A、B中有一个是空集,则它们的笛卡儿积是 空集,即 A×B=A×B= (2)当A#B且A、B都不是空集时,有A×B#B×A 3)当A、B、C都不是空集时,有 (A×B)×C={〈〈a,b〉,C)‖〈a,b)∈A×B)(C∈C)}, A×(B×C)气〈a,(b,C)〉|(a∈A)∧(〈b,C〉∈B×C)}, 由于(a,(b,c〉〉不是有序3元组,(A×B)×C≠ A×(B×C 如果A、B、C中有一个是空集,那么上面式子的左右 两边都是空集这条性质说明笛卡儿积运算不适合结合律
4.1.2 笛卡儿积 有穷集合的笛卡儿积运算满足下述性质： （1）若A、B中有一个是空集，则它们的笛卡儿积是 空集，即 A×B=A×B=φ . （2）当A≠B且A、B都不是空集时，有A×B≠B×A. （3）当A、B、C都不是空集时，有 (A×B)×C={〈〈a,b〉,c〉|(〈a,b〉∈A×B)∧(c∈C)}， A×(B×C)={〈a,〈b,c〉〉|(a∈A)∧(〈b,c〉∈B×C)}， 由于〈a,〈b,c〉〉不是有序3元组， (A×B)×C ≠ A×(B×C). 如果A、B、C中有一个是空集，那么上面式子的左右 两边都是空集.这条性质说明笛卡儿积运算不适合结合律
4.1.2笛卡儿积 (4)笛卡儿积运算对并和交运算满足分配律,即 A×(B∪C)=(A×B)∪(A×C), (B∪C)×A=(B×A)∪(C×A), A×(B∩C)=(A×B)∩(A×C), (BnC)×A=(B×An(C×A)
4.1.2 笛卡儿积 （4）笛卡儿积运算对并和交运算满足分配律，即 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)
4.1.2笛卡儿积 定义41-4设A1,A2,,A为n个集合(n≥2),称集合 A1×A2×…×A={(X,x2,…,xn〉kX∈A,=1,2…,n} 为n阶笛卡儿积当A1=A2=.=A=A时,记A生成的n阶笛卡 儿积为An 设A1A2,…,An均为有限集合,并设A|=n1=1,2,…,n, 则A1×A2×,×An=n×n2×…×nn n维笛卡儿积的性质与二维笛卡儿积的性质类似,这里 不再赘述
4.1.2 笛卡儿积 定义4.1-4 设A1 ,A2 ,…,An为n个集合(n≥2)，称集合 A1×A2×…×An={〈x1 ,x2 ,…,xn〉|xi∈Ai ,i=1,2,…,n} 为n阶笛卡儿积.当A1=A2=…=An=A时，记A生成的n阶笛卡 儿积为An . 设A1 ,A2 ,…,An均为有限集合，并设|Ai |=ni ,i=1,2,…,n， 则|A1×A2×…×An |=n1×n2×…×nn . n维笛卡儿积的性质与二维笛卡儿积的性质类似，这里 不再赘述