离散习题答案 冯伟森

1、习题参考解答习题一 1、（1）设P：他是本片的编剧， Q：他是本片的导演。 PQ（2）设P：银行利率很低， Q：股价上扬。 PQ（3）设P：银行利率很低， Q：股价上升。 （PQ）（4）设P：这个对象是占空间的，Q：这个对象是有质量的，R：这个对象是不断变化的，S：这个对象称为物质。PQRS（5）设P：他今天乘火车去了北京，Q：他今天随旅行团去了九寨沟。PQ（6）设P：小张身体单薄，Q：小张极少生病，R：小张头脑好使。PQR（7）设P：这个人不识庐山真面目，Q：这个人身在庐山中。PQ（8）设P：两个三角形相似，Q：两个三角形的对应角相等或者对应边成比例。PQ（9）设P：一个整数能被6整除，Q：

2、这个整数能被2和3整除。PQ设R：一个整数能被3整除，S：这个整数的个位数之和也能被3整除。RS2、（1）命题 T（2）命题 T/F（3）不是命题，因为真值无法确定。（4）命题 T（5）不是命题。（6）命题 T（7）命题 T/F（8）不是命题，是悖论。5、（1）证：（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（P（QQ）（PQ）（P（PQ）P（3）证：P（QR）P（QR） PQRR （PQ）（RR） （PQ）（PR） 6、 解：如果PQQR，不能断定PR。因为当Q=T时，PQQR恒成立。如果PQQR，不能断定PR。因为当Q=F时，PQQR恒成立。如果PR，则PR。8

3、、 把下列各式用等价表示出来：（1）解：（PQ）P（PQ）（ PQ）（PP） （PQ）（ PQ）（PQ）（PQ）（PP）（PP） （1）解：（P（QR）P（P（QR）P（PP）（Q（RR）（PP）（PP）（QQ）（RR）（PP）（PP）（PP）（QQ）（RR）（RR）（QQ）（RR）（PP）（PP）（PP）（QQ）（RR）（RR）（QQ）（RR）（RR）（PP）（PP)（PP）（QQ）（RR）（RR）（QQ）（RR）（RR）（PP）9、 证：PQPQ（P）QPQ（PQ）（PQ）而，是功能完备集，是功能完备集，不能互相表示，故，是最小功能完备集。10、 证：由书上的表1.16可知，“”对应的真值

4、表含2个1和2个0，而“”对应的真值表也含2个1和2个0，对应的真值表含3个1和1个0，对应的真值表含1个1和3个0，所以，“”无法用“”和“”来表示，同样“”也无法用“”和“”来表示，因此，不是功能完备集。10、 解：（1） a）真值表法由表中可以看出，14、 解：由题设A：A去，B：B去，C：C去，D：D去则满足条件的选派应该是如下范式：（A（CD）（BC）（CD）构造和以上范式等价的主析取范式共有八个极小项，但根据题意，需根据题意，需派出两人出差，所以，只有其中三项满足要求：（ABCD），（ABCD），（ABCD）即有三种方案：A和C去或者A和D去或者B和D去。15、 证：（1）由定理1

5、.11，需证（PQ）（P（PQ）为永真式（3）由定理1.11，需证PPRS为永真式16、 证：（1）性质1 由定理1.11和“”的定义，AA是永真式，所以A=A。（2）性质2 由定理1.11，A=B，B=A，AB和B是永真式，即A是永真式，由定理1.3，AB成立。（3）性质3 由定理1.11，A=B，AB是永真式，又A是永真式，根据“”的定义，B必是永真式。17、 证：“=”，A=B，AB是永真式，“A，必有A=B。18、 解： 设 P：珍宝藏在东厢房Q：藏宝的房子靠近池塘R：房子的前院栽有大柏树S：珍宝藏在还原正中地下T：后院栽有香樟树M：珍宝藏在附近（后院）对语句符号化后得到以下蕴含式：Q

6、P，RP，Q，RS，TM=?所以S为真，即珍宝藏在花园正中地下。19、 解：（1）不成立（P=0，Q=1）（2）不成立（P=1，Q=R=0）（3）不成立（P=0，Q=1）（4）不成立（P=0，Q=1，R=0）（5）不成立（P=1，Q=1，R=0）20、 证：（1）利用CP规则P P（附加前提规则）PQ PQ TRQ P QR TE23R TPR CP规则（2）利用CP规则P P（附加前提规则）PQ TE3（PQ）（RS） PRS TI5S TE4SE TE3（SE）B PB TI5PB CP规则（4）（反证法）21、 把下列句子防疫成逻辑形式，并给出证明。（1）如果资方拒绝增加工资，那么罢工不

7、会结束；除非罢工超过一年，并且资方撤换了经理；现在资方拒绝了增加工资，罢工刚开始，判断罢工能否停止。（2）某公司发生了一起盗窃案，经仔细侦查，掌握了如下一些事实：被盗现场没留下任何痕迹；失窃时，小花或者小英正在卡拉OK厅；如果失窃时小胖正在附近，他就会习惯性的破门而入偷走东西后扬长而去；如果小花正在卡拉OK厅唱歌，那么金刚是最大的嫌疑者；如果失窃时小胖不再附近，那么他的女友小英会和他一起外出旅游；如果失窃时小英正在卡拉OK厅唱歌，那么瘦子是最大的嫌疑者。根据以上事实，请通过演绎推理找出偷窃者。22、（1）不相容（2）相容（P=1，R=Q=S=0）（3）不相容（4）不相容23、（1）证：（PQ）

8、（QS）（SQ）（PQ）P习题 二6、（1）F，（2）A为F；B为T；C为T，E为F。7、（1）F，（2）T，（3）F，（4）T8、解：个体域D：实数集：17、(1) 错误，应换元，即(2) 正确(3) 错误，a、b应是同一个常元18、(2) 证：首先，将结论否定作为前提加入到原有前提中习题 三习题 四习题 五4、解：每个集合的划分就可以确定一个等价关系集合有多少个划分就可以确定多少个等价关系不同的划分的个数为：不同的等价关系个数等于不同的划分个数，所以不同的等价关系个数为15.习题 六习题 十1、设G是一个（n，m）简单图。证明：，等号成立当且仅当G是完全图。2、设G是一个（n，n+1）的无

9、向图，证明G中存在顶点u，d(u)3。证明：反证法，假设，则G的总点度上限为max（d(u)）2n，根据握手定理，图边的上限为max（m）2n/2=n。与题设m=n+1矛盾，因此，G中存在顶点u，d(u )3。3、确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来：（1）（3,2,0,1,5）； （2）（6,3,3,2,2）（3）（4,4,2,2,4）； （4）（7,6,8,3,9,5）解：除序列（1）不是图序列外，其余的都是图序列。因为在（1）中，总和为奇数，不满足图总度数为偶数的握手定理。可以按如下方法构造满足要求的图：序列中每个数字ai对应一个点，如果序列数字是偶数，那么就

10、在对应的点上画ai/2个环，如果序列式奇数，那么在对应的点上画（ai-1）/2个环。最后，将奇数序列对应的点两两一组，添加连线即可。下面以（2）为例说明：每个节点对应的环数（6/2，（3-1）/2，（3-1）/2，2/2，2/2）=（3,1,1,1,1）将奇数3,3对应的节点V2，V3一组，画一条连线其他序列可以类似作图，当然大家也可以画图其他不同的图形。4、证明：在（n，m）图中2m/n。证明：图的点度数是一组非负整数d(v1),d(v2).d(vn)，那么这组数的算术平均值一定大于等于其中的最小值，同时小于等于其中的最大值。对应到图的术语及为：最大值为，最小值为，平均值=（d(v1)+d(

11、v2).+d(vn)）/n=2m/n，所以2m/n。5、证明定理10.2。【定理10.2】对于任何（n，m）有向图G=（V,E），证明：有向图中，每条有向边为图贡献一度出度，同时贡献一度入度，所以总出度和入度相等，并和边数相等。因此，上述关系等式成立。7、无向图G有21条边，12个3度数结点，其余结点的度数均为2，求G的阶数n。解：根据握手定理有：21=（312+2（n-12）/2，解次方程得n=15。10、判断图10.29中的两个图是否同构，并说明理由。解：题中两个图不同构，因为左边图的唯一3度点有2个1度点为其邻接点，而右图唯一的3度点只有1个1度点为其邻接点。因此这两个图不可能同构。13

12、、设有向图D=如下图10.31所示。（1）在图中找出所有长度分别为1,2,3,4的（至少用一种表示法写出它们，并以子图形式画出它们。）（2）在图中找出所有长度分别为3,4,5,6的回路，并以子图形式画出它们。解：（1）15、若u和v是图G中仅有的两个奇度节点，证明u和v必是连通的。证明：反证法，假设u和v不连通，那么它们必然分布于此图的两个连通分支中。那么它们将分别是各连通分支中唯一的奇数度节点。根据握手定理，一个图中奇度点的个数为偶数。而两个连通分支中，奇度点的个数为奇数。矛盾。矛盾的产生是由于假设不连通导致的，因此，题设结论成立。18、设G施阶数不小于3的连通图。证明下面四条命题相互等价：

13、（1）G无割边；（2）G中任何两个结点位于同一回路中；（3）G中任何一结点和任何一边都位于同一回路中；（4）G中任何两边都在痛一回路中。证明：（1）=（2）因为G连通，且G无割边，所以任意两个结点u，v，都存在简单道路p=u.wv。又因为G无割边，所以，删除边wv后，子图依然连通，即w，v存在简单道路p，以此类推，可以找到一个核p每条边都不相同的p=v.u，这样p和p就构成了一条回路。证明：（2）=（3）因为G中任意两个结点都位于同一回路中，所以任意结点u和任意边e的两个端点v1,v2都分别在两个回路C1，C2中，如果C1-C2=u.v1.v2.u，那么将回路中v1.v2，用v1v2=e替换，

14、就得到新的回路，并满足要求。如果C1C2，C1=u.v1.u,C2=u.v2.u，那么构成新的道路P=u.v1.u.v2.u，在其中将重复边剔除，得到新的回路C3，其中包含v1，v2结点，可以讲回路中v1.v2用v1v2=e替换，就得到新的回路，并满足要求。证明：（3）=（4）对任意两条边e1,e2其端点分别为u1,u2,v1,v2.根据（3）存在回路C1=u1.v1v2.u1,C2=u2.v1v1.u2.那么可以形成新的闭道路P=u1.v1v2.u2.v1v2.u1，在其中将重复边剔除，得到新的回路C3，其中包含e2和u1,u2结点，可以将回路中u1.u2用u1u2=e1替换，就得到新的回路

15、，包含e1,e2,满足要求。证明：（4）=（1）因为任意两条吧都在同一回路中，所以不存在割边。假设边e是割边，那么删除此边，图不连通，分支中的任何一对不再同一分支中的边，不能构成回路，与条件矛盾。所以，G中无割边。23、证明：在具有n（n2）个结点的简单无向图G中，至少有两个结点的度数相同。证明：此题可用鸽巢原理，因为n个结点的简单无向图G中，结点的度数只可能是0,1,2.n-1这n个数，又因为如果有结点的度数为0，那么就不可能有结点的度为n-1，反之亦然。所以n个结点，最多有n-1中度数，其中必有至少2个结点的度数相同。24、设G是2的简单图。证明：G中必有长度至少为+1的图。证明：设p=u

16、. v是满足题设要求图G中的最长基本道路，那么d(u),d(v)都应该大于等于。那么u,v的邻接点都应该在道路p上，否则此道路可以延长，与其是最长路假设矛盾。如果u,v是邻接点，那么可以构成一个圈c=u.vu，其长度+1.如果u,v不是邻接点，那么从p的终点开始删除点，知道其为u的邻接点为止，得到道路p,可知道路p，依然保持u的所有邻接点都在p上的性质，所以可构成一个圈c=u.uu,其长度+1，证毕。25、证明：G是单向连通图当且仅当存在一条包含G中全部结点的有向道路。证明：假设不存在包含全部结点的有向道路，那么设p=v1v2.v,k是G中最长的有向道路，且u结点不包含在此有向道路中。u和此道

17、路中任何中间结点都不可能双向可达，且u不能到达V1，且vk也不能到达u，否则，此最长路克扩充。那么忧郁道路上的每个结点和u都单向可达,所以此最长路和u之间的可达关系必然如下图所示：当k为偶数时，道路克扩充为，而当k为奇数时，不管与u之间是如火热单向可达的，都可以构造出更长的有向道路，矛盾，所以G中一定存在包含所有结点的有向道路。26、无向图G如图10.32所示，先将此图顶点和边标出，然后求同种的全部割点和割边。图10.32解：标注如下所示：根据标记后的图，可求得割点分别为：u4，u7，u8，割边分别为：u4u5,u7u8,u8u9。27、求图10.33的全部强分图和单向分图。解：标图重新标记如

18、下：因此，此图有两个强分图，一个包含一个结点v9，一个包含其他的8个结点。由于两个强分图之间存在有向道路，因此全部9个结点，构成了单向分图。28、证明：一个联通无向简单图中，任意两条边最长路至少有一个公共顶点。证明：假设两条最长路p1=v1v2.vk,p2=u1u2.uk没有公共点，那么链条道路上的点集之间就有道路相连，否则就不是连通图了。设此道路起点是p1上m点，终点是p2上w点，可根据如下情况进行调论：（1）m,w是p1,p2的中间结点，那么可构成新道路p=v1v2.m.w.uk，此路至少比p1长1,矛盾。（2）假设m和w不能均分p1,p1，那么可以将两个长路段和m,w之间的道路进行拼接，

19、那么可得到比p1长的道路，与p1,p2是最长路矛盾。因此任意两条最长路至少有一个公共点。29、证明：若G是n阶无向简单图，G中每一对不相邻的顶点的度数之和至少是n-1,则G 是连通图。证明：假设G不是连通图，G1，G2是G的两个连通分支，分别为n1,n2阶连通无向简单子图，则n1+n2n。对G1中任意结点v1和G2中任意结点v2而言，v1的最大点度为n1-1，v2的最大点度为n2-1；则v1,v2的点度之和，最大为n1+n2-2n-1.与题设条件矛盾，因此，原题设结论成立。30、求出图10.34的邻接矩阵、可达矩阵、强分图和关联矩阵。解：对图的结点和边进行编号如下：习题 十一19、给定权1,4

20、,9,1,2,6,4,6,8,10构造一个最优二叉树。解：根据带权最优二叉树定理构造过程如下：21、证明：正则二叉树必有奇数个结点，且树叶数t与结点数n之间有：t=（n-1）/2。证明：因为正则二叉树的边数m与分支点数i的关系为：m=2i，又因为是树，因此结点数n满足：n=m-1=2i-1，必为奇数。叶结点数t和枝结点数之和为n，即：t+i=n，因此t=(n-1)/2习题 十二1、证明下面3个图都是平面图。证明：因为所给图都可以以平面图的方式画出来，如下：2、下面3个图都是平面图，先给图中各边标定顺序，然后求出图中各面的边界和面度。解：略5、证明：少于30条边的简单平面图至少有一个顶点的度不大

21、于4。证明：假设图G（n，m）的每个结点的度到大于等于5，根据握手定理及平面图的判定定理有：5n2m60 （1）握手定理m3n-6 （2）根据（1）得：n12结合（1）（2）得：5n/23n-6，所以n12，矛盾。因此假设不成立，题设结论成立。习题 十三1、构造（n，m）欧拉图使满足条件：（1）m和n奇偶性相同；（2）m和n奇偶性相反。解：5、在图13.10中求中国邮递员问题的解。解：略，请参考书中解法。6、设G施有两个奇度点的连通图，设计一个构造G的欧拉道路的算法。解：step1：添加链接两个奇度点的边step2：调用一般的欧拉回路的算法step3：在回路中删除添加的边8、n（n2）个结点的

22、有向完全图中，哪些是欧拉图？解：n（n2）个结点的有向完全图中,每个都是欧拉图，因为每个结点都有相同的入读和出度，可以找到有向欧拉回路。9、证明：凡有割点的图都不是哈密顿图。10、证明：4k+1阶的所有2k正则简单图都是哈密顿图。11、在无向完全图中Kn中有多少条没有公共边的哈密尔顿回路？12、11个学生打算几天都在一张圆桌上共进午餐，并且希望每次午餐时每个学生两旁所坐的人都不相同，问11人共进午餐最多能有多少天？解：将11个学生分别用结点表示，由于每个同学都可能邻座，因此每两个结点之间都有一条边，因此得到无向完全图K11，每次午餐时学生都按照一条哈密尔顿回路落座，如果两条哈密尔顿回路有公共边，则公共边端点所代表的学生就是相邻的。因此上述问题转化为求K11有多少条无公共边的哈密尔顿回路问题，利用11题的结论，共有（11-1）/2=5条无公共边的哈密