《离散数学》PPT课件：第4章 二元关系与函数（4.1-4.2）集合的笛卡儿积和二元关系、关系的运算

第4章二元关系与函数 41集合的笛卡儿积与二元关系 42关系的运算 43关系的性质 44关系的闭包 45等价关系和偏序关系 46函数的定义和性质 47函数的复合和反函数

1 第4章 二元关系与函数 ◼ 4.1 集合的笛卡儿积与二元关系 ◼ 4.2 关系的运算 ◼ 4.3 关系的性质 ◼ 4.4 关系的闭包 ◼ 4.5 等价关系和偏序关系 ◼ 4.6 函数的定义和性质 ◼ 4.7 函数的复合和反函数

41集合的笛卡儿积和二元关系 ■有序对 ■笛卡儿积及其性质 ■二元关系的定义 ■二元关系的表示

2 4.1 集合的笛卡儿积和二元关系 ◼ 有序对 ◼ 笛卡儿积及其性质 ◼ 二元关系的定义 ◼ 二元关系的表示

有序对 定义由两个客体x和y,按照一定的顺序组成的 二元组称为有序对,记作≠x>(当xy时) xx,y>与==,求x,p 解3y-4=2,x+5=y→y=2,x=-3

3 有序对 定义 由两个客体 x 和 y，按照一定的顺序组成的 二元组称为有序对，记作 实例：点的直角坐标(3,−4) 有序对性质 有序性  （当x y时） 与 相等的充分必要条件是 =  x=u  y=v 例1 = ，求 x, y. 解 3y− 4 = 2, x+5 = y  y = 2, x = − 3

有序n元组 定义一个有序n(n23)元组是一个 有序对,其中第一个元素是一个有序n-1元组,即 ,x 当n=1时,形式上可以看成有序1元组 实例n维向量是有序n元组

4 有序 n 元组 定义 一个有序 n (n3) 元组 是一个 有序对，其中第一个元素是一个有序 n-1元组，即 = , xn> 当 n=1时, 形式上可以看成有序 1 元组. 实例 n 维向量是有序 n元组

笛卡儿积 定义设A,B为集合,A与B的笛卡儿积记作AxB, A×B={≤xy>|xeAy∈B 例2A={1,2,3},B={a,b,c} A×B={,,1C>,2,①>,2,b>,2,>, ,3,b>,,,C,1>,,2>,,C,2> ,,c,3>} A={∞},P(4)x4={

5 笛卡儿积 定义 设A,B为集合，A与B 的笛卡儿积记作AB， 即 AB ={ | xA  yB } 例2 A={1,2,3}, B={a,b,c} AB ={,,,,,, ,,} BA ={,,,,,, , ,} A={}, P(A)A={, }

笛卡儿积的性质 不适合交换律 AxB2BxA4(A≠B,A≠,B≠D) 不适合结合律(A×B)xC≠4x(BxC)(4≠,B≠) 对于并或交运算满足分配律 A×(B∪O=(4×B)(4×C) (BCx4=(B×A(C×4) A×(BO)=(4×B)(4×C (BnCx4=(B×A(C×4) 若A或B中有一个为空集,则AB就是空集 A×=c×B= 若|4|=m,|B|=n,则|AXB=mn

6 笛卡儿积的性质 不适合交换律 ABBA (AB, A, B) 不适合结合律 (AB)CA(BC) (A, B) 对于并或交运算满足分配律 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) 若A或B中有一个为空集，则AB就是空集. A=B= 若|A|=m, |B|=n, 则 |AB|=mn

性质的证明 证明A×(BO=(4xB∪(4xC) 证任取x少> xy>∈A×(B∪C) 分x∈A∧y∈B∪C 台x∈A∧∈BVy∈C 台(x∈A∧y∈B)V(x∈A∧y∈C 分≮∈AXBV∈A×C 分≮x>∈(4XB)∪(4×O) 所以有AX(B∪C=(4×B)∪(4XO

7 性质的证明 证明 A(BC)=(AB)(AC) 证 任取 ∈A×(B∪C)  x∈A∧y∈B∪C  x∈A∧(y∈B∨y∈C)  (x∈A∧y∈B)∨(x∈A∧y∈C)  ∈A×B∨∈A×C  ∈(A×B)∪(A×C) 所以有A×(B∪C) = (A×B)∪(A×C)

例题 例3(1)证明A=B∧C=D→AxC=BXD (2)AxC=BxD是否推出A=B∧C=D?为什么? 解(1)任取 xy>∈A×Cx∈A∧yeC 分x∈B∧yeD分≮x2∈BxD (2)不一定.反例如下 A={1},B={2},C=D=,则AXC=BXD但是A≠B

8 例题 解 (1) 任取 AC  xA  yC  xB  yD  BD 例3 (1) 证明 A=B  C=D  AC=BD (2) AC=BD是否推出 A=B  C=D ? 为什么？ (2) 不一定. 反例如下： A={1}，B={2}, C=D=, 则 AC=BD 但是 AB

元关系的定义 定义如果一个集合满足以下条件之 (1)集合非空,且它的元素都是有序对 (2)集合是空集 则称该集合为一个二元关系,简称为关系,记作R 如∈R,可记作xRy;如果gR,则记作x累y 实例:R={1,2>,a,b>},S={,n,b} R是二元关系,当a,b不是有序对时,S不是二元关系 根据上面的记法,可以写1R2,aRb,dQc等

9 二元关系的定义 定义 如果一个集合满足以下条件之一： （1）集合非空, 且它的元素都是有序对 （2）集合是空集 则称该集合为一个二元关系, 简称为关系，记作R. 如∈R, 可记作 xRy；如果R, 则记作x y 实例：R={,}, S={,a,b}. R是二元关系, 当a, b不是有序对时，S不是二元关系 根据上面的记法，可以写 1R2, aRb, a c 等

从A到B的关系与A上的关系 定义设AB为集合,AXB的任何子集所定义的二元 关系叫做从4到B的二元关系,当A=B时则叫做A上 的二元关系 例4A={0,1},B={1,2,3},R1={0,2>},R2=A×B, R3=,R4={}那么R1,R2,R3,R4是从A到B 的二元关系,R3和R4同时也是A上的二元关系 计数 4|=n,|4×A=n2,A×A的子集有2个所以A上有 22个不同的二元关系 例如||=3,则A上有=512个不同的二元关系 10

10 从A到B的关系与A上的关系 定义 设A,B为集合, A×B的任何子集所定义的二元 关系叫做从A到B的二元关系, 当A=B时则叫做 A上 的二元关系. 例4 A={0,1}, B={1,2,3}, R1={}, R2=A×B, R3=, R4={}. 那么 R1 , R2 , R3 , R4是从 A 到 B 的二元关系, R3和R4同时也是 A上的二元关系. 计数 |A|=n, |A×A|=n 2 , A×A的子集有 个. 所以 A上有 个不同的二元关系. 例如 |A|=3, 则 A上有=512个不同的二元关系. 2 2 n 2 2 n