离散数学课后答案（清华版）

http：//www.khdaw.com

课后答案网http：//www.khdaw.cn

第1章习题解答

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

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

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

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

所以它们都不是命题。

其次，)这个句子是陈述句，但它表示的判断结果是不确定。又因为(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)pnq。其中，p:2是素数，q：三角形有三条边。由于p与q都是真

命题，因而pGq为假命题。

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

题，q为真命题，因而pq为假命题。

(8)p-2000年10月1日天气晴好，今日(1999年2月13日)我们还不

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

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

1

(4

http：//www.khdaw.com

课后答案网http：//www.khdaw.cn

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

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

为假命题，为真命题。

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

为假命题。

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

(15)p：蓝色和黄色可以调配成绿色。这是真命题。

分析命题的真值是唯一确定的，有些命题的真值我们立即可知，有些则不

能马上知道，但它们的真值不会变化，是客观存在的。

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为假当且仅当

P为真,q为假，而为真当且仅当P与q真值相同.由于p与q都是真命题，

在4个蕴含式中，只有(2)pQr,其中，p同(1),r：明天为3号。

在这里，当p为真时，r一定为假，pQr为假，当p为假时，无论r为真

还是为假，p□/•为真。

2

http：//www.khdaw.com

课后答案网http：//www.khdaw.cn

1.5（1）p》q,其中，p：2是偶数，q：2是素数。此命题为真命题。

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

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

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

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

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

看电视。

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

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

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

条件，这种逻辑关系在叙述上也是很灵活的。例如，因为P，所以q"，只要P，

就q”“p仅当q”“只有q才P”“除非q,否则一〃”“没有q,就没有P”等都表

达了q是P的必要条件，因而都符号化为p□夕或一〃口—4的蕴含式。

在（5）中，q是p的必要条件，因而符号化为pDq,而在（6）（7）中，

P成了q的必要条件，因而符号化为qUp0

在（8）中，虽然没有出现联结词，但因两个命题的因果关系可知，应该符

号化为蕴含式。

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

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

3

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

的成真赋值，还是成假赋值，易知001是它的成假赋值。

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

0000,0001,111L现在考查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(八)（蕴含等值式）

TM(<-p(p)(p(r（结合律）

™1(^(r（排中律）

TM]（零律）

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

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

(P□-P)□一，

™(<-/?(<-)—p（蕴含等值式）

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

™/?(一〃（蕴含等值式）

TM]（排中律）

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

<-(p□4)”

™<-(p<-(q)3q（蕴含等值式）

TMp(-q5q（德•摩根律）

™P((~q3-7)（结合律）

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个)极小项，所以(3)为非重言式的

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

其余各式的类型，请读者自己验证。

分析b真值表法判断公式的类别是万能。公式A为重言式当且仅当A的

真值表的最后一旬全为1；A为矛盾式当且仅当A的真值表的最后一列全为0；A

为非重言式的可满足式当且仅当A的真值表最后一列至少有一个1,又至少有一

个0。真值表法不易出错，但当命题变项较多时，真值表的行数较多。

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

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

等值演算可将A化简，然后用观察法找到一个成真赋值，再找到一个成假赋值，

就可判断A为非重言式的可满足式了。例如，对(6)用等值演算判断它的类型。

(p3<-p)□q

™on^(矛盾律)

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

TM(一0(q)»(—q(0)(蕴含等值式)

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

TM13(零律)

（同一律）

到最后一步己将公式化得很简单。由此可知，无论P取0或1值，只要q取

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

值，于是公式为非重言式的可满足式。

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

范式含2“（〃为A中所含命题变项的个数）个极小项；A为矛盾式当且仅当A的

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

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

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

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

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

主合取范式含2,.个极大项（”为A中含的命题变项的个数）；A为非重言式的可

满足式当且仅当A的主析取范式中含含极大项，但不是全部的。

1.8（1）从左边开始演算

(p3q)((p3.q)

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

TM〃31（排中律）

TMp.（同一律）

(2)从右边开始演算

™—p((q3r)（蕴含等值式）

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

TM(P□q)3(〃□r).（蕴含等值式）

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

™<-(<-(p》q)(p)(德•摩根律)

TMp-g》—p(结合律、交换律)

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

™0.(零律)

由最后一步可知该公式为矛盾式。

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

•™一(一(p》q)(p)(蕴含等值式)

由于较高层次等价号两边的公式相同，因而此公式无成假赋值，所以，它为

重言式。

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

TM(p(q)“一q(<-p)(蕴含等值式)

TM~(p(q)((~q(~p)(蕴含等值式)

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

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

™<-p(<-q.(交换律)

由最后一步容易观察到，11为该公式成假赋值，因而它不是重言式，又00,

01,10为成真赋值，因而它不是矛盾式，它是非重言式的可满足式。

1.10题中给出的F,G,H,R都是2元真值函数。给出的5个联结词集都

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

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

(1)设A=<-(pDq),易知A是｛<-,□｝中公式且与F等值，即F™A.

(2)设B=p3—q,易知B是｛<-,»｝中公式且与F等值，即F™B.

(3)设C=­«p(q),易知C是｛一,»｝中公式，且F™C.

(4)设。=(〃口(9口4))口(〃口(4口4))，易知D为｛口中公式，且D

(5)设E=(pDp)□夕，易知E为｛口中公式，旦F™E.

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

找出其他联结词集中与F等值的公式。例如，已知A=一(2口0是｛一,□｝公式，

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

进行等值演算，消去联结词口，用一，3取代，得

A=一(，□q)

™一(一〃(q)

TMp3记为8.

则B为｛—,»｝中公式，且FTMB。再对A进行等值演算，消去口，用-,a

取代，得

A=一(〃□夕)

™<-(<-/?(q)记为C.

则C为｛一,3｝中公式，且F^C。再对B进行演算，消去一，口，用口取代,

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

B=p?<-q

TMp9(g□g)

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

™□初

TM(p□(q□/)口(p□%口q)记为D.

则D为｛□｝中公式，且PTM。再对进行演算，消去一,(，用口取代，在演算

C

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

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

C=(q)

TM□q

TM(P□.)□4记为E.

则E为｛□｝中公式，且F^E.

2°开始找一个与某真值函数等值的公式的方法，除观察法外，就是根据

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

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

G™m\(m3

™.p(p)3q

TMq.

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

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

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

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

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

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

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

则GTMATMBTMCTMQTME,对于同一个真值函数G,找到与它等值的形

式各异的公式。

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

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

当C不是矛盾式时，4(CTMB(C,则一定有A™B,这是因为，此时,

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

ATMA(CTMB(TMB

必有A™B

而当C不是矛盾式时，A(C™B(C,不一定有A™B,举反例如下：

设A,B,C均为含命题变项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是否为重言式进行讨论：

若C为重言式，则A3C™A,C™B,于是

A™A3C™B3C™B.

因而有

ATM8

当C不是重言式时，请读者举反例说明，A»CTMB3c时，不一定有

ATMB.

(3)若—ATM—8,则ATM8.证明如下：

ATM——A(双重否定律)

TM-8(一ATM—8)

TM8(双重否定律)

所以

ATM8

1.12(1)设(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

⑵设⑵中公式为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)设(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设公式A中含/?(/?£1)个命题变项，且A的主析取范式中含

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

的十进制数.

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

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

过的3,4,5,6.这样，只要知道A的主析取范式，它的主合邓范式自然也就知道了，

在(2),(3)中情况类似.

2°A的主析取范式中极小项角标的二进制表示即为A的成真赋值.在⑴中，

由于主析取范式中的极小项角标分别为0,1,2,7,它们的二进制表示分别为

000,001,010,111,所以,A的成真赋值为以上各值.类似地,A的主合取范式中所

含极大项角标的二进制表示,即为A的成假赋值.

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

p□((7□r)

TM―p((r(r)

™—p(—q(r).

由于演算过程较长,可以分别先求出由一p,-q,r派生的极小项.注意,本公式

中含3个命题变项，所以，极小项长度为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机0(如(加(如(用4(机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设p:A输入；

设q:B输入；

设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□夕)□([□初□(/■□厂)\

分析在将公式化成｛口｝或｛口｝中公式时，应分以下几步:

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

q：矿样为铜；

r：矿样为锡.

设

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.

设

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

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

重言式。

(1)推理的形式结构为

(p□q)3P□?

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

(p0q)3p@q.

所以，推理正确。

(2)推理的形式结构为

(〃□4)3〃□0

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

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

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

(3)推理的形式结构为

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

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

(pq)3<—p®—q.

所以，推理正确。

(4)推理的形式结构为

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

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

推理不正确。

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

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

正确。

1.17(1)

证明①一q(r前提引入

②—r前提引入

③①②析取三段论

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

⑤一P(夕④置换

⑥一p②⑤析取三段论

(2)

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

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

③q前提引入

④pQs②③假言推理

⑤p（前提引入

⑥rUp⑤置换

⑦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

所以，当推理的结论也为蕴含式时,可以将结论的前件作为推理的前提,称为

附加前提,并称使用附加前提的证明方法为附加前提证明法.（3）中第一个证明，

即为附加前提证明法.

1.18设P：他是理科生

q：他是文科生

r：他学好数学

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

结论q

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

证明①pUr前提引入

<-r前提引入

③.P①②拒取式

④<—q□p前提引入

⑤J—q③④拒邓式

⑥q⑤置理

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

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

，((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个极小项。极小项角码的二

进制表示为成真赋值，因而成真赋值为001,011,101,110,11L由成真赋值

立即可知成假赋值为000,

010,100,成假赋值的十进制的十进表示为极大项的角码，因而极大项为

,故有3个极大项。

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

方法3：真值表法

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

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

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

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

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

②―r前提引入

③一4①②析取三段论

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

⑤<-/?（q④置换

⑥~p③⑤析取三段论

至此可知-p是（1）的逻辑结论。

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

②・s前提引入

③I①②析取三段论

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

⑤一（p》/④置换

⑥—p(—q⑤置换

至此可知—p（一4是（2）的国逻辑结论

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

②pDq①置换前提引入

③一4(r前提引入

@qDr③置换

⑤pElr②④假言推理

⑥厂□s前提引入

⑦，□5⑤⑥假言推理

至此可知p是（3）的逻辑结论。

1.22答案A：④

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

扳键向上时，对应命题变项的真值为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章习题解答

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°初学者经常犯的错误是，将类似于(1)中的命题符号化为

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

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

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

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

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

“人都呼吸”。

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

DxF(x)

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

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

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

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

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

(1)令：是大学生，G(x):x是文科生，H(x):光是理科生，命题

符号化为

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

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