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

笛卡儿积的性质 不适合交换律 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<xy>∈A×C 分≮x>∈(4XB)∪(4×O) 所以有AX(B∪C=(4×B)∪(4XO

7 性质的证明 证明 A(BC)=(AB)(AC) 证 任取<x,y> <x,y>∈A×(B∪C)  x∈A∧y∈B∪C  x∈A∧(y∈B∨y∈C)  (x∈A∧y∈B)∨(x∈A∧y∈C)  <x,y>∈A×B∨<x,y>∈A×C  <x,y>∈(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> xy>∈A×Cx∈A∧yeC 分x∈B∧yeD分≮x2∈BxD (2)不一定.反例如下 A={1},B={2},C=D=,则AXC=BXD但是A≠B

8 例题 解 (1) 任取<x,y> <x,y>AC  xA  yC  xB  yD  <x,y>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 如<x少>∈R,可记作xRy;如果<x1少>gR,则记作x累y 实例:R={1,2>,a,b>},S={<1,2>,n,b} R是二元关系,当a,b不是有序对时,S不是二元关系 根据上面的记法,可以写1R2,aRb,dQc等

9 二元关系的定义 定义 如果一个集合满足以下条件之一： （1）集合非空, 且它的元素都是有序对 （2）集合是空集 则称该集合为一个二元关系, 简称为关系，记作R. 如<x,y>∈R, 可记作 xRy；如果<x,y>R, 则记作x y 实例：R={<1,2>,<a,b>}, S={<1,2>,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={<0,1>}那么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={<0,2>}, R2=A×B, R3=, R4={<0,1>}. 那么 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