离散数学课后答案

第1章习题解答

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

(10),(14),(15)是简单命题，(6),(7),(12),(13)是复合命题。

分析首先应注意到，命题是陈述句，因而不是陈述句的句子都不是命题。

本题中，(3)为疑问句，(5)为感叹句，(11)为祈使句，它们都不是陈述句，

所以它们都不是命题。

其次，(4)这个句子是陈述句，但它表示的判断结果是不确定。又因为(1),

(2),(8),(9),(10),(14),(15)都是简单的陈述句，因而作为命题，它们

都是简单命题。(6)和(7)各为由联络词“当且仅当”联结起来的复合命题，

(12)是由联结词“或”联结的复合命题，而(13)是由联结词"且'’联结起来

的复合命题。这里的“且''为"合取”联结词。在日常生活中，合取联结词有许

多表述法，例如，”虽然....但是……”、“不仅......而月......”、“•面.....

一面....”、”……和....."、”……与……”等。但要注意,有时“和”或“与”

联结的是主语，构成简单命题。例如，(14)、(15)中的“与”与“和”是联结

的主语，这两个命题均为简单命题，而不是复合命题，希望读者在遇到“和''或

"与'’出现的命题时，要根据命题所陈述的含义加以区分。

1.2(1)p:2是无理数，p为真命题。

(2)p:5能被2整除，p为假命题。

(6)p-qo其中，p:2是素数，q：三角形有三条边。由于p与q都是真

命题，因而p—q为假命题。

(7)p-q,其中，p：雪是黑色的，q：太阳从东方升起。由于p为假命

题，q为真命题，因而p—q为假命题。

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

但p的真值是确定的(客观存在的)，只是现在不知道而已。

(9)p：太阳系外的星球上的生物。它的真值情况而定，是确定的。

(10)p：小李在宿舍里.p的真值则具体情况而定，是确定的。

(12)pVq,其中，p:4是偶数，q:4是奇数。由于q是假命题，所以，q为假命题，

pVq为真命题。

(13)pVq,其中，p:4是偶数，q:4是奇数，由于q是假命题，所以，pVq为假命题。

(14)p：李明与王华是同学，真值由具体情况而定(是确定的)。

(15)p：蓝色和黄色可以调配成绿色。这是真命题。分析命题的真值是唯一确定的，有些

命题的真值我们立即可知，有些则不能马上知道，但它们的真值不会变化，是客观存在的。

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是偶数，q：2是素数。此命题为真命题。

(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：经一事，q：长一智

分析1。在前4个复合命题中，都使用了合取联结词，都符号化为合取式，

这正说明合取联结词在使用忖是很灵活的。在符号化时，应该注意，不要将联结

词部分放入简单命题中。例如，在(2)中，不能这样写简单命题：p：小王不但

聪明，q：小王而且用功。在(4)中不能这样写：p：他一边吃饭，q：他一边

看电视。

2。后4个复合命题中，都使用了蕴含联结词，符号化为蕴含式，在这里，

关键问题是要分清蕴含式的前件和后件。

p-q所表达的基本逻辑关系为，p是q的充公条件，或者说q是p的必要

条件，这种逻辑关系在叙述上也是很灵活的。例如，“因为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)中，虽然没有出现联结词，但因两个命题的因果关系可知，应该符号化为蕴含式。

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

分析1。(1)中公式含3个命题变项，因而它应该有23=8个赋值：000,

001,...,111题中指派p,q为0,r为1,于是就是考查001是该公式

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

2°在公式(2),(3),(4)中均含4个命题就项，因而共有24=16个赋值：

0000,0001,llllo现在考查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(结合律)

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）（结合律）

<=>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。真值表法不易出错，但当命题变项较多时，真值表的行数较多。

2D用等值演算法判断重言式与矛盾式比较方例，A为重言式当且仅当A与

1等值；A为矛盾式当且仅当A与0等值，当A为非重言式的可满足式时，经过

等值演算可将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中所含命题变项的个数)个极小项；A为矛盾式当且仅当A的

主析取范式中不含任何极小项，记它的主析取范式为0；A为非重言式的可满足

式当且仅当A的主析取范式中含极小项，但不是完全的。

当命题变项较多时，用主析取范式法判公式的类型，运算量是很大的。

用主合取范式判断公式的类型也是万能的。A为重言式当且仅当A的主合取

范式中不含任何极大项，此时记A的主合取范式为1；A为矛盾式当且仅当A的

主合取范式含2n个极大项(n为A中含的命题变项的个数)；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邛(结合律、交换律)

<=>(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元真值函数。给出的5个联结词集都

是全功能集，可以用观察法或等值演算法寻找与真值函数等值的公式。

首先寻找在各联结词集中与F等值的公式。

(1)设A=汽p—>q),易知A是卜,一｝中公式且与F等值，即F台A.

(2)设B=p△飞，易知B是卜,八｝中公式且与F等值，即F台B.

(3)设©=汽中Vq),易知C是卜,八｝中公式，且FOC.

(4)设D=(pT(qfq))T(pT(qfq)),易知D为｛月中公式，且F0D.

(5)设E=(plp)1q,易知E为｛1｝中公式，且FOE.

分析1°只要找到一个联结词集中与F等值的公式，经过等值演算就可以

找出其他联结词集中与F等值的公式。例如，已知A-(p-q)是｛一，一｝公式，

且F㈡A。进行以下演算，就可以找到F等值的其他联结词集中的公式。对A

进行等值演算，消去联结词一,用二八取代，得

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°开始找一个与某真值函数等值的公式的方法，除观察法外，就是根据

该真值函数的真值表，求它的主析取范式，而后进行等值演算即可。例如，由G

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

13GOmVm

<=>(-pAq)V(pAq)

gLpVp)Aq

<=>q.

由于公式q不带联结词，所以，它应该为任何联结词集中的合式公式。

3°在各联结词集中找到的与某真值函数等值的公式并不唯一。例如，取

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

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

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

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

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

则G㈡A㈡B0cOD㈡E,对于同一个真值函数G,找到与它等值的形

式各异的公式。

对于H和R,请读者自己去完成。

1.11(1)对C是否为矛盾式进行讨论。

当C不是矛盾式时，AVC<=>BVC,则一定有A<=>B,这是因为，此时，

AVC0A,BVC0B,所以，有

A<=>AVCOBVOB

必有A㈡B

而当C不是矛盾式时，AVCOBVC,不一定有A<=>B,举反例如下：

设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)设(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)设(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)设(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。设公式A中含n(nNl)个命题变项，且A的主析取范式中含

l(0WM2n)个极小项，则A的主合邓范式中含2nT个极大项，而且极大项的角标

分别为0到2nT这2n个十进制数中未在A的主析取范式的极小项角标中出现过

的十进制数.

在(1)中,n=3,A的主析取范式中含4个极小项,所以,A的主合取范式中必含

23-4=4个极大项,它们的角标为0到7中未在主析取范式的极小项角标中出现

过的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

课后答案网

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设p:A输入；

设q:B输入；

设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｝中公式时，应分以下几步：

(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设p：矿样为铁；

q：矿样为铜；

r：矿样为锡.

设

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.

设

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

由于本题给出的推理都比较简单，因而可以直接判断推理的形式结构是否为

重言式。

(1)推理的形式结构为

(p—q)Ap-q.

可以用多种方法判断上公式为重言式，其实，本推理满足假言推理定律，即

(p—q)Ap0q.

所以，推理正确。

(2)推理的形式结构为

(p—q)Ap->q.

课后答案网

21

可以用多种方法证明上公式不是重言式，其实，当p为假(即今天不是1

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

形式结构不是重方式，故，推理不正确。

(3)推理的形式结构为

(p-q)A-p—rq.

可以用多种方法证明上面公式为重言式，其实，它满足拒取式推理定律，即

(p—q)八p0p.

所以，推理正确。

(4)推理的形式结构为

(p—q)Arp—rq.

可以用多种方法证明上公式不是重言式，01为上公式的成假赋值，所以，

推理不正确。

分析对于前提与结论都比较简单的推理，最好直接判推理的形式结构是否

为重言式，来判断推理是否正确，若能观察出一个成假赋值，立刻可知，推理不

正确。

1.17

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

⑤pVq④置换⑥rp②⑤析取三段论

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

⑤pVf前提引入⑥r-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设p：他是理科生

q：他是文科生

r：他学好数学

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

结论q

通过对前提和结论的观察，知道推理是正确的，下面用构造证明法给以证明。

证明①p-r前提引入

f前提引入

③-P①②拒取式

④rq—p前提引入

⑤一q③④拒邓式

⑥q⑤置理

1.19本题可以用多种方法求解，根据要求回答问题，解本题最好的方法

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

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：真值表法

由真值表，求出成真赋值，将成真赋值转化成十进制数做为极小项的角码，

这样就求出了全部极小项，也容易求出极大项。

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

分析可用构造证明法解此题。

(1)①rqVr前提引入

②F前提引入

课后答案网

25

③rq①②析取三段论

④r(pA2)前提引入

⑤丁Vq④置换

⑥P③⑤析取三段论

至此可知rp是(1)的逻辑结论。

(2)①fVs前提引入

②F前提引入

③F①②析取三段论

@(pAq)—r前提引入

⑤NpAq)④置换

⑥丁V飞⑤置换

至此可知邛V飞是(2)的国逻辑结论。

(3)①rpVq前提引入

②p-q①置换前提引入

③FVr前提引入

@q—r③置换

⑤p-r②④假言推理

⑥r—s前提引入

⑦p-s⑤⑥假言推理

至此可知PTS是(3)的逻辑结论。

1.22答案A：④

分析在本题中，设A,B,C分别表示3个开关状态的命题变项，开关的

扳键向上时，对应命题变项的真值为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°初学者经常犯的错误是，将类似于(1)中的命题符号化为

课后答案网

28

Vx(F(x)AG(x))

即用合取联结词取代蕴含联结词，这是万万不可的。将(1)中命题叙述得

更透彻些，是说“对于宇宙间的一切事物百言，如果它是鸟，则它会飞翔。‘‘因

而符号化应该使用联结词一而不能使用八。若使用八，使(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°命题的真值与个体域有关。

2°有的命题在不同个体域中，符号化的形式不同，考虑命题

“人都呼吸”。

在个体域为人类集合忖，应符号化为

VxF(x)

这里，F(x):x呼吸，没有引入特性谓词。

在个体域为全总个体域时，应符号化为

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

这里，F(x):x为人,且F(x)为特性谓词。G(x):x呼吸。

课后答案网

29

2.3因题目中未给出个体域，因而应采用全总个体域。

(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无谓词，用它们来描述事物之间的关系。

2.4(1)对所有的x,存在着y,使得x-y=0,在(a),(b)中为真命题，在

(c),(d)中为假命题。

(2)存在着x,对所有的y,都有x•y=0,在(a),(b)中为真命题，在

(c),(d)中为假命题。

课后答案网

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)取解释为：个体域(实数集合)，为有理数，lID=RF(x):x

G(x):x能表示成分数，在下，的含义为1IX/x(F(x)-G(x))

“对于叙何实数x而言，若x为有理数，则x能表示成分数”，简言之为“有

理数都能表示成分数。’'在此蕴含式中，当前件F(x)为真时，后件G(x)也为真，

不会出现前件为真，后件为假的情况，所以在下，为真命题。IIVx(F(x)^G(x))

在在下，的含义为1IVx(F(x)AG(x))

“对于任何实数x,x既为有理数，又能表示成分数。”

取x=2,则F(2)Ag(2)显然为假，所以，在下，IIVx(F(x)AG(x))

为假命题.

⑵取解释为:个体域D=N(自然数集合),为奇数，为偶2IF(x):xG(x):x

数,在下，的含义为123x(F(x)AG(x))

“存在自然数x,x发既为奇数，又为偶数。”

取x=2,则F(2)为假，于是F(2)TG(2)为真,这表明mx(F(x)-G(x)为

真命题。

分析本题说明

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

课后答案网

31

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

这里，A㈡B表示A与B不等值，以后遇到㈡，含义相同。

在一阶逻辑中，将命题符号化时，当引入特性谓词(如题中的F(x))之后，

全称量词▼后往往使用联结词一而不使用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(自然数集合)，F(x):x为奇数，G(x):x

为偶数。

(1)在解释I下，公式被解释为

“如果所有的自然数不是奇数就是偶数，则所有自然数全为奇数，或所有自

然数全为偶数。’’因为蕴含式的前件为真，后件为假，所以真值为假。

(2)在I下，公式解释为

“如果存在着自然数为奇数，并且存在着自然为偶数，则存在着自然数既是

奇数，又是偶数。”

由于蕴含式的前件为真，后件为假，后以真值为假。

分析本题说明全称量词对析取不满足分配律，存在量词对合取不满足分配

律。

2.8令人=Vx\/y(F(x)AG(y)—L(x,y)),在A中，无自由出现的个体变项，

所以A为闭式。

给定解释：个体域D=N(整数集合)，为正数，为负数，I1F(x):xG(x):x

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

课后答案网

32

“对于任意的整数x和y,如果x为正整数，y为负整数，则x>y。”

这是真命题。

设解释：个体域D=R(R整数集合)，为有理数，为无理数，I2F(x):xG(y):y

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

“对于任意的实数x和y,如果x为有理数，y为元理数，则xNy。"

这是假命题。

分析闭式在任何解释下不是真就是假，不可能给出解释I,使得闭式在I

下真值不确定，这一点是闭式的一个重要特征。而非封闭的公式就没有这个特征.

2.9取((，),(，))和，则和都是非土产的1A=Lfxygxy((,),)2A=Vxfxyx1

A

2A

公式，在中，x,y都是自由出现的，在中，y是自出现的。1

AA2

取解释I为，个体域D=N(N为自然数集合),

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

的真值也不确定。

分析非闭式与闭式的显著区别是，前者可能在某些解释下，真值不确定，

而后者对于任何解释真值都确定，即不是真就是假。

当然非闭式也可以是逻辑有效式(如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))(消去量词等值式)

课后答案网

33

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

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

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

G(x):x长着绿色头发。

本命题直接符号化验为

-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))(蕴含等值式)

最后一步得到的公式满足要求(使用全称量词)，将它翻译成自然语言，即

为

“所有的人都不长绿色头发

可见得“没有人长着绿色头发。'‘与“所有人都不长绿色头发。”是同命题

的两种不同的叙述方法。

(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))(蕴含等值式)

课后答案网

34

最后得到的公式满足要求(只含全称量词)，将它翻译成自然语言，即为

“并不是北京人都去过香山。”

可见，“有的北京人没过过香山。”与“并不是北京人都去过香山。”是同一

命题不同的叙述方法。

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)

分析在有穷个体域内消去量词时，应将量词的辖域尽量缩小，例如，在

(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)(约束变项换名规则)

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)

课后答案网

36

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

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

在以上演算中分别使用了德•摩根律、量词否定等值式、约束变项换名规则

等。

分析公式的前束范式是不唯一的。(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)

在以上演算中分别使用了自由变项换名规则和量词辖域收缩扩张等值式。

2.16(1)②错。使用UI,UG,ELEG规则应对前束范式，而①中公式下

不是前束范式，所以，不能使用UI规则。

(2)0①中公式为WxA(x),这时,A(x)=F(x)VG(x),因而使用UI规则时,

应得A(a)(或A(y)),故应有F(a)VG(a),而不可能为F(a)VG(b).

(3)②错。应对A(c)=F(c)一G(c)使用EG规则，其中c为特定的使A为

真的个体常项，而不能为个体变项。

(4)②错。①中公式含个体变项x,不能使用EG规则。

(5)②错。①公式含两个个体常项，不能使用EG规则。

课后答案网

37

(6)⑤错。对①使用EI规则得F(c)八G(c),此c应使F(c)AG(c)为真，

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

分析由于⑤的错误，可能由真前提，推出假结论。反例如下：

设个体域为自然数集合N.F(x):x为偶数，G(x):x为素数，H(x):x能被3

整除，R(x):x能被4整数，显然