lisan(2)-2-qm《离散数学(2)-2》复习材料

离散数学期末复习要点与重点大纲（复习以课本和笔记为主。

文中标红为需重点掌握的，祝大家都能取得好成绩！）第1章命题逻辑复习要点1．理解命题概念，会判别语句是不是命题．理解五个基本联结词：否定P、析取、合取、条件、和双条件及其真值表，理解其他联结词的定义及基本等价式，会将简单命题符号化．具有确定真假意义的陈述句称为命题．命题必须具备：其一，语句是陈述句；其二，语句有唯一确定的真假意义.2．理解公式的概念(公式、赋值、成真指派和成假指派)和公式真值表的构造方法．能熟练地作公式真值表．理解永真式和永假式概念，掌握其判别方法．判定命题公式类型的方法：其一是真值表法，其二是等价演算法.3．了解公式等价概念，掌握公式的重要等价式和判断两个公式是否等价的有效方法：等价演算法、列真值表法和主范式方法．4．理解析取范式和合取范式、极大项和极小项、主析取范式和主合取范式的概念，熟练掌握它们的求法（真值表法和等价推导法）．命题公式的范式不惟一，但主范式是惟一的．命题公式A有n个命题变元，A的主析取范式有k个小项，有m个大项，则n=+mk2于是有(1) A是永真式2n(0)； (2) A是永假式m＝2n(0)；5．了解C是前提集合{A12,…}的有效结论或由A1, A2, …, 逻辑地推出C的概念．要理解并掌握推理理论的规则、重言蕴含式和等价式，掌握命题公式的证明方法：真值表法、直接证法、间接证法．重点：命题与联结词，真值表，主析取(合取)范式，命题演算的推理理论.第2章 谓词逻辑复习要点1．理解谓词、量词、个体词、个体域，会将简单命题符号化． 原子命题分成个体词和谓词，个体词可以是具体事物或抽象的概念，分个体常项和个体变项．谓词用来刻划个体词的性质或之间的关系．量词分全称量词，存在量词.命题符号化注意：使用全称量词，特性谓词后用；使用存在量词，特性谓词后用．2．了解原子公式、谓词公式、变元(约束变元和自由变元)与辖域等概念．掌握在有限个体域下消去公式的量词和求公式在给定解释下真值的方法．由原子公式、联结词和量词构成谓词公式．谓词公式具有真值时，才是命题．在谓词公式或中，x 是指导变元，A 是量词的辖域．会区分约束变元和自由变元．在非空集合D (个体域)上谓词公式A 的一个解释或赋值有3个条件．在任何解释下，谓词公式A 取真值1，A 为逻辑有效式(永真式)；公式A 取真值0，A 为永假式；至少有一个解释使公式A 取真值1，A 称为可满足式．在有限个体域下，消除量词的规则为：设D ＝{a 1, a 2, …, }，则)(...)()()(21n a A a A a A x xA ∧∧∧⇔∀)(...)()()(21n a A a A a A x xA ∨∨∨⇔∃会求谓词公式的真值，量词的辖域，自由变元、约束变元，以及换名规则、代入规则等．掌握谓词演算的等价式和重言蕴含式．并进行谓词公式的等价演算．3．理解前束范式的概念，掌握求公式的前束范式的方法.若一个谓词公式F 等价地转化成 B x Q x Q x Q k k ...2211，那么B x Q x Q x Q k k ...2211就是F 的前束范式，其中Q 1，Q 2，…，只能是或，而x 1, x 2, …, 是个体变元，B 是不含量词的谓词公式．前束范式仍然是谓词公式．重点：翻译；前束范式．第3章集合与关系复习要点1．理解集合、元素、集合的包含、子集、相等，以及全集、空集和幂集等概念，熟练掌握集合的表示方法．集合的表示方法：列举法和描述法.注意：集合的表示中元素不能重复出现，集合中的元素无顺序之分．掌握集合包含(子集)、真子集、集合相等等概念．注意：元素与集合，集合与子集，子集与幂集，与(),空集与所有集合等的关系.空集，是惟一的，它是任何集合的子集．集合A的幂集P(A)＝}x ， A的所有子集构成的集合．若{AxA＝n，则P(A)=2n．2．熟练掌握集合A和B的并A B，交A B，补集A(A 补集总相对于一个全集).差集A－B，对称差，A B＝(A－B)(B－A)，或A B＝(A B)－（A B）等运算．掌握集合运算律(运算的性质).3．掌握用集合运算基本规律证明集合恒等式的方法．集合的运算问题：其一是进行集合运算；其二是运算式的化简；其三是恒等式证明．证明方法有二：(1)要证明A＝B，只需证明A B，又A B；(2)通过运算律进行等式推导．4．了解有序对和笛卡尔积的概念，掌握笛卡尔积的运算．有序对就是有顺序二元组，如<x, y>，x, y的位置是确定的，不能随意放置．注意：有序对<a，b><b, a>，以a, b为元素的集合{a, b}={b, a}；有序对(a, a)有意义，而集合{a, a}是单元素集合，应记作{a}．集合A，B的笛卡尔积A×B是一个集合，规定A×B＝{<>x B}，是有序对的集合.笛卡尔积也可以多个集合合成，A1×A2×…×．5．理解关系的概念：二元关系、空关系、全关系、恒等关系.掌握关系的集合表示、关系矩阵和关系图，掌握关系的集合运算及复合关系、逆关系的性质与求法．二元关系是一个有序对集合，},{B y A x y x R ∈∧∈><=，记作． 设A 、B 是两个集合，且＝m ，＝n ，则从A 到B 可产生的不同的二元关系个数为nm 2。

离散数学复习要点离散数学是数学的一个分支领域，主要研究离散的结构和离散情形下的数学对象及其相关性质。

它与连续数学不同，离散数学的对象是离散的，如集合、图、布尔代数等。

在计算机科学、信息科学、通信工程等领域中，离散数学的理论和方法被广泛应用。

以下是离散数学的一些重要的复习要点：1.集合论：集合是离散数学的基础，集合的基本运算如交、并、差等，以及集合的基本性质如并集和交集的结合律、分配律等，都是需要复习的内容。

此外，还需要了解集合的基数和幂集等概念。

2.命题逻辑：命题是一个可以判断真假的陈述句，命题逻辑是研究命题及其逻辑关系的数学体系。

需要复习的内容包括命题的逻辑运算，如非、与、或、异或等，以及逻辑等价、逻辑推理等。

3.谓词逻辑：谓词逻辑是对自然语言中的谓词进行形式化表示和推理的系统。

复习重点包括一阶谓词逻辑的基本概念，如谓词、量词、域、项等，以及谓词的合取、析取、全称量词和存在量词等逻辑联结词的语义。

4.图论：图论是研究图及其性质的数学分支。

需要复习的内容包括图的基本概念，如顶点、边、路径、圈等，以及图的表示方法、图的遍历算法、连通图、树等。

5. 网络流模型：网络流模型是研究流动网络的数学方法，主要包括最大流、最小割等问题。

需要复习的内容包括网络的基本概念，如容量、割、流等，以及Ford-Fulkerson算法等解决网络流问题的方法。

6.布尔代数：布尔代数是一种关于逻辑运算的代数系统，常用于电路设计和逻辑推理。

需要复习的内容包括布尔代数的基本运算，如与、或、非等，以及布尔函数的最小项与最大项表示、卡诺图等。

7.组合数学：组合数学是研究离散中的计数问题的数学分支。

需要复习的内容包括排列、组合、多元排列组合等的计数方法，如乘法原理、加法原理、排列组合的顺序问题等。

8.代数系统：代数系统是研究代数结构及其性质的数学分支，包括群、环、域等。

需要复习的内容包括群的基本概念和性质，如封闭性、结合律、单位元、逆元等。

离散数学复习资料第1章命题逻辑本章重点：命题与联结词，公式与解释，真值表，公式的类型及判定, (主)析取(合取)范式，命题逻辑的推理理论.一、重点内容1. 命题命题表述为具有确定真假意义的陈述句。

命题必须具备二个条件：其一，语句是陈述句；其二，语句有唯一确定的真假意义.2. 六个联结词及真值表“⌝”否定联结词，P是命题，⌝P是P的否命题，是由联结词⌝和命题P组成的复合命题.P取真值1，⌝P取真值0，P取真值0，⌝P 取真值1. 它是一元联结词.“∧”合取联结词，P∧Q是命题P，Q的合取式，是“∧”和P，Q组成的复合命题. “∧”在语句中相当于“不但…而且…”，“既…又…”. P∧Q取值1，当且仅当P，Q均取1；P∧Q取值为0，只有P，Q之一取0.“∨”析取联结词，“⎺∨”不可兼析取(异或)联结词， P∨Q 是命题P，Q的析取式，是“∨”和P，Q组成的复合命题. P⎺∨Q是联结词“⎺∨”和P，Q组成的复合命题. 联结词“∨”或“⎺∨”在一个语句中都表示“或”的含义，前者表示相容或，后者表示排斥或不相容的或. 即“P⎺∨Q”↔“(⌝P∧Q)∨(P∧⌝Q)”. P∨Q取值1，只要P，Q之一取值1，P∨Q取值0，只有P，Q都取值0.“→”蕴含联结词， P→Q是“→”和P，Q组成的复合命题，只有P取值为1，Q取值为0时，P→Q取值为0；其余各种情况，均有P→Q的真值为1，亦即1→0的真值为0，0→1，1→1，0→0的真值均为1. 在语句中，“如果P则Q”或“只有Q，才P，”表示为“P→Q”.“↔”等价联结词，P↔Q是P，Q的等价式，是“↔”和P，Q组成的复合命题. “↔”在语句中相当于“…当且仅当…”，P↔Q 取值1当且仅当P，Q真值相同.3. 命题公式、赋值与解释，命题公式的分类与判别命题公式与赋值，命题P含有n个命题变项P1，P2,…,P n，给P1，P2,…,P n各指定一个真值，称为对P的一个赋值(真值指派). 若指定的一组值使P的真值为1，则这组值为P的真指派；若使P的真值为0，则称这组值称为P的假指派.命题公式分类，在各种赋值下均为真的命题公式A，称为重言式(永真式)；在各种赋值下均为假的命题公式A，称为矛盾式(永假式)；命题A不是矛盾式，称为可满足式；判定命题公式类型的方法：其一是真值表法，任给公式，列出该公式的真值表，若真值表的最后一列全为1，则该公式为永真式；若真值表的最后一列全为0，则该公式是永假式；若真值表的最后一列既非全1，又非全0，则该公式是可满足式.其二是推导演算法. 利用基本等值式(教材P.16的十六个等值式或演算律)，对给定公式进行等值推导，若该公式的真值为1，则该公式是永真式；若该公式的真。

离散数学复习提纲离散数学是一门关于离散对象的数学分支，它主要研究离散结构及其性质，广泛应用于计算机科学、信息技术、密码学等领域。

下面是一个离散数学的复习提纲，包括离散数学的基本概念、离散结构、图论、关系、逻辑以及集合论等内容。

一、离散数学的基本概念1.数学基础：集合、函数、关系、证明方法（数学归纳法、反证法、递归法等）；2.命题逻辑：命题、命题连接词、真值表、逻辑运算、逻辑等价、推理规则等；3.谓词逻辑：谓词、量词、公式、合取范式和析取范式、蕴含、等价、量词的否定规则等；4.证明方法：直接证明、间接证明、归谬证明、证明策略等。

二、离散结构1.图论：图的基本概念、图的表示方法、连通性、路径和回路、图的着色、最小生成树等；2.代数结构：群、环、域的定义、性质及基本例子；3.组合数学：组合基本原理、二项式系数、排列组合、生成函数、递归关系、容斥原理等；4.有限状态自动机：确定性有限状态自动机、非确定性有限状态自动机、正则表达式等。

1.图的基本概念：顶点、边、路径、回路、度等；2.图的表示：邻接矩阵、邻接表、关联矩阵等；3.图的遍历：深度优先、广度优先；4. 最短路径问题：Dijkstra算法、Floyd-Warshall算法；5. 最小生成树问题：Prim算法、Kruskal算法；6.匹配问题：最大匹配、二分图匹配等。

四、关系1.关系的基本概念：关系矩阵、关系的性质（反自反性、对称性、传递性等）；2.等价关系：等价关系的性质、等价类等；3.偏序关系：偏序关系的性质、偏序集合、哈斯图等；4.传递闭包：传递闭包的定义、传递闭包的计算方法等。

五、逻辑1.命题逻辑：命题的定义、逻辑运算、真值表、逻辑等价、推理规则等；2.谓词逻辑：量词的定义、公式的定义、量词的否定规则、等价变换等；3.命题逻辑与谓词逻辑的转换；4.形式化推理：前向链式推理、后向链式推理、消解法等。

1.集合的基本概念：子集、并集、交集、差集、补集等；2.集合运算：集合的并、交、差、补等运算的性质；3.集合的关系：包含关系、相等关系、等价关系等；4.集合的表示方法：列举法、描述法、元祖法等；5.集合的基数：有限集合的基数、无穷集合的基数、基数的性质。

离散数学复习要点第一章命题逻辑一、典型考查点1、命题的判断方法：陈述句真值唯一，特殊：反问句也是命题。

其它疑问句、祈使句、感叹句、悖论等皆不是。

详见教材P12、联结词运算定律┐∧∨→记住特殊的：1∧1⇔1，0∨0⇔0，1→0⇔0，11⇔1，00⇔1详见P53、命题符号化步骤：A划分原子命题，找准联结词。

特殊自然语言：不但而且，虽然但是用∧，只有P才Q，应为Q→P；除非P否则Q，应为┐P→Q。

B设出原子命题写出符号化公式。

详见P54、公式的分类判定（重言式、矛盾式、可满足式）方法：其一根据所有真值赋值情况，其二根据等价演算来判断。

详见P95、真值表的构造步骤：①命题变元按字典序排列，共有2n个真值赋值。

②对每个指派，以二进制数从小到大或从大到小顺序列出。

③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。

详见P8。

6、基本概念：置换规则，P规则，T规则，详见P24；合取范式，析取范式，详见P15；小项详见P16；大项详见P18，最小联结词组详见P157、等价式详见P22表1.6.2 证明方法：①真值表完全相同②用等价演算③利用A⇔B的充要条件是A⇒B且B⇒A。

主要等价式：(1)双否定：⎤⎤A⇔A。

(2)交换律：A∧B⇔B∧A，A∨B⇔B∨A，A↔B⇔B↔A。

3)结合律：(A∧B)∧C⇔A∧(B∧C)，(A∨B)∨C⇔A∨(B∨C)，(A↔B)↔C⇔A↔(B↔C)。

(4) 分配律：A∧(B∨C)⇔(A∧B)∨(A∧C)，A∨(B∧C)⇔(A∨B)∧(A∨C)。

(5) 德·摩根律：⎤(A∧B)⎤⇔A∨⎤B，⎤(A∨B)⎤⇔A∧⎤B。

(6) 等幂律：A∧A⇔A，A∨A⇔A。

(7) 同一律：A∧T⇔A，A∨F⇔A。

(8) 零律：A∧F⇔F，A∨T⇔T。

(9) 吸收律：A∧(A∨B)⇔A，A ∨(A∧B)⇔A。

(10) 互补律：A∧⎤A⇔F，(矛盾律)，A∨⎤A⇔T。

高三离散数学知识点汇总离散数学是计算机科学、信息技术以及其他相关领域中的重要基础学科，是高中阶段的数学课程之一。

下面将对高三离散数学的主要知识点进行汇总，以帮助学生更好地复习和掌握这门学科。

一、命题逻辑命题逻辑是离散数学的基础，它研究命题的逻辑关系及其合成。

以下是命题逻辑中常见的知识点：1. 命题与命题的合取（与）、析取（或）、非（非）运算；2. 命题的真值表与真值；3. 命题的等价、蕴含、互斥等逻辑关系；4. 命题的可满足性与有效性。

二、集合与关系集合论是离散数学中的另一重要组成部分，它研究集合及其间的关系。

以下是集合与关系中的主要知识点：1. 集合的表示方式与基本操作，如并集、交集、差集和补集；2. 笛卡尔积与关系的定义；3. 关系的性质，如自反性、对称性、传递性等；4. 等价关系与偏序关系的概念与判断；5. 关系的闭包与传递闭包。

三、图论图论是离散数学中的重要分支，它研究图及其相关的性质与算法。

以下是图论中的常见知识点：1. 图的基本概念与表示方式，如顶点、边、度、路径等；2. 树与森林的定义与性质，包括最小生成树与最短路径树等；3. 图的连通性与强连通性的判定；4. 图的着色与平面图的概念；5. 图的网络流与匹配等问题。

四、代数系统代数系统是离散数学的重要组成部分，它研究运算规则及其相应的结构。

以下是代数系统中的主要知识点：1. 半群、幺半群、群的概念与性质；2. 环、域的定义与性质；3. 线性方程组与矩阵的基本运算；4. 同余与剩余类的概念与应用。

五、概率与统计概率与统计是离散数学的重要应用领域，它研究随机事件及其规律性。

以下是概率与统计中的常见知识点：1. 随机事件的基本概念与性质；2. 概率的计算方法，包括古典概型、几何概型、条件概率等；3. 随机变量与概率分布的概念与应用；4. 抽样与统计推断，包括参数估计与假设检验等。

综上所述，高三离散数学的知识点涵盖了命题逻辑、集合与关系、图论、代数系统以及概率与统计等方面。

《离散数学》期末复习大纲（完整版）（含例题和考试说明）一、命题逻辑[复习知识点]1、命题与联结词（否定￢、析取∨、合取∧、蕴涵→、等价↔），复合命题2、命题公式与赋值（成真、成假），真值表，公式类型（重言、矛盾、可满足），公式的基本等值式3、范式：析取范式、合取范式，极大（小）项，主析取范式、主合取范式4、公式类型的判别方法（真值表法、等值演算法、主析取/合取范式法）5、命题逻辑的推理理论本章重点内容：命题与联结词、公式与解释、（主）析取范式与（主）合取范式、公式类型的判定、命题逻辑的推理[复习要求]1、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。

2、理解公式与赋值的概念；掌握求给定公式真值表的方法，用基本等值式化简其它公式，公式在解释下的真值。

3、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等值式或真值表将公式化为主析取（合取）范式的方法。

4、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价方法。

5、掌握命题逻辑的推理理论。

[疑难解析]1、公式类型的判定判定公式的类型，包括判定公式是重言的、矛盾的或是可满足的。

具体方法有两种，一是真值表法，二是等值演算法。

2、范式求范式，包括求析取范式、合取范式、主析取范式和主合取范式。

关键有两点：一是准确理解掌握定义；另一是巧妙使用基本等值式中的分配律、同一律和互补律（排中律、矛盾律），结果的前一步适当使用幂等律，使相同的短语（或子句）只保留一个。

3、逻辑推理掌握逻辑推理时，要理解并掌握12个（除第10，11）推理规则和3种证明法（直接证明法、附加前提证明法和归谬法）。

例1.试求下列公式的主析取范式：（1）))()((P Q Q P P ⌝∨⌝⌝∧→→；（2）)))((R Q Q P P →⌝∨→⌝∨（))()(())()((:)1P Q Q P Q P P P Q Q P P ∧∧∨∧∧⌝∨⌝=∧∧∨⌝∨⌝=原式解 Q P P P Q P P Q P ∨⌝=∨⌝∧∨⌝=∧∨⌝=)()()())(())((Q P P Q Q P ∧∨⌝∨∨⌝∧⌝=)()()(Q P Q P Q P ∧∨∧⌝∨⌝∧⌝=)))((()))(((:)2R Q Q P P R Q Q P P ∨∨∨∨=→⌝∨→⌝∨解)()()()(R Q P R Q P R Q P R Q P R Q P ∧⌝∧∨∧∧⌝∨⌝∧∧⌝∨∧⌝∧⌝=∨∨=)()()(R Q P R Q P R Q P ∧∧∨⌝∧∧∨⌝∧⌝∧∨）2．用真值表判断下列公式是恒真？恒假？可满足？（1）（P ∧⌝P ）↔Q（2）⌝（P →Q ）∧Q（3）（（P →Q ）∧（Q →R ））→（P →R ）解：（1） 真值表因此公式（1）为可满足。

百度文库离散数学复习整理离散数学复习整理离散数学复习整理函数***重点掌握：单射、满射、双射函数的概念一、函数的概念（和数学里面函数的概念差不多）A为函数f的定义域，记为domf=A；f(A)为函数f的值域，记为ranf。

|f|=|A|f(x)表示一个变值，f代表一个集合，因此f≠f(x)。

⨯|A||B||A|从A到B的不同的关系有2个；但从A到B的不同的函数却仅有|B|个。

(个数差别) 每一个函数的基数都为|A|个(|f|=|A|)，但关系的基数却为从零一直到|A|×|B|。

二、特殊函数单射：对任意x,x∈A，如果x≠x，有f(x)≠f(x)，则称f为从A到B的单射（不同的x对应121212不同的y)；满射：如果ranf＝B，则称f为从A到B的满射；（B的定义域都能通过函数f(x)求到）双射：若f是满射且是单射，则称f为从A到B的双射。

若A＝B，则称f为A上的函数；当A上的函数f是双射时，称f为一个变换。

定理：8.2.1设A，B是有限集合，且|A|=|B|，f是A到B的函数，则f是单射当且仅当f是满射。

典型(自然)映射：设R是集合A上的一个等价关系，g：A→A/R称为A对商集A/R的典型(自然) 映射，其定义为g(a)＝[a]，a∈A.R恒等函数：如果A=B，且对任意x∈A，都有f(x)=x，则称f为A上的恒等函数，记为I。

A常值函数：如果∃b∈B，且对任意x∈A，都有f(x)=b，则称f为常值函数。

上取整函数：对有理数x，f(x)为大于等于x的最小的整数，则称f(x)为上取整函数(强取整函数)，记为f(x)= ；下取整函数：对有理数x，f(x)为小于等于x的最大的整数，则称f(x)为下取整函数(弱取整函数)，记为f(x)= ；三、函数的复合运算不满足交换律，但满足结合律1.函数f和g可以复合⇔ranf⊆domg；2.dom(fog)=domf，ran(fog)⊆rang；3.对任意x∈A，有fog(x)=g(f(x))。

离散数学知识点总结离散数学是数学的一个分支，主要研究离散的数学结构和离散的数学对象。

它包括了许多重要的概念和技术，是计算机科学、通信工程、数学和逻辑学等领域的基础。

本文将对离散数学的一些核心知识点进行总结，包括命题逻辑、一阶逻辑、图论、集合论和组合数学等内容。

1. 命题逻辑命题逻辑是离散数学的一个重要分支，研究命题之间的逻辑关系。

命题是一个陈述语句，要么为真，要么为假，而且不能同时为真和为假。

命题逻辑包括逻辑运算和逻辑推理等内容，是离散数学的基础之一。

1.1 逻辑运算逻辑运算包括与（∧）、或（∨）、非（¬）、蕴含（→）和双条件（↔）等运算。

与、或和非是三种基本的逻辑运算，蕴含和双条件则是基于这三种基本运算得到的复合运算。

1.2 逻辑等值式逻辑等值式是指在命题逻辑中具有相同真值的两个复合命题。

常见的逻辑等值式包括德摩根定律、双重否定定律、分配率等。

1.3 形式化证明形式化证明是命题逻辑的一个重要内容，研究如何利用逻辑规则和等值式来推导出给定命题的真值。

形式化证明包括直接证明、间接证明和反证法等方法，是离散数学中的常见技巧。

2. 一阶逻辑一阶逻辑是命题逻辑的延伸，研究命题中的量词和谓词等概念。

一阶逻辑包括量词、谓词逻辑和形式化证明等内容，是离散数学中的重要部分。

2.1 量词量词包括全称量词（∀）和存在量词（∃），用来对命题中的变量进行量化。

全称量词表示对所有元素都成立的命题，而存在量词表示至少存在一个元素使命题成立。

2.2 谓词逻辑谓词逻辑是一阶逻辑的核心内容，研究带有量词的语句和谓词的逻辑关系。

谓词是含有变量的函数，它可以表示一类对象的性质或关系。

2.3 形式化证明形式化证明在一阶逻辑中同样起着重要作用，通过逻辑规则和等值式来推导出给定命题的真值。

一阶逻辑的形式化证明和命题逻辑类似，但更复杂和抽象。

3. 图论图论是离散数学中的一个重要分支，研究图和图的性质。

图是由节点和边组成的数学对象，图论包括图的表示、图的遍历、最短路径、最小生成树等内容，是离散数学中的一大亮点。

试卷类型一、选择题（10题，每题2分，共计20分）二、填空题（10空，每空2分，共计20分）三、选择题（8题，每空1分，共计8分）四、名词解释（3个，每个4分，共计12分）五、构造推理证明题（1题，计10分）六、计算题（共计30分）求解主析取范式或合取范式、等价关系或偏序关系哈斯图、最小生成树、求解前束范式离散数学的定义第1章数学语言与证明方法主要内容：●集合定义，集合的两种描述方法，空集合的定义与定理及推论，子集、真子集、全集，相等集合，包括0的自然数、有理数、整数、实数集合，集合的元素个数●集合的交、并、补、差、对称差、幂运算（集合的个数）定义，经过括号形成的更为复杂的集合运算，简单的可以通过文氏图来表示。

第2章命题逻辑主要内容：●命题及其真值。

感叹句、祈使句、疑问句都不是命题，陈述句中的悖论以及判断结果不惟一确定的也不是命题。

●简单命题与复合命题概念，5种联结词的具体涵义、真值表与符号表示，汉语的复合句的那些联结词与它们对应，特别是相容或和排斥或的符号化表示。

●联结词优先级：( ),⌝, ∧, ∨, →, ↔；同级按从左到右的顺序进行●命题常项、命题变项、合式公式定义，公式的赋值、真值表●命题公式的分类有重言式（永真式）、矛盾式（永假式）、可满足式●等值式的定义，真值表法和等值演算两种判断方法，置换规则●文字、简单析取式、简单合取式、析取范式、合取范式的定义●定理：(1) 一个简单析取式是重言式当且仅当它同时含某个命题变项和它的否定；(2) 一个简单合取式是矛盾式当且仅当它同时含某个命题变项和它的否定●定理：(1) 一个析取范式是矛盾式当且仅当它的每一个简单合取式都是矛盾式；(2)一个合取范式是重言式当且仅当它的每一个简单析取式都是重言式●定理：任何命题公式都存在着与之等值的析取范式与合取范式●求公式的范式的3个步骤●极小项、极大项的定义，对于每一个最小项只有一种指派使其取1，对于每一个最大项只有一种指派使其取0●定理：设m i与M i是由同一组命题变项形成的极小项和极大项, 则⌝m i ⇔ M i , ⌝M i⇔ m i●主析取范式、主合取范式的定义，求解公式的析取范式、合取范式、主析取范式、主合取范式●定理：任何命题公式都存在着与之等值的主析取范式和主合取范式, 并且是惟一的●求主析取范式的步骤，求主合取范式的步骤，快速求法、主析取范式的用途●命题逻辑推理的推理证明第3章一阶逻辑主要内容：●个体词（个体常项、个体变项）、个体域、全总个体域的定义●谓词（全称量词和存在量词）、n元谓词P(x1, x2,…, xn)的定义，命题的符号化●量词（全称量词和存在量词）、谓词公式、量词的辖域、谓词公式的真值判断、量词的消去等值变换●等值式的定义，5类基本等值式（量词的消去，量词辖域范围的收缩和扩展）●置换规则、换名规则的定义●前束范式的定义，利用量词的辖域的扩张，完成前束范式的求解●定理3.3(前束范式存在定理) 一阶逻辑中的任何公式都存在与之等值的前束范式第4章关系主要内容：●有序对、笛卡儿积、二元关系、从A到B的关系、A上的关系的定义●A上重要关系●A到B上关系的计数，A上关系的计数●关系的三种表示：关系的集合表达式、关系矩阵、关系图，后两种的使用限制●定义域、值域、域的定义●关系的运算：逆、合成的定义和表示方法以及简单计算●定理 4.1 设F是任意的关系, 则 (1) (F-1)-1=F (2) dom F-1=ran F,ran F-1=dom F●定理4.2 设F, G, H是任意的关系, 则(1) (F∘G)∘H=F∘(G∘H) (2) (F∘G)-1=G-1∘F-1●定理4.3 设R 为A上的关系, 则R∘I A= I A∘R = R●定义4.13 设R为A上的关系, n为自然数, 则 R 的 n次幂是 (1) R0 = {<x,x>| x∈A } = I A (2) R n+1 = R n∘R●定理4.4 设 A 为 n 元集, R是A上的关系, 则存在自然数 s 和 t, 使得 R s=R t.●定理4.5 设 R 是 A 上的关系, m, n∈N, 则 (1) R m∘R n = R m+n (2) (R m)n= R mn●自反性与反自反性, 对称性与反对称性，传递性的定义以及矩阵表示的特征。

离散数学知识点整理离散数学是现代数学的一个重要分支，它在计算机科学、信息技术、通信工程等领域有着广泛的应用。

以下是对离散数学中一些重要知识点的整理。

一、集合论集合是离散数学中最基本的概念之一。

集合是由一些确定的、互不相同的对象所组成的整体。

集合的表示方法有列举法和描述法。

列举法就是将集合中的元素一一列举出来，用花括号括起来；描述法是通过描述元素所具有的性质来表示集合。

集合之间的关系包括子集、真子集、相等。

如果集合 A 的所有元素都属于集合 B，那么 A 是 B 的子集；如果 A 是 B 的子集，且 B 中存在元素不属于 A，那么 A 是 B 的真子集；如果两个集合的元素完全相同，那么它们相等。

集合的运算有并集、交集、差集和补集。

并集是将两个集合中的所有元素合并在一起组成的新集合；交集是两个集合中共同的元素组成的新集合；差集是从一个集合中去掉另一个集合的元素所剩下的元素组成的集合；补集是在给定的全集 U 中，去掉集合 A 的元素，剩下的元素组成的集合。

二、关系关系是集合中元素之间的某种联系。

可以用笛卡尔积来定义关系。

关系的性质包括自反性、反自反性、对称性、反对称性和传递性。

自反性是指集合中的每个元素都与自身有关系；反自反性则是集合中的任何元素都与自身没有关系；对称性是如果 a 与 b 有关系，那么 b 与 a 也有关系；反对称性是如果 a 与 b 有关系且 b 与 a 有关系，那么 a 等于 b；传递性是如果 a 与 b 有关系，b 与 c 有关系，那么 a 与 c 有关系。

关系可以用关系矩阵和关系图来表示。

关系矩阵是一个二维矩阵，其中的元素表示对应元素之间是否有关系；关系图则是用节点表示元素，用有向边表示关系。

三、函数函数是一种特殊的关系，它对于定义域中的每个元素，在值域中都有唯一的元素与之对应。

函数的类型有单射函数（一对一函数）、满射函数（映上函数）和双射函数（一一对应函数）。

单射函数是指不同的定义域元素对应不同的值域元素；满射函数是指值域中的每个元素都有定义域中的元素与之对应；双射函数则同时满足单射和满射的性质。

离散数学复习资料离散数学是计算机科学与工程中的一门重要课程，对于学生来说离不开的内容就是集合、关系、图、逻辑等等。

由于离散数学的知识点比较多，所以需要用心复习备考。

本文就是为了给大家提供一些离散数学的复习资料，希望对大家的备考有所帮助。

1. 《离散数学及其应用》（Discrete Mathematics and its Applications）这本书是一本经典的教材，由美国著名数学家Kenneth H. Rosen编写，已经出版了七版。

书中内容系统、全面、深入，并且重视应用。

里面讲解的内容包括集合论、命题逻辑、谓词逻辑、证明技巧、图论、组合数学等等，每个知识点都有大量的例题和习题，适用于各个层次的学生。

此外，书中还有详细的解答和答案解析，让学生能够深入理解各个知识点的含义和应用，是一本很好的复习资料。

2. 离散数学MOOCMOOC是全称为Massive Open Online Course，中文名为大规模开放式在线课程，是指通过互联网向全球提供大规模课程，任何人都可以免费参加。

目前国内外各大高校都推出了MOOC课程，离散数学也不例外。

学生可以通过其官网或各大视频站搜索离散数学相关的MOOC，比如中国大学MOOC、Coursera等。

只要积极参与学习，基本可以达到一个不错的学习效果，同时也是一种便捷的复习方式。

3. 常见错题整理离散数学复习也需要练题，但是很多同学在复习时会出现死记硬背的情况，对于一些基础知识点掌握的不够扎实，导致在做题时出现错误。

所以整理自己的错题也是一种很好的复习方式。

学生可以以章节为单位，把做错的题目整理出来，并进行分析总结，找出其中的规律和易错点，以便更好地消化和理解这些知识点，提高做题的准确率。

4. 参考资料在复习时，参考资料也是非常重要的。

学生可以准备一本参考书或棕色折页，里面可以收集相关的定理、公式、图像等，方便随时查阅。

同时也可以利用网络资源，比如百度学术、Google Scholar等，搜索相关的论文和文献，从专业角度深入了解离散数学的各个方面，提高学习的水平和技巧。

《离散数学（第三版）》的期末复习知识点总结一、各章复习要求与重点第一章集合[复习知识点]1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、De Morgan律等），文氏（Venn）图3、序偶与迪卡尔积本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明[复习要求]1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。

2、掌握集合的表示法和集合的交、并、差、补等基本运算。

3、掌握集合运算基本规律，证明集合等式的方法。

4、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。

第二章二元关系[复习知识点]1、关系、关系矩阵与关系图2、复合关系与逆关系3、关系的性质（自反性、对称性、反对称性、传递性）4、关系的闭包（自反闭包、对称闭包、传递闭包）5、等价关系与等价类6、偏序关系与哈斯图（Hasse）、极大/小元、最大/小元、上/下界、最小上界、最大下界7、函数及其性质（单射、满射、双射）8、复合函数与反函数本章重点内容：二元关系的概念、关系的性质、关系的闭包、等价关系、半序关系、映射的概念[复习要求]1、理解关系的概念：二元关系、空关系、全关系、恒等关系；掌握关系的集合表示、关系矩阵和关系图、关系的运算。

2、掌握求复合关系与逆关系的方法。

3、理解关系的性质（自反性、对称性、反对称性、传递性），掌握其判别方法（定义、矩阵、图）。

4、掌握求关系的闭包（自反闭包、对称闭包、传递闭包）的方法。

5、理解等价关系和偏序关系的概念，掌握等价类的求法和偏序关系做哈斯图的方法，极大/小元、最大/小元、上/下界、最小上界、最大下界的求法。

6、理解函数概念：函数、函数相等、复合函数和反函数。

7、理解单射、满射、双射等概念，掌握其判别方法。

第三章命题逻辑[复习知识点]１、命题与联结词（否定、析取、合取、蕴涵、等价），复合命题２、命题公式与解释，真值表，公式分类（恒真、恒假、可满足），公式的等价３、析取范式、合取范式，极小（大）项，主析取范式、主合取范式４、公式类别的判别方法（真值表法、等值演算法、主析取/合取范式法）５、公式的蕴涵与逻辑结果６、形式演绎本章重点内容：命题与联结词、公式与解释、析取范式与合取范式、公式恒真性的判定、形式演绎[复习要求]１、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。

第一部分数理逻辑第一章命题逻辑重点：●熟练掌握联结词的定义；●掌握数理逻辑中命题的翻译及命题公式的定义；●熟记基本的等价公式和蕴涵公式；●利用真值表技术和公式法求公式的主析取范式和主合取范式；●熟练掌握应用基本推理方法完成命题逻辑推理：1.直接证法2.反证法3.CP规则难点：●如何正确地掌握对语言的翻译；●如何利用推理方法正确的完成命题推理。

第二章谓词逻辑重点：●谓词、量词、个体域的概念；●谓词逻辑中带量词命题的符号化；●熟记基本的谓词等价公式；●求公式的前束范式；●掌握谓词逻辑的推理规则以及能够熟练地完成一阶逻辑推理；难点：●谓词逻辑中带量词命题的符号化；●如何利用推理方法正确地完成一阶逻辑推理。

第二部分集合论第三章集合与关系重点：●掌握集合的五种基本运算和集合相等的证明方法；●幂集的概念以及和子集的关系；●序偶和笛卡尔积的概念；●关系定义及其和笛卡尔积之间的联系；●关系的复合；●关系的五种性质及其判断和证明；●关系的闭包；●等价关系定义、证明及其与等价类、集合的划分间的关系；●偏序关系的定义和证明，哈斯图；●偏序关系中的特殊元素；难点：●如何正确证明集合之间包含和相等关系；●如何正确地理解和判断关系的性质；●非常重要的关系性质的证明方法——按定义证明法；●如何正确地掌握等价关系及相应的等价类与集合划分之间的关系；●如何正确地理解和判断偏序关系中的八种特殊元素。

第四章函数重点：●能够判定某个二元关系是否是函数；●几种特殊的函数：满射，单射，双射；难点：●如何正确地判断三种特殊函数。

第三部分代数结构重点：●理解代数结构的构成和研究方法；●代数结构中运算的性质以及特殊元素；●广群⇒半群⇒独异点⇒群；●群的定义与性质；●环与域的判断和证明；●格的两种定义；●特殊格：分配格、有界格、有补格、有补分配格；●有补分配格与布尔代数之间的联系；难点：●循环群的判断和证明；●如何正确理解由偏序关系定义的格与由代数系统定义格之间的关系和区别；●如何正确理解布尔代数的概念。