第四章 1笛卡尔积与关系

13:161离散数学(DiscreteMathematics)13:162第四章二元关系和函数4.1序偶与笛卡尔积4.2关系及其表示4.3关系的性质4.4关系的复合4.6关系的闭包运算4.7等价关系与等价类4.8相容关系4.9偏序关系4.5逆关系4.10函数及其性质4.11复合函数和逆函数13:1634.1序偶与笛卡尔积笛卡尔积的性质(ThePropertiesofCartesianProduct)序偶与笛卡尔积(OrderedPairs&CartesianProduct)小结13:164一、序偶与笛卡尔积4.1序偶与笛卡尔积1.序偶序偶与2个元素的集合，是不相同的。例如，{1,2}={2,1}，但〈1,2〉〈2,1〉又例如，{1,2}={1,2,2}，但〈1,2〉〈1,2,2〉.〈a1,a2〉=〈b1,b2〉定义4.1.1由2个具有固定次序的个体a1,a2组成的序列称为序偶(OrderedPair)，记作，其中a1,a2分别称为的第一元素和第二元素。定义4.1.2设有两个序偶和，当a1=b1，a2=b2，称这两个有序n元组相等，并记作13:1653.笛卡尔积4.1序偶与笛卡尔积定义4.1.5设A、B为任意集合，A和B的笛卡尔积(CartesianProduct)用AB表示，定义为AB={|aA,bB}2.n重序元/有序n元组定义4.1.3n个具有给定次序的个体a1,a2,,an组成的序列称为有序n元组(简称n元组)，记作〈a1,a2,,an〉,定义为〈a1,a2,,an〉=〈b1,b2,,bn〉定义4.1.4设有两个n元组和，当a1=b1，a2=b2，，an=bn时，称这两个n元组相等，并记作13:166如果A=，B=，则有4.1序偶与笛卡尔积例1设A={1,2,3},B={a,b},则AB={}BA={}所以，ABBA规定：A=或B=时，AB=，BA=.笛卡尔积运算不满足交换律，即ABBA笛卡尔积运算不满足结合律，即A(BC)(AB)C13:167二、笛卡尔积的性质 定理4.1.1设A、B、C是任意的集合，则有(1)(2)(3)(4)4.1序偶与笛卡尔积以(1)为例，给出其证明。证明13:168定理4.1.2若C，则4.1序偶与笛卡尔积AB(AC)(BC)(CA)(CB)证明(略)定理4.1.3设A、B、C、D是任意非空集合，则有ABCD(AC)(BD)13:1694.1序偶与笛卡尔积设A=D=，B=C={1}，则而(2)反例如下：不成立。13:1610定义4.1.6设A1,A2,…,An为n个(n2)集合，它们的笛卡尔积用A1A2…An表示，定义为A1A2…An是有序n元组构成的集合，特别地，当A1=A2=…=An=A时，可以写成An。若|A|=m，则|An|=mn。4.1序偶与笛卡尔积13:1611三、小结4.1序偶与笛卡尔积本节介绍了序偶、有序n元组及笛卡尔积的概念。重点理解有序n元组及笛卡尔积的概念。13:161212离散数学(DiscreteMathematics)13:1613关系的定义(ThedefinitionofRelations)几种特殊的关系(SeveralspecialRelations)关系的表示(TheexpressionofRelations)小结4.2关系及其表示13:1614一、关系的定义4.2关系及其表示定义4.2.1任意序偶的集合确定了一个二元关系R，R中的任一序偶可记作或，不在R中的任一序偶可记作或。例如，R={}，或.定义4.2.2笛卡尔积AB的任意一个子集R称为是A到B的一个二元关系，可记作RAB。特别地，当A=B时，称R是集合A上的二元关系。13:1615问题：4.2关系及其表示且问例如小于关系就是自然数集合上的二元关系，是自然数与自然数笛卡尔积的子集。R是A到B上的小于关系，则R为将A到B的关系记做13:1616定义4.2.3设R是集合A到集合B的二元关系。R的定义域(domain)记作dom(R)，定义为：R的值域(Range)记作ran(R)，定义为：显然有。4.2关系及其表示13:1617例1设A={a,b,c}，B={2,5,8}，则令，则R和S均是由A到B的关系，且4.2关系及其表示例2设A={2,3,5}，B={2,6,7,8,9}，由A到B的关系D定义为：aDb，当且仅当a整除b。于是13:16184.2关系及其表示例3>=，其中R是实数集合。例4设，其中R是实数集合，则则>RR，且dom>=ran>=R.QRR，domQ=R，ranQ=R-R-.13:1619二、几种特殊的关系1.空关系(EmptyRelations)4.2关系及其表示对任意集合A和B，因为AB，AA，所以，是由A到B的关系，也是A上的关系，称为空关系。若集合A为空集，R是A上的任意二元关系，则R是A上的空关系，称为空集合上的空关系。若集合A为非空集合，由于AA，称是非空集合上的空关系。空集合上的空关系与非空集合上的空关系是不同的。13:1620二、几种特殊的关系1.空关系(EmptyRelations)4.2关系及其表示举例姐弟关系父子关系姐妹关系非空集合上的空关系姐弟关系父子关系空集合上的空关系13:16214.2关系及其表示2.全域关系(TotalFieldRelations)因为ABAB，所以AB是一个由A到B的关系，称为由A到B的全域关系。在某些 书 关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf 上，常将AA记作和AA也称为平凡关系(TravialRelations)13:16224.2关系及其表示3.恒等关系集合A上的恒等关系，定义为：IA是A上的恒等关系。例5设A={a,b,c}，则是A上的全域关系。IA=13:1623三、关系的表示1.集合表示法例6设A={2,3,4,8}，B={1,5,7}，用描述法定义由A到B的关系，试用列举法将R表示出来。解4.2关系及其表示用表示集合的列举法或描述法来表示关系。13:1624例7有王、张、李、何是某校的老师，该校有三门课程：语文、数学和英语，已知王可以教语文和数学，张可以教语文和英语，李可以教数学，何可以教英语,若记A={王，张，李，何}，B={语文，数学，英语}。那么这些老师与课程之间的对应关系就可以用由A到B的一个关系R中的序偶来表示。R={〈王,语文〉,〈王,数学〉,〈张,语文〉,〈张,英语〉,〈李,数学〉,〈何,英语〉}4.2关系及其表示13:16254.2关系及其表示2.矩阵表示法定义4.2.4设A、B都是有限集，A={a1,a2,am},B={b1,b2,,bn}，由A到B的关系R可以用一个mn的矩阵(Matrix)MR来表示，MR的第i行第j列的元素rij取值如下：矩阵MR称为R的关系矩阵。13:16261574.2关系及其表示例7设A={2,3,4,8}，B={1,5,7}，则R的关系矩阵如下：13:1627例8设A={1,2,3,4}，A上的关系R的关系矩阵为：1234求R及R的关系矩阵。解4.2关系及其表示13:1628例9设A={1,2,3,4}，求A上的空关系、恒等关系IA和全域关系UA的关系矩阵。解4.2关系及其表示13:1629关系图由结点和边组成。4.2关系及其表示3.关系图表示法例10设A={2,3,4,8}，B={1,5,7}，则R的关系图如下：2348157AB13:1630例11设A={1,2,3,4}，A上的关系R的关系图为：求R及R的关系图。解12344.2关系及其表示13:1631例12设A={1,2,3,4}，画出A上的空关系、恒等关系IA和全域关系UA的关系图。解4.2关系及其表示1234IA1234UA123413:1632四、小结4.2关系及其表示本节介绍了关系的定义、几种特殊的关系及关系的表示。重点掌握关系的表示方法。13:163333离散数学(DiscreteMathematics)13:1634集合A上关系的性质4.3关系的性质举例小结13:1635一、集合A上关系的性质定义4.3.1设R是集合A上的关系。4.3关系的性质(1)若对于所有的aA，均有aRa，则称R在A上是自反的(Reflexive)。即R在A上自反a(aAaRa)关系图特点：关系矩阵特点：每个结点都有自回路。对角线元素均为1。13:1636(2)若对于所有的aA，均有，则称R在A上是反自反的(Antireflexive)。一、集合A上关系的性质定义4.3.2设R是集合A上的关系。4.3关系的性质即R在A上反自反a(aA)关系图特点：关系矩阵特点：每个结点都没有自回路。对角线元素均为0。U自反反自反(若U非空)自反与反自反之间的关系：13:1637关系图特点：一、集合A上关系的性质定义4.3.3设R是集合A上的关系。4.3关系的性质即R在A上对称ab(aAbAaRbbRa)(3)对于所有的a,bA，若每当有aRb就必有bRa，则称R在A上是对称的(Symmetric)。关系矩阵特点：对称矩阵。每对结点之间若有定向弧线，一定是成对出现的。13:1638关系图特点：一、集合A上关系的性质定义4.3.4设R是集合A上的关系。4.3关系的性质关系矩阵特点：每对结点之间的定向弧线，一定不是成对出现的。(4)对于所有的a,bA，若每当有aRb和bRa，就必有a=b，则称R在A上是反对称的(Antisymmetric)。即R在A上反对称ab(aAbAaRbbRaa=b)关于对角线对称的两个元素不能同时为1。13:1639对称与反对称之间的关系：一、集合A上关系的性质定义4.3.5设R是集合A上的关系。4.3关系的性质(4)对于所有的a,bA，若每当有aRb和bRa，就必有a=b，则称R在A上是反对称的(Antisymmetric)。即R在A上反对称ab(aAbAaRbbRaa=b)U对称不反对称反对称不对称既对称又反对称13:1640一、集合A上关系的性质定义3-4.1设R是集合A上的关系。4.3关系的性质(5)对于所有的a,b,cA，若每当有aRb和bRc，就必有aRc，则称R在A上是可传递的(Transitive)。即R在A上可传递abc(aAbAcAaRbbRcaRc)关系图特点：若两个结点之间有路，则一定有一条长度为1的路。感谢谢谢，精品 课件 超市陈列培训课件免费下载搭石ppt课件免费下载公安保密教育课件下载病媒生物防治课件 可下载高中数学必修四课件打包下载 资料搜集