離散數(shù)學(xué)王元元習(xí)題解答 (5)

1、第二篇 集合論第四章 集合及其運(yùn)算4.1 集合的基本概念 內(nèi)容提要4.1.1集合及其元素 集合是一些確定的、作為整體識(shí)別的、互相區(qū)別的對(duì)象的總體。 組成集合的對(duì)象稱為集合的成員或元素（member）。通常用一對(duì)“ ”把集合的元素括起來，表示一個(gè)集合。 元素對(duì)于集合的隸屬關(guān)系是集合論的另一基本概念。即當(dāng)對(duì)象a是集合A的元素時(shí)，稱元素a屬于集合A，記為 aA 當(dāng)對(duì)象a不是集合A的元素時(shí)，稱a不屬于A，記為 Ø(aA)或aÏA 對(duì)任何對(duì)象a和任何集合A，或者aÎA或者aÏA,兩者恰居其一。這正是集合對(duì)其元素的“確定性”要求。定義41 空集和只含有有限多個(gè)元素的

2、集合稱為有限集（finite sets），否則稱為無限集（infinite sets）。有限集合中元素的個(gè)數(shù)稱為基數(shù)（cardinality）（無窮集合的基數(shù)概念將在以后重新嚴(yán)格定義）。集合A的基數(shù)表示為 |A|。4.1.2 外延公理、概括公理和正規(guī)公理集合論依賴于三大基本原理：外延公理（extensionality axiom）、概括公理（comprehension axiom）和正規(guī)公理（regularity axiom）。它們從根本上規(guī)定了集合概念的意義。外延公理：兩個(gè)集合 A和 B相等當(dāng)且僅當(dāng)它們具有相同的元素。即對(duì)任意集合A，B, A=B «"x(xÎA

3、«xÎB) 外延公理事實(shí)上刻劃了集合的下列特性：集合元素的“相異性”、“無序性”，及集合表示形式的不唯一性。 概括公理: 對(duì)任意個(gè)體域，任一謂詞公式都確定一個(gè)以該域中的對(duì)象為元素的集合。即對(duì)給定個(gè)體域U，對(duì)任意謂詞公式P(x)，存在集合S，使得 Sx êxÎUP(x) 概括公理規(guī)定了集合元素的確定性,以及集合的描述法表示的理論依據(jù)，它還規(guī)定了空集的存在性。 正規(guī)公理：不存在集合A1，A2, A3，使得 ÎA3 Î A2 ÎA1正規(guī)公理的一個(gè)自然推論是：對(duì)任何集合A，A¹A（否則有ÎAÎA

4、6;A）。從而規(guī)定了集合A與A的不同層次性,因而正規(guī)公理也就規(guī)定了集合不能是自己的元素。4.1.3 子集合 定義4.2 集合A稱為集合B的子集合（或子集，subsets），如果A的每一個(gè)元素都是B的元素，即 "x(xÎA®xÎB)A是B的子集，表示為AÍB（或BÊA），讀作“A包含于B”（或“B包含A”）。 定理4.1對(duì)任意集合A，B，AB當(dāng)且僅當(dāng)A Í B且B Í A 。定理4.2 對(duì)任意集合A，A Í U。 定理4.3 設(shè)A，B，C為任意集合，若A Í B,B Í C，則A 

5、05; C。 定理4.4 對(duì)任何集合A，Æ Í A。即空集是任意集合的子集。定理4.5 空集是唯一的。 定理 4.6 設(shè) A 為一有限集合，|A| = n，那么 A的子集個(gè)數(shù)為2n。 習(xí)題解答練習(xí)4.1l、證明：如果AÎb，那么bÎA。證 由于A為集合b的元素，而集合b中只有一個(gè)元素b，所以A=b；又因?yàn)閎Îb，所以bÎA。2、用描述法規(guī)定下列集合：（1）A 1，3，5（2）B = 2，3，5，7，11，13，17，89，97（3）C0，1，2，3，9（4）全集 U解 （1）A （2）B =，：為小于100的質(zhì)數(shù) （3）C （4）U

6、為任意一元謂詞公式3、對(duì)任意對(duì)象a，b,c，d，證明：a,a,bc,c，d 當(dāng)且僅當(dāng) a = c且b = d 證 設(shè)a = c且b = d，則顯然a,a,bc,c，d；設(shè)a,a,bc,c，d，則有ac，a,bc，d或者ac，d，a,bc。前一種情況有ac且bd；后一種情況有acd且abc，所以有ac且bd。命題得證。4、指出下列集合序列的排列規(guī)律，并依此規(guī)律再寫出兩個(gè)后續(xù)集合：Æ ，Æ，Æ,Æ,Æ，Æ，Æ，Æ，解 上述集合序列的排列規(guī)律是An+1AnÈAn。兩個(gè)后續(xù)集合分別為：Æ，Æ，

7、Æ，Æ，Æ，Æ，Æ，Æ；Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ。5、“如果AÎB, BÎC，那么AÎC”對(duì)任意對(duì)象A,B,C都成立嗎？都不成立嗎？舉例說明你的結(jié)論。解 并不都成立，例如：設(shè)A1,B1,C1，此時(shí)AÎB且BÎC，但AÏC；另一方面，并不是都不成立，例如：A1,B1, C1，1，此時(shí)

8、AÎB，BÎC，且AÎC。 6、確定下列各命題的真、假； （1）ÆÍ Æ （2）ÆÌ Æ （3）ÆÎÆ （4）Æ ÍÆ （5）ÆÎÆ （6）a, b Ía , b , c,a， b，c （7）a, bÎa， b， c，a， b，c （8）a, bÍa，b，a，b（9）a, bÎa，b，a，b（10）a, bÌa，b，a，b （11）對(duì)任意集合A，B，C，、若A

9、6;B，B Í C則AÎC。 （12）對(duì)任意集合A，B，C，若AÎB，B ÍC則A Í C。 （13）對(duì)任意集合A，B，C，若A Í B，BÎ C則A Î C。（l4）對(duì)任意集合A，B，C，若A Í B，B Î C則A Í C。解 （1）真，（2）假，（3）假，（4）真，（5）真，（6）真，（7）假，（8）假，（9）真，（10）真，（11）真，（12）假，（13）假，（14）假。 7、指出下列各組集合中的集合間的不同之處，并列出每一集合的元素和全部子集： （1） Æ，

10、98;（2）a，b，c，a，b，c，a，b，c解 （1）不同之處：前者是以空集為元素的集合，而后者是以前者為元素的集合。Æ的元素為Æ，全部子集為：Æ，ÆÆ的元素為Æ，全部子集為：Æ，Æ（2）第一個(gè)集合由3個(gè)元素組成；第二個(gè)集合由2個(gè)元素組成，其中一個(gè)元素為集合；第三個(gè)集合由1個(gè)元素組成，該元素為一個(gè)集合。a，b，c的元素為：a，b，c；全部子集為：Æ，a，b，c，a，b，b，c，a，c，a，b，c。a，b，c的元素為：a，b，c；全部子集為：Æ，a，b，c，a，b，c。a，b，c的元素為：a，b

11、，c；全部子集為：Æ，a，b，c。 8、羅素曾用下列較通俗的悖論來解釋他的集合論悖論（羅素悖論）：某鎮(zhèn)上一位理發(fā)師宣布，他只給那些不給自己刮臉的人刮臉。問：為什么這是一個(gè)悖論？解 如果理發(fā)師給自己刮臉，那么按照規(guī)定，理發(fā)師不能給自己刮臉（因?yàn)樗唤o那些不給自己刮臉的人刮臉）；如果理發(fā)師不給自己刮臉，那么按照規(guī)定，理發(fā)師應(yīng)該給自己刮臉（因?yàn)樗o那些不給自己刮臉的人刮臉）。這樣，理發(fā)師給自己刮臉或不給自己刮臉都得出矛盾。所以這是一個(gè)悖論。9、說明為什么在確定個(gè)體域上使用抽象原理(即使用概括公理)時(shí)羅素悖論不再成立。解 在確定的個(gè)體域D上使用概括公理時(shí)，羅素悖論中的集合當(dāng)我們?cè)賳枙r(shí)，回答時(shí)

12、不會(huì)導(dǎo)致矛盾，因?yàn)椤亩苊饬肆_素悖論的產(chǎn)生。10、設(shè)A，B為任意集合證明：如果對(duì)任意的集合C，C Í A當(dāng)且僅當(dāng)C Í B，那么AB。證 因?yàn)镃為任意的集合，因此，當(dāng)令CA時(shí)有A Í B，當(dāng)令CB時(shí)有B Í A，因此有AB。11、證明：不能使用“一切集合的集合（所謂大全集）”作為個(gè)體域U。（提示：若用大全集作為個(gè)體域；概括公理也將導(dǎo)致羅素悖論。）解 如題9，加上確定的個(gè)體域D為大全集U，則概括公理為S = x | xÎU Ù P(x)，它等價(jià)于S = x | P(x)，這就相同于抽象原理，會(huì)產(chǎn)成悖論。4.2 集合運(yùn)算 內(nèi)容提要4.2

13、.1 并、交、差、補(bǔ)運(yùn)算 定義4.4 設(shè)A，B為任意集合。 （l） AB稱為A與B的并集（union set），定義為 ABxxAxB稱為并運(yùn)算。 （2） AB稱為A與B的交集（intersection set），定義為 AB =xxAx B稱為交運(yùn)算。 （3） A-B稱為A與B的差集（difference set），定義為 A-BxxAx Ï B- 稱為差運(yùn)算。 （4）A稱為A的補(bǔ)集（complement set），定義為 A=U-A =x | xUxÏA 稱為補(bǔ)運(yùn)算，它是一元運(yùn)算，是差運(yùn)算的特例。定理4.7 設(shè)A，B，C為任意集合，那么 （l）AÈAA A&#

14、199;AA （冪等律） （2）AÈB = BÈA AÇB = BÇA （交換律） （3）AÈ（BÈC）=（AÈB）ÈC AÈ（BÈC）=（AÈB）ÈC （結(jié)合律） （4）AÈÆA， AÇU=A （同一律） （5）AÇÆ=Æ， AÈU = U （零一律） （6）AÈ(BÇC)=(AÈB)Ç(AÈC) AÇ(BÈC)=(AÇB)&

15、#200;(AÇC) （分配律） （7） AÈ（AÇB）= A， AÇ（AÈB）= A （吸收律） 定理 4.8 對(duì)任意集合 A，B，C， （l） A - BAÇB （2）A - AÆ， A - ÆA， A U = Æ （3）A - (BÈC)(A - B)Ç(A - C) A - (BÇC)(A - B)È(A - C) 定理4.9 對(duì)任意集合A，B（1） AA （雙重否定律）（2） UÆ , ÆU （補(bǔ)余律）（3） AÈAU , A

16、ÇAÆ （互否律） （4）(AÈB)AÇ B (AÇB)AÈ B （德摩根律） 定理4.10 對(duì)任意集合A , B , C , D， （1）A Í AÈB，B Í AÈB （2）AÇB Í A AÇB Í B。 （3）A - B Í A （4）A Í B, A - B = Æ,AÈB = B , AÇB = A 四個(gè)命題等價(jià)。 （5）若A Í B,則BÍ A 定理4.11 對(duì)任意集合A，

17、B若它們滿足 （l）AÈBU （2）AÇBÆ 那么BA4.2.2 求冪運(yùn)算和廣義并、交運(yùn)算* 定義 4.5 對(duì)任意集合 A，(A)稱為A的冪集（Power set），定義為 (A)x | xÍA 即A的全體子集構(gòu)成A的冪集。此種運(yùn)算稱為集合A的求冪運(yùn)算。 定理4.12 設(shè)A,B為任意集合, AÍB當(dāng)且僅當(dāng)(A) Í(B) 。 定義4.6 若集合C的每個(gè)元素都是集合，則稱C為集合族（collections）。若集合族C可表示為 C =Sd|d ÎD則稱 D為集合族的標(biāo)志集（index set）。定義4.7 設(shè)C為非空集合族，（

18、l） 稱為C的廣義并，定義為 （2） 稱為C的廣義交。定義為 （3）當(dāng)集合族C =Ad|d ÎD時(shí)，和可分別表示為，當(dāng)D為自然數(shù)集N時(shí)，它們又可分別表示為 ， 定理4.13 對(duì)任意集合A和集合族C，有 定理4.14 對(duì)任意集合A和集合族C，有 定理4.15 對(duì)任意集合族C有 定理4.16 對(duì)任意集合*4.2.3環(huán)和、環(huán)積運(yùn)算 定義4.8 對(duì)任意集合A，B， AÅB稱為A與B 的環(huán)和（cycle sum）或?qū)ΨQ差，定義為 AÅB = （A-B）È（B-A） AÄB稱為A與B 的環(huán)積（cycle product），定義為 AÄB = （A

19、ÅB）- 定理4.17 對(duì)任意集合A，B， 有（1） AÅB = （AÈB）-（A Ç B）（2） AÄB = （AÈB-）Ç（A- ÈB）定理4.18 對(duì)任意集合A，B，C，（1）A Å B = B Å A（2）A Å A = Æ（3）A- Å B- = A Å B （4）A Ä B = （A Å B）- = A- Å B = A Å B- （5）（A Å B）Å C = A Å （B

20、 Å C）（6）A Ä B = B Ä A（7）A Ä A = U（8）A- Ä B- = A Ä B（9）（A Ä B）Ä C = A Ä （B Ä C） 習(xí)題解答練習(xí)4.2l、證明定理4.7之（5）。證 （1）所以（2）所以2、證明定理4.8之（2）中的第二式。所以3、證明定理4.9之（4）。 證 所以。 4試以下列次序證明定理4.10的（4）：PÞ R ÞSÞQÞP證 P：A Í B，R：A È B = B，S：A Ç

21、B = A，Q：A B = Æ1）PÞ R：由定理4.10的（1）容易知道B Í A È B，下面要證明A È B Í B。設(shè)xÎA È B，那么xÎA或xÎB。若xÎA，因?yàn)锳 Í B，所以xÎB。因此有A È B Í B。所以A È B = B。2）R Þ S：由定理4.10的（2）容易知道A Ç B Í A，下面要證明A Í A Ç B。設(shè)xÎA，則xÎ A &

22、#200; B。因?yàn)橐阎狝 È B = B，那么有xÎ B，所以xÎ A Ç B，從而A Í A Ç B。故A Ç B = A得證。3）S Þ Q：反設(shè)A BÆ，那么至少有一個(gè)元素xÎ A且xÏ B，則A Ç BA，與已知條件S矛盾，故A B = Æ得證。4）Q Þ P：設(shè)xÎA，設(shè)xÏ B，則xÎ A B，與A B = Æ矛盾，所以xÎ B，故A Í B得證。5說明下列各命題是否為真，為什么。（

23、1）若A È B = A È C，則B = C 。（2）若A Ç B = A Ç C，則B = C 。解 （1）命題不為真。例，令A(yù) = 1,2，B = 1，C = 2。（2）命題不為真。例，令A(yù) = Æ，B = 1，C = 2。6對(duì)任意集合A，B，C，證明： （A È C）-（B È C）Í A - B證：xÎ（A È C）-（B È C）Û xÎ（A È C）Ç（B È C） Û xÎ（A È C）&#

24、199; BÇ CÛ xÎ（A Ç BÇ C）È（C Ç BÇ C）Û xÎ（A Ç BÇ C）Þ xÎ A Ç BÛ xÎ A - B故（A È C）-（B È C）Í A- B得證。 7對(duì)任意集合A，B，C，證明；（1） A -（B È C）（A - B）- C（A - C）- B（2）（A Ç B）- C = A Ç（B- C）=（A - C）Ç B

25、（3）（A - B）- CA -（B - C）當(dāng)且僅當(dāng)A Ç C = Æ（4）（A - B）- C =（A - C）-（B - C）證：（1）A -（B È C）A Ç（B È C） A Ç BÇ C （A - B）Ç C （A - B）- CA -（B È C）A Ç（B È C） A Ç BÇ C A Ç CÇ B =（A - C）Ç B （A - C）- B故A-（B È C）（A - B）- C（A - C）- B得證

26、。（2）（A Ç B）- C A Ç B Ç C A Ç（B Ç C） A Ç（B - C） （A Ç B）- C A Ç B Ç C A Ç CÇ B （A - C）Ç B故（A Ç B）- C = A Ç（B- C）=（A - C）Ç B得證。（3）設(shè)（A - B）- CA -（B - C）成立，為證A Ç C = Æ，反設(shè)有xÎA Ç C，則xÎA 且xÎC。而：（A - B）-

27、CA Ç BÇ C，所以xÏ A Ç BÇ C，從而xÏ（A - B）- C；A -（B - C）A Ç（B Ç C）A Ç（BÈ C）（A Ç B）È（A Ç C），由假設(shè)xÎA Ç C，則xÎ（A Ç B）È（A Ç C），從而x Î A -（B - C）。這與（A - B）- CA -（B - C）矛盾，所以假設(shè)不成立，故A Ç C = Æ得證。）設(shè)A Ç C

28、= Æ，此時(shí)設(shè)x為A中的任一元素，即xÎA，則x Ï C，所以A - CA，那么：（A - B）- C（A - B）ÇCA Ç BÇ CA Ç CÇ B（A - C）Ç BA Ç B；A -（B - C）A Ç（B Ç C）A Ç（BÈ C）（A Ç B）È（A Ç C）A Ç B所以在A Ç C = Æ 時(shí)，（A - B）- CA -（B - C）。綜合）、），故（A - B）- CA -（B

29、- C）當(dāng)且僅當(dāng)A Ç C = Æ得證。（4）證：（A - B）- C（A - B）Ç CA Ç BÇ C（A - C）-（B - C）（A Ç C）Ç（B Ç C） （A Ç C）Ç（BÈ C） （A Ç CÇ B）È（A Ç CÇ C） A Ç BÇ C故（A - B）- C（A - C）-（B - C）得證。 8證明；對(duì)任意集合A，B下列命題等價(jià)， （1）A Í B （2）AÈ B = U（

30、3）A Ç B= Æ證：（1）Þ（2）：為證AÈ B = U，反設(shè)有xÎ（AÈ B），即xÎ A Ç B，所以xÎ A且xÏB；而由A Í B知道xÎ A必有xÎ B，矛盾，故有AÈ B = U。（2）Þ（3）：因?yàn)锳È B = U，所以對(duì)任一x，有xÎA或xÎ B）若xÎA，則xÏA，那么xÏ A Ç B）若xÎB，則xÏB，那么xÏ A

31、99; B即沒有一個(gè)元素在集合A Ç B中，所以A Ç B= Æ。（3）Þ（1）：反證設(shè)A不包含于B，即有xÎ A且xÏB，所以有xÎ A Ç B，與已知A Ç B= Æ矛盾。所以A Í B。9設(shè)A = Æ，B = 1，2，求（A），（B）。解：A = Æ，所以（A）= Æ，Æ，（A）= Æ，Æ，Æ，Æ，Æ，故（A）= Æ，Æ，Æ，Æ，Æ，

32、8;，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ。B = 1，2，所以（B）= Æ，1，2，1，2，故（B）= Æ，Æ，1，

33、2， 1，2 ，Æ，1，Æ，2，Æ，1，2，1，2，1，1，2，2，1，2，Æ，1，2，Æ，1，1，2，1，2，1，2，Æ，2，1，2，Æ，1，2，1，2。 10對(duì)任意集合A，B。求證： （1）A = B當(dāng)且僅當(dāng)（A）=（B） （2）（A）Ç（B）（A Ç B）（3）（A）È（B）Í（A È B）證：（1）若A = B成立，那么有xÎ（A）Û x Í A Û x Í BÛ x Î（B）故有（A）=（B）；若

34、（A）=（B）成立，反設(shè)A B，那么有xÎ A且xÏ B（因?yàn)锳，B為任意集合，所以作此假設(shè)是合理的），則xÎ（A），而（A）=（B），則xÎ（B），這與xÏ B矛盾。因此A = B。綜上所述，故A = B當(dāng)且僅當(dāng)（A）=（B）得證。（2）xÎ（A）Ç（B）Û x Í A Ù x Í B Û x Í A Ç B Û x Î（A Ç B）故（A）Ç（B）（A Ç B）得證。（3）xÎ（A）È

35、;（B）Û x Í A Ú x Í B Þ x Í A È B Û x Î（A È B）故（A）È（B）Í（A È B）得證。11. 若C = x| xÎB 求。解：= B。 12. 對(duì)下列諸C，求 和。 （l）C =Æ （2）C =Æ，Æ （3）C =a，b，a,b （4）C =（N）（5）若允許C = Æ,請(qǐng)討論和。解：（1）= Æ，= Æ。（2）=Æ，= Æ。（3）=a，

36、b，= Æ。（4）=（N），= Æ。（5）=x | $s (s Î C Ù x Î s)，=x | "s (s Î C ® x Î s)，那么當(dāng)C = Æ時(shí),C中無任何元素，則此時(shí) ， 13對(duì)任意非空集合族C1，C2，證明： （1） （2） （3）（4）證 （1）x ÎÈÛ $s (s ÎÙ x Î s) Ú $s (s ÎÙ x Î s) Û $s (s ÎÙ x

37、Î s) Ú (s ÎÙ x Î s) Û $s (s Î(È)Ù x Î s) Û因此， 。（2）設(shè)xÎ() Ç ()，那么xÎ()且xÎ()，則：$s (s ÎÙ x Î s)且$s (s ÎÙ x Î s)，那么有：$(s1 Ç s2)(s Í (s1 Ç s2) Ù x Î s Ù s1 ÎÙ s2

38、Î)， 則：x Î s1 Ç s2| s1 ÎÙ s2 Î，即有() Ç () Í s1 Ç s2| s1 ÎÙ s2 Î；且以上推導(dǎo)均可逆，故有Ç s1 Ç s2| s1 ÎÙ s2 Î。（3）設(shè)對(duì)于任一x Î()，則對(duì)任一s1 Î有x Î s1或?qū)θ我籹2 Î有x Î s2，那么對(duì)任一s1 È s2（s1 Î，s2 Î）有x Î s1

39、 È s2，因此：x Î s1 È s2| s1 ÎÙ s2 Î，所以()Í s1 È s2| s1 ÎÙ s2 Î，且以上推導(dǎo)均可逆，故有() = s1 È s2| s1 ÎÙ s2 Î。（4）仿上題，易證ÇÍ；而對(duì)任一s，sÎÈ，有xÎs，則對(duì)任一s1Î，有x Î s1，且對(duì)任一s2Î有xÎ s2，因此ÍÇ。故有Ç=。 *1

40、4對(duì)任意集合A，B，C，證明： （1）A Å A Å B = B （2）（A - B）Å B = A È B （3）（A Ä B）È C =（A È C） Ä（B È C） （4）（A Å B）Ç C =（A Ç C） Å（B Ç C） （5）（A Å B） C =（A C） Å（B C） （6）A È B = A Å（B Å（A Ç B）證 （1）A Å A Å B = &#

41、198; Å B = ( Æ B) È (B Æ) = B（2）(AB) Å B = (A Ç B) Å B = (A Ç B B) È (B A Ç B) = (A Ç B) È B = (A È B) Ç (B È B) = A È B（3）(A Ä B) È C = (A Å B) È C = (A B) È (B A) È C = (AÇ B) È

42、(A Ç B) È C(A È C) Ä (B È C) = (A È C) Å (B È C) = (A È C) (B È C) È (B È C) (A È C) ) = (AÇ CÇ BÇ C) È (B È C) Ç (A È C) = (AÇ BÇ C) È (A Ç B) È C = (AÇ BÇ C) È

43、; C È (A Ç B) = (AÇ B) È C) Ç (C È C) È (A Ç B) = (AÇ B) È C È (A Ç B)所以有（A Ä B）È C =（A È C） Ä（B È C）。（4）(A Ç C) Å (B Ç C) = (A Ç C) (B Ç C) È (B Ç C) (A Ç C) = (A Ç C &#

44、199; (BÈ C) È (B Ç C Ç (AÈ C) = (A Ç C Ç B) È (A Ç C Ç C) È (B Ç CÇ A) È (B Ç C Ç C) = (A Ç C Ç B) È (B Ç CÇ A) = (A Ç B) È (AÇ B) Ç C = (A B) È (B A) Ç C = (A Å

45、; B) Ç C所以有(A Å B) Ç C = (A Ç C) Å (B Ç C)。（5）(A Å B) C = (A Ç B) È (AÇ B) Ç C = (A Ç B) Ç C) È (AÇ B) Ç C) = (A Ç B Ç C) È (AÇ B Ç C) (A C) Å (B C) = (A C) (B C) È (B C) (A C) = (A

46、99; CÇ (B C) È (BÇ CÇ (A C) = (A Ç CÇ (B È C) È (BÇ CÇ(A È C) = (A Ç CÇ B) È (AÇ CÇ C) È (BÇ CÇ A) È (BÇ CÇ C) = (A Ç CÇ B) È (BÇ CÇ A)所以有(A Å B) C = (A Ç

47、CÇ B) È (BÇ CÇ A)。（6）A Å (B Å (A Ç B) = A Å (B A Ç B) È (A Ç B B) = A Å (B Ç(A Ç B) ) È (A Ç BÇ B) = A Å (B Ç(A È B) = A Å (A Ç B) = (A A Ç B) È (A Ç B A) = (A Ç (A È

48、; B) È (A Ç B Ç A) = A È (A Ç B) È (A Ç B)= (AÈ A) Ç (A È B) È (A Ç B)= (A È B) È (A Ç B)= (A È B È A) Ç (A È BÇ B)= A È B所以有A È B = A Å (B Å (A Ç B)。*15.對(duì)任意集合A，B，C，證明：（1） 若A

49、C = B C，則A Å B Í C。（2）若A Å B = A Å C，則B = C。證 （1）反設(shè)(A Å B) Í C，則存在xÎ(A B) È (B A)且xÏC，）若xÎ A B，則有xÎA，xÏB，xÏC，所以xÎ A C而xÏ B C，與已知的A C = B C矛盾；）若xÎ B A，則有xÎ B，xÏ A，xÏC，所以xÎ B C而xÏ A C，與已知的A C = B C

50、矛盾。因此，A Å B Í C。（2） 反設(shè)B = C，那么不妨設(shè)有x，xÎB，xÏC。）若xÎ A，則xÏ A Å B，但xÎA Å C，與A Å B = A Å C矛盾。）若xÏA，則x ÎA Å B，但xÏA Å C，又與A Å B = A Å C矛盾。因此有B = C。4.3 集合的歸納定義及歸納法證明 內(nèi)容提要4.3.1集合的歸納定義 集合的歸納定義由三部分組成: （1）基礎(chǔ)條款：規(guī)定待定義集合以某些元素為

51、其基本成員，集合的其它元素可以從它們出發(fā)逐步確定。 （2）歸納條款：規(guī)定由已確定的集合元素去進(jìn)一步確定其它元素的規(guī)則。于是，可以從基本元素出發(fā)，反復(fù)運(yùn)用這些規(guī)則來確認(rèn)待定義集合的所有成員。 （3）終極條款：規(guī)定待定義集合只含有（l），（2）條款所確定的成員。條款（l），（2）又稱歸納定義的完備性條款，它們必須保證毫無遺漏地產(chǎn)生出待定義集合的全部成員；條款（3）又稱歸納定義的純粹性條款，它保證整個(gè)定義過程所規(guī)定的集合只包括滿足要求的那些對(duì)象。4.3.2 自然數(shù)的集合論定義 定義 4.9 （l）稱空集 Æ 為自然數(shù)，記為0。 （2）稱A為集合A的直接后繼，如果 AA ÈA 定義

52、4.10 歸納定義自然數(shù)集N： （l）基礎(chǔ)條款：ÆÎN 。 （2）歸納條款：如果xÎN ，則x= x ÈxÎ N。 （3）終極條款（略） 按照上述定義。自然數(shù)集N由下列元素組成： Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，或 0，0，0”，0”，將它們依次表示為 0，1，2，3， 習(xí)題解答練習(xí) 4.31歸納定義å*（å*å+Èl），令å= a，b。解 （1）基礎(chǔ)條款：å Í å*，l Î

53、 å*（2）歸納條款：如果xÎ å，yÎ å*，則xyÎ å*（3） 終極條款：除有限次使用（1）、（2）條款確定的元素外，å*中沒有別的元素。 2令å= a,b,c，歸納定義： （l） L Í å*，使L中所有字里都有字ab的出現(xiàn)，且所有含字 ab的字全在L中。（2） L Í å*，使L中所有字里都含有字符a和b，且所有含字符a,b的字全在L中。解 （1）基礎(chǔ)條款：ab Î L）歸納條款：如果xÎ å，yÎ L，則xy &#

54、206;L，yx ÎL）終極條款：除有限次使用（1）、（2）條款確定的元素外，L中沒有別的元素。（2）基礎(chǔ)條款：abÎ L，baÎ L）歸納條款：如果xÎ å，yÎ L，y=w1w2則w1xw2ÎL）終極條款：除有限次使用（1）、（2）條款確定的元素外，L中沒有別的元素。 3歸納定義下列集合： （1）十進(jìn)制無符號(hào)整數(shù)集合，非零數(shù)不得以 0為字頭。 （2）十進(jìn)制非負(fù)有窮小數(shù)。 （3）全體十進(jìn)制有理數(shù)。（4）二進(jìn)制形式的非負(fù)偶數(shù)， 非零數(shù)不得以0為字頭解 （1）設(shè)I表示十進(jìn)制無符號(hào)整數(shù)集合，其歸納定義如下：）基礎(chǔ)條款：0，1，2

55、，3，4，5，6，7，8，9Í I）歸納條款：如果xÎ I且x 0，yÎ I，則xy Î I 。）終極條款：除有限次使用（1）、（2）條款確定的元素外，I中沒有別的元素。（2）設(shè)R表示十進(jìn)制非負(fù)有窮小數(shù)集合，其歸納定義如下：）基礎(chǔ)條款：x. ê xÎ IÍ R）歸納條款：如果xÎ R，yÎ0，1，2，3，4，5，6，7，8，9，則xyÎ R）終極條款：除有限次使用（1）、（2）條款確定的元素外，R中沒有別的元素。（3）設(shè)Q表示全體十進(jìn)制有理數(shù)集合，其歸納定義如下：）基礎(chǔ)條款：I Í Q

56、 (I為整數(shù)集)）歸納條款：如果xÎ Q且x 0，yÎ Q，則x/y Î Q）終極條款：除有限次使用（1）、（2）條款確定的元素外，Q中沒有別的元素。 4 回憶命題公式的定義（公式中括號(hào)不省略）?，F(xiàn)將公式中命題變?cè)?、命題常元和聯(lián)結(jié)詞全部刪去，所留下的括號(hào)串稱為成形括號(hào)串。 （l）歸納定義成形括號(hào)串集合（假定它含有空括號(hào)串l）。 （2）證明：成形括號(hào)串中左括號(hào)數(shù)等于右括號(hào)數(shù)。（3）證明：成形括號(hào)串的字頭中，左括號(hào)數(shù)不少于右括號(hào)數(shù)。解 （1）設(shè)R表示成形括號(hào)串集合，其歸納定義如下（為了明晰，用 代替（ ） ）：）基礎(chǔ)條款：lÎ R）歸納條款：如果x、y

57、06;R，則x ÎR，xy ÎR）終極條款：除有限次使用（1）、（2）條款確定的元素外，R中沒有別的元素。（2）證明：設(shè)L（x），R（x）分別表示成形括號(hào)串x中的左、右括號(hào)數(shù)。）基礎(chǔ)：L（l）= R（l）= 0，命題成立。）歸納：設(shè)L（x）= R（x），L（y）= R（y），則 L（x）= L（x）+ 1 = R（x）+ 1 = R（x）， L（xy）= L（x）+ L（y）= R（x）+ R（y）= R（xy）因此對(duì)一切成形括號(hào)串x，有L（x）= R（x）。（3）證明：）基礎(chǔ)：空成形括號(hào)串的字頭的左括號(hào)數(shù)不少于右括號(hào)數(shù)無義地真。）歸納：設(shè)成形括號(hào)串x，y的字頭中左括號(hào)數(shù)大于或等于右括號(hào)數(shù)，則x的字頭為l 或 或 毗連x的字頭，而x的字頭中左括號(hào)數(shù)大于或等于右括號(hào)數(shù)，因此x的字頭中左括號(hào)數(shù)大于或等于右括號(hào)數(shù)。又xy的字頭集合中包括x的字頭以及x與y的字頭毗連而成的字頭。因?yàn)閤，y的字頭中左括號(hào)數(shù)大于或等于右括號(hào)數(shù)，而x中左括號(hào)數(shù)等于右括號(hào)數(shù)，因此xy的字頭的左括號(hào)數(shù)大于或等于右括號(hào)數(shù)。歸納完成，命題得證。5用歸納法證明：對(duì)任意正整數(shù)n有 (1 + 2 + + n)213 + 23 + + n3證 ）基礎(chǔ)：當(dāng)n = 1時(shí)，12 13）歸納：設(shè)當(dāng)n = k時(shí)，(1 + 2 + + k)213 + 23 + + k3那么當(dāng)n = k +1