離散數(shù)學(xué)課后答案（清華版）

http：//www.khdaw.com

課后答案網(wǎng)http：//www.khdaw.cn

第1章習(xí)題解答

1.1除(3),(4),(5),(11)外全是命題，其中，(1),(2),(8),(9),

(10),(14),(15)是簡單命題，(6),(7),(12),(13)是復(fù)合命題。

分析首先應(yīng)注意到，命題是陳述句，因而不是陳述句的句子都不是命題。

本題中，(3)為疑問句，(5)為感嘆句，(11)為祈使句，它們都不是陳述句，

所以它們都不是命題。

其次，)這個句子是陳述句，但它表示的判斷結(jié)果是不確定。又因?yàn)?1),

(2),(8),(9),(10),(14),(15)都是簡單的陳述句，因而作為命題，它們

都是簡單命題。(6)和(7)各為由聯(lián)結(jié)詞“當(dāng)且僅當(dāng)”聯(lián)結(jié)起來的復(fù)合命題，

(12)是由聯(lián)結(jié)詞“或”聯(lián)結(jié)的復(fù)合命題，而(13)是由聯(lián)結(jié)詞“且”聯(lián)結(jié)起來

的復(fù)合命題。這里的“且”為“合取”聯(lián)結(jié)詞。在日常生活中，合取聯(lián)結(jié)詞有許

多表述法，例如，“雖然……，但是……”、"不僅……，而且……”、"一面……，

一面……”、“……和……”、“……與……”等。但要注意，有時“和”或“與”

聯(lián)結(jié)的是主語，構(gòu)成簡單命題。例如，(14)、(15)中的“與”與“和”是聯(lián)結(jié)

的主語，這兩個命題均為簡單命題，而不是復(fù)合命題，希望讀者在遇到“和”或

“與”出現(xiàn)的命題時，要根據(jù)命題所陳述的含義加以區(qū)分。

1.2(1)p-.2是無理數(shù)，p為真命題。

(2)p-.5能被2整除，p為假命題。

(6)pnq。其中，p:2是素數(shù)，q：三角形有三條邊。由于p與q都是真

命題，因而pGq為假命題。

(7)pDq,其中，p：雪是黑色的，q：太陽從東方升起。由于p為假命

題，q為真命題，因而pq為假命題。

(8)p-2000年10月1日天氣晴好，今日(1999年2月13日)我們還不

知道P的真假，但P的真值是確定的(客觀存在的)，只是現(xiàn)在不知道而已。

(9)p：太陽系外的星球上的生物。它的真值情況而定，是確定的。

1

(4

http：//www.khdaw.com

課后答案網(wǎng)http：//www.khdaw.cn

(10)p：小李在宿舍里.P的真值則具體情況而定，是確定的。

(12)p(q,其中，p:4是偶數(shù)，q:4是奇數(shù)。由于q是假命題，所以，q

為假命題，為真命題。

(13)p(q,其中，p:4是偶數(shù)，q:4是奇數(shù)，由于q是假命題，所以，p(q

為假命題。

(14)p：李明與王華是同學(xué)，真值由具體情況而定(是確定的)。

(15)p：藍(lán)色和黃色可以調(diào)配成綠色。這是真命題。

分析命題的真值是唯一確定的，有些命題的真值我們立即可知，有些則不

能馬上知道，但它們的真值不會變化，是客觀存在的。

1.3令:2+2=4,q:3+3=6,則以下命題分別符號化為

(1)pOq

(2)p□<—(7

(3)<—/?q

(4)<-p□

(5)pUq

(6)p□<—(7

(7)<—p□q

(8)—pfJ—q

以上命題中，(1),(3),(4),(5),(8)為真命題，其余均為假命題。

分析本題要求讀者記住pUq及pq的真值情況。pUq為假當(dāng)且僅當(dāng)

P為真,q為假，而為真當(dāng)且僅當(dāng)P與q真值相同.由于p與q都是真命題，

在4個蘊(yùn)含式中，只有(2)pQr,其中，p同(1),r：明天為3號。

在這里，當(dāng)p為真時，r一定為假，pQr為假，當(dāng)p為假時，無論r為真

還是為假，p□/?為真。

2

http：//www.khdaw.com

課后答案網(wǎng)http：//www.khdaw.cn

1.5（1）p》q,其中，p：2是偶數(shù)，q：2是素數(shù)。此命題為真命題。

（2）psq,其中，p：小王聰明，q：小王用功

（3）p”，其中，p：天氣冷，q：老王來了

（4）p”，其中，p：他吃飯，q：他看電視

（5）p”,其中，p：天下大雨，q：他乘公共汽車上班

（6）p\dq,其中，p,q的含義同（5）

（7）pUq,其中,p,q的含義同（5）

（8）<—p—<—g,其中，p：經(jīng)一事，q：長一智

分析10在前4個復(fù)合命題中，都使用了合取聯(lián)結(jié)詞，都符號化為合取式,

這正說明合取聯(lián)結(jié)詞在使用時是很靈活的。在符號化時，應(yīng)該注意，不要將聯(lián)結(jié)

詞部分放入簡單命題中。例如，在（2）中，不能這樣寫簡單命題：p：小王不但

聰明，q：小王而且用功。在（4）中不能這樣寫：p：他一邊吃飯，q：他一邊

看電視。

20后4個復(fù)合命題中，都使用了蘊(yùn)含聯(lián)結(jié)詞，符號化為蘊(yùn)含式，在這里，

關(guān)鍵問題是要分清蘊(yùn)含式的前件和后件。

p^q所表達(dá)的基本邏輯關(guān)系為，P是q的充公條件，或者說q是P的必要

條件，這種邏輯關(guān)系在敘述上也是很靈活的。例如，因?yàn)镻，所以q"，只要P，

就q”“p僅當(dāng)q”“只有q才P”“除非q,否則一〃”“沒有q,就沒有P”等都表

達(dá)了q是P的必要條件，因而都符號化為p□夕或一〃口—4的蘊(yùn)含式。

在（5）中，q是p的必要條件，因而符號化為pDq,而在（6）（7）中，

P成了q的必要條件，因而符號化為qUp0

在（8）中，雖然沒有出現(xiàn)聯(lián)結(jié)詞，但因兩個命題的因果關(guān)系可知，應(yīng)該符

號化為蘊(yùn)含式。

1.6（1）,（2）的真值為0,（3）,（4）的真值為1。

分析1°（1）中公式含3個命題變項(xiàng)，因而它應(yīng)該有23=8個賦值：000,

3

001,111題中指派p,q為0,r為1,于是就是考查001是該公式〃3W3r）

的成真賦值，還是成假賦值，易知001是它的成假賦值。

2°在公式（2）,（3）,（4）中均含4個命題就項(xiàng)，因而共有24=16個賦值：

0000,0001,111L現(xiàn)在考查0011是它的成假賦值。

1.7（1）,（2）,（4）,（9）均為重言式，（3）,（7）為矛盾式，（5）,（6）,

（8）,（10）為非重言式的可滿足式。

一般說來，可用真值表法、等值演算法、主析取范式（主合取范式）法等判

斷公式的類型。

（1）對（1）采用兩種方法判斷它是重言式。

真值表法

表1.2給出了（1）中公式的真值表，由于真值表的最后一列全為1,所以，

（1）為重言式。

Pqrp(q(rp□(p(q(r)

00001

00111

01011

01111

10011

10111

11011

11111

等值演算法

“□(p(q(r)

TM—p((p(p(八)（蘊(yùn)含等值式）

TM(<-p(p)(p(r（結(jié)合律）

?1(^(r（排中律）

TM]（零律）

由最后一步可知，（1）為重言式。

（2）用等值演算法判（2）為重言式。

(P□-P)□一，

?(<-/?(<-)—p（蘊(yùn)含等值式）

?<r-p(~p（等《律）

?/?(一〃（蘊(yùn)含等值式）

TM]（排中律）

（3）用等值演算法判（3）為矛盾式

<-(p□4)”

?<-(p<-(q)3q（蘊(yùn)含等值式）

TMp(-q5q（德?摩根律）

?P((~q3-7)（結(jié)合律）

TMp》O（矛盾律）

?0（零律）

由最后一步可知，（3）為矛盾式。

(5)用兩種方法判(5)為非重言式的可滿足式。

真值表法

pq~p<—p□qq-P(―pq)□(<?□—0)

001011

0i1111

100111

110100

由表1.3可知（5）為非重言式的可滿足式。

主析取范式法

(<-pq)□(q—p)

TM(p(夕)□(y(一〃)

TM—(p(q)((—q(<-p)

?(一，(~q)?q?p

?<r-p(—q

?(一"1)((13—q)

?(<-〃3(~q(/(((<-〃(p)3-q)

?(<-p3—q)((<-p(q)(?p3-G((，(—q)

?(~p3r)((—，(q)((<-P3—q)

?(m\(mi.

在(3)的主析取范式中不含全部(4個)極小項(xiàng)，所以(3)為非重言式的

可滿足式，請讀者在以上演算每一步的后面，填上所用基本的等值式。

其余各式的類型，請讀者自己驗(yàn)證。

分析b真值表法判斷公式的類別是萬能。公式A為重言式當(dāng)且僅當(dāng)A的

真值表的最后一旬全為1；A為矛盾式當(dāng)且僅當(dāng)A的真值表的最后一列全為0；A

為非重言式的可滿足式當(dāng)且僅當(dāng)A的真值表最后一列至少有一個1,又至少有一

個0。真值表法不易出錯，但當(dāng)命題變項(xiàng)較多時，真值表的行數(shù)較多。

2，用等值演算法判斷重言式與矛盾式比較方例，A為重言式當(dāng)且僅當(dāng)A與

1等值；A為矛盾式當(dāng)且僅當(dāng)A與0等值，當(dāng)A為非重言式的可滿足式時，經(jīng)過

等值演算可將A化簡，然后用觀察法找到一個成真賦值，再找到一個成假賦值，

就可判斷A為非重言式的可滿足式了。例如，對(6)用等值演算判斷它的類型。

(p3<-p)□q

?on^(矛盾律)

TM(P□q)90no)(等價等值式)

TM(一0(q)?(—q(0)(蘊(yùn)含等值式)

TM(l(g)ar(同一律)

TM13(零律)

（同一律）

到最后一步己將公式化得很簡單。由此可知，無論P(yáng)取0或1值，只要q取

0值，原公式取值為1,即00或10都為原公式的成真賦值，而01,11為成假賦

值，于是公式為非重言式的可滿足式。

用主析取范式判斷公式的類型也是萬能的。A為重言式當(dāng)且僅當(dāng)A的主析取

范式含2“（〃為A中所含命題變項(xiàng)的個數(shù)）個極小項(xiàng)；A為矛盾式當(dāng)且僅當(dāng)A的

主析取范式中不含任何極小項(xiàng)，記它的主析取范式為0；A為非重言式的可滿足

式當(dāng)且僅當(dāng)A的主析取范式中含極小項(xiàng)，但不是完全的。

當(dāng)命題變項(xiàng)較多時，用主析取范式法判公式的類型，運(yùn)算量是很大的。

用主合取范式判斷公式的類型也是萬能的。A為重言式當(dāng)且僅當(dāng)A的主合取

范式中不含任何極大項(xiàng)，此時記A的主合取范式為1;A為矛盾式當(dāng)且僅當(dāng)A的

主合取范式含2,.個極大項(xiàng)（”為A中含的命題變項(xiàng)的個數(shù)）；A為非重言式的可

滿足式當(dāng)且僅當(dāng)A的主析取范式中含含極大項(xiàng)，但不是全部的。

1.8（1）從左邊開始演算

(p3q)((p3.q)

TMp3①(<-4)（分配律）

TM〃31（排中律）

TMp.（同一律）

(2)從右邊開始演算

?—p((q3r)（蘊(yùn)含等值式）

?(<-p(q)3(~P(r)（分配律）

TM(P□q)3(〃□r).（蘊(yùn)含等值式）

(3)從左邊開始演算

<-(p□q)

TM(("□4)9-p))

?一((一〃((7)((—，(<?))

?<-((<-p3q)((<-pm)((q3<-q)((P?q))

?一((<-〃》—q)((P3初

TM(p(q)3<-(。3分

請讀者填上每步所用的基本等值式。

本題也可以從右邊開始演算

(P(4)3—(p39)

?——((P(4)3—(pJq)

TM<-(<-(p(q)(<-<-(p》q))

?一((—P(r)((p3q))

?Vp3q)3(<-p(q)3(r(p)3(<-q(q))

TM—(13P(q)》(—q(p)31

TM<-((p□g)a(q口p))

TM—(p口q).

讀者填上每步所用的基本的等值式。

1.9(1)

<-((〃“)口〃)

TM―(<-(p?q)(p(蘊(yùn)含等值式)

?<-(<-(p》q)(p)(德?摩根律)

TMp-g》—p(結(jié)合律、交換律)

TM(p9.〃)9q(矛盾式)

?0.(零律)

由最后一步可知該公式為矛盾式。

(2)((“□夕)30口必)口(，口4)

??一(一(p》q)(p)(蘊(yùn)含等值式)

由于較高層次等價號兩邊的公式相同，因而此公式無成假賦值，所以，它為

重言式。

(3)(<-pq)(q□<-p)

TM(p(q)“一q(<-p)(蘊(yùn)含等值式)

TM~(p(q)((~q(~p)(蘊(yùn)含等值式)

TM(<-p3q)(—g(<-p(德?摩根律)

?<-c/(<-p(吸收律)

?<-p(<-q.(交換律)

由最后一步容易觀察到，11為該公式成假賦值，因而它不是重言式，又00,

01,10為成真賦值，因而它不是矛盾式，它是非重言式的可滿足式。

1.10題中給出的F,G,H,R都是2元真值函數(shù)。給出的5個聯(lián)結(jié)詞集都

是全功能集，可以用觀察法或等值演算法尋找與真值函數(shù)等值的公式。

首先尋找在各聯(lián)結(jié)詞集中與F等值的公式。

(1)設(shè)A=<-(pDq),易知A是｛<-,□｝中公式且與F等值，即F?A.

(2)設(shè)B=p3—q,易知B是｛<-,?｝中公式且與F等值，即F?B.

(3)設(shè)C=-?p(q),易知C是｛一,?｝中公式，且F?C.

(4)設(shè)。=(〃口(9口4))口(〃口(4口4))，易知D為｛口中公式，且D

(5)設(shè)E=(pDp)□夕，易知E為｛口中公式，旦F?E.

分析10只要找到一個聯(lián)結(jié)詞集中與F等值的公式，經(jīng)過等值演算就可以

找出其他聯(lián)結(jié)詞集中與F等值的公式。例如，已知A=一(2口0是｛一,□｝公式，

且。進(jìn)行以下演算，就可以找到F等值的其他聯(lián)結(jié)詞集中的公式。對A

進(jìn)行等值演算，消去聯(lián)結(jié)詞口，用一，3取代，得

A=一(，□q)

?一(一〃(q)

TMp3記為8.

則B為｛—,?｝中公式，且FTMB。再對A進(jìn)行等值演算，消去口，用-,a

取代，得

A=一(〃□夕)

?<-(<-/?(q)記為C.

則C為｛一,3｝中公式，且F^C。再對B進(jìn)行演算，消去一，口，用口取代,

在演算中，注意，對于任意的公式A,有

B=p?<-q

TMp9(g□g)

?<—<-(p3(7□g))

?□初

TM(p□(q□/)口(p□%口q)記為D.

則D為｛□｝中公式，且PTM。再對進(jìn)行演算，消去一,(，用口取代，在演算

C

中注意，對于任意的公式A

―ATM―(A(A)TMA□A.

C=(q)

TM□q

TM(P□.)□4記為E.

則E為｛□｝中公式，且F^E.

2°開始找一個與某真值函數(shù)等值的公式的方法，除觀察法外，就是根據(jù)

該真值函數(shù)的真值表，求它的主析取范式，而后進(jìn)行等值演算即可。例如，由G

的真值表可知G的主析取范式為m\(m3,于是

G?m\(m3

?.p(p)3q

TMq.

由于公式q不帶聯(lián)結(jié)詞，所以，它應(yīng)該為任何聯(lián)結(jié)詞集中的合式公式。

3。在各聯(lián)結(jié)詞集中找到的與某真值函數(shù)等值的公式并不唯一。例如，取

A=Jq【q.(｛<-,□｝中公式)

B=q3q.(｛<-,?中公式)

C=q(q.(｛―,(｝中公式)

。=(4□q)□(qq).(｛口｝中公式)

E=(4□q)□(qq).(｛□｝中公式)

則GTMATMBTMCTMQTME,對于同一個真值函數(shù)G,找到與它等值的形

式各異的公式。

對于H和R,請讀者自己去完成。

1.11(1)對C是否為矛盾式進(jìn)行討論。

當(dāng)C不是矛盾式時，4(CTMB(C,則一定有A?B,這是因?yàn)?，此時,

A(C?AB(C?B,所以，有

ATMA(CTMB(TMB

必有A?B

而當(dāng)C不是矛盾式時，A(C?B(C,不一定有A?B,舉反例如下：

設(shè)A,B,C均為含命題變項(xiàng)p,q的公式，A,B,C及A(C,8(C的真值表如表

1.4所示，從表1.4可看出，A(C?fi(C，但A?Bo

表L4

pqABcAVCBVC

0000000

0100000

1011111

1i01111

⑵對c是否為重言式進(jìn)行討論：

若C為重言式，則A3C?A,C?B,于是

A?A3C?B3C?B.

因而有

ATM8

當(dāng)C不是重言式時，請讀者舉反例說明，A?CTMB3c時，不一定有

ATMB.

(3)若—ATM—8,則ATM8.證明如下：

ATM——A(雙重否定律)

TM-8(一ATM—8)

TM8(雙重否定律)

所以

ATM8

1.12(1)設(shè)(1)中公式為A.

A?(p((^3r))(p3q3r)

ATM-(〃(g3明((，蟲》〃)

A?<-p3(<-q3<—r)((pmqmr)

A?(<—p?~q)(gq3<—r)((p3q3r)

A?(<—pm—q3(<r-r3r))((—p3q3r)3—r)((pmqar)

((<-〃9t79<-r)((/?a^ar)

A?m)(m\(mi

于是,公式A的主析取范式為

mo(m\(ZW2(mi

易知,A的主合取范式為

%((Ms(Me

A的成真賦值為

000,001,010,111

A的成假賦值為

011,100,101,110

⑵設(shè)⑵中公式為B

B?(<-p□q)口(<—q3p)

?(一<-〃(q)□(r3p)

TM(p(q)□(<-q3p)

TM<-(p(q)((-q3p)

TM(<-p(fq3P

TM—q3P(吸收律)

?((<-P(q)9<-)(八(<-q3p)

?(<-p(r)(p?(p3<-q)((P3q)

?mn(62(加3

所以,B的主析取范式為mo(m2(rm.

B的主合取范式為

B的成真賦值為00,10,11.

B的成假賦值為01.

(3)設(shè)(3)中公式為C.

C?<-(pQq)3q3r

TM(p3<—47)3g3r]

?pa(~q3q)3r

TMp303r

?0.

所以,c的主析取范式為0.

C的主合取范式為M。3Ml3M23M3

C的成假賦值為00,01,10,11

C無成真賦值,C為矛盾式.

分析10設(shè)公式A中含/?(/?￡1)個命題變項(xiàng)，且A的主析取范式中含

分別為0到2?1這2?個十進(jìn)制數(shù)中未在A的主析取范式的極小項(xiàng)角標(biāo)中出現(xiàn)過

的十進(jìn)制數(shù).

在⑴中,n=3,A的主析取范式中含4個極小項(xiàng),所以,A的主合取范式中必含

234=4個極大項(xiàng),它們的角標(biāo)為0到7中未在主析取范式的極小項(xiàng)角標(biāo)中出現(xiàn)

過的3,4,5,6.這樣，只要知道A的主析取范式，它的主合鄧范式自然也就知道了，

在(2),(3)中情況類似.

2°A的主析取范式中極小項(xiàng)角標(biāo)的二進(jìn)制表示即為A的成真賦值.在⑴中，

由于主析取范式中的極小項(xiàng)角標(biāo)分別為0,1,2,7,它們的二進(jìn)制表示分別為

000,001,010,111,所以,A的成真賦值為以上各值.類似地,A的主合取范式中所

含極大項(xiàng)角標(biāo)的二進(jìn)制表示,即為A的成假賦值.

1.13(1)首先求p□(“□〃)的主析取范式.

p□((7□r)

TM―p((r(r)

?—p(—q(r).

由于演算過程較長,可以分別先求出由一p,-q,r派生的極小項(xiàng).注意,本公式

中含3個命題變項(xiàng)，所以，極小項(xiàng)長度為3.

<-p?―p9(<-<7(q)3(<-r(r)

?(<-/?3<-<73r)((<-/?3<r-q3r)

((<-/73q3<-r)((<-p3—q3r)

?〃?0(〃?l(加2(加3

<-p?(<-p(p)3-q3(<-r(r)

?(<-p》—q3<-r)((<-p3—q3r)

((<-p?-43—r)(3r")

?(/Hl(7724(TWs

r?(一〃(p)3(—q(q)3r

?(<-〃3r3r)((<-〃3<r-q3r)

TM(p9—q3r)((p“3r)

?m\(/nn(ms(nr；

p□(q□r)TM機(jī)0(如(加(如(用4(機(jī)5(mt

類似地，可求出q0(pr)主的析取范式也為上式，由于公式的主析取范式

的唯一性,可知，

(p□(^□r))?((/□(/?□r)).

(2)①

TM一(p〃)

?—p(—q

TM.p?(—q(q))(((<-p(p)3.q)

?(—〃mr)((<-〃3初(((<-"(<-〃)((〃》jq)

?(<-p3r)((<-p3q)((p(~p)

?m(}(mi(.

②pUq

TM—(p》4)

?(r

?〃力.

由于pQq與pUq的主析取范式不同.因而它們不等值，即pQq?pQq.

1.14設(shè)p:A輸入；

設(shè)q:B輸入；

設(shè)r:C輸入；

由題的條件，容易寫出FA,FB,FC的真值表，見表1.5所示.由真值表分別寫出

它們的主析范鄧范式，而后，將它們都化成與之等值的(}中的公式即可.

表1.5

pqrFAFBFc

000000

001001

010010

011010

100100

101100

110100

111100

FA?(p3—q3<-r)((/73—q3r))((p3q3)((p3?r)

TM(P?T)9(<-r(r)((p3^)3(<-r(r)

?(7?9—G((〃34)

TM

P

?<—<-(p3q)

?<-(p□q)

?<-(p□q)

TM(p[]q)(p^p)

FB?(<-/73q3<-r)((<-〃》q》r)

?(<-p》q)3(<-r(r)

?(<—〃3q)

?<-<-(<-/73q)

?<-(p3—q)

TM〃□-q)

?pQ(qDq).

Fc?(<—p3<-p3r)

?<-(p(<7)3r

TM(p□q)3「

?<—<—((pq)3r

?<-(<-(pq)(<-r

?<—(pq)□<—r

?((p□夕)□([□初□(/■□廠)\

分析在將公式化成｛口｝或｛口｝中公式時，應(yīng)分以下幾步:

(D先將公式化成全功能集｛—,3,(｝中的公式.

(2)使用

―ATM—(A3A)?AA,

或

―ATM—(A(A)TMA口A.

使用雙重否定律

A38TM<_<_(A3B)?<-(A□B)

TM(A□B)□(A□B)

或

A(B?<-<-(A(B)?<-(A□B)

TM(A□B)□(A□B)

使用德?摩根律

A38TM——(A3B)TM—(一A(一3)

?―A：□―3TM(A□A)口(8口B)

或

A(B?<-<-(A(8)TM—(一A3-B)

?―A―8TM(AA)(B□B)

1.15設(shè)p：礦樣為鐵；

q：礦樣為銅；

r：礦樣為錫.

設(shè)

RTM(甲全對)3(乙對一半)3(丙全錯)，

?(<-p3)3((<-/?3<-r)((p?r))a(<-p3r)

TM(<-/73r3-p3<-r9<-/?3r)

((<—p3<—q3p3r3<—p3r)

?0(0?0.

金?(甲全對)3(乙全錯)3(丙對一半)

?(<-p3-q)3(p3<-r)9((/?3r)((<-/?3<-r)

?(~pa<—<73p3<-rapar)

((<-〃a<—qapara<—〃a<—r)

?0(0?0

F3TM(甲對一半)3(乙全對)3(丙全錯)

?(?，34)((P3r))3(~P》/")((一，3<-r)

?〃3q3—para—p9r

((pB<r-qa?—par?<—par)

?(<—/?a(7ar)(0

?~p3q3r.

F4TM(甲對一半)3(乙全錯)3(丙全對)

?((—p34)((P3<-<7))-r)3(p3-r)

?(<—〃aq―3<—r3pa<-r

((pm<r-q3p3<—r3p3<-r)

?0((pa—q3<—r)

TMpj~qa<-r.

FsTM(甲會錯)j(乙對一半)3(丙全對)

TM(P34)3((<-/?3<-r)((p9r))3(p3<-r)

TM(pmqm—p?<—r3P3<—r

((p3q3p3r3p3<-r)

TM()(()

TM0.

ATM(甲全錯)3(乙全對)9(丙對一半)

TM(p3q)3((<-/?3r)9((p9r)((<-/?3<-r)

?(p3q3-p?r?/73r

((pa(7a<T-p9r9—p9<-r)

?0(0

?0.

設(shè)

尸TM(一人全對)3(一人對一半)》(一人全錯)

則F為真命題，并且

RTMR(凡(氏(R(RR

?(<—p3q3r)((“3<r-q3<—r)?1.

但，礦樣不可能既是銅又是錫，于是q,r中必有假命題，所以-pmqmrTMo,

因而必有

p3<—q3<—r?1.

于是，必有P為真，q與r為假，即礦樣為鐵。

1.16令p：今天是1號；

q：明天是5號.

由于本題給出的推理都比較簡單，因而可以直接判斷推理的形式結(jié)構(gòu)是否為

重言式。

(1)推理的形式結(jié)構(gòu)為

(p□q)3P□?

可以用多種方法判斷上公式為重言式，其實(shí)，本推理滿足假言推理定律，即

(p0q)3p@q.

所以，推理正確。

(2)推理的形式結(jié)構(gòu)為

(〃□4)3〃□0

可以用多種方法證明上公式不是重言式，其實(shí)，當(dāng)P為假(即今天不是1

號)，q為真(明天真是5號)，也即01是上面公式的成假賦值，所以，推理的

形式結(jié)構(gòu)不是重方式，故，推理不正確。

(3)推理的形式結(jié)構(gòu)為

(〃□<7)3<—/?□—q.

可以用多種方法證明上面公式為重言式，其實(shí)，它滿足拒取式推理定律，即

(pq)3<—p?—q.

所以，推理正確。

(4)推理的形式結(jié)構(gòu)為

(p□<7)9<—/?□<—q.

可以用多種方法證明上公式不是重言式，01為上公式的成假賦值，所以，

推理不正確。

分析對于前提與結(jié)論都比較簡單的推理，最好直接判推理的形式結(jié)構(gòu)是否

為重言式，來判斷推理是否正確，若能觀察出一個成假賦值，立刻可知，推理不

正確。

1.17(1)

證明①一q(r前提引入

②—r前提引入

③①②析取三段論

④<-(p3<-q)前提引入

⑤一P(夕④置換

⑥一p②⑤析取三段論

(2)

證明①pD(q[Z]s)前提引入

②q□（（?□5）①置換

③q前提引入

④pQs②③假言推理

⑤p（前提引入

⑥r(nóng)Up⑤置換

⑦s④⑥假言三段論

(3)

證明①p附加前提引入

②，□夕前提引入

③q①②假言推理

④p”①③合取

或者

證明①p^q前提引入

②<-p(q①置換

③(~p(p)3(~p(q)②置換

④一。（（p3q）③置換

⑤P0(P3夕)④置換

(4)

證明①前提引入

②（5口/）3?口5）①置換

③②化簡

④13r前提引入

⑤t

⑥s③⑤假言推理

⑦前提引入

⑧(q□s)3(sq)⑦置換

⑨⑧化簡

⑩q⑥⑨似言推理

?qUp前提引入

?p⑩?假言推理

?r④化簡

?p3q3s3r⑥⑩??合取

分析由于

（43氐》…34）口（。口3）

?<—（Ai3A23…3AK）（（<-C（B）

?<-（Ai9A29…343。）（8

?A,9^29COB

所以，當(dāng)推理的結(jié)論也為蘊(yùn)含式時,可以將結(jié)論的前件作為推理的前提,稱為

附加前提,并稱使用附加前提的證明方法為附加前提證明法.（3）中第一個證明，

即為附加前提證明法.

1.18設(shè)P：他是理科生

q：他是文科生

r：他學(xué)好數(shù)學(xué)

前提p□r,—qp,<-r

結(jié)論q

通過對前提和結(jié)論的觀察，知道推理是正確的，下面用構(gòu)造證明法給以證明。

證明①pUr前提引入

<-r前提引入

③.P①②拒取式

④<—q□p前提引入

⑤J—q③④拒鄧式

⑥q⑤置理

1.19本題可以用多種方法求解，根據(jù)要求回答問題，解本題最好的方法

是真值表示或主析取范式法。這里采用主析取范式的主析取范式（過程略）

，((43一)

?m?(nu(mi((m?

所以，成真賦值為010,100,101,110,111,由④給也，成假賦值為000,

001,011,由③給出，公式是非重言式的可滿足式，由③給出。

1.20答案A：③；B：④；C：②

分析解本題的方法不限于求主析取范式或主合取范式，也可以利用真值表

法。

方法1：求主析取范式

TM(p”)(r

TM(2》幻3(r(一)((p(—p)r)3r

?m\(my(ms(me(mi

從上式可知，Jp》q)r的主析取范式中含5個極小項(xiàng)。極小項(xiàng)角碼的二

進(jìn)制表示為成真賦值，因而成真賦值為001,011,101,110,11L由成真賦值

立即可知成假賦值為000,

010,100,成假賦值的十進(jìn)制的十進(jìn)表示為極大項(xiàng)的角碼，因而極大項(xiàng)為

,故有3個極大項(xiàng)。

方法2：求主合取范式，分析類似主析取范式法。

方法3：真值表法

由真值表，求出成真賦值，將成真賦值轉(zhuǎn)化成十進(jìn)制數(shù)做為極小項(xiàng)的角碼，

這樣就求出了全部極小項(xiàng)，也容易求出極大項(xiàng)。

1.21答案A：③；B：⑤；C：⑥

分析可用構(gòu)造證明法解此題。

(1)①<—q(r前提引入

②―r前提引入

③一4①②析取三段論

④<-（p3-q）前提引入

⑤<-/?（q④置換

⑥~p③⑤析取三段論

至此可知-p是（1）的邏輯結(jié)論。

(2)①<-r(s前提引入

②?s前提引入

③I①②析取三段論

④(p?q)□r前提引入

⑤一（p》/④置換

⑥—p(—q⑤置換

至此可知—p（一4是（2）的國邏輯結(jié)論

(3)①一p(q前提引入

②pDq①置換前提引入

③一4(r前提引入

@qDr③置換

⑤pElr②④假言推理

⑥廠□s前提引入

⑦，□5⑤⑥假言推理

至此可知p是（3）的邏輯結(jié)論。

1.22答案A：④

分析在本題中，設(shè)A,B,C分別表示3個開關(guān)狀態(tài)的命題變項(xiàng)，開關(guān)的

扳鍵向上時，對應(yīng)命題變項(xiàng)的真值為1,否則為0,由真值表易知。

77TM(―A?3C)((—A?B9—C)

TM―A》((—B3C)((Ba<-O)

(A3((<-B3<-C)((B3C))

?(<-A^(B(Q)((A9(<-B(Q3(5(<-C))

TM(<-A子(8(。)((A3KB3―C)((一8》C))

?(一AT(B(Q)((A9<-(B(Q)

及A(B(C

第2章習(xí)題解答

2.1本題沒有給出個體域，因而使用全總個體域.

(1)令F(x)-.x是鳥

G(x):x會飛翔.

命題符號化為

□%(尸(x)□G(x)).

⑵令F(x):x為人.

G(x):x愛吃糖

命題符號化為

<-Ebc(F(x)DG(x))

或者

0x(尸(x)3<-G(x))

⑶令F(x):x為人.

G(x):x愛看小說.

命題符號化為

Qx(F(x)3G(x)).

(4)F(x):x為人.

G(x):x愛看電視.

命題符號化為

<—Zyc(F(x)》<—G(x)).

分析1°如果沒指出要求什么樣的個體域，就使用全總個休域，使用全總個

體域時，往往要使用特性謂詞。(1)-(4)中的F(x)都是特性謂詞。

2°初學(xué)者經(jīng)常犯的錯誤是，將類似于(1)中的命題符號化為

Zx(尸(X)3G(x))

即用合取聯(lián)結(jié)詞取代蘊(yùn)含聯(lián)結(jié)詞，這是萬萬不可的。將(1)中命題敘述得

更透徹些，是說“對于宇宙間的一切事物百言，如果它是鳥，則它會飛翔?！币?/p>

而符號化應(yīng)該使用聯(lián)結(jié)詞f而不能使用3o若使用3,使(1)中命題變成了“宇

宙間的一切事物都是鳥并且都會飛翔?！边@顯然改變了原命題的意義。

3°(2)與(4)中兩種符號化公式是等值的，請讀者正確的使用量詞否定

等值式，證明(2),(4)中兩公式各為等值的。

2.2(l)d(a),(b),(c)中均符號化為

rxF(x)

其中F(X):(X+1)2=X2+2X+1,此命題在(a),(b),(c)中均為真命題。

(2)在(a),3),(c)中均符號化為

□xG(x)

其中G(x):x+2=0,此命題在(a)中為假命題，在(b)(c)中均為真命題。

(3)在(a),S),(c)中均符號化為

DxH(x)

其中H(x):5x=1.此命題在(a),(b)中均為假命題，在(c)中為真命題。

分析1°命題的真值與個體域有關(guān)。

2°有的命題在不同個體域中，符號化的形式不同，考慮命題

“人都呼吸”。

在個體域?yàn)槿祟惣蠒r，應(yīng)符號化為

DxF(x)

這里，F(xiàn)(x):x呼吸，沒有引入特性謂詞。

在個體域?yàn)槿倐€體域時，應(yīng)符號化為

x{F(x)□G(九))

這里，尸(x):x為人，且尸(X)為特性謂詞。G(x):x呼吸。

2.3因題目中未給出個體域，因而應(yīng)采用全總個體域。

(1)令：是大學(xué)生，G(x):x是文科生，H(x):光是理科生，命題

符號化為

□x(F(x)□(G(x)("(x))

(2)令/(x):x是人，G(y