离散数学期末复习资料 一、集合论知识点及例题整理
一、集合和集合的关系，元素和集合的关系
?是元素和集合之间的关系，而?是集合和集合之间的关系。难点在于集合有时作为某些集合的一个元素的情况，如下面的例题。
例1．1若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( )． A．{a，{a}}?A B．{2}?A
C．{a}?A D．??A 例1．2若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( )． A．A?B，且A?B B．B?A，且A?B
C．A?B，且A?B D．A?B，且A?B 例1．3若集合A={1，{2}，{1，2}}，则下列表述正确的是( )． A．{1}?A B．{2}?A
C．1?A D．2 ? A 二、幂集
1. 定义：幂集是所有子集为元素的集合。若集合A为{a,b}，它的子集有?、{a}、{b}、
{a,b}，则它的幂集为{?,{a},{b},{a,b}}，如例2.1
2. A是n元集，则幂集P(A )有2 n个元素。如在上述集合中元素个数为2，其幂集的元素
个数,22＝4，再如例2.2
例2．1设集合A＝{a，b}，那么集合A的幂集是 ． 例2．2若集合A的元素个数为10，则其幂集的元素个数为 ． 例2．3设集合A={a}，则A的幂集为( )．
A．{{a}} B．{a，{a}} C．{?，{a}} D．{?，a}
三、集合的运算
有∩、∪、－、~和?等，这个知识点的理解比较简单，一般都和后面的二元关系结合起来考。
例3．1设集合A＝{a, b, c}，B={b, d, e}，求
（1）B?A； （2）A?B； （3）A－B； （4）B?A
1
例3．2设A={{a, b}, 1, 2}，B={ a, b, {1}, 1}，试计算
（1）（A?B） （2）（A∪B） （3）（A∪B）?（A∩B）．
例3．3设A={{2},1,2}，B={1,{1,2}}，试计算
（1）（A?B）； （2）（A∩B）； （3）A×B．
四、集合运算律
如书P9，这些运算律要写在半开卷纸上，用的最多的是分配律和吸收律。主要考法有2个，一个是化简，另一个是证明，但考得最多的可能是最后一题的证明。
这两题的证明方法是差不多的，都是通过两大步，一步是证明左面包含于右面，另一步是证明右面包含于左面，所以得出左右相等。对于每一步的证明，都是在一面中的任意元素x，如果能够证到它也属于另一面，那么前者包含于后者。 例4．1 试证明集合等式A? (B?C)=(A?B) ? (A?C) ．
例4．2 试证明集合等式A? (B?C)=(A?B) ? (A?C)
五、二元关系的概念
1. 二元关系通俗的讲就是从二个集合中分别取出一个元素，构成的有序对的集合，如
例5．1；
2. 这二个集合也可以是同一个集合，这样的话，有序对的两个元素都从该集合中取。 例5．1 设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系，
R?{?x,y?x?A且y?B且x,y?A?B}，则R的有序对集合
为 。 例5．2 设集合A={1, 2, 3}，R是A上的二元关系，
则R的有序对集合为 。 例5．3设集合A={0, 1, 2}，B={1,2, 3, 4,}，R是A到B的二元关系，
R?{?x,y?x?A且y?B且x,y?A?B}
则R的有序对集合为 。
2
六、二元关系的运算
二元关系的集合运算也有并、交、补、差和对称差，如例1；二元关系还有逆运算和复合运算，注意复合运算g?f实际上是f（g），如例2
关于逆运算，如R＝<1, 1>，<1, 2>，<1, 3>}，则R＝<1, 1>，<2, 1>，<3, 1>}
例6．1 设A={0，1，2，3，4}，R={
2设集合A={1，2，3}上的函数分别为：f={<1,2>,<2,1>,<3,3>,}，g={<1,3>,<2,2>,<3,2>,}，例6．
则复合函数g?f = ．
七、二元关系的性质
这是一个非常重要的知识点，几乎是必考的。 比如有一个集合A={a,b,c}则
1. 如果包含{
3. 如果集合中有
b是集合A中任意不相等的两个元素；
4. 如果集合中有
5. 如果集合中有
说明集合具有传递性；
例题如下：
例7．1 集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={
A．自反的 B．对称的
C．传递且对称的 D．反自反且传递的
例7．2 如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（ ）个．
A．0 B．2 C．1 D．3
例7．3 若A={1,2}，R={
3
C．传递的 D．反自反
例7．5判断下列各题正误，并说明理由．
如果R1和R2是A上的自反关系，则R1?R2，R1∪R2也是自反的。
例7．6．试证明：若R与S是集合A上的对称关系，则R∩S也是集合A上的对称关系．
例7．7 对任意三个集合A, B和C，试证明：若A?B = A?C，且A??，则B = C．
例7．8 设集合A={1，2}上的关系R＝{<1, 1>,<1, 2>}，则在R中仅需加一个元素 ，就可使新得到的关系为对称的．
例7．9设集合A={1，2}上的关系R＝{<2,2>,<1,2>}，则在R中仅需加入一个元素 ，就可使新得到的关系为自反的．
八、等价关系和序关系（主要考哈斯图）
知识点：如R是集合A上的二元关系，如R是自反的、对称的和传递的，则称R是A上的等价关系；如果关系R同时具有自反性、反对称性和传递性，则称R是偏序关系。 一般考偏序关系中的哈斯图，最主要是最大元、极大元、最小元和极小元。
例8．1设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大元、最小元、上界、下界依次为 ( )．
A．8、2、8、2 B．无、2、无、2 C．6、2、6、2 D．8、1、6、1
4
