北大离散数学04

东北⼤学离散数学复习总结（满分版）⽅法、知识点总结（知识重点和考题重点）前三章重点内容（知识重点）：1、蕴含（条件）“→”的真值P→Q的真值为假，当且仅当P为真，Q为假。

2、重⾔(永真)蕴涵式证明⽅法<1>假设前件为真，推出后件也为真。

<2>假设后件为假，推出前件也为假。

易错3、等价公式和证明中运⽤4、重要公式重⾔蕴涵式：P∧Q => P or QP or Q => p∨QA->B =>(A∧or∨C)->(B∧or∨C)其他是在此基础上演变等价公式：幂等律P∧P=P P∨P=P吸收律P∧(P∨Q)=P P∨(P∧Q)=P同⼀律P∨F=P P∧T=PP∨T=T P∧F=FP <-> Q = (P->Q)∧(Q->P) = (P∧Q)∨(﹁P∧﹁Q)5、范式的写法（最⽅便就是真值表法）6、派遣⼈员、课表安排类算法：第⼀步：列出所有条件，写成符号公式第⼆步：⽤合取∧连接第三步：求上⼀步中的析取范式即可7、逻辑推理的写法直接推理论证：其中I公式是指重⾔蕴涵式那部分其中E公式是指等价公式部分条件论证: 形如~ , ~, ~ => R->SR P(附加条件)... ...S TR->S CP8、谓词基本内容注意：任意⽤—> 连接存在⽤∧连接量词的否定公式量词的辖域扩充公式量词分配公式其他公式9、带量词的公式在论域内的展开10、量词辖域的扩充公式11、前束范式的写法给定⼀个带有量词的谓词公式，1)消去公式中的联接词→和←→(为了便于量词辖域的扩充)；2)如果量词前有“﹁ ”，则⽤量词否定公式﹁ ”后移。

再⽤摩根定律或求公式的否定公式，将“﹁ ”后移到原⼦谓词公式之前；3)⽤约束变元的改名规则或⾃由变元的代⼊规则对变元换名(为量词辖域扩充作准备)；4)⽤量词辖域扩充公式提取量词，使之成为前束范式形式。

简要概括：1、去-> ，<-> 2、移﹁3、换元4、量词辖域扩充12、谓词演算的推理理论推理规则：P、T、CP、US、ES、EG、UG 的使⽤ES US 去量词EG UG 添量词★谨记：ES要在US之前,很重要添加量词注意事项：13、集合的幂集（⽤P表⽰，也常有花P表⽰）A是集合，由A的所有⼦集构成的集合，称之为A的幂集。

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

第三部分逻辑学第六章命题逻辑第一节命题演算6-1-1 命题1.什麽叫命题其结果能判断真假，但不能既真又假的陈述句，称为命题。

作为判断使用的句子都是陈述句。

2.作为命题的陈述句，不能分成更简单的陈述句，这样的命题叫原子命题。

即简单命题。

3.什麽叫命题的真值作为命题的陈述句的判断结果，即正确（对应着真命题）或错误（对应着假命题）的两个值。

4.为了研究方便，我们把简单命题符号化。

每一个简单命题用一个小写英文字母表示。

而命题真值也要符号化。

用 1 表示命题的结果是真，即真命题；用 0 表示命题的结果是假，即假命题。

联结词与复合命题及其真值1.我们称用联结词联结在一起的简单命题为复合命题。

（1）否定联结词与命题否定式：“﹁”是否定联结词。

通过他可以构成命题否定式。

例如：用 p 表示“4是素数”。

p 的真值显然是假，即真值为 0；¬ p 表示假命题 p 的否定式，¬ p 的真值自然为真，即为 1。

（2）合取联结词与命题的合取式：“∧”是合取联结词。

通过他可以构成命题的合取式。

例如：p∧q，即 p 与 q 同时为真，复合命题的值才为真，即0 ∧ 0 = 0；0 ∧ 1 = 0；1 ∧ 0 = 0；1 ∧ 1 = 1。

所以，在p，q取不同真值的4种情况下，命题的合取式只有一个真值。

（3）析取联结词与命题析取式：“∨”是析取联结词。

通过他可以构成命题的析取式。

例如：p∨q，只要 p 、q 中至少一个真值为真，其值便为真，即0 ∨ 0 = 0；0 ∨ 1 = 1；1 ∨ 0 = 1；1 ∨ 1 = 1。

所以，在 4 种情况下，只有一个情况是假命题，即简单命题同时为假时命题析取式真值为 0。

（4）蕴涵联结词与命题蕴涵式：“如果... 则...”被称为蕴涵联结词，采用蕴涵符号“→”。

在这类句型中，q 是 p 的必要条件；p 是 q 的充分条件；蕴涵式 p→q 只有一个假值，即p为真，q 为假时蕴涵式命题的真值为 0。

15秋《离散数学》作业4
一、单选题（共 10 道试题，共 100 分。

）
1.
.
.
.
.
正确答案：
2.
.
.
.
.
正确答案：
3. 至少要去掉多少条边才能将一个10阶完全图变成非连通图（）
. 6
. 9
. 10
. 15
正确答案：
4. 同类型的代数系统不具有的特征是（）
. 子代数的个数相同
. 运算个数相同
. 相同的构成成分
. 相同元数的运算个数相同
正确答案：
5.
.
.
.
.
正确答案：
6. 设图G是有6个顶点的连通图，总度数为20，则从G中删去( )边后使之变成树．. 10
. 5
. 3
. 2
正确答案：
7.
.
.
.
.
正确答案：
8.
.
.
.
.
正确答案：
9.
.
.
.
.
正确答案：
10. 只有有限个元素的集合，称为（）. 实数集
. 自然数集
. 复数集
. 有限集合
正确答案：。