南京大学：《离散数学》课程教学资源（PPT课件讲稿）集合论——集合及其运算

集合及其运算 离散数学一集合论 ●●●●● 南京大学计算机科学与技术系

集合及其运算 离散数学－集合论 南京大学计算机科学与技术系

提要 ●基本概念 ●集合及其描述 ●集合相等、子集关系 ●幂集、笛卡尔乘积 ●集合运算 ●交并补、广义交、广义并 ●集合恒等式 ●集合相关命题的证明方式 ●自然数的构造

提要 ⚫ 基本概念 ⚫ 集合及其描述 ⚫ 集合相等、子集关系 ⚫ 幂集、笛卡尔乘积 ⚫ 集合运算 ⚫ 交并补、广义交、广义并 ⚫ 集合恒等式 ⚫ 集合相关命题的证明方式 ⚫ 自然数的构造

集合的定义 集合没有明确的定义,G. Cantor给出了一种刻划: 吾人直观或思维之对象,如为相异而确定之物,其总括 之全体即谓之集合,其组成此集合之物谓之集合之元素。 通常用大写字母表示集合,如A、B、C等,用小写字母表 示元素,如a、b、c等。若集合A系由a、b、c等诸元素所 组成,则表如A={a,b,c,…},而a为A之元素,亦常用a∈ A之记号表之者,a非A之元素,则记如a∈A。 (肖文灿译于1939年,《集合论初步》,商务印书馆) Naive set theory,朴素集合论

集合的定义 ⚫ 直观的定义 ⚫ 一个集合是一组无序的对象，这些对象称为这个集合的元 素或成员。 ⚫ aA表示a是集合A的一个成员， aA 表示a不是A的成员。 ⚫ Georg Cantor的描述 ⚫ [English translation] A set is a collection into a whole of definite, distinct objects of our intuition or our thought. The objects are called elements (member) of the set. Naïve set theory，朴素集合论

集合的描述 ●外延法:罗列、枚举 Va, e, i,o, u 1,3,5,7,9} ●概括法: ●{x|P(x)},P:某种思维、观察中总结出的对象性质 ●a∈{x|P(x)}→P(a) 例:z={x∈Z|x>0},Q={pq|p∈Z,q∈Z,q0} [a,b]={X∈R|a≤x≤b}

集合的描述 ⚫ 外延法：罗列、枚举 ⚫ V={a, e, i, o, u} ⚫ {1, 3, 5, 7, 9} ⚫ 概括法： ⚫ {x | P(x)}, P ：某种思维、观察中总结出的对象性质 ⚫ a{x | P(x)} ↔ P(a) ⚫ 例： +={x | x>0}，Q= { p/q | p , q, q0}， ▪ [a, b]={xR | axb}

集合 B) 文氏E 100 1203030 D) R B 70 60 40∵75 30 20 5

集合的描述 ⚫ 文氏图（Venn diagrams ）//John Venn U V a e o i u

集合相等、子集关系 定义:集合相等当且仅当它们有同样的元素 A=B当且仅当x(x∈A←X∈B)∥外延原则 ●定义:集合A称为集合B的子集,记作AcB ●Vx(x∈A→x∈B) 如果AcB,但A≠B,则A是B的真子集,记作AcB ●定理:对任意集合A和B,A=B当且仅当 ●AcB.且BcA

集合相等、子集关系 ⚫ 定义：集合相等当且仅当它们有同样的元素 ⚫ A=B 当且仅当 x(xA ↔xB) //外延原则 ⚫ 定义：集合A称为集合B的子集，记作AB ⚫ x (xA → xB ) ⚫ 如果AB, 但AB，则A是B的真子集，记作AB ⚫ 定理：对任意集合A和B, A=B 当且仅当: ⚫ AB, 且BA

子集关系的一个性质 ·证明:如果XcY且YcZ,则XcZ 要证明:“对任意的a,如果a∈X,则a∈Z ●证明: 对任意的a∈X ●根据已知的“XcY,可得:a∈Y 根据已知的“Y←Z”,可得:a∈Z 所以,va(a∈X→a∈Z),即XZ

子集关系的一个性质 ⚫ 证明：如果XY且YZ, 则XZ ⚫ 要证明：“对任意的a, 如果 aX, 则 aZ” ⚫ 证明： ⚫ 对任意的 aX ⚫ 根据已知的“XY”，可得：aY ⚫ 根据已知的“YZ”，可得：aZ ⚫ 所以，a (aX → aZ ), 即XZ

集合的大小 ●有限集合及其基数 若S恰有n个不同的元素,n是自然数,就说S是有限集合, 而n是S的基数,记作SFn ●无限集合 如果一个集合不是有限的,就说它是无限的

集合的大小 ⚫ 有限集合及其基数 ⚫ 若S恰有n个不同的元素，n是自然数，就说S是有限集合， 而n是S的基数，记作|S|=n。 ⚫ 无限集合 ⚫ 如果一个集合不是有限的，就说它是无限的

空集 ●存在一个没有任何元素的集合:空集O ●关于空集的一些性质: ●空集是任何集合的子集。 O∈A,即Ⅴx(x∈0→>x∈A) ●空集是唯一的,可以用O表示 如果0,O2都是空集,则0102和O2O1均为真

空集 ⚫ 存在一个没有任何元素的集合：空集Ø ⚫ 关于空集的一些性质： ⚫ 空集是任何集合的子集。 ⚫ ØA，即 x(xØ → xA) ⚫ 空集是唯一的，可以用Ø表示 ⚫ 如果 Ø1 , Ø2都是空集，则 Ø1Ø2 和 Ø2Ø1 均为真

关于空集的讨论 空集本身可以是一个对象,可以是某个集合的元素 O∈{O},O∈{O ●事实上,我们从空集开始构造整个集合世界! 自然数 ●有理数 ●实数(幂集运算)

关于空集的讨论 ⚫ 空集本身可以是一个对象，可以是某个集合的元素 ⚫ Ø{Ø}, Ø{Ø} ⚫ 事实上，我们从空集开始构造整个集合世界！ ⚫ 自然数 ⚫ 有理数 ⚫ 实数（幂集运算） ⚫ …