离散数学及应用 第3版 习题及答案

§1.5命题公式的推理演算

习题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.请对下面每个推理前提给出两个结论，使其中之一是有效的，而另一个不是有效的。

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

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

解(1)有效结论：prr,无效结论：rip,下面的真值表说明了这一点。

pqrpiqqTrpfrrfp

0001111

0011110

0101011

0111110

1000101

1010111

1101001

1111111

(2)有效结论：q/r,无效结论：p”,下面的真值表说明了这一点。

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

00010100

00100101

01010110

01100101

10010101

10100101

11011011

11101101

(3)有效结论：rf(pAq),无效结论：下面的真值表说明了这一点。

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

0001111

0011100

0100111

0111100

1001110

1011101

1100011

1111110

3.在下面各推理中没有给出结论。请对每个推理前提给出两个结论，使其中之一是有效

的，而另一个不是有效的。

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

(2)只要天气热，我就去游泳。我没去游泳。所以……

（3）除非天气热并且我有时间，我才去游泳。天气不热或我没有时间。所以

解

（1）有效结论：天气热。无效结论：天气不热。

（2）有效结论：天气不热。无效结论：天气热。

（3）有效结论：我不去游泳。无效结论：我去游泳。

4.用真值表法或等价演算法证明下列推理

(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规则

(2)pp规则

(3)q—rT规则，（1）（2）

(4)qP规则

(5)rT规则，(3),(4)

(6)rV5T规则，（5）

(2)解:

(1)p附加前提

(2)q->qP规则

(3)qT规则，(1),(2)

(4)—{qAr)P规则

(5)f7fE规则,(4)

(6)-irT规则，(3),(5)

(7)rP规则

(8)0T规则，(6),(7)

根据所学定理，有p—q，TqAr),r=>—。

(3)解:

(1)p一qP规则

(2)pCP规则

(3)qT规则，(1)(2)

(4)pf\qT规则，（2）（3）

（4）解：

(1)t/\rP规则

(2)tT规则，(1)

(3)s>tP规则

(4)ST规则，(2),(3)

(5)q—sP规则

(6)qT规则，(4),(5)

(7)qrPP规则

(8)pT规则，(6),(7)

(9)p^qT规则，(6),(8)

(5)解:

(1)PA<7p规则

(2)PT规则，(1)

(3)qT规则，(1)

(4)p—rP规则

(5)rT规则，(2)(4)

(6)q-sP规则

(7)sT规则，(3)(6)

(8)r/\sT规则，(5)(7)

(6)解:

(1)p^qP规则

(2)pT规则，(1)

(3)-npVrP规则

(4)rT规则，(2),(3)

(5)qT规则，(1)

(6)P规则

(7)ST规则,(5),(6)

(8)rv.vT规则，(4),(7)

(9)ff(rvs)T规则，(8)

(7)解:

(1)pt(q—r)P规则

(2)q—(p—r)E规则，(1)

(3)qP规则

(4)p—rT规则，(2),(3：)

(5)s—pp规则

(6)5—>rT规则，(4),(5)

(8)解：

(1)p附加前提

(2)p\/qT规则，（1）

(3)(〃vq)f(RAS)P规贝U

(4)rA5T规则,(2),(3)

(5)sT规则，（4）

(6)S7tT规则，（5）

(7)(5v>wP规则

(8)uT规则，（6）,（7）

根据所学定理，有(pvq)->(r/\s),(5v?)->M=>/7->wo

(9)解:

(1)rA-isp规则

(2)rT规则，（1）

(3)~\ST规则，（1）

(4)-irV(7P规则

(5)QT规则,(2)(4)

(6)P规则

(7)「PT规则，(5)(6)

（10）解：

(1)-i(rVs')CP规则

(2)-irA-isE规则，（1）

(3)-irT规则，（2）

(4)~~\ST规则，（2）

(5)P规则

规则，

(6)「qT(4)(5)

(7)p一『P规则

(8)「PT规则，（4）（5）

(9)-ipA-«qT规则，(6)(8)

(10)-i(pV<?)E规则，(9)

(11)(pV9)P规则

(12)1(pVq)A(pV<7)T规则，(10)(11)

(13)0E规则，(12)

6.用演绎推理法证明下列说法不可能同时成立。

(1)如果王平因病缺了许多课，那么他考试将不及格。

(2)如果王平考试不及格，则他没有学到知识.

(3)如果王平读了许多书，则他学到了许多知识。

(4)王平因病缺了许多课，而且在家读了许多书。

解设p：王平因病缺了许多课，q：王平考试将不及格，r：王平没有学到知识,

S：王平读了许多书，则上面的4种说法可以分别符号化为：

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

而这几个逻辑式子是相互矛盾的，即永假式0是它们的逻辑结论：

(1)piqp规则

(2)qTYp规则

(3)p—>rT规则,(1),(2)

(4)s——P规则

(5)rf-15E规则，(4)

(6)p-^—sT规则,(3),(5)

(7)p/\sP规则

(8)PT规则，(7)

(9)sT规则，(7)

(10)—\ST规则，(6),(8)

(11)sA-isT规则，(9),(10)

(12)0E规则，(11)

7.用演绎推理法证明下列推理过程：如果今天是星期六，我们就要去长城或故宫玩；如

果故宫游人太多，我们就不去故宫玩；今天是星期六；故宫游人太多。所以我们去长城玩。

解设p：今天是星期六，q：我们就要去长城