離散數(shù)學(xué)課后習(xí)題合集

第一章命題演算基礎(chǔ)

1.1判斷下列語句是否為命題，若是請翻譯為符號公式；若不是說明由。

(1)請給我一支筆！

(2)火星上有生物。

(3)X+Y=8

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

(5)如果嫦娥是虛構(gòu)的，而圣誕老人也是虛構(gòu)的，那么許多孩子受騙了。

解

(1)不為命題，因為它不是陳述句。

(2)是命題，用命題變元P表示該命題。

(3)不為命題，雖為陳述句，但不能判斷其真假性。

(4)是命題。設(shè)P表示努力工作，。表示把事情做好，則原句翻譯為命題公式Q-P。

(5)是命題。設(shè)P表示嫦娥是虛構(gòu)的，。表示圣誕老人也是虛構(gòu)的，R表示許多孩子

受騙了，則原句翻譯為(PAQ)-R。

1.2試判定下列公式的永真性和可滿足性。

(1)(Pg。)—(「PA](Q->[/?))

解

(1)當(dāng)P=T時，

原式=(T-f(「TA」(Q—Y))

=Qf(FATQ-「H))

=QfF

當(dāng)。=7時，上式=F；當(dāng)。=尸時，上式=7,因此公式存在成真解釋

(P,Q,&=(T,￡x),存在成假解釋(P,Q,R)=(T,T,x),故公式可滿足，但非永真。

(2)」(PfQ)A((。—

解

當(dāng)P=T時

原式=TTfQ）入（（Q-」R）V[T）

=—'Q△((Q-'—>R)vF)

=—)QA((Q——17?)

當(dāng)。=T時

上式=「TA(T—T?)

=F八—iR

=F

當(dāng)。=/時

上式=—\FA(F<->-i7?)

=TA―?~~17?

=-1-iR

二R

當(dāng)R=T時，上式=7,因此公式存在成真解釋(P,Q,R)=(T,F,T),存在成假解釋

(P,Q,R)=(T,T,x),故公式可滿足，但非永真。

(3)八。)-((Q->T?)—P)

解

當(dāng)P=T時

原式=(—?—TAQ)—>((Q->-R)7")

=(TAQ)->(QfT?)

=(?！?。-

當(dāng)Q=T時

上式=(Tf(T->T?)

=—iR

當(dāng)R=T時，上式=F,當(dāng)R=F時，上式=T,因此，公式存在成真解釋

(P,Q,R)=(T,T,F),存在成假解釋(P,Q,R)=(T,T,T),故公式可滿足,但非永真。

(4)(「「Pf。)一((QAH)-[P)

解

當(dāng)P=T時

原式=(-1-17->Q)->((QAR)―i7)

2

=(T-Q)f((QAR)一尸)

=QfTQAR)

=Q—>(—><2v—iR)

當(dāng)。=T時

上式=T—>(-1Tv-J?)

-Fv—iR

=「R

當(dāng)R=T時，上式=F,當(dāng)R=F時，上式=T,因此，公式存在成真解釋

(P,Q,R)=(T,T,F),存在成假解釋(P,Q,R)=(T,T,T),故公式可滿足,但非永真。

1.3試求下列公式的成真解釋和成假解釋

(1)T(P-Q)-(QvR)

解

(1)當(dāng)。=T時

原式=T(PTT)TR)C(TVR)

=TJtR)cT

=iR

當(dāng)R=T時，上式=F,當(dāng)R=F時，上式=7。

當(dāng)。=E時

原式=」((PfF)TR)c(FvR)

=*PTR)cR

當(dāng)R=T時

上式T)—T

?T—T

=F

當(dāng)R=F時

上式=T「P一尸)2尸

=「PcF

=P

當(dāng)尸=T時，上式=T,當(dāng)「=/時，上式=尸，

3

因此，公式的成真解釋為（d?/?）=（7,￡尸）,區(qū)7；尸）；成假解釋為

(P,Q,R)=(F,F,F),(x,T,T),(x,F,T)。

(2)TP-Q)A((Q—R)vP)

解

當(dāng)尸=T時

原式=TT-Q)△((Q—R)vT)

=TTfQ)八T

=-}Q/\T

=~'Q

當(dāng)Q=T時，上式=F；當(dāng)Q=F時，上式=T。

當(dāng)P=F時

原式=TFT。)A((QcR)7F)

=「T八(QcR)

=FA(QCR)

=F

因此，公式的成真解釋為(P,Q,R)=(T,F,x)；成假解釋為

(P,Q,R)=(T,T,x),(fx,x)。

(3)(「「PAQ)一((QfR)—[P)

解

當(dāng)尸=T時

原式=(「-1T八Q)一((QfR)—[T)

=Qf((QfR)cE)

=Q—TQTR)

當(dāng)Q=T時

上式=T-TT-R)

4

=TTfR)

=「R

當(dāng)R=T時，上式=F；當(dāng)R=尸時，上式=7。

當(dāng)。=/時

上式=尸分一＜尸-R)

=T

當(dāng)P=P時

原式=AQ)—((QfR)—「尸)

=(尸AQ)一((Q-R)-T)

=FT(QTR)

=T

因此，公式的成真解釋為(P,Q,R)=(T,T,E),(T,F,x),(￡x,x)；成假解釋為

(P,Q,R)=(T,T,T)。

(4)(「「PfiQMlQvJHAP))

解

當(dāng)P=7'時

原式=T」Q)A(。v(YAT))

=(T-1Q)A(QV「R)

=—iQA(。v—17?)

當(dāng)Q=T時

上式=「TA(TV「R)

"AT

=F

當(dāng)。=尸時

上式=—iFA(Fv—iR)

-TA—i7?

=「R

當(dāng)R=T時，上式=E；當(dāng)R=尸時，上式=T。

5

當(dāng)/^二/時

原式=(「Yf「Q)A(Qv(「RAF))

=(F-「Q)A(QVF)

=TA(Q")

=Q

當(dāng)。=T時，上式=T；當(dāng)。=/時，上式=F。

因此，公式的成真解釋為(P,Q,R)=(T,F,F),(F,T,x)；成假解釋為

(P,。,R)=(T,T,x),(T,F,T),(F,F,x)。

1.4試寫出下列公式的對偶式和內(nèi)否式

(1)(「PAQ)一((QV「R)AP)

(2)(Pf」Q)A((QVR)A'P)

(3)[(P-Q)A((Q—」R)v[P)

(4)(「P-Q)v((Qf

解

(1)內(nèi)否式為(PA[Q)—((「QVH)A「P)

消去“一”得式子AQ)v((Qv」R)AP)

對偶式=-i(—>PVQ)A((QA―i/?)VP)

(2)內(nèi)否式為([PfQ)A((「QV「R)AP)

消去“一”得式子v」Q)A((QvR)A「P)

對偶式為A「Q)v((QAR)v

(3)內(nèi)否式為-

消去“c”得式子vQ)A(((「QvA(Qv/?))v

對偶式為AQ)v(((「Q△T?)v(。人玲)A「P)

（4）內(nèi)否式為（P->[Q）v（（「Qf/?）vP）

6

消去“一”得式子（PvQ）v（（「Qv-1R）v「P）

對偶式為（產(chǎn)人Q）A（（「QA「R）A「P）

1.5試證明聯(lián)結(jié)詞集合｛「,f｝是完備的。

證明

因為，PvQ=「P—Q

PAQ=」（P-「Q）

所以，聯(lián)結(jié)詞集合｛],一｝可以表示集合｛=A,v｝。

又因為，聯(lián)結(jié)詞集合｛fA,v｝是完備的，即｛-A,v｝可以表示任何一個命題演算公式，

所以｛「,-?｝可以表示任何一個命題演算公式，故聯(lián)結(jié)詞集合｛],->｝是完備的。

1.6試證明聯(lián)結(jié)詞集合｛△｝,｛9｝不是完備的。

證明

設(shè)集合｛人｝是完備的，則由聯(lián)結(jié)詞集合的完備性定義知

「P=/（P,Q,R,…）=PAQARA…。當(dāng)P,0,R,…全取為真時，上式左邊=/，右邊

=T,矛盾。

因此｛人｝不是完備的。

設(shè)集合｛->｝是完備的，則由聯(lián)結(jié)詞集合的完備性定義知「尸=/（P,Q,R,…），其中/

表示“一”。當(dāng)P,Q,R,…全取為真時，上式左邊=口，右邊=7,矛盾。

因此｛-?｝不是完備的。

1.7試求下列公式的析取范式和合取范式

（1）-「Q）

解

原式=T-1PV0V（（PA「Q）V（-1PA[「Q））

二（PA-1。）V（PA-1Q）V（-1PAQ）

=（PA-10V（-1PAQ）（析取范式）

二（（P△」Q）V[P）A（（尸A」Q）VQ）

7

=(Pv-1P)A(-,PV-.0A(Pv0A(rQVQ)

=(「Pv「Q)/\(PvQ)(合取范式)

⑵(Pf(Qf(R-(QfP))

解

原式=―i(―iPv(—iQv―i/?))v(―iRv(―iQvP))

=(P△Q△R)"(Pv—>Qv—17?)

=(PvPv—iQv—J?)A(0vPv—iQv—iR)△(HvPv—>Qv—Ji)

=Pv「QvT?(合取范式和析取范式)

(3)TP->Q)A((Q->「R)V「P)

解

原式=V0A((「Qv」R)v「尸)

=PA—\QA(—\Pv―\Qv—iR)(合取范式)

=(PA—iQ)A(-nPV—)QV—J?)

=((「A」Q)A「P)V((尸A」Q)A[Q)V((PA「Q)A「R)

=(PA「Q)V(PA「QA「R)(析取范式)

(4)(P—Q)f(「PA」(Q-「火))

解

原式=TP-Q)vAT「QV「R))

=T—Q)v△QA&

=(「PAQ)V(PA「Q)V(「PAQAH)(析取范式)

=((「PAQ)V(PA[Q))V(「PAQA/?)

=((「PAQ)”)A((dAQ)V「Q))V(「PAQAR)

=((「P”)A(PX/QXPV「Q)A(QV[Q))VTAQAR)

=((爪Q)Av[Q))vAQ八R)

8

二((PVQ)V(「PAQAR))/\((-IP\/「Q)\/TAQAR))

=(PV(2v—1P)A(PV(2VQ)A(PV(2V7?)A(—iPV—yQV-iP)A

(—iPv-iQv0)A(—iPv—\QvR)

=(PV0A(PV(2V7?)A(-IPv—i0A(-iPv—iQvR)(合取范式)

1.8試求下列公式的主析取范式和主合取范式

(1)(「尸fR)-?(「P-(「QAR))

解

原式二V/?)V((「尸A(「QA7?))V(PAA7?)))

=(-1PA—17?)V(—1尸A—1。A/?)V(PA((2V—1/?))

=(―I尸A—iR)V(—1尸A—1QAR)V(P△Q)V(PA-1H)

=((—1尸A—i/?)△(Qv-1Q))V(—1PA—1QA7?)V((PA2)A(7?V—i/?))

V((PA「R)A(QV[Q))

—(―\PAQA-iR)V(—\PA-\QA_17?)V(—\PA—\QA7?)V(JPA2A7?)

V(PA2A—iR)V(尸AQA-1R)V(PA—1。A—i/?)

=(—iP△。八一iR)v(—iPA—1(2八一|R)v(->PA—\Q/\R)v(P/\Q/\R)

V(PA2A—1R)V(PA—iQA—1R)

.(0,124,6,7)

=n(3,5)

=(Pv—\Qv—iR)A(-\PvQviR)

(2)(「「PAQ)—((QfR)—[P)

解

原式=~i(-1-\PAQ)v((―\QvR)<—>―P)

—(―iPv—iQ)v((—iQvR)A—iP)v(―i(—iQ\zR)AP)

—(―iPv—)Q)v(―?尸A—iQ)v(―iPAR)v(尸AQ△—iR)

9

=(—iPA((2V—yQ)A(7?V—17?))v(—)QA(PV-iP)A(/?V—i??))V

((「P△[Q)△(RV[R))V((「尸△R)△(QV「Q))v(P△Q△「R)

=(-1PAQA/?)V(—iPA0A—i/?)V(—iPA-iQA7?)V(—iPA-iQA—>R)

V(PA—)(2A/?)V(PA-1QA—1/?)v(—1尸A—yQA??)V(—LPA—IQA—1R)V

(—iPA—iQA7?)v(—iPA—iQA—iR)v(—iP△Q△R)v(—i尸A—IQA/?)V

(PAQAT?)

=(-1PA2A/?)V(—iPAQA—17?)V(—1尸A-1。A7?)V(—iPA—A—iR)

V(PA—1(2A7?)V(PA-1QA—17?)v(PA(2A~nR)

.(0,123,4,5,6)

=口⑺

=一iPv―\Qv―iR

(3)(尸一「Q)vR

解

原式=」Pv「QvR

二口⑹

.(0,123,4,5,7)

—(―\PA—\QA—iR)v(—\PA—\QvR)v(—iPvQ\z—iR)v(—iPvQvR)

V(PA—1。A—iR)V(PA-1QAR)V(P/\QAR)

(4)P-(PA(。-P))

解

原式=「Pv(P/\(「QvP))

=(—iPVP)A(—1PV—)QVP)

=TrT

=T

10

=n(①)

=E(0,L2,3)

=(-1PA-.0V(-nPA0V(PA->Q)V(PAQ)

1.9用把公式化為主范式的方法判斷下列各題中兩式是否等價

(1)(PfQ)-(P/\Q),TAQ)A(Q->P)

解

(1)(P-Q)—(PAQ)

=T[PVQ)V(PAQ)

=(PA「Q)V(尸人Q)

=Z(2,3)

(「P八Q)八(QfP)

=(「P/XQ)A(「QVP)

=(->P/\QAF2)VJPAQAP)

=FvF

=F

，(①)

由此可見兩公式的主析取范式不相等，因此，兩公式不等價。

(2)(PTR)八(QfR),gQ)-R

解

(PTR)A(QTR)

-(-1Pv/?)A(―iQvR)

=((「pV/?)V(2A[Q))A((「QVR)V(PA」P))

=(—IPVQvR)A(—iPv—1(2vR)A(Pv—iQvR)A(—iPv—iQvR)

=(PV—1(2V7?)A(—1尸v2v1?)A(—iPv—1。vR)

=n(2,4,6)

II

(PvQ)fR

=—|(PV0)7R

=(-1PA-iQ)vR

=(—iPv/?)A(—)(2vR)

=((「pVR)V(QA[Q))△((「QV/?)A(PA[尸))

=(—iPvQv7?)A(—iPv—1(2v7?)A(Pv—iQv/?)A(—v-iQvR)

=(PV—1QV/?)A(—1Pv2v/?)A(—?尸v—iQvR)

=n(2,4,6)

由此可見兩公式的主合取范式相等，因此，兩公式等價。

12

第二章命題演算的推理理論

2.1用永真公理系統(tǒng)證明下列公式

（I）P<->（PvP）

證明

(1)PTP公理1

(2)(Pf&f((Q-((Pv。)—/?))公理13

(3)(PfP)f((PfP)f((PvP)fP))。,R用P代入

(4)(P-P)->((PvP)-?P)分(3)(1)

⑸(PvP)->P分⑷(1)

(6)Pf(PvQ)公理11

(7)Pf(PvP)。用P代入

(8)(Pf。)一((Q-P)-?(P—Q))公理7

(9)(Pf(PvP))f(((尸vP)f-(PvP)))。用PvP代入

(10)((PvP)fP)f(P一■(2"))分(9)(7)

(11)Pc(PvP)分(10)(5)

（2）T-Q）->（「QfP）

證明

（l）（Pf（Qf「P）公理14

（2）（「PfuQ）—（「QfP用代入，Q用代入

（3）-riPfP公理15

（4）（Pf。）一（（A-P）f（Hf。））定理

（5）（「ifP）f（（「Qf（「Q—尸））

P用代入，。用P代入，R用「Q代入

13

(6)(」Qf[「P)f(「QfP)分(5)(3)

⑺(PfQ)f((QfR)f(P-R))公理3

(8)((—I尸f-1->Q)f(->Q-—iP))f(((->Q->->P)f(-'Q-P))

f(JPf[[Q)fJQ-P)))

P用「尸一代入，。用f代入，R用「Qf尸代入

(9)((「Q-([Q-P))f((「Pf10f(「QfP))分(8)(2)

(10)(iP--n-iQ)f(「QTP)分(9)(6)

(11)Q-「「Q

(12)(Qf—i—iQ)f((-iPfQ)f(-'Pf-1。))

（4）式中P用。代入，。用代入，R用「p代入

(13)(-iP-Q)—>(一'尸—>—i-'Q)分（⑵（11）

(14)((「尸fQ)―(」Pt[「Q))t(((「Pt」T2)f([QfP))f

(JP—(「Qf尸)))

(7)式中P用「Pf。代入，。用「尸一代入，R用「Q分尸代入

(15)((「PT」「Q)f([QfP))f(JPfQ)—(1QfP))分(14)(13)

(16)(「PfQ)f(「QfP)分(15)(10)

(3)Pv-1P

證明

(1)Pf(PvQ)公理11

(2)PT(PV「P)。用「P代入

⑶(PfQ)f(「Qf」P)

(4)(尸-(尸v-1P))t(」(Pv」P)f「尸)。用Pv「尸代入

(5)TPv「P)f分(4)(3)

14

(6)Qf(PvQ)公理12

(7)f(Pv「P)。用「P代入

(8)(PfQ)f((Qf(PfR))公理3

(9)(TPv」P)f「尸)f((「P-(尸v[尸))f(」(尸v」P)f(Pv[P)))

P用」(Pv「P)代入，。用「P代入，及用尸v「P代入

(10)(「P-(Pv「P))f(「(Pv-iP)—(Pv[P))分(9)(5)

(11)」(Pv-1P)f(Pv-iP)分(10)(7)

(12)(「PfP)fP定理

(13)([(Pv「尸)一(Pv」P))一(Pv「尸)P用尸v「P代入

(14)Pv-1P分(13)(11)

(4)((PfQ)f((Pf

證明

(1)FPTP公理1

(2)QP用0代入

(3)(PfQ)f((R—P)f(HfQ))定理

⑷((P1[[Q)->(Pf。))P用「「Q代入，R用P代入

(5)(P->]「。)-(P->。)分(4)(2)

(6)(PfQ)f((QfR)f(P->??))公理3

(7)((Pf[「Q)f(PfQ))->(((P-Q)fY)f((PT」「Q)T[R))

P用代入，。用PfQ,R用代入

(8)((P->Q)->T?)->((P->]「Q)->[R)分(7)(5)

2.2已知公理：A:Pf(。fP)

8:(QfH)->((P->Q)->(P-?&)

C;(PVP)TP

15

D:QT(PYQ)

E:(PvQ)f(QvP)

及分離規(guī)則和代入規(guī)則。

試證明(1)PfP為定理

(2)(P-P)V(RA「R)為定理。

證明

(D(PvP)->P公理C

(2)QT(PYQ)公理。

(3)PT(PVP)。用P代入

(4)(Q->R)f((PfQ)f(P一2)公理B

(5)((PvP)fP)f((P->(PvP))->(PfP))。用PvP代入，R用P代入

(6)(Pf(PvP))f(P—P)分(5)(1)

(7)P1P分(6)(3)

(8)(P-P)f((RA-J?)V(P-P))

(2)式中。用PfP代入，P用R人「R代入

(9)(RA「R)V(P—P)分(8)(7)

(10)(PvQ)f(QvP)公理E

(11)((RA「R)v(PfP))f((PfP)V(/?A「R))

P用代入，。用P7尸代入

(12)(PfP)V(RA「R)分(11)(9)

2.3用假設(shè)推理系統(tǒng)證明下列公式

(1)(P->Q)f((Pf

證明

(1)PfQ假設(shè)

(2)P-假設(shè)

16

(3)FP后件的否定

(4)FPfP公理15

(5)P分(4)(3)

(6)Q分(1)(5)

⑺分(2)(5)

(6)(7)矛盾

由反證法推理定理知

PTQ，PT「QI

由推理定理知

(P-((P-「Q)一［P)

(2)(Pf(QfR))f((PfQ)f(PfR))

證明

(1)Pf(。fH)假設(shè)

(2)PTQ假設(shè)

(3)P假設(shè)

⑷QfR分⑴（3）

(5)Q分(2)(3)

(6)R分(4)(5)

由假設(shè)推理過程的定義知

Pf(QtR),PTQ,P\-R

由推理定理知

(P->(。-R))一((P-Q)->(Pf火))

(3)((PA。)-R))f(Pf(QfR))

證明

⑴(PAQ)-R假設(shè)

(2)P假設(shè)

(3)Q假設(shè)

(4)Pr(Qf(PAQ))公理10

(5)Qf(PAQ)分（4）⑵

17

(6)PAQ分(5)(3)

(7)R分(1)(6)

由假設(shè)推理過程的定義知

(P八Q)TR),P,Q\-R

由推理定理知

((P八。)-R))—(P-(0->R))

(4)((PAQ)A((P—H)A(Q->S)))T(SAH)

證明

(1)(PAQ)/\((P—R)/\(QfS))假設(shè)

(2)(P八Q)TP公理8

(3)(PAQ)FQ公理9

(4)((尸△Q)/\((P-R)A(Q-S)))f(PAQ)

(2)式中P用PAQ代入，。用(P-R)/\(Q—S)代入

(5)((PA0A((P-火)A(QfS)))f((PfR)A(QfS))

(3)式中產(chǎn)用PAQ代入，。用(P-R)A(Q-S)代入

(6)PAQ分(4)(1)

⑺(PfR)A(Q-S)分(5)(1)

(8)P分(2)(6)

(9)Q分(3)(6)

(10)((PfR)八(。->S))f(PfR)(2)式中P用P—R,。用QfS代入

(11)((P->R)A(。7S))f(。-S)(3)式中P用PfR,。用QfS代入

(12)PfR分(10)(7)

(13)QfS分(11)(7)

(14)R分(12)(8)

(15)S分(13)(9)

(16)P-(Qf(PAQ))公理10

18

(17)R―(S―>(7?AS))P用R,。用S代入

(18)S―>(RAS)分(17)(14)

(,19)RAS分(18)(15)

由假設(shè)推理過程的定義知

(PAQ)/X((P-R)A(Q-S))\-RAS

由推理定理知

((PAQ)A((P->H)A(Q-S)))f(SAR)

2.4用歸結(jié)原理證明下列公式

(1)((PAQ)A((PFH)A(Q-S)))f(SAR)

證明

化為合取范式：

((PAQ)A((PfR)A(QfS)))A［(SAR)

=((尸△Q)A((—1PvR)A(~^QvS)))A(—iSv—iR)

=PA2A(―>尸V7?)A(-1QVS)A(—iSV—iR)

建立子句集

(1)p

(2)Q

(3)「PvR

(4)—>QvS

(5)―iSv―、R

(6)R(1)(3)歸結(jié)

(7)-iS(5)(6)歸結(jié)

(8)—yQ(4)(7)歸結(jié)

(9)□(2)(8)歸結(jié)

(2)(PfQ)f((P->］。)一［P)

證明

化為合取范式：

(P->Q)AT(P-「。)一［P)

=(―\PvQ)A―i(―i(—\Pv―iQ)v―\P)

=(—\PVQ)A(―\PV―iQ)A—?—uP)

19

建立子句集:

(1)「PvQ

(2)

(3)—i—iP

(4)Q(1)(3)歸結(jié)

(5)「Q(2)(3)歸結(jié)

(6)□(4)(5)歸結(jié)

(3)—i(PA—>Q)A(—iQv7?)A—iR—iP

證明

化為合取范式：

—i(PA―iQ)A(—iQVR)A—iRA—i—iP

—(―\PvQ)A(―\QvR)A—、RA—?—J3

建立子句集：

(1)-1PvQ

(2)「QvR

(3)—tR

(4)/P

(5)Q(1)(4)歸結(jié)

(6)「Q(2)(3)歸結(jié)

(7)□(5)(6)歸結(jié)

(4)—iPvP

證明

化為合取范式：

VP)=PA-iP

化為子句集：

(1)P

(2)「P

(3)□(1)(2)歸結(jié)

20

第三章謂詞演算基礎(chǔ)

3.1試把下列語句符號化

(1)如果我知道你不在家，我就不去找你了。

解

設(shè)A?,02)表示61知道02不在家；

3(6],02)表示61去找02；

。表示我；6表示你；

則原句表示為：

A(a,Z?)—>。

(2)他送給我這只大的紅氣球。

解

設(shè)A(e),e2,e3)表示et送給e2e3；

8(e)表示e為大的；

C(e)表示e為紅的；

D(e)表示e為氣球；

a表示他，b表示我，c表示這只；

則原句譯為：

A(a,h,c)A3(c)AC(c)AZ)(C)(,

(3)蘇州位于南京與上海之間。

解

設(shè)4(e”J，03)表示e1位于02與63之間；

a表示蘇州，匕表示南京，c表示上海；

則原句表示為：

A(a,b,c)o

(4)他既熟悉C++語言，又熟悉PASCAL語言。

解

設(shè)A?,e2)表示6]熟悉02；

a表示他，b表示C++語言，c表示PASCAL語言；

則原句譯為：

21

A(a,b)AA(a,c)?

3.2試將下列語句符號化為含有量詞的謂詞演算公式：

(1)沒有不犯錯誤的人。

解

設(shè)P(e)表示e為人；

M(e)表示e為錯誤；

4(6],02)表示61犯e2-

則原句譯為：

「玉(P(x)AVy(M(y)fA(x,y)))。

(2)有不是奇數(shù)的質(zhì)數(shù)。

解

設(shè)0(e)表示e為奇數(shù)；

P(e)表示e為質(zhì)數(shù)。

則原句譯為：

3x(—>O(x)AP(x))。

(3)盡管有人能干，但未必一切人能干。

解

設(shè)P(e)表示e為人；

A(e)表示e能干。

則原句譯為：

3x(P(x)AA(x))A-1Vx(P(尤)TA(x))o

(4)魚我所欲，熊掌亦我所欲。

解

設(shè)尸(e)表示e為魚；

3(e)表示e為熊掌；

W(e”e2)表示0]所欲e?。

。表示我；

則原句表不為：

Vx(F(x)-W(a,x))AVx(B(x)-W(a,x))。

22

(5)人不犯我，我不犯人；人若犯我，我必犯人。

解

設(shè)P(e)表示e為人；

C(et,e2)表示et犯e2。

。表示我；

則原句譯為：

Vx((P(x)A—1C(x,a))f-iC(a,x))AVx((P(x)AC(x,a))-C(a,x))。

(6)有一種液體可熔化任何金屬。

解

設(shè)〃e)表示e為液體；

M(e)表示e為金屬；

C(et,e2)表示e,熔化e2。

則原句可譯為：

3X(￡(X)AVy(M(y)->C(x,y)))。

(7)并非“人為財死，鳥為食亡”。

解

設(shè)P(e)表示e為人；

A(e)表示e為財；

8(e)表示e為鳥；

F(e)表示e為食；

C(e”e2)表示e1為02死；

D(e,,e2)表示e1為e2亡。

則原句譯為：

-,(VxVy((P(x)AA(y))fC(x,y))AVxVy((P(x)AF(y))-D(x,y)))

(8)若要人不知，除非己莫為。

解

設(shè)P(e)表示e為人；

A(e)表示e為某一事情；

23

8(6],02)表示ej做了e2；

(7(,,02，03)表示知道02做了e30

則原句譯為：

VxVy((P(%)AA(y)AB(X,y))f3z(P(z)AC(Z,X,y)))

(9)任何一數(shù)均有一數(shù)比它大。

解

設(shè)A(e)表示e為數(shù)；

B(et,e2)表示e1比e2大；

則原句譯為：

Vx(A(x)一方(A(y)AB(y,x)))

(10)每個作家均寫過作品。

解

設(shè)A(e)表示e為作家；

N(e)表示e為作品；

卬(6件2)表示61寫了02。

則原句譯為：

Vx(A(x)T寺(N(y)AW(x,y)))

(11)有些作家沒寫過小說。

解

設(shè)A(e)表示e為作家；

N(e)表示e為小說；

W?,e?)表示修寫了e2。

則原句譯為：

Hx(A(x)AVy(N(y)-」W(x,y)))

(12)天下烏鴉一般黑。

解

設(shè)A(e)表示e為烏鴉：

8(G，02)表示6]與02一樣黑。

24

則原句譯為：

VxVy((A(x)AA(y))-B(x,y))

3.3令P(e)表示“e為質(zhì)數(shù)”;

E(e)表示“e為偶數(shù)”；

0(e)表示“e為奇數(shù)”；

表示“.除盡02”。

試把下列語句翻譯為日常語句：

(1)E⑵AP⑵

解

2為偶數(shù)且2為質(zhì)數(shù)。

(2)Vx(Z)(2,x)-E(x))

解

任何能被2除盡的數(shù)均為偶數(shù)。

(3)Vx(「E(x)f「。(2,幻)

解

任何不是偶數(shù)的數(shù)均不能被2除盡。

(4)Vx(E(x)—>Vy(D(x,y)fE(y)))

解

任何一個數(shù)，若能被任何偶數(shù)除盡，則該數(shù)一定是偶數(shù)。

(5)3x(E(x)AP(x))

解

有是偶數(shù)的質(zhì)數(shù)。

3.4指出下列公式的約束關(guān)系、自由變元和約束變元：

(1)Vx(A(x,y)TVy(B(x,y)TC(z)))

解

A(x,y)中的x和B(x,y)中的x受Vx約束；

B(x,y)中的y受Vy約束：

A(x,y)中的x為約束變元，8(x,y)中的x和y為約束變元;

A(x,y)中的)，和C(z)中的z為自由變元。

25

(2)Vx(A(x)TTh(A(y)AB(X,y))

解

A(x)->B(x,