第一篇：离散数学图论习题
第4章图论
综合练习
一、单项选择题
1．设L是n阶无向图G上的一条通路，则下面命题为假的是()．
(A)L可以不是简单路径，而是基本路径
(B)L可以既是简单路径,又是基本路径
(C)L可以既不是简单路径，又不是基本路径
(D)L可以是简单路径，而不是基本路径
答案：A
2．下列定义正确的是()．
(A)含平行边或环的图称为多重图(B)不含平行边或环的图称为简单图
(C)含平行边和环的图称为多重图(D)不含平行边和环的图称为简单图答案：D
3．以下结论正确是()．
(A)仅有一个孤立结点构成的图是零图
(B)无向完全图Kn每个结点的度数是n
(C)有n(n>1)个孤立结点构成的图是平凡图
(D)图中的基本回路都是简单回路
答案：D
4．下列数组中，不能构成无向图的度数列的数组是()．
(A)(1,1,1,2,3)(B)(1,2,3,4,5)(C)(2,2,2,2,2)(D)(1,3,3,3)
答案：B
5．下列数组能构成简单图的是()．
(A)(0,1,2,3)(B)(2,3,3,3)(C)(3,3,3,3)(D)(4,2,3,3)
答案：C
6．无向完全图K3的不同构的生成子图的个数为（）．
(A)6(B)5(C)4(D)
3答案：C
7．n阶无向完全图Kn中的边数为（）．(A)n(n1)n(n1)(B)(C)n(D)n(n+1)2
2答案：B
8．以下命题正确的是()．
(A)n(n1)阶完全图Kn都是欧拉图
(B)n(n1)阶完全图Kn都是哈密顿图
(C)连通且满足m=n－1的图
(D)n(n5)阶完全图Kn都是平面图
答案：C
10．下列结论不正确是()．
(A)无向连通图G是欧拉图的充分必要条件是G不含奇数度结点
(B)无向连通图G有欧拉路的充分必要条件是G最多有两个奇数度结点
(C)有向连通图D是欧拉图的充分必要条件是D的每个结点的入度等于出度
(D)有向连通图D有有向欧拉路的充分必要条件是除两个结点外，每个结点的入度等
1于出度 答案：D
11．无向完全图K4是（）．
（A）欧拉图（B）哈密顿图（C）树答案：B
12．有4个结点的非同构的无向树有()个．
(A)2(B)3(C)4(D)5 答案：A
13．设G是有n个结点，m条边的连通图，必须删去G的()条边，才能确定G的一棵生成树．
(A)mn1(B)nm(C)mn1(D)nm1 答案：A
14．设G是有6个结点的完全图，从G中删去()条边，则得到树．(A)6(B)9(C)10(D)15 答案：C
二、填空题
1．数组{1，2，3，4，4}是一个能构成无向简单图的度数序列，此命题的真值是.答案：0
2．无向完全图K3的所有非同构生成子图有个． 答案：
43．设图GV,E，其中Vn,Em．则图G是树当且仅当G是连通的，且m． 答案：n－
14．连通图G是欧拉图的充分必要条件是 答案：图G无奇数度结点
5．连通无向图G有6个顶点9条边，从G中删去G的一棵生成树T． 答案：4
6．无向图G为欧拉图，当且仅当G是连通的，且G中无 答案：奇数度
7．设图GV,E是简单图，若图中每对结点的度数之和，则G一定是哈密顿图． 答案：
8．如图1所示带权图中最小生成树的权是．
答案：1
2三、化简解答题
1．设无向图G＝
图
1图
2(2)写出结点v2, v4，v6的度数；(3)判断图G是简单图还是多重图．解：(1)图G的图形如图5所示．
(2)deg(v2)4,deg(v4)3,deg(v6)0．
(3)图G是多重图．作图如图2.2．设图G＝
V＝{a,b,c,d,e}, E={(a,b),(b,c),(c,d),(a,e)}
试作出图G的图形，并指出图G是简单图还是多
重图？是连通图吗？说明理由.be
解：图G如图8所示．.图G中既无环，也无平行边，是简单图． cd 图G是连通图．G中任意两点都连通.图
3所以，图G有9个结点．作图如图3．
四、计算题
1．设简单连通无向图G有12条边，G中有2个1度结点，2个2度结点，3个4度结点，其余结点度数为3．求G中有多少个结点．试作一个满足该条件的简单无向图．
解：设图G有x个结点，由握手定理
21+22+34+3（x223）＝12
23x24211827x＝9 故图G有9个结点． 图
4满足该条件的简单无向图如图4所示
2．设图G(如图5表示)是6个结点a,b,c, d,e,f的图，试求，图G的最小生成树，并计算它的权．
c 解：构造连通无圈的图，即最小生成树，用
克鲁斯克尔算法：
第一步： 取ab＝1；第二步： 取af=4第三步： 取fe＝3；第四步： 取ad=9图5第五步： 取bc=2
3如图6．权为1+4+3+9+23=40
3．一棵树T有两个2度顶点，1个3度顶点；3个4
问它有几片树叶？
解：设T有n顶点，则有n－1条边．T中有2个 2度顶点，1个3度顶点，3个4度顶点，其余n－2－1-3个1度顶
点．
由握手定理： 2·2+1·3+3·4+(n－2－1-3)=2(n－1)解得 n=15．于是T有15-6=9片树叶
五、证明题
1．若无向图G中只有两个奇数度结点，则这两个结点一定是连通的．
证：用反证法．设G中的两个奇数度结点分别为u和v．假若u和v不连通．
即它们之间无任何通路，则G至少有两个连通分支G1，G2，且u和v分别属于G1和G2，于是G1和G2各含有一个奇数度结点．这与握手定理的推论矛盾．因而u和v一定是连通的．
第二篇：《离散数学》图论部分习题
《离散数学》图论部分习题
1.已知无向图G有12条边，6个3度顶点，其余顶点的度数均小于3，问G至少有几个顶点？并画出满足条件的一个图形.（24-3*6）/2 +6=9 2.是否存在7阶无向简单图G，其度序列为1、3、3、4、6、6、7.给出相应证明.不存在；7阶无向简单图G中最大度≤6 3.设d1、d2、…、dn为n个互不相同的正整数.证明：不存在以d1、d2、…、dn为度序列的无向简单图.Max{d1，d2，…，dn}≥n，n阶无向简单图G中最大度≤n-1 4.求下图的补图.5.1)试画一个具有5个顶点的自补图
2)是否存在具有6个顶点的自补图，试说明理由。
对于n阶图，原图与其补图同构，边数应相等，均为(n*(n-1)/2)/2，即n*(n-1)/4且为整 数，n=4k或n=4k+1，不存在6阶自补图。
6.设图G为n(n>2且为奇数)阶无向简单图，证明：G与G的补图中奇度顶点个数相等.n(n>2且为奇数)，奇度点成对出现
7.无向图G中只有2个奇度顶点u和v，u与v是否一定连通.给出说明或证明。
只有2个奇度顶点u和v，如果不连通，在u和v在2个连通分支上，每个分支上仅有一个奇度顶点，与握手引理相矛盾。
8.图G如下图所示：
1)写出上图的一个生成子图.2)δ(G)，κ(G)，λ(G).δ(G)=2，κ(G)=1，λ(G)=2.说明：δ(G)=min{ d(v)| vV } ；κ(G)=min{ |V’| |V’是图G的点割集} ； λ(G)=min{ |E’| |E’是图G的边割集} 9.在什么条件下无向完全图Kn为欧拉图？
n为奇数时
10.证明：有桥的图不是欧拉图.假设是欧拉图：桥的端点是u和v，并且图各顶点度均为偶数； 桥为割边，删除桥，图不再连通，u和v应该在2各不同的连通分支上；且u和v度数变为奇数；由于其他顶点度数均为偶数，则u和v所在的连通分支上只有一个奇度顶点，与握手引理矛盾。
11.证明：有桥的图不是哈密尔顿图.若G是K2，显然不是哈密尔顿图；
否则n≥3，则桥的两个端点u和v至少有一个不是悬挂顶点（容易证明悬挂顶点不是割点）；设u不是悬挂点，则u是割点，存在割点显然不是哈密尔顿图。
12.树T有2个4度顶点，3个3度顶点，其余顶点全为树叶，问T有几片树叶？
X+2*4+3*3=2*（2+3+x-1）
x=9 13.证明：最大度Δ（T）≥k的树T至少有k片树叶。
设有n个顶点，其中x片树叶
2*（n-1）≥1*K+（n-x-1）*2+x*1
x≥k 14.已知具有3个连通分支的平面图G有4个面，9条边，求G的阶数.n-9+4=3+1
n=9
15.给出全部互不同构的4阶简单无向图的平面图形。
16.如果G是平面图, 有n个顶点、m条边、f个面，G有k个连通分支。试利用欧拉公式证明:：n-m+f=k+1.
第三篇：离散数学习题
集合论
1.A={,1}，B={{a}}求A的幂集、A×B、A∪B、A+B。2.A={1,2,3,4,5}, R={(x,y)|x 4.A={a,b,c},R= IA ∪{(a,b),(b,a)}，求a和b关于R的等价类。 5.R是A上的等价关系，A/R={{1,2}，{3}},求A，R。6.请分别判断以下结论是否一定成立，如果一定成立请证明，否则请举出反例。 ①如果A∪BC，则AC或者BC。②如果A×B=A×C且A，则B=C。 27.如果R是A上的等价关系，R,r(R)是否一定是A上的等价关系？证明或举例。 8.已知A∩CB∩C,A-CB-C,证明：AB。9.证明：AX(B∩C)=(AXB)∩(AXC)10.证明：P(A)∪P(B)P(A∪B)-111.证明：R[sym] iff R=R -1212.证明：r(R)=R∪IA,S(R)=R∪R,t(R)=R∪R∪...13.证明：s(R∪S)=s(R)∪s(S)14.R是A上的关系，证明：如果R是对称的，则r(R)也是对称的。 15.I是整数集，R={(x,y)|x-y是3的倍数}，证明：R是I上的等价关系。 16.如果R是A上的等价关系，则A/R一定是A的划分。17.R是集合A上的自反关系，S是A上的自反和对称关系，证明t(R∪S)是A上的等价关系。18.I是正整数集合，R是I×I上的二元关系，R={< 19.f:AB，R是B上的等价关系，令S={ 20.R是集合A上的自反关系，S是A上的自反和对称关系，证明t(R∪S)是A上的等价关系。 21.P和Q都是集合A上的划分，请问P∪Q，P-Q是否是A上的划分，22.RAXA,R[irref]且R[tra],证明：r(R)是A上的偏序关系。 23.画出{1,2,3,4,6}上整除关系的哈斯图，求{2,3,6}的4种元素。 24.A={a,b,c,d,e,f,g},R={(a,c),(a,e),(b,d),(b,f),(d,e),(d,f)},S=tr(R),画出S的哈斯图并求{b,c,d,f}的极大元等8种元素。 25.f:A→B,g:B→C都是单（满）射，证明：复合映射gof一定是单（满）射。 26.f:A→B,g:B→C，gof是单射，请问f和g是否一定是单射？请证明或举出反例。27.R是实数集，f:R×RR×R,f( 代数系统 1. 2.求 3.R是实数集，在R上定义运算*为x*y=x+y+xy,问： 5.R是实数集，R上的6运算定义如下：对R中元素x,y，f1( 6. 7.证明：如果群G中每个元素的逆元素都是它自已，则G是交换群。 8.循环群一定是交换群。 9.证明：阶为素数的群一定是循环群。 -110. 11.整数集Z上定义运算*：对任意整数x和y,x*y=x+y-4,其中+，-为普通加减法。证明： 12.证明：如果群G中至少有两个元素，则群中没有零元。13.S是G的子群，证明：{x|x是S的左陪集}是G的一个划分 14. 15.H，K都是群G的子群，请问H∩K,H∪K,H-K是否一定是G的子群？ 16.H，K是G的两个子群，aG, 试证：aHaK当且仅当HK。17.G={1,3,4,5,9},*是模11的乘法(即x*y=xy mod 11)，请问(G,*)是否构成群？ n18. 19.S是G的子群，证明：{x|x是S的左陪集}是G的一个划分 20.G是群，证明：S={aG|xG(ax=xa)},则S是G的子群。21. ++23.R为实数集，R为正实数集， 1.如何判断二部图？完全图、完全二部图的边数。2.如何求E回路？ 3.Petersen图是否为E图或H图。 4.哪些完全图是H图？哪些完全图是E图？ 5.n为何值时轮图为H图？ 6.如何求最小生成树。 7.证明：奇数个顶点的二部图（两步图）不是哈密尔顿图。8.证明：如果G是欧拉图，则其边图L(G)也是欧拉图。9.证明：奇数个顶点的二部图（两步图）不是哈密尔顿图。10.G是平面图，G有m条边，n个顶点，证明：m3n-6。并由此证明K5不是平面图。 11.证明：有6个顶点的简单无向图G和它的补图中至少有一个三角形。 12.证明：在至少有两个顶点的无向树中，至少有2个一度顶点。 13.G是无向简单连通图，G有n个顶点，则G最少有几条边，最多有几条边？ 14.证明：简单无向图G和它的补图中至少有一个是连通图。15.证明：无向图中奇度点（度数为奇数的点）有偶数个。16.证明：n个顶点的无向连通图至少有n-1条边。17.G是H图，V是G的顶点集，证明：对任意顶点集S，SV，都有ω（G-S）≤|S|。其中ω（G-S）表示G-S的分图数目。18.一棵无向树有3个3次点，1个顶点次数为2，其余顶点次数为1，问它有几个次数为1的顶点？写出求解过程。19.证明：每个简单平面图都包含一个次至多为5的顶点。20.连通平面图G有n个顶点，m条边和f个面，证明：n-m+f=2。21.如果图G的最大顶点次数≤ρ，证明：G是ρ+1可点着色的。 22.G是无向简单连通图，G有n个顶点，则G最少有几条边，最多有几条边？ 23.如果一个简单图G和它的补图同构，则称G是自补图，求所有4个顶点自补图。 24.G是平面图，G有m条边，n个顶点，证明：m3n-6。如果G中无三角形，则m2n-4。数理逻辑 1.如果今天是星期一，则要进行英语或数理逻辑考试。 没有不犯错误的人。整数都是有理数。有的有理数不是整数。 不存在最大的整数。有且只有一个偶数是素数。2.求真值表及范式：P(┓QR)、(┓QR)(PR)3.推理： p(qr)，┓s∨p，q ├ sr pr，qs，p∨q ├ r∨s p∨q，p┓r，st，┓sr，┓t ├ q p(┓(r∧s)┓q),p,┓s ├ ┓q 4.如果小王是理科学生，他一定会学好数学。如果小王不是文科学生，他一定是理科学生。小王没学好数学。所以小王是文科学生。 5.判断各公式在给定解释时的真假值，并且改变论域使该公式在新的解释下取值相反。论域：D={-2,3,6}, F(x):x≤3, G(x):x>5, R(x,y):x+y<4 ①x(F(x)∨G(x))②yyR(x,y) 习题五 1.设个体域D={a,b,c}，在D中消去公式x(F(x)yG(y))的量词。甲乙用了不同的演算过程： 甲的演算过程如下： x(F(x)yG(y))x(F(x)(G(a)G(b)G(c)))(F(a)(G(a)G(b)G(c))) (F(b)(G(a)G(b)G(c)))(F(c)(G(a)G(b)G(c)))(F(a)F(b)F(c))(G(a)G(b)G(c))乙的演算过程如下： x(F(x)yG(y))xF(x)yG(y)(F(a)F(b)F(c))(G(a)G(b)G(c)) 显然，乙的演算过程简单，试指出乙在演算过程中的关键步骤。 解：乙在演算中的关键步骤是，在演算开始就利用量词辖域收缩与扩张等值式，将量词的辖域缩小，因而演算简单。 2.设个体域D={a,b,c}，消去下列各式的量词： (1)xy(F(x)G(y))(2)xy(F(x)G(y))(3)xF(x)yG(y)(4)（xF(x,y)yG(y)) 解： （1）(F(a)F(b)F(c))(G(a)G(b)G(c))（2）(F(a)F(b)F(c))(G(a)G(b)G(c))（3）(F(a)F(b)F(c))(G(a)G(b)G(c))（4）(F(a,y)F(b,y)F(c,y))(G(a)G(b)G(c))在（1）（2）（4）中均将量词的辖域缩小，所以演算结果都比较简单 3.设个体域D={1,2}，请给出两种不同的解释I1和I2，使得下面公式在I1下都是真命题，而在I2下都是假命题。（1）x(F(x)G(x))（2）x(F(x)G(x))解： 解释I1为：个体为实数集合R，F(x)：x为自然数，G(x)：x为整数。在I1下，（1）为自然数都是整数，（2）为存在整数为自然数。他们都是真命题 解释I2为：个体域仍为实数集R，F(x)：x是无理数，G(x)：x能表示成分数，在I2下，（1）为无理数都能表示成分数，（2）为存在能表示成分数的无理数，他们都是假命题 4.给定公式AxF(x)xF(x) （1）在解释I1中，个体域D1={a}，证明公式A在I1下的真值为1.（2）在解释I2中，个体域D2={a1,a2,,an}，n2,A在I2下的真值还一定是1吗？为什么？ 解： （1）在I1下，xF(x)xF(x)F(a)F(a)F(a)F(a)1（2）在I2下 xF(x)xF(x)(F(a1)F(a2)F(an))(F(a1)F(a2)F(an)) 为可满足式，设F(x)：x为奇数，aii,i1,2,n,n2，此时，蕴涵式前件为真，后件为假，故蕴含式为假，若令F(x)；x为整数，则蕴含式前后件均为真，所以（2）中公式在I2下为可满足式 5.给定解释I如下：（a）个体域D={3,4}；（b）f(x)为f(3)4,f(4)3; （c）F(x,y)为F(3,3)F(4,4)0,F(3,4)F(4,3)1.试求下列公式在I下的真值。 (1)xyF(x,y)(2)xyF(x,y)(3)xyF(x,y)F(f(x),f(y))) 解： （1） xyF(x,y)x(F(x,3)F(x,4))(F(3,3)F(3,4))(F(4,3)F(4,4))111（2） x(F(x,3)F(x,4))(F(3,3)F(3,4))(F(4,3)F(4,4)0（3） x((F(x,3)F(f(x),f(3)))(F(x,4)F(f(x),f(4))))(((F(3,3)F(f(3),f(3)))(F(3,4)F(f(3),f(4))))(((F(4,3)F(f(4),f(3)))(F(4,4)F(f(4),f(4))))1 6.甲使用量词辖域收缩与扩张等值式进行如下演算 x(F(x)G(x,y))xF(x)G(x,y) 乙说甲错了，乙说的对吗？为什么？ 解：乙说的对，甲错了，全称量词的指导变元x，辖域为(F(x)G(x,y))，其中F(x)与G(x,y)都是x的约束变元，因而不能讲量词的辖域变小 7.请指出下面等值运算的两处错误 xy(F(x)(G(y)H(x,y))xy(F(x)(G(y)H(x,y))xy((F(x)G(y))H(x,y)) 解： 演算的第一步，应用量词辖域收缩与扩张算值式时丢掉了否定连接词，演算的第二步，在原错的基础上又用错了等值式 (F(x)G(y)H(x,y))和(F(x)G(y)H(x,y))不等值 8.在一阶逻辑中将下列命题符号化，要求用两种不同的等值形式（1）没有小于负数的正数 （2）相等的两个角未必都是对顶角 解： （1）x(F(x)G(x))x(G(x)F(x)) 其中F(x)：x小于负数，G(x)：x是正数 （2）xy(F(x)F(y)H(x,y)L(x,y)xy(F(x)F(y)H(x,y)L(x,y))其中F(x)：x是角，H(x,y)：x=y，L(x,y)：x和y是对顶角 9.设个体域D为实数集合，命题“有的实数既是有理数又是无理数”，这显然是个假命题。可是某人却说这是真命题，其理由如下 设F(x)：x是有理数，G(x）：x是无理数。xF(x),xG(x)都是真命题，于是，xF(x)xG(x)x(F(x)G(x))由于xF(x)xG(x)是真命题，故x(F(x)G(x))也是真命题，即有的实数是有理数，也是无理数这个人的结论对吗？为什么？ 解：存在量词对无分配律 10.在求前束范式时有人说x(F(x)G(x,y))已是前束范式，理由是量词已在公式的前面，他说的对吗？为什么？ 解：在前束范式中，否定联结词不能在量词前面出现 11.有人说无法求公式 x(F(x)G(x))xG(x,y)的前束范式，因为公式中的两个量词的指导变元相同。他的理由对吗？为什么？ 换名规则可以使两个指导变元不相同 12.求下列各式的前束范式：(1)xF(x)yG(x,y)(2)x(F(x,y)yG(x,y,z))(3)xF(x,y)xG(x,y) (4)x1(F(x1)G(x1,x2))(x2H(x2)x3L(x2,x3))(5)x1F(x1,x2)(F(x1)x2G(x1,x2))解： （1）xy(F(x)G(z,y))（2）xt(F(x,t)G(x,t,z)) （3）x1x2x3x4((F(x1,y)G(x2,y))(G(x3,y)F(x4,y)))（4）y1y2y3((F(y1)G(y1,x2))(H(y2)L(x2,y3)))（5）y1y2(F(y1,x2)(F(x1)G(x1,y2))) 13.将下列命题符号化，要求符号化的公式权威前束范式：（1）有点火车比有的汽车跑的快（2）有的火车比所有的汽车跑的快 （3）说有的火车比所有汽车跑得快是不对的（4）说有的飞机比有的汽车慢也是不对的 解： （1）xy(F(x)G(y)H(x,y))其中F(x)：x是汽车 G(y):y是 火车 H(x,y)：x比y跑得快（2）xy(F(x)(G(y)H(x,y)))其中F(x)：x是火车 G(y):y是 汽车 H(x,y)：x比y跑得快 （3)xy(F(x)G(y)H(x,y))其中F(x)：x是火车 G(y):y是 汽车H(x,y)：x比y跑得快 （4）xy(F(x)G(y)H(x,y))其中F(x)：x是飞机 G(y):y是 汽车 H(x,y)：x比y跑得慢 14.在自然推理系统F中，指出下面各证明序列中的错误：（1）①F(x)xG(x)前提引入 ②F(c)G(c)①EI规则（2）①xF(x)yG(y)前提引入 ②F(a)F(b)①EI规则（3）①F(y)G(y)前提引入 ②x(F(x)G(x))①EG规则（4）①F(a)F(b)前提引入 ②x(F(x)G(x))①EG规则（5）①F(c)G(c)前提引入 ②x(F(x)G(x))①UG规则 解：（1）对F(x)xG(x)不能使用EI规则，它不是前束范式，首先化成前束范式F(x)xG(x)x(F(y)G(x))，因为量词辖域(F(y)G(x)中，除了x还有自由出现的y所以不能用EI规则 （2）对xF(x)yG(y)也应该先化成前束范式才能消去量词，其前束范式为xy(F(x)G(y))，要消去量词，既要用UI规则，又要用EI规则（3）这里A(y)=F(y)G(y)满足要求 （4）这里，使F(a)为真的a不一定使G(a)为真，同样的，使G(b)为真的b不一定使F(b)为真 （5）这里，c为个体常项，不能对F(c)G(c)引入全称量词 15.在自然推理系统F中，构造下面推理的证明：（1）前提：xF(x)y((F(y)G(y))R(y)),xF(x) 结论：xR(x) （2）前提：x(F(x)(G(a)R(x))),xF(x) 结论：x(F(x)R(x))（3）前提：x(F(x)G(x)),xG(x) 结论：xF(x) （4）前提：x(F(x)G(x)),x(G(x)R(x)),xR(x) 结论：xF(x) （1）证明：1 xF(x) 前提引入 xF(x)y((F(y)G(y))R(y)) 前提引入 y((F(y)G(y))R(y) 2假言推理 F(c)EI(F(c)G(c))R(c) UI F(c)G(c) 附加 R(c)6假言推理 xR(x) 7EG （2）证明：1 xF(x) 前提引入 x(H(x)),xF(x)x(F(a)G(a))),G(a)I(y)H(a)x(F(x)(G(a)R(x))) x(G(a)H(a)I(a))前提引入 F(c)EI F(c)(G(a)R(c)) UI G(a)R(c)4假言推理 R(c) 5化简 F(c)R(c)6合取 x(F(x)R(x)) 7EG （3）证明：1 xF(x) 前提引入xF(x) 1置换F(c) 2UI x(F(x)G(x)) 前提引入F(c)G(c) 4UI 6F(c)5析取三段论xF(x) 6EG(4)证明：1 x(F(x)G(x)) 前提引入 F(y)G(y)UI x(G(x)R(X)) 前提引入 G(y)R(y) UI xR(x) 前提引入 R(y) 5UI G(y) 6析取三段论 8F(y) 27析取三段论 xF(x) UG 16.找一个解释I，在I下，使得xF(x)xG(x)为真，而使得x(F(x)G(x))为假，从而说明xF(x)xG(x)x(F(x)G(x))。解：取个体域为自然数集合N，F(x):x为奇数，G(x):x 为偶数。显然在以上解释下xF(x)xG(x)为真而x(F(x)G(x))为假。 17.给定推理如下： 前提：x(F(x)G(x)),x(H(x)G(x)) 结论：x(H(x)F(x))。 有些人给出的证明如下： 证明： ①xH(x)附加前提引入 ②H(y) ③x(H(x)G(x)) ④H(y)G(y) ⑤G(y) ⑥x(F(x)G(x)) ⑦F(y)G(y) ⑧F(y) ⑨xF(x) 解：根据16题可知两公式并不等价。 ①UI 前提引入 ③UI ②⑤假言推理 前提引入 ⑥UI ⑤⑦拒取式 ⑧UG 并且说，由附加前提证明法可知，推理正确，请指出以上证明的错误。18.给出上题（17）推理的正确证明（注意，不能使用附加前提证明法）。 证明：1 x(F(x)G(x)) 前提引入 x(H(x)G(x)) 前提引入 F(y)G(y)UI H(y)G(y) 2UI G(y)F(y) 3置换H(y)F(y)5假言三段论x(H(x)F(x))UG 19.在自然推理系统F中，构造下列推理的证明： 前提：xF(x)xG(x) 结论：x(F(x)G(x)) 证明：1xF(x)xG(x) 前提引入 yF(y)xG(x) 换名规则 yx(F(x)G(x))化简 x(F(x)G(x))EI 20.在自然推理系统F中，构造下列推理的证明（可以使用附加前提证明法）：（1）前提：x(F(x)G(x)) 结论：xF(x)xG(x)（2）前提：x(F(x)G(x)) 结论：xF(x)xG(x) 证明：（1）.1xF(x) 附加前提引入 F(y)UI x(F(x)G(x)) 前提引入 F(y)G(y) 3UI G(y)3假言推理 xG(x) （2）1 xF(x) 附加前提引入xF(x) 置换原则F(c) 2EI x(F(x)G(x)) 前提引入 F(c)G(c) UI G(c) 5析取三段论xG(x) EG 21.在自然推理系统中，构造下面推理的证明： 没有白色的乌鸦，北京鸭都是白色的。因此，北京鸭都不是乌鸦。 设F(x):x是乌鸦，G(x)：x是北京鸭，H(x):x是白色的。前提 x(F(x)H(x)),x(G(x)H(x))结论 x(G(x)F(x)) 证明：1 x(F(x)H(x)) 前提引入 2 x(F(x)H(x)) 置换原则 3 x(F(x)H(x)) 置换原则 4 x(H(x)F(x)) H(y)F(y) 4UI 6 x(G(x)H(x)) 前提引入 7 G(y)H(y) 5UI 8 G(y)F(y) 7假言三段论 9 x(G(x)F(x)) 8UG 22.在自然推理系统F中，构造下面推理的证明： (1)偶数都能被2整除。6是偶数。所以6能被2整除。 (2)凡大学生都是勤奋的。王晓山不勤奋，所以王晓山不是大学生。 （1）设F(x):x为偶数，G(x)：x能被2整除 前提 x(F(x)G(x)),F(6)结论 G(6)证明：1 x(F(x)G(x)) 前提引入 F(6)G(6) 1UI F(6) 前提引入 G(6) 3假言推理 (2)设F(x):x是大学生，G(x)：x是勤奋的，a 王晓山 前提 x(F(x)G(x)),G(a)，结论 F(a) 证明：1 x(F(x)G(x)) 前提引入 F(a)G(a) 1UI G(a) 前提引入 F(a)3 据取式 23.在自然推理系统F中，证明下面推理： （1）每个有理数都是实数。有的有理数是整数。因此，有的实数是整数9（2）有理数，无理数都是实数。虚数不是实数。因此，虚数既不是有理数也不是无理数。 （1）设F(x):x是有理数，G(x)：x实数，H(x):x是整数 前提 x(F(x)G(x))，x(F(x)H(x)) 结论 x(G(x)H(x)) (2)设F(x):x是有理数，G(x)：x是无理数，H(x):x是实数，I(x):x是虚数 前提 x((F(x)G(x))H(x)),x(I(x)H(x))结论 x(I(x)(F(x)G(x))) 证明：1 x(I(x)H(x)) 前提引入 I(y)H(y) UI x((F(x)G(x))H(x)), 前提引入 4(F(y)G(y))H(y)UI H(y)(F(y)G(y)) 置换 I(y)(F(y)G(y)) 5假言三段论 x(I(x)(F(x)G(x)) UG 24.在自然推理系统F中，构造下面推理的证明： 每个喜欢不行的人都不喜欢骑自行车。每个人或者喜欢骑自行车或者喜欢乘汽车。有的人不喜欢乘汽车，所以有的人不喜欢步行。（个体域为人类集合） 设F(x):x喜欢步行，G(x)：x喜欢骑自行车，H(x):x喜欢乘汽车 前提 x(F(x)G(x)，x(G(x)H(x)),xH(x)结论 xF(x) 证明：1 xH(x) 前提引入 H(c) UI x(G(x)H(x)) 前提引入 G(c)H(c)UI G(c) 4析取三段论 x(F(x)G(x)) 前提引入 F(c)G(c) UI F(c) 57拒取式 xF(x) 8UG 25.在自然推理系统F中，构造下列推理的证明（个体域为人类集合）： 每个科学工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者，并且是聪明的，所以王大海在他的事业中将获得成功。 设F(x):x是科学工作者，G(x)：x是刻苦钻研的，H(x):x是聪明的，I(x):x在事业中获得成功 前提 x(F(x)G(x))，x(G(x)H(x)I(x))，a:王大海，F(a),H(a)结论 I(a)证明：1 F(a) 前提引入 x(F(x)G(x)) 前提引入 F(a)G(a) 2UI G(a)3假言推论 H(a) 前提引入 x(G(x)H(x)I(x)) 前提引入 G(a)H(a)I(a) 6UI G(a)H(a)5合取 I(a)8假言推论 第一章部分课后习题参考答案 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r) 0∨(0∧1)0（2）（p↔r）∧(﹁q∨s)（0↔1）∧(1∨1)0∧10.（3）（p∧q∧r）↔(p∧q∧﹁r)（1∧1∧1）↔(0∧0∧0)0(4)（r∧s）→(p∧q)（0∧1）→(1∧0)0→01 17．判断下面一段论述是否为真：“是无理数。并且，如果3是无理数，则2也是无理数。另外，只有6能被2整除，6才能被4整除。” 答：p: 是无理数 q: 3是无理数 0 r: 2是无理数 s: 6能被2整除t: 6能被4整除 0 命题符号化为： p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。19．用真值表判断下列公式的类型：（4）(p→q)→(q→p)（5）(p∧r)(p∧q)（6）((p→q)∧(q→r))→(p→r)答： （4） p q p→q q p q→p (p→q)→(q→p) 0 0 0 0 0 0 0 0 0 0 所以公式类型为永真式 （5）公式类型为可满足式（方法如上例）（6）公式类型为永真式（方法如上例） 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.1(1)(p∧q→q)(2)(p→(p∨q))∨(p→r)(3)(p∨q)→(p∧r)答：(2)（p→(p∨q)）∨(p→r)(p∨(p∨q))∨(p∨r)p∨p∨q∨r1 所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r)0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式：(2)(p→q)∧(p→r)(p→(q∧r))(4)(p∧q)∨(p∧q)(p∨q)∧(p∧q)证明（2）(p→q)∧(p→r)(p∨q)∧(p∨r)p∨(q∧r))p→(q∧r)（4）(p∧q)∨(p∧q)(p∨(p∧q))∧(q∨(p∧q)(p∨p)∧(p∨q)∧(q∨p)∧(q∨q)1∧(p∨q)∧(p∧q)∧1 (p∨q)∧(p∧q)5.求下列公式的主析取范式与主合取范式，并求成真赋值 (1)(p→q)→(q∨p)(2)(p→q)∧q∧r(3)(p∨(q∧r))→(p∨q∨r)解： （1）主析取范式 (p→q)→(qp)(pq)(qp)(pq)(qp)(pq)(qp)(qp)(pq)(pq)(pq)(pq)(pq)m0m2m3 ∑(0,2,3)主合取范式： (p→q)→(qp)(pq)(qp)(pq)(qp)(p(qp))(q(qp))1(pq)(pq) M1 ∏(1)(2)主合取范式为： (p→q)qr(pq)qr (pq)qr0 所以该式为矛盾式.主合取范式为∏(0,1,2,3,4,5,6,7)矛盾式的主析取范式为 0(3)主合取范式为： (p(qr))→(pqr)(p(qr))→(pqr)(p(qr))(pqr)(p(pqr))((qr))(pqr))11 1 所以该式为永真式.永真式的主合取范式为 1 主析取范式为∑(0,1,2,3,4,5,6,7)第三章部分课后习题参考答案 14.在自然推理系统P中构造下面推理的证明：(2)前提：pq,(qr),r 结论：p(4)前提：qp,qs,st,tr 结论：pq 证明：（2） ①(qr)前提引入 ②qr ①置换 ③qr ②蕴含等值式 ④r 前提引入 ⑤q ③④拒取式 ⑥pq 前提引入 ⑦￢p（3）⑤⑥拒取式 证明（4）： ①tr 前提引入 ②t ①化简律 ③qs 前提引入 ④st 前提引入 ⑤qt ③④等价三段论 ⑥（qt）(tq)⑤ 置换 ⑦（qt）⑥化简 ⑧q ②⑥ 假言推理 ⑨qp 前提引入 ⑩p ⑧⑨假言推理(11)pq ⑧⑩合取 15在自然推理系统P中用附加前提法证明下面各推理： 4(1)前提：p(qr),sp,q 结论：sr 证明 ①s 附加前提引入 ②sp 前提引入 ③p ①②假言推理 ④p(qr)前提引入 ⑤qr ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理 16在自然推理系统P中用归谬法证明下面各推理： (1)前提：pq,rq,rs 结论：p 证明： ①p 结论的否定引入 ②p﹁q 前提引入 ③﹁q ①②假言推理 ④￢rq 前提引入 ⑤￢r ④化简律 ⑥r￢s 前提引入 ⑦r ⑥化简律 ⑧r﹁r ⑤⑦ 合取 由于最后一步r﹁r 是矛盾式,所以推理正确.第四篇：离散数学习题五
第五篇：离散数学课后习题答案
![下载离散数学图论习题[优秀范文5篇]word格式文档](http://static.xiexiebang.com/skin/default/images/icon_word.png){kind=icon}
点击咨询 