離散數(shù)學(xué)課后習(xí)題答案一

§1.1命題和邏輯連接詞

習(xí)題1.1

1.下列哪些語句是命題，在是命題的語句中，哪些是真命題，哪些是假命題，哪些命題的

真值現(xiàn)在還不知道？

(1)中國有四大發(fā)明。(2)你喜歡計算機(jī)嗎？

(3)地球上海洋的面積比陸地的面積大。(4)請回答這個問題！

⑸2+3=6。(6)x+7<10。

(7)園的面積等于半徑的平方乘以圓周率。(8)只有6是偶數(shù),3才能是2的倍數(shù)。

(9)若無=>,則x+z=y+z。(10)外星人是不存在的。

(11)2020年元旦下大雪。(12)如果1+1=3,則血就不是紅的。

解是真命題的有：(1)、(3)、(7)、(9)、(12)；是假命題的有：(5)、(8)；是命題

但真值現(xiàn)在不知道的有：(10)、(11);不是命題的有：(2)、(4)、(6)。

2.令P、4為如下簡單命題：P：氣溫在零度以下。q：正在下雪。用P、4和邏輯聯(lián)

接詞符號化下列復(fù)合命題。

(1)氣溫在零度以下且正在下雪。

(2)氣溫在零度以下，但不在下雪。

(3)氣溫不在零度以下，也不在下雪。

(4)也許在下雪，也許氣溫在零度以下，也許既下雪氣溫又在零度以下。

(5)若氣溫在零度以下，那一定在下雪。

(6)也許氣溫在零度以下，也許在下雪，但如果氣溫在零度以上就不下雪。

(7)氣溫在零度以下是下雪的充分必要條件。

解(1)。八4；(2)夕人14；(3)八F；(4)Pvq；

(5)PTq；(6)-rq)；(7)pcq.

3.令原子命題P：你的車速超過每小時120公里，q：你接到一張超速罰款單，用P、q

和邏輯聯(lián)接詞符號化卜列復(fù)合命題。

(1)你的車速沒有超過每小時120公里。

(2)你的車速超過了每小時120公里，但沒接到超速罰款單。

(3)你的車速若超過了每小時120公里，將接到一張超速罰款單。

(4)你的車速不超過每小時?120公里，就不會接到超速罰款單。

(5)你接到一張超速罰款單，但你的車速沒超過每小時120公里。

(6)只要你接到一張超速罰款單，你的車速就肯定超過了每小時120公里。

解(1)rp;(2)P八「q;(3)p—q；(4)ff；

(5)q人力；(6)qTP。

4.判斷下列各蘊(yùn)涵式是真是假。

(1)若1+1=2,則2+2=4。T(2)若1+1=2,則2+2=5。F

(3)若1+1=3,則2+2=4。T⑷若1+1=3,則2+2=5。T

(5)若豬會飛，那么2+2=4。T(6)若豬會飛，那么2+2=5。T

(7)若1+1=3,豬就會飛。T(8)若1+1=2,豬就會飛。F

解(1)T：(2)F：(3)T；(4)T；(5)T；(6)T；(7)T；(8)F,

5.對下列各語句，說一說其中的“或”是“同或”與“異或”時它們的含義并符號化。

你認(rèn)為語句想表示的是哪個“或”？

(1)要求有使用過C++或Java的經(jīng)驗。

(2)你必須持護(hù)照或選民登記卡才能入境。

(3)要選修離散數(shù)學(xué)課，你必須已經(jīng)選修過微積分課或高等數(shù)學(xué)課。

(4)從通用公司購買一部新車，你就能得到5000元現(xiàn)金回扣，或利率為4%的低息汽車

貸款。

(5)若下雪超過20公分或溫度低于-10℃,學(xué)校就停課。

解(1)“同或"的含義：要求有使用過C++或Java或兩者都使用過的經(jīng)驗；“異或”的

含義：要求有使用過C++或Java的但不能有兩者都使用過的經(jīng)驗。

令原子命題P：要求有使用C++的經(jīng)驗，q：要求有使用Java的經(jīng)驗，則同或和異或分

別符號化為：Pvq和(pA1q)v(-np/\q)。

我認(rèn)為該語句想表示的是“同或”。

(2)“同或"的含義：你必須持護(hù)照或選民登記卡或兩者都持有才能入境；''異或"的含

義：你必須持護(hù)照或選民登記卡但不是兩者都持有的才能入境。

令原子命題P：你必須持護(hù)照才能入境，4：你必須持選民登記卡才能入境，則同或和

異或分別符號化為：Pvq和(p△「幻v(「pAq)。

我認(rèn)為該語句想表示的是“同或”。

(3)“同或"的含義：要選修離散數(shù)學(xué)課，你必須已經(jīng)選修過微積分課或高等數(shù)學(xué)課或者

兩者都選修過：“異或”的含義：要選修離散數(shù)學(xué)課，你必須已經(jīng)選修過微積分課或高等數(shù)學(xué)

課但不是兩們都選修過。

令原子命題P：要選修離散數(shù)學(xué)課，你必須已經(jīng)選修過微積分課，要選修離散數(shù)學(xué)

課，你必須已經(jīng)選修過高等數(shù)學(xué)課，則同或和異或分別符號化為：Pvq和

我認(rèn)為該語句想表示的是“同或”。

（4）“同或"的含義：從通用公司購買一部新車，你就能得到5000元現(xiàn)金回扣，或利率

為4%的低息汽車貸款；或者兩者都得到；“異或”的含義：從通用公司購買一部新車，你就

能得到5000元現(xiàn)金回扣，或利率為4%的低息汽車貸款，但不能兩者都得。

令原子命題從通用公司購買一部新車，你就能得到5000元現(xiàn)金回扣，q：從通用公

司購買一部新車，你就能得到利率為4%的低息汽車貸款，則同或和異或分別符號化為：p、q

和（PA7）v（」pAq）。

我認(rèn)為該語句想表示的是“異或”。

（5）“同或"的含義：若下雪超過20公分或溫度低于-或兩者都達(dá)到，學(xué)校就停課;

“異或”的含義：若下雪超過20公分或溫度低于-1（）℃且不是兩者都達(dá)到，學(xué)校就停課。

令原子命題p：若下雪超過20公分，學(xué)校就停課，q：若溫度低于一io℃,學(xué)校就停

課，則同或和異或分別符號化為：pvq和（p八f）v-p八q）。

我認(rèn)為該語句想表示的是“同或”。

6.給出下列各蘊(yùn)涵形式命題的逆命題、否命題和逆否命題。

（1）如果今天下雪，我明天就去滑雪。

（2）只要有測驗，我就來上課。

（3）只有當(dāng)正整數(shù)沒有1和它自己以外的因數(shù)時，它才是質(zhì)數(shù)。

解（1）逆命題：如果我明天去滑雪，就今天會下雪；否命題：如果今天不下雪，我明

天就不去滑雪；逆否命題：如果我明天沒去滑雪，今天就沒下雪.

（2）逆命題：我來上課，就有測驗；否命題：只要沒有測驗，我就不來上課；逆否命題:

我不來上課，就沒有測驗。

（3）逆命題：正整數(shù)是質(zhì)數(shù)，則它沒有1和它自己以外的因數(shù)：否命題：只有當(dāng)正整數(shù)

有1和它自己以外的因數(shù)時，它才不是質(zhì)數(shù)；逆否命題：正整數(shù)不是質(zhì)數(shù)，則它有1和它自己

以外的因數(shù)。

7.求下列各個位串的按位NOT：各對位串的按位AMD和按位。/?:

(1)1011110,0100001(2)11110000,10101010

(3)0001110001,1001001000(4)1111111111,0000000000

解(1)按位NOT分別是0100001,1011110；按位。R是1111111；按位AND是000

0000；

(2)按位NOT分別是oo001111,01010101；按位。R是11111010；按位AM)是10

100000；

(3)按NOT分別是1110001110,0110110111；按位。R是1001111001；按位AND

Moooioooooo；

(4)按NOT分別是0000000000,1111111111；按位。R是1111111111：板位,AND

是0000000000：

8.你會用什么樣的布爾檢索尋找關(guān)于新澤西州海灘的網(wǎng)頁？如果你想找關(guān)于澤西島(在

英吉利海峽)海灘的網(wǎng)頁呢？

解尋找關(guān)于新澤西州海灘網(wǎng)頁的布爾檢索為：“NEW”AND“JERSEY”AND

“BEACHES”，尋找關(guān)于澤西島(在英吉利海峽)海灘網(wǎng)頁的布爾檢索為(“JERSEY”AND

"BEACHESM)AND(NOT“NEW”)。

9.你會用什么樣的布爾檢索尋找關(guān)于徒步旅行西弗吉尼亞的網(wǎng)頁？如果你想找關(guān)于徒步

旅行弗吉尼亞的網(wǎng)頁，而不是西弗吉尼亞呢？

解尋找關(guān)于徒步旅行西弗吉尼亞網(wǎng)頁的布爾檢索為：“WALKINGTOUR"AND

“VIRGINIA”AND“WEST”，尋找關(guān)于徒步旅行弗吉尼亞的布爾檢索為(**WALKING

TOUR”AND“VIRGINIA”)AND(NOT“WEST”)。

習(xí)題1.2

1.設(shè)P、4和r為如下簡單命題：P：2+3=5。q：大熊貓產(chǎn)在中國。r：復(fù)旦大學(xué)

在廣州。求下列復(fù)合命題的真值。

(1)(pgq)fr(2)(r一(2八4))3「0

(3)「r->(「pv-14Vr)(4)pv->q)fr)

解因為P、4和r分別取1,1,0o所以

(J)(/?<-><7)—>/■=(11)0=0.

(2)(r~^(p八~xP~(0-(1A1))―il—0.

(3)-1r->(-、pv—、qvr)=_iO―>(—ilv―ilv0)=0.

(4)(pAA—>r)<->((―\pv—>q)—>r)=(1A1A—iO)((—ilv—>1)—>0)=1

2.構(gòu)造下列復(fù)合命題的真值表，并由此判斷它們是否永真式、永假式和可滿足式。

(1)p(2)「p3q

(3)(pfq)7Tq)(4)(p[q)A(-?pf「q)

(5)(p—q)人(一1P—q)(6)(p7—>q)7(—>p——i4)

解(1)是可滿足式。

pq「qPTf

00i1

0i01

10i1

1100

(2)是可滿足式。

pq「p—>p<->q

00i0

0ii1

1001

1i00

(3)是永真式。

Pqprqfq(pfq)v(r?fq)

001101

011111

100011

111011

(4)是可滿足式。

pq「p「夕(pf「q)八(—'P->q)

0011111

0110100

1001111

1100010

（5）是永假式。

pqp—q「p「p—q(phq)八Lp-夕)

001100

010110

100010

1i1000

（6）是永真式。

pqrPQ—>4<->—tq(P—f)7(~'P71q)

001i011

0i10101

100i101

1100011

3.構(gòu)造下列復(fù)合命題的真值表，并由此判斷它們是否永真式、永假式和可滿足式。

⑴（p—/-r（2）（rf（pAq））Crp

（3）「rTJpvfvr）（4）（p△q△->，）—（（「pv->q）->r）

解（1）是可滿足式。

PqrPcq(pgGtr

00010

00111

0i001

0i101

10001

10101

1i010

11111

(2)是可滿足式。

Pqr〃△4r八q)(rT(p/\q))c「p

0000111

0010010

0100111

0110010

1000100

1010001

110i100

111i100

(3)是可滿足式。

-iq—f(—?pv—iqvr)

pqr「Pf—\pv—iqvr

00011111

00111011

0i010111

0i110011

10001111

10101011

1i000100

1i100011

(4)是可滿足式。

Pqrp△q△——ipv—iq(「pv-><7)-?r(pAqA-ir)c((-1〃v—iq)-r)

0000101

0010110

0i00101

0i10110

1000101

1010110

1101011

1111010

4.用真值表證明下面的等價式

(])―i(AAB)――IA.v-\B(2)A八(AvB)—A

(3)A—>B=—iAvB(4)4<->8=(A-5)△(5-A)

(5)AA(BvC)=(AAB)v(AAC)

解⑴

ABA/\BY「B」(AAB)-\Av—\B

0001111

0101011

1000111

1110000

(2)

ABAvB

0000

0110

1011

1111

(3)

ABA->B-iAvB

00111

01111

10000

11011

(4)

ABA-^BBfAA<r>B(Af8)八(B->A)

001111

011000

100100

111111

(5)

ABcBvCAABAAC/IA(BvC)

00000000

00110000

01010000

01110000

10000000

10110111

11011011

11111111

5.只使用命題變元。和q能構(gòu)造多少不同的命題公式真值表？

解能構(gòu)造出16(2的4次方)種不同的命題公式真值表。

6.用等價演算法證明下面的等價式

(1)p=(pA(7)

(2)>q)v(rp/\q)=(pvq)A-1(p/\<7)

(3)pt(qtp)=「pt(pt-1q)

(4)Tp—q)=Mq)八Tp>q)

(5)(p-><7)A(/?->r)=/7->(<7Ar)

(6)(pTr)人(qTr)=(p\/q)Tr

(7)PT(q-r)=(p八q)Tr

(8)P7(qTr)=qT(pTr)

解(1)右邊=(〃Aq)v=，A(qvrq)=〃人1=。=左邊

(2)左邊=(P八f)vJP八q)

=(pv-np)A(pvq)八(一)qv—A(—)qvq)

=1A(pVA(—1<7V—ip)A1

=(pvq)人"qvrp)

=(pvq)△->(口△4)

=右邊

(3)左邊=pt(qfp)=rpJqvp)=i

右邊=—>pf(p->—iq)=pv(->pv->q)=]

所以左邊=右邊

(4)左邊=~<P—?[)

=->((p-q)A(q-p))

=—!([PvV—1(—Vp)

=(pv(q△rp)

=(pvq)△(pv->p)A(—>qvq)△(—>qv->p)

="丫勺)八「仆人4)=右邊

(5)左邊=(P-4)△(〃-?，)

=(「pv(7)A(「pvr)

=—\p7(q入r)

=pf([△「)=右邊

(6)左邊=(P一廠)人(4f廣)

=(一)pvr)A(—iqvr)

=(-ipA—)q)vr

=-i(Pvvr

=(pvq)fr=右邊

(7)左邊=P-91r)=「pv(「qvr)

右邊=(P八q)Tr=Tp八q)7r=v-.9vr

所以左邊=右邊

(8)左邊=pf(q-r)=「pv(-14Vr)

右邊=qf(pfr)=「qv(「Pvr)

所以左邊=右邊

下面4道題是智力游戲題，解題時可以先把語句翻譯成命題公式，再利用其成真賦值進(jìn)行

求解。

7.邊遠(yuǎn)村莊的每個人要么總說真話,要么總說謊話。對旅游者的問題，村民要么回答“是”,

要么回答“不"。假定你在這一-地區(qū)旅游，走到了一個岔路口，?條岔路通向你想去的遺址，

另一岔路通向從林深處。此時恰有一村民站在岔路口，問村民什么樣的一個問題就能決定走那

條路？

解問“如果我問你右邊的路是否通向遺址，你會說'是‘，對嗎？"，如果回答“是”，

則右邊的路通向遺址，否則左邊的路通向遺址，具體分析如下：

(1)被問者總說真話且回答“對”。則右邊的路通向遺址。

(2)被問者總說真話且回答“不對”。則左邊的路通向遺址。

(3)被問者總說謊話且回答“對二因為是說謊者，所以實際上他會回答“不是”；又因

為是說謊者，他回答‘不是'，表明右邊的路通向遺址。

(4)被問者總說謊話且回答“不對”。因為是說謊者，所以實際上他會回答“是”；又因

為是說謊者，他回答'是'，表明右邊的路不通向遺址。

現(xiàn)在假設(shè)用。表示被問的人總說真話，〃表示被問的人回答“對”，尸表示如果我問右邊

的路是否通向遺址，回答'是'，s表示右邊的路通向遺址，則根據(jù)以上分析我們有如下表所

示的真值表。

Pqrs

0010

0101

1000

1111

這里，r和s都不是獨(dú)立的命題變元，可以看成命題P,4的邏輯表達(dá)式，即

r=pcq,s=p—(p—q)

8.一個探險者被幾個吃人者抓住了。有兩種吃人者：總是說謊的和永不說謊的。除非

探險者能判斷出一位指定的吃人者是說謊者還是說真話者，否則就要被吃人者烤了吃。探險

者只被允許問這位吃人者一個問題。

(1)解釋為什么問：“你說謊嗎？”是不行的。

(2)找一個問題，使探險者可以用來判斷該吃人者是說謊者還是說真話者。

解(1)略

(2)問“如果我問你是否是說謊者，你會說‘是‘，對嗎？"，如果回答“是"，則是說

謊者，否則不是說謊者。

9.偵探調(diào)查了罪案的四位證人。從證人的話偵探得出的結(jié)論是：如果男管家說的是真

話，那么廚師說的也是真話；廚師和園丁不可能都說真話；園丁和雜役不可能都在說謊；如

果雜役說真話，那么廚師在說謊。偵探能判定這四位證人分別是在說謊還是在說真話嗎？解

釋你的理由。

解設(shè)P：男管家說的是真話；廚師說的是真話；r：園丁說的是真話；九雜役

說的是真話。

則有P—4=1，4入r=°,rvs=l,=

若P=l,根據(jù)〃=1得4=1,再根據(jù)4Ar=°得r=(),再根據(jù)rvs=l得

S=l,與矛盾。

若。=°,根據(jù)=1得q=i或q=°。

若P=O,q=l,根據(jù)4Ar=0得廠=0,再根據(jù)廠vs=1得s=1,與sf「q=l矛

盾。

若P=O,q=o,根據(jù)qAr=O得r=1或r=0。

若p=°,q=Q廠=],根據(jù)「vs=l得s=l或s=0,都s>14=1相容。

若p=0,7=0,r=0,根據(jù)rvs=l得s=l,與s=l相容。

從以上分析可以可以判定男管家和廚師說謊，但不能判斷究竟是園丁還是雜役說真話。

10.四個朋友被認(rèn)定為非法進(jìn)入某計算機(jī)系統(tǒng)的嫌疑人。他們已對調(diào)查員作了陳述.。愛

麗絲說“卡諾斯干的”，約翰說“我沒干”，卡諾斯說“黛安娜干的”，黛安娜說“卡諾斯說

是我干的，他說謊”。

(1)如果調(diào)查員知道四個嫌疑人中恰有一人說真話，那么誰非法進(jìn)入了計算機(jī)系統(tǒng)？

說明理由。

(2)如果調(diào)查員知道四個嫌疑人中恰有一人說慌，那么誰非法進(jìn)入了計算機(jī)系統(tǒng)？說

明理由。

解設(shè)。：卡諾斯干的（愛麗絲說）；q：我沒干（約翰說）；/■：黛安娜干的（卡諾斯

說；S：卡諾斯說是我干的，他說謊（黛安娜說）。

（1）根據(jù)題意，有

（PA—A—ifA—15）V（—1/7AA—irA—16）V（—1/7AfATA―>S）V（—1PAfA—ifA5）=1

若p……八7=1,貝峭'P=l,f=l,這表明既是卡諾斯干的，又是約翰干

的，矛盾。

若f八q八t八7=1,則有「P=l,q=T,-1r=1,這表明既不是卡諾斯干的，

又不是約翰干的，也不是黛安娜干的，而只能是愛麗絲干的，但這與「s=l矛盾。

若「pA「4ArArs=l,則有r=1,f=l,這表明既是黛安娜干的，又是約翰干

的，矛盾。

若力八n八TAS=1,則有「4=1,這表明是約翰干的，這與「P=l,「r=l,

s=l相容。

所以是約翰非法進(jìn)入了計算機(jī)系統(tǒng)。

（2）略

習(xí)題1.3

1.下列命題公式哪些是析取范式哪些是合取范式？

（1）（可△->q）v（q△r）（2）（pv->q）△（可vq）

（3）（^PA->r）v<7（4）（pvq）A-iq

⑸-'Pvq（6）

（7）r7（8）q

1(10)0

解是析取范式的有：⑴、⑶、（5）、（6）、（7）、（8）、（9）、（10）；是合取范式有:

（2）、（4）、（5）、（6）、⑺、⑻、（9）、（10）,

2.在下列由3個命題變元P、q、組成的命題公式中，指出哪些是標(biāo)準(zhǔn)析取范式哪些

是標(biāo)準(zhǔn)合取范式？

⑴(―>pA—<qAr)v(—>pA<7Ar)(2)(pv—it?v—|/?)A(―>/?v<7vr)

(3)(「p△->4△t)vq(4)(PvAHpv-.r)Avr)

(5)「pvqvf(6)FAf八7

(7)1(8)0

解是標(biāo)準(zhǔn)析取范式的有：（1）、（6）、（8）；是標(biāo)準(zhǔn)合取范式的有：（2）、（5）、（7）。

3.找出一個只含命題變元。、4和r的命題公式，當(dāng)。和4為真而/?為假時命題公式

為真，否則為假。

解PM八7。

4.找出一個只含命題變元P、4和r的命題公式，在P、4和r中恰有兩個為假時命

題公式為真，否則為假。

解(pA-A—>r)v(—>pAA-ir)v(—ipA->qAr))。

5.利用等價演算法求下列命題公式的標(biāo)準(zhǔn)析取范式，并求其成真賦值。

(1)(「PTq)T(「qYP)(2)-1(/?A<7AT

(3)(pv(q/\r))-?(pvqvr)

解(1)LPTq)TEYP)

=->(Pvq)v(-14Vp)

=(-ipA—>q)v—uyvp

-(—ipA—>q)v(pA—iq)v(-ipA-iq)v(pA「q)v(pAq)

=JpA[q)v(pAf)v(pAq)

除P=0,4=1外，其余均為成真賦值。

(2)~i(pTq)八q八f=-i(-n/7vAAr=pA「qAAr=0

這是永假式，不存在成真賦值。

(3)(pv(qAr))f(pvqvr)

=-n(pv(^Ar))vp\zq7r

-(—ipA(—v—)r))vpv<7vr

二(—ipA—iq)vA—ir)vpv<7vr

=(「pA-\qA—ir)v(—ipA—i夕Ar)v(—?pA—?qA—?r)v(—?p△q/\—?r)

v(pA—A—ir)v(pA—\q△r)v(pAq八—ir)v(p△q△r)

v(—?p△[A—j")v(—>pAT)v(pA—)r)v(pAAr)

V(—?pA-11Ar)V(—1/7A^AT)V(pA—1夕Ar)v(pA^Ar)

=(-1〃A-i<7A—ir)v(-1〃A-i(7Ar)vJpA(7A—ir)v(—ipA(7Ar)

v(pA—)qA—?r)v(pA—yqAr)v(pA<7A-ir)v(pA(7Ar)

這是永真式，所有賦值都是成真賦值。

6.利用等價演算法求下列命題公式的標(biāo)準(zhǔn)合取范式，并求其成假賦值。

(1)TpTf)LP(2)(pA<y)v(-1pvr)

(3)(p-(pvq))vr

解⑴TpT-<q)八~<P=T1Pvf)八一<P=(P八q)八一p=。

這是永假式，所有賦值都是成假賦值。

(2)(pA<7)v(^/?vr)

=(pv—ip)A(pvr)A(<7v—i〃)Avr)

=(pvqvr)八(pv—vr)A(—ipvqvr)A(「pv(7v—)r)八(〃vqvr)A(—1〃vi7vr)

二(pvqvr)A(pv—iqvr)A(—?pvvr)A(「pvv—)r)

成假賦值為：p=O,q=O,「=O；p=0,<7=l,r=0,

p=l,q=O,r=0：p=l,q=0,r=]

(3)(pf(pvq))vr=-ipvpvqvr=1

這是永真式，不存在成假賦值.

7.利用真值表法求下列命題公式的標(biāo)準(zhǔn)析取范式和標(biāo)準(zhǔn)合取范式。

(1)Tp-4)(2)-Pvq)—>(pc->q)

(3)(P-4)—「(4)

(pT(q人r))AJpfJqA-ir))

解⑴

pqprqTpfq)

0010

0110

1001

1110

所以標(biāo)準(zhǔn)析取范式為

機(jī)io=P八'

標(biāo)準(zhǔn)合取范式為

AMH=(pv^)A(pv-1/7)AHpv-1/7)

(2)

pq「Pv夕p(-1Pvq)f(pCrq)

00100

01111

10011

11100

所以標(biāo)準(zhǔn)析取范式為

=(「

"知vtnwpA^)v(pAf)

標(biāo)準(zhǔn)合取范式為

MoovM〔I=(pvq)八(「pv

(3)

Pqrprq(pTq)Tr

00010

00111

01010

01111

10001

10101

11010

11111

所以標(biāo)準(zhǔn)析取范式為

用。。1v機(jī)°”v嗎00V〃2⑹vmIH

=(—ipA—iqAr)v(—ipAqAr)v(pA—)qA-ir)v(pA—iqAr)v(pAAr)

標(biāo)準(zhǔn)合取范式為

MoooA〃oi0AMl0=(〃vqvr)入(pviqvD/xJpv-^vr)

(4)

pqrpf(q△r)-yp—>(「qA-ir)(p->(<7Ar))A(「pT(「qA->r))

000111

001100

0i0100

0i1100

100010

101010

1i0010

1i1111

所以標(biāo)準(zhǔn)析取范式為

用000VM|U=AA-nr)V(pAAr)

標(biāo)準(zhǔn)合取范式為

AAAAA

M0GlAfOIOA70llAf100A/IOIA/ll0

=(pv4v—>r)A(/?v—14vr)A(pv—v—>r)A(—>pvvr)AJpvqv-nr)A(-1Pv—vr)

8.假定用〃個命題變元給出一個真值表。證明可依據(jù)此表構(gòu)造一個命題公式，使其真

值與此表一致。

證明略

9.設(shè)A是含有〃命題變元的命題公式，證明

(1)4是永真式當(dāng)且僅當(dāng)A的標(biāo)準(zhǔn)析取范式含有全部2"個最小項。

(2)A是永假式當(dāng)且僅當(dāng)A的標(biāo)準(zhǔn)析取范式不含任何最小項(即標(biāo)準(zhǔn)析取范式為0)。

(3)A是可滿足式當(dāng)且僅當(dāng)A的標(biāo)準(zhǔn)析取范式至少含有一個最小項。

證明略

10.設(shè)A是含有〃命題變元的命題公式，證明

(1)A是永假式當(dāng)且僅當(dāng)A的合取析取范式含有全部2”個最大項。

(2)A是永真式當(dāng)且僅當(dāng)A的標(biāo)準(zhǔn)合取范式不含任何最大項(即標(biāo)準(zhǔn)合取范式為1)。

(3)A是可滿足式當(dāng)且僅當(dāng)A的標(biāo)準(zhǔn)合取范式不包含所有最大項。

證明略

11.求下列命題公式的標(biāo)準(zhǔn)析取范式，再根據(jù)標(biāo)準(zhǔn)析取范式求標(biāo)準(zhǔn)合取范式。

(1)(pA9)vr

(2)(pTq)人(qfr)

解⑴略

(2)(P1q)八(qTr)

=(」pv9)A(-1夕vr)

=J?A-i(7)v(—ipAr)v(</A—uy)v(gAr)

=(—ipA-iq)v(—ipAr)vA—iq)vAr)

=(—ipA—iqA—ir)v(—1〃A—Ar)v(—>pAq八r)v(pAgAr)

=^000Vm001VW011V^lll

所以標(biāo)準(zhǔn)合取范式為

M(noAMI00AM101AMI10

=(pv—\qvr)A(—?pvvr)A(—)pvv—ir)A(—v—vr)

12.求下列命題公式的標(biāo)準(zhǔn)合取范式，再根據(jù)標(biāo)準(zhǔn)合取范式求標(biāo)準(zhǔn)析取范式。

(1)(pAq)Tq

(2)(Pcq)Tr

(3)

解(1)、(3)略

(2)(P?<7)->r

=TJPvq)人([qvp))Vr

=(pA-yq)VA—1/2)Vr

=(pA「q)v(qA-np)vr

二((pv(7)A(/?v-ip)A(—v<7)A(—iqv—ip))vr

=((/?vq)人(-1gv-|/)))vr

=(/?vvr)A(—ipv—vr)

=MoooA'"no

所以標(biāo)準(zhǔn)析取范式為

mmmAm

ooi△'"(HOA011Aioo!01人用111

=(—ipv—>qvr)A(—I/?vqvT)A(—>pvqvr)

A(/?v—><7v—>r)A(j>v—iqvr)A(pvvr)

13.三個人估計比賽結(jié)果，甲說：“4第1,B第2”,:“。第2,。第4"，：

“4第2,。第4”。結(jié)果三人估計的都不全對，但都對了一個。試?yán)们蠓妒降姆椒ㄍ扑?/p>

出A、B、C、。分別是第幾名？

解略

習(xí)題1.4

1.將下列命題公式化成與之等價且僅含｛「'八｝中聯(lián)接詞的命題公式。

⑴(口—「)△"⑵(P'("r))vp

解略

2.將下列命題公式化成與之等價且僅含｛「'v｝中聯(lián)接詞的命題公式.

(Dp/\q/\^r(2)(p->(q人rp))Aq△r

解略

3.將下列命題公式化成與之等價且僅含｛「'f｝中聯(lián)接詞的命題公式。

(D(pA^)vr(2)(pf-iq)Ar

(3)(p八q)Cr

解(1)(p八q)vr=T「Pv->q)vr=(Pfrq)Tr

(2)(P->—'V)△r=—1(—>(PT-><7)v—if)=—>((p—>—>q)—>—>r)

(3)gq)cr

=(-1(-\pv—】q)—>r)A(r——1(―\pv->q))

=TT-!(P—>r)v—>(r—>—i(p—>—?q)))

=—1((—Kp—>—>q)—>r)—>—)(r—>—i(pf—?q)))

4.對于命題公式pMqfr)。

(1)將它化成與之等價且僅含價｝中聯(lián)接詞的命題公式。

(2)將它化成與之等價且僅含｛)｝中聯(lián)接詞的命題公式。

解⑴pMq-r)

=pA(—117vr)

=-1-i(pA-i(qA-\K))

=->(/?T(qT--r))

=(PT((7T(rTr)))T(pf(qT(rTr))))

(2)PMqrr)

=p△(—>qvr)

=-i(一\pv-i(一\cjvr))

=—?pJ—?(—Jr)

=(pJp)i(((qJq)Jr)J((gJq)Jr))

§1.5命題公式的推理演算

習(xí)題1.5

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

(1)「P，pvq=>

(2)—><7Ar,r/\p,qnpY「q

(3)—i(pvr,—iq=>—ip

(4)pT(qTr),r=p/\q

(5)-np—>q,qTr,rfpnpvqvr

(6)pt