第二章命题逻辑的等值和推理演算课件

第二章第二章 命题逻辑的等值和推理演算命题逻辑的等值和推理演算 o推理形式推理形式和和推理演算推理演算是数理是数理逻辑研究的基本研究的基本内容内容 o推理形式推理形式是由前提和是由前提和结论经蕴涵涵词联结而成而成的的o推理推理过程是从程是从前提前提出出发，根据所，根据所规定的定的规则来推来推导出出结论的的过程程 o重言式重言式是重要的是重要的逻辑规律，正确的推理形式、律，正确的推理形式、等等值式都是重言式式都是重言式1谢谢观赏2019-8-23第二章 命题逻辑的等值和推理演算 推理形式和推理演算是数o本章本章对命命题等等值和推理演算和推理演算进行行讨论，是以，是以语义的的观点点进行的非形式的描述行的非形式的描述，不，不仅直直观且容易理解，也便于且容易理解，也便于实际问题的的逻辑描述和描述和推理。推理。o严格的形式化格的形式化的的讨论见第三章所建立的公理第三章所建立的公理系系统。2谢谢观赏2019-8-23本章对命题等值和推理演算进行讨论，是以语义的观点进行的非形式等值演算等值演算(考察逻辑关系符考察逻辑关系符(=)o等等值定理、公式定理、公式o联结词的完的完备集集(由个由个别联结词表示所有表示所有联结词的的问题)o对偶式偶式(命命题公式的公式的对偶性偶性)o范式范式(命命题公式的公式的统一一标准准)由真由真值表写命表写命题公式公式(由由T写、由写、由F写写)3谢谢观赏2019-8-23等值演算(考察逻辑关系符(=)等值定理、公式3谢谢观赏2推理演算推理演算(考察逻辑关系符考察逻辑关系符)o推理形式推理形式(正确推理形式的表示正确推理形式的表示)o基本推理公式基本推理公式(各种三段各种三段论及五种及五种证明方法明方法)o推理演算推理演算(证明推理公式的第六种方法，使明推理公式的第六种方法，使用推理用推理规则)o归结推理法推理法(证明推理公式的第七种方法，明推理公式的第七种方法，常用反常用反证法法)4谢谢观赏2019-8-23推理演算(考察逻辑关系符)推理形式(正确推理形式的表示)42.1 等值定理等值定理 o若把初等数学里的、若把初等数学里的、等运算符看作是等运算符看作是数与数之数与数之间的的联结词，那么由，那么由这些些联结词所表达的所表达的代数式之代数式之间，可建立，可建立许多等多等值式如下：式如下：x2y2=(xy)(xy)(xy)2=x22xyy2 sin2xcos2x=1在命在命题逻辑里也同里也同样可建立一些重要的可建立一些重要的等等值式式 5谢谢观赏2019-8-232.1 等值定理 若把初等数学里的、等运算符看2.1.1 等值的定义等值的定义 o给定两个命定两个命题公式公式A和和B,而而P1Pn是出是出现于于A和和B中的所有命中的所有命题变项,那么公式那么公式A和和B共有共有2n个解个解释,若若对其中的任一解其中的任一解释,公式公式A和和B的真的真值都相等都相等,就称就称A和和B是等是等值的的(或等价的或等价的)。记作作A=B或或ABo显然，可以根据真然，可以根据真值表来判明任何两个公式是否是表来判明任何两个公式是否是等等值的的 6谢谢观赏2019-8-232.1.1 等值的定义 给定两个命题公式A和B,而P1例例1:证明证明(P P)Q=Q证明明:画出画出(P P)Q与与Q的真的真值表可看出等表可看出等式是成立的。式是成立的。7谢谢观赏2019-8-23例1:证明(PP)Q=Q证明:画出(PP)例例2:证明证明P P=Q Qo证明明:画出画出P P,Q Q的真的真值表表,可看可看出它出它们是等是等值的的,而且它而且它们都是重言式。都是重言式。8谢谢观赏2019-8-23例2:证明PP=QQ证明:画出PP,Qo从例从例1、2还可可说明明,两个公式等两个公式等值并不一定并不一定要求它要求它们一定含有相同的命一定含有相同的命题变项n若若仅在等式一端的公式里有在等式一端的公式里有变项P出出现,那么等那么等式两端的公式其真式两端的公式其真值均与均与P无关。无关。n例例1中公式中公式(P P)Q与与Q的真的真值都同都同P无关无关n例例2中中P P,Q Q都是重言式都是重言式,它它们的真的真值也都与也都与P、Q无关。无关。说明说明9谢谢观赏2019-8-23从例1、2还可说明,两个公式等值并不一定要求它们一定含有相2.1.2 等值定理等值定理 定定理理 对公公式式A和和B,A=B的的充充分分必必要要条条件件是是AB是是重重言言式式。oA、B不不一一定定都都是是简单命命题,可可能能是是由由简单命命题P1,Pn构构成成的的.对A,B的的一一个个解解释,指指的的是是对P1,Pn的的一一组具具体体的的真真值设定定.o若若AB为重重言言式式,则在在任任一一解解释下下A和和B都都只只能能有有相相同同的的真真值,这就就是是定定理理的的意意思思。10谢谢观赏2019-8-232.1.2 等值定理 定理 对公式A和B,A=B的充分证明证明若若A B是重言式是重言式,即在任一解即在任一解释下下,A B的真的真值都都为Tn依依A B的定的定义只有在只有在A、B有相同的有相同的值时,才才有有A B=T。于是在任一解于是在任一解释下下,A和和B都有都有相同的真相同的真值,从而有从而有A=B。n反反过来，若有来，若有A=B,即在任一解即在任一解释下下A和和B都都有相同的真有相同的真值,依依A B的定的定义,A B只有只有为真真,从而从而A B是重言式。是重言式。注：根据注：根据该等等值定理，定理，证明两个公式等明两个公式等值，只要，只要证明由明由这两个公式构成的双条件式是重言式即可两个公式构成的双条件式是重言式即可11谢谢观赏2019-8-23证明若A B是重言式,即在任一解释下,A B“”作为逻辑关系符是一种等价关系作为逻辑关系符是一种等价关系o不要将不要将“”视作作联结词，在合式公式定，在合式公式定义里没有里没有“”出出现oA=B是表示公式是表示公式A与与B的一种关系。的一种关系。这种种关系具有三个性关系具有三个性质:1.自反性自反性 A=A2.对称性称性 若若A=B,则B=A3.传递性性 若若A=B,B=C,则A=C 这三条性三条性质体体现了了“”的的实质含含义。12谢谢观赏2019-8-23“”作为逻辑关系符是一种等价关系不要将“”视作联结词，在2.2 等值公式等值公式2.2.1 基本的等值公式基本的等值公式(命题定律命题定律,P和和Q是任意的命题公式是任意的命题公式)1.双重否定律双重否定律P=P2.结合律结合律(P Q)R=P(Q R)(P Q)R=P(Q R)(P Q)R=P (Q R)注注:所有这些公式，都可使用真值表加以验证所有这些公式，都可使用真值表加以验证13谢谢观赏2019-8-232.2 等值公式2.2.1 基本的等值公式(命题定律,3.交交换律律P Q=Q PP Q=Q PP Q=Q P4.分配律分配律P(Q R)=(P Q)(P R)P(Q R)=(P Q)(P R)P(QR)=(PQ)(PR)5.等等幂律律(恒等律恒等律)P P=PP P=PPP=TPP=T14谢谢观赏2019-8-233.交换律14谢谢观赏2019-8-236.吸收律吸收律P(P Q)=PP(P Q)=P7.摩根律摩根律(P Q)=P Q(P Q)=P Q对蕴涵涵词、双条件、双条件词作否定有作否定有(PQ)=P Q(PQ)=PQ=PQ=(P Q)(P Q)15谢谢观赏2019-8-236.吸收律15谢谢观赏2019-8-238.同一律同一律P F=PP T=PTP=PTP=P还有有PF=PFP=P16谢谢观赏2019-8-238.同一律16谢谢观赏2019-8-23 9.零律零律P T=TP F=F还有有PT=TFP=T10.补余律余律P P=TP P=F还有有PP=P PP=PPP=F 17谢谢观赏2019-8-23 9.零律17谢谢观赏2019-8-23Venn图图(理解等式理解等式)o将将P、Q理解理解为某某总体体论域上的子集合，并域上的子集合，并规定：定：nP Q为两集合的公共部分两集合的公共部分(交集合交集合)nP Q为两集合的全部两集合的全部(并集合并集合)n P为总体体论域域(如矩形域如矩形域)中中P的余集的余集18谢谢观赏2019-8-23Venn图(理解等式)将P、Q理解为某总体论域上的子集合，并Venn图图(理理解解等等式式)从从Venn 图，因，因P Q较P来得来得“小小”,P Q较P来得来得“大大”，从而有，从而有P(P Q)=PP(P Q)=P19谢谢观赏2019-8-23Venn图(理解等式)从Venn 图，因PQ较P来得“小”理解等理解等式式:Venn图，自然语言图，自然语言(P Q)=P QoVenn图(理解集合理解集合间、命、命题逻辑中、中、部分部分信息量信息量间的一些关系的一些关系)o对这些等式使用自然用些等式使用自然用语加以加以说明，将有助明，将有助于理解于理解n如如P表示表示张三是学生三是学生,Q表示李四是工人表示李四是工人,那么那么(P Q)就表示并非就表示并非“张三是学生或者李四是工三是学生或者李四是工人人”。这相当于相当于说，“张三不是学生而且李四三不是学生而且李四也不是工人也不是工人”，即可由，即可由 P Q表示表示,从而有从而有(P Q)=P Q20谢谢观赏2019-8-23理解等式:Venn图，自然语言(PQ)=PQ2.2.2 常用的等值公式常用的等值公式 o由于人由于人们对、更更为熟悉，常将含有熟悉，常将含有和和的公式化成的公式化成仅含有含有、的公式。的公式。这也是也是证明和理解含有明和理解含有，的公式的一般的公式的一般方法方法o公式公式11-18是等是等值演算中演算中经常使用的常使用的,也也该掌握它掌握它们,特特别是能直是能直观地解地解释它它们的成立的成立21谢谢观赏2019-8-232.2.2 常用的等值公式 由于人们对、更为熟悉，11.PQ=P Qo通常通常对PQ进行运算行运算时,不如用不如用 P Q来来得方便。而且以得方便。而且以 P Q表示表示PQ帮助我帮助我们理解如果理解如果P则Q的的逻辑含含义o问题是是这种表示也有缺点，种表示也有缺点，丢失了失了P、Q间的因果关系的因果关系 22谢谢观赏2019-8-2311.PQ=P Q22谢谢观赏2019-8-2312.PQ=QPo逆否定理，假言易位逆否定理，假言易位o如将如将PQ视为正定理正定理,那么那么 QP就是就是相相应的逆否定理的逆否定理,它它们必然同必然同时为真真,同同时为假假,所以是等所以是等值的的23谢谢观赏2019-8-2312.PQ=QP逆否定理，假言易位23谢谢观13.P(QR)=(PQ)Ro前提合并前提合并oP是是(QR)的前提的前提,Q是是R的前提的前提,于是可将于是可将两个前提的合取两个前提的合取P Q作作为总的前提。的前提。即如即如果果P则如果如果Q则R,等价于如果等价于如果P与与Q则R24谢谢观赏2019-8-2313.P(QR)=(PQ)R前提合并24谢谢观14.PQ=(PQ)(P Q)o从取真来描述双条件从取真来描述双条件o这可解可解释为PQ为真真,有两种可能的情形有两种可能的情形,即即(P Q)为真或真或(P Q)为真。而真。而P Q为真真,必是在必是在P=Q=T的情况下出的情况下出现;P Q为真真,必是在必是在P=Q=F的情况下的情况下出出现。从而可。从而可说,PQ为真真,是在是在P、Q同同时为真或同真或同时为假假时成立。成立。这就是从取真来就是从取真来描述描述这等式等式 25谢谢观赏2019-8-2314.PQ=(PQ)(PQ)从取真来描述双15.PQ=(P Q)(P Q)o从取假来描述双条件从取假来描述双条件o这可解可解释为PQ为假假,有两种可能的情形有两种可能的情形,即即(P Q)为假或假或(P Q)为假假,而而P Q为假假,必是在必是在P=F,Q=T的情况下出的情况下出现;P Q为假假,必是在必是在P=T,Q=F的情况的情况下出下出现。从而可。从而可说PQ为假假,是在是在P真真Q假假或或P假假Q真真时成立。成立。这就是从取假来描述就是从取假来描述这等等式式 26谢谢观赏2019-8-2315.PQ=(PQ)(PQ)从取假来描述双16.PQ=(PQ)(QP)o从从蕴含含词来描述双条件来描述双条件o这表明表明PQ成立成立,等价于正定理等价于正定理PQ和逆和逆定理定理QP都成立都成立 27谢谢观赏2019-8-2316.PQ=(PQ)(QP)从蕴含词来描述双条17.P(QR)=Q(PR)o前提交前提交换o前提条件前提条件P、Q可交可交换次序次序 28谢谢观赏2019-8-2317.P(QR)=Q(PR)前提交换28谢谢观18.(PR)(QR)=(P Q)Ro左端左端说明的是由明的是由P而且由而且由Q都有都有R成立。从成立。从而可以而可以说由由P或或Q就有就有R成立成立,这就是等式就是等式右端右端29谢谢观赏2019-8-2318.(PR)(QR)=(P Q)R左端说明的是由补充补充o等价否定等等价否定等值式式PQ=PQo归谬论(PQ)(PQ)=P30谢谢观赏2019-8-23补充等价否定等值式30谢谢观赏2019-8-232.2.3 置换规则置换规则 o置置换定定义对公式公式A的子公式的子公式,用与之用与之等等值的公式来代的公式来代换便称便称置置换o置置换规则n公式公式A的子公式置的子公式置换后后A化化为公式公式B,必有必有A=Bn当当A是重言式是重言式时,置置换后的公式后的公式B必也是重言式必也是重言式o置置换与代入是有区与代入是有区别的。置的。置换只要求只要求A的某一子公的某一子公式作代式作代换,不必不必对所有同一的子公式都作代所有同一的子公式都作代换31谢谢观赏2019-8-232.2.3 置换规则 置换定义31谢谢观赏2019-8-2代入规则回顾代入规则回顾 oA是一个公式，是一个公式，对A使用代入使用代入规则得公式得公式B，若，若A是重言式，是重言式，则B也是重言式也是重言式o为保保证重言式重言式经代入代入规则仍得到保持，要求仍得到保持，要求n公式中被代公式中被代换的只能是命的只能是命题变元元(原子命原子命题),而不能是而不能是复合命复合命题n对公式中某命公式中某命题变元施以代入，必元施以代入，必须对该公式中出公式中出现的的所有同一命所有同一命题变元代元代换以同一公式以同一公式32谢谢观赏2019-8-23代入规则回顾 A是一个公式，对A使用代入规则得公式B，若A是2.2.4 等值演算举例等值演算举例 例例1:证明明(P(Q R)(Q R)(P R)=R证明明:左端左端=(P(Q R)(Q P)R)(分配律分配律)=(P Q)R)(Q P)R)(结合律合律)=(P Q)R)(Q P)R)(摩根律摩根律)=(P Q)(Q P)R(分配律分配律)=(P Q)(P Q)R(交交换律律)=T R(置置 换)=R(同一律同一律)33谢谢观赏2019-8-232.2.4 等值演算举例 例1:证明(P(QR)例例2:试证 (P Q)(P(Q R)(P Q)(P R)=T证明明:左端左端=(P Q)(P(Q R)(P Q)(P R)(摩根律摩根律)=(P Q)(P Q)(P R)(P Q)(P R)(分配律分配律)=(P Q)(P R)(P Q)(P R)(等等幂律律)=T举例举例 34谢谢观赏2019-8-23例2:试证 (PQ)(P(QR)举问题提出：问题提出：由命题公式写真值表是容易的，那么如由命题公式写真值表是容易的，那么如何由真值表写命题公式呢？何由真值表写命题公式呢？2.3 命题公式与真值表关系命题公式与真值表关系35谢谢观赏2019-8-23问题提出：2.3 命题公式与真值表关系35谢谢观赏20192.3.1 从从T来列写来列写o记忆方法：各项间用记忆方法：各项间用，每项内用每项内用 o每项内书写方法：例每项内书写方法：例真值表中真值表中P=T且且Q=F等价于等价于P Q=To简化方法：有时简化方法：有时A的表达通过的表达通过 A来描述来描述36谢谢观赏2019-8-232.3.1 从T来列写记忆方法：各项间用，每项内用36谢2.3.2 从从F来列写来列写o记忆方法：各项间用记忆方法：各项间用 ，每项内用每项内用 o每项内书写方法：例每项内书写方法：例真值表中真值表中P=T且且Q=F等价于等价于 P Q=Fo简化方法：有时简化方法：有时A的表达通过的表达通过 A来描述来描述37谢谢观赏2019-8-232.3.2 从F来列写记忆方法：各项间用，每项内用37举例举例o从从A的真值的真值Tn直接直接:A=(P Q)(P Q)(P Q)n间接间接:A=A=(P Q)=P Qo从从B的真值的真值FB=(P Q)(P Q)o当当C可取任意值可取任意值C与与P,Q=T,T无关无关,可适当选取可适当选取C的真值的真值,使其表达式简单使其表达式简单38谢谢观赏2019-8-23举例从A的真值T38谢谢观赏2019-8-23作业作业(1)(P37)1(1,3),239谢谢观赏2019-8-23作业(1)(P37)1(1,3),239谢谢观赏2012.4 联结词的完备集联结词的完备集 o问题的提出问题的提出对对n 个命题变项个命题变项P1Pn来说来说,共可定义出多少个共可定义出多少个联结词联结词?在那么多联结词中有多少是相互独立的在那么多联结词中有多少是相互独立的?o3个新联结词：个新联结词：思考：考虑异或联结词与双条件联结词的关系思考：考虑异或联结词与双条件联结词的关系(可利用真值表可利用真值表)40谢谢观赏2019-8-232.4 联结词的完备集 问题的提出思考：考虑异或联结词与双2.4.1 命题联结词的个数命题联结词的个数o第一个第一个问题。可定。可定义多少个多少个联结词？o由命由命题变项和命和命题联结词可以构成无限多个可以构成无限多个合式公式合式公式o把所有的合式公式把所有的合式公式分分类：将等：将等值的公式的公式视为同一同一类，从中，从中选一个作代表称之一个作代表称之为真真值函函项。对一个真一个真值函函项，或者，或者说对于于该类合式公式合式公式，就可定就可定义一个一个联结词与之与之对应例：等价例：等价类。自然数集合。自然数集合N被被3除余数相同的除余数相同的自然数构成自然数构成3个集合个集合N0,N1,N241谢谢观赏2019-8-232.4.1 命题联结词的个数第一个问题。可定义多少个联结词o一元一元联结词是是联结一个命一个命题变项(如如P)的的oP有真假有真假2种种值，因此，因此P(自自变量量)上可定上可定义4种一种一元元联结词fi 或或说真真值函函项fi(P),i=1,2,3,4一元联结词的个数一元联结词的个数42谢谢观赏2019-8-23一元联结词是联结一个命题变项(如P)的一元联结词的个数42谢由真由真值表写出真表写出真值函函项的命的命题公式：公式：f0(P)=F(永假式永假式)f1(P)=P(P自身自身)f2(P)=P(否定否定词)f3(P)=T(永真式永真式)新的公式只有新的公式只有f2(P),与之与之对应的的联结词是否定是否定词一元联结词一元联结词43谢谢观赏2019-8-23由真值表写出真值函项的命题公式：一元联结词43谢谢观赏201o二元二元联结词联结两个命两个命题变项(如如P、Q)o两个两个变项共有共有4种取种取值情形情形,于是于是P、Q上可上可建立起建立起16种不同的真种不同的真值函函项,相相应的可定的可定义出出16个不同的二元个不同的二元联结词g0,g1,g15 图2.4.2给出了出了这些些联结词gi或或说真真值函函项gi(P,Q)的真的真值表定表定义二元联结词的个数二元联结词的个数44谢谢观赏2019-8-23二元联结词联结两个命题变项(如P、Q)二元联结词的个数44谢45谢谢观赏2019-8-2345谢谢观赏2019-8-23根据真值表写出各真值函项的命题表达式根据真值表写出各真值函项的命题表达式:g0(P,Q)=F(永假式永假式)g1(P,Q)=P Q (合取式合取式)g2(P,Q)=P Q g3(P,Q)=(P Q)(P Q)=P(Q Q)=Pg4(P,Q)=P Q g5(P,Q)=(P Q)(P Q)=(P P)Q=Qg6(P,Q)=P Q(异或式异或式)g7(P,Q)=P Q(析取式析取式)g8(P,Q)=P Q=P Q(或非式或非式)g9(P,Q)=P Q(双条件式双条件式)g10(P,Q)=(P Q)(P Q)=(P P)Q=Qg11(P,Q)=P Q=QP(蕴涵式蕴涵式)g12(P,Q)=(P Q)(P Q)=P(Q Q)=Pg13(P,Q)=P Q=PQ(蕴涵式蕴涵式)g14(P,Q)=P Q=P Q(与非式与非式)g15(P,Q)=T(永真式永真式)46谢谢观赏2019-8-23根据真值表写出各真值函项的命题表达式:46谢谢观赏2019-on元元联结词对n个命个命题变元元P1,Pn,每个每个Pi有两有两种取种取值,从而从而对P1Pn来来说共有共有2n种取种取值情形情形于是相于是相应的的真真值函函项就有就有22n个个,或或说可可定定义22n个个n元元联结词n元联结词的个数元联结词的个数47谢谢观赏2019-8-23n元联结词n元联结词的个数47谢谢观赏2019-8-232.4.2 联结词的完备集联结词的完备集 o第二个第二个问题。联结词是否都是独立的，或者是否都是独立的，或者说能否相互表示能否相互表示?o联结词的完的完备集定集定义:设C是是联结词的集合，的集合，如果如果对任一命任一命题公式公式(能直接使用能直接使用T和和F)都都有由有由C中的中的联结词表示出来的公式表示出来的公式(不能直不能直接使用接使用T和和F)与之等与之等值，就，就说C是完是完备的的联结词集合，或集合，或说C是是联结词的完的完备集。集。48谢谢观赏2019-8-232.4.2 联结词的完备集 第二个问题。联结词是否都是独立1.全体全体联结词的无限集合是完的无限集合是完备的的2.,是完是完备的的联结词集合集合 证明明：从：从2.3节介介绍的由真的由真值表列写表列写逻辑公式的公式的过程程可知可知,任一公式都可由任一公式都可由,表示出来表示出来,从而从而,是完是完备的的3.,是是联结词的完的完备集集(独立的完独立的完备集集)证明明：P Q=(P Q)，因此，因此可由可由,表表示示4.,是是联结词的完的完备集集(独立的完独立的完备集集)证明明：P Q=(P Q)，因此，因此可由可由,表表示示完备集完备集 49谢谢观赏2019-8-231.全体联结词的无限集合是完备的完备集 49谢谢观赏2015.,是完是完备集集(独立的完独立的完备集集)因因为：P Q=PQ6.是完是完备集集(独立的完独立的完备集集)7.是完是完备集集(独立的完独立的完备集集)8.,是完是完备的的 因因为它包含了它包含了2中的集合中的集合完备集完备集 50谢谢观赏2019-8-235.,是完备集(独立的完备集)完备集 50谢谢观o,不是完备的不是完备的因为因为F不能仅由该集合的联结词表达出不能仅由该集合的联结词表达出o,不是完备的不是完备的o,的任何子集都是不完备的的任何子集都是不完备的 ,的任何子集也是不完备的的任何子集也是不完备的(如果一个联结词的集合是不完备的，那如果一个联结词的集合是不完备的，那么它的任何子集都是不完备的么它的任何子集都是不完备的)o,不是完备的不是完备的不完备集不完备集 51谢谢观赏2019-8-23,不是完备的不完备集 51谢谢观赏2019最小的联结词的完备集最小的联结词的完备集基底基底 o基底：完基底：完备的的联结词集合的集合的联结词是独立的，是独立的，也就是也就是说这些些联结词不能相互表示不能相互表示o任取四个一元或二元任取四个一元或二元联结词，它，它们必必组不成不成基底基底52谢谢观赏2019-8-23最小的联结词的完备集基底 基底：完备的联结词集合的联结词是基基底底 o只含一个只含一个联结词的的:NK;NAo含两个含两个联结词的的:N,C;N,K;N,A;N,NC;F,C;T,NC;C,NE;E,NC;C,NCo含三个含三个联结词的的:F,K,E;F,A,E;T,K,NE;T,A,NE;K,E,NE;A,E,NE其中：其中：A-K-E-C-N-53谢谢观赏2019-8-23基底 只含一个联结词的:53谢谢观赏2019-8-232.5 对偶式对偶式 o研究目的研究目的n简化等化等值公式的公式的讨论希望一个公式成立，能希望一个公式成立，能够导出与其出与其“相像相像”的公式成立的公式成立n逻辑关系上看，是一种关系上看，是一种逻辑规律律o对偶式定偶式定义：将：将A中出中出现的的、T、F分分别以以、F、T代代换,得到公式得到公式A*,则称称A*是是A的的对偶偶式式,或或说A和和A*互互为对偶式偶式注：注：这里假定里假定A中中仅出出现 、三个三个联结词o若若A=B，必有，必有A*=B*?54谢谢观赏2019-8-232.5 对偶式 研究目的54谢谢观赏2019-8-23o新符号新符号“-”:(代入代入规则、内否式、内否式)若若A=A(P1,Pn)，令，令A=A(P1,Pn)o关于等关于等值的三个定理的三个定理定理定理2.5.1 (A*)=(A)*,(A)=(A)定理定理2.5.2 (A*)*=A,(A)=A定理定理2.5.3 A=A*(摩根律的另一种形式摩根律的另一种形式)更多：更多：(A B)*=A*B*，(A B)-=A-B-(A B)*=A*B*，(A B)-=A-B-对偶式相关定理对偶式相关定理 55谢谢观赏2019-8-23新符号“-”:(代入规则、内否式)对偶式相关定理 55谢谢56性质举例性质举例A=(P (Q R)TA*=(P (Q R)FA-=(P)(Q R)TA*-=(P)(Q R)FA-*=(P)(Q R)F谢谢观赏2019-8-2356性质举例A=(P (Q R)T谢谢观赏定定理理2.5.3 A=A*证明明:可用数学可用数学归纳法法,施施归纳于于A中出中出现的的 联结词个数个数n来来证明明基始基始:设n=0,A中无中无联结词,便有便有 A=P,从而从而 A=P但但 A*=P n=0时定理成立。定理成立。57谢谢观赏2019-8-23定理2.5.3 A=A*证明:可用数学归纳法,施归纳：设n k时定理成立，来定理成立，来证n=k+1时定理也成立定理也成立 n=k+1 1,A中至少有一个中至少有一个联结词，可分可分为三种情形三种情形A=A1,A=A1 A2,A=A1 A2 其中其中A1,A2中中联结词个数个数k。依依归纳法假法假设，A1=A1*,A2=A2*定定理理2.5.3 A=A*58谢谢观赏2019-8-23归纳：设n k时定理成立，来证n=k+1时定理也成立当当 A=A1时 A=(A1)A=A1 =(A1*)归纳法假法假设 =(A1)*定理定理2.5.1,2.5.2 =A*A=A1定定理理2.5.3 A=A*59谢谢观赏2019-8-23当 A=A1时 定理2.5.3 A=A*5当当 A=A1 A2时，A=(A1 A2)=A1 A2摩根律摩根律 =A1*A2*归纳法假法假设 =(A1*A2*)A定定义 =(A1 A2)*A*定定义 =A*另一种情况同理，从而定理得另一种情况同理，从而定理得证。定定理理2.5.3(摩摩根根律律)A=A*60谢谢观赏2019-8-23当A=A1A2时，定理2.5.3(摩根律)A 定理定理2.5.6(1)A与与A同永真同永真,同可同可满足足 (2)A与与A*同永真同永真,同可同可满足足注：注：“A和和B”同永真表示：同永真表示：A永真当且永真当且仅当当B永真永真证明：明：设A是由命是由命题变项P1,Pn构成的命构成的命题公式。公式。(1)如果如果A永真，根据代入永真，根据代入规则，则A-永真。永真。如果如果A-永真，永真，则(A-)-永真，又根据定理永真，又根据定理2.5.2有有 A=(A-)-,所以所以A永真永真(2)根据定理根据定理2.5.3，A=A*，所以根据，所以根据(1)可得可得(2)成立成立对偶式相关定理对偶式相关定理 61谢谢观赏2019-8-23定理2.5.6(1)A与A同永真,同可满足对偶式相关定理定理 2.5.4 若若A=B，必有，必有A*=B*证明明:因因为A=B等价于等价于AB 永真等价于永真等价于 AB永真。永真。依定理依定理2.5.3,A=A*,B=B*于是于是A*B*永真，永真，则(A*-B*-)-永真永真(根据代入根据代入规则，A永真，永真，A-永真永真)亦即亦即 A*B*永真永真故故 A*=B*对偶式相关定理对偶式相关定理 62谢谢观赏2019-8-23定理 2.5.4 若A=B，必有A*=B*对偶式相关定定理定理2.5.5 若若AB永真永真,必有必有B*A*永真永真或者，或者，AB和和B*A*同永真同永真证明明:(1)如果如果AB永真，永真，则 BA永真永真(逆否命逆否命题)根据定理根据定理2.5.3，A=A*-,B=B*-所以所以B*-A*-永真，永真，则(B*-A*-)-永真永真(代入代入规则)，即即B*A*永真永真(2)如果如果B*A*永真，根据永真，根据(1)有有:(A*)*(B*)*永真永真根据定理根据定理2.5.2，A=(A*)*,B=(B*)*所以所以AB永真永真 对偶式相关定理对偶式相关定理 63谢谢观赏2019-8-23定理2.5.5 若AB永真,必有B*A*永真对偶式相作业作业(2)(P37)3，4(2)64谢谢观赏2019-8-23作业(2)(P37)3，4(2)64谢谢观赏2019-8-2.6 范范式式on 个命个命题变项所能所能组成的具有不同真成的具有不同真值的命的命题公式公式仅有有22n个个,然而与任何一个命然而与任何一个命题公式等公式等值而形式而形式不同的命不同的命题公式可以有无公式可以有无穷多个多个o等等值的公式，能否都可以化的公式，能否都可以化为某一个某一个统一的一的标准形准形式？式？n希望希望这种种标准形能准形能为我我们的的讨论带来些方便，如借助于来些方便，如借助于标准形准形对任意两个形式上不同的公式，可判断它任意两个形式上不同的公式，可判断它们的是的是否等否等值n借助于借助于标准形容易判断任一公式是否准形容易判断任一公式是否为重言式或矛盾式重言式或矛盾式65谢谢观赏2019-8-232.6 范式n 个命题变项所能组成的具有不同真值的命题公式2.6.1 范式范式o若干若干术语n简单命命题P及其否定式及其否定式 P统称称为文字文字n一些文字的合取称一些文字的合取称为合取式合取式n一些文字的析取称一些文字的析取称为析取式析取式(也称子句也称子句)nP与与 P称称为互互补对n析取范式，形如：析取范式，形如：A1 A2 An其中其中Ai(i=1,n)为合取式合取式n合取范式，形如：合取范式，形如：A1 A2 An其中其中Ai(i=1,n)为析取式析取式66谢谢观赏2019-8-232.6.1 范式若干术语66谢谢观赏2019-8-2367范式举例范式举例op,qop1 p2,q1 q2谢谢观赏2019-8-2367范式举例p,q谢谢观赏2019-8-23范式定理范式定理o范式定理：任一命范式定理：任一命题公式都存在与之等公式都存在与之等值的析取范式、合取范式的析取范式、合取范式o求范式三步曲：求范式三步曲：1)消去消去和和2)否定深入到命否定深入到命题变项3)使用分配律的等使用分配律的等值变换68谢谢观赏2019-8-23范式定理范式定理：任一命题公式都存在与之等值的析取范式、合取举例举例o求求(P Q)(P Q)的析取范式的析取范式(P Q)(P Q)=(P Q)(P Q)(P Q)(P Q)=(P Q P Q)(P Q)(P Q)=(P Q P Q)(P P)(P Q)(QP)(Q Q)(析取范式析取范式)=(P Q)(QP)(析取范式，析取范式，简化化)注：范式的不唯一性注：范式的不唯一性69谢谢观赏2019-8-23举例求(PQ)(PQ)的析取范式69谢谢观赏2019举例举例o求求(P Q)(P Q)的合取范式的合取范式(P Q)(P Q)=(P Q)(QP)(析取范式，析取范式，简化化)=(P Q)(P P)(Q Q)(Q P)(合取范式合取范式)=(P Q)(Q P)(合取范式，合取范式，简化化)注：已知一种范式，可以使用分配律求另一种范式注：已知一种范式，可以使用分配律求另一种范式70谢谢观赏2019-8-23举例求(PQ)(PQ)的合取范式70谢谢观赏2019p 判断重言式判断重言式合取范式中所有析取式都有互补对合取范式中所有析取式都有互补对p 判断矛盾式判断矛盾式析取范式中所有合取式都有互补对析取范式中所有合取式都有互补对p 判断两公式是否等值判断两公式是否等值范式不唯一，引入唯一的主范式，范式不唯一，引入唯一的主范式，便于判别公式相等便于判别公式相等范式功能范式功能71谢谢观赏2019-8-23 判断重言式范式功能71谢谢观赏2019-8-232.6.2 主范式主范式o主析取范式主析取范式n极小极小项定定义与与编码Q1 Qn是由是由n个命个命题变项P1,Pn组成的公式成的公式,其其中中Qi=Pi或者或者Pi,我我们称其称其为极小极小项,一般用一般用mj表示表示例：例：P1,P2的极小的极小项有四个有四个P1 P2(m0),P1 P2(m1),P1 P2(m2),P1 P2(m3)n主析取范式定主析取范式定义 仅由极小由极小项构成的析取范式构成的析取范式n主析取范式唯一性定理主析取范式唯一性定理任一含有任一含有n个命个命题变项的公式，都有唯一一个与之等的公式，都有唯一一个与之等值的恰的恰仅含含这n个命个命题变项的主析取范式的主析取范式极小项必须含有极小项必须含有Q1,Qn全部全部n个文字个文字72谢谢观赏2019-8-232.6.2 主范式主析取范式极小项必须含有Q1,Qno由真值表写主析取范式：从由真值表写主析取范式：从T写写P Q=(P Q)(P Q)=m0 m3=0,3o由析取范式写主析取范式：填满命题变项法由析取范式写主析取范式：填满命题变项法,永真式永真式P=P(Q Q)=(P Q)(P Q)Q=Q(P P)=(Q P)(Q P)PQ=P Q=(P Q)(P Q)(Q P)(Q P)=(P Q)(P Q)(P Q)=m0 m1 m3 =0,1,3主析取范式主析取范式73谢谢观赏2019-8-23由真值表写主析取范式：从T写主析取范式73谢谢观赏2019-p所有可能极小项的个数：所有可能极小项的个数：2np每个极小项只在一个解释下为真每个极小项只在一个解释下为真p对于每个解释只有一个极小项为真对于每个解释只有一个极小项为真 p极小项互不相等，且极小项互不相等，且mi mj=F(i j)p任一含有任一含有n个变项的公式，都可由个变项的公式，都可由k个个(k2n)极小项的析取来表极小项的析取来表示；或者说所有的极小项可建立一个示；或者说所有的极小项可建立一个“坐标系坐标系”p恰由恰由2n个极小项的析取构成的公式，必为重言式个极小项的析取构成的公式，必为重言式 pA与与 A的主析取范式关系的主析取范式关系A由由k个极小项的析取组成，那么其余的个极小项的析取组成，那么其余的2n-k个极小项的析取必个极小项的析取必是是 A例如例如P1,P2,P3构成的构成的A=0,2,4,A=1,3,5,6,7极小项性质极小项性质74谢谢观赏2019-8-23所有可能极小项的个数：2n极小项性质74谢谢观赏2019-8主合取范式主合取范式o极大项定义与编码极大项定义与编码Q1 Qn是由是由n个命题变项个命题变项P1,Pn组成的公式组成的公式,其中其中Qi=Pi或者或者Pi(i=1,n),我们称其为极大项我们称其为极大项,一般用一般用Mj表示表示(0j2n-1)例：例：P1,P2的极大项有四个的极大项有四个P1 P2(M0),P1 P2(M1),P1 P2(M2),P1 P2(M3)o主合取范式定义主合取范式定义仅由极大项构成的合取范式仅由极大项构成的合取范式o主合取范式唯一性定理主合取范式唯一性定理任一含有任一含有n个命题变项的公式，都有唯一一个与之等值的恰仅含个命题变项的公式，都有唯一一个与之等值的恰仅含这这n个命题变项的主合取范式个命题变项的主合取范式o由真值表写主合取范式由真值表写主合取范式(从从F写写)o由合取范式写主合取范式由合取范式写主合取范式(填满命题变项法填满命题变项法,矛盾式矛盾式)极大项必须含有极大项必须含有Q1,Qn全部全部n个文字个文字75谢谢观赏2019-8-23主合取范式极大项定义与编码极大项必须含有Q1,Qn全极大项性质极大项性质p所有可能极大项的个数：所有可能极大项的个数：2np每个极大项只在一个解释下为假每个极大项只在一个解释下为假p对于每个解释只有一个极大项为假对于每个解释只有一个极大项为假 p极大项互不相等，且极大项互不相等，且Mi Mj=T(i j)p任一含有任一含有n个变项的公式，都可由个变项的公式，都可由k个个(k2n)极大项的合取来表极大项的合取来表示；或者说所有的极大项可建立一个示；或者说所有的极大项可建立一个“坐标系坐标系”p恰由恰由2n个极大项的合取构成的公式，必为矛盾式个极大项的合取构成的公式，必为矛盾式 pA与与 A的主合取范式关系的主合取范式关系A由由k个极大项的合取组成，那么其余的个极大项的合取组成，那么其余的2n-k个极大项的合取必个极大项的合取必是是 A例如例如P1,P2,P3构成的构成的A=0,2,5,A=1,3,4,6,776谢谢观赏2019-8-23极大项性质所有可能极大项的个数：2n76谢谢观赏2019-8主析取范式与主合取范式的转换主析取范式与主合取范式的转换设设A是由命题变项是由命题变项P1,P2,P3构成的公式构成的公式o已知主析取范式已知主析取范式A=0,1,4,5,7=(0,1,7-0,1,4,5,7)补补=2,3,6补补=5,4,1o已知主合取范式已知主合取范式A=1,4,5=(0,1,7-1,4,5补补)=(0,1,7-6,3,2)=0,1,4,5,777谢谢观赏2019-8-23主析取范式与主合取范式的转换设A是由命题变项P1,P2,主析取范式与主合取范式的转换主析取范式与主合取范式的转换注意注意o从真从真值表列写公式的主析取范式和主合取范式表列写公式的主析取范式和主合取范式时，除了分除了分别从从T和和F列写外，在填写合取式和析取式列写外，在填写合取式和析取式时是取是取变项还是其否定是有区是其否定是有区别的，的，这就是主合取就是主合取范式、主析取范式范式、主析取范式转换过程要求程要求补的原因的原因o数字数字补不同于不同于补集。集。这里的数字求里的数字求补是是对2n-1=23-1=7而言的，如而言的，如2的的补是是5，因，因为2+5=778谢谢观赏2019-8-23主析取范式与主合取范式的转换注意78谢谢观赏2019-8-2主范式的用途主范式的用途与真值表相同与真值表相同(1)求公式的成真求公式的成真赋值和成假和成假赋值例如：例如：(PQ)R m1 m3 m5 m6 m7，其成真指派其成真指派为001,011,101,110,111，其余的指派其余的指派 000,010,100为成假指派成假指派.类似地，由主合取范式也可立即求出成假指派和似地，由主合取范式也可立即求出成假指派和成真指派成真指派 79谢谢观赏2019-8-23主范式的用途与真值表相同(1)求公式的成真赋值和成假主范式的用途主范式的用途(续续)(2)判断公式的判断公式的类型型 设A含含n个命个命题变项，则 A为重言式重言式A的主析取范式含的主析取范式含2n个极小个极小项 A的主合取范式的主合取范式为TA为矛盾式矛盾式 A的主析取范式的主析取范式为F A的主合取范式含的主合取范式含2n个极大个极大项A为非重言式的可非重言式的可满足式足式A的主析取范式中至少含一个且不含全部极小的主析取范式中至少含一个且不含全部极小项A的主合取范式中至少含一个且不含全部极大的主合取范式中至少含一个且不含全部极大项 80谢谢观赏2019-8-23主范式的用途(续)(2)判断公式的类型 80谢谢观赏20主范式的用途主范式的用途(续续)(3)判断两个公式是否等值判断两个公式是否等值例例 用主析取范式判断下述两个公式是否等值：用主析取范式判断下述两个公式是否等值：P(QR)与与(P Q)R P(QR)与与(PQ)R解解 P(QR)=m0 m1 m2 m3 m4 m5 m7 (P Q)R =m0 m1 m2 m3 m4 m5 m7 (PQ)R=m1 m3 m4 m5 m7显见，显见，中的两公式等值，而中的两公式等值，而的不等值的不等值.81谢谢观赏2019-8-23主范式的用途(续)判断两个公式是否等值81谢谢观赏2019-作业作业(3)(P37)5(1，5，8)82谢谢观赏2019-8-23作业(3)(P37)5(1，5，8)82谢谢观赏2019-2.7 推理形式推理形式o自然语言推理自然语言推理n前提前提1：如果我今天病了，那么我没来上课：如果我今天病了，那么我没来上课n前提前提2：今天我病了：今天我病了n结论：所以今天我没来上课结论：所以今天我没来上课o推理形式推理形式n引入符号引入符号,形式化并用形式化并用条件式条件式表示出来表示出来例：例：(P Q)P)Qn正确的推理形式正确的推理形式o前提真，结论必真的推理形式前提真，结论必真的推理形式o(PQ)Q)P 正确的推理形式正确的推理形式(PQ)P)Q 不正确的推理形式不正确的推理形式P QP Q83谢谢观赏2019-8-232.7 推理形式自然语言推理PQPQ83谢谢观赏201重言蕴涵重言蕴涵o重言蕴涵重言蕴涵n对于公式对于公式A,B,如果当如果当A取值为真时，取值为真时，B必取值为真，则必取值为真，则称称A重言重言(永真永真)蕴涵蕴涵B，或称，或称B是是A的逻辑推论。记为：的逻辑推论。记为：A B(是真值关系，并非逻辑联结词是真值关系，并非逻辑联结词)o重言蕴涵与正确推理形式重言蕴涵与正确推理形式n如果如果A B，则，则AB是正确的推理形式是正确的推理形式n如果如果AB是正确的推理形式，可以用是正确的推理形式，可以用A B来表示来表示o用真值表法判断用真值表法判断A Bn查看真值表，如果所有使查看真值表，如果所有使A为真的解释，亦能使为真的解释，亦能使B为真，为真，则则A B84谢谢观赏2019-8-23重言蕴涵重言蕴涵84谢谢观赏2019-8-23 如果如果A B,A为重言式为重言式,则则B也是重言式也是重言式 如果如果A B,B A同时成立同时成立,必有必有A=B如果如果A=B,必有必有A B和和B A 如果如果A B,B C,则则A C 如果如果A B,A C,则则A BC 如果如果A C,B C,则则A B C重言蕴涵的结果重言蕴涵的结果85谢谢观赏2019-8-23 如果A B,A为重言式,则B也是重言式重言蕴涵的结2.8 基本的推理公式基本的推理公式1.(P Q)P化简律化简律2.(PQ)P 3.(PQ)Q4.P (P Q)附加律附加律 5.P PQ6.Q PQ7.(P Q)P Q 析取三段论析取三段论8.(PQ)P Q 假言推理、分离规则假言推理、分离规则假言推理、分离规则假言推理、分离规则86谢谢观赏2019-8-232.8 基本的推理公式1.(PQ)P化简律869.(PQ)Q P 拒取式拒取式10.(PQ)(QR)(PR)假言三段论、假言三段论、三段论三段论三段论三段论11.(PQ)(QR)(PR)等价三段论等价三段论12.(PR)(QR)(P Q)R 构造性二难构造性二难(特殊形式特殊形式)13.(PQ)(RS)(P R)(Q S)构造性二难构造性二难14.(PQ)(RS)(Q S)(P R)破破坏性二难坏性二难15.(QR)(P Q)(P R)16.(QR)(PQ)(PR)注：真值表证明，或者语义上直接说明注：真值表证明，或者语义上直接说明基本的推理公式基本的推理公式87谢谢观赏2019-8-239.(PQ)Q P 2.8.2 证明推理公式的方法证明推理公式的方法(五种五种)1.A B成立的充分必要条件是成立的充分必要条件是AB(或或AB)为为重言式重言式证明：如果证明：如果A B,那么在任一解释下那么在任一解释下,A真真B必真必真,而而不会出现不会出现A真真B假的情况假的情况,于是于是AB为重言式。为重言式。1.如果如果AB为重言式为重言式,则则在任一解释下在任一解释下,若若A为真为真,B只能为真不可能为假只能为真不可能为假,从而有从而有A B2.证明证明AB为重言式的方法为重言式的方法1.真值表、等值演算、范式真值表、等值演算、范式88谢谢观赏2019-8-232.8.2 证明推理公式的方法(五种)A B成立的充分例例1 用等值演算法证明用等值演算法证明(PQ)PQ为重言式为重言式 (PQ)PQ(P Q)P)Q(P Q)P)Q Q PQ T 举例举例89谢谢观赏2019-8-23例1 用等值演算法证明(PQ)PQ为重言式举例89谢谢例例2 用用主析取范式主析取范式法证明法证明(PQ)QP不是重言式不是重言式 (PQ)QP(P Q)Q)P(P Q)Q)P(吸收律吸收律)Q P(Q P)(Q P)(PQ)(PQ)(P Q)(PQ)(PQ)m0 m2 m3缺少缺少m1即即(P Q),所以所以(PQ)QP不是重言式，或者不是重言式，或者说推理形式说推理形式(PQ)QP不正确不正确举例举例90谢谢观赏2019-8-23例2 用主析取范式法证明(PQ)QP不是重言式举例902.AB成立的充分必要条件是成立的充分必要条件是AB为重言式为重言式,即即A B是是矛盾式矛盾式3.(逆否定理逆否定理)AB成立的充分必要条件成立的充分必要条件B A4.解释法解释法例例:(PQ)(QR)(PR)若若(PQ)(QR)T,则同时有则同时有PQT,QR=T若若P=T,则则Q=T,进而进而R=T.故故PRT若若P=F,则则Q可取任意值可取任意值:(1)Q=T,则则R=T;(2)Q=F,则则R取何值取何值无论如何无论如何,PR=T5.真值表法真值表法,即通过真值表检验即通过真值表检验A为真时为真时B一定为真一定为真注：注：证明证明AB时不考虑时不考虑A为假的情况为假的情况证明推理公式的方法证明推理公式的方法91谢谢观赏2019-8-232.AB成立的充分必要条件是AB为重言式,即AB上述方法的特点上述方法的特点o都是从真值的角度进行论证和解释都是从真值的角度进行论证和解释o看不出由前提看不出由前提A到结论到结论B的推演过程的推演过程o难于扩展到谓词逻辑的推演过程难于扩展到谓词逻辑的推演过程92谢谢观赏2019-8-23上述方法的特点都是从真值的角度进行论证和解释92谢谢观赏202.9 推理演算推理演算(证明推理公式AB的新方法)o基本思想：从前提基本思想：从前提A1,An出发出发(即即A=A1 A2 An)运用推理规则和基本推理公式，运用推理规则和基本推理公式，逐步推演出结论逐步推演出结论B，即证明即证明ABo推理规则推理规则前提引入规则前提引入规则推理过程中可以随时引入前提推理过程中可以随时引入前提A1,An结论引用规则结论引用规则推理过程中得到的中间结论可作为后续推理的前提推理过程中得到的中间结论可作为后续推理的前提代入规则代入规则(参考参考P8)推理过程中对推理过程中对重言式重言式的命题变项可使用该规则的命题变项可使用该规则93谢谢观赏2019-8-232.9 推理演算(证明推理公式AB的新方法)基本思想：从前推理规则推理规则4.置换规则置换规则(参考参考P18)推理过程中命题公式中任何部分公式都可由与之推理过程中命题公式中任何部分公式都可由与之等值等值的的公式公式置换置换5.分离规则分离规则(假言推理假言推理)已知命题公式已知命题公式AB和和A,则有命题公式则有命题公式B(B被分离出来被分离出来)条件证明规则条件证明规则(附加前提附加前提)A1 A2B与与A1 A2 B是等价的。即结论方的条件是等价的。即结论方的条件A2移