《离散数学课件》7偏序关系.ppt

上节课内容等价关系 等价关系等价类定义性质商集 集合的划分等价关系和划分的对应 1 2 49 7 6偏序关系和格 7 6 1偏序关系 偏序集7 6 2哈斯 Hasse 图7 6 3链 反链 全序集7 6 4极大元 极小元 最大元 最小元7 6 5上界 下界 最小上界 最大下界7 6 6格 3 49 一 偏序关系 例在实数集R上定义二元关系S 对于任意的x y R x y S当且仅当x y R有自反性 反对称性 传递性 4 49 偏序关系 偏序集 定义1设A是一个非空集合 R是A上的一个二元关系 若R有自反性 反对称性 传递性 则称R是A上的一个偏序关系 记作 并称 A 是一个偏序集 如果 x y 则记作x y 读作x 小于或等于 y 例1A 1 2 3 4 R 1 1 2 2 3 3 4 4 1 2 1 3 1 4 2 4 R是A上一个偏序关系 5 49 例2 p109 设Z n Z n 0 即Z 是正整数的集合 在Z 上定义一个二元关系R如下 对于任意的x y Z x y R当且仅当x y 证明 Z R 是偏序集 6 49 例2 p109 证明 Z R 是偏序集 1 对于任意的x Z 显然有x x 所以 x x R 即R是自反的 2 对于任意的x y Z 若 x y R 且 y x R 则x y 即存在n Z y nx且y x 即存在m Z x my 所以x mnx 而n m Z 所以只有n m 1 即x y时才有 x y R 且 y x R 即R有反对称性 3 对于任意的x y z Z 若 x y R 且 y z R 则由 x y R 得x y 即 n0 Z 使得y xn0 再由 y x R 得y x 即 m0 Z 使得z m0y 所以z m0n0 x 即x z 所以 x z R 即R有传递性 综上所述 R是Z 上偏序关系 即 Z R 是偏序集 对于任意的x y Z x y R当且仅当x y 7 49 例3设A是任意一个集合 A 是A的幂集合 在 A 上建立一个二元关系R 对于任意的x y A x y R当且仅当x y 不难证明 A R 也是一个偏序集 8 49 例 在实数集R上定义二元关系S 对于任意的x y R x y S当且仅当x y 可以证明S是R上的一个偏序关系 在实数集R上定义二元关系S 对于任意的x y R x y S 当且仅当x y 可以证明S 是R上的一个偏序关系 集合A上的恒等关系IA是A上的偏序关系 9 49 关于记号 对于一个偏序关系 往往用记号 来表示 若 a b 记为a b 读做 a小于等于b 一个偏序集 通常用符号 A 来表示 10 49 注意 偏序关系 a小于等于b 并不意味着平时意义上的a小于等于b 一个集合上可以定义不同的偏序关系 得到不同的偏序集 还要说明一下 一个偏序集 A 包含集合A与集合A上的偏序关系 不允许x A 出现 而仅有x A x y 即谈到元素是从A中取 讲到关系是在 中取 11 49 覆盖 设 A 是一个偏序集 A是一个有限集 A n 对于任意的x y A 且x y 假设 x y 即x y 如果对于 z A 由x z 且z y 一定能够推出x z或y z 那么我们说y覆盖x 设R为非空集合A上的偏序关系 x y A 如果x y且不存在z A使得x z y 则称y覆盖x 12 49 A 1 2 3 4 1 1 2 2 3 3 4 4 1 2 1 3 1 4 2 4 显然2覆盖13覆盖14覆盖2 但4不覆盖1 1 2 3 4 哈斯图 13 49 二 哈斯图 HasseDiagram 设 A 是一个偏序集 A是一个有限集 A n 可以用一个图形来表示偏序集 A 这个图形有n个顶点 每一个顶点表示A中一个元素 两个顶点x与y 若有y覆盖x 则点x在点y的下方 且两点之间有一条直线相连结 哈斯图 利用偏序自反 反对称 传递性简化的关系图 14 49 例 A a b c d e a a b b c c d d e e a b a c a d a e b c b d c d e d 显然b覆盖a e覆盖ac覆盖bd覆盖cd覆盖e a b c d e 特点 每个结点没有环 两个连通的结点之间的有序关系通过结点位置的高低表示 位置低的元素的顺序在前 具有覆盖关系的两个结点之间连边 16 哈斯图实例 例 17 49 例试画出哈斯图 设A 1 2 3 4 1 2 1 5 3 6 4 6 0 3 6 1 5 8 0 3 4 6 R是A上的一个偏序关系 对于任意的x y A x y R当且仅当x y 18 A a b c d e f g h R IA 哈斯图实例 例已知偏序集的哈斯图如右图所示 试求出集合A和关系R的表达式 19 注意事项 1 不出现三角形 2 不出现水平线段 3 尽量减少交叉线 20 49 可比 不可比 设 A 是一个偏序集 对于任意的x y A 若x y或者y x 则说x与y可比 否则说x与y不可比 例给出如图所示的偏序集 2与1 2与4等都是可比的 而2与3 与 都是不可比的 21 49 三 链 反链 设 A 是一个偏序集 B是A的一个子集 如果 中任意两个元素都可比 说 B 是一条链 2 如果 中任意两个元素都不可比 说 B 是一条反链 22 49 例给出如图所示的偏序集 a b c d 链 a d e 链 b e 反链 c e 反链 23 49 全序集 设 A 是一个偏序集 如果它本身就是一条链 那么称之为全序集 并称 为全序关系 例A a b c d e a a b b c c d d e e a b a c a d a e b c b d c d e d b e e c 25 49 四 偏序集中的特定元素 设 A 是一个偏序集 B A y B 若 x x B x y 成立 则称y为B的极小元 若 x x B y x 成立 则称y为B的极大元 1 极大元 极小元 26 49 例给出如图所示的偏序集 在 1 2 中 1是极小元 2是极大元在 1 2 3 中 1是极小元 2 3是极大元在 1 2 3 4 中 1是极小元 3和4是极大元 27 49 设 A 是一个偏序集 B A y B 若 x x B y x 成立 则称y为B的最小元 若 x x B x y 成立 则称y为B的最大元 2 最大元 最小元 28 49 一个有限的偏序集 一定有极大元和极小元 但不一定有最大元和最小元 例给出如图所示的偏序集 1是最小元 也是极小元 3和4是极大元 无最大元 29 49 例考察如图所示偏序集最小元与最大元 a 无最大元 c 表示的偏序集没有最小元与最大元 b 和 d 表示的偏序集有最小元与最大元 a b c d 极大 极小与最大最小元的找法 1 孤立点 既是极大元也是极小元 若图中有孤立点 则必无最大 最小元 2 除孤立点外 其他极小元是图中所有向下通路的终点 其他极大元是图中所有向上通路的终点 3 若极小元唯一则其为最小元 若极大元唯一则其为最大元 例找出极大 极小元与最大 最小元 极小 1极大 5 6 7 8 9最小 1最大 无 极小 极大 a b c 最小 最大 a b c 32 49 设 A 是一个偏序集 B A y A 若 x x B x y 成立 则称y为B的上界若 x x B y x 成立 则称y为B的下界 3 上界 下界 33 49 例给出如图所示的偏序集 h i j和k都是 f g 的上界 c d a为其下界 34 49 设 A 是一个偏序集 B A y A 令C y y为B的上界 则称C的最小元为B的最小上界或上确界 令D y y为B的下界 则称D的最大元为B的最大下界或下确界 4 上确界 下确界 35 49 例给出如图所示的偏序集 b d 的上界是h和f下界是a 上确界是f 下确界是a 1 B中的元素向上走共同能到达的即为上界 上界中的最大元即为上确界 2 B中元素向下走共同能到达的为下界 下界中的最小元即为下确界 36 实例