离散数学习题解答耿素云屈婉玲北京大学出版社（供参考）

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

答

(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)?(?p??r)?(p?q?r)?(?p??q?(r??r)?(?p?(q??q)??r)?(p?(q??q)?(r??r))?((p??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)?(p??q??r)?(?p?q?r)?m0?m1?m2?m3?m4?m5?m6?m7所以是重言式，真值为000,001,010,011,100,101,110,111.

6.求下列公式的主析取范式，并求成真赋值： （1）?(q??p)??p

答：?(q??p)??p??(?q??p)??p?q?p??p?0，是矛盾式，所有赋值均为成真赋值。

（2）(p?q)?(?p?r)

答：(p?q)?(?p?r)?(p??p?r)?(q??p?r)?(?p?q?r)?M4，成假赋值为100.

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

答：(p?(p?q))?r?(?p?(p?q))?r?(?p?p?q?r?1，所以为重言式。所有赋值均为成真赋值。

7.求下列公式的主析取范式，再用主析取范式求主合取范式： （1）(p?q)?r

答：(p?q)?r?(p?q?(r??r))?((p??p)?(q??q)?r) （2）(p?q)?(q?r) 答：

(p?q)?(q?r)?(?p?q)?(?q?r)?(?p??q)?(?p?r)?(q??q)?(q?r)?(?p??q?(r??r))?(?p?(q??q)?r)?((p??p)?q?r)?(?p??q?r)?(?p??q??r)?(?p?q?r)?(p?q?r)

?m0?m1?m3?m7?M2?M4?M5?M68.求下列公式的主合取范式，再用主合取范式求主析取范式： （1）(p?q)?q

答：(p?q)?q??(p?q)?q??p??q?q?1?m0?m1?m2?m3

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

为重言式。

（2）(p?q)?r

答：(p?q)?r??((p?q)?(?p??q))?r?(?(p?q)??(?p??q))?r （3）?(r?p)?p?q

答：?(r?p)?p?q?r??p?p?q 因此为矛盾式.

9.用真值表求下面的公式的主析取范式. （1）(p?q)?(?p?r) 答：公式的真值表如下： 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 0 0 0 0 0 0 1 1 1 1 1 1 0 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 其成真赋值为001,010,011,100,101,110,111，所以其主析取范式为 （2）(p?q)?(p??q) 答：公式的真值表如下： 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 1 1 0 故其成真赋值为001，010. 所以其主析取范式为m1?m2. 10.用真值表求下面公式的主合取范式. （1）(p?q)?r

答：(p?q)?r?(p?r)?(q?r) （2）(p?q)?(q?r)

答：(p?q)?(q?r)?(?p?q)?(?q?r) 11.用真值表求下面公式的主析取范式和主合取范式.

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

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

0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 0 1 0 1 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 答：（1）由真值表可得成真赋值为011,101,111，故主析取范式为m3?m5?m7，主合取范式为M0?M1?M2?M4?M6

（2）由真值表可得无成假赋值，故主析取范式为

m0?m1?m2?m3?m4?m5?m6?m7，主合取范式为1.

（3）由真值表可得无成真赋值，故主析取范式为0，主合取范式为

M0?M1?M2?M3.

12.已知公式A含3个命题变项p,q,r，并且它的成真赋值为000，011，110，求A的主合取范式和主析取范式.

答：由题意得，A的主主合取范式为M1?M2?M4?M5?M7，主析取范式

m0?m3?m6.

13. 已知公式A含3个命题变项p,q,r，并且它的成真赋值为000，011，110，求A的主合取范式和主析取范式.

答：由题意得，A的主主合取范式为M2?M3?M6?M7，主析取范式

m0?m1?m5?m7.

14.已知公式A含n个命题变相p1,p2,......,pn，并且无成假赋值，求A的主合取范式. 答：A的主合取范式为1..

15.用主析取范式判断下列公式是否等值：

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

（1）(p?q)?r与q?(p?r) 答：(p?q)?r?(p??q)?r 所以上述公式不等值. （2）?(p?q)与?(p?q) 答：?(p?q)??p??q

16.用主合取范式判断下列公式是否等值. （1）p?(q?r)与?(p?q)?r 答：p?(q?r)?M6

（2）p?(q?r)与(p?q)?r 答：p?(q?r)?M6

17.将下列公式化成与之等值且仅含??,?,??中联结词的公式： （1）?(p?(q?(q?r)))

答：?(p?(q?(q?r)))??(?p?(q?(q?r))) （2）(p?q)??r

答：(p?q)??r，原式已满足题目要求. （3）p?(q?r)

答：p?(q?r)?(p?(q?r))?((?r)?p) 18.将下列公式化成与之等值且仅含{?,?}中联结词的公式： （1）p??q??r

答：此公式已经符合题目要求. （2）(p?r)?q

答：(p?r)?q?((p?r)?(r?p))?q （3）(p?(q?r))?q

答：(p?(q?r))?q?(?p?(q?r))?p