教程离散数学lisanch第二章命题逻辑等值和推理演算

第二章x2－y2=(x＋y)(x－y)(x＋y)2=x2＋2xy＋y2sin2x＋cos2x=1给定两个命题A和B,而P1…Pn是出现于A和B中的所有命题变项,那么A和B共有2n个解释,若对其中的任一解释下,A和B的真值都相等,AB是等值的(或称等价)A=BAB。显然，根据真值表就可以判明任何两个是否是等值的。1:证明(P∧P)∨Q=Q证明:画出(P∧P)∨QQ的真值表可看出,2.1.1 (P∧P) FFFFFTFTTFFF 2:P∨P证明:P∨P,Q∨Q的真值表,可看出它们是等值的,而且它们都是从例1、2还可说明,两个等值并不要求它们一定含有相同题变项。若仅在等式一端的里有变项P出现,那么等式两端的其真值均与P无关例1中(P∨P)∨Q与Q的真值都同P无关,例2中P∨P,Q∨Q都是重言式,它们的真值也都与P、Q无关。再有对例1和例2来说,的解释PQ的设定,如{P,Q}={T,F}P=T,Q=F。定理对A和B,A=B的充分必要条件是AB是重言式AB为重言式(A、B必不会都是简单命题,P1,…,Pn构成的A,B的一个解释,P1,…Pn的一组具体的真值设定),则在AB都只能有相同的真值,这就是定理的意思。证明是容易的。若AB是重言式,即在任一解释下AB的真值都为T。依AB的定义只有在A、B有相同的值时,ABT。于是在任一解释下A和B都有相同的真值时,从而有A=B。反过来，若有AB,即在任一解释下A和B都有相同的真值,依AB的定义AB只有为真,AB是重有了这个等值定理，证明两个等值，只要证明由这两个构成的双条=B看成是表示A与B的一种关系。这种关系具有三个性质自反性AA对称性ABBA传递性若A=B,B=C则A=C。 等值基本的等值(命题定律P=(P∨Q)∨R=P∨(Q∨R)(P∧Q)∧R=(PQ)R=P(Q(PQ)RP∨Q=Q∨PP∧Q=PQ=QPQQP∨(Q∧R)=P∧(Q∨R)=P(QR)=P(QR)P∨P=PP∧P=PPP=TPP=P∨(P∧Q)=PP∧(P∨Q)=律(P∨Q)=(P∧Q)=(PQ)=(PQ)=PQ==P∨F=PP∧T=PTP=PTP=PF=PFP=P∨T=TP∧F=PT=TFP=P∨P=TP∧P=PP=PP=PPP=所有这些，都可使用直值表加以验证。若使用Venn图(参见7.4.1节)也容易理解这些等值式,PQ理解为某总体论域上的子集合,∧Q为两集合的公共部分(交集合P∨Q为两集合的全部(并集合P为总体论域(如矩形域)P2.2.1所示。 P 从Venn图看6就很容易了,因P∧Q较P来得“小”,P∨Q较P来得P∨(P∧Q) P∧(P∨Q)=若∨,∧分别以+和·来表示,P∨(Q∧R)=化 P+Q·R=(P+Q)·(P+P∨P= P+P=PP∧P= P·P=PP∨(P∧Q)=P化 P+P·Q=P∧(P∨Q)=化 P·(P+Q)=这些以+·表示的等式,在实数域里明显地不成立,这就提醒我们,与、或的表示是工人,那么(P∨Q)就表示并非“是学生或者是工人”。这相当于说，“不是学生而且也不是工人”，即可由P∧Q表示,从而有(P∨Q)=P∧Q。若干常用的等值∧的。这也是证明和理解含有，的的一般方法11-18是等值演算中经常使用的,也该掌握它们,特别是能直观地解释它PQ=P通常对PQ进行运算时,不如用P∨QP∨Q表示PQPQ=如将PQ视为正定理,那么QP就是相应的逆否定理,它们必然同时为真,同时为假,所以是等值的。P(QR)=P是(QR)的前提Q是R的前提,于是可将两个前提的合取P∧Q作为总的PQR,PQR。PQ=PQ为真,有两种可能的情形,即(P∧Q)为真或(P∧Q)P∧Q为真,PQT的情况下出现P∧Q为真,PF的情况下出现。从而可说PQ为真,P、Q同时为真或同时为假时成PQ=这可解释为PQ为假,有两种可能的情形,即(P∨Q)为假或(P∨Q)为假,而P∨Q为假,必是在PF,QT的情况下出现P∨Q为假,必是在PT,FPQ为假,PQPQPQ=PQ成立,PQQPP(QR)=P、Q(PR)PQRPQR成立,定理:对A的子,用与之等值的来代换便称置换。置换规则A的子置换后A化为B,必有A=B。当A是重言式时,置换后的B必也是重言式。置换与代入是有区别的。置换只要求A的某一子作代换,不必对所有同一的子都作代换。1:证明(P∧(Q∧R))∨(Q∧R)∨(P∧R)证明=(=((P∧Q)∧R))∨((Q∨P)∧R结合律 (律 (分配律 (交换律 ( 换 (同一律例2:试 ∨(P∧Q)∨(P∧R)=证明左端 (律 (等幂律 ( 入路的功能明确后，如何寻求简单而又可靠的电子线路，提供了有力的。命题与真值表的关对任一依赖于命题变元P1…Pn题A来说,可根据P1…Pn的真值给出A的真值,从而建立起由P1…Pn到A的真值表。这个由列值表的过程反过来若给定了由P1…Pn到A的真值表,是否可以写出命题A对P1…Pn的逻辑表达式呢?回答是肯定的。例如图2.3.1所示的真值表,可列写出A,B由P、Q表达的来PQABCFFTTFTFTTTFFTFFFTTTTTFFT第四行，ATAT有三种可能的情形或第一种情形或第二种情形,A=(…)1∨(…)2APFQF同时出现,也即A=B=A来说,T的解释个数(3)F的解释个数(1),自然在真值表中补上A列为好,以便对A列写A=

A=F2.3.1BF,PQBFBF有两种可能的情形,或第一种情形,B=进而分析每种使B为情形。第一种情形是P=TQ=F出现,也即P∨Q为假,于是可将(…)1写成(P∨Q)。同理(…)2写成(P∨Q)。于是得B=A=要注意的是这两种列写的区别,首先是区分从T还是从F来列写,分别形的不同结构。再者,P、Q时,再有当列写C时,因图2.3.1中对解释{P、Q}={T,T}时,C取何值可任意,C与{P,Q}={T,T}无关,C的真值,C的表达式除了所详述过的五个联结词外,还可定义的联结词。像计算机的硬件电异或(半加 ∨:P∨Q=与 PQ=或 PQ=问题是对n个命题变项P1…Pn 来说,共可定义出多少个联结词?还可以问,式。可把所有的合式加以分类，将等值的视为同一类，从中选一个作P,可建立四种不同的真值函项,相应的可定义出四个不同的一元f0f1f2f36.2.4.1fifi(P)的定义。PFFFTTTFTFTf0(P)=f1(P)=f2(P)=Pf3(P)=T其中f0(P)是永假式f3(P)是永真式,均与P无关,而f1(P)就是变项P本身,从而新的只有f2(P),这就是由否定词所建立的真值函项。PQ共有四种取值情形,于是联结PQ16种不同的真值函项16个不同的二元g0g1…g152.4.2gIgi(P,Q)的定PQFFFFFFFFFTFFFFTTTFFFTTFFTTFTFTFTFFTTTTTTFFFFTFTTFFFTTFTT TTTTTTTTFFTTFTFTg0(P,Q)=Fg1(P,Q)P∧Qg2(P,Q)=g3(P,Q)=(P∧Q)∨(P∧Q)=P∧(Q∨Q)=Pg4(P,Q)=P∧Qg5(P,Q)=(P∧Q)∨(P∧Q)=(P∨P)∧Q=Qg6(P,Q)=P∨Qg7(P,Q)=g8(P,Q)=P∧Q=PQg9(P,Q)=PQg10(P,Q)=(P∧Q)∨(P∧Q)=(P∨P)∧Q=Qg11(P,Q)=P∨Q=QPg12(P,Q)=(P∧Q)∨(P∧Q)=P∧(Q∨Q)=Pg13(P,Q)=P∨Q=PQg14(P,Q)=P∨Q=PQg15(P,Q)=T7种联结词,不甚常用,没有过多讨论。nP1…Pn,,Pi有两种取值,P1…Pn2n22n个,或说可定义22nn元联结由于可定义的联结词的数量是极大的,需要考虑它们是否都是独立的?也就定义:设C是联结词的集合如果对任一命题都有由C中的联结词表示显然全体联结词的无限集合是完备的,而{∨∨,∧}就不是完备的。定理{,∨,∧}是完备的联结词集合从节2.3介绍的由真值表列写逻辑的过程可知,任一都可由,∧表示出来,从而{,∨,∧}是完备的,一般情形下,这定理的证明可使用数学归纳法,施归纳于联结词的个数来论证。P∧Q=(P∨Q)P∨Q=这说明,∧可由{,∨}表示,∨可由{,∧}表示,故{,∨},{,∧}词的完备集。还可证明{}也都是联结词的完备集。但{∨,∧尽管{,∨},{,∧}是完备的,但使用起来并不够方便,我们愿意采取折衷方案,不是仅用两个也不是使用过多的联结词,还是选用详细讨论过的五个联结词集{,∧,∨,,},当然是完备的,只是相互并不独立。系上看，这也是一种逻辑规律，是我们所感的。这节所讨论题A,假定其中仅出现,∨,∧这三个联结词定义将A中出现的∨、∧、T、F分别以∧、∨、F、T代换,得到2.2.1中有许多对偶式出现,如(P∨Q)∧R的对偶式为(P∧Q)∨R 的对偶式为P∧T不难知道,(P∨Q)∧R=成立,(P∧Q)∨R=为方便,A=A(P1,…A－A(P1,…定理 (A*)=(A*),(A－)=定理 (A*)*=A,定理 A=可用数学归纳法,An来证明。基始:n=0,A中无联结词,便有A=P,A但A*－=∴n=0n≤kn=k+1n=k1≥1,AA=A1,A=A1∧A2,A=A1A2中联结词个数≤k依归纳法假设，A1A1*－A2当AA1A= 2.5.1,=当AA1∧A2A== = = = =从而定理得证这定理实为律的另一种形式它把、－联系起来了。定理2.5.4 若A=B必有A*=B*证明:因为A=B等价于AB 2.5.3,AA*－B于 A*－ 必 A* A*=定理 若AB,必有定理 A与A－同,同可满A与A*同,同可满对偶性是逻辑规律,给证明的等值和求否定都带来了方便1n个命题变项所能组成的具有不同真值题仅有22n个,然而与任何与命题A等值的，能否都可以化为某一个统一的标准形式。希望这种1

r2

xy2a 为叙述方便,P及其否定式P统称文字。一些文字的析取称析取式（也称子句）P与P称为互补对。即简单命题与其否定式称为互补对。合取称为积,折取P,P,P∧Q,P∧Q∧PP,P,P∨Q,P∨Q∨Q都的,其中Ai(i=1,…,n)为合取式。即析取范式是基本和之积。的,其中Ai(i=1,…,n)为析取式。即合取范式是基本和之积 可通过求范式的具体步骤，来认识范式存在定理的正确性。对一个已给的,可按下述步骤求得该的合取范式和析取范式AB=AB (多用于求合取范式= (多用于求析取范式因范式中不出现符号,将它们以范式中出现的符号,∨,∧来表示是重复使用律和双重否定律,把否定词内移到直接作用于命题变项(A∧B)=(A∨B)=A=将所有的否定词,都内移到命题变项前,A∧(B∨C)=(A∧B)∨(A∧C) A∨(B∧C)= (多用于求合取范式将化成一些合取式的析取,或化成一些析取式的合取,都必须使用分配对任一，经步骤(1)、(2)、(3)必能化成范式。而且所求得的范式与该公1:求(P∨Q)(P∧Q)的析取范式。== (律、双重否定 (律这已是析取范式了又因P∧P,Q∧Q,P∧Q∧P∧Q都是式,从2.2.1P∨FP,可见一的范式不是唯一的例2:求(P∨Q)(P∧Q)的合取范式 == (律、双否定

= (吸收律也可由已求得的一种范式,1求得的析取范式,便可得合取范式。= (分配律= (同一律2的结果。反过来,由合取范式使用分配律便可得析范式可用来判断重言式和一个的范式不是唯一的,因此使用范式判别几个是否相等就比较困对n个命题变项P1,…,Pn来说,所组成的(基本积其中Qi=Pi 或Pi(i=1,…,n),则称Q1∧…∧Qn为极小项,并以mi表示。极小项必须含有Q1,…,Qn全部n个文字。P1P2P1∧P2P1∧P2P1∧P2P1∧P2Pi1对应,而Pi0对应,P1∧P200对应,m0P1∧P210对应,m2。P1∧P211对应,m3。nP1,…,Pn可组成2nmi0i2n1Q1,…,Qmn使用真值表列 法，都可得到一个的主析取范式3:PQP,QPQ的真值表(6.2.6.3,T(T的真值指派项的析取)PQ,便得PQ=(P∧Q)∨(P∧Q)=并简记为∨0,3PQ又因为等值都有相同的真值表,从而可知所有等值(变项均为n4:用填满命题变项法,PQPQ=PQ的析取范式。现将这范式中的合取式PQ,QP,P、Q,P==(P∧Q)∨(P∧Q)Q=Q∧(P∨P)=PQ=====PQ(6.2.6.4)对一个含有n个变项的来说,所有可能的极小项个数和该的解释个数一样多,都是2n。极小项两两不等值,mi∧mjF(ij)任一含有n个变项的,都可由k个(k2n)极小项的析取来表示或说恰由2n个极小项的析取构成的，必为重言式。2niVmiAk个极小项的析取组成,那么其余的2nkAP1P2P3A=∨0,2,4,则=由n个命题变项P1,…,Pn所组成的(基本和QiPi或Pi(i1,…n),Q1∨…∨Qn为极大项,Mi表示。Q1,…,Qnn个文字。P1,…Pn可构成四个极大项：P1∨P2P1∨P2P1∨P2,M0M1M2M3nP1,…Pn可组成2nMi0i2n1Q1,…,Qn全部出现。n5:PQPQPQ的真值表(6.2.6.5),F(F的反真值指派项的合取)PQ,便得PQ==并简记为∧1,2PQ6:用填满命题变项法,P∧QP∧Q=====对一个含有n个变项的来说,所有可能的极大项个数和该的解释个数一样多,都是2n。极大项两两不等值,Mi∨MjT(ij)任一含有n个变项的,都可由k个(k2n)极大项的合取来表示。或恰由2n个极大项的合取构成的，必为式。2niMiAk个极大项的合取组成,那么其余的2nkAP1P2P3A=∧0,2,5则A=若已知Ａ的主析取范式，如A=补=∧补补=补(求补是对2n12317而言的,25,2+5=A的主合取范式,A=补=∨({0,1,,7}{1,4,5}补==从真值表列写的主析取范式,主合取范式时,除分别从T和F列写外,在填写合取式和析取式时是取变项还是变项的否定是有区别的,这就是主合取命题等值式就介绍这些,将以自然语句描述的推理关系,引入符号,抽象化并以条件式表示出来便得1:如果今天我病了,那么我没来上课。P表示“今天我病了”Q表示“我没来上课”(则第一个自然PQ)。便可将这推理关系以条件式也可以用图式表示 P真PQ真,Q真,P、Q可表任意命题,从而推理形式2:P,Q。（(PQ)∧P)说的是,PQ真PQ3:P,Q。Q。((PQ)∧Q)表明,PQQ假,P假。同样这类推理形式反映的是一类推1-3建立推理形式的办法，可以引入任意多个推理形式。自然要问它们13所建立的推理形式((PQ)∧P)((PQ)∧Q)2((PQ)∧P)如果给定两个AB,只要A取值为真,B就必取值为真,便称A重言(永真)BBA的逻辑推论。并用符号联结词，AB也不是合式。AB表示的推理形式来说推理形式是正确的,AB是同一概念了,AB表示了。P1…Pn,P1,…,PnAB的真值表,然后查看,A为真的解释,B是否也都为真。 所有使P为真的解释是{P,Q{T,F},{P,Q{T,T}即图2.7.1P∨QT,PP∨Q。也可以说推理形式AB,AAB,AB来说的任一解释下,ABA为重言式,对A都真,B也真,B也是重言式。AB,BA同时成立,AB在任一解释下，由ABA真有B真。由BAB真有A真,或说AB假。从而任一解释下A,B同时为真同时为假,A=B。反过来，ABABBAAB,BC,ACAB,ACAB∧CAC,BCA∨BC基本的推理为了进行推理演算,需引入一些基本的重言蕴涵式,作为基本的推理(或称推理定律),进而在推理演算中直接对这些皆可根据蕴涵的定义用真值表法或其它方法加以验证,也可给予直观的语义说明。AB基本的推理16.使用真值表法证明这些推理是容易的，可按节2.7.2例4的办法若从语义上给予直观说明也是不难的。如2（PQ)P,(PQ)Q。意思是说,PQ不成立(取假),P为真,Q为假。这从PQ的定义可知,因只有当P=T而Q=F时,PQ=F又如7,∨Q)Q。意思是说P不对,P∨Q又对,Q8,P∧(PQ)Q常称言推理,或称作分离规则,是最常使用的推理了。10,(PQ)∧(QR)PR常称言,也是最常使用的推理公证明推理方2.1的等值定理,A=BAB为重言式是等价的,从而可用ABABABAB是重言式也是等价定理2.8.1 AB成立的充分必要条件是AB为重言式。AB成立。从而在任一解释下,ABAB情形,AB反过来AB为重言式,从而在任一解释下,A真B只能为真不可能AB。定理2.8.2AB成立的充分必要条件是A∧B是式证明是容易的。因(AB)(A∨B)A∧BAB为真A∧B2.8.1,ABAB是重言式A∧B是这两个定理说明了可用AB是重言式或A∧B是式来证明推理若BAAB从而若使B为解释下也有A为假,便得AB这种证明方法是显然的,若将ABBA就是其逆否定理, (PQ)∧(QR)=T,从而有PQ=TQR=P=T,QTRT从而PR=T。 而若P=F，右端必成立。故这假言推理式成立。AB的证明,A=A1,…,An的一致性,A自身不能为假。如果A1,…,An不是一致的而是有的,从而A为假,这时不管结论B是什么,AB都是成立的,但这种推理是没有实用意义的。B的推演过程。而且这些方法也难于在谓词逻辑中使用。来实现的。从前提A1，…,An出发，通过使用推理规则和基本的推理所列出的几条规则,较节6.2.7.4的基本推理更为一般化在推理过程中,推理规则和基本推理配合使用。前提引入规 在推理过程中,可以随时引入前提结论规则 在推理过程中所得到的中间结论,可作为后续推理的前代入规 在推理过程中,对重言式中题变使用代入规则 在推理过程中,命题中的都可以用与之等值题来置换。分离规则(假言推理 如果已知命题AB和A,则有命题B条件证明规 A1∧A2B与A1A2B是等价的1,2在推理过程中显然是常用的,正确性是自然的。代入规则置换规则已作过说明,由于它的重要性而列为推理规则,AB,A成立的条件下,B分离出来的规则,6A1A2BA1∧A2B的证明,意思是说,可将要证明的结论A2B中的A2作为条件来使用,从而简化了证1:RPQ,QR,P的逻辑推论。 (1)(2)分离规则(I8,假言推理 (3)(4)分离规则(I8,假言推理2:R∨SC∨D,C∨D)E,E(A∧B),(C∨D) (1)(2)假言 (3)(4)假言 (5)(6)分离规则(I8,假言推理128行,其繁琐程度可想可知,使用真值表法实现这个证