离散数学基础[洪帆]第二章关系.pptVIP

第2章 关系;2.1 笛卡儿积; 定义 假设(a1,a2,…,an) 和(b1,b2,…,bn) 是两个有序n元组, 则 (a1,a2,…,an)= (b1,b2,…,bn)成立, 当且仅当a1=b1, a2=b2,…, an=bn。 3. 序偶 当n=2时，有序二元组(a,b)称为序偶。; 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)| ai∈Ai,i=1,2,…,n}; 例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,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 关系;注： 若 是A到B的一个关系， 如果(a,b) ∈ , 则称a与b有 关系 , 记作a b, 如果(a,b) , 则称a与b没有 关系，记作a b。;集合称为关系的值域，记作; 例1 设集合A={1,2,4,7,8}, B={2,3,5,7}, 定义由A到B的关系: ={(a,b)|(a+b)/5是整数} 试问 由哪些序偶组成？ 并求此关系的定义域和值域。 ; 1）定义 由集合A到A自身的关系称为 集合A上的关系。 ;a) 普遍关系 若关系 R =A2, 则称R为A上的普遍关系, 记作UA, 即UA={(ai,ak)|ai,ak∈A}。 ; 令有向图G=(V,E), 其中顶点集V=A,边集E按如下规定: 有向边 ; 例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上的二元关系。 画出关系R与S的关系图。 ;且关系矩阵的第i行、第j列的元素 ; 例4 设集合A=2{0,1}, B=2{0,1,2}-2{0}, ={(a,b)|a-b= } 是一个由A到B的关系, 试列出关系 的定义域和值域，构造出关系矩阵。;2.3 关系的复合;二、关系的逆关系（关系的逆运算） ; 三、关系的复合运算 1. 定义 设 是一个有A1和A2的关系, 是一个由A