离散数学及其应用课后习题答案

离散数学及其应用课后习题答案【篇一：离散数学及其应用(课后习题)】

出下列命题是原子命题还是复合命题。（3）大雁北回，春天来了。（4）不是东风压倒西风，就是西风压倒东风。（5）张三和李四在吵架。解：（3）和（4）是复合命题，（5）是原子命题。

习题1.2

1. 指出下列命题的真值：

（1）若2?2?4，则太阳从西方升起。解：该命题真值为t（因为命题的前件为假）。（3）胎生动物当且仅当是哺乳动物。

解：该命题真值为f（如鸭嘴兽虽是哺乳动物，但不是胎生动物）。

2. 令p：天气好。q：我去公园。请将下列命题符号化。（2）只要天气好，我就去公园。（3）只有天气好，我才去公园。（6）天气好，我去公园。解：（2）p?q。（3）q?p。（6）p?q。

习题1.3

2. 将下列命题符号化（句中括号内提示的是相应的原子命题的符号表示）：（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.4

1. 写出下列公式的真值表：（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：乙成绩最好。c：丙成绩最好。d：丁成绩最好。四个人所说的命题分别用p、q、r、s表示，则

p??a；q??a??b??c?d；r??a?b??c??d；s??d。

则只有一人符合实际的命题k符号化为

k?(p??q??r??s)?(?p?q??r??s)?(?p??q?r??s)?(?p??q??r?s) p??q??r??s??a??(?a??b??c?d)??(?a?b??c??d)?d ??a?(a?b

?c??d)?(a??b?c?d)?d ?(?a?d)?(a?b?c??d)?(a??b?c?d)

?(?a?b?c?d)?(?a?b?d)?(?a??b?c?d)?(?a?c?d)?0;

同理，

?p?q??r??s?a??a??b??c?d??(?a?b??c??d)?d?0; ?p??q?r?? s?a??(?a??b??c?d)??a?b??c??d?d?0; ?p??q??r?s?a??(?a?

?b??c?d)??(?a?b??c??d)??d ?a?(a?b?c??d)?(a??b?c?d)??d ?a??d.

所以，当k为真时，a??d为真，即甲的成绩最好。

习题1.5

2. 证明下列各蕴含式：

（3）p?(q?r)?(p?q)?(p?r)。证明：

方法一：真值表法（列出命题公式(p?(q?r))?((p?q)?(p?r))的真值表）。

方法二：等值演算法

(p?(q?r))?((p?q)?(p?r))??(p?(q?r))?((p?q)?(p?r))??(?p?(?q?r)) ??(?p?q)?(?p?r)?(p?q??r)?(p??q)?(?p?r)

?(p?q??r)?((p??p?r)?(?q??p?r))?(p?q??r)?(?q??p?r)

?(p??q??p?r)?(q??q??p?r)?(?r??q??p?r)?1.

方法三：分析法

（1）直接分析法：若前件p?(q?r)为真，分两种情况：

（i）p为假，则p?q为真，p?r为真，(p?q)?(p?r)为真。

（ii）p为真，则q?r为真，此时若q为真，则r为真，则p?q为真，p?r为

真，(p?q)?(p?r)为真；若q为假，则p?r为假，(p?q)?(p?r)为真。综上，若前件为真，后件必为真，故该蕴含式成立。

(2）间接分析法：若后件(p?q)?(p?r)为假，则p?q为真，p?r为假。由

p?r为假可知，p为真，r为假。再由p?q可知，q为真。此时q?r 为假，

p?(q?r)为假，即前件为假。故蕴含式成立。

5. 叙述下列各个命题的逆换式和逆反式，并以符号写出。（1）如

果下雨，我不去。解：设p：天下雨。q：我去。

逆换式：如果我不去，天就下雨。符号表示为?q?p。逆反式：如

果我去，天就不下雨。符号表示为q??p。（2）仅当你走我将留下。解：设p：我留下。q：你走。

逆换式：如果你走，我就留下。符号表示为：q?p。逆反式：如果

你不走，我就不留下。符号表示为：?q??p。

习题1.6

2. 将下列命题公式用只含?和?的等价式表达，并要求尽可能简单。（1）(p?q)??p.

解： (p?q)??p?(p?? p)?q?0?q?0.（2）(p?(q??r))??p?q.

解： (p?(q??r))??p?q?(?p?(q??r))?(?p?q??r)

?p? q?

?p?q?

??p?q(?p??q

?p?)q?(?p?q?)q?(?r?)

?(p?q?)

?r?

?(?p?q)?(?p?q)?(?p?(?p?q)?(?p?q??r)??(p??q).

（3）?p??q?(?r?p).

(?p?q? ?r?

?p? q?

解：?p??q?(?r?p)??p??q?(r?p)

?(?p??q?r)?(?p??q?p)?(?p??q?r)?0 ??p??q?r??(p?q??r).

习题1.7

6．求下列命题公式的主析取范式和主合取范式：（1）

((p?q)?r)?p.

解：

((p?q)?r)?p??(?(p?q)?r) ?p?((p?q)??r)?p?(p?q?p)?(p??r)?(p? q?(r??r))?(p?(q??q)? ?r?(p?q?r)?(p?q??r)?(p?q?r)?(p?q??r)?

m0?m1?m3（主合取范式）

?m2?m4?m5?m6?m7.（主析取范式）

?(p?q)?(p ??r

?(p?q??r)(?p??q ?r??(p??q? ?r)

【篇二：离散数学最全课后答案(屈婉玲版)】

略

1.3．略

1.4．略

1.5．略

1.6．略

1.7．略

1.8．略

1.9．略

1.10．略

1.11．略

1.12．将下列命题符号化, 并给出各命题的真值:

(1)2+2＝4 当且仅当 3+3＝6. (2)2+2

＝4 的充要条件是 3+3?6. (3)2+2?4

与 3+3＝6 互为充要条件. (4)若

2+2?4, 则 3+3?6, 反之亦然.

(1)p?q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为 1.

(2)p??q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为 0.

(3) ?p?q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为 0.

(4) ?p??q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为 1.

1.13．将下列命题符号化, 并给出各命题的真值:

(1)若今天是星期一, 则明天是星期二. (2)只有今

天是星期一, 明天才是星期二. (3)今天是星期一

当且仅当明天是星期二. (4)若今天是星期一, 则

明天是星期三.

令 p: 今天是星期一; q: 明天是星期二; r: 明天是星期三.

(1) p?q ??1.

(2) q?p ??1.

(3) p?q ??1.

(4) p?r 当 p ??0 时为真; p ??1 时为假.

1.14．将下列命题符号化.

(1) 刘晓月跑得快, 跳得高.

(2)老王是山东人或河北人.

(3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组.

(5)李辛与李末是兄弟.

(6)王强与刘威都学过法语. (7)他一面吃

饭, 一面听音乐. (8)如果天下大雨, 他就乘

班车上班. (9)只有天下大雨, 他才乘班车

上班. (10)除非天下大雨, 他才乘班车上

班. (11)下雪路滑, 他迟到了.

(12)2 与 4 都是素数, 这是不对的.

(13)“2 或 4 是素数, 这是不对的”是不对的.

(1)p?q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高.

(2)p?q, 其中, p: 老王是山东人, q: 老王是河北人.

(3)p?q, 其中, p: 天气冷, q: 我穿了羽绒服.

(4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题.

(5)p, 其中, p: 李辛与李末是兄弟.

(6)p?q, 其中, p: 王强学过法语, q: 刘威学过法语.

(7)p?q, 其中, p: 他吃饭, q: 他听音乐.

(8)p?q, 其中, p: 天下大雨, q: 他乘班车上班.

(9)p?q, 其中, p: 他乘班车上班, q: 天下大雨.

(10)p?q, 其中, p: 他乘班车上班, q: 天下大雨.

(11)p?q, 其中, p: 下雪路滑, q: 他迟到了.

12) ??(p?q)或?p??q, 其中, p: 2 是素数, q: 4 是素数. (13) ???(p?q)或 p?q, 其中, p: 2 是素数, q: 4 是素数.

1.15．设 p: 2+3=5.

q: 大熊猫产在中国.

r: 复旦大学在广州. 求

下列复合命题的真值:

(1)(p?q) ?r

(2)(r??(p?q)) ???p

(3) ?r??(?p??q?r)

(4)(p?q??r) ??(( ?p??q) ?r)

(1)真值为 0.

(2)真值为 0.

(3)真值为 0.

(4)真值为 1.

注意: p, q 是真命题, r 是假命题.

1.16．

1.17．

1.18．

1.19．略略略用真值表判断下列公式的类型:

(1)p??(p?q?r)

(2)(p??q) ??q

(3) ??(q?r) ?r

(4)(p?q) ??(?q??p)

(5)(p?r) ??( ?p??q)

(6)((p?q) ??(q?r)) ??(p?r)

(7)(p?q) ??(r?s)

(1), (4), (6)为重言式.

(3)为矛盾式.

(2), (5), (7)为可满足式.

1.20．

1.21．

1.22．

1.23．

1.24．

1.25．

1.26．

1.27．

1.28．

1.29．

1.30．

1.31．略略略略略略略略略略略将下列命题符号化, 并给出各命题的真值:

(1)若 3+＝4, 则地球是静止不动的.

(2)若 3+2＝4, 则地球是运动不止的. (3)若地球

上没有树木, 则人类不能生存.

(4)若地球上没有水, 则 3 是无理数.

(1)p?q, 其中, p: 2+2＝4, q: 地球静止不动, 真值为 0.

(2)p?q, 其中, p: 2+2＝4, q: 地球运动不止, 真值为 1.

(3) ?p??q, 其中, p: 地球上有树木, q: 人类能生存, 真值为 1.

(4) ?p?q, 其中, p: 地球上有水, q:3 是无理数, 真值为 1.

2.1. 设公式 a = p?q, b = p??q, 用真值表验证公式 a 和 b 适合德摩根律:

?(a?b) ???a??b.

因为 ?(a?b)和 ?a??b 的真值表相同, 所以它们等值.

2.2. 略

2.3.用等值演算法判断下列公式的类型,对不是重言式的可满足式,再用真值表法求出成真赋值.

(1) ??(p?q?q)

(2)(p??(p?q)) ??(p?r)

(3)(p?q) ??(p?r)

(1) ??(p?q?q)????(?(p?q) ??q) ????(?p ???q ??q) ??p?q??q ??p?0 ??0 ??0. 矛盾式. (2)

重言式.

(3) (p?q) ??(p?r) ???(p?q) ??(p?r) ???p??q ??p?r 易见, 是可满足式, 但不是重言式. 成真赋值为: 000, 001, 101, 111

2.4. 用等值演算法证明下面等值式:

(1) p??(p?q) ??(p??q)

(3) ??(p?q) ??(p?q) ???(p?q)

(4) (p??q) ??(?p?q) ??(p?q) ???(p?q)

(1) (p?q) ??(p??q) ??p ??(q??q) ??p ??1 ??p.

(3) ??(p?q)

???((p?q) ??(q?p))

???((?p?q) ??(?q?p))

??(p??q) ??(q??p)

??(p?q) ??(p??p) ??(?q?q) ??(?p??q)

??(p?q) ???(p?q)

(4) (p??q) ??(?p?q)

??(p??p) ??(p?q) ??(?q??p) ??(?q?q)

??(p?q) ???(p?q)

2.5. 求下列公式的主析取范式, 并求成真赋值:

(1)( ?p?q) ??(?q?p)

(2) ??(p?q) ?q?r

(3)(p??(q?r)) ??(p?q?r)

(1)(?p?q) ??(?q?p)

???(p?q) ??(?q?p)

???p??q ???q ??p???p??q ???q ??p(吸收

律)??(p??p)??q ??p?(q??q) ??p??q ??p??q ??p?q ??p??q ??m10 ??m00 ??m11 ??m10

??m0 ??m2 ??m3

???(0, 2, 3).

成真赋值为 00, 10, 11.

(2)主析取范式为 0, 无成真赋值, 为矛盾式.

(3)m0?m1?m2?m3?m4?m5?m6?m7, 为重言式.

2.6. 求下列公式的主合取范式, 并求成假赋值:

(1) ??(q??p) ??p

(2)(p?q) ??(?p?r)

(3)(p??(p?q)) ?r

(1)??(q??p) ???p

???(?q??p) ???p

??q?p ???p

??q?0

??0

??m0?m1?m2?m3

这是矛盾式. 成假赋值为 00, 01, 10, 11.

(2)m4, 成假赋值为 100.

(3)主合取范式为 1, 为重言式.

【篇三：离散数学及其应用】

txt>摘要：离散数学，又称为组合数学。离散数学是计算机出现以

后迅速发展起来的一门数学分支。计算机科学就是算法的科学，而

计算机所处理的对象是离散的数据，所以离散对象的处理就成了计

算机科学的核心，而研究离散对象的科学恰恰就是离散数学。离散

数学的发展改变了传统数学中分析和代数占统治地位的局面。它在

各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时

离散数学也是计算机专业的许多专业课程，如程序设计语言、数据

结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习

创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来

参与创新性的研究和开发工作打下坚实的基础。

关键词：离散数学电路设计软件技术人工智能应用等

1、离散数学的相关介绍

1.1离散数学的简介

离散数学是现代数学的一个重要分支，是计算机类专业的重要课程。它以研究离散量的结构及其相互间的关系为主要目标，其研究对象

一般是有限个或可数个元素，因此离散数学可以充分描述计算机学

科离散性的特点。由于离散数学在计算机科学中的重要作用，国内

外几乎所有大学的计算机类专业的教学计划中都将其列为核心课程

进行重点建设，它是其他骨干课程，如数据结构、操作系统、人工

智能、计算机网络、软件工程、编译原理等的先修课程，国内许多

大学将其作为计算机专业类研究生入学考试的内容。

1.2离散数学的发展

20世纪的计算机出现，带动了世界性的信息革命的伟大进程。计算

机科学在信息革命中的学科地位有如牛顿力学在工业革命中的学科

地位一样，由计算机出现带动的信息革命当然计算机科学将起着主

导的作用。随着信息时代的到来，工业革命时代以微积分为代表的

连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被

人们认识。离散数学课程所传授的思想和方法，广泛地体现在计算

机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论

计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人

工智能到认知系统，无不与离散数学密切相关。

1.3离散数学的内容

离散数学是传统的逻辑学，集合论（包括函数），数论基础，算法

设计，组合分析，离散概率，关系理论，图论与树，抽象代数（包

括代数系统，群、环、域等），布尔代数，计算模型（语言与自动机）等汇集起来的一门综合学科。离散数学课程主要介绍离散数学

的各个分支的基本概念、

基本理论和基本方法。这些概念、理论以及方法大量地应用在数字

电路、编译原理、数据结构、操作系统、数据库系统、算法的分析

与设计、人工智能、计算机网络等专业课程中；同时，该课程所提

供的训练十分有益于学生概括抽象能力、逻辑思维能力、归纳构造

能力的提高，十分有益于学生严谨、完整、规范的科学态度的培养。

2、离散数学在其他学科的应用

2.1 数理逻辑在人工智能中的应用

人工智能是计算机学科中一个非常重要的方向,离散数学在人工智能

中的应用主要是数理逻辑部分在人工智能中的应用。数理逻辑包括

命题逻辑和谓词逻辑,命题逻辑就是研究以命题为单位进行前提与结

论之间的推理,而谓词逻辑就是研究句子内在的联系。大家都知道,人

工智能共有两个流派,连接主义流派和符号主义流派。其中在符号主

义流派里,他们认为现实世界的各种事物可以用符号的形式表示出来,

其中最主要的就是人类的自然语言可以用符号进行表示。语言的符

号化就是数理逻辑研究的基本内容,计算机智能化的前提就是将人类

的语言符号化成机器可以识别的符号,这样计算机才能进行推理,才能

具有智能。由此可见数理逻辑中重要的思想、方法及内容贯穿到人

工智能的整个学科。

2.2 图论在数据结构中的应用

前序遍历法:如果二叉树为空,则返回。否则(1)访问根节点(2)前序遍历左子树(3)前序遍历右子树,得到前序序列。

中序遍历法:如果二叉树为空,则返回。否则(1)中序遍历左子树(2)访问根节点(3)中序遍历右子树,得到中序序列。

后序遍历法:如果二叉树为空,则返回。否则(1)后序遍历左子树(2)后序遍历右子树(3)访问根节点,得到后序序列。

通过访问不同的遍历序列,可以得到不同的节点序列,通常在计算机中利用不同的遍历方法读出代数表达式,以便在计算机中对代数表达式进行操作。

2.3 离散数学在生物信息学中的应用

生物信息学是现代计算机科学中一个崭新的分支,它是计算机科学与生物学相结合的产物。目前,在美国有一个国家实验室sandia国家实验室,

主要进行组合编码理论和密码学的研究,该机构在美国和国际学术界有很高的地位。另外,由于dna是离散数学中的序列结构,美国科学院院士,近代离散数学的奠基人rota教授预言,生物学中的组合问题将成为离散数学的一个前沿领域。而且,ibm公司也将成立一个生物信息学研究中心。在1994年美国计算机科学家阿德勒曼公布了dna计算机的理论,并成功地运用dna计算机解决了一个有向哈密尔顿路径问题,这一成果迅速在国际产生了巨大的反响,同时也引起了国内学者的关注。dna计算机的基本思想是:以dna碱基序列作为信息编码的载体,利用现代分子生物学技术,在试管内控制酶作用下的dna序列反应,作为实现运算的过程;这样,以反应前dna序列作为输入的数据,反应后的dna序列作为运算的结果,dna计算机几乎能够解决所有的np

完全问题。

2.4离散数学在门电路设计中的应用

在数字电路中，离散数学的应用主要体现在数理逻辑部分的使用。在数字电路中广于使用的逻辑代数即为布尔代数。逻辑代数中的逻

辑运算与、或、非、异或与离散数学中的合取，析取、否定、异或（排斥或）相对应。

数字电路的学习重点在于掌握电路设计技术，在设计门电路时，要求设计者根据给出的具体逻辑问题，求出实现这一逻辑功能的逻辑

电路。一般的设计过程为如下：

首先，进行逻辑抽象.分析给定的逻辑问题，确定输入、输出变量,一般把引起事件的原因作为输入变量，把事件的结果作为输出变量。

再以二值逻辑的0、1两种状态分别代表变量的两种不同状态，并根

据给定的因果关系列出逻辑真值表。于是，这个实际的逻辑问题被

抽象成一个逻辑函数了，而且这个逻辑函数是以真值表形式给出的。然后根据真值表写出逻辑函数式。在这一步的主要工作为对逻辑函

数进行化简和变换，此时采用的方法一般为使用逻辑代数公式，即

离散数学中的命题演算公式将命题公式直接进行化简；或者用卡诺

图法进行化简；或者同时采用两种方法，互相验证结果是否最简。

但在一般情况下，在真值表中变量较多，逻辑函数式较为复杂时，

我们采用卡诺图法更为方便快捷，且出错率更低。在得到最简逻辑

函数式后，选定器件类型，开始构建实际电路。在对所用器件种类

有所限制或使用中规模集成电路构建设计好的电路时，需要把函数

式变换为适当的形式。此时，我们将采用命题等值演算对函数式进

行变换，变换的结果通常为合取范式和析取范式，以便使用最少的

器件和最简单的连线。

2、总结

总之，离散数学无处不在，它的主要应用就是在各种复杂关系中找

出最优的方案。所以离散数学完全可以看成是一门量化的关系学，

一门量化了的运筹学，一门量化了的管理学。现在我国每一所大学

的计算机专业都

开设离散数学课程,正因为离散数学在计算机科学中的重要应用,可以

说没有离散数学就没有计算机理论,也就没有计算机科学。所以,应努

力学习离散数学,推动离散数学的研究,使它在计算机中有着更为广泛

的应用。

参考文献：

【1】离散数学耿素云、屈婉玲、张立昂编著清华大学出版社

【2】离散数学及其应用（美）kenneth h.rosen著袁崇义屈婉玲

王捍贫刘田译

【3】《离散离散数学及其应用》

【4】百度百科“离散数学”词条傅彦著学出版社电子科技大