离散数学电子教材3a.doc

《离散数学电子教材3a.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3章集合与关系集合是数学中最基本的概念之一，是现代数学的重要基础，并且已渗透到各种科学与技术领域中。对计算机工作者来说，集合论是不可缺少的数学工具，例如在编译原理、开关理论、数据库原理、有限状态机和形式语言等领域中，都已得到广泛的应用。集合论的创始人是康托（G.Cantor，1845—1918）。他所做的工作一般称为朴素集合论。由于朴素集合论在定义集合的方法上缺乏限制，从而出现了称之为悖论的某些矛盾。为了消除这些悖论，很多数学家，象Hilbert、Fraenkel和Zermelo等都认真研究了产生悖论的原因，并在致力于问题解决的过程中，获得了种种出色的发现，由此导致了公理化的

2、集合论系统的建立，使集合理论日臻完善。本章介绍的集合论十分类似于朴素集合论，它具有数学分支的基本特征，象平面几何中的点、线、面一样，采纳不加定义的原始概念，提出符合客观实际的公设，确立推理关系的定理。在我们规定的范围内，既不会导致悖论，也不会影响结论的正确性。本章重点讨论关系（主要是二元关系），它仍然是一种集合，但它是一种更为复杂的集合。它的元素是序偶，这些序偶中的两个元素来自于两个不同或者相同的集合。因此，关系是建立在其它集合基础之上的集合。关系中的序偶反映了不同集合中元素与元素之间的关系，或者同一集合中元素之间的关系。本章将讨论这些关系的表示方法、关系的运算以及关系的性质，

3、最后讨论集合上几类特殊的关系。3.1集合的基本概念3.1.1集合与元素集合(set)（或称为集）是数学中的一个最基本的概念。所谓集合，就是指具有共同性质的或适合一定条件的事物的全体，组成集合的这些“事物”称为集合的元素。例如：班里的全体同学、全国的高等学校、自然数的全体、直线上的所有点等，均分别构成一个集合，而同学、高等学校、每个自然数、直线上的点等分别是所对应集合的元素。集合常用大写字母表示，集合的元素常用小写字母表示。若是集合，是的元素，则称属于，记作；若不是的元素，则称不属于，记作。若组成集合的元素个数是有限的，则称该集合为有限集(FiniteSet)，否则称为无限集(I

4、nfiniteSet)。表示集合的方法通常采用列举法和描述法。如果集合的所有元素都能列举出来，则可把它们写在大括号里表示该集合，此为列举法。例如，，{课桌，灯泡，自然数，老虎}，，{…}。应该注意，与是不同的。表示一个元素；而表示仅含有一个元素的集合，称之为单元素集。如果可利用一项规则，以便决定某一事物是否属于该集合，此为描述法。例如：是正奇数}，是中国的省}，，或。如果我们用表示任何谓词，则可表示集合。设集合为，如果114为真，那么，否则。3.1.2集合间的关系外延性原理：如果、是集合,则当且仅当的每一元素都是的元素而且的每一元素都是的元素时，有。当且仅当。两个集合相等，记作

5、；两个集合不相等，则记作。集合的元素还可以允许是一个集合。例如：必须指出：但；同理，，但。例题3.1.1(1)但在讨论的集合中，元素具有无序性且同一元素的重复没有意义。(2)设谓词：“为的元素或为的元素自身独自构成的集合”且设，则。(3)常见集合专用字符的约定：—自然数集合(非负整数集)(或)—整数集合(，)—有理数集合(，)—实数集合(，)—分数集合(，)脚标+和-是对正、负的区分—复数集合—素数集合—奇数集合—偶数集合(4)集合表示式的互换：描述式列举式定义3.1.1设、是任意两个集合，假如的每一个元素是的元素，则称是的子集(Subset)，或包含在内，或包含，记作，或。例

6、如：，则。定理3.1.1集合和集合相等的充分必要条件是这两个集合互为子集。证明：设任意两个集合、且，故为真，且也为真，即且。反之，且，假设，则与的元素不完全相同，设有一元素且，这与矛盾；或设某一元素，但，这就与矛盾。故、的元素必须相同，即。根据子集的定义及定理3.1.1显然有：对任意两个集合，，，114；（自反性）（反对称性）（传递性）定义3.1.2若集合的每一个元素都属于，但集合中至少有一个元素不属于，则称是的真子集(ProperSubset)，记作，读作真包含于。例如：整数集是有理数集的真子集。定义3.1.3不包含任何元素的集合是空集(EmptySet)，记作。，是任意谓词

7、。例如：是一个空集。注意：，但。定理3.1.2对于任意一个集合，。证明：假设是假，则至少有一个元素，使且，因为空集不包含任何元素，所以这是不可能的。对于每个非空集合，至少有两个不同的子集：和，即和，我们称和是的平凡子集。一般的说，的每个元素都能确定的一个子集，即若，则。定义3.1.4在一定范围内，如果所有集合均为某一集合的子集，则称该集合为全集(UniversalSet)，记作。对于任一，因，故，即恒真，是任意谓词。全集的概念相当于论域，如在初等数论中，全体整数组成了全集。在考虑某大学的部分