离散数学关系的运算

第4章二元关系与函数

?

4.1 集合的笛卡儿积与二元关系?4.2 关系的运算?4.3 关系的性质?4.4 关系的闭包

?4.5 等价关系和偏序关系?4.6 函数的定义和性质(略)?4.7 函数的复合和反函数(略)

1

4.1 集合的笛卡儿积和二元关系

?

有序对

?笛卡儿积及其性质?

二元关系的定义?

二元关系的表示

2

笛卡儿积

定义设A,B为集合，A与B 的笛卡儿积记作A?B，即A?B ={ | x?A ?y?B }例2 A={1,2,3}, B={a,b,c}A?B ={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>, <3,a>,<3,b>,<3,c>} B?A ={,,,,,,, ,} A={?}, P(A)?A={, <{?},?>} 3

笛卡儿积的性质

不适合交换律A?B?B?A(A?B, A??, B??)不适合结合律(A?B)?C?A?(B?C) (A??, B??)对于并或交运算满足分配律

A?(B?C)=(A?B)?(A?C) (B?C)?A=(B?A)?(C?A) A?(B?C)=(A?B)?(A?C) (B?C)?A=(B?A)?(C?A)

若A或B中有一个为空集，则A?B就是空集.

A??=??B=?

若|A|=m, |B|=n,则|A?B|=mn

4

二元关系的定义

定义如果一个集合满足以下条件之一：（1）集合非空, 且它的元素都是有序对（2）集合是空集

则称该集合为一个二元关系, 简称为关系，记作R.如∈R, 可记作xRy；如果?R, 则记作x y实例：R={<1,2>,}, S={<1,2>,a,b}.

R是二元关系, 当a, b不是有序对时，S不是二元关系根据上面的记法，可以写1R2, aRb, a c 等.

5