离散数学期末复习

离散数学内容总结第一篇数理逻辑第1章命题逻辑求命题公式的主析取范式及主合取范式例求的主析取范式及主合取范式。例求(P→Q)R的主析取范式及主合取范式。例求命题公式的主析取范式和主合取范式。例求公式A=(p®Øq)®r的主析取范式与主合取范式。例求的主析取范式。判断公式类型例用等值演算法判断公式qÙØ(p®q)的类型例判断下列命题公式的类型（永真式、永假式、可满足式）,方法不限。(1)(2)证明例证明:
例证明:
例推证:
Q∧(P→Q)

P例前提：
,结论：
。该结论是否有效？请说明原因。在命题逻辑中构造下面推理的证明:例如果小张守第一垒并且小李向B队投球,则A队获胜。或者A队未获胜,或者A队成为联赛的第一名。小张守第一垒。A队没有成为联赛的第一名。因此小李没有向B队投球。例一个公安人员审查一件盗窃案,已知下列事实：（1）甲或乙盗窃了录像机；（2）若甲盗窃了录像机,则作案时间不能发生在午夜前；（3）若乙的证词正确,则午夜时屋里灯光未灭；（4）若乙的证词不正确,则作案时间发生在午夜前；（5）午夜时屋里灯光灭了。根据以上事实,推断谁是盗窃犯。（在命题逻辑中构造推理证明。）例如果今天是周一,则要进行离散数学或C语言程序设计两门课中一门课的考试。如果C语言程序设计课的老师有会,则不考C语言程序设计。今天是周一,C语言程序设计课的老师有会,所以进行离散数学课的考试。例若明天是星期一或星期三,我就有课。若有课,今天必须备课。我今天没备课。所以,明天不是星期一和星期三。例若明天是周一或周二,小华就要考试。若要考试,今天必须复习。小华今天没复习。所以,明天不是周一和周二。例如果A工作努力,B或C将生活愉快。如果B生活愉快,那么A将不努力工作。如果D愉快,则C将不愉快。所以,如果A工作努力,D将不愉快。第2章谓词逻辑求谓词公式的前束范式例求谓词公式的前束范式例求公式∀xF(x)∧∃xG(x)的前束范式。证明例证明:﹁
x(A(x)∧B(x))

x(A(x)→﹁B(x))在一阶逻辑中符号化下述命题,并推证之。例凡人必有一死,苏格拉底是人,所以苏格拉底会死的。凡人都会犯错,小王是人,所以小王会犯错。所有三角形其内角和为180度。△ABC是三角形。所以△ABC内角和为180度。所有的有理数均可以表示成分数。0.3是有理数。所以0.3可以表示成分数。偶数都可以被2整除,6是偶数。所以6可以被2整除。哲学家都善于思考。柏拉图是哲学家。所以,柏拉图善于思考。例东北人都不怕冷,王国端怕冷。所以王国端不是东北人。非洲人都不怕热,玛丽怕热。所以玛丽不是非洲人。凡奇数均不能被2整除,8能被2整除。所以8不是奇数。凡奇数均不能被2整除,36能被2整除。所以36不是奇数。英语系学生都不学离散数学,小刘学离散数学。因此,小刘不是英语系学生。海南人都不怕热,小赵怕热。所以小赵不是海南人。无理数都不能表示成分数,3.1415能表示成分数。所以3.1415不是无理数。例鸟都会飞,麻雀是鸟,所以麻雀会飞。例乌鸦都不是白色的,北京鸭是白色的。因此,北京鸭不是乌鸦。第二篇集合论第3章集合计算例设.例设A={{a,{b}},c,{c},{a,b}},B={{a,b},{b}},计算(1)A∩B,(2)A⊕B,(3)P(B)集合恒等式的证明例设A.B.C是三个集合,证明:A
B=A
(B-A)例设A.B.C是三个集合,证明:A－(B
C)＝(A－B)－C例设A.B.C是三个集合,证明:A
(B－C)＝(A
B)－(A
C)例设A、B、C是三个集合,证明:(A－B)
(A－C)=A－(B
C)例设A、B、C是任意三个集合,证明：((A(B－C))A)(B－(B－A))＝A。例设A.B.C是任意三个集合,证明:((A
(B－C))
A)
(B－(B－A))＝A例设A,B,C为集合,证明:A∩(B－C)=(A－C)∩(B－C)例已知A∩B=A∩C,且
∩B=
∩C,证明B=C。包含排斥原理（即容斥原理）的简单应用例假设某班有20名学生,其中有10人英语成绩为优,有8人数学成绩为优,又知有6人英语和数学成绩都为优。问两门课都不为优的学生有几名？例有100名程序员,其中47名熟悉C++语言,35名熟悉JAVA语言,23名熟悉这两种语言。问有多少人对两种语言都不熟悉？例在一个班级的50名学生中,有26人在第一次考试中得到A,21人在第二次考试中得到A,假如有17人两次考试都没得到A,问有多少学生两次考试都得到A？第4章关系第5章函数例设集合A={1,2,3,4,5},A上的关系R和S为:R={<x,y>|x+y=5,x,y
A},S={<x,y>|x<y,x,y
A},求R
S。例设A={0,1,2,3},A上的两个关系:R={(a,b)︱a=b+1或a=b/2},S={(a,b)︱b=a+2},求(1)R
S,(2)S
R。例设B={1,2,3,4},B上的关系R＝{〈1,2〉,〈2,1〉,〈2,3〉,〈3,4〉｝,求(1)RR(2)R-1例设A={a,b,c,d},A上的关系R＝{<a,b>,<b,a>,<b,c>,<c,d>｝,求(1)R
R(2)R-1例设集合A＝{2,4,6,8,10,12},B={2,4,6},从A到B的关系R＝{<x,y>|x=2y},求R和R-1例设集合A＝｛1,2,3,4,5,6｝,B={1,2,3},从A到B的关系R＝｛〈x,y〉|x=2y｝,求(1)R,(2)R-1例设R1={<1,2>,<2,2>,<2,3>,<3,3>},R2={<2,2>,<2,3>,<3,4>},求(1)R1-1,(2)R1
R2例R1={<1,2>,<1,3>,<2,3>,<3,3>},R2={<2,2>,<2,3>,<3,4>},(1)求R1-1(2)求R2
R1(3)R1是函数吗？例设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求r(R),s(R),t(R)。例已知A＝{
},在A上定义二元关系R：R={}（1）试画出R的关系图；（2）求R的自反闭包和对称闭包。例R1={<1,2>,<1,3>,<2,3>,<3,3>},R2={<2,2>,<2,3>,<3,4>},(1)求R1-1(2)求R2
R1(3)R1是函数吗？例设集合A={a,b,c,},B={b,c,d},C={d,e,f},R1={<1,2>,<2,2>,<2,3>,<3,3>},R2={<2,2>,<2,3>,<3,4>},求(1)
,(2)A⊕B,(3)R1-1,(4)R1
R2例设A={a,b,c},R是A幂集上的包含关系,说明R是偏序关系并画出R的哈斯图。例求集合A={1,2,3}的幂集,R是A幂集上的包含关系,说明R是偏序关系并画出R的哈斯图。例设S={1,2,…,10},
是S上的整除关系,画出<S,
>的哈斯图。例画出集合A＝{2,3,4,6,7,8,9}上整除关系的哈斯图。例设集合A={0,1,2,3,4,5},R={<0,0>,<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>,<4,4>,<4,5>,<5,4>,<5,5>},试用关系图验证R是A上的等价关系。例A={1,2,3},R为A上关系,关系矩阵为
,(1)画出关系图。(2)求R
R,R-1。(3)求r(R),s(R),t(R)；(4)指出R具有的性质。(5)R是偏序关系吗？若是画出哈斯图。第三篇图论连通性判断,通路数的计算例有向图G如下图所示:(1)写出此图的邻接矩阵表示。（4分）(2)v1到v3长为3的通路有多少条？v1到自身长为3的回路有多少条？（4分）(3)G中长为3的通路共有多少条？其中回路多少条？（4分）例具有四个节点的有向图G如下图所示:写出此图的邻接矩阵。（3分）G是单向连通还是强连通？（3分）长为4的通路共有多少条?其中有多少条回路?（4分）例已知有向图G的邻接矩阵为A=（1）画出图并说出此图有几条边。（2）v4到v2长为3的通路有多少条？v1到自身长为3的回路有多少条？（3）此图是强连通还是单向连通图？例G是具有四个节点的有向图,它的邻接矩阵表示如下画此图并说明该图共有几条边？G是单向连通还是强连通？分别求出从v4到v4长度小于4的回路条数及从v1到v2.从v1到v3、v1到v4长度是3的通路数。例已知有向图G的邻接矩阵为A=（1）画出图G并说出此图有几条边。（2）v1到v3,v4到v2长为3的通路有多少条？v1到自身长为3的回路有多少条？（3）此图是强连通还是单向连通图？哈密尔顿图的充分条件及其简单应用例一次会议有10人参加,其中每个人都在其中有不下6个朋友。这10人围成一圆桌入席。有没有可能使任意相邻而坐的两个人都是朋友？为什么？计算例已知无向图G有12条边,1度顶点有2个,2度、3度、5度顶点各1个,其余顶点度数均为4,求4度顶点的个数。例一棵树有两个结点度数为2,一个结点度数为3,三个结点度数为4,其余结点度数均为1,问它有几个度数为1的结点？例已知无向树T中,有1个3度顶点,2个2度顶点,其余顶点全是树叶。试求树叶数。例无向树
有8片树叶,2个3度分支点,其余的分支点都是4度顶点,问
有几个4度分支点？求出下图的一棵最小生成树,并计算其权。12312345678910求最优二元树及其权例求以1,3,4,5,6为权的最优2元树,要求写出步骤并计算它的权。例(1)求以2,3,5,7,8,9为权的最优2元树
,(2)求
,（3)求
的高度
,(4)求
的树叶有多少？(5)求
的2度顶点,3度顶点,4度顶点各有多少？例给定权1,4,9,16,25,36,49,64,81,100,构造一棵最优二叉树。利用最优二元树进行编码例设7个字母在通信中出现的频率如下:a:35%,b:20%,c:15%,d:10%,e:10%,f:5%,g:5%用Huffman算法求传输它们的前缀码.要求画出最优树,指出每个字母对应的编码。并指出传输10n(n≥2)个按上述频率出现的字母,需要多少个二进制数字。例在通信中,设八进制数字出现的频率(%)如下:0:25,1:20,2:15,3:10,4:10,5:10,6:5,7:5采用2元前缀码,求传输数字最少的2元前缀码(称作最佳前缀码),并求传输100个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的(长为