电大《离散数学》考试复习资料

电大《离散数学》考试复习资料各位同学，大家好。离散数学作为计算机科学与技术领域的基础学科，其概念抽象、逻辑性强，是不少同学学习的难点，也是电大考试中需要重点攻克的科目。这份复习资料旨在帮助大家梳理核心知识点，明确复习重点，掌握解题思路与方法，希望能为大家的备考之路提供一些切实的帮助。请务必结合教材例题和课后习题进行深入理解和练习，方能真正融会贯通。一、数理逻辑数理逻辑是离散数学的基础，主要研究推理的有效性。这部分内容概念较多，符号抽象，需要同学们耐心琢磨。（一）命题逻辑复习建议：这是数理逻辑的入门，也是重中之重。要准确理解命题的概念，熟练掌握各种联结词的逻辑含义及真值表，这是后续学习的基石。1.命题与联结词：*命题：能判断真假的陈述句。注意：悖论不是命题，祈使句、疑问句、感叹句不是命题。*联结词：否定（¬）、合取（∧）、析取（∨）、蕴含（→）、等价（↔）。务必牢记它们的真值表，特别是蕴含联结词“→”的真值情况，这是易错点。理解“只有P，才Q”、“除非P，否则Q”等自然语言表述对应的逻辑联结词。2.命题公式与赋值：*命题公式的定义（合式公式）。*成真赋值与成假赋值。*重言式（永真式）、矛盾式（永假式）、可满足式的概念及判定（真值表法）。3.等值演算：*等值式：常见的基本等值式（如双重否定律、幂等律、交换律、结合律、分配律、德摩根律、吸收律、零律、同一律、排中律、矛盾律、蕴含等值式、等价等值式、假言易位、等价否定等值式、归谬论等）必须熟记并能灵活运用。*等值演算：利用基本等值式对命题公式进行化简和证明两个公式等值。这是一项基本技能，多做练习是关键。4.范式：*简单合取式与简单析取式。*析取范式与合取范式：概念及求法（利用等值演算消去联结词→、↔，将否定词内移，利用分配律等）。*极小项与极大项：理解其编码规则和性质。*主析取范式与主合取范式：概念、求法（真值表法、等值演算法）及其用途（判断公式类型、判断公式等值、求成真/成假赋值等）。主范式是命题逻辑部分的核心考点之一。5.推理理论：*推理的形式结构：即“A₁∧A₂∧...∧Aₖ→B”，判断其是否为重言式。*推理规则：掌握P规则（前提引入）、T规则（结论引入，即由前面公式推出后面公式）、以及常见的蕴含式推理规则（如假言推理、拒取式、析取三段论、假言三段论、等价三段论、构造性二难等）和等值式推理规则（如置换规则）。*构造证明法：熟练运用直接证明法、附加前提证明法（CP规则，用于结论为蕴含式）和归谬法（反证法）构造推理证明。这是命题逻辑部分的难点和常考题型。（二）谓词逻辑（一阶逻辑）复习建议：命题逻辑的扩展，引入了量词，表达能力更强。重点在于理解个体词、谓词、量词的概念，以及谓词公式的解释和等值演算，难点是带量词的推理。1.基本概念：*个体词、个体域、全总个体域。*谓词：一元谓词（表示性质）、多元谓词（表示关系）。*量词：全称量词（∀）、存在量词（∃）。*指导变元、辖域、约束出现、自由出现。*闭式：无自由出现变元的谓词公式。2.谓词公式与解释：*谓词公式的定义。*谓词公式的解释（非空个体域、个体常项、函数、谓词的指定）。*谓词公式的类型：永真式、矛盾式、可满足式。3.等值演算：*量词否定等值式。*量词辖域收缩与扩张等值式。*量词分配等值式（∀对∧，∃对∨）。*消去量词（在有限个体域上）。4.前束范式：*定义：所有量词均非否定地出现在公式的最前面，且其辖域延伸到公式的末尾。*求前束范式的方法（利用等值式、换名规则、代替规则）。5.推理理论：*量词消去与引入规则：全称指定规则（US/UI）、全称推广规则（UG）、存在指定规则（ES/EI，注意此规则的使用条件，避免“重复指定”错误）、存在推广规则（EG）。*运用上述规则进行谓词逻辑的推理证明。这部分综合性强，需要多做例题体会。二、集合论集合论是现代数学的基础，也是离散数学的重要组成部分。其概念和方法渗透到后续各个章节。（一）集合的基本概念与运算复习建议：集合的基本概念较为直观，但要注意严格性。集合的运算及其性质是基础，务必熟练。1.集合的概念：*集合的定义、元素与集合的关系（属于∈、不属于∉）。*集合的表示方法：列举法、描述法。*集合的特性：确定性、互异性、无序性。*常用数集：自然数集N、整数集Z、有理数集Q、实数集R。*子集、真子集、集合相等、空集∅、全集U、幂集P(A)（注意幂集的元素个数为2^|A|）。2.集合的基本运算：*并（∪）、交（∩）、相对补（-或\）、绝对补（~或A'）、对称差（⊕）。*集合运算的基本性质：交换律、结合律、分配律、吸收律、德摩根律、幂等律、同一律、零律、互补律等。能利用这些性质进行集合等式的证明或化简。3.集合的计数：*文氏图（VennDiagram）的应用。*容斥原理：两个集合的容斥公式、三个集合的容斥公式，并能用于解决实际计数问题。（二）二元关系复习建议：关系是集合论的核心内容，概念多，抽象度高，是考试的重点和难点。要理解关系的本质是集合，掌握关系的表示方法、性质及运算。1.有序对与笛卡儿积：*有序对的定义与性质。*笛卡儿积A×B的定义（所有有序对的集合）及其性质（一般不满足交换律和结合律）。2.二元关系的定义与表示：*定义：从A到B的二元关系是A×B的子集；A上的二元关系是A×A的子集。*表示方法：集合表达式、关系矩阵（布尔矩阵）、关系图（有向图）。3.关系的运算：*定义域dom(R)、值域ran(R)、域fld(R)。*关系的逆运算R⁻¹。*关系的合成运算R∘S（注意顺序）。*关系的幂运算Rⁿ。4.关系的性质：*自反性、反自反性、对称性、反对称性、传递性。要能准确理解这些性质的定义，能根据关系的集合表达式、关系矩阵或关系图判断关系是否具有这些性质，并能构造具有指定性质的关系。*关系性质的判定定理。5.关系的闭包：*自反闭包r(R)、对称闭包s(R)、传递闭包t(R)的定义和构造方法（公式法、关系图法、Warshall算法求传递闭包）。6.等价关系与划分：*等价关系：同时具有自反、对称、传递性的关系。*等价类：定义及性质。*商集：A/R={[a]ₐ|a∈A}。*集合的划分：划分的定义、划分与等价关系的一一对应（由等价关系可确定划分，由划分可确定等价关系）。7.偏序关系与偏序集：*偏序关系：同时具有自反、反对称、传递性的关系（通常记为≤）。*偏序集：集合A与A上的偏序关系≤构成的有序对(A,≤)。*哈斯图（HasseDiagram）：是表示偏序关系的有效工具，能清晰展示元素间的“直接”序关系。*偏序集中的特殊元素：极大元、极小元、最大元、最小元、上界、下界、上确界（最小上界）、下确界（最大下界）。这些概念需要结合具体例子理解，注意它们之间的区别与联系。（三）函数复习建议：函数是一种特殊的二元关系。要理解函数的定义、性质以及特殊类型的函数。1.函数的概念：*函数的定义（从A到B的函数f:A→B，强调“单值性”）。*函数的定义域dom(f)=A，陪域codom(f)=B，值域ran(f)⊆B。*函数相等。*从A到B的函数的个数：若|A|=m,|B|=n，则有n^m个。2.函数的性质：*单射（injective，一对一）：若a₁≠a₂则f(a₁)≠f(a₂)。*满射（surjective，到上）：ran(f)=B。*双射（bijective，一一对应）：既是单射又是满射。3.函数的复合：*函数f与g的复合（f∘g），注意条件和顺序。*复合函数的性质（若f,g是单射/满射/双射，则f∘g也具有相应性质）。4.逆函数：*只有双射函数才有逆函数。*逆函数的定义和性质。三、代数系统代数系统主要研究具有运算的集合及其性质，是抽象代数的基础。这部分内容抽象程度高，需要理解代数结构的共性。（一）代数系统的基本概念复习建议：重点理解运算的定义、运算的性质以及代数系统的同构概念。1.运算：*n元运算的定义。*二元运算的封闭性。*二元运算的性质：交换律、结合律、分配律（对另一种运算）、吸收律（两种运算之间）、幂等律。*二元运算的特异元素：单位元（幺元）、零元、逆元（针对某个元素，相对于单位元而言）。能判断给定运算是否有这些元素，若有能求出。2.代数系统：*代数系统的定义（非空集合A和A上的若干运算组成）。*子代数系统（子代数）。*代数系统的同态与同构：同态映射、同态像、单同态、满同态、同构。理解同构是一种保持运算性质的双射，两个同构的代数系统具有完全相同的代数性质。（二）几类典型的代数系统复习建议：掌握半群、独异点、群、环、域、格、布尔代数的定义和基本性质，重点是群和格。1.半群与独异点：*半群：具有封闭、可结合二元运算的代数系统。*独异点：具有单位元的半群。2.群：*群的定义：具有单位元，每个元素都有逆元的独异点（即：封闭、可结合、有幺元、每个元素有逆元）。也可定义为：二元运算封闭、可结合、存在幺元、每个元素存在逆元。*群的性质：幺元唯一、逆元唯一、消去律成立（若a∘b=a∘c则b=c；若b∘a=c∘a则b=c）。*子群：子群的定义和判定方法。*阿贝尔群（交换群）：运算满足交换律的群。*循环群：在群中存在元素a（生成元），使得群中所有元素都能表示为a的幂（有限次运算）。循环群一定是阿贝尔群。3.环与域（简介）：*环：定义了两种二元运算（通常称“加法”和“乘法”）的代数系统，关于加法构成阿贝尔群，关于乘法构成半群，乘法对加法满足分配律。*整环：无零因子（满足消去律）的交换环。*域：乘法（除去零元）构成阿贝尔群的整环。实数域、有理数域是常见的域。4.格与布尔代数：*格的定义：偏序格（任意两个元素都有最小上界和最大下界的偏序集）和代数格（具有两个满足交换律、结合律、吸收律的二元运算的代数系统），以及两者的等价性。*格的性质：运算的交换律、结合律、吸收律、幂等律，保序性等。*分配格：满足分配律的格。*有补格：存在全上界1和全下界0，且每个元素都有补元的格。*布尔代数：有补分配格。布尔代数的运算性质（布尔代数的公理系统），德摩根律在布尔代数中成立。四、图论图论以图为研究对象，是离散数学中应用性极强的部分。概念繁多，需要结合图形理解。（一）图的基本概念复习建议：图的基本概念是后续内容的基础，务必清晰。图的矩阵表示也是重点。1.图的定义与表示：*无向图与有向图的定义：顶点集、边集（无向边、有向边）、顶点数n、边数m。*相关术语：端点、关联、相邻、环、平行边、简单图、多重图、完全图（无向完全图Kₙ、有向完全图）、子图、生成子图、导出子图。*顶点的度数：无向图顶点的度d(v)（入度=出度），有向图顶点的入度d⁺(