离散数学及其应用数理逻辑部分课后习题答案

离散数学及其应用数理

逻辑部分课后习题答案

作业答案：数理逻辑部分

P14：习题一

1、下列句子中，哪些是命题在是命题的句子中，哪些是简单命题哪些是真命题

哪些命题的真值现在还不知道

(3)忑■是无理数。

答：简单命题，真命题。

(9)吸烟请到吸烟室去！

答：不是命题。

(12)8是偶数的充分必要条件是8能被3整除。

答：复合命题，假命题。

14、讲下列命题符号化。

(6)王强与刘威都学过法语。

答：p：王强学过法语；平刘威学过法语。

符号化为：。人4

(10)除非天下大雨，他就乘班车上班。

答：p：天下大雨；q：他乘班车上班。

符号化为:PTq

(13)“2或4是素数，这是不对的''是不对的。

答：p：2是素数；q:4是素数。

符号化为：TTpvq))

15、设p:2+3=5.

4：大熊猫产在中国。

r:太阳从西方升起。

求下列复合命题的真值。

(2)(r*p八q))crp

(4)(pAg/\-1r)—((「，v-><7)->r)

解答：p真值为1；q真值为1；『真值为0.

(2)「入4真值为1；rf(p/\q)真值为1；「p真值为0；

所以(rT•(pAg))3r?真值为0.

(4)1r真值为1,「pv-uy真值为0,v「q)-»r真值为1；

所以)一•((「pv-1q)fr)真值为1.

2

19、用真值表判断下列公式的类型。

(4)(/?-»<7)-»—>—1/7)

Pq7piq-\(]--1P(p—>q)—(—i(7f—ip)

0011i11

0110i11

1001001

1100i11

所以为重言式。

(7)(pfq)—(rgs)

pqrspfqr—s(pfq)c(rcs)

0000i11

0001i00

0010i00

0011i11

0100i11

0101i00

0110i00

0111i11

1000010

1001001

1010001

1011010

1100i11

1101i00

1110i00

1111i11

所以为可满足式。

3

P36:习题二

3、用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表

法求出其成真赋值。

⑴Tp八qiq)

解答：

Tp八qTq)

O-i(TpAq)vq)

O」((「Pv「q)vq)

<=>-i(->pv-17v<7)

=」］

O0

所以为永假式。

(2)(pf(pvg))v(pfr)

解答：

(pf(pvq))v(p—r)

o(「pv(pvq))vJpvr)

=(—7P7G7(—>pvr)

=1v(—ipvr)

O1

所以因为永真式。

(3)(pv<7)->(pAr)

解答：

(pvq)T(p八叫

0-«(pv^F)v(pAr)

=(—>pA—)g)v(pAr)

为可满足式。

真值表为

pqrp、qp/\r(pvq)—(〃△/•)

000001

001100

010100

011100

100100

4

101100

110100

111111

4、用等值演算法证明下面的等值式。

(2)((p-»q)/\(pfr))o(p->(q/\r))

解答：

((pf4)△(〃-7))

=(-1/7VA(—1PVr)

——ipv((7Ar)

0P-(q△r)

(4)(p/x-^)v(rpAg)O(pvq)/\->(pvq)

解答：

(p△-><7)v(「p△q)

O(pv「p)△(pvq)八(一iqv->p)A(—,<7vq)

O(pvq)△(-1>「，)

=(p\zq)人Tq/\p)

5、求下列公式的主析取范式，并求它们的成真赋值。

⑴([pfg)-»(-><?vp)

解答：

(「PT*T(FVp)

=(，")->(->>〃)

0Tp丫q)v(fvp)

<=>(―>pA—>q)v(—iqvp)

O(「p△「q)v-14Vp(析取范式)

O(「pA-if7)v((-1Pvp)Aiq)v(/?△(r?vq))

<=>(「PA「q)v((「pA「q)v(7?A->g))v((pA->g)v(p人q))

O(「pA-n<7)v(pA-14))v(pA.7)

。机vmvm

023

所以成真赋值为00,10,11

⑶(pv(q△7))-»(〃vqvr)

解答：

5

(pv(<7Ar))->(/?v^vr)

—-i(pv(f7Ar))v(pvvr)

=(-ipA—1(4Ar))v(pv^vr)

=(—1〃A(—।夕v—ir))v(pv(7vr)

=(「pA-)(7)v(—ipA-)r)7P7q71r(析取范式)

u>(-ipA-\qA(—irvr))v(—ipAJqvA—«r)v(pAJqvA(—vr))v

((—>/?vp)Aq八(—irvr))v((—)/?vp)AJqvg)Ar)

=(—ipA—\qA-ir)v(—ipAFAr)v(-ipA—)qA—ir)v(—ip△q△T)V

(pA—)qA-ir)v(pA—i,Ar)v(/?A<7A—)r)v(/?AAr)v

(—>p△q△—ir)v(-ipA^Ar)v(/7A^A—>r)v(pAAr)v

(—ipA—iqAr)v(—ipAr)v(pA-\qAr)v(pA(7Ar)

<=>(—ipA—\qA-ir)v(~ipA—iqAr)v(—)pA(7A—>r)v(—«pA(7Ar)

(pA—A-ir)v(pA—\qAr)v(pAA—,r)v(p△q△〃)

=mvmvmvmvmvmvmvm

01234567

所以为永真式，成真赋值为000,001,010,011,100,101,110,111

6、求下列公式的主合取范式，并求它们的成假赋值。

(1)-<9「P

解答:

Tq->「p)A「p

0-1(—)^V-ip)A—)/?

=(qA〃)△—!〃

Op/\-i〃Aq(合取范式)

=(pV(qVF))A(「pV(qVF))A((pv-ip)vq)

=(P7GM(〃V—1夕)A(—1/7V(7)A(—1/7V—it/)A(/?V(7)A(—>〃Vq)

O(/?VA(pV—)q)A(—1〃V<7)A(—1〃V—1夕)

AMAM八M

0123

为永假式，成假赋值为00,01,10,11

⑶(pf(pvq))vr

解答：

6

(pf(P"))vr

U>(—ipv(pv^))vr

0(-ip7P7G7丫

01

永真式，无成假赋值

7、求下列公式的主析取范式，再用主析取范式求主合取范式。

(1)(pAq)vr

解答：

(pA^)vr(已经是析取范式)

=(〃AqA(―irvr))v((—>pvp)A(—v(7)Ar)

=(p△4八—«r)v(pAqAr)v(—«pA-yqAr)v(—«pAAr)v(/7A—Ar)v(/?AAr)

=(—ipA—i(yAr)v(「pAr)v(pA—iqAr)v(pA—ir)v(/?AAr)

0根v7mvmvm

13567

oA/AMAM

024

8、求下列公式的主合取范式，再用主合取范式求主析取范式。

(2)(pcq)lr

解答：

(pgq)fr

<:>((，Tq)MqTp))Tr

O((「Pvq)人Jqvp))->r

0—i((-ip")△-qvp))vr

=((pA]q)v((7A「〃))vr

o(pvvr)A(pv—\pvr)A(—vvr)A(7v「pvr)

<=>(pv(yvr)A(—)qv—«〃vr)

«>(pvvr)A(-pv—vr)

oMAM

06

<=>mvvmvmvmvm

123457

13、已知公式A含3个命题变项p,q,r,并且它的成假赋值为010,Oil,110,

111,求A的主析取范式和主合取范式。

7

解答：成真赋值为000,001,100,101

所以主析取范式为vmVmV机

0145

而主合取范式为MAMAM人M

2367

15、用主析取范式判断下列公式是否等值。

(2)->(/?

解答：

Tp^q)

=rpv

=(「pA(「qv(7))v((-1Pvp)A->q)

<=>(—ipA「q)v(-ip△q)v(~>pA-)q)V(pA-«q)

=(-ipA—i^)v(-ip△q)v(p△->g)

otnvmv

o12

TPy)

~\pA-\C/

U>m

0

所以两式并不等值。

18、将下列公式化成与之等值且仅含有｛「,人｝中联结词的公式

⑶(pf(q/\r))vp

解答：

(p—(q八r))Yp

<=>(「pv((/Ar))vp

0—vpvAr)

O1

29、在某班班委成员的选举中，已知王小红、李强、丁金生3位同学被选进了

班委会。该班的的甲、乙、丙3位同学预言：

甲说：王小红为班长，李强为生活委员；

乙说：丁金生为班长，王小红为生活委员。

丙说：李强为班长，王小红为学习委员。

班委会分工名单公布后发现，甲乙丙三人都恰好猜对了一半。问王小红、李

强、丁金生各任何职(用等值演算求解)

解答：命题符号化：

P：王小红为班长；令：李强为生活委员；厂：丁金生为班长；s：王小红为生活委

员；

8

〃:李强为班长；V：王小红为学习委员。

设A:p△—\q；A:—ip八q；B:r八一is；B:—)rA5；C:wA—«V；C:—AV；

121212

由题意可知：

pAr<=>0;pA5<=>0;pAMo0;pAv<=>0;qA5<=>0;q△〃=0;rAW<=>0；5AVOO

所以AAB<=>0;AAB<=>0;AAC<=>0;AACO0;AAB<=>0;AAC<=>0;

111211122221

B/\Co0,8ACo0

II22

所以

(AvA)A(Bv5)A(CvC)

121212

=(4ABAC)v(AABAC)v(AABAC)v(AABAC)V

111112121122

(AABAC)V(AABAC)V(AABAC)V(AABAC)

211212221222

<»0v0v0v0v0v(AABAC)VOVO

212

oAABAC

212

所以选举结果为：李强为生活委员；丁金生为班长；王小红为学习委员。

30、某公司要从赵、钱、孙、李、周5名新毕业的大学生中选派一些人出国学

习。选派必须满足条件：

(1)若赵去，钱也去；

(2)李、周两人中必有一人去；

(3)钱、孙两人中去且仅去一人；

(4)孙、李两人同去或同不去；

(5)若周去，则赵、钱也同去。

用等值演算法分析该公司该如何选派他们出国。

解答：命题符号化：

P：赵去；(7：钱去；，：孙去；s:李去；f:周去。

所满足的条件即为

(1)若赵去，钱也去：pTq；

(2)李、周两人中必有一人去:svt；

(3)钱、孙两人中去且仅去一人：(4△-10V(「q/xr)；

⑷孙、李两人同去或同不去：(rAs)v；

(5)若周去，则赵、钱也同去：f->(p/\q)。

将所有条件进行合取，然后求其主析取范式

(pf4)A(svf)△((q△—.r)vAr))A((rA5)v(—irARS))人(ff(p△q))

=(—>pA—ArA5A—if)V(PAA—ifA—15AZ)

9

（过程省略）

所以最终方案有两套：

（1）赵钱周不去，孙李去；（2）赵钱周去，孙李不去。

P50:习题三

9、用3种方法（真值表、等值演算、主析取范式）证明下面推理是正确的。

若a是奇数，则a不能被2整除。若a是偶数，则a能被2整除。因此，如果a

是偶数，则a不是奇数。

解答：命题符号化：〃：a为奇数；q:a为偶数；r:a能被2整除

推理的形式结构：

前提：p；qTr；q

结论：f

推理的形式结构的另外一种描述：

（pf-ir）八（q-r）八q=­p

证明：（1）真值表法：

pqrF—1rp—)rqTr(〃f—>r)A(qfr)八q(〃->—ir)△(q—>r)△qf—

000111101

001101101

010111001

011101111

100011101

101000101

110011001

111000101

所以（pf为永真式；推理（p->t）△（q->r）人q=>

是正确的。

（2）等值演算：

10

(p->—>r)△(qr)△q——1/7

=(—ipv-nr)A(—iqvr)△q——)〃

=T(1»P7—«r)A(—iqvr)Aq)v—ip

=((〃Ar)v(<?A—>r)v—)q)v—ip

=(pAr)v(q△—«r)v—iqv-)p

=((〃Ar)v—>p)v((qAf)v—iq)

=((Pv「p)A(rv「p))v((qv->q)A(TV「q))

=(1A(rv—ip))v(1A(—»rv—>q))

O(rv-ip)v(—irv—iq)

=(rv—>〃)v(—irv-iq)

<»rv—)rv—ipv—iq

ol

(3)主析取范式

(p-»—ir)A(q—>r)Aq-»—)〃

<=>(r?v—)r)A(—i(/vr)A—ip

=v—)r)A(—i夕vr)A(7)V—p

=((pAr)v((7A—.r)v—)q)v―1P

=(p△r)v(qA-)r)v—iqv—

=(〃A(—\qvAr)v((—i〃vp)Aq八-ir)v((「pvp)A—iqA(—»rvr))v(「pA(—vq)A(—«rvr))

mvAHvmvm7m71nvmvm

01234567

12、填充下面推理证明中没有写出的推理规则。

刖提-p—>(4—>r),q一>(rfs)

结论：(pvq)fs

证明：

CDpv</附加前提引入

②P①化简

③4①化简

④〃(4->厂)前提引入

⑤qTr②④假言推理

⑥r③⑤假言推理

⑦s)前提引入

8r->s③@假言推理

⑨s⑥⑧^言推理

II

14、在自然推理系统P中构造下面推理的证明：

⑵前提：Pf

结论：「P

证明：

①TqAr)前提引入

②―i<7V—iT①置换

③，前提引入

4-i<7②③析取三段论

⑤piq前提引入

④⑤拒取式

(4)前提：qTp,q—s,s7t,t/\r

结论：

证明：

①〃r前提引入

②，①化简

③「①化简

④S一，前提引入

5_；(s—>/)A(Z—>S)④置换

6t—>s⑤化简

⑦9—s前提引入

8(qfs)人(sfq)⑦置换

⑨sf4⑧化简

⑩，―>q⑥假言三段论

②⑩假言推理

°qip前提引入

Op。。假言推理

9pdqOO合取

15、在自然推理系统P中用附加前提法证明下面推理：

(1)前提：PT(qT吟,STp,q

结论：s->r

证明：

①s附加前提引入

②STp前提引入

12

③;p①2)假言推理

④pf(q->r)前提引入

⑤qTr(W假言推理

⑥9前提引入

⑦r⑤⑥假言推理

16、在自然推理系统P中用归谬法证明下面推理：

(1)前提：p\q,pTr,qTs

结论：rvs

证明：

①Trvs)结论否定引入

-ifA-iS①置换

③-iS②化简

④->r②化简

⑤前提引入

⑥4fs前提引入

⑦④⑤拒取式

⑧F③®拒取式

A-nq⑦®合取

⑩Tpvq)⑨置换

Qp\zq前提引入

⑩。矛盾。

17:在自然推理系统P中构造下面推理的证明：

只要A曾到过受害者房间并且11点以前没有离开，A就是谋杀嫌疑犯。A曾到

过受害者房间。如果A在11点以前离开，看门人会看见过他。看门人没有看

见他。所以，A是谋杀嫌疑犯。

解答：

(1)命题符号化：P：A曾到过受害者房间；q:A在11点以前离开；

r：A就是谋杀嫌疑犯；s:看门人会看见过A；

(2)推理的形式结构：

前提：(p八Ftr；p；qts；7

结论：「

⑶证明

①f前提引入

13

②qis前提引入

③-117①O拒取式

④P前提引入

⑤P八7③④合取

⑥（pA->q）f