离散数学二元关系课件.ppt

《离散数学二元关系课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学周塔计算机教研室2012年9月江苏科技大学本科生必修课程第7章二元关系1本章说明本章的主要内容有序对与笛卡儿集二元关系的定义和表示法关系的运算关系的性质关系的闭包等价关系与划分偏序关系本章与后续各章的关系本章是图论的基础2本章内容7.1有序对与笛卡儿积7.2二元关系7.3关系的运算7.4关系的性质7.5关系的闭包7.6等价关系与划分7.7偏序关系本章小结习题作业37.1有序对与笛卡儿积定义7.1由两个元素x和y（允许x=y）按一定顺序排列成的二元组叫做一个有序对(orderedpair)或序偶，记作，其中x是它的第一元素，y是它的第二元素

2、。有序对具有以下性质：（1）当x≠y时，≠。（2）＝的充分必要条件是x＝u且y＝v。说明有序对中的元素是有序的集合中的元素是无序的4例7.1例7.1已知＝<5,2x+y>，求x和y。由有序对相等的充要条件有x+2＝52x+y＝4解得x＝3,y＝-2。解答5定义7.2设A，B为集合,用A中元素为第一元素，B中元素为第二元素构成有序对。所有这样的有序对组成的集合叫做A和B的笛卡儿积(Cartesianproduct)，记作A×B。笛卡儿积的符号化表示为A×B＝{

3、x∈A∧y∈B}笛卡儿积

4、的定义A表示某大学所有学生的集合，B表示大学开设的所有课程的集合，则A×B可以用来表示该校学生选课的所有可能情况。令A是直角坐标系中x轴上的点集，B是直角坐标系中y轴上的点集，于是A×B就和平面点集一一对应。举例6笛卡尔积举例设A={a,b},B={0,1,2}，则A×B={,,,,,}B×A={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>}举例说明如果

5、A

6、=m,

7、B

8、=n,则

9、A×B

10、=mn。7笛卡儿积的运算性质(1)对任意集合A，根据定义有A×＝,×A＝(2

11、)一般的说，笛卡儿积运算不满足交换律，即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)8A×(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)

12、∈A×B∨∈A×C∈(A×B)∪(A×C)所以A×(B∪C)=(A×B)∪(A×C)9例7.2例7.2设A={1,2},求P(A)×A。P(A)×A＝{,{1},{2},{1,2}}×{1,2}＝{<,1>,<,2>,<{1},1>,<{1},2>,<{2},1>,<{2},2>,<{1,2},1>,<{1,2},2>}解答10例7.3例7.3设A，B，C，D为任意集合，判断以下命题是否为真，并说明理由。(1)A×B＝A×CB＝C(2)A-(B×C)＝(A-B)×(A-C)(3)A＝B∧C＝DA×C＝B×D(4)存在集合A

13、，使得AA×A(1)不一定为真。当A＝，B＝{1},C＝{2}时，有A×B＝＝A×C，但B≠C。(2)不一定为真。当A=B={1},C＝{2}时，有A-(B×C)＝{1}–{<1,2>}＝{1}???(A-B)×(A-C)＝×{1}＝(3)为真。由等量代入的原理可证。(4)为真。当A＝时，有AA×A成立。解答117.2二元关系(binaryrelation)定义7.3如果一个集合满足以下条件之一：（1）集合非空，且它的元素都是有序对（2）集合是空集则称该集合为一个二元关系，记作R。二元关系也可简称为关系。对于二元关系R，如果∈R，

14、可记作xRy；如果R，则记作xRy。设R1＝{<1,2>,}，R2＝{<1,2>,a,b}。则R1是二元关系，R2不是二元关系，只是一个集合，除非将a和b定义为有序对。根据上面的记法可以写1R12，aR1b，aR1c等。举例R＝{<上,下>,<前,后>,<正,反>,<左,右>}是否为二元关系？12集合A上的二元关系的数目依赖于A中的元素数。如果

15、A

16、=n，那么

17、A×A

18、=n2，A×A的子集就有个。每一个子集代表一个A上的二元关系，所以A上有个不同的二元关系。例如

19、A

20、=3，则A上有个不同的二元关系。7.2二元关系定义7.4设A，B为集

21、合，A×B的任何子集所定义的二元关系叫做从A到B的二元关系；特别当