国防科学技术大学计算机学院离散数学课后习题答案命题逻辑

课后答案网第四章命题逻辑习题4.11.题号是否为命题命题的真值a)（没有确定的真假）b)Fc)Td)Te)Ff)（祈使句）g)（疑问句）2.a)PRQb)QRc)Pd)QRP（需考虑优先级）3.（答案不止一种，只要真值表相同即可）a)P:PPPQ:(PQ)(PQ)即(PQ)PQ:(PP)(QQ)PQ:P(QQ)PQ:(PQ)((PP)(QQ))或(P(QQ))(Q(PP))b)P:PPPQ:(PQ)(PQ)即(PQ)PQ:(PP)(QQ)和参考c)或d)定义c)PQ:(PQ)PQ:PQPQ:(PQ)(PQ)d)PQ:(PQ)PQ:(PQ)PQ:(PQ)(QP)e)PQ:PQ其它参考c)f)证明：要证明用、、、不能表示，只需证明仅用、、、不能表达出含的某些公式即可。因为PPP；PPP；PPT；PPT。增加T之后，TPPTP；PTTPT；TPP；PTT；TPPTP。这也就是说，由、、、只能得出P或T，不能得出P。习题4.21.a)Tb)Tc)Td)Fe)Ff)T2.以e)为例课后答案网QPQFFFFTFTTFTTFFTFFFTTTFTFTTFTTTFTFTTTFTTTFFTTFTFFT3.解释以P、Q、R的顺序排列，则为真的解释如下所示：c)(FFT)、(FTT)、(TFT)、(TTT)d)(FFF)、(FTF)4.a)是永真的b)是永真的c)是永真的d)是可满足的e)是可满足的f)是可满足的g)是永真的h)是永真的i)是永假的j)是永假的5.a)(((PQ)((PQ)R))(PQ))(PQ)（有的括号可省略）b)(Q(PP))((PP)Q)（有的括号可省略）6.c)是a)的代换实例（Q/P，(PP)/Q）d)是a)的代换实例（(P(QP))/Q）e)是b)的代换实例（R/P，S/Q，Q/R，P/S）b)是e)的代换实例（S/P，R/Q，P/R，Q/S）习题4.31.以a)为例：a)P(QP)P(PQ)的真值表如下：PQP(QP)P(PQ)FFFTFTFTTFTFTFFTFTTFFTTFTFTTTFTTFTTTFTTTFFTTTTTTTTFTTTTT上述真值表说明P(QP)P(PQ)为永真式。所以，P(QP)P(PQ)。2.a)(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Q)PTP所以，(PQ)(PQ)P。根据对偶原理得出的新的等价式为：课后答案网(PQ)(PQ)P。b)(PQ)(PQ)(PQ)(P(QQ))(PQ)(PF)(PQ)P(PQ)(PP)(PQ)F(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.a)PQQ（I2）PQ（I6）c)PQPPPQ（I9）PPQ（I1）e)(PPQ)(PPR)(TQ)(PPR)（E23）(TQ)(TR)（E23）(FQ)(TR)（E16）(FQ)(FR)（E16）(TQ)(FR)(TQ)(TR)(QT)(RT)（E3）QR（E14）上述均为等价变换，所以蕴含式也成立。5.以b)为例：b)P(QRP)P((QR)P)P((QR)P)P((QR)P)P(P(QR))(PP)(QR)PQR(PQR)(PQR)为P(QRP)只包含和的化简式。课后答案网习题4.41.e)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)(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Q))(PQ)(PT)(PQ)P(PQ)(PP)(PQ)T(PQ)PQPQ为PQ(PQ)的主合取范式。g)(PQR)(PQR)(P(QR))(P(QR))（化去）(P(QR))(P(QR))（最多保留一个）(PQ)(PR)(PQ)(P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)为(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P)(PQR)(QRP)(QRQR)（关于的分配率）F(PQR)(QRP)F（化简）(PQR)(QRP)（化简）(PQR)(QRP)为(PQR)(PQR)的主析取范式。2.a)(PQ)(PR)(PQ)(PR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)课后答案网QRP(QR)(PQ)(PR)(PQR)(PQR)(PQR)所以，(PQ)(PR)PQR。c)PQ(PQ)(PQP)(PQQ)FFFPQ(PQ)(PQP)(PQQ)FFF所以，PQ(PQ)PQ(PQ)。3.合式公式P既是主合取范式，又是主析取范式。4.求wffA的主析取范式的算法：i)利用E16和E22删去和在A中的所有出现，得到A1；ii)利用德摩尔根律将A1中的内移到原子之前，并用E1使每个原子之前至多仅有一个；iii)在用分配律将ii)的结果化为若干个合取式的析取，其中每个合取式的因子皆为原子或原子的否定；iv)对于iii)的结果中的每个合取式B，若命题变元P在B中不出现，利用(BP)(BP)(B(PP)BTB)取代B，直到每个合取式都变为极小项，最后删除相同项。