1. 离散数学学习笔记从命题逻辑到图论作为一名计算机专业的学生我深刻体会到离散数学在计算机科学中的重要性。这门课程不仅是数据结构、数据库等后续课程的基础更是培养计算思维和抽象建模能力的核心课程。下面我将分享我在学习《离散数学》过程中整理的笔记希望能帮助到同样在学习这门课程的同学。提示本文内容基于浙江科技大学信息与电子工程学院的教学大纲和课程内容整理适合作为计算机相关专业学生的复习参考资料。1.1 课程概述与学习目标离散数学主要研究离散量的结构及其相互关系是现代数学的重要分支。在计算机科学领域离散数学的应用无处不在数据结构树、图等概念直接来源于离散数学数据库关系代数、范式理论等都以离散数学为基础算法设计图论、组合数学等是算法设计的理论基础计算机组成逻辑电路设计需要命题逻辑和布尔代数知识通过本课程的学习学生应达到以下目标掌握命题逻辑和谓词逻辑的基本原理和应用理解集合论和关系理论的核心概念能够运用图论知识解决实际问题培养严谨的数学思维和抽象建模能力2. 命题逻辑详解2.1 基本概念与联结词命题是具有唯一真值的陈述句。例如北京是中国的首都是一个真命题236是一个假命题。命题联结词是连接命题的基本工具否定(¬)命题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∨Q2.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∩B4.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∈R4.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. 学习心得与应试技巧在学习离散数学的过程中我总结了以下几点经验概念理解离散数学的概念抽象一定要通过具体例子来理解。例如理解等价关系时可以思考同班同学关系是否满足自反、对称、传递性。多做练习特别是命题逻辑的范式转换、关系的闭包运算等需要通过大量练习来掌握。建立联系将离散数学的概念与计算机科学中的实际问题联系起来。例如理解图论中的最短路径问题与网络路由算法的关系。应试技巧命题逻辑熟练掌握等价式和永真蕴含式谓词逻辑注意量词的顺序和辖域集合与关系掌握各种性质的判断方法图论记住各种特殊图的判定定理常见错误混淆必要和充分条件忽视空集的特殊性错误理解反对称的定义离散数学作为计算机科学的基础课程其重要性不言而喻。希望通过这份笔记能够帮助大家更好地理解和掌握这门课程的核心内容。在实际学习中建议结合具体的编程实践来加深理解例如用代码实现图的遍历算法或者命题逻辑的真值表计算等。