离散数学结构答案第6版

离散数学第2版答案

【篇一：离散数学课后习题答案_屈婉玲(高等教育出版

社)】

txt>16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。

（1）p∨(q∧r)? 0∨(0∧1) ?0

（2）（p?r）∧(﹁q∨s) ?（0?1）∧(1∨1) ?0∧1?0.

（3）（?p∧?q∧r）?(p∧q∧﹁r) ?（1∧1∧1） ? (0∧0∧0)?0 (4)（?r∧s）→(p∧?q) ?（0∧1）→(1∧0) ?0→0?1

17．判断下面一段论述是否为真：“?是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 答：p: ?是无理数 1 q: 3是无理数 0 r: 2是无理数 1 s: 6能被2整除 1 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 01 1

第1章

一.填空题 1.

2. 公式P→(Q→R)在联结词全功能集{﹁,∨}中等值形式为___________________。

3. 4.

5. 6.

7. 全体小项的析取式必为____________________式。

8. P,Q为两个命题，则德摩根律可表示为7. 全体小项的析取式必为_________式。

9. P,Q为两个命题，则吸收律可表示为____________________ 。

10. 设P：我有钱，Q：我去看电影。命题“虽然我有钱，但是我不去看电影”符号化为_____ _______________。

11. 设P：我生病，Q：我去学校。命题“如果我生病，那么我不去学校”符号化为_________ ___________。 12. 13.

14.

15. 设P、Q为两个命题，交换律可表示为____________________。 16.

17. 命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化 为____________________ 。 18. 19. 20.

21. P：你努力，Q：你失败。命题“除非你努力，否则你将失败”的翻译为__________

第1章

一.填空题 1.

2. 公式P→(Q→R)在联结词全功能集{﹁,∨}中等值形式为___________________。

3. 4.

5. 6.

7. 全体小项的析取式必为____________________式。

8. P,Q为两个命题，则德摩根律可表示为7. 全体小项的析取式必为_________式。

9. P,Q为两个命题，则吸收律可表示为____________________ 。

10. 设P：我有钱，Q：我去看电影。命题“虽然我有钱，但是我不去看电影”符号化为_____ _______________。

11. 设P：我生病，Q：我去学校。命题“如果我生病，那么我不去学校”符号化为_________ ___________。 12. 13.

14.

15. 设P、Q为两个命题，交换律可表示为____________________。 16.

17. 命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化 为____________________ 。 18. 19. 20.

21. P：你努力，Q：你失败。命题“除非你努力，否则你将失败”的翻译为__________

习题9

1. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。

证明：（1）先证结论：

因为G是简单图，所以G的结点度上限 max(d(v)) ≤ n-1, G图的总点度上限为 max(Σ(d(v)) ≤ n﹒max(d(v)) ≤ n(n-1) 。根据握手定理，G图边的上限为 max(m) ≤ n(n-1)/2,所以。 （2） =〉G是完全图 因为G具有上限边数，假设有结点的点度小于n-1,那么G的总度数就小于上限值，边数就小于上限值，与条件矛盾。所以，G的每个结点的点度都为n-1，G为完全图。 G是完全图 =〉 因为G是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G的边数 。■

2. 设G是一个（n，n+1）的无向图，证明G中存在顶点u，d（u）≥3。

证明：反证法，假设,则G的总点度上限为max(Σ(d(u)) ≤2 n，根据握手定理，图边的上限为max(m) ≤ 2n/2=n。与题设m = n+1，矛盾。因此，G中存在顶点u，d（u）≥3。■

3．确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来: （1）（3，2，0，1，5）； （2）

离

散

数

学DsicetreMa temhticsa息信科学工程学院 与作制：者 永 政

蔺散离数学的展发

1世8以前纪 数学,本上是基究研离散对象的量和空间关系的科数 。学

之后因天文学,,理物的学展发如,星行道,轨牛三顿大学力定等研 律,极大地究推动了连续学(数以微积,分学物理方程数, 实复变、 数函为代论)的发展。表离 对散象的研则究处于滞停状态。2世030年纪代, 灵图提计出算的理机模型论——灵机图。这种模型 于实早制造际计算十机多,现年实的算计机的计算能,力 质上本和图机的灵计能力算样一 。由在于算机计内机,器字总是有限的长, 代表离它散数或其它的离散对象 ，此随因着计算科学机和术技迅猛的发展,散数学离就 显得要。重 信科学与息程学院工 2

为什要学离么数散 学

计算机求解的本模式基： 实际问题 数是建模 学 算 设法 计编程现 实离散学数数学建模打为知下基础识、算法为计设提 供体指具导 离散学数结实构际上是通用的就抽象模式的的合， 告集你各种模式诉本的质特征它和们之的间系，关以 及选它用的们略；策诉告你哪些问题是可解的，些是哪当前 在图机模灵上型(最无)优解的哪，是可以些得 近似到/较解的优 简而。之言，散数学离的用就作在于

第10章 图

第10章习题答案

1.解 (1)设G有m条边，由握手定理得2m＝?d(v)＝2＋2＋3＋3＋4＝14，所以G的边数7条。

v?V(2)由于这两个序列中有奇数个是奇数，由握手定理的推论知，它们都不能成为图的度数列。 (3) 由握手定理得?d(v)＝2m＝24，度数为3的结点有6个占去18度，还有6度由其它结点占有，

v?V其余结点的度数可为0、1、2，当均为2时所用结点数最少，所以应由3个结点占有这6度，即图G中至多有9个结点。

2.证明 设v1、v2、?、vn表示任给的n个人，以v1、v2、?、vn为结点，当且仅当两人为朋友时其对应的结点之间连一条边，这样得到一个简单图G。由握手定理知

?d(v)＝3n必为偶数，从而n必为偶数。

kk?1n3. 解 由于非负整数列d＝(d1，d2，…，dn)是可图化的当且仅当?di≡0(mod 2)，所以(1)、(2)、

i?1n(3)、(5)能构成无向图的度数列。

(1)、(2)、(3)是可简单图化的。其对应的无向简单图如图所示。

(5)是不可简单图化的。若不然，存在无向图G以为1，3，3，3度数列，不妨设G中结点为v1、v2、

v3、v4，且d(v1)＝1，d(v2)＝d(v3)＝d

04任务_0002 试卷总分：100 测试时间：-- ? 单项选择题

一、单项选择题（共 10 道试题，共 100 分。） 1. 设完全图Kn有

n个结点(n?2)，m条边，当（ ）时，Kn中存

在欧拉回路．

A. m为奇数 B. n为偶数 C. n为奇数 D. m

为偶数

满分：10 分

2. 设

G是连通平面图，有v个结点，e条边，r个面，则r=

( )．

A. e－v＋2 B. v＋e－2 C. e－v－2 D. e＋v＋2

满分：10 分

3.

设有向图（a）、（b）、（c）与（d）如图四所示，则下列结论成立的是(

图四

A. （a）是强连通的

)．

B. （b）是强连通的 C. （c）是强连通的 D. （d）是强连通的 满分：10 分

4.

如图一所示，以下说法正确的是 ( ) ．

A. {(a, e)}是割边 B. {(a, e)}是边割集 C. {(a, e) ,(b, c)}是边割集 D. {(d, e)}是边割集 满分：10 分

5. 无向树TA. 6 B. 7 C. 8 D. 9

2006年下半年《离散数学》（闭卷）70学时

离散数学（A卷）

闭卷、70学时

一、 填空选择题 (每空1分，共26分)

1、给定命题公式如下：p?(q??r)。该公式的成真赋值为A,成假赋值为B,公式的类型为C。

供选择的答案

A：①无；②全体赋值；

③010，100，101，111；④010，100，101，110，111。

B：①无；②全体赋值；③000，001，011；④000，010，110。 C：①重言式；②矛盾式；③可满足式。

（?x)(P(y)?Q(x,y))?(?y)R(x,y)中，?x的辖域是 P(z)→Q(x,z) ， 2、在公式

?y的辖域是 R(x,z) 。

3、设Z+={x∣x∈Z∧X>0},π1, π2,π3是Z+的3个划分。

π1={{x}∣x∈Z+},π2={S1,S2},S1为素数集,S2=Z+-S1.π3＝{Z+}, (1)3个划分块中最多的是A,最少的是B. +++

(2)划分π1对应的是Z上的C,π2对应的是Z上的D,π3对应的是Z上的E. 供选择的答案

A:( ①),B:( ③ ) ①π1, ②π2,③π3. C:( ⑧)

第一章

1. 假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A

和B表示ECNU不必学习离散数学的二年级的学生的集合。

试求： P(?) P(P(?)) P(P(P(?)))

2. (1) (2) (3)

3. 在1?200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？

能被5整除的有40个， 能被15整除的有13个，

∴能被3或5整除，但不能被15整除的正整数共有 66-13+40-13=80个。

第三章

1. (1) (2) (3) (4) (5)

下列语句是命题吗？ 2是正数吗？ x2+x+1=0。 我要上学。

明年2月1日下雨。

如果股票涨了，那么我就赚钱。

2. 请用自然语言表达命题(p??r)?(q??r)，其中p、q、r为如下命题： p：你得流感了

q：你错过了最后的考试 r：这门课你通过了

3. 通过真值表求p?(p?(q?p))的主析取范式和主合取范式。

4. 给出p?(q?s),q,p??r?r?s的形式证明。

第四章

1. 将?x(C(x)??y(C(y)?F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同

班同学，个体域是学校全体

离散数学练习题

第一章

一．填空

1.公式(p??q)?(?p?q)的成真赋值为 01；10

2.设p, r为真命题，q, s 为假命题，则复合命题(p?q)?(?r?s)的真值为 0 3.公式?(p?q)与(p??q)?(p?q)共同的成真赋值为 01；10

4.设A为任意的公式，B为重言式，则A?B的类型为 重言式

5．设p, q均为命题，在 不能同时为真 条件下，p与q的排斥也可以写成p与q的相容或。

二．将下列命题符合化 1.

7不是无理数是不对的。

7是无理数； 或p，其中p:

7是无理数。

解：?(?p)，其中p:

2.小刘既不怕吃苦，又很爱钻研。

解：?p?q,其中p: 小刘怕吃苦，q：小刘很爱钻研

3.只有不怕困难，才能战胜困难。

解：q??p，其中p: 怕困难，q: 战胜困难

或p??q，其中p: 怕困难， q: 战胜困难

4.只要别人有困难，老王就帮助别人，除非困难解决了。

解：?r?(p?q)，其中p: 别人有困难，q:老王帮助别人 ，r: 困难解决了 或：(?r?p)?q，其中p:别人有困难，q: 老王帮助别人，r: 困难解决了

5.整数n是整数当且仅当n能被2整除。

解：p?q，其中p: