《离散数学》第一章习题参考答案

基础习题

1(1)是，简单命题

⑵是，简单命题

⑶是，复合命题

⑷不是

(5)不是

(6)是,复合命题

(7)是，简单命题

(8)不是

(9)不是

(10)是，简单命题

(11)是，复合命题

(12)是，复合命题

(13)是，复合命题

(14)不是

(15)是,简单命题

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

(2)p,其中p:乃是无理数。真值为1。

(3)pvq,其中p:2是素数，q:5是素数。真值为1。

(6)pAq,其中p:2是正数，q:-3是正数。真值为0。

(7)p,其中p:王健与魏钢是朋友。真值依实际情况而定，非。即1。

(10)p,其中p:圆的周长等于直径乘以不。真值为1。

(iDq-p,其中p:5是奇数，q:7是2的倍数。真值为1。

(12)q—p,其中p:4是奇数，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的倍数，q:8是4的倍数。真值为1。

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

(4)pAq,其中p:3是偶数，q:3是素数。真值为0。

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

4(l)pVQ,其中p:2是偶数，q:4是偶数。真值为1。

(2)pVq,其中p:5是奇数，q:2是奇数。真值为1。

⑶-ipV-iq,其中p:2是素数，q:6是偶数。真值为0。

(4)(pA-iQ)K(->pAQ),其中p:小丽能买一个盲盒，q:小丽能买一个拼图，依

据实际情况，真值为1当且仅当〃、q中只有一个真值为1。

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

实际情况，真值为1当且仅当p、中有一个真值为1。

5设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:实函数y=/(x)在/点可导，Q：实函数y=/(x)在/点连续。

真值为0。

(2)p—q,其中p:4是偶数，q:三角形有四个内角。真值为0。

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

7设2是正整数；中国有四大发明；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

主析取范式：网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设p:今年是2024年，q:明年是2025年，r:明年是2026年，

（1）推理正确，pir,p=r（假言推理规则），

（2）推理的形式结构为（pTq）/\q—p,真值表如下，非重言式，故推理不正

确。

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

00101

01110

10001

11111

⑶推理正确，p-r,「r=「p（拒取式规则）。

（4）推理的形式结构为（pTq）A「pT「q,真值表如下，非重言式，故推理不正

确。

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

0011111

0110110

1001000

1100100

（5）推理的形式结构为（p-（qV厂））Aprq,1（）1为其成假赋值，非重言式，故

推理不正确。

（6）推理正确，推理的形式结构为

前提per，-y>

结论f

证明①〃一厂前提引入规则

②（〃-「）△（「fp）①置换规则

③rfp②化简规则

④T前提引入规则

⑤f③④拒取式规则

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

结论：rA(/?->5)

证明：①pfs前提引入规则

②T前提引入规则

③r，①②拒取式规则

④p“前提引入规则

⑤q③④析取三段论规则

⑥g一尸前提引入规则

⑦「⑤⑥假言推理规则

①⑥合取引入规则

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

结论：qTr

证明：①4附加前提引入规则

②p前提引入规则

③〃->(4->(rAS))前提引入规则

④43(r/\s)②③假言推理规则

⑤…①④假言推理规则

@r⑤化简规则

由附加前提证明法证得推理是正确的。

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

结论：r

证明：①〃前提引入规则

@(5—>•r)v-/?前提引入规则

③①②析取三段论规则

④7否定结论引入规则

⑤f③④拒取式规则

@-irA—15④⑤合取引入规则

⑦-1(，vs)⑥置换规则

⑧T~s)->T〃vg)前提引入规则

⑨Tpvq)⑦⑧假言推理规则

⑩⑨置换规则

⑪力⑩化简规则

⑫〃八力①⑪合取引入规则

⑫得到了矛盾式，由归谬法证得推理是正确的。

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

结论：rv.v

证明：①〃前提引入规则

②p->(qf力前提引入规则

③gf广①②假言推理规则

®q前提引入规则

⑤「③④假言推理规则

⑥rvs⑤附加规则

15设p:今天我有空，q:我去博物馆玩，r:我去奥体公园玩,:博物馆人

多。

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

结论：r

证明：①p前提引入规则

②p->(qVr)前提引入规则

③qVr①②假言推理规则

@s前提引入规则

⑤s->「q前提引入规则

⑥④⑤假言推理规则

⑦r③⑥析取三段论规则

提升习题

1设Pi：陈思为大队长，qi：陈思为宣传委员，陈思为组织委员，P2：孙瑶

为大队长，q2：孙瑶为宣传委员，P3：王博为大队长。

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

1=>(p3AFDV(ip?Aqj②

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

①八②得1。「内Aq2Ap3AM④

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

最终得出：孙瑶为宣传委员，王博为大队长，陈思为组织委员。

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

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

3设p:老大在撒谎，q:老二在撒谎，r:老三在撒流。本题即为求A=