离散数学课后答案详细

第一章 命题逻辑基本概念

课后练习题答案

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

（1）p∧q,其中，p:2是素数，q:5是素数,真值为1；

（2）p∧q,其中，p:是无理数，q:自然对数的底e是无理数,真值为1； （3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1； （4）p∧q,其中，p:3是素数，q:3是偶数,真值为0； （5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0.

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

（1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1； （2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1； （3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0； （4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1； （5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；

6.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨； （2）(p∧┐q)∨(┐p∧q),其中，p：刘晓月选学英语，q：刘晓月选学日语；.

7.因为p与q不能同时为真.

13.设p:今天是星期一，q:明天是星期二，r:明天是星期三： （1）p→q，真值为1（不会出现前件为真，后件为假的情况）； （2）q→p，真值为1（也不会出现前件为真，后件为假的情况）； （3）p

q，真值为1；

（4）p→r，若p为真，则p→r真值为0，否则，p→r真值为1.

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 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式

（5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例）

第二章 命题逻辑等值演算

本章自测答案

3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r)

答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1 所以公式类型为永真式

(3) P q r p∨q p∧r （p∨q）→(p∧r)

0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0

返回

0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1

所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)?(p→(q∧r))

(4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明（2）(p→q)∧(p→r)

? (?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r)

（4）(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q)

?(p∨?p)∧(p∨q)∧(?q∨?p) ∧(?q∨q) ?1∧(p∨q)∧?(p∧q)∧1 ?(p∨q)∧?(p∧q)

5.

: (1) (p→q)→(q∨p) (2) (p→q)∧q∧r (3) (p∨(q∧r))→(p∨q∨r) (1) (p→q)→(q∨p) ?(p∨q)∨(q∨p) ?p∧q∨q∨p

?p∧q∨q∨p (吸收律) ?(p∨p)∧q∨p∧(q∨q)?p∧q∨p∧q∨p∧q∨p∧q?m10∨m00∨m11∨m10?m0∨m2∨m3?↖(0, 2, 3). 成真赋值00, 10, 11.

(2) 主析取范式为0、 无成真赋值、 为矛盾式

(3) M0 ∨ M1 ∨ M2 ∨ M3 ∨ M4 ∨ M5 ∨ M6 ∨ M7.

(1)：

∨

∨

,成真赋值为00、10、11；

(2)：0，矛盾式，无成真赋值； (3)：

∨

∨

∨

∨

∨

∨

∨

,重言式，000、001、010、011、100、101、110、111全部为成真赋值；

6. (1) (q→p)∧p

?(q∨p)∧p ?q∧p∧p ?q∧0 ?0

?M0∧M1∧M2∧M3

这是矛盾式，成假赋值00,01,10,11 （2）M4，成假赋值100 （3）主合取范式为1，为重言式

7.(1)： (2)：

8.(1)：1? (2)： (3)： 11.(1)： (2)：

∨∨

∨∨∧

?∨∧

∧∨∧

∧∨.

∧∨

∧∨

； ?1；

∨∧∨?∧∨∨∧∨∨∧

,重言式； ∨∧

∨∧

∨∧

∨

；

∨∨

∨∨

∨∨

∨?

?∧

∧∧

∧∧

； ；

?0，矛盾式.

(3)：0? 12.A?

∧

∧∧∧?∨∨.

15.(1)(p→q)→r与q→(p→r) (2(p→q)→r ?(p∨q)∨r ?(p∨q)∨r ?p∧q∨r

?p∧q∧(r∨r)∨(p∨p)∧(q∨q)∧r

?p∧q∧r∨p∧q∧r∨p∧q∧r∨p∧q∧r∨p∧q∧r∨p∧q∧r = m101∨m100∨m111∨m101∨m011∨m001 ?m1∨m3∨m4∨m5∨m7 = ↖(1,4、5、7)。 而 q→(p→r) ?q∨(p∨r) ?q∨p∨r

?(p∨p)∧q∧(r∨r)∨p∧(q∨q)∧(r∨r)∨(p∨p)∧(q∨q) ∧r

?(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)

= m0∨m1∨m4∨m5∨m0∨m1∨m2∨m3∨m1∨m3∨m5∨m7 ?m0∨m1∨m2∨m3∨m4∨m5∨m7

?↖(01、2 3,4,5、 7)。两个公式的主吸取范式不同，所以(p→q) →r,q→(p→r)。 16.

(1 )(p→q)→r与q→(p→r) (2) (1) (p→q)(p∧q)与(p∨q)→r) ?m1∨m3∨m4∨m5∨m7 q→(p→r) ?m0∨m1∨m2∨m3∨m4∨m5∨m7 所以(p→q) →r) q→(p→r) (2)(p∧q) ?m0∨m1∨m2 ?

(p∨q) ?m0 所以(p∧q) (p∨q) 17

17合取范式判断下列公式是否等值： (1)p→(q→r)与(p∧q)∨r (2)p→(q→r)与(p→q) →r

(1) p→(q→r) ?M6(p∧q)∨r ?M6

所以p→(q→r)?(p∧q)∨r (2) p→(q→r) ?M6 (p → q) →r ?M0∧M1∧M2∧M6

所以p→(q→r) (p→q)→r q→(p→r)。

20将下列公式化成与之等值且仅含 {结构型式、 →} 中联结词的公式。

(3) (p∧q) ?r。注意到A?B ?(A→B)∧(B→A) 和 A∧B ?(A∨B) ?(A→B) 只 A∨B ?A→B。(p∧q)?r 10 ?(p∧q→r)∧(r→p∧q)?((p→q)→r)∧(r→(p→q)) ?(((p→q)→r)→(r→(p→q))) 注联结词越少、 公式越长。

2.21.证明： (1) (p↑q)?(q↑p)、(p↓q) ?(q↓p)。(p↑q) ?(p∧q) ?(q∧p) ?(q↑p)。(p↓q) ?(p∨q) ?(q∨p) ?(q↓p)。

第三章 命题逻辑的推理理论

本章自测答案

6.在解本题时，应首先将简单陈述语句符号化，然后写出推理的形式结构*，其次就是判断*是否为重言式，若*是重言式，推理就正确，否则推理就不正确，这里不考虑简单语句之间的内在联系

(1)、(3)、(6)推理正确，其余的均不正确，下面以(1)、(2)为例，证明(1)推理正确，(2)推理不正确 (1)设p:今天是星期一，q:明天是星期三，推理的形式结构为 (p→q)∧p→q(记作*1)

在本推理中，从p与q的内在联系可以知道，p与q的内在联系可以知道，p与q不可能同时为真，但在证明时，不考虑这一点，而只考虑*1是否为重言式.

可以用多种方法（如真值法、等值演算法、主析取式）证明*1为重言式，特别是，不难看出，当取A为p,B为q时，*1为假言推理定律，即 (p→q)∧p→q ? q

(2)设p:今天是星期一，q:明天是星期三，推理的形式结构为 (p→q)∧p→q(记作*2)

可以用多种方法证明*2不是重言式，比如，等值演算法、主析取范式（主和取范式法也可以）等 (p→q)∧q→p ?(┐p∨q) ∧q →p ?q →p ?┐p∨┐q ?

?

∨

∨

从而可知，*2不是重言式，故推理不正确，注意，虽然这里的p与q同时为真或同时为假，但不考虑内在联系时，*2不是重言式，就认为推理不正确.

9.设p:a是奇数，q:a能被2整除，r:a：是偶数 推理的形式结构为

(p→q┐)∧(r→q)→(r→┐p) (记为*)

可以用多种方法证明*为重言式，下面用等值演算法证明： (p→┐q)∧(r→q)→(r→┐p)

?(┐p∨┐q) ∨(q∨┐r)→(┐q∨┐r) (使用了交换律) ?(p∨q)∨(┐p∧r)∨┐q∨┐r

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库离散数学课后答案详细在线全文阅读。