哈尔滨理工大学：《离散数学 Discrete Mathematics》课程教学资源（PPT课件讲稿）07 二元关系

哈尔滨理工大学斛监課裎 离影数 :第7章二元关系 计算机系

第7章 二元关系 离 散 数 学 哈尔滨理工大学本科生课程 计算机系

本章说明 口本章的主要内容 有序对与笛卡儿集 二元关系的定义和表示法 关系的运算 关系的性质 关系的闭包 等价关系与划分 偏序关系 口本章与后续各章的关系 本章是函数的基础 本章是图论的基础

本章说明 ❑ 本章的主要内容 –有序对与笛卡儿集 –二元关系的定义和表示法 –关系的运算 –关系的性质 –关系的闭包 –等价关系与划分 –偏序关系 ❑ 本章与后续各章的关系 –本章是函数的基础 –本章是图论的基础

本章内容 7.1有序对与笛卡儿积 7.2二元关系 7.3关系的运算 7.4关系的性质 7.5关系的闭包 7.6等价关系与划分 7.7偏序关系 本章小结 习题 作业

本章内容 7.1 有序对与笛卡儿积 7.2 二元关系 7.3 关系的运算 7.4 关系的性质 7.5 关系的闭包 7.6 等价关系与划分 7.7 偏序关系 本章小结 习题 作业

7.1有序对与笛卡儿积 定义7.1由两个元素x和y(允许x=y)按一定顺序排列成的二元 组叫做一个有序对( ordered pair)或序偶,记作,其中x 是它的第一元素,y是它的第二元素。 有序对x,y>具有以下性质: (1)当x≠y时,≠。 (2)=的充分必要条件是x=u且y=v ‖说明〉口有序对中的元素是有序的 口集合中的元素是无序的

7.1 有序对与笛卡儿积 定义7.1 由两个元素x和y（允许x=y）按一定顺序排列成的二元 组叫做一个有序对(ordered pair)或序偶，记作，其中x 是它的第一元素，y是它的第二元素。 有序对具有以下性质： （1）当x≠y时，≠。 （2）＝的充分必要条件是x＝u且y＝v。 说明 ❑ 有序对中的元素是有序的 ❑ 集合中的元素是无序的

例7,1 例7.1已知x+2,4=,求x和y。 解答由有序对相等的充要条件有 X+2=5 2x+y=4 解得x=3,y=-2

例7.1 例7.1 已知＝，求x和y。 由有序对相等的充要条件有 x+2＝5 2x+y＝4 解得 x＝3,y＝-2。 解答

的卡儿积的定义 定义7.2设A,B为集合,用A中元素为第一元素,B中元素为第 二元素构成有序对。所有这样的有序对组成的集合叫做A和B 的笛卡儿积( Cartesian product),记作A×B。 笛卡儿积的符号化表示为 A×B=x,y>x∈A∧y∈B 举例口A表示某大学所有学生的集合,B表示大学开设的所有 课程的集合, 则AXB可以用来表示该校学生选课的所有可能情况。 口令A是直角坐标系中x轴上的点集,B是直角坐标系中y 轴上的点集, 于是A×B就和平面点集一一对应

定义7.2 设A，B为集合,用A中元素为第一元素，B中元素为第 二元素构成有序对。所有这样的有序对组成的集合叫做A和B 的笛卡儿积(Cartesian product)，记作A×B。 笛卡儿积的符号化表示为 A×B＝{|x∈A∧y∈B} 笛卡儿积的定义 ❑ A表示某大学所有学生的集合，B表示大学开设的所有 课程的集合， 则A×B可以用来表示该校学生选课的所有可能情况。 ❑ 令A是直角坐标系中x轴上的点集，B是直角坐标系中y 轴上的点集， 于是A×B就和平面点集一一对应。 举例

的卡尔积举例 举例设Aa,b},B={0,1,2},则 A×B={,,,,,,,,,<2,b》 说明口如果|A|=m,|B=n,则|A×B|=mn

笛卡尔积举例 设A={a,b}, B={0,1,2}，则 A×B={,,,,,} B×A={,,,,,} 举例 说明 ❑ 如果|A|=m,|B|=n,则|A×B|=mn

的卡儿积的远性质 (1)对任意集合A,根据定义有 Ax=,g×A= (2)一般的说,笛卡儿积运算不满足交换律,即 A×B≠B×A (当A≠∧B≠∧A≠B时) (3)笛卡儿积运算不满足结合律,即 (AXB)×G≠AX(B×C)(当A≠∧B≠∧G≠时) (4)笛卡儿积运算对并和交运算满足分配律,即 A×(BU0)=(A×B)U(A×c) (BUC)×A=(B×A)∪(C×A A×(B∩c)=(A×B)∩(A×0) (B∩c)×A=(B×A)∩(C×A (5)Acc∧BcD→A× BCCXD

笛卡儿积的运算性质 (1)对任意集合A，根据定义有 A×＝, ×A＝ (2)一般的说，笛卡儿积运算不满足交换律，即 A×B≠B×A (当 A≠ ∧ B≠ ∧ A≠B 时) (3)笛卡儿积运算不满足结合律，即 (A×B)×C≠A×(B×C) (当 A≠ ∧ B≠ ∧ C≠ 时) (4)笛卡儿积运算对并和交运算满足分配律，即 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) (5)AC ∧ BD  A×B  C×D

A×(B∪C)=(A×B∪(AxC的证明 任取 ∈A×(BU0 分x∈A∧y∈BUG 台ⅹ∈A∧(y∈BVy∈0 分(x∈A∧y∈B)V(x∈A∧y∈0 分∈A×B∈A× 台∈(A×B)∪(AX0) 所以AX(BU0=(A×B)U(AX0)

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)

关于 ACCABCD→ AXBCCXD的讨论 该性质的逆命题不成立,可分以下情况讨论。 (1)当A=B=⑦时,显然有AC和BcD成立。 (2)当A≠⑦且B≠⑦时,也有A∞C和BcD成立,证明如下: 任取x∈A,由于B≠,必存在y∈B,因此有 x∈A∧y∈B →∈AXB →∈0×D →ⅹ∈c∧y∈D →∈c 从而证明了AcG 同理可证BcD

关于AC∧BD  A×BC×D的讨论 该性质的逆命题不成立，可分以下情况讨论。 （1）当A=B=时，显然有AC 和 BD 成立。 （2）当A≠且B≠时，也有AC和BD成立，证明如下： 任取x∈A，由于B≠,必存在y∈B,因此有 x∈A∧y∈B  ∈A×B  ∈C×D  x∈C∧y∈D  x∈C 从而证明了 AC。 同理可证 BD