高中数学竞赛标准讲义第一章集合与简易逻辑

第一章 集合与简易逻辑

一、基础知识
定义1 一般地，一组 确定的、互异的、无序的对象的全体构成集合，简称集，用大写字母来
表示；集合中的各个对象称为元素 ，用小写字母来表示，元素
x
在集合
A
中，称
x
属于
A
，记
+
为
x?A
，否则称
x
不属于
A
，记作
x?A
。例如，通常用
N
，
Z
，
Q
，
B
，
Q
分别表示自然数集、
整数集、有理数集、实数集、 正有理数集，不含任何元素的集合称为空集，用
?
来表示。集
合分有限集和无限集两种 。
集合的表示方法有列举法：将集合中的元素一一列举出来写在大括号内并用逗号隔开表示集
合的方法，如{1，2，3}；描述法：将集合中的元素的属性写在大括号内表示集合的方法。例
如{有 理数}，
{xx?0}
分别表示有理数集和正实数集。
定义2 子集：对于两个集 合
A
与
B
，如果集合
A
中的任何一个元素都是集合
B
中的元素，则
A
叫做
B
的子集，记为
A?B
，例 如
N?Z
。规定空集是任何集合的子集，如果
A
是
B
的子< br>集，
B
也是
A
的子集，则称
A
与
B
相等。如果
A
是
B
的子集，而且
B
中存在元素不属于
A
，则
A
叫
B
的真子集。
定义3 交集，
A?B?{xx?A且x?B}.

定义4 并集，
A?B?{xx?A或x?B}.

定义5 补集，若
A?I,则C
1
A?{xx?I,且x?A}
称为
A
在
I
中的补 集。
定义6 差集，
AB?{xx?A,且x?B}
。
定义7 集合
{xa?x?b,x?R,a?b}
记作开区间
(a,b)
，集合 {xa?x?b,x?R,a?b}
记作闭区间
[a,b]
，R记作
(? ?,??).

定理1 集合的性质：对任意集合
A
，
B
，
C
，有：
（1）
A?(B?C)?(A?B)?(A?C);
（2）
A?(B?C)?(A?B)?(A?C)
；
（3）
C
1< br>A?C
1
B?C
1
(A?B);
（4）
C
1
A?C
1
B?C
1
(A?B).

【证明】这里仅证（1）、（3），其余由读者自己完成。
（1）若
x?A?(B? C)
，则
x?A
，且
x?B
或
x?C
，所以
x?(A?B)
或
x?(A?C)
，
即
x?(A?B)?(A?C )
；反之，
x?(A?B)?(A?C)
，则
x?(A?B)
或x?(A?C)
，
即
x?A
且
x?B
或
x?C
，即
x?A
且
x?(B?C)
，即
x?A?(B?C).< br>
（3）若
x?C
1
A?C
1
B
，则
x?C
1
A
或
x?C
1
B
，所以
x?A
或
x?B
，所以
x?(A?B)
，
又
x?I
，所以
x?C
1
(A?B)
，即
C
1
A?C1
B?C
1
(A?B)
，反之也有
C
1
(A? B)?C
1
A?C
1
B.

定理2 加法原理：做一件事 有
n
类办法，第一类办法中有
m
1
种不同的方法，第二类办法中有
m
2
种不同的方法，…，第
n
类办法中有
m
n
种不同的方法，那么完成这件事一共有
N?m
1
?m
2
? ??m
n
种不同的方法。
定理3 乘法原理：做一件事分
n
个步 骤，第一步有
m
1
种不同的方法，第二步有
m
2
种不同的< br>方法，…，第
n
步有
m
n
种不同的方法，那么完成这件事一共 有
N?m
1
?m
2
???m
n
种不同的
方 法。
二、方法与例题
1．利用集合中元素的属性，检验元素是否属于集合。
例1 设
M?{aa?x?y,x,y?Z}
，求证：
（1）
2k?1?M,(k?Z)
；
22

（2）
4k?2?M,(k?Z)
；
（3）若
p?M,q?M
，则
pq?M.

[证明]（1） 因为
k,k?1?Z
，且
2k?1?k?(k?1)
，所以
2k?1 ?M.

（2）假设
4k?2?M(k?Z)
，则存在
x,y?Z< br>，使
4k?2?x?y
，由于
x?y
和
x?y
有相同的奇偶性，所以
x?y?(x?y)(x?y)
是奇数或4的倍数，不可能等于
4k?2
，假设
不成立，所以
4k?2?M.

（3）设
p?x?y,q?a?b,x,y,a,b?Z
，则
pq?(x?y)(a?b)
< br>22222222
22
22
22
?a
2
a
2
?y
2
b
2
?x
2
b
2
?y2
a
2
?(xa?yb)
2
?(xb?ya)
2
?M

（因为
xa?ya?Z,xb?ya?Z
）。
2．利用子 集的定义证明集合相等，先证
A?B
，再证
B?A
，则
A
=
B
。
例2 设
A
，
B
是两个集合，又设集合M满足
。
A?M?B? M?A?B,A?B?M?A?B
，求集合M（用
A
，
B
表示）【解】先证
(A?B)?M
，若
x?(A?B)
，因为
A?M? A?B
，所以
x?A?M,x?M
，
所以
(A?B)?M
；

再证
M?(A?B)
，若
x?M
，则
x?A? B?M?A?B.
1）若
x?A
，则
x?A?M?A?B
；2）若< br>x?B
，则
x?B?M?A?B
。所以
M?(A?B).

综上，
M?A?B.

3．分类讨论思想的应用。
例3
A?{xx
2
?3x?2?0},B?{xx
2
?ax?a?1?0},C ?{xx
2
?mx?2?0}
，若
A?B?A,A?C?C
，求a,m.

【解】依题设，
A?{1,2}
，再由
x?ax?a ?1?0
解得
x?a?1
或
x?1
，
因为
A?B ?A
，所以
B?A
，所以
a?1?A
，所以
a?1?1或2，所以
a?2
或3。
2
因为
A?C?C
，所以< br>C?A
，若
C??
，则
??m?8?0
，即
?22? m?22
，若
C??
，则
1?C
或
2?C
，解得< br>m?3.

2
综上所述，
a?2
或
a?3
；
m?3
或
?22?m?22
。
4．计数原理的应用。
例4 集合
A
，
B
，
C
是
I
= {1，2，3，4，5，6，7，8，9，0}的子集，（1）若
A?B?I
，求有
序 集合对（
A
，
B
）的个数；（2）求
I
的非空真子集的个数 。
【解】（1）集合
I
可划分为三个不相交的子集；
A

B
，
B

A
，
A?B,I
中的每个元素恰属于其
10
中一个子集，10个元素共有3种可能，每一种可能确定一个满足条件的集合对，所以集合对10
有3个。
（2）
I
的子集分三类：空集，非空真子集，集合
I
本身，确定一个子集分十步，第一步，1
或者属于该子集或者不属于，有两种；第二步，2 也有两种，…，第10步，0也有两种，由
乘法原理，子集共有
2
5．配对方法。
10
?1024
个，非空真子集有1022个。
例5 给定集合
I ?{1,2,3,?,n}
的
k
个子集：
A
1
,A
2
,?,A
k
，满足任何两个子集的交集非空，
并且再添加
I
的任何一个其他子集后将不再具有该性质，求
k
的值。
【解】将
I
的子集作如下配对：每个子集和它的补集为一对，共得
2
这
k
个子集中，因 此，
k?2
n?1
n?1
对，每一对不能同在
；其次，每一对中必有 一个在这
k
个子集中出现，否则，若有
n?1
一对子集未出现，设为
C
1
A
与
A
，并设
A?A
1
??
，则
A
1
?C
1
A
，从而可以在
k
个子集 中
再添加
C
1
A
，与已知矛盾，所以
k?2
6．竞 赛常用方法与例问题。
。综上，
k?2
n?1
。
定理4 容斥 原理；用
A
表示集合
A
的元素个数，则
A?B?A?B?A?B,< br>

A?B?C?A?B?C?A?B?A?C?B?C?A?B?C
，< br>需要xy
此结论可以
推广到
n
个集合的情况，即
?

?
A
i?1
n
i
?
?
A
i
?
?
A
i
?A
j
?
i?1i?j
n1?i?j?k?n
?
A
i
?A
j
?A
k???(?1)
n?1
?
n
A
i
.

i?1
定义8 集合的划分：若
A
1
?A
2
?? ?A
n
?I
，且
A
i
?A
j
??(1?i ,j?n,i?j)
，则这
些子集的全集叫
I
的一个
n
-划 分。
定理5 最小数原理：自然数集的任何非空子集必有最小数。
定理6 抽屉原理： 将
mn?1
个元素放入
n(n?1)
个抽屉，必有一个抽屉放有不少于
m?1
个
元素，也必有一个抽屉放有不多于
m
个元素；将无穷多个元素放入
n
个抽屉必有一个抽屉放
有无穷多个元素。
例6 求1，2，3，…，100中不能被2，3，5整除的数的个数。
【解】 记
I?{1,2, 3,?,100},A?{x1?x?100,且x能被2整除（记为2x）}
，
B?{x1? x?100,3x},C?{x1?x?100,5x}
，由容斥原理，
?
100??
100
?
A?B?C?A?B?C?A?B?B?C?C?A?A?B?C?
?
?
?
?
??
23
????
?
1 00
??
100
??
100
??
100
??
100
?
?
?
?
?
?
?
?
?< br>?74
，所以不能被2，3，5整除的数有
??????
56101530??????????
I?A?B?C?26
个。
例7 S是集合{1，2， …，2004}的子集，S中的任意两个数的差不等于4或7，问S中最多
含有多少个元素？
【解】将任意连续的11个整数排成一圈如右图所示。由题目条件可知每相邻两个数至多有一
个属于S， 将这11个数按连续两个为一组，分成6组，其中一组只有一个数，若S含有这11
个数中至少6个，则 必有两个数在同一组，与已知矛盾，所以S至多含有其中5个数。又因
为2004=182×11+2， 所以S一共至多含有182×5+2=912个元素，另一方面，当
S?{rr?11k?t,t?1, 2,4,7,10,r?2004,k?N}
时，恰有
S?912
，且S满足题目条件 ，
所以最少含有912个元素。
例8 求所有自然数
n(n?2)
，使得存 在实数
a
1
,a
2
,?,a
n
满足：
n(n?1)
}.

2
【解】 当
n?2
时，< br>a
1
?0,a
2
?1
；当
n?3
时，
a
1
?0,a
2
?1,a
3
?3
；当
n ?4
时，
{a
i
?a
j
}1?i?j?n}?{1,2, ?,
a
1
?0,a
2
?2,a
3
?5,a
4
?1
。下证当
n?5
时，不存在
a
1
,a
2
,?,a
n
满足条件。
n(n?1)
.

2
所以必存在某两个下标
i?j
，使得
a
i
?a
j< br>?a
n
?1
，所以
a
n
?1?a
n?1?a
1
?a
n?1
或
令
0?a
1
?a
2
???a
n
，则
a
n
?
a
n< br>?1?a
n
?a
2
，即
a
2
?1
， 所以
a
n
?
（ⅰ）若
a
n
?
n(n?1) n(n?1)
,a
n?1
?a
n
?1
或
a
n
?
，
a
2
?1
。
22
n(n?1)< br>,a
n?1
?a
n
?1
，考虑
a
n
?2
，有
a
n
?2?a
n?2
或
a
n?2?a
n
?a
2
，
2
即
a
2
?2
，设
a
n?2
?a
n
?2
，则
a< br>n?1
?a
n?2
?a
n
?a
n?1
，导致 矛盾，故只有
a
2
?2.

考虑
a
n
?3
，有
a
n
?3?a
n?2
或
a
n
?3?a
n
?a
3
，即
a
3
?3
，设a
n
?3?a
n?2
，则

a
n?1?a
n?2
?2?a
2
?a
0
，推出矛盾，设
a
3
?3
，则
a
n
?a
n?1
?1?a< br>3
?a
2
，又推出矛盾，
所以
a
n?2
? a
2
,n?4
故当
n?5
时，不存在满足条件的实数。
n (n?1)
考虑
a
n
?2
，有
a
n
?2? a
n?1
或
a
n
?2?a
n
?a
3
，即
a
3
?2
，
,a
2
?1
，
2
这时
a
3
?a
2
?a
2
?a
1
，推出矛盾，故
a
n?1
?a
n
?2
。考虑
a
n
?3
，有
a
n
?3?a
n?2
或< br>（ⅱ）若
a
n
?
a
n
?3?a
n
?
a
3
，即
a
3
=3，于是
a
3
? a
2
?a
n
?a
n?1
，矛盾。因此
a
n ?2
?a
n
?3
，所以
a
n?1
?a
n? 2
?1?a
2
?a
1
，这又矛盾，所以只有
a
n? 2
?a
2
，所以
n?4
。故当
n?5
时，不
存在满足条件的实数。
例9 设
A
={1，2，3，4，5，6}，
B
={7，8，9，……，
n
}，在
A
中取三个数，
B
中取两个数组
成五个元素的集合
A
i
，
i?1,2,?,20,A
i
?A
j
?2,1?i?j?20.
求
n
的最小值 。
【解】
n
min
?16.

设
B
中 每个数在所有
A
i
中最多重复出现
k
次，则必有
k?4。若不然，数
m
出现
k
次（
k?4
），
则3k?12.
在
m
出现的所有
A
i
中，至少有一个A
中的数出现3次，不妨设它是1，就有集合
{1，
a
1
,a< br>2
,m,b
1
}
{1,a
3
,a
4
,m,b
2
},{1,a
5
,a
6
,m,b
3}
，其中
a
i
?A,1?i?6
，为满足题意的
集合。
a
i
必各不相同，但只能是2，3，4，5，6这5个数，这不可能，所以
k ?4.

20个
A
i
中，
B
中的数有40个，因此 至少是10个不同的，所以
n?16
。当
n?16
时，如下
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}， {2，3，4，13，15}， {2，3，5，9，11}，
{2，3，6，14，16}， {2，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}。
例10 集合{1，2，…，3
n
}可以划分成
n
个互不相交的三元 集合
{x,y,z}
，其中
x?y?3z
，
求满足条件的最小正整数
n.

【解】 设其中第
i
个三元集为
{x
i,y,z
i
},i?1,2,?,n,
则1+2+…+
3n?
?
4z
i?1
n
i
,

n
3n(3n?1)
?4
?
z
i
。当
n
为偶数时，有
83n< br>，所以
n?8
，当
n
为奇数时，有
83n?1
，所以
2
i?1
所以
n?5
，当
n?5
时，集合{1，1 1，4}，{2，13，5}，{3，15，6}，{9，12，7}，{10，14，
8}满足条件， 所以
n
的最小值为5。
三、基础训练题
1．给定三元集合
{1, x,x?x}
，则实数
x
的取值范围是___________。
2．若集 合
A?{xax
2
?2x?1?0,a?R,x?R}
中只有一个元素，则< br>a
=___________。
3．集合
B?{1,2,3}
的非空真子集有___________个。
2
4．已知集合
M?{xx?3x?2?0},N?{xax?1?0}
，若
N?M
，则由满足条件的实数
2
a
组成的集合
P
=____ _______。
5．已知
A?{xx?2},B?{xx?a}
，且
A? B
，则常数
a
的取值范围是___________。
6．若非空集合S满 足
S?{1,2,3,4,5}
，且若
a?S
，则
6?a?S
，那么符合要求的集合S有
___________个。
7．集合
X?{2n?1 n?Z}与Y?{4k?1k?Z}
之间的关系是___________。
8．若集合A?{x,xy,xy?1}
，其中
x?Z
，
y?Z
且
y?0
，若
0?A
，则
A
中元素之和是

__ _________。
9．集合
P?{xx
2
?x?6?0},M?{xm x?1?0}
，且
M?P
，则满足条件的
m
值构成的
集合为 ___________。
10．集合
A?{xy?2x?1,x?R
?
} ,B?{yy??x
2
?9,x?R}
，则
A?B?
___________。
11．已知S是由实数构成的集合，且满足1）
1?S;2
）若
a?S
，则
S中至少含有多少个元素？说明理由。
12．已知
A?{(x,y)y?ax},B?{(x,y)y?x?a},C?A?B
，又
C
为单元素集合，求实
数
a
的取值范围。
四、高考水平训练题
1．已知集合
A?{x,xy,x?y},B?{0,x,y}
，且
A
=
B
，则
x?
___________，< br>y?
___________。

2．
I?{1,2,3,4,5, 6,7,8,9},A?I,B?I,A?B?{2},(C
1
A)?(C
1
B)?{1,9},

1
?S
。如果
S??
，
1? a
(C
1
A)?B?{4,6,8}
，则
A?(C
1
B)?
___________。
3．已知集合
A?{x10?3x?x
2
?0},B?{xm?1?x?2m?1}
，当
A?B??
时，实数
m
的取值范围是___________。
??
1
??
a
a?A?x?1
4．若实数为常数，且
??
,则a?
__________ _。
2
?
?
ax?x?1
?
?
22
5． 集合
M?{m,m?1,?3},N?{m?3,2m?1,m?1}
，若
M?N?{ ?3}
，则
m?
___________。
6．集合
A?{aa? 5x?3,x?N
?
},B?{bb?7y?2,y?N
?
}
，则< br>A?B
中的最小元素是
___________。
7．集合
A?{x ?y,x?y,xy},B?{x?y,x?y,0}
，且
A
=
B
， 则
x?y?
___________。
8．已知集合
A?{x
___________。
9．设集合
问：
A?{(x,y)y
2
?x?1?0},B?{(x,y)4x
2
? 2x?2y?5?0},
C?{(x,y)y?kx?b}
，
是否存在
k,b ?N
，使得
(A?B)?C??
，并证明你的结论。
10．集合
A
和
B
各含有12个元素，
A?B
含有4个元素，试求同时满足下列条 件的集合
C
的
个数：1）
C?A?B
且
C
中含有3 个元素；2）
C?A??
。
11．判断以下命题是否正确：设
A
，
B
是平面上两个点集，
C
r
?{(x,y)x?y?r}
， 若对
任何
r?0
，都有
C
r
?A?C
r
? B
，则必有
A?B
，证明你的结论。
五、联赛一试水平训练题
2 22
2222
x?1
?0},B?{xpx?4?0}
，且
B?A< br>，则
p
的取值范围是
2?x
m
2
x?1
,x ?2},B??,且B?A
，则实数
m
的取值范1．已知集合
A?{xx?0 },B?{zz?
mx?1
围是___________。
2．集合
A?{ 1,2,3,?,2n,2n?1}
的子集
B
满足：对任意的
x,y?B,x ?y?B
，则集合
B
中
元素个数的最大值是___________。 3．已知集合
P?{a,aq,aq},Q?{a,a?d,a?2d}
，其中
a ?0
，且
a?R
，若
P
=
Q
，则实
2

数
q?
___________。
4．已知集合
A?{ (x,y)x?y?a,a?0},B?{(x,y)xy?1?x?y}
，若
A?B
是平面
上正八边形的顶点所构成的集合，则
a?
___________。
5．集合
M?{uu?12m?8n?4l,m,l,n?Z}
，集合
N?{uu?2 0p?16q?12r,p,q,r?Z}
，则集合M与
N
的关系是________ ___。
6．设集合
M?{1,2,3,?,1995}
，集合
A
满足：
A?M
，且当
x?A
时，
15x?A
，则
A
中
元素最多有___________个。
7．非空集合
A?{x2a?1 ?x?3a?5},B?{x3?x?22}
，≤则使
A?A?B
成立的所有
a
的集合是___________。
8．已知集合
A
，
B
，
aC
（不必相异）的并集
A?B?C?{1,2,?,n}
,

则满足条件的有序三元
组（
A
，
B
，
C
） 个数是___________。
9．已知集合
A?{(x,y)ax?y?1},B?{( x,y)x?ay?1},C?{(x,y)x
2
?y
2
?1}
，问 ：
当
a
取何值时，
(A?B)?C
为恰有2个元素的集合？说明理由 ，若改为3个元素集合，结论
如何？
10．求集合
B
和
C
，使得
B?C?{1,2,?,10}
，并且
C
的元素乘积等于
B< br>的元素和。
11．S是
Q
的子集且满足：若
r?Q
，则r?S,?r?S,r?0
恰有一个成立，并且若
a?S,b?S
，
则< br>ab?S,a?b?S
，试确定集合S。
12．集合S={1，2，3，4，5，6， 7，8，9，0}的若干个五元子集满足：S中的任何两个元素
至多出现在两个不同的五元子集中，问： 至多有多少个五元子集？
六、联赛二试水平训练题
1．
S
1
,S
2
,S
3
是三个非空整数集，已知对于1，2，3的任意一个排列
i ,j,k
，如果
x?S
i
，
y?S
j
，则
x?y?S
i
。求证：
S
1
,S
2
,S
3
中必有两个相等。
2．求证：集合{1，2，…，1989}可以划分为117个互不相交的 子集
A
i
(i?1,2,?,117)
，使
得（1）每个
A
i
恰有17个元素；（2）每个
A
i
中各元素之和相同。
3．某人写了
n
封信，同时写了
n
个信封，然后将信任意装入信封，问：每封 信都装错的情况
有多少种？
4．设
a
1
,a
2
, ?,a
20
是20个两两不同的整数，且整合
{a
i
?a
j
1?i?j?20}
中有201个不
同的元素，求集合
{a
i
?a
j
1?i?j?20}
中不同元素个数的最小可能值。
5．设S是由
2n
个人组成的集合。求证：其中必定有两个人，他们的公共朋友的个数为偶数。
6 ．对于整数
n?4
，求出最小的整数
f(n)
，使得对于任何正整数
m
，集合
{m,m?1,?,m?n?1}
的任一个
f(n)
元子集 中，均有至少3个两两互质的元素。
7．设集合S={1，2，…，50}，求最小自然数
k
，使S的任意一个
s
元子集中都存在两个不同
的数
a
和b
，满足
(a?b)ab
。
8．集合
X?{1,2,?,6k },k?N
?
，试作出
X
的三元子集族&，满足：
（1）
X
的任意一个二元子集至少被族&中的一个三元子集包含；
（2）
&?6k(&表示&的元素个数
）
。
2
2
，
?
，m
}
，求最小的正整数
m
，使得对
A
的任意一个14-分划9．设集合
A?{1
，
A
1
,A
2
,?,A
14
，一定存在某个集合
A
i
(1?i?14)< br>，在
A
i
中有两个元素
a
和
b
满足
4
b?a?b
。
3