《離散數(shù)學》第一章習題參考答案

基礎(chǔ)習題

1(1)是，簡單命題

⑵是，簡單命題

⑶是，復(fù)合命題

⑷不是

(5)不是

(6)是,復(fù)合命題

(7)是，簡單命題

(8)不是

(9)不是

(10)是，簡單命題

(11)是，復(fù)合命題

(12)是，復(fù)合命題

(13)是，復(fù)合命題

(14)不是

(15)是,簡單命題

2(Dp,其中p：古埃及是世界四大文明古國之一。真值為1。

(2)p,其中p:乃是無理數(shù)。真值為1。

(3)pvq,其中p:2是素數(shù)，q:5是素數(shù)。真值為1。

(6)pAq,其中p:2是正數(shù)，q:-3是正數(shù)。真值為0。

(7)p,其中p:王健與魏鋼是朋友。真值依實際情況而定，非。即1。

(10)p,其中p:圓的周長等于直徑乘以不。真值為1。

(iDq-p,其中p:5是奇數(shù)，q:7是2的倍數(shù)。真值為1。

(12)q—p,其中p:4是奇數(shù)，q:4能被3整除c真值為1。

(13)p,其中p:2050年10月1日是晴天。真值依2050年10月1日的實際天氣

情況而定，非。即L

(15))p,其中p:外星人是存在的。真值非0即1,隨著今后科技的進步可以判斷

出來。

3(l)pAq,其中p:蘋果樹是落葉喬木，q:梨樹是落葉喬木。真值為1。

(2)pAq,其中p:8是2的倍數(shù)，q:8是4的倍數(shù)。真值為1。

(3)pA「q,其中p:0是最小的自然數(shù)，q:0是正數(shù)。真值為1。

(4)pAq,其中p:3是偶數(shù)，q:3是素數(shù)。真值為0。

(5)p,其中p:豆沙包是由面粉和紅小豆做成的。真值為1。

4(l)pVQ,其中p:2是偶數(shù)，q:4是偶數(shù)。真值為1。

(2)pVq,其中p:5是奇數(shù)，q:2是奇數(shù)。真值為1。

⑶-ipV-iq,其中p:2是素數(shù)，q:6是偶數(shù)。真值為0。

(4)(pA-iQ)K(->pAQ),其中p:小麗能買一個盲盒，q:小麗能買一個拼圖，依

據(jù)實際情況，真值為1當且僅當〃、q中只有一個真值為1。

(5)pvq,其中p:王冬的生日是9月12日，q:王冬的生日是9月13日。依據(jù)

實際情況，真值為1當且僅當p、中有一個真值為1。

5設(shè)p:3<1,q:地球是靜止的

(1)p—>q,真值為1：(2)p~iq,真值為1:⑶--P，真值為0：(4)—iq—>p,

真值為0;(5)「qTp；真值為0；(6)p-q,真值為1。

6p-q,其中p:今天是星期六，q:昨天是星期五。真值為1。

(l)pcq,其中p:實函數(shù)y=/(x)在/點可導(dǎo)，Q：實函數(shù)y=/(x)在/點連續(xù)。

真值為0。

(2)p—q,其中p:4是偶數(shù)，q:三角形有四個內(nèi)角。真值為0。

(3)p—q,其中p:1+2.3,(?:l+3#4o真值為1。

7設(shè)2是正整數(shù)；中國有四大發(fā)明；r：太陽從東方落下。求下列命題

的真值。

(1)0(2)0(3)0(4)1

8(1)矛盾式：(等值演算法)〃人「八Tq—>〃)=八「pu>0

⑵重言式：（等值演算法）

（（〃->4）—>（r/—>—^））vro（（〃->/—>（〃->q））vrolv/ol

⑶非重言式的可滿足式：（真值表法）

pqrpiqPir(pfq)—■(〃》?)

000111

001111

010111

011111

100001

101010

110100

111111

（4）重言式：（等值演算法）（pTp）v（pTr;）oiv（pTr?）oi

⑸非重言式的可滿足式：（真值表法）

(〃->q)<->(〃->/?)

pqrp—q

001100

010100

101010

110100

(6)非重言式的可滿足式：(主范式法)

(―y?Av?*))v((</A?")v(pAr))o(-y?A-<q)v(~>pA?*)v(<yAF)v(pA??)

=(-y?A—>qAr)v(-y?A—>^A-ir)v(-1PAr)v(pAT)v(pAFAr)

u>"bv?H|v"qv""vtn-1

(7)非重言式的可滿足式：(等值演算法)

TfrrZTpTq)O[p八q)v(〃人r)o〃

9(l)x(2)“3)q(4)x(5)x(6)x(7)Y

10(1)/7-?(</—>/?)o-ipv(-^v/?)<=>pv(-y?v-^)->(pxy)

⑵T〃一14)OT〃一幻vTq-〃)O(〃△r)v(qA」p)o(〃vg)△T〃Aq)

(3)(/?—><7)A(p—>r)<=>(r)v<7)A(—y?vr)<=>—y?v((/A7-)u>pT(q八r)

(4)((〃-><7)<->(f—>-/?；)Ar<Z>((/7—><7)<->(p—>i7))A?■<Z>1Ar<Z>??

11(1)主合取范式：v</)—>(—>(/—>—/)))<=>(-/?v</)A(—/?v</)<=>(—./?v</)<=>M2,

主析取范式：恤7ml.

成假賦值10;成真賦值00、OKHo

(2)主析取范式：

(pvq)Tf=(―7?Ar)V-ir<Z>(—/2八r八7?)V(—/7A-^TA-i〃)V(/2A-,r)

v(〃A「夕八—.r)v(—AA—>r)o〃?()vm}v/w2Vm4v.

主合取氾式：M3八M5八M7.

成真賦值000、001、010、100、110；成假賦值011、10klllo

(3)

pqrpiq(〃一

00010

00111

01010

01111

10001

10100

11010

11111

主析取范式：網(wǎng)7rnyvm4vm7.

主合取范式：）A八

M/\M2M5M?.9

成真賦值001、011、100、111;成假賦值000、010、10kHOo

（4）主合取范式：（〃fq）v（gfr）o「pvqvFvrol.

9

主析取范式：〃7（）v/〃?vm2vm3vm4v，n$vv，許.

成真賦值000、001、010、oil、100、10k110、111；無成假賦值。

12（1）主析取范式：〃[2v〃?5v/%7.主合取范式：MAA7]A/V/AMAM

，o346?E

（2）主合取范式：A/OAM,AM2AM6AM7.主析取范式：z〃3vm4v

13設(shè)p:今年是2024年，q:明年是2025年，r:明年是2026年，

（1）推理正確，pir,p=r（假言推理規(guī)則），

（2）推理的形式結(jié)構(gòu)為（pTq）/\q—p,真值表如下，非重言式，故推理不正

確。

Pqp—q（/7-><?）At/（〃一>夕）八夕—〃

00101

01110

10001

11111

⑶推理正確，p-r,「r=「p（拒取式規(guī)則）。

（4）推理的形式結(jié)構(gòu)為（pTq）A「pT「q,真值表如下，非重言式，故推理不正

確。

Pq（〃->9）八r?（〃一>g）A-i〃TF

0011111

0110110

1001000

1100100

（5）推理的形式結(jié)構(gòu)為（p-（qV廠））Aprq,1（）1為其成假賦值，非重言式，故

推理不正確。

（6）推理正確，推理的形式結(jié)構(gòu)為

前提per，-y>

結(jié)論f

證明①〃一廠前提引入規(guī)則

②（〃-「）△（「fp）①置換規(guī)則

③rfp②化簡規(guī)則

④T前提引入規(guī)則

⑤f③④拒取式規(guī)則

14(1)前提：［)7q，qn，pis

結(jié)論：rA(/?->5)

證明：①pfs前提引入規(guī)則

②T前提引入規(guī)則

③r，①②拒取式規(guī)則

④p“前提引入規(guī)則

⑤q③④析取三段論規(guī)則

⑥g一尸前提引入規(guī)則

⑦「⑤⑥假言推理規(guī)則

①⑥合取引入規(guī)則

⑵前提：p，〃一＞(“一＞(r/\s))

結(jié)論：qTr

證明：①4附加前提引入規(guī)則

②p前提引入規(guī)則

③〃->(4->(rAS))前提引入規(guī)則

④43(r/\s)②③假言推理規(guī)則

⑤…①④假言推理規(guī)則

@r⑤化簡規(guī)則

由附加前提證明法證得推理是正確的。

⑶刖提：〃，T「vs)，(s—>r)V—

結(jié)論：r

證明：①〃前提引入規(guī)則

@(5—>?r)v-/?前提引入規(guī)則

③①②析取三段論規(guī)則

④7否定結(jié)論引入規(guī)則

⑤f③④拒取式規(guī)則

@-irA—15④⑤合取引入規(guī)則

⑦-1(，vs)⑥置換規(guī)則

⑧T~s)->T〃vg)前提引入規(guī)則

⑨Tpvq)⑦⑧假言推理規(guī)則

⑩⑨置換規(guī)則

?力⑩化簡規(guī)則

?〃八力①?合取引入規(guī)則

?得到了矛盾式，由歸謬法證得推理是正確的。

(4)前提：pT(qfr),p,

結(jié)論：rv.v

證明：①〃前提引入規(guī)則

②p->(qf力前提引入規(guī)則

③gf廣①②假言推理規(guī)則

?q前提引入規(guī)則

⑤「③④假言推理規(guī)則

⑥r(nóng)vs⑤附加規(guī)則

15設(shè)p:今天我有空，q:我去博物館玩，r:我去奧體公園玩,:博物館人

多。

前提：P-(qVr),s->-iq,p,s

結(jié)論：r

證明：①p前提引入規(guī)則

②p->(qVr)前提引入規(guī)則

③qVr①②假言推理規(guī)則

@s前提引入規(guī)則

⑤s->「q前提引入規(guī)則

⑥④⑤假言推理規(guī)則

⑦r③⑥析取三段論規(guī)則

提升習題

1設(shè)Pi：陳思為大隊長，qi：陳思為宣傳委員，陳思為組織委員，P2：孫瑤

為大隊長，q2：孫瑤為宣傳委員，P3：王博為大隊長。

1=>(PiA「口2)V(「PiAq2)①

1=>(p3AFDV(ip?Aqj②

1o(P2A-i^i)V(-ip2ArJ③

①八②得1?！竷?nèi)Aq2Ap3AM④

③A④得10-yp1Aq2Ap3A-iQiA-ip2八R，

最終得出：孫瑤為宣傳委員，王博為大隊長，陳思為組織委員。

2(1)主析取范式：恤V町V"72V…，主合取范式：1。

(2)主析取范式：0,主合取范式：MovM,0

3設(shè)p:老大在撒謊，q:老二在撒謊，r:老三在撒流。本題即為求A=