離散數學常考題型梳理

離散數學?？碱}型梳理第1章集合及其運算一、題型分析本章主要介紹集合論的基本概念和結論，集合的運算及其性質，以及利用運算性質進行集合表達式的化簡和集合恒等式的證明等內容．經常涉及到的題型有：1-1集合與集合之間的包含、元素與集合之間的屬于關系1-2冪集的計算1-3集合之間的運算1-4利用集合運算性質證明集合恒等式因此，在本章學習過程中希望大家要清楚地知道：1．集合與集合之間存在一種包含關系，當兩個集合A和B存在關系A包含B，用AB表示，或存在關系B被A包含，用BA表示，這時稱B為A的子集．注意空集是任意一個集合的子集，集合A也是自己的子集．當B且BA，也就是說，只有BA或AB成立，則稱B為A的真子集．若B不是A的子集，即BA不成立時，則稱A不包含B，記作BA．然而，元素與集合之間存在一種從屬關系，當是集合中的元素，則稱屬于，記作；若不是集合中的元素，則稱不屬于，記作．因此，這兩種關系一定不要混淆．2．由集合A的所有子集組成的集合，稱為A的冪集，記作P(A)或2A．若集合A是由n個元素所組成的集合，則A的冪集由2n元素組成．當n=3時，A的冪集由23=8個元素組成例如，設集合A={0,1,2}，則A的全部子集由以下子集組成：0元子集（即空集）：；1元子集：{0}，{1}，{2}；2元子集：{0,1}，{0,2}，{1,2}；3元子集（即集合A）：{0,1,2}．因此，計算集合A的冪集時，首先要按照上述方法寫出集合A的全部子集，然后檢驗寫出的子集個數是否等于2n個，其中n是集合A的元素個數．圖1AB3．集合之間的運算有并（）、交（）、差（-）、圖1AB補（~）和對稱差（）等五種運算，在做集合運算的題目時，一定要按照它們的定義進行計算．(1)集合A和B的并集AB圖2或AB圖2特點：由集合A和B的所有元素組成的集合．見圖1(2)集合A和B的交集且AB圖3特點：由集合A和B的公共元素組成的集合．AB圖3(3)集合A與B的差集特點：由屬于A，而不屬于B的所有元素組成的集合．AE~AE~A圖4(4)集合A的補集~A=特點：由屬于全集E但不屬于集合A的元素組成的集合．AB圖5AB圖5補集總相對于一個全集而言，可以看作是全集E與集合A的差集．(5)集合A與B的對稱差AB＝(A－B)(B－A)或AB＝(AB)－(AB)特點：由分別屬于集合A與B的元素但不屬于它們公共元素組成的集合．見圖5(6)把集合A，B合成集合A×B叫做笛卡兒積，規(guī)定A×B＝{<x,y>xA且yB}注意：由于有序對<x,y>中x，y的位置是確定的，因此A×B的記法也是確定的，不能寫成B×A.．笛卡兒積的運算一般不能交換.．雖然，笛卡兒積的內容是第2章2.1.1目的內容，是二元關系的預備知識，但我們認為把它作為集合的一種運算考慮更好些。4．教材1.2.2集合運算的性質給出的交換律、結合律、分配律、冪等律、同一律、零律、補余律、吸收律、摩根律和雙補律等的恒等式是證明其它集合恒等式、化簡集合表達式的主要依據，正確運用這些恒等式是做好集合證明或化簡題的關鍵．因此，大家要通過適當的練習逐步掌握這些集合運算性質二、?？贾R點分析?？贾R點1：集合與集合之間的包含、元素與集合之間的屬于關系（歷年考核次數：4次，本課程共考過6次；重要程度：★★★★）（2008年9月試卷第1題）若集合A＝{a，{a}，{1，2}}，則下列表述正確的是()．A．{a，{a}}AB．{2}AC．{a}AD．A[解題過程]C選項A，錯了．因為{a，{a}}是集合A＝{a，{a}，{1，2}}的子集，集合之間應該用包含關系表示，即{a，{a}}A．選項B，錯了．因為2不是集合A＝{a，{a}，{1，2}}的元素，當然{2}也不是A的子集．正確的表示方法是{2}A．選項C，正確．因為a是集合A＝{a，{a}，{1，2}}的元素，所以取元素a組成一個集合{a}就是A的子集，用包含關系表示是正確的．注意：{a}也是集合A的元素，若屬于關系也是正確的．選項D，錯了．因為空集是任意一個集合的子集，所以也是A的子集，集合之間應該用包含關系表示，即A．易錯點：同學們對集合中有的元素用集合形式表示的情形容易混淆，但這種類型考題中經常出現，大家一定要習慣．本題主要是檢查大家對屬于關系和包含關系是否理解，能否正確運用．提示：首先檢查各選項給出的關系符號和左邊的式子是集合A的元素還是子集，然后判斷選項中使用的關系符號是否正確，確定選項．（2009年7月試卷第1題）若集合A={a，b}，B={a，b，{a，b}}，則（）．A．AB，且ABB．AB，但ABC．AB，但ABD．AB，且AB[解題過程]A選項A，正確．因為集合A={a，b}既是取集合B={a，b，{a，b}}中元素a，b組成的一個集合，是B的一個真子集，用AB表示是正確的；但它也是B的元素，所以用AB表示也是正確的．選項B，錯了．選項中第一個式子AB是正確的，但第二個式子AB是錯的．因為集合A={a，b}是取集合B={a，b，{a，b}}中元素a，b組成的一個集合，是B的一個真子集，應該用AB表示，而不是用AB表示．選項C，錯了．選項中第一個式子AB是正確的，但第二個式子AB是錯的．因為集合A={a，b}是集合B={a，b，{a，b}}中元素，應該用AB表示，而不是用AB表示．選項D，錯了．因為集合A={a，b}是取集合B={a，b，{a，b}}中元素a，b組成的一個集合，是B的一個真子集，應該用AB表示，而不是用AB表示．又因為集合A={a，b}是集合B={a，b，{a，b}}中元素，應該用AB表示，而不是用AB表示．易錯點：同學們對集合中有的元素用集合形式表示的情形容易混淆，但這種情況考題中經常出現，大家一定要習慣．本題主要是檢查大家對屬于關系和真子集的概念是否正確理解．提示：選項中出現“且”、“但”這樣得連接詞時，只有當連接詞兩邊的式子都正確時，選項才是正確的．?？贾R點2：冪集的計算（歷年考核次數：3次，本課程共考過6次；重要程度：★★★）（運用此知識點和相關知識點解答本題，即將知識點講解與題目解答結合起來）（2008年7月試卷第3題）若集合A的元素個數為10，則其冪集的元素個數為（）．A．1024B．10C．100D．1[解題過程]A選項A，正確．由集合A的所有子集組成的集合，稱為A的冪集，記作P(A)或2A若集合A是由n個元素所組成的集合，則A的冪集由2n元素組成．本題集合A有10個元素，因此A的冪集由210=1024個元素組成．選項B，錯了．因為集合A有10個元素，所以A的冪集的元素應該有210=1024個，而不是10個．選項C，錯了．因為集合A有10個元素，所以A的冪集的元素應該有210=1024個，而不是100個．選項D，錯了．因為集合A有10個元素，所以A的冪集的元素應該有210=1024個，而不是1個．易錯點：當n比較大時，有些同學不會計算2的n次冪，即把210計算錯了．注意：若集合A有n個元集，則其冪集P(A)有2n個元素．（2008年7月試卷第6題）設集合A＝{a，b}，那么集合A的冪集是．[解題過程]{，{a}，，{a,b}}按照冪集定義，集合A＝{a，b}的所有子集就是A的冪集．A的全部子集由以下子集組成：0元子集（即空集）：；1元子集：{a}，；2元子集（即集合A）：{a，b}．所以，集合A的冪集是：{，{a}，，{a,b}}易錯點：在寫集合A的所有子集時，容易遺漏空集．注意：因為集合A有2個元集，則其冪集P(A)有22=4個元素．?？贾R點3：集合之間的運算（歷年考核次數：3次，本課程共考過6次；重要程度：★★★）（運用此知識點和相關知識點解答本題，即將知識點講解與題目解答結合起來）（2008年9月試卷第17題）．設A={{1},{2},1,2}，B={1,2,{1,2}}，試計算（1）AB；（2）A∩B；（3）A×B．[解題過程]（1）求集合A與B的差集，就是求屬于A而不屬于B的所有元素組成的集合．即AB={{1},{2},1,2}{1,2,{1,2}}={{1},{2}}（2）求集合A和B的交集A∩B，就是求由集合A和B的公共元素組成的集合．即A∩B={{1},{2},1,2}∩{1,2,{1,2}}={1,2}（3）求集合A與B的笛卡兒積A×B，就是求一個元素是有序對的集合，而這些有序對的第一個元素取自集合A，第二個元素取自集合B．即A×B={{1},{2},1,2}×{1,2,{1,2}}={<{1},1>，<{1},2>，<{1},{1,2}>，<{2},1>，<{2},2>，<{2},{1,2}>，<1,1>，<1,2>，<1,{1,2}>，<2,1>，<2,2>，<2,{1,2}>}易錯點：同學們對集合中有的元素用集合形式表示的情形容易混淆，既不把{1},{2}看作集合A的元素，不把{1,2}看作集合B的元素，或者把{1}，{2}，{1,2}看作是相同的．提示：笛卡兒積A×B是由集合A的每一個元素與集合B的各個元素合成有序對<x,y>（其中xA且yB）作為元素的集合．所謂有序對就是指一個有順序的數組，如<x,y>，x,y的位置是確定的，不能隨意放置．（2009年1月試卷第17題）設A={{a,b},1,2}，B={a,b,{1},1}，試計算（1）AB；（2）A∪B；（3）（A∪B）（A∩B）．[解題過程]（1）求集合A與B的差集，就是求屬于A而不屬于B的所有元素組成的集合．即AB={{a,b},1,2}{a,b,{1},1}={{a,b},2}（2）求集合A和B的并集A∪B，就是求由集合A和B的所有元素組成的集合．即A∪B={{a,b},1,2}∪{a,b,{1},1}={{a,b},1,2,a,b,{1}}（3）因為A∪B={{a,b},1,2,a,b,{1}}A∩B={{a,b},1,2}∩{a,b,{1},1}={1}所以（A∪B）（A∩B）={{a,b},1,2,a,b,{1}}{1}={{a,b},2,a,b,{1}}易錯點：同學們對集合中有的元素用集合形式表示的情形容易混淆，既把{a,b}與a,b看作是相同的．提示：求集合A與B的對稱差AB＝（A∪B）（A∩B），就是先求集合A與B的并集A∪B、A與B的交集A∩B，然后再求它們的差集．?？贾R點4：利用集合運算性質證明集合恒等式（歷年考核次數：4次，本課程共考過6次；重要程度：★★★）（運用此知識點和相關知識點解答本題，即將知識點講解與題目解答結合起來）（2008年9月試卷第19題）和（2009年10月試卷第18題）試證明集合等式A(BC)=(AB)(AC)．[證明過程]若對A(BC)中的任一元素x，即x∈A(BC)，則有x∈A或x∈BC，即x∈A或x∈B且x∈A或x∈C，也即x∈AB且x∈AC，得x∈(AB)(AC)．所以A(BC)(AB)(AC)．反之，若對(AB)(AC)中的任一元素x，即x∈(AB)(AC)，則有x∈AB且x∈AC，即x∈A或x∈B且x∈A或x∈C，也即x∈A或x∈BC，得x∈A(BC)．所以(AB)(AC)A(BC)．由此得A(BC)=(AB)(AC)．易錯點：要證明集合恒等式A(BC)=(AB)(AC)，必須要證明A(BC)(AB)(AC)，還要證明A(BC)(AB)(AC)，但同學們往往只做其中一個．提示：集合恒等式的證明方法通常有二：（1）要證明A＝B，只需要證明AB，又AB；（2）通過運算律進行等式推導.（2010年1月試卷第18題）設A，B是任意集合，試證明：若AA=BB，則A=B．[證明過程]設對A中的任一元素x，即xA，那么有序對<x，x>是笛卡兒積AA的元素，即<x，x>AA．因為AA=BB，故有<x，x>BB，則有xB．所以AB．又設對B中的任一元素x，即xB，那么有序對<x，x>是BB的元素，即<x，x>BB．因為AA=BB，故有<x，x>AA，則有xA．所以BA．由此得A=B．易錯點：要證明笛卡兒積的恒等式AA=BB，必須要證明AA(AB)(AC)，還要證明A(BC)(AB)(AC)，但同學們往往只做其中一個．提示：本題給出的條件是：笛卡兒積的恒等式AA=BB，需要證明兩個任意集合A，B相等，即A＝B．因此，需要證明AB，又AB．三、模擬練習（模擬練習中，既可以出歷年真題，也可以出一些和上述知識點對應的題目）練習1：（2010年1月試卷第1題）若集合A＝{a，{a}}，則下列表述正確的是()．A．{a}AB．{{{a}}}AC．{a，{a}}AD．A解析：A因為a是集合A＝{a，{a}}的元素，所以取元素a組成一個集合{a}就是A的子集，用包含關系表示是正確的．練習2：（2009年1月試卷第1題）若集合A={1，2}，B={1，2，{1，2}}，則下列表述正確的是()．A．AB，且ABB．BA，且ABC．AB，且ABD．AB，且AB解析：A因為集合A={1，2}既是取集合B={1，2，{1，2}}中元素1，2組成的一個集合，是B的一個真子集，用AB表示是正確的；但它也是B的元素，所以用AB表示也是正確的．練習3：若集合A={a，b}，B={a，{a，b}}，則（）．A．ABB．BAC．ABD．AB解析：D因為集合A={a，b}是集合B={a，{a，b}}的元素，所以用AB表示也是正確的．練習4：若集合A＝{2，a，{a}，4}，則下列表述正確的是()． A．{a，{a}}AB．{a}AC．{2}AD．aA解析：B因為a是集合A＝{2，a，{a}，4}的元素，所以取元素a組成一個集合{a}就是A的子集，用包含關系表示是正確的．練習5：（2009年7月試卷第6題）若集合A的元素個數為10，則其冪集的元素個數為．解析：1024因為集合A有10個元集，所以它的其冪集有210=1024個元素．練習6：設集合A={1,a}，則P(A)=()．A．{{1},{a}}B．{,{1},{a}}C．{,{1},{a},{1,a}}D．{{1},{a},{1,a}}解析：C因為，按照冪集定義，集合A＝{1，a}的所有子集就是A的冪集P(A)．A的全部子集由以下子集組成：0元子集（即空集）：；1元子集：{1}，{a}；2元子集（即集合A）：{1，a}．所以，集合A的冪集是：{,{1},{a},{1,a}}．練習7：（2010年1月試卷第16題）設集合A={{1},1,2}，B={1,{1,2}}，試計算（1）AB；（2）A∩B；（3）A×B．[解題過程]（1）因為A={{1},1,2}，B={1,{1,2}}，所以AB={{1},1,2}{1,{1,2}}={{1},2}（2）因為A={{1},1,2}，B={1,{1,2}}，所以A∩B={{1},1,2}∩{1,{1,2}}={1}（3）因為A={{1},1,2}，B={1,{1,2}}，所以A×B={{1},1,2}×{1,{1,2}}={<{1},1>，<{1},{1,2}>，<1,1>，<1,{1,2}>，<2,1>，<2,{1,2}>}練習8：設集合A＝{{a},b,c}，B={a,b,{c}}，求（1）（A∪B）－A；（2）A－（A∩B）；(3)BA．[解題過程]（1）因為A＝{{a},b,c}，B={a,b,{c}}