北科大 离散数学习题解答汇总.docx

北科大 离散数学习题解答汇总第一章习题 1 填空题 a+b=a，当且仅当b=0。 假。 2。 ØP®(ØQ®R) P为真且Q为假。 4。 永假式；永真式。 T.F，T.F N222F；M0ÙM1ÙM2ÙM3或(M00ÙM01ÙM10ÙM11)。 (10) P。 2选择题 C C C C C C D C A C 3.判断下列语句是否是命题，若是试将其符号化。 是。P 是。P 是。P 是。P 是。P 不是。 是。令P：太阳出来，Q：天下雨，R：阴天，S：温度下降 则原命题可表示为：ØP®QÚ(RÙS) 不是。 不是。 是。令P：我给你写了信，Q：信在路上丢了， 则原命题可表示为：P®Q 4试做出下列公式的填表 (ØP)Ù(ØQ)=A P T T F F Q T F T F A F F F T A=Ø(PÙQ)®(Ø(PÚQ) P T T F F Q T F T F A T F F F A=(P®(Q®R) P T T T T F F F F Q T T F F T T F F R T F T F T F T F A T F T T T F F F A=(PÙQ)®R) P T T T T F F F F Q T T F F T T F F R T F T F T F T F A T F T T T T T T 注：该题公式与等值，故真值表相同。 A=(P«(ØQ)UQ) P Q A T T F F T F T F T T F F (6)A=(PÙQ)Ú(RÙS) P T T T T T T T T F F F F F F F F Q T T T T F F F F T T T T F F F F R T T F F T T F F T T F F T T F F S T F T F T F T F T F T F T F T F A T T T T T F F F T F F F T F F F (7)A=(ØP)ÙQ)®(ØQ)ÙR) P Q R A T T T T T T F T T F T T T F F T F T T F F T F T F F T T F F F F A =(P®(Q®R)®(P®Q)®(P®R) P Q R A T T T T F F F F T T F F T T F F T F T F T F T F F T T F F F F F 5联结词“¯”和“­”有下列等式关系 ¯）(1)P­Q=T (2) P¯Q=T(TP)­(TQ) (1) 证明：T(TP)¯(TQ)ÛT(T(TPÈTQ)ÛT(PÇQ)=P­Q (2) 同理可证 6证明下列公式对是等价的。 (1) 证明 P®QÛ(TQ®TP) 证明：右 ÛØ(ØQÚØ(P)ÛQÚ(ØP)Û(ØP)ÚQÛP®Q=左 (2) 证明 (PÙQ)ÙR)Û(PÙR)Ú(QÙR) 证明 ：利用“Ù”关于“Ú”的分配律有 左Û(PÙR)Ú(QÙR)Û右 (3) 证明 (ØP)Ù(ØQ)®(ØR)Û(R®(QÚP) 证明： 左Û(Ø(ØP)Ù(ØQ)Ú(ØR)Û(PÚQ)Ú(ØR) Û(ØR)Ú(QÚP)Û(R®(QÚP)Û右 证明 (ØP)ÚQ)®R)Û(PÙ(ØQ)ÚR) 证明 左Û(Ø(ØP)ÚQ)ÚR)Û(PÙ(ØQ)ÚRÛ右 证明 (P®Q)Ù(R®Q)Û(PÚR)®Q) 证明 ： 左Û(ØPÚQ)Ù(ØRÚQ)Û(ØPÙØR)ÚQ) Û(Ø(PÚR)ÚQ)Û(PÚR®Q)Û右 证明 Ø(P«Q)Û(PÚQ)ÙØ(PÙQ) 证明：左ÛØ(PÙØQ)Ù(ØPÚQ)ÛØ(PÚØQ)ÚØ(ØPÚQ) Û(ØPÙQ)Ú(PÙØQ)Û(PÚØP)Ù(ØPÙØQ)Ù(QÚP)Ù(QÚØQ) Û(PÚQ)Ù(ØPÚØQ)Û(PÚQ)ÙØ(PÙQ)Û右 证明 (P®(P®Q)®(Q®(P®R)Û(PÚQ)ÙØ(ØPÙ(ØQÙØR)Ú(ØPÙØQ)Ú(ØPÙØR)证：左ÛØ(ØPÚ(ØQÚR)Ú(ØQÚ(ØPÚR) Û Ø(ØPÚ(ØQÚR)Ú(ØQÚØPÚR) ÛT 右Û (PÚQ)ÙØ(ØPÙ(ØQÙØR)Ú(ØPÙØQ)Ú(ØPÙØR) Û(PÚQ)Ù(PÚ(QÙR)Ú(ØPÙ(ØQÚØR)Û(PÚQÚØP)Ù(PÚQ)Ù(ØQÚØR)Ù(PÚ(QÙR)ÚØP)Ù(PÚ(QÙR)Ú(ØQÙØR)ÛTÙTÙTÙ(PÚ(QÙR)ÚØ(QÙR)ÛT 所以 左Û右 证明(P®Q)Ù(R®Q)Û(PÚR)®Q 证：左Û(ØPÙQ)Ù(ØRÚQ)Û(ØPÙØR)ÚQ ÛØ(PÚR)ÚQÛ(PÚR)®QÛ右 证明(PÙQÙA®C)Ù(A®PÚQÚC)Û(AÙ(P«Q)®C 证明：右Û(AÙ(P®Q)Ù(Q®P)®C ÛØ(AÙ(P®Q)Ù(Q®P)ÚCÛØ(AÙ(ØPÚQ)Ù(ØQÚP)ÚCÛØAÚ(PÙØQ)Ú(QÙØP)ÚCÛ(ØAÚP)Ù(ØAÚØQ)Ú(QÚC)Ù(ØPÚC)Û(ØAÚPÚQÚC)Ù(ØAÚPÚØPÚC)Ù(ØAÚØQÚQÚC)Ù(ØAÚØQÚØPÚC)Û(ØAÚ(PÚQÚC)ÙTÙTÙ(Ø(AÙQÙP)ÚC) 证明(P®(Q®R)Û(Q®(P®R) 证：左Û(ØPÚ(ØQÚR)Û(ØQÚ(ØPÚR) Û(Q®(P®Q)=右 7略 8化简下面的命题公式 AÚ(ØAÚ(BÙØB)ÛAÚ(ØAÚF)=AÚØA=T (AÙBÙC)Ú(ØAÙBÙC)Û(AÚØA)Ù(BÙC) ÛTÙ(BÙC)ÛBÙC (A®B)«(ØB®ØA)ÙCÛ(ØAÚB)®(BÚØA)ÙC ÛTÙCÛC (P®Q)«(ØQ®ØP)ÙRÛ(ØPÚQ)«(QÚØP)ÙR ÛTÙRÛR 9解：当AÙCÛBÙC时 未必有AÛB 因为当C=F时 对任何命题公式A与B 恒有AÙCÛBÙC 10解：若ØAÛØB 则必有AÛB 因为当ØA«ØB为永真公式时 A«B11设三元联结词f定义如下： 也是永真公式。 e1 T T T T F F F F e2 T T F F T T F F e3 T F T F T F T F f(e1,e2,e3) F T T T F F T T 解 由f的定义，不难看出 ØPÛf(P,P,P)PÚQÛf(f(P,P,P),f(P,P,P),f(Q,Q,Q)因为Ø,Ú是功能完备的，所以联结词f是最小完备的。 由于 P®QÛf(P,P,f(Q,Q,Q)PÙQÛØf(P,P,Q)所以由于P®QÛØPÚQÛf(P,P,P)ÚQ Ûf(f(f(P,P,P),f(P,P,P),f(P,P,P),f(f(P,P,P),f(P,P,P),f(P,P,P),f(Q,Q,Q)12.解：首先，将公式(ØPÚQ)®PÙØQ)ÚØ(ØQ®ØP)化简成与之等价的公式： 原式Û(Ø(ØPÚQ)Ú(PÙØQ)ÚØ(QÚØP) Û(PÙØQ)Ú(PÙØQ)Ú(PÙØQ) ÛPÙØQ 从而该公式所表达的含义为“我今天没课，但也没法去阅览室。” 13判断下列公式是永真公式、永假公式还是其他。 解：(PÚQ)®(PÙQ)ÛØ(PÚQ)Ú(PÙQ)Û(ØPÙØQ)Ú(PÙQ) 因为它的主析取范式没含有所有的极小项。因此，他是一个可满足式。 (P®Q)ÙQ)«(QÚR)ÙQ)Û(ØPÚQ)ÙQ)«(RÙQ)ÚQ) Û(ØPÙQ)ÚQ«(RÙQ)ÚQ 因此，它是一个重言式。 Ø(Q®P)ÚØP)Ù(PÚR)ÛØ(ØQÚPÚØP)Ù(PÚR)=F 因此，它是一个矛盾式。 (ØPÚQ)®R)®(PÙØQ)ÚR) Û(P®Q)®R)®(Ø(P®Q)ÚR)Û(P®Q)®R)®(P®Q)®R) ÛT因此，它是一个重言式。 (PÚQ)ÙR)®(PÚ(QÙR)Û(ØPÙØQ)ÚØR)Ú(PÚ(QÙR) Û(ØPÚØR)Ù(ØQÚØR)Ú(PÚQ)Ù(PÚR)Û(ØPÚØRÚPÚQ)Ù(ØPÚØRÚPÚR)Ù(ØQÚØRÚPÚQ)Ù(ØPÚØRÚPÚR)ÛT因此，它是一个重言式。 (6)(ØPÙØQ)®ØR)«(RÙØ(PÚQ) Û(PÚQÚØR)«(RÙØPÙØQ)ÛØ(RÙØPÙØQ)«(RÙØPÙØQ) 因此他是一个永假式。 (7)(P«Q)ÙR)Ú(PÚQ)ÙØR) Û(PÙQ)Ú(ØPÙØQ)ÙR)Ú(PÙØR)Ú(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)®(Q®R)«(Q®(PÚR) Û(PÚØQ)Ú(ØQÚR)«(Q®(PÚR) Û(PÚØQÚR)®(PÚØQÚR) 因此它是一个重言式 14.求下列公式的主吸取范式及主合取范式： 解：(1) Ø(PÙQ)«Ø(ØP®R) Û(PÙQ)Ù(PÚR)Ú(Ø(PÙR)ÙØ(ØP®R) Û(PÙQÙP)Ú(PÙQÙR)Ú(ØPÚØQ)Ù(ØP®ØR) Û(PÙQ)Ú(PÙQÙR)Ú(ØPÙØ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)ÙQÚR ÛØ(PÚQ)ÙQÚR Û(PÙØQ)ÙQ)ÚR ÛRÛ(QÚR)Ù(Ø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®R)Ù(P«Q) Û(PÚR)(ØPÚQ)Ù(PÚØ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ÙP)Ú(ØPÙØQÙØR)Ú(PÙQÙR)Ú(QÙRÙØQÙØR) Û(PÙQÙR)Ú(ØPÙØQÙØR)Ûm111Úm000 这便是该公式的主析取范式。 主合取范式为M001ÙM010ÙM011ÙM100ÙM101ÙM110 Û(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)Ù(QÚØR) Û(ØPÚQÚR)Ù(ØPÚØQÚR)Ù(ØPÚQÚØR) ÛM100ÙM001ÙM101 这便是该公式的主合取范式。 主析取范式为m000Úm101Úm011Úm110Úm111Û(PÙQÙR)Ú(ØPÙQÙØR)Ú(ØPÙQÙR)Ú(PÙQÙØR)Ú(ØPÙØQÙØR)(6)略 (7) P®(P®Q)ÚØ(ØQÚØP)ÛØPÚ(ØPÚQ)Ù(QÙP)ÛØPÚ(ØPÙQÙP)Ú(QÙQÙP)ÛØPÚ(PÙQ)Û(ØPÙQ)Ú(ØPÙØQ)Ú(PÙQ)Ûm10Úm11Úm00这便是该公式的主析取范式 主合取范式为M01ÛPÚØQ Ø(P®ØQ)®R)ÛØ(Ø(ØPÚØQ)ÚR)Û(ØPÚØQ)ÚØRÛ(ØPÙØR)Ú(ØQÙØR)Û(ØPÙQÙØR)Ú(ØPÙØQÙØR)Ú(PÙØQÙØR)Ú(ØPÙØQÙØR) Û(PÙØQÙØR)Ú(ØPÙQÙØR)Ú(ØPÙØQÙØR)Ûm100Úm010Úm000这便是该公式的主析取范式 主合取范式为M001ÚM011ÚM101ÚM110ÚM111Û(PÚQÚØR)Ù(PÚØQÚØR)Ù(ØPÚQÚØR)Ù(ØPÚØQÚR)Ù(ØPÚØQÚØR)(QÚØP)®RÛØ(QÚØP)ÚRÛØ(QÚP)ÚRÛ(ØQÚR)Ù(PÚR)Û(PÚØQÚR)Ù(ØPÚØQÚR)Ù(PÚQÚR)Ù(PÚØQÚR) Û(PÚØQÚR)Ù(ØPÚØQÚR)Ù(PÚQÚR)ÛM010ÙM110ÙM000这便是该公式的主合取范式 主析取范式为M001ÙM011ÙM100ÙM101ÙM111 Û(ØPÙØQÙR)Ú(ØPÙQÙP)Ù(PÙQÙØR)Ù(PÙØQÙP)Ù(PÙQÙP) 16.试证下列蕴函关系. Þ(P®Q) 证：因为®(P®Q)ÛØ(PÙQ）Ú(ØPÚQ)Û(ØPÚØQ)Ú(ØPÚQ)ÛT 所以®QÞPÚQ 证：利用真值表法 令 A=®Q)®(PÚQ),z则公式A的真值表为 P T T F F Q T F T F ®QÞPÚQ. Ø(PÙØq),ØqÚR,ØRÞØP 证：利用真值法：设公式Ø(PÙØq),ØqÚR,ØR均为T。 则R为F，由ØqÚR为T，知Øq为T，从而q为F。 再由Ø(PÙØq)为T知：PÙØq为F。以及q为F知：P为F。 因此，ØP为T。即 Ø(PÙØq),ØqÚR,ØRÞØP p®(qÚR),(SÚT)®P,SÚTÞqÚR )®P,SÚT均为真。 证：设公式p®(qÚR),(SÚT由SÚT真及(SÚT再由p®(qÚR)®P真知P真。 )真及P真知qÚR真 )®P,SÚTÞqÚR 因此p®(qÚR),(SÚTPÙQ,(P«Q)®(RÚS)ÞSÚR )®(RÚS)真。由PÙQ真可推出P«Q真。 证：设PÙQ真，(P«Q再由(P«Q)®(RÚS)真，可推出RÚS真，即SÚR真。 )®(RÚS)ÞSÚR )ÙØR,Ø(ØQÙS)ÞØS )ÙØR,Ø(ØQÙS)均为真 因此，PÙQ,(P«Q(ØQÚRP®Q，(ØQÚR证：设P®Q，由(ØQÚR)ÙØR真ÞØQÚR真且ØR真ÞØQÚR真且R假 ÞØQ真。再P®Q真ÞØQ®ØP真。从而ÞØP真。 再由Ø(ØPÙS)真ÞØSÚP真ÞS®P真ÞØP®ØS真 从而ØS真。 因此，该蕴涵关系成立 (9) (P®(Q®R)Þ(P®Q)®(P®R) 证： (P®(q®R)®(P®Q)®(P®R) ÛØ(ØPÚØqÚR)Ú(Ø(ØPÚq)Ú(ØPÚR) Û(PÙqÙØR)Ú(PÙØq)Ú(ØPÚR) Û(PÙqÙØR)Ú(PÚØPÚR)Ù(ØqÚØPÚR) Û(PÙqÙØR)Ú(ØPÚØqÚR) Û(PÙqÙØR)ÚØ(PÙqÙØR)ÛT 因此，ÚÚÚ FB=Ú FC= 20.解：因为A的主合取范式为M001ÙM100ÙM010 所以A的主析取范式为m000Úm011Úm101Úm110Úm111 ÚÚÚ 即AÛÚ 21.证：因为«,Ø不是完备的，所以«,Ø不是最小完备联结同集. 因为Ñ，Ø不是完备的，所以Ñ，Ø不是最小完备联结同集. 22证：因为VÙ®均不是完备的，例如公式ØP不可由它们单独表示，所以，它们都不是最小完备联结同集. 23 .证：由命题1.37得知®.Ø是完备的.且联结词Ø不能由联结词®表示，所以，®.Ø是最小完备联结词集。 ¾®Q=Ø(P®Q),所以¾¾®,Ø也是最小完备联结词。 由因为 P¾CC24.利用CP规则证明： (1)P®(Q®R),(RÙS)®T,ØSÚT®WÞ(PÙQ)®W 证：PÙQ P (2)P T,(1),I1 (3)P®(Q®P) P (4)Q®R T,(2),(3),I11 (5)Q T,(1),I2 (6)R T,(4),(5),I11 (7)RÙS®T P (8)ØRÚØSÚT T (7) E (9)R®ØSÚT T (8) E (10)ØSÚT T,(6),(9),I11 (11)ØSÚT®W P (12)W T,(10),(11),I11 (13)(PÙQ)®W C P (1).(12) (2) ØPÚQ,ØQÚP,R®SÞP®S 证：(1)P P (2) ØPÚQ P (3) ØQÚR P (4)R®S P (5)P®Q T (2) (6) Q®R T (3) (7)P®R T,(5),(6),I13 (8)P®S T,(4),(7,I13 (9)S T,(1),(8),I11 (10) P®S C P (1) (9) P®QÞP® 证： (1)(3)PQPPT,(1),(2),I11 T,(1),(3),I9CP(1),(4)(2)P®Q(4)PÙQ(5)P®(PÙQ)P®(QÙR),ØQÚS,(T®ØS),Q®(PÙØT)ÞQ®T 证： (1)QPPT(2),ET,(1),(3)IPT,(4),(6),IT,(7)T(8),ICP,(1),(9)(2)ØQÚS(3)Q®S(4)S(5)(T®ØW)®ØS(7)Ø(T®ØW)(8)TÙW(9)T(10)Q®T(6)S®Ø(T®ØW)T(5),E(PÚQ)®RÞ(PÙQ)®R 证： (1)PÙQ(2)P(3)PÚQPT(1)I1T(2)I3(4)(PÚQ)®RP(5)RT(3),(4)I11(6)PÙQ®RCP(1),(5)(PÚQ)®(RÙs),(SÚT)®WÞP®W证：P P PÚQ TI (PÚQ)®(RÙS) P RÚS TI11 R T.I1 RÚT TI3 (RÚT)®W P W T. P®W CP. 3I11 (P®Q)®R,(RÚS)®W,7X®(SÙ7W)ÞP®(Q®X) 证 P P Q Q P®Q T.CP (P®Q)®R P R T. (P®S)®W P R®7SÚW TE 7X®(SÙ7W) P 7(SÙW)®X TE 7SÚW®X TE R®X TI13 X T. Q®X CP P®(Q®X) CP 25解：由条件、分别有下列命题公式 A®C，B®ØC，ØC®AÚB 求它们的合取式得 I11 I11 (A®C)Ù(B®ØC)Ù(ØC®AÚB) Û(ØAÚC)Ù(ØBÚØC)Ù(CÚAÚB)Û(ØAÚBÚC)Ù(ØAÚØBÚC)Ù(AÚØBÚØC)Ù(ØAÚØBÚØC)Ù(AÚBÚC)Û(AÚBÚC)Ù(AÚØBÚØC)Ù(ØAÚBÚC)Ù(ØAÚØBÚC)Ù(ØAÚØBÚØC) ÛM000ÙM011ÙM100ÙM110ÙM111 Ûm001Úm010Úm101 Û(ØAÙØBÙC)Ú(ØAÙBÙØC)Ú(AÙØBÙC) 所以，立项方案有三种； 第一种：C上，A、B不上； 第二种：B上，A、C不上； 第三种：A、C上，B不上。 26解：令P：营业员A作案. Q：营业员B作案. R:：营业员A提供正确证词. S：作案时间为营业时间. T：货柜上了锁. 则侦察结果可写成如下的命题公式 PÚQ Q®ØS，R®ØT ØR®S，T 推理如下：T P R®ØT P T®ØR T(2)E ØR T(1)、(3) Q®ØS P ØR®S P S®ØQ T(5)E (7)I13 ØR®ØQ T(6)、(8)I11 ØQ T(4)、PÚQ P (10)I P T(9)、 所以作案者为A。 27.解：令P：文件系统加锁 Q：新消息将被排成队 R：系统正常运行 S：新消息被送入缓冲区 则符号化为ØP®Q，ØP«R，ØQ®S，ØP®S，ØS 28.解：令A2为A获得第二名，A3为A获得第三名， B2为B获得第二名，B5为B获得第五名， C2为C获得第二名，C3为C获得第三名， D1为D获得第一名，D4为D获得第四名， E4为E获得第四名，E5为E获得第五名。 依据条件：甲猜对一半(A2ÙØB5)Ú(ØA2ÙB5)在真值指派f下为真， 乙猜对一半(C3ÙØE4)Ú(ØC3ÙE4)在真值指派f下为真， 丙猜对一半(C2ÙØD4)Ú(ØC2ÙD4)在真值指派f下为真， 丁猜对一半(B2ÙØA3)Ú(ØB2ÙA3)在真值指派f下为真， 戊猜对一半(D1ÙØE5)Ú(ØD1ÙE5)在真值指派f下为真， 从而在真值指派f下 公式 G=(A2ÙØB5)Ú(ØA2ÙB5)Ù(C3ÙØE4)Ú(ØC3ÙE4)Ù(C2ÙØD4)Ú(ØC2ÙD4)Ù(B2ÙØA3)Ú(ØB2ÙA3)Ù(D1ÙØE5)Ú(ØD1ÙE5)为真。 另外，一个人只能获得一个名次，所以还应有在真值指派f下 A2ÙA3,B2ÙB5,C2ÙC3,D1ÙD4,E4ÙE5均为假.又设并列名次，所以，在真值指派f下 A2ÙB2,A2ÙC2,B2ÙC2,A3ÙC3,D4ÙE4,B5ÙE5为假 利用上述条件，化简公式G 由(A2ÙØB5)Ù(ØA2ÙB5)Ù(A2ÙØA3)Ù(ØB2ÙA3)Û(ØA2ÙB5ÙØB2ÙA3)(C3ÙØE4)Ú(ØC3ÙE4)Ù(C2ÙØD4)Ú(ØC2ÙD4)Û(C3ÙØE4ÙØC2ÙD4)Ú(ØC3ÙE4ÙC2ÙØD4)得G=Ù(C3ÙØE4ÙØC2ÙD4)Ú(ØC3ÙE4ÙC2ÙØD4)Ù(D1ÙØE5)Ú(ØD1ÙE5)Û(ØA1ÙB5ÙØB2ÙA3ÙD1ÙØE5)Ù(C3ÙØE4ÙØC2ÙD4)Ú(ØC3ÙE4ÙC2ÙØD4)Û(ØA1ÙB5ÙØB2ÙA3ÙD1ÙØE5ÙØC3ÙE4ÙC2ÙØD4)因此，第一名为D，第二名为C，第三名为A，第四名E，第五名为B。 29.解：令P表示该矿样为铁；Q表示该矿样为铜；R表示该矿样为锡。 由条件知有一人的判断都正确，所以， (ØPÙØQ)Ú(ØP´R)Ú(PÙØR)Û(ØPÙ(ØQÚR)Ú(PÙØR) Û(ØPÚØR)Ù(PÚØQÚR)为真。 由条件知，有一人的判断对一半，所以 (PÙØQ)Ú(ØPÙQ)Ú(PÙR)Ú(ØPÙØQ)Ú(ØPÙØR)Ú(PÙR) Û(PÚQ)Ù(ØPÚØQ)Ú(PÚØR)Ù(ØPÚR)Ú(ØPÚR)Ù(PÚØR) Û(PÚQÚØR)Ù(ØPÚØQÚR)Ú(ØPÚR)Ù(PÚØR) Û(PÚQÚØR)Ù(ØPÚØQÚR)为真。 由条件知，有一人的判断全错，所以 (PÙQ)Ú(PÙØR)Ú(ØPÙR) Û(PÙ(QÚØR)Ú(ØPÙR) Û(PÚR)Ù(ØPÚQÚØR)为真 从而 (ØPÚØR)Ù(PÚØQÚR)Ù(PÚQÚØR)Ù(ØPÚØQÚR)Ù(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)为真 又因为矿样只能为一种矿石，所以QÙR为假 PÙØQÙØR为真，即P为真 因此，该矿样为铁。 从而，甲是普通队员 乙是见习生 丙是专家 30解：令A.B.C.D分别表示派A.B.C.D出差 则条件为A®CÚD ( 2 ) 为Ø ( 3 ) C®ØD 将条件合成为ÙØÙ 求该公式的主析取范式 首先求主合取范式 原式ÛÙÙ (Ø CÚØD） ÛÙÙ Ù ÙÙ ÛÙÙ ÙÙÙ ÙÙÙ Ù ÛÙÙ ÙÙÙ Ù ÛM0011ÙM0110ÙM0111ÙM1000ÙM1011ÙM1100ÙM1110ÙM1111 从而 主析取范式为 m0000Úm0001Úm0010Úm0100Úm0101Úm1001Úm1010Úm1101 ÛÚÚ ÚÚÚ ÚÚ 因为派三个人出差 所以ÚÚ 为真。因此 符合条件的派法有三种： 第一种：派B和D出差， 第二种：派A和D出差， 第三种：派A和C出差。 31 解：由题意得 GÛ(ØpÙØqÙr)Ú(pÙØqÙØr)Ú(ØrÙqÙr)Ú(pÙqÙØr) 这是主析取范式 ，从而主合取范式为 GÛM000ÙM010ÙM101ÙM111 Û(pÚqÚr)Ù(pÚØqÚr)Ù(ØpÚqÚØr)Ù(ØrÚØqÚØr)32 解：设三个按扭分别A，B，C表示，P，Q，R表示按纽A，B，C。 G表示会场电铃响。 则GÛ(pÙqÙØr)Ú(pÙØqÙr)Ú(ØpÙqÙr)Ú(pÙqÙr) 33 解：令A表示执行下载，根据条件构成A的真值表如下： ETTTTTTTTNTTTTFFFFDOTTTFFFTTFFTFTFTFAFFFF TTTFFFFFFFFFTTTTFFFFTTFFTTFFTTFTTTFTTTFTTTFT执行下载的主合取范式为 (ØEÚØNÚØDÚØO)Ù(ØEÚØNÚØOÚO)Ù(ØEÚØNÚDÚØO)Ù(ØEÚØNÚDÚO)Ù(ØEÚNÚDÚO)第二章习题 1 填空 A(x)，B(y) "x(C(x)®A(x) "x(A(x)®B(y) "x"y(F(x)ÙF(y)®ØH(x,y) $x(F(x)ÙØG(x) T "y(P(x,y)ÙQ(y,z)，P(x,y)ÙQ(y,z)，P(x,y) $!x(Q(x)ÙP(x) $!x(Q(x)ÙP(x) y,x和z "x(Q(x)®R(y)，$x(Q(x)ÙZ(x)，$x(Q(x)ÙR(x)ÙØZ(x) 2选择题 B B A B C C B B B D C A 3下列哪些是谓词公式 解：公式均为谓词公式。 4在谓词逻辑中将下列命题符号化 有些汽车比所有火车都跑得慢； 解：令A(x)：x是汽车，B(x)：x是火车，C(x,y)：x比y跑得慢。 符号化为$x(A(x)Ù("y(B(y)®C(x,y) 会叫的狗未必会咬人； 解：令A(x)：x会叫，B(x)：x是狗，C(x)：x会咬人 符号化为$x(A(x)ÙB(x)ÙØC(x) 存在最小自然数 解：令A:x是自然数，B：x 小于y 符号化为$x(A(x)Ç"y(A(y)®ØB(y,x) 对于每个实数都存在比它大的有理数 解：令A:x是实数，B:x是有理数，R：x 比y大 符号化为"x(A(x)®$y(B(y)ÇR(y,x) 每个自然数都有唯一的后继 解：令A:x是自然数，B：x 是y的后继 符号化为"x(A(x)®$!y(A(y)ÇB(y,x)） 没有以0为后继的自然树 解：令A:x是自然数，B：x 是y的后继 符号化为Ø$x(A(x)ÇB(0,x) 存在唯一的偶实数 解：令A:x是偶数，令B:x是素数 符号化为$!x(A(x)ÇB(x) (8)没有即是奇数也是偶数的数 解：令A:x是奇数，令B:x是偶数 符号化为Ø$x(A(x)ÇB(x) 天下乌鸦一般黑 解：令A:x是乌鸦，令B:x是黑的 符号化为"x(A(x)®B(x) 一个数是素数当且仅当它只能被1和它自身整除 解：A(x):x是素数;.B(x,y):x被y整除;.C(x,y):x与y相等;D(x):x是实数; 符号化为："x(A(x)«$y(D(y)ÙB(x,y)®(C(y,1)ÚC(y,x) 5、利用所给定命题和谓词，将下列诸命题符号化。 P表示“今天天气好”；Q表示“入学考试准时进行”； A表示“c是考生”：B(c)表示“c提前进入考场”； C表示“c取得良好成绩”;E表示“e1=e2”。 如果今天天气不好，就一定有些考生不能提前进入考场， 符号化为：ØP®$x(A(x)ÙØB(x) 如果所有考生提前进入考场，那么入学考试可以准时进行。 符号化为："x(A(x)®B(x)®Q 并非所有提前进入考场的考生都能取得良好成绩。 符号化为：Ø("x(A(x)®B(x)®C(x) 又且仅有一个提前进入考场的考生未取得良好成绩。 符号化为：$!x(A(x)ÙB(x)ÙØC(x) 或：(A(x)ÙB(x)ÙØC(x)Ù(A(y)ÙB(y)ÙØC(y)®E(x,y) 7、将下列命题符号化，要求只是用全称量词。 有些有理数是整数，但并非所有有理数都是整数。 解：令A: x是有理数，B: x是整数; 符号化为：Ø("x(ØA(x)ÚØB(x)Ù(Ø"x(A(x)®B(x) (2)有些素数是偶数。有些素数是奇数 解：令A(x)：x是素数。B(x):x是偶数。C(x)：x是奇数。 符号化为Ø"xØ(A(x)ÙB(x)ÙØ"x(A(x)ÙC(x) 6.将下列命题符号化，要求只使用存在量词 (1)有些人是大学生，但并非所有人都是大学生 解：令：A(x):x是人,B(x):x是大学生 符号化为$x(A(x)ÙB(x)Ù$x(A(x)ÙØB(x) (2)所有整数都是有理数 解：令A(x):x是整数。B(x):x是有理数 符号化为Ø$x(A(x)ÙØB(x) 8设个体域为a,b，请消除以下谓词中的量词 (1)"x(P(x)®Q(x) 解：原式Û(p(a)®q(a)Ù(p(b)Ùq(b) (2)("x)($y)(R(x,b) 解：原式Û($yR(a,b)Ù($yR(b,b) Û(R(a,a)ÚR(a,b)Ù(R(b,a)ÚR(b,b) (3)($y)("x)R(x,y) 解：原式Û("x)(R(x,a)Ú("x)(R(x,b) Û(R(a,a)ÙR(b,a)Ú(R(a,b)ÙR(b,b) 9.若A(x)表示"x是整数"B(x)表示"x是偶数" C(x)表示"x是奇数"D(x)表示"x是素数" E(x)表示"x能整除y". 试用日常用语叙述下列命题。 "x(B(X)®A(X) 解：所有的偶数都是奇数。 $X(A(X)ÙC(X) 解：有些奇数是奇数。 "X(E(2.X)®B(X) 解：所有被2 整除的数均是偶数。 $X(C(X)ÙD(X) 解：有些奇数是素数。 $X(C(X)ÙD(X)ÙØ"X(C(X)®D(X) 解：有些奇数十素数，但并非所有奇数都是素数。 10.将命题“并非E1中的每个数都小于或等于E2中的每个数”分别按下面所要求的形式表达出来： (1) 出现全称量词，不出现存在量词 解:令A(X,Y)表示“X属于Y” B(X,Y)表示“X£Y” 则Ø"X"YAX,(E)ÙB(Y,E)®B(X,Y) 12出现存在量词，不出现全称量词 解：令A(X,Y)表示“X属于Y” B(X，Y)表示“XY” 则$X$YAX，(E)ÙA(Y，E)ÙB(X，Y) 1211.指出下列各式的自由变元和约束变元，并确定量词的辖域 ($X)(P(X)ÙR(X)ÙS(X)®"X(P(X)ÙQ(X) 解：所有变元均为约束变元 量词