第工科离散数学课件 四章 4_2_关系运算(1) - 关系的求逆与复合.pptx

4.2 关系运算作为集合，关系可参与集合的一般运算，也存在逆和复合等特殊运算，他们是关系数据库中的表连接等操作的支撑理论。 4.2.1 关系的逆和复合4.2 关系运算-关系的逆和复合1. 关系的逆运算[关系的逆] 设R是X到Y的二元关系，将其每个序偶的元素交换顺序所得到的关系称为R的逆关系，记作 R-1 或RC：R-1 = {y, x?x, y?R}问：(1)若x, y?R，结论是？答： ?y, x?R-1 。示例：大于等于关系“≥”的逆就是小于等于关系“≤”。(2)若x, y?R-1，结论是？答： ?y, x?R 。例4-6：集合 A = {1,2,3}上的关系R = {1,1,2,2,3,3,1,2,2,3}的逆。解：R-1 = {1,1, 2,2, 3,3, 2,1, 3,2}。 定理：设R是任意关系，有(1) (R-1)-1 = R(2) dom R-1 = ran R，ran R-1 = dom R4.2 关系运算-关系的逆和复合证明：?(1)，说明(R-1)-1与R互相包含。对?x, y，有 x, y∈(R-1)-1 ?y, x∈R-1 ?x, y∈R结论成立。——由于关系本身是集合，因此，验证关系等式、包含关系的基本技术仍是“集合包含”的定义。?? 4.2 关系运算-关系的逆和复合例4-7：设 A = {2, 3, 6}，A上的二元关系 R = {3,3, 3,2,6,2}，S = {3,1, 2,2, 2,3}求R°S和S°R。解： R°S = {3,1, 3,2, 3,3, 6,2, 6,3}， S°R = {2,3, 2,2} 2. 关系的复合运算[关系的复合] 设R和S分别是X到Y和Y到Z的关系，连接R和S的序偶所得到的关系：R°S = {x, z?x∈X ? z∈Z ? ?y(y∈Y?x, y∈R?y, z∈S)} 复合关系=合成关系。 ——?x?z(x∈X ? z∈Z ? ?y(y∈Y?x, y∈R?y, z∈S))? ? 4.2 关系运算-关系的逆和复合答：(1) a, b∈R°S。(2) ?t∈Y，使a, t∈R，t, b∈S 。 ——命题?t(t∈Y?a, t∈R?t, b∈S)为真 (3) a, b∈R°S 。问：(1)若a, b∈R，b, c∈S，结论是？(2)若a, b∈R°S，结论是？(3)若a, b∈R，b, b∈S，结论是？——R°S = {x, z??x?z(x∈X ? z∈Z ? ?y(y∈Y?x, y∈R?y, z∈S))} 例4-8：设S、T是集合?上的关系，定义为：S = {x, y?x, y∈ ? ? y = x3}T = {x, y?x, y∈ ? ? y = x+1}求S-1、S°T和T°S。4.2 关系运算-关系的逆和复合解： S-1 = {y, x?x, y∈? ? y = x3}——计算复合关系S°T时先将T 换一下符号：T = {y, z | y, z∈? ? z = y+1}S与T中的序偶连接条件是z = y +1 = x3+1得S°T = {x, z?x, z∈? ? z = x3+1}。同理，得T°S = {x, z?x, z∈? ? z = (x+1)3}。 4.2 关系运算-关系的逆和复合2. 若R = {x, y?x, y∈ ? ? 2x+3y = 57}，求R2 = R°R？——x ≤ 57/2，y ≤ 57/3，写出序偶，逐个连接？麻烦——R = {y, z?y, z∈ ? ? 2y+3z = 57}，y=(57-3z)/2，2x+3((57-3z)/2)=57， R2 ={x, z| 4x-9z+57=0}1. 命题u, v∈T，w, u∈S为真，蕴含什么结论？——w, v∈S°T