SYSTEMATIC MATHEMATICS

离散数学

本课程分为 8 个按内容确定长度的单元,各单元分别有 4、4、4、5、5、5、9、4 章,共 40 个可直接学习的知识章节。不逐个列出,怎样知道一共有多少种排列?一个网络怎样以最低成本连接所有地点?一条反复执行的规则最终会不会停下?离散数学研究选择、字符串、日程和网络这类一个一个分开的对象,而不是连续变化的长度。课程先把普通说法写成能判断真假的准确句子、真值表、范式与带量词的命题,再按依赖顺序学习集合、函数、关系、证明方法、计数、Pascal 恒等式与二项式定理、归纳、递归、循环不变量、递推、生成函数、渐近界、无向与有向可达性、加权路径、生成树、匹配、着色、有限概率与期望。每个新符号都先说明名称和意思再使用,每个主要结论都给出可检查的论证;错误初始化、负权、图不连通、箭头反向、贪心陷阱、奇环与初值不足等边界也会明确说明。课程调度综合项目在所需有向图工具之后作为最后一章。

本课程之前: 代数与函数第 1–3 章:变量、方程、不等式与解集。不要求先修证明、编程、概率或图论课程。

COURSE FACTSLevel, chapters, units, prerequisite, and outcome
第 1 章

命题在解释下具有真值

目标: 为什么假前提不是 p→q 的反例?

命题是在术语与语境确定后为真或为假的陈述句。

对象与证书:在固定解释下,一个命题有一个真值;¬p、p∧q、p∨q 与 p→q 按定义的真值规则形成新命题。 本节要建立的结论是:蕴含 p→q 恰好在 p 真且 q 假时为假。 判断所需证据是真值表、见证、双射、划分、归纳链、不变量、递推、图追踪还是归一化概率。

例题是:当 p=true、q=false 时,求 (p→q)∧p 的真值。 从“在唯一违反行中 p→q 为假。”开始,以“false∧true 为假。”完成重建。再把证书与这个边界比较:“打开门”是命令,不是具有真值的命题。

蕴含 p→q 恰好在 p 真且 q 假时为假。

蕴含承诺在每个 p 成立的情形中 q 也成立。

p=true、q=false 这一行违反承诺。

若 p 假则没有活动的 p 情形;若 q 真则承诺结果成立。

当 p=true、q=false 时,求 (p→q)∧p 的真值。

  1. 在唯一违反行中 p→q 为假。
  2. p 本身为真。 这一步独立检查所述有限实例。
  3. false∧true 为假。 这一步独立检查所述有限实例。

结果: 复合命题为假。