集合与简易逻辑(20210317003404)

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

2、别表示有理数集和正实数集。 定义2子集：对于两个集合 A与B,如果集合A中的任何一个元素都是集合 B中的元素， 则A叫做B的子集，记为 A二B，例如N二Z。规定空集是任何集合的子集，如果A是B 的子集，B也是A的子集，则称 A与B相等。如果A是B的子集，而且B中存在元素不属于 A,贝U A叫B的真子集。 定义3交集，A B二xx A且X B. 定义4并集，A B =xx A或x B. 定义5 补集，若 AG I,则G A=x|x I ,且X更A称为A在I中的补集。 定义6差集，A B=XxEA,且x世B。 定义7集合xa ： x b, x R, a ： b记作开区间(a, b)，集合 Xa_x

3、_b,x R,a : b记作闭区间a,b , R记作(-：,=). 定理1集合的性质：对任意集合 代B, C,有： (1) A (B C) =(A B) (A C); (2) A (B C) =(A B) (A C)； (3) GA GB 二 G(A B); (4) C1 A GB 二 G(A B). 【证明】这里仅证(1)、( 3),其余由读者自己完成。 (1 )若A (B C)，则A，且B或C，所以(A B)或(A C), 即 x (A B) (A C)；反之，x (AB) (A C)，则 x (AB)或x(AC), 即 x A且 x B 或 x C，即 x A且 x(B C)，即 x A

4、 (BC). (3 )若 x GA C1 B ,则 x，C1 A 或C1 B，所以 x； A 或 x B，所以x- (AB), 又X I，所以X G (A B)，即GA C1 B C1 (A B)，反之也有 C1 (A B) C1 A C1 B. 定理2 加法原理：做一件事有 n类办法，第一类办法中有mj种不同的方法，第二类办法 中有m2种不同的方法，第 n类办法中有 mn种不同的方法，那么完成这件事一共有 N =m1 m2亠亠mn种不同的方法。 定理3 乘法原理：做一件事分n个步骤，第一步有m1种不同的方法，第二步有m2种不同 的方法，第n步有mn种不同的方法，那么完成这件事一共有 N =

5、g m mn种不 同的方法。 二、方法与例题 1.利用集合中元素的属性，检验元素是否属于集合。 例 1 设 M =a|a =x2 - y2 ,x, y Z，求证： (1) 2k -r M ,(k Z)； (2) 4k -2 M ,(k Z)； (3 )若p三M , q三M ，贝U pq三M . 证明(1 因为 k,k -r Z，且 2k -1 =k2 _ (k _1)2，所以 2k -1 M . (2) 假设 4k 2 M (k Z),则存在 x, y Z，使 4k _ 2 =x2 _ y2，由于 x - y和 x y 有相同的奇偶性，所以 x2 - y2 = (x - y)(x y)是奇数或

6、4的倍数，不可能等于 4k - 2 , 假设不成立，所以4k _2 - M . (3) 设 p =x2 _y2,q 二 a2 b2,x, y,a,b Z，贝H pq =(x2 _y2)(a2 _b2) 222.22.222 2 2 =aa yb_xbya =(xayb) _(xb_ya) M (因为 xa _ ya ：= Z, xb _ ya ：= Z )。 2利用子集的定义证明集合相等，先证A B，再证BA，贝U A=B 例2设A B是两个集合，又设集合 M满足 A M=B M=A B, A B M=A B，求集合 M (用 代 B 表示)。 【解】先证(A B) M，若x (A B)，因为

7、A M A B，所以x A M,x M , 所以(A B) - M ; 再证 M(A B)，若 x M，则 x ABM = AB.1 )若 x A，则 x AM=A B ； 2)若 x B，则 xBM=AB。所以 M (AB). 综上，M = A B. 3 分类讨论思想的应用。 例 3 A=xx2 _3x+2=0, B=x,x2 _ax+a1 = 0, C=xx2_mx + 2 = 0，若 A B =A,A C =C，求 a,m. 【解】依题设， A =1,2，再由x2ax，a1=0解得x = a-1或x=1 , 因为A B A，所以B A，所以a-A，所以a-仁1或2，所以a=2或3。 因为

8、 A C 二C，所以 CIA，若 Ct，则厶二 m2 -8 ： 0，即一 2.2 ： m ： 2 2 , 若C .,则1 C或2 C，解得m =3. 综上所述，a =2或 a = 3; m=3 或2：2 : m ： 2-2。 4 计数原理的应用。 例 4 集合 A, B, C是 I=1 , 2, 3, 4, 5, 6,乙 8, 9, 0的子集，(1 )若 A B = I，求 有序集合对(A, B)的个数；(2)求I的非空真子集的个数。 【解】(1)集合I可划分为三个不相交的子集；A B, BA, A B,I中的每个元素恰属于其 中一个子集，10个元素共有310种可能，每一种可能确定一个满足条件

9、的集合对，所以集合 对有310个。 (2) I的子集分三类：空集，非空真子集，集合I本身，确定一个子集分十步，第一步，1 或者属于该子集或者不属于，有两种；第二步，2也有两种，第10步，0也有两种，由 乘法原理，子集共有 210 =1024个，非空真子集有1022个。 5.配对方法。 例5给定集合I =1,2,3，n的k个子集：A,A2,，Ak，满足任何两个子集的交集非 空，并且再添加I的任何一个其他子集后将不再具有该性质，求k的值。 【解】将I的子集作如下配对： 每个子集和它的补集为一对，共得2n4对，每一对不能同在 这k个子集中，因此，k乞2n；其次，每一对中必有一个在这k个子集中出现，否

10、则，若 有一对子集未出现，设为 CA与A,并设A /=巧，则A 乂 G A，从而可以在 k个子 集中再添加C1 A，与已知矛盾，所以k_2nJ1。综上，k=2n。 6 竞赛常用方法与例问题。 定理4 容斥原理；用 A表示集合A的元素个数，则 AU B=| A+|B - A1 B, aUbUc| = A + B| +|c a1 B AC. BC| +|a! b1 C , 需要xy此结论可 以推广到n个集合的情况，即a n U A n A -S A A + z a n a n 乓 n 一+(_1严 n a 7 i 4 1 岂 i 4 定义8集合的划分：若 AA/.iAn=|，且aAj = . (

11、i, j 4 ),则3k 12.在m出现的所有 A中，至少有一个A中的数出现3次，不妨设它是 1, 2 , 3 , 乙 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 , 乙 9, 1, 4 , 6 , 13 , 16, 1 ,5 , 6, 8 , 11, 2 ,3 , 4 , 13 , 15, 2 ,3 , 5 , 9 , 11, 2, 3 , 6 , 14 , 16, 2 : ,

12、4 , 5 , 8 , 10, 2 ,4 , 6 , 7 , 11, 2 , 5 , 6 , 12 , 13, 3, 4 , 5 , 12 , 16, 3 : ,4 , 6 , 8 , 9, 3 ,5 , 6 , 7 , 10, 4 , 5 , 6 , 14 , 15。 40个，因此至少是 10个不同的，所以 如下 1 就有集合1 , a1 ,a2,m,a 1总，a4,m,b2,1,a5,a6,m,b3，其中 aA,1 _ i _ 6 , 为满足题意的集合。ai必各不相同，但只能是2,3, 4, 5,6这5个数，这不可能，所以k乞4. 20个A中，B中的数有 20个集合满足要求： 例10集合1

13、 , 2,，3n可以划分成 求满足条件的最小正整数 n. n 【解】 设其中第i个三元集为 , y,Zj, i = 1,2,，n,则1+2+3n4zi , i=1 所以3n(3n = 4、zi。当为偶数时，有83，所以n_8，当为奇数时，有83 1 , 2i # 所以 n 一5,当 n =5 时，集合1 , 11, 4, 2 , 13, 5 , 3 , 15, 6, 9 , 12 , 7 , 10 , 14 , 8满足条件, 三、基础训练题 给定三元集合 若集合A = 所以的最小值为5。 1. 2. 3. 4. 1,x, x2 x，则实数x的取值范围是 xax2 +2x +1 =0,a e R

14、, x乏R中只有一个元素，则 a = 集合B =1,2,3的非空真子集有个。 已知集合M =xx2 3x +2 = 0, N =xax +1 =0,若N匸M，则由满足条件的实 数a组成的集合P=。 5已知A=xxc2, B=xxa，且A9 B，则常数a的取值范围是 。 6若非空集合 S满足S 1,2,3,4,5，且若a S，贝U 6 - a S，那么符合要求的集合S 有个。 7集合X二2 / n Z与丫二4k_1kZ之间的关系是 2 )若aS，贝US。如果S = ._ , 1 -a S中至少含有多少个元素？说明理由。 12.已知 A =( x, y) y =ax, B =( x, y) y =

15、 x + a, C = A B，又 C为单元素集合，求 实数a的取值范围。 四、咼考水平训练题 1 .已知集合 A =x, xy,x + y, B =0, x, y，且 A=B,则 x=, y =o 2. | 二1,234,5,6,7,8,9, A I,B I,A B 二2, (G A) (GB)二1,9, (C1 A)=4,6,8，则 aG(G B) =o 3. 已知集合 A=x10+3x-x2 Z0, B=xm+1 兰x 兰 2m 1，当 aGb=0 时，实 数m的取值范围是 4. 若实数a为常数，且a a = 1 ax2 -x 1 =1,则 a 二 5. ,m21，若 M N =-3，则

16、 集合 M =m , m 1,-3, N =m -3,2m -1 =o 集合A =a a =5x +3, x e N，B =b b=7y+2,yN，则AB中的最小元素 m 6. 是 o 7.集合 A = x - y,x y,xy, B =x2y2, x2 - y2,0,且 A=B,则 x y = x +1 ,1995，集合A满足：A M，且当xA时，A，则A 中元素最多有 个。 7.非空集合 A=x2a+1兰x兰3a5, B=x3兰x兰22，w则使A匸Al B成立的所 有a的集合是。 &已知集合A, B, aC (不必相异)的并集 A B C =1,2，n,则满足条件的有序三 元组(A, B,

17、 C)个数是。 9.已知集合 A =( x, y) ax 十 y = 1, B =( x, y) x + ay = 1, C =( x, y)x2 十 y2 = 1，问： 当a取何值时，(A B) C为恰有2个元素的集合？说明理由，若改为 3个元素集合，结 论如何？ 10求集合B和C,使得B C二1,2，,10，并且C的元素乘积等于 B的元素和。 11. S是Q的子集且满足：若r Q，则rS,-r S, r = 0恰有一个成立，并且若 a S, b S，则ab S,a b S，试确定集合 S。 12. 集合S=1，2，3，4，5，6，7，8，9，0的若干个五元子集满足：S中的任何两个元素 至多

18、出现在两个不同的五元子集中，问：至多有多少个五元子集？ 六、联赛二试水平训练题 1. S1 ,S2,S3是三个非空整数集，已知对于1, 2, 3的任意一个排列i, j,k，如果S， ySj，贝U xyS。求证：S , , E中必有两个相等。 2. 求证：集合1 , 2,，1989可以划分为117个互不相交的子集 A (i =1,2/ ,117), 使得(1)每个A恰有17个元素；(2)每个A中各元素之和相同。 3. 某人写了 n封信，同时写了 n个信封，然后将信任意装入信封，问：每封信都装错的情 况有多少种？ 4. 设a1 ,a2,a20是20个两两不同的整数，且整合a, +a)1 j 20中有201个不 同的元素，求集合a, -a j 1兰i c j兰20中不同元素个数的最小可能值。 5. 设S是由2n个人组成的集合。求证：其中必定有两个人，他们的公共朋友的个数为偶数。 6对于整数n _4,求出最小的整数 f (n)，使得对于