吉林某大学离散数学课后习题答案

第二章命题逻辑

§2.2主要解题方法

2.2.1证明命题公式恒真或恒假

主要有如下方法：

方法一.真值表方法。即列出公式的真值表，若表中对

应公式所在列的每一取值全为1,这说明该公式在它的所有

解释下都是真，因此是恒真的；若表中对应公式所在列的每

一取值全为0,这说明该公式在它的所有解释下都为假，因

此是恒假的。

真值表法比较烦琐，但只要认真仔细，不会出错。

例2.2.1说明G=(PAQ->R)A(P->Q)->(P->R)是恒真、

恒假还是可满足。

解：该公式的真值表如下：

PQRPAQP-(P八Q.PfRG

-RQR)A(P

-Q)

00011111

00111111

01011111

01111111

10010011

10110011

11001001

11111111

表2.2.1

由于表2.2.1中对应公式G所在列的每一取值全为1,故

G恒真。

方法二.以基本等价式为基础，通过反复对一个公式

的等价代换，使之最后转化为一个恒真式或恒假式，从而实

现公式恒真或恒假的证明。

例2.2.2说明G=((P->R)v-nR)->J(Q-P)AP)

是恒真、恒假还是可满足。

解：由(P-»R)7fRJPVRv-iR=1,以及

-i(QfP)AP=-i(-iQvP)AP=QA-IPAP=0

知，((P->R)R)->J(Q-P)AP)=0,故G

恒假。

方法三.设命题公式G含n个原子，若求得G的主析取范

式包含所有2n个极小项，贝IJG是恒真的；若求得G的主合取范

式包含所有2n个极大项，贝IJG是恒假的。

方法四.对任给要判定的命题公式G,设其中有原子巳，

P2,…，Pn,令匕取1值，求G的真值，或为1,或为0,或

成为新公式①且其中只有原子P2，…，Pn,再令用取0值，

求G真值，如此继续，到最终只含。或1为止，若最终结果

全为1,则公式G恒真，若最终结果全为0,则公式G恒假，

若最终结果有1,有0,则是可满足的。例子参见书中例2.4.3O

方法五.注意到公式G蕴涵公式H的充要条件是：公式

G->H是恒真的；公式G,H等价的充要条件是：公式GoH是

恒真的，因此，如果待考查公式是GfH型的，可将证明GfH

是恒真的转化为证明G蕴涵H加果待考查公式是GsH型的,

可将证明G-H是恒真的转化为证明G和H彼此相蕴涵。

例2.2.3证明G=(P-R)->((Q->R)->((PvQ)->

R))恒真。

证明：要证明(P->R)->((Q->R)->((PvQ)->R))

恒真，只需证明(P->R)n((Q->R)f((PvQ)R))。

我们使用形式演绎法。

(1)P->R规则1

(2)Q->R附加前提

(3)-,PvR规则2,根据(1)

(4)「QvR规则2,根据(2)

(5)JPvR)AJQvR)规则2,根据(3)、

(4)

(6)JPA「Q)vR规则2,根据(5)

(7)「(PvQ)vR规则2,根据(6)

(8)(PvQ)->R规则2,根据(7)

(9)(Q-R)->((PvQ)->R)规则3,根据⑵、

(8)

2.2.2公式蕴涵的证明方法

主要有如下方法：给出两个公式A,B,证明A蕴涵B,我

们有如下几种方法：

方法一.真值表法。将公式A和公式B同列在一张真值表

中，扫描公式A所对应的列，验证该列真值为1的每一项，

它所在行上相应公式B所对应列上的每一项必为1(真)，则

公式A蕴涵Bo

例2.2.4设A=(PAQ-»R)A(P-»Q),B=(P'R),证明A=>BO

证明：

pQRPAQP-AB

-RQ

0001111

0011111

0101111

0111111

1001001

1011001

1100100

1111111

表2.2.2

由表2.2.2可以看出，使A为真的解释均使B亦为真，因

止匕，A=>BO

方法二.证明AfB是恒真公式。

由例2.2.1知,(P/\Q->R)A(P->Q)f(P-R)恒真，因此,

立即可得到例2.2.4中的结论：(PAQFR)A(PfQ)n(PfR),

即A=>B0

例2.2.5设A、B和C为命题公式，且AnB。请分别阐

述(肯定或否定)下列关系式的正确性。

(1)(AAC)N(BAC);

(2)(A->C)=>(B->C)O

解：由AnB知，A-B是恒真公式，故A=1时，B不可能

为0。

真值表如下：

ABCAfB(AAC)(AfC)

-»

(BAC)(BfC)

000111

001111

010110

011111

110111

111111

表2.2.3

从真值表可以看出，(AAC)->(BAC)是恒真公式，所以

(A->C)n(B->C)(AAC)N(BAC)正确；(A->C)->(B.C)

不是恒真公式，所以，(A-C)n(B-»C)不正确。

例2.2.6设A=(R->P)fQ,B=PfQ,证明A蕴涵B。

证明：我们来证明A-B恒真。

((R->P)-Q)-»(P-»Q)=「J(「RvP)vQ)

v(—lPvQ)

=((-iRvP)A-IQ)v(-iPvQ)

=(-IRA-HQ)v(PA-!Q)

V-1(PA-1Q)

方法三.利用一些基本等价式及蕴涵式进行推导。

对于例2.2.6,由基本等价式可得：

A二(RfP)-Q

j(-iRvP)vQ

=(RA-IP)VQ

=(RvQ)A(-IPvQ)

二(RvQ)A(P->Q)

由教材中基本蕴涵式2.P/\QnQ可知，(RvQ)△(P'Q)

n(P->Q),即A蕴涵B。

方法四.任取解释I,若I满足A,往证I满足B。

例2.2.7设A=P-Q,B=(R-Q)-»((PvR)-Q),证

明A蕴涵Bo

证明：任取解释I,若I满足A,则有如下两种情况：

(1)在解释I下，P为假，这时，B等价于(RfQ)一

(RfQ),因此，I亦满足B。

(2)在解释I下，P为真，Q为真，所以，PvRfQ

为真，故B为真，即，I满足B。

综上，I满足B,因此，A蕴涵B。

方法五.反证法，设结论假，往证前提假。

对于例2.2.6,证明(R->P)Q蕴涵P->Q,若使用方

法三，是很烦琐的，而使用方法四，就很简单。假设存在解

释I使PfQ为假，则只有一种情形，P在I下为真，且Q

在I下为假，这时R->P在I下为真，故I弄假(RfP)一

Qo因此，(R->P)-»Q蕴涵P->Qo

方法六.分别将公式A和公式B转化为它们各自的主析

取范式或主合取范式。若公式A的主析取范式所包含的所有

极小项也包含在公式B的主析取范式中；或者，公式B的主

合取范式中所包含的极大项均包含在公式A的主合取范式

中，则公式A蕴涵公式B。

使用这种方法需要注意，当公式A和公式B中包含的原子

不完全相同时，在求两公式的极小项或极大项时，要考虑该

两公式包含命题原子的并集中的所有原子。

在例2.2.6中，A和B的主析取范式分别为：

A二(-1PA-IQAR)v(-1PAQA-IR)V

(-1PAQAR)v(PAQA-IR)v(PAQAR),

B二(-1PA—iQA—iR)v(—iPA-IQAR)VJPAQA-IR)V

(—IPAQAR)v(PAQA—iR)v(PAQAR),

可见，AnB。

A和B的主合取范式分别为：

A二(PvQvR)A(-1PvQvR)A(-1PvQv-iR),

(—1PvQvR)A(—1PvQv—iR)

可见，A=>BO

另外若给出前提集合S二｛G1,…，Gk),公式G,证明SnG

有如下两种方法：

1.G]A…AGk=>G

2.形式演绎法：根据一些基本等价式和基本蕴涵式，

从S出发，演绎出G。

教材中已经给出了这方面的例子，在此不再赘述。

2.2.3求主合取范式和主析取范式

1.极小项与极大项的性质

以3个原子为例，则对应极小项和极大项的表为:

PQR极小项极大项

AA

000nio=1P-1QiRM0=PvQvR

001R1］二—।PA-1QARMi二PvQv「R

1

010用2=-P△QA-iRM2=Pv-iQvR

1

011叱二~P△QARM3=Pv-nQv^R

1

100用4=P△QA-iRM4JPVQVR

101nig—PA―।QARM5

AAVV

110oig--PQ-iRM6=^P^QR

111m7=PAQARM7JPV-IQV「R

表2.2.4

由表2.2.4可知,对n个命题原子忤，…，Pn,极小项有

如下性质：

(1)n个命题原子P1,…，Pn有2"个不同的解释，每个解

释对应P1，…，Pn的一个极小项。

(2)对P1,…，匕的任意一个极小项m,有且只有一个解

释使01取1值，若使极小项取1的解释对应的二进制数为i,

则m记为n，于是关于…，Pn的全部极小项为吗，…,

叫"T。

(3)任意两个不同的极小项的合取式恒假：miAm-0,

iWj。

2”—I

(4)所有极小项的析取式恒真：v^=1o

i=O

极大项有如下性质：

(1)n个命题原子忤，…，Pn有2"个不同的解释，每个解

释对应巳，Pn的一个极大项。

(2)对肉，…，巳的任意一个极大项M,有且只有一个解

释使M取0值，若使极大项取0的解释对应的二进制数为i,

则M记为Mi，于是关于巳，…，Pn的全部极大项为Mo,M1,…，

(3)任意两个不同的极大项的析取式恒真：此vM-1,

iWj。

(4)所有极大项的合取式恒假1AM=0。

/•=O

2.主合取范式与主析取范式之间的关系

由极小项和极大项的定义可知，二者有如下关系：

m।-—1M।,M।——iiTi।

由此可知，若PvQvR为一公式G的主合取范式，则

G=-1—iG

-—1-1MQ

二―।(M^AM2A''"AMg)

——iM-|v_1M2v**■v-iMg

=mzm2v-vm6

为G的主析取范式。

若JPAQ)vJPA「Q)V(PAQ)为一公式H的主

析取范式，则

H—H

二(JPAQ)v(-1PA-IQ)

v(PAQ))

——।(—।(01QvvIB3))

——1(叱)

2

=-iPvQ

为H的主合取范式。

一般地，若公式A中含n个命题原子，且A的主析取范式

中含有k个极小项：叫…血,，则「A的主析取范式中必含有

*1'k

其余的2"-k个极小项，不妨设为：叫，…,叫，即

71J2n-k

因此，

A=―।-iA

——1(m；v...vm)

力

J2».k

=—IAH.A...A—.

力

J2n_k

—A/iA...AA/.o

n

JiJ2-k

由此可知，从一公式A的主析取范式求其主合取范式的步骤

如下：

(1)求出A的主析取范式中没有包含的所有极小项。

(2)求出与(1)中极小项下标相同的极大项。

(3)将(2)求出的所有极大项合取起来，即得A的主合取

范式。

类似地，从一公式A的主合取范式求其主析取范式的步骤为：

(1)求出A的主合取范式中没有包含的所有极大项。

(2)求出与(1)中极大项下标相同的极小项。

(3)将(2)求出的所有极小项析取起来，即得A的主析取

范式。

3.求主合取范式和主析取范式的方法

方法一.真值表法。主析取范式恰好是使得公式为真的解

释所对应的极小项的析取组成，主合取范式恰好是使得公式

为假的解释所对应的极大项的合取组成。

方法二.公式推导法。设命题公式G中所有不同原子为

P1(…，Pn，贝IJG的主析取范式的求法如下：

(a)将公式G化为析取范式。

(b)删去析取范式中所有恒假的短语。

(c)用等幕律将短语中重复出现的同一文字化简为一

次出现，如，PAP=PO

(d)对于所有不是关于忤，…，Pn的极小项的短语使用

同一律，补进短语中未出现的所有命题原子，并使用分配律

展开，即，如果短语GJ不是关于匕，…，Pn的极小项，则

GJ中必然缺少原子，不妨设为Pm…，Pjk，于是

GJ—GJA(Pjiv—1Pj!)A,,'A(PjkV—1Pjk)

二叫.

这样，就将非极小项GJ化成了一些极小项之析取。将相同

的短语的多次出现化为一次出现，就得到了给定公式的主析

取范式。

主合取范式的求法类似，留给读者作为练习。

由上面讨论可知，只要求出一种范式，可立即得到另外一

种范式。

例2.2.8求公式G=P-(Q-R)的主析取范式与主合取范

式。

解：(1)使用真值表法。见表2.2.5。

pQRP-(Q-R)

0001

0011

0101

0111

1001

1011

1100

1111

表2.2.5

根据真值表中使得公式为真的解释，所对应的极小项的

析取即为其主析取范式：

G二(-1PA—।QA-IR)v(-1PA—iQAR)V(—)PAQA-IR)V

(-1PAQAR)v(PA-IQA-IR)v(PA-IQAR)V(PAQAR)

二movm2vm3vm4vm5vm7

根据真值表中使得公式为假的解释，所对应的极大项的

合取即为其主合取范式：

G=Pv-1QvR=M6

(2)公式推导法

G二P一(Q-R)

=-iPv-1QvR

=(-1PA(QV「Q)A(RV-iR))v

(—iQA(PV-IP)A(RV-iR))v

(RA(PV「P)A(QV[Q))

二(-1PA-IQA-IR)v(-1PA-IQAR)V(—IPAQA-IR)V

(-1PAQAR)v(PA—iQA-iR)v(PAQAR)

二movm2vm3vm4vm5vm7

G=P-(Q-R)

=—!Pv-iQvR

二M6

4.主合取范式与主析取范式的应用

(1)由2.2.1可知，利用主合取范式与主析取范式可

求解判定问题。

(2)证明等价式成立。由于任意公式的主范式是唯一

的，所以可以分别求出两个给定的公式的主范式，若二者主

范式相同，则给定的两公式是等价的，否则，给定的两公式

不等价。

例2.2.9判断P-(Q-R)与(PvQ)一R是否等价。

证明：我们利用求主合取范式的方法来判断。

由例2.2.8知，P-(Q-R)的主合取范式为：M6O下

面求(PvQ)-R的主合取范式。

(PvQ)-R=「(PvQ)vR

二(-1PA-IQ)VR

=(―iPvR)A(―iQvR)

二(「Pv(QA「Q)VR)A((PA-HP)

v—IQVR)

=(-1PvQvR)A(-1Pv-iQvR)

A(Pv-iQvR)

—M?AM4AMg

二者的主合取范式不相同，因此，这两个公式不等价。

2.2.4联结词的转化和全功能集

关于联结词的转化和全功能集方面一般有如下题型：

(1)要求只用几个联结词表示某个命题公式，见例

2.2.10o

(2)给出一个新的联结词的定义，要求证明其是全功能

集，并用其表示某个命题公式。这种题目的做法如下：由于

不难证明出{「，△},{「，▽},{「，一},{T},{U都是全

功能联结词集合，因此，若要证明新定义的联结词是全功能

集，只需证明上面某个全功能集合(比如［［，A})中的每个

联结词(如，「和A)都可以用新联结词表示。若想用其表示

某个命题公式，可以先将基本联结词(rA,V)用给定的

新联结词表示，然后按要求把原命题公式转化成用新联结词

表示的形式。见例2.2.11。

(3)证明一个联结词集合不是全功能集。一般用归纳法,

证明在有限步内，用这个联结词结合不可能表示所有的命

题。见例2.2.12。

应该说明的是，寻求最少联结词的全功能联结词集合，主

要不是个理论问题，而是为了满足工程实践的需要。但是，

一般情况下，为了不至于因为联结词的减少而使得公式的形

式变得复杂，我们仍常采用“「，A,v,一”这5个联

结词。

例2.2.10将公式(P-(Qv「R))A(^PAQ)用仅含

联结词「和V的公式等价表示。

解：(P一(Qv「R))AJP/\Q)=JPv(Qx/1R))A

JPAQ)

二(-IPA(-IPAQ))v

((Qv-.R)AJPAQ))

=(「PAQ)V(QA

JPAQ))v(「RAJPAQ))

=(-IPAQ)v(-IPAQ)

V((—IPAQ)A-1R)

=-IPAQ

=-1(Pv-nQ)

例2.2.11定义三元联结词如表2.2.60

ef(ee,e)

ei2e3b23

0001

0011

0100

0110

1001

1011

1101

1110

表2.2.6三元联结词fe，e2,e3)的真值表

(1)试证明｛f｝是完备的，即，联结词集合｛「，A｝或｛「,

v｝可由该联结词表示。

(2)用该联结词表示公式：(P-R)AQO

(1)证明：因为

「P二f(P,P,P),PvQ二f(「P,「P,「Q),

所以联结词集合｛「，W可由该三元联结词f表示。

而联结词集合J,S是完备的，因此，｛f｝是完备

的。

(2)解:因为

PvQ二fjp,「p,「Q),

所以

p一Q—PvQ=f(P,P,「Q).

又由

PAQ=-1JPv「Q)=-1(-iQv-iP)

二「f(P,P,Q)=「f(Q,Q,P).

因此

(P-R)AQ=f(P,P,「R)AQ

Q,f(P,P,[R))

二「f(Q,Q,f(P,P,f(R,R,R)))

=f(f(Q,Q,f(P,P,f(R,R,R))),f(Q,Q,f(P,

P,f(R,R,R))),f(Q,Q,f(P,P,f(R,R,R))))o

例2.2.12｛A,一｝是否是联结词的全功能集合？证明

你的结论。

在证明此题之前，我们先直观分析一下。考虑△和一这

两个联结词的特点：当一个命题公式中只含有联结词△和一

时，则当公式中出现的所有命题原子都取真值1时，公式也

必然取真值10这就是说，仅含A和一的公式不能表示所有的

命题公式，比如恒假式：因此，联结词集合｛A,-｝

不是全功能集。

证明：下面证明｛A,-｝不是联结词的全功能集。

对公式中出现的联结词个数使用数学归纳法来证明下

面的结论：当一个命题公式中只含有联结词△和一时，则当

公式中出现的所有命题原子都取真值1时，公式也必然取真

值L

n=0时，即公式中不含任何联结词时，公式为原子，结

论显然。

假设nWk时，命题成立，即，如果一个公式中含有n

个联结词A,则当公式的所有原子真值取1时，公式也

取真值1。

当n=k+1时，设任一含k+1个联结词的公式为A,则存

在公式B和C，使得：

A二B-C或A=BAC,

且B和C中的联结词个数均Wk。

由归纳假设知，当所有原子取真值1时，B和C在该解释

下的真值均为1,因此，A在该解释下的真值亦为1。归纳完

成。

由该结论知，如果一个命题公式中只含有联结词A和一，

那么至少存在一个解释满足该公式。因此，只含有联结词A

和一的公式肯定不能表示恒假公式。所以，｛八，一｝不是联

结词的全功能集。

2.2.5综合应用题

综合题主要是先符号化，再使用上面的知识进行联结词

的转化、或求主合取范式、主析取范式、利用基本等价式化

简、或进行逻辑推理来论证或做逻辑判断等。

例2.2.13一个排队线路，输入为A,B,C,其输出分

别为FA，FB,FCO在同一时间内只能有一个信号通过。如果

同时有两个或两个以上信号通过时，则按A,B,C的顺序输

出。例如，A,B,C同时输入时，只能A有输出。写出FA，FB，

心的逻辑表达式，并化成全功能集乩｝中的表达式。

解：先将已知事实中的各简单命题符号化，设：

P：A输入；

Q：B输入；

R：C输入。

然后根据已知条件，写出FA，FB，Fc的真值表如表2.2.7。

pQR

FAFBFc

000000

001001

010010

011010

100100

101100

110100

111100

表2.2.7

于是，

FA二(PA—1QA—iR)v(PA—।QAR)V(PAQA—<R)

v(PAQAR)

二((P/\「Q)AJRVR))v((PAQAJRVR))

二(PA-IQ)v(PAQ)

二PA(-IQVQ)

二P

一(PvP)

J(PJP)

二「((PJP)V(PJP))

二(PJP)J(PJP).

FB=(—IPAQA—IR)v(-IPAQAR)

=(-.PAQ)A(-IRVR)

JP/\Q

――i—i(-iPAQ)

j(Pv-iQ)

二Pj-iQ

二PJ(QJQ)

FC^PAIQAR

二-)(PvQv->R)

二(PvQ)JJR)

二(「「(PvQ))JJR)

二(「(PJQ))JJR)

二((PJQ)J(PJQ))J(RJR)

例2.2.14—一个公安人员审查一件盗窃案，已知的事

实如下：

(1)A或B盗窃了x

(2)若A盗窃了x,则作案时间不能发生在午夜前

(3)若B证词正确，则在午夜时屋里灯光未灭

(4)若B证词不正确，则作案时间发生在午夜前

(5)午夜时屋里灯光灭了

(6)A并不富裕

试用演绎法找出盗窃犯。

解：先将已知事实中的各简单命题符号化，设：

P:A盗窃了x

Q:B盗窃了x

R:作案时间发生在午夜前

S：B证词正确

T：在午夜时屋里灯光未灭

U：A并不富裕

再将各前提写出：

G1:PVQG2:P一「R

G3:S-TG4:：「S-RG5：「TG6:U

演绎过程为：

(1)S-T(规则1)

(2)(规则1)

(3)「S(规则2)

(4)「S-R(规则1)

(5)R(规则2)

(6)P一「R(规则1)

⑺「P(规则2)

(8)PVQ(规贝ij1)

(9)Q(规则2)

因此，是B盗窃了xo

例2.2.15一甲、乙、丙、丁四个人有且仅有两个人参

加围棋优胜比赛。关于谁参加比赛，下面四种判断都是正确

的：

(1)甲和乙只有一人参加；

(2)丙参加，丁必参加；

(3)乙或丁至多参加一人；

(4)丁不参加，甲也不会参加。

请推断出哪两个人参加了围棋比赛。

解：先将已知事实中的各简单命题符号化，设：

P:甲参加了比赛；

Q:乙参加了比赛；

R：丙参加了比赛；

S：丁参加了比赛.

依已知条件⑴-(4)有:

(1)JP八Q)v(P/\]Q)

(2)R-S

(3)「(QAS)

(4)「S-「P

将(1)-(4)式合取起来有：

((「PAQ)v(PA^Q))A(R-S)(QAS)AJS

一［P)

=((—IPAQ)v(PA—iQ))A(-iRvS)A(—)QV-IS)A(SV—)P)

=(PA-iQA-IRAS)v(PA—iQAS)v(—)PAQA—IRA—)S)

根据已知，甲、乙、丙、丁四个人有且仅有两个人参加比

赛，知，「PAQ△「RA「S为假，所以只有(PA「QA「RAS)

V(P/K「Q△S)为真，即甲和丁参加了比赛。

§2.3第二章习题解答

2.3.1习题2.1解答

1.设P是命题“天下雪”；Q是命题“我上街”；R是命题“我有时间”。

(1)用逻辑符号写出以下命题：

a.如天不下雪并且我有时间，那么我上街。

b.我去上街，仅当我有时间。

c.天不下雪。

d.天正在下雪，我也没去上街。

解：a可表示为：(-1PAR)fQ；

b可表不为：Q—>R；

c可表示为：-J5；

d可表不为：PA—iQo

(2)对下述命题用中文写出语句。

a.(RA-iP)

b.RAQ

c.(Q->R)A(R->Q)

d.「(RvQ)

解：a为：我上街当且仅当我有时间并且天不下雪；

b为：我有时间并且上街了；

c为：我上街了当且仅当我有时间；

d为：我每忖间乂没上街。

2.说出下述每一命题的逆命题和逆否命题：

(1)如果天下雨，我将不去。

(2)仅当你去我将逗留。

(3)如果n是大于2的正整数，则方程x"yn=zn无正整数解。

(4)如果我不获得更多帮助，我不能完成这个任务。

解：(1)逆命题为：如果我不去，那么天下雨；逆否命题为：如果我去，那么天不下

雨。

(2)逆命题为：仅当我将逗留你去；逆否命题为：你不去我将不逗留。

(3)逆命题为：如果方程xn+yn=zn无正整数解，则n是大于2的正整数：逆否命题为：如果

方程x，yn=zn有正整数解，贝Ijn是不大于2的正整数。

(4)逆命题为：我不能完成这个任务，因为我没有获得更多帮助。逆否命题：如果我完成了

任务，则我获得了更多帮助。

3.给P和Q指派真值1,给R和S指派真值0,求出下面命题的真值：

a)(PA(QAR))V-3((PVQ)A(RVS))

b)(—I(PAQ)V―iR)v(((->PAQ)V―IR)AS)

c)(-1(PAQ)V-1R)V((Q<^-1P)-»(RV-1S))

d)(Pv(Q-(R/\]P)))—(Qv「S)

解：

a)令G=(PA(QAR))V-I((PVQ)A(RVS))

则：Ti(G)=(1A(1A0))v-.((1v1)A(OVO))

=Ov—iO=1

b)令G=(-.(PAQ)V^R)V(((-)PAQ)V^R)AS)

则：Ti(G)=(-,(1A1)v-,0)vWC-,1A1)ViO)AO)

=lvO=l

c)令G=(「(PAQ)V「R)V((Q-「P)'(Rv[S))

=(—I(PAQ)V―iR)v(―।((—iQv-iP)A(PvQ))v(Rv—iS))

二(―iPv—iQv—)R)v((QAP)v(―iPv—iQ)v(Rv―iS))

则：

T|(G)=(—ilv-nlv—iO)v((IAI)v(—ilv—il)v(0v—!0))=1vl=l

d)令G=(PV(Q^(RA-1P)))<^(QV-.S)

=(Pv(Q->(RA—iP)))<->(Qv-iS)

=(PV(-1QV(RA^P)))<->(QV-1S)

=(―।(Pv(—IQV(RA—iP)))v(Qv―iS))A(—।(Qv-iS)v(Pv(—IQV(RA―)P))))

=(—)PA(QA(-IRVP)))v(Qv-)S))A((—।QAS)v(PV(-)QV(RA-IP))))

TJ(G)=(-n1A(1A(lOvl)))V(ID))A((-.1A0)

v(1V(-I1V(0A-I1))))

=1A1=1

2.3.2习题2.1解答

1.构成下列公式的真值表：

(1)QA(PfQ)-P

⑵一,(PVQAR).(PvQ)A(PvR)

(3)(PvQfQAR)-P人-.R

(4)((-)P-»PA-.Q)fR)AQV-,R

解：(1)设6=(^(P-Q)-P,其真值表如下：

pQG

001

010

101

111

(2)设G=「(PVQAR)—(PvQ)A(PvR),其真值表如下:

PQRGPQRG

00001001

00101010

01001101

01101110

(3)设G=(PvQfQ人R)FPA「R,其真值表如下：

PQRGPQRG

00001001

00101011

01011101

01101110

(4)设6=((「PfP人[Q)fR)AQV-.R,其真值表如下:

PQRGPQRG

00011001

00101010

01011101

01111111

2.指出下列公式哪些是恒真的哪些是恒假的：

(1)PA(PfQ)-Q

⑵(P-Q)f(-PvQ)

⑶(PfQ)A(Q-R)t(P->R)

(4)(P-Q)c(PAQV-,PA-,Q)

解：(1)是恒真的，(2)是恒真的，(3)是恒真的，(4)是可满足的。

3.对P和Q的所有值，证明PfQ与「PvQ有同样的真值。证明(P-Q)cJPvQ)

是恒真的。

解：对P-Q的任意解释I,若I使PfQ为真，贝IJI使P为假或P和Q同时为真，若

I使P为假，则使「P,此时「PvQ为真，若I使P和Q同时为真，则Q为真，此时「PvQ为

真,也就是说PfQ为真时「PvQ为真。若I使PfQ为假，则I使P为真Q为假，此时「PvQ

为假，也就是说PfQ为假时「PvQ为假。综上知PfQ与「PvQ同真同假，由定义知(Pf

Q)—JPvQ)是恒真的。

4.判断下列公式是恒真？恒假？可满足？

a)(P—>(QAR))A(—iP―>(—IQA―iR))；

b)Pf(P八(QfP))；

c)(QfP)八(「PAQ)；

d)(—iPv—iQ)―—iQ)o

解：(1)设G=(P-»(QAR))A(-iP-»(-nQA-nR))

二(「PV(QAR))A(PV(IQAIR))

=(((—IPV(QAR))AP)v((—«PV(QAR))A-IQA—IR)

=((-IPAP)V(PAQAR))v((-IPV(QAR))A-IQA-IR)

=((-)PAP)V(PAQAR))v((—)PVQ)A(—IPVR)A—IQA—«R)

=((-1PAP)V(PAQAR))V(((IPVQ)A^Q)A((^PVR)A

[R))

=(PAQAR)V(「P人「QA「R),其真值表如下：

PQRGPQRG

00011000

00101010

01001100

01101111

因此G是可满足的。

(2)设G=Pf(P/\(QfP))

=—iPv(PA(—iQvP))

=—)PvP

=T

其真值表如下:

PQG

001

011

101

111

因此G是恒真的。

⑶G=(QfP)A(「P/\Q)

=(—IQVP)A(—IPAQ)

=-1(—IPAQ)A(—IPAQ)

=F

其真值表如下:

PQG

000

010

100

110

因此G是恒假的。

(4)G=(-1Pv-1Q)->(P<^-,Q)

=(PAQ)v((Pf」Q)A([QfP))

=(PAQ)v((-.Pv「Q)A(QvP))

=(PAQ)V(—IPAQ)V(PA—IQ)

其真值表如下:

PQG

000

011

101

111

区此G是可满足的。

2.3.3习题2.3解答

1.证明下面的等价式:

(1)(^PA(-1QAR))V(QAR)V(PAR)=R

(2)Pf(Q-P)=[P->(PfQ)

(3)Pf(QvR)=(P-Q)v(P-R)

(4)(P-Q)八(R-Q)=(PvR)fQ

(1)证明：(「PZIQARDWQAR)v(P/\R)

△((「

二(((-1P/\(「Q/\R))vQ)P/XJQAR))vR))V(PAR)

=((((-,PvQ)A(RVQ))A((-,PVR)AR))V(PAR)

=((-)PvQ)A(RVQ)AR)V(PAR)

=((-IPVQ)AR)V(PAR)

二(「PAR)v(QAR)V(PAR)

=RA(-,PVP)v(QAR)

=R得证。

(2)证明：左边二Pf(QfP)

=—iPv(-iQvP)

=—iPv-)QvP

=Pv—iPv—)Q

=T

右边:「Pf(PrQ)

=Pv-iPvQ

=T

可有：左边=右边，得证

(3)证明：左边=[PvQvR

右边=-.PvQv-.PvR

=—iPvQvR

可有：左边=右边，得证

(4)证明：左边=(-.PvQ)A(-,RvQ)

=(―IPA-1R)vQ

=—i(PvR)vQ

=(PvR)tQ=右边

得证

2设$={6”…，GJ是命题公式集合。试求出在不增加新原子的情况下从S出发演绎出

的所有命题公式。

提示：考虑GI人…AGn的主合取范式。

解：任设一公式G，为从S出发演绎出来的公式。则可知G，

为G=GIA…AGI1的一个逻辑结果。而G有唯一一个与其等价的主合取范式，设为G”。

可设G”共有m个极大项，则可以知道令G”取1的解释使这m个极大项也取1。则从S

出发的演绎出来的的所有命题公式正是从这m个极大项中任取n(OWnWm)个合取组成，共

有2m个，其中包括恒真公式这里用1表示。

设H为由若干极大项构成的合取公式。现在证明：

1)S=>H,即G=>H。从定义出发，设有一解释1使6=61人…AG”取1值，必使G的主

合取范式也取I值。即使每一个极大项都取1值。从而使由若干极大项合取组成

的公式H也取1值，则有S=>H。

2)任意设公式H是S的一个逻辑结果，H是一些极大项的合取。现在要证组成H的

反证法：若不然，假设H中有一个极大项mk不在G的主合取范式中。则取使mk为0

的解释I,可有解释I使H取0值。而I使所有不等于mk的极大项都为1,则可有G的

主合取范式G”在I卜取1值，即G在1卜取1值，这与G=>H矛盾。

3.证明：两个公式之间的蕴涵关系具有反身性，反对称性和传递性。

证明：a)任意设一公式P,

由于PfP是恒真的，则有P=>P

即蕴涵关系有反身性。

b)任取两个命题公式P,Q

如果P=>Q并且Q=>P,则有PfQ恒真，QfP恒真,则(PfQ)A(Q->P)恒真,

那么有P-Q恒真，得出P=Q,所以蕴涵关系有反对称性。

c)任取命题公式P,Q,R

如果P=>Q,Q=>R；对于P,Q,R的任意一个解释I。如果I满足P则I也满足Q,

若I满足Q则I满足Ro

则有I满足P时，也满足R，故有P=>R。

因此蕴涵关系有传递性。

4.证明：若前提集合S中的公式都是恒真的，G是从S出发的一个演绎的逻辑结果，则

G必是恒真公式。

证明：设S是由G1,…，Gn构成的，则G|,…，G”是恒真的，那么G】A...人Gn是恒真的，

而由已知有：

G1人…人Gn=>G,因此由蕴涵定义有G必为恒真公式。

5.设G1,…，Gn是公式。证明：从｛G1,…，Gn｝出发可演绎出公式G的充要条件是从

｛G1,…，Gn，「G｝出发可演绎出公式(R人[R)。其中R为任意公式。

证明：充分性，即｛Gi，…，Gn，[G｝=>(RA「R),可有

G1人…人GnA「G=>(R人]R),因(RA「阳恒假，