离散数学课件-第4章.ppt

1 离散数学DiscreteMathematics 汪荣贵教授合肥工业大学软件学院专用课件2010 03 学习内容 4 1集合的基本知识4 2序偶与笛卡尔积4 3关系及其性质4 4n元关系及其应用4 5关系的闭包4 6等价关系4 7偏序 偏序 一 偏序定义1 集合S上的关系R 如果它是自反的 反对称的和传递的 就称为偏序 集合S与偏序R一起叫做偏序集 记作 S R 例如数值的 关系和集合的 都是偏序关系 example1 证明 大于或等于 关系 是整数集合上的偏序 solution 因为对所有整数a 有a a 是自反的 如果a b且b a 那么a b 因此 是反对称的 最后 因为a b和b c 所以 是传递的 从而 是整数集合上的偏序且 Z 是偏序集 example2 整除关系 是正整数集合上的偏序 因为由前几节所述 它是自反的 反对称的和传递的 我们看到 Z 是偏序集 Z 表示正整数集合 example3 证明包含关系 是集合S的幂集上的偏序 Solution 因为只要A是S的子集 就有A A 是自反的 因为A B和B A推出A B 因此它是反对称的 最后 因为A B和B C推出A B 是传递的 因此 是P S 上的偏序 且 P S 是偏序集 在任意一个偏序集中记号a b表示 a b R 使用这个记号是由于 小于或等于 关系是偏序关系的范例 注意 符号 表示任意偏序关系 并不仅仅是 小于或等于 关系 记号a b表示a b但a b 如果a b 我们说 a小于b 或 b大于a 当a与b是偏序集 S 的元素时 不一定有a b或b c 例如 在 P Z 中 1 2 与 1 3 没有关系 反之亦然 因为没有一个集合被另一个集合包含 类似地在 Z 中 2与3没关系 3与2也没关系 由此得到定义2 定义2 偏序集 S 的元素a和b叫做可比的 如果a b或b a 当a和b是S的元素并且既没有a b 也没有b a 则称a与b是不可比的 example4 在偏序集 Z 中 整数3和9是可比的吗 5和7是可比的吗 整数3和9是可比的 因为3 9 整数5和7是不可比的 因为5不能整除7 并且7也不能整除5 用形容词 部分的 偏的 描述偏序是由于一些对元素可能是不可比的 当集合中的每对元素都可比时 这个关系叫做全序 定义3 如果 S 是偏序集 且S的每对元素都是可比的 则S叫做全序集或线序集 且 叫做全序或线序 一个全序集也叫做链 example5 偏序集 Z 是全序集 因为只要a和b是整数 就有a b或b a example6 偏序集 Z 不是全序集 因为它包含着不可比的元素 例如5和7 定义4 对于偏序集 S 如果 是全序 并且S的每个非空子集都有一个最小元素 就称它为良序集 Forexample N是自然数集合 I是整数集合 是小于等于关系 就是良序集 而不是良序集 定理所有良序集 一定是全序集 Proof 设为良序集 任取x y A 则 x y A 它有最小元素 该最小元素或是x 或是y 于是有x y或y x 所以是全序集 定理有限的全序集 一定是良序集 Proof 设A a1 a2 an 是全序集 假设它不是良序 必存在非空子集B A B中无最小元素 因B是有限集 必存在x y B 使得x与y之间不满足 关系 与 是全序矛盾 是良序集 example7 正整数的有序对的集合Z Z 与 构成良序集 对于 a1 a2 和 b1 b2 如果a1 b1 或如果a1 b1且a2 b2 字典顺序 则 a1 a2 b1 b2 在前几章的学习中我们现实了怎样使用良序归纳原则证明关于一个良序集的结果 现在我们叙述并证明这个证明技术是有效的 定理1良序归纳原理设S是一个良序集 如果下述条件成立 基础步 P x0 对S的最小元素为真 且归纳步 对一切y S 如果P x 对所有的x y为真 则P y 为真 那么P x 对所有的x S为真 proof 假若P x 不对所有的x S为真 那么存在一个元素y S使得P y 为假 于是集合A x S P x 为假 是非空的 因为S是良序的 集合A有最小元素a 易知a不等于x0 因为从基础步知道P x0 为真 根据a是选自A的最小元素 我们知道对所有的x S x a 都有P x 为真 由归纳步这就可以退出P a 为真 这个矛盾就证明了P x 必须对所有x S为真 二 字典顺序字典顺序是以字母表中的字母顺序为基础的 这是从一个集合上的偏序构造一个集合上的串的序的特殊情况 我们将说明这种构造在任一个偏序集上是怎么做的 首先 我们将说明怎样在两个偏序集 A1 1 和 A2 2 的笛卡尔积上构造一个偏序 在A1 A2上的字典顺序定义如下 如果第一个对的第一个元素 在A1中 小于第二个对的第一个元素 或者第一个元素相等 但是第一个对的第二个元素 在A2中 小于第二个对的第二个元素 那么第一个对小于第二个对 换句话说 a1 a2 小于 b1 b2 即 a1 a2 b1 b2 或者a1 1b1 或者a1 b1且a2 2b2 把相等加到A1 A2上的序就得到偏序 example8 确定在偏序集 Z Z 中是否有 3 5 4 8 3 8 4 5 和 4 9 4 11 这里的 是从Z上通常的 关系构造的字典顺序 Solution 因为3 4 故而 3 5 4 8 且 3 8 4 5 因为 4 9 与 4 11 的第一元素相同 但9 11 我们有 4 9 4 11 下图明显地显示了Z Z 中比 3 4 小的有序对的集合 可以在n个偏序集 A1 1 A2 2 An n 的笛卡尔积上定义字典顺序 如下定义A1 A2 An上的偏序 如果a10是的a1 b1 ai bi 且ai 1 i 1bi 1 那么 a1 a2 an b1 b2 bn 换句话说 如果在两个n元组不同元素出现的第一位置上等一个n元组的元素小于第二个n元组的元素 那么第一个n元组小于第二个n元组 example9 注意 1 2 3 5 1 2 4 3 因为这些4元组的前两位相同 但是第一个4元组的第三位3小于第二个4元组的第三位4 这里的4元组上的字典顺序是整数集合上的通常的 小于或等于 关系导出的字典顺序 我们现在可以定义串上的字典顺序 考虑偏序集S上的串a1a2 an和b1b2 bn 假定这些串不相等 设t是m n中较小的数 定义字典顺序如下 a1a2 an小于b1b2 bn 当且仅当 a1a2 at b1b2 bt 或者 a1a2 at b1b2 bt 并且m n其中这个不等式中的 表示St中的字典顺序 换句话说 为确定两个不同串的序 较长的串被切到较短的串的长度t 即t min m n 然后使用St上的字典顺序比较每个船的前t为组成的t元组 如果对应于第一个串的t元组小于第二个串的t元组 或者这两个t元组相等 但是第二个串更长 那么第一个串小于第二个串 example10 考虑小写英语字母串构成的集合 使用在字母表中的字母序 可以构成在串的集合上的字典顺序 如果两个串第一次出现不同字母时 第一个串的字母先于第二个字母 或者如果第一个串和第二个串在所有的位都相同 但是第二个串有更多的字母 那么 第一个串小于第二个串 这种排序和字典使用的排序相同 例如discreet discrete因为这两个串在第7位首次出现字母 并且e t discreet discreetness因为这两个串前8个字母相同 但是第二个串更长 此外discrete discretion 在有穷偏序集的有向图中有许多可以不必显示出来 因为他们是必须存在的 例如 考虑在集合 1 2 3 4 上的偏序 a b a b 的有向图 参见图a 因为这个关系是偏序 它是自反的并且有向图在所有的顶点都有环 因此 我们不必显示这些环 因为它们是必须出现的 在图b中没有显示这些环 由于一个偏序是传递的 我们不必显示那些由于传递性而必须出现的边 例如 在图c中没有显示边 1 3 1 4 和 2 4 因为它们是必须出现的 如果假设所有的边的方向是向上的 我们不必显示边的方向 图c没有显示方向 三 哈塞图 Hasse图 我们可以使用下面的过程表示一个有穷集上的偏序 从这个关系的有向图开始 1 自反性 每个顶点都有自回路 省去 2 反对称性 两个顶点间只可能有一个箭头从左 右 或从下 上的方向从小到大安置顶点 可省略箭头 3 传递性 由于有 a b b c R则 a c R故只画 a b b c 对应的边 省略边 a c 完成以上步骤就得到一个包含着足够表示偏序信息的图 这个图叫作哈塞图 哈塞图 Hasse图 定义 设 是 上的一个偏序关系 如果a b 则将 画在 下面 且不 使a c c b 则 间用直线连接 并符合简化的关系图的绘制 称这样得到关系图为哈塞图 Hasse图 29 2020 3 27 example11 画出表示 1 2 3 4 6 8 12 上的偏序 a b a整除b 的哈塞图 Solution 由这个偏序的有向图开始 如下图a所示 移走所有的环 如下图b所示 然后删去所有由传递性导出的边 这些边是 1 4 1 6 1 8 1 12 2 8 3 12 排列所有的边使得方向向上 并且删除所有的箭头得到哈塞图 结果如图c所示 example12 画出幂集P S 上的偏序 A B A B 的哈塞图 其中S a b c Solution 关于这个偏序的哈塞图是由相关的有向图得到的 先删除所有的环和所有的由传递性产生的边 即 a b a c b c a b c a a b c b a b c 和 c a b c 最后 使所有的边方向向上并删除箭头 得到哈塞图如下所示 example 1 2 3 s1 s2 s1 s2 s1 s2 p B 求R1 R2 R3所表示关系的哈塞图 具有极值性质的偏序集元素有许多重要应用 偏序集的一个元素叫做极大的 当它不小于这个偏序集的任何其他元素 即a在偏序集 S 中是极大的 当不存在b S使得a b 类似地 偏序集的一个元素叫做极小的 如果它不大于这个偏序集的任何其他元素 即a在偏序集 S 中是极小的 如果不存在b S使得b a 使用哈塞图很容易是识别极大元素和极小元素 它们是图中的 顶 元素与 底 元素 四 极大元素与极小元素 定义 极大元与极小元 设 S 是偏序集 若 S 且在S中找不到一个元素b b a 使a b b a 则称a为A中的极大元素 极小元素 y是B的极小元素 y y B x x B x y x y y是B的极大元素 y y B x x B x y y x example N 是偏序集 A 2 3 4 5 6 7 8 9 则 中极大元素 极小元素 注 极大元 极小元并不要求唯一 且同一元素 可以既是极大元 又是极小元 如 极大元 极小元必须是子集 中的元素 example13 偏序集 2 4 5 10 12 20 25 的哪些元素时极大的 哪些是极小的 Solution 右图关于这个偏序集的哈塞图显示了极大元素是12 20和25 极小元素时2和5 通过这个例子可以看出 一个偏序集可以有多于一个的极大元素和多于一个的极小元素 在偏序集中存在一个元素大于每个其他的元素 这样的元素叫做最大元素 即a是偏序集 S 的最大元素 当对所有的b S有b a 当最大元素存在时它是唯一的 类似地 一个元素叫做最小元素 当它小于偏序集的所有其他元素 即a是偏序集 S 的最小元素 如果对所有的b S有a b 当最小元素存在时它也是唯一的 40 2020 3 27 定义 最大元素与最小元素 设 S 是偏序集 若 则称 为 的最大元素 最小元素 example 上例中其Hasse图如下图所示 结论 子集 中是不存在最大元 最小元 的 定理 是偏序集 B是A的非空子集 如果B有最小元素 最大元素 则最小元素 最大元素 是唯一的 proof 假设B有两个最小元素a b 则因为a是最小元素 b B 根据最小元素定义 有a b 类似地 因为b是最小元素 a B 根据最小元素定义 有b a 因为 有反对称性 所以有a b 同理可证最大元素的唯一性 小结 是偏序集 B是A的非空子集 则 B的极小 大 元素总是存在的 就是子集中处在最下 上 层的元素是极小 大 元素 B的最小元 最大元 素有时可能不存在 只要有唯一的极小 大 元素 则这个极小 大 元素就是最小 大 元素 否则就没有最小 大 元素 example14 确定下图的每个哈塞图表示的偏序集是否有最大元素和最小元素 Solution 哈塞图 a 的偏序集的最小元素时a 这个偏序集没有最大元素 哈塞图 b 的偏序集既没有最大元素也没有最小元素 哈塞图 c 的偏序集没有最小元素 它的最大元素时d 哈塞图 d 的偏序集有最小元素a和最大元素d example15 设S是集合 确定偏序集 P S 中是否存在最大元素与最小元素 Solution 最小元素时空集 因为对于S的任何子集T 有 T 集合S是这个偏序集的最大元素 因为只要T是S的子集 就有T S 46 2020 3 27 example16 在偏序集 Z 中是否存在最大元素和最小元素 Solution 1是最小元素 因为只要n是正整数 就有1 n 因为没有被所有正整数整除的整数 所以不存在最大元素 47 2020 3 27 有时可以找到一个元素大于偏序集 S 的子集A中所有的元素 如果u是S的元素使得对所有的元素a A 有a u 那么u叫做A的一个上界 也可能存在一个元素小于A中的所有的其他元素 如果l是S的一个元素使得对所有的元素a A 有l a 那么l叫做A的一个下界 定义 上界与下界 设 P 是半序集 A P 若a P 对 b A b a a b 称a为A的上界 下界 example B a b c R3 s1 s2 s1 s2 s1 P B P B 是偏序集 设 a b c a c a b a c 其Hasse图如右图所示 注 1 上例中 无最大元素 但存在 的上界 2 为 的最小元 也是 的下界 3 最大 小 元素是 的一个上 下 界 4 上 下 界可以不唯一 也可以不存在 example17 找出下图所示哈塞图的偏序集的子集 a b c j h 和 a c d f 的下界和上界 Solution a b c 的上界是e f j和h 它的唯一的下界是a j h 没有上界 它的下界是a b c d e和f a c d f 的上界是f h和j 它的下界是a 元素x叫做子集A的最小上界 上确界 如果x是一个上界并且它小于A的其他上界 因为如果这样的元素存在 只存在一个 称这个元素为最小上界 上确界 是有意义的 即如果只要a A就有a x 并且只要z是A的上界 就有x z x就是A的最小上界 上确界 类似地 如果y是A的下界 并且只要z是A的下界 就有z y y就是A的最大下界 下确界 A的最大下界 下确界 如果存在也是唯一的 一个子集A的最大下界 下确界 和最小上界 上确界 分别记作glb A 和lub A 定义 上确界与下确界 设 S 是偏序集 A S 若a是A的一个上界 下界 而 A的上界 下界 z 都有a b b a 则称a是A的上确界 下确界 example 给定 A 的哈塞图如图所示 example18 在下图所示偏序集中如果 b d g 的最大下界和最小上界存在 求出这个最大下界和最大上界 Solution b d g 的上界是g和h 因为g h g是最小上界 b d g 的下界是a和b 因为有a b b是最大下界 example19 在偏序集 Z 中 如果集合 3 9 12 和 1 2 4 5 10 的最大下界和最小上界存在 求出这些最大下界和最小上界 Solution 求最大下界 如果3 9 12被一个整数整除 那么这个整数就是 3 9 12 的下界 这样的整数只有1和3 因为1 3 3是 3 9 12 的最大下界 集合 1 2 4 5 10 关系到 的下界只有1 因此1是 1 2 4 5 10 的最大下界 求最小上界 一个整数是 3 9 12 的上界 当且仅当它被3 9和12整除 具有这种性质的整数就是那些被3 9和12的最小公倍数36整除的整数 因此 36是 3 9 12 的最小上界 一个正整数是集合 1 2 4 5 10 的上界 当且仅当它被1 2 4 5 10整除 具有这种性质的整数就是被这些整数的最小公倍数20整除的整数 因此 20是集合 1 2 4 5 10 的最小上界 五 格在这里我们引入格的概念 定义 设 X 是偏序集 如果 x y X 集合 x y 都有最小上界和最大下界 则称 X 是格 example20 确定如下图所示的每个哈塞图表示的偏序集是否是格 Solution 图a和c中的哈塞图表示的偏序集是格 因为在每个偏序集中每对元素都有最小上界和最大下界 另一方面 图b所示的哈塞图的偏序集不是格 因为元素b和c没有最小上界 为此只要注意到d e和f中每一个都是上界 但这3个元素的任何一个关于这个偏序集中的序都不大于其他2个 example 下列各集合对于整除关系都构成偏序集 判断哪些偏序集是格 L 1 2 3 4 5 L 1 2 3 4 6 9 12 18 36 L 1 2 22 2n L 1 2 3 4 5 6 7 8 9 10 Solution 不是 因为L中的元素对 2 3 没有最小上界 是 因为L 1 2 3 4 6 9 12 18 36 任何一对元素a b 都有最小上界和最大下界 是 与 同理 不是 因为L中的元素对 6 7 没有最小上界不存在最小上界 example 下图中给出了一些偏序集的哈斯图 判断它们是否构成格 Solution 它们都不是格 在 a 中 1 2 没有下界 因而没有最大下界 在 b 中 2 4 虽有两个上界 但没有最小上界 在 c 中 1 3 没有下界 因而没有最大下界 在 d 中 2 3 虽有三个上界 但没有最小上界 example21 偏序集 Z 是格吗 Solution 设a和b是两个正整数 这两个整数的最小上界和最大下界分别是它们的最小公倍数和最大公约数 因此这个偏序集是格 example22 确定偏序集 1 2 3 4 5 和 1 2 4 8 16 是否为格 Solution 因为2和3在 1 2 3 4 5 中没有上界 它们当然没有最小上界 因此第一个偏序集不是格 第二个偏序集的每两个元素都有最小上界和最大下界 在这个偏序集中两个元素的最小上界是他们中间较大的元素 而两个元素的最大下界是它们中间较小的元素 因此第二个偏序集是格 example23 确定 P S 是否为格 其中S是集合 Solution 设A和B是S的两个子集 A和B的最小上界和最大下界分别是A B和A B 因此 P S 是格 example24 信息流的格模式在许多设置中 从一个人或计算机程序到另一个人或计算机程序的信息流要受到限制 这可以通过安全权限来实现 我们可以使用格的模型来表示不同的信息流策略 例如 一个通用的信息流策略适用于政府或军事系统中的多级安全策略 为 诶组信息分配一个安全级别 并且每个安全级别用一个对 A C 表示 其中A是权限级别 C是种类 然后允许人和计算机程序从一个被特别限制的安全类的集合中访问信息 在美国政府中 使用的典型的权限级别是不保密 0 秘密 1 机密 2 和绝密 3 在安全级别中使用的种类是一个集合的子集 这个集合含有与一个特定行业领域相关的所有的分部 每个分部表示一个指定的对象域 例如 如果分部的集合是 间谍 鼹鼠 双重间谍 那么存在8个不同的种类 分部集合有8个子集 对于每个子集有一类 例如 间谍 鼹鼠 我们可以对安全类排序 规定 A1 C1 A2 C2 当且仅当A1 A2和C1 C2 信息允许从安全类 A1 C1 流向安全类 A2 C2 当且仅当 A1 C1 A2 C2 例如 信息允许从安全类 机密 间谍 鼹鼠 流向安全类 绝密 间谍 鼹鼠 双重间谍 反之 信息不允许从安全类 绝密 间谍 鼹鼠 流向安全类 机密 间谍 鼹鼠 双重间谍 或 绝密 间谍 六 拓扑排序假设一个项目由20个任务构成 某些任务只能在其他任务结束之后完成 如何找到关于这些任务的顺序 为了对这个问题构造模型 我们建立一个任务集合上的偏序 使得a b 当且仅当a和b是任务且直到a结束后b才能开始 为安排好这个项目 需要得出与这个偏序相容的所有20个任务的顺序 我们将说明怎样做到这一点 从定义开始 如果只要aRb就有a b 则称一个全序 与偏序R是相容的 从一个偏序构造一个相容的全序叫做拓扑排序 需要使用引理1 引理1 每个有穷非空偏序集 S 都有极小元素 Proof 选择S的一个元素a0 如果a0不是绩效元素 那么存在元素a1 满足a1 a0 如果a1不是极小元素 那么存在元素a2 满足a2 a1 继续这一过程 使得如果an不是极小元素 那么存在元素an 1满足an 1 an 因为在这个偏序集只有有穷个元素 这个过程一定结束并且具有极小元素an 我们将要描述的拓扑排序算法对任何有穷非空偏序集都有效为在偏序集 A 上定义一个全序 首先选择一个极小元素a1 由引理1这样的元素存在 接着 A a1 也是一个偏序集 如果它是非空的 选择这个偏序集的一个极小元素a2 然后再取走a