jhy-第四章 二元关系.ppt

第四章二元关系
二元关系是一个很重要的概念,它在很多数学领域中
都有应用,在计算机科学的如下理论都离不开关系:
逻辑设计、数据结构、编译原理、软件工程
数据库理论、计算理论、算法分析、操作系统等
本章主要介绍:
关系的概念及表示方法
关系的性质
关系的运算: 关系的复合, 逆关系, 关系的闭包
三种重要关系: 等价关系, 相容关系, 次序关系
1
4-1 序偶与集合的笛卡尔积
“序偶”概念以前已经用过。
例如,用序偶表示平面直角坐标系
中一个点(a,b)。
设x表示上衣,y表示裤子,
(x,y)可以表示一个人的着装。

:由两个对象x、y组成的序列称为有序二元组,也
称之为序偶,记作<x,y>;称x、y分别为序偶<x,y>的第
一,第二元素。
注意,序偶<x,y>与集合{x,y}不同:
序偶<x,y>:元素x和y有次序;
集合{x,y}:元素x和y的次序是无关紧要的。
x
y
0
•(a,b)
a
b
2
:设<x,y>,<u,v>是两个序偶,如果
x=u和y=v,则称<x,y>和<u,v>相等,
记作<x,y>=<u,v>.
3 .定义:有序3元组是一个序偶,其第一个元素也是个序偶。
有序3元组<< a,b>, c>可以简记成<a,b,c>。
但<a,<b,c>>不是有序3元组。
:有序n元组是一个序偶,其第一个元素本身是个有
序n-1元组,记作<<x1 , x2 ,, xn-1>, xn>。且可以简记成
<x1 , x2 ,, xn-1, xn>。
5. 定义: <x1, x2 ,, xn>=<y1 , y2 ,·, yn>
( x1= y1)( x2= y2) ( xn= yn)
3

例如“斗兽棋”的16颗棋子:
虎
象
狮
豹
狼
鼠
猫
狗
虎
象
狮
豹
狼
鼠
猫
狗
可看成是由两种颜色的集合A和8种动物的集合B组成的。
A={红,蓝}
B={象,狮,虎,豹,狼,狗,猫,鼠}
每个棋子可以看成一个序偶,斗兽棋可记成集合AB :
{<红,象>,<红,狮>,<红,虎>,<红,豹>,<红,狼>,<红,狗>,<红,猫>,<红,鼠>,
<蓝,象>,<蓝,狮>,<蓝,虎>,<蓝,豹>,<蓝,狼>,<蓝,狗>,<蓝,猫>,<蓝,鼠> }
4
:设A、B是集合,由A的元素为第一元素,
B的元素为第二元素组成序偶的集合,称为A和B
的笛卡尔积,记作A×B,即
AB={<x,y>|xA∧yB}
例1 设A={0,1},B={a,b},求AB , BA,
AA 。
解: AB={<0,a>,<0,b>,<1,a>,<1,b>}
BA={<a,0 >,<b,0>,<a,1>,<b,1>}
AA={<0,0>,<0,1>,<1,0>,<1,1>}
可见 A×B≠B×A
所以,集合的笛卡尔积运算不满足交换律。
5
另外
(AB)C={<<a,b>,c>|<a,b>AB cC}
A(BC)={<a,<b,c>>|aA <b,c>BC},
因<a,<b,c>>不是有序三元组,
所以(AB)CA(BC)。
故也不满足结合律。

1) 如果A、B都是有限集,且|A|=m, |B|=n,则
|AB |=mn.
证明:由笛卡尔积的定义及排列组合中的乘法原
理,直接推得此定理。
2) AΦ=ΦB=Φ
6
3) 对∪和∩满足分配律。
设A,B,C是任意集合,则
⑴ A(B∪C)= (AB)∪(AC);
⑵ A(B∩C)= (AB)∩(AC);
⑶(A∪B)C= (AC)∪(BC);
⑷(A∩B)C= (AC)∩(BC)
证明⑴:任取<x,y>A(B∪C)
xA yB∪C xA (yB∨yC)
( xA yB)∨(xAyC)
<x,y>AB∨<x,y>AC
<x,y>(AB)∪(AC) 所以⑴式成立。
其余可以类似证明。
7
4)若C,则
AB(ACBC) (CACB).
证明: 必要性: 设AB,求证 ACBC
任取<x,y>AC xAyC
xByC (因AB)
<x,y>BC 所以, ACBC.
充分性: 若C, 由ACBC 求证 AB
取C中元素y, 任取 xAxAyC
<x,y>AC
<x,y>BC (由ACBC )
xB