高中數(shù)學(xué)競賽基礎(chǔ)知識(shí)-集合與簡單邏輯

1、學(xué)習(xí)必備歡迎下載高中數(shù)學(xué)競賽基礎(chǔ)知識(shí)第一章集合與簡易邏輯一、基礎(chǔ)知識(shí)定義 1一般地，一組確定的、互異的、無序的對象的全體構(gòu)成集合，簡稱集，用大寫字母來表示；集合中的各個(gè)對象稱為元素，用小寫字母來表示，元素x 在集合A 中，稱x 屬于 A，記為xA ，否則稱x 不屬于A，記作xA 。例如，通常用N， Z， Q， B，Q+分別表示自然數(shù)集、整數(shù)集、有理數(shù)集、實(shí)數(shù)集、正有理數(shù)集，不含任何元素的集合稱為空集，用來表示。集合分有限集和無限集兩種。集合的表示方法有列舉法：將集合中的元素一一列舉出來寫在大括號(hào)內(nèi)并用逗號(hào)隔開表示集合的方法，如1 ， 2，3 ；描述法：將集合中的元素的屬性寫在大括號(hào)內(nèi)表示集合的

2、方法。例如 有理數(shù) ， x x0 分別表示有理數(shù)集和正實(shí)數(shù)集。定義2子集：對于兩個(gè)集合A 與B，如果集合A 中的任何一個(gè)元素都是集合B 中的元素，則A 叫做B 的子集，記為AB ，例如NZ。規(guī)定空集是任何集合的子集，如果A是 B 的子集， B 也是 A 的子集，則稱 A 與 B 相等。如果 A 是 B 的子集，而且 B 中存在元素不屬于 A，則 A 叫 B 的真子集。定義 3交集， AB x xA且 xB.定義 4并集， AB x xA或 xB.定義 5補(bǔ)集，若AI,則C1Ax xI, 且xA 稱為 A在I中的補(bǔ)集。定義 6差集， AB x xA,且 xB 。定義 7集合 x axb, xR,

3、 ab記作開區(qū)間 (a,b) ，集合 x axb, xR, ab 記作閉區(qū)間 a,b ，R 記作 (,).定理1集合的性質(zhì)：對任意集合A， B，C，有：（ 1）A(BC)( AB)(AC );（2）A(BC )( AB)(AC )；（3） C1 AC1 BC1 (AB); （4） C1 AC1 BC1 (AB).【證明】這里僅證（1）、（3），其余由讀者自己完成。1x A ( B C )，則 xA ，且 xB 或 xC ，所以x ( A B)或（ ）若學(xué)習(xí)必備歡迎下載x (AC ) ，即 x ( A B)( AC ) ；反之， x ( A B)( A C ) ，則 x ( AB)或 x ( A

4、C ) ，即 xA 且 xB 或 x C ，即 xA 且 x (BC ) ，即 x A (B C ).（ 3）若 x C1 AC1 B ，則 xC1 A 或 xC1 B ，所以 xA 或 xB ，所以x (AB) ，又 xI ，所以 xC1(A B)，即 C1A C1BC1 (AB) ，反之也有C1(A B) C1A C1B.定理2加法原理：做一件事有n類辦法，第一類辦法中有 m1種不同的方法，第二類辦法中有 m2種不同的方法， ，第 n 類辦法中有 mn 種不同的方法，那么完成這件事一共有 N m1m2mn 種不同的方法。定理3乘法原理： 做一件事分 n 個(gè)步驟， 第一步有 m1 種不同的方

5、法， 第二步有 m2 種不同的方法， ，第 n步有 mn 種不同的方法， 那么完成這件事一共有Nm1 m2mn種不同的方法。二、方法與例題1利用集合中元素的屬性，檢驗(yàn)元素是否屬于集合。例 1設(shè) M a a x 2y 2 , x, y Z ，求證：（ 1） 2k 1 M , (kZ ) ；（ 2） 4k 2 M ,(kZ) ；（ 3）若 p M , qM ，則 pq M .證明（ ）因?yàn)?k, k1Z ，且2k1 k2(k 1)2 ，所以2k1 M .1（ 2）假設(shè) 4k2M(kZ ) ，則存在 x, yZ ，使 4k2x 2y 2 ，由于 xy 和xy有相同的奇偶性，所以x 2y2( xy)(

6、 xy) 是奇數(shù)或 4 的倍數(shù)，不可能等于4k2 ，假設(shè)不成立，所以4k2M .（ 3）設(shè) px2y2 , qa2b 2 , x, y,a,bZ ，則 pq( x2y2 )( a2 b2 )a 2 a2y2 b2x2 b2y 2 a2( xayb) 2(xb ya) 2M學(xué)習(xí)必備歡迎下載（因?yàn)?xayaZ , xbyaZ ）。2利用子集的定義證明集合相等，先證AB ，再證 BA，則 A=B。例 2設(shè) A，B 是兩個(gè)集合，又設(shè)集合M 滿足AMBMAB,ABMAB，求集合 M（用 A，B表示）?！窘狻肯茸C ( AB)M ，若 x( AB) ，因?yàn)?AMAB ，所以xAM , xM ，所以 ( AB

7、)M ；再證 M( AB) ，若 xM ，則 xABMAB.1）若 xA ，則xAMAB ；2）若 xB ，則 xBMAB 。所以 M( AB).綜上，MAB.3分類討論思想的應(yīng)用。例 3A x x23x20, B x x2axa10, C x x 2mx 20 ，若 A BA, ACC ，求a, m.【解】依題設(shè)，A 1,2，再由 x2axa10 解得 xa1或 x1，因?yàn)锳BA，所以BA，所以a1 A ，所以 a11 或22或3。，所以 a因?yàn)?ACC，所以CA，若 C，則m 28 0，即2 2 m2 2 ，若 C，則 1C 或 2C ，解得 m 3.綜上所述， a2或 a3 ； m 3

8、或2 2m2 2 。4計(jì)數(shù)原理的應(yīng)用。例 4集合 A，B，C 是 I=1 ，2，3，4，5，6，7，8，9，0 的子集，（1）若 ABI ，求有序集合對（ A，B）的個(gè)數(shù)；（ 2）求 I 的非空真子集的個(gè)數(shù)?！窘狻浚?1）集合 I 可劃分為三個(gè)不相交的子集；AB，BA，AB, I 中的每個(gè)元素恰屬于其中一個(gè)子集， 10 個(gè)元素共有 310 種可能，每一種可能確定一個(gè)滿足條件的集合對，所以集合對有 310 個(gè)。（ 2）I 的子集分三類： 空集，非空真子集， 集合 I 本身，確定一個(gè)子集分十步，第一步，1 或者屬于該子集或者不屬于，有兩種；第二步，2 也有兩種， ，第 10 步， 0 也有兩種，學(xué)

9、習(xí)必備歡迎下載由乘法原理，子集共有2101024 個(gè)，非空真子集有1022 個(gè)。5配對方法。例5給定集合 I1,2,3, n 的 k 個(gè)子集： A1 , A2, , Ak ，滿足任何兩個(gè)子集的交集非空，并且再添加I 的任何一個(gè)其他子集后將不再具有該性質(zhì)，求k 的值。【解】將 I 的子集作如下配對：每個(gè)子集和它的補(bǔ)集為一對，共得2n 1 對，每一對不能同在這 k 個(gè)子集中， 因此， k2n1 ；其次，每一對中必有一個(gè)在這k 個(gè)子集中出現(xiàn)， 否則，若有一對子集未出現(xiàn)，設(shè)為C1與A，并設(shè)AA1，則A1C1A，從而可以在 k 個(gè)A子集中再添加 C1A ，與已知矛盾，所以 k2n 1。綜上， k2n1。

10、6競賽常用方法與例問題。定理 4容斥原理；用A 表示集合 A 的元素個(gè)數(shù)，則ABAB AB ,A BCA BCA BAC BCAB需要xy 此結(jié)論C ，可以推廣到 n 個(gè)集合的情況，即nnnAiAiAiA jAiA j Ak( 1) n 1Ai .i 1i 1i j1 i j k ni 1定義 8集合的劃分： 若 A1A2AnI ，且 Ai Aj(1 i, jn, i j ) ，則這些子集的全集叫I 的一個(gè) n -劃分。定理 5最小數(shù)原理：自然數(shù)集的任何非空子集必有最小數(shù)。定理 6抽屜原理：將mn1個(gè)元素放入n(n1) 個(gè)抽屜，必有一個(gè)抽屜放有不少于m 1個(gè)元素，也必有一個(gè)抽屜放有不多于 m

11、個(gè)元素； 將無窮多個(gè)元素放入 n 個(gè)抽屜必有一個(gè)抽屜放有無窮多個(gè)元素。例 6 求 1， 2，3， ， 100 中不能被 2， 3， 5 整除的數(shù)的個(gè)數(shù)。【解】記 I 1,2,3,100, A x 1 x 100,且 x能被 2整除（記為 2 x） ，B x1 x100,3 x, C x 1 x100,5 x ，由容斥原理，100100ABCABCABBCCAABC32學(xué)習(xí)必備歡迎下載100100100100100，所以不能被2， 3，5 整除的數(shù)有5610157430IA例7BCS 是集合26 個(gè)。1 ， 2， ， 2004 的子集，S 中的任意兩個(gè)數(shù)的差不等于4 或7，問S中最多含有多少個(gè)元

12、素？【解】將任意連續(xù)的11 個(gè)整數(shù)排成一圈如右圖所示。由題目條件可知每相鄰兩個(gè)數(shù)至多有一個(gè)屬于S，將這 11 個(gè)數(shù)按連續(xù)兩個(gè)為一組，分成6 組，其中一組只有一個(gè)數(shù)，若含有這 11 個(gè)數(shù)中至少6 個(gè)，則必有兩個(gè)數(shù)在同一組，與已知矛盾，所以S 至多含有其中S5個(gè)數(shù)。又因?yàn)?004=182×11+2，所以S 一共至多含有182×5+2=912個(gè)元素，另一方面，當(dāng)S r r11kt, t1,2,4,7,10, r2004, kN 時(shí)，恰有 S912 ，且 S 滿足題目條件，所以最少含有912 個(gè)元素。例 8求所有自然數(shù) n(n2) ，使得存在實(shí)數(shù)a1 , a2 , an 滿足： a

13、ia j 1 ijn1,2, n( n1).2【解】 當(dāng) n2 時(shí)， a10, a21；當(dāng) n3時(shí)， a10, a21, a3 3 ；當(dāng) n4時(shí)，a10, a22, a35, a41。下證當(dāng) n 5 時(shí)，不存在 a1 , a2 ,an 滿足條件。令 0 a1a2an ，則 ann( n 1) .2所以必存在某兩個(gè)下標(biāo)ij ，使得 aia jan 1，所以 an1an1a1an1 或an1ana2 ，即 a21，所以 ann(n1) , an 1an 1或 ann(n1) ， a21。n(n1) , an 1 an22（）若 an1，考慮 an 2 ，有 an2an 2 或2an2ana2 ，即

14、 a22，設(shè) an 2an2 ，則 an 1 an2anan1 ，導(dǎo)致矛盾，故只有 a22.考慮 an3，有 an 3an 2 或 an 3an a3 ，即 a33 ，設(shè) an3 an 2 ，則an 1 an 22a2a0 ，推出矛盾， 設(shè) a33 ，則 an an 11 a3a2 ，又推出矛盾，所以 an 2a2 ,n4故當(dāng) n5時(shí)，不存在滿足條件的實(shí)數(shù)。學(xué)習(xí)必備歡迎下載（）若 ann(n1) , a2 1，考慮 an2 ，有 an2an1 或 an 2an a3，2即 a32 ，這時(shí) a3a2a2a1，推出矛盾，故 an 1an2 。考慮 an3 ，有an3an 2 或 an3ana3 ，

15、即 a3=3，于是 a3a2anan 1 ，矛盾。因此an2an 3 ，所以 an 1an21a2a1，這又矛盾，所以只有 an 2a2 ，所以 n4 。故當(dāng) n5 時(shí)，不存在滿足條件的實(shí)數(shù)。例 9 設(shè) A=1 ， 2， 3， 4， 5，6 ， B=7 ， 8， 9， ， n ，在 A 中取三個(gè)數(shù)， B 中取兩個(gè)數(shù)組成五個(gè)元素的集合Ai，i1,2,20, AiA j2,1 ij20.求 n 的最小值。【解】 nmin16.設(shè) B 中每個(gè)數(shù)在所有Ai 中最多重復(fù)出現(xiàn)k 次，則必有 k4 。若不然，數(shù)m 出現(xiàn) k 次（ k4 ），則 3k12. 在 m 出現(xiàn)的所有 Ai 中，至少有一個(gè) A 中的數(shù)

16、出現(xiàn)3 次，不妨設(shè)它是1，就有集合 1 ， a1 , a2 , m,b1 1, a3 ,a4 ,m,b2 , 1,a5 , a6 , m, b3 ，其中 aiA,1 i6 ，為滿足題意的集合。ai必各不相同， 但只能是，這5個(gè)數(shù)，這不可能，所以 k4.2345620 個(gè) Ai 中， B 中的數(shù)有 40 個(gè)，因此至少是 10 個(gè)不同的，所以n16 。當(dāng) n 16時(shí)，如下 20 個(gè)集合滿足要求：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 。例