离散数学第二版全答案

2.1 等值式

一、等值式的概念

两公式什么时候代表了同一个命题呢？抽象地看，它们的真假取值完全相同时即代表了相同的命题。

设公式A,B共同含有n个命题变项，可能A或B有哑元，若A与B有相同的真值表，则说明在2n个赋值的每个赋值下，A与B的真值都相同。于是等价式AB应为重言式。

定义2.1 设A,B式两个命题公式，若A,B构成的等价式A

B是等值的，记作A

B.

B为重言式，则称A与

定义中给出的符号不是联结词符，它是用来说明A与B等值（AB是重言式）的一种记法，因而是元语言符号。此记号在下文中频繁出现，千万不要将它与混为一谈，同时也要注意它与一般等号=的区别。 判断等值式有如下方法： 1.真值表

2.等值演算

3.范式

二、用真值表判断公式的等值

例2.1 判断下面两个公式是否等值：

┐(p∨q)与┐p∧┐q

解 用真值表法判断┐(p∨q)

(┐p∧┐q)是否为重言式。此等价式的真值表如表2.1

(┐p∧┐q)。

所示，从表中可知它是重言式，因而┐(p∨q)与┐p∧┐q等值，即┐(p∨q)

其实，在用真值表法判断AB是否为重言式时，真值表的最后一

2.13 设解释I为：个体域DI ={-2,3,6},一元谓词F（X）：X（X）：X>5,R(X):X（1） 解：

x(F(x)x(F(x)(F(-2) ((-2((1 00

(2)

x(R(x)

F(x))

G(5) G(5)

F(3)) (( 3

(R(6)7)

(3

F(6))3))

03)

7。在I下求下列各式的真值。

3，G

G(x)) G(x)) G(-2))

(F(3) ((3((0 G(3)) 3)

(F(6) (3>5)) 0))

G(6)) ((6

3)

(6<5))

(-2>5))

0))

0))((1 0

解：x(R(x)(R(-2)((-2

F(x))

F(-2)) (R(3)7)

(-2

3))

G(5)

7)

(( 6

(63)) (5>5) (1 10

1) 1

(1 0

1) 0

(1

0)

0

(3)解：

x(F(x)x(F(x)

G(x)) G(x))

(F(3)

((3 (0

G(3)) 3) 1)

(F(6) (3>5))

G(6)) ((6

3)

(6>5))

(F(-2) ((-2(1

G(-2)) 3)

(-2>5)) (1

0)

0)

1 1

1 1

2.14 求下列各式的前束范式，要求

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

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

.WORD 完美格式.

离散数学答案 屈婉玲版

第二版 高等教育出版社课后答案 第一章部分课后习题参考答案

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∧

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. 将下列命题符号化：

(1) 所有的火车都比某些汽车快。

(2) 任何金属都可以溶解在某种液体中。 (3) 至少有一种金属可以溶解在所有液体中。 (4) 每个人都有自己喜欢的职业。 (5) 有些职业是所有的人都喜欢的。

解 (1) 取论域为所有交通工具的集合。令

T(x):x是火车， C(x):x是汽车， F(x,y):x比y跑得快。

“所有的火车都比某些汽车快”可以符号化为?x(T(x)??y(C(y)?F(x,y)))。 (2) 取论域为所有物质的集合。令

M(x):x是金属， L(x):x是液体， D(x,y):x可以溶解在y中。

“任何金属都可以溶解在某种液体中” 可以符号化为?x(M(x)??y(L(y)?D(x,y)))。 (3) 论域和谓词与(2)同。“至少有一种金属可以溶解在所有液体中” 可以符号化为

?x(M(x)??y(L(y)?D(x,y)))。

(4) 取论域为所有事物的集合。令

M(x):x是人， J(x):x是职业， L(x,y):x喜欢y。

“每个人都有自己喜欢的职业” 可以符号化为?x(M(x)??y(J(y)?L(x,y))) (5)论域和谓词与(4)同。“有些

第一章

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

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

试卷二试题与答案

一、填空 20% （每小题2分）

1、 P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为

；“虽然你努力了，但还是失败了”的翻译为 。 2、论域D={1，2}，指定谓词P

P (1,1) T P (1,2) T P (2,1) F P (2,2) F 则公式?x?yP(y,x)真值为 。 2、 设S={a1 ，a2 ，?，a8}，Bi是S的子集，则由B31所表达的子集是 。

3、 设A={2，3，4，5，6}上的二元关系R?{?x,y?|x?y?x是质数}，则R=

（列举法）。

R的关系矩阵MR=

。

5、设A={1，2，3}，则A上既不是对称的又不是反对称的关系

R=

第1章 集合、映射与运算

1.1 集合的有关概念

习题1.1

1.用列举法表示下列集合: (1){x|x?R,x2?5x?6?0}.

(2){2x|x?N}.

解 (1) {x|x?R,x2?5x?6?0}?{2,3}. (2) {2x|x?N}?{0,2,4,6,...,2x,...}.

2. 写出35的所有因数集合及D35.

解 35的所有因数集合为{-35, -7, -5, -1, 1, 5, 7, 35}，D35 = {1, 5, 7, 35}. 3.比较集合?,{?}和{{?}}的不同之处.

解 ?是空集，它里面没有元素; {?}是由空集?组成的集合，它里面有一个元素?; {{?}}里面有一个元素为{?}，但{?}与?是不同的.

4.判定下列断言是否成立，说明理由: (1) ???.

(2) ???. (3) ??{?}.

(4) ??{?}.

解 (1)成立，因为空集是任意集合的子集. (2)不成立，因为空集中不含任意元素. (3)成立，因为空集是任意集合的子集. (4)成立，因为{?}含有元素?.

5.设A和B是集合，试举出使A?B且A?B同时成立的例子.

解 例如A?{a,b}，B?{a,b,{a,b},c}，这时A?