离散数学课后习题合集

第一章 命题演算基础

1.1 判断下列语句是否为命题，若是请翻译为符号公式；若不是说明由。

（1）请给我一支笔！ （2）火星上有生物。 （3）X?Y?8

（4）只有努力工作，方能把事情做好。

（5）如果嫦娥是虚构的，而圣诞老人也是虚构的，那么许多孩子受骗了。 解

（1）不为命题，因为它不是陈述句。

（2）是命题，用命题变元P表示该命题。

（3）不为命题，虽为陈述句，但不能判断其真假性。

（4）是命题。设P表示努力工作，则原句翻译为命题公式Q?P。 Q表示把事情做好，（5）是命题。设P表示嫦娥是虚构的，Q表示圣诞老人也是虚构的，R表示许多孩子受骗了，则原句翻译为(P?Q)?R。 1.2 试判定下列公式的永真性和可满足性。

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

（1）当P?T时，

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

=Q?F =?Q

当Q=T时，上式=F；当Q?F时，上式=T，因此公式存在成真解释

(P,Q,R)?(T,F,?)，存在成假解释(P,Q,R)?(T,T,?)，故公式可满足，但非永真。

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

当P?T时

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

1

=?Q?((Q??R)?F)

=?Q?((Q??R) 当Q=T时

上式=?T?(T??R) =F??R =F

当Q=F时

上式=?F?(F??R) =T???R =??R =R

当R?T时，上式=T，因此公式存在成真解释(P,Q,R)?(T,F,T)，存在成假解释

(P,Q,R)?(T,T,?)，故公式可满足，但非永真。

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

当P?T时

原式=(??T?Q)?((Q??R)?T) =(T?Q)?(Q??R) =(Q?(Q??R) 当Q?T时

上式=(T?(T??R)

=?R

当R?T时，上式=F，当R?F时，上式=T，因此，公式存在成真解释

(P,Q,R)?(T,T,F)，存在成假解释(P,Q,R)?(T,T,T)，故公式可满足，但非永真。

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

当P?T时

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

2

=(T?Q)?((Q?R)?F) =Q??(Q?R) =Q?(?Q??R) 当Q?T时

上式=T?(?T??R)

=F??R =?R

当R?T时，上式=F，当R?F时，上式=T，因此，公式存在成真解释

(P,Q,R)?(T,T,F)，存在成假解释(P,Q,R)?(T,T,T)，故公式可满足，但非永真。

1.3 试求下列公式的成真解释和成假解释

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

（1）当Q?T时

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

=?R

当R?T时，上式=F，当R?F时，上式=T。

当Q?F时

原式=?((P?F)?R)?(F?R) =?(?P?R)?R 当R?T时

上式=?(?P?T)?T =?T?T =F 当R?F时

上式=?(?P?F)?F

=?P?F =P

当P?T时，上式=T，当P?F时，上式=F，

3

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

(P,Q,R)?(F,F,F),(?,T,T),(?,F,T)。

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

当P?T时

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

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

当P?F时

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

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

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

当P?T时

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

上式=T??(T?R)

成假解释为

4

；

=?(T?R)

=?R

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

上式=F??(F?R) =T 当P?F时

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

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

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

当P?T时

原式=(??T??Q)?(Q?(?R?T)) =(T??Q)?(Q??R) =?Q?(Q??R) 当Q?T时

上式=?T?(T??R) =F?T =F 当Q?F时

上式=?F?(F??R)

=T??R =?R

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

成假解释为

5