离散数学教程-王元元-第6章 关系.pptVIP

离散数学 第6章 关系 第6章 关系 6.1.1 关系及二元关系 例6.1 设A = {a, b, c, d, e, f ，…} 为学生的集合 B = {?, ?,γ,δ,?} 为可选修课程的集合 C = { 2, 3, 4, 5 } 为学习成绩的集合 R：学生与课程之间的关系 —— 选修关系 S：学生、课程和成绩之间的关系 ——学生课程成绩关系 关系的表示：具有这种联系的对象的有序元组的集合。 R＝ {a,?,a,δ,b,?,b,?,c,γ,e,?,f,γ,…} S＝{a,?,5,a,δ,4,b,?,4,b,?,4,c,γ,5,e,?,3,f,γ,2,…} 6.1.1 关系及二元关系 定义6.1 称R为集合A1, A2, … , An-1到An的n元关系，如果R是 A1?A2?…?An 的一个子集。当A1＝A2＝…＝An-1＝An 时，也称R为A上的n 元关系。当n = 2时，称R为A1到 A2的二元关系。 A1, A2, … , An-1到An的n元关系也可 视为A1?A2?…?An-1到An的二元关系。 6.1.1 关系及二元关系 6.1.1 关系及二元关系 6.1.1 关系及二元关系 6.1.1 关系及二元关系 6.1.1 关系及二元关系 例6.3 设 A ={ a, b, c, d, e, f }，B = {?, ?, γ, δ, ?}， R = {a,?, a,δ, b,?, b,?, c,γ, e, ? , f,γ } Dom(R) ={ a, b, c, e, f }， Ran(R) = {? , ? ,γ,δ} 6.1.1 关系及二元关系 前域和陪域相同时的有向图表示。( A ={1 , 2 , 3 , 4 , 5}) 6.1.1 关系及二元关系 关系矩阵：设 R? A?B，A={a1, … ,am}, B ={b1, … ,bn}，那么R 的关系矩阵MR 为一 m?n 矩阵，它的第i , j 分量cij 只 取值0或1，cij＝1? aiRbj；cij＝0?﹁aiRbj 。 6.1.2 关系基本运算 定义6.3 如果R与S都是A到B的二元关系，并且 ?x?y(x?A∧y?B→xRy?xSy) 那么称关系R和S相等， 注意：两个关系是否相等，本质上取决于两个关系作为序偶集合 是否相等。 6.1.2 关系基本运算 四种基本运算： 设R和S为A到B的二元关系，其并、交、差、补运算定义： R∪S＝{ x, y ? xRy∨xSy } R∩S＝{ x, y ? xRy∧xSy } R – S＝{ x, y ? xRy∧﹁xSy } Rˉ＝A?B - R ＝{ x, y ? ﹁xRy } 6.1.2 关系基本运算 四种基本运算的矩阵求法： 有限二元关系的并、交、差、补的矩阵可如下求取： MR∪S = MR∨MS （矩阵对应分量作逻辑析取运算） MR∩S = MR∧MS （矩阵对应分量作逻辑合取运算） MR-S = MR∩S- =MR∧MS- MS- = (MS)ˉ （矩阵各分量作逻辑非运算） 6.1.2 关系基本运算 定义6.4 设R是A到B的关系，R的逆关系或逆是B到A的关系，记 为R~，“ ~ ”称关系的逆运算，规定为 R~= { y, x ? xRy } 对任意x?A, y?B， xRy ? yR~x 把R的关系图的所有有向边反转即可得到逆关系R~的关系图。 若MR为R的关系矩阵，那么 MR~=MRι （MRι表示矩阵M的转置矩阵） 例6.4 EA~= EA , ?~ = ? , (A?B)~=B?A ;