離散數(shù)學

習題1

1.判斷下列語句是否命題。若是,請給出命題地真值。

(1)離散數(shù)學是計算機專業(yè)地必修課。

(2)2是無理數(shù)。

(3)我正在說謊話。

(4)今天天氣好熱呀！

(5)整數(shù)3能被2整除。

(6)下午開會嗎？

(7)三角形有三條邊，當且僅當5是素數(shù)。

(8)馬有四條腿。

(9)雪是白地當且僅當太陽從東方升起。

(10)9+2<10o

(11)如果1+1=2,則2+3=5。

(12)魯迅獲得過諾貝爾文學獎。

解答：(1)是命題,T(2)是命題,F。(3)不是命題。(4)不是命題。

(5)是命題,F。(6)不是命題。(7)是命題,T。(8)是命題,T。

(9)是命題,T。(10)是命題,T/F。(11)是命題,T。(12)是命題,F。

2.將下列命題符號化。

(1)太陽高照且氣溫不高。

(2)如果明天下雨，我就乘公交車上班。

(3)我買電腦,僅當我有錢。

(4)雖然天氣很好，老吳還是不來。

(5)王明不但學習好而且還有運動天賦。

(6)明天它在廣州，或在深圳。

(7)若兩個圓面積相等，則半徑相等，反之亦然。

(8)打印機既可作為輸入設(shè)備,又可作為輸出設(shè)備。

(9)只有我不復(fù)習功課，我才去看電影。

(10)如果a與b是奇數(shù)，則a+匕不是奇數(shù)。

解答：(1)設(shè)P:太陽高照;Q:氣溫不高。則命題可符號化為：PA

Q。

(2)設(shè)尸:明天下雨;Q:我乘公交車上班。則命題可符號化

漸設(shè)PT淡氣很好;Q:老吳來。則命題可符號化為：P

⑶設(shè)尸：策朗電腦建;：Q我蜜娥有典前典賊符勵傕鮑可符號他匆。：P

A12O

他)餃戶:IW忝畫面積相等劭：：嘀不匐竄蝴網(wǎng)|」俞腦顏挈脂化—。。

渤設(shè)他。打印機可作為輸入設(shè)備;Q:打印機可作為輸出設(shè)備。則命題可符號化

為：

以令9)設(shè)P：我復(fù)習功課;。：我去看電影。則命題可符號化為：Q-「匕

(10)設(shè)尸：。是奇數(shù)Q:b是奇數(shù)穴：a+6是奇數(shù)。則命題可符號化為：P

Q―-Ro

3.寫出下列命題公式地真值表。

⑴e&(&P)

1

第1章命題邏輯

⑵(R(當Q》Q

⑶(A&R

(4)(F>&R

解答：(1)

pC(PP)

00f0「%1

011111

100100

111110

(2)

PQ(PQ

00叫

01011

10001

11111

(3)

PQR(尸R

0000f⑵1

001011

010011

011011

100100

101101

110011

111011

(4)

PQR(PR

000-iao

00111

01010

01111

10001

10100

11010

11111

4.設(shè)P,Q,R,S地真值依次為1,0,1,0。試求下列命題地真值。

⑴人(QR)

⑵(A(川S?(但S(鳳S))

(3)(巧&)(v

RS)

2

離散數(shù)學

⑷(砂(@?(公尸)》(出S)

解答：(l)Av(Q<?>入(01)0111。

(2)(外(應(yīng)S)”((處8(心T))。(人(1/0)”((M0>\(00))

0(1B(10)O10。0。A

⑶(4&)(v5)=(4券(v0)=1°0。

(4)(RP))?v1S)o(10))?v0)

。('1(0in&('1B(?o0lol。A(1

5.構(gòu)造下列各命題地真值表,并指出下述命題中哪些是永真式？哪些是永假式？哪些是可

滿足式？

⑴(A0(P

⑵((9&)/??(外R)

(3)(G?W)(G?戰(zhàn)

(4)(A②QG

解答：(1)

PQ(P(救Q)

00-10111

011111

100100

111101

因此,(PfQ)g(戶=

。)是永真式。

⑵

PQR((P

000f1。[3]?月1(今K)

00111111

01010011

011I111I

10000110

10100111

11010010

11111111

因此,((P-。)人(Q-R))f(P-尺)是永真式。

⑶

GH(G代G

00-1加1(少110

0111100

1000110

1110000

因此,(GfH)A(GfH)一"G是永假式。

(4)

3

第1章命題邏輯

pQ（「Q

000-121

01011

10100

11011

因此，（P-。）一>。是可滿足式。

6.用基本等價公式證明下列等式。

（1）（3助（3R）Q（R00

（2）（4&）（AR）O分（@塔

⑶外（3R）o外3R）

（4）A（&>R）o（A&R

證明：（1）（A助R

0（砂助（&R）

。（人Q）R

O（R0）R

0（抄&R

⑵（外&）（外R）

0（萬③（砂R）

。步（&R）

。分（@/?）

⑶外（@>/?）

O出（&R）

O9（砂R）

O@gR）

<=>@>（3R）

（4）分（3R）

<=>?&R）

0（H&R

O（A0）R

0（人&R

7.求下列公式所對應(yīng)地合取范式與析取范式。

⑴火（火Q）

⑵（當0R

（3）（?。）（SR）

⑷（（艮0>人田

解答：（1）火（外。）4人R

（Q）（合取范式）

二（人因（氏Q）oRQ（析取范式）

（2）（A>0RO（VVROAV（析取范式）

PQ）（尸Q）R

4

離散數(shù)學

0（時助（&R）（合取范式）

⑶V。）（SR）o（PQ）（VR）O人@V

0（（AaAS）f（R@公）淅取范武）（SR）（合取范式）

（4）（（A33Ro（（A&2RO（R&R（析取范式）

0（萬助（&R）（合取范式）

8.求下列公式所對應(yīng)地主合取范式與主析取范式。

（1）@國。）

（2）外便（公P）

（3）vQ）（SR）

（4）（收為△/?一

解答：（l）0v（PQ）=（（入@S（2Q）O（PQA（v0（9Q）

0MAMAM（主合取范式）P

O（aP）（001Q）O（火Q）0OK0<=>/nn（主析取范式）

⑵外（R（公P））o。（人（vP））=（矽林（P（v

O1（萬（&P））。H9PQ尸））

o（R（&QA（0（的p?（R（9Q））

0（人③（人③（@為（@（人③出Q）

0（人0）（人0）（A0）（AQ）

rn^/n,vm（主析取范式）

O1（主合取范式）"

（3）（RQ）（SR）O氏@（WR）

0（步（@△一酸（SS））

A（&便式領(lǐng)保網(wǎng)（5黝（S處（A閃邇Q））

。（抄@炒助（炒&敝助（砂&敖S）

△（抄&修5）（。QRS）A（乃@RS）

△（9&位5）（。QR

A（H&R*&吊S）R5）

A（H8故助（步&月助（步（&尺勘（步&

A（抄&郎S）助

S）（HQW&故S）

△（步Q&S）

<=>（?&@的（抄&救助（砂8位*R&敖S）

A（朽QR5）A（B&R5）（。9RS）

A（RQ裁助（抄&月助（步。沿助（矽&RS）

△（9&R助（/&RS）

OMO（AMI（AMIOhMo（小MmM”小Mo小Mi/hMxxAMX）（AM

0010

AMoo"M）ioi（主合取范式）

0（八@*（A0R）

0（只@（政助0（A@瓜（SS））

5

第1章命題邏輯

<=>(人@氏0(人0瓜0(人@瓜5)

v(AaRS)

<=>(A@貝0(人@瓜S)(人@瓜5)

<=>"oiM恤MM"7(主析取范式)

011!

R

(4)(K&RO(R&RORQMow(主合取范式)

O(R(8③(@(@(。B(P

v(瓜(矽林(。0)初

0(人@網(wǎng)(A@悶(人@梅(我@R)

V(PQ7(PQV(PQR)

。機令機4物M加加機oW〃岫mA(主析取范式)

011

9.構(gòu)造以下推理地證明。

⑴前提vv

結(jié)論PPQ,(。R),R

(2)前提7P&R,P->S

結(jié)論：以Ss,

證明:(1)證明過程如下

1)R)P

2)QRT,1),E

3)RP

4)QT,2),3),1

5)9QP

6)PT,4),5),1

⑵證明過程如下

1)外SP

2)SP

3)PT,1),2),1

vQP

妙T,3),4),1

6)2?RP

7)RT,5),6),1

8)限ST,2),7),I

10.用附件前提法證明以下推理地正確性。

⑴前提：(4&(3R),RfP

結(jié)論：gP

(2)前提:g(G>R)Sv

結(jié)論：g(SR)P

證明：(1)由CP規(guī)則，只需證明：(外0(8R),RP。證明如下

分愿&(e?/?)P

2)(3①(VR)T,1),E

3)((A①段°QT,2),E

6

離散數(shù)學

4)2P(附加前提)

5)但蟲RT,3),4),1

6)(A&RT,5),E

7)apP

8)(A&PT,6),7),I

9)(&PT,8),E

10)(人vPT,9),E

11)P<2)T,10),E

12)0pCP,4),11)

(2)?由CP規(guī)則，只需證明：j（公R)SvP,QS

a/0,SvP,Q,SR。證明如下Re或只需證明

1)SP（附加前提）

2)vP

3)PSpT,1),2),1

4)今(e>R)P

5)@?RT,3),4),I

6)QP（附加前提）

7)RT,5),6),1

8)5RCP,1),7)

9)G?(SR)CP,6),8)

11.用反證法證明以下推理地正確性。

（1）前提：（入&R

結(jié)論：（R>vR）-X。R

V

（2）前提：AQ,QR,RA

結(jié)論：Ps

證明:（1）證明過程如下

1)（（外於（3R))p（附加前提）

2)（（V段（V/?))T,1),E

3)(G八(0/R)T,2),E

4)收玲QT,3),E

5)便&央P

6)(仄&T,5),E

7)RR)T,6),E

8）便（也@助（（艮aR))T,4),7),1

9)FT,8),E

（2）證明過程如下

1)（「）P（附加前提）

2)PT,1),E

3)外Qp

4)QT,2),3),1

5)2RP

7

第1章命題邏輯

6)RT,4),5),1

7)RSP

8)RT,7),I

9)用RT,6),8),1

10)FT,9),E

12.用構(gòu)造證明地方法證明以下推理地正確性。

(1)如果小張與小朱看電影，則小李也去。小吳不去看電影或者小張去看電影。小朱去

看電影。所以，當小吳去看電影時，小李也去。

(2)如果小王來，則校長與小李中恰有一人來。如果校長來，則小趙就不來。所以，如

果小趙來了,但小李沒有來，則小王也沒有來。

證明：(1)設(shè)P：d、張去看電影;。:小朱去看電影式:小李去看電影S:小

場點慧梏掾化為：樂Q^,RSvP,QSR。由CP規(guī)則，只需證明：PQR

§P,Q,SR。證明如下fAf

DSP(附加前提)

2)S尸P

3)PT,1),2),1

4)。P

5)AQT,3),4),1

6)ARP

7)RT,5),6),1

8)SRCP,1),7)

(2)設(shè)尸:小王來;Q:小李來;R:小趙來;S:校長來。則原題

Af護化器(25),5->RR人。尸。由CP規(guī)貝人只需證明

外(@時(0s),s->R，RQTp。由以下公式

(A(@v(QS汝(的豚(瓜。)地真值表，

P屯R6(3很0(@(S助(阿Q)

0000101010111001

0001100111111001

0010101010110111

0011100111000011

0100111100111000

0101100000111000

0110111100110000

0111100000000000

1000001010011001

1001100111111001

1010001010010011

1011