北大离散数学

2020/9/26
《集合论与图论》第9讲
12
例2(解(2))
例2: (2) A2={a,b,c}, B2={1,2}, 解: (2) A2B2中无单射,无双射,满射6个:
f1={<a,1>,<b,1>,<c,2>}, f2={<a,1>,<b,2>,<c,1>}, f3={<a,2>,<b,1>,<c,1>}, f4={<a,1>,<b,2>,<c,2>}, f5={<a,2>,<b,1>,<c,2>}, f6={<a,2>,<b,2>,<c,1>}.
2020/9/26
《集合论与图论》第9讲
26
定理3(证明)
证明: (2) dom(f○g) = A. 显然dom(f○g)A,下证Adom(f○g),
x, xA !y(yBxgy) !y!z(yBzCxgyyfz) !z(zCx(f○g)z) xdom(f○g).
2020/9/26
《集合论与图论》第9讲
第9讲 函数
内容提要 函数,偏函数,全函数,真偏函数 单射,满射,双射,计数问题 象,原象 常数函数,恒等函数,特征函数,单调函数,
自然映射 合成(复合),反函数,单边逆(左逆,右逆) 构造双射(有穷集,无穷集)
2020/9/26
《集合论与图论》第9讲
1
函数(function),映射(mapping)
2020/9/26
《集合论与图论》第9讲
21
特殊函数
常数函数: f:AB, bB, xA, f(x)=b

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学习目的本章主要涉及命题演算中两个重要内容之一：等值演算。

首先理解命题公式等值的含义，掌握构造真值表和不构造真值表两种方法证明等值式，熟练应用于命题公式的化简和范式表示基本内容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，则Φ⇔Ψ。