下载文档原格式
离散数学及其应用课后习题答案【篇一：离散数学及其应用(课后习题)】出下列命题是原子命题还是复合命题。
（3）大雁北回，春天来了。
（4）不是东风压倒西风，就是西风压倒东风。
（5）张三和李四在吵架。
解：（3）和（4）是复合命题，（5）是原子命题。
习题1.21. 指出下列命题的真值：（1）若2?2?4，则太阳从西方升起。
解：该命题真值为t（因为命题的前件为假）。
（3）胎生动物当且仅当是哺乳动物。
解：该命题真值为f（如鸭嘴兽虽是哺乳动物，但不是胎生动物）。
2. 令p：天气好。
q：我去公园。
请将下列命题符号化。
（2）只要天气好，我就去公园。
（3）只有天气好，我才去公园。
（6）天气好，我去公园。
解：（2）p?q。
（3）q?p。
（6）p?q。
习题1.32. 将下列命题符号化（句中括号内提示的是相应的原子命题的符号表示）：（1）我去新华书店（p），仅当我有时间（q）。
（3）只要努力学习（p），成绩就会好的（q）。
（6）我今天进城（p），除非下雨（q）。
（10）人不犯我（p），我不犯人（q）；人若犯我，我必犯人。
解：（1）p?q。
（3）p?q。
（6）?q?p。
（10）(?p??q)?(p?q)。
习题1.41. 写出下列公式的真值表：（2）p?(q?r)。
解：该公式的真值表如下表：2. 证明下列等价公式：（2）(p?q)??(p?q)??(p?q)。
证明：?(p?q)??((p?q)?(?p??q))??(p?q)??(?p??q))??(p?q)?(p?q) ?(p ?q)??(p?q)（4）(p?q)?(p?r)?p?(q?r)。
证明：(p?q)?(p?r)?(?p?q)?(?p?r)??p?(q?r)?p?(q?r)3. 甲、乙、丙、丁4人参加考试后，有人问他们谁的成绩最好，甲说，不是我。
乙说：是丁。
丙说：是乙。
丁说：不是我。
已知4个人的回答只有一个人符合实际，问成绩最好的是谁？解：设a：甲成绩最好。
b：乙成绩最好。
第四讲几种特殊图一、小结本讲主要介绍欧拉图与汉密尔顿图、平面图与着色以及一些相关的概念与结论等。
1．欧拉图的概念给定无孤立结点图G ，若存在一条路经过图G的每条边一次且仅一次，则该路称为欧拉路；若存在一条回路经过图G的每条边一次且仅一次，在该回路称为欧拉回路；具有欧拉回路的图称为欧拉图；具有欧拉路但无欧拉回路的图称为半欧拉图。
规定平凡图为欧拉图。
2．欧拉路与回路存在的充要条件无向图G具有一条欧拉路，当且仅当G是连通的，且有零个或2个奇数度数的结点。
无向图G具有一条欧拉回路，当且仅当G是连通的，并且它的结点度数都是偶数的。
3．汉密尔顿图的概念给定图G ，若存在一条路经过图G的每个结点一次且仅一次，则该路称为汉密尔顿路；若存在一条回路经过图G的每个结点一次且仅一次，则该回路称为汉密尔顿回路；具有汉密尔顿回路的图称为汉密尔顿图；具有汉密尔顿路但无汉密尔顿回路的图称为半汉密尔顿图。
4．汉密尔顿回路存在的必要条件若图G=<V,E>中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S均有W(G-S)￡|S|成立，其中W(G-S)是（G-S）中连通分支数。
5．汉密尔顿路存在的充分条件设G=<V，E>是具有n个结点的简单图，若在G中每一对结点度数之和大于等于n - 1，则在G中存在一条汉密尔顿路。
6．平面图的概念设G=<V，E>是一个无向图，如果能把G的所有结点与边画在平面上，并且使得任何两条边除端点外没有其他的交点，则称G是一个平面图（也称可平面图）.显然平面图的边与边只在结点处相交。
将平面图“图示在平面上”，有时也说成“将平面图嵌入一平面”。
7．平面图的面、边界、面的次数等概念设G是一个连通平面图，如果由图中的边所包围的一个区域内既不包含图的结点，也不包含图的边，则这个区域称为G的一个面，包围该面的所有边所构成的回路称为这个面的边界。
面r的边界的回路长度称为该面的次数，记为deg(r)。
