离散数学243(偏序关系)[20141015]

《离散数学243(偏序关系)[20141015]》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、主讲教师：常亮E-mail:changl@guet.edu.cnQQ：737059669办公室电话:2291071手机:13481395869辅导教师：周小川答疑时间：星期四上午10:20-11:50答疑地点：5教5楼软件工程教研室离散数学回顾关系可能具有的性质：自反反自反对称反对称传递特殊关系：具有上述某些性质的关系等价关系：自反、对称、传递偏序关系：自反、反对称、传递2.4.3偏序关系定义2.28设R为非空集合A上的关系（即A并且RAA）。如果R是自反的、反对称的和传递的，则称R为A

2、上的偏序关系。一般用符号“≼”来表示偏序关系。设R是一个偏序关系。如果∈R,则记为x≼y。如果集合A上存在偏序关系，则称A为偏序集，记为。例：集合A={2,4,6,8}上的小于等于关系={<2,2>,<2,4>,<2,6>,<2,8>,<4,4>,<4,6>,<4,8>,<6,6>,<6,8>,<8,8>}。“偏序”例2.66判断下列关系是否为偏序关系①集合A的幂集合P(A)中元素之间的包含关系“”；②实数集合R上的小于等于关系“”；③实数集合R上的大于等于关系“”；

3、④自然数集合N上的模n同余关系；⑤人群中的“父子”关系。例2.67判断集合A={2,3,4,5,6,8}上的整除关系是否为偏序关系？并用关系矩阵和关系图表示。解:集合A上的整除关系为R={<2,2>,<2,4>,<2,6>,<2,8>,<3,3>,<3,6>,<4,4>,<4,8>,<5,5>,<6,6>,<8,8>}该关系具有自反性、反对称性和传递性。所以，它是偏序关系。该关系的关系矩阵和关系图表示如下：625348R可比、盖住定义2.29设R为非空集合A上的偏序关系，对于任意元素x,yA，

4、如果R或R，则称x与y是可比的。如果R且R，则称x与y是不可比的。若x≼y且xy，则称x排在y的前面，记作x≺y，读作“x小于y”。若x≺y且不存在元素zA使得x≺z且z≺y，则称y盖住x。设R为非空集合A上的偏序关系，对于任意元素x,yA，可能出现以下几种情况：①x≺y（或y≺x）；②x=y；③x与y不是可比的。例2.68考察集合A={2,3,4,5,6,8}上的整除关系R={<2,2>,<2,4>,<2,6>,<2,8>,<3,3>,<3

5、,6>,<4,4>,<4,8>,<5,5>,<6,6>,<8,8>}。可比的情况：不可比的情况：盖住的情况：哈斯图对偏序关系的关系图可进行如下简化：①自反：可以将各顶点上的环全部略去；②反对称：边为单向，可以规定向上方向为箭头方向，省略箭头；③传递：可以将由传递性导出的边省去。将经过上述简化后得到的关系图称为哈斯图。哈斯图的绘制步骤：（1）以“”表示元素；（2）若x≺y，则y画在x的上层；（3）若y盖住x，则连线；（4）不可比的元素可画在同一层。例对于集合A={2,3,4,5,6,8}上的整除

6、关系，画出其哈斯图。解:集合A上的整除关系为R={<2,2>,<2,4>,<2,6>,<2,8>,<3,3>,<3,6>,<4,4>,<4,8>,<5,5>,<6,6>,<8,8>}该关系具有自反性、反对称性和传递性。所以，它是偏序关系。该关系的关系矩阵和关系图表示如下：625348R846235关系R的哈斯图哈斯图例2.70:绘制如下偏序关系的哈斯图①集合A={1,2,3,4,6,12}上的整除关系；②集合A={2,3,4,5,8}上的大于等于关系“”；③集合A={2,3,6,12,24,3

7、6}上的整除关系；④集合A={a,b,c}的幂集P(A)上的包含关系“”；解：偏序关系①、②、③和④的哈斯图绘制于图1246231整除关系23458大于等于关系{a,b,c}{a,b}{a,c}{b,c}{a}{b}{c}包含关系243612623整除关系偏序集中的8个特殊元素(最大元、最小元)定义2.30对于偏序集和集合A的任意子集B，如果存在元素bB，使得任意xB都有x≼b，则称b为B的最大元素，简称为最大元；如果存在元素bB，使得任意xB都有b≼x，则称b为B的最小元

8、素，简称为最小元。例2.71对于例2.70中偏序关系①（即集合A={1,2,3,4,6,12}上的整除关系），令B1={1,6}、B2={1,2,3}、B3={4,6,12}、B4={2,4,6}、B5={1,2,6,12}、B6={1,2,3,4,6,12}。分别求出B1、B2、B3、B4、B5和B6的最大元和最小元。解:对于集合B1={1,6}，最大元为6，最小元为1；对于集合B2={1,2,3}，元素2和3不可比，所以，不存在最大元，最小元为1；对于集合B3={4,6,12}，元素4和6不