命题逻辑习题

1、数理逻辑习题命题逻辑（一）1.指出下列语句中哪些是命题 a) 离散数学的研究对象是自然数。b) 请勿喧哗。c) 夸夸其谈可以创造财富。d) “飞碟”来自于银河系之外。e) 今天很冷。f) 你明天还来吗？解 a) 是命题。因为它是假的陈述句。b) 不是命题。因为它是祈使句。c) 是命题。因为它是假的陈述句。d) 是命题。因为它是可确定真假的陈述句，虽然其真假性现时还无法确定，但随着人类认识的发展终将得到证实。e) 是命题。因为它是可确定真假的陈述句，其真假取决于说话人的主观判断和外部环境的客观温度。f) 不是命题。因为它是疑问句。2.用符号形式写下面命题，其中P表示命题“明天下雪”；Q表示命题“

2、我们明天上课”；R表示命题“我们明天上公园”。a) 如果明天下雪且我们停课，那么我们去公园。b) 只有明天不下雪，我们才去公园。c) 除非明天不下雪且我们上公园，否则我们将上课。d)无论明天下雪与否，我们照常上课。解 a) PÙØQR；b) ØØPØR（或RØP）；c) Ø(ØPÙR)«ØQ （或ØPÙR«ØQ）；d) PÚØPQ（或Q）。3.用上题的命题P，Q，R解释下面的形式命题。 a) ØPÚQ

3、16;Rb) PÙRc) ØPQÚRd) ØQ«R解 a) 只有明天下雪且不上课，我们才去公园；b) 明天下雪，明天我们去公园；c) 如果明天不下雪，那么我们上课或去公园；d) 除非明天不停课(上课)，否则我们去公园。4.将下述命题符号化 a) 不是小王就是老李来找过你。b) 尽管小张与小赵是同学，但他们很少在一起。c) 如果程序能正常结束，那么就不会有语法错误。d) 既然你今天不去开会，就该在家好好休息一下。e) 只有博览群书，知识才能丰富。f) 只要懂得法律，就能够成为一名律师。g) 学好数、理、化，走扁天下都不怕。h) 并非由于学校是重点

4、，毕业生才是一流的，而是由于毕业生是一流的，学校才能成为重点。i) 他能考上交大，除了由于他有一个较好的环境之外，还在于他平时的刻苦精神。解 a) 令：P：小王来找过你Q：老李来找过你形式化公式：PÚQ（实际上是不可兼或：PQ）；b) 令：P：小张与小赵是同学 Q：小张与赵在一起。形式化公式：PÙØQ；c) 令：P：程序正常结束 Q：程序有语法错误形式化公式：PØQ；d) 令：P：你今天去开会 Q：你在家休息一下。形式化公式：ØPÙQ；e) 令：P：(某人)博览群书 Q：(某人)知识丰富形式化公式：ØPØQ（或者Q

5、P）；f) 令：P：(某人)懂得法津 Q：(某人)成为一名律师形式化公式：PQ；g) 令：P：(某人)学好数学 Q：(某人)学好物理 R：(某人)学好化学 S：(某人)走遍天下都不怕形式化公式：P ÙQ ÙRS；h) 令：P：学校是重点 Q：毕业是一流的形式化公式：Ø(PQ) Ù(QP) ；i) 令：P：他考上了交大 Q：他有一个较好的环境 R：他平时刻苦形式化公式：Q ÙRP。5.试通过对命题公式中联结词的个数归纳，证明命题公式在任一指派下的真假值都是唯一的。证 (采用串值数学归纳法)为证命题公式在任一赋值下的真值是唯一的，我们对公式中所含联

6、结词的个数n进行串值归纳： 1）若n0，则P是一原子公式，从而() P()显然是唯一的。2）假设n0，1，2，k时，任何含有n个联结词的公式在下的真值() 是唯一的。3）于是，当nk+1时，则根据合式公式的形成规则，可知 Ø1，或者1*2（这里* Ù或Ú或或«）。我们设1和2中的联结词个数分别为k1和k2，那么a) 当Ø1时，则有k1+1k+1，从而k1k0于是由归纳假设可知，真值是唯一的，所以由Ø的真值表知真值() Ø (1()是唯一的；b) 当1*2时，则有k1+k2+1k+1，从而k1+k2k，即有k1£k，

7、k2£k。于是由归纳假设知，真值1()，2 ()是唯一的，所以由*的真值表（Ù，Ú，«的真值表）知真值()1()*2()都是唯一的。这就用串值归纳法证明了命题公式在任一赋值下的真值（真假值）都是唯一的。6.令P，Q，R，S分别取值为T，F，T，F。求出下列命题公式在相应指派下的真假值。 a) ØPÚ (QPÙR)b) QÚP(QÙS«R)c) (PQ) Ù(RQÙS)d) PÚ(QRÙØS)«QÚØP解 这里赋值（T

8、，F，T，F） a) (Ø P Ú(QPÙR)()Ø P° Ú(Q°P°ÙR°)Ø T Ú(FTÙT)F Ú (FT)F Ú TTb) (QÚP(QÙS«R)() Q°ÚP°(Q°ÙS °«R°) FÚT(FÙF«T) T(F«T) TFFc) (PQ) Ù (RQÙS)() (

9、P°Q°) Ù (R°Q°ÙS°) (TF) Ù (TFÙF) FÙ (TF) FÙF Fd) (PÚ(QRÙØS)«QÚØ P)() (P°Ú(Q°R°ÙØS°)«Q°ÚØP°) TÚ(FTÙØF)«FÚØT TÚ(FTÙT)&

10、#171;FÚF TÚ(FT)«F TÚT«FT«FF7.构造下列命题公式的真值表。 a) PÙ(QÚR)b) (PQ) Ù(PÚR)c) (P(QÙØQ)ØPd) (PQ)(PR)(P(QR)解 a)PQRQÚRPÙ(QÚR)TTTTTTTFTTTFTTTTFFFFFTTTFFTFTFFFTTFFFFFFb)PQRPQPÚR(PQ) Ù(PÚR)TTTTTTTTFTTTTFTFTFTFFFTFFTTTTT

11、FTF TFFFFTTTTFFFTFFc) PQØPØQQÙØQP(QÙØQ)(P(QÙØQ)ØPTTFFFFTTFFTFFTFTTFFTTFFTTFTTd) PQRPQPRQR(PQ)(PR)P(QR)(PQ)(PR)(P(QR)TTTTTTTTTTTFTFFFFTTFTFTTTTTTFFFFTTTTFTTTTTTTTFTFTTFTTTFFTTTTTTTFFFTTTTTT8.利用真值表法判断下列逻辑等价式是否成立。 a) (PØQ)(QØP)b) (PQ)(QP)c) P(QR)(P

12、Q)(PR)d) Ø(PQ)PÙØQe) Ø(PÙQ)ØPÚØQf) P«Q(PÙQ) Ú(ØPÚØQ)g) P(QP)ØP(QØP)h) (PR)Ù(QR)PÚQRi)(P«Q)«RP«(Q«R)解a) 成立。PQØPØQPØQQØPTTFFFFTFFTTTFTTFTTFFTTTT此真值表最后两列全完相同。故a) 的逻辑等价式成立。b)

13、 不成立。PQPQQPTTTTTFFTFTTFFFTF此真值表最后两列不完全相同。故b) 的逻辑等价式不成立。c) 成立。PQRPQPRQRP(QR)(PQ)(PR)TTTTTTTTTTFTFFFFTFTFTTTTTFFFFTTTFTTTTTTTFTFTTFTTFFTTTTTTFFFTTTTT此真值表最后两列完全相同。故c) 的逻辑等价式成立。d) 成立。PQØQPQØ(PQ)PÙØQTTFTFFTFTFTTFTFTFFFFTTFF此真值表最后两列完全相同。故d) 的逻辑等价式成立。e) 成立。PQØPØQPÙQØ

14、 (PÙQ)ØPÚØQTTFFTFFTFFTFTTFTTFFTTFFTTFTT此真值表最后两列完全相同。故e) 的逻辑等价式成立。f) 成立。PQØPØQP ÙQØP ÙØQP«Q(PÙQ)Ú(ØPÙØQ)TTFFTFTTTFFTFFFFFTTFFFFFFFTTFTTT此真值表最后两列完全相同。故f) 的逻辑等价式成立。g) 成立。PQØ PQPQØ PP(QP)Ø P(QØ P)TTFTFTTT

15、FFTTTTFTTFTTTFFTTTTT此值表最后两列完工全相同。故f) 逻辑等价式成立。h) 成立。PQRPRQRPÚQ(PR)Ù(QR)PÚQRTTTTTTTTTTFFFTFFTFTTTTTTTFFFTTFFFTTTTTTTFTFTFTFFFFTTTFTTFFFTTFTT此真值表最后两列完全相同。故h) 的逻辑等价式成立。i) 成立。PQRP«QQ«R(P«Q)«RP«(Q«R)TTTTTTTTTFTFFFTFTFFFFTFFFTTTFTTFTFFFTFFFTTFFTTFTTFFFTTFF此真值表最后

16、两列完全相同。故i) 的逻辑等价式成立。9.东东的爷爷带东东乘车去玩，当路过一座高楼时，爷爷说：“你只有现在好好学习，将来才能住上这样的高楼。”东东听了爷爷的话以后，回答说，“爷爷决有住上这样的高楼，所以爷爷没有好好学习。”请问：东东是否误解了爷爷原话的意思，为什么解 东东误解了爷爷原话的意思。因为若令：P：(你)现在好好学习 Q：(你)将来住上这样的高楼则爷爷的原话形式化为：QP而东东的回答形式化是：ØQØP这两个公式不是逻辑等价的。这可用真值表法证明如下：PQØPØQQPØQØPTTFFTTTFFTTFFTTFFTFFTTTT此真

17、值表最后两列不完全相同，说明QP与ØQØP不是逻辑等价的（事实上QPØPØQ），所以，东东的回答与爷爷的原话是不等价的，不是一个意思。因而，东东误解了爷爷原话的意思。10.某单位派人外出学习。但由于工作关系，A，B两个不能同去。如果B去则C必须留下工作。如果派D去则B和C至少应去一人。试问 a) 四人中最多能派几人？b) 若己决定派B去，是否还可以增派其它人？请通过对成真指派的分析给出上面问题的最佳人选。解 令：P：A去 Q：B去 R：C去 S：D去则问题形式化为一公式（条件公式）：=Ø(PÙQ) Ù(QØR) &

18、#217;(S(QÚR)a) 因四人全去,得到赋值1(T，T，T，T)，使得真值(1)F，从而四人全去不行, 故至多只能派三人同去。又因A和B不能同时去，而A去，C去，D去，得到赋值2(T，F，T，T)，使得真值(2)T，故至少可以派三个人同去。所以，四人中最多能派三人同去。b) 若己决定派B去，则根据Ø(PÙQ)，可知不能派A去；又根据(QØR)，可知不能派C去，因而至多只能增派D去。从而得到赋值3(F，T，F，T)，使得真值(3)T。故此，若己决定派B去，则还可以增派D同去。11.利用真值表判断下列公式的永真性（有效性）。a) ØP(PQ)

19、b) (PQ)(QR)(PR)c) (PÚQ)ÙR)Ú(PÙQØR)d) (P(QR)«(Q(PR)解 a)ØP（PQ）PQØPPQØP(PQ)TTFTTTFFFTFTTTTFFTTT 因为此值表的最后一列全是T, 故公式是有效的。b) (PQ)(QR)(PR)PQRPQQPPR(QR)(PR)(PQ)(QR)(PR)TTTTTTTTTTFTFFTTTFTFTTTTTFFFTFFTFTTTTTTTFTFTFTTTFFTTTTTTFFFTTTTT因为此真值表的最后一列全是T, 故公式是有效的。c) (P&#

20、218;Q)ÙR)Ú(PÙQ)ØR)PQRPÚQQÙPØR(PÚQ)ÙRPÙQØR(PÚQ)ÙR)Ú(PÙQØR)TTTTTFTFTTTFTTTFTTTFTTFFTTTTFFTFTFTTFTTTFFTTTFTFTFTFTTFFTFFFFTTFFFFFTFTT因为此真值表的最后一列全是T, 故公式是有效的。d) (P(QR)«(Q(PR)PQRQRPRP(QR)Q(PR)TTTTTTTTTFFFFFTFTTTTTTFFTFTTF

21、TTTTTTFTFFTTTFFTTTTTFFFTTTT因为此真值表的最后两列完全相同, 故公式是有效的。12.利用真值表证明下列逻辑蕴涵式。 a)Ø(PQ)Pb)ØQÙ(PQ) ØPc) (PÚQ)Ù(PR) Ù(QS) RÚSd)ØP(QÙØQ) P证 a) 逻辑蕴涵式Ø(PQ)P成立。PQPQØ (PQ)PTTTFTTFFTTFTTFFFFTFF因为此真值表凡是Ø(PQ)列为T的行，P列相应的行也为T。b) 逻辑蕴涵式ØQÙ(PQ)

22、 ØP成立PQØQPQØQÙ(PQ)Ø PTTFTFFTFTFFFFTFTFTFFTTTT因为此真值表凡是Ø QÙ(PQ)列为T的行，ØP列相应的行也为T。c) 逻辑蕴涵式(PÚQ)Ù(PR) Ù(QS) RÚS成立。PQRSPÚQPÚRQS(PÚQ)Ù(PR)Ù(QS)RÚSTTTTTTTTTTTTFTTFFTTTFTTFTFTTTFFTFFFFTFTTTTTTTTFTFTTTTTTFFTTFTFTTFFFTFTF

23、FFTTTTTTTTFTTFTTFFTFTFTTTTTTFTFFTTFFFFFTTFTTFTFFTFFTTFTFFFTFTTFTFFFFFTTFF因为此真值表凡是(PÚQ)Ù(PR) Ù(QS)列为T的行，RÚS列相应的行也为T。d) 逻辑蕴涵式ØP(QÙØQ) P成立。PQØPØQQÙØQØP(QÙQ)PTTFFFTTTFFTFTTFTTFFFFFFTTFFF 因为真值表凡是ØP(QÙØQ)列为T的行，P列相应的行也为T。13.求下列

24、命题公式的代入实例。 a) P(PQ)Q)其中：P代入为PQ，Q代入为(PQ)Qb) (PQ)(QR)(PR) 其中，P代入为QR，Q代入为PR。解 a) (P(PQ)Q)(PQ)/P,(PQ)Q)/Q=(PQ)(PQ)(PQ)Q)(PQ)Q) ；b) (PQ)(QR)(PR)(QR)/P,(PR)/Q=(QR)(PR)(PR)R)(QR)R) 。14.设a1，a2，b为命题公式。如果a1a2，证明： a) Øa2Øa1b) a1Ùba2Ùbc) a1Úba2Úbd) a1ba2b 证 a)对于任一赋值，如果(Øa2)()=

25、T，则a2()=F。根据a1a2，可知a1()=F，从而(Øa1)()=T。所以Øa2Øa1成立。b) 对任一赋值，如果(a1Ùb)()=T，那么a1()=T且b()=T。根据a1a2，可得a2()=T，从而a2()=T且b()=T，也即是(a2Ùb)()=T，所以a1Ùba2Ùb成立。c) 对任一赋值，如果(a1Úb)()=T，那么a1()=T或者b()=T。于是分情况证明如下：1°若a1()=T，那么根据a1a2，可知a2()=T，因此(a2Úb)()=T；2°若b()=T，则显然

26、(a2Úb)()=T；因此，无论如何，总有(a2Úb)()=T。所以a1Úba2Úb成立。d) 对任一赋值，如果(a2b)()=T，那么若a2()=T，则b()=T。于是： 1°若a1()=F，那么显然有(a1b)()=T；2°若a1()=T，那么根据a1a2，可知a2()=T，从而有b()=T，因此得到(a1b)()=T；于是，无论如何，总有(a1b)()=T。所以a1ba2b成立。15.利用变换法证明下列逻辑等价式。 a) P(QP)ØP(PQ) b) (PR)Ù(QR)PÚQR c)Ø(P

27、«Q)(PÚQ)Ù(PÚQ) d)Ø(PQ)PÙØQ证明 a) P(QP)ØPÚ(ØQÚP) （替换定理，联结词化归） (PÚØP)ÚØQ （结合律） PÚØP (PÚØP) ÚQ PÚ(ØPÚQ) （结合律） ØØPÚ(ØPÚQ) （替换定理，双重否定律） ØP(PQ) （替换定理，联结词化归）b) (PR

28、)Ù(QR) (ØPÚR) Ù(ØQÚR) （替换定理，联结词化归） (ØPÙØQ)ÚR （分配律） Ø(PÚQ) ÚR （替换定理，de Morg an律） PÚQR （联结词化归） c) Ø(P«Q) Ø(PQ)Ù(QR) （替换定理，联结词化归） Ø(ØPÚQ)Ù(ØQÚP) （替换定理，联结词化归）Ø(ØPÚQ)

29、8;Ø(ØQÚP) （de Morgan律）(ØØPÙØQ)Ú(ØØQÙØP) （替换定理，de Morgam律）(PÙØQ)Ú(QÙØP) （替换定理，双重否定律）(PÚØP)Ù(PÚQ)Ù(ØPÚØQ)Ù(QÚØQ)（分配律、替换定理，结合律，交换律）(PÚQ) Ù (ØPÚ

30、ØQ) （化简律）d) Ø(PQ) Ø (ØPÚQ) （替换定理，联结词化归） ØØPÙØQ （de Mergan律） PÙØQ （替换定理，双重否定律）。16.利用变换法证明下列逻辑蕴涵式。 a) P(QR) (PQ)(PR)b) (PQ)Q PÚQc) (PQ)(QP)QPd) PQ PÚRQÚR证 a) 实际上，我们可证逻辑等价式：P(QR)(PQ) (PR)就是 P(QR)ØP Ú (ØQÚR) （替换定理，

31、联结词化归）(PÚØPÚR)Ù(ØPÚQÚR) （化简律）(PÙØQ)Ú (ØPÚR) （分配律）Ø (ØPÚQ)Ú (ØPÚR) （替换定理、双重否定律，de Morgan律）Ø (PQ) Ú (PR) （替换定理，联结词化归）(PQ)(PR) （联结词化归）b) 实际上我们可证逻辑等价式：(PQ)QPQ变换证明如下：(PQ)QØ (ØPÚQ)ÚQ （替换

32、定理，联结词化归）(ØØPÙØQ)ÚQ （替换定理、de Morgan律）(PÙØQ)ÚQ （替换定理、双重否定律）( PÚQ) Ù (QÚØQ) （分配律）PÚQ （化简律）c) 实际上，我们可证逻辑等价式：(PQ)(QP)QP变换证明如下 (PQ) (QP) Ø (ØPÚQ)Ú (ØQÚP) （替换定理、联结词化归） (ØØPÚØQ)Ú (ØQ

33、ÚP) （替换定理，de Morgasn律） (PÙØQ) Ú (ØQÚP) （替换定理、双重否定律） ØQÚP （吸收律） QP （联结词化归）d) PQØPÚQ （联结词化归）ØPÚQÚR （析取构成式） (ØPÚQÚR) Ù (RÚØRÚQ) （化简律） (ØPÙØR)Ú (QÚR) （分配律）Ø (PÚR)Ú

34、(QÚR) （替换定律， de Morgan律） PÚRQÚR （联结词化归）。17.求下列命题公式的对偶式。 a) (PQ)ØPÚRb) Ø (P«Q)Ù(PÚQ)c) (PQÚR)Ù(QP)解 a) 由于(PQ)ØPÚRØ(ØPÚQ) ÚØPÚR所以其对偶式为Ø(ØPÙQ)ÙØPÙR 。b) 由于 Ø (P«Q) Ù

35、; (PÚQ)Ø (PQ) Ù (QP) Ù ( PÚQ) Ø (ØPÚQ) Ù (ØQÚP ) Ú (PÚQ) Ø (PÚØQ) Ù (ØPÚQ) Ù (PÚQ)因此其对偶式为 Ø (ØPÚQ)Ù(ØPÚQ)Ú(PÙQ) 。c) 因为 (ØPQÚR) Ù (QP) (Ø

36、;ØPÚQÚR) Ù (ØQÚP) (PÚQÚR) Ù (ØQÚP)从而其对偶式为 (PÙQÙR) Ú (ØQÙP) 。18.将下列命题公式化成只含有全功能联结词集合Ø,中联结词的命题公式。 a) PÚ (QÙØR)b) (PÚQ)ÙRPÚRc) PÚ (ØQÙRP)d) Ø (P« (ØQRÚP)

37、解 a) PÚ (QÙØR) (QÙØR)ÚP (ØØQÙØR)ÚP Ø (ØQÚR)ÚP (QR)Pb) (PÚQ)ÙRPÚR(ØPQ)ÙR)(ØPR)Ø (ØPQ)ØR)(ØPR)c) PÚ (ØQÙRP)ØP(Ø (ØQØR)P) ØP(Ø (RQ)P)

38、d) Ø (P«(ØQRÚP)Ø (P(ØQRÚP) Ú (ØQRÚP)P)Ø (P(ØQ(ØPR)Ù(ØQ(ØPR)P) (P(ØQ(ØPR)Ø (ØQ(ØPR) P) 。19.证明是极小全功能的。证 根据定理2，联结词集Ø，Ú是全功能的，故为证是全功能的，只需证明Ø，Ú中的每个联结词都可分别由来表示即可。由于ØPPPPÚQ(

39、PQ)(PQ)因此是全功能的。由于中只有一个联结词，故所以是极小全功能的。20.证明Ù，Ú不是全功能的。证 Ù，Ú不是全功能的。否则，联结词Ø必定可由联结词集Ù，Ú来表示，即，对于任一原子公式P，存在公式a，a中只含联结词Ù和Ú，使得ØPa设是一对a中出现的所有命题变项及P都指派真值T的赋值。则我们可用串值归纳法证明a()T；但是(ØP)()ØTF，从而ØP不可能与公式a逻辑等价，矛盾。事实上，我们施串值归纳于a中联结词Ù和Ú的个数m，来证a (

40、)T：当m1时，只能有aPÙP或PÙQ或QÙQ,或PÚP或PÚQ或QÚQ。由于给P和Q都赋值T，故这时显然有a ()T。当m1，2，k时，归纳假设总有a ()T。则当mk+1时，只能有aa1Ùa2或a1Úa2，其中a1和a2中所含联结词Ù和Ú的个数分别为和，于是就有 即从而有，£，因此，根据归纳假设有a1()=T，a2()=T,所以a ()= a1 () Ù a2 ()=TÙT=T或者a ()= a1 () Ú a2 ()=TÚ T=T 总之a

41、()=T。 21.将下列命题公式化为析取范式。 a) ØPÚØQ(P«ØQ) ÚRb) (PÚ (ØPQ) Ù (QR)c) (PQÙR) Ù (ØPØQÙØR)d) Q Ù (ØPQ ÚØ (QR)解 a) (ØPÚØQ)(P«ØQ)ÚR Ø (ØP ÚØQ) Ú (PØQ) Ù

42、; (ØQP) ÚR) (ØØP ÙØØQ) Ú (ØP ÚØQ) Ù (ØØQ ÚP) ÚR) (PÙQ)Ú (ØPÙP)Ú (ØQÙP)Ú (ØPÙQ)Ú (ØQÙQ)ÚR (PÙQ)Ú (PÙØQ)Ú (ØPÙQ)Ú

43、;Rb) (PÚ (ØPQ) Ù (QR)(PÚ (ØØPÚQ) Ù (ØQÚR)(PÚPÚQ) Ù (ØQÚR)(PÚQ)Ù (ØQÚR)(PÙØQ)Ú (QÙØQ)Ú (PÙR)Ú (QÙR)(PÙØQ)Ú (PÙR) Ú (QÙR)c) (P(QR)(P

44、(QR)(ØPÚ (QÙR) Ù (ØØPÚ (ØQÙØR)(ØPÚ (QÙR) Ù (PÚ (ØQÙØR)(ØPÙP) Ú (QÙRÙP) Ú (ØPÙØQÙØR) Ú (QÙRÙØQÙØR)(PÙQÙR) Ú (&#

45、216;PÙØQÙØR)d) QÙ (ØP(QÚØ (QR)QÙ (ØØPÚ (QÚØ (ØQÚR)QÙ (QÚPÚØ (ØQÚR)Q22.将上题的各命公式化为主析取范式。解 a) (ØPÚØQ)(P«ØQ)ÚR) (PÙQ)Ú (PÙØQ)Ú (ØP

46、7;Q)ÚR(PÙQ) Ù (RÚØR)Ú (PÙØQ) Ù (RÙØR) Ú (ØPÙQ) Ù (RÚØR) Ú (QÚØQ) ÙR) (PÙQÙR) Ú (PÙQÙØR) Ú (PÙØQÙR) Ú (PÙØQÙØR) Ú (&

47、#216;PÙQÙR) Ú (ØPÙQÙØR) Ú (QÙR) Ú (ØQÙR)(PÙQÙR)Ú (PÙQÙØR)Ú (PÙØQÙR)Ú (PÙØQÙØR)Ú (ØPÙQÙR) Ú (ØPÙQÙØR) Ú (PÚ

48、6;P)Ù(QÙR) Ú (PÚØ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Ù

49、;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)m7Úm6Úm5&#

50、218;m4Úm3Úm2Úm1 b) (PÚ (ØPQ) Ù (QR) (PÙØQ)Ú (PÙR) Ú (QÙR) (PÙØQ)Ú (RÙØR) Ú (PÙR)Ú(OÙØQ) Ù (PÙØP)Ú (QÙR) (PÙØQÙR) Ú (PÙØQÙØR)&

51、#218; (PÙQÙR)Ú(PÙØQÙR)Ú (PÙQÙR)Ú (ØPÙQÙR) (PÙQÙR)Ú (PÙØQÙR) Ú (PÙØQÙØR) Ú (ØPÙQÙR) m7Úm5Úm4Úm3 c) (PQÙR) Ù (ØPØQÙØR

52、) (PÙQÙR)Ú (ØPÙØQÙØR) m7Úm0 d) QÙ(ØP(QÚØ(QR) Q (PÙQ)Ú (ØPÙQ) (PÙQ) Ù (RÙØR) Ú (ØPÙQ) Ù (RÙØR) (PÙQÙR) Ú (PÙQÙØR)Ú (ØPÙQ&

53、#217;R)Ú (ØPÙQÙØR) m7Úm6Úm3Úm223.通过化主析取范式的方法，判断下面的逻辑等价式是否成立。 a) (PÙQ) Ú (ØPÙQÙR)(PÚ (QÙR) Ù (QÚ (ØPÙR) b) ØPÚ (PÙQ) ÚRØ (PÙØQ) Ù (QÚR)解 a) 因为 (PÙQ) Ú

54、(ØPÙQÙR) (PÙQ) Ù (RÚØR) Ú (ØPÙQÙR) (PÙQÙR) Ú (PÙQÙØR) Ú (ØPÙQÙR) m7Úm6Úm3又因为(PÚ (QÙR) Ù (QÚ (ØPÙR) (PÙQ)Ú (QÙRÙQ)Ú (PÙØP

55、ÙR) Ú (QÙRÙØPÙR) (PÙQ) Ú (QÙR) Ú (ØPÙQÙR) (PÙQ) Ù (RÚØR)Ú (PÚØP) Ù (QÙR) Ú (ØPÙQÙR) (PÙQÙR) Ú (PÙQÙØR) Ú (PÙQÙR) Ú (

56、6;PÙQÙR) Ú (ØPÙQÙR) (PÙQÙR)Ú (PÙQÙØR)Ú (ØPÙQÙR) m7Úm6Úm3 所以 (PÙQ)Ú (ØPÙQÙR)(PÚ (QÙR) Ù (QÚ (ØPÙR) b) 因为 ØPÚ (PÙQ)ÚR (ØPÙ (Q&#

57、218;ØQ) Ú (PÙQ) Ù (RÚØR) Ú (QÚØQ) ÙR) (ØPÙQ) Ú (ØPÙØQ) Ú (PÙQÙR) Ú (PÙQÙØR) Ú (QÙR) Ú (ØQÙR) (PÙQÙR)Ú(PÙQÙØR) Ú (ØPÙ

58、;Q) Ù (RÚØR) Ú (ØPÙØQ) Ù (RÚØR)Ú (PÚØP) Ù (QÙR) Ú (PÚØP) Ù (ØQÙR) (PÙQÙR)Ú(PÙQÙØR)Ú(ØPÙQÙR)Ú (ØPÙQÙØR) Ú (ØP&#

59、217;Ø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) 

60、18; (ØPÙQÙØR) Ú (ØPÙØQÙR) Ú (ØPÙØQÙØR) m7Úm6Úm5Úm3Úm2Úm1Úm0又因为 Ø (PÙØQ) Ù (QÚR) (ØPÚØØQ) Ù (QÚR) (ØPÚQ) Ù (QÚR) QÚ

61、(ØPÙR) (PÚØP) ÙQ) Ú (ØPÙ (QÚØQ)ÙR) (PÙQ) Ú (ØPÙQ) Ú (ØPÙQÙR) Ú (ØPÙØQÙR) (PÙQ) Ù (RÚØR) Ú (ØPÙQ) Ù (RÚØR) Ú (ØPÙQ&#

62、217;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)

63、Ú (ØPÙQÙØR) Ú (ØPÙØQÙR) m7Úm6Úm3Úm2Úm1 所以ØPÚ (PÙQ) ÚR与Ø (PÙØQ) Ù (QÚR)不逻辑等价。24.设计一个控制两间会议室的照明电路，要求分别装在这两间会议室的两只开关都能控制整个会议室的照明。解 会议室两个门旁开关表示k1、k2，“0”表示开关断开，“1”表示开关接通。S表示会议室的照明状态，“1”表示全室灯

64、亮，“0”表示全室灯暗。假设开始时，室内无人，灯暗。两只开关都处于“0”状态。有人进入室内时，随手改变门旁的开关状态，则会议室灯亮，S为“1”。此时两只开关中有一只（奇数）处于“0”状态。当有人离开会议室时，随手改变门旁的开关状态，会议室灯暗，S为“0”。此时两只开关（偶数）都处于“0”状态。故此,我们有: 当有偶数只开关处于“0”状态时，S为“0”； 当有奇数只开关处于“0”状态时，S为“1”；所以，我们有:S(Øk1Ùk2)Ú (k1ÙØk2)(k1Úk2) Ù (Øk1ÚØk2)其电路图如

65、图所示：K1K2非门非门或门与门S或门第24题图25.某公安员在追捕一个逃犯的途中面对前面具有两条路分叉的路口。己知该路口住着两个居民，其中一个说谎成性，另一个天性诚实。请问：该公安员如何发问才能确定逃犯的去向。解 公安人员手指一路问身旁一名居民说：“逃犯是从这条路逃走的，他（指另一居民）将回答是，你说对吗？”当被问居民回答：“否”时，公安人员应从所指那条路去追逃犯；当被问居民回答“对”时，公安人员应从另一条路去追逃犯。分析：如果被问居民诚实，他回答“对”。则另一居民是说谎者，他回答“是”，那么，逃犯没有从所指路逃走；如果被问居民诚实，他回答“否”。则另一居民是说谎者，他回答“否”，那么，逃犯

66、是从所指路逃走的；如被问居民说谎，可以此类推分析。形式化：设P：被问居民是诚实的Q：被问居民回答“是”R：另一居民回答“是”S：逃犯是从所指路逃走的则 S(PÙØQ) Ú (ØPÙØQ) (PÚØP)ÙØQ ØQRP«Q真值表如下：PQRSØQP«QTTTFFTTFFTTFFTFFFFFFTTTT即：“逃犯是从所指路逃走的”当且仅当“被问居民诚实且其回答是否”（即另一人不诚实因而将回答“否”）或者“被问战士说谎且其回答是否”（即另一人诚实因而将回答是“是”

67、）当且仅当“被问战士回答是否”。并且“另一居民回答是是”当且仅当“被问居民诚实且其回答是是”或者“被问居民说谎且其回答是否”。26.证明析取消去规则（Ú）和否定规则（Ø）都是可靠的。证(a)析取消去规则（Ú）为：GaÚb，G,ag，G,bg Þ Gg 其可靠性为要性：GaÚb，G,ag，G,bg Þ Gg 证法一：令：d为G中所有公式之合取式。根据定理2，则要证：daÚb，dÙag，dÙbg Þ dg 根据定理1，即要证：daÚb，dÙag，dÙbg &#

68、222; dg 即要证：(daÚb)Ù(dÙag)Ù(dÙbg) Þ dg （*）但是我们能够证明：(daÚb)Ù(dÙag)Ù(dÙbg)dg （* *）事实上：(daÚb)Ù(dÙag)Ù(dÙbg)(ØdÚaÚb)Ù(ØdÚØaÚg)Ù(ØdÚØbÚg)ØdÚ (aÚb)&

69、#217;(Ø(aÙb)Úg)ØdÚ (aÚb)Ùg)(ØdÚ aÚb)Ù(ØdÚg)ØdÚgdg因此，根据（* *）可知（*）成立。所以析取消去法规则（Ú）是可靠的。证法二：令：d为G中所有公式之合取式。根据定理2，则要证：daÚb，dÙag，dÙbg Þ dg对于任一赋值，若d ()=T，则由daÚb，可得(aÚb)()=T，于是有a ()=T或者b ()=T。(i) 若a ()=T，则(dÙa)()=T，从而由dÙag，可得g ()=T；(ii) 若b ()=T，则(dÙb)()=T，从而由dÙbg，可得g ()=T；综合（i）（ii），总有g ()=T。所以，由赋值的任意性，dg。（b）否定消去规则（Ø）为：G,Øag，G,ØaØg Þ Ga 其