当前位置：文档之家 › 第三章 集合

第三章 集合

  • 格式：ppt
  • 大小：380.00 KB
  • 文档页数：40

下载文档原格式

  / 40

合集下载

离散数学---集合

离散数学---集合

特定的一些集合的表示符号
自然数集N={0，1，2，…} ， ， ， 自然数集 整数集合Z={…-2，-1，0，1，2，…} 整数集合 ， ， ， ， ， 有理数集合Q={xx=P⁄⁄q，p,q∈Z} 有理数集合 ， ∈ 实数集合R={ x x是实数 是实数} 实数集合 是实数 复数集合C={x x=a+bi,a,b∈R,i=复数集合C={x x=a+bi,a,b∈R,i=-1}
E B A
集合的相等
2、 相等： 、 相等： 定义： 相等， 定义：若 A⊆ B，且B⊆ A则 称A，B相等， ⊆ ， ⊆ 则 ， 相等 记 作A=B。 。 即 ∀ x∈A则 x∈B， 并且有 ∀ x∈B则 x∈A。 ∈ 则 ∈ ， 并且有∀ ∈ 则 ∈ 。 若A，B 不相等记 作 A≠ B
真子集： 真子集：
集合的说明： 集合的说明：
1、描述法中A={ x 1≤x≤5}与A={y1≤y≤5} 、描述法中 与 是表示同一个集合 2、集合中元素是无序的。 、集合中元素是无序的。 {a,b,c},{a,c,b},{b,c,a}表示同一个集合 。 表示同一个集合。 表示同一个集合 3、集合中的元素可能也是集合， 、集合中的元素可能也是集合， 例：A={1，{2}，2，{3，4}，{6}} ， ， ， ， ， =5， {2}∈ A,{6}∈ A=5，2∈A，{2}∈A，6∉A,{6}∈A
求幂集的过程
写出A的全部子集 设A={0，1，2}写出 的全部子集。 ， ， 写出 的全部子集。 元子集： 解：A的0元子集：∅ 的 元子集 A的1元子集：{0}，{1}，{2} 元子集： ， ， 的 元子集 A的 2元子集 ： {0， 1}， {0， 2}， {1， 2}。 元子集： ， ， ， ， ， 。 的 元子集 元子集： ， ， A的3元子集：{0，1，2} 的 元子集 A共有 个子集，即P（A）=8 共有8个子集， （ ） 共有 个子集 一般地如果 ， 一般地如果A=n， 元子集有1个即空集 则A的0元子集有 个即空集∅， 的 元子集有 个即空集∅ A的1元子集共有 n1个， 元子集共有C 的 元子集共有 A的 2元子集共有 2n个，…， 元子集共有C 的 元子集共有 ， A的m元子集共有 mn个，… 元子集共有C 的 元子集共有 n元子集共有 nn=1个， 元子集共有C 元子集共有 个 所以A的子集个数为 的子集个数为C 所以 的子集个数为 0n+ C1n+…+ Cnn=2n

第三章 集合论基础

第三章 集合论基础

第三章集合论基础1.如何表示集合？请各举一例。

2.一般地用谓词公式描述法定义集合A：A={x|P(x)}, 请问什么样的元素属于A，什么样的元素不属于A？3.判断下面命题的真值，并说明原因。

集合{a}与集合{{a}}是相同的集合。

4.A、B是集合。

试用谓词公式，表达A⊆B、A=B以及A⊂B。

5.证明空集是唯一的。

6.判断下面命题的真值。

对你的回答，给予证明或者举反例。

1．如果A∈B，B⊆C ，则A∈C。

2．如果A∈B，B⊆C，则A⊆C 。

7.判断下面命题的真值。

对你的回答，给予证明或者举反例。

1．如果A⊆B，B∈C，则A∈C。

2．如果A⊆B，B∈C，则A⊆C。

8.设A={a,{a},{a,b},{{a,b},c}}，判断下面命题的真值。

⑴{a}∈A ⑵⌝({a}⊆ A) ⑶c∈A⑷{{a,b}}⊆A ⑸{{{a}}}⊆A9.判断下面命题的真值。

⑴{a,b}∈{{a,b},c} ⑵{a}⊆{{a,b},c} ⑶{a,b}⊆{{a,b},c}⑷{c}⊆{{a,b},c} ⑸({c}⊆{{a,b,c}})→(Φ⊆{a})10.集合A的幂集是如何定义的？令A={1,{1}}，求A的幂集P(A).11.设A={Φ}，B=P(P(A))。

判断下面命题的真值。

1．Φ∈B 2．Φ⊆B 3．{Φ}∈B 4．{Φ} ⊆ B 5．{{Φ}}∈B 6．{{Φ}}⊆B12.填空：设E是全集，A、B、C是任意集合，则⑴A⊕ ~E=( ) ⑵A⊕A=( ) ⑶~A－A =（）⑷A－B( )A ⑸A－B=A( )~B ⑹A( )~A=E13.给定全集E={1,2,3,4,5} A={1,2,3} B={2,3,4}1．求A的幂集P(A)2．求B⊕ ~A14.给定全集N={1,2,3,4,…...}A={1,2,7,8} B={ i | i2<50 }C={i | i可被3整除，0≤i≤30 }D={ i |i=2k, k∈i+, 1≤k≤6 }分别求(1) B-(A∪C) (2) (~A∩B)∪D15.证明A⊆B ⇔ A∩B=A。

离散数学第三章 集合

离散数学第三章 集合

别地，以集合为元素的集合称为集合族或集合类，
如A={{1,2,3}, { 8,9,6}}。
14
2018/11/12
2. 子集、全集与空集 子集是描述一个集合与另一个集合之间的 关系，其定义如下。

定义3.1.1 设A和B是任意两个集合，如果集合 A 的每个元素，都是集合 B 中的一个元素，则
称A是B的子集，或称A被包含于B中，或者说
正则公理的一个自然推论是: 对任何集合S, {S} S (否则有…SSS),
从而规定了集合{S}与 S的不同层次性。
6
2018/11/12
集合与其成员是两个截然不同的概念, 集合 的元素可以是任何具体或抽象事物, 包括别的集
合, 但不能是本集合自身。
因为一个集合是由它的成员构成的, 是先有
10ቤተ መጻሕፍቲ ባይዱ
2018/11/12
表示一个特定集合，基本上有两种方法：

一是枚举法，在可能时列出它的元素，元素之 间用逗号分开，再用花括号括起。如 A={a,e,i,o,u}
表明集合A是由字母a, e, I ,o和u为元素构成的。
11
2018/11/12

二是谓词法，用谓词公式来确定集合。即个体 域中能使谓词公式为真的那些元素，确定了一 个集合，因为这些元素都具有某种特殊性质。 若P(x)含有一个自由变元的谓词公式，则 {x|P(x)}定义了集合S，并可表为 S={x|P(x)}
17
2018/11/12

定义3.1.3 如果一个集合包含了所要讨论的每 一个集合，则称该集合为全集，记为U或E。 它可形式地表为 U={x|P(x)∨┐P(x)}
其中P(x)为任何谓词公式。
18

第三章 集合论基础

第三章 集合论基础
(１)重复元素没有意义，即
Ａ＝{1,2,2,4}={1,2,4}
(２)同一集合不同表达形式当然相等。例 如：
Ａ＝{x|x(x-1)=0}，Ｂ={0,1} 则Ａ＝Ｂ。
4. 几个重要集合
(１)空集Φ 指不含有任何元素的集合。其表达式如下：
Φ＝{x｜P(x)∧P(x)} 式中谓语P(x)∧P(x)说明既满足Ｐ(x)，又满足Ｐ(x)的 元素是不存在的。因为Ｐ(x)为Ｔ，P(x)为F，显然这样的x是
式中：x－表示集合元素； p(x)-作为谓语，用以说明x是什么，或在什么范围内变化。 例如：
Ａ＝{x｜1≤ x ≤2} 这里p(x)是说明集合Ａ的元素是由〔１,２〕闭区间全
体实数组成的。又如：
A {xi i 1,2, , n} 此集合与 A {x1, x2 , , xn} 完全等价。
3. 集合的包含与相等
1. 集合与元素
当我们把一群确定的事物当作整体来考察时，则该整体就 叫作集合，或简称集。例如某学校的全体教职员工可视为一个 集合；全体教职员工、教学实验设备等也可视为一个集合，习
惯上，我们常用大写字母Ａ、Ｂ、Ｃ、Ｄ…表示集合，集合中
的每一个具体事物叫做这个集合的元素（或简称元），并用大 括号括起来，以表示是一个整体。集合的元素一般用小写字母
若ａ是集合Ａ的一个元素，即ａ属于Ａ，记为 ａ∈Ａ，若ａ不是集合Ａ的一个元素，即ａ不属 于Ａ，记为ａＡ。
上述元素与集合的关系可用特征函数来描述， 即
0
A (x) 1
当x A时 当x A时
2. 集合的表示方法
集合的表示方法有多种多样。就给定的集合来讲，一般 有三种表达形式：
(１)列举法 指把集合中的所有元素一一列举出来的方
法。如Ａ＝{1,2,3,4}, B={b1,b2,b3}等。

离散数学第3章 集合

离散数学第3章 集合
命题演算证明法的书写规范 (以下的X和Y代表集合公式) (1) 证XY
任取x， xX … xY (2) 证X=Y
方法一 分别证明 XY 和 YX 方法二 任取x，xX … xY
注意：在使用方法二的格式时，必须保证每步推理都是充分 必要的
27
第三章 集合
命题演算法
例3-3.2 证明A(AB) = A （吸收律）
元素a属于A，记作aA； 或者a不属于A，记作aA，也可以记作┓(aA)。
（4）任意性：集合的元素也可以是集合。 例：A={1，{2}，2，{3，4}，{6}} A=5，2A，{2}A，6A,{6}A
6
第三章 集合 例如：A={{a,b}，d，{{b}}}。可以用一种树形图来表示这种
隶属关系，该图分层构成，每一层上的结点都表示一个集 合，它的儿子就是它的元素。 集合的树型层次结构
32
第三章 集合
§3-3-3 笛卡儿积
定义3-3.2 两个元素a，b组成二元组，若它们有次序 之别，称为二元有序组，或称为有序对或序偶，记为<a， b>，称a为第一分量，b为第二分量；若它们无次序区分， 称为二元无序组，或称为无序对，记为（a，b）。
有序对具有如下性质。 （1）有序性：当x≠y时<x，y>≠<y，x>。 （2）<x，y>与<u，v>相等的充分必要条件是
A
B
11
第三章 集合
§3-2 集合之间的关系
§3-2-1 集合之间的关系 （1）相等关系： • 两集合A和B相等，当且仅当它们有相同的元素。 • 若A与B相等，记为A=B；否则，记为A≠B。 • 可形式化为：A=B(x)(xAxB)。
12
第三章 集合

离散数学 第三章 集合

离散数学 第三章 集合

离散数学
将集合中的元素逐一列出，两端加上花括号。 { 1，2，3，4，5}； { 风，马，牛 }； { 2，4，6，8，10，… }； { 3，7，11，15，19，… }； 比较适合集合中的元素有限（较少或有规律），无限 （离散而有规律）的情况。 (3)谓词表示法： { x:P(x) } 或者{ x︱P(x) } 其中：P表示 x 所满足的性质（一元谓词）。 { x : x I （且） x8} ={…，-3，-2， -1，0，1，2，3，4，5，6 , paradox(1902))： 罗素1902年在集合论中也发现了如下的悖论。他 构造了这样一个集合 S={ x:xx } 然后他提出问题： SS ？ 如果SS ，那么，按罗素给S的定义，则应有 SS； 如果S S ，那么，按罗素给S的定义，则应有 SS ； 罗素悖论的发现，几乎毁灭集合论，动摇数学的 基础，倾危数学的大厦。直接引发了数学的第三次 危机。
8
离散数学
第三章 集合 (set)
§１.集合理论中的一些基本概念
个体与集合之间的关系 集合的表示法 集合与集合之间的关系 幂集
§2 .集合代数 集合的基本运算
集合的补运算 集合的交运算和并运算
集合的宏运算
9
离散数学
第三章 集合 (set)
§１.集合理论中的一些基本概念 集合概念将作为一个不言自明的元概念（基本概 念）。它不能用别的术语来精确的定义，只能用别的 术语来加以说明。它本身就是用来定义其它概念的概 念。 我们来看看一些关于什么是集合的各种不同的说法， 以便加深对集合这个元概念的理解。 1. 莫斯科大学的那汤松教授说： 凡具有某种特殊性质的对象的汇集称之为集。 2. 复旦大学的陈建功教授说： 凡可供吾人思维的，不论它有形或无形，都叫做 物。具有某种条件的物，称它们的全部谓之一集。 3. 南开大学的杨宗磐教授说：

《离散数学》课件-第3章集合的基本概念

《离散数学》课件-第3章集合的基本概念
17
例题
计算以下幂集：
，{}；{，{}}
解：
P()={} P({})={，{}} P({，{}})= {, {}，{{}},{，{}}}
18
3.3 集合的运算
集合的运算 并，交，补（绝对补），差（相对补－），和对称差等。
19
集合的并运算
• 定义3.3.1 设A，B为集合，由A和B的所有元素组成的集 合称为A与B的并集， 可表示为： AB={x|xAxB} 其文氏图：
其文氏图如下：
~E = ， ~ = E， ~（~A）= A A ~A = ， A ~A = E
27
德.摩根定律
• 定理3.3.5 设A，B为任意二个集合，则有： • （1） （AB）= A B • （2） （A B）= A B • 证明 设E为全集，显然有AE=A，AE=E成立。 • （1） （AB）= {x | xEx（AB）}= {x |
据的增加、删除、修改、排序，以及数据间关系的描述。
集合论在计算机语言、数据结构、编译原理、数据库与
知识库、形式语言及人工智能等许多领域得到广泛的应
用。
2
3.1 集合及其表示
• 集合是由一些对象聚集在一起构成的。 例如，全体整数 全体中国人 26个英文字母
• 构成集合的对象可以是各种类型的事物。 • 定义3.1.1 集合中的对象叫集合的元素，或成员。
• 集合中的元素可以具有共同性质，也可以表面上看起来不相干。
• 如{2，Tom，计算机，广州}
• 在集合论中，规定元素之间是彼此相异的，并且是没有次序关 系的。
例如，{3,4,5},{3,4,4,5,5},{5,3,4}都是同一个集合。
• 例如，A={3,4,5},

集合的基本概念和运算

集合的基本概念和运算
把以上定义加以推广，可以得到n个集合的并集和交集，即
A1 A2 ... An {x | x A1 x A2 ... x An}
A1 A2 ... An {x | x A1 x A2 ... x An}
3.2.1 集合的运算
定义3.2.2 设U为全集， A⊆U，则称A对U的相对补集为A的绝 对补集，记作~A。
Ø A xxØ x A
右边的蕴涵式中因前件 xØ 为假，所以整个蕴涵式对一切x为真，
因此 Ø为 真A 。
3.1 集合的基本概念
推论 空集是唯一的。
一般地，称集合A的子集Ø和A为A的平凡子集。
含有n个元素的集合简称n元集，它的含有m个(m≤n)元素的子集 称作它的m元子集。任给一个n元集，如何求出它的全部子集呢？
离散数学
第三章 集合的基本概念和运算
华中师范大学计算机科学系
第三章 集合的基本概念和运算
3.1 集合的基本概念 3.2 集合的基本运算 3.3 集合中元素的计数 3.4 笛卡尔乘积
3.1 集合的基本概念
集合是不能精确定义的基本的数学概念，直观地讲，集合是 由某些可以相互区别的事物汇集在一起所组成的整体。对于给定 的集合和事物，应该可以断定这个特定的事物是否属于这个集合。 如果属于，就称它为这个集合的元素。
排中律 A ~ A U
矛盾律 A ~ A Ø
吸收律 AA B A, A A B A 双重否定律 ~ ~ A A
德·摩根律 AB C A B AC AB C A B AC
~ B C ~ B ~ C
~ B C ~ B ~ C
定义3.2.1设A，B为集合，A与B的并集A∪B，交集A∩B，B对A 的相对补集A-B分别定义如下： A B {x | x A xB} A B {x | x A xB} A B {x | x A xB}

第三章 集合与关系

第三章 集合与关系
例1 若A={α ，β }，B={1，2，3}，求A×B，B×A， A×A， B×B，以及(A×B)∩(B×A)。 解： A×B={<α ,1>,<α ,2>,<α ,3>,<β ,1>,<β ,2>,< β ,3>} B×A={<1,α >,<1,β >,<2,α >,<2,β >,<3,α >,<3,β >} A×A={<α , α >,<α , β >,<β , α >,<β , β >} B×B={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2> ,<3,3>} (A×B)∩(B×A)=φ
(2)、全集： 定义5：在所研究的同一个问题中，如果涉及到的集合均 是某一个集合的子集，则称该集合是全体。记作。 全集的概念是相对。要看具体研究的问题。 例：在考虑某大学的部分学生组成的集合（如系，班级 等）时，该大学的全体学生组成了全集。 (3)、幂集： 定义6：设A是一个集合，由A的所有子集组成的集合称为 A的幂集，记作ρ(A)或2A 。 例如：A={a,b,c}
设A、B、C为三个集合，则下列分配律成立。 a) A∩(B∪C）=（A∩B）∪（A∩C） b) A∪(B∩C）=（A∪B）∩（A∪C） 证明： 设S=A∩(B∪C），T=（A∩B）∪（A∩C）， 若x∈S，则x∈A且x∈B∪C， x∈A且x∈B或x∈C， 即x∈A且x∈B或 x∈A且x∈C， 即X∈A∩B或x∈A∩C， 即x∈T，所以ST。 反之，若x∈T，则x∈A∩C， 即x∈A且x∈B或x∈A且x∈C， 即 x ∈ A且 x ∈ B∪ C， 于是x∈S，所以TS。因此T=S。

第三章 集合体

第三章 集合体

例:求六棱柱被截切后的水平投影和侧面投影
1‫׳2 ׳‬ 1‫״‬ 3‫״‬ 5‫״‬ 7‫״‬ 2‫״‬ 4‫״‬ 6‫״‬
3‫׳‬ 5‫׳‬
7‫׳‬
4‫׳‬
作图方法:
1 求棱线与截平面 的共有点
2 连线 3 根据可见性处理轮廓线
6‫׳‬
5
3 1
7 2 6 4
试完成五棱柱被两平面Ｐ、Ｑ截切后的投影。
特征视图
形体的特征视图
特征视图
形体的特征视图
要将几个视图联系起来看
有一个视图相同的不同集合体
2 求一般点。
3 连线。
平面与常见回转面的截交线形状及投影
平面截圆球
截平面截圆球，截 交线为圆。
例:求圆球被截切后的水平投影和侧面投影
轮廓线怎样处理?
分析:球面被侧平 面截切，侧面投影 为圆；球面被水平 面截切，水平面投 影为圆。
轮廓线要不 要?
求半球体截切后的俯视图和左视图。
水平面截圆球的截交线 两个侧平面截圆球的截 的投影，在俯视图上为 交线的投影，在左视图 部分圆弧，在侧左视图 上为部分圆弧，在俯视 上积聚为直线。 图上积聚为直线。
三视图的画法
4.布置视图 应考虑尺寸标注和标题栏的位置合理布置各
视图位置。画出作图基准线，即对称中心线、主要回转体的轴
线、底面及重要端面的位置线。 5.绘制底稿 6.检查、描深 按标准线型描深。 叠加型组合体应按照形体分析法逐个画出各 底稿完成后，应认真检查，确认无误后，
形体的投影，从而得到整个组合体的三视图。
（五）检查、加深
例：绘出轴承座的三面投影 1) 绘出底板的三面投影
1)、绘出底板的三面投影
2)、绘出圆台的三面投影

武汉大学离散数学第3章 集合

武汉大学离散数学第3章 集合
∴A∩CB∩D
l)若AB, 那么, A∩B=A ∵AB,又AA,根据（h）A∩AA∩B，即A A∩B，另一
方面，A∩BA ∴A=A∩B
推论: a)A∪U=U b)A∩U=A
3.2.2 补运算
1.补运算定义 设U是全集，A的补集为 A~=U-A={xxU∧xA}={xxA}
U
2.补运算性质 定理1：a)A∪A~=U
b)A∩A~=
A A~
证：a)xA∪A~xA∨xATxU ∴A∪A~=U
b)xA∩A~xA∧xAFx ∴A∩A~=
举例
1)若全集为{1,2,3,4,5,6,7,8} 而A={1,2,3,4} 则A~ = {5,6,7,8}
注意：属于关系和包含关系都可以是两个集合之间的 关系，对于某些集合可以同时成立这两种关系。
例如A＝{a，{a}}和{a}，既有{a}∈A，又有{a} A。 前者把它们看成是不同层次上的两个集合，后者把它 们看成是同一层次上的两个集合，都是正确的。
3.1.5 全集
讨论的某个具体问题中，所涉及的集合都是某个集合的 子集，此集合称为全集U。
∵x(xxA)永真，∴A。 定理5：空集是唯一的。
证：设有两个空集，，’， 则’，’， ∴=’。
注：与{}不同，前者没有元素，后者是以空集为一个元素 的集合。
3.1.7 幂集
定义:设A是一个集合,A的所有子集的集合,称为A的幂集, 并记为ρ (A)或2A
例1：试求出集合{p,q}的幂集。 解：，{p},{q},{p,q}是{p,q}的子集 ∴ ρ ({p,q})={,{p},{q},{p,q}}是{p,q}的幂集。
(3)称元素可以出现多次的集合为多重集,称某元素出现 的次数为该元素的重复数。 {a,b,a,c,a,b}

离散数学 教案 第3章 集合

离散数学 教案 第3章 集合

当n无限增大时，可以记为
21
计算机科学与技术学院
Discrete Mathematics
例1 集合A={x-2＜x＜2，xR}， B={x0≤x≤4,xR}
求A∪B，A∩B 。 解：A∪B={x-2＜x＜2或0≤x≤4,xR} ={x-2＜x≤4,xR} A∩B={x-2＜x＜2且0≤x≤4,xR} ={x0≤x＜2,xR}
把集合的所有元素写在花括号内，元素之间用逗 号分开；一般用于有限集和有规律的无限集合。
2.描述法 用谓词来概括集合中元素的属性。通常用 { xA(x)}来表示具有性质A的一些对象组成的集合。
例：D={(x,y)x2+y2≤1∧x∈R∧y∈R}
西南科技大学
5
计算机科学与技术学院
Discrete Mathematics 常用集合的表示方法和表示符号 （1）自然数集N={0，1，2，…}
由定义可知，广义交和广义并是针对集族而言的， 对于非集族来说，其广义交和广义并为空集。
西南科技大学
25
计算机科学与技术学院
Discrete Mathematics 下面以n个集合为例说明：
例如：
西南科技大学
26
计算机科学与技术学院
Discrete Mathematics 可以把n个集合的并和交简记为: 和 ，即:
（2）整数集合I={…-2，-1，0，1，2，…}
（3）有理数集合Q={xx=Pq∧p,qZ}
（4）实数集合R={ x x是实数
（5）复数集合C={x x=a+bi∧a,bR∧i2=-1}
西南科技大学
6
计算机科学与技术学院
Discrete Mathematics
3. 归纳定义法

离散数学第三章集合的基本概念和运算

离散数学第三章集合的基本概念和运算
第3章 集合的基本概念和运算
3.1 集合的基本概念
3.2 集合的基本运算
3.3 集合中元素的计数
3.1 集合的基本概念
1.子集:若 B⊆A⇔∀x(x∈B→x∈A),则称B为A的子集. 2.真子集:若 B⊆A ∧ B≠A,则称B为A的真子集. 3.集合相等: B⊆A ∧ A⊆B⇔A=B,称集合A与B相等. 4.空集:不含任何元素的集合称为空集.记作φ. 空集是一切集合的子集;空集是唯一的. 5.n元集:含有n个元素的集合称为n元集. 6.全集:如果所涉及的集合都是某个集合的子集,则称这个集 合为全集(E). 7.幂集:设A为集合,把A的全体子集构成的集合,称为A的幂集 记作P(A),P(A)={x|x⊆A}. 若A是n元集,则P(A)有2n个元集(n元集有2n个子集).
二.集合运算的算律 幂等律：A∪A=A, A∩A=A;
结合律: (A∪B)∪C=A∪(B∪C), (A∩B)∩C=A∩(B∩C); 交换律: A∪B=B∪A , A∩B=B∩A; 分配律: A∪(B∩C)=(A∪B)∩(A∪C), A∩(B∪C)=(A∩B)∪(A∩C); 同一律: A∪φ=A, 排中律: A∪～A=E; A∩E=A; 零律: A∪E=E, A∩φ=φ;
| Ai I A j I Ak | +... + ( −1) m | A1 I A2 I ...I Am | ∑
推论： 推论：在S中至少具有一条性质的元素数是
| A1 U A 2 U ... U A m |= +
1≤ i < j < k ≤ m
∑|A
i =1
m
i
|−
1≤ i < j ≤ m
∑|AI
i
二.包含排斥原理 包含排斥原理

第三章 集合与关系

第三章 集合与关系
图1
四、集合与集合 1． 集合与集合之间的关系：, =, ⊈, , , A B x (xAxB) A=BABBA ABABAB A ⊈ B x (xAxB) 思考： 和 的定义 2．注意和是不同层次的问题
五、空集和全集 1．空集 ：不含有任何元素的集合 实例： {x|xRx2+1=0} 定理 6.1 空集是任何集合的子集。 证 对于任意集合 A， A x (xxA) T (恒真命题) 推论 是惟一的 2．全集 E：包含了所有集合的集合 全集具有相对性：与问题有关，不存在绝对的全集 六、幂集 1．定义：P(A)={x | xA} 2．实例： P()={}, P({})={,{}} 3．计数：如果|A|=n，则|P(A)|=2n.
第三章 集合与关系 3-1~3-3
主要内容 集合的基本概念----属于、包含、幂集、空集、 文氏图等 集合的基本运算----并、交、补、差等 集合恒等式----集合运算的算律、 恒等式的证明 方法 与后续内容的关系 是集合论后续内容的基础 是典型的布尔代数系统
第一节 集合的基本概念
一、集合的定义 集合没有精确的数学定义 直观理解： 由离散个体构成的整体称为集合， 称这些个体为集合的元素 常见的数集：N, Z, Q, R, C 等分别表示自然数、整数、有理数、实数、 复数集合 二、集合的表示法 1．枚举法----通过列出全体元素来表示集合 2．谓词法----通过谓词概括集合元素的性质 实例： 枚举法 自然数集合 N={0,1,2,3,…} 谓词法 S={x| x 是实数，x21=0}
3．广义运算的性质 （1）=，无意义 （2）单元集{x}的广义并和广义交都等于 x （2）广义运算减少集合的层次（括弧减少一层） （3）广义运算的计算：一般情况下可以转变成初级运算 {A1,A2,…,An}=A1A2…An {A1,A2,…,An}=A1A2…An 4．引入广义运算的意义 可以表示无数个集合的并、交运算，例如 {{x}|xR}=R 这里的 R 代表实数集合.

《离散数学》第3章 集合

《离散数学》第3章 集合

P ( A) = {φ , A}
第二节 集合的运算 内容： 内容：集合的运算，文氏图，运算律。 重点： 重点：(1) 掌握集合的运算
A ∪ B, A ∩ B, A − B, ~ A, A ⊕ B
(2) 用文氏图表示集合间的相互 关系和运算， (3) 掌握基本运算律的内容及运用。
一、集合的运算。 集合的运算。 集合 A, B 的并集 A ∪ B， 交集 A ∩ B，相对补集
三 包含排斥定理 设A和 B是两个有限集合，则 A ∪ B = A + B − A ∩ B ，
B 其中 A, B 分别表示 A、的元数．
把包含排斥定理推广到n个集合的情况可用如下定 理表述： 设A1 , A2 ,⋯ A为有限集合，其元数分别为 A , A ,⋯, A ，则 n
1 2 n
A1 ∪ A2 ∪ ⋯ ∪ An
A= B ⇔ A⊆ B∧B⊆ A
5、特殊的集合。 空集 φ 全集 E (或 U )
φ ⊆ A ⊆ E ( A 为任一集合)
例1、选择适当的谓词表示下列集合。 、 (1) 小于5的非负整数集 (2) 奇整数集合
{x | x ∈ N ∧ x < 5} {x | x = 2n + 1 ∧ n ∈ Z }
{ } (8) {a, b} ∈ {a, b, {{a, b}}}
(7) {a, b} ⊆ a, b, {{a, b}}
例3、A, B, C 为集合，若 A ∈ B 且B ∈ C ， 、 有可能 A ∈ C 吗，有可能 A ∉ C 吗？ 解：两种情形都有可能。 设 A = {a}, B = {{a}} , C = {{a}, {{a}}} ， 则 A ∈ B, B ∈ C ，有 A ∈ C 。 又设 A = {a}, B = {{a}} , C = {{{a}}}， 则 A ∈ B, B ∈ C ，但 A ∉ C 。

第03章 集合的基本概念与运算

第03章 集合的基本概念与运算

5. 全集 定义3.6 在一个具体问题中, 如果所涉及的集
合都是某个集合的子集, 则称该集合为全集, 记为 E。它可形式地表为
E = { x | P(x)∨¬ P(x) }
其中：P(x)为任何谓词公式。
显然, 全集E即是第二章中的全总个体域。于是,
每个元素 x 都属于全集 E, 即命题(x)(xE)为真。
全集E用一个矩形的内部表示, 其他集合用矩
形内的园面或一封闭曲线圈成的面积来表示。
集合之间的关系和运算可以用文氏图给予 形象的描述
四、集合运算算律
设A、B、C 为任意集合, 则：
等幂律：A∩A A , A∪A A 结合律：(A∩B )∩C A∩(B∩C ) , (A∪B )∪C A∪(B∪C ) 交换律： A∩B B∩A ,
推论
① AB = AB ② AB = BA
③ AA =
④ A = A
集合代数与对偶原理
这里形式地讨论由集合、集合变元、集合运算和 圆括号所构成的 集合代数以及集合代数中的对偶
原理
与命题逻辑相似, 对于给定集合实行集合运算, 可 生成 新 的集合。可用大写英文字母表示确定集合 一样，也用大写字母表示不确定的集合, 即集合常
集合的树型层次结构
在每个层次上把集合作为一个结点, 它的元素作为它 的儿子 如：集合 A＝{ a, {b, c}, d, {{d}} } 的树形图。 图中的 a, b, c, d 也是集合, 由 于所讨论的问题与 a, b, c, d 的元素无关, 所以没有列出它
们的元素。鉴于集合的元素是
集合这一规定, 隶属关系可以 看作是处在不同层次上的集合 之间的关系。
证明：当 n =2 时, 结论成立。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

3.2
3.2.3 集合的补
集合的补运算有以下性质
集合的运算
(1)双重否定律:~(~A)=A (2)摩根律:~=U (3)摩根律:~U= (4)矛盾律:A∩(~A)= (5)排中律:A∪(~A)=U 为了简单,约定A∩(~B)表示为A∩~B,A∪(~B)表示为 A∪~B.
3.2
3.2.3 集合的补
包含排斥原理
例3.3.3 某班有学生60人,其中有38人选修Visual C++课 程,有l6人选修Visual Basic课程.有21人选修Java课程; 有3人这三门课程都选修,有2人这三门课程都不选修, 问仅选修两门课程的学生人数是多少? 解 设选修Visual C++课程的学生为集合A;选修Visual Basic 课程的学生为集合B;选修Java课程的学生为集合C. 由题意可知: |A|=38 |A∩B∩C|=3 |B|=16 |C|=21 60-|A∪B∪C|=2
因为|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C| 所以有:|A∩B|+|A∩C|+|B∩C|=20.
3.3 3.3
包含排斥原理
应注意,仅学两门语言的人数不是20,因为 A∩BA∩B∩C, 所 以 仅 选 修 Visual C++ 课 程 和 Visual Basic课程的学生数应是|A∩B|-|A∩B∩C|=|A∩B|-3.同理, 仅选修Visual C++课程和Java课程的学生数应是|A∩C||A∩B∩C|=|A∩C|-3.仅选修Visual Basic课程和Java课程的 学生数应是|B∩C|-|A∩B∩C|=|B∩C|-3.所以仅选修两门课 程的学生数是 |A∩B|+|A∩C|+|B∩C|-3|A∩B∩C|=11.
集合之间的关系
集合A和集合B相等的充分必要条件是AB且BA. 如果集合A是集合B的子集,但A和B不相等,也就
是说在B中至少有一个元素不属于A,则称A是B的真子集,记作 AB 或 BA
例如:集合A={1,2},B={1,2,3},那么A是B的真子集 定义3.1.4 若集合U包含我们所讨论的每一个集合,则称U是所讨 定义 论问题的完全集,简称全集.
3.2
3.2.3 集合的补
集合的运算
集合的补运算,其文氏图表示,阴影部分表示~A.
U A A
3.2
3.2.4
集合的运算
集合的对称差
定义3.2.5 设A,B是两个集合,由属于A而不属于B,或者属于B 定义 不属于A的元素组成的集合,称作A和B的对称差,记作AB.即 AB=(A∪B)-(A∩B) 例如,A={1,2,3,4}, B={1,3,5,7,9} 那么 AB={2,4,5,7,9}
集合的运算
定理3.2.4 设A,B是两个集合,则下列关系式成立: 定理 ~(A∪B)=~A∩~B ~(A∩B)=~A∪~B 这个定理称为德摩根定律.读者可以用文氏图验证. 定理3.2.5 设A,B,C是任意三个集合,则下列关系式成立: 定理 A-B=A∩~B A-B=A-(A∩B) 定理可由差运算的定义直接得到.
3.1 集合的概念与表示
3.1.3
定义3 定义3.1.5
集合之间的关系
设A是有限集,由A的所有子集ρ(A),即ρ(A)={X|XA}. 在A的所有子集中,A和这两个子集又叫平凡子集. 例如:A={1,2,3},则 ρ(A)={,{1},{2},{3},{1,2},{1,3}, {2,3},{1,2,3}}
1 n
n 1 n
+ c
n n
= 2
n
|ρ(A)|= 2 n
3.2
3.2.1 3.2.2 3.2.3 3.2.4
集合的运算
集合的交运算 集合的并运算 集合的补 集合的对称差
3.2 3.2.1
集合的运算 集合的交运算
定义3.2.1 对于任意两个集合A,B,由所有既属于A又属于B的元 定义 素构成的集合,称作A与B的交集,记作A∩B.即 A∩B ={x | x∈A且x∈B} 例如,A={a,b,c},B={b,c,d,e},则 A∩B={b,c} 又如,A={1,2,3,4,5},B={1,3,5,7,9},则 A∩B={1,3,5}
3.2
3.2.2 集合的并运算
集合的运算
用文氏图表示集合之间的并运算:
U A B
用平面上的矩形表示全集U.用矩形内的圆表示U中的任一集合. 图中表示了集合A和集合B的并集.阴影部分就是A∪B.
3.2
3.2.2 集合的并运算
集合的运算
由集合并运算的定义可知,并运算具有以下性质: (1)幂等律:A∪A=A (2)同一律:A∪=A (3)零律:A∪U=U (4)结合律:(A∪B)∪C=A∪(B∪C) (5)交换律:A∪B=B∪A
100-|A∪B∪C|=25
3.3 3.3
由包含排斥原理可知:
包含排斥原理
| A∪B∪C|=|A|+|B|+|C|-|A∩B|-|B∩C|-|A∩C|+|A∩B∩C| 100-25=34+24+48-14-13-15+|A∩B∩C| 所以 |A∩B∩C|=11 这三种爱好都有的大学生人数是11.
3.3 3.3
3.2.2
定理3 定理3.2.1
集合的并运算
3.2
集合的运算
设A,B,C是三个集合,则下列分配律成立: A∩(B∪C)=(A∩B)∪(A∩C) A∪(B∩C)=(A∪B)∩(A∪C)
定理3.2.2 定理
设A,B为两个集合,则下列关系式成立: A∪(A∩B)=A A∩(A∪B)=A
这个定理称为吸收律,读者可以用文氏图验证.
3.2
3.2.2 集合的并运算
定义3 定义3.2.2
集合的运算
任意两个集合A,B的并,记作A∪B,它也是一个集
合,由所有属于A或者属于B的元素合并在一起而构成的,即 A∪B={x | x∈A或x∈B} 例如,A={a,b,c},B={a,b,c,d,e},则 A∪B={a,b,c,d,e} 又如,A={1,2,3,4,5},B={1,3,5,7,9},则 A∪B={1,2,3,4,5,7,9}
这个结论称作包含排斥原理. 定理3.3.2 设A1,A2,…,An为有限集合,|A1|,|A2|,…, 定理3.3.2 |An|为其基数,则
A1 ∪ A2 ∪ ∪ An = ∑ Ai
i =1
n
1≤ i < j ≤ n
∑A ∩A
i
j
+
i 1≤ i < j < k ≤ n
∑A ∩A
j
∩ Ak +
+ (1)n 1 A1 ∩ A2 ∩ ∩ An
3.2 3.2.4
集合的运算
集合的对称差集合的补
例3.2.1 已知:AB=AC,则B=C. 证明:AB=AC A(AB)=A(AC) (AA)B =(AA)C B=C B=C
3.3 3.3
定理3.3.1 定理3.3.1
包含排斥原理
设A,B为有限集合,|A|,|B|为其基数,则 |A∪B|=|A|+|B|-|A∩B|
3.3 3.3
包含排斥原理
假设某班有20名学生,其中有10人英语成绩为优,有 例 3 . 3 .1 8人数学成绩为优,又知有6人英语和数学成绩都为优.问两门课 都不为优的学生有几名? 解 设英语成绩是优的学生组成的集合是A,数学成绩是优的学 生组成的集合是B,因此两门课成绩都是优的学生组成的集合是 A∩B.由题意可知 |A|=10 |B|=8 |A∩B|=6
3.2
3.2.4
集合的运算
集合的对称差
集合的对称差的文氏图表示
U A B
3.2 3.2
3.2 3.2.4
集合的运算
集合的对称差集合的补
由对称差的定义易得下列性质: (1)AA= (2)A=A (3)AU=~A (4)AB=BA (5)(AB)C=A(BC) (6)AB=(A-B)∪(B-A)
3.2 3.2
3.1.3 集合之间的关系
定义3 定义3.1.1 如果集合A中的每一个元素都是集合B中的元素, 则称A是B的子集,也可以说A包含于B,或者B包含A,这种 关系写作 AB 或 称B不包含A,记作 BA 或 AB BA
如果A不是B的子集,即在A中至少有一个元素不属于B时,
3.1 集合的概念与表示
3.1.3 集合之间的关系
3.2
3.2.3 集合的补
集合的运算
定理3.2.3 设A,B,C为任意集合,则下列关系式成立: 定理 (1)A-B=A -(A∩B) (2)A∪(B – A)=A∪B (3)A ∩(B–C)=(A∩B)–C (4)A-B A
3.2
3.2.3 集合的补
集合的运算
定义3.2.4 设U是全集,A是U的一个子集,称U-A为A关于全集 定义 的补集,也叫做A的绝对补集,简称为补集.记作~A.即 U-A={x|xU且xA} 例如,U={x | x是计算机学院的全体学生}, A={x | x是计算机学院的全体女学生}, 则 ~A={x | x是计算机学院的全体男学生}
3.3 3.3
包含排斥原理
例3.3.4 75个儿童到公园游乐场.他们在那里可以骑旋转 木马,坐滑行铁道车,乘宇宙飞船.已知其中有20人这 三种东西都乘坐过.其中55人至少乘坐过其中的两 种.若每样乘坐—次的费用是5元钱,公园游乐场总共收 入700元钱.试确定有多少儿童没有乘坐过其中的任何一 种. 解 设A是骑旋转木马的儿童的集合;B是坐滑行铁道车 的儿童的集合;C是坐宇宙飞船的儿童的集合.
3.2
3.2.1
集合的运算
集合的交运算