当前位置：文档之家 › 离散数学课件 第三章 集合与关系-1

离散数学课件 第三章 集合与关系-1

  • 格式：ppt
  • 大小：272.00 KB
  • 文档页数：63

下载文档原格式

  / 63

合集下载

离散数学---集合

离散数学---集合

特定的一些集合的表示符号
自然数集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).ppt

集合与关系(1).ppt

设R2为任意包含R的对称关系，
<a,b>∈R1 =R∪R–1，<a,b>∈R∨<a,b>∈R–1 。
若<a,b>∈R， ∵R2 R， ∴ <a,b>∈ R2 ；
若<a,b>∈R–1 ，则<b,a>∈R ；∴ <b,a>∈R2 ；
又∵R2对称， ∴ <a,b>∈R2。即R1 R2。
∴ s(R)=R1= R∪R–1。
2021/4/3
28
3.8关系的闭包运算
• (1) rs（R）= sr（R）；
• 证明： • (1) sr(R) =s(IA∪R)
=IA∪R∪(IA∪R) -1 =IA∪R∪R -1 =IA∪s(R)=rs(R)
2021/4/3
29
3.8关系的闭包运算
• (2) rt（R）= tr（R）；
• 证明：
– Q＝{{a}，{a，b}，{a，c}}
– D＝{{a}，{b，c}}
– G ＝{{a，b，c}}
– E＝{{a}，{b}，{c}}
– F＝{{a}，{a，c}}
• S、Q是A的 覆盖 • D、G、E是A的 划分
•F
既不是划分也不是覆盖
2021/4/3
33
3.9 集合的划分和覆盖
• 显然，若是划分则必是覆盖，其逆不真。
2021/4/3
27
3.8关系的闭包运算
• 关系R的自反(对称，传递)闭包还可以进一步复合 成自反(对称、传递)等闭包，它们之间有如下定理：
• 定理 设R是集合A上任意二元关系， 则 • (1) rs（R）= sr（R）； • (2) rt（R）= tr（R）； • (3) ts（R） st（R）。

离散数学(chapter3集合的基本概念和运算)PPT课件

离散数学(chapter3集合的基本概念和运算)PPT课件
离散数学
主讲教师
13.11.2020
1
第三章 集合的基本概念和运算
§3.1 集合的基本概念 §3.2 集合的基本运算 §3.3 集合中元素的计数
13.11.2020
离散数学
2
集合论 集合论是研究集合一般性质的数学分支,它的创 始人康托尔(G.Cantor ,1845－1918)。在现代数学中， 每个对象(如数，函数等)本质上都是集合，都可以用 某种集合来定义，数学的各个分支，本质上都是在研 究某一种对象集合的性质。集合论的特点是研究对象 的广泛性，它也是计算机科学与工程的基础理论和表 达工具，而且在程序设计，数据结构，形式语言，关 系数据库，操作系统等都有重要应用。本课程在第三， 四章中介绍集合论的内容。
如：
A∪B
E
A∩B
E
AB
E
~A
E
AB
E
13.11.2020
离散数学
15
二、文氏图 （Jahn Venn）
例4：用文氏图表示下面集合
13.11.2020
离散数学
16
二、文氏图 （Jahn Venn）
例5：用集合公式表示下面文氏图中的阴影部分
(1)A ∩ B ∩ C，
(2) (A∩B )∪(B∩C)∪(C∩A)
或A = B x(x A x B)
x(x A x B) x(x B x A)
13.11.2020
离散数学
8
四、集合之间的关系
3、真子集： B A。 BABABA BABA B=A
4、幂 集：集合A的全体子集构成的集合，记作P (A)。 符号化为 P (A) = { x | x A}
n 元集A的幂集P (A)含有2n个元素。

离散数学第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
第三章 集合

《离散数学》课件-第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},

离散数学第3章_(1-6)(新教材)(1)

离散数学第3章_(1-6)(新教材)(1)

注: J恰好是全体n位二进制数,也就是集合 {0,1,2,…, 2 n 1} 的二进制表示.
第三节 集合的运算
1. 集合的并
定义3.1 A和B是集合, 所有属于A或属于B 的元素组成的集合S, 称为A和B的并集, 记作 AB, 即, S=AB={x |(xA)(xB)}
A AB AB B
A
例如, 设全集E为整数集合Z, O为奇数集合, 则 为偶数集合, A
定理3.3(补与差的性质) (1)A-B=A B , (2)A-B=A-(AB) (3) A =E, A = A A
(4)
A
=A,
,
(5) E , E
(6)
A E A
定义1.1(集合相等的定义): 两个集合A和B是相等的, 当且仅当A和B有相同的元素, 记作A=B; 集合A与 集合B不相等,记作AB;
例如上面例1中的(1)和(2)中的两个集合S和T, 不难 看出它们实际上是两个相同的集合,也即有S=T. 再看上面例1中的(3),根据数论中著名的 Lagrange四平方定理(该定理的结论是:每个自然数 都可以表示成四个整数的平方数之和)可以看出:这 个例子中的集合W与全体自然数组成的集合N也是 相等的集合。
定义2.2(幂集) 假设A是一个给定的集合, 将集合A的每 个子集看成一个元素,则集合A的所有子集为元素所作成的 新的集合称为集合A的幂集,记为(A). 例1.求空集的幂集. 解由于空集只有一个子集，也就是空集自己,从而它的 幂集为 ()={} . (注)请注意将空集与{}区别开来: 中没有任何元素,而 {}中恰好有一个元素。
.(De Morgan律)
(11)设A、B是任何集合, 若AB, 则有: [1] B ,[2] (BA)A=B. A

《离散数学关系》课件

表示元素之间的顺序关系，如 大小关系、前后关系等。
等价关系
表示元素之间具有相同性质的 关系，等价关系具有自反性、 对称性和传递性。
偏序关系
表示元素之间的部分顺序关系 ，偏序关系具有自反性、反对
称性和传递性。
02 关系的运算
关系的并
总结词
关系的并运算是将两个关系中的所有元素组合在一起形成一个新的关系。
性质
离散数学关系具有传递性、反对称性、自反性等性质。传递性是指如果关系R(x,y)和关系R(y,z)都成立，则关系 R(x,z)也成立；反对称性是指如果关系R(x,y)和关系R(y,x)同时成立，则x=y；自反性是指对于集合中的任意元素x ，都存在关系R(x,x)。
关系的表示方法
表格法
通过表格的形式表示关系，行表示关系的起点，列表示关系的终 点，表格中的元素表示起点和终点之间是否存在关系。
05 关系的应用
关系在数据库中的应用
关系数据库
关系代数
数据库规范化
关系数据库是建立在关系模型基础上 的数据库，使用二维表格来表示和存 储数据。关系数据库中的表通过行和 列来组织数据，每一列代表一个属性 ，每一行代表一个记录。关系数据库 中的关系是指表格之间的关系，通过 主键和外键来建立表格之间的联系。
基数性质
关系的基数具有一些性质，如非 负性（基数总是大于或等于0）、 传递性（如果关系R中存在元素a 和b，且a和b之间有关系，那么 在关系S中a和b也一定有关系）等 。
基数计算
计算关系的基数需要先确定关系 中所有元素的数量，然后进行计 数。例如，如果一个关系是由两 个集合的笛卡尔积形成的，那么 它的基数就是这两个集合的元素 数量的乘积。
VS
推荐系统
推荐系统是根据用户的历史行为和偏好， 为其推荐相关或感兴趣的物品或服务的过 程。在推荐系统中，关系是指用户和物品 之间的关系，通过分析用户和物品之间的 关联规则和协同过滤等技术来实现个性化 推荐。

离散数学集合与关系

例如bxx是偶数其中px是谓词公式如果论域内客体a使得pa为真则aa否则34说明集合中的元素间次序是无关紧要的但是必须是可以区分的即是不同的
第三章 集合与关系
3.1集合的概念与表示方法 3.2 集合的运算
第三章集合与关系
3-1 基本概念
3.1 集合与元素 集合是个最基本的概念。 集合：是由确定的对象(客体)构成的集体。用大 写的英文字母表示。 这里所谓‚确定‛是指：论域内任何客体， 要么属于这个集合，要么不属于这个集合，是 唯一确定的。 元素：集合中的对象，称之为元素。 ∈：表示元素与集合的属于关系。 例如，N表示自然数集合，2∈N，而1.5不属于N 写成(1.5∈N), 或写成 1.5N。
第三章集合与关系
描述法：用句子(或谓词公式)描述元素的属性。 例如，B={x| x是偶数} C={x|x是实数且2≤x≤5} 一般地，A={x|P(x)}, 其中P(x)是谓词公式， 如果论域内客体a使得P(a)为真，则a∈A，否则 a A 。 3.4 说明 ⑴集合中的元素间次序是无关紧要的，但是必须是 可以区分的，即是不同的。例如A={a,b,c,a}， B={c,b,a}，则A与B是一样的。 ⑵对集合中的元素无任何限制，例如令 A={人，石头，1，Ｂ}, B={Φ,{Φ}}
第三章集合与关系
谓词定义： A=BABBA x(x∈Ax∈B)x(x∈Bx∈A) x((x∈Ax∈B)(x∈Bx∈A)) x(x∈Ax∈B) 2. 性质 (1)有自反性，对任何集合A，有A=A。 (2)有对称性，对任何集合A、B，如果有A=B，则 B=A。 (3)有传递性，对任何集合A、B、C，如果有A=B 且 B=C ，则A=C。
第三章集合与关系
3.2 有限集合与无限集合 这里对有限集合与无限集合只给出朴素的定 义，以后再给出严格的形式定义。 有限集合：元素是有限个的集合。 如果A是有限集合，用|A|表示A中元素个数。 例如，A={1,2,3}, 则|A|=3。 无限集合：元素是无限个的集合。 对无限集合的所谓‘大小’的讨论，以后再进 行。 3.3 集合的表示方法 列举法：将集合中的元素一一列出(或有规律的列 出)，写在大括号内。 例如，N={0,1,2,3,4,……} A={a,b,c,d}

离散数学第3章-集合与关系

（1） 任一对象a，对某一集合A来说，a属于A或a不属于A， 两者必居其一，且仅居其一。并且当a属于A时，称a是A的成
员，或A包含a，a在A之中，a属于A。即 a A a A
（2）集合中元素具有互异性和无序性。如{a,b,c,d}={a,b,b,c,d}
3-1 集合的概念和表示法
(3) 集合的元素个数可以是有限个也可以是无限个，具有有限个元素的集 合的为有限集，否则称为无限集。 (4) 集合中的元素也可以是集合，如
称为A和B的笛卡尔积，记作：A B
例：A {、、 、、
则：
3-4 序偶和笛卡尔积
5、多重直积：
A1 A2 A3是集合，A1 A2是笛卡尔集，也是集合仍可再作笛卡尔积
A A A A A A ( ) { , , | , , }
1
2
3
1
2
3
1
1
2
2
3
3
A A A { , , | , , }
E AB
S={x∣(x∈A)∧（xB）}
={x∣（x∈A）∧ （x∈B）}
3-2 集合的运算
b）集合A关于全集E的补。 E-A称为A的绝对补，记作~A。
E A
~A={x∣(x∈E）∧（x A）}
~ A有下列性质： ⑴ ~（ ~A）=A
⑵ ~E=
⑶~ =E
⑷A∪~A=E
⑸A∩~A=
3-2 集合的运算
* 以后判断两集合相等就主要用这一重要定理。
定理：对任一Set A， A
3-1 集合的概念和表示法
例：若A={a,b,c},写出其所有子集。 解：Ø 、{a}、{b}、{c}、{a，b}、{a，c}、{b，c}、{a，b，c}均是A的子 集

离散数学-集合


例题
利用上例中的公式可以证明对称差A⊕B下列的性质。 设A,B是任意的集合。 ① A⊕A = φ ② A⊕φ = A ③ A⊕E = ~A 证明： ① A⊕A = (A-A)∪(A-A) = φ⊕φ = φ ② A⊕φ = (A-φ)∪(φ-A) = A∪φ = A ③ A⊕E = (A-E)∪(E-A)= φ∪~A = ~A
有限集合的计数
例8 某班有50名学生，第一次考试中26人成绩为优，第二次考试中21人 成绩为优，已知两次考试中都不为优的共17人。问两次考试中都为 优的有多少人？ 解：设A，B分别表示第一次和第二次考试中成绩为优的学生集合。 画出文氏图，如图3.7所示。 首先填A∩B中的人数，这正是要求 的，设为x。 A-B中的人数是26-x，B-A中的人数 是21-x，分别填入对应的区域。并 列出如下方程： (26-x)＋x＋(21-x)＋17=50 解得：x=14
对称差
定义3-2.5 设A，B是集合，由 A中元素或B中元素， 但不是A与B的公共元素组成的集合，称为A和B的对 称差，记为A⊕B。 A⊕B=⎨x|x∈A ∨ x∈B⎬=(A∪B)-(A∩B) A⊕B的定义如图所示。 例6 令A=⎨1,2,3,4⎬，B= ⎨1,2,5,6⎬， 则 A⊕B = A∪B-A∩B = ⎨1,2,3,4,5,6⎬-⎨1,2⎬ = ⎨3,4,5,6⎬
3-2 集合的运算
定义3-2.1 设A，B是集合，由A与B的公共元素组成的集合，称 为A和B的交集，记为A∩B。 A∩B=⎨x|x∈A∧x∈B⎬ 交集的定义如图所示。 从交集的定义可以得到： A∩B⊆A，A∩B⊆B 如果A与B无公共元素，即 A∩B=φ， 称A和B是互不相交的。 例1 令A=⎨a,b,c⎬，B=⎨d,e⎬， 则A∩B=φ，A和B是互不相交的。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

集合的相关概念
1、有限集（finite sets）和无限集（infinite sets） 2、子集： A是B的子集： AB x(xAxB) 称A包含于B；或可记为B A，称B包含A 。 3、真子集：A是B的真子集，记作AB。 AB (x)(xAxB) (x)(xBxA) 4、空集：对任何集合A， A。 5、平凡子集 6、全集:在一定范围内，如果所有集合均为某一个 集合的子集，则称该集合为全集，记为E。
由二项式定理
(x+y)n= C 0 xn + n
Cn
Cn
0
1
xn-1y + …… + C n yn n
取x=y=1,∴ 2n=
∴ |ρ(A)|= 2n
+ C 1n + …… + C n n
3-2 集合的运算
设E为全集，A、B为任意两个集合。令 A∩B ={x|(xA)∧(xB)} A与B的交 A∪B ={x|(xA)∨(xB)} A与B的并 A-B ={x|(xA)∧(xB)} B对于Ａ的补(相对补) ~A= E-A={x|(xE)∧(xA)} A的绝对补 A⊕B =(A-B)∪(B-A)={x|(xA)(xB)} A与B的对称差
定理3-3.1 设A1、A2为有限集合，元素个数分别为 |A1|、|A2|，则|A1∪A2|=|A1|+|A2|-|A1∩A2| （包含排斥原理）
A
B
证明：①当A1∩A2=, 则|A1∪A2|=|A1|+|A2|，成立。 ②当A1∩A2，则 |A1|= |A1∩～A2 |+|A1∩A2|, |A2|= |A2∩～A1|+|A2∩A1| ∴|A1|+|A2|=|A1∩～A2|+|A2∩～A1| +|A1∩A2|+|A1∩A2| 又因为 |A1∪A2|＝|A1∩～A2|+|A2∩～A1|+|A1∩A2| ∴|A1|+|A2|=|A1∪A2|+|A1∩A2| ∴|A1∪A2|=|A1|+|A2|-|A1∩A2|
德· 摩根律的证明:方法２
证：1）任取x∈～(A∪B),则x A∪B ∴ x A 且 x B ∴ x∈～A 且 x∈～B ∴ x∈～A∩～B ∴～(A∪B)～A∩～B 2）任取x∈～A∩～B ∴ x∈～A 且 x∈～B ∴ x A 且 x B ∴ x A∪B ∴ x∈～(A∪B) ∴ ～A∩～B ～(A∪B) ∴ ～(AB)＝～A～B
集合的表示方法
列举法；例：A={a,b,c,d} 叙述法；例：S={x|x>=0,且x为整数} 例：a和b构成的集合。列举法：A={a,b} 叙述法：A={xx=a∨x=b} 注意： 集合的元素可以是集合。例：A={a,b,c,{a,b,c}} 应把单个元素的集合与单个元素区别开来。 例：{a}与a不同；{{1}}与{1}不同；特别地， 与{}不同，前者没有元素，后者是以空集为一 个元素的集合。
集合相等
外延公理 两个集合A和B相等当且仅当它们具有相同的元素。 定理3-1.1 对任意集合A、B，A＝B当且仅当A B 且B A 。(证明过程见书P83，自学)
即对任意集合A，B： A=B x(xAxB)
幂集的元素个数
定理3-1.3 设 A 为一有限集合，A n（A集合 有n个元素），那么 A的幂集ρ(A)的元素个数为2n。 证：A中由m个不同元素(0≤m≤n)做成的不同子集 个数：C m n 故 |ρ(A)|= C 0 + C 1n + …… + C n n n
包含排斥原理（推广定理）
对于任意三个有限集合： |A1∪A2∪A3| = |A1|+|A2|+|A3|-|A1∩A2|-|A1∩A3| －|A2∩A3|+|A1∩A2∩A3| 对于n个任意有限集合： n n |A1∪A2∪……∪An|= A i - A i A j
i 1
1 i< j n
集合的相关概念
7、幂集（Power set）：对任意集合 A，A的幂集 ρ(A) 定义为： ρ(A)＝｛X | XA ｝ A的全体子集构成A的幂集。此种运算称为集合A 的求幂运算。 例1：试求出集合{p,{q}}的幂集。 ρ(A)={ ,{p},{{q}},{p,{q}} } 例2：试求空集的幂集。 ρ()={ }
包含排斥原理举例
例：设某班有60名同学，其中班足球队员有28名， 篮球队员有15名。若有25名同学没有参加这二个队， 问同时参加这二个队的队员有多少名？ 解：设A为足球队员集合，B为篮球队员集合，则 |A∪B|= 60-25 = 35， ∴|A∩B|=|A|+|B|-|A∪B|=28+15-35=8
3-4 序偶与笛卡尔积
由两个元素x和y（允许x=y）按一定顺序排列 成的二元组叫做一个有序对或序偶，记作<x,y>， 其中x是它的第一元素，y是它的第二元素。 序偶相等 给定两个序偶<x,y> 和 <a,b>，当且仅当 x=a 和 y=b 时，序偶 <x,y> 和 <a,b> 相等，亦即： (<x,y> = <a,b>) iff ((x=a)(y=b))的证明: ～(AB)＝～A～B
方法1： 证：～(AB) ＝{ x |x～(AB)} ＝{ x |x(AB)} ＝{ x |(xA)∧(xB)} ＝{ x |(x～A)∧(x～B)} ＝ ～A～B ～(AB) ＝～A～B的证明同上。
分配律的证明:A∩(B∪C)= (A∩B)∪(A∩C)
（根据定理3-1.1,有A=B,iff A B且B A) 证：任取 x A∩(B∪C) 则 xA同时x(B∪C) 则有 xA同时xB 或者 xA同时xC 所以有 xA∩B或者xA∩C 即 x(A∩B)∪(A∩C) ∴ A∩(B∪C) (A∩B)∪(A∩C) 反之，也有(A∩B)∪(A∩C) A∩(B∪C) ∴ A∩(B∪C)= (A∩B)∪(A∩C)
4、 A-B=A∩~B, A-B=A-(A∩B) 5、 A∩(B-C)=(A∩B)-(A∩C)
6、 设A,B为两个集合，若AB,则
~B~A,(B-A)∪A=B
基本集合恒等式
幂等律 结合律
交换律 分配律 同一律 零律
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∩E＝A A∪E＝E A∩ ＝
第三章 集合与关系
本章内容
1. 集合的概念和表示
2. 集合运算 3. 包含排斥原理 4. 序偶与的卡尔积 5. 关系及其表示 6. 关系的性质
7. 复合关系和逆关系
8. 关系的闭包运算 9. 集合的划分与覆盖 10. 等价关系与等价类 11. 相容关系
12. 序关系
3-1 集合的概念和表示法
集合是不能精确定义的基本概念。直观地说， 把一些事物汇集到一起组成一个整体就叫集合，而 这些事物就是这个集合的元素或成员。 例如： 方程x2－1＝0的实数解集合； 26个英文字母的集合； 坐标平面上所有点的集合； ……
+
n
Ai A j Ak
1 i< j< k n
+…+(-1)n-1A1∩A2∩……∩An
包含排斥原理举例
例:试统计在1到100之间能被2,3,5中某一数整除的 所以|A1∪A2∪A3|=|A1|+|A2|+|A3|-|A1∩A2|数的个数。 |A1∩A3|- |A2∩A3|+|A1∩A2∩A3| 解：A1表示1到100之间能被2整除的整数集， =50+33+20-16-10-6+3=74 A2表示1到100之间能被3整除的整数集， A3表示1到100之间能被5整除的整数集， 则|A1|=int(100/2)=50，|A2|=int(100/3)=33， |A3|=int(100/5)=20， |A1∩A2|=int(100/(2*3))=16， |A1∩A3|=int(100/(2*5))=10， |A2∩A3|=int(100/(3*5))=6 |A1∩A2∩A3|=int(100/(2*3*5))=3
集合不仅可用来表示数及其运算，更可以用于 非数值信息及离散结构的表示和处理。像数据的删 节、插入、排序，数据间关系的描述，数据的组织 和查询都很难用传统的数值计算来处理，但可以用 集合运算来实现。集合论被广泛应用在计算机科学 中，如数据结构、操作系统、数据库、知识库、编 译原理、形式语言、程序设计、人工智能、信息检 索、CAD等。
三元组
三元组
三元组是一个序偶，它的第一个成员是一个
序偶，可记为：<< x,y>,z>,可简写为：<x,y,z> 两个三元组相等：
<x,y,z> = <u,v,w>
(x=u) ∧ (y=v)∧ (z=w) 注意：<<x,y>,z><x,<y,z>>
n元组
n元组 n元组是一个序偶，它的第一个成员是一个 (n-1) 元组，并可记为：<< x1,x2 ,...,xn-1 >,xn>, 可简写为：<x1,x2 ,...,xn-1,xn> 两个n元序组相等： <a1，… , an> = <b1，… , bn> (a1=b1) ∧ …∧ (an=bn)
各种运算的文氏图
集合举例
例：E={1,2,3,4,5}, A = {1,3,4}, B = {3,5} A∩B ={3} A∪B = {1，3，4，5} A-B = {1，4} B-A = {5} A⊕B = {1,4,5} ~A= {2,5} ~B= {1,2,4}