离散数学习题解答(耿素云屈婉玲)北京大学出版社 下载本文

WORD格式.整理版

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

?m0?m1?m2?m3?m4?m5?m7 所以上述公式不等值. (2)?(p?q)与?(p?q) 答:?(p?q)??p??q ?m0?m1?m2 ?(p?q)??p??q ?m0

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

(2)p?(q?r)与(p?q)?r 答:p?(q?r)?M6

(p?q)?r=M0?M2?M6

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

答:?(p?(q?(q?r)))??(?p?(q?(q?r))) ?p??(?(q?r))

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

答:(p?q)??r,原式已满足题目要求. (3)p?(q?r)

优质.参考.资料

WORD格式.整理版

答:p?(q?r)?(p?(q?r))?((?r)?p)

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

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

答:(p?r)?q?((p?r)?(r?p))?q ?((?p?r)?(?r?p))?q ?(?(p??r)??(r??p))?q (3)(p?(q?r))?q

答:(p?(q?r))?q?(?p?(q?r))?p ??(p??(q?r))?p ??((p??(q?r))??p)

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

答:(?p??q)?r??(?(?p??q)??r) (2)(p?(q??p))?q?r

答:(p?(q??p))?q?r??(?(?p??(?q?p))??q??r)

(3)p?q??r

答:p?q??r??(?p??q?r)

?}中联结词的公式: 20.将下列公式化成与之等值且仅含{?,(1)(p?q)?r(2)(p??q)?r(3)(p?q)?r

答:(p?q)?r??(?p??q)?r??(p??q)?r?(p??q)?r (2)(p??q)?r

优质.参考.资料

WORD格式.整理版

答:(p??q)?r??(?(p??q)??r)??((p??q)??r) (3)(p?q)?r

答:(p?q)?r?(?(?p??q)?r)?(r??(?p??q))

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

21.证明:

(p?q)?(q?p). (1)(p?q)?(q?p),(p?(q?r))?((p?q)?r). (2)(p?(q?r))?((p?q)?r),证明:(1)p?q??(p?q)??(q?p)?q?p;

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

(2)令p?0,q?0,r?1则

p?(q?r)?1,(p?q)?r?0,p?(q?r)?1,(p?q)?r?0.,可知(p?(q?r))?((p?q)?r),(p?(q?r))?((p?q)?r).

22.从表2.6中,找出与下列公式等值的真值函数: (1)p?q

(2)p?q

(3)(p??q)?(?p?q) (4)?(p?q)

(2)(2)(2)(2)答:(1)F14;(2)F8;(3)F6;(4)F2

23.设A、B、C为任意的命题公式,证明: (1)等值关系有自反性:A?A

(2)等值关系有对称性:若A?B,则B?A

(3)等值关系有传递性:若A?B且B?C,则A?C

答:(1)A?A?(A?A)?(A?A)?A?A??A?A?1

(2)B?A?(?B?A)?(?A?B)?(?A?B)?(?B?A)?A?B (3)

优质.参考.资料

WORD格式.整理版

若A?B且B?C?(A?B)?(B?A)?(B?C)?(C?B)?(A?B)?(B?C)?(C?B)?(B?A)?(A?C)?(C?A)

?A?C即A?C24.设A、B为任意的命题公式,证明:?A??B当且仅当A?B 答:?A??B?(A??B)?(B??A)?(A?B)?(B?A)?A?B. 因此?A??B当且仅当A?B。

25.设A、B、C为任意的命题公式,(1)若A?C?B?C,举例说明A?B不一定成立。(2)若A?C?B?C,举例说明A?B不一定成立。由(1)、(2)可知,联结词

?与?不满足消去率。

答:(1)设A?p?1,B?q?0,C?r?1,则A?C?1?B?C?1

,但

A?1,B?0,二者不等价。

(2)设A?p?1,B?q?0,C?r?0,则A?C?0?B?C?0,但

A?1,B?0,二者不等价。

26.在上题(25)中,若已知A?C?B?C,在什么条件下,A?B一定成立?又若已知A?C?B?C,在什么条件下,A?B一定成立? 解:若C?0;则A?C?B?C,A?B一定成立。 若C?1;则A?C?B?C,A?B一定成立。

27.某电路中有一个灯泡和三个开关A、B、C。已知在且仅在下述四种情况下灯亮: (1)C的扳键向上,A、B的扳键向下。(2)A的扳键向上,B、C的扳键向下。(3)B、C的扳键向上,A的扳键向下。(4)A、B的扳键向上,C的扳键向下。 设F为1表示灯亮,p、q、r分别表示A、B、C的扳键向上。 (a)求F的主析取范式。

(b)在联结词完备集{?,?}上构造F。

?,?}上构造F。 (c)在联结词完备集{?, 答:(a)由题意知,灯亮的情况如下:

F?(p??q??r)?(?p??q?r)?(?p?q?r)?(p?q??r) ?m1?m3?m4?m6

(b)F?(p??q??r)?(?p??q?r)?(?p?q?r)?(p?q??r)

优质.参考.资料