离散数学习题答案

《离散数学》习题选解

习题一

1.命题有：⑴、(2)、(3)、(6)、(7)、(10)、(11)、(12)、(13).

简洁命题有：⑴、(2)、(7)、(10)、(13).

真命题有：⑴、(2)、(3)、(10)、(11).

真值待定的命题有：(7)、(13)

3.(2)解：令后是无理数，则原命题可符号化为一，其否式为后是无理数，其

符号化为〃，〃的真值为0.

(4)解：令〃：Ini是整数，其否式为Ini不是整数，其可符号化f的真值为0.

4.(3)解：令〃：2是最小的素数，q：2是最小的自然数，则此命题可符号化为

其值为1.

(5)解：令p：4是素数，q：4是偶数，则此命题可符号化为力人丑，其值为0.

5.解：(4)令p：3是偶数，q：4是偶数，则此命题可符号化为其值为1.

(5)令p：3是素数，q：4是偶数，则此命题可符号化为「pvr，其值为0.

6.解：(2)令p：刘晓月只选学英语，q：刘晓月只选学日语，则此命题可符号化为pvq或

7.解：由于〃与9不能同时为真.

8.解：(5)令p：2<1,q：3<2,则此命题可符号化为rf其值为0.

(6)令〃：2<1,q：3<2,则此命题可符号化为4，其值为L

11.解：(1)令〃：2+2=4,q：地球是动的，则此命题可符号化为〃-F，其值为0.

(4)令〃：地球上有水，q：后是无理数，则此命题可符号化为7?-»“，其值为1.

12.解：(2)令p：2+2=4,q：3+3=6,则此命题可符号化为〃―p,其值为0.

(4)令p：2+2=4,q：3+3=6,则此命题可符号化为力—,其值为1.

13.解：(3)令p：今日是星期一，q：明天是星期二，则此命题可符号化为peg,其值

为1.(4)令p：今日是星期一，q：明天是星期三，则此命题可符号化为pf4,其值为

0.

14.解：(7)令p：他吃饭，q：他听音乐，则此命题可符号化为p/\q.

(9)令p：他乘班车上班，q:天下大雨，则此命题可符号化为pfq.

(11)令p：下雪，q：路滑，r：他迟到了，则此命题可符号化为〃入4—九

(12)令p：2是素数，q：4是素数，则此命题可符号化为「(0八q).

(13)令〃：2是素数，q：4是素数，则此命题可符号化为「(「(pvq)).

15.解：p,q,r的真值分别为1,1,0,于是有：

(1)(pcq)fro(l—1)-001-000,

(2)(r->(pAq))<->—、p<=>(0―>(1A1))<->―il1<->0<=>0>

(3)—>r—>(—i/?v—x7vr)<=>—0—>(—ilv—ilv0)ol—(0v0v0)=l—>0=0

(4)(〃AqA-1厂)((-v-->r)<^>(1A1A-0)((-Jv-1)->0)

o(1A1)c(0->0)o1c1o1,

16.解：由于pu>0,<7<=>0,rol,sol,所以

(1)〃v(qAr)o0\z(0A1)o0\/0o0,

(2)(/?<-^r)A(—><7v5)<=>(0<->1)A(—Ovl)o0A1o0,

(3)(-\pA—qAr)<->(pAq△―ir)(-0A—0A1)(0A0A—J)100>

(4)(―As)―>(pA—、q)(—ilA1)―>(0A―il)<=>001>

17.解：令p：乃是无理数，q：3是无理数，r：&是无理数，/：6能被2整除，

w：6能被4整除，〃，4，r/,故的值分别为1,0,1,1,0,则此题可符号化为

/?△(4fr)△(卬-f),其值为1人(0-1)人(。-1)01八1八101，因此此论述为真.

18.解：令p：小王会唱歌，q：小李会跳舞，则此题可符号化为

(r?v-1q)A-i(/?->q)由题设条件知(r7v-><7)A一><7)。1，

又(一i〃v—iq)A—</?—>q)o(—1〃v—i^)Avg)o(—>〃v—>q)A(/?A—>q)

O(R?A/?A-i<?)v(/?A—,<7Arq)。0d(〃A-i<?)o〃A—><7o1,所以p,q的值分别

为1,0,即当小王会唱歌而小李不会跳舞时，就满足题目的要求.

19.解：(5)由于原式共有3个不同的变元p,q,r,故其真值表为：

Om0vmxvm2,所以原式的成真赋值为00,01,11.

注：此题也可用其值表法来做.

21.解：(2)(―v〃)△(〃->/=(-iq\/r)((〃△]〃)v-iqvr)A

(—i/?v^v(rA—)r))<=>(pv7vr)A(-77v—\qvr)A(—/?vvr)A(-y?v(7v—ir)

AM6AM4AM5<=>M2AM4AAM)，所以原式的成假赋值为010,100,101,

110.

(3)(p-4)AVp)o(―v4)A(―/7V—1厂Vp)<=>(-ipVA1<»

-1/7v(7<=>—)/?vq(rA-ir)<=>(—)〃vvr)A(~I〃VV—ir)<=>M4AA/5

所以原式的成假赋值为100,10L

注：此题也可用真值表法来做.

22.解：由于T”~>4人〃)。0，所以f4八〃)△-IVOOA—1厂00，故

fqAp)人为冲突式，它没有成真赋值，其全部23=8个赋值全为成假赋值.

23.解：由于〃Aq—>〃o1,所以((〃Aq)->〃)vr=lvr=l,故((〃人q)—>〃)vr

为重言式，它没有成假赋值，其全部23=8个赋值全为成真赋值.

24.解：由于(pf(pvq))A((pAq)-p)O1,所以pf(pvq)=1且(pAq)-p

=1,即pf(pvq)和(pAq)fp均为重言式.

25.解：由于(一(P—4)人q)v(-<rvp)Ap)<=>0,所以-<P-乡)人400且

vp)八p=。,即它们都是冲突式.

26.解：由于?一>(pvq)=1,—</?fq)/\400,所以

(pf(pvq))A(-<p-»q)Aq)ol/\0o0.故

(pT(PVq))AIp-q)八q)为冲突式，

交(〃-»(〃vg))v(4〃-»q)Aq)olvOol,

所以(〃-»(〃V(7))V(♦〃-»q)A4)为重言式.

27.证明：若A/\8ol,贝1JA0L80I,即均为重言式，反之若Aoi,Bol,

则即AAB为重言式.

28.解：AABOO,则有下列三种情形：(1)Ao0,8=0,(2)Ao0,8=1,(3)

A=1,8=0,因此由AA3是冲突式，不能得出A与5都是冲突式的结论.

29.证明：若AvboO,则Ao0,B00,即A,6均为冲突式，若A=0,B=0,则

AvBoOvOoO,即AvB为冲突式.

32.解：若AvBol,则有下列三种情形：(1)A=l,B=0,(2)A=0,B=l,(3)

(2)Aoi,8=1,因此由Av3为重言式，不能得出A与3都是重言式的结论.

习题二

1.解：公式A与8共含有p,q两个变元，故它们的真值表为

\pqfP—q"△F「(AA6)-iAA-\B

0011000

0101000

1()10100

1101000

所以-1(AvB)<=>—iAA—.

3.解：(2)所以此式为重言式.

(3)原式一1(〃vq)v(/?Ar)<=>(—1〃A—iq)v(〃Ar)o(—>〃△—A(rV—>r))V

(p八(qY「q)八r)

o(—f)A—tqAr)v(—i〃A—><7Ar)v(/?Ar)v(/?A—>qAr)

mm

omx7mo7m77s=ovm,vvm7,所以此式为非重言式的可满足式，其成

真赋殖为000,001,101,111.

注：此题可用真值表法求出成真赋值和成假赋值.

4.证明：(3)―>(夕—q)=T(p-q)△(4­〃))=r(p-q)V—>(乡—0)=

Tfvq)v—!(->"v/?)=(/?A1q)v(q△—>/?)=(/?v(q△—>/?))A(~>qv(q△—>/?))

=(7?vq)△(pv—/?)A(qv-iq)A(—,/?v—>q)<=>(pAA1A1ATpAq)=

0(pvq)A-i(p/\q)

(4)(/?A—>q)v(—i/?Aq)=(pv(—>pAq))A(—v(—>pAq))=

(/7v-i/?)A(pv^)A(rv-y7)A(—igvq)ol/\(pvq)人TpAq)A1o

(pyq、八Tp八q)

5.解：(2)—4)人<7人厂=T—>〃vq)AqAr=〃A—人gAr=0,所以此式的

主析取范式为o,它没有成真赋值...........................

(3)(pvAr))—>(/?v<7vr)—</?v(<7Ar))v(pv<yvr)<=>

1

=1EU

(1)(->pAF)v(fv/?)<=>(~>pv-i^vp)A(Fv-i^vp)o1△(/?v7)o

所以

’3，

6.解：(1)—(q—>p)A—tp<^>—1(—1^v-^p)A—ippA(7A—tp0<»

MOAM,AM2AM3.所以此式为冲突式，其全部2?=4个赋值都是成假赋值.

(2)(pAt/)vvr)=(pvv厂)A(4r)o1A(「〃7q7co

「p\/q7roMA，所以此长的成假赋超为100.

(3)(〃-»(〃vq))\/〃=(r?vpv/vrol，所以此式为重言式，所以此式的主合取

范式为1,它没有成假赋值.

7.解：(1)(pAq)V〃O(/?A9A(〃v—ir))v((pv「p)/\(qv—ig)A〃)O

(pAqAr)\z(p△q八—ir)v(pAr)v(pA—Ar)v一pAAr)v(-1PA-^qAr)<»

vv"芍vm5vm3vm,o〃i]\z"%vm5v/n6vm7<=>MoAM2AM4.

(2)(pf/八(4—>〃)o(—pv^F)A(Mvr)<=>(­)pA(rvr))v

(qA(—)qvr))o(-1/7A-14)v(-1PAr)v(^rA「q)v(^rAr)<=>((-ipA「4)A(rv—)r))v

(「〃A((7v—it/)Ar)v((〃v—ip)△4Ar)=(—ipA—iqAr)v(「〃A—iqA-nr)v

m

(—ipAAr)v(—ipA—iQAr)v(pAr)v—p△q△r)=相]7mo7m37\vm7v

0m0v根1v根3Vm7=M2AM4AM5AM6.

8.解：(1)(〃Aq)fiqv4ol.所以此式的主合取范式为1,

它的主析取范式为"％v㈣vm2v7%.

(2)(pc/—>〃<=>((〃-t7)A(q->〃))—厂o—A(—iqv/7))vr

<=>(pA7)v(1/?A^)vr<=>(pA7)v((「pvr)Avr))<=>

(/?v((—)/?vr)Avr)))A(—v((「pvr)Avr)))o(/?v—1/?vr)A(pv^rvr)A

(—I17v—ipvr)A(-it/v(yvr)<=>(pv^vr)A(-1〃vfvr)<=>A/oAM6<=>

/%]vm2vvm4v/n5v/n7.

(3)—i(rT〃)△〃A4=rA-np△〃Aqo0<=>Af0AA/,AM?AM3AM4A

M5AM6AM7•所以它的主析取范式为0,主合取范式为

M()AA/,AM2AM3AA/4AM5AMsA%.

9.解:(1)由于原式共有3不不同的变元〃M",故其真值表为：

Pqr-p-n/?Ar(〃vq)v(f>Ar)

0001000

0011011

0101101

0111111

1000101

1010101

1100101

1110101

(2)(1)由于原式共有2个不同的变元p，d故其真值表为:

\pq

fplqper(〃一>1)—(〃—r/)

00100

010111

101011

1110100

所以它的主析取范式为叫

10.解：(1)由于原式共有3个不同的变元〃4人故其真值表为:

Pqr(pAi?)vr

00000

00101

01000

10000

10101

11011

11111

01101

⑶由于原式共有2个不同的变元故其真值表为:

pqqTfTq—f)->(q-->/?)△-ip

001100

011100

100100

110010

所以此式为冲突式，它的主合取范式为八M,AV,,它的主析取范式为0.

(1)由于原式共有3个不同的3乏元p,q,r,故其真值表为：

Pqr［八q(pvfy)Ar

00000

00100

01010

01111

10010

10111

11010

11111

所以它的主方斤取范式为/

n3vm5vm-；,它的主合取范式为

M()AM,AM2AM4AMb.

12.解：A而主合取范式为％入”2人〃4人加5人知6,它的主析取范式为moV加3V〃％•

13.解：A的主合取范式为人/3人“4人而7，它前主析取范式为%Vm|vm5Vm6.

14.解：Aoi,所以它的主合取范式为1.

注：的主析取范式为

Am0vw,­••vw.

14.解：(1)(p一q)-ipvq)vr<=>(〃△

((-ipVp)AqV—yq)Ar)<=>(pA—A—if)v(pAfAr)V(—)/?AAr)VJpA-1QAr)

v(pAr)v(pA-iqAr)<=>m4v/n5vm3v//2jvm7vm5<=>加］v机3vvm5vm7

oM°AM2AM6.

qt(pTr)o-ip\/-iq7roM69

所以(pTq)Tr与qT(p->r)不等值.

「八fQ叫】

(2)—i(pAg)=「pv—140M3,Tpyq)QpQMM2M3,所以

-<(P△4)与一>(〃vq)不等值.

16.解：(1)p—>(g-r)=「pv—尸=加6，Tp八公7Y=~P7f7Y=MG，

所以pT(qTr)oTpA<7)vr.

(2)(p—q)—ro—»(-npv^r)vr<=>(pA—iq)vr<=>(pA—A(—irvr))v

((—ipvp)A(qv—iq)Ar)<=>(pA—yqAT)V(pA—)qAr)vJpAAr)v(「pArqAr)

、

v(pA(7Ar)v(pA—iqAr)<=>m4vm5vm3v机1vm7V/n5om7mm4vm5vm7

oA/oAA/2AA76,pT(qfr)o—^pv—\qvr<=>M6.

所以(pfqjf-与pf①一>r)不等值.

17.解：(1)原式<=>—i(-npvq—(qAr))<=>pA-\qc(q人r))

<=>〃AT(qf(gAr))A((q△r)-q))o〃A—I((—K/v(qAr))A(—)(qAr)vq))

=〃A((qATqAr))v((^rAr)A—«q)).

(2)原式o(〃v—«r)A(qA—1〃).

(3)原式o(pT(q—r))A((ty<->r)-»p)<=>(「〃v((qTr)A(r-><7)))

A(T03〃)A(rfq))vp)

O(—ipv((—i夕vr)A(—)rv4)))A(—1((—iqvr)A(—)rvq))v〃)o(「〃vfvr)A

(—ipv-^rvq)△((gA—ir)v(rA7)vp).

18.解：(1)宣式.

(2)原式<=>(p'r)A(〃—p)A^<=>vr)A(—«rvp)/\q

<=>—1(/7A—ir)A—i(rA—ip)Aq.

(3)原式<=>「pv(qAr)vp<=>1<=>—<〃八可)或原式=->(9八->4)或原式T-Af*)

或原式0Tp4—1(^AT)A-ip),

19.解：(1)庸式―i(-1(-\pv-\Cj)v—ir).

(2)原式o(「〃v(4A「〃))A<7Ar<=>(—tpA(7Ar)v(「〃八q/\r)=

-^pAr<=>—i(z^vfv—ir).

(3)原式<=>(r?v—iqvr).

20.解：(1)原式u>―i(―\pv—\(j)\zF<^>(p—>—\(j)―>〃<=>q—>―p)—>r.

(2)原式<=>—1(―kp->—\Cj)v—\K)―((p->-14)一>-)r)—i(r—>-i(p—>-[q)).

(3)原式O(p/\4—r)八"-〃八/<=>—!(—1(〃八4'fp八40

―i((pAq->r)—>—i(r—>pAq))<=>―i((—1(-pv―q)—>r)—>―I(F—>—1(―ipv—iq)))

<=>—)((Tp-——―M))))・

21.证明：(1)pT<7<=>Tp八q)<=>-i((7八〃)=qTp.

〃J夕<=>—i(pv<7)<=>—i(qvp)<=>qJ〃.

(2)〃T(qTr)0-1(〃八(4T6)<=>-i(pA-I(^Ar))<=>-ipvAr)

o(「〃A((yv—1(7)A(rv-ir))v((〃v「〃)A<7Ar)<=>(—>pA(7Ar)vA<7A—ir)v

(—)〃A—iqAr)v(「〃A「qA—)r)v(/?Ar)v(「〃A<7Ar)<=>

。、7

m37nl”mxvmvm7vv7mlymoAf4AA/5AA/6.

而(pT9)Tro—)(—!(/?A△r)=(pA9)v—«尸=(p八qA(rv—(r))v((pv「p)

A((7v—1^)A—)r)o(〃AgAr)\/(〃AqA—)r)v(〃AqA—)r)v(pA—qA—)r)v

。=

(「〃A4A—)r)v(—pA—iqA—ir)=m77m67m67mA7m2ym

movvm4vJ%vmi<=>Al,AAAf5.

所以〃f(qTr)与(pTq)T〃不等值：

〃J(qJr)<=>-i(pvTqvr))oA(<7vr)<=>(—)〃A(7)vAr)<=>

(—)pA(rv—ir))v(-77A((yv「q)Ar)<=>(「pAAr)v(—/7A—)r)v

AAr)V(—1/7A—1〃△r)=m3V加2Vm3V//=Vm2V机3・

而(pJq)J〃<=>—>(—i(pvq)vr)<=>(pv<7)A—ir<=>(pA—ir)v(q八t)o

(〃A(4v—it/)A—ir)vdpv〃)A4A—)r)=(〃八gA—)r)v(pA—iqA-ir)v

(「〃AqA—)r)v(〃AqA—ir)0m6Vm4V根2V根60m2Vm4v.

所以pJ(qJr)与(pIq)J7不等值.

22.解：⑴pTq的真值表为

pqpt

q

27.解：状况一o-np/\r△〃，状况二0P1〃，状况三u>r?A<7△八

状况四OpAqA—1八贝1!

(a)F<=>mjvm3vm4vm6<x>A/oAM2AM5AM1.

(b)由(a)知/o(pvqvr)△(pvfvr)A(—v(yv—ir)AJpv—\qv—)r)

o—1(—A—\qA—)r)A-T(—ipA(7A—»r)A—i(pA—\qAr)A—i(pAAr).或先把化简为

F<=>(「pAT)v(pA—.r)<=>(/?vr)A(—)pv—«r)oTf八—»r)A—i(pAr).

注：厂还有其他的等价形式.

(c)由(b)可知/<=>(〃v〃)人(—ipv—ir)。(—>p—>r)A(r—>—ip)<=>—ip<-»〃或

Fo-T(〃<->〃)・

注：尸还有其他的等价形式.

29.解：令p：李强为生活委员，q：王小红为班长，r：丁金生为班长，s：王小红为生活

委员，A李强为班长，w：王小红为学习委员，则有：

甲说对一半=(「〃△<?)v(pA—>4)O1,

乙说对一半<=>(rAr)v(―ir八s)o1,

丙说对一半o(ZA—iU)v(—itAM)o1,

由于每人不能兼任，所以有：p/\f<=>0,$△〃<=>O,q/\s=O,4A

gA〃<=>0,PASO。,因此((-ipA<7)v(pA-1/)A((rA—«5)V(—.rAS))A

((fA—iw)v(—if△〃))o1,而((-ip△q)v(p△—iq))A((rAr)v(-irAS))A

((rA-1U)V(TA〃))

<=>(—1〃AArA—ISArA—!〃)V(—1〃AArA—iSA—i/AU)

(「〃八一iFASA/A—iM)V(—ipAqAf△SA-itA〃)V(〃AfAVA—iSA/A—1〃)

(〃AfATA—kVA—iZAW)V(/7AfAA5A/A—1W)V(/?AfA—)rA5A—irAW)

<^>0v0v0v0v0v(72A—1i7ATA—k?A—i/AW)vOvO<^>〃A—i,ATA—kVA—AW所

以p/\F/\r/\7八T八〃ol,即p为1,q%0,r为1,，为0,〃为1,因此李强为

生活委员，丁金生为班长，王小红为学习委员.

30.解：令赵去，q：钱去，r：李去，s：周去，，：孙去，则条件LA、opfq.

条件2：A2<=>—1(—>尸△—>s)<=>厂vs,条件3：4=(夕A—if)v(―△，),条件4：A4<=>

(厂Af)v(fAT),条件5：4osfp/\q.因此有：全部条件Ao(p-4)八

(rvs)A((qA—it)v(—iqA/))A((r4f)7(—)rA—it))A(s—>p八q)o

(—ipvty)A(rvs)A((qA-)，)v(—At))A((rAf)v(—irA—it))A(—>SV(〃Aq))=

((~ffA(rvs))v(^A(rvs)))A((qA—it)v(—At))A((rAR)v(—)rA—it))A

(—ISV(pAq))O((—«pAr)V(」p△s)V(4Ar)V(4AS))A((^FAT)V-qA/))A

((rAf)V(—irAT))A(—iSV(pAg))O((—ipArA4A—if)V(—ipATAf△/)V(—pA5AT)

V(—i/?A5A—yqA力)VgA〃△q八一if)VArA—A，)\/(qAS/\4A—if)VA5A—\QA/))A

((rAZ)V(—ifA—iZ))A(—iSv(pAg))

OdpATA^A—ifAfAZ)V(—'PATA^A—iZA—ifA—if)V(力ATAfAfATAZ)V

(—ipATAFA/A—ifAT)V(f7A5A^A—I^ATAOV(~ip△S△4AT八—ifAT)V

(—ipA5A—iqA/AFAZ)V(~ipA5A-i,AZA—irA—if)V(^ATA^A—iZArAf)V

V((/ArA^A—i/A—irA—1，)V(qASA4A_1，AVA。V(4ASAqA—ifA—>rA—if))

A(—kVV(pA</))<=>

(「〃△SA4A-itA—irA—ifA—15)V(「〃ASAA—itA—)r△—it△〃A幻V

(qA〃A4A—i。AA—i/A—15)"(qAVAqA—i，A—)rA—AApA<7)V

V((7A5A<7A—iZA—)rA—ifA—1S)VA5AA—iZA—)rA—A/?A</)V(/7ArAfA/ArAr)

<=>(/7A^A5A—ifA—if)V(—i/?ATA-iQAArA/A—>5)<»1,所以p为1,q为1,一为

0,s为1,，为0,或者〃为0,q为。,r为1,s为0,，为1。因此赵、钱、周去或者孙、

李去.

注：在计算过程中，多次用到A/\「4o0.

习题三

6.解：(1)令〃：今日是星期一，qz明天是星期三，则

前提：piq,p

结论：q

推理的弦式结构：(PTq)八PTq

等值演算法：(PTq)八PTq=(Jp7q)p)Tq=Tp八公7qo

—p7f7qQ1,由定理3.1知此推也正就

主析取范式法：(pTq)八pTq=(Tr〃vty)v「〃)v4o(〃A—it?)7rp7q

<=>(/?Ar)V(—ipA(^Vr))V((pV—1/?)△q)o(P△f)V(—1/7A^F)V(—1/?A—19)V

A4)v(p△乡vm,vvvm<=>由定理3.1

(—ip)omQ3m°vvvm3<=>1,

知此推理正确.

真值表法:

Pq(〃一>〃)Apq

0000

0101

1000

1111

所以不会消灭前提的合取式为真而结论为假的状况，因此推理正确.

(3)令〃：今日是星期一，q：明天是星期三，则

前提：pTq,—yq

结论：—

推理的形式结构：(.一乡)A「乡一>-ip

等值演算法：(P-，(j)A―\Q—>-\p(—\pVq)A—\C[—>—\p<=>_i(―\pA―\Q)V—\p<=>

P7q7「PO1,因此推理正确.

圭析取范热法：(pTq)八fv4)△F->「〃=T(「Pv(y)A

—iq)V—ipO(〃A—1<7)V((〃V—ip)A^)V(—tpA(t7V—It7))<=>(/?A—14)V(〃A/V

(—ipAV(—ip△4)V(—ipA—iq)=根2Vm3V根]vm]v相00根0VV根2V根3

O1,因此推理正确.

直接构造推理证明的方法.

证明：①pfq前提引入

②F前提引入

③力①@拒取式

真值表法：它们的真值表为:

\pq(〃-“)A-i"

0011

01

，0(1)

00

00

所以不会消灭前提的合取式为真而结论为假的状况，因此推理正确.

(4)令〃：今日是星期一，q：明天是星期二，则

前提：pfq,—p

结论：f

推理的形式结构：

等值演算法：(〃一>g)A「〃一>=->((->/?vq)人r，)vO(〃A-><7)v

pvp,所以当p为0,4为1舟，原式为0,因此(〃->q)A-lp->-1<7不是重言式，由

定理3.1知此推理不正确.

主析取范式法：(〃一>q)△->〃一>—1<7o(pA—><7)v〃V—ov(pA(<7v-i<7))

v((/?v—i〃)A—><7)0m2v(pA<y)v(〃△—>g)v(/?A—iq)v(—>/?A->q)/n2v/w3v

m2v/n,vm0<x>m0vw,vmy,因此(p-q)Af?——不是重言式，由定理3.1知此

推理不正确.

真值表返们的真值表为：

0q(〃-“)Aff

bo11

p1

10

『001

1100

所以会消灭前提的合取式为真而结论为假的状况，因此推理不正确.

(6)令〃：今日是星期一，q：明天是星期三，则

前提：〃一<7，

结论：一q

推理的形式结构：―

等值演算法：

(/?<-><7)A—1〃—>—uy

O(((〃—>^)A(^r—>p))A—i〃)—>—><7O—>((—!/?vq)A(—1<7v/7)A—i/?)v—1(7o

(/?A—1<7)v(—>/?Av/?v—><7o(/?A—><7)v((—,/?v〃)A(〃vq))v—><yo(p八一1q)

v/?v<7v-xy<=>1,由定理3.1知而推理定确.

主析取范式法：(〃<-><7)A—1/7hqo(〃△—v(―>/?Avp\/fom27m、

v(pA(<yv—i^))v((pv->p)A—<q)<=>m2v//v(〃Aq)(〃A—ig)(〃A—iq)(—A—>q)

om,v/Tijvm3vm,vm,vm0<=>m0v/?7(vm7vm3o1,由定理3.1知此推理正确.

真值袤法：它们的真值表为:

\pq(pCq)Ar

001i

0100

100i

11>00

所以不会消灭前提的合取式为真而结论为假的状况，因此推理正确.

直接构造推理证明的方法.

证明：①pcq前提引入

②(pfq)A(q-p)①置换规章

③qfp②化简规章

@-p前提引入

⑤—③④拒取式

9.证明：令p：a是奇数，q：。能被2整除，r：。是偶数，则

前提：p—rTq

结论：r―>-'P

推理的形式结构：(/?->->^)A(r(r->->p)

证法一(附加前提的证法)：

①p—前提引入

②rTq前提引入

③r附加前提引入

@q②③假言推理

⑤M①@拒取式

证法二(直接构造推理证明的方法)

①前提引入

②riq前提引入

③(p--><7)A(r->q)①②合取引入

@(pA(r-><7)A(^V-,^)③置换规章

⑤-ip\z—④破坏性二难

⑥rfT?④置换规章

证法三(主析取范式法)：

(P-7)A(r-4)—(rT—>p)

<=>—.((-ipvA(rv-14))v(->rv—>/?)<=>(pA^r)v(rA[q)v->rV->/?<=>(/?AA

(rv—>r))v((/?v—p)ATA—>4)v((/?v->p)Av—><7)A—,r)v(—i。人(qv—>q)A(rv—ir))

<=^>(/?A^Ar)v(/?A^A—,r)v(/?A—>qAr)v(—>/?A—Ar)v(—ipAq人—>r)v

(—ipA-iqA—>r)v(pAA-nr)v(/?A「qA—>r)v(—AqAr)v(—>pA<7A—>r)v

V

(~>PAAr)V(~>pA-1^A—)r)=加7V人V加6Vm2V/«2V加。V1%

v飞v叫vgv叫Om0vzn,vm->vm3vm4vm5vZM67m1o1,由定理3.1知

此推理正确."

证法四(真值表法)：由于(p->->q)A(r-><7)-»(r->r2)共含有3个不同的变元p,q,r,

故其真值表为:____________________________

Pqr(pf—q)A(尸一>“)1—r?

00011

00101

01011

01111

10011

10111

11001

11100

所以不会消灭前提的合取式为真而结论为假的状况，因此推理正确.

10.证明：令〃：。力两数之积是负数，q：a<0,r：b<0,贝!I

前提：pf(f八(q八T),「p

结论：一\(iA―>r

推理的形式结构：(pT(—14Ar)VA-)r))AW—19Af

证法一(真值表法)：由于(pf(-i4Ar)v(q/\-ir))A-np--14A-1r共含有3个不同的变

元p,q,r,故其真值表为:________________________

Pqr(〃―(一i"/\r)v(4Af—it?A—

00011

00110

01010

01101

10010

10100

11000

11100

所以会消灭前提的合取式为真而结论为假的状况，因此推理不正确.

证法二(主析取范式法)

(p—»(―i<7Ar)vA—ir))A—>—1<7A—0—1((—>/?v(—><7Ar)vA—>r))A—7?)

v(—A—ir)O(pA(<7v—.r)v(—vr))vpv(—,<7A—>r)O(((〃Aq)v(/?A—,r))A

(—vr))vpv(—1<7A—.r)o(/?A<7A—wy)v(〃AqAr)v(/?A—.rA—,(7)v(pA—>rAr)

v/?v(—14A—ir)=(p△r)v(，入一>4A—>r)v(pA(4V—>4)△(，V—>r))V((/?v—>/?)

A(—14A—>r))<=>(/?AAr)v(/?A7A—>r)v(。入r)v(/?△4八—>r)v(/?A—><7Ar)

v(/?A-yqA—ir)v(/?A—1<7A—,r)v(—1PAFA—>r)<=>啊v/M4vm7v/n6v/M5

vm4vm4v/M0om。vm4Vm5vm6vm7<=>M,AM2AM3,因此此式不是重言式，

由定理3.1知此推理不正确.

11.证明：①〃前提引入

②「pvq前提引入

③q①②析取三段论

④)r前提引入

⑤「③④析取三段论

⑥rfs前提引入

⑦s⑤⑥假言推理

12.证明：①附加前提引入

②〃①化简规章

③q①化简规章

⑥pT(qTr)前提引入

⑤4—厂②④假言推理

⑥r③⑤假言推理

⑦qT(rTs)前提引入

⑧rfs③⑦假言推理

⑨s©©假言推理

13.证法1(等值演算法)：(1)关于结论1的推理的形式结构：(TpTq”q'MP'q)

A(r->5)->r,关于结论2的推理的形式结构：(T〃fq)八q)八(pvq)

A(r->5)->5,关于结论3的推理的形式结构：>4)Aq)A(pvq)

A(rfs)—>rvs,

由于(一</?fq)△q)△(pvq)△(r-s)=(-<—,/?v4)△q)△(7?vq)△(—,rv5)

=Aq)A(pvq)A(-nrvs)=()△(/?vq)s)=0,所以有：

(—i(p-4)△4)△(pvq)△(r-s)-ro—{T(PTq)八q)八'q)

A(r5))vr<=>—10vr<=>1,

同理可得：(一<;?—q)Aq)A(pvq)A(r—s)-so1,

(—(P->q)人4)入(Pvq)A(r—>5)—>rv5<=>1,因此由这些前提推出结论1、

结论2、结论3的推理都是正确的.