当前位置：文档之家 › 离散数学 关系4---文本资料

离散数学 关系4---文本资料

  • 格式：ppt
  • 大小：2.75 MB
  • 文档页数：63

下载文档原格式

  / 63

合集下载

离散数学第四章-一阶逻辑基本概念

离散数学第四章-一阶逻辑基本概念
谓词常项 如, F(a)：a是人 谓词变项 如, F(x)：x具有性质 n（n1）元谓词——含n个命题变项的谓词，
记作F(x1,x2… … xn) 一元谓词(n=1)——表示性质 多元谓词(n2)——表示事物之间的关系 例如, L(x,y)：x与 y 有关系 L，L(x,y)：xy，…
0元谓词——不含个体变项的谓词.实际上就是一般的命题
第四章 一阶逻辑基本概念 一阶逻辑命题符号化 一阶逻辑公式及其解释 第五章 一阶逻辑等值演算与推理 一阶逻辑等值式与基本的等值式 置换规则、换名规则、代替规则 前束范式
自然推理系统NL及其推理规则
2021/4/6
3
第四章 一阶逻辑基本概念
主要内容
一阶逻辑命题符号化
个体词、谓词、量词 一阶逻辑命题符号化
x : 个体域中有一个个体x xF(x)表示个体域中有一个个体x具有性质F
2021/4/6
11
量词
全称量词: 表示所有的.
存在量词: 表示存在, 有一个.
xF(x)表示个体域中所有的x具有性质F xF(x)表示个体域中有一个个体x具有性质F xyG(x,y) 表示个体域中所有的个体x和y有关系G xyG(x,y) 表示个体域中存在个体x和y有关系G xyG(x,y) 表示对个体域中每一个x都存在一个y使得
x(F(x)y(G(y)L(x,y))) 或者 xy(F(x)G(y)L(x,y))
(2) 令F(x)：x是无理数，G(y)：y是有理数，L(x,y)：x>y
x(F(x)y(G(y)L(x,y))) 或者 xy(F(x)G(y)L(x,y))
2021/4/6
一阶逻辑公式及其解释
一阶语言 合式公式 合式公式的解释 永真式、矛盾式、可满足式

《离散数学》课件-第四章 二元关系

《离散数学》课件-第四章 二元关系
则关系R的各次幂为： R0 =A ={<1,1> ， <2,2> ， <3,3> ， <4,4> ， <5,5>} R1=R
R2= R • R={<1,1>，<2,2>，<1,3>，<2,4>， <3,5>}
R3=R2 • R={<1,2>，<2,1>，<1,4>，<2,3>， <2,5>}
R4= R3 • R={<1,1>，<2,2>，<1,5>，<2,4>，
从关系图来看关系的n次幂
R：
1
2
3
4
5
R2：
1
2
3
4
5
R2就是从R的关系图中的任何一个结点x出发，长 为2的路径，如果路径的终点是y，则在R2 的关系 图中有一条从x到y的有向边。其他以次类推：
R3：
1
2
3
4
5
R4：
1
2
3
4
5
定理 设|A|=n，R A×A，则必有i，j∈N， 0≤i＜j≤2n2，使得Ri=Rj。
＝R5，R7＝R6•R＝R5，…，Rn＝R5 (n＞5) 故Rn{R0,R1,R2,R3,R4,R5}。
S0=IA,S1＝S,
S2＝S•S＝{<a,c>,<b,d>,<c,e>,<d,f>}， S3＝S•S•S＝S2•S＝{<a,d>,<b,e>,<c,f>}， S4＝S3•S＝{<a,e>,<b,f>}， S5＝S4•S＝{<a,f>}， S6＝S5•S＝Φ， S7＝Φ， …， 故，Sn{S0,S1,S2,S3,S4,S5,S6}

离散数学 第4章 关系

离散数学 第4章 关系
11
实例
例3 (1) R={<x,y> | x,yN, x+y<3} ={<0,0>, <0,1>, <0,2>, <1,0>, <1,1>, <2,0>} (2) C={<x,y> | x,yR, x2+y2=1}，其中R代表实数集合， C是直角坐标平面上点的横、纵坐标之间的关系， C中的所有的点恰好构成坐标平面上的单位圆. (3) R={<x,y,z> | x,y,zR, x+2y+z=3}， R代表了空间直角坐标系中的一个平面.
A×(B×C)=1,2×a,x,a, y,b,x,b, y =1,a,x,1,a, y,1,b,x,1,b, y 2,a,x,2,a, y,2,b,x,2,b, y 显然A×B×C≠A×(B×C)。
8
⑴ A×(B∪C) =(A×B)∪(A×C) 证明：仅证明⑴ 任取a,b a,bA×(B∪C) aA∧bB∪C aA∧( bB∨bC) (aA∧bB)∨(aA∧bC) a,bA×B∨a,bA×C a,b(A×B)∪(A×C) 故 A×(B∪C)=(A×B)∪(A×C) 可类似地证明⑵、⑶、⑷。
12
5元关系的实例—数据库实体模型
员工号 301 302 303 304 … 姓名 张 林 王晓云 李鹏宇 赵 辉 … 年龄 50 43 47 21 … 性别 男 女 男 男 … 工资 1600 1250 1500 900 …
5元组： <301,张林,50,男,1600>，<302,王晓云,43,女,1250>
关系的表示
表示方式：关系的集合表达式、关系矩阵、关系图
定义4.8 关系矩阵 若A={x1, x2, …, xm}，B={y1, y2, …, yn}， R是从A到B的关系，R的关系矩阵是布尔矩阵MR = [ rij ] mn, 其中 rij = 1 < xi, yj> R. 定义4.9 关系图 若A= {x1, x2, …, xm}，R是从A上的关系， R的关系图是GR=<A, R>, 其中A为结点集，R为边集.如果 <xi,xj>属于关系R，在图中就有一条从 xi 到 xj 的有向边. 注意：设A, B为有穷集 关系矩阵适合于表示从A到B 的关系或者A上的关系 关系图适合于表示A上的关系

离散数学第四章(关系)

离散数学第四章(关系)

例： （1）自然数集N上的小于或等于关系≤ 是自反关系；一族集合B 中的包含关系 是B 中的自反关系。 （2）自然数集N上的小于关系＜是反自 反关系；一族集合B 中的真包含关系 是B 中的反自反关系。
问：集合A上的恒等关系IA 是A上的自反关系吗？
集合A上的恒等关系IA是集合A上一 个自反关系。 集合A上的恒等关系IA是集合A上所 有自反关系R的子关系：IA R
主对角线元素 主对角线元素 主对角线元素 例：设A={a,b,c} ， 全为 1 R1={(a,a) R是 ， 全为 0， R是 既有 ，也有1 (b,b) (c,c) ，(a,b) ，0 (c,a)} 自反关系。 反自反关系。 R既非自反 R2={(a,b)， (b,c)，(c,a)} R3={(a,a),(b,c)} 的，也非反自 反的关系。
1 2 1 2 3 4 5 6 7 √ √ √ √ √ √ √ √ √ 3 4 √ √ √ √ 5 6 7 √
√
√
√
（3）矩阵表示法
例：设A={a1,a2,a3,a4,a5},B={b1,b2,b3}, R是A到B的二元关系。且 R={<a1,b2>,<a2,b3>,<a3,b1>,<a4,b3>,<a5,b2>} 则R的矩阵表示如下： b1 b2 b3 0 1 0 1 0
如果<a,b>R, 就说 a 与 b 有关系R, 并记为 aRb ; 如果<a,b>R, 就说 a 与 b 没有关系R, 并记为aR′b
例 设A={a,b,c,d}，B={x,y,z},则 A×B={<a,x>,<a,y>,<a,z>,<b,x>,<b,y>,<b,z>, <c,x>,<c,y>,<c,z>,<d,x>,<d,y>,<d,z>} 令R={<a,y>,<b,x>,<b,y>,<d,x>}，由于R是A×B 的子集，所以R是从A到B的一个二元关系。 A={a,b,c,d}是R的前域， B={x,y,z}是R的陪域。 R的定义域为 dom(R)＝{a,b,d}, R的值域为 ran(R)＝{x,y}。

离散数学-第四章 代数系统

离散数学-第四章 代数系统

(r1 r2 r1r2 ) r3 (r1 r2 r1r2 )r3
r1 r2 r3 r1r2 r1r3 r2 r3 r1r2 r3
r1 (r2 r3 ) r1 (r2 r3 r2r3 )
(r1 r2 r3 r2 r3 ) r1 (r2 r3 r2 r3 ) r1 r2 r3 r2 r3 r1r2 r1r3 r1r2 r3
1 3 5 7
7 5 3 1
1 3 5 7
1 3 5 7 3 3 5 7 5 3 5 7 1 7 3 7
6
三、运算的封闭性
定义在集合A上的运算在A上一定是封闭的. 定义在集合A上的运算在A的子集上是否封闭呢？
例５ 定义函数 : N N ，使 (n1 , n2 ) n1 n2
2
令S
(b, a, a), (b, a, b), (b, b, a), (b, b, b)}
2
f : An A ，于是对于 A n 设有集合 A和函数 中的每一个有序 n元组 (a , a ,, a ) ,在 A 中必有 1 2 n 唯一个元素 a与之对应，即 f (a1 , a 2 , , a n ) a
er er el ， 令 e el er ，则 e 是 的单位元。 设 e 也是 的单位元， 则 e e e e 因此 e 是 的唯一的单位元。
因此， el
18
2． 零元
是集合A上的二元运算，若存在一元 素 z l A ，使得对于任意的 a A ,有 z l a z l ， 则称 z l是A中运算 的左零元；若存在一元素 ， 使得对于任意的 , zr a A a,则称 z是A中 zr A r 运算 z r 的右零元，若存在一元素 ，使得对于任 意 z A, a,则称Z是A中运算 z 的零 A z a a z 元。

离散数学第四章(第1讲)

离散数学第四章(第1讲)
xy??a??bc?xy??xyx??a??y??bc?xy??xyx??a??y??b??y??c?xy??xyx??a??y??b??x??a??y??c?xy??a??ba??c即a??bca??ba??c例
第四章 二元关系
§1 序偶与笛卡尔积 §2 关系及其表示 §3 关系的性质 §4 关系的运算 §5 等价关系与划分 §6 相容关系与覆盖 §7 偏序关系
§1 序偶与笛卡尔乘积
1 序偶 《定义》由二个具有给定次序的客体所组成的序列
称为序偶。记作〈x，y〉 例：X—Y二维平面上的一个点的坐标〈x，y〉就
是一个序偶。
说明： (1)在序偶中二个元素要有确定的排列次序。 若ab时，则〈a，b〉〈b，a〉 若〈x，y〉=〈a，b〉（x=a y=b） (2) 多重序元： 三元组：〈〈x，y〉，z〉 =〈x，y，z〉 n元组： 〈〈〈〈x1，x2〉，x3〉…〉，xn〉= 〈x1,…,xn〉
ran R={a,b,c,d}
FLD R={1,2,3,4,a,b,c,d}
４．关系和笛卡尔乘积 笛卡尔乘积的任何子集都可以定义一种二元关系。 例：X={1,2,3,4}，Y={1,2}
X Y {1,1 ,1,2 , 2,1 , 2,2 , 3,1 , 3,2 , 4,1 , 4,2 }
S1={<x,y>|x X yYx ≤ y}={<1,1><1,2><2,2>}
2 笛卡尔乘积 《定义》设A，B为二个任意集合，若序偶的第 一个成员（左元素）是A的一个元素，序偶的 第二个成员（右元素）是B的一个元素，则所 有这样的序偶构成的集合称为A和B的笛卡尔乘 积。
记作：A B={〈x，y〉|（xA）（yB）}

离散数学第4章 关系

离散数学第4章 关系

例4-1.2 集合A={a，b}，B={c，d}，试写出从 A到B的所有不同关系。 解：A×B={<a，c>，<a，d>，<b，c>，<b， d>}。于是A×B上的所有16个不同的关系： 关系中包含0个元素：； 关系中包含1个元素：{<a，c>}，{<a，d>}， {<b，c>}，{<b，d>}； 关系中包含2个元素：{<a，c>，<a，d>}， {<a，c>，<b，c>}，{<a，c>，<b，d>}， {<a，d>，<b，c>}，{<a，d>，<b，d>}， {<b，c>，<b，d>}；
（5）R是传递的
(x)(y)(z)(x，y，zAxRyyRz→xRz) R的关系矩阵(rij)n×n中对任意的i,j,k有, 若 rik＝1且rkj＝1则rij＝1 （当X是有限集 合）。 R的关系图中任意一条长度为2的路径都有从 其起始顶点到终止顶点的边（当X是有限集合）。
(3)关系矩阵:X＝﹛x1,x2,…,xn﹜到
Y=﹛y1,y2,…,ym﹜的关系R的关系矩阵为 MR＝(aij)n×m 1, 若xiRyj 其中 aij ＝ 0, 若xiRyj
(4)关系图:
X＝﹛x1,x2,…,xn﹜到Y ＝ ﹛y1,y2,…,ym﹜的关 系R的关系图为：分别在左右两列用小圆圈列出的X中的n个元 素和Y中的m个元素，若xiRyj，则从xi到yj画一条有向边。如右 图所示 X＝﹛x1,x2,…,xn﹜上的关系图为：在平面上用小 圆圈列出的X中的n个元素（位置不限），若xiRXj,则从xi到xj 画一条有向边。如左图所示 X Yy 1 x 1 x3 x2 x2 y2 x1 xn xn

离散数学 第四章 关系

离散数学 第四章 关系

若ai Rbj 若ai Rbj
矩阵MR 称为R的关系矩阵。
17
第四章 关系
4.1 二元关系
例：设A={1，2，3，4}，A上的关系R={<x,y>|y是x 的整数倍}，故R={<1,1>,<1,2>,<1,3>,<1,4>,<2,2>,<2, 4>,<3,3>,<4,4>}.
1 2 3 4
1 1 2 0 MR 3 0 4 0
2
第四章 关系
4.1 二元关系
4.1.1 基本概念
4.1.2 关系的表示
3
第四章 关系
4.1 二元关系
4.1.1 基本概念 1)定义： A×B的子集叫做A到B上的一个二元关系。 A1×A2×A3的子集叫做A1×A2×A3上的一个三元 关系。 A1×A2×…xAn的子集叫做A1×A2×… × An上的 一个n元关系。 A×A×A ×… × A的子集叫做A上的n元关系。
1 1 0 0
1 0 1 0
1 1 0 1
18
第四章 关系
4.1 二元关系
3.关系图表示法
关系图由结点和边组成
若A= {x1, x2, …, xm}，R是A上的关系，R的关系图是 GR=<A, R>，其中A为结点集，R为边集。如果<xi,xj> R，在图中就有一条从 xi 到 xj 的有向边；如果<xi,xi> R，在图中就有一条从 xi 到 xi 的有向边。
12
第四章 关系
4.1 二元关系 4)关系的个数： 2，A×A的子集有 2 n 个。 假设|A|=n，|A×A|=n 2n 所以 A上有 个不同的二元关系。

离散数学讲义(第4章)

离散数学讲义(第4章)
16
4-4 基数的概念（续）
Peano公理：
（1）0N，（其中0=） （2）如果0N，则n+N（其中n+=n∪{n}）
（3）如果一个子集S N具有性质：
（a） 0S （b）如果nS，有n+S 则S=N
注：
1）性质（3）称极小性质，指明了自然数系统的最小性。 即自然数系统是满足公理（1）（2）的最小集合。 2）自然数也可不从0开始，只需定义=1即可。
证明：令f：PS，f(x)=tg-1x/p+1/2 (- ∞ <x< ∞)
显然f的值域是S，且f是双射函数。
18
4-4 基数的概念（续）
定理：在集合族上等势关系是一个等价关系。 证明：设集合族为S a）对任意的A S，必有A A b）若A,B S，如果A B，必有B A c）若A,B,C S，如果A B，B C，则有A C 定义：如果有一个从集合{0,1,…,n-1}到A的双射函数，那 么称集合 A 是有限的；如果集合 A 不是 有限的 ，则它是 无 限的。 定理：自然数集合N是无限的。 证明：设 n 是 N 的任意元素，f 是任意的从 {0,1,…,n-1} 到 N 的函数。设k=1+max{f(0),f(1),…,f(n-1)} ，那么k N， 但对每一个x {0,1,…,n-1}，有f(x) k。因此f不能是满 射函数，即f也不是双射函数。因为n和f都是任意的，故N 是无限的。
注：一般有h (g f) = (h g) f，即函数的复合是可结 合的。因此可以将括号去掉。
12
4-2 逆函数和复合函数（续）
定义：函数f：X Y称作常函数，如果存在某个y0 Y， 对于每个x X，都有f(x)=y0，即f(X)={y0}。 定义：如果Ix={〈x,x〉|xX}，则称函数Ix：X X为恒 等函数。

离散数学-第四章 关系-内容提要

离散数学-第四章 关系-内容提要

{}
传递。
(5)如 果 VJ
:IT{∶ ∶ ∶ ∶ 蚕 ⒈11∶⒈ ∶ Ll ;, 翕 罐 ∶ ∶ ∶ 置 R在 A上
:I∶
:: 1∷
Vj V石
(Π
、 、 y,z)∈ R→ 〈 R∧ 〈 J,z〉 ∈ R),则 称 Π ,y,z∈ A∧ 〈 ,j〉 ∈
1亠
判别法
:
利用关系表达式判别 (1)R在 A上 白反 ㈡rA∈ R。
,
系:简 称全胛 蜮 线序 曳
柙
\宀
:'艹
° Γ ˉ叽
抖 ¨ ‰ 艹 渺 冖妒 ”
^讷
p¨ ¨
¨
i
∶
^¨
Ⅱ… ¨
=艹
)。
`呻
/
‘ :° f耷
一
^A’
工 < ′
工 < ′
Ι ⒕
,
、
\′
I纟
:
轱
/廴
跃
:
h,如 果 J≤ y∨ y※ J,贝 刂 ∈ 称
J与 j可 比。
称 y覆 盖 J。
偏序集中的特殊元素
得 ⒎ 则
:
y,z〉 ∈ S))。 ∈ R∧ 〈
有关基本运算的定理 ・ 定理 4.1 设 F是 任意的关系 ,则
(1)(Fˉ l)ˉ ^l=F。
・
(2)domFˉ ˉ ∴ =ranF,ranF~l=domF。
定理 4.2 设 F,G,Ⅳ 是任意的关系 ,则 (1)(F° G)° H=Fo(G° H), (2)(FoG)ˉ l=G^loF_ˉ
:
(2)R在 (3)R在 (4)R在 (5)R在 (1)R在 (2)R在 (3)R在 (4)R在
A上 反 自反 ⑶R∩ rA=¤ 。 A上 对称 山R=Rl。 ; A上 反对称 ㈡R∩ R~l∈ A上 传递 ㈡R。 R∈ R。

离散数学4-关系与函数

离散数学4-关系与函数
BA = {<a,1>,<b,1>,<c,1>,<a,2>,<b,2>,<c,2>,<a,3>, <b,3>,<c,3>}
A={}, P(A)A= {<,>, <{},>}
7
笛卡儿积的性质
不适合交换律 ABBA (AB, A, B) 不适合结合律 (AB)CA(BC) (A, B) 对于并或交运算满足分配律
<x,y>∈A×(B∪C) x∈A∧y∈B∪C x∈A∧(y∈B∨y∈C)
(x∈A∧y∈B)∨(x∈A∧y∈C) <x,y>∈A×B∨<x,y>∈A×C <x,y>∈(A×B)∪(A×C)
所以有A×(B∪C) = (A×B)∪(A×C).
10
二元关系的定义
定义 如果一个集合满足以下条件之一： （1）集合非空, 且它的元素都是有序对 （2）集合是空集
❖关系R1 ：{m, n}到 {w, x, y, z} ，且R1 ={<m, x>，<m, z>，<n, w>}。
❖ 计算R1∘R2
a R2 m
R1
w
b
n
x
o
y
c
p
z
23
第二种方法：关系矩阵乘法
利用图示（不是关系图）方法求合成
❖关系R2：{a, b, c}到 {m, n, o, p} ，且R2={<a, p>，<a, o>，<b, m>}。
12
从A到B的关系与A上的关系
定义 设A,B为集合, A×B的任何子集所定义的二元系叫 做从A到B的二元关系, 当A=B时则叫做 A上的二元关系.

离散数学第4章关系

离散数学第4章关系
第一个关系中的顺序排列。
关系的复合运算
总结词
复合运算是一种二元运算，它返回两个 关系中满足一定条件的元素组成的新关 系。
VS
详细描述
关系的复合运算是指将两个关系中的元素 按照一定的顺序组合在一起，形成一个新 的关系。这个新的关系只包含满足一定条 件的元素，这些元素按照它们在各自关系 中的顺序排列。
关系的表示
总结词
关系的表示方法有多种，包括表格、图形和符号等。
详细描述
关系的表示方法可以根据具体情况选择。表格表示法是一种常用的方法，通过二维表格的形式列出所 有可能的元素对及其关系状态。图形表示法则更加直观，通过节点和边的形式展示关系。符号表示法 则使用特定的符号或字母来表示关系，如集合论中的笛卡尔积等。
04
关系闭包
闭包的定义
闭包
对于给定的关系R，其闭包记作R+， 是指在R的基础上通过添加某些有序对 后得到的新的关系。
定义方式
如果存在一个集合A，对于A中的任意 元素x和y，如果(x,y)在R+中，那么(x,y) 在R中也一定存在。
闭包的性质
02
01
03
自反性
如果一个关系是自反的，那么其闭包也是自反的。
详细描述
如果集合中的任何一个元素x，都不满足关系 R，使得x与自己有R关系，则称关系R具有反 自反性。例如，在一个班级中，“是自己的 老师”这个关系不具有自反性，因为没有人
是自己的老师。
对称性
总结词
对称性是指如果元素x和元素y之间有关系R，并且元素y 和元素x之间也有关系R，则称关系R是对称的。
详细描述
02
关系的运算
关系的并运算
总结词
并运算是一种二元运算，它将两个关系合并成一个新的关系 。

离散数学第四章 关系

离散数学第四章 关系
21
2010-11-3
定理4.3.1 若R⊆A×B，S⊆B×C，T⊆C×D， 则 (R*S)*T=R*(S*T) 这说明复合运算是可结合的。我们常删去括号 将它们写成R*S*T。 由归纳法易证, 任意n个关系的合成也是可结合 的。在R1*R2*…*Rn中, 只要不改变它们的次序, 不论在它们之间怎样加括号, 其结果是一样的.
4
2010-11-3
定义4.1.2 给定集合A和B，若有序对的第一分 量是A的元素，第二分量是B的元素，所有这些 有序对的集合，称为A和B的笛卡尔积，记为 A×B， A×B={‹x,y›|x∈A∧y∈B}
5
2010-11-3
例 设A = {a, b, c}, B = {0, 1}, 则 A × B = {‹a, 0›, ‹a, 1›, ‹b, 0›, ‹b, 1›, ‹c, 0›, ‹c, 1›} B × A = {‹0, a›, ‹0, b›, ‹0, c›, ‹1, a›, ‹1, b›, ‹1, c›} A × A = {‹a, a›, ‹a, b›, ‹a, c›, ‹b, a›, ‹b, b›, ‹b, c›, ‹c, a›, ‹c, b›, ‹c, c›} B × B = {‹0, 0›, ‹0, 1›, ‹1, 0›, ‹1, 1›} 可以看出：A × B ≠ B × A (除非A = ∅或 B = ∅或 A = B,见后面定理) 即笛卡尔积不满足交换律。
18
2010-11-3
例 设A和B分别是学校的所有学生和所有课程的集合。假 设R由所有有序对‹a,b›组成，其中a是选修课程b的学生。 S由所有有序对‹a,b›构成，其中课程b是a的必修课。什么 是关系R∪S，R∩S，R⊕S，R-S和S-R？ 解：关系R∪S由所有的有序对‹a,b›组成，其中a是一个学 生，他或者选修了课程b，或者课程b是他的必修课。 R∩S是所有有序对‹a,b›的集合，其中a是一个学生，他选 修了课程b并且课程b也是a的必修课。 R⊕S由所有有序 对‹a,b›组成，其中学生a已经选修了课程b，但课程b不是 a的必修课，或者课程b是a的必修课，但a没有选修它。 R-S是所有有序对‹a,b›的集合，其中a已经选修了课程b但 课程b不是a的必修课。S-R是所有有序对‹a,b›的集合，其 中课程b是a的必修课，但a没有选它。

离散数学 第4-5章

离散数学 第4-5章

例题6： 1 2 带权图如右，求图的最小生成树 6 5 e 4 解：选取含最大边(c,d)的回路cdec， 3 删去其中权数最大的边(c,d)，然后 b 1 c 再选取含最大边(a,b)的回路abea，删去其中权数最 大的边(a,b)，再选取含最大边(c,e)的回路bceb，删 去其中权数最大的边(c,e)，再选取含最大边(a,d)的 回路adea，删去其中权数最大的边(a,d)，即得最小 a 生成树。 d 1 T=<{a,b,c,d,e},{(c,b),(b,e),(e,a),(e,d)}>。 e 2
汉密尔顿图的判定：
必要条件但不是充分条件定理： 1。在汉密尔顿图G中删除结点集V1后，G－V1的 连通分支数W (G V1 ) | V 1|。不满足这一条件的图一 定不是汉密尔顿图。 充分条件但不是必要条件定理： 2。如果无向简单图G中任何一对结点的度数之和 都大于等于结点数，则G中存在一条汉密尔顿回路。
例题4： 下列结论不正确的是（ D ）。 A）无向连通图G是欧拉图的充分必要条件是G不 含奇数度结点 B）非平凡连通图G有欧拉通路的充分必要条件是 G最多有两个奇数度结点 C）有向连通图D是欧拉图的充分必要条件是D的 每个结点的入度等于出度 D）有向连通图D是有向欧拉图的充分必要条件是 除两个结点外，每个结点的入度等于出度
例题3： 设G是无向图如右(彼得森图)， 说明G不是欧拉图。 解：因为无向图G中所有的 结点的度数全为奇数，所以 G不是欧拉图。 2。无向连通图存在欧拉通路的充分必要条件是图 中只有两个奇数度的结点。 3。当n为奇数时，完全无向图Kn是欧拉图。例 如K3、K5等。 4。当n为偶数时，完全无向图Kn不是欧拉图，也 不存在欧拉通路。
g
例题8： 设图G如右，作图G 的嵌入图，说明图G是 平面图。 解： 图G的嵌入图如下， 故图G是平面图。

离散数学第4章 有限集和无限集

离散数学第4章 有限集和无限集

A C
B
软件学院
有限集
例：120个学生中有100个学生至少要学法、德、英三 种语言中的一种，假定有65人学法语，45人学德语， 42人学英语，20个人学法语和德语，25人学法语和 英语，15人学德语和英语，请问同时学三种语言的 有多少人？ 解：令A、B、C表示学法语学、德语和英语的人数 100＝65＋45＋42－20－25－15＋|A∩B∩C| 所以 |A∩B∩C|＝8。
性质：可列集的无限子集仍为一可列集。
可列集是无限集中的最小集合。
软件学院
无限集的性质 例如：整数集I是可列集。 N={0,1, 2, 3, 4, 5, 6……}
I={0,1,-1, 2,-2, 3,-3……}
有理数集Q为可列集。 一切有理数都可写为m/n的形式，对于分数可以按照 分子和分母的顺序排列。 实数集R是不可列集。
软件学院
第四章 有限集与无限集 有限集S的元素的个数称为S的基数，可记为|S|。 自然数集N是无限集。 实数集R是无限集。 基数是与集合的元素数量有关的概念。在有限集中， 基数即是元素的个数，而在无限集中，集合基数就 变得复杂了。理论上讲，无限集中元素数量为无限， 但这太笼统了，因为个数中其浓度与密度是不同的。 如：实数与自然数同为无限个元素，但是实数无限浓 度高于自然数的无限浓度。
软件学院
无限集的性质 因为自然数集N不可能与某个自然数n等势。所以N的 基数不能是有限数，就用一个‚无限大‛的数 0表示（Aleph零）。 可列集是与自然数集中元素可以建立一一对应的集 合，即可列集与自然数集等势，势也为Aleph零。 所以我们可以用‘等势’来表示集合间的大小比较。 由于可列集是‘最小’的无限集，故已经没有比可 列集更小的无限集了。因此，其他无限集的势比 Aleph零要大，如实数集比可列集要大，它的基 数是Aleph。

离散数学第四讲关系

离散数学第四讲关系
利用关系图和关系矩阵都可找出所有最大相容类这里只介绍利用关系矩阵构成所有最大相容类其步骤如下201212168只与自身相容的元素能够分别单独地构成最大相容类因此从矩阵中删除这些元素所在行和从由简化的矩阵最右一列开始向左扫描发现1时以相应的行号和列号组成一相容类
第四讲
序偶与笛卡尔积 二元关系 关系运算 关系类型
2011-2-13
5
实例
例2 证明A (1) 证明A=B,C=D ⇒ A×C=B×D 为什么？ (2) A×C = B×D是否推出 A=B,C=D? 为什么？
任取<x,y> 解 (1) 任取 <x,y>∈A×C ∈ × ⇔ x∈A∧y∈C ∈ ∧ ∈ ⇔ x∈B∧y∈D ∈ ∧ ∈ ⇔ <x,y>∈B×D ∈ × (2) 不一定 反例如下： 不一定.反例如下 反例如下： A={1}，B={2}, C = D = ∅, 则A×C = B×D但是 ≠ B. 但是A ， × × 但是 定理3-4.2和3-4.3 例3、例4见P103定理 、 见 定理 和
i
1 i=
i
上的n元关系。特别A 上的n元关系。特别A1=A2=···=An时，称S为A上

2011-2-13
8
定义4.1.2 定义4.1.2
令R⊆ A×B，且
dom(R)={x|(∃y)(xRy)} dom(R)={x|(∃y)(xRy)} (R xRy
ran(R)={y|(∃x)(xRy)} an(R)={y|(∃x)(xRy)} )={y|( xRy FLD(R)=D(R) FLD(R)=D(R)
2011-2-13 7
可见， 是有序对的集合。 可见，R是有序对的集合。若<x,y>∈R，则也表为 x,y>∈ xRy， xRy，即<x,y>∈R⇔xRy。 x,y>∈ xRy。 则称S ×A，则称S为 ×A
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

划分的加细
Stirling子集数
3/18/2019
ห้องสมุดไป่ตู้
《集合论与图论》第8讲
2
等价(equivalence)关系定义
设 RAA 且 A, 若R是自 反的, 对称的, 传递的,则称R为等价关系 例9: 判断是否等价关系(A是某班学生): R1={<x,y>|x,yAx与y同年生} R2={<x,y>|x,yAx与y同姓} R3={<x,y>|x,yAx的年龄不比y小} R4={<x,y>|x,yAx与y选修同门课程} R5={<x,y>|x,yAx的体重比y重}
(3)
z
x
3/18/2019
y
《集合论与图论》第8讲 10
定理27(证明(4))
(4) U{ [x]R | xA } = A. 证明: (4) A=U{ {x} | xA } U{ [x]R | xA } U{ A | xA }=A. U{ [x]R | xA } = A. #
4 1
3/18/2019
8 2 5
《集合论与图论》第8讲
3
13
商集(quotient set)
设R是A上等价关系, A/R = { [x]R | xA } 称为A关于R的商集, 简称A的商集. 显然 U A/R = A. 例11(续): A/R3 ={ {1,4}, {2,5,8}, {3} }.

x
3/18/2019
y
《集合论与图论》第8讲 11
同余(congruence)关系
设n{2,3,4,…}, x,yZ,则 x与y模n同余(be congruent modulo n) xy(mod n) n|(x-y) x-y=kn (kZ) 同余关系是等价关系 0 1 11 [0] ={ kn|kZ}, 10 2 [1] ={ 1+kn|kZ}, 9 3 [2] ={ 2+kn|kZ},…, 8 4 7 6 5 [n-1]={(n-1)+kn|kZ}.
《集合论与图论》第8讲
例10
设 RAA 且 A, 对R依次求三 种闭包共有6种不同顺序, 其中哪些顺序 一定导致等价关系? rst( R ), rts( R ), str( R ), srt( R ), trs( R ), tsr( R )=t(s(r( R ))) 解: st( R )ts( R ), sr( R )=rs( R ),… tsr( R )=trs( R )=rts( R ) str( R )=srt( R )=rst( R )
等价关系:
3/18/2019 《集合论与图论》第8讲 3
例9(续)
定义 R1 x与y同年生 R2 x与y同姓 自反 对称 传递 等价关系
R3 x的年龄不比 y小 R4 x与y选修同 门课程
R5 x的体重比y 重
3/18/2019








4

x
y
3/18/2019
《集合论与图论》第8讲
9
定理27(证明(3))
xRy [x]R[y]R= ; 证明: (3) (反证) 假设z, z[x]R[y]R, 则 z[x]R[y]R zRxzRy xRzzRy xRy, 这与xRy矛盾! [x]R[y]R=.
同余关系:
3/18/2019 《集合论与图论》第8讲 12
例11
例11:
设 A={1,2,3,4,5,8}, 求 R3 = { <x,y> | x,yA xy(mod 3) } 的等价类, 画出R3的关系图. 解: [1]=[4]={1,4}, [2]=[5]=[8]={2,5,8}, [3]={3}. #
x
3/18/2019 《集合论与图论》第8讲 8
定理27(证明(2))
(2) xRy [x]R=[y]R ; 证明: (2) 只需证明[x]R[y]R和[x]R[y]R. () z, z[x]RxRy zRxxRy zRy z[y]R . [x]R[y]R. () 同理可证. z
第8讲 等价关系与序关系
内容提要 等价关系,等价类,商集 划分, 第二类Stirling数 偏序,线序,拟序,良序 哈斯图 特殊元素: 最?元,极?元,?界,?确界 (反)链
3/18/2019 《集合论与图论》第8讲 1
等价(equivalence)关系
定义 同余关系 等价类 商集 划分
商集:
3/18/2019
《集合论与图论》第8讲
14
例12(1)
设A={a1,a2,…,an}, IA, EA, Rij=IA{<ai,aj>,<aj,ai>} 都是A上等价关系, 求对应的商集, 其中 ai,ajA, ij. 是A上等价关系吗? 解: A/IA={ {a1}, {a2},…, {an } } A/EA={ {a1,a2,…,an } } A/Rij= A/IA{{ai,aj}} - {{ai},{aj}}. 不是A上等价关系(非自反). #
等价类:
3/18/2019 《集合论与图论》第8讲 7
定理27
定理27:设R是A上等价关系,x,yA,
(1) [x]R (2) xRy [x]R=[y]R ; (3) xRy [x]R[y]R= ; (4) U{ [x]R | xA } =A. 证明: (1) R自反xRxx[x]R[x]R.
例10:
3/18/2019 《集合论与图论》第8讲 5
例10(续)
tsr(R)=trs(R) =rts( R )
自反 对称 传递 等价关系 (等价闭包)
str(R)=srt(R) =rst( R )

3/18/2019
《集合论与图论》第8讲
6
等价类(equivalence class)
设R是A上等价关系,xA,令 [x]R={ y | yA xRy }, 称[x]R为x关于R的等价类, 简称x的等价类, 简记为[x]. 等价类性质: [x]R ; xRy [x]R=[y]R ; xRy [x]R[y]R= ; U{ [x]R | xA } =A.