(完整版)离散数学答案(尹宝林版)第一章习题解答

解 有。p既是关于p的主析取范式，又是关于p的主合取范式。

27.求下列公式的主范式，进而判断其是否永真式、永假式、可满足式。 (1) ?p?q?r (2) (p?q)?r

(3) ?p??q?(p??q) (4) p?(p?q?(?q?r)) (5) (p?q?r)?(?p??q??r) (6) p?q?(?p??q)

解 (1) ?p?q?r??(?p?q)?r?p??q?r

?p?q?r的主合取范式是p??q?r，包含一个极大项，因此它是非永真的可满

足式。

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

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

(p?q)?r的主合取范式是(p?q?r)?(p??q?r)?(?p??q?r)，包含了

三个极大项，因此它是非永真的可满足式。

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

?p??q?(p??q)的主合取范式为p?q，包含了一个极大项，因此它是非永真

的可满足式。

(4) p?(p?q?(?q?r))?p?(?p?q?(??q?r))?1

p?(p?q?(?q?r))的主合取范式为1，不包含任何极大项，因此它是永真式。

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

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

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

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

(p?q?r)?(?p??q??r)的主析取范式为(?p??q??r)?(p?q?r)，

包含了两个极小项，因此它是非永真的可满足式。 (6) p?q?(?p??q)

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

p?q?(?p??q)的主合取范式为(p?q)?(p??q)?(?p?q)?(?p??q)，

包含了所有的四个极大项，因此它是永假式。 28.用主范式证明下列等值式。

(1) (p?q)?p?q?(?p?p)?(r?p) (2) (p?q)?(p?r)?p?q?r 式

(p??q??r)?(p??q?r))?(p?q??r)?(p?q?r)，因此，

解 (1) (p?q)?p?q??(?p?q)?(p?q)

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

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

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

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

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

(p?q)?p?q和(?p?p)?(r?p)等值于同一个关于p,q,r的主析取范

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

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

?(?p?q?(r??r))?(?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)?(?p?r)

?(?p?q?(r??r))?(?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)?(p?r)和p?q?r的主合取范式相同，所以，

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

29.判断以下关系是否成立，并说明理由。 (1) p?q,?p|?q (2) p?q, ,q|?p

(3) p1?q1,p2?q2,p1?p2|?q1?q2 (4) p?q,q?p|?p?q

(5) p?q?r,p?q??r|?p?q?r

解 (1) 若真值赋值v使得v(p?q)?v(?p)?1，则v(q)?1。所以p?q,?p|?q。 (2) 真值赋值v?(p/0,q/1)使得v(p?q)?v(p?q)?v(q)?1，但v(p)?0，所以

p?q,p?q,q|?/p。

(3) 若真值赋值v使得v(p1?q1)?v(p2?q2)?v(p1?p2)?1，则v(p1)?v(p2)?1，因而v(q1)?v(q2)?1，v(q1?q2)?1。所以p1?q1,p2?q2,p1?p2|?q1?q2。 (4) 真值赋值v?(p/0,q/0)使得v(p?q)?v(q?p)?1，但v(p?q)?0。所以

p?q,q?p|?/p?q。

(5) 真值赋值v?(p/0,q/1,r/0)使得v(p?q?r)?v(p?q??r)?1，但

v(p?q?r)?0。所以p?q?r,p?q??r|?/p?q?r。

30.判断以下公式组成的集合是否可满足，并说明理由。 (1) (p?q)?(s??r)，?(s??r)

(2) p1，?p1?p2，?p1??p2?p3,…，?p1????pn?pn?1,… (3) p?q，?p??q，p?q

解 (1) 可满足。真值赋值(p/1,q/0,r/1,s/0)满足它。

(2) 可满足。若真值赋值v使得v(pi)?1,i?1,2,?，则v满足它。 (3) 可满足。真值赋值(p/0,q/1)满足它。

31.设A,B,C是任意公式。A?B|?C当且仅当A|?C且B|?C。

证明1 （?）设A?B|?C。任取满足A的真值赋值v，则v(A?B)?1，因为A?B|?C，所以v(C)?1。这表明A|?C。任取满足B的真值赋值v，则v(A?B)?1，因为A?B|?C，所以v(C)?1。这表明B|?C。

（?）设A|?C且B|?C。任取满足A?B的真值赋值v，则v(A)?1或v(B)?1。 ① 若v(A)?1，因为A|?C，所以v(C)?1。 ② 若v(B)?1，因为B|?C，所以v(C)?1。 因此，A?B|?C。

证明2 A?B?C??(A?B)?C?(?A??B)?C

?(?A?C)?(?B?C)?(A?C)?(B?C)

A?B|?C

当且仅当A?B?C是永真式

当且仅当(A?C)?(B?C)是永真式 当且仅当A?C和B?C都是永真式 当且仅当A|?C且B|?C

32.设?1和?2是公式集合，B是公式，?2|?B，对于?2中每个公式A，?1|?A。证明：