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

*离散数学DiscreteM;学习内容4.1集合的基本知识4;偏序一、偏序定义1：集合S上;【example1】证明“大;【example2】整除关系;【example3】证明包含;在任意一个偏序集中记号a?;定义2：偏序集(S,?);用形容词“部分的（偏的）”描述;01【example5】偏序;定义4：对于偏序集(S,?;定理所有良序集，一定是全序集;定理有限的全序集，一定是良序;【example7】正整数的;基础步：P(x0)对S的最小元;假若P(x)不对所有的x∈S;字典顺序字典顺序是以字母表中的;首先，我们将说明怎样在两个偏序;【example8】确定在偏;无标题;可以在n个偏序集(A1,?1;【example9】注意（1;我们现在可以定义串上的字典顺序;【example10】考虑;在有穷偏序集的有向图中有许多可;无标题;我们可以使用下面的过程表示一个;哈塞图（Hasse图）01;【example11】画出表;无标题;【example12】画出幂;无标题;【example】：Ａ＝｛１，;12345678;具有极值性质的偏序集元素有许多;[定义]极大元与极小元：设（S;【example】（N，|）是;【example13】偏序集;在偏序集中存在一个元素大于每个;结论：子集Ａ中是不存在最大元（;[定理]A,?是偏序集;A,≤是偏序集，B是A的非;【example14】确定下;哈塞图(a)的偏序集的最小元素;21【example15】设S;【example16】在偏序;有时可以找到一个元素大于偏序集;[定义]上界与下界：;上例中，Ａ无最大元素，但存在Ａ;【example17】找出下;STEP03STEP01S;元素x叫做子集A的最小上界（上;设（S，≤）是偏序集，A?S，;【example】给定（A,≤;Solution：{b，d，g;【example19】在偏序;求最小上界：;格在这里我们引入格的概念。定义;0102030405图a和c中;L=｛1,2,22,…,2n｝;不是，因为L中的元素对{2,3;构成格。【example】下图;Solution：它们都不是格;【example21】偏序集;【example22】确定偏;【example23】确定（;【example24】信息流;在美国政府中，使用的典型的权限;我们可以对安全类排序，规定（A;21假设一个项目由20个任务构;01.从定义开始，如果只要aR;继续这一过程，使得如果an不是;我们将要描述的拓扑排序算法对任;时b已经被移出，否则c就不会是;无标题;【example25】找出对;产生的全序是15242;在项目的安???中常会用到拓扑排序;Solution：可以通过执行;下面那些集合是偏序集？1在偏序;Solution：满足自反、反;PARTONESolutio;确定由线面的0-1矩阵表示的关;3.确定以下3个有向图所表示;找出下面英语字母串的字典顺序。;单击此处添加正文，文字是您思想;本节内容到此结束谢谢大家！