离散数学王元元习题解答 (5)

1、第二篇 集合论第四章 集合及其运算4.1 集合的基本概念 内容提要4.1.1集合及其元素 集合是一些确定的、作为整体识别的、互相区别的对象的总体。 组成集合的对象称为集合的成员或元素（member）。通常用一对“ ”把集合的元素括起来，表示一个集合。 元素对于集合的隶属关系是集合论的另一基本概念。即当对象a是集合A的元素时，称元素a属于集合A，记为 aA 当对象a不是集合A的元素时，称a不属于A，记为 Ø(aA)或aÏA 对任何对象a和任何集合A，或者aÎA或者aÏA,两者恰居其一。这正是集合对其元素的“确定性”要求。定义41 空集和只含有有限多个元素的

2、集合称为有限集（finite sets），否则称为无限集（infinite sets）。有限集合中元素的个数称为基数（cardinality）（无穷集合的基数概念将在以后重新严格定义）。集合A的基数表示为 |A|。4.1.2 外延公理、概括公理和正规公理集合论依赖于三大基本原理：外延公理（extensionality axiom）、概括公理（comprehension axiom）和正规公理（regularity axiom）。它们从根本上规定了集合概念的意义。外延公理：两个集合 A和 B相等当且仅当它们具有相同的元素。即对任意集合A，B, A=B «"x(xÎA

3、«xÎB) 外延公理事实上刻划了集合的下列特性：集合元素的“相异性”、“无序性”，及集合表示形式的不唯一性。 概括公理: 对任意个体域，任一谓词公式都确定一个以该域中的对象为元素的集合。即对给定个体域U，对任意谓词公式P(x)，存在集合S，使得 Sx êxÎUP(x) 概括公理规定了集合元素的确定性,以及集合的描述法表示的理论依据，它还规定了空集的存在性。 正规公理：不存在集合A1，A2, A3，使得 ÎA3 Î A2 ÎA1正规公理的一个自然推论是：对任何集合A，A¹A（否则有ÎAÎA

4、6;A）。从而规定了集合A与A的不同层次性,因而正规公理也就规定了集合不能是自己的元素。4.1.3 子集合 定义4.2 集合A称为集合B的子集合（或子集，subsets），如果A的每一个元素都是B的元素，即 "x(xÎA®xÎB)A是B的子集，表示为AÍB（或BÊA），读作“A包含于B”（或“B包含A”）。 定理4.1对任意集合A，B，AB当且仅当A Í B且B Í A 。定理4.2 对任意集合A，A Í U。 定理4.3 设A，B，C为任意集合，若A Í B,B Í C，则A 

5、05; C。 定理4.4 对任何集合A，Æ Í A。即空集是任意集合的子集。定理4.5 空集是唯一的。 定理 4.6 设 A 为一有限集合，|A| = n，那么 A的子集个数为2n。 习题解答练习4.1l、证明：如果AÎb，那么bÎA。证 由于A为集合b的元素，而集合b中只有一个元素b，所以A=b；又因为bÎb，所以bÎA。2、用描述法规定下列集合：（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的质数 （3）C （4）U

6、为任意一元谓词公式3、对任意对象a，b,c，d，证明：a,a,bc,c，d 当且仅当 a = c且b = d 证 设a = c且b = d，则显然a,a,bc,c，d；设a,a,bc,c，d，则有ac，a,bc，d或者ac，d，a,bc。前一种情况有ac且bd；后一种情况有acd且abc，所以有ac且bd。命题得证。4、指出下列集合序列的排列规律，并依此规律再写出两个后续集合：Æ ，Æ，Æ,Æ,Æ，Æ，Æ，Æ，解 上述集合序列的排列规律是An+1AnÈAn。两个后续集合分别为：Æ，Æ，

7、Æ，Æ，Æ，Æ，Æ，Æ；Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ。5、“如果AÎB, BÎC，那么AÎC”对任意对象A,B,C都成立吗？都不成立吗？举例说明你的结论。解 并不都成立，例如：设A1,B1,C1，此时AÎB且BÎC，但AÏC；另一方面，并不是都不成立，例如：A1,B1, C1，1，此时

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）对任意集合A，B，C，、若A

9、6;B，B Í C则AÎC。 （12）对任意集合A，B，C，若AÎB，B ÍC则A Í C。 （13）对任意集合A，B，C，若A Í B，BÎ C则A Î C。（l4）对任意集合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）第一个集合由3个元素组成；第二个集合由2个元素组成，其中一个元素为集合；第三个集合由1个元素组成，该元素为一个集合。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、罗素曾用下列较通俗的悖论来解释他的集合论悖论（罗素悖论）：某镇上一位理发师宣布，他只给那些不给自己刮脸的人刮脸。问：为什么这是一个悖论？解 如果理发师给自己刮脸，那么按照规定，理发师不能给自己刮脸（因为他只给那些不给自己刮脸的人刮脸）；如果理发师不给自己刮脸，那么按照规定，理发师应该给自己刮脸（因为他给那些不给自己刮脸的人刮脸）。这样，理发师给自己刮脸或不给自己刮脸都得出矛盾。所以这是一个悖论。9、说明为什么在确定个体域上使用抽象原理(即使用概括公理)时罗素悖论不再成立。解 在确定的个体域D上使用概括公理时，罗素悖论中的集合当我们再问时，回答时

12、不会导致矛盾，因为。从而避免了罗素悖论的产生。10、设A，B为任意集合证明：如果对任意的集合C，C Í A当且仅当C Í B，那么AB。证 因为C为任意的集合，因此，当令CA时有A Í B，当令CB时有B Í A，因此有AB。11、证明：不能使用“一切集合的集合（所谓大全集）”作为个体域U。（提示：若用大全集作为个体域；概括公理也将导致罗素悖论。）解 如题9，加上确定的个体域D为大全集U，则概括公理为S = x | xÎU Ù P(x)，它等价于S = x | P(x)，这就相同于抽象原理，会产成悖论。4.2 集合运算 内容提要4.2

13、.1 并、交、差、补运算 定义4.4 设A，B为任意集合。 （l） AB称为A与B的并集（union set），定义为 ABxxAxB称为并运算。 （2） AB称为A与B的交集（intersection set），定义为 AB =xxAx B称为交运算。 （3） A-B称为A与B的差集（difference set），定义为 A-BxxAx Ï B- 称为差运算。 （4）A称为A的补集（complement set），定义为 A=U-A =x | xUxÏA 称为补运算，它是一元运算，是差运算的特例。定理4.7 设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 （结合律） （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 对任意集合 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 对任意集合A，B（1） AA （双重否定律）（2） UÆ , ÆU （补余律）（3） AÈAU , A

16、ÇAÆ （互否律） （4）(AÈB)AÇ B (AÇB)AÈ B （德摩根律） 定理4.10 对任意集合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 四个命题等价。 （5）若A Í B,则BÍ A 定理4.11 对任意集合A，

17、B若它们满足 （l）AÈBU （2）AÇBÆ 那么BA4.2.2 求幂运算和广义并、交运算* 定义 4.5 对任意集合 A，(A)称为A的幂集（Power set），定义为 (A)x | xÍA 即A的全体子集构成A的幂集。此种运算称为集合A的求幂运算。 定理4.12 设A,B为任意集合, AÍB当且仅当(A) Í(B) 。 定义4.6 若集合C的每个元素都是集合，则称C为集合族（collections）。若集合族C可表示为 C =Sd|d ÎD则称 D为集合族的标志集（index set）。定义4.7 设C为非空集合族，（

18、l） 称为C的广义并，定义为 （2） 称为C的广义交。定义为 （3）当集合族C =Ad|d ÎD时，和可分别表示为，当D为自然数集N时，它们又可分别表示为 ， 定理4.13 对任意集合A和集合族C，有 定理4.14 对任意集合A和集合族C，有 定理4.15 对任意集合族C有 定理4.16 对任意集合*4.2.3环和、环积运算 定义4.8 对任意集合A，B， AÅB称为A与B 的环和（cycle sum）或对称差，定义为 AÅB = （A-B）È（B-A） AÄB称为A与B 的环积（cycle product），定义为 AÄB = （A

19、ÅB）- 定理4.17 对任意集合A，B， 有（1） AÅB = （AÈB）-（A Ç B）（2） AÄB = （AÈB-）Ç（A- ÈB）定理4.18 对任意集合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） 习题解答练习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。设xÎA È B，那么xÎA或xÎB。若xÎA，因为A Í B，所以xÎB。因此有A È B Í B。所以A È B = B。2）R Þ S：由定理4.10的（2）容易知道A Ç B Í A，下面要证明A Í A Ç B。设xÎA，则xÎ A &

22、#200; B。因为已知A È B = B，那么有xÎ B，所以xÎ A Ç B，从而A Í A Ç B。故A Ç B = A得证。3）S Þ Q：反设A BÆ，那么至少有一个元素xÎ A且xÏ B，则A Ç BA，与已知条件S矛盾，故A B = Æ得证。4）Q Þ P：设xÎA，设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 = 1,2，B = 1，C = 2。（2）命题不为真。例，令A = Æ，B = 1，C = 2。6对任意集合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对任意集合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）当且仅当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）设（A - B）- CA -（B - C）成立，为证A Ç C = Æ，反设有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），由假设xÎA Ç C，则xÎ（A Ç B）È（A Ç C），从而x Î A -（B - C）。这与（A - B）- CA -（B - C）矛盾，所以假设不成立，故A Ç C = Æ得证。）设A Ç C

28、= Æ，此时设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 = Æ 时，（A - B）- CA -（B - C）。综合）、），故（A - B）- CA -（B

29、- C）当且仅当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证明；对任意集合A，B下列命题等价， （1）A Í B （2）AÈ B = U（

30、3）A Ç B= Æ证：（1）Þ（2）：为证AÈ B = U，反设有xÎ（AÈ B），即xÎ A Ç B，所以xÎ A且xÏB；而由A Í B知道xÎ A必有xÎ B，矛盾，故有AÈ B = U。（2）Þ（3）：因为AÈ B = U，所以对任一x，有xÎA或xÎ B）若xÎA，则xÏA，那么xÏ A Ç B）若xÎB，则xÏB，那么xÏ A

31、99; B即没有一个元素在集合A Ç B中，所以A Ç B= Æ。（3）Þ（1）：反证设A不包含于B，即有xÎ A且xÏB，所以有xÎ A Ç B，与已知A Ç B= Æ矛盾。所以A Í B。9设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对任意集合A，B。求证： （1）A = B当且仅当（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）成立，反设A B，那么有xÎ A且xÏ B（因为A，B为任意集合，所以作此假设是合理的），则xÎ（A），而（A）=（B），则xÎ（B），这与xÏ B矛盾。因此A = B。综上所述，故A = B当且仅当（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. 对下列诸C，求 和。 （l）C =Æ （2）C =Æ，Æ （3）C =a，b，a,b （4）C =（N）（5）若允许C = Æ,请讨论和。解：（1）= Æ，= Æ。（2）=Æ，= Æ。（3）=a，

36、b，= Æ。（4）=（N），= Æ。（5）=x | $s (s Î C Ù x Î s)，=x | "s (s Î C ® x Î s)，那么当C = Æ时,C中无任何元素，则此时 ， 13对任意非空集合族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）设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 Î；且以上推导均可逆，故有Ç s1 Ç s2| s1 ÎÙ s2 Î。（3）设对于任一x Î()，则对任一s1 Î有x Î s1或对任一s2 Î有x Î s2，那么对任一s1 È s2（s1 Î，s2 Î）有x Î s1

39、 È s2，因此：x Î s1 È s2| s1 ÎÙ s2 Î，所以()Í s1 È s2| s1 ÎÙ s2 Î，且以上推导均可逆，故有() = s1 È s2| s1 ÎÙ s2 Î。（4）仿上题，易证ÇÍ；而对任一s，sÎÈ，有xÎs，则对任一s1Î，有x Î s1，且对任一s2Î有xÎ s2，因此ÍÇ。故有Ç=。 *1

40、4对任意集合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.对任意集合A，B，C，证明：（1） 若A

49、C = B C，则A Å B Í C。（2）若A Å B = A Å C，则B = C。证 （1）反设(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） 反设B = C，那么不妨设有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 集合的归纳定义及归纳法证明 内容提要4.3.1集合的归纳定义 集合的归纳定义由三部分组成: （1）基础条款：规定待定义集合以某些元素为

51、其基本成员，集合的其它元素可以从它们出发逐步确定。 （2）归纳条款：规定由已确定的集合元素去进一步确定其它元素的规则。于是，可以从基本元素出发，反复运用这些规则来确认待定义集合的所有成员。 （3）终极条款：规定待定义集合只含有（l），（2）条款所确定的成员。条款（l），（2）又称归纳定义的完备性条款，它们必须保证毫无遗漏地产生出待定义集合的全部成员；条款（3）又称归纳定义的纯粹性条款，它保证整个定义过程所规定的集合只包括满足要求的那些对象。4.3.2 自然数的集合论定义 定义 4.9 （l）称空集 Æ 为自然数，记为0。 （2）称A为集合A的直接后继，如果 AA ÈA 定义

52、4.10 归纳定义自然数集N： （l）基础条款：ÆÎN 。 （2）归纳条款：如果xÎN ，则x= x ÈxÎ N。 （3）终极条款（略） 按照上述定义。自然数集N由下列元素组成： Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，或 0，0，0”，0”，将它们依次表示为 0，1，2，3， 习题解答练习 4.31归纳定义å*（å*å+Èl），令å= a，b。解 （1）基础条款：å Í å*，l Î

53、 å*（2）归纳条款：如果xÎ å，yÎ å*，则xyÎ å*（3） 终极条款：除有限次使用（1）、（2）条款确定的元素外，å*中没有别的元素。 2令å= a,b,c，归纳定义： （l） L Í å*，使L中所有字里都有字ab的出现，且所有含字 ab的字全在L中。（2） L Í å*，使L中所有字里都含有字符a和b，且所有含字符a,b的字全在L中。解 （1）基础条款：ab Î L）归纳条款：如果xÎ å，yÎ L，则xy &#

54、206;L，yx ÎL）终极条款：除有限次使用（1）、（2）条款确定的元素外，L中没有别的元素。（2）基础条款：abÎ L，baÎ L）归纳条款：如果xÎ å，yÎ L，y=w1w2则w1xw2ÎL）终极条款：除有限次使用（1）、（2）条款确定的元素外，L中没有别的元素。 3归纳定义下列集合： （1）十进制无符号整数集合，非零数不得以 0为字头。 （2）十进制非负有穷小数。 （3）全体十进制有理数。（4）二进制形式的非负偶数， 非零数不得以0为字头解 （1）设I表示十进制无符号整数集合，其归纳定义如下：）基础条款：0，1，2

55、，3，4，5，6，7，8，9Í I）归纳条款：如果xÎ I且x 0，yÎ I，则xy Î I 。）终极条款：除有限次使用（1）、（2）条款确定的元素外，I中没有别的元素。（2）设R表示十进制非负有穷小数集合，其归纳定义如下：）基础条款：x. ê xÎ IÍ R）归纳条款：如果xÎ R，yÎ0，1，2，3，4，5，6，7，8，9，则xyÎ R）终极条款：除有限次使用（1）、（2）条款确定的元素外，R中没有别的元素。（3）设Q表示全体十进制有理数集合，其归纳定义如下：）基础条款：I Í Q

56、 (I为整数集)）归纳条款：如果xÎ Q且x 0，yÎ Q，则x/y Î Q）终极条款：除有限次使用（1）、（2）条款确定的元素外，Q中没有别的元素。 4 回忆命题公式的定义（公式中括号不省略）。现将公式中命题变元、命题常元和联结词全部删去，所留下的括号串称为成形括号串。 （l）归纳定义成形括号串集合（假定它含有空括号串l）。 （2）证明：成形括号串中左括号数等于右括号数。（3）证明：成形括号串的字头中，左括号数不少于右括号数。解 （1）设R表示成形括号串集合，其归纳定义如下（为了明晰，用 代替（ ） ）：）基础条款：lÎ R）归纳条款：如果x、y

57、06;R，则x ÎR，xy ÎR）终极条款：除有限次使用（1）、（2）条款确定的元素外，R中没有别的元素。（2）证明：设L（x），R（x）分别表示成形括号串x中的左、右括号数。）基础：L（l）= R（l）= 0，命题成立。）归纳：设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）因此对一切成形括号串x，有L（x）= R（x）。（3）证明：）基础：空成形括号串的字头的左括号数不少于右括号数无义地真。）归纳：设成形括号串x，y的字头中左括号数大于或等于右括号数，则x的字头为l 或 或 毗连x的字头，而x的字头中左括号数大于或等于右括号数，因此x的字头中左括号数大于或等于右括号数。又xy的字头集合中包括x的字头以及x与y的字头毗连而成的字头。因为x，y的字头中左括号数大于或等于右括号数，而x中左括号数等于右括号数，因此xy的字头的左括号数大于或等于右括号数。归纳完成，命题得证。5用归纳法证明：对任意正整数n有 (1 + 2 + + n)213 + 23 + + n3证 ）基础：当n = 1时，12 13）归纳：设当n = k时，(1 + 2 + + k)213 + 23 + + k3那么当n = k