集合代数课件

1、1,目 录 序言 第一章 集合 第二章 关系 第三章 函数 第四章 代数系统 第五章 格与布尔系统 第六章 图论,2,离散的数学结构 Discrete Mathematic Structures,离散数学简介。 内容：集合论、代数系统、布尔代数、图论、数理逻辑。 离散数学具有抽象性、非线性、非寻绎性、构造性、结构性、整体性等结构性数学特点。 方法和手段 证明方法：包括（数学）归纳法、演绎法、反证法、归谬法、二难法、二分法、枚举法（穷举法）、相容排斥法等方法，特别着重于存在性、结构性、构造性方法，以及各部分内容自己所特有的方法。,3,第一章 集合 (set) .集合理论中的一些基本概念 个体与集合之间的关系 集合的表示法 集合与集合之间的关系 幂集 2 .集合代数 集合的基本运算 集合的补运算 集合的交运算和并运算 集合的宏运算,4,第一章 集合 (set) .集合理论中的一些基本概念 1.凡具有某种特殊性质的对象的汇集称之为集。 莫斯科大学的那汤松教授 2. 凡可供吾人思维的，不论它有形或无形，都叫做物。 具有某种条件的物，称它们的全部谓之一集。 复旦大学的陈建功教授 3.集就是“乌合

2、之众”。不考虑怎样“乌合”起来的，众可以具体，可以抽象。 南开大学的杨宗磐教授 任意性：组成集合的元素任意； 构成的法则任意； 什么都可以构成集合，不加任何限制。,5,4. 集合是由总括某些个体成一个整体而成的。对于每个个体，只设其为可思考的对象，辨别它的异同。个体之间并不需要有任何关系。 集合论之父G.Cantor（1845-1918） 事实： (a)承认集合的存在性。即，接受集合概念； (b)承认集合是由一些个体（对象）组成的。这些个 体称为该集合的成员或元素（member,element）； (c )承认个体是可辩认的。即，一个个体要么是一 个集合的成员，要么不是；二者必居其一，也只居其 一。 确定性：确定性是说集合确定； 个体确定； 集合与个体之间的关系确定。,6,集合的概念： 1. 个体（元素） 2. 个体的可辨认性 3. 集合（动词，汇到一块） 通常用小写拉丁字母表示个体：a、b、c、d、 通常用大写拉丁字母表示集合：A、B、C、D、 有时还用德文花写字母表示集合：, 关于个体的辨认有赖于各方面公认的知识。 一.个体与集合之间的关系： 个体与集合之间的关系称为属于关系。 对

3、于某个个体 a 和某个集合 A 而言， 只有两种可能：,7,(1)a 属于（belong to） A，记为 aA（记号 是希腊字i的第一个字母，意思是“是”。由意大利数学家G.Peano首先采用），同时称 a 是 A 的元素或A 的成员。 (2)a 不属于 A，记为 aA或a A ，称 a 不是 A 的元素或a 不是 A 的成员。 判断个体 a 属于 A 还是不属于 A ，必须使用个体的可辨认性。,8,二.集合的表示法（用花括号 表示集合）： (1)文字表示法：用文字表示集合的元素，两端加上花括号。 比较粗放。比较适合在对集合中的元素了解甚少、不详，难以用精确的数学语言来刻划时使用。 (2)元素列举法（罗列法）：将集合中的元素逐一列出，两端加上花括号。 比较适合集合中的元素有限（较少或有规律），无限（离散而有规律）的情况。 (3)谓词表示法： x:P(x) 或者 xP(x) 其中：P表示 x 所满足的性质（一元谓词）。 比较适合在对集合中的元素性质了解甚详，且易于用精确的数学语言来刻划时使用。,9,外延(extension) ：集合 x:P(x) 称为性质谓词P(x) 的外延； 内涵(

4、intension,connotation)：性质谓词P(x) 称为集合 x:P(x) 的内涵； 采用谓词法定义集合，关键是要得出内涵P(x) ，并且显然有如下的： 概括原理：集合 x:P(x) 恰由那些满足性质谓词P(x) 的元素组成。即 x x:P(x) （当且仅当） P(x)真 。,10,悖论(paradox)： 所谓悖论是指这样一个所谓的命题P，由P真立即推出P假；由P假立即推出P真；即 P真P假 。 理发师悖论： 某偏远小山村仅有一位理发师。这位理发师规定： 他只给那些不给自己刮脸的人刮脸。 那么要问：这位理发师的脸由谁来刮？ 如果他给自己刮脸，那么，按他的规定，他不应该 给自己刮脸； 如果他不给自己刮脸，那么，按他的规定，他应该 给自己刮脸；,11,罗素悖论(Russell paradox(1902)： 罗素1902年在集合论中也发现了如下的悖论。他 构造了这样一个集合 S= x:xx 然后他提出问题： SS ？ 如果SS ，那么，按罗素给S的定义，则应有 S S ； 如果S S ，那么，按罗素给S的定义，则应有SS ； 罗素悖论的发现，几乎毁灭集合论，动摇数学的 基础，倾

5、危数学的大厦。直接引发了数学的第三次危 机。,12,为了解决集合论中的悖论问题，人们产生了类型论和形式化公理化集合论(ZF和ZFC公理系统)，以求排除集合论中的悖论。 近年来，基于ZFC公理系统和一阶逻辑(谓词逻辑) ，人们提出了抽象的计算机程序设计语言_Z语言。 在公理化集合论中，人们引进了类(class)的概念。 本章 所讲解的集合论是朴素（naive）集合论；所讨论的集合一般也不会产生悖论。,13,三.集合的名字： (1)大写的拉丁字母：例如A、B； (2)小写的希腊字母：例如、； (3)花写的徳文字母：例如, ； 不够用时可以加下标。 同一个集合可以有几个名字。 四.集合的相等（equality） ： 外延性原理： 两个集合相等，当且仅当，它们的成员完全相同。 即 A=B x(xA xB) ； 两个集合不相等，记为AB 。,14,无序性：集合中的元素是无序的。 因此，为了使用方便， 可任意书写集合中元素的 顺序。但一般情况下，通常采用字母序、字典序；有 时，还需要强行命名一种序。 (2) 无重复性：集合中元素的重复是无意义的。 包（bag）：若允许元素重复称为包。 集合的性质：

6、 任意性、确定性、无序性、无重复性。,15,五.空集（empty,null,void set）：记为 空集是没有成员的集合。即 x(x）（空集公理）； 所以= ； 空集是集合（作这点规定是运算封闭性的要求）。 空集是唯一的。因为若有两个空集，则它们有完全相同的元素（都没有任何元素），所以它们相等，是同一集合。 六.全集（universe of discourse）：记为X 全集是所要研究的问题所需的全部对象（元素） 所构成的集合。 全集给个体（研究的对象）划定适当的范围。,16,七.单元素集合（singleton set）： 只含一个元素的集合称为单元素集。 例如 a ； 张三 ； 左边是空集；右边不是空集，而是单元素集合，有一个成员 ；这说明：差别在于级别。即，右边的集合级别高。 单元素集合是构造复杂集合的原子。,17,八.子集（subset）： 对于两个集合A，B，若A中的每个元素x都是B 的 一个元素，则称A包含在B中（或者B包含A ），记为 AB。同时称A是B的子集（称B是A 的超集(superset)）。即 AB x(xA xB) 。 真子集（proper subset）：

7、称A是B的真子集或者A真包含在B中（或者B真包含A ），记为AB。即 AB ABAB。,18,子集的两种特殊情况（平凡子集）： (1)空集（见下面定理2）； (2)每个集合自己（见下面定理1的(1)）； 九.集合与集合之间的关系: 集合与集合之间的关系： (1)B包含A， AB x(xA xB) ； (2)A包含B， BA x(xB xA)； (3)A等于B， A=B x(xB xA) ABBA ； (4)A与B互不包含， (AB)(BA) x(xAxB)y(yByA) ；,19,定理1.设A,B,C为任意三个集合。那么 (1) 自反性： A A (每个集合是它自己的子集) ； (2) 反对称性：AB BA A=B ； (3) 传递性： AB BC AC ； 证明.（采用逻辑法） (1) x(xA xA) (同一律： pp ) AA 所以包含关系是自反的； (2)ABBA x(xA xB)x(xB xA) x(xA xB)(xB xA) (量词对 的分配律： xA(x)xB(x)x(A(x)B(x) ) x(xAxB) A=B 所以包含关系是反对称的；,20,(3)ABBC x(xA

8、xB)x(xB xC) x(xA xB) (xB xC) (量词对 的分配律：xA(x)xB(x)x(A(x)B(x) ) x(xA xC) ( (假言) 三段论原则：(pq)(q r) p r ) AC 所以包含关系是传递的。,21,定理2.空集是任一集合的子集。即 A 。 证明.(采用逻辑法) x(x） (空集的定义) x (x) x(xxA) (由析取构成式及联结词归约有： p( p q)(pq) A 。,22,十.幂集(power set)： 定义1.幂集 一个集合A的所有子集构成的集合称为A的幂集。记为 2A(或P(A) ) ，即 2A = B ：B A 。 A的两个平凡子集 和A 都属于A的幂集。即 2A ，A 2A 。 例1. 若A=1,2,3，则 2A =,1,2,3, 1,2, 1,3, 2,3, 1,2,3。 注：(1) 包含关系两边必须是集合，并且这两个集合的级别（广义上）相同； (2)属于关系左边是元素（广义上） ，右边是集合，两边级别差一级。,23,定义2.基数 一个有穷集合（有限集合元素个数有限的集 合）A中元素的个数称为A的基数。记为 |A|(或A，)。 基数的性质： (1)齐性： |=0 ； (2)非负性： |A|0 （对任何集合A ）； 定理3. 若A是有限集合， 则有 | 2A |= 2 |A| 。 证明.由于集合A有限，故可设 A=a1，a2，an，于是 | A |=n。A的子集按其基数大小可分为0，1，2，n共n+1类。,24,A的所有k个元素的子集（基数为k的类）为从n个元素中取k个元素的组合数 。另外，因A，故（按加法原理） 2A =1+ + + + = 但由于二项式定理 (x+y)n= xkyn-k 令x=y=1，则有2n = ， 从而，有 | 2A |= 2n = 2 | A | 。,25,定理4. 若A，B是两个集合，那么，A=B 2A = 2B。 证明. )：一方面， AA (自反性) A2A (因为2A=B:B A ) A2B (充分性条件： 2A = 2B) AB (因为2B =A:AB ) 另一方面， B B (自反性) B2B (因为2B =A:AB ) B2A (充分性条件： 2A = 2B) BA (因为2A =

《集合代数课件》由会员F****n分享，可在线阅读，更多相关《集合代数课件》请在金锄头文库上搜索。