集合论第1章集合及其运算.docx

《集合论第1章集合及其运算.docx》由会员分享，可在线阅读，更多相关《集合论第1章集合及其运算.docx（37页珍藏版）》请在三一文库上搜索。

1、集合论与图论以前学习的高等数学（数学分析）都是连续函数，而计算机是离散型结构，所以它所研究的对象应是离散型的。因此，做为计算机理论的核心课程离散数学就显然非常重要，计算机专业学生必须开设此课程。目的 ：培养学生抽象思维和逻辑思维的能力要求 ：概念第一，正确使用概念进行正确的推理。特点 ：抽象，概念多；与其它课程不同，不是以计算为主，而是以推理论证为主；比较难。内容 ：集合映射集合论关系无穷集合图的基本概念树和割集离散数学图 论连通度和匹配平面图的欧拉公式和图的着色有向图近世代数数理逻辑形式语言与自动机可计算理论等等离散：不考虑实数的性质，只考虑有限或可数的整数。因此可用归纳法。1第一篇集合论集

2、合论是德国数学家康托（Cantor ）在 1874 年建立的，它是现代数学的基础，在当今数学中每个对象本质上都是集合。有时我们说： “数学能嵌套在集合论中”其含义就是指数学的一些对象如：数、函数、线、面等都可以用集合来定义。换句话说，数学的各个分支在本质上都是研究这种或那种对象的集合。例如：几何学研究点、线、面的集合；数学分析连续函数的集合；代数研究数的集合以及在此集合上定义有关运算的集合等等。因此，把集合论作为现代各种数学的基础是有道理的，也是合适的。集合论的特点：（ 1）研究的 对象十分 广泛 ：数、图形或其它任何客体都可以作为研究的对象。（ 2）因为它研究的对象是如此广泛，为了便于研究必

3、须寻找对象 的共性 ，而要做到这一点，就必须进行抽象。（ 3）在抽象化的基础上，可用统一的方法来 研究和处理 集合论的各类问题。2第一章集合及其运算 1 集合的基本概念在日常生活中， 常会遇到“集合”的概念，例如：所有中国人的 成的集合；坐 面上的有点的集合，自然数集， 数集，全世界无 者等等。集合是集合 中最基本的概念，所以很 出精确的定 。因此，我 把“集合”作 原始的概念 出非形式定 ，只 予一种描述 明 个概念的含 。1.1 集合含 一般地，把一些确定的，可以区分的事物放在一起 成一个整体称 集合， 称集。 成集合的每个事物称 集合的元素（或成 ）。我 的 定 ：把一些互不相同 西放在

4、一起形成一个整体一、怎 理解集合：集合的概念很 ，但准确理解其含 却非易事，注意以下几点：（ 1）集合的元素可以是任何事物，既可以是具体的事物，也可以是抽象的事物， 可以是另外的集合，但构成 个集合的元素决不能是 个集合的自身。（ 2）一个集合的各个元素是可以互相区分的。 意味着，在 个集合中不会重复出 相同的元素。（ 3） 成一个集合的各个元素在 集合中是无次序的。（ 4）任一元素（事物）是否属于一个集合，回答是确定的。也就是 ，a,A, aA或 a A 必有一个成立。二、集合 中三个原始概念：集合、元素、。三、集合与元素的表示符号用大写的字母表示不同的集合：如：A,B,C 用小写的字母表示

5、不同的元素：如：a,b,c 但 种表示不是唯一的，因 某个集合的元素可以是另一个集合。四、几种特殊集合的表示符号N 自然数集合：I (Z ) 整数I (Z ) 正整数I (Z ) 整数Q 有理整数Q 正有理数Q 有理数3R 数R 正 数R 数C 复数等等外延表示法1.2 集合的具体表示方法内表示法一、外延表示法 把集合中的全部元素一一列 出来， 元素之 用逗号隔开， 并把它 用花括号括起来。例： A 1， 2， 3， 4， 5一般 来， 一个集合 含有少数几个元素 ， 才可用 种方法 出。 即使有限个但数量 大， 原 上 种方法也是可行的， 然而 上， 很少能把全部元素列出。 不 当列出几个元

6、素后，就可以看出 成 集合的其他元素的 律 ，也可采用此方法，只列出部分元素，其余用“”来表示。例： a， b， c， x，y， z利用此方法可以表示含有无 多个元素的集合。N 1， 2， 3，二、内涵表示法用集合中元素的共同性 来刻画集合。A x | x 是整数且 1 x5 N x|x 是自然数或 N x|x 是大于零的整数E x|x 2n， nI f(x)|f(x)在 a，b上 等等 0， 1 x| x 0， 1且 x 是 数集合 有其它表示方法， 但上述两种表示方法是常用的。原 上， 能 、 准确而且易于被大家公 的表示方法都是可以使用的。例如 0， 1区 上的所有 数的集合，就可以用

7、0， 1表示。1.3 空集和全集 是两个特殊的集合， 然它 的概念很 ，但在集合中的地位却很重要的。定 1 不含任何元素的集合称 空集， 。符号化表示 ： x | xx例 1 方程 x210 的 根的全体形成的集合就是空集。4定义 2 在给定的问题中，所考虑的所有事物的集合称为全集，记为S。符号化表示为：S x | xx说明： 全集是一个相对的概念，由于所研究的问题不同，所取的全集也不同。1在研究平面解析几何问题时，可以把整个平面取作全集。2在初等数论中，把整数集I 作为全集。即使是同一个问题，也可以取不同的集合。例如 ：有关整数的问题，即可取I 为全集，也可取Q或 R 为全集，但取I 为全集

8、，比取Q或 R 为全集，显然要简便一些。定义 3 仅含有一个元素的集合称为单元集。例 2 方程 x24x40实根的全体形成的集合就是一个单元集2。注意： 2与 2 的区别。推广之： x与 x 的区别 x元素， x集合，x x 。 2 子集、集合的相等在第一节中，“集合”，“元素”、元素与集合间的“属于”关系是三个没有精确定义原始概念。对它们仅给出了直观的描述，来说明它们的各自含义。在本节中将利用这三个概念定义集合的子集，集合间的包含关系，集合的相等，幂集，集族等概念。2.1 子集定义 4 设 A,B 是两个集合， 若集合 A 中的每个元素都是B 的元素，则称 A 是 B 的子集合简称子集，这时

9、也说A 包含在 B 里，或 B 包含着 A。A 是 B 的子集记为AB（或 BA ）。ABxA, xB等价地有：AB不在 B 中的元素必不在A 中。一、例题例 1 N自然数， Q有理数， R实数， C复数，则NQRC例 2 a a,b a,b, c二、集合不包含若 A 不是 B 的子集，则记为A ? B （ A 不包含在 B 里）。显然5例 3 若 A a,b, B a, c, d ，则 A ? B 。于是A ? BxA使得 xB三、真包含定义 5 设 A,B 为两个集合，若AB 且xB 使得 xA ，则称 A 是 B 的真子集，记为 AB 。即ABAB 且xB 使得 xA 。例 4（ 1）设

10、 A a, b, B a,b, c ，则 AB 。（ 2） NQRC四、注意 ：“”与“”的区别“”元素与集合间的属于关系，而“”是集合间的包含关系。2.2集合相等定义 3 设 A,B 是两个集合，若AB 且 BA ，则称 A 与 B 相等。并记为A B。即ABAB 且 BA 。一、 例题例 4 设 A2,3 ， B 为方程 x25x60 的根形成的集合，则A B。二、集合不相等若集合 A 和集合 B 不相等，则记为A B。即A BA?B 或 B?A。三、说明：（ 1）AB，说明 A 和 B 是由完全相同的元素组成的，并不意味着它们是由相同的定义出来。（ 2）有集合不相等有：ABAB 且 AB

11、（ 3）定义 3 给出了一个重要原则：要证明两个集合相等，唯一的方法就是证明每一个集合中的任一元素均是另一个集合的元素，称为 互为子集法。这种方法必须掌握，它贯穿在本书的各章中，考试必考。在前面我们说过，集合中的元素可以是具体也可以是抽象的，甚至可以是其它的集合，于是就得到了一个定义集族。实际上，集族并不是一个新概念，只是提醒大家，这个集合中的元素也是集合罢了。于是62.3集族定义 6 以集合为元素的构成集合称为集族。例 1 在学校中，每个班级的学生形成一个集合，而全校就是各个班形成的一个集族。例 2 设 A1 , A2 , A3 为集合，则 A1 , A2 , A3 为一个集族。若令 I1,

12、2,3 ，则 i I ， i确定了一个唯一的集合Ai ，于是集族 A1 , A2 , A3 ，又常写成 Ai i I，即 I 中元素 i 确定的那些集形成的集族。I 称为标号集。2.4 幂集定义 5 集合 S 的所有子集 （包括空集及S 本身 ）形成的集族称为S 的幂集，记为 2S 或P(S) ，于是 2S A | AS 。例 1 设 S, 则2S ；设 S1, 则2S,1 ；设 S1,2, 则2S,1,2, 1,2；设 S1,2,3，则 2S ,1,2,3, 1,2, 1,3,2,3 , 1,2,3 。S 有共八个子集。说明 ：（ 1） S 有 n 个元素，则S 有个 2n 个子集。这就是为

13、什么采用符号2S 的原因。（ 2）和 的区别与联系。区别 ：空集， 一个集族，这个集族只有一个元素，就是空集。联系： ，但 且 。又 , 含有两个元素。而其它的集合没有此性质，即A, A A 与 A A 不能同时成立。3.2 性质定理 1（ 1）空集是任一集合的子集。（ 2）空集是唯一的。证：（ 1）证 I 设 A 是任一集，由于空集没有任何元素，所以断言中每个元素均是A的元素成立。因此按子集的定义有A ，即是 A 的子集。7证 II由 AB不在 B中元素，必不在A 中，因此A 。（ 2）设,都是空集，由（1）可知，且，于是，从而空集是唯一的。 3 集合的基本运算集合的基本运算就是以给定的集合

14、作为对象，根据确定规则得到另外一些集合。 给定若干集合，可以通过集合的并、交、差，对称差和余集等运算产生新的集合。3.1 并、交运算一、定义定义 1 设 A，B 是任意两个集合，则由至少属于集合A 与集合 B 之一的一切元素组成的集合，称为集合A 和 B 的并集，记为AB 。即AB x | xA或xB例 1（ 1）设 A1,3,5, B2,4,6, ，则 AB1,2,N 。（ 2） A a,b, c, d, B b, d, e, f ，则 AB a, b, c, d ,e, f 在这里： b,d 既是 A 又是 B 的元素，在并集AB ， b 和 d 只能写一次，因为AB 是由互不相同的元素组

15、成的。定义 2 设 A， B 是任意两个集合，则由既属于A 又属于 B 的一切元素组成的集合，称为集合 A 与集合 B 的交集，记为AB 。即AB x | xA且xB例 2（ 1） A1,3,5, B2,4,6, AB（ 2） A a,b, c, d, e, f , B c, d, e, f , g ，则 AB c, d ,e, f 。说明：（ 1）当两个集合的交集为空集时，则称它们是不相交的。（ 2）两两不相交：设A1 , A2 , An 是 n 个集合，若Ai , Aj (ij ) 有 AiAj，则称 A1 , A2 , , An 是两两不相交的。（ 3）两个集合并、交运算可以推广到多个集

16、合上去。n设 A1 , A2 , A3 ,An 是 n 个集合，则这n 个集合的并运算和交运算可简单记为Ai 和i18nAi 。于是有：i 1nAiA1A2Ani 1nAiA1A2Ani1当 n 无穷大时，可记为：AiA1A2An,AiA1A2Ani1i1二、性质（ 并、交运算以及它们之间的关系）定理 1 设 A,B,C 是任意三个集合，S 为全集，则（ 1）交换律成立，即ABBA（ 2）结合律成立，即( AB)CA( BC )（ 3）幂等律成立，即AAA（ 4）AA（ 5） S A S（ 6） ABBAB定理 2 设 A,B,C 是任意三个集合，S 是全集，则（ 1） ABBA（ 2） (

17、A B) C A( B C )（ 3） AAA（ 4）A（ 5） SAA（ 6） ABAAB下面看两个运算（和）的关系，主要是看分配律和吸收律。定理 3 设 A,B,C 是任意三个集合，则（ 1） A(BC )( AB)( AC )（ 2） A(BC )( AB)( AC )9（ 3） A( AB)A（ 4） A ( A B) A3.2差运算一、定义定义 3 设 A， B 是任意两个集合，则由属于 A 但不属 B 的一切元素组成的集合，称为 A 与 B 的差集（或称集合 B 对集合 A 的相对补集），记为 AB（或 A-B）。即A B x | xA但xB例 3（ 1） A a,b, c, d,

18、 e, f , B c, d, e, f ，则 A B a, b 。（ 2） A1,2,3,4, B 3,4,5,6,7，则 A B1,2 。（ 3） A3, B 1,2,3,4 ，则 AB。由此推出（ 4）A。二、性质（差运算以及差与并、交运算的关系）定理 4 设 A,B,C 是三个任意集合，则（ 1） ABA ( AB)（ 2） A B A BC下面看并、交运算与差运算的关系（ 3） ( AB)BBA证：两边同时交上 B ，即 B( A B)BB A ，有 B B A ，故 B A 。因为A B A，所以 ( AB) BA；而 A( A B) B 是永真式。B A故 ( A B) B A（

19、 4） A(B C )( AB) ( AC )证：证xA( B C ) ，则 xA 且 xB C ，即而 xA 且 xB 但 xC ，于是 xAB 但 xAC ，即 x( AB)( AC ) 。从而10A( B C )( AB) ( AC )反之，x( AB)(AC ) ，有 xAB 但 xAC ，即 xA 且 xB 但xC 。于是 xBC 且 xA，即 xA(B C ) ，从而( AB) ( AC )A(B C ) 。由集合相等的定义得：A( B C )( AB)( AC )证 右边 (A) (AC) (A B) (AC)CB( A B) ( ACC C ) ( A B) AC ( A B)

20、 CC （ A B） CCA （B CC） A （B C） 左边（ 5） A (B C ) ( A B) C证： 右()()C(C)() 。A B C A B CA B CA B C3.3 对称差一、定义定义 4 设 A， B 是任意两个集合，则差集AB 与 BA 的并集称为集合A 与集合 B 的对称差，记为 AB （或 AB ）。即：A B( AB)(BA)例 4（ 1） A a,b, c, d, B a,d , e, f ，则 AB b, c f ,e b,c, e, f 。（ 2） A1,2,3, B2,4,6, ，则 AB1,2,N 。二、性质定理 5 设 A,B,C 是任意三个集合，

21、则（ 1）交换律成立，即 A B B A（ 2）结合律成立，即 ( A B) C A (B C )（ 3）分配律成立，即A(B C )( AB)(AC )证： A( B C )A( BC )(CB) A( B C ) A(CB)( AB) ( AC )( AC ) ( AB)( AB) AC 11（ 4） A A（ 5） AA, A SS AAC（ 6） A ( A B) B证： A ( A B)(A A)BBB3.4余集运算一、定义定义 5 设 S是集合，AS ，则差集 SA 称为集合A 对集合 S的余集，记为AC 。即ACSA 。说明 ：在有些书中， 余集也称为A 的绝对补集或A 对 S

22、相对补集或补集，而且记号也未统一。有的作者用：CS A, A , A 等表示A 的余集，在本书用AC表示 A的余集。例 5（ 1） SN , A1,3,5, , AS ，则 ACSA2,4,6, 。（ 2） , , , , , ,C , 。S a b c d A c d A S A a b二、性质定理 6 设 A是任意一个集合，S 是全集，则（ 1） SC（ 2） C S（ 3） A AC S（ 4） A AC（ 5） ACS AA S并与交运算与余集的关系定理 7 设 A,B 是任意两个集合则（ 1） ( AB)CACBC（ 1）（ 2） ( AB)CACBC（ 2）（ 3）若 A B ，则

23、 BCAC12（ 4） ( AC )C A（ 1）、（ 2）称为 De Morgan 公式把 De Morgan 公式推广到多个集合上去。设 A1, A2 , , An 是 n 个集合，则ncnncnAiAic ,AiAici1i1i1i1当 n 无穷大时，则ccAiAic ,AiAici 1i 1i 1i 13.5 文氏图集合间的关系和有关的运算可以用文氏图给予形象的描述。文氏图的构造方法如下：（ 1）首先画一个大矩形表示全集S，矩形内的点表示全集中的元素；（ 2）在矩形内画一些圆表示不同的集合，用圆内的点表示相应的元素。于是，用文氏图就可以表示集合间关系的集合和集合的五种基本运算了。如图

24、1 所示表示集合间关系。SSSSABAABABA 与 B 不相交A 与 B 相等SABAAB且 A B图 1如图 2 所示表示集合间的五种运算。13图 2文氏图是数学上常用的方法。优点 ：形象直观、易于理解；缺点： 理论基础不够严谨，因此只能用于说明，不能用于证明。3.6 对偶原理利用 De Morgan 公式，余集的基本性质和性质（3）若 AB ，则 BCAC 就可以推出对偶原理。对偶原理：若有关集合的并、交及余集运算的某一关系式成立，则将式中记号：, , , 分别换成 , , , 等号不变，并将式中每一个集合换成它的余集。由此得到的新的关系式也一定成立。例 6 若 ( CB)CB成立，则(

25、 ABC)CCC成立。AB3.7 例题例 1 设 A,B,C 是三个任意集合，若AB, BC ，则 AC 可能吗？ AC 常真吗？举例说明。解：（ 1） A a, B a, C a, a，则有 AB, BC , AC（ 2）A C 也不常真。 例： A a, B a,C a, AB, BC ，但 A C 。例 2 设 A,B,C 是任意三个集合：（ 1）若 ABAC ，则有 BC 吗？（ 2）若 ABAC ，则有 BC 吗？（ 3）若 ABAC 且 A BAC ，则有 BC 吗？解：（ 1）、（ 2）不成立，（ 3）成立。反例如下：14（ 1） A1,2,3, B1,2, C1,3 ，则 AB

26、AC ，但 BC 。（ 2） A1,2,3, B2,4, C2,5 ，则 ABAC ，但 BC 。（ 3）证明： B B( B A)B (C A)( BC )( B A)( B C ) (CA) C (B A) C (C A) C例 3 设 A,B 为任意集合，证明（ 1） ABP(A)P(B)AB（ 2） P( A)P(B)AB分析：1. 要证两个集合之间有包含关系，利用定义证明方法；2. 要知道 P( A) 与 P( B) 的定义。证：（ 1） xP( A) ，有 xA ，而 AB ，故 xB ，即 xP( B) 。所以 P( A)P( B) 。反之，xA ，则 xA ，即 xP( A)

27、，又 P( A)P(B) ，所以 xP( B) ，即 xB ，所以 xB ，即 AB 。（ 2）P( A)P( B)(P( A)P( B)(P( B)P( A)ABBAAB例 4 设 A,B 是任意两个集合，AB 与 AB 这可能吗？证明你的断言。 分析：由于集合元素可以是具体的也可以是抽象的，还可以是集合。 因此， 一个集合完全可以成为另一个集合的元素，同时又是另一集合的子集。解： 若 A a, B a, a ，则有 AB, AB 。例 5 设 A,B 是任意集合，则（ 1）若 A B B ，则 A B 有何关系？（ 2） A B B A，则 A 与 B 又有何关系。证：（ 1）由 ABB

28、，则可得出AB。证 设 B，则xB ，由 A BB ，得 xA B ，即 xA但 xB ，这与 xB矛盾，所以B。而由 ABB ，得 A，即 A，故 AB。证 因为 A BB ，所以 ABCB ，再边同交上B 有 ( ABC )BBBB ，15由于运算“”满足结合律，故(C)(C)ABB AB，于是B AAB 。所以 BA , AB。说明： 证明 2 简单明确， 但对初学者而言， 前一论证更好地揭示了命题的含义。在对集合论有了更深层的理解之后，第二种证法就不难给出了。通常情况下， 证明一个集合为空集，一般都采用反证明。（ 2）由 ABB A ，可导出 AB。决不是 AB证 由 ABB A得A

29、BCB AC( A BC ) ( A B) ( B AC ) ( A B)A ( BCB) B ( ACA) A E B E A B证： 这种证法的思路是通过证明，AB 和 BA 来导出 A B 的，为此，要先证明A BAB 。因为 ABBA，而A B ( A B) ( A B) ( A B) ( B A) A BCB AC。故由 A BB A，得 A BA B 。同理，由 A,B 的对称性得：B AA BB ABA 。于是由 A BB A得 ( AB)( BA)即 AB ，结论成立。例 6 若 ( A B) (B A)C ，则 A (B C ) (C B)A B C。 分析 ：若对集合的余集

30、和对称差的定义能较好的理解，则此题不难证明。 此外本题也考查对集合的运算的掌握。证：即证明：若 ABC，则 A(BC )(C B)B CB ( AB)( BA)B( ABC )( BAC )B ( ABC ) ( A B)( B AC ) B ，故 A ( B C ) 。例 7 若 A,B,C 是任意集合，当 ABAC 且 ACBACC ，是否有 B=C？证16BBEB( AAC )( BA)(BAC )( AB)( ACB)(AC)( ACC)( AAC )CECC证 证 BC(BC )(CB)xB ，若 xA，则 xAB ，又 ABAC ，有 xAC ，所以 xC ，即 BC 。若 xA

31、，则 xAC ，所以 xACBACC ，有 xA CC，所以 xC ，即 BC ，综上有：BC 。同理可得： CB 。故 B C 。例 8 设 A,B,C 是集合，求下列各式成立的充分必要条件（ 1） ( A B) ( A C ) A（ 2） ( A B) ( A C )（ 3） ( A B) ( A C )（ 4） ( A B) ( A C )解：（ 1）()() (C) (C)(CC)A BA CA BA CA B CA(BC )CA ( BC)A于是这个等式成立充分必要条件是ABC。（ 2） ( A B) ( A C )A ( B C )A (B C )（ 3）() ()(C)(C)(CC)()，A BA CA BA CA B CA B C于是要使 ( A B)( AC)成立，必有 ABC