離散數(shù)學(xué)（馮偉森版）課后習(xí)題答案

習(xí)題一解答或提示

1.(1)設(shè)P：他是本片的編劇，Q：他是本片的導(dǎo)演。PAQ

(2)設(shè)P:銀行利率降低，Q:股價(jià)上揚(yáng)。PfQ

(3)設(shè)P:銀行利率降低，Q:股價(jià)上升。?(PfQ)

(4)設(shè)P:這個(gè)對(duì)象是占據(jù)空間的,Q:這個(gè)對(duì)象是有質(zhì)量的,R:這個(gè)對(duì)象是不斷變化的,S:

這個(gè)對(duì)象稱為物質(zhì)。PAQAR^S

(5)設(shè)P:他今天乘火車去了北京，Q：他今天隨旅行團(tuán)去了九寨溝。PVQ

(6)設(shè)P:小張身體單薄，設(shè)Q：小張極少生病，設(shè)R：小張頭腦好使。PAQAR

(7)設(shè)P:這個(gè)人不識(shí)廬山真面目，設(shè)Q:這個(gè)人身在廬山中。QfR

(8)設(shè)P:兩個(gè)三角形相似，設(shè)Q:兩個(gè)三角形的對(duì)應(yīng)角相等或者對(duì)應(yīng)邊成比例。PoQ

(9)設(shè)P：一個(gè)整數(shù)能被6整除，設(shè)Q：這個(gè)整數(shù)能被

2和3整除。PfQ

設(shè)R:一個(gè)整數(shù)能被3整除，設(shè)S:這個(gè)整數(shù)的各

位數(shù)字之和也能被3整除。RfS

2、(1)命題T

(2)命題T/F

(3)不是命題，因?yàn)檎嬷禑o(wú)法確定。

(4)命題T

(5)不是命題。

(6)命題T

(7)命題T/F

(8)不是命題，是悖論。

5、(1)證：?((~PAQ)V(?PA?Q))V(PAQ)

=(?(-pAQ)A-(?P八?Q))V(PAQ)

=((PV~Q)A(PVQ))V(PAQ)

=(PV(?QVQ))V(PAQ)

<=>PV(PAQ)=P

(3)證：P-?(QVR)

。?PV(QVR)

=~PVQV?PVR

o(~PVQ)V(~PVR)

=(P-Q)V(P-R)

6、解：如果PVQoQVR,不能斷定P=R。因?yàn)楫?dāng)Q=T時(shí)，PVQoQVR恒成立。

如果PAQoQAR,不能斷定P=R。因?yàn)楫?dāng)Q=F時(shí)，PAQoQAR恒成立。

如果?Pu>?R,則P=R。

8、把下列各式用f等價(jià)表示出來(lái)：

(1)解：(PAQ)V?P

=((PtQ)t(PtQ))V(PtP)

<=>(((PtQ)t(PtQ))t((PtQ)t(PtQ)))t((PtP)t(PtP))

(3)解：(P-(QV~R))A?P

=(?PV(QV~R))A~P

=((PtP)V(QV(RtR)))A(PtP)；

o((PtP)V((QtQ)t((RtR)t(RtR))))A(PtP)

=(((PtP)t(PtP?t(((QtQ)t((RtR)t(RtR)))t

((QtQ)t((RtR)t(RtR)))))A(PtP)

((((PtP)t(PtP))t(((QtQ)t((RtR)t(RtR)))t((QtQ)

t((RtR)t(RtR)))))t(PtP))t((((PtP)t(PtP))t(((QtQ)t((R

tR)t(RtR)))t((QtQ)t((RtR)t(RtR)))))t(PtP))

9、證：VPVQ=??PVQo(?P)-Q

PAQ=?(?PV?Q)=?(p-*~Q)

而｛?，V,八｝是功能完備集，

...｛?，f｝是功能完備集，?，f不能互相表示，

故｛?，一｝是最小功能完備集。

又YP二g?(PfQ),.,.｛?，二｝也是最小功能完備集。

10、證：由書上的表1.16可知，“?”對(duì)應(yīng)的真值表含2個(gè)1和2個(gè)0,而“V”對(duì)應(yīng)

的真值表也含2個(gè)1和2個(gè)0,V對(duì)應(yīng)的真值表含3個(gè)1和1個(gè)0,A對(duì)應(yīng)的真值表含1

個(gè)1和3個(gè)0,所以，“V”無(wú)法用“?”和“V”來(lái)表示，同樣“A”也無(wú)法用“?”和

“V”來(lái)表示，因此，｛?，V｝不是功能完備集。

12.解：(1)a)真值表法

PQR

QARQARfS(P-(QARfS))

S

0000011

0001011

0010011

0011011

0100011

0101011

0110101

0111111

1000011

1001011

1010011

1011011

1100011

1101011

1110100

1111111

由表中看出，

i）使公式（P-（QARfS））取值1時(shí)的解釋所對(duì)應(yīng)的全部極小項(xiàng)為:

(?PA?QA?RA?S),(~PA~QA~RAS),(~PA~QARA~S),(~PA~QA

RAS),(-PAQA-RA-S),(-PAQA-RAS),(?PAQARA?S),(-PAQARAS),

(?QAP八?R八?S),(-QAPA-RAS),(?QAPARA?S),(-QAPARAS),(-R

AQAPA-S),(-RAQAPAS),(SAQARAP),由定理1.8,其主析取范式為：

(-PA-QA-RA-S)V(-PA-QA~RAS)V(-PA-QARA-S)V(~P

A-QARAS)V(?PAQA?RA?S)V(-PAQA-RAS)V(?PAQARA?S)V

(-PAQARAS)V(~QAPA-RA-S)V(-QAPA-RAS)V(-QAPARA-S)

V(-QAPARAS)V(-RAQAPA-S)V(-RAQAPAS)V(SAQARAP)o

ii)使公式(P-(QARTS))取值0時(shí)的解釋所對(duì)應(yīng)的全部極大項(xiàng)為：

?PV?QV?RVS由定理1.7,其主合取范式為：?PV?QV?RVS?！?/p>

b)等價(jià)變換法

Pf(QAR)fS)

o-PV(~(QAR)VS)

。?PV?QV?RVS---主合取范式

o(~PA(~QVQ)A(~RVR)A(~SVS))

V(~QA(-PVP)A(?RVR)ACSVS))

V(~RA(~PVP)A(-QVQ)A(~SVS))

V(SA(~PVP)A(~QVQ)A(?RVR))……添加永真式

=(~PA?QA?R八?S)V(?PA?QA?RAS)V(~PA?QARA?

V(-PA-QARAS)V(~PAQA-RA-S)V(-PAQA-RAS)V(-PAQA

RA-S)V(-PAQARAS)V(?QA?PA?RA?S)V(?QA?P八?RAS)V(-Q

A-PARA-S)V(-QA-PARAS)V(~QAPA-RA-S)V(-QAPA~RAS)V

(~QAPARA?s)v(~QAPARAS)v(~RA?QA~PA~S)V(?RA~QA~P

AS)V(-RA-QAPA-S)V(-RA-QAPAS)V(?RAQA?PA?S)V(-RAQ

A-PAS)V(-RAQAPA-S)V(-RAQAPAS)V(SA?QA?RA?P)V(SA-

QA-RAP)V(SA-QARA-P)V(SA-QARAP)V(SAQA-RA-P)V(SAQ

A-RAP)V(SAQARA-P)V(SAQARAP)……合并相同的項(xiàng)

<=>(?PA~QA~RA~S)V(~PA~QA?RAS)V(?PA~QARA?S)V(~

PA-QARAS)V(?PAQA?RA?S)V(-PAQA-RAS)V(-PAQARA-S)V

(-PAQARAS)V(~QAPA-RA-S)V(-QAPA-RAS)V(-QAPARA-S)

V(-QAPARAS)V(-RAQAPA-S)V(-RAQAPAS)V(SAQARAP)

主析取范式

(3)等價(jià)變換法

P-(RA(Q->P))o~PV(RA(~QvP))=~PV((RA~Q)V(RAP))

=(~PA(~QVQ)A(~RVR))V((RA~QA(~PVP))V(RAPA(~QVQ)))

=(~PA~QA~R)v(~PAQA~R)V(~PA~QAR)VPAQAR)V(RA~QA~P)

v(RA~QAP)V(RAPA~Q)V(RAPAQ)

=(~PA~QA~R)v(~PAQA~R)V(~PA~QAR)V(~PAQAR)V(RA~QAP)

V(RAPAQ)-------主析取范式

PT(RA(QTP))O~PV(RA(~QVP))

<=>(~PVR)V(T)<=>~PVR

=~PVRv(~QAQ)

=(~PVRV~Q)A(-PVRVQ).......主合取范式

13.解：

(1)(P—*Q)—?(PAQ)?=>~(~PVQ)V(PAQ)?TA(-PVQ)=~PVQ

(~P->Q)A(Q->P)=(~(~P)VQ)AQVP)<=>(PVQ)A(~QVP)

=Pv(~Q/\Q)oP------不等價(jià)

⑵(P一Q)A(P-R)=(~PVQ)A(~PVR)=~Pv(Q/\R)

P一(QAR)=~PV(QAR)--------等價(jià)

14.解：由題設(shè)A：A去，B：B去，C：C去，D：D去

則滿足條件的選派應(yīng)是如下范式：(A一(CVD))2(BAC)A~(CAD)

構(gòu)造和以上范式等價(jià)的主析取范式

(A一(CVD))2(BAC)2(CAD)

=(~Av(CA~D)v(~CAD))A(~Bv~C)A(~CV~D)

=(~AABv~C)ACv~D))v((CA~D)ABv~C)ACv~D))

v((~CAD)A(~Bv~C)A(~Cv~D))

=(~AA~BA~C)V(~AA~BA~D)V(~AA~CA~C)V(~AA~CA~D)

V(CA~DA~BA~C)V(CA~DA~BA~D)V(CA~DA~CA~C)

V(CA~DA~CA~D)V(~CADA~BA~C)V(~CADA~BA~D)

V(~CADA~CA~C)V(~CADA~CA~D)

=AA~BA~C)V(~AA~BA~D)V(~AA~CA~C)V(~AA~CA~D)

V(CA~DA~BA~D)V(~CADA~BA~C)V(~CADA~CA~C)

=AA~BA~C)v(~AA~BA~D)v(~AA~C)VAA~CA~D)

V(CA~BA~D)V(~CA~BAD)V(~CAD)

=(~AA~BCA(DV~D))V(~AA~BA~DA(CV~O)

V(~AA~CA(BV~B)A(DV~D))V(~AA~CA~DA(BV~B))

v(CA~BA~DA(Av~A))v(~CA~BADA(AV~A))

v(~CADA(Av~A)A(Bv~B))

=(~AA~BA~CAD)V(~AA~BA~CA~D)V(~AA~BACA~D)

VAA~BA~CA~D)VAABA~CA~D)VAA~BA~CA~D)

V(AA~BACA~D)V(~AA~BACD)V(ABCAD)

VAA~BA~CAD)V(~AABA~CAD)V(~AABA~CD)

V(~AA~BA-CAD)V(~AA~BA~CA~D)V(AABA~CAD)

V(AA~BCAD)V(~AABA~CAD)V(~AA~BCAD)

=(~ABA~CAD)V(~AA~BA~CA~D)V(~AA~BACA~D)

V(~AABA~CA~D)V(ABACD)V(AA~BA~CAD)

v(~AABA~CAD)V(AABA~CAD)

共有八個(gè)極小項(xiàng)，但根據(jù)題意，需派兩人出差，所以，只有其中三項(xiàng)滿足要求：

(AA~BACA~D)?(AA~BA~CAD),AABA~CAD)

即有三種方案：A和C去或者A和D去或者B和D去。

15.證：(1)由定理LU,需證(P一Q)一(P—(PAQ))為永真式

v(P-Q)一(P一(PAQ))

<=>~(~PvQ)v(~Pv(PAQ))

=~(~PvQ)v((~PvP)A(~PvQ))

(~PvQ)v(~PvQ)=T

...(p—Q)=(PT(PAQ))

(3)由定理1.11,需證PA~PAR—S為永真式

vPA~PAR―?S=FAR—?SoF―>S<=>T

APA~PAR=S

16.證：(1)性質(zhì)1由定理1.11和“一”的定義，A一A是永真式，所以A=A。

(2)性質(zhì)2由定理1.11,???A=B,B=A,A—B和B—A是永真式，

即A一B是永真式，由定理1.3,A=B成立。

(3)性質(zhì)3由定理1.11,「A=B,A—?B是永真式，又?：A是永真式，

根據(jù)“一”的定義，B必是永真式。

17.證：“=”?：A=B,A—B是永真式，

vA-?B0~AvB=~(~B)V―AB-A=T

~B=~A

“=”因?yàn)樯鲜龅葍r(jià)式是可逆的，當(dāng)?B=~A,必有A=B。

18.解：設(shè)P：珍寶藏在東廂房

Q：藏寶的房子靠近池塘

R：房子的前院栽有大柏樹

S：珍寶藏在花園正中地下

T：后院栽有香樟樹

M：珍寶藏在附近(后院)

對(duì)語(yǔ)句符號(hào)化以后得到以下蘊(yùn)涵式：

Q—~P,R-P,Q,RvS,T—M=?

(QiP)A(R—P)AQA(RvS)A(T-M)

?QA(Q—~P)A(R-?P)A(RvS)A(T-M)

=~PA(R一P)A(RVS)A(T^M)

PA(~P—…R)A(RvS)A(T―>M)

=~RA(RVS)A(T―>M)

0sA(T—M)

所以s為真，即珍寶藏在花園正中地下。

19.解：⑴不成立(P=0,Q=l)

(2)不成立(P=l,Q=R=O)

(3)不成立(P=0,Q=l)

(4)不成立(P=0,Q=l,R=0)

（5）不成立（P=l,Q=l,R=0）

20.證：（1）利用CP規(guī)則

①PP（附加前提規(guī)則）

②~PvQP

③QTW②

④R-QP

Q—R

⑤T@E23

⑥~R血⑤

⑦P—RCP規(guī)則①⑥

（2）利用CP規(guī)則

①PP（附加前提規(guī)則）

②PVQT①E?

③(PVQ)—(RAS)P

④RAST①k

⑤ST@E4

⑥SvET⑤E?

⑦(SvE)一BP

⑧BT@?I5

(9)P—BCP規(guī)則①⑧

（4）（反證法）

①~P)P（附加前提規(guī)則）

②P

③P-RP

④RT②③k

⑤(R->Q)A(”S)P

⑥RfQT⑤E?

⑦QT④⑥I5

⑧R-ST⑤E?

⑨sT④⑧I5

?(QTE)A(S-B)P

?QTETOE3

QS-BT?E3

?ET⑦?I5

?BT?OI5

?EABT?0E5

?~(EAB)P

OFT??

21.(2)解：對(duì)原子命題符號(hào)化

P:無(wú)任何痕跡

Q：失竊時(shí)，小花在0K廳

R：失竊時(shí)，小英在0K廳

S：失竊時(shí)，小胖在附近

T：金剛是偷竊者

M：瘦子是偷竊者

前提：{P,QVR,S——P,Q—T,?S—?R,R—M}

結(jié)論：？

推導(dǎo)：①PP

②S—~PP

③?ST①②EI

④?S-RP

⑤?RT③④I

⑥QVRP

⑦QT⑤⑥1

⑧Q-TP

⑨TT⑦⑧I

**?金剛是竊賊。

22.解：⑴不相容

（2）相容（P=1,R=。=S=0）

（3）不相容

（4）不相容

23.⑴證：（P—>?Q）A（RVS）A（S—>?Q）A（P一0AP

q（?pV?①人（RVS）A（~SV?Q）A（?PVQ）AP

即4)={~PV~Q,RVS,?SV?Q,?PVQ,P)

利用消解原理:

?PP

②zpv?QP

③?Q①②

④zPVQP

⑤?p③④

?PAP=F口①⑤

習(xí)題2.1

1.把下列命題翻譯成謂詞公式：

（1）每個(gè)有理數(shù)都是實(shí)數(shù)，但是并非每個(gè)實(shí)數(shù)都是有理數(shù),有些

實(shí)數(shù)是有理數(shù).

解：設(shè)A（x）：x是實(shí)數(shù)鳳x）:x是有理數(shù)，則有：

V（xXWx）—>A（X））A—iVx（A（x）—>B（X））A3X（A（X）AB（X））

（2）直線a和b平行當(dāng)且僅當(dāng)a和b不相交.

解：A（x）：x是直線,

F（x,y）:x與y平行G（x,y）：x與y相交，則有：

VaVb［A（a）AA（b）—>（JF（G,b）——iG（a,Z>））］

（3）除非所有的會(huì)員都參加，這個(gè)活動(dòng)才有意義

解：4（x）：x是會(huì)員C（x）:x有意義

F（x,j）:無(wú)參加ya:這個(gè)活動(dòng)

C（a）-?Vx（A（x）r/了,〃））或者—>Vx（A（x）->F（x,a））—>—\C（a）

（4）任何正整數(shù)不是合數(shù)就是質(zhì)數(shù).

解：A（x）:x是正整數(shù)B（x）:x是合數(shù)C（x）：x是

質(zhì)數(shù)

Vx（A（x）rB（X）VC（X））

（5）凡是存錢的人都想有利息,如果沒(méi)有利息，人們就不會(huì)存錢

解：A（x）：x是人B（x）：x存錢a：利息

P：存錢有利息F（x,y）：x想有y

Vx［（A（x）AB（x）—>F（x,a））A（—IP—>A（X）A—J?（X））］

2.設(shè)論域D={0,1,2}.把下列公式用不含量詞的公式表示出來(lái).

（1）（vx）P（x）A（3x）Q（x）

P（O）A尸⑴AP（2）A（/?（O）VK⑴vQ（2））

(2)(vx)[P(x)-Q(x)]

[p(o)->e(o)]A[p⑴-e(i)]A[尸⑵te(2)

(3)(vx)[-P(x)]v(Bx)Q(x)

解為：(~P(0)八?P(1)A?P(2))V(Q(0)vQ(l)vQ(2))

3.指出下列公式中的約束變?cè)妥杂勺冊(cè)?并確定公式的轄域.

(1)(VX)P(X)TQ(X)

P(x)中的X為約束變?cè)?，轄域?yàn)椋篜(X).

Q(X)中的X為自由變?cè)?/p>

(2)(vx)[P(x)△Q(x)]一((vx)P(x)AQ(x))

(Vx)[P(x)AQ(x)]中，P(x)和Q(x)中的x均為

約束變?cè)犛驗(yàn)镻(x)AQ(x)；

(Vx)P(x)/\Q(x)中，P(x)中的x為約束變?cè)?/p>

轄域?yàn)镻(x),Q(x)中的x為自由變?cè)?/p>

(3)(3x)(3y)[P(x,y)AQ(a)]v(vz)R(x,z)

Gx)Gy)[P(x,y)AQ(a)]中,x,y是約束變?cè)?，?/p>

域?yàn)镻(x,y)AQ(a),

Q(a)中的a為自由變?cè)?/p>

(Vz)R(x,z)中,z為約束變?cè)?轄域?yàn)镽(x,z),z

為自由變?cè)?/p>

4.對(duì)下列公式中的變?cè)M(jìn)行代換，以使任何變?cè)荒芗仁羌s束

變?cè)质亲杂勺冊(cè)?

(1)(vx)(3y)[P(xy)Q(y,z)]v(vz)R(x,y,z).

解：(Vx)(h)[?(x,y)-?°(y,f)]v(Vz)H(x,y,z)

(2)((vx)[P(x)-R(x)]vQ(x))A((3x)R(x)-(2z)S(x.z))

解為：((Vx)[P(x)->R(x)]vQ(U))A((3x)R(x)T(3z)S(V,z))

習(xí)題2.2

1.（1）D：數(shù)A（x）:x=0f（x,y）=xy

VXVJ［A（/（X,J））->A（x）vA（j）］A-iA（xT）fY（/（x-l,x+1））

永真式

⑵A（x）:x是誠(chéng)實(shí)的人B（x）：x講實(shí)話a：小林

VX［A（X）—?B（x）］A—iA（a）—>—iB（a）

可滿足式

（3）A（x）:x不便宜B（x）:x是好貨

“尤丁）:X買的ya：衣服b：小王

Vx（A（x）—>B（X）］AF（a,b）/\A（a）—>B（a）

可滿足式

（4）A（x）:x是作家B（x）:x懂得人性本質(zhì)

C（x）:x是詩(shī)人￡>（x）:x是真正的

E（x）:x能刻畫人們內(nèi)心世界

尸（x）：x很高明P（x,y）:x創(chuàng)作了y

a：莎土比亞b：哈姆雷特

Vx［（A（x）AB（x）-?F（X））A（C（x）A—IE（X）—>—iZ）（x））］AP（a,b）

A—1（3x）（A（x）A—iB（x）A￡（X））AVX［C（X）AP（x,b）—>Z）（x）］

2.（1）T

⑵A=P(a,f(b))AP(b,f(a))

=P(3,f(2))AP(2,f(3))

=P(3,3)AP(2,2)

=1AO

=0

B=(Vx)Gy)P(y,x)

=Gy)P(y,2)A(3y)P(y,3)

o(P(2,2)vP(3,2))A(P(2,3)vP(3,3))

=(Ovl)A(0vl)

=1

C=(By)(Vx)P(y,x)

<=>(Vx)P(2,x)v(Vx)P(3,x)

o(P(2,2)AP(2,3))V(P(3,2)AP(3,3))

=(0A0)V(1A1)

=1

E=(Vx)(Vy)[P(x,y)-?P(f(x),f(y))]

o((Vy)[P(2,y)TP(f(2),f(y))])A((Vy)[P(3,y)

->P(f(3),f(y))])

o((P(2,2)->P(f(2),f(2)))A((P(2,3)->P(f(2),f

(3)))A((P(3,2)-?P(f(3),f(2)))A(P(3,3)fP(f

⑶,f⑶)))

=((Of1)A(Of1))A((IfO)A(If0))

=0

3.(1)F(2)T

(3)T

4.D:實(shí)數(shù)P(x,y):y=ex,Q(y)：y>0

習(xí)題2.3

1.(1)Q(y)]

oBxBy[~P(x)v2(y)]

o七臥?P(x)vRQ(y)]

<=>3x~P(x)vRQ(y)

o?VxP(x)vh。(y)

=(Ar)P(x)t(3j)g(y)

(2)(3x)Gy)[P(x)fQ(y)]o(Vx)P(x)fGy)Q(y)

證明：

<=>Gx)[?P(x)]VGy)Q(y)]

<=>(Vx)P(x)-?(3y)Q(y)

⑶?Gy)(Vx)P(x,y)=(Vy)(3x)[?P(x,y)]

證明：

<=>(Vy)[~(Vx)P(x,y)]

o(Vy)[Gx)[~P(x,y)]]

<=>(Vy)Gx)[~P(x,y)]

2.不成立

解:因?yàn)镚x)[P(x)fQ(x)]

。Gx)[~P(x)]vGx)Q(x)

o(Vx)P(x)fGx)Q(x),故原式不成立.

n—Siol>0)尸(1)尸⑵0(0)。⑴。⑵

DT0,051501'0'1

3.⑴?((Vx)P(x)t6y)P(y))

o?(?(Vx)P(x)v(3y)P(y))

((3xX-P(x)v(3y)P(y))

o(Vx)尸(%)△(￥/?P。))

=(VxRy)(尸(x)人?P(y))——skolem范式

⑵?((Vx)尸(x)fGdVz)0(y,z))

<=>~(-(Vx)p(x)v3(JXVZ)6(J,Z))

=(VX)P(X)A(VJX3Z)~Q(J,z)

=(Vx)(Vy)(玉X尸(x)人?Q(y,z))----前束范式

<=>(VXXVJX^(^)A?Q(y,f(x,y)))-—skolem范式

(3)(Vx)(Vy)[(3z)P(x,y,z)A((3u)Q(x,u)A

(3v)Q(y,v))]

(4)(Vx)[~P(x,0)—(Gy)P(y,f(x))A(Vz)Q(x,z))]

4、解:

習(xí)題2.4

1.⑴證:在某個(gè)解釋下，(%迫F)[P(x)A2(y)]取值1,必有

尸(4)八。0),取值1,因此，3?eDP(a)取值1。

.?.(h)P(x)取值1,由定義，蘊(yùn)含關(guān)系成立。

(2)①?((3X)P(X)AQ(a))o?(3x)P(x)v?Q(a)

o(Hx)P(x)Q(a)

(2)證：在某個(gè)解釋下，?((玉)P(x)人Q(a))取值1

即(土)尸⑴AQ(a)取值0,分二種情況：

i)(土)明=0,則無(wú)論。⑷為何值，0x)P(x)+。(“)取值lo

ii)Q(a)=0(3x)P(x)=1,則(土)尸(x)t■?Q(o)取值1

由定義，蘊(yùn)含關(guān)系成立。

(3)(Vx)[~P(x)-Q(x)]A(Vx)[~Q(x)]nP(x)

o(Vx)[P(x)VQ(x)]A(Vx)[~Q(x)]

o(Vx)([P(x)VQ(x)]ArQ(x)])

<=>(Vx)(P(x)A?Q(x))

<=>(Vx)P(x)A(Vx)?Q(x)

=>(Vx)P(x)

=>P(y)

<=>P(x)

(4)(Vx)[P(x)vQ(x)]A(Vx)[~P(x)]=>(Vx)Q(x)

證明：

<=>(VX)[(P(X)VQ(X))ACP(X))]

o(Vx)[Q(x)A?P(x)]

o(Vx)Q(x)A(Vx)[?P(x)]

=>(Vx)Q(x)(簡(jiǎn)化法則)

(5)(3x)[P(x)f?Q(x)]A(Vx)P(x)n?(Vx)Q(x)

證明：

o(Gx)[~P(x)]vOx)[-Q(X)])A(Vx)P(x)

oC(Vx)P(x)v?(Vx)Q(x))A(Vx)P(x)

<=>C(Vx)Q(x))A(Vx)P(x)

n~(Vx)Q(x)(簡(jiǎn)化法則)

2、(1)P(x)A(Vx)Q(x)=>Gx)[P(x)AQ(x)]

答：該蘊(yùn)涵關(guān)系成立

判別方法一:當(dāng)左取1時(shí),必有P(t)=l,(Vx)Q(x)=l,

從而Q(t)=l,即P(t)AQ(t)=l,即右取1.

判別方法二:P(X)八(Vx)Q(x)

o(Vx)[P(y)AQ(x)]

nGy)[P(y)AQ(y)]

⑵Gx)P(x)—(Vx)Q(x)=>(Vx)[P(x)fQ(x)]

答：該蘊(yùn)含關(guān)系成立

右=(3x)P(x)->(Vx)Q(x)

<=>?Gx)P(x)v(Vx)Q(x)

<=>(Vx)[~P(x)]v(Vx)Q(x)]

=>(Vx)[P(x)->Q(x)]

(3)(Vx)[P(x)->Q(x)]=>(3x)P(x)-?(Vx)Q(x)

答:該蘊(yùn)涵關(guān)系不成立

判別方法一:構(gòu)造解釋口={41)}

左=(Vx)[P(X)TQ(X)]=1,而右

=(3x)P(x)->(Vx)Q(x)=0.

判別方法二:右二(3x)P(x)T(Vx)Q(x)

o?Gx)P(x)v(Vx)Q(x)

o(Vx)[~P(x)]v(Vx)Q(x)]

=>(Vx)[P(x)->Q(x)]

此為單向蘊(yùn)涵關(guān)系，故原式不成立.

3、這個(gè)證明不正確

證明：當(dāng)(Vx)[P(x)vQ(x)]取值1的時(shí)候，P(x)、Q(x)

中至少有一個(gè)對(duì)于任意的x取值都為1,則右邊式子中,(Vx)

P(x)、(Vx)Q(x)至少有一個(gè)也為1,故原式子成立。

習(xí)題2.5

1(2)(反證法)

①?(h)[P(x)fQ(x)]P

②(Vx)[p(x)-Q(x)]T①,E

③(Vx)[?(?P(x)fv°(x)]T②,I

④(VX"(X)A?Q(x))T③,I

⑤P(X)A?Q(x)US@

⑥P(x)T⑤,I

⑦(Vx)P(x)UG⑥

⑧(Vx)P(x)T(Vx)Q(x)P

⑨(Vx)2(x)T⑧,I

⑩?。(x)T⑤,I

OQ(x)US⑨

口口T⑩口1

2.(1)錯(cuò)誤，應(yīng)換元，即

①(Vx)P(x)->Q(x),

②P(y)->。⑴

(2)正確

(3)錯(cuò)誤，a、b應(yīng)是同一個(gè)常元

(4)錯(cuò)誤，因?yàn)樵趐(x”(玉)[Q(X)AE(%)]中x并不是自由

出現(xiàn)

(5)錯(cuò)誤，因?yàn)樵?球)尸(x)-Q(x)中，前件是命題，

而后件不是命題

(6)錯(cuò)誤，因?yàn)閍、b并不是同一個(gè)常量

(7)錯(cuò)誤，①②和③④的順序不對(duì)

應(yīng)先使用ES,再使用US

3(1)解：設(shè)F(x,y):x2y;G(z):z20;f(x,y)=x-y

前提：

①V(x)V(y)(F(x,y)-*G(f(x,y))

②V(x)V(y)JF(x,y)f-1G(f(x,y))

③V(x)V(y)(-1G(f(x,y)-G(f(y,x)))

結(jié)論：V(x)V(y)(G(f(x,y))VG(f(y,x)))

證明(反證法)：

@-iV(x)V(y)(G(f(x,y))VG(f(y,x)))

②Ox)(3x)-i(G(f(x,y))VG(f(y,x)))

③—iG(f(a,b))A—iG(f(b,a))

@V(x)V(y)(F(x,y)fG(f(x,y))

⑤F(a,b)-*G(f(a,b))

⑥->G(f(a,b))-*-iF(a,b)

⑦V(x)V(y)(-iG(f(x,y)fG(f(y,x)))

⑧-iG(f(b,a))fG(f(a,b))

(9)V(x)V(y)JF(x,y)f-1G(f(x,y))

⑩-nF(a,b)-1G(f(a,b))

(11)G(f(a,b))-F(a,b)

?->F(a,b)AF(a,b)

4.(2)

證：首先，將結(jié)論否定否作為前提加入到原有前提中

{[(3x)P(x)->(V.r)[(P(x)vQ(x)-?7?(x))]}A(3X}P(X)A(3X)Q(X)A

~(HxX3y)[7?(x)A/?(%)]

o{(Vx)~%)v(Vx)[?(P(x)vQ(x))vA(3W)P(W)A(3v)g(v)A

?中)伏(卬)入R(y)]

<=>(VxX3wX3vXVwXvyI(~P(x)vR(x))△(?P(x卜?Q(x)vR(x))]

AP(w)A7?(W)A(~R(卬)V?R(⑷))]

o(V%XVwXv>')[(~P(X"R(x))△(??0(x)vR(x))AP(Q)A。(即

人(?R(w)v?R(y))]Skolem范式

子句集為{?P(x)vR(x),?P(x)v~Q(x)vR(x),P(a)R(b),?R(w)v?R(y)}

①?P（x）vH（x）

②P（a）

③於）①,②代換{a/x}

④R（c）③代換{c/x}

⑤?/?（w）v?/?（＞'）

⑥?R（y）④,⑤代換{c/w}

⑦?R（c）⑥代換{c/y}

⑧口

習(xí)題三

16.解

2A={0,{0},{a},{},{0.a},{0,},{a,},{0,a,}}

17.證：（1）

設(shè)xe2Au2B,則xe2A或xe2B.即XGAUB,

故xe2AU3.

等號(hào)成立的條件是：Ar）B=O.

（2）a=>wxe2An2B=>x62A且xe2B=?xcA5.xcB=JXcAnB

=>xe2AnB.

“="如XC2ACB,由于上述過(guò)程是可逆的，所以XC2AC2B.

18.解：(1)由于是求包含a的子集個(gè)數(shù)，實(shí)際上就是

在去掉a以后剩下的n—1個(gè)元素中分別取1個(gè)、2個(gè)、…、

n—1個(gè)元素的可能組合問(wèn)題，即CL+C1+CL+…+墨二"

(2)類似地，包含a、b的子集個(gè)數(shù)為

C上+C1+C氧+…+CM。

19.證：

?="對(duì)v(x,y)eAxC,xeA,yeC,vAcB,xeB,C40,

(x,y)eBxC,AxCcBxC.

?=????Ch0,???AxCh0,BxCh0,vxeA,vyeC,(x,y)eAxC,

又??,AxCGBxC,??.（x,y）wBxC,則xcB,故AGB。

習(xí)題四

6.

RiR2R5

關(guān)系

性質(zhì)

自反VVX

性

反自XXXXV

反性

對(duì)稱XVX

性

反對(duì)VXXXV

稱性

傳遞VVVXJ

性

10.(3)"=>"R是對(duì)稱的，設(shè)(x,y)eR則Rn(x,y)GR-1

v<y,x>eR~l:.<x,y>eR=><y,x>GR,§PR~l=R

"<="R=RiV(x,y)eR,由R”的定義，(y,x)6R~'

：.(y,x)eR,即R是對(duì)稱的。

(5)“n”R是傳遞的，對(duì)V<X,z>eR2

3jGA3<x,j>G1?<>G7?:.<X,Z>^R

即R2qR

"<="R2=R,,對(duì)V<x,y>eR<y,z>eR,由R，的定義,

有<x,z>eR2aR:.<x,z>eR,即R是可傳遞的。

13.解：?.?/?=&U&，且與口號(hào)二①

mmm

R=R\^R2A=AjUA2

:.R^=ZA(R*=I4,二需3|m,5|m

=>加=15,即72=16

R16=R；6UA”=R]UR?=R

故使Rm=Rn的最小正整數(shù)tn=1,W=16

1100000、

01000000、

11100000

15、珞：0100000

11100000

10000000

0000100000011111

M=M"R)=

R0000010000011111

00i11

16.當(dāng)曲。?.瞪1世，/W=I霜1

0000000:111000田12111

（）00?0100；0；、00011111,

t(RA）曲）=U（R1U出）

i=l

由歸納法可證：對(duì)VieNR；UR,(RiUR2)i

、00

8；A0000I￡.

."(心)山(&)=UKUUR="uK2)q.4(&u勺)'="iuR)

V=1x)V=12.2

+00

⑷證:①1+y=R???R+=t(R)=URi

i=l

..(R+y=MR))+=3(f(R))J

J=1

由歸納法可證：VMN+(?R)y=?R)

/\i0000

.?.(/?+「=U(f?y=u?(/?))=f(R)=R+

J=1j=l

③R。R*=/?+R*=心U?R)

/.RoR*=RO(IA\J^(/?))=ROIA\JROt(R)

=RUR°t(R)=t(R)=R+

習(xí)題五

1.證：,/A=N*}

R={((?,“(c,d))Iad=bc\

①自反性由A的定義，ab=baa,beN

：.([a,b\(a,hy)eR

②對(duì)稱性設(shè)((a,b),(c,d))eH,則ad=be

即cb=da((c,d),(a,〃))eR

③傳遞性設(shè)((。1，坊),(。便1))6￡,則

((q，4),(c2d2))eR，則c[d2=4c2

=>a14d2=4Gd2=bxdxc1=>a[d2-h{c2

???46力),&&))eR

3.解：???A={1,2,3,4,},So={{1,2,4},{3}}

設(shè)A={1,2,4},4={3}

R={(1,1),(1,2),(1,4)(2,1),(2,2)(2,4),(4,1),(4,2),(4,4)(3,3)}

4.解：???每個(gè)集合的劃分就可以確定一個(gè)等價(jià)關(guān)系

集合有多少個(gè)劃分就可以確定多少個(gè)等價(jià)關(guān)系

不同的劃分個(gè)數(shù)為：

血猶卜+“+戲+』5

不同的等價(jià)關(guān)系個(gè)數(shù)等于不同的劃分個(gè)數(shù)，所以不同的等價(jià)關(guān)系

個(gè)數(shù)為15o

5.解:

①限色不是A上的等價(jià)關(guān)系

②RC&是A上的等價(jià)關(guān)系

③「伏-&）是A上的等價(jià)關(guān)系

④與?！辈皇茿上的等價(jià)關(guān)系

9.解：A-{a,b,c]

2A={<1>,(a),(b\(c),(a,b\(a,c),(b,c),(a,b,c)}

10.L都是等價(jià)關(guān)系和偏序

關(guān)系。

<Sc,

13.證：i)自反性，對(duì)D方/.(b,b)wR,(H的

自反性)

顯然,:.(b,b)GRC\(BxB)

ii)反對(duì)稱性，對(duì)Ya,beB,(a,Z>)eZ?n(Bx3),伍㈤e/?D(BxB)

即(Q,Z>)GR,0,a)e/?,由R的反對(duì)稱性，=>a=b

iii)傳遞性，