离散数学课件第四章(第1讲)

《离散数学课件第四章(第1讲)》由会员分享，可在线阅读，更多相关《离散数学课件第四章(第1讲)（28页珍藏版）》请在装配图网上搜索。

1、 第四章第四章二元关系二元关系1 序偶与笛卡尔积2 关系及其表示3 关系的性质4 关系的运算5 等价关系与划分6 相容关系与覆盖7 偏序关系1 序偶与笛卡尔乘积序偶与笛卡尔乘积 1 序偶序偶定义定义由二个具有给定次序的客体所组成的序列由二个具有给定次序的客体所组成的序列称为序偶。记作称为序偶。记作x，y 例：例：XY二维平面上的一个点的坐标二维平面上的一个点的坐标x，y就就是一个序偶。是一个序偶。说明：说明：(1)在序偶中二个元素要有确定的排列次序。在序偶中二个元素要有确定的排列次序。若若a b时，则时，则a，b b，a 若若x，y=a，b（x=a y=b）(2)多重序元：多重序元：三元组：三

2、元组：x，y，z=x，y，z n元组：元组：x1，x2，x3，xn=x1,xn2 笛卡尔乘积笛卡尔乘积定义定义设设A，B为二个任意集合，若序偶的第为二个任意集合，若序偶的第一个成员（左元素）是一个成员（左元素）是A的一个元素，序偶的的一个元素，序偶的第二个成员（右元素）是第二个成员（右元素）是B的一个元素，则所的一个元素，则所有这样的序偶有这样的序偶构成构成的集合称为的集合称为A和和B的笛卡尔乘的笛卡尔乘积。积。记作：记作：A B=x，y|（x A）（y B）例：设例：设A=1，2，B=a，b，则：，则：A B=1，a,1，b,2，a,2，b B A=a，1,a，2,b，1,b，2 A B B

3、 A，即即“”是不满足交换律。是不满足交换律。例：设例：设A=a，b，B=1，2，C=z,则则:(A B)C=a,1,a,2,b,1,b,2 z =a,1,z,a,2,z,b,1,z,b,2,z A (B C)=a，b 1,z,2,z=a,1,z,a,2,z,b,1,z,b,2,z（A B）C A （B C）,“”不满足结合律。不满足结合律。定理定理若若A A，B B，C C是三个集合，则有：是三个集合，则有：A A（B CB C）=（A A B B）（A A C C）A A（B CB C）=（A A B B）（A A C C）（A BA B）C=C=（A A C C）（B B C C）（A

4、BA B）C=C=（A A C C）（B B C C）证明证明:A(B C)=(A B)(A C)证明：设证明：设是是A（B 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 C)=(A B)(A C)例：设例：设A=1，B=1，2，C=2，3,则则 A（B C）=1 1，2，3 =1,1,1,2,1,3（A B）（A C）=1 1，2 1 2，3 =1,1,1,2,1,3 例：设例：设A=1，B=1，2，C=2，3,则：则：A（B C）=1 2=1,2（A B）（A C）=

5、1,1,1,2 1,2,1,3 =1,2 注：注：n个集合的笛卡儿乘积的定义个集合的笛卡儿乘积的定义：A2=A AA3=A A AAn=A A An个个A2 关系及其表示关系及其表示1 关系关系 定义：指事物之间（客体之间）的相互联系。定义：指事物之间（客体之间）的相互联系。在数学上关系可表达集合中元素间的联系。在数学上关系可表达集合中元素间的联系。序偶序偶a，b可以反映可以反映a，b二个元素之间具有某二个元素之间具有某 种关系。种关系。定义定义以序偶作为元素的任何集合是一个二元关系。以序偶作为元素的任何集合是一个二元关系。由定义可知：二元二元关系是一个集合。设设R表示二元关系，表示二元关系，

6、若若 R,用用 xRy 表示，表示，若若 R，则也可写成：，则也可写成：x R y。关系表示方法关系表示方法（1）枚举法（列举法）枚举法（列举法）例：二元关系例：二元关系R定义如下图：定义如下图：可用枚举法表示为：可用枚举法表示为：,4,3,2,1dcbaR（2 2）谓词公式表示法）谓词公式表示法 一个集合可用谓词公式来表达，所以二元关系一个集合可用谓词公式来表达，所以二元关系也可用谓词公式来表达。也可用谓词公式来表达。例：实数集合例：实数集合R R上的上的“”关系可表达为：关系可表达为：“”=”=)(|,yxRyRxyx（3 3）关系矩阵表示法）关系矩阵表示法 设二元关系设二元关系 R R

7、是是A B上的二元关系，上的二元关系，关系矩关系矩阵表示法描述如下：阵表示法描述如下：(a)(a)集合集合A A中的元素表示矩阵的行元素，集合中的元素表示矩阵的行元素，集合B B中的中的元素表示矩阵的列元素；元素表示矩阵的列元素；(b)(b)若若 R ，则在关系矩阵对应位置记上，则在关系矩阵对应位置记上“1”1”，否则记为，否则记为“0”0”。例：设例：设A=aA=a，b b，cc，B=1 B=1，3 3，44，R R1 1 是是ABAB上的上的二元关系，给出二元关系，给出R R1 1的关系矩阵的关系矩阵.R R1 1=abc134101110MR1=1102,1,2,1,2,1,2ccbba

8、aYXR例：设例：设X=aX=a，b b，cc，Y=1 Y=1，22，R R2 2 是是XYXY上上的二元关系，的二元关系，给出给出R R2 2的关系矩阵的关系矩阵.例：设例：设X=aX=a，b b，cc，Y=1 Y=1，22，R R3 3 是是X YX Y上的二元关系且上的二元关系且R R3 3=，给出给出R R3 3的关系矩阵的关系矩阵.例：设X=1，2，3，4，R R4 4 是是X X X X上的二元关上的二元关系系，给出，给出R R4 4的关系矩阵的关系矩阵.R4=100110M R4 =1110000000（4）关系图表示法）关系图表示法设设R为集合为集合XYXY上的二元关系，上的二

9、元关系，关系矩阵图表示法描述如下：关系矩阵图表示法描述如下：(a)把集合、中的元素以点的形式全部画在平面上；把集合、中的元素以点的形式全部画在平面上；(b)若若 R ，则在，则在x和和y之间画一带箭头弧线，其箭头指之间画一带箭头弧线，其箭头指向向y。反之不画任何联线。反之不画任何联线。例：设例：设X=1X=1，2 2，3 3，44，R R1 1 是是X X 上的二元关系，上的二元关系，给出给出R R1 1的关系图。的关系图。R1=.关系的前域和值域关系的前域和值域 定义定义设设R是一个二元关系，由是一个二元关系，由 R的所有序偶的的所有序偶的第一元素第一元素x组成的集合组成的集合dom R称称

10、R的前域的前域,即即),(|RyxyxdomR定义定义 R R的前域和值域的并集称做的前域和值域的并集称做R R的域的域,记做记做FLD R,FLD R,即即:FLD R=:FLD R=domdom R R ran R ran R定义定义设设R是一个二元关系，由是一个二元关系，由 R的所有序偶的的所有序偶的第二元素第二元素y组成的集合组成的集合ran R称称R的值域的值域,即即,(|RyxxyranR例：例：X=1,2,3,4,5,6,Y=X=1,2,3,4,5,6,Y=a,b,c,d,e,fa,b,c,d,e,f,R,R为为X X到到Y Y的的二元关系二元关系.,4,3,2,1dcbaRdo

11、mdom R=1,2,3,4 R=1,2,3,4ran R=ran R=a,b,c,da,b,c,d FLD R=1,2,3,4,a,b,c,dFLD R=1,2,3,4,a,b,c,d关系和笛卡尔乘积关系和笛卡尔乘积笛卡尔乘积的任何子集都可以定义一种二元关系。笛卡尔乘积的任何子集都可以定义一种二元关系。例：X=1,2,3,4，Y=1,2 2,41,1|,22yxYyXxyxS思考：思考：集合集合XY上可以产生多少种二元关系？上可以产生多少种二元关系？2,4,1,4,2,3,1,3,2,2,1,2,2,1,1,1YXS1,S2都是XY的子集，并且它们二元关系。S1=|x X y Y x y=三

12、个特殊关系：全域关系，空关系，恒等关系三个特殊关系：全域关系，空关系，恒等关系定义定义集合集合A2定义了定义了A集合中的一种关系，该关系集合中的一种关系，该关系称为称为 A中的全域关系，用中的全域关系，用EA表示：表示：,|,AEAAx yxA yA 例：例：A=1，2,则集合则集合A上的全域关系为：上的全域关系为：E EA A=定义定义空集也是空集也是 AxA的一个子集，它也定义了一的一个子集，它也定义了一种关系种关系,称为空关系，用称为空关系，用A表示。表示。例：例：A=1，2,则集合则集合A上的空关系为：上的空关系为：A=定义定义：集合：集合A A中的恒等关系，用中的恒等关系，用I IA A表示：表示：思考：集合思考：集合A=1,2,R为为AXA上的恒等关系，则上的恒等关系，则R如如何表示？何表示？I IA A=|x x A A 例：例：A=1,2,3,4,则集合则集合A上的恒等关系为：上的恒等关系为：I IA A=