离散数学课后题目及答案

习题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）请给我一支笔！ （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?

第二章 命题逻辑

§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

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

数理逻辑习题

判断题

1．任何命题公式存在惟一的特异析取范式 （ √ ） 2． 公式p?(?p?q)是永真式 （ √ ） 3．命题公式(p?q)?p是永真式 （ √ ） 4．命题公式p??q?r的成真赋值为010 （ × ） 5．?xA(x)?B??x(A(x)?B) （ √ ）

6．命题“如果1＋2＝3，则雪是黑的”是真命题 （ × ） 7．p?(p?q)?p （ √ ）

8．?x(F(x)?G(x))是永真式 （ × ） 9．“我正在撒谎”是命题 （ × ） 10． ?xF(x)??xG(x)是永真式（ √ ）

11．命题“如果1＋2＝0，则雪是黑的”是假命题 （ × ） 12．p?(p?q)?p （ √ ）

13．?x(F(x)?G(x))是永假式 （ × ）

14．每个命题公式都有唯一的特异（主）合取范式 （ √ ） 15．若p:雪是黑色的，则公式p?q是永真式 （ √ ） 16．每个逻辑公式都有唯一的前束范式 （ × ） 17．公式p?q的特异（主）析取式为?p?q （ × ） 18．命题公式 ?p?(q?r)的成假赋值是110 （ √ ） 19．一阶逻辑公式?x(F(x)?G(x,y))是闭式（ × ）

单项选择题

第一章命题逻辑

习题1.11．解⑴不是陈述句，所以不是命题。

⑵x取值不确定，所以不是命题。

⑶问句，不是陈述句，所以不是命题。

⑷惊叹句，不是陈述句，所以不是命题。

⑸是命题，真值由具体情况确定。

⑹是命题，真值由具体情况确定。

⑺是真命题。

⑻是悖论，所以不是命题。

⑼是假命题。

2．解⑴是复合命题。设p：他们明天去百货公司；q：他们后

p∨。

天去百货公司。命题符号化为q

⑵是疑问句，所以不是命题。

⑶是悖论，所以不是命题。

⑷是原子命题。

⑸是复合命题。设p：王海在学习；q：李春在学习。命题符号化为p∧q。

⑹是复合命题。设p：你努力学习；q：你一定能取得优异成绩。p→q。

⑺不是命题。

⑻不是命题

⑼。是复合命题。设p：王海是女孩子。命题符号化为：?p。

1

3．解⑴如果李春迟到了，那么他错过考试。

⑵要么李春迟到了，要么李春错过了考试，要么李春通过了考试。

⑶李春错过考试当且仅当他迟到了。

⑷如果李春迟到了并且错过了考试，那么他没有通过考试。

4．解⑴?p→(q∨r)。⑵p→q。⑶q→p。⑷q → p。

习题1.2

1．解⑴是1层公式。

⑵不是公式。

⑶一层：p∨q，?p

二层：?p?q

所以，)

p?

?

∨是3层公式。

→

p

(

q

)

(q

⑷不是公式。

⑸(p→q)∧?(?q?( q→?r))是5层公式，

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

第一章命题逻辑

习题1.11．解⑴不是陈述句，所以不是命题。

⑵x取值不确定，所以不是命题。

⑶问句，不是陈述句，所以不是命题。

⑷惊叹句，不是陈述句，所以不是命题。

⑸是命题，真值由具体情况确定。

⑹是命题，真值由具体情况确定。

⑺是真命题。

⑻是悖论，所以不是命题。

⑼是假命题。

2．解⑴是复合命题。设p：他们明天去百货公司；q：他们后

p∨。

天去百货公司。命题符号化为q

⑵是疑问句，所以不是命题。

⑶是悖论，所以不是命题。

⑷是原子命题。

⑸是复合命题。设p：王海在学习；q：李春在学习。命题符号化为p∧q。

⑹是复合命题。设p：你努力学习；q：你一定能取得优异成绩。p→q。

⑺不是命题。

⑻不是命题

⑼。是复合命题。设p：王海是女孩子。命题符号化为：?p。

1

3．解⑴如果李春迟到了，那么他错过考试。

⑵要么李春迟到了，要么李春错过了考试，要么李春通过了考试。

⑶李春错过考试当且仅当他迟到了。

⑷如果李春迟到了并且错过了考试，那么他没有通过考试。

4．解⑴?p→(q∨r)。⑵p→q。⑶q→p。⑷q → p。

习题1.2

1．解⑴是1层公式。

⑵不是公式。

⑶一层：p∨q，?p

二层：?p?q

所以，)

p?

?

∨是3层公式。

→

p

(

q

)

(q

⑷不是公式。

⑸(p→q)∧?(?q?( q→?r))是5层公式，

1.1 命题及其表示法

1.下列陈述句中，（ ）不是命题。

A.2013年国庆节是星期天。 B.火星上有生物。 C.月球距离地球近。 D.上海是大城市。 2.下列命题中，（ ）是复合命题。

A.江山代有人才出。 B.我花开时百花杀。 C.春江水暖鸭先知。 D.万紫千红总是春。 3.下列命题中，（ ）是原子命题。

A.燕子飞回南方，春天来了。 B.天才是炼成的，而不是天生的。 C.暮春三月，江南草长。 D.哥白尼指出地球绕太阳转。 4.下列命题中，（ ）是原子命题。

A.王芳与王菲是姐妹。 B.王芳与王菲是三好学生。 C.王芳与王菲持有驾照。 D.王芳与王菲喜欢早睡早起。 5.下列命题中，（ ）是原子命题。

A.数学是科学的皇后，而数论是数学的皇后。 B.数学使人精细，逻辑使人善辩。 C.较大的偶数都可表示为两个素数的和。 D.数学是一种语言，也是一种工具。 6.判断一个语句是否为命题，首先看它是否为 陈述句 ，然后再看它是否具有唯一的 真值