命题逻辑习题

命题逻辑习题命题逻辑习题命题逻辑习题命题逻辑习题编制仅供参考审核批准生效日期地址：电话：传真:邮编:数理逻辑习题命题逻辑（一）1.指出下列语句中哪些是命题a)离散数学的研究对象是自然数。b)请勿喧哗。c)夸夸其谈可以创造财富。d)“飞碟”来自于银河系之外。e)今天很冷。f)你明天还来吗[解]a)是命题。因为它是假的陈述句。b)不是命题。因为它是祈使句。c)是命题。因为它是假的陈述句。d)是命题。因为它是可确定真假的陈述句，虽然其真假性现时还无法确定，但随着人类认识的发展终将得到证实。e)是命题。因为它是可确定真假的陈述句，其真假取决于说话人的主观判断和外部环境的客观温度。f)不是命题。因为它是疑问句。2.用符号形式写下面命题，其中P表示命题“明天下雪”；Q表示命题“我们明天上课”；R表示命题“我们明天上公园”。a)如果明天下雪且我们停课，那么我们去公园。b)只有明天不下雪，我们才去公园。c)除非明天不下雪且我们上公园，否则我们将上课。d)无论明天下雪与否，我们照常上课。[解]a)PQ→R；b)P→R（或R→P）；c)(PR)Q（或PRQ）；d)PP→Q（或Q）。3.用上题的命题P，Q，R解释下面的形式命题。a)PQ→Rb)PRc)P→QRd)QR[解]a)只有明天下雪且不上课，我们才去公园；b)明天下雪，明天我们去公园；c)如果明天不下雪，那么我们上课或去公园；d)除非明天不停课(上课)，否则我们去公园。4.将下述命题符号化a)不是小王就是老李来找过你。b)尽管小张与小赵是同学，但他们很少在一起。c)如果程序能正常结束，那么就不会有语法错误。d)既然你今天不去开会，就该在家好好休息一下。e)只有博览群书，知识才能丰富。f)只要懂得法律，就能够成为一名律师。g)学好数、理、化，走扁天下都不怕。h)并非由于学校是重点，毕业生才是一流的，而是由于毕业生是一流的，学校才能成为重点。i)他能考上交大，除了由于他有一个较好的环境之外，还在于他平时的刻苦精神。[解]a)令：P：小王来找过你Q：老李来找过你形式化公式：PQ（实际上是不可兼或：PQ）；b)令：P：小张与小赵是同学Q：小张与赵在一起。形式化公式：PQ；c)令：P：程序正常结束Q：程序有语法错误形式化公式：P→Q；d)令：P：你今天去开会Q：你在家休息一下。形式化公式：PQ；e)令：P：(某人)博览群书Q：(某人)知识丰富形式化公式：P→Q（或者Q→P）；f)令：P：(某人)懂得法津Q：(某人)成为一名律师形式化公式：P→Q；g)令：P：(某人)学好数学Q：(某人)学好物理R：(某人)学好化学S：(某人)走遍天下都不怕形式化公式：PQR→S；h)令：P：学校是重点Q：毕业是一流的形式化公式：(P→Q)(Q→P)；i)令：P：他考上了交大Q：他有一个较好的环境R：他平时刻苦形式化公式：QR→P。5.试通过对命题公式中联结词的个数归纳，证明命题公式在任一指派下的真假值都是唯一的。[证](采用串值数学归纳法)为证命题公式在任一赋值υ下的真值是唯一的，我们对公式中所含联结词的个数n进行串值归纳：1）若n＝0，则α＝P是一原子公式，从而α(υ)＝P(υ)显然是唯一的。2）假设n＝0，1，2，…，k时，任何含有n个联结词的公式α′在υ下的真值α′(υ)是唯一的。3）于是，当n＝k+1时，则根据合式公式的形成规则，可知＝α1，或者α＝α1*α2（这里*＝或或→或）。我们设1和2中的联结词个数分别为k1和k2，那么a)当α＝α1时，则有k1+1＝k+1，从而k1＝k0于是由归纳假设可知，真值是唯一的，所以由的真值表知真值α(υ)＝(α1(υ))是唯一的；b)当α＝α1*α2时，则有k1+k2+1＝k+1，从而k1+k2＝k，即有k1k，k2k。于是由归纳假设知，真值α1(υ)，α2(υ)是唯一的，所以由*的真值表（，，→，的真值表）知真值α(υ)＝α1(υ)*α2(υ)都是唯一的。这就用串值归纳法证明了命题公式α在任一赋值υ下的真值（真假值）都是唯一的。6.令P，Q，R，S分别取值为T，F，T，F。求出下列命题公式在相应指派下的真假值。a)P(Q→PR)b)QP→(QSR)c)(P→Q)(R→QS)d)P(Q→RS)QP[解]这里赋值υ＝（T，F，T，F）a)(P(Q→PR))(υ)＝P(Q→PR)＝T(F→TT)＝F(F→T)＝FT＝Tb)(QP→(QSR))(υ)＝QP→(QSR)＝FT→(FFT)＝T→(FT)＝T→F＝Fc)((P→Q)(R→QS))(υ)＝(P→Q)(R→QS))＝(T→F)(T→FF)＝F(T→F)＝FF＝Fd)(P(Q→RS)QP)(υ)＝(P(Q→RS)QP)＝T(F→TF)FT＝T(F→TT)FF＝T(F→T))F＝TTF＝TF＝F7.构造下列命题公式的真值表。a)P(QR)b)(P→Q)(PR)c)(P→(QQ))→Pd)((P→Q)→(P→R))→(P→(Q→R))[解]a)PQRQRP(QR)TTTTTTTFTTTFTTTTFFFFFTTTFFTFTFFFTTFFFFFFb)PQRP→QPR(P→Q)(PR)TTTTTTTTFTTTTFTFTFTFFFTFFTTTTTFTFTFFFFTTTTFFFTFFc)PQPQQQP→(QQ)(P→(QQ))→PTTFFFFTTFFTFFTFTTFFTTFFTTFTTd)PQRP→QP→RQ→R(P→Q)→(P→R)P→(Q→R)((P→Q)→(P→R))→(P→(Q→R))TTTTTTTTTTTFTFFFFTTFTFTTTTTTFFFFTTTTFTTTTTTTTFTFTTFTTTFFTTTTTTTFFFTTTTTT8.利用真值表法判断下列逻辑等价式是否成立。a)(P→Q)┝┥(Q→P)b)(P→Q)┝┥(Q→P)c)P→(Q→R)┝┥(P→Q)→(P→R)d)(P→Q)┝┥PQe)(PQ)┝┥PQf)PQ┝┥(PQ)(PQ)g)P→(Q→P)┝┥P→(Q→P)h)(P→R)(Q→R)┝┥PQ→Ri)(PQ)R┝┥P(QR)[解a)成立。PQPQP→QQ→PTTFFFFTFFTTTFTTFTTFFTTTT此真值表最后两列全完相同。故a)的逻辑等价式成立。b)不成立。PQP→QQ→PTTTTTFFTFTTFFFTF此真值表最后两列不完全相同。故b)的逻辑等价式不成立。c)成立。PQRP→QP→RQ→RP→(Q→R)(P→Q)→(P→R)TTTTTTTTTTFTFFFFTFTFTTTTTFFFFTTTFTTTTTTTFTFTTFTTFFTTTTTTFFFTTTTT此真值表最后两列完全相同。故c)的逻辑等价式成立。d)成立。PQQP→Q(P→Q)PQTTFTFFTFTFTTFTFTFFFFTTFF此真值表最后两列完全相同。故d)的逻辑等价式成立。e)成立。PQPQPQ(PQ)PQTTFFTFFTFFTFTTFTTFFTTFFTTFTT此真值表最后两列完全相同。故e)的逻辑等价式成立。f)成立。PQPQPQPQPQ(PQ)(PQ)TTFFTFTTTFFTFFFFFTTFFFFFFFTTFTTT此真值表最后两列完全相同。故f)的逻辑等价式成立。g)成立。PQPQ→PQ→PP→(Q→P)P→(Q→P)TTFTFTTTFFTTTTFTTFTTTFFTTTTT此值表最后两列完工全相同。故f)逻辑等价式成立。h)成立。PQRP→RQ→RPQ(P→R)(Q→R)PQ→RTTTTTTTTTTFFFTFFTFTTTTTTTFFFTTFFFTTTTTTTFTFTFTFFFFTTTFTTFFFTTFTT此真值表最后两列完全相同。故h)的逻辑等价式成立。i)成立。PQRPQQR(PQ)RP(QR)TTTTTTTTTFTFFFTFTFFFFTFFFTTTFTTFTFFFTFFFTTFFTTFTTFFFTTFF此真值表最后两列完全相同。故i)的逻辑等价式成立。9.东东的爷爷带东东乘车去玩，当路过一座高楼时，爷爷说：“你只有现在好好学习，将来才能住上这样的高楼。”东东听了爷爷的话以后，回答说，“爷爷决有住上这样的高楼，所以爷爷没有好好学习。”请问：东东是否误解了爷爷原话的意思，为什么[解]东东误解了爷爷原话的意思。因为若令：P：(你)现在好好学习Q：(你)将来住上这样的高楼则爷爷的原话形式化为：Q→P而东东的回答形式化是：Q→P这两个公式不是逻辑等价的。这可用真值表法证明如下：PQPQQ→PQ→PTTFFTTTFFTTFFTTFFTFFTTTT此真值表最后两列不完全相同，说明Q→P与Q→P不是逻辑等价的（事实上Q→P┝┥P→Q），所以，东东的回答与爷爷的原话是不等价的，不是一个意思。因而，东东误解了爷爷原话的意思。10.某单位派人外出学习。但由于工作关系，A，B两个不能同去。如果B去则C必须留下工作。如果派D去则B和C至少应去一人。试问a)四人中最多能派几人b)若己决定派B去，是否还可以增派其它人请通过对成真指派的分析给出上面问题的最佳人选。[解]令：P：A去Q：B去R：C去S：D去则问题形式化为一公式（条件公式）：α=(PQ)(Q→R)(S→(QR))a)因四人全去,得到赋值υ1＝(T，T，T，T)，使得真值α(υ1)＝F，从而四人全去不行,故至多只能派三人同去。又因A和B不能同时去，而A去，C去，D去，得到赋值υ2＝(T，F，T，T)，使得真值α(υ2)＝T，故至少可以派三个人同去。所以，四人中最多能派三人同去。b)若己决定派B去，则根据(PQ)，可知不能派A去；又根据(Q→R)，可知不能派C去，因而至多只能增派D去。从而得到赋值υ3＝(F，T，F，T)，使得真值α(υ3)＝T。故此，若己决定派B去，则还可以增派D同去。11.利用真值表判断下列公式的永真性（有效性）。a)P→(P→Q)b)(P→Q)→((Q→R)→(P→R))c)((PQ)R)(PQ→R)d)(P→(Q→R))(Q→(P→R))[解]a)⊨P→（P→Q）PQPP→QP→(P→Q)TTFTTTFFFTFTTTTFFTTT因为此值表的最后一列全是T,故公式是有效的。b)⊨(P→Q)→((Q→R)→(P→R))PQRP→QQ→PP→R(Q→R)→(P→R)(P→Q)→((Q→R)→(P→R))TTTTTTTTTTFTFFTTTFTFTTTTTFFFTFFTFTTTTTTTFTFTFTTTFFTTTTTTFFFTTTTT因为此真值表的最后一列全是T,故公式是有效的。c)⊨((PQ)R)((PQ)→R)PQRPQQPR(PQ)RPQ→R((PQ)R)(PQ→R)TTTTTFTFTTTFTTTFTTTFTTFFTTTTFFTFTFTTFTTTFFTTTFTFTFTFTTFFTFFFFTTFFFFFTFTT因为此真值表的最后一列全是T,故公式是有效的。d)⊨(P→(Q→R))(Q→(P→R))PQRQ→RP→RP→(Q→R)Q→(P→R)TTTTTTTTTFFFFFTFTTTTTTFFTFTTFTTTTTTFTFFTTTFFTTTTTFFFTTTT因为此真值表的最后两列完全相同,故公式是有效的。12.利用真值表证明下列逻辑蕴涵式。a)(P→Q)⊨Pb)Q(P→Q)⊨Pc)(PQ)(P→R)(Q→S)⊨RSd)P→(QQ)⊨P[证]a)逻辑蕴涵式(P→Q)⊨P成立。PQP→Q(P→Q)PTTTFTTFFTTFTTFFFFTFF因为此真值表凡是(P→Q)列为T的行，P列相应的行也为T。b)逻辑蕴涵式Q(P→Q)⊨P成立PQQP→QQ(P→Q)PTTFTFFTFTFFFFTFTFTFFTTTT因为此真值表凡是Q(P→Q)列为T的行，P列相应的行也为T。c)逻辑蕴涵式(PQ)(P→R)(Q→S)⊨RS成立。PQRSPQPRQ→S(PQ)(P→R)(Q→S)RSTTTTTTTTTTTTFTTFFTTTFTTFTFTTTFFTFFFFTFTTTTTTTTFTFTTTTTTFFTTFTFTTFFFTFTFFFTTTTTTTTFTTFTTFFTFTFTTTTTTFTFFTTFFFFFTTFTTFTFFTFFTTFTFFFTFTTFTFFFFFTTFF因为此真值表凡是(PQ)(P→R)(Q→S)列为T的行，RS列相应的行也为T。d)逻辑蕴涵式P→(QQ)⊨P成立。PQPQQQP→(QQ)PTTFFFTTTFFTFTTFTTFFFFFFTTFFF因为真值表凡是P→(QQ)列为T的行，P列相应的行也为T。13.求下列命题公式的代入实例。a)P→((P→Q)→Q)其中：P代入为P→Q，Q代入为(P→Q)→Qb)(P→Q)→((Q→R)→(P→R))其中，P代入为Q→R，Q代入为P→R。[解]a)(P→((P→Q)→Q))[(P→Q)/P,((P→Q)→Q)/Q]=(P→Q)→(((P→Q)→((P→Q)→Q))→((P→Q)→Q))；b)((P→Q)→((Q→R)→(P→R)))[(Q→R)/P,(P→R)/Q]=((Q→R)→(P→R))→(((P→R)→R)→((Q→R)→R))。14.设1，2，为命题公式。如果1⊨2，证明：a)2⊨1b)1⊨2c)1⊨2d)1→⊨2→[证]a)对于任一赋值υ，如果(2)(υ)=T，则2(υ)=F。根据1⊨2，可知1(υ)=F，从而(1)(υ)=T。所以2⊨1成立。b)对任一赋值υ，如果(1)(υ)=T，那么1(υ)=T且(υ)=T。根据1⊨2，可得2(υ)=T，从而2(υ)=T且(υ)=T，也即是(2)(υ)=T，所以1⊨2成立。c)对任一赋值υ，如果(1)(υ)=T，那么1(υ)=T或者(υ)=T。于是分情况证明如下：1°若1(υ)=T，那么根据1⊨2，可知2(υ)=T，因此(2)(υ)=T；2°若(υ)=T，则显然(2)(υ)=T；因此，无论如何，总有(2)(υ)=T。所以1⊨2成立。d)对任一赋值υ，如果(2→)(υ)=T，那么若2(υ)=T，则(υ)=T。于是：1°若1(υ)=F，那么显然有(1→)(υ)=T；2°若1(υ)=T，那么根据1⊨2，可知2(υ)=T，从而有(υ)=T，因此得到(1→)(υ)=T；于是，无论如何，总有(1→)(υ)=T。所以1→⊨2→成立。15.利用变换法证明下列逻辑等价式。a)P→(Q→P)┝┥P→(P→Q)b)(P→R)(Q→R)┝┥PQ→Rc)(PQ)┝┥(PQ)(PQ)d)(P→Q)┝┥PQ[证明]a)P→(Q→P)┝┥P(QP)（替换定理，联结词化归）┝┥(PP)Q（结合律）┝┥PP┝┥(PP)Q┝┥P(PQ)（结合律）┝┥P(PQ)（替换定理，双重否定律）┝┥P→(P→Q)（替换定理，联结词化归）(P→R)(Q→R)┝┥(PR)(QR)（替换定理，联结词化归）┝┥(PQ)R（分配律）┝┥(PQ)R（替换定理，deMorgan律）┝┥PQ→R（联结词化归）c)(PQ)┝┥((P→Q)(Q→R))（替换定理，联结词化归）┝┥((PQ)(QP))（替换定理，联结词化归）┝┥(PQ)(QP)（deMorgan律）┝┥(PQ)(QP)（替换定理，deMorgam律）┝┥(PQ)(QP)（替换定理，双重否定律）┝┥(PP)(PQ)(PQ)(QQ)（分配律、替换定理，结合律，交换律）┝┥(PQ)(PQ)（化简律）d)(P→Q)┝┥(PQ)（替换定理，联结词化归）┝┥PQ（deMergan律）┝┥PQ（替换定理，双重否定律）。16.利用变换法证明下列逻辑蕴涵式。a)P→(Q→R)⊨(P→Q)→(P→R)b)(P→Q)→Q⊨PQc)(P→Q)→(Q→P)⊨Q→Pd)P→Q⊨PR→QR[证]a)实际上，我们可证逻辑等价式：P→(Q→R)┝┥(P→Q)→(P→R)就是P→(Q→R)┝┥P(QR)（替换定理，联结词化归）┝┥(PPR)(P┐QR)（化简律）┝┥(PQ)(PR)（分配律）┝┥(PQ)(PR)（替换定理、双重否定律，deMorgan律）┝┥(P→Q)(P→R)（替换定理，联结词化归）┝┥(P→Q)→(P→R)（联结词化归）b)实际上我们可证逻辑等价式：(P→Q)→Q┝┥P∨Q变换证明如下：(P→Q)→Q┝┥(PQ)Q（替换定理，联结词化归）┝┥(PQ)Q（替换定理、deMorgan律）┝┥(PQ)Q（替换定理、双重否定律）┝┥(PQ)(QQ)（分配律）┝┥PQ（化简律）c)实际上，我们可证逻辑等价式：(P→Q)→(Q→P)┝┥Q→P变换证明如下(P→Q)→(Q→P)┝┥(PQ)(QP)（替换定理、联结词化归）┝┥(PQ)(QP)（替换定理，deMorgasn律）┝┥(PQ)(QP)（替换定理、双重否定律）┝┥QP（吸收律）┝┥Q→P（联结词化归）d)P→Q⊨PQ（联结词化归）⊨PQR（析取构成式）⊨(PQR)(RRQ)（化简律）⊨(PR)(QR)（分配律）⊨(PR)(QR)（替换定律，deMorgan律）⊨PR→QR（联结词化归）。17.求下列命题公式的对偶式。a)(P→Q)→PRb)(PQ)(PQ)c)(P→QR)(Q→P)[解]a)由于(P→Q)→PR┝┥(PQ)PR所以其对偶式为(PQ)PR。b)由于(PQ)(PQ)┝┥((P→Q)(Q→P))(PQ)┝┥((PQ)(QP))(PQ)┝┥((PQ)(PQ))(PQ)因此其对偶式为((PQ)(PQ))(PQ)。c)因为(P→QR)(Q→P)┝┥(PQR)(QP)┝┥(PQR)(QP)从而其对偶式为(PQR)(QP)。18.将下列命题公式化成只含有全功能联结词集合{,→}中联结词的命题公式。a)P(QR)b)(PQ)R→PRc)P(QR→P)d)(P(Q→RP))[解]a)P(QR)┝┥(QR)P┝┥(QR)P┝┥(QR)P┝┥(Q→R)→Pb)(PQ)R→PR┝┥((P→Q)R)→(P→R)┝┥((P→Q)→R)→(P→R)c)P(QR→P)┝┥P→((Q→R)→P)┝┥P→((R→Q)→P)d)(P(Q→RP))┝┥((P→(Q→RP))((Q→RP)→P))┝┥((P→(Q→(P→R)))((Q→(P→R))→P))┝┥(P→(Q→(P→R)))→((Q→(P→R))→P)。19.证明{↓}是极小全功能的。[证]根据定理2，联结词集{，}是全功能的，故为证{↓}是全功能的，只需证明{，}中的每个联结词都可分别由↓来表示即可。由于P┝┥P↓PPQ┝┥(P↓Q)↓(P↓Q)因此{↓}是全功能的。由于{↓}中只有一个联结词，故所以{↓}是极小全功能的。20.证明{，}不是全功能的。[证]{，}不是全功能的。否则，联结词必定可由联结词集{，}来表示，即，对于任一原子公式P，存在公式，中只含联结词和，使得P┝┥设υ是一对中出现的所有命题变项及P都指派真值T的赋值。则我们可用串值归纳法证明(υ)＝T；但是(P)(υ)＝T＝F，从而P不可能与公式逻辑等价，矛盾。事实上，我们施串值归纳于中联结词和的个数m，来证(υ)＝T：当m＝1时，只能有＝PP或PQ或QQ,或PP或PQ或QQ。由于υ给P和Q都赋值T，故这时显然有(υ)＝T。当m＝1，2，…，k时，归纳假设总有(υ)＝T。则当m＝k+1时，只能有＝12或12，其中1和2中所含联结词和的个数分别为和，于是就有即从而有，，因此，根据归纳假设有1(υ)=T，2(υ)=T,所以(υ)=1(υ)2(υ)=TT=T或者(υ)=1(υ)2(υ)=TT=T总之(υ)=T。21.将下列命题公式化为析取范式。a)PQ→(PQ)Rb)(P(P→Q))(Q→R)c)(P→QR)(P→QR)d)Q(P→Q(Q→R))[解]a)(PQ)→(PQ)R┝┥(PQ)(((P→Q)(Q→P))R)┝┥(PQ)(((PQ)(QP))R)┝┥(PQ)(PP)(QP)(PQ)(QQ)R┝┥(PQ)(PQ)(PQ)Rb)(P(P→Q))(Q→R)┝┥(P(PQ))(QR)┝┥(PPQ))(QR)┝┥(PQ)(QR)┝┥(PQ)(QQ)(PR)(QR)┝┥(PQ)(PR)(QR)c)(P→(Q∧R))∧(┐P→(┐Q∧┐R))┝┥(P(QR))(P(QR))┝┥(P(QR))(P(QR))┝┥(PP)(QRP)(PQR)(QRQR))┝┥(PQR)(PQR)d)Q(P→(Q(Q→R)))┝┥Q(P(Q(QR)))┝┥Q(QP(QR))┝┥Q22.将上题的各命公式化为主析取范式。[解]a)(PQ)→((PQ)R)┝┥(PQ)(PQ)(PQ)R┝┥((PQ)(RR))((PQ)(RR))((PQ)(RR))((QQ)R))┝┥(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(QR)(QR)┝┥(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)((PP))(QR))((PP)(QR))┝┥(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)┝┥(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)┝┥m7m6m5m4m3m2m1b)(P(P→Q))(Q→R)┝┥(PQ)(PR)(QR)┝┥((PQ)(RR))((PR)(OQ))((PP)(QR))┝┥(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)┝┥(PQR)(PQR)(PQR)(PQR)┝┥m7m5m4m3c)(P→QR)(P→QR)┝┥(PQR)(PQR)┝┥m7m0d)Q(P→(Q(Q→R)))┝┥Q┝┥(PQ)(PQ)┝┥((PQ)(RR))((PQ)(RR))┝┥(PQR)(PQR)(PQR)(PQR)┝┥m7m6m3m223.通过化主析取范式的方法，判断下面的逻辑等价式是否成立。a)(PQ)(PQR)┝┥(P(QR))(Q(PR))b)P(PQ)R┝┥(PQ)(QR)[解]a)因为(PQ)(PQR)┝┥((PQ)(RR))(PQR)┝┥(PQR)(PQR)(PQR)┝┥m7m6m3又因为(P(QR))(Q(PR))┝┥(PQ)(QRQ)(PPR)(QRPR)┝┥(PQ)(QR)(PQR)┝┥((PQ)(RR))((PP)(QR))(PQR)┝┥(PQR)(PQR)(PQR)(PQR)(PQR)┝┥(PQR)(PQR)(PQR)┝┥m7m6m3所以(PQ)(PQR)┝┥(P(QR))(Q(PR))b)因为P(PQ)R┝┥(P(QQ))((PQ)(RR))((QQ)R)┝┥(PQ)(PQ)(PQR)(PQR)(QR)(QR)┝┥(PQR)(PQR)((PQ)(RR))((PQ)(RR))((PP)(QR))((PP)(QR))┝┥(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)┝┥(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)┝┥m7m6m5m3m2m1m0又因为(PQ)(QR)┝┥(PQ)(QR)┝┥(PQ)(QR)┝┥Q(PR)┝┥((PP)Q)(P(QQ)R)┝┥(PQ)(PQ)(PQR)(PQR)┝┥((PQ)(RR))((PQ)(RR))(PQR)(PQR)┝┥(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)┝┥(PQR)(PQR)(PQR)(PQR)(PQR)┝┥m7m6m3m2m1所以P(PQ)R与(PQ)(QR)不逻辑等价。24.设计一个控制两间会议室的照明电路，要求分别装在这两间会议室的两只开关都能控制整个会议室的照明。[解]会议室两个门旁开关表示k1、k2，“0”表示开关断开，“1”表示开关接通。S表示会议室的照明状态，“1”表示全室灯亮，“0”表示全室灯暗。假设开始时，室内无人，灯暗。两只开关都处于“0”状态。有人进入室内时，随手改变门旁的开关状态，则会议室灯亮，S为“1”。此时两只开关中有一只（奇数）处于“0”状态。当有人离开会议室时，随手改变门旁的开关状态，会议室灯暗，S为“0”。此时两只开关（偶数）都处于“0”状态。……。故此,我们有:当有偶数只开关处于“0”状态时，S为“0”；当有奇数只开关处于“0”状态时，S为“1”；所以，我们有:S┝┥(k1k2)(k1k2)┝┥(k1k2)(k1k2)其电路图如图所示：┐┐┐∧∧K1K非门非门或门与门S或门第24题图25.某公安员在追捕一个逃犯的途中面对前面具有两条路分叉的路口。己知该路口住着两个居民，其中一个说谎成性，另一个天性诚实。请问：该公安员如何发问才能确定逃犯的去向。[解]公安人员手指一路问身旁一名居民说：“逃犯是从这条路逃走的，他（指另一居民）将回答‘是’，你说对吗”当被问居民回答：“否”时，公安人员应从所指那条路去追逃犯；当被问居民回答“对”时，公安人员应从另一条路去追逃犯。分析：①如果被问居民诚实，他回答“对”。则另一居民是说谎者，他回答“是”，那么，逃犯没有从所指路逃走；②如果被问居民诚实，他回答“否”。则另一居民是说谎者，他回答“否”，那么，逃犯是从所指路逃走的；③如被问居民说谎，可以此类推分析。形式化：设P：被问居民是诚实的Q：被问居民回答“是”R：另一居民回答“是”S：逃犯是从所指路逃走的则S┝┥(PQ)(PQ)┝┥(PP)Q┝┥QR┝┥PQ真值表如下：PQRSQPQTTTFFTTFFTTFFTFFFFFFTTTT即：“逃犯是从所指路逃走的”当且仅当“被问居民诚实且其回答是‘否’”（即另一人不诚实因而将回答“否”）或者“被问战士说谎且其回答是‘否’”（即另一人诚实因而将回答是“是”）当且仅当“被问战士回答是‘否’”。并且“另一居民回答是‘是’”当且仅当“被问居民诚实且其回答是‘是’”或者“被问居民说谎且其回答是‘否’”。26.证明析取消去规则（－）和否定规则（－）都是可靠的。[证](a)析取消去规则（－）为：⊢，,⊢，,⊢⊢其可靠性为要性：⊨，,⊨，,⊨⊨证法一：令：为中所有公式之合取式。根据定理2，则要证：⊨，⊨，⊨⊨根据定理1，即要证：⊨→，⊨→，⊨→⊨→即要证：⊨(→)(→)(→)⊨→（*）但是我们能够证明：(→)(→)(→)⊨→（**）事实上：(→)(→)(→)┝┥()()()┝┥(()(()))┝┥(())┝┥()()⊨⊨→因此，根据（**）可知（*）成立。所以析取消去法规则（－）是可靠的。证法二：令：为中所有公式之合取式。根据定理2，则要证：⊨，⊨，⊨⊨对于任一赋值υ，若(υ)=T，则由⊨，可得()(υ)=T，于是有(υ)=T或者(υ)=T。(i)若(υ)=T，则()(υ)=T，从而由⊨，可得(υ)=T；(ii)若(υ)=T，则()(υ)=T，从而由⊨，可得(υ)=T；综合（i）（ii），总有(υ)=T。所以，由赋值υ的任意性，⊨。（b）否定消去规则（－）为：,⊢，,⊢⊢其可靠性为要性：,⊨，,⊨⊨证法一：令：为中所有公式之合取式。根据定理2，则要证：⊨，⊨⊨根据定理1，即要证：⊨→，⊨→⊨→即要证：⊨(→)(→)⊨→（*）但是我们能够证明：(→)(→)⊨→（**）事实上：(→)(→)┝┥()()┝┥()())┝┥┝┥→因此，根据（**）可知（*）成立。所以否定消去规则（－）是可靠的。证法二：令：为中所有公式之合取式。根据定理2，则要证：⊨，⊨⊨对于任一赋值υ，若(υ)=T，则有(υ)=T。否则(υ)=F，从而()(υ)=F，于是有()(υ)=T。(i)由⊨，可得(υ)=T；(ii)由⊨，可得()(υ)=T，从而可得(υ)=F；(i),(ii)矛盾。所以，由赋值υ的任意性，⊨。27.构造形式证明过程。⊢⊢()⊢()()⊢()()⊢()()()⊢()()⊢()()⊢⊢→P⊢P→QQ⊢P→QQ,P→Q⊢P[证]a)（1） P（2） －(1)（3） －(1)（4） －(2)(3)b)（1） P（2）□ H(－)（3）□ +(2)（4）□ H(－)（5）□ +（4）（6） －(1)(3)(5)|(2)(4)c)（1）() P（2） －(1)（3） －(1)（4） －(2)（5） －(1)（6） +(4)(5)（7）() +(3)(6)d)（1）() P（2）□ H(－)（3）□□ H(－)（4）□□() +(3)（5）□□ H(－)（6）□□ +(5)（7）□□() +(6)（8）□() －(2)(4)(7)|(3)(5)（9）□ H(－)（10）□ +(9)（11）□() +(10)（12）() －(1)(8)(11)|(12)(9)e)（1）() P（2） －(1)（3） －(1)（4）□β H(－)（5）□ +(2)(4)（6）□()() +(5)（7）□ H(－)（8）□ +(2)(7)（9）□()() +(8)（10）()() －(3)(6)(9)|(4)(7)f)（1）() P（2）□ H(－)（3）□ +(2)（4）□ +(2)（5）□()() +(3)(4)（6）□ H(－)（7）□ －(6)（8）□ +(7)（9）□ －(6)（10）□ +(9)（11）□()() +(8)(10)（12）()() －(1)(5)(11)|(2)(6)（1） P（2）□ H(－)（3）□□ H(＋)（4）□□ －(3)（5）□() ＋(4)(2)|(3)（6）□ H(－)（7）□□ H(＋)（8）□□ －(7)（9）□() ＋(8)(6)|(7)（10）() －(1)(5)(9)|(2)(6)h)（1）() P（2）□ H(＋)（3）□ +(2)（4） ＋(3)(1)|(2)（5）□ H(＋)（6）□ +(5)（7） ＋(6)(1)|(5)（8） +(4)(7)i)（1） P（2）□ H(－)（3）□□ H(→+)（4）□□□ H(－)（5）□□ －(3)(2)|(4)（6）□→ →+(5)|(3)（7）□ H(－)（8）□□ H(→+)（9）□→ →+(7)|(8)（10）→ －(1)(6)(9)|(2)(7)j)（1）P P（2）□P H(→+)（3）□□Q H(－)（4）□Q －(2)(1)|(3)（5）P→Q →+(4)|(2)k)（1）Q P（2）□P H(→+)（3）P→Q →+(1)|(2)l)（1）Q P（2）P→Q P（3）□P H(+)（4）□Q →－(3)(2)（5）P +(4)(1)|(3)28.构造形式推理过程。→,()⊢,→,→⊢→,→⊢→→(→),⊢→(→)(),⊢→→,,→,→⊢[证]a)（1）→ P（2）() P（3）□ H(＋)（4）□ →－(3)(1)（5）□ +(4)（6） +(5)(2)|(3)b)（1） P（2）→ P（3）→ P（4）□ H(－)（5）□ →+(4)(2)（6）□ +(5)（7）□ H(－)（8）□ →－(7)(3)（9）□ +(8)（10） －(1)(6)(9)|(4)(7)c)（1）→ P（2）→ P（3）□ H(→+)（4）□□ H(+)（5）□□ +(4)（6）□□ →－(5)(1)（7）□□ →－(6)(2)（8）□□□ H(－)（9）□□□□ H(+)（10）□□□□ －(3)（11）□□□() +(8)(10)|(9)（12）□□□ H(－)（13）□□□□ H(+)（14）□□□□ －(3)（15）□□□() +(12