华东交通大学：《离散数学》课程教学资源（PPT课件讲稿）第四章 二元关系和函数

第四章二元美系和函数 541集合的卡尔积与二元关系 542关系的运算 543关系的性质 54关系的闭包 54.5等价关系和偏序关系 546函数的定义和性质 57函数的复合和反函数 2021/2/24 离散数学

2021/2/24 离散数学 1 第四章 二元关系和函数 §4.1 集合的笛卡尔积与二元关系 §4.2 关系的运算 §4.3 关系的性质 §4.4 关系的闭包 §4.5 等价关系和偏序关系 §4.6 函数的定义和性质 §4.7 函数的复合和反函数

84.1集合的笛卡尔积与二元关系 一、二元关系的概念 有房对(序偶):由两个元素x和按一定顺序排成 的二元组。记作:。其中是它的第 元素,y是它的第二元素。 如平面直角坐标系点的坐标。 特:(1)当x≠y时,≠ (2)=当且仅当x=l,y=v (1)(2)说明有序对区别于集合。 2021/2/24 离散数学

2021/2/24 离散数学 2 §4.1 集合的笛卡尔积与二元关系 一、二元关系的概念 有序对（序偶）：由两个元素x 和y 按一定顺序排成 的二元组。记作：。其中x是它的第 一元素，y是它的第二元素。 特点：(1)当x  y 时，  (2) = 当且仅当x = u, y = v (1)(2)说明有序对区别于集合。 如平面直角坐标系点的坐标

、二元关系的概念(续) 元有序对:第一元素是一个n-1元有序对的有序对。 记作:x1,x2,…,xn>。 即=|x∈A∧y∈B 2021/2/24 离散数学

2021/2/24 离散数学 3 一、二元关系的概念（续） n 元有序对：第一元素是一个n –1元有序对的有序对。 记作：。 即 = , xn > 笛卡尔积：设A、B为两集合，以A中元素为第一元 素，B中元素为第二元素构成的二元有 序对的全体叫做A和B的笛卡儿积。 记作：A  B 符号化 A  B = { | xA  yB }

、二元关系的概念(续) 例1:设4={a,b},B={0,1,2},求A4xB,B×A 解:由笛卡尔积的定义知 A×B={,,, ,,} B×A={,, 2,a>,} 一般地,着4=m,|B|=n,则4×B=|BxA|=m 2021/2/24 离散数学

2021/2/24 离散数学 4 一、二元关系的概念（续） 例1：设A = { a, b }，B = { 0, 1, 2 }，求A  B，B  A。 解：由笛卡尔积的定义知 A  B = { , , , , , } B  A = { , , , , , } 一般地，若|A| = m, |B| = n, 则|A  B| = |B  A| = mn

、二元关系的概念(续) 笛卡尔积运算的性质: (1)如果A,B中有一个空集,则笛卡儿积是空集, 即:⑦xB=Ax=团 (2)当A≠B,且A,B都不是空集时,有A×B≠B×A, 即笛卡尔积不满足交换律。 (3)当A,B,C都不是空集时,有(4×B)×C≠ Ax(B×C),即笛卡尔积不满足结合律。 2021/2/24 离散数学

2021/2/24 离散数学 5 一、二元关系的概念（续） 笛卡尔积运算的性质： (1) 如果A, B中有一个空集，则笛卡儿积是空集， 即：  B = A   =  (3) 当A, B, C都不是空集时，有(A  B)  C  A  ( B  C)，即笛卡尔积不满足结合律。 (2) 当A  B，且A, B都不是空集时，有A  B  B  A, 即笛卡尔积不满足交换律

、二元关系的概念(续) (4)笛卡尔积运算对U或∩运算满足分配律 即Ax(BUC)=(4×B)U(4×O) (BUC)×A=(B×A)U(C×A) A×(BnC=(4×B)n(×O) (BnO)×A=(BxA)∩(C×A) 证明:∈(BUO×A分x∈BUC∧y∈A 分(x∈BVx∈C)AyeA 分(x∈B^y∈A)v(x∈C∧y∈A) 冷(∈B×A)(∈C×A) 冷∈(B×A)U(C×A) 2021/2/24 离散数学

2021/2/24 离散数学 6 一、二元关系的概念（续） (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) 证明：  (B∪C)  A  xB∪C  yA  ( xB  xC )  yA  ( xB  yA )  ( xC  yA )  (  B  A )  (  C  A )  (B  A)∪(C  A)

、二元关系的概念(续) 例2:设4={1,2},求P(4)×A 解:P(4)×A ={∞,{1},{2},{1,2}}×{1, 2} ={,,,,, {2},2>,,{1,2},2>} 推广:m阶笛卡尔积 A1×A2X…×An ={x1,x2,…,xn>|X1∈A1Ax2eA42A…Axne 2021/2/24 离散数学

2021/2/24 离散数学 7 一、二元关系的概念（续） 例2：设A = {1, 2}，求P (A)  A。 解： P (A)  A 推广：n阶笛卡尔积 A1  A2  …  An = { | x1A1  x2A2  …  xnAn } = { , {1}, {2}, {1, 2} }  {1, 2} = { , , , , , , , }

、二元关系的概念(续) 二元美系是指在集合中两个元素之间的某种相关性 例如:家庭成员集合{a,bcd}上的父子关系 R={, 二元美系的学定y:如果一个集合为空集或者它 的元素都是二元有序对,则这个集合 称为一个二元关系,记作:R 如果∈R,记作xRy 如果R,记作xRy/ 2021/2/24 离散数学

2021/2/24 离散数学 8 一、二元关系的概念（续） 二元关系是指在集合中两个元素之间的某种相关性. 例如:家庭成员集合{a,b,c,d}上的父子关系. R={,}. 二元关系的数学定义：如果一个集合为空集或者它 的元素都是二元有序对，则这个集合 称为一个二元关系，记作：R 如果  R ，记作 x R y 如果  R ，记作 x R y

、二元关系的概念(续) 从A到B的二元美系:设A、B为集合,A×B的任何 子集所定义的二元关系叫做从A到B的二元关系。 设A={abc代表三个人的构成的集合 B={234代表四项工作构成的集合 若a从事工作1b从事工作2c从事工作3,则人从事工 作之间的关系可以表示为: R={12>为A到B的二元关系之 2021/2/24 离散数学 9

2021/2/24 离散数学 9 一、二元关系的概念（续） 从A到B的二元关系：设A、B为集合， A  B的任何 子集所定义的二元关系叫做从A到B的二元关系。 设A={a,b,c}代表三个人的构成的集合 B={1,2,3,4}代表四项工作构成的集合 若a从事工作1,b从事工作2,c从事工作3,则人从事工 作之间的关系可以表示为: R={,,} 为A到B的二元关系之 一

特别地,若A=B,叫作A上的二元关系。 例如:家庭成员集合4={abc4上的成员分别代表父、母、兄、 弟,则该集合上的各种关系为: 父子关系:{,,<b, 兄弟关系:。。。夫妻关系。。。都是A上的二元关系 着4|=n,则4×4=n2,A×A的所有子集有2阶, 因此,A上有2个不同的二元关系。 2021/2/24 离散数学 10

2021/2/24 离散数学 10 特别地，若A = B，叫作A上的二元关系。 若|A| = n，则|A  A| = n 2 ， A  A的所有子集有 个， 因此， A上有 个不同的二元关系。 2 2 n 2 2 n 例如: 家庭成员集合A={a,b,c,d}上的成员分别代表父、母、兄、 弟，则该集合上的各种关系为： 父子关系：{ , }. 母子关系： { , }. 兄弟关系： 。。。夫妻关系。。。 都是A上的二元关系