离散数学 第2版 教学课件 作者 王元元 离散第26讲 关系及其运算.ppt

《离散数学 第2版 教学课件 作者 王元元 离散第26讲 关系及其运算.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机专业基础课程授课人：王元元单位：计算机理论教研室理工大学指挥自动化学院PowerPointTemplate_Sub1二元关系2等价关系3序关系2第26讲关系及其运算关系及其运算《离散数学》第26讲Page156to164引言“关系”——事物之间的联系人与人之间：父子关系、朋友关系、师生关系数与数之间：大于关系、小于关系、整除关系…集合与集合之间：包含关系元素与集合之间：隶属关系命题与命题之间：逻辑等价关系、逻辑蕴涵关系程序与程序之间：调用关系宇宙万物之间充满了各种各样的关系怎样为关系建立数学模型？P(x,y):x,y有关系P；x,y有图G所示关系xyG4第26讲关系

2、及其运算回顾：序偶和集合的笛卡儿积由两个具有固定次序的客体组成的序列，称为序偶，记作其中x称为序偶的第一分量，y称为序偶的第二分量=当且仅当x=a,y=b对任意集合A，B，它们的笛卡尔积是由所有以A中元素为第一分量，B中元素为第二分量的序偶组成的集合AB={

3、xA∧yB}笛卡尔坐标系是实数集合与实数集合的笛卡尔积5第26讲关系及其运算集合论中的关系模型集合论将关系刻画为一个序偶的集合，所有具有这种关系的对象组成的序偶都是集合的成员例如，A={a,b,c}表示人的集合，B={u,v,w}表示城市的集合人和出生城市之间的关系可表示

4、为：R1={,,}人和旅游到过的城市之间的关系可表示为：R3={,,,,,}关系通过列举外延来描述事物之间的联系，由此可以方便地利用集合论的概念、研究方法和研究结论6第26讲关系及其运算关系的基本概念定义：设A，B是集合，其笛卡儿积AB的子集R称为A到B的一个二元关系。若A=B，则称R为A上的二元关系除了二元关系外，还有三元关系，四元关系……注意点：关系仍是一个集合，其元素为序偶R，可表示为aRb，反之可表示为┐aRb从集合A到B有多少个关系？2

5、A

6、×

7、B

8、(

9、A

10、=

11、m,

12、B

13、=n时,A到B有2mn个关系){y=2x+5}是实数域上的一个线性关系{x2+y2=1}是实数域上的一个圆关系7第26讲关系及其运算与关系有关的一些术语设A，B为集合，R是A到B的一个关系，即RA×BA为R的前域B为R的陪域R中各元素的第一分量所组成的集合称为R的定义域，记成Dom(R)，即Dom(R)={x

14、xA∧y(yB∧R)}R中各元素的第二分量所组成的集合称为R的值域，记成Ran(R)，即Ran(R)={y

15、yB∧x(xA∧R)}A={1,2,3}，B={,,γ}，R={<1,>,<1,

16、γ>,<2,γ>}A={1,2,3}是R的前域，B={,,γ}是R的陪域Dom(R)={1,2}，Ran(R)={,γ}Dom(R)A，Ran(R)B8第26讲关系及其运算关系的表示方法列举法R:人与出生地的关系，R={,,}描述法R:人与出生地的关系，R={

17、xA∧yB∧x出生于y}或R={

18、xA∧yB∧P(x,y)}其中P(x,y)表示“x出生于y”9第26讲关系及其运算关系的表示方法归纳定义R:自然数集合上的小于关系列举法R={<0,1>,<0,2>,<0,3>,…,<1,2>,<1,3>,<1,4

19、>,…,……,,,,…,……}描述法：R={

20、xA∧yB∧x-y为负数}（a）基础条款：<0,1>R（b）归纳条款：如果R，那么R,R（c）终极条款（略）。10第26讲关系及其运算关系的特殊表示方法关系图A={a,b,c,d}B={u,v,w}R1={,,}A={a,b,c,d,e}，R2={,,,,}cdabeaABudbcvwcABaubwvd11第26讲关系及其运算关系的表示方法关系

21、矩阵定义：给定二个有限集合A={a1,a2,…,am}，和B={b1,b2,…,bn}，R是A到B的二元关系，则MR=(rij)mn叫做R的关系矩阵，其中1当R时0当R时rij=A={1,2,3,4}，R是A上的关系，且R={<4,1>,<4,2>,<4,3>,<3,1>,<3,2>,<2,1>}12第26讲关系及其运算集合A上三个特殊的二元关系给定集合A，

22、A

23、=n，A上共有2nn个不同的二元关系，其中AA，故是A上的一个关系，称为A上的一个空关系AA也是A上的一个关系，称为A上