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。证明：
?1|?B。
证明 任取满足?1的真值赋值v。对于?2中每个公式A，因为?1|?A，所以v(A)?1。这表明v满足?2。又因为?2|?B，所以v(B)?1。因此，?1|?B。 33.公式集合?不可满足当且仅当?|?0。
证明 （?）设?|?/0，则存在真值赋值v满足?且v(0)?0，因此?可满足。 （?）设?|?0。若?可满足，有真值赋值v满足?，由?|?0得出v(0)?1，这是不可能的。因此，?不可满足。
34.设n是正整数，??{p1?q1,?,pn?qn,p1???pn}?{?(qi?qj)|1?i?j?n}。证明：?|?(q1?p1)???(qn?pn)。
证明 设真值赋值v满足?，则v(p1???pn)?1，存在i?n使v(pi)?1。因为所以v(qi)?1。若1?j?i，因为v(?(qj?qi))?1，因此v(qj)?0。v(pi?qi)?1，若
i?j?n，因为v(?(qi?qj))?1，因此v(qj)?0。所以
v((q1?p1)???(qn?pn))?1。