离散数学第2版答案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

习题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）

习题 2.1

1．将下列命题符号化。

(1) 4不是奇数。

解：设A(x)：x是奇数。a：4。

“4不是奇数。”符号化为：¬A(a)

(2) 2是偶数且是质数。

解：设A(x)：x是偶数。B(x)：x是质数。a：2。

“2是偶数且是质数。”符号化为：A(a)∧B(a)

(3) 老王是山东人或河北人。

解：设A(x)：x是山东人。B(x)：x是河北人。a：老王。

“老王是山东人或河北人。”符号化为：A(a)B(a)

(4) 2与3都是偶数。

解：设A(x)：x是偶数。a：2，b：3。

“2与3都是偶数。”符号化为：A(a)∧A(b)

(5) 5大于3。

解：设G(x,y)：x大于y。a：5。b：3。

“5大于3。”符号化为：G(a,b)

(6) 若m是奇数，则2m不是奇数。

解：设A(x)：x是奇数。a：m。b：2m。

“若m是奇数，则2m不是奇数。”符号化为：A(a)→A(b)

(7) 直线A平行于直线B当且仅当直线A不相交于直线B。

解：设C(x,y)：直线x平行于直线y。设D(x,y)：直线x相交于直线y。a：直线A。b：直线B。

“直线A平行于直线B当且仅当直线A不相交于直线B。”符号化为：C(a,b) ¬D(x,y)

(8) 小王既聪明又用功，但身体不

第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

离散数学第8章 函数

CHAPTER Eight

离散数学Discrete Mathematics

6/2/2013 9:02 PM

Discrete Math. , Chen Chen

离散数学第8章 函数

CHAPTER Eight

第八章 函数§8.1 函数的定义与性质

§8.2 函数的复合与反函数§8.3 双射函数与集合的基数§8.4一个电话系统的描述实例

6/2/2013 9:02 PM

Discrete Math. , Chen Chen

离散数学第8章 函数

§8.1 函数的定义与性质

CHAPTER Eight

定义8.1 设 F 为二元关系，若 x domF 都存在唯一的 y ranF 使xFy 成立, 则称F为函数。 对于函数F, 如果 xFy,则记y =F(x),并称y为 F 在 x 的值。 例8.1 设F1={<x1,y1>, <x2,y1>, <x3,y2>},F2={<x1,y1>, <x1,y2>}. 则F1是函数， 而F2不是函数。

定义8.2 设F、G是函数，则 F=G F G∧ G F.

注：如果F=G,那么它们满足：(1

离散数学第8章 函数

CHAPTER Eight

离散数学Discrete Mathematics

6/2/2013 9:02 PM

Discrete Math. , Chen Chen

离散数学第8章 函数

CHAPTER Eight

第八章 函数§8.1 函数的定义与性质

§8.2 函数的复合与反函数§8.3 双射函数与集合的基数§8.4一个电话系统的描述实例

6/2/2013 9:02 PM

Discrete Math. , Chen Chen

离散数学第8章 函数

§8.1 函数的定义与性质

CHAPTER Eight

定义8.1 设 F 为二元关系，若 x domF 都存在唯一的 y ranF 使xFy 成立, 则称F为函数。 对于函数F, 如果 xFy,则记y =F(x),并称y为 F 在 x 的值。 例8.1 设F1={<x1,y1>, <x2,y1>, <x3,y2>},F2={<x1,y1>, <x1,y2>}. 则F1是函数， 而F2不是函数。

定义8.2 设F、G是函数，则 F=G F G∧ G F.

注：如果F=G,那么它们满足：(1

离散数学练习题

第一章

一．填空

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:

第6章自测题

一、填空题(每小题3分，共15分)

1. 对于n阶简单无向图图G，若其边数为m，则G的补图G的边数为( ). 2. 任意n阶简单图G有?(G)? ( ). 3. K3的所有不同构的非空子图有( )个.

?014. 设有向图G = (V, E)，V = {v1，v2，v3，v4}，若G的邻接矩阵A=??1??1101001001?1?, 则v

1

0?1??的出度od(v1) =________, v1的入度id(v1) =________, 从v2到v4长度为2的路有________条.

5.在边赋权图中, 从节点u到节点v的路中, ( )的路称为u到v的最短路径.

二、单选题(每小题3分，共15分)

1. 一个连通无向图有3个5度点、1个4度点、3个2度点，其它的都是1度，那么它

的节点个数是≤（ ）

(A) 17 (B) 18

(C) 19

(D) 20.

2. 4阶完全无向图K4中含3条边的不同构的生成子图有 (A)3 (B)4 (C)5 (D)2

2.2 命题逻辑等值演算 2.2.1 等值式与等值演算– 等值式与基本等值式 – 真值表法与等值演算法

2.2.2 联结词完备集– 真值函数 – 联结词完备集 – 与非联结词和或非联结词1

等值式定义2.11 若等价式A B是重言式, 则称A与B等值, 记作 A B, 并称A B是等值式 说明: (1) 是元语言符号, 不要混同于 和= (2) A与B等值当且仅当A与B在所有可能赋值下的真值都相 同, 即A与B有相同的真值表 2n (3) n个命题变项的真值表共有 2 个, 故每个命题公式都有 无穷多个等值的命题公式 (4) 可能有哑元出现. 在B中出现, 但不在A中出现的命题变 项称作A的哑元. 同样,在A中出现, 但不在B中出现的命题变 项称作B的哑元. 哑元的值不影响命题公式的真值. 2

真值表法例1 判断 (p q) 与 p q 是否等值 解 p q 0 0 0 1 1 0 1 1 p q 1 1 0 0 1 0 1 0 p q (p q) p q (p q) ( p q) 0 1 1 1 1 0 0 0 1 0 0 0 1 1 1 1

结论: (p q) ( p q)3

真值表法(续)例2 判断下述3个公式

一、填空题

1 设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; ?(B)＝ __________________________ .

2. 设有限集合A, |A| = n, 则 |?(A×A)| = __________________________.

3. 设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________.

4. 已知命题公式G＝?(P?Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________.

5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________.

6 设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝___________________