離散數(shù)學課后答案

第1章習題解答

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

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

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

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

所以它們都不是命題。

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

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

都是簡單命題。(6)和(7)各為由聯(lián)絡(luò)詞“當且僅當”聯(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)p-qo其中，p:2是素數(shù)，q：三角形有三條邊。由于p與q都是真

命題，因而p—q為假命題。

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

題，q為真命題，因而p—q為假命題。

(8)p:2000年10月1II天氣晴好，今日(1999年2月13II)我們還不知道p的真假，

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

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

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

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

pVq為真命題。

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

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

(15)p：藍色和黃色可以調(diào)配成綠色。這是真命題。分析命題的真值是唯一確定的，有些

命題的真值我們立即可知，有些則不能馬上知道，但它們的真值不會變化，是客觀存在的。

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

(1)p—q(2)p—＞飛(3)rp—q(4)中一飛(5)p—q(6)p一飛⑺丁一q

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

分析本題要求讀者記住p-q及p-q的真值情況。p-q為假當且僅當

P為真,q為假，而p-q為真當且僅當p與q真值相同.由于p與q都是真命題，

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

在這里，當p為真時，r一定為假，p—r為假，當p為假時，無論r為真

還是為假，p-r為真。

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

(2)pAq，其中，p：小王聰明，q：小王用功

(3)pAq,其中，p：天氣冷，q：老王來了

(4)pAq,其中，p：他吃飯，q：他看電視

(5)pAq,其中，p：天下大雨，q：他乘公共汽車上班

(6)ptq，其中，p-q的含義同(5)

(7)p—<1，其中，p,q的含義同(5)

(8)p一2，其中，p：經(jīng)一事，q：長一智

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

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

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

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

看電視。

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

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

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

條件，這種邏輯關(guān)系在敘述上也是很靈活的。例如，“因為p,所以q"，“只要p,

就q”“p僅當q”“只有q才p”“除非q,否則不”“沒有q,就沒有p”等都表

達了q是p的必要條件，因而都符號化為p-q或丁一2的蘊含式。

在(5)中，q是p的必要條件，因而符號化為p—q,而在(6)(7)中，p

成了q的必要條件，因而符號化為q-p。

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

1.6(1),(2)的真值為0,(3),(4)的真值為1。

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

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

pA(qAr)的成真賦值，還是成假賦值，易知001是它的成假賦值。

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

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

1.7(1),(2),(4),(9)均為重言式，(3),(7)為矛盾式，(5),(6),(8),(10)

為非重言式的可滿足式。一般說來，可用真值表法、等值演算法、主析取范式(主合取范式

法等判斷公式的類型。

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

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

重言式。

等值演算法p-(pVqVr)O-pV(pVpVr)(蘊含等值式)

臺「pVp)VpVr(結(jié)合律)

pqrpVqVrp—>(pVqVr)

00001

00111

01011

01111

10011

10111

11011

11111

01VqVr(排中律)

O1(零律)

由最后一步可知，(1)為重言式。

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

（P-邛）T邛

㈡J）V「）—P（蘊含等值式）

OrpVrp（等嘉律）

<=>pV-p（蘊含等值式）

<=>1（排中律）

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

r（p—q）Aq

㈡-（p-Vq）Aq（蘊含等值式）

OpV三八q（德,摩根律）

<=>pV（^qAq）（結(jié)合律）

<=>pA0（矛盾律）

30（零律）

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

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

真值表法

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

pq邛T->qq—邛「p-q）->（q-?邛）

001011

011111

100111

110100

主析取范式法

「p-q）->（q-?邛）

0（p\Zq）-「qV-p）

gr（pVq）V（rqVrp）

<=>（rpV飛）V「qV￥

臺￥V-q

<=>（rpAl）V（l/\rq）

0（rpA（rqVq）V（（rpVp）Arq）

<=>（rpArq）V（rpVq）V（不Ar）V（PV飛）

<=>（rp八rq）V（T>Vq）V（丁八rq）

.012OmVmVrn

在（3）的主析取范式中不含全部（4個）極小項，所以（3）為非重言式的

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

其余各式的類型，請讀者自己驗證。

分析1D真值表法判斷公式的類別是萬能。公式A為重言式當且僅當A的

真值表的最后一旬全為1;A為矛盾式當且僅當A的真值表的最后一列全為0；A

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

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

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

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

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

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

(P八￥)一q

O0-q(矛盾律)

㈡(p—q)A(q^-0)(等價等值式)

O「0Vq)AjqVO)(蘊含等值式)

<=>(1Vq)A飛(同一律)

OlArq(零律)

㈡rq(同一?律)

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

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

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

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

范式含2n(n為A中所含命題變項的個數(shù))個極小項；A為矛盾式當且僅當A的

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

式當且僅當A的主析取范式中含極小項，但不是完全的。

當命題變項較多時，用主析取范式法判公式的類型，運算量是很大的。

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

范式中不含任何極大項，此時記A的主合取范式為1；A為矛盾式當且僅當A的

主合取范式含2n個極大項(n為A中含的命題變項的個數(shù))；A為非重言式的可

滿足式當且僅當A的主析取范式中含含極大項，但不是全部的。

1.8(1)從左邊開始演算

(pAq)V(p△飛)

OpA(qVrq)(分配律)

㈡pAl(排中律)

0p.(同一?律)

(2)從右邊開始演算

P-*(qAr)

<=>-pV(qAr)(蘊含等值式)

飲￥Vq)A(邛Vr)(分配律)

㈡(p—q)A(p-r).(蘊含等值式)

(3)從左邊開始演算

-(p—q)

臺((P-q)A(qip))

Or((rpVq)V(-pVq))

0r(「pA-q)V(pAq))

O(pVq)AYpAq).

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

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

(PVq)AXpAq)

㈡r(PVq)Ar(pAq)

0r(r(pVq)V-(pAq))

<=>V-q)V(pAq))

0r(「pAq)A(-pVq)A(^qVp)A(-qVq))

<=>ApVq)八(fVp)A1

0r((p-q)A(qip))

㈡r(p-q).

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

1.9(1)

XPAq)-p)

<=>^(pAq)Vp(蘊含等值式)

Or(r(pAq)VP)(德?摩根律)

㈡r((rpAq)V(-pA)V(qA-'q)V(pAq))

OpAqA邛(結(jié)合律、交換律)

<=>(pAT>)Aq(矛盾式)

O0.(零律)

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

<2)((p—q)A(q->p))->(p*->q)

<=>-(-(pAq)Vp)(蘊含等值式)

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

重言式。

(3)(邛—q)T(q—rp)

㈡(PVq)-「qV))(蘊含等值式)

or(pVq)V(rqVrp)(蘊含等值式)

㈡(rp/\q)\ZrqV-'p(德?摩根律)

0rVrp(吸收律)

<=>pVF(交換律)

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

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

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

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

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

(1)設(shè)A=汽p—>q),易知A是卜,一｝中公式且與F等值，即F臺A.

(2)設(shè)B=p△飛，易知B是卜,八｝中公式且與F等值，即F臺B.

(3)設(shè)?=汽中Vq),易知C是卜,八｝中公式，且FOC.

(4)設(shè)D=(pT(qfq))T(pT(qfq)),易知D為｛月中公式，且F0D.

(5)設(shè)E=(plp)1q,易知E為｛1｝中公式，且FOE.

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

找出其他聯(lián)結(jié)詞集中與F等值的公式。例如，已知A-(p-q)是｛一，一｝公式，

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

進行等值演算，消去聯(lián)結(jié)詞一,用二八取代，得

A=r(PTq)0r(rpV口)臺PA飛記為B.則B為｛r,A｝中公式，且F<=>B。再對A進

行等值演算，消去T，用r,八取代，得A=r(p-q)㈡r(rp\q)記為C.則C為八｝中

公式，且FOC。再對B進行演算，消去r,T,用T取代，在演算中，注意，對于任意的

公式A,有

-A今r(AAA)<=>ATA.

B=pArq

gPA(q?q)

OE(PA(qfq))

gXpT(qTq))

Q(pT(qtq))T(pT(qTq)記為D.

則D為什｝中公式，且F0D.再對C進行演算，消去r,V,用[取代，在演算

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

rAg-(AVA)OAJA.

C=「(rpVq)

Orp[q

㈡(pJ.p)J,q記為E.

則E為｛1｝中公式，且FOE.

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

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

的真值表可知G的主析取范式為，于是13mVm

13GOmVm

<=>(-pAq)V(pAq)

gLpVp)Aq

<=>q.

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

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

A=rq—q.(｝中公式)

B=qAq.(卜,八｝中公式)

C=qVq.(｛qV｝中公式)

D=(qfq)f(qTq).(｛T｝中公式)

E=(q[q)J(qJq).(｛1｝中公式)

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

式各異的公式。

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

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

當C不是矛盾式時，AVC<=>BVC,則一定有A<=>B,這是因為，此時，

AVC0A,BVC0B,所以，有

A<=>AVCOBVOB

必有A㈡B

而當C不是矛盾式時，AVCOBVC,不一定有A<=>B,舉反例如下：

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

1.4所示，從表1.4可看出，AVC<=>BVC,但A0B。

表1.4

(2)對C是否為重言式進行討論：

若C為重言式，則AAC0A,COB,于是

AOAACOBACOB.

因而有A臺B

當C不是重言式時，請讀者舉反例說明,AACOBAC時，不一定有

A<=>B.

(3)若rA<=>rB,則AOB.證明如下:

A(雙重否定律)

<=>-B(-A<=>-B)

臺B(雙重否定律)

所以

A臺B

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

A<=>(pV(q八r))—(pAqAr)

A<=>-'(pV(qAr))V(pAqAr)

AO「pA(「qAT)V(pAqAr)

AO(~pA-'q)V(rqAT)V(pAqAr)

pqABCAVCBVC

0

0

1

1

0

1

0

1

0

0

1

0

0

0

1

1

0

0

1

1

0

0

1

I

0

0

1

1

A<=>(「p/\「qA(~rAr))V「pAqAr)AT)V(pAqAr)

V(邛AqA^r)V(pAqAr)

017A<=>mVmVm

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

0127mVmVmVm

易知,A的主合取范式為

3456MVMVMVM

A的成真賦值為

000,001,010,111

A的成假賦值為

011,100,101,110

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

B<=>(p—q)-LqAp)

oLpVqJLqAp)

㈡(pVq)—「qAp)

0r(pVq)V「qAp)

V^q)V-'qAp

0rq八p(吸收律)

<=>(LpVq)A-1)VpA(fAp)

<=>「pV飛)VpA(pA^q)V(pAq)

023<=>mVmVm

所以,B的主析取范式為.023mVmVm

B的主合取范式為1M

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

B的成假賦值為01.

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

C<=>r(p-<|)AqAr

0(pA^q)AqAr]

<=>pA(rqAq)Ar

<=>pAOAr

O0.

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

C的主合取范式為0123MAMAMAM

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

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

分析1。設(shè)公式A中含n(nNl)個命題變項，且A的主析取范式中含

l(0WM2n)個極小項，則A的主合鄧范式中含2nT個極大項，而且極大項的角標

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

的十進制數(shù).

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

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

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

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

2°A的主析取范式中極小項角標的二進制表示即為A的成真賦值.在

(1)中，由于主析取范式中的極小項角標分別為0,1,2,7,它們的二進制表示分別

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

所含極大項角標的二進制表示，即為A的成假賦值.

J.13W首先求p-Kq-r)的主析取范式.

錯誤！鏈接無效。

0￥V(飛Vr)

—邛V^qVr).

由于演算過程較長，可以分別先求出由「p「q,r派生的極小項.注意，本公式

中含3個命題變項，所以，極小項長度為3.

-p臺p八(「qVq)A(fVr)

O(「pA^qAr)V(「pAAr)

V「pAqA-T)V(「pA-'qAr)

01230mVmVmVm

-p<=>(-'pVp)A_,qA(fVr)

臺(「pA-'qA-r)V(邛八rqAr)

V("pA「qAT)V(pAAr)

0145OmVmVmVm

r<4(「pVp)A「qVq)Ar

今(「p八「qAr)V(邛A^qAr)

<=>(pA-'qAr)V(pAqAr)

13157OmVmVmVm

0123457p—(q—r)0mVmVmVmVmVmVm

類似地，可求出q-(p-r)主的析取范式也為上式，由于公式的主析取范式

的唯一性,可知，

(p->(q->r))O(q-(p—r)).

⑵①

p?q

㈡「(pAq)

O-pV-xq

課后答案網(wǎng)

16

g「P八(「qVq))V((-pVp)/\p)

O(~pArj)V(-pAq))V((「pV-np)V(pA)

<=>("p八飛)V(pAq)V(pV-'p)

.012OmVmVm

②p[q

Or(pAq)

<=>-pV-xq

.0Om

由于pTq與plq的主析取范式不同,因而它們不等值，即pTq0P1q.

1-14設(shè)p:A輸入；

設(shè)q:B輸入；

設(shè)r:C輸入；

山題的條件，容易寫出的真值表，見表1.5所示.山真值表分別寫出ABCF,F,F

它們的主析范鄧范式，而后，將它們都化成與之等值的｛1｝中的公式即可;

表1.5

F(pqr)(pqr))(pqr)(pqr)A臺A「ZV八「AVAA-1VAA

pqrFAFBCF

000

001

010

011

100

10I

110

111

0

0

0

0

1

1

1

1

0

0

1

1

0

0

0

0

0

1

0

0

0

0

0

0

O(pA-'q)A(TVr)V(pAq)A(fVr)

<=>(pA-1q)V(pAq)

<=>p

O—(pAq)

g」(plq)

<=>rplq)

妗(PIq)I(PIP)

FB(pqr)(pqr)<=>AA-*VAA

臺(「pAq)A(fVr)

臺(-PAq)

0—(「pAq)

㈡「(pA-q)

3PLq)

0p1(q1q).

F(ppr)C臺「八」八

<=>r(pVq)Ar

o(plq)Ar

㈡r(plq)Ar

Or(r(pj.q)VF

04pJ.q)J.-T

o((PIq)1(P1q))1(r1r)\

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

(1)先將公式化成全功能集｛r,A,V｝中的公式.

⑵使用

rAor(AAA)OATA,

或

-Aor(AVA)臺AJ,A.

使用雙重否定律

AAB<=>—(AAB)臺r(ATB)

<=>(AtB)j(ATB)

或

AVB0—(AVB)44-(AJ.B)

O(A1B)J(A1B)

使用德?摩根律

AABorr(AAB)0r「AV-B)

<=>rALB臺(A[A)[(B]B)

或

AVB㈡—(AVB)㈡r(-AA-B)

0rATrB臺(AtA)t(BtB)

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

q：礦樣為銅；

r：礦樣為錫.

設(shè)

Fl<=>(甲全對)A(乙對一半)八(丙全錯)，

O(rpArq)八((rpAF)V⑴A「))AZ)

㈡(PApA^p八F八"八f)

V(邛A飛APAr八FAr)

<=>OV0<=>0.

()()()2F0甲全對A乙全錯八丙對一半

供rp八rq)/\(pA-T)A((pAr)V(rpAF)

<=>(rpA^qApATApAr)

V(rp八rqApArAA-T)

()()()3F<=>甲對一半八乙全對八丙全錯

<=>((rpAq)V(pA2))八(rpAr)V「pA-T)

㈡(rpAq八rpArA丁Ar

V(pArqArp/\rA^pAr)

g「pAqAr)V0

<=>-pAqAr.

()()()4FO甲對一半八乙全錯八丙全對

<=>(LpAq)V(pA))A(pA-T)A(pAf)

O(-pAq-'A-TApA-r

V(pA^qApAFApA-T)

OOV(p八2AF)

㈡pArq/\F

()()()5F今甲會錯A乙對一半A丙全對

㈡(pAq)A(「pA-T)V(pAr))A(pA^r)

O(pAqA邛AFAp八f

V(pAqApArApA~T)

<=>0V0

㈡0.

<=>0VOO0

()()()6FO甲全錯八乙全對A丙對一半

O(pAq)A((-pAr)A((pAr)V「pA-r)

<=>(pAqAArApAr

V(pAq八邛ArA-p/\F)

<=>0V0

O0.

設(shè)

FO(一人全對)A(一人對一半)△(一人全錯)

則F為真命題，并且

123456FOFVFVFVFVFVF

㈡(fpAqAr)V(p八《Af)㈡1.

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

pAqAr㈡0,因而必有

pArq/\-T<=>1.

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

1-1<5令p：今天是1號；

q：明天是5號.

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

重言式。

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

(p—q)Ap-q.

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

(p—q)Ap0q.

所以，推理正確。

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

(p—q)Ap->q.

課后答案網(wǎng)

21

可以用多種方法證明上公式不是重言式，其實，當p為假(即今天不是1

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

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

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

(p-q)A-p—rq.

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

(p—q)八p0p.

所以，推理正確。

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

(p—q)Arp—rq.

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

推理不正確。

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

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

正確。

1.17

(1)證明①rqVr前提引入②f前提引入③rq①②析取三段論④zpA^q)前提引入

⑤pVq④置換⑥r(nóng)p②⑤析取三段論

(2)證明①p一(q-s)前提引入②q-(q-s)①置換③q前提引入④p-s②③假言推理

⑤pVf前提引入⑥r(nóng)-p⑤置換⑦r—s④⑥假言三段論

(3)證明①p附加前提引入②p-q前提引入③q①②假言推理④pAq①③合取

(4)證明①前提引入②(sit)A(t-s)①置換③②化簡④tAr前提引入⑤t

⑥s③⑤假言推理⑦前提引入⑧(q-s)/\(s—q)⑦置換⑨s-q⑧化簡

⑩q⑥⑨似言推理?q-p前提引入?p⑩?假言推理?r④化簡

?pAqAsAr⑥⑩??合取

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

q：他是文科生

r：他學好數(shù)學

前提p—>r,rq—p,T

結(jié)論q

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

證明①p-r前提引入

f前提引入

③-P①②拒取式

④rq—p前提引入

⑤一q③④拒鄧式

⑥q⑤置理

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

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

pV(qAT)

24567<=>mVmVmVmVm

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

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

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

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

法。

方法1：求主析取范式

r(pAq)-^r

<=>(pAq)Vr

O(pAq)A(rV-r)V(pV-p)A(qV-q)Ar

13567<=>mVmVmVmVm

從匕式可知，NpAq)-r的主析取范式中含5個極小項。極小項角碼的二

進制表示為成真賦值，因而成真賦值為001,011,101,110,UL由成真賦值

立即可知成假賦值為000,

010,100,成假賦值的十進制的十進表示為極大項的角碼，因而極大項為

,故有3個極大項。024M,M,M

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

方法3：真值表法

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

這樣就求出了全部極小項，也容易求出極大項。

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

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

(1)①rqVr前提引入

②F前提引入

課后答案網(wǎng)

25

③rq①②析取三段論

④r(pA2)前提引入

⑤丁Vq④置換

⑥P③⑤析取三段論

至此可知rp是(1)的邏輯結(jié)論。

(2)①fVs前提引入

②F前提引入

③F①②析取三段論

@(pAq)—r前提引入

⑤NpAq)④置換

⑥丁V飛⑤置換

至此可知邛V飛是(2)的國邏輯結(jié)論。

(3)①rpVq前提引入

②p-q①置換前提引入

③FVr前提引入

@q—r③置換

⑤p-r②④假言推理

⑥r(nóng)—s前提引入

⑦p-s⑤⑥假言推理

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

1.22答案A：④

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

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

F臺QA八-BAC)V(-AABA-C)

V(AA-BApV(AABAC)

g-AA((-BAC)V(BA-C))

VAA(「BA-C)V(BAC))

<=>(-AA(BVC))V(AA(-BVC)A(BV-C))

<=>(-AA(BVC))V(AA《BA-C)VLBAC))

<=>(-AA(BVC))V(AAXBVC))

<=>AVBVC

第2章習題解答

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

⑴令F(x):x是鳥

G(x):x會飛翔.

命題符號化為

Vx(F(x)一G(x)).

⑵令F(x):x為人.

G(x):x愛吃糖

命題符號化為

rVx(F(x)—G(x))

或者

2x(F(x)A^G(x))

(3)令F(x):x為人.

G(x):x愛看小說.

命題符號化為

3x(F(x)AG(x)).

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

G(x):x愛看電視.

命題符號化為

-'Bx(F(x)ArG(x)).

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

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

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

課后答案網(wǎng)

28

Vx(F(x)AG(x))

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

更透徹些，是說“對于宇宙間的一切事物百言，如果它是鳥，則它會飛翔。‘‘因

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

宙間的一切事物都是鳥并且都會飛翔。'‘這顯然改變了原命題的意義。

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

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

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

VxF(x)

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

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

3xG(x)

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

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

3xH(x)

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

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

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

“人都呼吸”。

在個體域為人類集合忖，應(yīng)符號化為

VxF(x)

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

在個體域為全總個體域時，應(yīng)符號化為

Vx(F(x)—G(x))

這里，F(xiàn)(x):x為人,且F(x)為特性謂詞。G(x):x呼吸。

課后答案網(wǎng)

29

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

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

符號化為

X/x(F(x)一(G(x)VH(x))

(2)令F(x):x是人，G(y):y是化，H(x):x喜歡，命題符號化為

3X(F(X)AVy(G(y)-H(x,y)))

(3)令F(x):x是人，G(x):x犯錯誤，命題符號化為

-BxCF(x)ArG(x)),

或另?種等值的形式為

Vx(F(x)-G(x)

(4)令F(x):x在北京工作，G(x):x是北京人，命題符號化為

rVx(F(x)-G(x)),

或

3X(F(X)ArG(x)),

(5)令F(x):x是金屬，G(y):y是液體，H(x,y):x溶解在y中，命題符號

化為

Vx(F(x)->3y(G(y)AH(x,y))).

(6)令F(x):x與y是對頂角，H(x,y):x與y相等，命題符號化為

VxVy(F(x,y)-H(x,y)).

分析(2),(5),(6)中要使用2無謂詞，用它們來描述事物之間的關(guān)系。

2.4(1)對所有的x,存在著y,使得x-y=0,在(a),(b)中為真命題，在

(c),(d)中為假命題。

(2)存在著x,對所有的y,都有x?y=0,在(a),(b)中為真命題，在

(c),(d)中為假命題。

課后答案網(wǎng)

30

(3)對所有x,存在著y,使得x?y=l,在(a),(b)(c)中均為假命題，而在

(d)中為真命題。

(4)存在著x,對所有的y,都有xy=l,在(a),(b)(c)(d)中都是假命題。

(5)對所有的x,存在著y,使得x?丫=*在佰),8)?((1)中都是真命題。

(6)存在x,對所有的y,都有x-y=x,在(a),(b)中為真命題,在(c)(d)

中為假命題。

(7)對于所有的x和y,存在著z,使得x-y=z,在(a),(b)中為真命題，

在(c)(d)中為假命題。

2.5(1)取解釋為：個體域(實數(shù)集合)，為有理數(shù)，lID=RF(x):x

G(x):x能表示成分數(shù)，在下，的含義為1IX/x(F(x)-G(x))

“對于敘何實數(shù)x而言，若x為有理數(shù)，則x能表示成分數(shù)”，簡言之為“有

理數(shù)都能表示成分數(shù)。’'在此蘊含式中，當前件F(x)為真時，后件G(x)也為真，

不會出現(xiàn)前件為真，后件為假的情況，所以在下，為真命題。IIVx(F(x)^G(x))

在在下，的含義為1IVx(F(x)AG(x))

“對于任何實數(shù)x,x既為有理數(shù)，又能表示成分數(shù)?！?/p>

取x=2,則F(2)Ag(2)顯然為假，所以，在下，IIVx(F(x)AG(x))

為假命題.

⑵取解釋為:個體域D=N(自然數(shù)集合),為奇數(shù)，為偶2IF(x):xG(x):x

數(shù),在下，的含義為123x(F(x)AG(x))

“存在自然數(shù)x,x發(fā)既為奇數(shù)，又為偶數(shù)?！?/p>

取x=2,則F(2)為假，于是F(2)TG(2)為真,這表明mx(F(x)-G(x)為

真命題。

分析本題說明

Vx(F(x)^G(x))<=>Vx(F(x)AG(x)),

課后答案網(wǎng)

31

3x(F(x)AG(x))0mx(F(x)-G(x)),

這里，A㈡B表示A與B不等值，以后遇到㈡，含義相同。

在一階邏輯中，將命題符號化時，當引入特性謂詞(如題中的F(x))之后，

全稱量詞▼后往往使用聯(lián)結(jié)詞一而不使用A,而存在量訶三后往往使用八，而不

使用t，如果用錯了，會將真命題變成假命題，或者將假命題變成真命題。

2.6在解釋R下各式分別化為

(1)Vx(-x<0);

(2)VxVy(x-y>x);

(3)VxVyVz(x<y)—>(x-z<y-z));

(4)Vx3y(x<x-2y).

易知，在解釋R下，(1),(2)為假；，(3)(4)為真。

2.7給定解釋I為：個體域D=N(自然數(shù)集合)，F(xiàn)(x):x為奇數(shù)，G(x):x

為偶數(shù)。

(1)在解釋I下，公式被解釋為

“如果所有的自然數(shù)不是奇數(shù)就是偶數(shù)，則所有自然數(shù)全為奇數(shù)，或所有自

然數(shù)全為偶數(shù)?！驗樘N含式的前件為真，后件為假，所以真值為假。

(2)在I下，公式解釋為

“如果存在著自然數(shù)為奇數(shù)，并且存在著自然為偶數(shù)，則存在著自然數(shù)既是

奇數(shù)，又是偶數(shù)。”

由于蘊含式的前件為真，后件為假，后以真值為假。

分析本題說明全稱量詞對析取不滿足分配律，存在量詞對合取不滿足分配

律。

2.8令人=Vx\/y(F(x)AG(y)—L(x,y)),在A中，無自由出現(xiàn)的個體變項，

所以A為閉式。

給定解釋：個體域D=N(整數(shù)集合)，為正數(shù)，為負數(shù)，I1F(x):xG(x):x

L(x,y):x>y,在下，A的含義為1I

課后答案網(wǎng)

32

“對于任意的整數(shù)x和y,如果x為正整數(shù)，y為負整數(shù)，則x>y?！?/p>

這是真命題。

設(shè)解釋：個體域D=R(R整數(shù)集合)，為有理數(shù)，為無理數(shù)，I2F(x):xG(y):y

L(x,y):x<y,在下，A的含義為2I

“對于任意的實數(shù)x和y,如果x為有理數(shù)，y為元理數(shù)，則xNy。"

這是假命題。

分析閉式在任何解釋下不是真就是假，不可能給出解釋I,使得閉式在I

下真值不確定，這一點是閉式的一個重要特征。而非封閉的公式就沒有這個特征.

2.9取((，),(，))和，則和都是非土產(chǎn)的1A=Lfxygxy((,),)2A=Vxfxyx1

A

2A

公式，在中，x,y都是自由出現(xiàn)的，在中，y是自出現(xiàn)的。1

AA2

取解釋I為，個體域D=N(N為自然數(shù)集合),

f(x,y,)=x+y,g(x,y)=x-yL(x,y)為x=y。在I下，為為假，1

Ax+y=x'y

所以在I下，真值不確定，即在I下的真值也是命題。1

A

2A

在I下，為當時，它為真；時為假，在1下A2Vx(x+y=x),y=0y彳0A2

的真值也不確定。

分析非閉式與閉式的顯著區(qū)別是，前者可能在某些解釋下，真值不確定，

而后者對于任何解釋真值都確定，即不是真就是假。

當然非閉式也可以是邏輯有效式(如F(x)-F(x)),也可能為矛盾式(如

F(x)A「F(x)),也可能不存在其值不確定的解釋。

2.10(1)

--VxA(x)<=>「(A(a)AA(b)AA(c))(消去量詞等值式)

<=>[A(a)V「A(b)V「A(c)(德,摩根律)

O3x-A(x)(消去量詞等值式)

(2)

3xA(x_,(A(a)VA(b)VA(c))(消去量詞等值式)

課后答案網(wǎng)

33

臺「A(a)八「A(b)八「A(c)(德,摩根律)

0Bx-A(x)(消去量詞等值式)

2.11(1)令F(x):x為人。

G(x):x長著綠色頭發(fā)。

本命題直接符號化驗為

-3x(F(x)AG(x))]

Tfff3x(F(x)AG(x))

OVx-'(F(x)AG(x))(量詞否定等值式)

<=>Vx(-F(x)V-G(x))(德?摩根律)

OVx(F(x)-rG(x))(蘊含等值式)

最后一步得到的公式滿足要求(使用全稱量詞)，將它翻譯成自然語言，即

為

“所有的人都不長綠色頭發(fā)

可見得“沒有人長著綠色頭發(fā)。'‘與“所有人都不長綠色頭發(fā)?！笔峭}

的兩種不同的敘述方法。

(2)令F(x):x是北京人

G(x):x去過香山。

命題直接符號化為

3x(F(x)A_,G(x))]

M3x(F(x)A-G(x))

Bx(F(x)A-G(x))(雙重否定律)

Or\7xr(F(X)A^G(x))(理詞否定等值式)

Q-Vx(-F(x)VG(x))(德?摩根律)

07x(F(x)-G(x))(蘊含等值式)

課后答案網(wǎng)

34

最后得到的公式滿足要求(只含全稱量詞)，將它翻譯成自然語言，即為

“并不是北京人都去過香山?！?/p>

可見，“有的北京人沒過過香山?！迸c“并不是北京人都去過香山?！笔峭?/p>

命題不同的敘述方法。

2.12(1)VxF(x)-ByG(y)

0(F(a)AF(b)AF(c)—(G(b)VG(c)).

(2)VxF(x)A3yG(y)

3VxF(x)A3yG(y)(量詞轄域收縮擴張等值式)

<=>(F(a)AF(b)AF(c))A(G(a)VG(b)V(c)).

(3)3xVyH(x,y)

<=>3x(H(x,a)AH(x,b)AH(x,c)

臺(H(a,a)AH(a,b)AH(x,c)

V(H(b,a)AH(b,b)AH(b,c)

V(H(c,a)AH(c,b)AH(c,c)

分析在有窮個體域內(nèi)消去量詞時，應(yīng)將量詞的轄域盡量縮小，例如，在

(2)中，首先將量詞轄域縮小了(因為myG(y)中不含x,所以，可以縮小)。否

則，演算是相當麻煩的。見下面的演算：

Vx(F(x)A3yG(y)

<=>(F(a)AByG(y))A(F(b)AByG(y))AF(c)A3yG(y))

Q(F(a)A(G(a)VG(b)VG(c)

A(F(b)A(G(a)VG(c))

A(F(c)A(G(a)VG(b)VG(c))

<=>(F(a)A(F(b)A(G(a)VG(b)V(c)).

顯然這個演算比原來的轡算麻煩多了。

2.13在I下

(1)Vx(F(x)AG(x))

O(F(-2)AG(-2))A(F(3)AG(3))AF(6)AG(6))

㈡(1A0)A(1AO)A(O八1)00,

所以，Vx(F(x)八G(x)在I下為假。

(2)Vx(R(x)一F(x))VG(5)

O((R(-2)->F(-2))A(R(3)-F(3))A(R(6)7F(6)))V0

0((1)A(l-1)㈡0,

所以，此公式在I下也是假命題。

(3)3x(F(x)VG(x))

OmxF(x)V3xG(x)(量詞分配等值式)

O(F(-2)VF(3)VF(6))V(G(-2)VG(3)VG(3)

O(1V1V0)V(OV0

所以，此公式在I下為真

2.14(1)

-3xF(x)-VyG(x,y)

<=>Vx-F(x)^VyG(x,y)(量詞否定等值式)

㈡Vz-F(z)^VyG(x,y)(約束變項換名規(guī)則)

0mzVy「F(z)-G(x,y)(量詞轄域收縮擴張等值式)

<=>3zVy(F(z)VG(x,y)

(2)

r(WxF(x,y)V3yG(x,y))

<=>3xrF(x,y)AV廣G(x,y)

課后答案網(wǎng)

36

(,)(,)1122<=>3z-■FzyAVz-■Gxz

((,)(,)1212O3zVz-TzyA-<JXZ

在以上演算中分別使用了德?摩根律、量詞否定等值式、約束變項換名規(guī)則

等。

分析公式的前束范式是不唯一的。(1)中最后兩步都是前束范式，其實

Vy3z(F(z)

VG(x,y))也是(1)中公式的前束范式。

2.15(1)

VxF(x)V3yG(x,y)

<=>VxF(x)V3yG(z,y)

<=>VxBy(F(x)VG(z,y))

(2)

3x(F(x)AVyG(x,y,z))-三zH(x,y,z)

<=>5x(F(x)AVyG(x,y,u))-*3zH(v,,z)

<=>SxVy(F(x)AG(x,y,u))T3zH(v,,z)

嶼Vx3y(F(x)AG(x,y,u))-^H(v,,z)

在以上演算中分別使用了自由變項換名規(guī)則和量詞轄域收縮擴張等值式。

2.16(1)②錯。使用UI,UG,ELEG規(guī)則應(yīng)對前束范式，而①中公式下

不是前束范式，所以，不能使用UI規(guī)則。

(2)0①中公式為WxA(x),這時,A(x)=F(x)VG(x),因而使用UI規(guī)則時,

應(yīng)得A(a)(或A(y)),故應(yīng)有F(a)VG(a),而不可能為F(a)VG(b).

(3)②錯。應(yīng)對A(c)=F(c)一G(c)使用EG規(guī)則，其中c為特定的使A為

真的個體常項，而不能為個體變項。

(4)②錯。①中公式含個體變項x,不能使用EG規(guī)則。

(5)②錯。①公式含兩個個體常項，不能使用EG規(guī)則。

課后答案網(wǎng)

37

(6)⑤錯。對①使用EI規(guī)則得F(c)八G(c),此c應(yīng)使F(c)AG(c)為真，

此c不一定使H(c)AR(c)為真。

分析由于⑤的錯誤，可能由真前提，推出假結(jié)論。反例如下：

設(shè)個體域為自然數(shù)集合N.F(x):x為偶數(shù)，G(x):x為素數(shù)，H(x):x能被3

整除，R(x):x能被4整數(shù)，顯然