离散数学课后习题合集(2)

当P?F时

原式=(??F??Q)?(Q?(?R?F)) =(F??Q)?(Q?F) =T?(Q?F) =Q

当Q?T时，上式=T；当Q?F时，上式=F。

因此，公式的成真解释为(P,Q,R)?(T,F,F),(F,T,?)；(P,Q,R)?(T,T,?),(T,F,T),(F,F,?)。

1.4 试写出下列公式的对偶式和内否式

（1）(?P?Q)?((Q??R)?P) （2）(P??Q)?((Q?R)??P) （3）?(P?Q)?((Q??R)??P) （4）(?P?Q)?((Q??R)??P) 解

（1） 内否式为(P??Q)?((?Q?R)??P) 消去“?”得式子?(?P?Q)?((Q??R)?P) 对偶式=?(?P?Q)?((Q??R)?P)

（2）内否式为(?P?Q)?((?Q??R)?P) 消去“?”得式子(?P??Q)?((Q?R)??P) 对偶式为(?P??Q)?((Q?R)??P)

（3）内否式为?(?P??Q)?((?Q?R)?P)

消去“?”得式子?(?P?Q)?(((?Q??R)?(Q?R))??P) 对偶式为?(?P?Q)?(((?Q??R)?(Q?R))??P)

（4）内否式为(P??Q)?((?Q?R)?P)

成假解释为

6

消去“?”得式子(P?Q)?((?Q??R)??P) 对偶式为(P?Q)?((?Q??R)??P) 1.5 试证明联结词集合{?,?}是完备的。

证明

因为， P?Q??P?Q P?Q??(P??Q)

所以，联结词集合??,??可以表示集合??,?,??。

又因为，联结词集合??,?,??是完备的，即??,?,??可以表示任何一个命题演算公式，所以??,??可以表示任何一个命题演算公式，故联结词集合??,??是完备的。 1.6 试证明联结词集合???,???不是完备的。

证明 设集合

???是完备的，则由联结词集合的完备性定义知

?P?f(P,Q,R,?)?P?Q?R??。当P,Q,R,?全取为真时，上式左边=F，右边

=T，矛盾。

因此???不是完备的。

设集合???是完备的，则由联结词集合的完备性定义知?P?f(P,Q,R,?)，其中f表示“?”。当P,Q,R,?全取为真时，上式左边=F，右边=T，矛盾。 因此???不是完备的。

1.7 试求下列公式的析取范式和合取范式

（1）(?P?Q)?(P??Q) 解

原式=?(?P?Q)?((P??Q)?(?P???Q)) =(P??Q)?(P??Q)?(?P?Q) =(P??Q)?(?P?Q)（析取范式） =((P??Q)??P)?((P??Q)?Q)

7

=(P??P)?(?P??Q)?(P?Q)?(?Q?Q) =(?P??Q)?(P?Q)（合取范式）

（2）(P?(Q??R))?(R?(Q?P)) 解

原式=?(?P?(?Q??R))?(?R?(?Q?P)) =(P?Q?R)?(P??Q??R)

=(P?P??Q??R)?(Q?P??Q??R)?(R?P??Q??R) =P??Q??R（合取范式和析取范式）

（3）?(P?Q)?((Q??R)??P) 解

原式=?(?P?Q)?((?Q??R)??P) =P??Q?(?P??Q??R)（合取范式） =(P??Q)?(?P??Q??R)

=((P??Q)??P)?((P??Q)??Q)?((P??Q)??R) =(P??Q)?(P??Q??R)（析取范式）

（4）(P?Q)?(?P??(Q??R)) 解

原式=?(P?Q)?(?P??(?Q??R)) =(?P?Q)?(?P?Q?R)

=(?P?Q)?(P??Q)?(?P?Q?R)（析取范式） =((?P?Q)?(P??Q))?(?P?Q?R)

=((?P?Q)?P)?((?P?Q)??Q))?(?P?Q?R)

=((?P?P)?(P?Q)?(?P??Q)?(Q??Q))?(?P?Q?R) =((P?Q)?(?P??Q))?(?P?Q?R)

8

=((P?Q)?(?P?Q?R))?((?P??Q)?(?P?Q?R)) =(P?Q??P)?(P?Q?Q)?(P?Q?R)?(?P??Q??P)? (?P??Q?Q)?(?P??Q?R)

=(P?Q)?(P?Q?R)?(?P??Q)?(?P??Q?R)（合取范式） 1.8 试求下列公式的主析取范式和主合取范式

（1）(?P?R)?(?P?(?Q?R)) 解

原式=?(??P?R)?((?P?(?Q?R))?(P??(?Q?R))) =(?P??R)?(?P??Q?R)?(P?(Q??R)) =(?P??R)?(?P??Q?R)?(P?Q)?(P??R)

=((?P??R)?(Q??Q))?(?P??Q?R)?((P?Q)?(R??R)) ?((P??R)?(Q??Q))

=(?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)?(P??Q??R) =?(0,1,2,4,6,7) =

?(3,5)

=(P??Q??R)?(?P?Q??R)

（2）(??P?Q)?((Q?R)??P) 解

原式=?(??P?Q)?((?Q?R)??P)

=(?P??Q)?((?Q?R)??P)?(?(?Q?R)?P) =(?P??Q)?(?P??Q)?(?P?R)?(P?Q??R)

9

=(?P?(Q??Q)?(R??R))?(?Q?(P??P)?(R??R))? ((?P??Q)?(R??R))?((?P?R)?(Q??Q))?(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)?(?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) =?(0,1,2,3,4,5,6) =

?(7)

=?P??Q??R

（3）(P??Q)?R 解

原式=?P??Q?R =?(6)

=

?(0,1,2,3,4,5,7)

=(?P??Q??R)?(?P??Q?R)?(?P?Q??R)?(?P?Q?R) ?(P??Q??R)?(P??Q?R)?(P?Q?R)

（4）P?(P?(Q?P)) 解

原式=?P?(P?(?Q?P)) =(?P?P)?(?P??Q?P) =T?T =T

10