第3章集合与关系hhs.ppt

第二部分集合论
集合论溯源
十六世纪末起源
十九世纪德国数学家康托创立古典集合论
1900年前后出现各种悖论
1908年策莫罗建立集合论的公理系统
目前集合论公理系统有两种形式:
策莫罗-弗兰克尔-柯很形式(ZFC)
贝尔内斯-诺伊曼-葛德尔形式(BNG)
在计算机领域得到广泛应用
第二部分集合论
古典集合论
康托称集合是“一些确定的、不同的东西的总体,这些东西,人们能够意识到,并且能够判断一个给定的东西是否属于这个总体”。
悖论
--理发师悖论:在一个小岛上有唯一的一位理发师。他宣称:我为岛上所有不为自己理发的人理发,而不给那些为自己理发的人理发。”。
请问:理发师的头发由谁来理呢?
--罗素悖论:令集合S为包含所有不以自身为元素的那些集合,即S={x| x x}
请问:S S吗?
Ï
Ï
第二部分集合论
ZFC公理:
包括九个公理
外延公理
空集公理
无序对公理
正则公理
替换公理
方幂集公理
集公理
无限公理
选择公理
外延公理:假定A和B都是集合,如果任何一个事物属于 A也一定属于B,属于B 也一定属于A ,那么A和B是同一个集合,或称两个集合A和B相等。
空集公理:存在一个不包括任何元素的集合。
正则公理:任何一个非空集合A一定包含一个元素a,A的任何一个元素都不是 a 的元素
计算机应用领域
集合论是学****计算机科学必备的基础知识, 计算机领域的大多数基本概念和理论都可以采用集合论的有关术语来描述和论证, 集合论被广泛地应用于形式语言、编译理论、信息检索、数据结构、算法分析、程序设计、人工智能等领域。
第三章集合与关系
集合的基本概念
集合的基本运算
集合中元素的计数
笛卡尔乘积
关系的概念
关系的表示与性质
关系的运算
关系的闭包运算
相容关系与覆盖
等价关系与划分
偏序关系
集合的基本概念
1. 集合定义
集合没有精确的数学定义
理解:由离散个体构成的整体称为集合,称这些个体为集
合的元素
常见的数集:N, Z, Q, R, C 等分别表示自然数、整数、有
理数、实数、复数集合
2. 集合表示法
枚举法----通过列出全体元素来表示集合
谓词表示法----通过谓词概括集合元素的性质
实例:
枚举法:
谓词法:
集合的基本概念
3. 集合的元素具有的性质
无序性:元素列出的顺序无关
相异性:集合的每个元素只计
数一次
确定性:对任何元素和集合都
能确定这个元素是否
为该集合的元素
任意性:集合的元素也可以是
集合

隶属关系:或者

d A , a A
集合的基本概念
:, =, ⊈, , , 
A  B x ( xA  xB ),A是B的子集
A = B  A  B  B  A
A  B  A  B  A  B ,A是B的真子集
A ⊈ B x ( xA  xB )
思考:和的定义
注意和是不同层次的问题
集合的基本概念
:不含有任何元素的集合
实例: { x | xR  x2+1=0 }
空集是任何集合的子集。
证: 对于任意集合A,
A x (xxA) T (恒真命题)
推论是惟一的
一般地,称集合A的子集Ø和A为A的平凡子集。
8. 幂集: ρ(A)={ x | x  A }
实例: ρ()={}, ρ({})={,{}}
计数:如果|A|=n,则| ρ(A)|=2n.
9. 全集 E:包含了所有集合的集合
全集具有相对性:与问题有关,不存在绝对的全集
集合的基本概念
例 A= {a, b, c},求A的幂集ρ(A) 。
解: 将A的子集从小到大分类:
0元子集,即空集, Ø ;
1元子集,即单元集,{a},{b},{c};
2元子集,{a, b},{b, c},{a, c};
3元子集,{a, b, c};
集合A有ρ(A) ={ , {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}。 集合的基本运算
1 集合的运算
2 集合运算算律
集合的基本运算有:
并 AB = {x | xA  xB}
交 AB = {x | xA  xB}
相对补 AB = {x | xA  xB}
对称