北大离散数学
- 格式：ppt
- 大小：327.00 KB
- 文档页数：61
下载文档原格式
合集下载
Ramsey定理 北京大学计算机系离散数学讲义(ppt版)
2020/10/7
W1 W2 W3 W4 W5 W11 W12 W13 W14 W15 W6 W7 W8 W9 W10
20
S10
方案的最优性
满足目标要求： 任取 10 个工作站. 如果恰好为 W1,W2,…,W10，Wi 访问 Si，i=1,…10, 满足要求; 如果 W1-W10 中只选中 k 个工作 站，不妨设为 W1--Wk, 剩下的 10-k 个选自 W11-W15. 那 么 Wi 访问 Si，i=1,…,k. 还剩下 10-k 个服务器空闲，恰好 分配给 10-k 个工作站.
保证这组工作站可以同时访问不同的服务器.
问题：达到这个目标需要的最少缆线数目 N 是多少？
方案 1：每个工作站都连到每个服务器，需要
1015=150
2020/10/7
根缆线，N 150.
例11的解决方案
方案 2 将工作站标记为 W1,W2, …, W15, 服务器标记为 S1,S2, …, S10. 对于 k=1,2,…,10，我们连接 Wk 到 Sk, 剩下 5 个工作站的每一个都连接到 10 个服务器 总共 60 条直接连线.
2020/10/7
简单Ramsey定理的推广
(1) R(p,q)的集合表述：
Kn 的顶点集 V
集合 S
Kn 的边集 E
S 的 2 元子集的集合 T
用 2 色涂色 Kn 的边 将 T 划分成 E1,E2
存在蓝色完全 p 边形 存在 S 的 p 子集，其所有 2 元子集E1
存在红色完全 q 边形 存在 S 的 q 子集，其所有 2 元子集E2
对于 K8，存在一种涂色方案， 既没有蓝色三角形，也没有红 色完全四边形.
R(3,4)=9.
2020/10/7
W1 W2 W3 W4 W5 W11 W12 W13 W14 W15 W6 W7 W8 W9 W10
20
S10
方案的最优性
满足目标要求： 任取 10 个工作站. 如果恰好为 W1,W2,…,W10，Wi 访问 Si，i=1,…10, 满足要求; 如果 W1-W10 中只选中 k 个工作 站，不妨设为 W1--Wk, 剩下的 10-k 个选自 W11-W15. 那 么 Wi 访问 Si，i=1,…,k. 还剩下 10-k 个服务器空闲，恰好 分配给 10-k 个工作站.
保证这组工作站可以同时访问不同的服务器.
问题：达到这个目标需要的最少缆线数目 N 是多少？
方案 1：每个工作站都连到每个服务器，需要
1015=150
2020/10/7
根缆线，N 150.
例11的解决方案
方案 2 将工作站标记为 W1,W2, …, W15, 服务器标记为 S1,S2, …, S10. 对于 k=1,2,…,10，我们连接 Wk 到 Sk, 剩下 5 个工作站的每一个都连接到 10 个服务器 总共 60 条直接连线.
2020/10/7
简单Ramsey定理的推广
(1) R(p,q)的集合表述：
Kn 的顶点集 V
集合 S
Kn 的边集 E
S 的 2 元子集的集合 T
用 2 色涂色 Kn 的边 将 T 划分成 E1,E2
存在蓝色完全 p 边形 存在 S 的 p 子集，其所有 2 元子集E1
存在红色完全 q 边形 存在 S 的 q 子集，其所有 2 元子集E2
对于 K8，存在一种涂色方案， 既没有蓝色三角形，也没有红 色完全四边形.
R(3,4)=9.
2020/10/7
北大数学系本科教材
北大数学系本科教材
北大数学系本科教材包括以下几门课程的教材：
1. 微积分：北大的微积分教材包括《微积分（修订版）》和《微积分习题讲义（修订版）》。
2. 线性代数：北大的线性代数教材包括《线性代数与解析几何（修订版）》和《线性代数习题指导与解答》。
3. 概率论与数理统计：北大的概率论与数理统计教材包括《概率论与数理统计教程（修订版）》和《概率论与数理统计习题讲义》。
4. 离散数学：北大的离散数学教材包括《离散数学》。
5. 数学分析：北大的数学分析教材包括《数学分析习题解答》和《数学分析辅导教程》。
这些教材都是经过北大数学系教授和专家精心编写的，旨在提供给本科学生综合学习和参考。
另外，北大数学系还有其他教材，涵盖更多的专业课程和研究领域，如代数学、几何学等。
北京大学离散数学教材 2
命题逻辑等值演算2学习目的本章主要涉及命题演算中两个重要内容之一：等值演算。
首先理解命题公式等值的含义，掌握构造真值表和不构造真值表两种方法证明等值式，熟练应用于命题公式的化简和范式表示基本内容z命题公式等值关系及其证明z联结词的全功能集z命题公式的范式表示等值关系基本概念等值的两种定义：z如果两个逻辑形式对其中的命题变项的任何取值，都具有相同的值，则称它们是相等的。
z A、B等值是指等价式A↔B为重言式，记为A⇔B。
可直接构造真值表证明两个命题形式的等值。
等值演算根据已知的等值式，可以推演出另外许多的等值式，这种推演过程称为等值演算。
这些已知等值式通常是经过证明了的常用等值式，其中许多是布尔代数或逻辑代数的主要组成部分，称为等值关系模式：(1) 双重否定律： A ⇔¬¬A(2) 等幂律：(2a) A ⇔ A∧A(2b) A ⇔ A∨A(3) 交换律：(3a) A∧B ⇔ B∧A(3b) A∨B ⇔ B∨A(3c) A∨B ⇔ B∨A(3d) A↔B ⇔ B↔A(4) 结合律：(4a) (A∧B)∧C ⇔ A∧(B∧C)(4b) (A∨B)∨C ⇔ A∨(B∨C)(4c) (A∨B) ∨C ⇔ A∨ (B∨C)(4d) (A↔B) ↔C ⇔ A↔ (B↔C)(5) 分配律：(5a) A∨(B∧C) ⇔ (A∨B)∧(A∨C)(5b) A∧(B∨C) ⇔ (A∧B)∨(A∧C)(5c) A∧(B∨C) ⇔ (A∧B) ∨ (A∧C)(6) 德•摩根律：(6a) ¬(A∧B) ⇔¬B∨¬A(6b) ¬(A∨B)⇔¬B∧¬A(7) 吸收律：(7a) A∨(A∧B)⇔A(7b) A∧(A∨B)⇔A(7c) A∨(¬A∧B)⇔A∨B(7d) A∧(¬A∨B)⇔A∧B(7e) (A∧B) ∨ (¬A∧C) ∨ (B∧C) ⇔ (A∧B) ∨ (¬A∧C) (8) 零律：(8a) A∨1 ⇔ 1(8b) A∧0 ⇔ 0(9) 同一律：(9a) A∨0 ⇔ A(9b) A∨0 ⇔ A(10)排中律：A∨¬A ⇔ 1(11)矛盾式：A∧¬A ⇔ 0(12)蕴涵等值式：A→B ⇔¬A∨B(13)等价等值式：(13a) A↔B ⇔ (A→B) ∧ (B→A)(13b) A↔B ⇔¬ (A∨B)(14)假言易位：A→B ⇔¬B→¬A(15)等价否定等值式：A↔B ⇔¬A↔¬B(16)否定等价等值式：¬ (A↔B) ⇔¬A↔B ⇔ A↔¬B(17)归谬律：(A→B) ∧ (A→¬B) ⇔¬A(18)输出律：(A∧B) → C ⇔ A → (B → C)(19) A ∨¬A ⇔ 0(20) A ∨ B ⇔ (A ∧¬B) ∨ (¬A ∧ B)通常在等值演算的过程中，还可以用到一些规则或定理：z置换规则设Φ是含有公式A的命题形式，Ψ是用公式B置换Φ中的公式A(不一定是每一处)而得到的命题形式，如果A ⇔ B，则Φ⇔Ψ。
北大离散数学22.3-4
m
∑
∞
∞
⎛m⎞ n (1 + z ) = ∑ ⎜ ⎟ z , ⎜ n⎟ n = 0⎝ ⎠
m
4
二项式定理（续）
当α = -m 时，
⎛ α ⎞ ⎛ − m ⎞ ( − m )( − m − 1） − m − n + 1) ...( ⎟= ⎜ ⎟=⎜ ⎜ n⎟ ⎜ n ⎟ n! ⎠ ⎝ ⎠ ⎝ ⎛ m + n − 1⎞ ( −1) n m ( m + 1)...( m + n − 1) ⎟ = = ( −1) n ⎜ ⎜ ⎟ n n! ⎝ ⎠
G ( y ) = (1 + y + ... + y n1 )(1 + y + ... + y n2 )...(1 + y + ... + y nk )
的 yr 的系数
16
多重集的r-组合数（续）
例 3 S ={ 3⋅a, 4⋅b, 5⋅c }的 10 组合数 解：生成函数 G(y) = (1+y+y2+y3)(1+y+y2+y3+y4)(1+y+y2+y3+y4+y5) = (1+2y+3y2+4y3+4y4+3y5+2y6+y7)(1+y+y2+y3+y4+y5) = (1 + … +3y10+2y10+y10 + …) N=6 {a,a,a,b,b,b,b,c,c,c}, {a,a,a,b,b,b,c,c,c,c}, {a,a,a,b,b,c,c,c,c,c}, {a,a,b,b,b,b,c,c,c,c}, {a,a,b,b,b,c,c,c,c,c}, {a,b,b,b,b,c,c,c,c,c}
∑
∞
∞
⎛m⎞ n (1 + z ) = ∑ ⎜ ⎟ z , ⎜ n⎟ n = 0⎝ ⎠
m
4
二项式定理（续）
当α = -m 时，
⎛ α ⎞ ⎛ − m ⎞ ( − m )( − m − 1） − m − n + 1) ...( ⎟= ⎜ ⎟=⎜ ⎜ n⎟ ⎜ n ⎟ n! ⎠ ⎝ ⎠ ⎝ ⎛ m + n − 1⎞ ( −1) n m ( m + 1)...( m + n − 1) ⎟ = = ( −1) n ⎜ ⎜ ⎟ n n! ⎝ ⎠
G ( y ) = (1 + y + ... + y n1 )(1 + y + ... + y n2 )...(1 + y + ... + y nk )
的 yr 的系数
16
多重集的r-组合数（续）
例 3 S ={ 3⋅a, 4⋅b, 5⋅c }的 10 组合数 解：生成函数 G(y) = (1+y+y2+y3)(1+y+y2+y3+y4)(1+y+y2+y3+y4+y5) = (1+2y+3y2+4y3+4y4+3y5+2y6+y7)(1+y+y2+y3+y4+y5) = (1 + … +3y10+2y10+y10 + …) N=6 {a,a,a,b,b,b,b,c,c,c}, {a,a,a,b,b,b,c,c,c,c}, {a,a,a,b,b,c,c,c,c,c}, {a,a,b,b,b,b,c,c,c,c}, {a,a,b,b,b,c,c,c,c,c}, {a,b,b,b,b,c,c,c,c,c}
北大离散数学02
2013-1-2
《集合论与图论》第2讲
15
命题符号化(举例、续)
例:
“有些病人相信所有的医生”。 解: 设: F(x): x是病人; G(x): x是医生; H(x,y): x相信y 原命题符号化成: x(F(x)y(G(y)H(x,y)))
2013-1-2
《集合论与图论》第2讲
16
命题符号化(举例、续)
2013-1-2 《集合论与图论》第2讲 10
命题符号化(举例、续)
例:
“凡人都是要死的”. 解1: 采用全总个体域. 设: F(x): x是人; G(x):x是要死的. 原命题符号化成: x(F(x)G(x)) 解2: 采用全体人作为个体域. 设: G(x): x是要死的. 原命题符号化成: xG(x)
2013-1-2
《集合论与图论》第2讲
14
命题符号化(举例、续)
例:
“有的汽车比火车快”。 解: 设: F(x): x是汽车; G(x): x是火车; H(x,y): x比y快 原命题符号化成: x(F(x)y(G(y)H(x,y))) 或: xy(F(x)G(y)H(x,y))
例:
“存在唯一的对象满足性质P”。 解: 设: P(x): x满足性质P 原命题符号化成: !xP(x) 或: x( P(x) y( P(y)x=y ) )
2013-1-2
《集合论与图论》第2讲
17
合式公式中的变项
在xA, xA中, A是量词的辖 域. 例如: x(F(x)y(G(y)H(x,y))) 指导变项: 紧跟在量词后面的个体变项. 例如: x(F(x)y(G(y)H(x,y))) 约束出现: 在辖域中与指导变项同名的变 项. 例如: x(F(x)y(G(y)H(x,y))) 自由出现: 既非指导变项又非约束出现. 例如: y(G(y)H(x,y))
北大离散数学演示文稿
定理1: 对任意集合A, A
证明: Ax(xxA)
x(0xA)1. #
推论: 空集是唯一的.
证明: 设1与2都是空集, 则 12 21 1=2 . #
全集
全集: 如果限定所讨论的集合都是某个集 合的子集,则称这个集合是全集,记作E
全集是相对的, 视情况而定, 因此不唯一. 例如, 讨论(a,b)区间里的实数性质时, 可 以选E=(a,b), E=[a,b), E=(a,b], E=[a,b], E=(a,+),E=(-,+)等
P1 (x): x是英文字母 A={x|P1 (x)}={x| x是英文字母} ={a,b,c,d,…,x,y,z}
P2 (x): x是十进制数字 B={x|P2(x)}= {x|x是ห้องสมุดไป่ตู้进制数字} ={0,1,2,3,4,5,6,7,8,9}
描述法（续）
两种表示法可以互相转化，例如 E={2,4,6,8,…}
北大离散数学演示文稿
集合论(set theory)
十九世纪数学最伟大成就之一 集合论体系
朴素(naive)集合论 公理(axiomatic)集合论
创始人康托(Cantor)
Georg Ferdinand Philip Cantor 1845 ~ 1918 德国数学家, 集合论创始人.
什么是集合(set)
幂集(power set)
幂集: A的全体子集组成的集合,称为A的 幂集,记作P(A)
P(A)={x|xA}
注意:
xP(A) xA
例子: A={a,b}, P(A)={,{a},{b},{a,b}}. #
n元集(n-set)
n元集: 含有n个元素的集合称为n元集 0元集: 1元集(或单元集),如{a}, {b}, {}, {{}},… |A|: 表示集合A中的元素个数,
离散数学习题解答北京大学出版社
习题一1.下列句子中,哪些是命题？在是命题的句子中,哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？（1）中国有四大发明.答：此命题是简单命题，其真值为1.（2）5是无理数.答：此命题是简单命题，其真值为1.（3）3是素数或4是素数.答：是命题，但不是简单命题，其真值为1.x+<（4）235答：不是命题.（5）你去图书馆吗？答：不是命题.（6）2与3是偶数.答：是命题，但不是简单命题，其真值为0.（7）刘红与魏新是同学.答：此命题是简单命题，其真值还不知道.（8）这朵玫瑰花多美丽呀！答：不是命题.（9）吸烟请到吸烟室去！答：不是命题.（10）圆的面积等于半径的平方乘以π.答：此命题是简单命题，其真值为1.（11）只有6是偶数，3才能是2的倍数.答：是命题，但不是简单命题，其真值为0.（12）8是偶数的充分必要条件是8能被3整除.答：是命题，但不是简单命题，其真值为0.（13）2008年元旦下大雪.答：此命题是简单命题，其真值还不知道.2.将上题中是简单命题的命题符号化.解:（1）p：中国有四大发明.（2）p:是无理数.（7）p:刘红与魏新是同学.（10）p:圆的面积等于半径的平方乘以π.（13）p:2008年元旦下大雪.3.写出下列各命题的否定式,并将原命题及其否定式都符号化,最后指出各否定式的真值.（15是有理数.5.p5.q5.其否定式q的真值为1.（225不是无理数.答：是有理数. p 不是无理数. q 是有理数. 其否定式q 的真值为1.（3）是自然数.答：否定式：不是自然数. p ：是自然数. q ：不是自然数. 其否定式q 的真值为1. （4）ln1是整数.答：否定式：ln1不是整数. p ：ln1是整数. q ：ln1不是整数. 其否定式q 的真值为1.4.将下列命题符号化，并指出真值. （1）2与5都是素数答：p ：2是素数，q ：5是素数，符号化为p q ∧，其真值为1.（2）不但π是无理数，而且自然对数的底e 也是无理数.答：p ：π是无理数，q ：自然对数的底e 是无理数，符号化为p q ∧，其真值为1. （3）虽然2是最小的素数，但2不是最小的自然数.答：p ：2是最小的素数，q ：2是最小的自然数，符号化为p q ∧⌝，其真值为1. （4）3是偶素数.答：p ：3是素数，q ：3是偶数，符号化为p q ∧，其真值为0. （5）4既不是素数，也不是偶数.答：p ：4是素数，q ：4是偶数，符号化为p q ⌝∧⌝，其真值为0. 5.将下列命题符号化，并指出真值. （1）2或3是偶数. （2）2或4是偶数. （3）3或5是偶数.（4）3不是偶数或4不是偶数. （5）3不是素数或4不是偶数.答: p ：2是偶数，q ：3是偶数，r :3是素数，s :4是偶数, t :5是偶数 (1) 符号化: p q ∨，其真值为1. (2) 符号化：p r ∨，其真值为1. (3) 符号化：r t ∨，其真值为0. (4) 符号化：q s ⌝∨⌝，其真值为1.(5) 符号化：r s ⌝∨⌝，其真值为0. 6.将下列命题符号化.（1）小丽只能从筐里拿一个苹果或一个梨.答：p ：小丽从筐里拿一个苹果，q ：小丽从筐里拿一个梨，符号化为: p q ∨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课.答：p ：刘晓月选学英语，q ：刘晓月选学日语，符号化为: ()()p q p q ⌝∧∨∧⌝. 7.设p ：王冬生于1971年，q ：王冬生于1972年，说明命题“王冬生于1971年或1972年”既可以化1 1 0 1根据真值表,可以判断出,只有当p与q同时为真时两种符号化的表示才会有不同的真值,但结合命题可以发现,p与q不可能同时为真,故上述命题有两种符号化方式.8.将下列命题符号化,并指出真值.（1）只要,就有；（2）如果,则；（3）只有,才有；（4）除非,才有；（5）除非,否则；（6）仅当.答:设p:,则:;设q:,则:.符号化真值（1） 1（2） 1（3）0（4）0（5）0（6） 19.设p：俄罗斯位于南半球,q：亚洲人口最多,将下面命题用自然语言表述,并指出其真值：（1）；（2）；；（3）；（4）；（5）；（6）；（7）.自然语言真值（1）只要俄罗斯位于南半球,亚洲人口就最多 1（2）只要亚洲人口最多,俄罗斯就位于南半球0（3）只要俄罗斯不位于南半球,亚洲人口就最多 1（4）只要俄罗斯位于南半球，亚洲人口就不是最多 1（5）只要亚洲人口不是最多，俄罗斯就位于南半球 1（6）只要俄罗斯不位于南半球，亚洲人口就不是最多0（7）只要亚洲人口不是最多，俄罗斯就不位于南半球 1 10．设p：9是3的倍数,q：英国与土耳其相邻,将下面命题用自然语言表述,并指出真值：（1）；（2）；（3）；（4）.答:根据题意,p为真命题,q为假命题.自然语言真值（1）9是3的倍数当且仅当英语与土耳其相邻0（2）9是3的倍数当且仅当英语与土耳其不相邻 1（3）9不是3的倍数当且仅当英语与土耳其相邻 1（4）9不是3的倍数当且仅当英语与土耳其不相邻011．将下列命题符号化,并给出各命题的真值：（1）若2+2=4,则地球是静止不动的；（2）若2+2=4,则地球是运动不止的；（3）若地球上没有树木,则人类不能生存；（4）若地球上没有水,则是无理数.答:命题1 命题2 符号化真值（1）p:2+2=4 q:地球是静止不动的0 （2）p:2+2=4 q:地球是静止不动的 1 （3）p:地球上有树木q:人类能生存 1 （4）p:地球上有树木q:人类能生存 1（1）2+2=4当且仅当3+3=6；（2）2+2=4的充要条件是3+36；（3）2+24与3+3=6互为充要条件；（4）若2+24,则3+36,反之亦然.答:设p:2+2=4,q:3+3=6.符号化真值(1) 113.将下列命题符号化,并讨论各命题的真值：（1）若今天是星期一,则明天是星期二；（2）只有今天是星期一,明天才是星期二；（3）今天是星期一当且仅当明天是星期二；（4）若今天是星期一,则明天是星期三.答:设p:今天是星期一,q:明天是星期二,r:明天是星期三.14.将下列命题符号化：（1）刘晓月跑得快,跳得高；（2）老王是山东人或者河北人；（3）因为天气冷,所以我穿了羽绒服；（4）王欢与李乐组成一个小组；（5）李欣与李末是兄弟；（6）王强与刘威都学过法语；（7）他一面吃饭,一面听音乐；（8）如果天下大雨,他就乘班车上班；（9）只有天下大雨,他才乘班车上班；（10）除非天下大雨,否则他不乘班车上班；（11）下雪路滑,他迟到了；（12）2与4都是素数,这是不对的；（13）“2或4是素数,这是不对的”是不对的.(12) p:2是素数q:4是素数-(13) p:2是素数q:4是素数-15.设p：2+3=5.q：大熊猫产在中国.r:太阳从西方升起.求下列符合命题的真值：（1）（2）（3）（4）解：p真值为1，q真值为1，r真值为0.（1）0，（2）0，（3）0，（4）116.当p,q的真值为0,r,s的真值为1时,求下列各命题公式的真值：（1）（2）（3）（4）解：（1）0，（2）0，（3）0，（4）117.判断下面一段论述是否为真：“是无理数.并且,如果3是无理数,则也是无理数.另外,只有6能被2整除,6才能被4整除.”解：p:是无理数q: 3是无理数r:是无理数s: 6能被2整除t：6能被4整除符号化为:，该式为重言式，所以论述为真。
北大离散数学chap5
则矩阵的加法和乘法都是二元运算。
(5) 集合S 的幂集 P ( S ) 上的, , , 都是二元运算，
而绝对补集( S 为全集)是一元运算。
(6) 所有命题公式的集合上的 , , , 都是二元运算，而否定 为一元运算。 (7) S S 表示集合 S 上的所有函数的集合，
函数的合成运算 是 S S 上的二元运算。
例如：在 N , Z , Q, R 上，加法的幺元是0，
乘法的幺元是1。在 Z 上的减法运
算没有幺元，只有右幺元0 ( x 0 x)
在 M n ( R) 上，矩阵加法的幺元是 n 阶0矩阵，
矩阵乘法的幺元是 n 阶单位矩阵。
在幂集 P ( S ) 上，运算 的幺元是 ，运算
的幺元是全集 S 。
(3) , , 在幂集P ( S ) 上可结合，可交换，
但是相对补不可结合，不可交换， 和
是互相可分配的。 (4) , 在全体命题公式集合上可结合，可交换，
和 是相互可分配的。
三、一些特殊元素。 设 为 S 上的二元运算， 1、幺元 e ：若e S ，对x S ， x x e x e 则称 e 为运算 的幺元。 注：(1) 若幺元存在必唯一。 (2) 若只有el x x 或只有 x er x ， 则 el ， r 称为左幺元或右幺元。 e
(2)
解：但它们的逆元都不存在。
四、其它一些运算律和特殊元素。(了解)
1、设 和 都是 S 上的可交换的二元运算，
若 x, y S ，
x ( x y) x x ( x y) x
则称 和 满足吸收律。
四、其它一些运算律和特殊元素。(了解)
2、设 是 S 上的二元关系，
北大离散数学课件
*
*
定理21
《集合论与图论》第7讲
定理21: 设 R1,R2AA 且 A, 则 (1) r(R1R2) = r( R1 )r( R2 ); (2) s(R1R2) = s( R1 )s( R2 ); (3) t(R1R2) t( R1 )t( R2 ). 证明: (1) 利用定理20, r(R1R2)r(R1)r(R2). r(R1)r(R2)自反且包含R1R2,所以 r(R1R2)r(R1)r(R2). r( R1R2) = r( R1 )r( R2 )
推广形式: 若把m件物品装进k只抽屉, 则至少有一只抽屉装 只以上的物品.
1.8=2, 1.8=1, -1.8=-1, -1.8=-2.
*
*
定理18: 设 RAA, 若 s,tN (s<t),使得Rs = Rt, 则
定理18
《集合论与图论》第7讲
Rs+k = Rt+k ;
Rs+kp+i = Rs+i, 其中k,iN, p=t-s;
*
*
定理21(证明(2))
《集合论与图论》第7讲
(2) s( R1R2) = s( R1 )s( R2 ); 证明(2): 利用定理20, s(R1R2)s(R1)s(R2). s(R1)s(R2)对称且包含R1R2,所以 s(R1R2)s(R1)s(R2). s( R1R2) = s( R1 )s( R2 )
G( R )
G(r( R ))
*
*
对称闭包(symmetric closure)
《集合论与图论》第7讲
对称闭包: 包含给定关系R的最小对称关系, 称为R的对称闭包, 记作s( R ). (1) R s( R ); (2) s( R )是对称的; (3) S( (RS S对称) s( R )S ).
*
定理21
《集合论与图论》第7讲
定理21: 设 R1,R2AA 且 A, 则 (1) r(R1R2) = r( R1 )r( R2 ); (2) s(R1R2) = s( R1 )s( R2 ); (3) t(R1R2) t( R1 )t( R2 ). 证明: (1) 利用定理20, r(R1R2)r(R1)r(R2). r(R1)r(R2)自反且包含R1R2,所以 r(R1R2)r(R1)r(R2). r( R1R2) = r( R1 )r( R2 )
推广形式: 若把m件物品装进k只抽屉, 则至少有一只抽屉装 只以上的物品.
1.8=2, 1.8=1, -1.8=-1, -1.8=-2.
*
*
定理18: 设 RAA, 若 s,tN (s<t),使得Rs = Rt, 则
定理18
《集合论与图论》第7讲
Rs+k = Rt+k ;
Rs+kp+i = Rs+i, 其中k,iN, p=t-s;
*
*
定理21(证明(2))
《集合论与图论》第7讲
(2) s( R1R2) = s( R1 )s( R2 ); 证明(2): 利用定理20, s(R1R2)s(R1)s(R2). s(R1)s(R2)对称且包含R1R2,所以 s(R1R2)s(R1)s(R2). s( R1R2) = s( R1 )s( R2 )
G( R )
G(r( R ))
*
*
对称闭包(symmetric closure)
《集合论与图论》第7讲
对称闭包: 包含给定关系R的最小对称关系, 称为R的对称闭包, 记作s( R ). (1) R s( R ); (2) s( R )是对称的; (3) S( (RS S对称) s( R )S ).
离散数学北京大学出版社第二版配套PPT课件_屈婉玲_耿素云_张立昂ch
离散数学北京大学出版社第二版配套PPT课件介绍本文档是北京大学出版社出版的《离散数学》第二版的配套PPT课件的简介。
透过课件，学生可以更好地理解和学习离散数学的概念和原理。
课件的作者包括屈婉玲、耿素云和张立昂等离散数学领域的专家，他们精心设计了课件的内容和布局，旨在帮助学生更好地理解离散数学的基础知识，并应用到实际问题中。
内容概述离散数学是计算机科学和信息技术中的一门基础课程，它研究离散的数学结构和离散对象之间的关系。
离散数学的理论和方法在计算机科学、密码学、人工智能等领域有着广泛的应用。
《离散数学》第二版的配套PPT课件涵盖了离散数学的主要内容，包括集合论、逻辑、关系、图论、计数原理等。
课件的设计旨在让学生通过图示、例子和练习等形式来理解和掌握离散数学的概念和方法。
课件还提供了一些附加材料和参考资料，供学生进一步学习和探索离散数学的相关内容。
课件特点1.系统性：课件内容有机地连接起来，形成一个完整的体系，学生可以从不同的章节中逐步深入学习离散数学的不同方面。
2.可视化：课件中使用了大量的图示和示例，帮助学生更直观地理解离散数学的概念和原理。
3.互动性：课件中设置了各种练习和思考题，鼓励学生积极参与和思考，提高学习效果。
4.实用性：课件中的例子和实际应用案例帮助学生将离散数学的理论应用到实际问题中，增强学习的实际效果。
使用指南学生可以使用任何支持Markdown文本格式的编辑器来打开和阅读本课件。
在阅读的同时，建议学生积极参与，思考课件中的问题，并完成相应的练习。
学生还可以根据自己的学习情况，有针对性地选择课件中的章节进行学习。
附加材料《离散数学》第二版的配套PPT课件还提供了一些附加材料，供学生进一步学习和探索离散数学的相关内容。
这些附加材料包括参考资料、习题解答和扩展阅读等。
学生可以根据自己的学习需要，选择适合自己的附加材料进行阅读。
结语《离散数学》第二版的配套PPT课件是学习离散数学的重要辅助工具，它通过图示、例子和练习等形式，帮助学生更好地理解和掌握离散数学的概念和方法。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
2m2
2020/7/31
《集合论与图论》第5讲
26
A上的二元关系
A上的二元关系: 是AA的任意子集 R是A上的二元关系
RAA RP(AA) 若|A|=m, 则|AA|=m2, 故
|P(AA)|= 2m2 即A上不同的二元关系共有 2m2个
2m2
2020/7/31
《集合论与图论》第5讲
27
A上的二元关系(例1)
2020/7/31
《集合论与图论》第5讲
14
例题1
例题1: 设A,B,C,D是任意集合, (1) AB= A= B= (2) 若A, 则 ABAC BC. (3) AC BD ABCD,
并且当(A=B=)(AB)时, ABCD ACBD.
2020/7/31
《集合论与图论》第5讲
15
卡氏积图示
2020/7/31
《集合论与图论》第5讲
6
有序对(推论)
推论: ab <a,b><b,a> 证明: (反证) <a,b>=<b,a>a=b,
与ab矛盾. #
2020/7/31
《集合论与图论》第5讲
7
有序三元组(ordered triple)
有序三元组: <a,b,c>=<<a,b>,c>
有序n(2)元组: <a1,a2,…,an>=<<a1,a2,…,an-1>,an>
2020/7/31
《集合论与图论》第5讲
24
A到B的二元关系
A到B的二元关系: 是AB的任意子集. R是A到B的二元关系
RAB RP(AB) 若|A|=m,|B|=n, 则|AB|=mn, 故
|P(AB)|=2mn 即A到B不同的二元关系共有2mn个
2m2
2020/7/31
《集合论与图论》第5讲
证明: (1) x, x∪A z(zA xz) z(zB xz) x∪B.
(2) x, x∩A z( zA xz ) z( zB xz ) x∩B. #
2020/7/31
《集合论与图论》第5讲
5
有序对(定理1)
定理1: <a,b>=<c,d> a=cb=d 证明: () 显然.
第5讲 二元关系的基本概念 北京大学
内容提要 1. 有序对与卡氏积 2. 二元关系 3. 二元关系的基本运算
2020/7/31
《集合论与图论》第5讲
1
有序对与卡氏积
有序对(有序二元组) 有序三元组, 有序n元组 卡氏积 卡氏积性质
2020/7/31
《集合论与图论》第5讲
2
有序对(ordered pair)
反例: A=B=C={1}. (AB)C={<<1,1>,1>}, A(BC)={<1,<1,1>>}.
2020/7/31
《集合论与图论》第5讲
12
卡氏积分配律
1. A(BC) = (AB)(AC) 2. A(BC) = (AB)(AC) 3. (BC)A = (BA)(CA) 4. (BC)A = (BA)(CA)
2020/7/31
《集合论与图论》第5讲
21
n元关系(n-ary relation)
n元关系: 是集合, 其元素全是有序n元组. 例1: F1={<a,b,c,d>,<1,2,3,4>,
<物理,化学,生物,数学>}, F1是4元关系. 例2: F2={<a,b,c>,<,,>,
<大李,小李,老李>} F2是3元关系. #
25
A到B的二元关系(举例)
例: 设 A={a1,a2}, B={b}, 则A到B的二元关系共有4个:
R1=,
R2={<a1,b>},
R3={<a2,b>}, R4={<a1,b>,<a2,b>}.
B到A的二元关系也有4个:
R5=,
R6={<b,a1>},
R7={<b,a2>}, R8={<b,a1>,<b,a2>}. #
2020/7/31
《集合论与图论》第5讲
10
卡氏积非交换性
非交换: AB BA (除非 A=B A= B=)
反例: A={1}, B={2}. AB={<1,2>}, BA={<2,1>}.
2020/7/31
《集合论与图论》第5讲
11
卡氏积非结合性
非结合: (AB)C A(BC) (除非 A= B= C=)
2020/7/31
《集合论与图论》第5讲
34
特殊关系(续)
设AR, 则可以定义A上的: 小于等于(less than or equal to)关系:
LEA = { <x,y> | xA yA xy } 小于(less than)关系,
LA = { <x,y> | xA yA x<y } 大于等于(greater than or equal to)关系 大于(great than)关系,…
2m2
2020/7/31
《集合论与图论》第5讲
29
A上的二元关系(例1,续2)
R12 = { <a1,a1>,<a1,a2>,<a2,a1>
}
R13 = { <a1,a1>,<a1,a2>,
<a2,a2> }
R14 = { <a1,a1>,
<a2,a1>,<a2,a2> }
R15 = {
<a1,a2>,<a2,a1>,<a2,a2> }
有序对: <a,b> = { {a}, {a,b} }
其中, a是第一元素, b是第二元素. <a,b>也记作(a,b) 定理1: <a,b>=<c,d> a=cb=d 推论: ab <a,b><b,a>
2020/7/31
《集合论与图论》第5讲
3
有序对(引理1)
引理1: {x,a}={x,b} a=b 证明: () 显然.
() 由引理2, <a,b>=<c,d> {{a},{a,b}}={{c},{c,d}} ∪{{a},{a,b}}=∪{{c},{c,d}}{a,b}={c,d}. 又 {{a},{a,b}}={{c},{c,d}} ∩{{a},{a,b}}=∩{{c},{c,d}} {a}={c} a=c. 再由引理1, 得b=d. #
定理2: <a1,a2,…,an>= <b1,b2,…,bn> ai = bi, i =1,2,…,n. #
2020/7/31
《集合论与图论》第5讲
8卡氏积(Cຫໍສະໝຸດ rtesian product)卡氏积: AB={<x,y>|xAyB}.
例: A={,a}, B={1,2,3}. AB={<,1>,<,2>,<,3>,<a,1>,<a,2>,<a,3>}. BA={<1,>,<1,a>,<2,>,<2,a>,<3,>,<3,a>}. AA={ <,>, <,a>, <a,>, <a,a>}. BB={ <1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,
2020/7/31
《集合论与图论》第5讲
13
卡氏积分配律(证明1)
A(BC) = (AB)(AC). 证明: <x,y>, <x,y>A(BC) xAy(BC) xA(yByC) (xAyB)(xAyC) (<x,y>AB)(<x,y>AC) <x,y>(AB)(AC)
A(BC) = (AB)(AC). #
D
A
A
C
BC
B
A(BC) = (AB)(AC) ACBDABCD
2020/7/31
《集合论与图论》第5讲
16
例题1(证明(2))
(2) 若A, 则ABAC BC. 证明: () 若 B=, 则 BC.
设 B, 由A, 设xA. y, yB<x,y>AB
<x,y>AC xAyC yC. BC
2020/7/31
2m2
2020/7/31
《集合论与图论》第5讲
31
一些特殊关系
空关系 恒等关系 全域关系 整除关系 小于等于关系,… 包含关系, 真包含关系
2020/7/31
《集合论与图论》第5讲
32
特殊关系
设A是任意集合, 则可以定义A上的: 空关系:
恒等关系:
IA = { <x,x> | xA } 全域关系:
《集合论与图论》第5讲
17
例题1(证明(2),续)
(2) 若A, 则ABACBC. 证明(续): ()若B=,则AB=AC.
设 B. <x,y>, <x,y>AB xAyB
xAyC <x,y>AC ABAC. # 讨论: 在()中不需要条件 A.
2020/7/31
《集合论与图论》第5讲