《离散数学王元元习题解答 (5)》由会员分享，可在线阅读，更多相关《离散数学王元元习题解答 (5)（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= 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假如
