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

第二章命题逻辑 2.2 主要解题方法2.2.1 证明命题公式恒真或恒假主要有如下方法：方 法 一.真 值 表 方 法即列出公式的真值表，若表中对应公式所在列的每一取值全为1,这说明该公式在它的所有解释下都是真，因此是恒真的；若表中对应公式所在列的每一取值全为0,这说明该公式在它的所有解释下都为假，因此是恒假的真值表法比较烦琐，但只要认真仔细，不会出错例 2.2.1 说明 G=(PAQ-R)A(P-Q)-(P-R)是恒真、恒假还是可满足解：该公式的真值表如下：PQRPAQ-RP-Q(P 八 Q.R)A(P-Q)PfRG0001111100111111010111110111111110010011101100111100100111111111表 2.2.1由于表2.2.1中对应公式G所在列的每一取值全为1,故G恒真方法二.以基本等价式为基础，通过反复对一个公式的等价代换，使之最后转化为一个恒真式或恒假式，从而实现公式恒真或恒假的证明例 2.2.2 说明 G=(P-R)v-n R)-J (Q-P)A P)是恒真、恒假还是可满足解：由(P-R)7 f R JPV Rv-i R=1,以及-i(Qf P)A P=-i(-iQv P)A P =QA-I PA P=0知，(P-R)R)-J (Q-P)A P)=0,故 G恒假。

方法三.设命题公式G含n个原子，若求得G的主析取范式包含所有2n个极小项，贝IJ G是恒真的；若求得G的主合取范式包含所有2n个极大项，贝IJ G是恒假的方法四.对任给要判定的命题公式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等价的充要条件是：公式G o H是恒真的，因此，如果待考查公式是G f H型的，可将证明Gf H是恒真的转化为证明G蕴涵H加果待考查公式是G s H型的,可将证明G-H是恒真的转化为证明G和H彼此相蕴涵例 2.2.3 证明 G=(P-R)-(Q-R)-(P v Q)-R)恒真证 明：要证明(P-R)-(Q-R)-(P v Q)-R)恒真，只需证明(P-R)n(Q-R)f(P v Q)R)我们使用形式演绎法1)P-R(2)Q-R(3)-,P v R(4)Q v R(5)J P v R)A J Q v R)(4)(6)J PAQ)v R(7)(P v Q)v R(8)(P v Q)-R(9)(Q-R)-(P v Q)-规 则1附加前提规则2,根 据(1)规则2,根 据(2)规 则2,根 据(3)、规 则2,根 据(5)规则2,根 据(6)规 则2,根 据(7)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=(PR),证明 A=BO证 明：pQRPAQ-RP-QAB00011110011111010111101111111001001101100111001001111111表 2.2.2由表2.2.2可以看出，使A为真的解释均使B亦为真，因止 匕，A=BO方 法 二.证 明A fB是恒真公式由例 2.2.1 知,(P/Q-R)A(P-Q)f(P-R)恒真，因此,立即可得到例2.2.4中的结论：(PAQFR)A(PfQ)n(P f R),即 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不可能真值表如下：为0ABCAfB(AAC)(BAC)(AfC)-(BfC)000111表 2.2.3001111010110011111110111111111从真值表可以看出，(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=P f Q,证明 A 蕴涵 B证 明：我们来证明A-B恒真R-P)-Q)-(P-Q)=J (RvP)vQ)v(lPvQ)=(-iRvP)A-I Q)v(-iPvQ)=(-IRA-H Q)v(P A-!Q)V-1(P A-1 Q)方法三.利用一些基本等价式及蕴涵式进行推导对于例2.2.6,由基本等价式可得：A二(Rf P)-Qj(-iRvP)vQ=(RA-I P)VQ=(RvQ)A(-I PvQ)二(RvQ)A(P-Q)由教材中基本蕴涵式2.P/QnQ可知，(R vQ)(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)一(Rf Q),因此，I亦满足B2)在 解 释I下，P为真，Q为真，所以，PvRf Q为真，故B为真，即，I满 足B综上，I满 足B,因此，A蕴 涵B方 法 五.反 证 法，设结论假，往证前提假对于例2.2.6,证明(R-P)Q蕴 涵P-Q,若使用方法三，是很烦琐的，而使用方法四，就很简单。

假设存在解释I使P f Q为假，则只有一种情形，P在I下为真，且Q在I下为假，这 时R-P在I下为真，故I弄假(R f P)一Qo 因此，(R-P)-Q 蕴涵 P-Qo方 法 六.分 别 将 公 式A和公式B转化为它们各自的主析取范式或主合取范式若公式A的主析取范式所包含的所有极小项也包含在公式B的主析取范式中；或者，公式B的主合取范式中所包含的极大项均包含在公式A的主合取范式中，则公式A蕴涵公式B使用这种方法需要注意，当公式A和公式B中包含的原子不完全相同时，在求两公式的极小项或极大项时，要考虑该两公式包含命题原子的并集中的所有原子在 例2.2.6中，A和B的主析取范式分别为：A二(-1 PA-I QAR)v(-1 PAQA-IR)V(-1 PAQAR)v(PAQA-IR)v(PAQAR),B二(-1 PA i QA iR)v(i PA-I QAR)V J PAQA-IR)V(I PAQAR)v(PAQA iR)v(PAQAR),可见，A n BA和B的主合取范式分别为：A二(PvQvR)A(-1 PvQvR)A(-1 P v Q v-iR),(1 PvQvR)A(1 PvQv iR)可见，A=BO另外若给出前提集合S二 G1,，Gk),公式G,证明SnG有如下两种方法：1.G A A Gk=G2.形式演绎法：根据一些基本等价式和基本蕴涵式，从S出发，演绎出G。

教材中已经给出了这方面的例子，在此不再赘述2.2.3求主合取范式和主析取范式1.极小项与极大项的性质以3个原子为例，则对应极小项和极大项的表为:PQR极小项极大项000n io=1 PA-1 QAiRM0=PvQvR001R 1 二 PA-1 QARM i 二 PvQvR010用2 =-1 P QA-iRM 2 =Pv-iQvR011叱 二 1 P QARM3=Pv-nQvR100用4=P1 QA-iRM 4 JPVQVR101n ig PA QARM 5110o ig-PAQA-iRM6=PVQVR111m7=PA QARM 7 JPV-IQVR表 2.2.4由 表2.2.4可 知,对n个命题原子忤，Pn,极小项有如下性质：(1)n个命题原子P1,，P n有2个不同的解释，每个解释对应P1，P n的一个极小项2)对P1,，匕的任意一个极小项m,有且只有一个解释使0 1取1值，若使极小项取1的解释对应的二进制数为i,则m记为n，于 是 关 于，P n的全部极小项为吗，,叫 T3)任意两个不同的极小项的合取式恒假：miA m-0,i W j2”I(4)所有极小项的析取式恒真：v=1oi=O极大项有如下性质：(1)n个命题原子忤，P n有2个不同的解释，每个解释对应巳，P n的一个极大项。

2)对肉，巳的任意一个极大项M,有且只有一个解释使M取0值，若使极大项取0的解释对应的二进制数为i,则M记为Mi，于是关于巳，P n的全部极大项为M o,M1,，(3)任意两个不同的极大项的析取式恒真：此v M-1,i W j4)所有极大项的合取式恒假1AM=0/=O2.主合取范式与主析取范式之间的关系由极小项和极大项的定义可知，二者有如下关系：m -1 M ,M iiT i 由此可知，若 PvQvR为一公式G的主合取范式，则G =-1iG-1-1 MQ二 (M A M 2 A A Mg)iM-|v_1M2 v*v-iM g=m z m2v-v m6为 G的主析取范式若 J PA Q)v J PAQ)V(PA Q)为一公式 H 的主析取范式，则HH二(J PA Q)v (-1 PA-I Q)v (PA Q)(0 1Q v v IB3)1 (叱)2=-iPvQ为H的主合取范式一般地，若公式A中含n个命题原子，且A的主析取范式中含有k个极小项：叫血,，则A的主析取范式中必含有*1k其余的2-k个极小项，不妨设为：叫，,叫，即71J2n-k因此，A =-iA1 (m；v.v m)力J2.k=IAH.A.A.力J2n_k A/i A .A A/.oJi J2n-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的极小项的短语使用同一律，补进短语中未出现的所有命题原子，并使用分配律展开，即，如果短语G J不是关于匕，Pn的极小项，则G J中必然缺少原子，不妨设为P m，Pjk，于是GJ GJ A(P ji v 1 Pj!)A,A(P jkV 1 Pjk)二 叫 .这样，就将非极小项G J化成了一些极小项之析取。

将相同的短语的多次出现化为一次出现，就得到了给定公式的主析取范式主合取范式的求法类似，留给读者作为练习由上面讨论可知，只要求出一种范式，可立即得到另外一种范式例2.2.8求公式G=P-(Q-R)的主析取范式与主合取范式解：(1)使用真值表法见表2.2.5表 2.2.5pQRP-(Q-R)00010011010101111001101111001111根据真值表中使得公式为真的解释，所对应的极小项的析取即为其主析取范式：G二(-1 PA QA-IR)v(-1 PA i。