北大离散数学
- 格式：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课件是学习离散数学的重要辅助工具，它通过图示、例子和练习等形式，帮助学生更好地理解和掌握离散数学的概念和方法。
离散数学教程-北大社
内容简介本书共分五编。
第一编为集合论，其中包括集合的基本概念、二元关系、函数、自然数、基数、序数。
第二编为图论，其中包括图的基本概念、图的连通性、欧拉图与哈密顿图、树、平面图、图的着色、图的矩阵表示、覆盖集、独立集、匹配、带权图及其应用。
第三编为代数结构，其中包括代数系统的基本概念、几个重要的代数系统：半群、群、环、域、格与布尔代数。
第四编为组合数学，其中包括组合存在性、组合计数、组合设计与编码以及组合最优化。
第五编为数理逻辑，其中包括命题逻辑、一阶谓词逻辑、Herbrand定理和直觉逻辑。
本书体系严谨、内容丰富、配有大量的例题和习题，并与计算机科学的理论与实践密切结合。
本书不仅适用于计算机及相关专业的本科生或研究生，也可供计算机专业的科技人员使用或参考。
目录第一编集合论第一章集合(1)1.1 预备知识(1)1.2 集合的概念及集合之间的关系(7)1.3 集合的运算(10)1.4 基本的集合恒等式(13)1.5 集合列的极限(17)习题一(20)第二章二元关系(23)2.1 有序对与卡氏积(23)2.2 二元关系(26)2.3 关系矩阵和关系图(32)2.4 关系的性质(34)2.5 二元关系的幂运算(37)2.6 关系的闭包(39)2.7 等价关系和划分(45)2.8 序关系(49)习题二(53)第三章函数(58)3.1 函数的基本概念(58)3.2 函数的性质(59)3.3 函数的合成(62)3.4 反函数(64)习题三(68)第四章自然数(70)4.1 自然数的定义(70)4.2 传递集合(74)4.3 自然数的运算(76)4.4 N上的序关系(78)习题四(80)第五章基数(势)(81)5.1 集合的等势(81)5.2 有穷集合与无穷集合(83)5.3 基数(84)5.4 基数的比较(85)5.5 基数运算(89)习题五(93)第六章序数(95)6.1 关于序关系的进一步讨论(95) 6.2 超限递归定理(97)6.3 序数(99)6.4 关于基数的进一步讨论(105)习题六(105)第二编图论第七章图(107)7.1 图的基本概念(107)7.2 通路与回路(119)7.3 无向图的连通性(121)7.4 无向图的连通度(123)7.5 有向图的连通性(129)习题七(130)第八章欧拉图与哈密顿图(132)8.1 欧拉图(132)8.2 哈密顿图(137)习题八(142)第九章树(144)9.1 无向树的定义及性质(144)9.2 生成树(146)9.3 环路空间(149)9.4 断集空间(151)9.5 根树(153)习题九(154)第十章图的矩阵表示(156)10.1 关联矩阵(156)10.2 邻接矩阵与相邻矩阵(159)习题十(163)第十一章平面图(165)11.1 平面图的基本概念(165)11.2 欧拉公式(168)11.3 平面图的判断(170)11.4 平面图的对偶图(172)11.5 外平面图(175)11.6 平面图与哈密顿图(177)习题十一(179)第十二章图的着色(180)12.1 点着色(180)12.2 色多项式(181)12.3 地图的着色与平面图的点着色(185)12.4 边着色(187)习题十二(189)第十三章支配集、覆盖集、独立集与匹配(190)13.1 支配集、点覆盖集、点独立集(190)13.2 边覆盖集与匹配(193)13.3 二部图中的匹配(198)习题十三(199)第十四章带权图及其应用(201)14.1 最短路径问题(201)14.2 关键路径问题(204)14.3 中国邮递员问题(206)14.4 最小生成树(208)14.5 最优树(213)14.6 货郎担问题(216)习题十四(220)第三编代数结构第十五章代数系统(222)15.1 二元运算及其性质(222)15.2 代数系统、子代数和积代数(227) 15.3 代数系统的同态与同构(230)15.4 同余关系和商代数(233)15.5 Σ代数(236)习题十五(237)第十六章半群与独异点(240)16.1 半群与独异点(240)16.2 有穷自动机(242)习题十六(247)第十七章群(249)17.1 群的定义和性质(249)17.2 子群(253)17.3 循环群(255)17.4 变换群和置换群(257)17.5 群的分解(263)17.6 正规子群和商群(269)17.7 群的同态与同构(272)17.8 群的直积(278)习题十七(281)第十八章环与域(285)18.1 环的定义和性质(285)18.2 子环、理想、商环和环同态(289) 18.3 有限域上的多项式环(294)习题十八(296)第十九章格与布尔代数(299)19.1 格的定义和性质(299)19.2 子格、格同态和格的直积(303)19.3 模格、分配格和有补格(307)19.4 布尔代数(311)习题十九(318)第四编组合数学第二十章组合存在性定理(322)20.1 鸽巢原理和Ramsey定理(322)20.2 相异代表系(331)习题二十(335)第二十一章基本的计数公式(337)21.1 两个计数原则(337)21.2 排列和组合(338)21.3 二项式定理与组合恒等式 (343)21.4 多项式定理(347)习题二十一(349)第二十二章组合计数方法(352)22.1 递推方程的公式解法(352)22.2 递推方程的其他解法(361)22.3 生成函数的定义和性质(370)22.4 生成函数与组合计数(375)22.5 指数生成函数与多重集的排列问题(384) 22.6 Catalan数与Stirling数(388)习题二十二(394)第二十三章组合计数定理(398)23.1 包含排斥原理(398)23.2 对称筛公式及应用(403)23.3 Burnside引理(410)23.4 Polya定理(414)习题二十三(420)第二十四章组合设计与编码(422)24.1 拉丁方(422)24.2 t设计(427)24.3 编码(436)24.4 编码与设计(446)习题二十四(449)第二十五章组合最优化问题(450)25.1 组合优化问题的一般概念 (450)25.2 网络的最大流问题(452)习题二十五(457)第五编数理逻辑第二十六章命题逻辑(458)26.1 形式系统(458)26.2 命题和联结词(461)26.3 命题形式和真值表(464)26.4 联结词的完全集(468)26.5 推理形式(471)26.6 命题演算的自然推理形式系统N(473)26.7 命题演算形式系统P(486)26.8 N与P的等价性(494)26.9 赋值(496)26.10 可靠性、和谐性与完备性 (505)习题二十六(507)第二十七章一阶谓词演算(511)27.1 一阶谓词演算的符号化(511)27.2 一阶语言(515)27.3 一阶谓词演算的自然推演形式系统N L(519) 27.4 一阶谓词演算的形式系统K L(530)27.5 N L与K L的等价性(534)27.6 K L的解释与赋值(536)27.7 K L的可靠性与和谐性(547)27.8 K L的完全性(551)习题二十七(558)第二十八章消解原理(562)28.1 命题公式的消解(562)28.2 Herbrand定理(567)28.3 代换与合一代换(572)28.4 一阶谓词公式的消解(576)习题二十八(581)第二十九章直觉主义逻辑(583)29.1 直觉主义逻辑的直观介绍(583)29.2 直觉主义的一阶谓词演算的自然推演形式系统(58 5)29.3 直觉主义一阶谓词演算形式系统IK L(594)29.4 直觉主义逻辑的克里普克(Kripke)语义(597)29.5 直觉主义逻辑的完备性(602)习题二十九(607)附录1 第一编与第二编符号注释与术语索引(608)附录2 第三编与第四编符号注释与术语索引(614)附录3 第五编符号注释与术语索引(620)参考书目和文献(624)05668本书共分4大部分，数理逻辑部分包括命题逻辑的基本概念、等值演算、范式与推理理论，一阶逻辑的基本概念、前束范式以及推理理论。
北京大学离散数学教材 1
命题逻辑基本概念1逻辑是解决推理方法的学科，中心是推理，基本要素是命题，所以称为命题逻辑。
数理逻辑则是用数学方法研究推理。
学习目的本章首先要深刻理解命题的概念，理解原子命题和符合命题的关系，在此基础之上理解逻辑联结词的定义，命题公式的定义和分类，最后熟练掌握并应用真值表的构造基本内容：z命题概念；z逻辑联结词概念，复合命题和联结词的关系；z命题符号化和翻译z合式公式概念及分类；z构造真值表判定公式类型命题(statement, proposition)概念在二值逻辑中，命题是或真或假，而不会同时又真又假的陈述句。
z陈述句；z或真或假，唯一真值；例：(1) 地球是圆的；真的陈述句，是命题(2) 2+3=5；真的陈述句，是命题(3) 你知道命题逻辑吗？非陈述句，故非命题(4) 3-x=5；陈述句,但真假随x的变化而变化，非命题(5) 请安静！非陈述句，故非命题(6) 火星表面的温度是800°C；现时不知真假的陈述句，但只能要么真要么假，故是命题(7) 明天是晴天；尽管要到第二天才能得知其真假，但的确是要么真要么假，故是命题(8) 我正在说谎；无法得知其真假，这是悖论注意: (4)不是命题，后续章节中会提到，这被称为谓词，命题函数或命题变项。
分类：z简单命题，通常用p, q, r,…,等表示命题变项，命题常项用1(T)，0(F)表示；z复合命题，由简单命题和联结词构成；逻辑联结词和复合命题多个命题变项由联结词联结起来成为复合命题。
否定式和否定联结词(negation)命题p的非或否定，称为p的否定式，表示为¬p；符号¬即为否定联结词。
真值表：p¬ pT FF T严格说，¬ p不是复合命题。
例：p：今天天气好；¬p：今天天气不好p：2+5>1；¬p： 2+5≤1；在此情形下，p为真，¬p为假。
合取式和合取联结词(conjunction)p且q称为p, q的合取式，记为p∧q；符号∧即为合取联结词。
第十七章 群 北京大学计算机系离散数学讲义(ppt版)
说明：证明用到逆元的定义式 2 可以推广到有限个元素之积.
2020/6/30
群的性质（续）
方程 ax=b 和 ya=b 在群 G 中有解且有唯一解. 证: a-1b 是 ax=b 的解.
假设 c 为解，则 c = ec = (a-1a)c =a-1(ac) = a-1b
aG, 方程 ax=e 有解，得到 a 的右逆元.
2020/6/30
群的性质（续）
消去律 ab= ac b=c, ba = ca b=a 说明：消去律也可以定义群 设 G 是有限半群，且不含零元.若 G 中成立消去律，则 G 是群. 证：设 G={a1=e,a2,…,an}，任取 aiG，
aiG ={aiaj |j=1,2,…,n} 由封闭性, aiGG, 假设|aiG|<n, 则存在 j,k 使得 aiaj=aiak, 根据消去律，aj=ak, 矛盾. 所以 aiG=G. 任取 ai,aj, ai,ajG ajaiG 方程 aix=aj 有解 同理，方程 yai=aj 有解.G 是群. 注：<Z5,>不是群，因为有 0；<Z+,>也不是群，无限.
只要证 s=q (at)q=(at)r/d=(ar)t/d=ep=e
s|q (at)s=e ats=e r|ts q|ps
q|s （p,q 互素） 分析：相互整除
2020/6/30
|a|=r, ak=e 当且仅当 r|k
关于群性质的证明题（续）
例 5 设 G 为有限群，x,yG, y 为 2 阶元，xe, 且 x2y=yx, 求|x|
2020/6/30
群的性质（续）
G 为群，aG, 且|a|=r, 则 （1）ak =e r | k （2）|a|=|a-1| （3）若|G| = n, 则 rn. 证 （1）充分性. ak = arl =(ar)l=el = e
2020/6/30
群的性质（续）
方程 ax=b 和 ya=b 在群 G 中有解且有唯一解. 证: a-1b 是 ax=b 的解.
假设 c 为解，则 c = ec = (a-1a)c =a-1(ac) = a-1b
aG, 方程 ax=e 有解，得到 a 的右逆元.
2020/6/30
群的性质（续）
消去律 ab= ac b=c, ba = ca b=a 说明：消去律也可以定义群 设 G 是有限半群，且不含零元.若 G 中成立消去律，则 G 是群. 证：设 G={a1=e,a2,…,an}，任取 aiG，
aiG ={aiaj |j=1,2,…,n} 由封闭性, aiGG, 假设|aiG|<n, 则存在 j,k 使得 aiaj=aiak, 根据消去律，aj=ak, 矛盾. 所以 aiG=G. 任取 ai,aj, ai,ajG ajaiG 方程 aix=aj 有解 同理，方程 yai=aj 有解.G 是群. 注：<Z5,>不是群，因为有 0；<Z+,>也不是群，无限.
只要证 s=q (at)q=(at)r/d=(ar)t/d=ep=e
s|q (at)s=e ats=e r|ts q|ps
q|s （p,q 互素） 分析：相互整除
2020/6/30
|a|=r, ak=e 当且仅当 r|k
关于群性质的证明题（续）
例 5 设 G 为有限群，x,yG, y 为 2 阶元，xe, 且 x2y=yx, 求|x|
2020/6/30
群的性质（续）
G 为群，aG, 且|a|=r, 则 （1）ak =e r | k （2）|a|=|a-1| （3）若|G| = n, 则 rn. 证 （1）充分性. ak = arl =(ar)l=el = e
北大离散数学ppt课件
2020/6/2
《集合论与图论》第5讲
35
特殊关系(续)
设A为任意集合, 则可以定义P(A)上的: 包含关系:
A = { <x,y> | xA yA xy } 真包含关系:
A = { <x,y> | xA yA xy }
2020/6/2
第5讲 二元关系的基本概念 北京大学
内容提要 1. 有序对与卡氏积 2. 二元关系 3. 二元关系的基本运算
2020/6/2
《集合论与图论》第5讲
1
有序对与卡氏积
有序对(有序二元组) 有序三元组, 有序n元组 卡氏积 卡氏积性质
2020/6/2
《集合论与图论》第5讲
2
有序对(ordered pair)
D
A
A
C
BC
B
A(BC) = (AB)(AC) ACBDABCD
2020/6/2
《集合论与图论》第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/6/2
2020/6/2
《集合论与图论》第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/6/2
《集合论与图论》第5讲
15
卡氏积图示
2m2
2020/6/2
- 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讲