离散数学集合与关系共28页

离散数学关系
基本要求和重难点:
• 基本要求
了解序偶与笛卡尔积,掌握关系得性质和运算,重 点掌握关系闭包运算得求法和偏序关系及哈斯图 得正确画法。
• 重难点
关系5种性质得判断,关系得闭包运算和偏序关系 得性质及特殊元素得判断。
引言
日常生活中,大家熟知一些常见关系, 例:家庭集合,有父子关系、夫妻关系等。 全校同学作为一个集合,有同班关系,同组关系。 在计算机科学中,在计算机逻辑设计中,应用了等 价关系,相容关系。 在编译原理、关系数据库、数据结构、数学中也有 关系。
例题
返回第5、3节目录
五、传递性例题
例: A={1,2,3,4} R={<1,4>,<4,3>,<1,3>,<3,1>,<1,2>,<3,2>,<2,3>, <4,2>,<1,1>,<3,3>} R不就是传递得
返回传递性
返回第5、3节目录
六、举 例
自反性 反自反性 对称性 反对称性 传递性
任何集合上得
返回总目录
一、自反性
自反性
定义: 若xA,均有xRx,那么称R就是自反得。
A上关系R就是自反得x(xA xRx)
在关系矩阵中,反映为主对角线元素均为1 在关系图中,反映为每结点都有自回路 例1: A＝{1,2,3},R={<1,1>,<2,2>,<3,3>,<1,2>}
1 23
例2:“＝”关系和“≤”关系就是自反得吗？
S={<4,2>,<2,5>,<3,1>,<1,3>}

其中P(x)为任何谓词公式。 如：A={x|x∈R ∧ x2+1=0}。 该方程无实数解。 注意： φ ≠{φ } 由定义可知，对任何集合A，有A。这是因为任意元素x，公式xxA总是 为真。
第23页/共193页
注意： 与{}是不同的。 {}是以为元素的集合， 而没有任何元素，能 用构成集合的无限序列： ，{}，{{}}，···
例 设A={{1,2,3}, 1,2,3}， 则 {1,2,3} A 且 {1,2,3} A 。
第27页/共193页
重要结论
➢对任意集合A, 有A A。 ➢空集是任意集合的子集，且空集是唯一的。 ➢对于任意两个集合A、B，A=B的充 要条件是AB且BA。（这个结论非常简单， 但它非常重要，很多证明都是用这个Fra bibliotek法或思路来证明。）
第2页/共193页
集合的基本概念
例:
1. 二十六个英文字母可以看成是一个集合；
2. 所有的自然数看成是一个集合； 3. 重庆邮电大学计算机学院2010级的本科学生可以看成是一个集合； 4. 这间教室中的所有座位可以看成是一个集合。
第3页/共193页
集合的元素
组成一个集合的那些对象或单元称为这 个集合的元素。通常，用小写的英文字母a, b, c,…表示集合中的元素。元素可以是单 个的数字也可以是字母，还可以是集合。
下列选项正确的是（ 3 ）；
（1） 1A
（2）{1,2,3} A
（3）{{4,5}} A （4） ØA
例3.4 下列各选项错误的是（2）；
（1） Ø Ø
（2） Ø Ø
（3） Ø { Ø }
（4） Ø { Ø }
例3.5 在0 ___ Ø 之间填上正确的符号：（4）

(A×B)×C≠A×(B×C) (当A≠∧B≠∧C≠时)
(4)笛卡儿积运算对并和交运算满足分配律，即
A×(B∪C)=(A×B)∪(A×C) (B∪C)×A=(B×A)∪(C×A)
A×(B∩C)=(A×B)∩(A×C) (B∩C)×A=(B×A)∩(C×A)
(5) AC∧BDA×BC×D
3
我们给出性质(4)第一个式子的证明。
说明:(1)把关系这种“无形”的联系用集合这种“有形”的实体来描述。
(2)有序对是讲究次序的。
8
on numbers: a=b a<b a≥b
on integers: a|b on subsets: A B
|A|=|B| on people: a is married to b
a is younger than b a is a descendant of b.
例7 求集合A＝｛1,2,3,4｝上的恒等关系、空关系、 全域关系和小于关系，并画出小于关系的关系图。
16
例7 求集合A＝｛1,2,3,4｝上的恒等关系、空关系、 全域关系和小于关系，并画出小于关系的关系图。
IA={<1,1>,<2,2>,<3,3>,<4,4> } EA={ <1,1>,<1,2>,<1,3>,<1,4>,
定义3.16 设A,B,C是三个任意集合,R是A到B的二元关系,S是B到C 的二元关系，则定义关系R和S的合成或复合关系 RοS＝{<a,c>| aA,cC ∧ bB,使 <a,b>R且<b,c>S }。
例11 集合A＝{a,b,c},B＝{1,2,3}，R是A上关系，S是A到B

第1章 集合
1.3 集合的运算
1.3.2 集合的交运算
定理1.3
设A，B，C是三个集合，则下列分配律成立： A∩（B∪C）＝（A∩B）∪（A∩C） A∪（B∩C）＝（A∪B）∩（A∪C）
定理1.4 设A，B为两个集合，则下列关系式成立： A∪（A∩B）＝A A∩（A∪B）＝A
这个定理称为吸收律，读者可以用文氏图验证。
A＝B，C＝D
第1章 集合
1.2 集合之间的关系
定理1.1 集合A和集合B相等的充分必要条件是A⊆B且B⊇A。 定义1.3 如果集合A是集合B的子集，但A和B不相等，也就 是说在B中至少有一个元素不属于A，则称A是B的真子集，记作
A⊂B 或 B⊃A 例如：集合A＝｛1，2｝，B＝｛1，2，3｝，那么A是B的真子集
A∩B＝｛1，3，5｝
第1章 集合
1.3 集合的运算
1.3.2 集合的交运算 集合的交运算的文氏图表示，见图3.2，其中阴影部分就是A∩B。
U
A
B
第1章 集合
1.3 集合的运算
1.3.2 集合的交运算 由集合交运算的定义可知，交运算有以下性质： （1）幂等律：A∩A＝A （2）同一律：A∩U＝A （3）零律：A∩＝ （4）结合律：(A∩B)∩C＝A∩(B∩C) （5）交换律：A∩的运算
1.3.2 集合的交运算 定义1.7 任意两个集合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｝，则
定义1.4 若集合U包含我们所讨论的每一个集合，则称U是所讨论 问题的完全集，简称全集。

则ρ 的关系图如下 A B
13
例如 例3中的 A {1,2,3,4} ，
{(1,1), (1,2 ), (1,3 ), (1,4 ), ( 2,2 ), ( 2,4 ), ( 3,3 ), ( 4,4 )}
的关系图如下：
14
练习3-6
1. 设A
{0,1,2}，B {0,2,4} ，A到B的关系
B {1,2}
。 }
A B {
(0,1), (0,2), (1,1), (1,2) (1,1), (1,2 ), ( 2,1), ( 2, 2)
B B {
}
8
关系的表示
一、集合表示法
用表示集合的列举法或描述法来表示关系。
例1 设A { 2,3,4,8},B {1,5,7 } , 用描述 } 法定义由A到B的关系 {( a, b ) | a b，试
用列举法将
表示出来。
解
{( 2,5 ), ( 2,7 ),( 3,5 ), ( 3,7 ) ( 4,5 ), ( 4,7 )}
9
例2 有王、张、李、何是某校的老师，该校有
三门课程：语文、数学和英语，已知王可以教语文 和数学，张可以教语文和英语，李可以教数学，何 可以教英语，若记A={王，张，李，何}，B={语文， 数学，英语}。那么这些老师与课程之间的对应关系 就可以用由A到B的一个关系
3利用关系图求复合关系是有限集a上的关系则复合关系也是a上的关系由复合关系的定义对于任意的反映在关系图上这意味着当且仅当在的关系图中有某一结点存在使得有边由指向且有边由指向的关系图中有边从指向理同志关系上搞庸俗关系学热衷于迎来送往
1Байду номын сангаас

表示元素之间的顺序关系，如 大小关系、前后关系等。
等价关系
表示元素之间具有相同性质的 关系，等价关系具有自反性、 对称性和传递性。
偏序关系
表示元素之间的部分顺序关系 ，偏序关系具有自反性、反对
称性和传递性。
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}

（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的子 集

满射。
双射
03
如果一个映射既是单射又是满射，则称该映射为双射。
函数的基本性质
确定性
对于任意一个输入，函数只能有一个输出。
互异性
函数的输出与输入一一对应，没有重复的输 出值。
可计算性
对于任意给定的输入，函数都能计算出唯一 的输出值。
域和陪域
函数的输入值的集合称为函数的定义域，函 数输出的集合称为函数的陪域。
04
集合的运算性质
并集运算性质
并集的交换律
对于任意集合A和B，有A∪B=B∪A。
并集的幂等律
对于任意集合A，有A∪A=A。
并集的结合律
对于任意集合A、B和C，有 A∪(B∪C)=(A∪B)∪C。
并集的零律
对于任意集合A和空集∅，有A∪∅=ቤተ መጻሕፍቲ ባይዱ。
交集运算性质
交集的交换律
对于任意集合A和B，有A∩B=B∩A。
在数学中的应用
集合论
集合论是数学的基础，它为数学提供了基本的逻辑和概念 框架。通过集合，可以定义和讨论概念、关系和性质等。
概率论
在概率论中，集合用来表示事件，事件发生的概率可以定 义为该事件所对应的集合的元素个数与样本空间所对应的 集合的元素个数之比。
拓扑学
拓扑学是研究几何形状在大范围内变化的学科。在拓扑学 中，集合用来表示空间中的点、线、面等元素，以及它们 之间的关系。
THANKS FOR WATCHING
感谢您的观看
03
集合的分类
有穷集和无穷集
有穷集
集合中元素的数量是有限的，可以明 确地列举出集合中的所有元素。例如 ，集合{1, 2, 3}是一个有穷集。
无穷集
集合中元素的数量是无限的，无法列 举出集合中的所有元素。例如，自然 数集N={1, 2, 3,...}是一个无穷集。

Φ {Φ}


第22页
3、幂集 引例：求集合的子集及子集的个数
例



A 子集 子集个数 Φ Φ 1 {a} Φ,{a} 2 {a,b} Φ,{a},{b},{a,b} 4 {a,b,c} Φ,{a},{b},{c},{a,b}, {a,c}, {b,c}, {a,b,c} 8 一般来说，对于n个元素的集合A，它的不同的子集 总数有：
0 2 ＋ Cn ＋ C1 C n n ＋…… ＋

Cn n

＝(1+1)n＝2n 所以，n元集共有2n个子集。
第23页
一般来说，对于n个元素的集合A，它的不同的子 集总数有 0 1 2 n
Cn ＋ Cn
＋ C n ＋…… ＋
Cn
而 1 n-1 n n n x n-2y2 ＋… ＋ ＋ (x+y)n= C 0 C n x y ＋ C2 n x C n n y 令x=y=1时得 0 n 2 n ＋ 2 = Cn ＋ C1 ＋ …… ＋ C C n n n 所以不同子集总数有 2n
文氏(Venn)图-辅助的集合的表示方法
第6 页
1、枚举法（显式表示法）

就是把集合的元素（全部或部分）写在花括号的里面， 每个元素仅写一次，不考虑顺序，并用”,”分开。 例 （1）命题的真假值组成的集合：S={T,F} （2）A＝{a，e，i，o，u}
第7 页
在使用中，分两种情况：
（1）当集合中元素个数有限且较少时，将元素全部写出。 例1：设集合A是由绝对值不超过3的整数组成。 A={-3, -2, -1, 0, 1, 2, 3} （2）当集合A元素的个数无限或有限但个数较多时，不 能或不需要一一列举出来，只要写出少数元素，以显示 出它的规律。（当规律不明确，不能用此方法）。 例2：设集合B是由自然数的平方构成的集合。 B = {0, 1, 4, 9, 16, …, n2, …}

离散数学 14
2019/1/15
空集

空集：没有任何元素的集合。

对任一集合A， 有A
A x(x∈→x∈A)
空集是唯一的。 若存在空集 1 ，2 ，由以上定理

1 2 ∧ 2 1 1 ＝ 2
2019/1/15
离散数学
15
例：设a,b,c 各不相同，判断下述等式中哪个等式 成立。
2019/1/15
离散数学
33
集合运算的主要运算律
排中律： A ~A＝E 矛盾律： A~A＝ 吸收律： A (AB)＝A A(A B)＝A 德· 摩根律： A(B C)＝(AB)(AC) A(BC)＝(AB)(AC) ~(B C)＝~B~C ~(BC)＝~B ~C ~＝E ~E＝ 双重否定律： ~(~A)＝A 补交转换律: A－B＝A ∩ ~B
20
练习
例1：集合A为以空集为唯一元素的集合， B = ρ(ρ(A))，判断下列式子是否正确。 （1） ∈ B （2） B （3）{} B （4）{{} ，{{}}} B （5）{ ，{{}}} ∈ B

解: A={}, P(A)={,{}} P(P(A))={,{},{{}},{,{}}}
离散数学 5
2019/1/15
例如，集合A＝{a，{b，c}，d，{{d}}}
这里a∈A，{b，c}∈A，d∈A，{{d}}∈A，但是 b A , {d} A. b 和 {d}是A的元素的元素.


2019/1/15
离散数学
6
常用集合符号
N：全体自然数的集合,
称作自然数集; Z：全体非负整数的集合, 称作非负整数集; I： 全体整数的集合, 称作整数集; P：全体素数的集合, 称作素数集; Q：全体有理数的集合, 称作有理数集; R：全体实数的集合, 称作实数集; C：全体复数的集合, 称作复数集;

(A×C)∪(A×D)∪(B×C)∪(B×D)
32
本章主要掌握集合的谓词表示法，和集合的 基本运算，以及序偶的概念，集合的笛卡尔 集，及相关定理。定理的证明相对简单，所 以证明略。
对于数学归纳法，由于中学就已学过，所以 这里就省略。
33
思考题：
1 AB与AB能同时成立吗？ 2 何为一个集合的幂集，含有n个元素的集合，其
有序偶:它不仅与含有的元素x，y有关，还与x，y出现的次序有关。
这样的偶集称为有序偶，并记为：<x,y>
例如，用<x，y>表示平面直角坐标系下的横坐标为x且纵 坐标为y的点时，则<x，y>和<y，x>在xy时就代表不 同的点，因而就不相同。
25
用集合定义有序偶
定义1 有序偶的集合定义：若x，y为任意两个元素， 令 <x，y>={{x}，{x，y}}
6
例1 如果论域是整数集I，那么能被3整除的正整数集合S 用归纳法可定义如下：
（1）（基础）3S， （2）（归纳）如果xS和yS，则x+yS
7
集合的特殊情况
1、不含任何元素的集合称为空集，记为φ 2、含讨论问题所需全部元素的集合称为全集，记为∪ 3、 称含有有限个元素的集合为有限集合 4、 含有无限个元素的的集合称为无限集合或无限集 5、 集合A中元素的个数（或基数或集合的势）记为:|A|
(A=B 当且仅当AB 且 BA） 3)集合的包含关系具有传递性:即
若A B且B C，则A C
9
大家有疑问的，可以询问和交流
可以互相讨论下，但要小声点
10
子集的两种特殊情况（平凡子集）： 1）空集是任一集合的子集。 2）任何集合都是它自己的子集。

第11页
练习：
给定X上相容关系r’ ，如图所示, r’所有的最大相容类： x 2 {x1,x2,x5}, {x2, x3, x5}, x1 {x3, x4,x5}, {x1,x4 ,x5},

x3 x4


x5
第12页
x 。 x2。 3 x。
2
四、完全覆盖
定义3-11.5
x1。 。 x 1 x7。
第4 页
（2）R的有向图： 每个结点自回路，两个节点间有边则双向。自反、对称
any y y able
（3）R的关系矩阵：
fly
fit
f
l y
1111001 1111000 b MR = 1 1 1 1 1 0 0 k key 1111100 book pump 0011100 0000010 1000001 R主对角线全1，关于主对角线对称。
第8 页
定义3-11.3

设r是集合A上的相容关系，C是r的一个相容类， 若C不能真包含于任何其它相容类中，则称C是一 个最大相容类，记作：Cr。

也可以说，C是一个相容类，若C中加入任意一 个新元素，就不再是相容类，C就是一个最大相 容类。 x2。 {x1,x2,x3,x4} , {x3, x4, x5}, {x 1,x7} , {x6}都是最大相容类。 x1。 。 x3 x4。 x7。 x5。 x6。
R1=R2,不同覆盖产生相同的相容关系
定理：集合A上相容关系 r 与完全覆盖Cr(A)存在一一 对应。
第14页


本节要求：相容关系、相容类概念，画图，求完全覆 盖。 作业 第139页 (2)
第15页
也可以说c是一个相容类若c中加入任意一个新元素就不再是相容类c就是一个最大相x3x4x5x1x72最大完全多边形的顶点集合构成最大相容类

R8
2
。 。 3
R5
R5
。 。 2。 。 3 3 2。 。 3
R6 R7 对称性 Y 反对称性 Y 反自反性 N 传递性 Y
自反性 Y
R6 R7 R8
N Y N
N N Y
Y Y Y
N N Y
N Y Y
恒等关系是自反的、对称的、反对称的、传递的。 全关系是自反的、对称的、传递的。 空关系是反自反的、对称的、反对称的、传递的。 若X= Φ，则X上的空关系Φ：自反、反自反的、对称的、 反对称的、传递的。
例 自反
2
1
。
反自反
1
。
自反 1
2
。
1
。自反
。 。 3
R1
1
2
。 。 3
R2
1
。 。 。 2。 3 3
R3
1
反自反
2
。
。 。 3
R5
非自反 非反自反
2
。
2
。
非自反 非反自反
R4
1
。反自反
R8
。 。 3
R6
。 。 2。 。 3 3
R7

R1、R3、R4是自反的，R2、R5、 R8均是反自反关系。 注意：任何一个不是自反的关系，未必是反自反的， 任何一个不是反自反的关系，未必是自反的， 如R6、R7非自反，也非反自反。 存在既不是自反的也不是反自反的关系。
第7 页
三、对称性

定义：R是集合A上的关系，若对任何x, y∈A，若有 <x,y>R，必有<y,x>R ，则称R为A中的对称关系。 R是A上对称的 (x)(y)((xA∧yA∧<x,y>R) <y,x>R)