离散数学第3章(1-6)(新教材)

《离散数学第3章(1-6)(新教材)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二篇集合论基础第三章集合与关系第一节集合的基本概念一般教科书中都把若干有某种共同性质、彼此不同的东西(元素)放在一起就构成一个集合.实际上没有共同性质的若干个对象放在一起也可认为作成一个集合。集合是数学中不能精确定义的少数概念之一.若元素a属于集合A,记作aA,若元素a不属于集合A,记作aA.(注)为了避免出现悖论,我们应该避免使用诸如“所有的集合组成的集合”这一类的术语.例1.下面是集合的几个例子:(1)S={1,2,3,4};(2)T={(xR)(x4-10x3+35x2-50x+24=0)}(3)W={z

2、(zZ)

3、(x,y,u,vZ)(x2+y2+u2+v2=z)}集合可以用列举法和描述法这两种方法加以表达.列举法通常适用于元素个数较少的有限集合,而描述法则通常适用于元素个数较多以及无限的集合.集合具有如下四个重要的性质:(i)集合元素的确定性:即对具体一个集合的元素而言,一个元素或在此集合中,或不在此集合中,二者必居其一;(ii)集合元素的无重复性:即集合的元素彼此不同,没有重复的元素在同一个集合中重复出现;(iii)集合元素的无序性:例如我们认为{1,2}={2,1};(iv)集合元素的抽象性:集合中的元素不必是具体的事物,

4、也可以是抽象的对象,甚至集合也可以作为集合的元素.定义1.1(集合相等的定义):两个集合A和B是相等的,当且仅当A和B有相同的元素,记作A=B;集合A与集合B不相等,记作AB;例如上面例1中的(1)和(2)中的两个集合S和T,不难看出它们实际上是两个相同的集合,也即有S=T.再看上面例1中的(3),根据数论中著名的Lagrange四平方定理(该定理的结论是:每个自然数都可以表示成四个整数的平方数之和)可以看出:这个例子中的集合W与全体自然数组成的集合N也是相等的集合。常用的以数作为元素的集合及其符号表示:N—自然数作成的集合,Z—

5、整数作成的集合,Z+—正整数作成的集合,Q—有理数作成的集合,R—实数作成的集合,C—复数作成的集合;kZ—k的整数倍组成的集合,Zk—{0,1,…,k-1},整数模k的剩余类作成的集合。定义1.2(有限集和无限集)如果一个集合中只有限多个元素,则称之为一个有限集;反之则称之为一个无限集.第二节子集和幂集定义2.1(子集和真子集)。设A、B是任意两个集合,任取xA,都有xB,则称A是B的子集,或A包含在B内,记作AB,或BA.即如果有AB,但AB,也就是说,至少存在一个元素bB,使得bA,则称A是B的一个真子集,记

6、为AB或者BA.根据上述定义不难看出:任何一个集合A都有两个特殊的子集合,一是空集,用符号表示;另一个是集合A自身.它们称为集合A的平凡子集.对于给定的非空集合A,如果除了这两个平凡的子集合之外,它还有其他的子集合,则称之为集合A的非平凡子集.下面的图(称为Venn图)表达了集合B与其子集合A之间的关系:例如,A={1,2},B={1,2,3},则AB,且也有AB.BA例如,设Z是整数集合,2Z是偶数集合,则2ZZ;{{1,2,3}}{a,{1,2,3},1,{a}},{a,{1,2,3}}{a,{1,2,3},1

7、,{a}},但,{1,2,3}{a,{1,2,3},1,{a}},注意“”与“”的意义完全不同.“”显然有性质:(1)AA;自反性(2)AB且BC,则AC;传递性(注)在每个问题中如果所有出现的集合都是某一集合的子集,称此集合为该问题中的全集,记作E;全集是一个相对唯一确定的集合,根据问题的不同,我们有时需要取不同的集合作为全集。定理2.1集合A和B相等的充分必要条件是A和B互为子集。证明:[1]设A=B,则(x)(xAxB)为真,且(x)(xBxA)为真,即AB,且BA;[2]反之(用反证法

8、),若AB,且BA,假设AB,即A与B的元素不完全相同.不妨设有某一元素xA,但xB,与AB矛盾,若有某xB,但xA,同样与BA矛盾,故A=B.要避免使用“包罗一切的集合”或“由一切集合组成的集合”等术语,否则会导致集合论中的悖论。集合论中的悖论:定义:寻常集----不包含自身作为元素的集合,不寻常集----包含自身作为元素的集合,再定义T是由所有寻常集组成的集合,即,T={A

9、A是寻常集},现在问T是寻常集还是不寻常集?如果:(1)若T是寻常集,它不包含自身作为元素;但根据T的定义,T又应该包含自身

10、作为元素.这就与T是寻常集的假设矛盾;(2)若T是不寻常集,则根据不寻常集的定义,TT,与T是寻常集的集合这一原来的定义相矛盾。定义2.2(幂集)假设A是一个给定的集合,将集合A的每个子集看成一个元素,则集合A的所有子集为元素