离散数学 关系ppt课件

1、123456789 把学生选课表用集合来表示：把学生选课表用集合来表示：R= 张三张三,离散数学离散数学, 李四李四,微积分微积分, 张三张三,高级言语高级言语, 序偶的集合序偶的集合R同样也描写了学生集合同样也描写了学生集合A=张三，李四，张三，李四，与课程集合与课程集合B=离散离散数学，微积分，高级言语，数学，微积分，高级言语，之间之间“多值对应的联络。多值对应的联络。1011121314151617181920 2. 关系矩阵关系矩阵 ：由表格法笼统而来：由表格法笼统而来 【定义】设集合【定义】设集合Ax1,x2,xm, By1,y2, yn, R是从是从A到到B的关系的关系, 那么那么

2、mn矩阵矩阵MR(mij) mn叫叫R的关系矩阵的关系矩阵, 其中其中:1,(,)0 ,(,)ijijijifxyRmifxyR 21 【例】【例】 设设A1,2,3,4,5, Ba,b,c,求下面两个关系的关系矩阵。求下面两个关系的关系矩阵。 A到到B的关系的关系: R1(1,a),(1,b),(2,b),(3,a) B到到A的关系的关系: R2(a,2),(c,4),(c,5)221,0,ijijijifa aRmifa aR 【例】 求A1, 2, 3, 4上的关系、 EA和IA的关系矩阵。 23.),()(fyxyxf).3 ,(),3 ,(),2 ,(cbaf ?)3 ,(),3 ,

3、(),2 ,(caa242526:,BASR, ,RS RS R RS RS.RBARBAR.RAARAAR2728293031RRB32333435 【定理【定理2-2】 【定理【定理2-3】 (1) (2) (3) R是是A上的关系上的关系, 那么那么11()RR111()RSRS111()RSRS 11RR3637383940R S 411112211nnRmmnm nuuuuMuu 其中：其中：iju 421112211ssSnnsn svvvvMvv 其中：其中：ijv 431112211ssR Smmsm swwwwMww 44451 0 01 1 0 01 1 11 1 1 0

4、1 0 0 1 1 10 0 00 0 1 00 0 00 0 0R SRSMMM 461 1 1 01 1 1 01 1 1 10 0 1 10 0 1 11 0 1 0 0 0 0 00 0 0 00 0 0 00 0 1 10 0 1 11 0 1 0R SRSMMM 47 二元关系与其关系矩阵是一一对应的，复合关系RS的关系矩阵等于R的关系矩阵与S的关系矩阵的乘积，而矩阵的乘法运算满足结合律，所以关系的复合也满足结合律，即： 48设设 R AB，那么：，那么： (1) IA R = R (2) R IB = R4950515253545556575859 【例】 设A1,2,3, R1

5、 , R2 , R3 , R4是A上的关系，其中 R1(1, 1), (2, 2) R2(1, 1), (1, 2), (2, 1) R3(1,2), (1, 3) R4(1,2), (2,1), (1, 3) 阐明它们能否为A上的对称关系或反对称关系。 60616263646566676869703abZ 7172737475767778798081828384858687888990919293949596979899100101102103104105106107108109为了更清楚地表示偏序集中元素间的一种层次关系为了更清楚地表示偏序集中元素间的一种层次关系, 我们引入哈斯图我们引入哈斯图(Hasse图图) 。 11011111211311411511611711811