离散数学期末复习

1、离散数学内容总结第一篇数理逻辑第1章命题逻辑求命题公式的主析取范式及主合取范式.例求(p,q)r),p的主析取范式及主合取范式。例求(PQ)R的主析取范式及主合取范式。例求命题公式(PQ),R的主析取范式和主合取范式。例求公式的主析取范式与主合取范式。例求(pq)r的主析取范式。判断公式类型例用等值演算法判断公式q(pq)的类型例判断下列命题公式的类型(永真式、永假式、可满足式)，方法不限。iriTK、4下)飞)aft)证明例证明：(p,q)ro(pr)(qr)例证明：p(qr)o(pq)r例推证：QA(P-Q)P例前提：pr,qs,p,q，结论：r,s。该结论是否有效？请说明原因。在命题逻辑

2、中构造下面推理的证明：例如果小张守第一垒并且小李向B队投球，则A队获胜。或者A队未获胜，或者A队成为联赛的第一名。小张守第一垒。A队没有成为联赛的第一名。因此小李没有向B队投球。解：先将简单命题符号化。P：小张守第一垒；Q：小李向B队投球；R：A队取胜；S：A队成为联赛第一名。前提：(PAQ)fR,RVS,P,S结论：Q证明：(1)RVS前提引入S前提引入(3)R(1)(2)析取三段论(4)(PAQ)-R前提引入(5)(PAQ)(3)(4)拒取式(6)PVQ(5)置换(7)P前提引入(8)Q(6)(7)析取三段论例一个公安人员审查一件盗窃案,已知下列事实：甲或乙盗窃了录像机；若甲盗窃了录像机,

3、则作案时间不能发生在午夜前；若乙的证词正确,则午夜时屋里灯光未灭；若乙的证词不正确,则作案时间发生在午夜前；午夜时屋里灯光灭了。根据以上事实,推断谁是盗窃犯。(在命题逻辑中构造推理证明。)解：分析如下。首先将元素符号化：P：甲偷了录像机；Q：乙偷了录像机；R：作案时间在午夜；S：乙的正词正确；T：午夜时灯光未灭。前提：PVQ,P-R,S-T,S-R,-T推演：(1)T前提引入(2S)-T前提引入(3)S拒(取1式)(2)(4)S-R前提引入(5)R假言推理(3)(4)(6P)-R前提引入(7)P拒(取5式)(6)(8P)VQ前提引入(9)Q析取三段论(7)(8)所以乙偷了录像机。例如果今天是周

4、一，则要进行离散数学或语言程序设计两门课中一门课的考试。如果语言程序设计课的老师有会，则不考语言程序设计。今天是周一，语言程序设计课的老师有会，所以进行离散数学课的考试。例若明天是星期一或星期三,我就有课。若有课,今天必须备课。我今天没备课。所以，明天不是星期一和星期三。解设明天是星期一明天是星期三，我有课，我备课前提Vff结论一1A-1证明rfs前提引入円前提引入円拒取式(Vpqf)r前提引入円P拒取式A置换结论有效,即明天不是星期一和星期三例若明天是周一或周二，小华就要考试。若要考试，今天必须复习。小华今天没复习。所以，明天不是周一和周二。(答案同上)例如果A工作努力，B或C将生活愉快。如

5、果B生活愉快，那么A将不努力工作。如果D愉快，则C将不愉快。所以，如果A工作努力，D将不愉快。第2章谓词逻辑求谓词公式的前束范式例求谓词公式,xP(x)TxQ(x)的前束范式解o,xF(x)TyG(y)换名规则oxy(F(x)TG(y)量词辖域扩张例求公式VxF(x)A3xG(x)的前束范式。解：VxF(x)A3xG(x)oVxF(x)AVxG(x)(*量词否定等值式3xP(x)oVxP(x)*)oVx(F(x)AG(x)(*量词分配等值式Vx(A(x)AB(x)oVxA(x)AVxB(x)*)证明例证明：一1Ao,fx在一阶逻辑中符号化下述命题，并推证之。.例凡人必有一死，苏格拉底是人，所以

6、苏格拉底会死的。解令F是人是要死的苏格拉底前提国x(结论证明国前提引入()x)前提引入T假言推理凡人都会犯错，小王是人，所以小王会犯错。所有三角形其内角和为180度。AABC是三角形。所以ABC内角和为180度。所有的有理数均可以表示成分数。0.3是有理数。所以0.3可以表示成分数。偶数都可以被2整除，6是偶数。所以6可以被2整除。哲学家都善于思考。柏拉图是哲学家。所以，柏拉图善于思考。例东北人都不怕冷，王国端怕冷。所以王国端不是东北人。解设是东北人怕冷王国端前提T,结论，证明国前提引入,t前提引入，T规则，拒取非洲人都不怕热，玛丽怕热。所以玛丽不是非洲人。凡奇数均不能被2整除，8能被2整除。

7、所以8不是奇数。凡奇数均不能被2整除，36能被2整除。所以36不是奇数。英语系学生都不学离散数学，小刘学离散数学。因此，小刘不是英语系学生。海南人都不怕热，小赵怕热。所以小赵不是海南人。无理数都不能表示成分数，3.1415能表示成分数。所以3.1415不是无理数。例鸟都会飞，麻雀是鸟，所以麻雀会飞。证明：令F(x)：x是鸟，G(x)：x会飞，M(x)：x是麻雀，前提：Vx(F(x)G(x),Vx(M(x)F(x)结论：Vx(M(x)TG(x)推演：Vx(F(x)Vx(F(x)G(x)Vx(M(x)F(x)F(x)G(x)M(x)F(x)M(x)G(x)前提引入前提引入UIUI(4)假言三段论V

8、x(M(x)G(x)(5)UG(注意：“麻雀”不是个体，而是类属，故不能令a：麻雀)例乌鸦都不是白色的，北京鸭是白色的。因此，北京鸭不是乌鸦第二篇集合论第3章集合计算例设A=1,2,3,B=2,3,4,5,Z=2,3,求(AB)例设A=a,b,c,c,a,b,B=a,b,b,计算(l)AAB,(2)AB,(3)P(B)集合恒等式的证明例设A、B、C是三个集合，证明：AB(BA)例设A、B、C是三个集合，证明：A(BC)=(AB)C例设A、B、C是三个集合，证明：Ac(bc)=(anB)(AcC)证明：nannAnCnn(AC)nnAnnCnnCn(nC)n()例设A、B、C是三个集合，证明：(

9、AB)(AC)(BnC)证明：n=nCn(CnBnCn例设A、B、C是任意三个集合，证明：(A(BC)nA)(B(BA)=A。例设A、B、C是任意三个集合，证明：(A(BC)nA)(B(BA)=A例设A，B，C为集合，证明：AG(BC)(A-C)n(BC)例已知AnBnc，且AnBAnc，证明bc证明：uAuA)AaA包含排斥原理(即容斥原理)的简单应用例假设某班有名学生，其中有人英语成绩为优，有人数学成绩为优，又知有6人英语和数学成绩都为优。问两门课都不为优的学生有几名？例有100名程序员，其中47名熟悉C+语言，35名熟悉JAVA语言，23名熟悉这两种语言。问有多少人对两种语言都不熟悉？例

10、在一个班级的50名学生中，有26人在第一次考试中得到A，21人在第二次考试中得到A，假如有17人两次考试都没得到A,问有多少学生两次考试都得到A？第4章关系第5章函数例设集合，上的关系和为：，求。解：R=vl,4,v2,3,v3,2,v4,lS=,RS=,例设A=0,l,2,3,A上的两个关系：R=(a,b)Ia=b+1或a=b/2，S=(a,b)Ib=a+2，求(1)R。S，(2)S。R。例设，上的关系二4，求。TOC o 1-5 h z例设，上的关系=，求。例设集合A=2,4,6,8,10,12,B=2,4,6，从A到B的关系R=|,求R和R-1例设集合日,，从至U的关系=,求例设,v2,

11、2,v2,3,v3,3R2=,，求，R1R2例R1=,R2=,求Ri求R2。R1R1是函数吗？例设，求，。例已知=a,b,c,d,e在上定义二元关系：,b,b,a,a,c,b,d,d,a,e,a,e,c()试画出的关系图；()求的自反闭包和对称闭包。例：1=1,2，,1,3，,2=2,32，,2，3,32，,3,，,：,v2,3,v3,4,求A,B,(2)AB,(3)，(4)R1。R2例设，是幕集上的包含关系，说明是偏序关系并画出的哈斯图。例求集合A=1,2,3的幕集，是幕集上的包含关系，说明是偏序关系并画出的哈斯图。例设，是上的整除关系，画出的哈斯图。例画出集合A=2,3,4,6,7,8,9

12、上整除关系的哈斯图。例设集合，R=,v5,5，试用关系图验证R是A上的等价关系。100例A=1,2,3,R为A上关系，关系矩阵为110,101(1)画出关系图。(2)求R。R,R-1。求r(R)，s(R)，t(R)；指出R具有的性质。(5)R是偏序关系吗？若是画出哈斯图。第三篇图论连通性判断，通路数的计算例有向图如下图所示：V4写出此图的邻接矩阵表示。（分至U长为的通中长为的通路共U自身长为的回路有多少条？（分）V4写出此图的邻接矩阵表示。（分至U长为的通中长为的通路共U自身长为的回路有多少条？（分）有多少条？少条？其中回路多少条？（分）是单向连通还是强连通？（单向连通）（分）长为的通路共有多

13、少条其中有多少条回路（分）TOC o 1-5 h zA4=3210110021104310通路有20条，5条回路例已知有向图G的邻接矩阵为0101，A0011A=11001110（1）画出图并说出此图有几条边。（2）v4到v2长为3的通路有多少条？v1到自身长为3的回路有多少条?（3）此图是强连通还是单向连通图？例G是具有四个节点的有向图，它的邻接矩阵表示如下0101、001101010100丿画此图并说明该图共有几条边？是单向连通还是强连通？分别求出从到长度小于的回路条数及从到、从到、到长度是的通路数。例已知有向图的邻接矩阵为0101001111001110()画出图并说出此图有几条边。()

14、至U、至U长为的通路有多少条？到自身长为的回路有多少条？(、)此图是强连通还是单向连通图？哈密尔顿图的充分条件及其简单应用.例一次会议有人参加，其中每个人都在其中有不下个朋友。这人围成一圆桌入席。有没有可能使任意相邻而坐的两个人都是朋友？为什么？计算例已知无向图有条边，度顶点有个，度、度、度顶点各个，其余顶点度数均为至求度顶点的个数。例一棵树有两个结点度数为、，一个结点度数为、，三个结点度数为至，其余结点度数均为至，问它有几个度数为至的结点？例已知无向树中，有个度顶点，个度顶点，其余顶点全是树叶。试求树叶数。例无向树T有片树叶，个度分支点，其余的分支点都是度顶点，问T有几个4度分支点？dd求最

15、优二元树及其权例求以为权的最优元树，要求写出步骤并计算它的权。例(1)求以2,3,5,7,8,9为权的最优2元树T，(2)求W(T),(3)求T的高度h(T),求T的树叶有多少？(5)求T的2度顶点，3度顶点，4度顶点各有多少？例给定权1，4，9，16，25，36，49，64，81，10，0构造一棵最优二叉树。利用最有二元树进行编码例设7个字母在通信中出现的频率如下:a:35%，b:20%，c:15%，d:10%，e:10%，f:5%，g:5%用Huffman算法求传输它们的前缀码.要求画出最优树，指出每个字母对应的编码。并指出传输10n(n$2)个按上述频率出现的字母，需要多少个二进制数字。例在通信中,设八进制数字出现的频率(%如)下:采用2元前缀码,求传输数字最少的2元前缀码(称作最佳前缀码),并求传输10个0按上述比例出现的八进制数字需要多少个二进制数字？若用等长的(长为3)的码字传输需要多少个二进制数字?(要求画出最优2元树)例设7个字母在通信中出现的频率如下：a:35%，b:20%，c:15%，d:10%，e:10%，f:5%，g:5%用Huffman算法求传输它们的前缀码.要求画出最优树，指出每个字母对应的编码。并指出传输10n(n$2)个按上述频率出现的字母，需要多少个二进制数字。第四篇代数系统例设为群，如果eg都有2证明：为群(即为交换群)。例设是任意集合