离散数学王元元习题解答5.doc

《离散数学王元元习题解答5.doc》由会员分享，可在线阅读，更多相关《离散数学王元元习题解答5.doc（19页珍藏版）》请在课桌文档上搜索。

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

2、nfinite sets。有限集合中元素的个数称为基数cardinality无穷集合的基数概念将在以后重新严格定义。集合A的基数表示为|A|。4.1.2外延公理、概括公理和正规公理集合论依赖于三大根本原理：外延公理extensionality axiom、概括公理prehension axiom和正规公理regularity axiom。它们从根本上规定了集合概念的意义。外延公理：两个集合 A和 B相等当且仅当它们具有一样的元素。即对任意集合A，B,A=Bx(xAxB) 外延公理事实上刻划了集合的如下特性：集合元素的“相异性、“无序性，与集合表示形式的不唯一性。 概括公理: 对任意个体域，任一

3、谓词公式都确定一个以该域中的对象为元素的集合。即对给定个体域U，对任意谓词公式P(x)，存在集合S，使得 Sx xUP(x) 概括公理规定了集合元素确实定性,以与集合的描述法表示的理论依据，它还规定了空集的存在性。正规公理：不存在集合A1，A2, A3，使得 A3A2A1正规公理的一个自然推论是：对任何集合A，AA否如此有AAA。从而规定了集合A与A的不同层次性,因而正规公理也就规定了集合不能是自己的元素。4.1.3子集合定义4.2集合A称为集合B的子集合或子集，subsets，如果A的每一个元素都是B的元素，即x(xAxB)A是B的子集，表示为AB或BA，读作“A包含于B或“B包含A。 对任

4、意集合A，B，AB当且仅当A B且B A 。对任意集合A，AU。定理4.3 设A，B，C为任意集合，假如A B,B C，如此AC。定理4.4 对任何集合A， A。即空集是任意集合的子集。定理4.5 空集是唯一的。定理 4.6设 A 为一有限集合，|A|= n，那么 A的子集个数为2n。习题解答练习4.1l、证明：如果Ab，那么bA。证由于A为集合b的元素，而集合b中只有一个元素b，所以A=b；又因为bb，所以bA。2、用描述法规定如下集合：1A 1，3，52B = 2，3，5，7，11，13，17，89，973C0，1，2，3，94全集 U解 1A 2B =，：为小于100的质数 3C4U为任

5、意一元谓词公式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+1AnAn。两个后续集合分别为：，；，。5、“如果AB, BC，那么AC对任意对象A,B,C都成立吗？都不成立吗？举例说明你的结论。解 并不都成立，例如：设A1,B1,C1，此时AB

6、且BC，但AC；另一方面，并不是都不成立，例如：A1,B1, C1，1，此时AB，BC，且AC。 6、确定如下各命题的真、假； 1 2 3 4 5 6a, b a,b,c,a， b，c 7a, ba， b， c，a， b，c 8a, ba，b，a，b9a, ba，b，a，b10a, ba，b，a，b 11对任意集合A，B，C，、假如AB，BC如此AC。 12对任意集合A，B，C，假如AB，B C如此AC。 13对任意集合A，B，C，假如A B，B C如此A C。l4对任意集合A，B，C，假如A B，B C如此AC。解 1真，2假，3假，4真，5真，6真，7假，8假，9真，10真，11真，12假

7、，13假，14假。 7、指出如下各组集合中的集合间的不同之处，并列出每一集合的元素和全部子集：1 ， 2a，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，c；全部子集为：，a，b，c。 8

8、、罗素曾用如下较通俗的悖论来解释他的集合论悖论罗素悖论：某镇上一位理发师宣布，他只给那些不给自己刮脸的人刮脸。问：为什么这是一个悖论？解 如果理发师给自己刮脸，那么按照规定，理发师不能给自己刮脸因为他只给那些不给自己刮脸的人刮脸；如果理发师不给自己刮脸，那么按照规定，理发师应该给自己刮脸因为他给那些不给自己刮脸的人刮脸。这样，理发师给自己刮脸或不给自己刮脸都得出矛盾。所以这是一个悖论。9、说明为什么在确定个体域上使用抽象原理(即使用概括公理)时罗素悖论不再成立。解 在确定的个体域D上使用概括公理时，罗素悖论中的集合当我们再问时，回答时不会导致矛盾，因为。从而防止了罗素悖论的产生。10、设A，B

9、为任意集合证明：如果对任意的集合C，C A当且仅当C B，那么AB。证 因为C为任意的集合，因此，当令CA时有A B，当令CB时有B A，因此有AB。11、证明：不能使用“一切集合的集合所谓大全集作为个体域U。提示：假如用大全集作为个体域；概括公理也将导致罗素悖论。解 如题9，加上确定的个体域D为大全集U，如此概括公理为S = x | xU P(x)，它等价于S = x | P(x)，这就一样于抽象原理，会产成悖论。4.2集合运算 容提要4.2.1 并、交、差、补运算 设A，B为任意集合。 l AB称为A与B的并集union set，定义为 ABxxAxB称为并运算。 2 AB称为A与B的交集

10、intersection set，定义为 AB =xxAx B称为交运算。 3 A-B称为A与B的差集difference set，定义为 A-BxxAx B- 称为差运算。 4A称为A的补集plement set，定义为 A=U-A=x| xUxA称为补运算，它是一元运算，是差运算的特例。定理4.7 设A，B，C为任意集合，那么 lAAA AAA 幂等律 2AB = BA AB = BA 交换律 3ABC=ABC ABC=ABC 结合律4AA， AU=A 同一律 5A=， AU = U 零一律 6A(BC)=(AB)(AC) A(BC)=(AB)(AC) 分配律 7AAB= A， AAB=

11、A 吸收律定理 4.8对任意集合 A，B，C，l A - BAB 2A - A，A - A， A U = 3A - (BC)(A - B)(A - C) A - (BC)(A - B)(A - C) 定理4.9对任意集合A，B（1） AA 双重否认律（2） U , U补余律3AAU , AA互否律4(AB)A B(AB)A B德摩根律 对任意集合A , B , C , D， 1A AB，B AB 2ABA ABB。 3A - B A 4A B,A - B= ,AB = B , AB=A 四个命题等价。 5假如A B,如此BA定理4.11 对任意集合A，B假如它们满足 lABU 2AB 那么BA

12、4.2.2 求幂运算和广义并、交运算*定义 4.5 对任意集合 A，(A)称为A的幂集Power set，定义为(A)x | xA 即A的全体子集构成A的幂集。此种运算称为集合A的求幂运算。定理4.12设A,B为任意集合, AB当且仅当(A)(B) 。定义4.6 假如集合C的每个元素都是集合，如此称C为集合族collections。假如集合族C可表示为 C =Sd|d D如此称 D为集合族的标志集index set。定义4.7 设C为非空集合族，（l） 称为C的广义并，定义为 2 称为C的广义交。定义为 3当集合族C=Ad|d D时，和可分别表示为，当D为自然数集N时，它们又可分别表示为 ，定

13、理4.13 对任意集合A和集合族C，有对任意集合A和集合族C，有定理4.15 对任意集合族C有定理4.16 对任意集合*4.2.3环和、环积运算 定义4.8 对任意集合A，B， AB称为A与B 的环和cycle sum或对称差，定义为 AB = A-BB-AAB称为A与B 的环积cycle product，定义为 AB = AB- 对任意集合A，B， 有（1） AB = AB-A B（2） AB = AB-A- B定理4.18对任意集合A，B，C，1A B = B A2A A = 3A- B- = A B 4A B = A B-= A- B = A B- 5A B C = A B C6A B

14、= B A7A A = U8A- B- = A B9A 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 RSQP证P：A B，R：A B = B，S：A B = A，Q：A B = 1P R：由定理4.10的1容易知道B A B，下面要证明A B B。设xA B，那么xA或xB。假如xA，因为A B，所以xB。因此有A B B。所以A B = B。2R S：由定理4.10的2容易知道A B A，下面要证明A A B。设xA，如此x A B。因为A

15、B = B，那么有x B，所以x A B，从而A A B。故A B = A得证。3S Q：反设A B，那么至少有一个元素x A且xB，如此A BA，与条件S矛盾，故A B = 得证。4Q P：设xA，设xB，如此x A B，与A B = 矛盾，所以x B，故A B得证。5说明如下各命题是否为真，为什么。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 CA - B证：xA C-B C xA CB

16、CxA C B CxA B CC B C xA B C x A B x A - B故A C-B CA- B得证。 7对任意集合A，B，C，证明；（1） A -B CA - B- CA - C- B2A B- C = A B- C=A - CB 3A - B- CA -B - C当且仅当A C = 4A - B- C =A - C-B - C证：1A -B CA B C A B C A - B C A - B- CA -B CA B C A B C A C B =A - C B A - C- B故A-B CA - B- CA - C- B得证。2A B- C A B C A B C A B -

17、C A B- C A B C A C B A - CB故A B- C = A B- C=A - CB得证。3设A- B- CA -B - C成立，为证A C = ，反设有xA C，如此xA 且xC。而：A - B- CA B C，所以x A B C，从而xA - B- C；A -B - CA B CA B CA BA C，由假设xA C，如此xA BA C，从而x A -B - C。这与A- B- CA -B - C矛盾，所以假设不成立，故A C = 得证。设A C = ，此时设x为A中的任一元素，即xA，如此x C，所以A - CA，那么：A- B- CA - BCA B CA C BA -

18、 C BA B；A -B - CA B CA B CA BA CA B所以在A C = 时，A- B- CA -B - C。综合、，故A - B- CA -B - C当且仅当A C = 得证。4证：A - B- CA - BCA B CA - C-B - CA CB C A CB C A C BA CC A B C故A - B- CA - C-B - C得证。8证明；对任意集合A，B如下命题等价， 1A B 2A B = U3AB= 证：12：为证A B = U，反设有xA B，即x AB，所以x A且xB；而由A B知道x A必有x B，矛盾，故有A B = U。23：因为A B = U，所

19、以对任一x，有xA或x B假如xA，如此xA，那么x AB假如xB，如此xB，那么x AB即没有一个元素在集合AB中，所以AB= 。31：反证设A不包含于B，即有x A且xB，所以有x A B，与AB= 矛盾。所以A B。9设A = ，B = 1，2，求A，B。解：A = ，所以A= ，A= ，故A= ，。B = 1，2，所以B= ，1，2，1，2，故B= ，1，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。求证： 1A = B当且仅当A=B 2ABA B3ABA B证：1假如A = B成立

20、，那么有xA x A x B x B故有A=B；假如A=B成立，反设A B，那么有x A且x B因为A，B为任意集合，所以作此假设是合理的，如此xA，而A=B，如此xB，这与x B矛盾。因此A = B。综上所述，故A = B当且仅当A=B得证。2xAB x A x B x A B x A B故ABA B得证。3xAB x A x B x A B x A B故ABA B得证。11. 假如C = x|xB 求。解：= B。12. 对如下诸C，求 和。lC = 2C =， 3C =a，b，a,b 4C =N5假如允许C = ,请讨论和。解：1= ，= 。2=，= 。3=a，b，= 。4=N，= 。5

21、=x | $s (s C x s)，=x | s (s C x s)，那么当C = 时,C中无任何元素，如此此时 ， 13对任意非空集合族C1，C2，证明： 1 2 34证 1x $s (s x s) $s (s x s)$s (s x 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)， 如此：x s1 s2| s1 s2，即有() () s1 s2| s1 s2；且以上推导均可逆，故有 s1 s2| s1 s2。3设对于任一x ()

22、，如此对任一s1有x s1或对任一s2有x s2，那么对任一s1 s2s1，s2有x s1 s2，因此：x s1 s2| s1 s2，所以() s1 s2| s1 s2，且以上推导均可逆，故有() = s1 s2| s1 s2。4仿上题，易证；而对任一s，s，有xs，如此对任一s1，有x s1，且对任一s2有x s2，因此。故有=。*14对任意集合A，B，C，证明： 1A A B = B 2A - B B = A B 3A B C =A C B C 4A B C =A C B C 5A B C =A C B C 6A B = A B A B证 1A A B = B = ( B) (B) = B

23、2(AB) B = (A B) B = (A B B) (B A B) = (A B) B = (A B) (B B) = A B3(A B) C = (A B) C = (A B) (B A) C = (A B) (A B) C(A C) (B C) = (A C) (B C) = (A C) (B C) (B C) (A C) ) = (A CB C) (B C) (A C) = (AB C) (A B) C = (AB C) C (A B) = (AB) C) (C C) (A B) = (AB) C (A B)所以有A B C =A C B C。4(A C) (B C) = (A C)

24、 (B C) (B C) (A C) = (A C (BC) (B C (A C) = (A C B) (A C C) (B CA) (B C C) = (A C B) (B CA) = (A B) (A B) C = (A B) (B A) C = (A B) C所以有(A B) C = (A C) (B C)。5(A B) C = (A B)(AB) C = (A B) C) (AB) C) = (A B C) (AB C) (A C) (B C) = (A C) (B C) (B C) (A C) = (A C (B C) (B C (A C) = (A C (B C) (B C(A C

25、) = (A C B) (A C C) (B C A) (B C C) = (A C B) (B C A)所以有(A B) C = (A C B) (B C A)。6A (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 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

26、，证明：（1） 假如A C = B C，如此A B C。2假如A B = A C，如此B = C。证 1反设(A B) C，如此存在x(A B) (B A)且xC，假如x A B，如此有xA，xB，xC，所以x A C而x B C，与的A C = B C矛盾；假如x B A，如此有x B，x A，xC，所以x B C而x A C，与的A C = B C矛盾。因此，A B C。（2） 反设B = C，那么不妨设有x，xB，xC。假如x A，如此x A B，但xA C，与A B = A C矛盾。假如xA，如此x A B，但xA C，又与A B = A C矛盾。因此有B = C。 集合的归纳定义与归

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

28、，如果 AA A 归纳定义自然数集N： l根底条款：N 。 2归纳条款：如果xN ，如此x= x xN。 3终极条款略 按照上述定义。自然数集N由如下元素组成：，或 0，0，0，0，将它们依次表示为 0，1，2，3，习题解答练习 4.31归纳定义*+l，令= a，b。解 1根底条款：*，l*2归纳条款：如果x，y*，如此xy*（3） 终极条款：除有限次使用1、2条款确定的元素外，*中没有别的元素。 2令= a,b,c，归纳定义： l L *，使L中所有字里都有字ab的出现，且所有含字 ab的字全在L中。2L*，使L中所有字里都含有字符a和b，且所有含字符a,b的字全在L中。解 1根底条款：ab

29、 L归纳条款：如果x，y L，如此xy L，yx L终极条款：除有限次使用1、2条款确定的元素外，L中没有别的元素。2根底条款：ab L，ba L归纳条款：如果x，y L，y=w1w2如此w1xw2L终极条款：除有限次使用1、2条款确定的元素外，L中没有别的元素。 3归纳定义如下集合： 1十进制无符号整数集合，非零数不得以 0为字头。 2十进制非负有穷小数。 3全体十进制有理数。4二进制形式的非负偶数， 非零数不得以0为字头解 1设I表示十进制无符号整数集合，其归纳定义如下：根底条款：0，1，2，3，4，5，6，7，8，9 I归纳条款：如果x I且x 0，yI，如此xy I 。终极条款：除有限次使用1、2条款确定的元素外，I中没有别的元素。2设R表示十进制非负有穷小数集合，其归纳定义如下：根底条款：x. x I R归纳条款：如果x R，y0，1，2，3，4，5，6，7，8，9，如此xyR终极条款：除有限次使用1、2条款确定的元素外，R中没有别的元素。3设Q表示全体十进制有理数集合，其归纳定义如下：根底条款：I Q (I为整数集)归纳条款：如果x Q且x 0，yQ，如此x/y Q终极条款：除有限次使用1、2条款确定的元素外，Q中没有别的元素。4 回忆命题公式的定义公式中括号不省略。现将公