《离散数学第三版》方世昌的期末复习知识点总结含例题

《离散数学》复习重点0000第一章命题逻辑的基本概念000一、命题公式的类型：重言式矛盾式可满足式0000二、给出公式的成真赋值、成假赋值0000例：p q 成真赋值为01 00 11000三、判断公式类型0000四、题目：P15 20 21 0000P13 6000第二章命题逻辑的基本概念000一、熟记等值演算判断公式的类型0000二、求公式的主析取范式和主合取范式00001 方法1 等值演算00002 方法2 真值表0003 主吸取范式和主合取范式的关系0000第三章命题逻辑的推理理论000一、推理定理P46000二、自然推理系统0000三、题目：P50 例3.5 例3.6 P53 14 15 180000第四章一阶逻辑的基本概念000一、在一阶逻辑中将命题符号化00001 注意：同一命题在不同个体域中符号化形式可能不一样000二、习题:P57 例4.2 P65 2 4 50000注意：例4.2中任意用蕴含，存在用合取0000第五章一阶逻辑等值演算与推理0000这章不是重点，不考0000第六章集合代数0000一、P85 定理6.1 定义6.50000二、运算：00001 相对补对称差00002 交并补0000第七章二元关系0000一、笛卡尔积A*B={<x，y>|x∈A∧y∈B}000二、二元关系P104 定义7.40000三、集合的表示方法：集合表达式关系图关系矩阵0000四、关系的运算00001 关系的定义域 domR = {x|∃y(<x，y>∈R)}0000关系的值域 ranR={y|∃x(<x，y>∈R)}00002 复合运算（右复合）0000错误！未找到引用源。

={<x，y>|∃t（<x，t>∈F∧<t，y>∈G）}000 03 关系的逆运算错误！未找到引用源。

0000错误！未找到引用源。

={<x，y>|<y，x>∈R}0004 恒等关系错误！未找到引用源。

离散数学期末复习总要离散数学期末复习各个章节要点纲要（及定理）离散数学定义定理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）为可满足。

《离散数学》期末复习提要《离散数学》是中央电大“数学与数学应用专业”（本科）的一门选修课。

该课程使用新的教学大纲，在原有离散数学课程的基础上削减了教学内容（主要是群与环、格与布尔代数这两章及图论的后三节内容），使用的教材为中央电大出版的《离散数学》（刘叙华等编）和《离散数学学习指导书》（虞恩蔚等编）。

离散数学主要研究离散量结构及相互关系，使学生得到良好的数学训练，提高学生抽象思维和逻辑推理能力，为从事计算机的应用提供必要的描述工具和理论基础。

其先修课程为：高等数学、线性代数；后续课程为：数据结构、数据库、操作系统、计算机网络等。

课程的主要内容1、集合论部分（集合的基本概念和运算、关系及其性质）；2、数理逻辑部分（命题逻辑、谓词逻辑）；3、图论部分（图的基本概念、树及其性质）。

学习建议离散数学是理论性较强的学科，学习离散数学的关键是对离散数学（集合论、数理逻辑和图论）有关基本概念的准确掌握，对基本原理及基本运算的运用，并要多做练习。

教学要求的层次各章教学要求的层次为了解、理解和掌握。

了解即能正确判别有关概念和方法；理解是能正确表达有关概念和方法的含义；掌握是在理解的基础上加以灵活应用。

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

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

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

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

[本章重点习题]P5~6，4、6； P14~15，3、6、7； P20，5、7。

离散数学知识点总结离散数学知识点总结同时要善于总结，在学习《离散数学》的过程，对概念的理解是学习的重中之重。

本文就来分享一篇离散数学知识点总结，希望对大家能有所帮助！一、认知离散数学离散数学是计算机科学基础理论的核心课程之一，是计算机及应用、通信等专业的一门重要的基础课。

它以研究量的结构和相互关系为主要目标，其研究对象一般是有限个或可数个元素，充分体现了计算机科学离散性的特点。

学习离散数学的目的是为学习计算机、通信等专业各后续课程做好必要的知识准备，进一步提高抽象思维和逻辑推理的能力，为计算机的应用提供必要的描述工具和理论基础。

1．定义和定理多离散数学是建立在大量定义、定理之上的逻辑推理学科，因此对概念的理解是学习这门课程的核心。

在学习这些概念的基础上，要特别注意概念之间的联系，而描述这些联系的实体则是大量的定理和性质。

在考试中有一部分内容是考查学生对定义和定理的识记、理解和运用，因此要真正理解离散数学中所给出的每个基本概念的真正的含义。

比如，命题的定义、五个基本联结词、公式的主析取范式和主合取范式、三个推理规则以及反证法；集合的五种运算的定义；关系的定义和关系的四个性质；函数（映射）和几种特殊函数（映射）的定义；图、完全图、简单图、子图、补图的定义；图中简单路、基本路的定义以及两个图同构的定义；树与最小生成树的定义。

掌握和理解这些概念对于学好离散数学是至关重要的。

2. 方法性强在离散数学的学习过程中，一定要注重和掌握离散数学处理问题的方法，在做题时，找到一个合适的解题思路和方法是极为重要的`。

如果知道了一道题用怎样的方法去做或证明，就能很容易地做或证出来。

反之，则事倍功半。

在离散数学中，虽然各种各样的题种类繁多，但每类题的解法均有规律可循。

所以在听课和平时的复习中，要善于总结和归纳具有规律性的内容。

在平时的讲课和复习中，老师会总结各类解题思路和方法。

作为学生，首先应该熟悉并且会用这些方法，同时，还要勤于思考，对于一道题，进可能地多探讨几种解法。

离散数学总复习第1章命题逻辑一、命题的判断例：1、仁者无敌！2、x+y<23、如果雪是红的，那么地球是月亮的卫星。

4、我正在说谎。

二、命题符号化例：1、蓝色和黄色可以调成绿色。

2、付明和杨进都是运动员。

3、刘易斯是百米游泳冠军或百米跨栏冠军。

4、李飞现在在宿舍或在图书馆。

5、只要天不下雨，我就步行上学校。

6、只有天不下雨，我才步行上学校。

7、并非只要你努力了，就一定成功。

三、主范式1、会等值演算；2、主合取和主析取范式的相互转换。

例：求命题公式P∨Q的主析取范式和主合取范式。

3、根据主范式进行方案的选择例1：某科研所要从3名科研骨干A,B,C中挑选1-2名出国进修，由于工作需要，选派需同时满足条件：（1）若A去，则C同去；（2）只有C不去，B才去；（3）只要C不去，则A或B就可以去。

问有哪些选派方案？例2：甲、乙、丙、丁四人有且仅有两个人参加比赛，下列四个条件均要满足：（1）甲和乙有且只有一人参加；（2）丙参加，则丁必参加；（3）乙和丁至多有一人参加；（4）丁不参加，甲也不会参加。

问哪两个人参加了比赛？四、简单的推理例1：如果明天天气好我们就去爬长城。

明天天气好。

所以我们去爬长城。

例3：课后习题16第2章谓词逻辑一、谓词逻辑中的命题符号化例：1、所有运动员都是强壮的2、并非每个实数都是有理数3、有些实数是有理数二、量词的辖域，约束变元换名、自由变元代替例：1、∀x(P(x)∨∃yR(x,y))→Q(x)2、∀x(P(x,z)∨∃yR(x,y))→Q(x)中量词的辖域，重名情况，改名等三、命题逻辑永真式的任何代换实例必是谓词逻辑的永真式。

同样，命题逻辑永假式的任何代换实例必是谓词逻辑的永假式。

例：1、(∀xP(x)→∃xQ(x))↔(⌝∀xP(x)∨∃xQ(x))2、(∀xP(x)→∃xQ(x))∧(∃xQ(x))→∀zR(z)))→(∀xP(x) →∀zR(z))1-2是永真式（重言式）3、⌝(∀xF(x) ∃yG(y)) ∧ ∃yG(y) 永假式（矛盾式）四、消量词例：个体域D={1,2}，对∀x∀y(P(x)→Q(y))消量词五、简单的前束范式会判断即可。

《离散数学》方世昌的期末复习知识点总结1.集合论-集合的定义和运算：交、并、差、补、反转。

子集与真子集的概念。

-集合的基数：有限集、无限集、可数集、不可数集的定义与特性。

-集合的运算律：交换律、结合律、分配律、幂等律、吸收律。

-集合的等价关系：等价关系的定义和性质，等价关系的划分和等价类。

2.逻辑与命题关系-命题与命题符号：命题的定义、真值表和含有逻辑连接词的复合命题。

-命题逻辑：命题的蕴涵、等价、否定、充分条件和必要条件。

-谓词逻辑：命题的全称量词、存在量词及其关系。

-命题逻辑推理：假言推理、析取推理、拒取推理、类比推理等。

3.图论-图的基本概念与术语：顶点、边、邻接、路径、回路、连通、子图、生成树等。

-图的分类：无向图、有向图、简单图、多重图、完全图。

-图的矩阵表示：邻接矩阵、关联矩阵、度矩阵等。

-图的遍历算法：深度优先、广度优先。

-图的最短路径算法：迪杰斯特拉算法、弗洛伊德算法。

4.代数系统与半群-代数结构：代数系统的定义、代数公理、代数性质。

-半群：半群的定义与性质，封闭性、结合律和单位元。

-半群的子半群与同态：子半群的概念，同态映射的定义与性质。

-有限半群与无限半群：有限半群的定义和性质，无限半群的特点与例子。

5.数论与代数-整数与整数集合的性质：整数的除法原理、整除、公约数、最大公约数和最小公倍数。

-同余关系与同余类：同余关系的定义、同余类的性质、同余关系的基本定理。

-质数与素数：质数的定义、素数的性质、素数的判定方法。

-线性同余方程：线性同余方程的解法、同余方程的应用。

以上仅是《离散数学》中的部分重要知识点总结，该教材还包括很多其他内容，如排列组合、概率论、布尔代数等等。

期末复习时，建议从教材中选取一些重点章节进行深入学习和复习，同时要进行大量的习题训练，加深对知识点的理解和掌握。

祝你在期末考试中取得好成绩！。

【半群】G非空，·为G上的二元代数运算，满足结合律。

【群】（非空，封闭，结合律，单位元，逆元）恰有一个元素1适合1·a=a·1=a,恰有一个元素a-1适合a·a-1=a-1·a=1。

【Abel群/交换群】·适合交换律。

可能不只有两个元素适合x2=1【置换】n元置换的全体作成的集合Sn对置换的乘法作成n 次对称群。

【子群】按照G中的乘法运算·,子集H仍是一个群。

单位子群{1}和G称为平凡子群。

【循环群】G可以由它的某元素a生成,即G=（a）。

a所有幂的集合an，n=0，±1，±2，…做成G的一个子群，由a生成的子群。

若G的元数是一个质数，则G必是循环群。

n元循环群（a）中,元素ak是（a）的生成元的充要条件是（n，k）=1。

共有ϕ（n）个。

【三次对称群】{I（12）（13）（23）（123）（132）}【陪集】a，b∈G，若有h∈H，使得a =bh，则称a合同于b（右模H），a≡b（右mod H）。

H有限，则H的任意右陪集aH的元数皆等于H的元数。

任意两个右陪集aH和bH或者相等或者不相交。

求右陪集：H本身是一个；任取a∉H而求aH又得到一个；任取b∉H∪aH而求bH又一个。

G=H∪aH∪bH∪…【正规子群】G中任意g，gH=Hg。

（H=gHg-1对任意g∈G都成立）Lagrange定理G为有限群，则任意子群H的元数整除群G的元数。

1有限群G的元数除以H的元数所得的商，记为（G：H），叫做H在G中的指数，H的指数也就是H的右（左）陪集的个数。

2设G为有限群,元数为n,对任意a∈G，有an=1。

3若H在G中的指数是2，则H必然是G的正规子群。

证明：此时对H的左陪集aH，右陪集Ha，都是G中元去掉H的所余部分。

故Ha=aH。

4G的任意多个子群的交集是G的子群。

并且，G的任意多个正规子群的交集仍是G的正规子群。

5 H是G的子群。

离散数学知识点总结离散数学是数学中的一个分支，研究离散对象及其关系的数学理论。

它与连续数学形成鲜明的对比，连续数学主要研究连续对象和其性质。

离散数学在计算机科学、信息科学、电子工程等领域具有重要的应用价值。

下面将对离散数学的主要知识点进行总结。

1.命题逻辑：命题逻辑研究由命题符号组成的复合命题及其逻辑关系。

其中命题是一个陈述性的语句，可以是真或假。

命题逻辑包括命题的逻辑运算、真值表、命题的等价、充分必要条件等。

2.谓词逻辑：谓词逻辑是对命题逻辑的扩充，引入了量词、谓词和项。

它的研究对象是命题函数，可以表示个体之间的关系。

谓词逻辑包括谓词的运算、量词的运算、公理化和推理规则等。

3.集合论：集合论是研究集合及其操作的数学分支。

集合是一种由确定的对象组成的整体。

集合论包括集合的基本运算（交、并、差、补）、集合的关系（包含、相等、子集、真子集）以及集合的运算律和推导定理等。

5.组合数学：组合数学是研究物体的组合与排列问题的数学分支。

它包括排列、组合、分配、生成函数等内容，经常应用于计数和概率问题中。

6.图论：图论是用来描述物体间其中一种关系的图形结构的数学理论。

它研究的对象是由顶点和边构成的图，包括无向图、有向图、带权图等。

图论研究的内容包括图的性质、连通性、路径、回路、树、图的着色等。

7.代数系统：代数系统是一种由一组元素及其相应的运算规则构成的数学结构。

常见的代数系统有群、环、域、格等，它们分别研究了集合上的不同运算规律和结构。

8.布尔代数：布尔代数是一种应用于逻辑和计算机的代数系统。

它以真和假为基础，通过逻辑运算（与、或、非）构成了布尔代数。

布尔代数在计算机硬件设计和逻辑推理中广泛应用。

9.图的同构与图的着色：图的同构是指两个图在结构上相同，也就是说，它们具有相同的顶点和边的连接关系。

图的同构判断是一个NP难问题，需要借助于图的着色等方法来判断。

图的着色是给图的顶点分配颜色，使得相邻顶点的颜色不同。

离散数学初步例题和知识点总结离散数学是现代数学的一个重要分支，它在计算机科学、信息科学、密码学等领域都有着广泛的应用。

下面我们通过一些例题来讲解离散数学中的部分重要知识点。

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

例 1：设集合 A ＝｛1, 2, 3, 4}，B ＝｛3, 4, 5, 6}，求 A ∪ B 和 A∩ B。

解：A ∪ B ＝｛1, 2, 3, 4, 5, 6}，A ∩ B ＝｛3, 4}集合的运算包括并集、交集、差集等。

并集是将两个集合中的所有元素合并在一起，去掉重复的元素；交集是两个集合中共同拥有的元素组成的集合。

知识点：集合的基本运算规则1、交换律：A ∪ B ＝ B ∪ A，A ∩ B ＝B ∩ A2、结合律：（A ∪ B) ∪ C ＝ A ∪（B ∪ C)，（A ∩ B) ∩ C ＝ A ∩ （B ∩ C)3、分配律：A ∩ （B ∪ C) ＝（A ∩ B) ∪（A ∩ C)，A ∪（B ∩C) ＝（A ∪ B) ∩ （A ∪ C)二、关系关系是集合元素之间的某种联系。

例 2：设集合 A ＝｛1, 2, 3}，R 是 A 上的关系，R ＝｛（1, 1)，（1, 2)，（2, 2)，（2, 3)，（3, 3)｝，判断 R 是否具有自反性、对称性和传递性。

解：R 具有自反性，因为对于 A 中的每个元素 a，都有（a, a) ∈ R；R 不具有对称性，因为（1, 2) ∈ R 但（2, 1) ∉ R；R 具有传递性，因为（1, 2) ∈ R 且（2, 3) ∈ R ，同时（1, 3) ∈ R 。

知识点：1、自反关系：对于集合中的每个元素 a，都有（a, a) ∈ R 。

2、对称关系：若（a, b) ∈ R ，则（b, a) ∈ R 。

3、传递关系：若（a, b) ∈ R 且（b, c) ∈ R ，则（a, c) ∈ R 。

三、函数函数是一种特殊的关系。

例 3：设函数f: R → R ，f(x) ＝ x^2 ，求 f(－2)，f(0)，f(3)。

离散数学知识点全归纳离散数学是数学的一个分支，研究的是离散对象和离散结构。

在计算机科学、信息技术以及其他领域中，离散数学具有重要的应用价值。

以下是离散数学的一些重要知识点的全面总结。

1. 集合论和逻辑- 集合：基本概念、运算、包含关系、并集、交集、差集、幂集等。

- 命题逻辑：命题、命题的连接词、真值表、逻辑等价、析取范式、合取范式等。

- 谓词逻辑：谓词、量词、逻辑推理、存在量词和全称量词等。

2. 证明方法- 直接证明：利用已知事实和逻辑推理，直接得出结论。

- 对证法：从假设的反面出发，利用矛盾推理得出结论。

- 数学归纳法：证明基础情况成立，再证明递推步骤成立。

3. 图论- 图的基本概念：顶点、边、路径、回路、度、连通性等。

- 图的表示：邻接矩阵、邻接表等。

- 最短路径：Dijkstra算法、Floyd-Warshall算法等。

- 最小生成树：Prim算法、Kruskal算法等。

4. 关系与函数- 关系及其性质：自反性、对称性、传递性、等价关系等。

- 函数及其性质：定义域、值域、单射、满射、双射等。

- 逆函数和复合函数：求逆函数、复合函数的定义和性质。

5. 组合数学- 排列和组合：排列、组合的计算公式和性质。

- 递归关系：递推公式、递归算法等。

- 图的着色：色数、四色定理等。

6. 代数系统- 半群、幺半群、群、环、整环和域的定义和性质。

- 同态：同态映射、同构等。

- 应用：编码理论、密码学等。

以上是离散数学的一些重要知识点的概括。

深入理解和掌握这些知识，对于解决实际问题和在相关领域中取得成功非常重要。

在学习过程中，建议结合实际例子和习题进行练习，加深对知识的理解和应用能力。

离散数学方世昌课后习题答案
《离散数学方世昌课后习题答案》
离散数学是计算机科学和数学中非常重要的一个分支，它研究的是离散的数学
结构和离散的数学对象。

方世昌老师的离散数学课程是非常受欢迎的，他的课
后习题也备受学生关注。

在这篇文章中，我们将为大家提供一些方世昌老师离
散数学课后习题的答案，希望能够对大家的学习有所帮助。

1. 证明：如果一个图G有一个奇数度的顶点，那么G一定有偶数个奇数度的顶点。

解答：首先，我们知道一个图中所有顶点的度数之和等于图中边的数量的两倍。

而奇数度的顶点的个数一定是偶数个，因为如果奇数度的顶点的个数是奇数个，那么所有顶点的度数之和就是奇数，与实际情况不符。

因此，如果一个图G有
一个奇数度的顶点，那么G一定有偶数个奇数度的顶点。

2. 证明：如果一个图G有n个顶点，每个顶点的度数都不小于n/2，那么G一
定是连通图。

解答：假设G不是连通图，那么G一定是由两个或多个连通子图组成的。

而每
个连通子图中的顶点个数一定小于n，因此每个连通子图中的顶点的度数一定
小于n/2。

这与题目中所给条件矛盾，因此G一定是连通图。

以上是方世昌老师离散数学课后习题的部分答案，希望能够对大家的学习有所
帮助。

离散数学是一门非常重要的课程，希朩大家能够认真学习，掌握其中的
知识。

《失散数学》期末复习概要《失散数学》是中央电大“数学与数学应用专业”（本科）的一门选修课。

该课程使用新的教课纲领，在原有失散数学课程的基础上减少了教课内容（主假如群与环、格与布尔代数这两章及图论的后三节内容），使用的教材为中央电大第一版的《失散数学》（刘叙华等编）和《失散数学学习指导书》（虞恩蔚等编）。

失散数学主要研究失散量构造及互相关系，使学生获得优秀的数学训练，提升学生抽象思想和逻辑推理能力，为从事计算机的应用供给必需的描绘工具和理论基础。

其先修课程为：高等数学、线性代数；后续课程为：数据构造、数据库、操作系统、计算机网络等。

课程的主要内容1、会合论部分（会合的基本观点和运算、关系及其性质）；2、数理逻辑部分（命题逻辑、谓词逻辑）；3、图论部分（图的基本观点、树及其性质）。

学习建议失散数学是理论性较强的学科，学习失散数学的要点是对失散数学（会合论、数理逻辑和图论）相关基本观点的正确掌握，对基来源理及基本运算的运用，并要多做练习。

教课要求的层次各章教课要求的层次为认识、理解和掌握。

认识即能正确鉴别相关观点和方法；理解是能正确表达相关观点和方法的含义；掌握是在理解的基础上加以灵巧应用。

一、各章复习要求与要点第一章集合[复习知识点]1、会合、元素、会合的表示方法、子集、空集、全集、会合的包含、相等、幂集2、会合的交、并、差、补等运算及其运算律（互换律、联合律、分派律、汲取律、DeMorgan律等），文氏（Venn）图3、序偶与迪卡尔积本章要点内容：会合的观点、会合的运算性质、会合恒等式的证明[复习要求]11、理解会合、元素、子集、空集、全集、会合的包含、相等、幂集等基本观点。

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

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

4、认识序偶与迪卡尔积的观点，掌握迪卡尔积的运算。

[本章要点习题]P5~6，4、6；P14~15，3、6、7；P20，5、7。

《离散数学》期末考试复习要点（长期有效）第一章命题逻辑1-1 ：命题、原子命题、复合命题、命题常量、命题变元1-2 ：联结词否定、和取、析取、条件、双条件1-1,1-2习题（1）（3）（5）（6）1-3：翻译例题3---例题61-3 习题（1）（5）(7)1-4: 真值表，等价公式例题1—例题61-4 习题（1）1-5 所有知识，表1-5.21-5 习题（1）（6）（7）1-7：合取范式、吸取范式、小项、大项及其性质、主析取范式及其简洁式、主合取范式及其简洁式、命题公式的成真赋值例题6---例题111-7习题（4）1-8：论证过程三种方法--真值表法、直接证法、间接证法例题1（p42）例题2—例题6 表1-8.3和表1—8.41-8 习题（1）（3）（4）（5）第二章谓词逻辑2-1 ：所有知识2-2：所有知识2-1,2-2习题（1）（2）2-3 例题1—例题42-3 习题（4）2-4 所有知识2-4 习题（2）（3）2-5 所有知识2-5 习题（1）（2）2-6 所有知识例题1，例题22-7 全称指定、全称推广、存在指定、存在推广。

例题1—例题32-7 习题（1）a）b）（2）a)（3）第三章集合与关系3-1 所有知识3-1 习题（4）（6）（7）（9）3-2 所有知识3-2 习题（3）（6）3-4 序偶、定理3-4.1例题13-4 习题（1）（2）（3）d）e）3-5 关系的定义，空关系，全域关系，恒等关系，关系矩阵，关系图。

例题1-例题63-5 习题（1）（2）（7）3-6 所有知识例题1—例题53-6 习题（1）3-7 复合关系，逆关系，例题1—例题43-7 习题（1）3-8 关系的闭包的定义，会求三个闭包。

例题1—例题33-8 习题（1）（2）3-9 集合的划分和覆盖的定义3-9 习题（1）3-10 等价关系的定义，等价类的概念。

商集的概念。

例题1—例题3。

3-10 习题（2）（3）3-11 相容关系的概念，相容类，最大相容类。