第二篇 集合论主要包括如下内容：
集合论基础二元关系函数第三章 集合论基础本章主要介绍如下内容：
基本概念及集合的表示方法集合间的关系特殊集合集合的运算
＊包含排斥原理
3-1 基本概念
1.集合与元素集合是个最基本的概念。
集合,是由确定的对象 (客体 )构成的集体。用大写的英文字母表示。
这里所谓“确定”是指：论域内任何客体，
要么属于这个集合，要么不属于这个集合，是唯一确定的。
元素,集合中的对象，称之为元素。
∈,表示元素与集合的属于关系。
例如,N表示自然数集合,2∈ N，而 1.5不属于 N
写成?(1.5∈ N),或写成 1.5?N。
2,有限集合与无限集合这里对有限集合与无限集合只给出朴素的定义，以后再给出严格的形式定义。
有限集合,元素是有限个的集合。
如果 A是有限集合，用 |A|表示 A中元素个数。例如,A={1,2,3},则 |A|=3。
无限集合,元素是无限个的集合。
对无限集合的所谓‘大小’的讨论，以后再进行。
3.集合的表示方法列举法,将集合中的元素一一列出，写在大括号内。
例如,N={1,2,3,4,……} A={a,b,c,d}
描述法,用句子 (或 谓词公式 )描述元素的属性。
例如,B={x| x是偶数 }
C={x|x是实数且 2≤x≤5}
一般地,A={x|P(x)},其中 P(x)是谓词公式，如果论域内客体 a使得 P(a)为真，则
a∈ A，否则 a?A。
4,说明
⑴集合中的元素间次序是无关紧要的，但是必须是可以区分的，即是不同的。例如 A={a,b,c,a},B={c,b,a,}，
则 A与 B是一样的。
⑵对集合中的元素无任何限制，例如令
A={人，石头,1，Ｂ },B={Φ,{Φ}}
⑶ 本书中常用的几个集合符号的约定：
自然数集合 N= {1,2,3,……}
整数集合 I，实数集合 R，有理数集合 Q
⑷ 集合中的元素也可以是集合，下面的集合的含义不同：
如 a,张书记
{a},党支部 (只有一个书记 )
{{a}},分党委 (只有一个支部 )
{{{a}}},党委 (只有一个分党委 )
{{{{a}}}},市党委 (只有一个党委 )
3-2 集合间的关系一,被包含关系 (子集 )?
1.定义,A,B是集合，如果 A中元素都是
B中元素，则称 B包含 A,A包含于 B，
也称 A是 B的子集。记作 A?B。
文氏图表示如右下图。
例如,N是自然数集合，
R是实数集合，则 N?R
谓词定义,
A?Bx(x∈ A?x∈ B)
A B
2,性质,
⑴有自反性，对任何集合 A有 A?A。
⑵有传递性，对任何集合 A,B,C，有
A?B且 B?C,则 A?C。
⑶有反对称性，对任何集合 A,B，有
A?B且 B?A,则 A=B。
二,相等关系
1,定义,A,B是集合，如果它们的元素完全相同，则称 A与 B相等。记作 A=B。
定理,A=B，当且仅当 A?B且 B?A。
证明,充分性,已知 A?B且 B?A，假设 A≠B，则至少有一个元素 a,使得 a∈ A而
a?B；或者 a∈ B而 a?A。如果 a∈ A而
a?B，则与 A?B矛盾。如果 a∈ B而 a?A，
则与 B?A矛盾。所以 A=B。
必要性 显然成立，因为如果 A=B，则必有 A?B且 B?A。
谓词定义,
A=B?A?B?B?A
x(x∈ A?x∈ B)x(x∈ B?x∈ A)
x((x∈ A?x∈ B)?(x∈ B?x∈ A))
x(x∈ A?x∈ B)
2,性质
⑴有自反性，对任何集合 A，有 A=A。
⑵有传递性，对任何集合 A,B,C，如果有 A=B且 B=C,则 A=C。
⑶有对称性，对任何集合 A,B，如果有
A=B，则 B=A。
三,真被包含关系 (真子集 )?
1,定义,A,B是集合，如果 A?B且 A≠B，
则称 B真包含 A,A真包含于 B，也称 A是 B
的真子集。记作 A?B。
谓词定义,A?B?A?B?A≠B
x(x∈ A?x∈ B)x(x∈ A?x∈ B)
x(x∈ A?x∈ B)?
(x(x∈ A?x∈ B)x(x∈ B?x∈ A))
(?x(x∈ A?x∈ B)x(x∈ A?x∈ B))
(?x(x∈ A?x∈ B)x(x∈ B?x∈ A))
x(x∈ A?x∈ B)x(x∈ B?x?A)
2,性质有传递性，对任何集合 A,B,C，如果有
A?B且 B?C,则 A?C。
练习题,设 A={a,{a},{a,b},{{a,b},c}}判断下面命题的真值。
⑴ {a}∈ A ⑵?({a}? A)
⑶ c∈ A ⑷ {a}?{{a,b},c}
⑸ {{a}}?A ⑹ {a,b}∈ {{a,b},c}
⑺ {{a,b}}?A ⑻ {a,b}?{{a,b},c}
⑼ {c}?{{a,b},c} ⑽ ({c}?A)?(a∈ Φ)
3-3 特殊集合一,全集 E
定义,包含所讨论的所有集合的集合，
称之为全集，记作 E。
实际上，就是论域。
它的文氏图如右图。
由于讨论的问题不同，
全集也不同。所以全集不唯一。例如，
若讨论数，可以把实数集看成全集。
若讨论人，可以把人类看成全集。
E
由于论域内任何客体 x都属于 E，所以 x∈ E为永真式。所以需要用永真式定义 E。
E={x| P(x)∨?P(x)}
性质,对于任何集合 A，都有 A?E。
二,空集 Φ
定义,没有元素的集合，称之为空集，记作 Φ。
因为论域内如何客体 x∈ Φ是矛盾式，所以要用一个矛盾式定义 Φ。
Φ={x| P(x)∧?P(x)}
性质,
1.对于如何集合 A，都有 Φ?A。
因为?x(x∈ Φ?x∈ A)为永真式，所以 Φ?A。
2.空集是唯一的。
证明 假设有两个空集 Φ1,Φ2,则因为是 Φ1空集，则由性质 1得 Φ1?Φ2 。
因为是 Φ2空集，则由性质 1得 Φ2?Φ1 。
所以 Φ1=Φ2 。
三,集合的幂集定义,A是集合，由 A的所有子集构成的集合，称之为 A的幂集。记作 P(A)或 2A。
P(A)={B| B?A}
例如,A P(A)
Φ {Φ}
{a} {Φ,{a}}
{a,b} {Φ,{a},{b},{a,b}}
Ａ＝ {a,b,c} 则
P(A)= {Φ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}
C33C32C31C30|P(A)|＝ ＋＋＋
Cn2 ＋ ……Cn0 Cn1 Cnn＋ ＋ ＋
Cn2 ＋ …Cn0 C n1 Cnn＋ ＋ ＋xn-1y xn-2y2xn yn
Cn2 ＋ ……Cn0 Cn1 Cnn＋ ＋ ＋
性质,
1.给定有限集合 A，如果 |A|=n,则 |P(A)|=2n。
证明：因为Ａ有 n个元素，故 P(A)中元素个数为而
(x+y)n=
令 x=y=1时得
2n=
所以 |P(A)|= 2n |2A|= 2|A|= 2n
幂集元素的编码,
Ａ＝ {a,b,c} 则
P(A)= {Φ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}
A的八个子集分别表示成,B0,B1,B2,B3,B4,B5,B6,B7
再将它们的下标写成二进制形式得,B000,B001,B010,
B011,B100,B101,B110,B111,
Φ {c} {b} {b,c} {a} {a,c} {a,b} {a,b,c}
B000 B001 B010 B011 B100 B101 B110 B111
B0 B1 B2 B3 B4 B5 B6 B7
子集 Bijk编码的写法,Ａ＝ {a,b,c}
i,j,k的 确定,Bi j k?A,
如果 a∈ Bijk,则 i=1; b∈ Bijk,则 j=1; c∈ Bijk,则 k=1;否则为 0。
如Ａ＝ {a,b,c,d} 子集 B9 = B1001 ={a,d} {a,c,d}= B1011 = B11
作业 86页 (4) (7 )
练习 P86 (7) 设 A={Φ},B=P(P(A))
P(A)= {Φ,{Φ}}
在求 P(P(A))时，一些同学对集合 {Φ,{Φ}}难理解，实际上你就将 {Φ,{Φ}}中的元素分别看成
Φ=a,{Φ}=b,于是 {Φ,{Φ}}={a,b}
B=P(P(A))=P({a,b}) ={B0,B1,B2,B3 }={B00,B01,B10,B11}
={Φ,{b},{a},{a,b}}
然后再将 a,b代回即可
B=P(P(A))=P({Φ,{Φ}})={Φ,{Φ},{{Φ}},{Φ,{Φ}}}
以后熟悉后就可以直接写出。
a) Φ∈ B Φ?B
b) {Φ}∈ B {Φ}? B
c) {{Φ}}∈ B {{Φ}}?B
a),b),c)中命题均为真。
3-4 集合的运算介绍五种运算,∩∪ - ~?
一,交运算 ∩
1.定义,A,B是集合，由既属于 A，也属于 B的元素构成的集合,称之为 A与 B的交集,记作 A∩B。
例如 A={1,2,3} B={2,3,4}
A∩B={2,3}
谓词定义,
A∩B={x|x∈ A∧ x∈ B}
x∈ A∩B? x∈ A∧ x∈ B
如果 A∩B=Φ，则称 A与 B不相交。
A B
A∩B
2.性质
⑴ 幂等律 对任何集合 A，有 A∩A=A。
⑵ 交换律 对任何集合 A,B，有 A∩B=B∩A。
⑶ 结合律 对任何集合 A,B,C，有
(A∩B)∩C=A∩(B∩C)。
⑷ 同一律 对任何集合 A，有 A∩E=A。
⑸ 零律 对任何集合 A，有 A∩Φ=Φ。
⑹ A?B?A∩B=A。
前 5个公式高中都学过，下面只证明⑹。
证明,A∩B=Ax(x∈ A∩B?x∈ A)
x((x∈ A∩B? x∈ A)∧ (x∈ A? x∈ A∩B))
x((a?A∩B∨ x∈ A)∧ (x?A∨ x∈ A∩B))
x((?(x∈ A∧ x∈ B)∨ x∈ A)∧
(x?A∨ (x∈ A∧ x∈ B))
x(((x?A∨ x?B)∨ x∈ A)∧
(x?A∨ (x∈ A∧ x∈ B)))
x(T∧ (T∧ ( x?A∨ x∈ B)))
x( x?A∨ x∈ B)
x(x∈ A?x∈ B)
A?B
二,并运算 ∪
1.定义,A,B是集合，由或属于 A，或属于 B的元素构成的集合,称之为 A与 B的并集,记作 A∪ B。
例如 A={1,2,3} B={2,3,4}
A∪ B={1,2,3,4}
谓词定义,
A∪ B ={x|x∈ A∨ x∈ B}
x∈ A∪ B? x∈ A∨ x∈ B
2.性质
⑴ 幂等律 对任何集合 A，有 A∪ A=A。
⑵ 交换律 对任何集合 A,B，有 A∪ B=B∪ A。
⑶ 结合律 对任何集合 A,B,C，有
(A∪ B)∪ C=A∪ (B∪ C)。
A B
A∪ B
⑷ 同一律 对任何集合 A，有 A∪ Φ=A。
⑸ 零律 对任何集合 A，有 A∪ E =E 。
⑹ 分配律 对任何集合 A,B,C，有
A∩(B∪ C) =(A∩B)∪ (A∩C)。
A∪ (B∩C) =(A∪ B)∩(A∪ C)。
⑺ 吸收律 对任何集合 A,B，有
A∪ (A∩B)=A A∩(A∪ B) =A。
证明 A∪ (A∩B)= (A∩E)∪ (A∩B) (同一 )
= A∩(E∪ B) (分配 )
= A∩E=A (零律 ) (同一 )
⑻ A?B? A∪ B=B。
三,差运算 - (相对补集 )
1.定义,A,B是集合，由属于 A，而不属于 B的元素构成的集合,称之为 A与 B的差集,或 B对 A的相对补集，记作 A-B。
例如 A={1,2,3} B={2,3,4}
A-B={1}
谓词定义,
A-B ={x|x∈ A∧ x? B}
x∈ A-B? x∈ A∧ x?B
2.性质设 A,B,C是任意集合，则
⑴ A-Φ=A ⑵ Φ-A=Φ
⑶ A-A=Φ ⑷ A-B?A
A B
A-B
⑸ A?B? A-B=Φ
⑹ (A-B)-C=(A-C)-(B-C)
证明：任取 x∈ (A-C)-(B-C)
x∈ (A-C)∧ x?(B-C)
(x∈ A∧ x?C)∧?(x∈ B∧ x?C)
(x∈ A∧ x?C)∧ (x?B∨ x∈ C)
(x∈ A∧ x?C∧ x?B)∨
(x∈ A∧ x?C∧ x∈ C)
x∈ A∧ x?C∧ x?B
x∈ A∧ x?B∧ x?C
(x∈ A∧ x?B)∧ x?C
x∈ A-B∧ x?C?x∈ (A-B)-C
所以 (A-B)-C=(A-C)-(B-C)
⑺ A-(B∩C)=(A-B)∪ (A-C)
⑻ A-(B∪ C)=(A-B)∩(A-C)
证明：任取 x∈ A-(B∪ C)
x∈ A∧ x?(B∪ C)
x∈ A∧?(x∈ B∨ x∈ C)
x∈ A∧ (x?B∧ x?C)
(x∈ A∧ x?B)∧ (x∈ A∧ x?C )
x∈ A-B∧ x∈ A-C
x∈ (A-B)∩(A-C)
所以 A-(B∪ C)=(A-B)∩(A-C))
⑼ A∩(B-C)=(A∩B)-(A∩C)
⑽ 但 ∪ 对 - 是不可分配的，如 A∪ (A-B)=A
而 (A∪ A)-(A∪ B)=Φ
注意,这不是分配律四,绝对补集 ~
1.定义,A是集合,由不属于 A的元素构成的集合,
称之为 A的绝对补集,记作 ~A。
实际上 ~A=E-A。
例如,E={1,2,3,4}
A={2,3},~A={1,4}
谓词定义,
~A =E-A={x|x∈ E∧ x? A}
= {x|x? A}
x∈ ~A? x?A
2.性质设 A,B,C是任意集合，则
⑴ ~E=Φ ⑵ ~Φ=E ⑶ ~(~A)=A
⑷ A∩~A=Φ ⑸ A∪ ~A=E ⑹ A-B=A∩~B
A~A
E
⑺ ~(A∩B)=~A∪ ~B ⑻ ~(A∪ B)=~A∩~B
这两个公式称之为底 -摩根定律。
证明 ⑺：任取 x∈ ~(A∩B)
x∈ ~(A∩B)?x?A∩B(x∈ A∧ x∈ B)
(x?A∨ x?B)?x∈ ~A∨ x∈ ~B
x∈ ~A∪ ~B ∴ ~(A∩B)=~A∪ ~B
⑼ A?B? ~B?~A
证明,A?Bx(x∈ A?x∈ B)
x(x?B?x?A)x(x∈ ~B?x∈ ~A)
~B?~A
⑽ ~A=B 当且仅当 A∪ B=E且 A∩B=Φ
证明,A∪ B=E∧ A∩B=Φ
x(x∈ A∪ B?x∈ E)∧ (P?T=P)
x(x∈ A∩B?x∈ Φ) (P?F=?P)
x(x∈ A∪ B?T)∧?x(x∈ A∩B?F)
x(x∈ A∪ B∧?(x∈ A∩B))
x((x∈ A∨ x∈ B)∧?(x∈ A∧ x∈ B))
x((x∈ A∨ x∈ B)∧ (x?A∨ x?B))
x((x?A?x∈ B)∧ (x∈ B?x?A))
x((x∈ ~A?x∈ B)∧ (x∈ B?x∈ ~A))
x((x∈ ~A?x∈ B)
~A=B
五,对称差?
1.定义,A,B是集合,由属于 A而不属于 B，
或者属于 B而不属于 A的元素构成的集合,称之为 A与 B的对称差,记作 A?B。
例如 A={1,2,3} B={2,3,4}
A?B={1,4}
谓词定义,
A?B=(A-B)∪ (B-A)
={x|(x∈ A∧ x?B)∨ (x∈ B∧ x?A)}
A?B=(A∪ B)-(A∩B)
A B
A?B
E
2.性质
⑴ 交换律 对任何集合 A,B，有 A?B=B?A。
⑵ 结合律 对任何集合 A,B,C，有
(A?B)?C=A?(B?C)。
此式证明较繁，教材里有证明，这里从略。
⑶ 同一律 对任何集合 A，有 A?Φ=A。
⑷ 对任何集合 A，有 A?A=Φ。
⑸ ∩对?可分配 A∩(B?C)=(A∩B)?(A∩C)
证明,(A∩B)?(A∩C)
= ((A∩B)∪ (A∩C))-((A∩B)∩(A∩C))
= (A∩(B∪ C))-(A∩B∩C)
= A∩((B∪ C)-(B∩C)) (∩对 -分配 )
= A∩(B?C)
*3-5,包含排斥原理这节主要解决 集合的计数 问题。例如有 AB两个商店,A
店经营 1000种商品,B店经营 1200种商品，其中有 100种商品两个商店都经营，问两个商店共经营多少种商品？
显然 |A∪ B|=|A|+|B|-|A∩B|
如果有 ABC三个有限集合，则
|A∪ B∪ C|=|A∪ B|+|C|-|(A∪ B)∩C|
=|A|+|B|-|A∩B|+|C|-|(A∩C)∪ (B∩C)|
=|A|+|B|-|A∩B|+|C|-
(|A∩C|+|B∩C|-|A∩B∩C|)
=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|
A B
A∩BA∪ B
一般地,有 n个有限集合 A1,A2,..,An,则例 1 某个研究所有 170名职工，其中 120人会英语,80人会法语,60人会日语,50人会英语和法语,25人会英语和日语,30人会法语和日语,10人会英语、日语和法语。
问有多少人不会这三种语言？
令 U为全集,E,F,J分别为会英语、
法语和日语人的集合。 |U|=170
|E|=120 |F|=80 |J|=60 |E∩F|=50
|E∩J|=25 |F∩J|=30 |E∩F∩J|=10
|E∪ F∪ J|=|E|+|F|+|J|-|E∩F|-|E∩J|-|F∩J|+|E∩F∩J|
= 120＋ 80＋ 60－ 50－ 25－ 30＋ 10＝ 165
|U-(E∪ F∪ J)|=170-165=5 即有 5人不会这三种语言。
n
i
in
nkji
kji
nji
ji
n
i
i
n
i
i AAAAAAAA
1
1
1111
)1(...
E F
J
10
U
例 2.求 1到 1000之间不能被 5,6,8整除的数的个数。
解,设全集 E＝ {x| x是 1到 1000的整数 } |E|=1000
A5,A6,A8是 E的子集并分别表示可被 5,6,8整除的数的集合。x? 表示小于或等于 x的最大整数。
LCM(x,y):表示 x,y两个数的最小公倍数。
(Least Common Multiple )
33
30
1 0 0 0
)6,5(
1 0 0 0
|65|
1 2 5
8
1 0 0 0
||
1 6 6
6
1 0 0 0
||
2 0 0
5
1 0 0 0
||
8
6
5
L C M
AA
A
A
A
不能被 5,6,8整除的数的集合为～ (A5∪ A6∪ A8)
|~(A5∪ A6∪ A8)|=|E|－ |A5∪ A6∪ A8|=|E|－ (|A5|+|A6|+|A8|－
|A5∩A6|－ |A5∩A8|－ |A6∩A8 |+|A5∩A6∩A8|)
＝ 1000－ (200+166+125－ 33－ 25－ 41＋ 8)＝ 600
8
120
1 0 0 0 0
)8,6,5(
1 0 0 0
||
41
24
1 0 0 0
)8,6(
1 0 0 0
||
25
40
1 0 0 0
)8,5(
1 0 0 0
||
865
86
85
L C M
AAA
L C M
AA
L C M
AA
例 3.对 24名科技人员掌握外语的情况进行调查结果如下：
英、日、德、法四种外语中，每个人至少会一种；
会英、日、德、法语的人数分别是 13,5,10,9人；
同时会英、日语的有 2人；
同时会英、法语的有 4人；
同时会德、法语的有 4人；
同时会英、德语的有 4人；
会日语的人不会德语，也不会法语；
问这 24人中，只会一种外语的人各是多少人？
同时会英、法、德三种语言的人有多少人？
解,设全集为 U,E,F,G,J分别表示会英、法、德、日语人的集合。 |U|＝ 24 |E∩F|=|G∩F|=|E∩G|=4
又设 |E∩F∩G|=x 只会英、日、德、法一种外语的人分别是 y1,y2,y3,y4。 于是可以画出文氏图及方程如下：
y1 +2(4-x)+x+2=13
y2 +2(4-x)+x=9
y3 +2(4-x)+x=10
y4+2=5
y1+ y2+ y3 +y4 +3(4-x)+x+2=24
解得,y1＝ 4,y2＝ 2,y3＝ 3,y4＝ 3 x=1
EF
G
Jx4-x
4-x
4-x
2y1y2
y3 y4
作业：
第 94页⑶ d) ⑷ ⑸ b) ⑹ ⑺ c) ⑼
本章小结,
1.掌握集合间三种关系的定义、谓词定义、
证明方法。
2.掌握三个特殊集合，会求集合的幂集。
3.掌握集合的五种运算定义、计算方法、
性质。
*4.会用包含排斥原理解决集合计数问题,
习题课 (此课在以后讲 )
第 86页 (4)判断下面命题的真值：
a)如果 A∈ B,B?C,则 A∈ C。 T
证明：因为 B?C,A∈ B，所以 A∈ C。
b)如果 A∈ B,B?C，则 A?C 。 F
举反例 A={1} B={{1}} C={{1},2}
满足 A∈ B,B?C,但是不满足 A?C (1∈ A 但 1?C )。
c)如果 A?B,B∈ C，则 A∈ C。 F
举反例 A={1} B={1,2} C={{1,2}}
满足 A?B,B∈ C,但是 A?C 。
d)如果 A?B,B∈ C，则 A?C。 F
举反例 A={1} B={1,2} C={{1,2}}
满足 A?B,B∈ C,但是不满足 A?C 。
e),f) 的真值都为 F，类似举反例。
(7)设 A={Φ},B=P(P(A))
B=P(P(A))=P({Φ,{Φ}})={Φ,{Φ},{{Φ}},{Φ,{Φ}}}
a) Φ∈ B Φ?B
b) {Φ}∈ B {Φ}? B
c) {{Φ}}∈ B {{Φ}}?B
a),b),c)中命题均为真。
第 94页 (3)全集 =N={1,2,3,4,…...}
解,A={1,2,7,8} B={1,2,3,4,5,6,7}
C={3,6,9,12,15,18,21,24,27,30}
D={2,4,8,16,32,64} ~A={3,4,5,6,9,10,11,12...}
c) B-(A∪ C)
={1,2,3,4,5,6,7}-{1,2,3,6,7,8,9,12,15,18,21,24,27,30}
={4,5}
d) (~A∩B)∪ D={3,4,5,6}∪ D={2,3,4,5,6,8,16,32,64}
(4),证明 (A∩B)∪ C=A∩(B∪ C) iff C?A.
证明；充分性 已知 C?A
(A∩B)∪ C=(A∪ C)∩(B∪ C)
=A∩(B∪ C) (∵ C?A ∴ A∪ C=A)
必要性 已知 (A∩B)∪ C=A∩(B∪ C)
任取 x∈ C? x∈ (A∩B)∪ C? x∈ A∩(B∪ C)? x∈ A
所以 C?A.
(5)b)证明 (A-B)-C=(A-C)-B
方法 1.任取 x∈ (A-B)-C
x∈ (A-B)∧ x?C?(x∈ A∧ x?B)∧ x?C
(x∈ A∧ x?C)∧ x?B? x∈ (A-C)∧ x?B
x∈ (A-C)-B 所以 (A-B)-C=(A-C)-B
方法 2 (A-B)-C=(A∩~B)∩~C =(A∩~C)∩ ~B =(A-C)-B
c)课堂已讲
(6) 计算 Φ∩{Φ}=Φ {Φ}∩{Φ}= {Φ}
{Φ,{Φ}} -Φ={Φ,{Φ}} {Φ,{Φ}}-{Φ}={{Φ}}
{Φ,{Φ}}-{{Φ}}={Φ}
(7) 证明各式彼此等价。
c)A∪ B=E,~A?B,~B?A.
证明,A∪ B=Ex(x∈ A∪ B?x∈ E)
x(x∈ A∪ B) (因 x∈ E 为 T) (P?T?P)
x(x∈ A∨ x∈ B)
x(x?A?x∈ B)x(x∈ ~A?x∈ B)? ~A?B
同理 A∪ B=E?,..x(x∈ A∨ x∈ B)
x(x?B?x∈ A)x(x∈ ~B?x∈ A)? ~B?A
所以 A∪ B=E? ~A?B? ~B?A.
(9),在什么条件下，下面命题为真？
a) (A-B)∪ (A-C)=A
解,(A-B)∪ (A-C)= (A∩~B)∪ (A∩~C)=A∩(~B∪ ~C)
= A∩~(B∩C)=A-(B∩C)=A
所以满足此式的 充要条件 是,A∩B∩C= Φ
b) (A-B)∪ (A-C)=Φ
解,(A-B)∪ (A-C)= A-(B∩C)=Φ
所以满足此式的 充要条件 是,A? B∩C
c) (A-B)∩(A-C)=Φ
解,(A-B)∩(A-C)= (A∩~B)∩(A∩~C)=A∩(~B∩~C)
= A∩~(B∪ C)=A-(B∪ C)=Φ
所以满足此式的 充要条件 是,A? B∪ C
d) (A-B)?(A-C)=Φ
解,因为 当且仅当 A=B,才有 A?B=Φ
所以满足此式的 充要条件 是,A-B=A-C
补充题
1.A,B是有限集合,P(A)表示 A的幂集,已知 |A|=3,
|P(B)|=64,|P(A∪B)|=256,则 |B|=( ),
|A∩B|=( ),|A -B|=( ),|A?B|=( )。
解,
由 |P(B)|=64=26，得 |B|=6
由 |P(A∪B)|=256 ＝ 28，得 |A∪B|=8
由包含排斥原理得 |A∪ B|=|A|+|B |A∪ B|=|A|+|B－ |A∩B|
得 8＝ 3+6－ |A∩B|,所以 |A∩B|＝ 1
|A-B|=|A|－ |A∩B|=3－ 1=2
|A?B|=|A∪ B|－ |A∩B|=8－ 2=6
2.设 F表示一年级大学生的集合,S表示二年级大学生的集合,M表示数学专业学生的集合,C表示计算机专业学生的集合,D表示听离散数学课学生的集合,G表示星期六晚上参加音乐会的学生的集合,H表示星期六晚上很迟才睡觉的学生集合,则将下面各个句子所对应的集合表达式分别写在句子后面的括号内,
(1)所有计算机专业二年级的学生在学离散数学课,
( ).
(2)这些且只有这些学离散数学课的学生或者星期六晚上去听音乐会的学生在星期六晚上很晚才睡觉。
( )
(3) 星期六晚上的音乐会只有大学一、二年级的学生参加,( )
(4)除去数学专业和计算机专业以外的二年级的学生都去参加星期六晚上的音乐会,( )
C?S?D
D?G=H
G? F? S
~(M?C)?S?G
第三章 集合论到此结束
集合论基础二元关系函数第三章 集合论基础本章主要介绍如下内容：
基本概念及集合的表示方法集合间的关系特殊集合集合的运算
＊包含排斥原理
3-1 基本概念
1.集合与元素集合是个最基本的概念。
集合,是由确定的对象 (客体 )构成的集体。用大写的英文字母表示。
这里所谓“确定”是指：论域内任何客体，
要么属于这个集合，要么不属于这个集合，是唯一确定的。
元素,集合中的对象，称之为元素。
∈,表示元素与集合的属于关系。
例如,N表示自然数集合,2∈ N，而 1.5不属于 N
写成?(1.5∈ N),或写成 1.5?N。
2,有限集合与无限集合这里对有限集合与无限集合只给出朴素的定义，以后再给出严格的形式定义。
有限集合,元素是有限个的集合。
如果 A是有限集合，用 |A|表示 A中元素个数。例如,A={1,2,3},则 |A|=3。
无限集合,元素是无限个的集合。
对无限集合的所谓‘大小’的讨论，以后再进行。
3.集合的表示方法列举法,将集合中的元素一一列出，写在大括号内。
例如,N={1,2,3,4,……} A={a,b,c,d}
描述法,用句子 (或 谓词公式 )描述元素的属性。
例如,B={x| x是偶数 }
C={x|x是实数且 2≤x≤5}
一般地,A={x|P(x)},其中 P(x)是谓词公式，如果论域内客体 a使得 P(a)为真，则
a∈ A，否则 a?A。
4,说明
⑴集合中的元素间次序是无关紧要的，但是必须是可以区分的，即是不同的。例如 A={a,b,c,a},B={c,b,a,}，
则 A与 B是一样的。
⑵对集合中的元素无任何限制，例如令
A={人，石头,1，Ｂ },B={Φ,{Φ}}
⑶ 本书中常用的几个集合符号的约定：
自然数集合 N= {1,2,3,……}
整数集合 I，实数集合 R，有理数集合 Q
⑷ 集合中的元素也可以是集合，下面的集合的含义不同：
如 a,张书记
{a},党支部 (只有一个书记 )
{{a}},分党委 (只有一个支部 )
{{{a}}},党委 (只有一个分党委 )
{{{{a}}}},市党委 (只有一个党委 )
3-2 集合间的关系一,被包含关系 (子集 )?
1.定义,A,B是集合，如果 A中元素都是
B中元素，则称 B包含 A,A包含于 B，
也称 A是 B的子集。记作 A?B。
文氏图表示如右下图。
例如,N是自然数集合，
R是实数集合，则 N?R
谓词定义,
A?Bx(x∈ A?x∈ B)
A B
2,性质,
⑴有自反性，对任何集合 A有 A?A。
⑵有传递性，对任何集合 A,B,C，有
A?B且 B?C,则 A?C。
⑶有反对称性，对任何集合 A,B，有
A?B且 B?A,则 A=B。
二,相等关系
1,定义,A,B是集合，如果它们的元素完全相同，则称 A与 B相等。记作 A=B。
定理,A=B，当且仅当 A?B且 B?A。
证明,充分性,已知 A?B且 B?A，假设 A≠B，则至少有一个元素 a,使得 a∈ A而
a?B；或者 a∈ B而 a?A。如果 a∈ A而
a?B，则与 A?B矛盾。如果 a∈ B而 a?A，
则与 B?A矛盾。所以 A=B。
必要性 显然成立，因为如果 A=B，则必有 A?B且 B?A。
谓词定义,
A=B?A?B?B?A
x(x∈ A?x∈ B)x(x∈ B?x∈ A)
x((x∈ A?x∈ B)?(x∈ B?x∈ A))
x(x∈ A?x∈ B)
2,性质
⑴有自反性，对任何集合 A，有 A=A。
⑵有传递性，对任何集合 A,B,C，如果有 A=B且 B=C,则 A=C。
⑶有对称性，对任何集合 A,B，如果有
A=B，则 B=A。
三,真被包含关系 (真子集 )?
1,定义,A,B是集合，如果 A?B且 A≠B，
则称 B真包含 A,A真包含于 B，也称 A是 B
的真子集。记作 A?B。
谓词定义,A?B?A?B?A≠B
x(x∈ A?x∈ B)x(x∈ A?x∈ B)
x(x∈ A?x∈ B)?
(x(x∈ A?x∈ B)x(x∈ B?x∈ A))
(?x(x∈ A?x∈ B)x(x∈ A?x∈ B))
(?x(x∈ A?x∈ B)x(x∈ B?x∈ A))
x(x∈ A?x∈ B)x(x∈ B?x?A)
2,性质有传递性，对任何集合 A,B,C，如果有
A?B且 B?C,则 A?C。
练习题,设 A={a,{a},{a,b},{{a,b},c}}判断下面命题的真值。
⑴ {a}∈ A ⑵?({a}? A)
⑶ c∈ A ⑷ {a}?{{a,b},c}
⑸ {{a}}?A ⑹ {a,b}∈ {{a,b},c}
⑺ {{a,b}}?A ⑻ {a,b}?{{a,b},c}
⑼ {c}?{{a,b},c} ⑽ ({c}?A)?(a∈ Φ)
3-3 特殊集合一,全集 E
定义,包含所讨论的所有集合的集合，
称之为全集，记作 E。
实际上，就是论域。
它的文氏图如右图。
由于讨论的问题不同，
全集也不同。所以全集不唯一。例如，
若讨论数，可以把实数集看成全集。
若讨论人，可以把人类看成全集。
E
由于论域内任何客体 x都属于 E，所以 x∈ E为永真式。所以需要用永真式定义 E。
E={x| P(x)∨?P(x)}
性质,对于任何集合 A，都有 A?E。
二,空集 Φ
定义,没有元素的集合，称之为空集，记作 Φ。
因为论域内如何客体 x∈ Φ是矛盾式，所以要用一个矛盾式定义 Φ。
Φ={x| P(x)∧?P(x)}
性质,
1.对于如何集合 A，都有 Φ?A。
因为?x(x∈ Φ?x∈ A)为永真式，所以 Φ?A。
2.空集是唯一的。
证明 假设有两个空集 Φ1,Φ2,则因为是 Φ1空集，则由性质 1得 Φ1?Φ2 。
因为是 Φ2空集，则由性质 1得 Φ2?Φ1 。
所以 Φ1=Φ2 。
三,集合的幂集定义,A是集合，由 A的所有子集构成的集合，称之为 A的幂集。记作 P(A)或 2A。
P(A)={B| B?A}
例如,A P(A)
Φ {Φ}
{a} {Φ,{a}}
{a,b} {Φ,{a},{b},{a,b}}
Ａ＝ {a,b,c} 则
P(A)= {Φ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}
C33C32C31C30|P(A)|＝ ＋＋＋
Cn2 ＋ ……Cn0 Cn1 Cnn＋ ＋ ＋
Cn2 ＋ …Cn0 C n1 Cnn＋ ＋ ＋xn-1y xn-2y2xn yn
Cn2 ＋ ……Cn0 Cn1 Cnn＋ ＋ ＋
性质,
1.给定有限集合 A，如果 |A|=n,则 |P(A)|=2n。
证明：因为Ａ有 n个元素，故 P(A)中元素个数为而
(x+y)n=
令 x=y=1时得
2n=
所以 |P(A)|= 2n |2A|= 2|A|= 2n
幂集元素的编码,
Ａ＝ {a,b,c} 则
P(A)= {Φ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}
A的八个子集分别表示成,B0,B1,B2,B3,B4,B5,B6,B7
再将它们的下标写成二进制形式得,B000,B001,B010,
B011,B100,B101,B110,B111,
Φ {c} {b} {b,c} {a} {a,c} {a,b} {a,b,c}
B000 B001 B010 B011 B100 B101 B110 B111
B0 B1 B2 B3 B4 B5 B6 B7
子集 Bijk编码的写法,Ａ＝ {a,b,c}
i,j,k的 确定,Bi j k?A,
如果 a∈ Bijk,则 i=1; b∈ Bijk,则 j=1; c∈ Bijk,则 k=1;否则为 0。
如Ａ＝ {a,b,c,d} 子集 B9 = B1001 ={a,d} {a,c,d}= B1011 = B11
作业 86页 (4) (7 )
练习 P86 (7) 设 A={Φ},B=P(P(A))
P(A)= {Φ,{Φ}}
在求 P(P(A))时，一些同学对集合 {Φ,{Φ}}难理解，实际上你就将 {Φ,{Φ}}中的元素分别看成
Φ=a,{Φ}=b,于是 {Φ,{Φ}}={a,b}
B=P(P(A))=P({a,b}) ={B0,B1,B2,B3 }={B00,B01,B10,B11}
={Φ,{b},{a},{a,b}}
然后再将 a,b代回即可
B=P(P(A))=P({Φ,{Φ}})={Φ,{Φ},{{Φ}},{Φ,{Φ}}}
以后熟悉后就可以直接写出。
a) Φ∈ B Φ?B
b) {Φ}∈ B {Φ}? B
c) {{Φ}}∈ B {{Φ}}?B
a),b),c)中命题均为真。
3-4 集合的运算介绍五种运算,∩∪ - ~?
一,交运算 ∩
1.定义,A,B是集合，由既属于 A，也属于 B的元素构成的集合,称之为 A与 B的交集,记作 A∩B。
例如 A={1,2,3} B={2,3,4}
A∩B={2,3}
谓词定义,
A∩B={x|x∈ A∧ x∈ B}
x∈ A∩B? x∈ A∧ x∈ B
如果 A∩B=Φ，则称 A与 B不相交。
A B
A∩B
2.性质
⑴ 幂等律 对任何集合 A，有 A∩A=A。
⑵ 交换律 对任何集合 A,B，有 A∩B=B∩A。
⑶ 结合律 对任何集合 A,B,C，有
(A∩B)∩C=A∩(B∩C)。
⑷ 同一律 对任何集合 A，有 A∩E=A。
⑸ 零律 对任何集合 A，有 A∩Φ=Φ。
⑹ A?B?A∩B=A。
前 5个公式高中都学过，下面只证明⑹。
证明,A∩B=Ax(x∈ A∩B?x∈ A)
x((x∈ A∩B? x∈ A)∧ (x∈ A? x∈ A∩B))
x((a?A∩B∨ x∈ A)∧ (x?A∨ x∈ A∩B))
x((?(x∈ A∧ x∈ B)∨ x∈ A)∧
(x?A∨ (x∈ A∧ x∈ B))
x(((x?A∨ x?B)∨ x∈ A)∧
(x?A∨ (x∈ A∧ x∈ B)))
x(T∧ (T∧ ( x?A∨ x∈ B)))
x( x?A∨ x∈ B)
x(x∈ A?x∈ B)
A?B
二,并运算 ∪
1.定义,A,B是集合，由或属于 A，或属于 B的元素构成的集合,称之为 A与 B的并集,记作 A∪ B。
例如 A={1,2,3} B={2,3,4}
A∪ B={1,2,3,4}
谓词定义,
A∪ B ={x|x∈ A∨ x∈ B}
x∈ A∪ B? x∈ A∨ x∈ B
2.性质
⑴ 幂等律 对任何集合 A，有 A∪ A=A。
⑵ 交换律 对任何集合 A,B，有 A∪ B=B∪ A。
⑶ 结合律 对任何集合 A,B,C，有
(A∪ B)∪ C=A∪ (B∪ C)。
A B
A∪ B
⑷ 同一律 对任何集合 A，有 A∪ Φ=A。
⑸ 零律 对任何集合 A，有 A∪ E =E 。
⑹ 分配律 对任何集合 A,B,C，有
A∩(B∪ C) =(A∩B)∪ (A∩C)。
A∪ (B∩C) =(A∪ B)∩(A∪ C)。
⑺ 吸收律 对任何集合 A,B，有
A∪ (A∩B)=A A∩(A∪ B) =A。
证明 A∪ (A∩B)= (A∩E)∪ (A∩B) (同一 )
= A∩(E∪ B) (分配 )
= A∩E=A (零律 ) (同一 )
⑻ A?B? A∪ B=B。
三,差运算 - (相对补集 )
1.定义,A,B是集合，由属于 A，而不属于 B的元素构成的集合,称之为 A与 B的差集,或 B对 A的相对补集，记作 A-B。
例如 A={1,2,3} B={2,3,4}
A-B={1}
谓词定义,
A-B ={x|x∈ A∧ x? B}
x∈ A-B? x∈ A∧ x?B
2.性质设 A,B,C是任意集合，则
⑴ A-Φ=A ⑵ Φ-A=Φ
⑶ A-A=Φ ⑷ A-B?A
A B
A-B
⑸ A?B? A-B=Φ
⑹ (A-B)-C=(A-C)-(B-C)
证明：任取 x∈ (A-C)-(B-C)
x∈ (A-C)∧ x?(B-C)
(x∈ A∧ x?C)∧?(x∈ B∧ x?C)
(x∈ A∧ x?C)∧ (x?B∨ x∈ C)
(x∈ A∧ x?C∧ x?B)∨
(x∈ A∧ x?C∧ x∈ C)
x∈ A∧ x?C∧ x?B
x∈ A∧ x?B∧ x?C
(x∈ A∧ x?B)∧ x?C
x∈ A-B∧ x?C?x∈ (A-B)-C
所以 (A-B)-C=(A-C)-(B-C)
⑺ A-(B∩C)=(A-B)∪ (A-C)
⑻ A-(B∪ C)=(A-B)∩(A-C)
证明：任取 x∈ A-(B∪ C)
x∈ A∧ x?(B∪ C)
x∈ A∧?(x∈ B∨ x∈ C)
x∈ A∧ (x?B∧ x?C)
(x∈ A∧ x?B)∧ (x∈ A∧ x?C )
x∈ A-B∧ x∈ A-C
x∈ (A-B)∩(A-C)
所以 A-(B∪ C)=(A-B)∩(A-C))
⑼ A∩(B-C)=(A∩B)-(A∩C)
⑽ 但 ∪ 对 - 是不可分配的，如 A∪ (A-B)=A
而 (A∪ A)-(A∪ B)=Φ
注意,这不是分配律四,绝对补集 ~
1.定义,A是集合,由不属于 A的元素构成的集合,
称之为 A的绝对补集,记作 ~A。
实际上 ~A=E-A。
例如,E={1,2,3,4}
A={2,3},~A={1,4}
谓词定义,
~A =E-A={x|x∈ E∧ x? A}
= {x|x? A}
x∈ ~A? x?A
2.性质设 A,B,C是任意集合，则
⑴ ~E=Φ ⑵ ~Φ=E ⑶ ~(~A)=A
⑷ A∩~A=Φ ⑸ A∪ ~A=E ⑹ A-B=A∩~B
A~A
E
⑺ ~(A∩B)=~A∪ ~B ⑻ ~(A∪ B)=~A∩~B
这两个公式称之为底 -摩根定律。
证明 ⑺：任取 x∈ ~(A∩B)
x∈ ~(A∩B)?x?A∩B(x∈ A∧ x∈ B)
(x?A∨ x?B)?x∈ ~A∨ x∈ ~B
x∈ ~A∪ ~B ∴ ~(A∩B)=~A∪ ~B
⑼ A?B? ~B?~A
证明,A?Bx(x∈ A?x∈ B)
x(x?B?x?A)x(x∈ ~B?x∈ ~A)
~B?~A
⑽ ~A=B 当且仅当 A∪ B=E且 A∩B=Φ
证明,A∪ B=E∧ A∩B=Φ
x(x∈ A∪ B?x∈ E)∧ (P?T=P)
x(x∈ A∩B?x∈ Φ) (P?F=?P)
x(x∈ A∪ B?T)∧?x(x∈ A∩B?F)
x(x∈ A∪ B∧?(x∈ A∩B))
x((x∈ A∨ x∈ B)∧?(x∈ A∧ x∈ B))
x((x∈ A∨ x∈ B)∧ (x?A∨ x?B))
x((x?A?x∈ B)∧ (x∈ B?x?A))
x((x∈ ~A?x∈ B)∧ (x∈ B?x∈ ~A))
x((x∈ ~A?x∈ B)
~A=B
五,对称差?
1.定义,A,B是集合,由属于 A而不属于 B，
或者属于 B而不属于 A的元素构成的集合,称之为 A与 B的对称差,记作 A?B。
例如 A={1,2,3} B={2,3,4}
A?B={1,4}
谓词定义,
A?B=(A-B)∪ (B-A)
={x|(x∈ A∧ x?B)∨ (x∈ B∧ x?A)}
A?B=(A∪ B)-(A∩B)
A B
A?B
E
2.性质
⑴ 交换律 对任何集合 A,B，有 A?B=B?A。
⑵ 结合律 对任何集合 A,B,C，有
(A?B)?C=A?(B?C)。
此式证明较繁，教材里有证明，这里从略。
⑶ 同一律 对任何集合 A，有 A?Φ=A。
⑷ 对任何集合 A，有 A?A=Φ。
⑸ ∩对?可分配 A∩(B?C)=(A∩B)?(A∩C)
证明,(A∩B)?(A∩C)
= ((A∩B)∪ (A∩C))-((A∩B)∩(A∩C))
= (A∩(B∪ C))-(A∩B∩C)
= A∩((B∪ C)-(B∩C)) (∩对 -分配 )
= A∩(B?C)
*3-5,包含排斥原理这节主要解决 集合的计数 问题。例如有 AB两个商店,A
店经营 1000种商品,B店经营 1200种商品，其中有 100种商品两个商店都经营，问两个商店共经营多少种商品？
显然 |A∪ B|=|A|+|B|-|A∩B|
如果有 ABC三个有限集合，则
|A∪ B∪ C|=|A∪ B|+|C|-|(A∪ B)∩C|
=|A|+|B|-|A∩B|+|C|-|(A∩C)∪ (B∩C)|
=|A|+|B|-|A∩B|+|C|-
(|A∩C|+|B∩C|-|A∩B∩C|)
=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|
A B
A∩BA∪ B
一般地,有 n个有限集合 A1,A2,..,An,则例 1 某个研究所有 170名职工，其中 120人会英语,80人会法语,60人会日语,50人会英语和法语,25人会英语和日语,30人会法语和日语,10人会英语、日语和法语。
问有多少人不会这三种语言？
令 U为全集,E,F,J分别为会英语、
法语和日语人的集合。 |U|=170
|E|=120 |F|=80 |J|=60 |E∩F|=50
|E∩J|=25 |F∩J|=30 |E∩F∩J|=10
|E∪ F∪ J|=|E|+|F|+|J|-|E∩F|-|E∩J|-|F∩J|+|E∩F∩J|
= 120＋ 80＋ 60－ 50－ 25－ 30＋ 10＝ 165
|U-(E∪ F∪ J)|=170-165=5 即有 5人不会这三种语言。
n
i
in
nkji
kji
nji
ji
n
i
i
n
i
i AAAAAAAA
1
1
1111
)1(...
E F
J
10
U
例 2.求 1到 1000之间不能被 5,6,8整除的数的个数。
解,设全集 E＝ {x| x是 1到 1000的整数 } |E|=1000
A5,A6,A8是 E的子集并分别表示可被 5,6,8整除的数的集合。x? 表示小于或等于 x的最大整数。
LCM(x,y):表示 x,y两个数的最小公倍数。
(Least Common Multiple )
33
30
1 0 0 0
)6,5(
1 0 0 0
|65|
1 2 5
8
1 0 0 0
||
1 6 6
6
1 0 0 0
||
2 0 0
5
1 0 0 0
||
8
6
5
L C M
AA
A
A
A
不能被 5,6,8整除的数的集合为～ (A5∪ A6∪ A8)
|~(A5∪ A6∪ A8)|=|E|－ |A5∪ A6∪ A8|=|E|－ (|A5|+|A6|+|A8|－
|A5∩A6|－ |A5∩A8|－ |A6∩A8 |+|A5∩A6∩A8|)
＝ 1000－ (200+166+125－ 33－ 25－ 41＋ 8)＝ 600
8
120
1 0 0 0 0
)8,6,5(
1 0 0 0
||
41
24
1 0 0 0
)8,6(
1 0 0 0
||
25
40
1 0 0 0
)8,5(
1 0 0 0
||
865
86
85
L C M
AAA
L C M
AA
L C M
AA
例 3.对 24名科技人员掌握外语的情况进行调查结果如下：
英、日、德、法四种外语中，每个人至少会一种；
会英、日、德、法语的人数分别是 13,5,10,9人；
同时会英、日语的有 2人；
同时会英、法语的有 4人；
同时会德、法语的有 4人；
同时会英、德语的有 4人；
会日语的人不会德语，也不会法语；
问这 24人中，只会一种外语的人各是多少人？
同时会英、法、德三种语言的人有多少人？
解,设全集为 U,E,F,G,J分别表示会英、法、德、日语人的集合。 |U|＝ 24 |E∩F|=|G∩F|=|E∩G|=4
又设 |E∩F∩G|=x 只会英、日、德、法一种外语的人分别是 y1,y2,y3,y4。 于是可以画出文氏图及方程如下：
y1 +2(4-x)+x+2=13
y2 +2(4-x)+x=9
y3 +2(4-x)+x=10
y4+2=5
y1+ y2+ y3 +y4 +3(4-x)+x+2=24
解得,y1＝ 4,y2＝ 2,y3＝ 3,y4＝ 3 x=1
EF
G
Jx4-x
4-x
4-x
2y1y2
y3 y4
作业：
第 94页⑶ d) ⑷ ⑸ b) ⑹ ⑺ c) ⑼
本章小结,
1.掌握集合间三种关系的定义、谓词定义、
证明方法。
2.掌握三个特殊集合，会求集合的幂集。
3.掌握集合的五种运算定义、计算方法、
性质。
*4.会用包含排斥原理解决集合计数问题,
习题课 (此课在以后讲 )
第 86页 (4)判断下面命题的真值：
a)如果 A∈ B,B?C,则 A∈ C。 T
证明：因为 B?C,A∈ B，所以 A∈ C。
b)如果 A∈ B,B?C，则 A?C 。 F
举反例 A={1} B={{1}} C={{1},2}
满足 A∈ B,B?C,但是不满足 A?C (1∈ A 但 1?C )。
c)如果 A?B,B∈ C，则 A∈ C。 F
举反例 A={1} B={1,2} C={{1,2}}
满足 A?B,B∈ C,但是 A?C 。
d)如果 A?B,B∈ C，则 A?C。 F
举反例 A={1} B={1,2} C={{1,2}}
满足 A?B,B∈ C,但是不满足 A?C 。
e),f) 的真值都为 F，类似举反例。
(7)设 A={Φ},B=P(P(A))
B=P(P(A))=P({Φ,{Φ}})={Φ,{Φ},{{Φ}},{Φ,{Φ}}}
a) Φ∈ B Φ?B
b) {Φ}∈ B {Φ}? B
c) {{Φ}}∈ B {{Φ}}?B
a),b),c)中命题均为真。
第 94页 (3)全集 =N={1,2,3,4,…...}
解,A={1,2,7,8} B={1,2,3,4,5,6,7}
C={3,6,9,12,15,18,21,24,27,30}
D={2,4,8,16,32,64} ~A={3,4,5,6,9,10,11,12...}
c) B-(A∪ C)
={1,2,3,4,5,6,7}-{1,2,3,6,7,8,9,12,15,18,21,24,27,30}
={4,5}
d) (~A∩B)∪ D={3,4,5,6}∪ D={2,3,4,5,6,8,16,32,64}
(4),证明 (A∩B)∪ C=A∩(B∪ C) iff C?A.
证明；充分性 已知 C?A
(A∩B)∪ C=(A∪ C)∩(B∪ C)
=A∩(B∪ C) (∵ C?A ∴ A∪ C=A)
必要性 已知 (A∩B)∪ C=A∩(B∪ C)
任取 x∈ C? x∈ (A∩B)∪ C? x∈ A∩(B∪ C)? x∈ A
所以 C?A.
(5)b)证明 (A-B)-C=(A-C)-B
方法 1.任取 x∈ (A-B)-C
x∈ (A-B)∧ x?C?(x∈ A∧ x?B)∧ x?C
(x∈ A∧ x?C)∧ x?B? x∈ (A-C)∧ x?B
x∈ (A-C)-B 所以 (A-B)-C=(A-C)-B
方法 2 (A-B)-C=(A∩~B)∩~C =(A∩~C)∩ ~B =(A-C)-B
c)课堂已讲
(6) 计算 Φ∩{Φ}=Φ {Φ}∩{Φ}= {Φ}
{Φ,{Φ}} -Φ={Φ,{Φ}} {Φ,{Φ}}-{Φ}={{Φ}}
{Φ,{Φ}}-{{Φ}}={Φ}
(7) 证明各式彼此等价。
c)A∪ B=E,~A?B,~B?A.
证明,A∪ B=Ex(x∈ A∪ B?x∈ E)
x(x∈ A∪ B) (因 x∈ E 为 T) (P?T?P)
x(x∈ A∨ x∈ B)
x(x?A?x∈ B)x(x∈ ~A?x∈ B)? ~A?B
同理 A∪ B=E?,..x(x∈ A∨ x∈ B)
x(x?B?x∈ A)x(x∈ ~B?x∈ A)? ~B?A
所以 A∪ B=E? ~A?B? ~B?A.
(9),在什么条件下，下面命题为真？
a) (A-B)∪ (A-C)=A
解,(A-B)∪ (A-C)= (A∩~B)∪ (A∩~C)=A∩(~B∪ ~C)
= A∩~(B∩C)=A-(B∩C)=A
所以满足此式的 充要条件 是,A∩B∩C= Φ
b) (A-B)∪ (A-C)=Φ
解,(A-B)∪ (A-C)= A-(B∩C)=Φ
所以满足此式的 充要条件 是,A? B∩C
c) (A-B)∩(A-C)=Φ
解,(A-B)∩(A-C)= (A∩~B)∩(A∩~C)=A∩(~B∩~C)
= A∩~(B∪ C)=A-(B∪ C)=Φ
所以满足此式的 充要条件 是,A? B∪ C
d) (A-B)?(A-C)=Φ
解,因为 当且仅当 A=B,才有 A?B=Φ
所以满足此式的 充要条件 是,A-B=A-C
补充题
1.A,B是有限集合,P(A)表示 A的幂集,已知 |A|=3,
|P(B)|=64,|P(A∪B)|=256,则 |B|=( ),
|A∩B|=( ),|A -B|=( ),|A?B|=( )。
解,
由 |P(B)|=64=26，得 |B|=6
由 |P(A∪B)|=256 ＝ 28，得 |A∪B|=8
由包含排斥原理得 |A∪ B|=|A|+|B |A∪ B|=|A|+|B－ |A∩B|
得 8＝ 3+6－ |A∩B|,所以 |A∩B|＝ 1
|A-B|=|A|－ |A∩B|=3－ 1=2
|A?B|=|A∪ B|－ |A∩B|=8－ 2=6
2.设 F表示一年级大学生的集合,S表示二年级大学生的集合,M表示数学专业学生的集合,C表示计算机专业学生的集合,D表示听离散数学课学生的集合,G表示星期六晚上参加音乐会的学生的集合,H表示星期六晚上很迟才睡觉的学生集合,则将下面各个句子所对应的集合表达式分别写在句子后面的括号内,
(1)所有计算机专业二年级的学生在学离散数学课,
( ).
(2)这些且只有这些学离散数学课的学生或者星期六晚上去听音乐会的学生在星期六晚上很晚才睡觉。
( )
(3) 星期六晚上的音乐会只有大学一、二年级的学生参加,( )
(4)除去数学专业和计算机专业以外的二年级的学生都去参加星期六晚上的音乐会,( )
C?S?D
D?G=H
G? F? S
~(M?C)?S?G
第三章 集合论到此结束
