次序关系-集合与关系-离散数学.ppt

《次序关系-集合与关系-离散数学.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、次序关系1次序关系也是常遇到的重要关系，例如：数值的≤、＜、≥、＞关系；集合的、关系；图书馆的图书按书名的字母次序排序；词典中的字(词)的排序；计算机中文件按文件名排序；程序按语句次序执行；…….本节讨论几种次序关系。2等价关系有向图等价类商集划分相容类最大相容类完全覆盖简化图二元关系性质自反对称传递反对称反自反相容关系偏序关系全序哈斯图重要元素3一、偏序关系(partialorderrelation)1.定义3-12.1R是A上自反、反对称和传递的关系，则称R是A上的偏序关系。并称是偏序集

2、。因为数集上的≤是熟知的，且是偏序关系，所以用符号“≤”表示任意偏序关系。∈R，表示为a≤b，读作“a小于等于b”。意即在偏序关系中a排在b的前面。要注意!!“≤”不一定是“小于或等于”的含义。常见偏序关系：小于等于关系、大于等于关系、集合的包含关系、恒等关系、空集上的空关系。全域关系呢？？4A={1,2,4,6},≤是A中的整除关系，证明其是偏序关系。证明：R={<1,1>,<2,2>,<4,4>,<6,6>,<1,2>,<1,4>,<1,6>,<2,4>,<2,6>}自反IA={<1,1>,

3、<2,2>,<3,3>,<4,4>}IAR反对称RC={<1,1>,<2,2>,<4,4>,<6,6>,<2,1>,<4,1>,<6,1>,<4,2>,<6,2>}RC∩R={<1,1>,<2,2>,<4,4>,<6,6>}IA传递R2=RR={<1,1>,<1,2>,<1,4>,<1,6>,<2,2>,<2,4>,<2,6>,<4,4>,<6,6>}R所以，R是偏序关系。例3-12.1。。。。64125是偏序集，x,y∈A，若要么x≤y，要么y≤x，则称x与y是可比较的。例3-12.1

4、中1与2，1与4，1与6，2与4，2与6是可比较的，而4与6是不可比较的。2.x与y是可比较的。。。。64126二、全序(线序、链)定义3-12.2：是偏序集，任何x,y∈A，如果x与y都是可比较的，则称≤是全序关系(线序、链)。例3-12.2：B={1,2,4,8},≤表示整除关系，如右图分析得到≤是全序关系。。。。。8412全序关系一定是偏序关系，但是偏序不一定是全序。偏序关系的有向图，不能直观地反映出元素之间的次序，所以下面介绍另外一种图---Hasse图。通过这个图，就能够清晰地反映出元

5、素间的层次。7三、偏序集哈斯图（Hasse图）(1)用矩阵表示偏序关系，不能明显看出二元关系的特征。(2)用简化的关系图表示较合适。简化的关系图：(1)自反性：每个结点都有自回路，可省去自回路。(2)反对称性：两个结点间只可能有一个箭头方向，所以将箭头默认为从下→上，可省略箭头。(3)传递性：由于有,∈R，则∈R，故只画,对应的边，省略边。8令是偏序集，x,y,z∈Ａ作图规则：(1)用“°”表示A中元素。(2)若x≤y，且x≠y，则将结

6、点y画在结点x的上方。(3)若x≤y，x≠y且没有不同于x,y的z，使得x≤z，z≤y，则在x,y之间连一直线。方法：分层法一般先从最下层结点(全是序偶的第一元素（射出的边)，逐层向上画，直到最上层结点(全是序偶的第二元素（射入的边）。偏序集哈斯图（Hasse图）的画法9它们的Hasse图分别如下：例3-12.1和3-12.242。。。。8412哈斯图的意义在于：元素之间从下向上有线相连，则这两个元素存在着偏序关系；反之则不存在偏序关系。右图是全序，它的Hasse图是一条直线，所以全序也叫线序，或链。。。

7、。。6142。。。。61１。２。４。６。42。2８。１。２。４。810练习：教材第146页　(7)12343142全序23142314(a)2314(b)2413(d)2413(c)134211C={1,2,3,6,12,24,36},D={1,2,3,5,6,10,15,30}≤是C、D上整除关系，<Ｃ,≤>,<Ｄ,≤>的Hasse图，以及A={a,b,c}<ρ(A),>的Hasse图：练习３。36。６。１。12。２。24。30。3。１。2。5。10。15。6。{a,b,c}。{b}。Φ。{a}。{c

8、}。{a,c}。{b,c}。{a,b}。<ρ(A),>12定义设是偏序集,x,yA,如果x≤y，且x≠y,且不存在z使得x≤z,z≤y，则称y盖住x。并且记COVA={

9、x,yA∧y盖住x}。例：在A={1,2,4,6}上的整除关系中，有哪些盖住关系呢？解：整除关系：{<1,1>,<1,2>,<1,4>,<1,6>,<2,2>,　<2,4>,<2,6>,<4,4>,<6,6>}2