离散数学课后题目及答案第二版

习题3.7

1. 列出关系{?a，b，c，d?|a，b，c，d?Z且a?b?c?d?6}中所有有序4元解 {?a，b，c，d?|a，b，c，d?Z且a?b?c?d?6}

??组。

?{?1,1,1,6?,?1,1,6,1?,?1,6,1,1?,?6,1,1,1?,?1,1,2,3?,?1,1,3,2?,?1,2,1,3?,?1,3,1,2?,

?1,2,3,1?,?1,3,2,1?,?2,3,1,1?,?3,2,1,1?,?2,1,3,1?,?3,1,2,1?,?2,1,1,3?,?3,1,1,2?

2. 列出二维表3.18所表示的多元关系中所有5元组。假设不增加新的5元组，找出二维表3.18所有的主键码。

表3.18 航班信息

航空公司 Nadir Acme Acme Acme Nadir Acme Nadir

解 略

3. 当施用投影运算?2,3,5到有序5元组?a，b，c，d?时你能得到什么？

解 略

4. 哪个投影运算用于除去一个6元组的第一、第二和第四个分量？

解 略

5. 给出分别施用投影运算?1,2,4和选择运算?航空公司＝Nadir到二维表3.18以后得到的表。 解 对航班信息二维表进行投影运算?2,3,5

§1.1 命题和逻辑连接词

习题1.1

1. 下列哪些语句是命题，在是命题的语句中，哪些是真命题，哪些是假命题，哪些命题的真值现在还不知道？

（1）中国有四大发明。

（2）你喜欢计算机吗？ （3）地球上海洋的面积比陆地的面积大。 （4）请回答这个问题！ （5）632=+。

（6）107<+x 。 （7）园的面积等于半径的平方乘以圆周率。 （8）只有6是偶数，3才能是2的倍数。

（9）若y x =，则z y z x +=+。

（10）外星人是不存在的。 （11）2020年元旦下大雪。

（12）如果311=+，则血就不是红的。 解 是真命题的有：（1）、（3）、(7)、 (9) 、（12） ；是假命题的有：（5）、 (8) ；是命题但真值现在不知道的有： (10)、 (11)；不是命题的有：（2）、（4）、（6）。

2. 令p 、q 为如下简单命题：p ：气温在零度以下。q ：正在下雪。用p 、q 和逻辑联接词符号化下列复合命题。

（1）气温在零度以下且正在下雪。

（2）气温在零度以下，但不在下雪。

（3）气温不在零度以下，也不在下雪。

（4）也许在下雪，也许气温在零度以下，也许既下雪气温又在零度以下。

（5）若气温在零度以下，那一定在下雪。

（6）也许气温在零度以下，也许在下雪，但如果气温在零度以上就不下雪。 （7）气温在零度以下是下雪的充分必要条件。

解 （1

第1章 习题解答

习题1.1

1. 下列句子中，哪些是命题？哪些不是命题？如果是命题，指出它的真值。 ⑴ 中国有四大发明。 ⑵ 计算机有空吗? ⑶ 不存在最大素数。 ⑷ 21+3＜5。

⑸ 老王是山东人或河北人。 ⑹ 2与3都是偶数。 ⑺ 小李在宿舍里。

⑻ 这朵玫瑰花多美丽呀! ⑼ 请勿随地吐痰!

⑽ 圆的面积等于半径的平方乘以?。 ⑾ 只有6是偶数，3才能是2的倍数。 ⑿ 雪是黑色的当且仅当太阳从东方升起。 ⒀如果天下大雨，他就乘班车上班。

解：⑴⑶⑷⑸⑹⑺⑽⑾⑿⒀是命题，其中⑴⑶⑽⑾是真命题，⑷⑹⑿是假命题，⑸⑺⒀的真值目前无法确定；⑵⑻⑼不是命题。

2. 将下列复合命题分成若干原子命题。 ⑴ 李辛与李末是兄弟。

⑵ 因为天气冷，所以我穿了羽绒服。 ⑶ 天正在下雨或湿度很高。 ⑷ 刘英与李进上山。

⑸ 王强与刘威都学过法语。

⑹ 如果你不看电影，那么我也不看电影。 ⑺我既不看电视也不外出，我在睡觉。 ⑻ 除非天下大雨，否则他不乘班车上班。 解：⑴本命题为原子命题；

⑵ p：天气冷；q：我穿羽绒服； ⑶ p：天在下雨；q：湿度很高； ⑷ p：刘英上山；q：李进上山；

⑸ p：王强学过法语；q：刘威学过法语； ⑹ p：你看电影；q：我看

屈婉玲版离散数学课后习题答案

1

第四章部分课后习题参考答案

3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值:

(1) 对于任意x,均有

2=(x+)(x

).

(2) 存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解：

F(x):

2=(x+)(x

).

G(x): x+5=9.

(1)在两个个体域中都解释为?xF(x)，在（a）中为假命题，在(b)中为真命题。

(2)在两个个体域中都解释为?xG(x)，在（a）(b)中均为真命题。

4. 在一阶逻辑中将下列命题符号化:

(1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解:

(1)F(x): x能表示成分数 H(x): x是有理数

命题符号化为: ??x(?F(x)?H(x)) (2)F(x): x是北京卖菜的人

1

屈婉玲版离散数学课后习题答案

2

H(x): x是外地人

命题符号化为: ??x(F(x)?H(x)) 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快.

(3) 不存在比所有火车都快的汽车. 解:

离散数学课后习题答案 (左孝凌版)

1-1，1-2 （1） 解：

a) b) c) d) e) f) g) h) i)

是命题，真值为T。 不是命题。

是命题，真值要根据具体情况确定。 不是命题。 是命题，真值为T。 是命题，真值为T。 是命题，真值为F。 不是命题。 不是命题。

（2） 解：

原子命题：我爱北京天安门。

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

a) b) c) d)

(┓P ∧R)→Q Q→R ┓P 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) b) c) d) e) f) (6) 解：

a) b) c) d) e) f) g)

P:天气炎热。Q:正在下雨。 P∧Q P:天气炎热。R:湿度较低。 P∧R R:天正在下雨。S:湿度很高。 R∨S A:刘英上山。B:李进上山。

第一章 命题演算基础

1.1 判断下列语句是否为命题，若是请翻译为符号公式；若不是说明由。

（1）请给我一支笔！ （2）火星上有生物。 （3）X?Y?8

（4）只有努力工作，方能把事情做好。

（5）如果嫦娥是虚构的，而圣诞老人也是虚构的，那么许多孩子受骗了。 解

（1）不为命题，因为它不是陈述句。

（2）是命题，用命题变元P表示该命题。

（3）不为命题，虽为陈述句，但不能判断其真假性。

（4）是命题。设P表示努力工作，则原句翻译为命题公式Q?P。 Q表示把事情做好，（5）是命题。设P表示嫦娥是虚构的，Q表示圣诞老人也是虚构的，R表示许多孩子受骗了，则原句翻译为(P?Q)?R。 1.2 试判定下列公式的永真性和可满足性。

（1）(P?Q)?(?P??(Q??R)) 解

（1）当P?T时，

原式=(T?Q)?(?T??(Q??R)) =Q?(F??(Q??R))

=Q?F =?Q

当Q=T时，上式=F；当Q?F时，上式=T，因此公式存在成真解释

(P,Q,R)?(T,F,?)，存在成假解释(P,Q,R)?(T,T,?)，故公式可满足，但非永真。

（2）?(P?Q)?((Q??R)??P) 解

当P?T时

原式=?(T?Q)?((Q?

屈婉玲版离散数学课后习题答案

第十章部分课后习题参考答案

4．判断下列集合对所给的二元运算是否封闭： （1） 整数集合Z和普通的减法运算。

封闭,不满足交换律和结合律，无零元和单位元

（2） 非零整数集合错误！未找到引用源。普通的除法运算。不封闭

（3） 全体n?n实矩阵集合错误！未找到引用源。（R）和矩阵加法及乘法运算，其中

n错误！未找到引用源。2。

封闭 均满足交换律，结合律，乘法对加法满足分配律； 加法单位元是零矩阵，无零元；

乘法单位元是单位矩阵，零元是零矩阵；

（4）全体n?n实可逆矩阵集合关于矩阵加法及乘法运算，其中n错误！未找到引用源。2。不封闭

（5）正实数集合错误！未找到引用源。和错误！未找到引用源。运算，其中错误！未找到引用源。运算定义为：

错误！未找到引用源。

不封闭 因为 1?1?1?1?1?1??1?R?

（6）n错误！未找到引用源。关于普通的加法和乘法运算。 封闭，均满足交换律，结合律，乘法对加法满足分配律 加法单位元是0，无零元；

乘法无单位元（n?1），零元是0；n?1单位元是1

（7）A = {a1,a2,?,an} 错误！未找到引用源。n错误！未找到引用源。运算定义如下：

错误！未找到引用

1-1，1-2 （1） 解：

a) 是命题，真值为T。 b) 不是命题。

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

e) 是命题，真值为T。 f) 是命题，真值为T。 g) 是命题，真值为F。 h) 不是命题。 i) 不是命题。 （2） 解：

原子命题：我爱北京天安门。

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

a) (┓P ∧R)→Q b) Q→R c) ┓P d) 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∧Q b) 设P：小李看书。Q：小李听音乐。P∧Q c) 设P：气候很好。Q：气候很热。P∨Q

d) 设P： a和b是偶数。Q：a+b是偶数。P→Q

e) 设P：四边形ABCD是平行四边形。Q ：四边形ABCD的对边平行。P?Q f

离散数学课后习题答案_(左孝凌版)

1-1，1-2 （1） 解：

a) b) c) d) e) f) g) h) i)

是命题，真值为T。 不是命题。

是命题，真值要根据具体情况确定。 不是命题。 是命题，真值为T。 是命题，真值为T。 是命题，真值为F。 不是命题。 不是命题。

（2） 解：

原子命题：我爱北京天安门。

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

a) b) c) d)

(┓P ∧R)→Q Q→R ┓P 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) b) c) d) 设P：王强身体很好。Q：王强成绩很好。P∧Q 设P：小李看书。Q：小李听音乐。P∧Q 设P：气候很好。Q：气候很热。P∨Q 设P： a和b是偶数。Q：a+b是偶数。P→Q

离散数学课后习题答案_(左孝凌版)

e) f) (6) 解：

a) b) c) d

第二章 命题逻辑

§2.2 主要解题方法

2.2.1 证明命题公式恒真或恒假

主要有如下方法：

方法一. 真值表方法。即列出公式的真值表，若表中对应公式所在列的每一取值全为1，这说明该公式在它的所有解释下都是真，因此是恒真的；若表中对应公式所在列的每

18

一取值全为0，这说明该公式在它的所有解释下都为假，因此是恒假的。

真值表法比较烦琐，但只要认真仔细，不会出错。

例2.2.1 说明 G= (P?Q?R)?(P?Q)?(P?R)是恒真、恒假还是可满足。

解：该公式的真值表如下：

P Q R P?QP?(P?QP?R G ?R Q ?R)?(P?Q) 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 表2.2.1

由于表2.2.1中对应公式G所在列的每一取值全为1，故

19

1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 G恒真。

方法二. 以基本等价式为基础，通过反复对一个公式的等价代换，使之最后转化为一个恒真式或恒假式，从而实现公式恒真或恒假的证明。

例2.2.2