(完整版)离散数学及其应用(课后习题)

a t a t i m e an dA l lt h i ng si nt h ei r be i ng ar eg oo df o r so me t hi n 3-5.1 列出所有从X={a,b,c}到Y={s}的关系。

解：Z 1={<a,s>}Z 2={<b,s>} Z 3={<c,s>}Z 4={<a,s>,<b,s>} Z 5={<a,s>,<c,s>} Z 6={<b,s>,<c,s>}Z 7={<a,s>,<b,s>,<c,s>}3-5.2 在一个有n 个元素的集合上，可以有多少种不同的关系。

解 因为在X 中的任何二元关系都是X ×X 的子集，而X ×X=X 2中共有n 2个元素，取0个到n 2个元素，共可组成22n 个子集，即22|)(|n X X =⨯℘。

3-5.3 设A ＝{6：00，6：30,7：30，…, 9：30,10：30}表示在晚上每隔半小时的九个时刻的集合，设B={3,12,15,17}表示本地四个电视频道的集合,设R 1和R 2是从A 到B 的两个二元关系，对于二无关系R 1，R 2，R 1∪R 2，R 1∩R 2，R 1⊕R 2和R 1-R 2可分别得出怎样的解释。

解：A ×B 表示在晚上九个时刻和四个电视频道所组成的电视节目表。

R 1和R 2分别是A ×B 的两个子集，例如R 1表示音乐节目播出的时间表，R 2是戏曲节日的播出时间表，则R 1∪R 2表示音乐或戏曲节目的播出时间表，R 1∩R 2表示音乐和戏曲一起播出的时间表，R 1⊕R 2表示音乐节目表以及戏曲节目表，但不是音乐和戏曲一起的节日表，R 1-R 2表示不是戏曲时间的音乐节目时间麦。

3-5.4 设L 表示关系“小于或等于”，D 表示‘整除”关系,L 和D 刀均定义于解：L={<1,2>,<1,3>,<1,6>,<2,3>,<2,6>, <3,6>,<1,1>,<2,2>,<3,3>,<6,6>}D={<1,2>,<1,3>,<1,6>,<2,6>,<3,6>,<1,1>,<2,2>,<3,3>,<6,6>} L ∩D={<1,2>,<1,3>,<1,6>,<2,6>,<3,6>,<1,1>,<2,2>,<3,3>,<6,6>}3-5.5对下列每一式，给出A 上的二元关系，试给出关系图：a){<x,y>|0≤x ∧y ≤3}，这里A={1,2,3,4}；b){<x,y>|2≤x,y ≤7且x 除尽y ,这里A ＝{n|n ∈N ∧n ≤10}c) {<x,y>|0≤x-y<3}，这里A={0,1,2,3,4}；d){<x,y>|x,y 是互质的}，这里A={2,3,4,5,6}解：a) R={<0,0>,<0,1>,<0,2>,<0,3>, <1,0>,<1,1>,<1,2>,<1,3>, <2,0>,<2,1>,<2,2>,<2,3>, <3,0>,<3,1>,<3,2>,<3,3>,} 其关系图b) R={<2,0>,<2,2>,<2,4>,<2,6>,<3,0>,<3,3>,<3,6>, <4,0>,<4,4>, <5,0>,<5,5>,i m e an dA l lt h in gs in th ei r be i ng ar eg oo df o rsa）若R1和R2是自反的，则R1○R2也是自反的；b）若R1和R2是反自反的，则R1○R2也是反自反的；c）若R1和R2是对称的，则R1○R2也是对称的；d）若R1和R2是传递的，则R1○R2也是传递的。

离散数学及应用课后习题答案【篇一：离散数学及其应用图论部分课后习题答案】p165:习题九1、给定下面4个图（前两个为无向图，后两个为有向图）的集合表示，画出它们的图形表示。

（1）g1??v1,e1?，v1?{v1,v2,v3,v4,v5}，e1?{(v1,v2),(v2,v3),(v3,v4),(v3,v3),(v4,v5)} （2）g2??v2,e2?，v2?v1，e1?{(v1,v2),(v2,v3),(v3,v4),(v4,v5),(v5,v1)} （3）d1??v3,e3?,v3?v1,e3?{?v1,v2?,?v2,v3?,?v3,v2?,?v4,v5?,?v5,v 1?} （4）d2??v4,e4?,v4?v1,e3?{?v1,v2?,?v2,v5?,?v5,v2?,?v3,v4?,?v4,v 3?} 解答：（1）（2）10、是否存在具有下列顶点度数的5阶图？若有，则画出一个这样的图。

（1）5，5，3，2，2；（2）3，3，3，3，2；（3）1，2，3，4，5；（4）4，4，4，4，4 解答：（1）（3）不存在，因为有奇数个奇度顶点。

14、设g是n(n?2)阶无向简单图，g是它的补图，已知?(g)?k1,?(g)?k2，求?(g)，(g)。

解答：?(g)?n?1?k2；?(g)?n?1?k1。

15、图9.19中各对图是否同构？若同构，则给出它们顶点之间的双射函数。

解答：（c）不是同构，从点度既可以看出，一个点度序列为4，3，3，3，3而另外一个为4，4，3，3，1（d）同构，同构函数为12f(x)345解答：（1）三条边一共提供6度；所以点度序列可能是x?ax?bx?c x?dx?e16、画出所有3条边的5阶简单无向图和3条边的3阶简单无向图。

①3，3，0，0，0，0；②3，2，1，0，0，0；③3，1，1，1，0，0；④2，2，2，0，0，0；⑤2，2，1，1，0，0；⑥2，1，1，1，1，0；⑦1，1，1，1，1，1；由于是简单图，①②两种情形不可能图形如下：（2）三条边一共提供6度，所以点度序列可能为①3，3，0；②3，2，1；③2，2，2 由于是简单图，①②两种情形不可能21、在图9.20中，下述顶点序列是否构成通路？哪些是简单通路？哪些是初级通路？哪些是回路？哪些是简单回路？哪些是初级回路？（1）a,b,c,d,b,e；（2）a,b,e,d,b,a；（3）a,d,c,e,b；（4）d,b,a,c,e;（5）a,b,c,d,e,b,d,c；（6）a,d,b,e,c,b,d；（7）c,d,a,b,c；（8）a,b,c,e,b 解答：（1）构成通路，且为初级通路，因为点不重复（2）构成了回路，但是不为简单回路和初级回路，因为有重复的边(a,b) （3）构成了初级通路，因为点不重复；（4）不构成通路，因为边(a,c)不存在；（5）构成通路，但是不为简单通路和初级通路，因为有重复的边(d,c) （6）构成了回路，但是不为简单回路和初级回路，因为有重复的边(d,b) （7）构成了初级通路；（8）简单通路，但是不为初级通路，有重复边。

1.3.1习题1.1解答1设S = {2，a，{3}，4}，R ={{a}，3，4，1}，指出下面的写法哪些是对的，哪些是错的？{a}∈S,{a}∈R,{a,4,{3}}⊆S,{{a},1,3,4}⊂R,R=S,{a}⊆S,{a}⊆R,φ⊆R,φ⊆{{a}}⊆R⊆E,{φ}⊆S,φ∈R,φ⊆{{3},4}。

解：{a}∈S ，{a}∈R ，{a，4，{3}} ⊆ S ，{{a}，1，3，4 } ⊂ R ，R = S ，{a}⊆S ，{a}⊆ R ，φ⊆ R ，φ⊆ {{a}} ⊆ R ⊆ E ，{φ} ⊆ S ，φ∈R ，φ⊆ {{3}，4 } 2写出下面集合的幂集合{a，{b}}，{1，φ}，{X，Y，Z}解：设A={a，{b}}，则ρ(A)={ φ，{a}，{{b}}，{a，{b}}}；设B={1，φ}，则ρ(B)= { φ，{1}，{φ}，{1，φ}}；设C={X，Y，Z}，则ρ(C)= { φ，{X}，{Y}，{Z}，{X，Y }，{X，Z }，{ Y，Z }，{X，Y，Z}}；3对任意集合A，B，证明：(1)A⊆B当且仅当ρ(A)⊆ρ(B)；(2)ρ(A)⋃ρ(B)⊆ρ(A⋃B)；(3)ρ(A)⋂ρ(B)=ρ(A⋂B)；(4)ρ(A-B) ⊆(ρ(A)-ρ(B)) ⋃{φ}。

举例说明：ρ(A)∪ρ(B)≠ρ( A∪B)证明：(1)证明：必要性，任取x∈ρ(A)，则x⊆A。

由于A⊆B，故x⊆B，从而x∈ρ(B)，于是ρ(A)⊆ρ(B)。

充分性，任取x∈A，知{x}⊆A，于是有{x}∈ρ(A)。

由于ρ(A)⊆ρ(B)，故{x}∈ρ(B)，由此知x∈B，也就是A⊆B。

（2）证明：任取X∈ρ(A)∪ρ(B)，则X∈ρ(A)或X∈ρ(B)∴X⊆A或X⊆B∴X⊆(A∪B)∴X∈ρ(A∪B)所以ρ(A)∪ρ(B) ⊆ρ( A∪B)（3）证明：先证ρ(A)∩ρ(B) ⊆ρ( A∩B)任取X∈ρ(A)∩ρ(B)，则X∈ρ(A)且X∈ρ(B)∴X⊆A且X⊆B∴X⊆ A∩B∴X∈ρ( A∩B)所以ρ(A)∩ρ(B) ⊆ρ( A∩B)再证ρ( A∩B) ⊆ρ(A)∩ρ(B)任取Y∈ρ(A∩B)，则Y⊆ A∩B∴Y⊆A且Y⊆B∴Y∈ρ(A)且Y∈ρ(B)∴Y∈ρ(A)∩ρ(B)所以ρ( A∩B) ⊆ρ(A)∩ρ(B)故ρ(A)∩ρ(B) = ρ( A∩B)得证。

《离散数学》课后习题答案《离散数学》简介1、集合论部分：集合及其运算、二元关系与函数、自然数及自然数集、集合的基数2、图论部分：图的基本概念、欧拉图与哈密顿图、树、图的矩阵表示、平面图、图着色、支配集、覆盖集、独立集与匹配、带权图及其应用3、代数结构部分：代数系统的基本概念、半群与独异点、群、环与域、格与布尔代数4、组合数学部分：组合存在性定理、基本的计数公式、组合计数方法、组合计数定理5、数理逻辑部分：命题逻辑、一阶谓词演算、消解原理离散数学被分成三门课程进行教学，即集合论与图论、代数结构与组合数学、数理逻辑。

教学方式以课堂讲授为主，课后有书面作业、通过学校网络教学平台发布课件并进行师生交流。

《离散数学》学科内容随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。

离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。

由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型;又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。

离散数学是传统的逻辑学，集合论(包括函数)，数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数(包括代数系统，群、环、域等)，布尔代数，计算模型(语言与自动机)等汇集起来的一门综合学科。

离散数学的应用遍及现代科学技术的诸多领域。

离散数学也可以说是计算机科学的基础核心学科，在离散数学中的有一个著名的典型例子-四色定理又称四色猜想，这是世界近代三大数学难题之一，它是在1852年，由英国的一名绘图员弗南西斯格思里提出的，他在进行地图着色时，发现了一个现象，“每幅地图都可以仅用四种颜色着色，并且共同边界的国家都可以被着上不同的颜色”。

1-1，1-2（1）解：a)是命题，真值为T。

b)不是命题。

c)是命题，真值要根据具体情况确定。

d)不是命题。

e)是命题，真值为T。

f)是命题，真值为T。

g)是命题，真值为F。

h)不是命题。

i)不是命题。

（2）解：原子命题：我爱北京天安门。

复合命题：如果不是练健美操，我就出外旅游拉。

（3）解：a)(┓P ∧R)→Qb)Q→Rc)┓Pd)P→┓Q（4）解：a)设Q:我将去参加舞会。

R:我有时间。

P:天下雨。

Q (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。

b)设R:我在看电视。

Q:我在吃苹果。

R∧Q:我在看电视边吃苹果。

c) 设Q:一个数是奇数。

R:一个数不能被2除。

（Q→R）∧(R→Q):一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。

(5) 解：a)设P：王强身体很好。

Q：王强成绩很好。

P∧Qb)设P：小李看书。

Q：小李听音乐。

P∧Qc)设P：气候很好。

Q：气候很热。

P∨Qd)设P： a和b是偶数。

Q：a+b是偶数。

P→Qe)设P：四边形ABCD是平行四边形。

Q ：四边形ABCD的对边平行。

P Qf)设P：语法错误。

Q：程序错误。

R：停机。

（P∨ Q）→ R(6) 解：a)P:天气炎热。

Q:正在下雨。

P∧Qb)P:天气炎热。

R:湿度较低。

P∧Rc)R:天正在下雨。

S:湿度很高。

R∨Sd)A:刘英上山。

B:李进上山。

A∧Be)M:老王是革新者。

N:小李是革新者。

M∨Nf)L:你看电影。

M:我看电影。

┓L→┓Mg)P:我不看电视。

Q:我不外出。

R:我在睡觉。

P∧Q∧Rh)P:控制台打字机作输入设备。

Q:控制台打字机作输出设备。

P∧Q1-3（1）解：a)不是合式公式，没有规定运算符次序（若规定运算符次序后亦可作为合式公式）b)是合式公式c)不是合式公式（括弧不配对）d)不是合式公式（R和S之间缺少联结词）e)是合式公式。

（2）解：a）A是合式公式，(A∨B)是合式公式，(A→(A∨B))是合式公式。

离散数学课后习题答案1.3.1习题1.1解答1设S = {2，a，{3}，4}，R ={{a}，3，4，1}，指出下⾯的写法哪些是对的，哪些是错的？{a}∈S,{a}∈R,{a,4,{3}}?S,{{a},1,3,4}?R,R=S,{a}?S,{a}?R,φ?R,φ?{{a}}?R?E,{φ}?S,φ∈R,φ?{{3},4}。

解：{a}∈S ，{a}∈R ，{a，4，{3}} ? S ，{{a}，1，3，4 } ? R ，R = S ，{a}?S ，{a}? R ，φ? R ，φ? {{a}} ? R ? E ，{φ} ? S ，φ∈R ，φ? {{3}，4 }2写出下⾯集合的幂集合{a，{b}}，{1，φ}，{X，Y，Z}解：设A={a，{b}}，则ρ(A)={ φ，{a}，{{b}}，{a，{b}}}；设B={1，φ}，则ρ(B)= { φ，{1}，{φ}，{1，φ}}；设C={X，Y，Z}，则ρ(C)= { φ，{X}，{Y}，{Z}，{X，Y }，{X，Z }，{ Y，Z }，{X，Y，Z}}；3对任意集合A，B，证明：(1)A?B当且仅当ρ(A)?ρ(B)；(2)ρ(A)?ρ(B)?ρ(A?B)；(3)ρ(A)?ρ(B)=ρ(A?B)；(4)ρ(A-B) ?(ρ(A)-ρ(B)) ?{φ}。

举例说明：ρ(A)∪ρ(B)≠ρ( A∪B)证明：(1)证明：必要性，任取x∈ρ(A)，则x?A。

由于A?B，故x?B，从⽽x∈ρ(B)，于是ρ(A)?ρ(B)。

充分性，任取x∈A，知{x}?A，于是有{x}∈ρ(A)。

由于ρ(A)?ρ(B)，故{x}∈ρ(B)，由此知x∈B，也就是A?B。

（2）证明：任取X∈ρ(A)∪ρ(B)，则X∈ρ(A)或X∈ρ(B)∴X?A或X?B∴X?(A∪B)∴X∈ρ(A∪B)所以ρ(A)∪ρ(B) ?ρ( A∪B)（3）证明：先证ρ(A)∩ρ(B) ?ρ( A∩B)任取X∈ρ(A)∩ρ(B)，则X∈ρ(A)且X∈ρ(B)∴X?A且X?B∴X? A∩B∴X∈ρ( A∩B)所以ρ(A)∩ρ(B) ?ρ( A∩B)再证ρ( A∩B) ?ρ(A)∩ρ(B)任取Y∈ρ(A∩B)，则Y? A∩B∴Y?A且Y?B∴Y∈ρ(A)且Y∈ρ(B)∴Y∈ρ(A)∩ρ(B)所以ρ( A∩B) ?ρ(A)∩ρ(B)故ρ(A)∩ρ(B) = ρ( A∩B)得证。

习题一1.下列句子中,哪些是命题？在是命题的句子中,哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？（1）中国有四大发明.答：此命题是简单命题，其真值为 1.（2）5 是无理数.答：此命题是简单命题，其真值为 1.（3）3 是素数或 4 是素数.答：是命题，但不是简单命题，其真值为1.（4）2x+ <3 5 答：不是命题.（5）你去图书馆吗？答：不是命题.（6）2 与3 是偶数.答：是命题，但不是简单命题，其真值为0.（7）刘红与魏新是同学.答：此命题是简单命题，其真值还不知道.（8）这朵玫瑰花多美丽呀！答：不是命题.（9）吸烟请到吸烟室去！答：不是命题.（10）圆的面积等于半径的平方乘以π.答：此命题是简单命题，其真值为 1.（11）只有6 是偶数，3 才能是2 的倍数.答：是命题，但不是简单命题，其真值为0.（12）8 是偶数的充分必要条件是8 能被3 整除.答：是命题，但不是简单命题，其真值为0.（13）2008 年元旦下大雪.答：此命题是简单命题，其真值还不知道.2.将上题中是简单命题的命题符号化.解:（1）p：中国有四大发明.（2）p: 是无理数.（7）p:刘红与魏新是同学.（10）p:圆的面积等于半径的平方乘以π.（13）p:2008 年元旦下大雪.3.写出下列各命题的否定式,并将原命题及其否定式都符号化,最后指出各否定式的真值.（1）5 是有理数.答：否定式：5 是无理数. p：5 是有理数.q：5 是无理数.其否定式q 的真值为1.（2）25 不是无理数.答：否定式：25 是有理数. p：25 不是无理数. q：25 是有理数. 其否定式q 的真值为1.（3）2.5 是自然数.答：否定式：2.5 不是自然数. p：2.5 是自然数. q：2.5 不是自然数. 其否定式q 的真值为1.（4）ln1 是整数.答：否定式：ln1 不是整数. p：ln1 是整数. q：ln1 不是整数. 其否定式q 的真值为1.4.将下列命题符号化，并指出真值.（1）2 与5 都是素数答：p：2 是素数，q：5 是素数，符号化为p q∧ ，其真值为 1.（2）不但π是无理数，而且自然对数的底e 也是无理数.答：p：π 是无理数，q：自然对数的底e 是无理数，符号化为p q∧ ，其真值为1.（3）虽然2 是最小的素数，但2 不是最小的自然数.答：p：2 是最小的素数，q：2 是最小的自然数，符号化为p q∧¬ ，其真值为1.（4）3 是偶素数.答：p：3 是素数，q：3 是偶数，符号化为p q∧ ，其真值为0.（5）4 既不是素数，也不是偶数.答：p：4 是素数，q：4 是偶数，符号化为¬ ∧¬p q，其真值为0.5.将下列命题符号化，并指出真值.（1）2 或3 是偶数.（2）2 或4 是偶数.（3）3 或5 是偶数.（4）3 不是偶数或4 不是偶数.（5）3 不是素数或4 不是偶数.答: p：2 是偶数，q：3 是偶数，r:3 是素数，s:4 是偶数, t:5 是偶数(1)符号化: p q∨ ，其真值为1.(2)符号化：p r∨ ，其真值为1.(3)符号化：r t∨ ，其真值为0.(4)符号化：¬ ∨¬q s，其真值为1.(5)符号化：¬ ∨¬r s，其真值为0.6.将下列命题符号化.（1）小丽只能从筐里拿一个苹果或一个梨.答：p：小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨，符号化为: p q∨ .（2）这学期，刘晓月只能选学英语或日语中的一门外语课.答：p：刘晓月选学英语，q：刘晓月选学日语，符号化为: (¬ ∧ ∨ ∧¬p q)(p q) .7.设p：王冬生于1971 年，q：王冬生于1972 年，说明命题“王冬生于1971 年或1972年”既可以化答:列出两种符号化的真值表：p q0 0 0 00 1 1 11 0 1 11 1 0 1根据真值表,可以判断出,只有当p 与q 同时为真时两种符号化的表示才会有不同的真值,但结合命题可以发现,p 与q 不可能同时为真,故上述命题有两种符号化方式.8.将下列命题符号化,并指出真值., 就有；（1）只要, 则；（2）如果, 才有；（3）只有, 才有；（4）除非, 否则；（5）除非（6）仅当.答:设p: , 则: ; 设q: , 则: .符号化真值（1） 1（2） 1（3）0（4）0（5）0（6） 1 ：俄罗斯位于南半球,q：亚洲人口最多,将下面命题用自然语言表述（1）；（2）；；（3）；（4）；（5）；（6）；（7）.答:根据题意,p 为假命题,q 为真命题.自然语言真值（1）只要俄罗斯位于南半球,亚洲人口就最多 1 （2）只要亚洲人口最多,俄罗斯就位于南半球0 （3）只要俄罗斯不位于南半球,亚洲人口就最多 1 （4）只要俄罗斯位于南半球，亚洲人口就不是最多 1 （5）只要亚洲人口不是最多，俄罗斯就位于南半球 1 （6）只要俄罗斯不位于南半球，亚洲人口就不是最多0 （7）只要亚洲人口不是最多，俄罗斯就不位于南半球 1（1）；（2）；（3）；（4）.答:根据题意,p 为真命题,q 为假命题.自然语言真值（1）9 是 3 的倍数当且仅当英语与土耳其相邻0 （2）9 是 3 的倍数当且仅当英语与土耳其不相邻 1 （3）9 不是3 的倍数当且仅当英语与土耳其相邻 1（4） 9 不是 3 的倍数当且仅当英语与土耳其不相邻11. 将下列命题符号化,并给出各命题的真值： （1） 若 2+2=4,则地球是静止不动的； （2） 若 2+2=4,则地球是运动不止的； （3） 若地球上没有树木,则人类不能生存；（4） 若地球上没有水,则 是无理数.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,反之亦然.答:设 p:2+2=4,q:3+3=6.符号化真值 (1)1(2)(3)(4)113. 将下列命题符号化,并讨论各命题的真值： （1） 若今天是星期一,则明天是星期二； （2） 只有今天是星期一,明天才是星期二；命题 1命题 2 符号化 真值 （1） p:2+2=4 q:地球是静止不动的（2） p:2+2=4 q:地球是静止不动的1 （3） p:地球上有树木 q:人类能生存1（4）p:地球上有树木q:人类能生存1（3）今天是星期一当且仅当明天是星期二；（4）若今天是星期一,则明天是星期三.答:设p:今天是星期一,q:明天是星期二,r:明天是星期三.将下列命题符号化：（1）刘晓月跑得快,跳得高；（2）老王是山东人或者河北人；（3）因为天气冷,所以我穿了羽绒服；（4）王欢与李乐组成一个小组；（5）李欣与李末是兄弟；（6）王强与刘威都学过法语；（7）他一面吃饭,一面听音乐；（8）如果天下大雨,他就乘班车上班；（9）只有天下大雨,他才乘班车上班；（10）除非天下大雨,否则他不乘班车上班；（11）下雪路滑,他迟到了；（12）2 与4 都是素数,这是不对的；（13）“2 或 4 是素数,这是不对的”是不对的.答:(6) p:王强学过法语q:刘威学过法语-(7) p:他吃饭q:他听音乐-(8) p:天下大雨q:他乘车上班-(9) p:天下大雨q:他乘车上班-(10) p:天下大雨q:他乘车上班-(11) p:下雪q:路滑r:他迟到了(12) p:2 是素数q:4 是素数-(13) p:2 是素数q:4 是素数-15.设p：2+3=5.q：大熊猫产在中国.r:太阳从西方升起. 求下列符合命题的真值：（1）（2）（3）（4）解：p真值为1，q 真值为1，r 真值为0.（1）0，（2）0，（3）0，（4）116.当p,q 的真值为0,r,s 的真值为1 时,求下列各命题公式的真值：（1）（2）（3）（4）解：（1）0，（2）0，（3）0，（4）117.判断下面一段论述是否为真：“ 是无理数.并且,如果3 是无理数,则也是无理数.另外,只有6 能被2 整除,6 才能被4 整除.”解：p: 是无理数q: 3 是无理数r:是无理数s: 6 能被2 整除t：6 能被 4 整除符号化为: ，该式为重言式，所以论述为真。

可编辑修改精选全文完整版离散数学习题答案习题一：P121.判断下列句子哪些是命题？在是命题的句子中，哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？(1)中国有四大发明。

(2)5是无理数。

(3)3是素数或4是素数。

(4)x2+3<5，其中x是任意实数。

(5)你去图书馆吗？(6)2与3都是偶数。

(7)刘红与魏新是同学。

(8)这朵玫瑰花多美丽呀！(9)吸烟请到吸烟室去！(10)圆的面积等于半径的平方乘π。

(11)只有6是偶数，3才能是2的倍数。

(12)8是偶数的充分必要条件是8能被3整除。

(13)2025年元旦下大雪。

1、2、3、6、7、10、11、12、13是命题。

在上面的命题中，1、2、7、10、13是简单命题；1、2、10是真命题；7的真值现在还不知道。

2.将上题中是简单命题的命题符号化。

(1)p：中国有四大发明。

(2)q：5是无理数。

(7)r：刘红与魏新是同学。

(10)s：圆的面积等于半径的平方乘π。

(1)t：2025年元旦下大雪。

3.写出下列各命题的否定式，并将原命题及其否定式都符号化，最后指出各否定式的真值。

“5是有理数”的否定式是“5不是有理数”。

解：原命题可符号化为：p：5是有理数。

其否定式为：非p。

非p的真值为1。

4.将下列命题符号化，并指出真值。

(1)2与5都是素数。

(2)不但π是无理数，而且自然对数的底e也是无理数。

(3)虽然2是最小的素数，但2不是最小的自然数。

(4)3是偶素数。

(5)4既不是素数，也不是偶数。

a：2是素数。

b：5是素数。

c：π是无理数。

d：e是无理数。

f：2是最小的素数。

g：2是最小的自然数。

h：3是偶数。

i：3是素数。

j：4是素数。

k：4是偶数。

解：（1）到（5）的符号化形式分别为a∧b，c∧d，f∧非g，h∧i，非j∧非k。

这五个复合命题的真值分别为1，1，1，0，0。

5.将下列命题符号化，并指出真值。

a：2是偶数。

b：3是偶数。

c：4是偶数。

离散数学及算法（曹晓东，原旭版） 课后作业题答案第一章 命题逻辑1．第7页第3题（1）解：逆命题：如果我去公园，则天不下雨；反命题：如果天下雨，则我不去公园；逆反命题：如果我不去公园，则天下雨了。

（2）解：（此题注意：P 仅当Q 翻译成P Q →）逆命题：如果你去，那么我逗留。

反命题：如果我不逗留，那么你没去。

逆反命题：如果你没去，那么我不逗留。

（3）解：逆命题：如果方程n n n x y z +=无整数解，那么n 是大于2的正整数。

反命题：如果n 不是大于2的正整数，那么方程n n n xy z +=有整数解。

逆反命题：如果方程n n n x y z +=有整数解，那么n 不是大于2的正整数。

（4）解：逆命题：如果我不完成任务，那么我不获得更多的帮助。

反命题：如果我获得了更多的帮助，那么我能完成任务。

逆反命题：如果我能完成任务，那么我获得了更多的帮助。

2．第15页第1题（4）解：(())P Q P T ⌝⌝∨→⌝↔()()P Q P Q ⌝∧↔⌝∨⌝()()P Q P Q ⇔⌝∨⌝↔⌝∨⌝ （重言式）（9）解：P P Q F Q T ∧⌝→⇔→⇔（重言式）（10）解：P Q Q T Q Q ∨⌝→⇔→⇔（可满足式）3．第16页第5题（2）证明：(())P Q P ⌝⌝∨→⌝(())()P Q P P Q PP Q PP P QF QF ⇔⌝∨∨⌝⇔⌝∨∧⇔⌝∧⌝∧⇔⌝∧∧⌝⇔∧⌝⇔因此，(())P Q P F ⌝⌝∨→⌝↔，得证。

（4）证明：()()P P P P →⌝∧⌝→()()P P P P P P F⇔⌝∨⌝∧∨⇔⌝∧⇔因此，()()P P P P F →⌝∧⌝→↔，得证。

4．第16页第6题（1）P Q P Q ∧⇒→证明：设P Q ∧为真，那么P 为真，并且Q 为真，因此P Q →为真。

所以P Q P Q ∧⇒→。

（2）()()()P Q R P Q P R →→⇒→→→证明：设()()P Q P R →→→为假，于是P Q →为真，P R →为假。

离散数学（第⼆版）课后习题答案详解（完整版）习题⼀1.下列句⼦中,哪些是命题？在是命题的句⼦中,哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？（1）中国有四⼤发明.答：此命题是简单命题，其真值为 1.（2）5 是⽆理数.答：此命题是简单命题，其真值为 1.（3）3 是素数或 4 是素数.答：是命题，但不是简单命题，其真值为1.（4）2x+ <3 5 答：不是命题.（5）你去图书馆吗？答：不是命题.（6）2 与3 是偶数.答：是命题，但不是简单命题，其真值为0.（7）刘红与魏新是同学.答：此命题是简单命题，其真值还不知道.（8）这朵玫瑰花多美丽呀！答：不是命题.（9）吸烟请到吸烟室去！答：不是命题.（10）圆的⾯积等于半径的平⽅乘以π.答：此命题是简单命题，其真值为 1.（11）只有6 是偶数，3 才能是2 的倍数.答：是命题，但不是简单命题，其真值为0.（12）8 是偶数的充分必要条件是8 能被3 整除.答：是命题，但不是简单命题，其真值为0.（13）2008 年元旦下⼤雪.答：此命题是简单命题，其真值还不知道.2.将上题中是简单命题的命题符号化.解:（1）p：中国有四⼤发明.（2）p: 是⽆理数.（7）p:刘红与魏新是同学.（10）p:圆的⾯积等于半径的平⽅乘以π.（13）p:2008 年元旦下⼤雪.3.写出下列各命题的否定式,并将原命题及其否定式都符号化,最后指出各否定式的真值.（1）5 是有理数.答：否定式：5 是⽆理数. p：5 是有理数.q：5 是⽆理数.其否定式q 的真值为1.（2）25 不是⽆理数.答：否定式：25 是有理数. p：25 不是⽆理数. q：25 是有理数. 其否定式q 的真值为1.（3）2.5 是⾃然数.答：否定式：2.5 不是⾃然数. p：2.5 是⾃然数. q：2.5 不是⾃然数. 其否定式q 的真值为1.（4）ln1 是整数.答：否定式：ln1 不是整数. p：ln1 是整数. q：ln1 不是整数. 其否定式q 的真值为1.4.将下列命题符号化，并指出真值.（1）2 与5 都是素数答：p：2 是素数，q：5 是素数，符号化为p q∧，其真值为 1.（2）不但π是⽆理数，⽽且⾃然对数的底e 也是⽆理数.答：p：π是⽆理数，q：⾃然对数的底e 是⽆理数，符号化为p q∧，其真值为1.（3）虽然2 是最⼩的素数，但2 不是最⼩的⾃然数.答：p：2 是最⼩的素数，q：2 是最⼩的⾃然数，符号化为p q∧? ，其真值为1.（4）3 是偶素数.答：p：3 是素数，q：3 是偶数，符号化为p q∧，其真值为0.（5）4 既不是素数，也不是偶数.答：p：4 是素数，q：4 是偶数，符号化为? ∧?p q，其真值为0.5.将下列命题符号化，并指出真值.（1）2 或3 是偶数.（2）2 或4 是偶数.（3）3 或5 是偶数.（4）3 不是偶数或4 不是偶数.（5）3 不是素数或4 不是偶数.答: p：2 是偶数，q：3 是偶数，r:3 是素数，s:4 是偶数, t:5 是偶数(1)符号化: p q∨，其真值为1.(2)符号化：p r∨，其真值为1.(3)符号化：r t∨，其真值为0.(4)符号化：? ∨?q s，其真值为1.(5)符号化：? ∨?r s，其真值为0.6.将下列命题符号化.（1）⼩丽只能从筐⾥拿⼀个苹果或⼀个梨.答：p：⼩丽从筐⾥拿⼀个苹果，q：⼩丽从筐⾥拿⼀个梨，符号化为: p q∨ .（2）这学期，刘晓⽉只能选学英语或⽇语中的⼀门外语课.答：p：刘晓⽉选学英语，q：刘晓⽉选学⽇语，符号化为: (? ∧∨∧?p q)(p q) .7.设p：王冬⽣于1971 年，q：王冬⽣于1972 年，说明命题“王冬⽣于1971 年或1972年”既可以化答:列出两种符号化的真值表：合命题可以发现,p 与q 不可能同时为真,故上述命题有两种符号化⽅式.8.将下列命题符号化,并指出真值., 就有；（1）只要, 则；, 才有；（3）只有, 才有；（4）除⾮, 否则；（5）除⾮（6）仅当.答:设p: , 则: ; 设q: , 则: .（1）；（2）；；（3）；（4）；（5）；（6）；（7）.答:根据题意,p 为假命题,q 为真命题.（1）；（2）；（3）；（4）.答:根据题意,p 为真命题,q 为假命题.（1）若2+2=4,则地球是静⽌不动的；（2）若2+2=4,则地球是运动不⽌的；（3）若地球上没有树⽊,则⼈类不能⽣存；（4）若地球上没有⽔,则是⽆理数.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,反之亦然.答:设p:2+2=4,q:3+3=6.（1）若今天是星期⼀,则明天是星期⼆；（2）只有今天是星期⼀,明天才是星期⼆；（3）今天是星期⼀当且仅当明天是星期⼆；（4）若今天是星期⼀,则明天是星期三.答:设p:今天是星期⼀,q:明天是星期⼆,r:明天是星期三.（1）刘晓⽉跑得快,跳得⾼；（2）⽼王是⼭东⼈或者河北⼈；（3）因为天⽓冷,所以我穿了⽻绒服；（4）王欢与李乐组成⼀个⼩组；（5）李欣与李末是兄弟；（6）王强与刘威都学过法语；（7）他⼀⾯吃饭,⼀⾯听⾳乐；（8）如果天下⼤⾬,他就乘班车上班；（9）只有天下⼤⾬,他才乘班车上班；（10）除⾮天下⼤⾬,否则他不乘班车上班；（11）下雪路滑,他迟到了；（12）2 与4 都是素数,这是不对的；（13）“2 或 4 是素数,这是不对的”是不对的.答:q：⼤熊猫产在中国.r:太阳从西⽅升起. 求下列符合命题的真值：（1）（2）（3）（4）解：p真值为1，q 真值为1，r 真值为0.（1）0，（2）0，（3）0，（4）116.当p,q 的真值为0,r,s 的真值为1 时,求下列各命题公式的真值：（1）（2）（3）（4）解：（1）0，（2）0，（3）0，（4）117.判断下⾯⼀段论述是否为真：“ 是⽆理数.并且,如果3 是⽆理数,则也是⽆理数.另外,只有6 能被2 整除,6 才能被4 整除.”解：p: 是⽆理数q: 3 是⽆理数r:是⽆理数s: 6 能被2 整除t：6 能被 4 整除符号化为: ，该式为重⾔式，所以论述为真。

习题一1.判断下列语句是否是命题，为什么？若是命题，判断是简单命题还是复合命题？(1)离散数学是计算机专业的一门必修课。

(2)李梅能歌善舞。

(3)这朵花真美丽！(4)３＋２＞６。

(5)只要我有时间，我就来看你。

(6)x＝５。

(7)尽管他有病，但他仍坚持工作。

(8)太阳系外有宇宙人。

(9)小王和小张是同桌。

(10)不存在最大的素数。

解在上述10个句子中，(3)是感叹句，因此它不是命题。

(6)虽然是陈述句，但它没有确定的值，因此它也不是命题。

其余语句都是可判断真假的陈述句，所以都是命题。

其中：(1)、(4) 、(8) 、(9) 、是简单命题，、(2) 、(5) 、(7)、(10) 是复合命题。

2.判断下列各式是否是命题公式，为什么？(1)(P→(P∨Q))。

(2)(⌝P→Q)→(Q→P)))。

(3)((⌝P→Q)→(Q→P))。

(4)(Q→R∧S)。

(5)(P∨QR)→S。

(6)((R→(Q→R)→(P→Q))。

解 (1)是命题公式。

(2)不是命题公式，因为括号不配对。

(3)是命题公式。

(4)是命题公式。

(5)不是命题公式，因为QR没有意义。

(6)不是命题公式，因为R→(Q→R)→(P→Q) 没有意义。

3.将下列命题符号化：(1)我们不能既划船又跑步。

(2)我去新华书店，仅当我有时间。

(3)如果天下雨，我就不去新华书店。

(4)除非天不下雨，我将去新华书店。

(5)张明或王平都可以做这件事。

(6)“2或4是素数，这是不对的”是不对的。

(7)只有休息好，才能工作好。

(8)只要努力学习，成绩就会好的。

(9)大雁北回，春天来了。

(10)小张是山东人或河北人。

解 (1)符号化为⌝(P ∧Q )，其中，P ：我们划船，Q ：我们跑步。

(2)符号化为Q →R ，其中，R ：我有时间，Q ：我去新华书店。

(3)符号化为P →⌝Q ，其中，P ：天下雨，Q ：我去新华书店。

(4)符号化为⌝P →Q ，其中，P ：天下雨，Q ：我去新华书店。

作业答案：数理逻辑部分P14：习题一1、下列句子中，哪些是命题？在是命题的句子中，哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？（3 答：简单命题，真命题。

（9）吸烟请到吸烟室去！ 答：不是命题。

（12）8是偶数的充分必要条件是8能被3整除。

答：复合命题，假命题。

14、讲下列命题符号化。

（6）王强与刘威都学过法语。

答：:p 王强学过法语；:q 刘威学过法语。

符号化为：p q ∧（10）除非天下大雨，他就乘班车上班。

答：:p 天下大雨；:q 他乘班车上班。

符号化为：p q →（13）“2或4是素数，这是不对的”是不对的。

答：:p 2是素数；:q 4是素数。

符号化为：(())p q ⌝⌝∨15、设:p 2+3=5. :q 大熊猫产在中国。

:r 太阳从西方升起。

求下列复合命题的真值。

（2）(())r p q p →∧↔⌝（4）()(())p q r p q r ∧∧⌝↔⌝∨⌝→ 解答： p 真值为1；q 真值为1；r 真值为0.（2）p q ∧真值为1；()r p q →∧真值为1；p ⌝真值为0；所以(())r p q p →∧↔⌝真值为0.（4）p q r ∧∧⌝真值为1，p q ⌝∨⌝真值为0，()p q r ⌝∨⌝→真值为1；所以()(())p q r p q r ∧∧⌝↔⌝∨⌝→真值为1.19、用真值表判断下列公式的类型。

（4）()()p q q p →→⌝→⌝所以为重言式。

（7）所以为可满足式。

P36:习题二3、用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出其成真赋值。

（1）()p q q ⌝∧→ 解答：()(())(())()10p q q p q q p q q p q q ⌝∧→⇔⌝⌝∧∨⇔⌝⌝∨⌝∨⇔⌝⌝∨⌝∨⇔⌝⇔所以为永假式。

（2）(())()p p q p r →∨∨→ 解答：(())()(())()()()1()1p p q p r p p q p r p p q p r p r →∨∨→⇔⌝∨∨∨⌝∨⇔⌝∨∨∨⌝∨⇔∨⌝∨⇔ 所以因为永真式。