1. 离散数学学习笔记：从命题逻辑到图论
作为一名计算机专业的学生，我深刻体会到离散数学在计算机科学中的重要性。这门课程不仅是数据结构、数据库等后续课程的基础，更是培养计算思维和抽象建模能力的核心课程。下面我将分享我在学习《离散数学》过程中整理的笔记，希望能帮助到同样在学习这门课程的同学。
提示：本文内容基于浙江科技大学信息与电子工程学院的教学大纲和课程内容整理，适合作为计算机相关专业学生的复习参考资料。
1.1 课程概述与学习目标
离散数学主要研究离散量的结构及其相互关系，是现代数学的重要分支。在计算机科学领域，离散数学的应用无处不在：
- 数据结构：树、图等概念直接来源于离散数学
- 数据库：关系代数、范式理论等都以离散数学为基础
- 算法设计：图论、组合数学等是算法设计的理论基础
- 计算机组成：逻辑电路设计需要命题逻辑和布尔代数知识
通过本课程的学习，学生应达到以下目标：
- 掌握命题逻辑和谓词逻辑的基本原理和应用
- 理解集合论和关系理论的核心概念
- 能够运用图论知识解决实际问题
- 培养严谨的数学思维和抽象建模能力
2. 命题逻辑详解
2.1 基本概念与联结词
命题是具有唯一真值的陈述句。例如："北京是中国的首都"是一个真命题，"2+3=6"是一个假命题。
命题联结词是连接命题的基本工具：
- 否定(¬)：命题P的否定记作¬P
- 合取(∧)：P∧Q表示"P且Q"
- 析取(∨)：P∨Q表示"P或Q"
- 蕴含(→)：P→Q表示"如果P则Q"
- 等价(↔)：P↔Q表示"P当且仅当Q"
注意：在自然语言中，"或"有时表示"排他或"(要么P，要么Q，但不能同时)，但在逻辑中"∨"表示"可兼或"(可以同时为真)。
2.2 命题公式与等价式
命题公式是由命题变元和联结词组成的表达式。例如：(P→Q)∧(Q→P)是一个命题公式。
常用等价式：
- 交换律：P∨Q ⇔ Q∨P
- 结合律：(P∨Q)∨R ⇔ P∨(Q∨R)
- 分配律：P∨(Q∧R) ⇔ (P∨Q)∧(P∨R)
- 德摩根律：¬(P∨Q) ⇔ ¬P∧¬Q
- 蕴含律：P→Q ⇔ ¬P∨Q
2.3 范式与推理理论
范式是命题公式的标准形式，主要有两种：
- 析取范式：由简单合取式组成的析取式
- 合取范式：由简单析取式组成的合取式
求范式的步骤：
- 消去→和↔
- 将¬内移或消去
- 使用分配律
推理理论包括：
- 真值表法
- 推理规则法(P规则、T规则、CP规则)
- 间接证明法(反证法)
3. 谓词逻辑深入解析
3.1 谓词与量词
谓词逻辑扩展了命题逻辑，可以表达更复杂的逻辑关系。
基本概念：
- 个体词：可以独立存在的客体
- 谓词：描述个体性质或关系的词
- 量词：
- 全称量词∀：表示"对于所有"
- 存在量词∃：表示"存在"
例如："所有学生都学习数学"可以表示为：∀x(S(x)→M(x))，其中S(x)表示"x是学生"，M(x)表示"x学习数学"。
3.2 谓词公式与变元约束
谓词公式由谓词、个体词、量词和联结词组成。例如：∀x(P(x)→∃yQ(x,y))。
变元约束相关概念：
- 辖域：量词的作用范围
- 自由变元：不受量词约束的变元
- 约束变元：受量词约束的变元
3.3 前束范式与推理规则
前束范式是将所有量词都移到公式最前面的标准形式。例如：∀x∃y(P(x)∨Q(y))。
谓词逻辑的推理规则：
- 全称指定(US)
- 全称推广(UG)
- 存在指定(ES)
- 存在推广(EG)
4. 集合与关系的核心概念
4.1 集合运算与性质
集合的基本运算：
- 并集：A∪B = {x | x∈A ∨ x∈B}
- 交集：A∩B = {x | x∈A ∧ x∈B}
- 差集：A-B = {x | x∈A ∧ x∉B}
- 补集：A' = {x | x∉A}
- 对称差：A⊕B = (A-B)∪(B-A)
集合运算的性质：
- 交换律：A∪B = B∪A
- 结合律：(A∪B)∪C = A∪(B∪C)
- 分配律：A∪(B∩C) = (A∪B)∩(A∪C)
- 德摩根律：(A∪B)' = A'∩B'
4.2 关系及其表示
关系是集合笛卡尔积的子集。例如：A={1,2}, B={a,b}, 则R={<1,a>,<2,b>}是A到B的一个关系。
关系的表示方法：
- 集合表示法：列举所有序偶
- 矩阵表示法：用0/1矩阵表示关系
- 图表示法：用有向图表示关系
关系的性质：
- 自反性：∀x∈X, <x,x>∈R
- 对称性：<x,y>∈R ⇒ <y,x>∈R
- 传递性：<x,y>∈R ∧ <y,z>∈R ⇒ <x,z>∈R
4.3 闭包运算与等价关系
闭包运算是在原有关系基础上添加最少的序偶使其具有某种性质：
- 自反闭包r(R)：使关系R具有自反性
- 对称闭包s(R)：使关系R具有对称性
- 传递闭包t(R)：使关系R具有传递性
等价关系是同时具有自反性、对称性和传递性的关系。等价关系可以将集合划分为互不相交的等价类。
5. 函数与图论基础
5.1 函数的分类与性质
函数是一种特殊的关系，满足每个输入对应唯一输出。
函数的分类：
- 入射函数(单射)：不同的输入对应不同的输出
- 满射函数：值域等于陪域
- 双射函数：既是单射又是满射
5.2 图的基本概念
图由顶点集V和边集E组成，记作G=(V,E)。
图的分类：
- 无向图：边没有方向
- 有向图：边有方向
- 简单图：无自环和重边
- 完全图：任意两个顶点之间都有边
图的相关概念：
- 度数：与顶点关联的边数
- 路径：顶点和边的交替序列
- 连通性：任意两个顶点之间存在路径
5.3 特殊图与算法
- 欧拉图：包含经过每条边一次的回路
- 哈密顿图：包含经过每个顶点一次的回路
- 平面图：可以在平面上画出且边不相交
- 树：连通无环图
重要算法：
- Kruskal算法：求最小生成树
- Huffman算法：构造最优二叉树
6. 学习心得与应试技巧
在学习离散数学的过程中，我总结了以下几点经验：
概念理解：离散数学的概念抽象，一定要通过具体例子来理解。例如，理解等价关系时，可以思考"同班同学"关系是否满足自反、对称、传递性。
多做练习：特别是命题逻辑的范式转换、关系的闭包运算等，需要通过大量练习来掌握。
建立联系：将离散数学的概念与计算机科学中的实际问题联系起来。例如，理解图论中的最短路径问题与网络路由算法的关系。
应试技巧：
- 命题逻辑：熟练掌握等价式和永真蕴含式
- 谓词逻辑：注意量词的顺序和辖域
- 集合与关系：掌握各种性质的判断方法
- 图论：记住各种特殊图的判定定理
常见错误：
- 混淆"必要"和"充分"条件
- 忽视空集的特殊性
- 错误理解"反对称"的定义
离散数学作为计算机科学的基础课程，其重要性不言而喻。希望通过这份笔记，能够帮助大家更好地理解和掌握这门课程的核心内容。在实际学习中，建议结合具体的编程实践来加深理解，例如用代码实现图的遍历算法或者命题逻辑的真值表计算等。
