前言
本书是根据教育部高等学校教学指导委员会编制的离散数学课程教学的基本要求，为帮助计算机及相关专业的本、专科生更好地掌握离散数学知识点、完成课后习题而编写，是与教材《离散数学》（书号为9787302421672，由张小峰等编著）相配套的知识解析与习题指导教材。本书根据离散数学课程教学的基本要求，对知识点进行解析，全书分为两个部分： 第一部分是与教材相对应的12章知识点解析与课后习题解答，每章都分别从学习要求、重要知识点、总结和习题解答4个方面进行描述，帮助学生掌握离散数学的知识点以及学习技巧。第二部分是模拟题部分，共包含6套模拟题与参考答案。每套模拟题难易程度适中，涵盖了离散数学的重要知识点，帮助学生了解对知识的掌握程度。本书具有以下特点。（1） 以基本知识为主线，对知识点进行对比、分析和归纳，帮助学生理解和掌握。（2） 注重学生逻辑思维能力和解题方法的培养。（3） 模拟题经过了实际考试的检验，知识点较为全面，难易程度适中，可以有效检验学生的掌握程度。本书具体编写分工如下： 第1章、第2章、第5章和第6章由张小峰编写，第8章由杨洪勇编写，第12章由赵永升编写，其余章节和内容由李秀芳编写，全书的策划和定稿工作由李秀芳负责。在本书的规划和写作过程中，山东大学张彩明教授、西安电子科技大学李兴华教授、鲁东大学邹海林教授等对书稿进行了审阅，提出了许多建设性的建议，在此深表感谢。在本书的编写过程中，作者参考了多种版本的离散数学、习题解答相关的教材和辅导书以及网站资料，从中受益匪浅，在此一并向有关作者致谢。由于作者水平有限，本书在内容的取舍、题目选取以及模拟题设计等方面难免存在不足之处，敬请专家、同行和读者批评指正。作者联系方式： ytlxf@126.com。
作者2017年1月于鲁东大学
第5章集合论基础〖1〗5.1学习要求本章内容主要包括集合的概念与表示、集合之间的关系、集合运算、容斥原理等，重点要求掌握以下内容。（1） 理解集合的4种特性，掌握集合的两种表示方法： 枚举法和特性刻画法。（2） 熟练掌握集合间的3种关系。（3） 熟练掌握3种基本集合运算，理解差运算、幂运算及笛卡儿积。（4） 掌握序偶、有序ｎ元组、笛卡儿积的概念和性质。（5） 理解并掌握容斥原理，能够利用容斥原理进行求解。5.2重要知识点〖45〗1. 集合的概念与表示把具有某种性质的个体汇集在一起，形成一个集合（set）。在集合中，个体通常被称为元素（element）或成员。一般情况下，用大写字母A、B、C、、A1、B1、C1、表示集合，而集合中的元素通常用小写字母a、b、c、、a1、b1、c1、表示。如果元素a是集合A中的元素，记为aA，读作a属于A；如果元素a不是集合A中的元素，记为aA，读作a不属于A。集合有两种表示方法： 列举法和描述法。1 列举法： 当一个集合中元素的个数是有限时，通常将集合中的所有元素列举出方法称为列举法，又称为枚举法。2 描述法： 通常通过刻画集合中元素具备的性质来表示集合，这种方法称为描述法。一般地，用谓词Px表示x具备的性质，用{x|Px}表示具有性质P的全体元素构成的集合。2. 集合之间的关系（1） 包含关系。设A、B是两个集合，如果集合A中的每一个元素都是集合B中的元素，称集合A是集合B的子集（subset），记作AB或BA，如果A不是B的子集，记作AB。形式化表示如下：ABxxAxBABxxAxB（2） 相等关系。设A、B是两个集合，如果A是B的子集，同时B也是A的子集，称两集合相等,即A=BABBA如果集合A和B不相等，记为AB，即ABABBA（3） 真包含关系。如果集合A是集合B的子集，并且AB，则称集合A是集合B的真子集（proper subset），记为AB，即ABABAB。3. 集合运算设A、B为两个集合，则（1） 由A和B的全体元素构成的集合称为A和B的并集（union），记为AB，即AB={x|xAxB}（2） 由A和B的公共元素构成的集合称为A和B的交集（intersection），记为AB，即AB={x|xAxB}（3） 由属于集合A但不属于集合B的元素构成的集合称为A和B的差集（difference），记为A-B，即A-B={x|xAxB}（4） 由属于集合A但不属于集合B，或者属于集合B而不属于集合A的元素构成的集合，称为集合A和B的对称差（symmetric difference），记为AB，即AB={x|xAxBxAxB}（5） 设U为全集，对任意AU，称U-A为集合A的补集（complement），记为，即={x|xUxA}上述集合之间的运算可以用韦恩图（Venn diagram）直观地表示，韦恩图是用封闭曲线表示集合及其关系的图形，其构造方式如下： 用一个矩形内部的点代表全集U，用矩形内部的圆或者其他封闭曲线的内部表示U的子集，用阴影区域表示集合之间运算结果构造的新的集合。（6） 设A是一个集合，由A的所有子集组成的集合称为A的幂集（power set），记为A或2A，即A={B|BA}设全集为U，A、B为U的子集，根据集合的运算，可以得到有关运算的许多性质，则有如下恒等式成立。（1） 交换律： AB=BA，AB=BA。（2） 结合律： ABC=ABC，ABC=ABC。（3） 分配律： ABC=ABAC，ABC=ABAC。（4） 吸收律： AAB=A，AAB=A。（5） 幂等律： AA=A，AA=A。（6） 德摩根律： AB=AB，AB=AB。（7） 矛盾律： AA=。（8） 排中律： AA=U。（9） 零律： AB=U，A=。（10） 同一律： A=A，AU=A。（11） 双重否定律： A=A。4. 序偶与笛卡儿积（1） 序偶。设有两个元素x、y，二者按照一定的顺序组成的二元组称为序偶，记为，其中x称为序偶的第一元素，y称为序偶的第二元素。设有n个元素a1、a2、、an，它们按照一定的顺序组成的n元组称为n元有序组，记为。同样，两个n元有序组和相等，当且仅当ai=bi，其中1in。（2） 笛卡儿积。设A、B为两任意集合，以集合A中的元素为第一元素，集合B中的元素为第二元素组成序偶，所有这样的序偶构成的集合，称为A与B的笛卡儿积，记为AB，符号化表示为AB={|aA,bB}。笛卡儿积运算具有以下性质。（1） 笛卡儿积不满足交换律，即： 如果AB，则ABBA。（2） 笛卡儿积不满足结合律，即： 如果集合A、B、C为非空集合，则（AB）CA（BC）（3） 笛卡儿积对集合的交运算和并运算满足分配律，即A（BC）=AB（AC）A（BC）=AB（AC）（BC）A＝BA（CA）（BC）A＝BA（CA）5. 容斥原理容斥，指在计算某类物的数目时，要排斥那些不应包含在这个数目中的数目，但同时要包容那些被错误排斥了的数目作为补偿。这种原理称为容斥原理，又称为包含排斥原理。设A、B为任意有限集合，则有|AB|=|A| |B|-|AB|；设A1、A2、、An是任意n个集合，则有|A1A2An－1|=|A1| |A2| |An|－|A1A2|－－|An－1An| -13-1|AiAjAk| －1n-1|A1A2An|5.3总结本章内容主要包括集合的定义与表示、集合的基数、元素与集合的关系、集合与集合之间的关系、集合的运算以及运算律的证明、容斥原理及其应用，其中集合包含与相等关系的证明、幂集和笛卡儿积计算以及容斥原理是学习的重点和难点。围绕上述知识点，相关习题主要有以下几种类型。（1） 基本概念题： 主要考查集合的正确表示，可以用枚举法列举集合中的元素。（2） 判断题： 主要考查集合包含或相等关系的判断；对于给定的运算等式，两边同时添加或去掉相同的集合，判断等式是否成立等。（3） 计算题： 主要考查集合的并、交、差、幂集以及笛卡儿积运算、容斥原理的应用等。（4） 证明题： 主要考查两个集合包含关系和相等关系的证明。针对以上知识点和习题类型，在求解过程中需要注意以下几点。（1） 集合的正确表示通常是将集合的一种表示方法转化成另一种表示方法，或者对自然语言描述的集合采用规范的描述法或者枚举法表示。因此，明确集合的各种表示方法是关键。（2） 对给定的包含关系或属于关系的判断，最直接的方法是根据定义判断。对于给定的运算等式，两边同时添加或去掉相同的集合，判断等式成立可以按照定义直接证明；如果判断等式不成立，可以通过列举反例的方法。（3） 集合的基本运算可以按照定义直接计算。在计算幂集时可以按照0元子集、1元子集、2元子集的顺序计算，避免遗漏某些子集。4 证明两个集合之间的包含或相等关系，可以根据集合包含关系或相等关系的定义进行证明。例如，证明AB，则需要证明对于任意的xA，都有xB。如果证明A=B，则需要证明A、B两个集合互为子集，即证明AB和BA同时成立。除此之外，还可以利用集合的运算定律证明集合相等。（5） 容斥原理是先包容、后排斥，是排除法的公式化表示。5.4习题解答1. 用枚举法表示下列集合。（1） A＝{aN,a|12}。（2） 20以内的素数构成的集合。（3） B={xZ|x2-3x 2=0}。（4） C={|a,bN,a b=5}。解：1 A={1,2,3,4,6,12}。2 A={2,3,5,7,11,13,17,19}。3 B={1,2}。4 C={,,,，,}。2. 判断下列各式的正确性。（1） {,{}}。（2） {,{}}。（3） {}{,{}}。（4） {}{,{}}。解：（1） 空集作为集合的元素，所以式子正确。（2） 因为空集是任何集合的子集，所以式子正确。（3） {}是集合中的元素，所以式子正确。（4） 因为是集合中的元素，所以{}是集合的子集，即式子正确。3. 已知 U={1,2,3,4,5,6}， A={1,4}， B={1,2,6}， C={3,4,5}，求：1 A。2 AB。3 。4 AB。5 AB-C。6 B-A。1 A={1,4}{3,4,5}={4}。2 AB={1,4}{1,2,6}{1,2,3}={1}{1,2,3}={1,2,3}。3 ={2,3,5,6}{3,4,5}={2,3,4,5,6}。4 AB={1,4}{1,2,6}={1}={2,3,4,5,6}。5 AB－C={1,4}{1,2,6}－{3,4,5}={1,2,4,6}－{3,4,5}={1,2,6}。6 B－A={{2},{6},{1,2},{1,6},{2,6},{1,2,6}}。4. 证明下列各式：1 A－B=－。证明： 本质是证明两个集合相等，因此需要证明等式两边互为子集。xA－B，有xA,xB 。因此有 x,x，即 x－ 。因此 A－B－ 。反之， x－，有 x,x，因此 xA,xB，即 xA－B 。因此 －A－B 。综合上述两点，有 A－B=－ 。2 A－B－C=A－BAC。证明： 运用集合运算的相关性质证明。A－B－C=A－BC=ABC=ABC=ABAC=A－BAC3 A－BC=A－BA－C 。证明： 运用集合运算的相关性质证明。A－BC=ABC=ABC=ABAC=A－BA－C5. 求下列集合的幂集：1 A={a,b,c}。A={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}2 B={a,{a}}。B={,{a},{{a}},{a,{a}}}3 {a}。{a}={,{{a}}}{a}={,{},{{{a}}},{,{{a}}}}4 C={,}。C={,{},{},{,}}6. 画出下列集合的韦恩图。（1） 。（2） A-B。解： 集合的韦恩图如图5.1和图5.2所示。图5.1图5.2A-B=AC
7. 已知A={a,b,c}，计算AA。解：A={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}AA={,,,,,,,,,,,,,,,,,,,,,,,}8. 已知A、B为任意集合，证明：1 AB=AB。分析： 要证明上述等式成立，因等式两边仍为集合，则可以按照集合相等的证明方法进行证明，即证明等式两边互为子集。证明：① 证明ABAB。CAB，有CA，CB，即CA且CB。因此CAB，即CAB。因此有ABAB。② 证明ABAB。CAB，有CAB，即CA且CB，因此有CA，CB，即CAB。因此有ABAB。2 ABAB。证明同1题中的第①步。9. 某班有25名学生，其中14人会打篮球，12人会打排球，6人会打排球和篮球，5人会打篮球和网球，还有2人会打这3种球。已知6个会打网球的人都会打排球。求不会打球的同学人数。解：设集合A表示会打篮球的同学组成的集合，B表示会打排球的同学组成的集合，C表示会打网球的同学组成的集合。根据题意，有|A|=14，|B|=12，|C|=6，|AB|=6，|AC|=5，|BC|=6，|ABC|=2。根据容斥原理，有|ABC|=14 12 6－6－5－6 2=17因此不会打球的同学人数有25-17=8。10. 计算1000以内素数的个数并编程实现。#include int main{int num\[1001\];int i,j;int count=0;fori=0;i
|
購物車/收銀台(0) | 在線留言板
| 付款方式
| 聯絡我們
| 運費計算
| 幫助中心 |
加入書簽
HOME
新書上架
