离散数学 课件 ch7.ppt

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

1、主要内容有序对与笛卡儿积二元关系的定义与表示法关系的运算关系的性质关系的闭包等价关系与划分偏序关系第七章二元关系17.1有序对与笛卡儿积定义7.1由两个元素x和y，按照一定的顺序组成的二元组称为有序对，记作.有序对性质:(1)有序性（当xy时）(2)与相等的充分必要条件是=x=uy=v.2笛卡儿积定义7.2设A,B为集合，A与B的笛卡儿积记作AB，且AB={xAyB}.例1A={1,2,3},B={a,b,c}AB={<1,a>,<

2、1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>}BA={,,,,,,,,}A={},B=P(A)A={<,>,<{},>}P(A)B=3笛卡儿积的性质(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)(

3、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=m,B=n,则AB=mn4性质证明证明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).5实例例2(1)证明A=B,C=D

4、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.67.2二元关系定义7.3如果一个集合满足以下条件之一：(1)集合非空,且它的元素都是有序对(2)集合是空集则称该集合为一个二元关系,简称为关系，记作R.如果∈R,可记作xRy；如果R,则记作xy实例：R={<1,2>,},S={<1,2>,a,b}.R是

5、二元关系,当a,b不是有序对时，S不是二元关系根据上面的记法，可以写1R2,aRb,ac等.7A到B的关系与A上的关系定义7.4设A,B为集合,A×B的任何子集所定义的二元关系叫做从A到B的二元关系,当A=B时则叫做A上的二元关系.例3A={0,1},B={1,2,3},那么R1={<0,2>},R2=A×B,R3=,R4={<0,1>}R1,R2,R3,R4是从A到B的二元关系,R3和R4也是A上的二元关系.计数:A=n,A×A=n2,A×A的子集有个.所以A上有个不同的二元关系.例如A=3,则A上有=512个不同的二元关

6、系.8A上重要关系的实例定义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是集合族.9实例例如,A={1,2},则EA={<1,1>,<1,2>,<2,1>,<2,2>}IA={<1,1>,<2,2>}例如A={1,2,3},B={a,b},则LA={<1,

7、1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>}DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}例如A=P(B)={,{a},{b},{a,b}},则A上的包含关系是R={<,>,<,{a}>,<,{b}>,<,{a,b}>,<{a},{a}>,<{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>}类似的还可以定义：大于等于关系,小于关系,大于关系,真包含关系等.10关系的表示1.关系矩阵若A={x1,x2,…,xm}，B={y1,y2,

8、…,yn}，R是从A到B的关系，R的关系矩阵是布尔矩阵MR=[rij]mn,其中rij=1R.2.关系图若A={x1,x2,…,xm}，R是从A上的关系，R的关系图是GR=,其中A为结点集，R为边集.如果