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

第1章習(xí)題解答

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

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

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

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

所以它們都不是命題。

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

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

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

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

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

多表述法，例如，”雖然....但是……”、“不僅......而月......”、“?面.....

一面....”、”……和....."、”……與……”等。但要注意,有時(shí)“和”或“與”

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

的主語(yǔ)，這兩個(gè)命題均為簡(jiǎn)單命題，而不是復(fù)合命題，希望讀者在遇到“和''或

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

1.2(1)p:2是無(wú)理數(shù)，p為真命題。

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

(6)p-qo其中，p:2是素?cái)?shù)，q：三角形有三條邊。由于p與q都是真

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

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

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

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

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

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

(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：李明與王華是同學(xué)，真值由具體情況而定(是確定的)。

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

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

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

(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為假當(dāng)且僅當(dāng)

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

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

在這里，當(dāng)p為真時(shí)，r一定為假，p—r為假，當(dāng)p為假時(shí)，無(wú)論r為真

還是為假，p-r為真。

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

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

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

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

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

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

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

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

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

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

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

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

看電視。

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

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

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

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

就q”“p僅當(dāng)q”“只有q才p”“除非q,否則不”“沒(méi)有q,就沒(méi)有p”等都表

達(dá)了q是p的必要條件，因而都符號(hào)化為p-q或丁一2的蘊(yùn)含式。

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

成了q的必要條件，因而符號(hào)化為q-p。

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

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

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

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

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

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

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

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

為非重言式的可滿(mǎn)足式。一般說(shuō)來(lái)，可用真值表法、等值演算法、主析取范式(主合取范式

法等判斷公式的類(lèi)型。

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

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

重言式。

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

臺(tái)「pVp)VpVr(結(jié)合律)

pqrpVqVrp—>(pVqVr)

00001

00111

01011

01111

10011

10111

11011

11111

01VqVr(排中律)

O1(零律)

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

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

（P-邛）T邛

㈡J）V「）—P（蘊(yùn)含等值式）

OrpVrp（等嘉律）

<=>pV-p（蘊(yùn)含等值式）

<=>1（排中律）

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

r（p—q）Aq

㈡-（p-Vq）Aq（蘊(yùn)含等值式）

OpV三八q（德,摩根律）

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

<=>pA0（矛盾律）

30（零律）

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

（5）用兩種方法判（5）為非重言式的可滿(mǎn)足式。

真值表法

由表1.3可知（5）為非重言式的可滿(mǎn)足式。

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￥

臺(tái)￥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個(gè)）極小項(xiàng)，所以（3）為非重言式的

可滿(mǎn)足式，請(qǐng)讀者在以上演算每一步的后面，填上所用基本的等值式。

其余各式的類(lèi)型，請(qǐng)讀者自己驗(yàn)證。

分析1D真值表法判斷公式的類(lèi)別是萬(wàn)能。公式A為重言式當(dāng)且僅當(dāng)A的

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

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

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

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

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

等值演算可將A化簡(jiǎn)，然后用觀(guān)察法找到一個(gè)成真賦值，再找到一個(gè)成假賦值，

就可判斷A為非重言式的可滿(mǎn)足式了。例如，對(duì)（6）用等值演算判斷它的類(lèi)型。

(P八￥)一q

O0-q(矛盾律)

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

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

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

OlArq(零律)

㈡rq(同一?律)

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

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

假賦值，于是公式為非重言式的可滿(mǎn)足式。

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

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

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

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

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

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

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

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

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

1.8(1)從左邊開(kāi)始演算

(pAq)V(p△飛)

OpA(qVrq)(分配律)

㈡pAl(排中律)

0p.(同一?律)

(2)從右邊開(kāi)始演算

P-*(qAr)

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

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

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

(3)從左邊開(kāi)始演算

-(p—q)

臺(tái)((P-q)A(qip))

Or((rpVq)V(-pVq))

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

O(pVq)AYpAq).

請(qǐng)讀者填上每步所用的基本等值式。

本題也可以從右邊開(kāi)始演算

(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(蘊(yùn)含等值式)

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)(蘊(yùn)含等值式)

由于較高層次等價(jià)號(hào)兩邊的公式相同，因而此公式無(wú)成假賦值，所以，它為

重言式。

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

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

or(pVq)V(rqVrp)(蘊(yùn)含等值式)

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

0rVrp(吸收律)

<=>pVF(交換律)

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

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

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

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

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

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

(2)設(shè)B=p△飛，易知B是卜,八｝中公式且與F等值，即F臺(tái)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°只要找到一個(gè)聯(lián)結(jié)詞集中與F等值的公式，經(jīng)過(guò)等值演算就可以

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

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

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

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

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

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

公式A,有

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

B=pArq

gPA(q?q)

OE(PA(qfq))

gXpT(qTq))

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

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

中注意，對(duì)于任意的公式A

rAg-(AVA)OAJA.

C=「(rpVq)

Orp[q

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

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

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

該真值函數(shù)的真值表，求它的主析取范式，而后進(jìn)行等值演算即可。例如，由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,對(duì)于同一個(gè)真值函數(shù)G,找到與它等值的形

式各異的公式。

對(duì)于H和R,請(qǐng)讀者自己去完成。

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

當(dāng)C不是矛盾式時(shí)，AVC<=>BVC,則一定有A<=>B,這是因?yàn)?，此時(shí)，

AVC0A,BVC0B,所以，有

A<=>AVCOBVOB

必有A㈡B

而當(dāng)C不是矛盾式時(shí)，AVCOBVC,不一定有A<=>B,舉反例如下：

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

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

表1.4

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

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

AOAACOBACOB.

因而有A臺(tái)B

當(dāng)C不是重言式時(shí)，請(qǐng)讀者舉反例說(shuō)明,AACOBAC時(shí)，不一定有

A<=>B.

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

A(雙重否定律)

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

臺(tái)B(雙重否定律)

所以

A臺(tái)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無(wú)成真賦值,C為矛盾式.

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

l(0WM2n)個(gè)極小項(xiàng)，則A的主合鄧范式中含2nT個(gè)極大項(xiàng)，而且極大項(xiàng)的角標(biāo)

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

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

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

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

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

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

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

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

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

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

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

錯(cuò)誤！鏈接無(wú)效。

0￥V(飛Vr)

—邛V^qVr).

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

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

-p臺(tái)p八(「qVq)A(fVr)

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

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

01230mVmVmVm

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

臺(tái)(「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

類(lèi)似地，可求出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輸入；

山題的條件，容易寫(xiě)出的真值表，見(jiàn)表1.5所示.山真值表分別寫(xiě)出ABCF,F,F

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

表1.5

F(pqr)(pqr))(pqr)(pqr)A臺(tái)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

臺(tái)(「pAq)A(fVr)

臺(tái)(-PAq)

0—(「pAq)

㈡「(pA-q)

3PLq)

0p1(q1q).

F(ppr)C臺(tái)「八」八

<=>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｝中公式時(shí)，應(yīng)分以下幾步：

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

⑵使用

rAor(AAA)OATA,

或

-Aor(AVA)臺(tái)AJ,A.

使用雙重否定律

AAB<=>—(AAB)臺(tái)r(ATB)

<=>(AtB)j(ATB)

或

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

O(A1B)J(A1B)

使用德?摩根律

AABorr(AAB)0r「AV-B)

<=>rALB臺(tái)(A[A)[(B]B)

或

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

0rATrB臺(tái)(AtA)t(BtB)

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

q：礦樣為銅；

r：礦樣為錫.

設(shè)

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

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

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

V(邛A飛APAr八FAr)

<=>OV0<=>0.

()()()2F0甲全對(duì)A乙全錯(cuò)八丙對(duì)一半

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

<=>(rpA^qApATApAr)

V(rp八rqApArAA-T)

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

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

㈡(rpAq八rpArA丁Ar

V(pArqArp/\rA^pAr)

g「pAqAr)V0

<=>-pAqAr.

()()()4FO甲對(duì)一半八乙全錯(cuò)八丙全對(duì)

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

O(-pAq-'A-TApA-r

V(pA^qApAFApA-T)

OOV(p八2AF)

㈡pArq/\F

()()()5F今甲會(huì)錯(cuò)A乙對(duì)一半A丙全對(duì)

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

O(pAqA邛AFAp八f

V(pAqApArApA~T)

<=>0V0

㈡0.

<=>0VOO0

()()()6FO甲全錯(cuò)八乙全對(duì)A丙對(duì)一半

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

<=>(pAqAArApAr

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

<=>0V0

O0.

設(shè)

FO(一人全對(duì))A(一人對(duì)一半)△(一人全錯(cuò))

則F為真命題，并且

123456FOFVFVFVFVFVF

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

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

pAqAr㈡0,因而必有

pArq/\-T<=>1.

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

1-1<5令p：今天是1號(hào)；

q：明天是5號(hào).

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

重言式。

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

(p—q)Ap-q.

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

(p—q)Ap0q.

所以，推理正確。

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

(p—q)Ap->q.

課后答案網(wǎng)

21

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

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

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

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

(p-q)A-p—rq.

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

(p—q)八p0p.

所以，推理正確。

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

(p—q)Arp—rq.

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

推理不正確。

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

為重言式，來(lái)判斷推理是否正確，若能觀(guān)察出一個(gè)成假賦值，立刻可知，推理不

正確。

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)①置換③②化簡(jiǎn)④tAr前提引入⑤t

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

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

?pAqAsAr⑥⑩??合取

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

q：他是文科生

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

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

結(jié)論q

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

證明①p-r前提引入

f前提引入

③-P①②拒取式

④rq—p前提引入

⑤一q③④拒鄧式

⑥q⑤置理

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

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

pV(qAT)

24567<=>mVmVmVmVm

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

001,011,由③給出，公式是非重言式的可滿(mǎn)足式，由③給出。

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個(gè)極小項(xiàng)。極小項(xiàng)角碼的二

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

立即可知成假賦值為000,

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

,故有3個(gè)極大項(xiàng)。024M,M,M

方法2：求主合取范式，分析類(lèi)似主析取范式法。

方法3：真值表法

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

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

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)的國(guó)邏輯結(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個(gè)開(kāi)關(guān)狀態(tài)的命題變項(xiàng)，開(kāi)關(guān)的

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

F臺(tái)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章習(xí)題解答

2.1本題沒(méi)有給出個(gè)體域，因而使用全總個(gè)體域.

⑴令F(x):x是鳥(niǎo)

G(x):x會(huì)飛翔.

命題符號(hào)化為

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

⑵令F(x):x為人.

G(x):x愛(ài)吃糖

命題符號(hào)化為

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

或者

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

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

G(x):x愛(ài)看小說(shuō).

命題符號(hào)化為

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

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

G(x):x愛(ài)看電視.

命題符號(hào)化為

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

分析1。如果沒(méi)指出要求什么樣的個(gè)體域，就使用全總個(gè)休域，使用全總個(gè)

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

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

課后答案網(wǎng)

28

Vx(F(x)AG(x))

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

更透徹些，是說(shuō)“對(duì)于宇宙間的一切事物百言，如果它是鳥(niǎo)，則它會(huì)飛翔?！?/p>

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

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

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

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

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

VxF(x)

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

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

3xG(x)

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

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

3xH(x)

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

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

2°有的命題在不同個(gè)體域中，符號(hào)化的形式不同，考慮命題

“人都呼吸”。

在個(gè)體域?yàn)槿祟?lèi)集合忖，應(yīng)符號(hào)化為

VxF(x)

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

在個(gè)體域?yàn)槿倐€(gè)體域時(shí)，應(yīng)符號(hào)化為

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

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

課后答案網(wǎng)

29

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

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

符號(hào)化為

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

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

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

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

-BxCF(x)ArG(x)),

或另?種等值的形式為

Vx(F(x)-G(x)

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

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

或

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

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

化為

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

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

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

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

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

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

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

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

課后答案網(wǎng)

30

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

(d)中為真命題。

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

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

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

中為假命題。

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

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

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

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

“對(duì)于敘何實(shí)數(shù)x而言，若x為有理數(shù)，則x能表示成分?jǐn)?shù)”，簡(jiǎn)言之為“有

理數(shù)都能表示成分?jǐn)?shù)?！?在此蘊(yùn)含式中，當(dāng)前件F(x)為真時(shí)，后件G(x)也為真，

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

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

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

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

為假命題.

⑵取解釋為:個(gè)體域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)為

真命題。

分析本題說(shuō)明

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不等值，以后遇到㈡，含義相同。

在一階邏輯中，將命題符號(hào)化時(shí)，當(dāng)引入特性謂詞(如題中的F(x))之后，

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

使用t，如果用錯(cuò)了，會(huì)將真命題變成假命題，或者將假命題變成真命題。

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為：個(gè)體域D=N(自然數(shù)集合)，F(xiàn)(x):x為奇數(shù)，G(x):x

為偶數(shù)。

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

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

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

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

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

奇數(shù)，又是偶數(shù)?！?/p>

由于蘊(yùn)含式的前件為真，后件為假，后以真值為假。

分析本題說(shuō)明全稱(chēng)量詞對(duì)析取不滿(mǎn)足分配律，存在量詞對(duì)合取不滿(mǎn)足分配

律。

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

所以A為閉式。

給定解釋?zhuān)簜€(gè)體域D=N(整數(shù)集合)，為正數(shù)，為負(fù)數(shù)，I1F(x):xG(x):x

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

課后答案網(wǎng)

32

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

這是真命題。

設(shè)解釋?zhuān)簜€(gè)體域D=R(R整數(shù)集合)，為有理數(shù)，為無(wú)理數(shù)，I2F(x):xG(y):y

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

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

這是假命題。

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

下真值不確定，這一點(diǎn)是閉式的一個(gè)重要特征。而非封閉的公式就沒(méi)有這個(gè)特征.

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

A

2A

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

AA2

取解釋I為，個(gè)體域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下，為當(dāng)時(shí)，它為真；時(shí)為假，在1下A2Vx(x+y=x),y=0y彳0A2

的真值也不確定。

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

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

當(dāng)然非閉式也可以是邏輯有效式(如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

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

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

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

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

本命題直接符號(hào)化驗(yàn)為

-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))(蘊(yùn)含等值式)

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

為

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

可見(jiàn)得“沒(méi)有人長(zhǎng)著綠色頭發(fā)。'‘與“所有人都不長(zhǎng)綠色頭發(fā)。”是同命題

的兩種不同的敘述方法。

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

G(x):x去過(guò)香山。

命題直接符號(hào)化為

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))(蘊(yùn)含等值式)

課后答案網(wǎng)

34

最后得到的公式滿(mǎn)足要求(只含全稱(chēng)量詞)，將它翻譯成自然語(yǔ)言，即為

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

可見(jiàn)，“有的北京人沒(méi)過(guò)過(guò)香山?！迸c“并不是北京人都去過(guò)香山?！笔峭?/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)(量詞轄域收縮擴(kuò)張等值式)

<=>(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)

臺(tái)(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)

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

(2)中，首先將量詞轄域縮小了(因?yàn)閙yG(y)中不含x,所以，可以縮小)。否

則，演算是相當(dāng)麻煩的。見(jiàn)下面的演算：

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)).

顯然這個(gè)演算比原來(lái)的轡算麻煩多了。

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)(約束變項(xiàng)換名規(guī)則)

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

<=>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

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

等。

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

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)

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

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

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

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

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

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

真的個(gè)體常項(xiàng)，而不能為個(gè)體變項(xiàng)。

(4)②錯(cuò)。①中公式含個(gè)體變項(xiàng)x,不能使用EG規(guī)則。

(5)②錯(cuò)。①公式含兩個(gè)個(gè)體常項(xiàng)，不能使用EG規(guī)則。

課后答案網(wǎng)

37

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

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

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

設(shè)個(gè)體域?yàn)樽匀粩?shù)集合N.F(x):x為偶數(shù)，G(x):x為素?cái)?shù)，H(x):x能被3

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