离散数学 郝晓燕 第4章 关系

《离散数学 郝晓燕 第4章 关系》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章关系§4-1关系的概念及表示定义4-1.1给定任意集合A和B，若RAB，则称R为从A到B的二元关系，当A=B时，称R为A上的二元关系。R，读作“x对y有关系R”，可表示为xRy,即RxRy。若R，读作“x对y无关系R”，可表示为xRy，即RxRy特别地，若R=，称R为A到B上的空关系；若R=AB，称R为A到B上的全域关系；若R={

2、xA}，称R为A上的恒等关系，记为IA举例1)老师集合﹛李老师，张老师，王老师﹜到课程集合﹛

3、数学，英语，物理，化学﹜的任课关系：﹛﹤李老师,物理﹥，﹤李老师,化学﹥，﹤张老师,数学﹥，﹤王老师,英语﹥﹜2)一个学生的各课程的成绩：﹛﹤物理，90﹥，﹤化学，80﹥，﹤数学，95﹥，﹤英语，85﹥﹜是课程集合﹛数学，英语，物理，化学﹜到分数集合﹛1，2，…，99，100﹜的得分关系。3)集合﹛2，3，4，5﹜上的小于关系﹛﹤2，3﹥，﹤2，4﹥，﹤2，5﹥，﹤3，4﹥，﹤3，5﹥，﹤4，5﹥﹜4)集合﹛2，3，4，5﹜上的整除关系﹛﹤2，2﹥，﹤2，4﹥，﹤3，3﹥，﹤4，4﹥，﹤5，5﹥﹜例

4、4-1.1集合B={a，b}，A=P(B)，求B上的恒等关系和A上的包含关系。解：B上的恒等关系IB={，};A=P(B)={，{a}，{b}，{a，b}}，则A上的包含关系R={<，>，<，{a}>，<，{b}>，<，{a，b}>，<{a}，{a}>，<{a}，{a，b}>，<{b}，{b}>，<{b}，{a，b}>，<{a，b}，{a，b}>}例4-1.2集合A={a，b}，B={c，d}，试写出从A到B的所有不同关系。解：A×B={，，

5、，c>，}。于是A×B上的所有16个不同的关系：关系中包含0个元素：；关系中包含1个元素：{}，{}，{}，{}；关系中包含2个元素：{，}，{，}，{，}，{，}，{，}，{，}；关系中包含3个元素：{，，}，{，，}，{，，}，{

6、>，，}；关系中包含4个元素：{，，，}。思考：有限集合A包含n个元素，B包含m个元素，从A到B的不同关系共有多少个？§4-1-2关系的表示方法(1)列举法:列出关系的所有序偶.如老师集合﹛李老师，张老师，王老师﹜到课程集合﹛数学，英语，物理，化学﹜的任课关系﹛﹤李老师,物理﹥，﹤李老师,化学﹥，﹤张老师,数学﹥，﹤王老师,英语﹥﹜(2)描述法:描述出关系中序偶的两个元素所具有的性质.如X＝﹛2，3，4，5﹜上的整除关系:D＝﹛﹤x，y﹥

7、

8、xX∧yX∧y能被x整除﹜.有理数集合Q上的倒数关系:T＝﹛﹤x，y﹥

9、x,yQ∧x,y0∧xy＝1﹜.X上的相等关系:Ix＝﹛﹤x，x﹥

10、xX﹜.(3)关系矩阵:X＝﹛x1,x2,…,xn﹜到Y=﹛y1,y2,…,ym﹜的关系R的关系矩阵为MR＝(aij)n×m其中aij＝(4)关系图:X＝﹛x1,x2,…,xn﹜到Y＝﹛y1,y2,…,ym﹜的关系R的关系图为：分别在左右两列用小圆圈列出的X中的n个元素和Y中的m个元素，若xiRyj，则从xi到yj画一条有向边。如右图所示X＝﹛x1,x

11、2,…,xn﹜上的关系图为：在平面上用小圆圈列出的X中的n个元素（位置不限），若xiRXj,则从xi到xj画一条有向边。如左图所示x1x2x3xny1y2ynx1x2xn﹕﹕1,若xiRyj0,若xiRyjXYR的关系矩阵MR为1000100101010011举例X＝﹛a,b,c,d﹜上的关系R＝﹛﹤a,a﹥,﹤b,a﹥,﹤b,d﹥,﹤c,b﹥,﹤c,d﹥，﹤d,c﹥,﹤d,d﹥﹜abcdR的关系图为§4-2关系的性质设R是集合X上的关系（1）R是自反的对任意的xX，有xRx.(定义)R的关

12、系矩阵中主对角线全为1（当X是有限集合）。R的关系图中每个顶点处均有自环（当X是有限集合）。（2）R是反自反的对任意的xX，有xRx.(定义)R的关系矩阵中主对角线全为0（当X是有限集合）。R的关系图中每个顶点处均没有自环（当X是有限集合）。（3）R是对称的(x)(y)(x，y∈X∈R→∈R)R的关系矩阵是对称矩阵（当X是有限集合）。R的关系图中任两个顶点间若有边则必有两条方向相反的边（当X是有限集合）。（4）R是反对称的(