1.设G有16条边，有三个四度顶点，四个三度顶点，其余顶点的度数都小于3，问G中至
少
有几个顶点？ 答：总度数=16*2=32
3*4+4*3=24 （32-24）/2=4 至少有 3+4+4=11
至少有11个顶点
2．设9阶无向图G中，每个顶点的度数不是5就是6，证明G中至少有5个六度定点或者
至少
有6个5度顶点
证明，因为： 4*6+5*5=24+25=49不可能，
所以当n6<4 时， n5>=6 满足条件 当 n6>=5时，满足条件
得证
3.空间不可能存在奇数个面而且每个面均有奇数条棱的多面体
答： 假如有 奇数个面 n 每个面都有奇数个棱mi(I=1,2,…n)， 那么 m1+m2+…+mn= D mi为奇数，n奇数，所以D为奇数
但对于上式来说，每条棱都记了两次，那么 D=2*(总棱数) 为偶数 矛盾
所以空间不可能存在奇数个面而且每个面均有奇数条棱的多面体
4.在一次象旗比赛中，任意两个选手之间至多只下一盘棋，又每个人至少下一盘，证明总 能找到两名选手，他们下过的盘数是相同的
证明：建一个图的模型：每个选手相当于图的顶点，选手下的盘数相当于顶点得度数，两
个选手的对局相当于两个顶点的边，已知 顶点的度数是 1----n-1, 选手有n个，根据鸽
巢原理
可知，比存在两个顶点的度数相同，也就是总能找到两名选手，他们下过的盘数是相同的 。
5.设n阶无向简单图G为3次图(3-正则图)，边数m和n满足以下关系2n-3=m
问G有几种非同构的情况？并证明你的结论
解：3n=2m 2n-3=m => n=6 m=9 所以G是6阶 3正则图.设G1，G2均为无向简单图，G1同构于 G2 等价于 G1的补图
同构
于G2的补图。所以可知 有两种同构的情况
6．下面给出的两个整数列，哪个是可图化的，对于可图化的请至少给出三个非同构的图 1） d=(1,2,2,4,4,5) 可图化
第一节 等值式 例6、求命题公式 的主析取范式，主合取范式，成真赋值和成假赋值。 解：先求主析取范式 故主合取范式为 例6、求命题公式 的主析取范式，主合取范式，成真赋值和成假赋值。 解：成真赋值为极小项角码对应的二进制数， 即00，10，11。 成假赋值为极大项角码对应的二进制数， 即01。 例7、设 (1) 求 的真值表。 (2) 求 的主析取范式、主合取范式。 解： 例7、设 (2) 求 的主析取范式、主合取范式。 解： 例7、设 (2) 求
的主析取范式、主合取范式。 解： 例8、判断下列推理是否正确。
解：可用多种方法(如真值表法，等值演算法， 主范式法)验证， 并非重言式， 故推理不正确。 (1) 前提： 结论： ， 例8、判断下列推理是否正确。 (2) 如果今天是星期二，则
name=baidusnap0>明天是星期四。 今天是星期二，所以明天是星期四。 以上推理即假言推理，所以是正确的。 解： ：明天是星期四， ：今天是星期二， 前提： 结论： ， 例9、写出对应下面推理的证明。 有红、黄、蓝、白四队参加足球联赛。如果红队第三，则当黄队第二时，蓝队第四；或者白队不是第一，或者红队第三；事实上，黄队第二。因此，如果白队第一，那么蓝队第四。 证明：设 ：红队第三， ：黄队第二， ：蓝队第四， ：白队第一。 前提： 结论： 前提： 结论： 前提引入 附加前提引入 ①②析取三段论 前提引入 ④ ① ③ ② ⑤ ③④假言推理
前提： 结论： ③④假言推理 前提引入 ⑤⑥假言推理 ⑤ ⑦ ⑥ 由附加前提证明法知推理正确。 例10、一公安人员审查一件盗窃案，已知的事实如下： (1) 甲或乙盗窃了录音机； (2) 若甲盗窃了录音机，则作案时间不能 发生在午夜前； (3) 若乙的证词正确，则午夜时屋里灯光未灭； (4) 若乙的证词不正确，则作案时间发生在午夜之前； (5) 午夜时屋里灯光灭了。 问是谁盗窃了录音机。 ：乙盗窃了录音机， ：作案时间发生在午夜前， ：乙的证词正确， ：午夜灯光未灭。 解：设 ：甲盗窃了录音机， 前提： ， ， ， ，
离散数学求等价类例题
在离散数学中，等价关系是一种非常重要的关系。等价关系描述了两个对象之间的某种关系，使得它们可以被分类到同一个等价类中。在这里，我们将讨论一个求等价类的例题。
假设我们有一个集合S={1,2,3,4,5,6,7,8,9,10,11,12}，并且我们定义了一个关系R，如果两个元素的差是3的倍数，则它们在R下是等价的。
现在我们的任务是找出所有在R下等价的元素，并将它们分别放在它们自己的等价类中。
首先，我们可以列出所有的可能的元素对。这样做可以帮助我们更好地理解哪些元素在R下是等价的。
我们可以使用以下步骤来找到所有的等价类：
1. 将每个元素放在它自己的等价类中。
2. 对于每个等价类中的元素，找到与它等价的所有元素。如果有一个元素与该等价类中的元素等价，则将其添加到该等价类中。
3. 重复步骤2，直到没有新的元素可以添加到任何等价类中。
在这个例子中，我们可以得到以下等价类：
{1,4,7,10}
{2,5,8,11}
{3,6,9,12}
这些等价类中的元素在R下是等价的。我们可以看到，其中的每个等价类都包含了与其内部元素等价的所有元素。
通过这个例题，我们可以更好地理解等价关系和等价类的概念。它们在离散数学中有着广泛的应用，对于我们理解和解决许多问题都是非常重要的。
《离散数学(第三版)》方世昌的期末复习知识点总结含例题(word版可编辑修改)
1《离散数学(第三版)》方世昌的期末复习知识点总结含例题(word版可编辑修
改)
编辑整理：
尊敬的读者朋友们：
这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对
文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（《离散数学(第三版)》方世昌
的期末复习知识点总结含例题(word版可编辑修改)）的内容能够给您的工作和学习带来便利。同
时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。
本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快 业绩进步，以
下为《离散数学(第三版)》方世昌的期末复习知识点总结含例题(word版可编辑修改)的全部内容。《离散数学(第三版)》方世昌的期末复习知识点总结含例题(word版可编辑修改)
2《离散数学（第三版）》方世昌 的期末复习知识点总结含例题
一、各章复习要求与重点
第一章 集 合
［复习知识点］
1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集
2、集合的交、并、差、补等运算及其运算律(交换律、结合律、分配律、吸收律、 De
Morgan律等）,文氏（Venn）图
3、序偶与迪卡尔积
本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明
［复习要求］
1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。
2、掌握集合的表示法和集合的交、并、差、补等基本运算。
3、掌握集合运算基本规律，证明集合等式的方法。
4、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。
[疑难解析]
1、集合的概念
因为集合的概念学生在中学阶段已经学过，这里只多了一个幂集概念，重点对幂集加以掌
握，一是掌握幂集的构成，一是掌握幂集元数为2n。
2、集合恒等式的证明
通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命
