离散数学课件]PPT课件.pptx

集 合 论
第三章 集合与关系
§1集合的概念和表示法
§2集合的运算
§4序偶与笛卡尔积
§5关系及其表示
§6关系的性质
§7复合关系和逆关系
§8关系的闭包运算
§9集合的划分和覆盖
§10等价关系与等价类
§11相容关系
§12序关系
第1页/共133页
§1集合的概念和表示法
1、集合与元素
（1）集合：就是把人们直观的或想象中的某些确定的能够区分的对象汇合在一起组成的一个整体。
讨论：
①一些不同的确定的对象之全体。
例： 1000以内的素数的集合；
　　这个班里高个子学生的集合；（不是集合）
②元素（成员）：组成集合的各个对象。
③符号：用大写英文字母表示集合，用小写英文字母或其它符号表示元素。
集合：A，B….　　　　元素：a，b….
第2页/共133页
§1集合的概念和表示法
④元素与集合间的关系： 若a是集合S中的元素，则可写成a S ；若b不是集S合中的元素，则可写成b S 。
⑤集合S的基数(势)：S中的元素个数。用|S|表示。
⑥有限集合：集合的基数（元素）是有限的。
无限集合：集合的基数（元素）是无限的。
第3页/共133页
§1集合的概念和表示法
⑦本书中常用集合符:
Im(m≥1) 有限个正整数的集合{1,2,3……m}
Nm(m≥0) 有限个自然数的集合{0,1,2……m}
以上是有限集合,下面是无限集合：
N 自然数集合 {0,1,2……}
I+ 正整数集合 {1,2,3……}
I 整数集合 {……-1,0,1,2……}
P 素数集合 {大于1的正整数，只能被1和自己整除}
Q 有理数集合 {i/j. i、j均为整数且j≠0}
R 实数集合 {有理数、无理数}
C 复数集合 {a+bi，a、b可为实数}
第4页/共133页
§1集合的概念和表示法
(2)集合的表示方法:
(a)枚举法 (列举法)
把集合的元素列于花括号内。
例：
命题的真假值组成的集合：S={T,F}
自然数0,1,2,3,4五个元素的集合：P={0,1,2,3,4}
(b)谓词公式描述法
所有集合均可用谓词公式来表示：S={x | p(x) }
第5页/共133页
§1集合的概念和表示法
例：大于10的整数的集合：S1={x | x I ∧ x>10}
偶整数集合：S2={x | y (y I ∧ x=2y)}
有限个元素集合：
S3={1,2,3,4,5}={x | x I ∧ (1 ≤ x ≤ 5) }
S4={F,T}={x | x=T ∨ x=F}
S5={1,4}={ x | (x²-5x+4=0) }
(c)同一集合可以用多种不同的形式表示。
(d)集合也可作为某一集合的元素。
例：S={a,{1,2},p,{q}}
第6页/共133页
§1集合的概念和表示法
(3)三个特殊集合：空集、全集合、集合族
《定义》如果一个集合包含了所要讨论的每一个集合，则称该集合为全集合，简称全集，用E表示。
E={x | p(x) ∨  p(x)} p(x)为任何谓词公式
《定义》不拥有任何元素的集合称为空集（或称零集），用表示
={x | p(x) ∧  p(x) }={ }
注意： ≠ {} 前者是空集，是没有元素的集合；后者是以作为元素的集合。
第7页/共133页
§1集合的概念和表示法
《定义》集合中的元素均为集合，称这样的集合为集合族。
例A={{a}，{b}，{c、d}}
2、集合之间的关系
《公理》给定二个集合A和B，当且仅当A和B具有同样的元素（成员），则A和B才是相等的，记作A=B
并规定：（A=B）x (x A ↔ x B)
例：{a, b, c}={b, a, a, c, c}
第8页/共133页
§1集合的概念和表示法
例：{a,b,c}={b,c,a}
例：设P={{1,2},4}，Q={1,2,4}，则PQ
《定义》设A、B是任意二个集合，如果集合A的每一个元素都是B的一个元素，则称A 是B的子集，或者说A包含于B，或者说B包含A，记作AB，或者BA。
并规定：ABBAx(x A → x B)
第9页/共133页
§1集合的概念和表