《离散数学》课程教学课件（PPT讲稿）7a 二元关系

二元关系

析取范式与合取范式 二元关系

一CUSTOMERS WHOBOUGHT THIS ITEM:自Why did the Maths日品可textbook look so sad?OG9电旺BOUGHTaeSdeonpBecause it had so manyproblems!piccate

有序对与笛卡儿积定义7.1由两个元素×和y，按照一定的顺序组成的二元组称为有序对，记作.有序对性质：(1)有序性≠(当x#y时(2)与相等的充分必要条件是=X=u^y=V二元集y中的元素是无序的，不具备上述性质3

3 有序对与笛卡儿积 定义7.1 由两个元素x 和 y，按照一定的顺序组成的二元组 称为有序对，记作. 有序对性质: (1) 有序性  （当xy时） (2) 与相等的充分必要条件是 =  x=uy=v. 二元集{x,y}中的元素是无序的，不具备上述性质

笛卡儿积定义7.2设A,B为集合，A与B的笛卡儿积记作AxB，符号化表示为AxB=( XEAΛyEB)例1 A={1,2,3), B=[a,b,c)AxB=[,,,,,,,,]BxA=[,,,,,,,,]A={O), B=P(A)xA= [, )P(A)×B= O4

4 笛卡儿积 定义7.2 设A,B为集合，A与B的笛卡儿积记作AB，符号化表 示为 AB = {| xAyB}. 例1 A={1,2,3}, B={a,b,c} AB ={,,,,,,,,} BA ={,,,,,,,,} A={}, B= P(A)A = {, } P(A)B = 

笛卡儿积的性质(1) 不适合交换律A×B BxA (A+B,A+O, B+)(2) 不适合结合律(A×B)×C± A×(B×C) (A+, B+, C+O)(3)对于并或交运算满足分配律A×(BUC) = (AxB)U(AxC)(BUC)xA = (BxA)U(CxA)Ax(BNC) = (AxB)N(AxC)(BC)xA = (BxA)n(CxA)(4)若A或B中有一个为空集，则AxB就是空集.AxQ=QxB=0(5) ACC^BCD=A×BCCxD,(6)若 [A/ =m, |B[ =n, 则 [AxB| =mn5

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

性质证明证明 A×(BUC)= (A×B)U(A×C)证任取EA× (BUC)XEAAyEBUCXEAA(VEBVyEC) (xEAAyEB)V(xEAAyEC)EA × BVEA× C←E(A X B) U (A X C)所以有A × (BUC)=(A X B) U(A × C)6

6 性质证明 证明 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)

实例例2(1) 证明A=B,C=D=A×C=BxD(2)AxC=BxD是否推出A=B,C=D?为什么 ?解(1)任取EAxC XEAAYEC XEBAVED<>EBxD(2)不一定.反例如下：A=[1], B=[2], C = D = , 则AxC= BxD但是A ≠ B.7

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

二元关系定义7.3如果一个集合满足以下条件之一：(1)集合非空，且它的元素都是有序对(2）集合是空集则称该集合为一个二元关系，简称为关系，记作R如果ER,可记作xRy；如果史R,则记作xRy实例 : R=[,], S=[,a,b]R是二元关系，当a，b不是有序对时，S不是二元关系根据上面的记法，可以写1R2,aRb,aRc等.8

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

A到B的关系与A上的关系定义7.4设AB为集合，AXB的任何子集所定义的二元关系叫做从A到B的二元关系，当A=B时则叫做A上的二元关系例3A=[0,1], B=[1,2,3], 那么Ri=[], R2=A × B, R3=O, R4=[]R1,R2,R3,R4是从A到B的二元关系，R3和R4也是A上的二元关系.2h计数：IA|=n, IA×A|=n2,A×A的子集有2"个.所以A上有2个不同的二元关系例如[A/=3,则A上有=512个不同的二元关系9

9 A到B的关系与A上的关系 定义7.4 设A,B为集合, A×B的任何子集所定义的二元关系叫做从A 到B的二元关系, 当A=B时则叫做A上的二元关系. 2 2 n 例3 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

A上重要关系的实例定义7.5设A为集合，(1)①是A上的关系，称为空关系(2) 全域关系 E^=[| xEA^yEA) =AXA恒等关系 IA =[/ xEA)小于等于关系 LA =[[ x,yEAΛx≤y], A为实数子集整除关系 DB=[/ x,yEBΛx整除y), A为非0整数子集包含关系 R_=[/ x,yEA^xCy],A是集合族.10

10 A上重要关系的实例 定义7.5 设 A 为集合, (1) 是A上的关系，称为空关系 (2) 全域关系 EA = {| x∈A∧y∈A} = A×A 恒等关系 IA = {| x∈A} 小于等于关系 LA = {| x,y∈A∧x≤y}, A为实数子集 整除关系 DB = {| x,y∈B∧x整除y}, A为非0整数子集 包含关系 R = {| x,y∈A∧xy}, A是集合族