离散数学复习纲要

离散数学复习纲要等值演算主析取范式推理理论一阶逻辑公式及解释一阶逻辑等值式集合的基本计算集合中元素的计数第七章无向图及有向图最短路径及关键路径第八章二部图欧拉图哈密顿图平面图第九章无向树及生成树第十章加法法则和乘法法则基本排列组合的计数方法考试题型:一、选择题：1.下列语句为命题的是（c）。A．勿踏草地；。B．你去图书馆吗？；C．月球上有水；D．本命题为假。2.下列推理中，（d）是错误的。A.如果x是有理数，则它为整数。1/2是有理数。所以1/2是整数。B.若周末气温超过30度，小红就去游泳。小红周末没去游泳。所以周末气温没超过30度。C.下午小明或者去看电影，或者去打篮球。下午小明没去打篮球。因此下午小明去看电影了。D.若a能被4整除，则a能被2整除。a能被2整除。因此a能被4整除。3．谓词公式中的x(

d

)。

A．只是约束变元

B．只是自由变元

C．既非约束变元又非自由变元

D．既是约束变元又是自由变元

4.下面等值式中，（c）是不正确的。A.B.C.D.5．下列各有向图是强连通图的是（d）6.树T中有3个3度顶点，2个2度顶点,其余顶点都是树叶，则T中树叶片数为（c）A．1B．4C．5D．67.命题公式¬(p→q)ÙqÙr的类型是（d）A．重言式．B．非重言式的可满足式．C．简单合取式．D．矛盾式．二、简答题：1.设A=，求A的幂集P(A)。解P(A)={,{a},{b},{a.b}}2.树T有2个4度顶点，2个3度顶点，其余顶点全是树叶。问T有几片树叶？解、设T有x片树叶,n个顶点，m条边n=2+2+x，m=n-1=4+x-1，由握手定理2´(4+x-1)=2´4+2´3+x×1解得x=8，故T有8片树叶.3.利用等值演算方法求命题公式(pq)(qp)的主合取范式；利用该主合取范式求公式的主析取范式，并指出该公式的成真赋值和成假赋值．解:(pq)(qp)(pq)(qp)(pq)(qp)(pqp)(qqp)qppqM1此为公式的主合取范式．该公式的主析取范式是m0m2m3．公式的成真赋值为00，10，11．公式的成假赋值为01．4.利用等值演算法求公式Ø(r®p)Ú(qÙ(pÚr))的主析取范式，并给出其成真赋值．解:Ø(r®p)Ú(qÙ(pÚr))ÛØ(ØrÚp)Ú(qÙp)Ú(qÙr)Û(ØpÙr)Ú(pÙq)Ú(qÙr)Û((ØpÙr)Ù(ØqÚq))Ú((pÙq)Ù(ØrÚr))Ú((qÙr)Ù(ØpÚp))Û(ØpÙØqÙr)Ú(ØpÙqÙr)Ú(pÙqÙØr)Ú(pÙqÙr)Ûm1Úm3Úm此为公式的主析取范式．公式的成真赋值为001、011、110和111．5.75个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都乘过，其中55人至少乘坐过其中的两种。若每样乘坐一次的费用是0.5元，公园游乐场总共收入70元，求有多少儿童没有乘坐过其中任何一种。解设、、分别表示骑旋转木马、坐滑行铁道、乘宇宙飞船的儿童组成的集合，|∩∩|＝20，|∩|＋|∩|＋|∩|－2|∩∩|＝55，||＋||＋||＝70/0.5＝140。由容斥原理，得|∪∪|＝||＋||＋||―|∩|―|∩|―|∩|＋|∩∩|所以|∩∩|＝75－|∪∪|＝75－(||＋||＋||)＋(|∩|＋|∩|＋|∩|－2|∩∩|)＋|∩∩|＝75－140＋55＋20＝10没有乘坐过其中任何一种的儿童共10人。6.某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。解设A、B、C分别表示会打排球、网球和篮球的学生集合。则：|A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。因为|(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，＝25－20＝5。故，不会打这三种球的共5人。7.判断下图是否为欧拉图，若是，请给出一欧拉回路（用阿拉伯数字在边上标明顺序即可）；若不是，请说明原因；（4分）答：因为该图是连通图且图中没有奇度顶点，所以该图是欧拉图(只要判断正确给2分)。欧拉回路标序如下图：８１２８１２３４５６７９10111213314找的欧拉回路正确再2分8.如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。（９分）解：用Prim算法求产生的最优树。算法略。结果如图：树权C(T)=23+1+4+9+3+17=57即为总造价。9.设图中所示赋权图表示某7个城市及预先测算出它们之间的一些直接通信线路的造价，试给出一个设计方案，使得各城市间能够通信，而又使总造价最小。要求画出其最小生成树及最小生成树的补图，并计算出其最小总造价。解该问题是求最小生成树问题。图的最小生成树即为所求的通信线路图设计方案。其权即是小总造价为1+3+4+8+9+23=48三、证明题：1.在一阶逻辑中构造下面推理的证明前提：x(F(x)G(x))，x(F(x)H(x))结论：x(F(x)ÙG(x)ÙH(x))x(F(x)H(x))前提引入x(F(x)H(x))(1)置换(F(c)H(c))(2)EI规则F(c)H(c)(3)置换F(c)(4)化简x(F(x)G(x))前提引入F(c)G(c))(7)UI规则G(c)(5)(8)假言推理F(c)G(c)H(c)(4)(8)合取x(F(x)ÙG(x)ÙH(x))(9)EG规则2.在命题逻辑的自然推理系统中构造下面推理的证明。前提：┒(P∧┒Q)，┒Q∨R，┒R结论：┒P证明:（1）前提引入（2）前提引入（3）（1）（2）析取三段论（4）前提引入（5）置换(6)(3)(5)析取三段论3.在一阶逻辑中构造下面推理的证明：前提：x(H(x)ÙD(x)S(x))，x(H(x)(S(x)ÚF(x)))，x(H(x)ÙF(x))结论：x(H(x)ÙD(x))．(1)x(H(x)ÙF(x))前提引入(2)H(a)F(a))EI规则(3)H(a)(2)化简(4)F(a)(2)化简(5)x(H(x)(S(x)ÚF(x)))前提引入(6)H(a)(S(a)ÚF(a))，UI规则(7)S(a)ÚF(a)(3)(6)假言推理(8)S(a)(4)(7)析取三段论(9)x(H(x)ÙD(x)S(x))前提引入(10)H(a)ÙD(a)S(a)UI规则(11)(H(a)ÙD(a))(8)(10)拒取式(12)H(a)D(a)(11)置换(13)D(a)(3)(12)析取三段论(14)H(a)D(a)(3)(13)合取(15)x(H(x)ÙD(x))EG规则五、应用题：ccbfgdea1.今有a，b，c，d，e，f和g七人，已知a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲德语和意大利语；f会讲法语、日语和俄语；g会讲法语和德语，试问：如何将这七个人安排围坐在一张圆桌上，使得每个人都可和他身边的人交谈．以a，b，c，d，e，f和g七人为顶