离散数学期末复习指导(专科)

《离散数学》期末复习一、期末考试题型试题类型及分数分别为单项选择题和填空题各有15题，分数占60％；化简解答题与计算题及证明题，共占40％。

各章分数的比例大致与其所用课时比例相同。

单项选择题和填空题主要涉及基本概念、基本理论、重要性质和结论、公式及其简单计算。

单项选择题给出四个备选答案，其一正确。

填空题只需填写正确结论，不写计算、推论过程或理由。

化简解答题与计算题主要考核同学们的基本运算技能和速度，要求写出计算过程。

证明题主要考查应用概念、性质、定理及重要结论进行逻辑推理的能力，要求写出推理过程。

二、各章复习要求和重点第1章命题逻辑复习要求1. 命题及其联结词。

命题表述为具有确定真假意义的陈述句。

命题必须具备二个条件：其一，语句是陈述句；其二，语句有唯一确定的真假意义，六个联结词。

2. 命题公式及分类。

在各种赋值下均为真的命题公式A，称为重言式(永真式)；在各种赋值下均为假的命题公式A，称为矛盾式(永假式)；命题A不是矛盾式，称为可满足式；真值表3. 命题的判定及命题演算的推理理论。

推理方法有：真值表法；等值演算法；主析取范式法，构造证明法(直接证明法、附加前提证明法和间接证明法)本章重点：命题与联结词，公式与解释，真值表，公式的类型及判定, (主)析取(合取)范式，命题逻辑的推理理论.。

第2章一阶逻辑复习要求1.谓词与量词谓词，在谓词逻辑中，原子命题分解成个体词和谓词. 个体词是可以独立存在的客体，它可以是具体事物或抽象的概念。

谓词是用来刻划个体词的性质或事物之间关系的词 量词，是在命题中表示数量的词，量词有两类：全称量词∀，表示“所有的”或“每一个”；存在量词∃，表示“存在某个”或“至少有一个”2. 2.公式与解释谓词公式，由原子公式、联结词和量词可构成谓词公式(严格定义见教材).命题的符号化结果都是谓词公式.例如∀x(F(x)→G(x))，∃x(F(x)∧G(x))，∀x∀y(F(x)∧F(y)∧L(x,y)→H(x,y))等都是谓词公式3. 解释(赋值)，谓词公式A的个体域D是非空集合，则(1) 每一个常项指定D中一个元素；(2) 每一个n元函数指定D n到D的一个函数；(3) 每一个n元谓词指定D n到{0,1}的一个谓词；按这个规则做的一组指派，称为A的一个解释或赋值。

离散数学期末复习指导注意：1试题类型及结构：单项选择题的分数占15％，填空题的分数占15％，公式翻译题的分数占12％，判断说明题的分数占14％，计算题的分数占36％；证明题的分数占8％．2考试重点：本学期的三次教学活动资料、学习笔记和历年试题！3离散数学期末复习指导分为两个部分：第一部分，离散数学历年试题汇编，熟悉考试试题及解题方法；第二部分，例题精讲。

4请大家充分利用课程学习平台教学活动资料栏目（尤其是本学期 11 月 3 日 ， 24 日和 12 月 9 日 的三次教学辅导活动资料）、学习笔记栏目和课程复习 — 自测栏目中的资料，抓住重点进行复习争取期末考试获得好成绩。

第一部分，离散数学历年试题汇编一、单项选择题1．若集合A ={1，{1}，{2}，{1，2}}，则下列表述正确的是(A )．A ．{2}∈AB ．{1，2}⊂AC ．1∉AD ．2 ⊂ A 2．设G 为无向图，则下列结论成立的是 ( C ) ． A ．无向图G 的结点的度数等于边数的两倍． B ．无向图G 的结点的度数等于边数．C ．无向图G 的结点的度数之和等于边数的两倍．D ．无向图G 的结点的度数之和等于边数． 3．图G 如图一所示，以下说法正确的是(C ) ． A ．{(a ，b )}是边割集 B ．{ a ，c }是点割集 C ．{d }是点割集 D ．{ (c ，d )}是边割集图一4．设集合A ={1}，则A 的幂集为( D )．A ．{{1}}B ．{1，{1}}C ．{∅，1}D ．{∅，{1}}5．设A (x )：x 是人，B (x )：x 犯错误，则命题“没有不犯错误的人” 可符号化为（ B ）．A ．┐(∃x )( A (x ) → ┐B(x))B ．┐(∃x )( A (x )∧┐B (x ))C ．┐(∃x )( A (x )∧B (x ))D ．(∀x )( A (x )∧B (x ))6.若集合A={a,{1}}则下列表述正确的是( A).. {1}. {1}. {}. A A B A C a AD A∈⊆∈∅∈7. 设图,,GV E v V=<>∈，则下列结论成立的是(D).A 、deg()2v E =B 、deg()v E=οο ο οοο a b c defC 、deg()v Vv E ∈=∑ D 、deg()2v Vv E ∈=∑8. 如图一所示，以下说法正确的是（B ）。

离散数学复习资料离散数学是计算机科学与数学领域中的重要学科，它研究的是离散的数学结构和离散的数学对象。

在计算机科学领域，离散数学是构建算法和设计计算机系统的基础。

为了更好地复习离散数学，我们可以从以下几个方面入手。

一、集合论集合论是离散数学的基础，它研究的是集合及其运算。

在集合论中，我们需要了解集合的定义、基本运算和集合间的关系。

此外，还需要掌握集合的代数运算法则，如交、并、差和补集等。

复习时可以通过解题来加深理解，例如证明集合之间的等价关系、集合的幂集等。

二、逻辑与命题逻辑是离散数学中的重要分支，它研究的是推理和论证的规则。

在逻辑中，命题是最基本的逻辑单位。

复习时需要了解命题的定义和常见的逻辑运算符，如非、与、或、异或等。

此外，还需要熟悉命题的真值表和命题之间的逻辑等价关系。

通过解题和推理，可以提高对逻辑的理解和应用能力。

三、图论图论是离散数学中的一个重要分支，它研究的是图及其性质。

在图论中，我们需要了解图的基本概念，如顶点、边、路径、环等。

此外，还需要熟悉图的表示方法，如邻接矩阵和邻接表。

复习时可以通过解题来加深对图的理解，例如求最短路径、判断图的连通性等。

四、代数系统代数系统是离散数学中的一个重要内容，它研究的是代数结构及其性质。

在代数系统中，我们需要了解群、环、域等代数结构的定义和性质。

此外，还需要熟悉代数运算法则和代数结构之间的关系。

复习时可以通过解题来加深对代数系统的理解，例如证明一个集合构成一个群、判断一个环是否是域等。

五、概率论与统计学概率论与统计学是离散数学中的一个重要分支，它研究的是随机事件和随机变量的概率性质。

在概率论与统计学中，我们需要了解概率的定义和性质，掌握常见的概率分布和统计方法。

此外，还需要熟悉概率的运算法则和统计推断的基本原理。

复习时可以通过解题和实际问题的分析来加深对概率论与统计学的理解。

总之，离散数学作为计算机科学与数学领域中的重要学科，对于计算机科学专业的学生来说具有重要意义。

离散数学期末复习总要离散数学期末复习各个章节要点纲要（及定理）离散数学定义定理1.3.1命题演算的合式公式规定为：（1）单个命题变元本身是一个合式公式。

（2）如果A是合式公式，那么┐A是合式公式。

（3）如果A和B是合式公式，那么（A∨B）、（A∧B）、（A→B）、（A?B）、都是合式公式。

（4）当且仅当有限次地应用（1）（2）（3）所得到的包含命题变元，连接词和圆括号的符号串是合式公式。

1.3.2 设Ai是公式A的一部分，且Ai是一个合式公式，称Ai是A的子公式。

1.3.3 设P为一命题公式，P1,P2,……，Pn为出现在P中的所有命题变元，对P1,P2,……，Pn指定一组真值称为对P的一种指派。

若指定的一种指派，使P的值为真，则称这组指派为成真指派。

若指定的一种指派，使P的值为假，则称这种指派为成假指派。

含n个命题变元的命题公式，共有2n个指派。

1.3.4 给定两个命题公式A和B，设P1,P2,……，Pn为所有出现于A和B中的原子变元，若给P1,P2,……，Pn任一组真值指派，A和B的真值都相同，称A和B是等价的，记做A <=>B。

1.3.5 设A为一命题公式，若A在它的各种指派情况下，其取值均为真，则称A为重言式或永真式。

1.3.6 设A为一命题公式，若A在它的各种指派情况下，其取值均为假，则称A为矛盾式或永假式。

1.3.7设A为一命题公式，若A在它的各种指派情况下至少存在一组成真指派，则称A为可满足式。

1.4.1 设X式合式公式A的子公式，若有Y也是一个合式公式，且X<=>Y，如果将Ａ中的Ｘ用Ｙ置换，得到公式Ｂ，则A<=>B。

1.4.2 设A，B为两个命题公式，A<=>B，当且仅当A ←→B为一个重言式。

P=>Q称做P蕴含Q或蕴含式，又称永真条件式。

蕴含式有下列性质：（1）对任意公式A，又A=>A；（2）对任意公式A，B和C，若A=>B，B=>C，则A=>C；（3）对任意公式A，B和C，若A=>B，A=>C，则A=>(B∧C); （4）对任意公式A，B和C，若A=>C，B=>C，则A∨B=>C.1.4.3设P，Q为任意两个命题公式，P<=>Q的充分必要条件式P=>Q,，Q=>P。

《离散数学》期末复习大纲（完整版）（含例题和考试说明）一、命题逻辑[复习知识点]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）为可满足。

离散数学期末复习要点与重点离散数学计算机科学与技术专业的一门统设必修学位课程，共60学时，开设一学期．该课程的主要内容包括：数理逻辑、集合论、图论等．第1章 命题逻辑复习要点1．理解命题概念，会判别语句是不是命题．理解五个联结词：否定⌝P 、析取∨、合取∧、条件→、和双条件↔及其真值表，会将简单命题符号化．具有确定真假意义的陈述句称为命题．命题必须具备：其一，语句是陈述句；其二，语句有唯一确定的真假意义.2．了解公式的概念(公式、赋值、成真赋值和成假赋值)和公式真值表的构造方法．能熟练地作公式真值表．理解永真式和永假式概念，掌握其判别方法．判定命题公式类型的方法：其一是真值表法，其二是等值演算法.3．了解公式等价概念，掌握公式的重要等价式和判断两个公式是否等价的有效方法：等值演算法、列真值表法和主范式方法．4．理解析取范式和合取范式、极大项和极小项、主析取范式和主合取范式的概念以及和成真赋值、成假赋值的关系，熟练掌握它们的求法．命题公式的范式不惟一，但主范式是惟一的．5．了解C 是前提集合{A 1,A 2,…,A m }的有效结论或由A 1, A 2, …, A m 逻辑地推出C 的概念．要理解并掌握推理理论的规则、重言蕴含式和等价式，掌握命题公式的证明方法：真值表法、直接证法、间接证法．重点：命题与联结词，公式与解释，真值表，公式的类型及判定，主析取(合取)范式，命题演算的推理理论.第2章 谓词逻辑复习要点1．理解谓词、量词、个体词、个体域，会将简单命题符号化．原子命题分成个体词和谓词，个体词可以是具体事物或抽象的概念，分个体常项和个体变项．谓词用来刻划个体词的性质或之间的关系．量词分全称量词∀，存在量词∃.命题符号化注意：使用全称量词∀，特性谓词后用→；使用存在量词∃，特性谓词后用∧．2．了解原子公式、谓词公式、变元(约束变元和自由变元)与辖域等概念．掌握在有限个体域下消去公式的量词和求公式在给定解释下真值的方法．由原子公式、联结词和量词构成谓词公式．谓词公式具有真值时，才是命题．在谓词公式∀xA 或∃xA 中，x 是指导变元，A 是量词的辖域．会区分约束变元和自由变元．在非空集合D (个体域)上谓词公式A 的一个解释或赋值有3个条件．在任何解释下，谓词公式A 取真值1，A 为逻辑有效式(永真式)；公式A 取真值0，A 为永假式；至少有一个解释使公式A 取真值1，A 称为可满足式．会求谓词公式的真值，量词的辖域，自由变元、约束变元，以及换名规则、代入规则等． 掌握谓词演算的等值式和重言蕴含式．并进行谓词公式的等价演算．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，…，Q k 只能是∀或∃，而x 1, x 2, …, x k 是个体变元，B 是不含量词的谓词公式．前束范式仍然是谓词公式．重点：谓词与量词，公式与解释，谓词演算．第3章 集合及其运算复习要点1．理解集合、元素、集合的包含、子集、相等，以及全集、空集和幂集等概念，熟练掌握集合的表示方法．具有确定的，可以区分的若干事物的全体称为集合，其中的事物叫元素.．集合的表示方法：列举法和描述法.注意：集合的表示中元素不能重复出现，集合中的元素无顺序之分．掌握集合包含(子集)、真子集、集合相等等概念．注意：元素与集合，集合与子集，子集与幂集，∈与⊂(⊆),空集∅与所有集合等的关系. 空集∅，是惟一的，它是任何集合的子集． 集合A 的幂集P (A )＝}{A x x ⊆， A 的所有子集构成的集合．若∣A ∣＝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章 关系与函数复习要点1．了解有序对和笛卡儿积的概念，掌握笛卡儿积的运算．有序对就是有顺序二元组，如<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 ,y >∣x ∈A ,y ∈B }，是有序对的集合.笛卡儿积也可以多个集合合成，A 1×A 2×…×A n ．2．理解关系的概念：二元关系、空关系、全关系、恒等关系.掌握关系的集合表示、关系矩阵和关系图，掌握关系的集合运算和求复合关系、逆关系的方法．二元关系是一个有序对集合，},{B y A x y x R ∈∧∈><=，记作xRy ．空关系∅是唯一、是任何关系的子集的关系；全关系},,{A b a b a E A ∈><=A A ⨯≡；恒等关系},{A a a a I A ∈><=，恒等关系的矩阵M I 是单位矩阵．关系的集合运算有并、交、补、差和对称差．复合关系}),,(,{2121R c b R b a b c a R R R >∈<∧>∈<∃><=•=；复合关系矩阵：21R R R M M M ⨯=(按布尔运算)；有结合律：(R •S )•T ＝R •(S •T )，一般不可交换．逆关系},,{1R y x x y R >∈<><=-；逆关系矩阵满足：T R R M M =-1；复合关系与逆关系存在：(R •S )－1=S －1•R －1．3．理解关系的性质(自反性和反自反性、对称性和反对称性、传递性的定义以及矩阵表示或关系图表示)，掌握其判别方法(利用定义、矩阵或图，充分条件)，知道关系闭包的定义和求法．注：(1)关系性质的充分必要条件：① R 是自反的⇔I A ⊆R ；②R 是反自反的⇔I A ⋂R ＝∅；③R 是对称的 ⇔R ＝R －1；④R 是反对称的⇔R ⋂R －1⊆I A ；⑤R 是传递的⇔R •R ⊆R .(2)I A 具有自反性，对称性、反对称性和传递性．E A 具有自反性，对称性和传递性．故I A ，E A 是等价关系．∅具有反自反性、对称性、反对称性和传递性．I A 也是偏序关系．4．理解等价关系和偏序关系概念，理解集合上等价关系与划分一一对应的关系、掌握划分的求法和做偏序集哈斯图的方法．知道极大(小)元，最大(小)元的概念，会求极大(小)元、最大(小)元、上界和下界、最小上界和最大下界．等价关系和偏序关系是具有不同性质的两个关系.⎩⎨⎧==+⎭⎬⎫⎩⎨⎧+偏序关系等价关系传递性反对称性对称性自反性 知道等价关系图的特点和等价类定义，会求等价类．一个子集的极大(小)元可以有多个，而最大(小)元若有，则惟一.且极元、最元只在该子集内；而上界与下界可以在子集之外．由哈斯图便于确定任一子集的最大(小)元，极大(小)元．5．理解函数概念：函数(映射)，函数相等，复合函数和反函数。

《离散数学》期末复习《离散数学》期末复习内容：第一章~第七章题型：一、选择题（20%，每题2分）二．填空题（20%，每题2分）三、计算题（20%，每题5分）四、证明题（20%，每题5分）五、判断题（20%，每题2分）第1章数学语言与证明方法1.1 常用的数学符号1.计算常用的数学符号式子1.2 集合及其表示法1.用列举法和描述法表示集合2.判断元素与集合的关系(属于和不属于)3.判断集合之间的包含与相等关系，空集(E)，全集(?)4.计算集合的幂集5.求集合的运算：并、交、相对补、对称差、绝对补6.用文氏图表示集合的运算7.证明集合包含或相等方法一：根据定义, 通过逻辑等值演算证明方法二：利用已知集合等式或包含式, 通过集合演算证明1.3 证明方法概述1、用如下各式方法对命题进行证明。

直接证明法：A→B为真间接证明法：“A→B为真” ?“ ?B→ ?A为真”归谬法(反证法)：A∧?B→0为真穷举法：A1→B, A2→B,…, A k→B 均为真构造证明法：在A为真的条件下, 构造出具有这种性质的客体B ?空证明法：“A恒为假” ?“A→B为真”平凡证明法：“B恒为真” ?“A→B为真”数学归纳法：第2章命题逻辑2.1 命题逻辑基本概念1、判断句子是否为命题、将命题符号化、求命题的真值（0或1）。

命题的定义和联结词(?, ∧, ∨, →, ?)2、判断命题公式的类型赋值或解释.成真赋值,成假赋值；重言式(永真式)、矛盾式(永假式)、可满足式:。

2.2 命题逻辑等值演算1、用真值表判断两个命题公式是否等值2、用等值演算证明两个命题公式是否等值3、证明联结词集合是否为联结词完备集2.3 范式1、求命题公式的析取范式与合取范式2、求命题公式的主析取范式与主合取范式（两种主范式的转换）3、应用主析取范式分析和解决实际问题2.4 命题逻辑推理理论1、用直接法、附加前提、归谬法、归结证明法等推理规则证明推理有效第3章一阶逻辑3.1 一阶逻辑基本概念1、用谓词公式符号命题（正确使用量词）2、求谓词公式的真值、判断谓词公式的类型3.2 一阶逻辑等值演算1、证明谓词公式的等值式2、求谓词公式的前束范式第4章关系4.1 关系的定义及其表示1、计算有序对、笛卡儿积2、计算给定关系的集合3、用关系图和关系矩阵表示关系4.2 关系的运算1、计算关系的定义域、关系的值域2、计算关系的逆关系、复合关系和幂关系3、证明关系运算满足的式子4.3 关系的性质1、判断关系是否为自反、反自反、对称、反对称、传递的2、判断关系运算与性质的关系3、计算关系自反闭包、对称闭包和传递闭包4.4 等价关系与偏序关系1、判断关系是否为等价关系2、计算等价关系的等价类和商集3、计算集合的划分4、判断关系是否为偏序关系5、画出偏序集的哈期图6、求偏序集的最大元、最小元、极小元、极大元、上界、下界、上确界、下确界7、求偏序集的拓扑排序第5章函数1.判断关系是否为函数2.求函数的像和完全原像3.判断函数是否为满射、单射、双射4.构建集合之间的双射函数5.求复合函数6.判断函数的满射、单射、双射的性质与函数复合运算之间的关系7.判断函数的反函数是否存在，若存在求反函数第6章图1.指出无向图的阶数、边数、各顶点的度数、最大度、最小度2.指出有向图的阶数、边数、各顶点的出度和入度、最大出度、最大入度、最小出度最小入出度3.根据握手定理顶点数、边数等4.指出图的平行边、环、弧立点、悬挂顶点和悬挂边5.判断给定的度数列能否构成无向图6.判断图是否为简单图、完全图、正则图、圈图、轮图、方体图7.求给定图的补图、生成子图、导出子图8.判断两个图是否同构6.2 图的连通性1.求图中给定顶点通路、回路的距离2.计算无向图的连通度、点割集、割点、边割集、割边3.判断有向图的类型：强连通图、单向连通图、弱连通图6.3 图的矩阵表示1.计算无向图的关联矩阵2.计算有向无环图的关联矩阵3.计算有向图的邻接矩阵4.计算有向图的可达矩阵5.计算图的给定长度的通路数、回路数6.4 几种特殊的图1、判断无向图是否为二部图、欧拉图、哈密顿图第7章树及其应用7.1 无向树1.判断一个无向图是否为树2.计算无向树的树叶、树枝、顶点数、顶点度数之间的关系3.给定无向树的度数列，画出非同构的无向树4.求生成树对应的基本回路系统和基本割集系统5.求最小生成树7.2 根树及其应用1.判断一个有向图是否为根树2.求根树的树根、树叶、内点、树高3.求最优树4.判断一个符号串集合是否为前缀码5.求最佳前缀码6.用三种方法遍历根树。

离散数学期末复习要点与重点离散数学是计算机科学及其他相关学科中的一门重要的基础课程。

它主要研究离散的结构和对象，以及它们之间的关系和性质。

离散数学的核心内容包括集合论、关系、图论、布尔代数和逻辑等。

下面是离散数学期末复习的要点与重点。

一、集合论1.集合的基本概念，包括元素、子集、幂集、集合的运算等。

2.集合的性质，如交换律、结合律、分配律等。

3.集合的表示方法，包括列举法、描述法、特征函数法等。

4.集合的运算，如并、交、差、对称差等。

5.集合的关系，包括子集关系、相等关系、真子集关系等。

二、关系1.关系的基本概念，包括序偶、笛卡尔积、关系的定义等。

2.关系的性质，如自反性、对称性、传递性等。

3.关系的表示方法，包括关系矩阵、关系图、关系表等。

4.关系的运算，如复合、逆、幂等等。

5.等价关系和偏序关系的特性和性质。

6.关系的闭包，包括自反闭包、对称闭包、传递闭包等。

三、图论1.图的基本概念，包括顶点、边、路径、环等。

2.不同类型的图，包括无向图、有向图、简单图、多重图等。

3.图的表示方法，包括邻接矩阵、邻接表等。

4.图的遍历算法，包括深度优先（DFS）和广度优先（BFS）。

5. 最小生成树算法，包括Prim算法和Kruskal算法。

6. 最短路径算法，包括Dijkstra算法和Floyd-Warshall算法。

四、布尔代数1.布尔代数的基本运算，包括与、或、非等。

2.布尔函数的最小项和最大项表示方法。

3.布尔函数的化简，包括代数化简和卡诺图化简。

4.布尔函数的特性，包括恒等律、零律、单位律等。

5.布尔函数的逻辑门电路实现，包括与门、或门、非门等。

五、逻辑1.命题逻辑的基本概念，包括命题、命题变量、逻辑联结词等。

2.命题逻辑的语法，包括命题公式的形式化定义和语法规则。

3.命题逻辑的证明方法，包括直接证明、间接证明、反证法等。

4.谓词逻辑的基本概念，包括谓词、量词、合取范式等。

5.谓词逻辑的语义，包括赋值、满足关系等。