離散數(shù)學(xué)及應(yīng)用 第3版 習(xí)題及答案

§1.5命題公式的推理演算

習(xí)題1.5

1.用真值表方法判斷下列推理是否正確。

(1)p\zqnp

(2)—q/\r,rAp,q=p\/f

(3)―i(pA—1q),―\(jvF,-=>―p

(4)pT(qTr),pAq

(5)ffq,qTY,丫Tp=p\/q71r

(6)pfq,r/\s,-T^=>p/\s

解(1)推理不正確。

Pq-P〃vqp八q

00100

01110

10010

1I011

(2)推理正確。

pqr—Arr/\pP7f

000001

001101

010000

011000

100001

101111

110001

111011

(3)推理正確。

pqr-i(pA-iq)-iqVr->q-ip

00011ii

0011111

0101001

0111101

1000110

1010110

1101000

1111100

(4)推理不正確。

Pqrpt(qtr)pAq

00010

00110

01010

01110

10010

10110

11001

11111

(5)推理正確。

pqr「pTqqtrrtppVqVr

0000110

0010101

0101011

0111101

1001111

1011111

1101011

1111111

(6)推理不正確。

Pqrsp~qrAs-iqpAS

00001010

00011010

00101010

00111110

01001000

01011000

01101000

01111100

10000010

10010011

10100010

10110111

11001000

11011001

11101000

11111101

2.請對下面每個(gè)推理前提給出兩個(gè)結(jié)論，使其中之一是有效的，而另一個(gè)不是有效的。

(1)前提：pTq,qTr(2)前提：(〃Aq)fr,->r,q

(3)前提：pT(qTr),p,q

解(1)有效結(jié)論：prr,無效結(jié)論：rip,下面的真值表說明了這一點(diǎn)。

pqrpiqqTrpfrrfp

0001111

0011110

0101011

0111110

1000101

1010111

1101001

1111111

(2)有效結(jié)論：q/r,無效結(jié)論：p”,下面的真值表說明了這一點(diǎn)。

Pqr-irp八q(p△q)-rq八tp7r

00010100

00100101

01010110

01100101

10010101

10100101

11011011

11101101

(3)有效結(jié)論：rf(pAq),無效結(jié)論：下面的真值表說明了這一點(diǎn)。

pqrq->rpT(qTr)r—(，Aq)(p八一xq)3r

0001111

0011100

0100111

0111100

1001110

1011101

1100011

1111110

3.在下面各推理中沒有給出結(jié)論。請對每個(gè)推理前提給出兩個(gè)結(jié)論，使其中之一是有效

的，而另一個(gè)不是有效的。

(1)只有天氣熱，我才去游泳。我正在游泳。所以……

(2)只要天氣熱，我就去游泳。我沒去游泳。所以……

（3）除非天氣熱并且我有時(shí)間，我才去游泳。天氣不熱或我沒有時(shí)間。所以

解

（1）有效結(jié)論：天氣熱。無效結(jié)論：天氣不熱。

（2）有效結(jié)論：天氣不熱。無效結(jié)論：天氣熱。

（3）有效結(jié)論：我不去游泳。無效結(jié)論：我去游泳。

4.用真值表法或等價(jià)演算法證明下列推理

(1)—iAA―>B

⑵8nA-3

(3)—1(A―>B)A

(4)-i(A―>―iB

(5)(A->B)A(C->D)AAC->B/\D

(6)(A->B)八(C->Z))AvC->BYD

(7)(A-B)A(C-￡))A(AvC)nBv。

(8)(A->B)A(C->D)A(—iBv―iZ))―iAv—1C

證明

(1)(2)(3)(4)題都可以用下面的真值表。

AB-.AA->B-1(ATB)-iB

001101

011100

100011

110100

從而可以證出(1)(2)(3)(4)?

(5)[(A->B)A(C-D)]T[(AAC)-?(BAD)]

=r[(rAVB)A(rCVD)]V[r(AAC)V(BAD)]

=(AArB)V(CArD)V(rAV-QV(BAD)

=[(AA-B)V-A]V[(CA->D)V-C]V(BAD)

=(rBVrA)V(rCVrD)V(BAD)

=i(BAD)V(BAD)V(rAVrC)

(6)[(A-B)A(C—D)]一[(AVC)—(BVD)]

=r[(rAVB)A(rCVD)]V[r(AVC)V(BVD)]

=(AArB)V(CArD)V(rAAX：)V(BVD)

=[(AAiB)VB]V[(CArD)VD]V(rAArC)

=(AVB)V(CVD)V(->AA->C)

=BVDV(AVC)V->(AVC)

=1

(7)[(ATB)八(C->D)A(AVC)]-?(BVD)

=r[(rAVB)A(rCVD)A(AVC)JV(BVD)

=(AArB)V(CArD)V(rAArC)V(BVD)

=[(AA-B)VB]V[(CA-D)VD]V(->AA->C)

=(AVB)V(CVD)V(rA八rC)

=BVDV(AVC)Vr(AVC)

=1

(8)[(A-B)八(CTD)A(AVC)H(BVD)

=r[(rAVB)A(rCVD)八(rBV-D)]V(rAVrC)

=(AArB)V(CArD)V(BAD)V(->AV-Q

=[(AA-，B)V-nA]V[(CA-D)V--C]V(BAD)

=(rBVrA)V(rCVrD)V(BAD)

=->(BAD)V(BAD)V(rAVrC)

=1

5.用演繹推理法證明下列推理

(1)pT(qTr),p,q=r7s

(2)pTq,-^qAr),r=>—ip

(3)p—>q=>p—>(p八q)

(4)qTp,q—s,s—t,t/\r=p/\q

(5)p—>r,qTs,p/\qnes

(6)—>/?vr,—iq\/s,〃△q=>/—>(rvs)

(7)pT(qTr),sip,q=sTr

(8)(pvq)—>(rAS),(SYt)TUnpTU

(9)pf-q,f7q,rA—p

(10)p\/q,pfr,qfsnrvs

證明（1）解：

(1)〃T(4Tr)p規(guī)則

(2)pp規(guī)則

(3)q—rT規(guī)則，（1）（2）

(4)qP規(guī)則

(5)rT規(guī)則，(3),(4)

(6)rV5T規(guī)則，（5）

(2)解:

(1)p附加前提

(2)q->qP規(guī)則

(3)qT規(guī)則，(1),(2)

(4)—{qAr)P規(guī)則

(5)f7fE規(guī)則,(4)

(6)-irT規(guī)則，(3),(5)

(7)rP規(guī)則

(8)0T規(guī)則，(6),(7)

根據(jù)所學(xué)定理，有p—q，TqAr),r=>—。

(3)解:

(1)p一qP規(guī)則

(2)pCP規(guī)則

(3)qT規(guī)則，(1)(2)

(4)pf\qT規(guī)則，（2）（3）

（4）解：

(1)t/\rP規(guī)則

(2)tT規(guī)則，(1)

(3)s>tP規(guī)則

(4)ST規(guī)則，(2),(3)

(5)q—sP規(guī)則

(6)qT規(guī)則，(4),(5)

(7)qrPP規(guī)則

(8)pT規(guī)則，(6),(7)

(9)p^qT規(guī)則，(6),(8)

(5)解:

(1)PA<7p規(guī)則

(2)PT規(guī)則，(1)

(3)qT規(guī)則，(1)

(4)p—rP規(guī)則

(5)rT規(guī)則，(2)(4)

(6)q-sP規(guī)則

(7)sT規(guī)則，(3)(6)

(8)r/\sT規(guī)則，(5)(7)

(6)解:

(1)p^qP規(guī)則

(2)pT規(guī)則，(1)

(3)-npVrP規(guī)則

(4)rT規(guī)則，(2),(3)

(5)qT規(guī)則，(1)

(6)P規(guī)則

(7)ST規(guī)則,(5),(6)

(8)rv.vT規(guī)則，(4),(7)

(9)ff(rvs)T規(guī)則，(8)

(7)解:

(1)pt(q—r)P規(guī)則

(2)q—(p—r)E規(guī)則，(1)

(3)qP規(guī)則

(4)p—rT規(guī)則，(2),(3：)

(5)s—pp規(guī)則

(6)5—>rT規(guī)則，(4),(5)

(8)解：

(1)p附加前提

(2)p\/qT規(guī)則，（1）

(3)(〃vq)f(RAS)P規(guī)貝U

(4)rA5T規(guī)則,(2),(3)

(5)sT規(guī)則，（4）

(6)S7tT規(guī)則，（5）

(7)(5v>wP規(guī)則

(8)uT規(guī)則，（6）,（7）

根據(jù)所學(xué)定理，有(pvq)->(r/\s),(5v?)->M=>/7->wo

(9)解:

(1)rA-isp規(guī)則

(2)rT規(guī)則，（1）

(3)~\ST規(guī)則，（1）

(4)-irV(7P規(guī)則

(5)QT規(guī)則,(2)(4)

(6)P規(guī)則

(7)「PT規(guī)則，(5)(6)

（10）解：

(1)-i(rVs')CP規(guī)則

(2)-irA-isE規(guī)則，（1）

(3)-irT規(guī)則，（2）

(4)~~\ST規(guī)則，（2）

(5)P規(guī)則

規(guī)則，

(6)「qT(4)(5)

(7)p一『P規(guī)則

(8)「PT規(guī)則，（4）（5）

(9)-ipA-?qT規(guī)則，(6)(8)

(10)-i(pV<?)E規(guī)則，(9)

(11)(pV9)P規(guī)則

(12)1(pVq)A(pV<7)T規(guī)則，(10)(11)

(13)0E規(guī)則，(12)

6.用演繹推理法證明下列說法不可能同時(shí)成立。

(1)如果王平因病缺了許多課，那么他考試將不及格。

(2)如果王平考試不及格，則他沒有學(xué)到知識.

(3)如果王平讀了許多書，則他學(xué)到了許多知識。

(4)王平因病缺了許多課，而且在家讀了許多書。

解設(shè)p：王平因病缺了許多課，q：王平考試將不及格，r：王平?jīng)]有學(xué)到知識,

S：王平讀了許多書，則上面的4種說法可以分別符號化為：

pTq,qTr,5—>—,p/\s

而這幾個(gè)邏輯式子是相互矛盾的，即永假式0是它們的邏輯結(jié)論：

(1)piqp規(guī)則

(2)qTYp規(guī)則

(3)p—>rT規(guī)則,(1),(2)

(4)s——P規(guī)則

(5)rf-15E規(guī)則，(4)

(6)p-^—sT規(guī)則,(3),(5)

(7)p/\sP規(guī)則

(8)PT規(guī)則，(7)

(9)sT規(guī)則，(7)

(10)—\ST規(guī)則，(6),(8)

(11)sA-isT規(guī)則，(9),(10)

(12)0E規(guī)則，(11)

7.用演繹推理法證明下列推理過程：如果今天是星期六，我們就要去長城或故宮玩；如

果故宮游人太多，我們就不去故宮玩；今天是星期六；故宮游人太多。所以我們?nèi)ラL城玩。

解設(shè)p：今天是星期六，q：我們就要去長城