离散数学第2版答案pdf

离散数学第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

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＝___________________

习题 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) 小王既聪明又用功，但身体不

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

1-1．都是命题： 1-2设

P：明天天气晴朗 Q：我们就去郊游

则 P ?Q：如果明天天气晴朗，我们就去郊游 1-3根据真值表求公式P ? (P∧(Q ?R ))的主析取范式。 解

表1.15

P T T T T F F F F Q T T F F T T F F 例1.42真值表

R T F T F T F T F P ? (P∧(Q ?R)) T F T T T T T T 则

P ? (P∧(Q ?R )) ? (﹁P∧Q∧R )∨(﹁P∧Q∧﹁R )∨(﹁P∧﹁Q∧R )∨ (﹁P∧?Q∧﹁R )∨(P∧﹁Q∧R )∨(P∧﹁Q∧﹁R )∨(P∧Q∧R )

■

由于任意一组命题变元P1, P2, …, Pn的真值指派和它的极小项之间是一一对应的，故可以对极小项进行编码。首先需要规定变元在极小项中的排列次序，假设为P1, P2, …, Pn，用m表示极小项，若Pi出现在极小项中，则编码的第i个位置上的值为1，否则为0。比如变元P, Q, R（规定次序为P, Q, R）的极小项P∧﹁Q∧﹁R的编码为100，将此极小项记为m100。若将编码看作是一个二进制数，又可将例中的极小项记为m4。用此方法，可以简写所求得的

– 1 –

错误！文档

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是同

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