离散数学课后习题答案一

0 0 1 1 1 1

1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1 0 1 0 1 1 1 0 0 1 1 0 3. 在下面各推理中没有给出结论。请对每个推理前提给出两个结论，使其中之一是有

效的，而另一个不是有效的。

（1）只有天气热，我才去游泳。我正在游泳。所以…… （2）只要天气热，我就去游泳。我没去游泳。所以……

（3）除非天气热并且我有时间，我才去游泳。天气不热或我没有时间。所以…… 解 略

4. 用真值表法或等价演算法证明下列推理 （1）?A?A?B （2）B?A?B

（3）?(A?B)?A

（4）?(A?B)??B

（5）(A?B)?(C?D)?A?C?B?D （6）(A?B)?(C?D)?A?C?B?D （7）(A?B)?(C?D)?(A?C)?B?D

（8）(A?B)?(C?D)?(?B??D)??A??C 证明 略

5. 用演绎推理法证明下列推理

（1）p?(q?r)，p，q?r?s （2）p?q，?(q?r)，r??p （3）p?q?p?(p?q)

（4）q?p，q?s，s?t，t?r?p?q （5）p?r，q?s，p?q?r?s （6）?p?r，?q?s，p?q?t?(r?s) （7）p?(q?r)，s?p，q?s?r （8）(p?q)?(r?s)，(s?t)?u?p?u （9）p??q，?r?q，r??s??p （10）p?q，p?r，q?s?r?s

证明 （1）、（3）、（5）、（7）、（9）、（10）略 （2） （1）p

（2）q?q

（3）q

（4）?(q?r) （5）?q??r （6）?r （7）r

（8）0

根据所学定理，有p?q，?(q?r)，r??p。 （4） （1）t?r （2）t

（3）s?t

（4）s

（5）q?s

（6）q

（7）q?p

（8）p

（9）p?q （6） （1）p?q （2）p

（3）?p?r （4）r （5）q

（6）?q?s

（7）s

（8）r?s

（9）t?(r?s)

（8） （1）p

（2）p?q

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

（4）r?s （5）s

（6）s?t

附加前提 P规则

T规则，（1），（2） P规则 E规则，（4） T规则，（3），（5） P规则

T规则，（6），（7）

P规则 T规则，（1） P规则

T规则，（2），（3） P规则

T规则，（4），（5） P规则

T规则，（6），（7） T规则，（6），（8） P规则 T规则，（1） P规则

T规则，（2），（3） T规则，（1） P规则

T规则，（5），（6） T规则，（4），（7） T规则，（8） 附加前提 T规则，（1） P规则

T规则，（2），（3） T规则，（4） T规则，（5）

（7）(s?t)?u （8）u

P规则

T规则，（6），（7）

根据所学定理，有(p?q)?(r?s)，(s?t)?u?p?u。 6. 用演绎推理法证明下列说法不可能同时成立。 （1）如果王平因病缺了许多课，那么他考试将不及格。 （2）如果王平考试不及格，则他没有学到知识。 （3）如果王平读了许多书，则他学到了许多知识。 （4）王平因病缺了许多课，而且在家读了许多书。

解 设p：王平因病缺了许多课，q：王平考试将不及格，r：王平没有学到知识，

s：王平读了许多书，则上面的4种说法可以分别符号化为：

p?q，q?r，s??r，p?s

而这几个逻辑式子是相互矛盾的，即永假式0是它们的逻辑结论：

（1）p?q （2）q?r （3）p?r （4）s??r （5）r??s （6）p??s （7）p?s （8）p （9）s （10）?s （11）0

7. 用演绎推理法证明下列推理过程：如果今天是星期六，我们就要去长城或故宫玩；如果故宫游人太多，我们就不去故宫玩；今天是星期六；故宫游人太多。所以我们去长城玩。

解 略

8. 用演绎推理法证明下列推理过程：如果小王是理科学生，则他的数学成绩一定很好；如果小王不是文科学生，他一定是理科学生；小王的数学成绩不好。所以小王是文科学生。

解 略

9. 用演绎推理法证明下列推理过程：如果王平到过受害者房间并且11点以前没有离开，则王平犯谋杀罪；王平曾到过受害者房间；如果王平在11点以前离开，门卫会看见他；门卫没有看见他。所以王平犯了谋杀罪。

解 设p：王平到过受害者房间，q：王平11点以前没有离开受害者房间，r：王平

P规则 P规则

T规则，（1），（2） P规则 E规则，（4） T规则，（3），（5） P规则 T规则，（7） T规则，（7） T规则，（6），（8） T规则，（9），（10）

犯谋杀罪，s：门卫会看见王平，则上面推理的逻辑前提是：

p?q?r，p，?q?s，?s

要证明的逻辑结论是：r。

（1）?q?s （2）?s?q （3）?s （4）q （5）p

P规则 E规则，（1） P规则

T规则，（2），（3） P规则

T规则，（4），（5） P规则

T规则，（6），（7）

（6）p?q

（7）p?q?r （8）r

§1.6 对偶原理

1. 求下列公式的对偶式。 （1）p?(?q?r)?s

（2）?(p?q)?(p?r) （4）(p?1)??q?0

（3）?(p??q)?(p?0)?1

习题1.6

解 （1）的对偶式为：p?(?q?r)?s （2）的对偶式为：?(p?q)?(p?r) （3）的对偶式为：?(p??q)?(p?1)?0 （4）的对偶式为：(p?0)??q?1

2. 根据对偶原理，写出与下列等价式对应的另一个等价式。 （1）A?(B?C)?(A?B)?(A?C) （2）A?(A?B)?A （3）A?0?0 （4）A?1?A

（5）?A?(?B?C)??(A?B)?C

（6）(?A?(?B?C))?(B?C)?(A?C)?C 解 （1）A?(B?C)?(A?B)?(A?C) （2）A?(A?B)?A （3）A?1?1 （4）A?0?A

（5）?A?(?B?C)??(A?B)?C

（6）(?A?(?B?C))?(B?C)?(A?C)?C