离散数学（第二版） 课件 邹丽娜 5 二元关系1

离散数学第5章二元关系引例:设一旅馆内有n个房间，每个房间可住两个旅客，共可以住2n个旅客。在旅馆内，旅客与房间有一定关系。讨论关系：“某旅客住在某房间”---R为讨论方便起见，设n=3，表示有3个房间分别记为1，2，3；此时共住6个人，分别记为a、b、c、d、e、f

ab1cd2ef3二元关系a与1间存在关系R，记为aR1b与1间存在关系R，记为bR1

……f与3间存在关系R，记为fR3因此满足R的所有关系有：aR1，bR1，cR2，dR2，eR3，fR3

ab1cd2ef3二元关系由此可以看出：（1）满足R的关系pRq,可以看成是一个有序偶<p，q>（2）满足R的所有关系可看成是一个有序偶的集合，这个集合称为关系R。

如此例中

R={<a，1>，<b，1>，<c，2>，<d，2>，<e，3>，<f，3>}（3）这里R是二元关系。还可类似定义三元、四元关系（4）若令A={a，b，c，d，e，f}

B={1，2，3}则R中的每一个元素均属于AxB，即R

AxB，此时称关系R是从A到B的关系。二元关系有序对有序n元组笛卡儿积笛卡儿积

笛卡儿积的性质

笛卡儿积练习n重笛卡儿积

二元关系关系关系说出R1到R5分别属于A到B上的关系，还是B到A上的关系，还是A上的关系，还是B上的关系。关系关系例

设A=

1,2,3,4

,试列出下列关系R的元素。(1)R=

<x,y>

x是y的倍数

(2)R=

<x,y>

(x－y)2

A

(3)R=

<x,y>

x/y是素数

(4)R=

<x,y>

x

y

(5)R=

<x,y>

x

y

解:(1)R={<4,4>,<4,2>,<4,1>,<3,3>,<3,1>,<2,2>,<2,1>,<1,1>}(2)R={<2,1>,<3,2>,<4,3>,<3,1>,<4,2>,<2,4>,<1,3>,<3,4>,<2,3>,<1,2>}(3)R={<2,1>,<3,1>,<4,2>}(4)R=EA-IA={<1,2>,<1,3>,<1,4>,<2,1>,<2,3>,<2,4>,<3,1>,<3,2>,<3,4>,<4,1>,<4,2>,<4,3>}(5)R={<1,2>,<1,3>,<1,4>,<2,3>,<2,4>,<3,4>}习题练习关系的矩阵的表示法关系R的矩阵用MR表示，关系中的有序偶<ai,aj>用1表示，即若aiRaj，有aij=1，其余用0表示。说明：有多少个关系就有多少个1a1a2a3a4a1

a2

a3

a4关系的表示方法：集合、矩阵、图表示法。关系的图的表示法集合A={a1，a2，…an}上的关系R可用关系图表示。图中的结点---集合中的元素图中从ai到aj的有向边---关系中的有序偶<ai，aj>例题：设集合A={a1，a2，a3，a4，a5，a6}

关系R={<a1,a2>，<a3,a4>，<a4,a5>，

<a5,a2>，<a2,a6>，<a3,a1>,<a1,a1>}。关系图为：a1a6a2a5a3a4abcdabcd已知集合A={a,b,c,d}，则EA、IA的矩阵dabcR0abcdabcd关系的定义域、值域和域

练习限制：有序对的第一个元素都在A中。像：有序对中的值域。练习例

设R为{<1,2>,<1,3>,<2,2>,<2,4>,<3,2>},则R