离散数学复习辅导之一
- 格式：doc
- 大小：99.00 KB
- 文档页数：5
离散数学复习辅导之一
第1章 集合及其运算
一、主要内容
1．集合的概念
集合与元素——具有确定的，可以区分的若干事物的全体称为集合，其中的事物叫元素．集合的元素不能重复出现，集合中的元素无顺序之分. 集合与其元素之间存在属于“”或不属于“”关系.
集合A中元素的个数为集合的元数，记作A．
集合的表示方法
列举法是列出集合的所有元素，并用花括号括起来．例如A= {abcd,,,}，N = {0, 1, 2,
3, „}．
描述法是将集合中元素的共同属性描述出来．例如B = {xxxR210且}，D =
{xx是正整数}．
文氏图法是用一个简单的平面区域表示一个集合，用区域内的点表示集合内的元素．
2．集合的关系
包含(子集)——若对任一Aa，都有Ba，则称B包含A(或A包含于B)，称A是B的子集，记BA；又若AB，则称A是B的真子集，记AB．
集合相等——若AB，BA，则A＝B.
注意：要正确理解元素与集合、集合与子集、子集与幂集、与()、空集与所有集合等的关系．
3．特殊集合
全集合E——在一个具体问题中，所涉及的集合都是某个集合的子集，该集合为全集．
空集——不含任何元素的集合为空集，空集是惟一的，它是任何集合的子集．
集合A的幂集P(A)——集合A的所有子集构成的集合称为A的幂集，记作
P(A)=}{Axx.
若A＝n，则P(A)=2n.
4．集合的运算
集合A和B的并AB——由集合A和B的所有元素组成的集合．
集合A和B的交AB——由集合A和B的公共元素组成的集合．
集合A的补集A——属于E但不属于集合A的元素组成的集合，记作A．补集总相对于一个全集．
集合A与B的差集A－B——由属于A，而不属于B的所有元素组成的集合..
集合A与B的对称差记作
AB＝(A－B)(B－A)，或AB＝）AB〕－（AB）
要熟练掌握运算的性质 (运算律)，即交换律、结合律、分配律、幂等律、同一律、零律、补余律、吸收律、摩根律和双补律等．
5．恒等式证明
集合运算部分有三个方面的问题：其一是进行集合的运算；其二是集合运算式的化简；其三是集合恒等式的推理证明.
集合恒等式的证明方法通常有二：
(1) 要证明A＝B，只需要证明AB，又AB；
(2) 通过运算律进行等式推导．
6．有限集合的计数方法
首先根据已知条件把对应的文氏图画出来，然后将已知集合的元素填入表示该集合的区域内．通常从几个集合的交集填起，根据计算结果将数字逐步填入所有的空白区域内．如果交集的数字是未知的，可以将其设为x，再根据已知条件列出方程或方程组，解出未知数x．
也可以用容斥定理计算有限集合的元素个数．
定理1.2.2（容斥定理） 对任意两个有限集合A和B，有
AB= A+B- AB
其中A，B分别表示A，B的元素个数．
定理1.2.2的推广结论：对于任意三个有限集合A, B, C，有
ABC = A+B+C-AB-AC-BC+ABC
二、实例
例1 已知S＝{2, a, {3}, 4}，R={{a}, 3, 4, 1}，判断下列各题是否正确：.
(1) {a}S; (2) {a}R;
(3) {a, 4, {3}}S; (4) {{a}, 1, 3, 4}R;
(5) R=S; (6) {a}S
(7) {a}R (8) R
(9) {{a}}R (10) {}S
(11) R (12) {{3}, 4}
解 集合S有四个元素：2，a，{3}，4，而元素{3}又是集合；集合R类似．
(1) 错．因为{a}是单元素的集合，{a}不是集合S的元素，所以“{a}S”是错的．
(2) 对．因为{a}是R的元素，所以“{a}R”是正确的．
(3) 对．因为a, 4, {3}都是S的元素，以此为元素构成的集合是S的子集．所以“{a,4,{3}}S”是正确的．
(4) 对．因为{a}, 1, 3, 4都是R的元素，以此为元素构成的集合是R的子集，所以“{{a},1,3,4}R”是正确的．
(5) 错．因为元素2S，但2R，所以S R．
(6),，和题号的命题真值为1；而, ,题号命题真值为0．
(7) 错．因为{a}是集合R的元素，元素与集合之间不能用“”，正确的表示为：{a}R．
(8) 对．因为空集是任意集合的子集。
(9) 对．因为是集合{{a}}的子集，{{a}}是集合R的子集，所以{{a}}R是正确的。
(10) 错．因为不是集合S的元素，所以由空集构成的集合不是S的子集，即{}S是错的． (11) 错．因为不是集合R的元素，所以R是错的．
(12) 对．因为空集是任意集合的子集。
例2 写出下列集合的子集：
(1) A={a，{b}，c}； (2) B={}；
(3) C=
解 (1) 因为是任何集合的子集，所以是集合A的子集；
由A的任何一个元素构成的集合，都是A的子集，所以{a}，{{b}}，{c}是A的子集；
由A的任何两个元素构成的集合，也是A的子集，即{a，{b}}，{{b},{c}}，{a, c}；
同理，A的三个元素构成的集合，也是A的子集，于是集合A的所有子集为：
，{a}，{{b}}，{c}，{a，{b}}，{{b},c}，{a, c}，{a，{b}，c}
(2) 分析同(1)，B的子集有：，{}。
(3) 因为是任何集合的子集，故也是C的子集。因为C中没有元素，因此C就没有其它子集，所以C的子集只有：
说明：
(1) 在第1小题中，以集合A的8个子集为元素的集合，就是集合A的幂集，即
P(A)={ ，{a}，{{b}}，{c}，{a，{b}}，{{b},c}，{a, c}，{a，{b}，c}}
集合B的幂集为；P(B)={,{}}；集合C的幂集：P(C)={}
一般地，如果集合A的元素个数为,nA那么P(A)有2n个元素，即P(A)=2n．
(2) 根据真子集的定义，对于任何集合A，除了集合A本身不是A的真子集外，其它子集均是A的真子集. 于是本例
集合A有7个真子集：，{a}，{{b}}，{c}，{a，{b}}，{{b},c}，{a, c}
集合B只有1个真子集：
集合C没有真子集。
例3 判断下列哪些运算结果是对的？哪些是错的？请将错误的运算结果更正过来．
(1) }{； (2) }{；
(3) }{}}{,{}{； (4) }}{,{}{}}{,{；
(5) ABBA)(； (6) ABBA)(；
(7) AAA； (8) ABA)(.
解 (1) 对．
(2) 错．应为}{．
(3) 对．
(4) 错．应为{}{}.
(5) 错．应为BA.
(6) 错．应为BA(或BA~或A－AB).
(7) 错．应为，即AAAAAA. (8) 对．
例4 设集合A={a, b, c, d, e}，B={b, d, e}，C={a, b, d}，求(A－B)(BC)
解 (A－B)(BC)
＝（{a, b, c, d, e}－{b, d, e}） ({b, d, e}{a, b, d})
={a, c} {a, b, d, e}
={a, b, c, d, e}－{a}
={b, c, d, e}
例5 设A，B，C为三集合，证明：CBCA且的充分必要条件是CBA)(．
证明：必要性．因为CBCA且，所以
CCBACBA)()(
＝)()(CBCA
＝CCC
所以，CBA
充分性．因为CBA)(，所以
CABAAA)(，故CA
同理，CBBABB)(．故CB．
例6 某所大学计算机专业的80名学生在期末考试中，Pascal语言课有58人达到优秀，数据结构课有30人达到优秀，离散数学课有25人达到优秀．并且，Pascal语言和数据结构两门课都达到的有20人，Pascal语言和离散数学两门课都达到的有19人，数据结构和离散数学两门课都达到的有17人．还有10人一门优秀都没得到．如果获得3门优秀者可得奖学金200元，获得2门优秀者可得奖学金100元，那么计算机系应为本专业学生发奖学金多少元？
解 设期末考试中Pascal语言课、数据结构课、离散数学课达到优秀的学生集合分别为A , B , C，那么
A = 58，B= 30，C= 25，
AB= 20，AC= 19，BC= 17
而1门课都没达到优秀的学生)(~CBA= 10，即至少有1门课达到优秀的学生CBA= 80-)(~CBA= 70．
那么，由定理1.2.2的推广结论，得3门课都达到优秀的学生数为：
CBA=CBA- (A+B+C-AB-AC-BC)
=70 -58 -30 -25 +20 +19 +17= 13
所以，计算机系应为本专业学生发奖学金： 13200 +（20-13）100 +（19-13）100 +（17-13）100 = 4300（元）
三、练习题
1．设S，T，M为任意集合，判定下列各题是否正确：
(1) 是的子集； (2)如果ST＝SM，则T＝M；
(3) 如果S－T＝ ，则S＝T； (4)如果ST＝E，则ST；
(5) SS=S
2．用列举法表示以下集合：
(1) }7{2xNxxA； (2) }33{xNxxA；
(3) }0)1({2xRxxA．
3．设A，B为任意集合，试证明BAABBA
4．化简集合表达式))~)((())())(((ABBABCBBA
四、练习题答案
1．(1)，(4)正确，其余错误.
2．(1) A={0, 1, 2}；(2) A={1, 2, 3, 4, 5}； (3) A={－1}
3．当A＝B时，必有A－B＝B－A；
反之，由A－B＝B－A，得到：BABBBA)()(
化简后得到AB，即AB；
同理，由A－B＝B－A，得到：AABABA)()(
化简后得到BA，即BA.
所以A＝B．
