集合与简易逻辑【义】

《 集合与简易逻辑【义】》由会员分享，可在线阅读，更多相关《 集合与简易逻辑【义】（7页珍藏版）》请在金锄头文库上搜索。

1、第一章 集合与简易逻辑一、基础知识 定义 1 一般地，一组确定的、互异的、无序的对象的全体构成集合，简称集，用大写字 母来表示；集合中的各个对象称为元素，用小写字母来表示，元素在集合 A 中，称属xx 于 A，记为，否则称不属于 A，记作。例如，通常用 N，Z，Q，R，Q+分别AxxAx 表示自然数集、整数集、有理数集、实数集、正有理数集，不含任何元素的集合称为空集， 用来表示。集合分有限集和无限集两种。 集合的表示方法有列举法：将集合中的元素一一列举出来写在大括号内并用逗号隔开表示 集合的方法，如1，2，3；描述法：将集合中的元素的属性写在大括号内表示集合的方法。例如有理数，分别表示有理数集

2、和正实数集。0xx定义 2 子集：对于两个集合 A 与 B，如果集合 A 中的任何一个元素都是集合 B 中的元素， 则 A 叫做 B 的子集，记为，例如。规定空集是任何集合的子集，如果 A 是BA ZN B 的子集，B 也是 A 的子集，则称 A 与 B 相等。如果 A 是 B 的子集，而且 B 中存在元素不 属于 A，则 A 叫 B 的真子集。定义 3 交集，.BxAxxBA且I定义 4 并集，.BxAxxBA或U定义 5 补集，若称为 A 在 I 中的补集。,1AxIxxACIA且则定义 6 差集，。,BxAxxBA且定义 7 集合记作开区间，集合,baRxbxax),(ba记作闭区间，R

3、 记作,baRxbxax,ba).,(定理 1 集合的性质：对任意集合 A，B，C，有： （1） （2）；);()()(CABACBAIUIUI)()()(CABACBAUIUIU（3） （4）);(111BACBCACIU).(111BACBCACUI 【证明】这里仅证（1） 、 （3） ，其余由读者自己完成。 （1）若，则，且或，所以或)(CBAxUIAxBxCx)(BAxI，即；反之，则)(CAxI)()(CABAxIUI)()(CABAxIUI或，即且或，即且，即)(BAxI)(CAxIAxBxCxAx)(CBxU ).(CBAxUI（3）若，则或，所以或，所以BCACx11UACx1

4、BCx1AxBx，又，所以，即，反之也有)(BAxIIx)(1BACxI)(111BACBCACIU .)(111BCACBACUI定理 2 加法原理：做一件事有类办法，第一类办法中有种不同的方法，第二类办法n1m中有种不同的方法，第类办法中有种不同的方法，那么完成这件事一共有2mnnm种不同的方法。nmmmNL21定理 3 乘法原理：做一件事分个步骤，第一步有种不同的方法，第二步有种不n1m2m同的方法，第步有种不同的方法，那么完成这件事一共有nnm种不同的方法。nmmmNL21 二、方法与例题 1利用集合中元素的属性，检验元素是否属于集合。例 1 设，求证：,22ZyxyxaaM（1）；)

5、( ,12ZkMk（2）；)( ,24ZkMk（3）若，则MqMp,.Mpq证明（1）因为，且，所以Zkk1,22) 1(12kkk.12Mk（2）假设，则存在，使，由于和)(24ZkMkZyx,2224yxkyx 有相同的奇偶性，所以是奇数或 4 的倍数，不可能等于yx )(22yxyxyx，假设不成立，所以24 k.24Mk（3）设，则Zbayxbaqyxp,2222)(2222bayxpq22222222aybxbyaaMyaxbybxa22)()(（因为） 。ZyaxbZyaxa,2利用子集的定义证明集合相等，先证，再证，则 A=B。BA AB 例 2 设 A，B 是两个集合，又设集合

6、 M 满足 ，求集合 M（用 A，B 表示） 。BAMBABAMBMAUUUIII,【解】先证，若，因为，所以MBA)(I)(BAxIBAMAII，所以； MxMAx,IMBA)(I再证，若，则1）若，则)(BAMIMx.BAMBAxUUUAx；2）若，则。所以BAMAxIIBxBAMBxII).(BAMI综上，.BAMI 3分类讨论思想的应用。例 3 ，若02,01,023222mxxxCaaxxxBxxxA，求CCAABAIU,.,ma【解】依题设，再由解得或，2 , 1A012aaxx1 ax1x因为，所以，所以，所以或 2，所以或 3。ABAUAB Aa111a2a因为，所以，若，则，

7、即，CCAIAC C082m2222m若，则或，解得CC1C2. 3m综上所述，或；或。2a3a3m2222m 4计数原理的应用。 例 4 集合 A，B，C 是 I=1，2，3，4，5，6，7，8，9，0的子集， （1）若，IBAU 求有序集合对（A，B）的个数；（2）求 I 的非空真子集的个数。 【解】 （1）集合 I 可划分为三个不相交的子集；AB，BA，中的每个元素恰属于IBA,I 其中一个子集，10 个元素共有 310种可能，每一种可能确定一个满足条件的集合对，所以 集合对有 310个。 （2）I 的子集分三类：空集，非空真子集，集合 I 本身，确定一个子集分十步，第一步， 1 或者属

8、于该子集或者不属于，有两种；第二步，2 也有两种，第 10 步，0 也有两种，由乘法原理，子集共有个，非空真子集有 1022 个。1024210 5配对方法。例 5 给定集合的个子集：，满足任何两个子集的交集非, 3 , 2 , 1nILkkAAA,21L空，并且再添加 I 的任何一个其他子集后将不再具有该性质，求的值。k【解】将 I 的子集作如下配对：每个子集和它的补集为一对，共得对，每一对不能同12n在这个子集中，因此，；其次，每一对中必有一个在这个子集中出现，否则，k12nkk若有一对子集未出现，设为 C1A 与 A，并设，则，从而可以在1AAIACA11个子集中再添加，与已知矛盾，所以

9、。综上，。kAC112nk12nk 6竞赛常用方法与例问题。定理 4 容斥原理；用表示集合 A 的元素个数，则A,BABABAIU，需要xy 此结论可CBACBCABACBACBAIIIIIUU以推广到个集合的情况，即n nikji jinkjijiiniiAAAAAAA111IIIU.) 1(11ILniinA定义 8 集合的划分：若，且，IAAAnULUU21),1 (jinjiAAjiI则这些子集的全集叫 I 的一个-划分。n 定理 5 最小数原理：自然数集的任何非空子集必有最小数。 定理 6 抽屉原理：将个元素放入个抽屉，必有一个抽屉放有不少于1mn) 1( nn个元素，也必有一个抽屉

10、放有不多于个元素；将无穷多个元素放入个抽屉必有1mmn 一个抽屉放有无穷多个元素。 例 6 求 1，2，3，100 中不能被 2，3，5 整除的数的个数。【解】 记，（2（2,1001,100, 3 , 2 , 1xxxxAI记为整除能被且L，由容斥原理，5 ,1001,3 ,1001xxxCxxxB 3100 2100CBAACCBBACBACBAIIIIIUU，所以不能被 2，3，5 整除的数有7430100 15100 10100 6100 5100 个。26CBAIUU例 7 S 是集合1，2，2004的子集，S 中的任意两个数的差不等于 4 或 7，问 S 中最 多含有多少个元素？

11、【解】将任意连续的 11 个整数排成一圈如右图所示。由题目条件可知每相邻两个数至多有 一个属于 S，将这 11 个数按连续两个为一组，分成 6 组，其中一组只有一个数，若 S 含有 这 11 个数中至少 6 个，则必有两个数在同一组，与已知矛盾，所以 S 至多含有其中 5 个 数。又因为 2004=18211+2，所以 S 一共至多含有 1825+2=912 个元素，另一方面，当时，恰有，且 S 满足题目条,2004,10, 7 , 4 , 2 , 1,11NkrttkrrS912S件，所以最少含有 912 个元素。例 8求所有自然数，使得存在实数满足：)2( nnnaaa,21L.2) 1(

12、, 2 , 11nnnjiaajiL【解】 当时，；当时，；当时， 2n1, 021aa3n3, 1, 0321aaa4n。下证当时，不存在满足条件。1, 5, 2, 04321aaaa5nnaaa,21L令，则naaaL210.2) 1( nnan所以必存在某两个下标，使得，所以或ji 1njiaaa1111nnnaaaa，即，所以或，21aaann12a1,2) 1(1nnnaanna2) 1( nnan。12a（）若，考虑，有或，1,2) 1(1nnnaanna2na22nnaa22aaann即，设，则，导致矛盾，故只有22a22nnaa121nnnnaaaa. 22a考虑，有或，即，设

13、，则3na23nnaa33aaann33a23nnaa，推出矛盾，设，则，又推出矛02212aaaann33a2311aaaann盾， 所以故当时，不存在满足条件的实数。4,22naan5n（）若，考虑，有或，即1,2) 1(2annan2na12nnaa32aaann，这时，推出矛盾，故。考虑，有23a1223aaaa21nnaa3na或，即=3，于是，矛盾。因此23nnaannaa33a3a123nnaaaa，所以，这又矛盾，所以只有，所以32nnaa12211aaaann22aan 。故当时，不存在满足条件的实数。4n5n 例 9 设 A=1，2，3，4，5，6，B=7，8，9，n，在

14、A 中取三个数，B 中取两个数组成五个元素的集合，求的最小值。iA.201 , 2,20, 2 , 1jiAAijiILn【解】 .16minn设 B 中每个数在所有中最多重复出现次，则必有。若不然，数出现次（iAk4kmk） ，则在出现的所有中，至少有一个 A 中的数出现 3 次，不妨设它是4k.123 kmiA1，就有集合1，其中，121,bmaa, 1, 1365243bmaabmaa61 ,iAai为满足题意的集合。必各不相同，但只能是 2，3，4，5，6 这 5 个数，这不可能，所以ia. 4k20 个中，B 中的数有 40 个，因此至少是 10 个不同的，所以。当时，如iA16n16n下 20 个集合满足要求： 1，2，3，7，8， 1，2，4，12，14， 1，2，5，15，16， 1，2，6，9，10，1，3，4，10，11， 1，3，5，13，14， 1，3，6，12，15， 1，4，5，7，9， 1，4，6，13，16， 1，5，6，8，11，