CH4 二元关系和函数 4 偏序 关系.ppt

《CH4 二元关系和函数 4 偏序 关系.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、离散数学CH4二元关系和函数4偏序关系内容回顾:关系的性质例:A={1,2,3},A上的关系R={〈1,1〉,〈1,2〉,〈2,2〉,〈2,3〉}123自反性反自反性对称性反对称性传递性×××√×内容回顾:关系的性质例:A={1,2,3},A上的关系R={〈1,1〉,〈1,2〉,〈2,2〉}123自反性反自反性对称性反对称性传递性×××√√今日内容：偏序关系偏序关系、偏序集定义可比和盖住的概念有穷集哈斯图的画法最大、最小、极大、极小元、上界、下界、上确界、下确界1、偏序关系定义：设R为非空集合A上的关系，如果R是自反的、反对称

2、的和传递的，则称R为A上的偏序关系，简称偏序，记作≼。如果序偶〈x，y〉属于偏序关系≼，可记作x≼y，读作“x小于等于y“这里的小于等于不是指数的大小，而是指它们在偏序关系中的位置先后例：集合A={1,2}A上的恒等关系IAIA={<1,1>,<2,2>}具有自反、反对称、传递性是偏序关系例：集合A={1,2}幂集P(A)上的包含关系P(A)={,{1},{2},{1,2}}P(A)⊆={<,>,<,{1}>,<,{2}>,<,{1,2}>,<{1},{1}>,<{1},{1,2}>,<{2},{2}>,<{2

3、},{1,2}>,<{1,2},{1,2}>}具有自反、反对称、传递性是偏序关系例：整数集上的小于等于关系R≤是偏序关系证明：1.证自反性对x∈整数集，因为x≤x，根据定义则∈R≤。所以R≤满足自反性2.证反对称性已知对x，y∈整数集（x≠y），如果∈R≤，即x≤y，则y≤x肯定不成立，即不属于R≤。所以R满足反对称性3.证传递性对x，y，z∈整数集，如果，∈R≤，根据定义有x≤y,y≤z，可得x≤z即：∈R≤。所以R满足传递性R≤具有自反、反对称、传递性,所以

4、R≤为偏序关系2、偏序集定义：一个集合A和A上的偏序关系R一起叫做偏序集，记作〈A，R〉。例如,〈Z，R≼〉,〈P(A)，R〉都是偏序集,其中R≼表示通常的数的小于等于关系R表示集合的包含关系3、可比、盖住定义：设〈A，≼〉为偏序集，对于任意的x，y∈A，如果x≼y或者y≼x成立，则称x与y是可比的;如果x≺y（即x≼y∧x≠y），且不存在z∊A使得x≺z≺y，则称y盖住x例:是偏序集,其中A={1,2,3,4},≼是整除关系≼={<1,1>,<1,2>,<1,3>,<1,4>,<2,2>,<2,4>,<3,3>

5、,<4,4>}1和1,2,3,4,都是可比的2和3是不可比的(2不能整除3,3也不能整除2)2盖住1(因为1整除2，并且不存在z∊A使得1整除z并且z整除2）同样，有4盖住2但4不盖住1，因为有1≼2≼4成立4、哈斯图（有穷偏序集的描述）-----简化的关系图画出关系图的基础上,如下约定做简化：①自反性约定：将表示自反性的环去掉②反对称性约定：如果x≼y，把y画在x之上，则可以把x指向y的箭头去掉（单向边，方向向上）③传递性约定：如果x和y之间有边，但y不盖住x，则将该边去掉。即如果x≼z，z≼y，则把表示传递关系x≼y的边去

6、掉例:是偏序集,其中A={1,2,3,4},≼是整除关系,求该偏序集的哈斯图解：≼={<1,1>,<1,2>,<1,3>,<1,4>,<2,2>,<2,4>,<3,3>,<4,4>}={<1,1>,<1,2>,<1,3>,<1,4>,<2,2>,<2,4>,<3,3>,<4,4>}例:求下列关系的哈斯图设X＝﹛2,3,4,6,24﹜,D为X上的整除关系，则〈X,D〉的哈斯图:234624练习:求下列关系的哈斯图设X＝﹛a,b,c,d﹜上的偏序关系为R＝﹛﹤a,a﹥，,

7、,c﹥,﹤a,d﹥,﹤d,d﹥﹜则〈X,R〉的哈斯图为:abcd5、由哈斯图求关系abcdefg集合A上关系R的哈斯图6、最小元、最大元、极小元、极大元定义：设〈A，≼〉为偏序集，B⊆A。①若y∊B，使得x（x∊B→y≼x）成立，则称y是B的最小元。②若y∊B，使得x（x∊B→x≼y）成立，则称y是B的最大元。③若y∊B，使得﹁x（x∊B∧x≺y）成立，则称y是B的极小元。④若y∊B，使得﹁x（x∊B∧y≺x）成立，则称Y是B的极大元。例:A＝﹛a，b，c,d，e，f，g﹜,B＝﹛c,d﹜偏序集〈X,R〉的哈斯

8、图如图,则abcdefgA的最大元:gA的最小元:无A的极大元:gA的极小元:a,bB的最大元:无B的最小元:无B的极大元:c,dB的极小元:c,d例：P94图4-10A的最大元:无A的最小元:无A的极大元:e,g,hA的极小元:a,b,f,h7、上界、下界、上确界、下确界定