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

《离散数学课件-第4章.ppt》由会员分享，可在线阅读，更多相关《离散数学课件-第4章.ppt（87页珍藏版）》请在三一办公上搜索。

1、1,离散数学Discrete Mathematics,汪荣贵 教授合肥工业大学软件学院专用课件2010.03,学习内容,4.1集合的基本知识4.2 序偶与笛卡尔积4.3 关系及其性质4.4 n元关系及其应用4.5 关系的闭包4.6 等价关系4.7 偏序,偏序,一、偏序 定义1：集合S上的关系R，如果它是自反的、反对称的 和传递的，就称为偏序。集合S与偏序R一起叫做偏序集，记作（S,R）.例如数值的、关系和集合的都是偏序关系。,【example 1】证明“大于或等于”关系（）是整数集合上的偏序。solution：因为对所有整数a，有a a，是自反的。如果a b且b a，那么a=b，因此是反对称的

2、。最后，因为a b和b c，所以是传递的。从而是整数集合上的偏序且（Z,）是偏序集。,【example 2】整除关系“|”是正整数集合上的偏序，因为由前几节所述，它是自反的、反对称的和传递的。我们看到（Z+,|）是偏序集（Z+表示正整数集合）。,【example 3】证明包含关系是集合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.使用这个记号 是由于“小于或等于”关系是

3、偏序关系的范例。注意：符号 表示任意偏序关系，并不仅仅是“小于或等于”关系。记号ab表示a b但ab.如果ab,我们说“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是不可比的。【example 4】在偏序集(Z+,)中，整数3和9是可比的吗？5和7是可比的吗？整

4、数3和9是可比的，因为3|9.整数5和7是不可比的，因为5不能整除7，并且7也不能整除5.,用形容词“部分的（偏的）”描述偏序是由于一些对元素可能是不可比的。当集合中的每对元素都可比时，这个关系叫做全序。定义3：如果(S,)是偏序集，且S的每对元素都是可比的，则S叫做全序集或线序集，且 叫做全序或线序。一个全序集也叫做链。,【example 5】偏序集(Z,)是全序集，因为只要a和b是整数，就有a b或b a。【example 6】偏序集(Z+,|)不是全序集，因为它包含着不可比的元素，例如5和7.,定义4：对于偏序集(S,)，如果是全序，并且S的每 个非空子集都有一个最小元素，就称它为良序集

5、。For example，N是自然数集合，I是整数集合，是小于等于关系，就是良序集。而不是良序集。,定理 所有良序集，一定是全序集。Proof：设为良序集,任取x,y A,则x,y A,它有最小元素。该最小元素或是x,或是y。于是有x y或 y x，所以是全序集。,定理 有限的全序集，一定是良序集。Proof：设A=a1,a2,，an,是全序集。假设它不是良序，必存在非空子集BA，B中无最小元素，因B是有限集，必存在x,y B,使得x与y之间不满足关系,与是全序矛盾。是良序集。,【example 7】正整数的有序对的集合Z+Z+与构成良序集，对于(a1,a2)和(b1,b2),如果a1b1,或

6、如果a1=b1且a2 b2（字典顺序），则(a1,a2)(b1,b2).,在前几章的学习中我们现实了怎样使用良序归纳原则证明关于一个良序集的结果。现在我们叙述并证明这个证明技术是有效的。定理1 良序归纳原理 设S是一个良序集，如果下述条件成立：基础步：P(x0)对S的最小元素为真，且 归纳步:对一切y S,如果P(x)对所有的xy为真，则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)为

7、真。根据a是选自A的最小元素，我们知道对所有的x S(xa)都有P(x)为真。由归纳步这就可以退出P(a)为真。这个矛盾就证明了P(x)必须对所有x S 为真。,二、字典顺序字典顺序是以字母表中的字母顺序为基础的。这是从一个集合上的偏序构造一个集合上的串的序的特殊情况。我们将说明这种构造在任一个偏序集上是怎么做的。,首先，我们将说明怎样在两个偏序集(A1,1)和(A2,2)的笛卡尔积上构造一个偏序。在A1A2上的字典顺序定义如下：如果第一个对的第一个元素（在A1中）小于第二个对的第一个元素，或者第一个元素相等，但是第一个对的第二个元素（在A2中）小于第二个对的第二个元素，那么第一个对小于第二个

8、对。换句话说，(a1,a2)小于(b1,b2),即(a1,a2)(b1,b2)或者a11b1,或者a1=b1且a22b2.把相等加到A1A2上的序就得到偏序。,【example 8】确定在偏序集（ZZ，）中是否有(3,5)(4,8),(3,8)(4,5)和(4,9)(4,11)?这里的 是从Z上通常的关系构造的字典顺序。Solution：因为34,故而(3,5)(4,8),且(3,8)(4,5)。因为(4,9)与(4,11)的第一元素相同，但911,我们有(4,9)(4,11)。下图明显地显示了Z+Z+中比(3,4)小的有序对的集合。,可以在n个偏序集(A1,1),(A2,2),(An,n)的

9、笛卡尔积上定义字典顺序。如下定义A1A2An上的偏序：如果a10 是的a1=b1,ai=bi,且ai+1i+1 bi+1,那么(a1,a2,an)(b1,b2,bn)换句话说，如果在两个n元组不同元素出现的第一位置上等一个n元组的元素小于第二个n元组的元素，那么第一个n元组小于第二个n元组。,【example 9】注意（1，2，3，5）（1，2，4，3），因为这些4元组的前两位相同，但是第一个4元组的第三位3小于第二个4元组的第三位4（这里的4元组上的字典顺序是整数集合上的通常的“小于或等于”关系导出的字典顺序）。,我们现在可以定义串上的字典顺序。考虑偏序集S上的串a1a2an和b1b2bn,

10、假定这些串不相等。设t是m，n中较小的数。定义字典顺序如下：a1a2an小于b1b2bn,当且仅当（a1a2at）（b1b2bt）或者（a1a2at）=（b1b2bt）并且mn 其中这个不等式中的表示St中的字典顺序。换句话说，为确定两个不同串的序，较长的串被切到较短的串的长度t，即t=min(m,n)然后使用St上的字典顺序比较每个船的前t为组成的t元组，如果对应于第一个串的t元组小于第二个串的t元组，或者这两个t元组相等，但是第二个串更长，那么第一个串小于第二个串。,【example 10】考虑小写英语字母串构成的集合。使用在字母表中的字母序，可以构成在串的集合上的字典顺序。如果两个串第一

11、次出现不同字母时，第一个串的字母先于第二个字母，或者如果第一个串和第二个串在所有的位都相同，但是第二个串有更多的字母，那么，第一个串小于第二个串。这种排序和字典使用的排序相同。例如 discreet discrete因为这两个串在第7位首次出现字母，并且 e t.discreet discreetness因为这两个串前8个字母相同，但是第二个串更长。此外 discrete discretion,在有穷偏序集的有向图中有许多可以不必显示出来，因为他们是必须存在的。例如，考虑在集合1，2，3，4上的偏序(a,b)|a b的有向图，参见图a。因为这个关系是偏序，它是自反的并且有向图在所有的顶点都有环

12、，因此，我们不必显示这些环，因为它们是必须出现的。在图b中没有显示这些环。由于一个偏序是传递的，我们不必显示那些由于传递性而必须出现的边。例如，在图c中没有显示边(1,3),(1,4)和(2,4)，因为它们是必须出现的。如果假设所有的边的方向是向上的，我们不必显示边的方向；图c没有显示方向。,三、哈塞图（Hasse 图）,我们可以使用下面的过程表示一个有穷集上的偏序。从这个关系的有向图开始：(1)自反性：每个顶点都有自回路，省去。(2)反对称性：两个顶点间只可能有一个箭头从左 右，或从下上的方向从小到大安置顶点，可省略箭头。(3)传递性：由于有(a,b)，(b,c)R 则(a,c)R故只画(a

13、,b)，(b,c)对应的边,省略边(a,c)。,完成以上步骤就得到一个包含着足够表示偏序信息的图，这个图叫作哈塞图,哈塞图（Hasse 图）定义：设是上的一个偏序关系，如果a b，则将画在 下面，且不，使ac，c b，则，间用直线连 接。并符合简化的关系图的绘制，称这样得到关系图为 哈塞图（Hasse图）。,29,2023/9/14,【example 11】画出表示1，2，3，4，6，8，12上的偏序(a,b)|a 整除b的哈塞图。Solution：由这个偏序的有向图开始，如下图a所示。移走所有的环，如下图b所示，然后删去所有由传递性导出的边。这些边是(1,4),(1,6),(1,8),(1,

14、12),(2,8),(3,12).排列所有的边使得方向向上，并且删除所有的箭头得到哈塞图。结果如图c所示。,【example 12】画出幂集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)s1s2，s1，s2p(B)求R1,R2,R3 所表

15、示关系的哈塞图。,具有极值性质的偏序集元素有许多重要应用。偏序集的一个元素叫做极大的，当它不小于这个偏序集的任何其他元素。即a在偏序集（S，）中是极大的，当不存在bS使得ab.类似地，偏序集的一个元素叫做极小的，如果它不大于这个偏序集的任何其他元素。即a在偏序集（S，）中是极小的，如果不存在bS使得ba。使用哈塞图很容易是识别极大元素和极小元素。它们是图中的“顶”元素与“底”元素。,四、极大元素与极小元素,定义极大元与极小元：设（S，）是偏序集，若S，且在S中找不到一个元素b（ba），使ab（ba），则称a为A中的极大元素（极小元素）。y是B的极小元素 y(y B x(x B x y x y)

16、y是B的极大元素 y(y B x(x B x y y x),【example】（N，|）是偏序集，A=2，3，4，5，6，7，8，9则 中极大元素：，极小元素：，注：极大元，极小元并不要求唯一，且同一元素，可以既是极大元，又是极小元，如，。极大元，极小元必须是子集中的元素。,【example 13】偏序集（2，4，5，10，12，20，25，|）的哪些元素时极大的，哪些是极小的？Solution：右图关于这个偏序集的哈塞图显示了极大元素是12，20和25，极小元素时2和5。,通过这个例子可以看出，一个偏序集可以有多于一个的极大元素和多于一个的极小元素。,在偏序集中存在一个元素大于每个其他的元素

17、，这样的元素叫做最大元素，即a是偏序集（S，）的最大元素，当对所有的bS有b a。当最大元素存在时它是唯一的。类似地，一个元素叫做最小元素，当它小于偏序集的所有其他元素。即a是偏序集（S，）的最小元素，如果对所有的bS有a b。当最小元素存在时它也是唯一的。,40,2023/9/14,定义 最大元素与最小元素：设（S，）是偏序集，若，(），则称为的最大元素（最小元素）。【example】上例中其Hasse图如下图所示,结论：子集中是不存在最大元（最小元）的。,定理 是偏序集，B是A的非空子集，如果B有最小元素(最大元素)，则最小元素(最大元素)是唯一的。proof：假设B有两个最小元素a、b,

18、则 因为a是最小元素，bB，根据最小元素定义，有ab;类似地，因为b是最小元素，aB，根据最小元素定义，有ba。因为有反对称性，所以有a=b。同理可证最大元素的唯一性。,小结：是偏序集，B是A的非空子集，则 B的极小(大)元素总是存在的，就是子集中处在最下(上)层的元素是极小(大)元素。B的最小元(最大元)素有时可能不存在，只要有唯一的极小(大)元素，则这个极小(大)元素就是最小(大)元素。否则就没有最小(大)元素。,【example 14】确定下图的每个哈塞图表示的偏序集是否有最大元素和最小元素。,Solution：哈塞图(a)的偏序集的最小元素时a。这个偏序集没有最大元素。哈塞图(b)的偏

19、序集既没有最大元素也没有最小元素。哈塞图(c)的偏序集没有最小元素，它的最大元素时d。哈塞图(d)的偏序集有最小元素a和最大元素d。,【example15】设S是集合。确定偏序集（P(S),）中是否存在最大元素与最小元素。Solution：最小元素时空集。因为对于S的任何子集T,有 T，集合S是这个偏序集的最大元素，因为只要T是S的子集，就有T S。,46,2023/9/14,【example 16】在偏序集（Z+,|）中是否存在最大元素和最小元素？Solution：1是最小元素，因为只要n是正整数，就有1|n。因为没有被所有正整数整除的整数，所以不存在最大元素。,47,2023/9/14,有

20、时可以找到一个元素大于偏序集（S，）的子集A中所有的元素。如果u是S的元素使得对所有的元素a A,有a u，那么u叫做A的一个上界。也可能存在一个元素小于A中的所有的其他元素。如果l是S的一个元素使得对所有的元素a A,有l a，那么l叫做A的一个下界。,定义上界与下界：设（P,）是半序集，AP，若aP，对 bA,b a（a b）称a为A的上界（下界）。,【example】：B=a,b,c,R3=(s1,s2)|s1 s2，s1P(B),(P(B),)是偏序集。设，a,b,c,a,c,a,b,a,c其Hasse图如右图所示:,注：（1）上例中，无最大元素，但存在的上界，。（2）为的最小元，也是

21、的下界。（3）最大（小）元素是的一个上（下）界。（4）上（下）界可以不唯一，也可以不存在。,【example 17】找出下图所示哈塞图的偏序集的子集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的其他上界。因为如果这样的元素存在，只存在一个，称这个元素为最小上界（上确界）是有意义的。即如果只要aA就有a x，并且只要z是A的上界，就有x z,x就是A的

22、最小上界（上确界）。类似地，如果y是A的下界，并且只要z是A的下界，就有z y，y就是A的最大下界（下确界）。A的最大下界（下确界）如果存在也是唯一的。一个子集A的最大下界（下确界），和最小上界（上确界），分别记作 glb(A)和 lub(A).,定义上确界与下确界：设（S，）是偏序集，AS，若a是A的一个上界（下界），而A的上界（下界）z，都有a b（b a），则称a是A的上确界（下确界）。,【example】给定（A,）的哈塞图如图所示：,【example 18】在下图所示偏序集中如果b，d，g的最大下界和最小上界存在，求出这个最大下界和最大上界。,Solution：b，d，g的上界是g和

23、h。因为g h,g是最小上界。b，d，g的下界是a和b，因为有a b,b 是最大下界。,【example 19】在偏序集（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的最小

24、公倍数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,是格。【example 20】确定如下图所示的每个哈塞图表示的偏序集是否是格,Solution：图a和c中的哈塞图表示的偏序集是格。因为在每个偏序集中每对元素都有最小上界和最大下界。另一方面，图b所示的哈塞图的偏序集不是格，因为元素

25、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】下图中给出了一些偏

26、序集的哈斯图，判断它们是否构成格。,Solution：它们都不是格。在(a)中，1,2没有下界，因而没有最大下界。在(b)中，2,4虽有两个上界，但没有最小上界。在(c)中，1,3没有下界，因而没有最大下界。在(d)中，2,3虽有三个上界，但没有最小上界。,【example 21】偏序集（Z+,|）是格吗？Solution：设a和b是两个正整数，这两个整数的最小上界和最大下界分别是它们的最小公倍数和最大公约数，因此这个偏序集是格。,【example 22】确定偏序集（1，2，3，4，5，|）和（1，2，4，8，16，|）是否为格？Solution：因为2和3在（1，2，3，4，5，|）中没有上

27、界，它们当然没有最小上界。因此第一个偏序集不是格。第二个偏序集的每两个元素都有最小上界和最大下界。在这个偏序集中两个元素的最小上界是他们中间较大的元素，而两个元素的最大下界是它们中间较小的元素。因此第二个偏序集是格。,【example 23】确定（P(S),）是否为格，其中S是集合。Solution：设A和B是S的两个子集，A和B的最小上界和最大下界分别是AB和A B，因此（P(S),）是格。,【example 24】信息流的格模式 在许多设置中，从一个人或计算机程序到另一个人或计算机程序的信息流要受到限制，这可以通过安全权限来实现。我们可以使用格的模型来表示不同的信息流策略。例如，一个通用的

28、信息流策略适用于政府或军事系统中的多级安全策略。为，诶组信息分配一个安全级别，并且每个安全级别用一个对（A,C）表示，其中A是权限级别，C是种类。然后允许人和计算机程序从一个被特别限制的安全类的集合中访问信息。,在美国政府中，使用的典型的权限级别是不保密（0）、秘密（1）、机密（2）和绝密（3）。在安全级别中使用的种类是一个集合的子集，这个集合含有与一个特定行业领域相关的所有的分部，每个分部表示一个指定的对象域。例如，如果分部的集合是间谍，鼹鼠。双重间谍，那么存在8个不同的种类，分部集合有8个子集，对于每个子集有一类，例如间谍，鼹鼠。,我们可以对安全类排序，规定（A1,C1）（A2,C2）当且

29、仅当A1 A2和C1 C2.信息允许从安全类（A1,C1）流向安全类（A2,C2）当且仅当（A1,C1）（A2,C2）。例如，信息允许从安全类（机密，间谍，鼹鼠）流向安全类（绝密，间谍，鼹鼠，双重间谍），反之，信息不允许从安全类（绝密，间谍，鼹鼠）流向安全类（机密，间谍，鼹鼠，双重间谍）或（绝密，间谍）。,六、拓扑排序假设一个项目由20个任务构成。某些任务只能在其他任务结束之后完成，如何找到关于这些任务的顺序？为了对这个问题构造模型，我们建立一个任务集合上的偏序，使得ab,当且仅当a和b是任务且直到a结束后b才能开始。为安排好这个项目，需要得出与这个偏序相容的所有20个任务的顺序。我们将说明怎

30、样做到这一点。,从定义开始，如果只要aRb就有a b,则称一个全序与偏序R 是相容的。从一个偏序构造一个相容的全序叫做拓扑排序。需要使用引理1.引理1：每个有穷非空偏序集（S,）都有极小元素。,Proof：选择S的一个元素a0.如果a0不是绩效元素，那么存在元素a1,满足a1 a0.如果a1不是极小元素，那么存在元素a2,满足a2 a1.继续这一过程，使得如果an不是极小元素，那么存在元素an+1满足an+1an.因为在这个偏序集只有有穷个元素，这个过程一定结束并且具有极小元素an.,我们将要描述的拓扑排序算法对任何有穷非空偏序集都有效 为在偏序集（A,）上定义一个全序，首先选择一个极小元素a

31、1；由引理1这样的元素存在。接着，A-a1，也是一个偏序集。如果它是非空的，选择这个偏序集的一个极小元素a2.然后再取走a2，如果还有其他的元素留下来，在 A-a1,a2 中选择一个极小元素a3。继续这个过程，只要还有元素留下来，就在 A-a1,a2,ak 中选择一个极小元素ak+1.,因为A是有穷集，这个过程一定终止。最终产生一个元素序列a1,a2,an.所需要的全序定义为a1 a2.an这个全序是与初始的偏序相容的。为看出这一点，注意如果在初始的偏序中bc,c在算法的某个阶段被选择为极小元素，则这时b已经被移出，否则c就不会是极小元素。关于这个拓扑排序算法的伪代码在算法1中给出。,【exa

32、mple 25】找出对于偏序集(1，2，4，5，12，20，|)的一个相容的全序。Solution：第一步是选择一个极小元素。这个元素一定是1，因为他是唯一的极小元素。下一步选择（2，4，5，12，20，|）的一个极小元素。在这个偏序集中有两个极小元素，即2和5.我们选择5.剩下的元素是2，4，12，20。在这一步，唯一的极小元素是2.下一步选择4，因为它是（4，12，20，|）的唯一极小元素。因为12和20都是（12，20，|）的极小元素，下一步选哪一个都可以，我们选20，只剩下12作为最后的元素。,产生的全序是15242012这个排序算法所使用的步骤在下图中给出。,在项目的安排中常会用到拓

33、扑排序。【example 26】一个计算机公司的来发项目需要完成7个任务。其中某些任务只能在其他任务结束后才能开始。考虑如下建立任务上的偏序，如果任务Y在X结束后才能开始，则任务X任务Y。这7个任务关于这个偏序的哈塞图如下示。求一个全序，使得可以按照这个全序执行这些任务以完成这个项目。,Solution：可以通过执行一个拓扑排序得到7个任务的排序。排序的步骤显示在下图中。这个排序的结果，ACBEFDG,下面那些集合是偏序集？在偏序集（Z+,|）中下面哪对是可比的？a）5，15 b）6，9 c）8，16 d）7，7,【练习】,Solution：1.满足自反、反对称和传递性质的关系才是偏序关系。可以得到 a)是偏序集 b)不是偏序集。因为它不满足上面三个性质中的任何一个。c)是偏序集。d)不是偏序集。因为它不是自反的。,Solution：2.,2.确定由线面的0-1矩阵表示的关系是否为偏序。,3.确定以下3个有向图所表示的关系是否为偏序？,a,b,c,4.找出下面英语字母串的字典顺序。,本节内容到此结束,谢谢大家！,