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

《第二章命题逻辑的等值和推理演算优秀课件.ppt》由会员分享，可在线阅读，更多相关《第二章命题逻辑的等值和推理演算优秀课件.ppt（65页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章命题逻辑的等值和推理演算第1页，本讲稿共65页l等值演算等值演算(考察逻辑关系符考察逻辑关系符 )：1)等值定理、公式等值定理、公式 2)由真值表写命题公式由真值表写命题公式(由由T写、由写、由F写写)3)联结词的完备集联结词的完备集(由个别联结词表示所由个别联结词表示所有联结词的问题有联结词的问题)4)对偶式对偶式(命题公式的对偶性命题公式的对偶性)5)范式范式(命题公式的统一标准命题公式的统一标准)第2页，本讲稿共65页推理演算推理演算(考察逻辑关系符考察逻辑关系符 )：1)推理形式推理形式(正确推理形式的表示正确推理形式的表示)2)基本推理公式基本推理公式(各种三段论及五种证明方各

2、种三段论及五种证明方法法)3)推理演算推理演算(证明推理公式的第六种方法，证明推理公式的第六种方法，使用推理规则使用推理规则)4)归结推理法归结推理法(证明推理公式的第七种方法，证明推理公式的第七种方法，常用反证法常用反证法)第3页，本讲稿共65页2.1.1 2.1.1 等值的定义等值的定义 l等值的定义：等值的定义：给定两个命题公式给定两个命题公式A A和和B,B,而而P P1 1PPn n是出现于是出现于A A和和B B中的中的所有命题变所有命题变项项,那么公式那么公式A A和和B B共有共有2 2n n个解释个解释,若对若对其中的其中的任一解释任一解释,公式公式A A和和B B的真值都相

3、的真值都相等等,就称就称A A和和B B是等值的是等值的(或等价的或等价的)。记。记作作A=BA=B或或A A B B。注意逻辑关系词注意逻辑关系词2.1 2.1 等值定理等值定理 第4页，本讲稿共65页例例1:1:证明证明(P(P P)Q=QP)Q=Q证明证明:画出画出(P(P P)QP)Q与与Q Q的真值表可看出等的真值表可看出等式是成立的。式是成立的。第5页，本讲稿共65页例例2:2:证明证明PP P=QP=Q Q Q 证明证明:画出画出PP P,QP,Q Q Q的真值表的真值表,可看可看出它们是等值的出它们是等值的,而且它们都是重言式。而且它们都是重言式。第6页，本讲稿共65页l等值定

4、义补充说明：等值定义补充说明：两个公式等值并不要两个公式等值并不要求它们一定含有相同的命题变项求它们一定含有相同的命题变项。若仅在。若仅在等式一端的公式里有变项等式一端的公式里有变项P P出现出现,那么等式那么等式两端的公式其真值均与两端的公式其真值均与P P无关。例无关。例1 1中公式中公式(P(P P)QP)Q与与Q Q的真值都同的真值都同P P无关无关,例例2 2中中PP P,QP,Q Q Q都是重言式都是重言式,它们的真值也它们的真值也都与都与P P、Q Q无关。无关。第7页，本讲稿共65页2.1.2 2.1.2 等值定理等值定理 l定理定理2.1.1 2.1.1 对公式对公式A A和

5、和B,A=BB,A=B的充分必的充分必要条件是要条件是A A B B是重言式。是重言式。即任意解释下，即任意解释下，A A和和B B都有相同的真值。都有相同的真值。证明：定理中的两部分都与上一行等同。证明：定理中的两部分都与上一行等同。第8页，本讲稿共65页v “”作为逻辑关系符是一种作为逻辑关系符是一种等价关系等价关系A=BA=B是表示公式是表示公式A A与与B B的一种关系。这种关系的一种关系。这种关系具有三个性质具有三个性质:1.1.自反性自反性 A=A A=A。2.2.对称性对称性 若若A=BA=B则则B=AB=A。3.3.传递性传递性 若若A=B,B=CA=B,B=C则则A=CA=C

6、。这三条性质体现了这三条性质体现了“”的实质含义。的实质含义。第9页，本讲稿共65页2.2 2.2 等值公式等值公式(真值表验证，真值表验证，VennVenn图理解图理解)2.2.1 基本的等值公式(特别注意蓝色字特别注意蓝色字)1.双重否定律P=P2.结合律(PQ)R=P(QR)(PQ)R=P(QR)(P Q)R=P (Q R)第10页，本讲稿共65页3.交换律PQ=QPPQ=QPP Q=Q P4.分配律分配律P(QR)=(PQ)(PR)P(QR)=(PQ)(PR)P(QR)=(PQ)(PR)5.等幂律(恒等律)PP=PPP=PPP=TPP=T第11页，本讲稿共65页6.吸收律P(PQ)=P

7、P(PQ)=P7.摩根律摩根律(PQ)=PQ(PQ)=PQ对蕴涵词、双条件词作否定有(PQ)=PQ(PQ)=PQ=PQ=(PQ)(PQ)第12页，本讲稿共65页8.同一律PF=PPT=PTP=PTP=P还有PF=PFP=P第13页，本讲稿共65页 9.零律PT=TPF=F还有PT=TFP=T10.补余律PP=TPP=F还有PP=P PP=PPP=F 第14页，本讲稿共65页VennVenn图图l这种图是将这种图是将P P、Q Q理解为某总体论域上理解为某总体论域上的子集合的子集合,而规定而规定PQPQ为两集合的公为两集合的公共部分共部分(交集合交集合),PQ),PQ为两集合的全为两集合的全部部

8、(并集合并集合),),P P为总体论域为总体论域(如矩形如矩形域域)中中P P的余集。的余集。第15页，本讲稿共65页VennVenn图实例图实例1.P(PQ)=P2.P(PQ)=P3.(PQ)=PQ第16页，本讲稿共65页VennVenn图可以用来理解集图可以用来理解集合间、命题逻辑中、合间、命题逻辑中、部部分分信息量间的一些关系。信息量间的一些关系。第17页，本讲稿共65页2.2.2 2.2.2 若干常用的等值公式若干常用的等值公式 l等值演算中，等值演算中，由于人们对由于人们对、更为熟更为熟悉，常将含有悉，常将含有和和的公式化成仅含有的公式化成仅含有、的公式。这也是证明和理解含有的公式。

9、这也是证明和理解含有，的公式的一般方法。的公式的一般方法。但后面的推理演但后面的推理演算中，更希望见到算中，更希望见到和和.第18页，本讲稿共65页12.逆否定理PQ=QP11.PQ=P Q第19页，本讲稿共65页13.前提合并P(QR)=(PQ)R17.前提交换P(QR)=Q(PR)18.另一种前提合并(PR)(QR)=(PQ)R第20页，本讲稿共65页14.从取真来描述双条件词从取真来描述双条件词PQ=(PQ)(PQ)15.从取假来描述双条件词从取假来描述双条件词PQ=(PQ)(PQ)16.从蕴涵词描述双条件词从蕴涵词描述双条件词PQ=(PQ)(QP)第21页，本讲稿共65页2.2.3 2

10、.2.3 置换规则置换规则(注意与代入规则注意与代入规则p8p8的区别的区别)置换定义置换定义：对公式对公式A的子公式的子公式,用与之等值的用与之等值的公式来代换便称置换。公式来代换便称置换。置换规则：置换规则：将公式将公式A的子公式置换后，的子公式置换后，A化为化为公式公式B,必有必有A=B。置换与代入是有区别的：置换与代入是有区别的：代入规则要求操作代入规则要求操作重言式、对所有同一命题变元都作代换重言式、对所有同一命题变元都作代换第22页，本讲稿共65页2.2.4 2.2.4 等值演算举例等值演算举例 例例1:证明证明(P(QR)(QR)(PR)=R证明证明:左端左端=(P(QR)(QP

11、)R)(分配律分配律)=(P Q)R)(QP)R)(结合律结合律)=(PQ)R)(QP)R)(摩根律摩根律)=(PQ)(QP)R(分配律分配律)=(PQ)(PQ)R(交换律交换律)=TR(置置 换换)=R(同一律同一律)第23页，本讲稿共65页例例2:试证试证 (PQ)(P(Q R)(P Q)(P R)=T证明证明:左端左端=(PQ)(P(QR)(PQ)(PR)(摩根律摩根律)=(PQ)(PQ)(PR)(PQ)(PR)(分配律分配律)=(PQ)(PR)(PQ)(PR)(等幂律等幂律)=T(置换规则置换规则)第24页，本讲稿共65页问题提出：由命题公式写真值表是容易的，那问题提出：由命题公式写真

12、值表是容易的，那么如何由真值表写命题公式呢？么如何由真值表写命题公式呢？2.3 命题公式与真值表关系命题公式与真值表关系第25页，本讲稿共65页2.3.1 2.3.1 从从T T来列写来列写1.1.记忆方法：各项间用记忆方法：各项间用，每项内用每项内用2.2.每项内书写方法：例每项内书写方法：例 真值表中真值表中P=FP=F且且Q=FQ=F等价于等价于 PP Q=TQ=T3.3.简化方法：有时简化方法：有时A A的表达通过的表达通过 A A来描述来描述第26页，本讲稿共65页2.3.2 2.3.2 从从F F来列写来列写1.1.记忆方法：各项间用记忆方法：各项间用 ，每项内用每项内用2.2.每

13、项内书写方法：例每项内书写方法：例 真值表中真值表中P=TP=T且且Q=FQ=F等价于等价于 P PQ=FQ=F3.3.简化方法：有时简化方法：有时A A的表达通过的表达通过 A A来描述来描述4.4.任意值的问题任意值的问题(图图2.3.1)2.3.1)第27页，本讲稿共65页2.4 2.4 联结词的完备集联结词的完备集 问题的提出：问题的提出：对对n n 个命题变项个命题变项P P1 1PPn n来说来说,共共可定义出多少个联结词可定义出多少个联结词?在那么多联结词中在那么多联结词中有多少是相互独立的有多少是相互独立的?介绍介绍3 3个新型联结词：个新型联结词：异或异或 :PQ=(PQ)(

14、PQ)与非与非 :P Q=(PQ)或非或非 :P Q=(PQ)第28页，本讲稿共65页2.4.1 2.4.1 命题联结词的个数命题联结词的个数l要解决本节提出的第一个问题，首先要把要解决本节提出的第一个问题，首先要把n n个命题变项构造出的无限多个合式公式个命题变项构造出的无限多个合式公式分分类。类。l将等值的公式视为同一类，从中选一个作将等值的公式视为同一类，从中选一个作代表称之为真值函项。代表称之为真值函项。对一个真值函项，对一个真值函项，或者说对于该类合式公式或者说对于该类合式公式，就可定义一个，就可定义一个联结词与之对应。联结词与之对应。第29页，本讲稿共65页l例：一元联结词例：一元

15、联结词是联结一个命题变项是联结一个命题变项(如如P)P)的。的。P P有真假有真假2 2种值，因此种值，因此P(P(自变量自变量)上上可定义可定义4 4种一元联结词种一元联结词(真值函项、函数真值函项、函数)：真值表真值表见图。见图。f f0 0 f f1 1 f f2 2 f f3 3 或称或称f f0 0(P)f(P)f1 1(P)f(P)f2 2(P)f(P)f3 3(P)(P)第30页，本讲稿共65页由真值表由真值表写出真值函项的命题公式写出真值函项的命题公式：f0(P)=Ff1(P)=Pf2(P)=Pf3(P)=T第31页，本讲稿共65页l例：二元联结词例：二元联结词联结两个命题变项

16、联结两个命题变项(如如P P、Q)Q)，两个变项共有，两个变项共有4 4种取值情形种取值情形,于是于是P P、Q Q上可建立起上可建立起1616种不同的真值函项种不同的真值函项,相应相应的可定义出的可定义出1616个不同的二元联结词个不同的二元联结词g g0 0,g,g1 1,g,g1515 图图2.4.22.4.2给出了这些联结词给出了这些联结词g gi i或说真值函或说真值函项项g gi i(P,Q)(P,Q)的的真值表定义真值表定义。第32页，本讲稿共65页第33页，本讲稿共65页根据真值表写出各真值函项的命题表达式根据真值表写出各真值函项的命题表达式:g0(P,Q)=Fg1(P,Q)=

17、PQg2(P,Q)=P Qg3(P,Q)=(P Q)(PQ)=P(QQ)=Pg4(P,Q)=PQg5(P,Q)=(PQ)(PQ)=(PP)Q=Qg6(P,Q)=PQg7(P,Q)=PQg8(P,Q)=P Q=P Qg9(P,Q)=P Qg10(P,Q)=(P Q)(P Q)=(PP)Q=Qg11(P,Q)=P Q=QPg12(P,Q)=(P Q)(PQ)=P(QQ)=Pg13(P,Q)=PQ=P Qg14(P,Q)=P Q=P Qg15(P,Q)=T第34页，本讲稿共65页l联结词个数统计：联结词个数统计：对对n n 个命题变元个命题变元P P1 1PPn,n,每个每个P Pi i有两种取值有

18、两种取值,从而对从而对P P1 1PPn n来说共有来说共有2 2n n种取值情形种取值情形。于是相应的于是相应的直值函项就有直值函项就有2 22 2n n个个,或说或说可定义可定义2 22 2n n个个n n元联结词。元联结词。第35页，本讲稿共65页2.4.2 2.4.2 联结词的完备集联结词的完备集 l关于本节提出的第二个问题，也就是说这关于本节提出的第二个问题，也就是说这些联结词是否能相互些联结词是否能相互通过组合通过组合来表示呢来表示呢?l联结词的完备集定义联结词的完备集定义:设C是联结词的集合，如果对任一命题公式(能直接使用能直接使用T T和和F F)都有由C中的联结词表示出来的公

19、式(不能直接不能直接使用使用T T和和F F)与之等值，就说C是完备的联结完备的联结词集合词集合，或说C是联结词的完备集。联结词的完备集。第36页，本讲稿共65页l书上的书上的8 8个完备集个完备集(提问提问)：1.1.显然全体联结词的无限集合是完备的。显然全体联结词的无限集合是完备的。2.定理定理:,是完备的联结词集合。是完备的联结词集合。证明：从证明：从2.32.3节介绍的由真值表列写逻辑公式的过程可节介绍的由真值表列写逻辑公式的过程可知知,任一公式都可由任一公式都可由,表示出来表示出来,从而从而 ,是完备的。是完备的。8.8.,是完备的是完备的,因为它包含了因为它包含了2 2中的集合。中

20、的集合。另外，另外，,不是完备的，因不是完备的，因为为F F不能仅由该集合的联结词表达出来。不能仅由该集合的联结词表达出来。,也不是完备的。也不是完备的。第37页，本讲稿共65页3.3.,4.,4.,都是联结词的完都是联结词的完备集。备集。证明：证明：PQ=PQ=(PP Q)Q)PQ=PQ=(PP Q)Q)这说明这说明,可由可由 ,表示表示,可由可由 ,表示表示,故由定理故由定理2.4.12.4.1可证本结论。可证本结论。5.5.,是完备集。是完备集。证明：证明：6.6.是完备集。是完备集。证明：证明：7.7.是完备集。是完备集。证明：证明：第38页，本讲稿共65页特别注意特别注意如果一个联结

21、词的集合是不完备的，那么它的如果一个联结词的集合是不完备的，那么它的任何子集都是不完备的。因此，任何子集都是不完备的。因此，,的任何子集都是不完备的。的任何子集都是不完备的。,的任何子的任何子集也是不完备的。集也是不完备的。由此可推知，集合由此可推知，集合3,4,5,6,73,4,5,6,7都是独立的完备集。都是独立的完备集。事实上，事实上，6,76,7是仅有的两个只有一个联结词的完备是仅有的两个只有一个联结词的完备集集(不证不证).).,不是完备的不是完备的(不证不证).).第39页，本讲稿共65页2.5 2.5 对偶式对偶式 l新符号新符号“对偶式对偶式”：将将A A中出现的中出现的、T

22、T、F F分别以分别以、F F、T T代换代换,得到公式得到公式A A*,则称则称A A*是是A A的对偶式的对偶式,或说或说A A和和A A*互为对互为对偶式。偶式。若若A=BA=B必有必有A A*=B=B*?对仅含对仅含 、三个联结词的公式考察相似性三个联结词的公式考察相似性第40页，本讲稿共65页新符号新符号“-”“-”：若若A=A(PA=A(P1 1,P,Pn n)令令 A A=A(=A(P P1 1,P Pn n)关于等值的三个定理关于等值的三个定理 (这不是这不是2.12.1节的等值定理节的等值定理)定理定理2.5.1 2.5.1 (A(A*)=()=(A)A)*,(A(A)=()

23、=(A)A)定理定理2.5.2 (A2.5.2 (A*)*=A,(A=A,(A)=A=A定理定理2.5.3 2.5.3 摩根律摩根律 A=AA=A*可用数学归纳法可用数学归纳法,施归纳于施归纳于A A中出中出现的联结词个数现的联结词个数n n来证明。来证明。第41页，本讲稿共65页定理定理 2.5.4 2.5.4 若若A=BA=B必有必有A A*=B=B*证明证明:因为因为A=BA=B等价于等价于A AB B 永真等价于永真等价于 A AB B永真。永真。依定理依定理2.5.3,2.5.3,A=AA=A*,B=BB=B*于是于是 A A*B B*永真永真必有必有 A A*B B*永真永真故故

24、A A*=B=B*关于推理的三个定理关于推理的三个定理第42页，本讲稿共65页定理定理2.5.5 2.5.5 若若A AB B永真永真,必有必有B B*A A*永真永真定理定理2.5.6 A2.5.6 A与与A A同永真同永真,同可满足同可满足 A A与与A A*同永真同永真,同可满足同可满足注意：注意：“A A与与B B同永真同永真,同可满足同可满足”的意思是：的意思是：A A永真可推出永真可推出B B永真永真,反之亦然。反之亦然。第43页，本讲稿共65页2.6 2.6 范式范式(命题的统一形式命题的统一形式)ln n 个命题变项个命题变项所能组成的具有不同真值表的命题公式仅有所能组成的具有

25、不同真值表的命题公式仅有2 22 2n n个个,然而与任何一个命题公式等值而形式不同的命题公式可以有然而与任何一个命题公式等值而形式不同的命题公式可以有无穷多个无穷多个。这这些等值的公式，能否都可以化为某一个些等值的公式，能否都可以化为某一个统一的标准形式统一的标准形式?第44页，本讲稿共65页2.6.1 2.6.1 范式范式l好多新概念好多新概念文字、合取式、析取式、互补对、文字、合取式、析取式、互补对、析取范式、合取范式析取范式、合取范式l范式定理：范式定理：任一命题公式都存在与之等值的析取范式、任一命题公式都存在与之等值的析取范式、合取范式。合取范式。l求范三步曲：求范三步曲：1)消去消

26、去和和2)否定深入到变元否定深入到变元3)使用分配律的等值变换使用分配律的等值变换第45页，本讲稿共65页范式功能：范式功能：判断两公式是否等值判断两公式是否等值(参主范式参主范式)；判断重言式：判断重言式：合取范式中所有析取式都有互合取范式中所有析取式都有互补对；补对；判断矛盾式：判断矛盾式：析取范式中所有合取式都有互补析取范式中所有合取式都有互补对；对；第46页，本讲稿共65页2.6.2 2.6.2 主范式主范式l主析取范式主析取范式1.极小项定义与编码编码：2.主析取范式定义3.主析取范式唯一性定理4.由真值表写主析取范式(从T写)，例35.由析取范式写主析取范式，例4第47页，本讲稿共

27、65页极小项性质极小项性质1.所有极小项的个数2.极小项为真的唯一解3.极小项互不相同4.坐标系功能5.A与 A的主析取范式关系第48页，本讲稿共65页主合取范式主合取范式1.极大项定义：2.主合取范式定义3.主合取范式唯一性定理4.由真值表写主合取范式(从F写)，例55.由合取范式写主合取范式，例6第49页，本讲稿共65页极大项性质极大项性质1.所有极大项的个数2.极大项为假的唯一解3.极大项互不相同4.坐标系功能5.A与 A的主合取范式关系第50页，本讲稿共65页主析取范式与主合取范式的转化主析取范式与主合取范式的转化参见板书！参见板书！注意补集与数字补的不同含义。注意补集与数字补的不同含

28、义。第51页，本讲稿共65页2.7 2.7 推理形式推理形式1.1.通过蕴涵词建立正确通过蕴涵词建立正确(即条件真时，结论必真即条件真时，结论必真)或不正确的推理形式或不正确的推理形式例：例：(P PQ Q)P)P)Q Q 是正确的推理形式是正确的推理形式 (P PQ Q)Q Q)P P是正确的推理形式是正确的推理形式 (P PQ Q)P)P)Q Q是不正确的推理形式是不正确的推理形式第52页，本讲稿共65页2.2.正确推理形式的书写方法正确推理形式的书写方法使用逻辑关系词：重言蕴涵使用逻辑关系词：重言蕴涵A AB B表示命题表示命题A A为真时命题为真时命题B B一定为真一定为真3.3.重言

29、蕴涵的进一步应用重言蕴涵的进一步应用(与与2.8.12.8.1推理公推理公式不同，是一些推理规则即证明推理公式式不同，是一些推理规则即证明推理公式的方法的方法)第53页，本讲稿共65页如果如果A AB,AB,A为重言式，则为重言式，则B B也是重言式。也是重言式。如果如果A AB B，B BA A同时成立，必有同时成立，必有A=BA=B。如果如果A AB B，B BC C，则则A AC C。如果如果A AB B，A AC C，则则A AB BC C。如果如果A AC C，B BC C，则则A A B B C C。第54页，本讲稿共65页2.8 2.8 基本的推理公式基本的推理公式2.8.11.

30、(P Q)P 化简律化简律2.(P Q)P 3.(P Q)Q4.P (P Q)附加律附加律 5.P P Q6.Q P Q7.(P Q)P Q 析取三段论析取三段论8.(P Q)P Q 假言推理、分离规则假言推理、分离规则假言推理、分离规则假言推理、分离规则注意注意2、3、5、6的关系的关系第55页，本讲稿共65页9.(PQ)Q P 拒取式拒取式10.(PQ)(QR)(PR)假言三段论、假言三段论、三段论三段论三段论三段论11.(PQ)(QR)(PR)等价三段论等价三段论12.(P R)(Q R)(P Q)R 构造性二难构造性二难(特殊形式特殊形式)13.(PQ)(RS)(P R)(Q S)构造

31、性二难构造性二难14.(PQ)(RS)(QS)(PR)破坏性二难破坏性二难15.(QR)(P Q)(P R)16.(QR)(PQ)(PR)第56页，本讲稿共65页2.8.2 2.8.2 证明推理公式的证明推理公式的5 5种方法种方法1.1.定理定理2.8.1 2.8.1 A AB B成立的充分必要条件是成立的充分必要条件是A AB B为为重言式。注意：重言式。注意：2.2.1)1)比较定理比较定理2.1.12.1.13.3.2)2)证明证明A AB B为重言式的方法：等值演算、为重言式的方法：等值演算、主析取范式、真值表主析取范式、真值表第57页，本讲稿共65页例例1 1 用等值演算法证明用等

32、值演算法证明(pq)pqpq)pq为重言式为重言式 (pq)pq (p q)p)q (pq)p)q pq q T第58页，本讲稿共65页例例2 2 用用主析取范式主析取范式法证明法证明(p p q q)q q p p不是重言式不是重言式 (pq)qp (p q)qp (p q)q)p q p (pq)(pq)(pq)(p q)m0 m2 m3 缺少缺少m m1 1即即pqpq,所以所以(pq)qppq)qp不是重言式，或者说不是重言式，或者说推理形式推理形式(pq)qppq)qp不正确。不正确。第59页，本讲稿共65页2.2.定理定理2.8.2 2.8.2 A AB B成立的充分必要条件是成立

33、的充分必要条件是 A A B B为重言式即为重言式即A A B B为矛盾式。为矛盾式。3.3.逆否定理逆否定理 A AB B成立的充分必要条件成立的充分必要条件 B B A A4.4.解释法：参考书上解释法：参考书上p32p32页例子页例子5.5.真值表法：即通过真值表检验真值表法：即通过真值表检验A A为真时为真时B B一定为真。一定为真。又见方法又见方法1 1中的第中的第3 3个子方法。个子方法。注：注：证明证明A AB B时不考虑时不考虑A A为假的情况。为假的情况。第60页，本讲稿共65页2.9 2.9 推理演算推理演算(证明推理公式证明推理公式A AB B的新方法的新方法)从前提从前

34、提A A1 1,A,An n出发出发(即即A=AA=A1 1 A A2 2 A An n)运用运用推理规则和基本推理公式，逐步推演出结论推理规则和基本推理公式，逐步推演出结论B B，即证明即证明A AB B 。2.9.1 2.9.1 推理规则推理规则前提引入规则：前提引入规则：推理中推理中,随时引入前提随时引入前提A A1 1,A,An n2 2）结论引用规则：）结论引用规则：推理中推理中,中间结论作为后续推理前提中间结论作为后续推理前提第61页，本讲稿共65页3)3)代入规则代入规则(参考参考p8)p8)：推理中推理中,对重言式的命题变项使用对重言式的命题变项使用4)4)置换规则置换规则(参

35、考参考p18):p18):命题公式任何部分由与之等值的公式置换命题公式任何部分由与之等值的公式置换5)5)分离规则（假言推理）分离规则（假言推理）:已知命题公式已知命题公式A A和和A AB B为前提条件为前提条件,则有命题则有命题公式公式B B第62页，本讲稿共65页6)6)条件证明规则条件证明规则(附加前提附加前提):):利用利用A A1 1A A2 2B B与与A A1 1 A A2 2 B B等价，即结论方等价，即结论方的条件移到了前提方。的条件移到了前提方。例例1 1特点：前提引入规则、分离规则特点：前提引入规则、分离规则例例2 2特点：使用基本推理公式特点：使用基本推理公式例例3

36、3特点：置换规则特点：置换规则例例4 4特点：条件证明规则特点：条件证明规则(附加前提引入附加前提引入)例例5 5特点特点:反证法、条件证明、结论引入反证法、条件证明、结论引入第63页，本讲稿共65页2.10 2.10 归结推理法归结推理法(归结推理规则归结推理规则)(证明推理公式证明推理公式A AB B的新方法的新方法)一、思想一、思想1.1.证明证明A AB B等价于证明等价于证明A AB B是重言式是重言式 等价于证明等价于证明 A A B B是重言式是重言式 等价于证明等价于证明A AB B是矛盾式是矛盾式2.2.用反证法，假设用反证法，假设A AB B在某种解释下为真在某种解释下为真

37、3.3.将将A AB B化为合取范式，每个析取式均作为一个前化为合取范式，每个析取式均作为一个前题题(子句子句).).这些这些子句的集合记作子句的集合记作S.S.第64页，本讲稿共65页4.4.对对S S作归结作归结,消互补对，即使用推理消互补对，即使用推理(P P R R)(P P Q Q)R R Q(Q(注意注意R,QR,Q变形变形T,F)T,F)其中其中(P P R R)和和(P P Q Q)都是都是S S中的前题中的前题(子句子句).).最后最后导出矛盾。导出矛盾。二、具体步骤：见二、具体步骤：见p36p36例例1 1例例2 21)1)合取范式合取范式2)2)子句集子句集3)3)归结过程归结过程第65页，本讲稿共65页