离散数学 集合论.ppt

离散数学 集合论.ppt第二篇集合论
主要包括如下内容:
集合论初步
二元关系
函数
第三章集合论初步
本章主要介绍如下内容:
基本概念及集合的表示方法
集合间的关系
特殊集合
集合的运算
*包含排斥原理
3-1 基本概念

集合:是由确定的对象(客体)构成的集体。用大写的英文字母表示。
这里所谓“确定”是指:论域内任何客体,要么属于这个集合,要么不属于这个集合,是唯一确定的。
元素:集合中的对象,称之为元素。
∈:表示元素与集合的属于关系。
例如,N表示自然数集合,2∈N,
写成(∈N), 或写成 N。

列举法:将集合中的元素一一列出,写在大括号内。
例如,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。
3. 说明
⑴集合中的元素次序无关紧要,但是必须是可区分的,例如A={a,b,c,a},B={c,b,a,},则A与B相同
⑵对集合中的元素无任何限制,例如令
A={人,石头,1,B}, B={Φ,{Φ}}
⑶本书中常用的几个集合符号的约定:
自然数集N,整数集I,实数集合R,有理数集合Q
⑷集合中的元素也可以是集合,下面集合的含义不同:
如 a: 张书记
{a}: 党支部(只有一个书记)
{{a}}: 分党委(只有一个支部)
{{{a}}}: 党委(只有一个分党委)
3-2 集合间的关系
(子集) 
:A、B是集合,如果A中元素都是B中元素,则称B包含A,A包含于B,也称A是B的子集。记作AB。
文氏图表示如右下图。
A
B
例如,N是自然数集合,
R是实数集合,则NR
谓词定义:
ABx(x∈Ax∈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)