离散数学课件-第4章-7

《离散数学课件-第4章-7》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、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，因此≥是反对称的。

2、最后，因为a≥b和b≥c，所以≥是传递的。从而≥是整数集合上的偏序且（Z,≥）是偏序集。【example2】整除关系“

3、”是正整数集合上的偏序，因为由前几节所述，它是自反的、反对称的和传递的。我们看到（Z+,

4、）是偏序集（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.使用这个记号

5、是由于“小于或等于”关系是偏序关系的范例。注意：符号≼表示任意偏序关系，并不仅仅是“小于或等于”关系。记号a

6、)中，2与3没关系，3与2也没关系。由此得到定义2.定义2：偏序集(S,≼)的元素a和b叫做可比的，如果a≼b或b≼a。当a和b是S的元素并且既没有a≼b，也没有b≼a，则称a与b是不可比的。【example4】在偏序集

7、(Z+,≼)中，整数3和9是可比的吗？5和7是可比的吗？整数3和9是可比的，因为3

8、9.整数5和7是不可比的，因为5不能整除7，并且7也不能整除5.用形容词“部分的（偏的）”描述偏序是由于一些对元素可能是不可比的。当集合中的每对元素都可比时，这个关系叫做全序。定义3：如果(S,≼)是偏序集，且S的每对元素都是可比的，则S叫做全序集或线序集，且≼叫做全序或线序。一个全序集也叫做链。【example5】偏序集(Z,≤)是全序集，因为只要a和b是整数，就有a≤b或b≤a。【example6】偏序集(Z+,

9、)不是全序集，因为它包含着不可比的元素，例如5和7.定义4：对于偏序集(

10、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之间不满

11、足≤关系,与≤是全序矛盾。∴是良序集。【example7】正整数的有序对的集合Z+×Z+与≼构成良序集，对于(a1,a2)和(b1,b2),如果a1

12、所有的x∈S为真。那么存在一个元素y∈S使得P(y)为假。于是集合A={x∈S

13、P(x)为假}是非空的。因为S是良序的，集合A有最小元素a.易知a不等于x0,因为从基础步知道P(x0)为真。根据a是选自A的最小元素，我们知道对所有的x∈S(x