第3章集合和关系hhs.ppt

第二部分集合论集合论溯源十六世纪末起源十九世纪德国数学家创立古典集合论1900年前后出现各种悖论1908年策莫罗建立集合论的公理系统目前集合论公理系统有两种形式:策莫罗-弗兰克尔-(ZFC)-诺伊曼-葛德尔形式(BNG)在计算机领域得到广泛应用第二部分集合论古典集合论康托称集合是“一些确定的、不同的东西的总体,这些东西,人们能够意识到,并且能够判断一个给定的东西是否属于这个总体”。悖论--理发师悖论:在一个小岛上有唯一的一位理发师。他宣称:我为岛上所有不为自己理发的人理发,而不给那些为自己理发的人理发。”。请问:理发师的头发由谁来理呢?--罗素悖论:令集合S为包含所有不以自身为元素的那些集合,即S={x|xx}请问:SS吗?ÏÏ第二部分集合论ZFC公理:包括九个公理外延公理空集公理无序对公理正则公理替换公理方幂集公理集公理无限公理选择公理外延公理:假定A和B都是集合,如果任何一个事物属于A也一定属于B,属于B也一定属于A,那么A和B是同一个集合,或称两个集合A和B相等。空集公理:存在一个不包括任何元素的集合。正则公理:任何一个非空集合A一定包含一个元素a,A的任何一个元素都不是a的元素计算机应用领域集合论是学****计算机科学必备的基础知识,计算机领域的大多数基本概念和理论都可以采用集合论的有关术语来描述和论证,集合论被广泛地应用于形式语言、编译理论、信息检索、数据结构、算法分析、程序设计、人工智能等领域。:由离散个体构成的整体称为集合,称这些个体为集合的元素常见的数集:N,Z,Q,R,C等分别表示自然数、整数、有理数、实数、----通过列出全体元素来表示集合谓词表示法----通过谓词概括集合元素的性质实例:枚举法:谓词法::元素列出的顺序无关相异性:集合的每个元素只计数一次确定性:对任何元素和集合都能确定这个元素是否为该集合的元素任意性::或者A,a:,=,⊈,,,Bx(xAxB),=BABB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的平凡子集。:ρ(A)={x|xA}实例:ρ()={},ρ({})={,{}}计数:如果|A|=n,则|ρ(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****题:P86(6):并AB={x|xAxB}交AB={x|xAxB}相对补AB={x|xAxB}对称差AB=(AB)(BA)绝对补A=EAABABA–BAB~A文氏图