七章节关系课件.pptxVIP

7.1 集合的笛卡尔积集 7.2 二元关系的基本概念 7.3 二元关系的性质 7.4 二元关系的闭包运算 7.5 等价关系和集合的划分 7.6 偏序关系和格 7.7 链与反链 二元关系例子： { }=Ø {(1,a), (2,a)} {(1,a), (1,b), (1,c), (2,a), (2,b), (2,c)} 定义1 A ，B是两个集合，称 A×B 的一个子集为从 集合A到集合B的一个二元关系，简称从A到 B的一个二元关系。 例 A={1,2} ， B={a,b,c}, A×B＝{(1,a), (1,b), (1,c), (2,a), (2,b), (2,c)} …… A={1,2,3}， A2=A×A＝{(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)} 二元关系例子： Ø A2 {(1,1), (2,2), (3,3)} …… 设R是从A到B的一个二元关系，则R ⊆ A× B。 u 若R=Ø，称为空关系 u 若R＝A × B，称为全关系 u 当A＝B时，称二元关系R⊆A×A为A上的二元 关系 u 当A＝B时，记△A={(x,x)│x∊A}为A 的恒等关系 例 设 A＝{a,b,c,d}是4个学生的集合， B={英语，高等数学，计算机原理，离散数学，数据结构} A×B 给出了学生和课程之间的所有可能配对. “相关性”意义既可以是描述学生们所选取的课程, 也可 以是表示学生对某些课程有偏爱。 (a,英语),(a,高等数学), (b,计算机原理),( b,英语), (c,离散数学),(c,数据结构), (d,英语),(d,离散数据) 关系R＝ { } • 有序二元组 • 表 • 图 • 矩阵 例 A={a,b,c,d}, B={α, β ,γ} B A α β γ a √ b √ c √ √ d √ R={ (a, α),(b, γ),(c, α),(c, γ),(d, β) } 则 R1 UR2 ={(x,y)│x∊A, y∊B, 学生x学习课程y , 或者学生 x喜欢课程y } R1 ∩R2 ={(x,y)│x∊A, y∊B, 学生x学习喜欢的课程y } R1– R2 ={(x,y)│x∊A, y∊B, 学生x学习不喜欢课程y } R1⊕ R2 ={(x,y)│x∊A, y∊B, 学生x学习不喜欢课程y , 或者学生x喜欢课程y但不学习课程y} R1={(x,y)│x∊A, y∊B, 学生x学习课程y} R2 ={(x,y)│x∊A, y∊B, 学生x喜欢课程y} 定义2 设A和B是两个集合, R是从A到B的一个二元关系。令 R={(x,y) ∊ B×A │(y,x)∊R} 称之为R的逆关系。 定义3 设A ，B ，C是三个任意集合， R1是从A到B的一个二元关系， R2是从B到C的一个二元关系。 令： R1◦R2 ＝{(x,y)∊ A×C│存在z∊B，使得 (x,z)∊R1, (z,y)∊R2 } 它表示一个从A到C的二元关系， 称之为R1与R2 的复合关系。 当 A＝B＝C，且 R1＝R2=R时， R◦R记为R2 。 解： S1 ＝{ (y,x) │x,y∊N，且y=x2 } S2 ＝{ (y,x) │x,y∊N，且y=x+1 } S1◦S2 ＝{ (x,y) │x,y∊N，且y=x2+1 } S2◦S1 ＝{ (x,y) │x,y∊N，且y=(x+1)2 } S12 ＝{ (x,y) │x,y∊N，且y=x4 } (p77) 设S1 ，S2是自然数集N上两个二元关系， S1 ＝{ (x,y) │x,y∊N，且y=x2 } S2 ＝{ (x,y) │x,y∊N，且y=x+1} 求 S1, S2, S1 ◦S2, S2 ◦S1, S12。 例 设 A 、B 、C 、D是四个任意集合， R1 、R2 、R3分别是从 A到B，从B到C，从C到D的二元关系。 则有： ① R1 ◦ △B = △A ◦R1 = R1 ② R1=R1 ③ R1 ◦R2 = R2 ◦R1 ④ (R1 ◦R2) ◦ R3= R1 ◦(R2 ◦R3 ) 仅证 R1 ◦ △B = R1 对于任意的x ，y ,若(x,y)∊R1◦ △B， 则存在b∊B，使得(x,b)∊R1，(b,y)∊△B， 即 b ＝y ， ∴(x,y)=(x,b)∊R1 即有 R1 ◦ △B ⊆R1 反过来，对于任意的x ，y，若(x,y)∊R1 ⊆ A×B ， 则 y∊B ， ∴(y,y)∊△B 由(x,y)∊R1 ，(y,y)∊△B ∴(x,