1－1整數-南一書局.doc

第二章　排列組合 2－1集合元素的計數 集合的基本概念 　設A＝{－3 ,－2 ,－1 , 0 , 1 , 2 , 3 }，試用描述法表示集合A。 　解：設A＝{ x | x(Z，－3　(　x　(　3 } 　已知非空子集S　(　N，並且滿足如果x(S，那麼（8－x）(S”。(1)　寫出只含一個元素的所有集合S。(2)　寫出只含二個元素的所有集合S。(3)　滿足題設條件的集合S，共有幾個？ 　解：(1)　S只含一個元素，則x＝8－x，所以x＝4，故S＝{ 4 }。(2)　S只含二個元素，則x8－x，且x＋（8－x）＝8。　　故S＝{ 1 , 7 }，{ 2 , 6 }，{ 3 , 5 }。(3)　滿足題設條件的集合有　　A　只含一個元素者：S＝{ 4 }。　　B　只含二個元素者：S＝{ 1 , 7 }，{ 2 , 6 }，{ 3 , 5 }。　　C　只含三個元素者：S＝{ 1 , 4 , 7 }，{ 2 , 4 , 6 }，{ 3 , 4 , 5 }。　　D　只含四個元素者：S＝{ 1 , 2 , 6 , 7 }，{ 1 , 3 , 5 , 7 }，{ 2 , 3 , 5 , 6 }。　　E　只含五個元素者：　　　　S＝{ 1 , 2 , 4 , 6 , 7 }，{ 1 , 3 , 4 , 5 , 7 }，{ 2 , 3 , 4 , 5 , 6 }。　　F　只含六個元素者：S＝{ 1 , 2 , 3 , 5 , 6 , 7 }。　　G　只含七個元素者：S＝{ 1 , 2 , 3 , 4 , 5 , 6 , 7 }。　　總計S有1＋3＋3＋3＋3＋1＋1＝15（個）。 　集合M具有下列性質：如果x(M，那麼(　M。今已知5(　M，求M至少有多少元素？ 　解：5(　M　　(　M　　(　M?　(　M　　(　M所以M至少有 ,－ ,－ , }這些元素。 【註】若a(　M（a≠－1，0，1），則，－，都屬於M；而當x＝時，則＝a（回到原來元素），故M至少有四個元素。M＝{ a , , － , , … }。 　“良序原則（Well ordering principle）是指：設S是N的非空子集，則S含有最小元素。（即存在a0(　S，使得S中所有元素a　(　a0）現在證明：“數學歸納法良序原則（是等價的）。 證明：(1)　“數學歸納法良序原則　　設S是N的任一個非空子集，但S沒有最小元素。（反證法）　　令M＝{ x | x(N，x小於S中每一個數 }。　　因1是自然數集N的最小數，而S沒有最小數，　　所以1(　S且1(　M。　　假設m(M，現在設法證明它的後繼元素m(＝m＋1(M。　　事實上，如果m＋1(　M，依M的定義知：存在元素a1(　S使a1　(　m＋1。　　又因S中沒有最小元素，故又存在元素a2(　S使a2＜a1　(　m＋1，由此推得a2　(　m，此與m(　M相矛盾。　　所以M滿足：當m(　M時，則m＋1(　M。　　由數學歸納法知：M＝N。但S是非空，所以S中至少有一個數t。　　但t(　N＝M，即t(　S，又t(　M，依M的定義得出t＜t的矛盾結果，　　所以S必有最小元素。(2)　“良序原則數學歸納法　　設M　(　N且滿足　　(i)　1(　M。　　(ii)　若a(　M，則a(＝a＋1(　M。　　欲證：M＝N。　　用反證法，假設MN，令＝{ b | b(　N，b(　M }。　　由於假設MN（M　(　N），所以是N的非空子集。　　依良序原則，　　含最小元素b0，但已知1(　M，所以1(　，即b0＞1。　　b0－1＜b0，所以b0－1(　（b0是M的最小元素），從而得到b0－1(　M。　　再由M所滿足的第(ii)個性質知（b0－1）＋1(　M，即b0(　M。　　這就產生了b0(　，又b0(　M的矛盾，所以M＝N。 　從集合的包含關係判別命題：p　→　q的真偽設N為宇集，p，q，t分別表下列敘述：p：n是12的倍數。　q：n是4的倍數。　t：n是8的倍數。令P，Q，T分別表下列集合：　P＝{ n | n(　N，n適合p }＝{ 12 , 24 , 36 ,, 12k ,… }。　Q＝{ n | n(N，n適合q }＝{ 4 , 8 , 12 ,, 4k ,… }。　T＝{ n | n(N，n適合t }＝{ 8 , 16 , 24 ,…, 8k ,… }。試判別下列命題的真偽：(1)　若p，則q。　　(2)　若p，則t。　　(3)　若t，則q。 　解：(1)　若p，則q：　　若n是12的倍數，則n是4的倍數。　　　　　　　　?　若n(　P，則n(　Q。　　?　P　(　Q。　　由於P　(　Q是，故若p，則q亦真。 (2)　若