第二章命题推理离散数学.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第二章命题推理离散数学,第二章命题推理离散数学第二章命题推理离散数学,逻辑推理,演绎推理（数学家使用）,归纳推理（科学家使用）,溯因推理（侦探使用）,从真的前提出发，得到的结论只能够要求它及前提是,协调,的，但不一定是真的。,从前提出发，通过推导即“演绎”，得出结论的过程。前提和结论之间有,可推导性,关系：前提的真蕴涵结论的真。,生成,假设,来解释观察或结论,。,2,例 判断下面两个推理是否正确,:,(1),如果今天是星期二,今天有数学课。,今天是星期二，,所以今天有数学课。,(2),如果今天是星期二,今天有数学课。,今天不是星期二，,所以今天没有数学课。,第二章 命题演算的推理理论,3,推理是否正确？,记：,P,表示,今天是星期二,，,Q,表示,今天有数学课。,(1),如果今天是星期二,今天有数学课。,今天是星期二，所以今天有数学课。,(P,Q),P),Q,(2),如果今天是星期二,今天有数学课。,今天不是星期二，所以今天没有数学课。,(P,Q),P),Q,4,从真值表看推理是否正确：,P Q (P,Q),P),Q,(P,Q),P),Q,T T,T T,T F,T T,F T,T,F,F F,T T,永真公式,三段论,非永真,5,有效推理,若有,重言式,则称由前提,A,1,，,，,A,n,推出结论,B,的,推理有效,，,并称,B,是,A,1,，,A,2,，,，,A,n,的逻辑结论，记为：,A,1,，,A,2,，,，,A,n,B,或,A,1,，,A,2,，,，,A,n,B,重言式,推理规则,(A,1,A,2,A,n,),B,6,三段论,P,Q,大前提,P,小前提,Q,结 论,三段论推理的有效性由永真公式：,(P,Q),P),Q,所保证。,已知的一般原理,对特殊情况作出判断,所研究的特殊情况,7,前提和结论间具有,可推导性,的,形式关系,大前提：如果,1+1=3,，则雪是黑的。,小前提：,1+1=3,。,结 论：雪是黑的。,该推理过程正确,但不意味着前提及结论正确,8,9,/70,莫绍揆教授（,1917.8-2011.4,）,1939,年毕业于中央大学教学系,1948,年，瑞士苏黎世高级工业大学留学，师从希尔伯特的继承人贝尔奈斯,1950,年,4,月回国，任职南京大学，创建数理逻辑专业,数理逻辑教育和研究的开拓者之一。编著有：,数理逻辑导论,递归数论,递归论,算法论,9,10,/70,公理化,演绎推理,归结推理,离散数学,北京大学,耿素云,前提引入规则,结论引入规则,置换规则,8,条推理定律,离散数学及其应用,北京大学,屈婉玲,前提引入规则,结论引入规则,置换规则,9,条推理定律,24,个等值式,离散数学,解放军通信工程学院,方世昌,9,条推理规则,离散数学,朱怀宏，,南京大学出版社,前提引入规则（,P,规则）,结论引入规则（,T,规则）,置换规则,11,个重言式,22,个等价公式,关于推理理论的学习,10,11,/70,公理化,演绎推理,归结推理,离散数学导论,南京大学,徐洁磐,应用公理系统,自动定理证明,离散数学,基础教程,南京大学,徐洁磐,等式推理,蕴涵推理,离散数学及其在计算机中的应用,南京大学,徐洁磐,推理定理,离散数学导论,解放军理工大学,王元元,3,条公理模式,分离规则,自然推理系统,消解原理,离散数学,南京理工大学,朱保平,15,条公理,代入规则,分离规则,关于推理理论的学习,11,2.1,命题演算的公理系统,给出若干条永真公式,(,称为公理,),，,再给出若干条由永真公式推出永真公式的推理规则，,由它们出发推出一切永真公式。,要求：了解公理系统的构成规则和推理形式。,12,公理系统的组成部分,一、语法部分,基本符号,公理系统所允许出现的全体符号的集合,公理,规则,二、语义部分,13,基本符号,命题变元,P,，,Q,，,R,，,联结词,括号,(,，,),合式公式,推出符,14,公理,公理,1 P,P,公理,2 (P,(Q,R),(Q,(P,R),公理,3 (P,Q),(Q,R),(P,R),公理,4 (P,(P,Q),(P,Q),公理,5 (P,Q),(P,Q),公理,6 (P,Q),(Q,P),公理,7 (P,Q),(Q,P),(P,Q),调头,传递,凝缩,与,有关,15,公理,公理,8 (P,Q),P,公理,9 (P,Q),Q,公理,10 P,(Q,(P,Q),公理,11 P,(P,Q),公理,12 Q,(P,Q),公理,13 (P,R),(Q,R),(,P,Q),R),公理,14 (P,Q),(Q,P),公理,15,P,P,与,有关,与,有关,与,有关,16,规则,(1),代入规则：将公式,中出现的某一符号,B,每处均代以某一公式,C,，所到的公式,D,称为,C,对,的代入。,(2),分离规则：如果,A,B,，且,A,，则,B,。,MP,规则,17,二、语义部分,(1),公理是永真公式。,规则规定如何从永真公式推出永真公式。,分离规则指明,:,如果,A,B,永真且,A,永真，则,B,也为永真公式。,(3),代入规则指明如果,为永真公式，则某一个公式正确代入公式,后所得的公式也为永真公式。,(4),定理为永真公式。,18,公理系统的推理过程,定义,如果能够作出一系列合式公式序列,A,1,，,A,2,A,3,，,A,n,，,它们满足下列性质：,诸,A,i,或为公理,/,定理之一,(,可以使用代入规则,),；,或由前面的,A,g,、,A,h,利用分离规则而得；,(3)A,n,=B,。,称序列,A,1,，,A,2,，,A,n,为,B,的,永真证明过程,。,B,19,公理推理证明的方法,构造合式公式序列,A,1,，,A,2,A,3,，,A,n,=B,，,把待证明的公式结论变成永真蕴涵式的后件，再证明前件永真，最后利用分离规则得到结论。,B,20,定理,1(p20),P,P,证明：,(1),(P,Q,),(,Q,P,),公理,14,(2),(,P,P,),(,P,P,),P,用,P,，,Q,用,P,代入,(3),P,P,公理,1,(4),P,P,P,用,P,代入,(5),P,P,(2)(,4,),分离,P=P,21,定理,1,的推论,P,P,证明,：,(1),P,P,公理,15,(2),P,P,定理,1,(3),(P,Q),(Q,P),(P,Q),公理,7,(4),(P,P),(,P,P),(P,P),代入,(3),(5),(,P,P),(P,P),(2)(4),分离,(6),P,P,(1)(5),分离,22,定理,2,(p18),(P,Q),(R,P),(R,Q),分析：由传递公理,3,知道,(R,P,),(,P,Q,),(,R,Q,),及要求证的公式的联系是两个前件次序换一换，就可以用调头公理,2,：,(,P,(,Q,R,),(,Q,(,P,R,),加头公式,23,定理,3,(p18,拒取式,),(P,Q),(,Q,P),分析：由公理,14,，,(P,Q,),(,Q,P,),，,可以得到,(P,Q,),(,Q,P,),如果,(P,Q),(P,Q,),，,则由传递性知道结论成立。,24,例：,(P,Q),(P,Q,),证明：,(P,Q,),(,R,P,),(,R,Q,),加头定理,2,(2),(Q,Q,),(,P,Q,),(,P,Q,),P,用,Q,代入，,Q,用,Q,代入，,R,用,P,代入,(3),P,P,定理,1,(4),Q,Q,P,用,Q,代入,(5),(P,Q,),(,P,Q,),(6)(2),分离,25,定,理,4,P,(,P,Q),Q),证明：,(1),(,P,(,Q,R),(,Q,(,P,R),公理,2,(2),(,P,Q,)(,P,Q),(,P,(,P,Q,),Q),Q,用,P,代入,，,R,用,Q,代入,，,P,用,P Q,代入,(3),P,P,公理,1,(4),(P,Q)(P,Q),代入,(5),P,(,P,Q),Q),分离,(2)(4),26,例,1,已知公理：,A:,(Q,R),(,P,Q,),(,P,R,),B:(P,P,),P,C:Q,(,P,Q,),及分离规则和代入规则,试证明,P,P,为定理,27,例,1,的证明,(1),(Q,R),(,P,Q,),(,P,R,),公理,A,(2),(P,P,),P,公理,B,(3),Q,(,P,Q,),公理,C,(4),(QP)(PQ,),(PP),R,用,P,代入,(5),(P,P),P)(P(P,P),(PP),(4),式中,Q,用,P,P,(6),(P(P,P),(PP),(2)(5),分离,(7),P(P,P),(3),式中,Q,用,P,代入,(8),P,P,(6)(7),分离,28,例,2,已知公理,A:(P,(,Q,R,),(,P,Q,),(,P,R,),B:P,(Q,P),C:,(,P,Q,),(,QP),及分离规则和代入规则，,试证明,P,P,为定理。,29,(1)(P,(,Q,R,),(,P,Q,),(,P,R,),(2)P,(Q,P),(3)(,P,Q,),(,QP),(4),(P,(,QP),(,P,Q,),(,PP),代入,(1),(5)(,P,Q,),(,PP),(2)(4),分离,(6)(P,(,QP),(,PP),代入,(5),(7)PP,(2)(5),分离,(8)PP,代入,(8),(9)(,PP),(,PP),代入,(3),(10),PP,(8)(9),分离,例,2,的,证明,:,30,2.2,若干重要的导出规则,2.2.1,关于分离规则的讨论,从分离规则出发，由永真公式,(a),，导出分,(a),规则。,永真公式,(a),分,(a),分分,(a),分分分,(a),(,),(,(),(),31,2.2.2,关于公理和定理的导出规则,每一个永真公式,(,公理及定理,),都可以导出一条推理规则。,公理,2,P,(Q,R),Q,(P,R),调头规则,公理,3,P,Q,，,Q,R,P,R,传递规则,公理,7,P,Q,，,Q,P,P,Q,充要规则,公理,8,P,Q,P,化简规则,公理,10,P,，,Q,P,Q,合取规则,32,重要的导出规则,公理,13,P,R,，,Q,R,(,P,Q),R,析取,规则,定理,2,P,Q,(R,P)(,R,Q),加头规则,公理,14,P,Q,Q,P,逆否规则,拒取规则,P,Q,，,Q,P,定理,3,P,Q,QP,P,Q,，,Q,P,33,假言三段论（传递三段论）,P,Q,前提,Q,R,前提,P,R,结论,推理的有效性由公理,3,所保证。,34,化简,P,Q,前提,P,结论,推理的有效性由公理,8,所保证。,35,合取,P,前提,Q,前提,P,Q,结论,推理的有效性由公理,10,所保证。,36,拒取,P,Q,大前提,Q,小前提,P,结 论,推理的有效性由定理,3,所保证。,37,定理,3,(P,Q),(,Q,P),运用导出规则的新证明：,(P,Q,),(,Q,P,),公理,14,(2),(P,Q,),(,Q,P,),Q,用,Q,代入,(3),P,P,定理,1,(4),Q,Q,代入,(3),(5),(P,Q),(P,Q,),(4),加头,(6),(P,Q),(,Q,P),(5)(2),传递,38,替换定理,39,定理,3,(P,Q),(,Q,P),运用替换规则的新证明：,(P,Q,),(,Q,P,),公理,14,(2)(P,Q,),(,Q,P,),Q,用,Q,代入,(3)P,P,定理,1,的推论,(4)Q,Q,代入,(3),(5),(P,Q,),(,Q,P),(4),替换,(2),40,例,(p22),(,P,Q),(,Q,P),利用替换规则的新证明：,(1),(P,Q,),(,Q,P,),公理,14,(2),(P,Q,),(,Q,P,),代入,(1),(3),P,P,定理,1,的推论,(4),Q ,Q,代入,(3),(5),(P,Q,),(,QP)(3),替换,(2),(6),(P,Q,),(,Q,P,)(4),替换,(5),41,2.3,假设推理系统,自然推理系统,一、扩充的推理规则,二、假设推理过程,三、推理定理,四、假设推理证明定理的方法,2.3.1,假设推理系统的组成,42,一、扩充的推理规则,记,R,：,A,1,，,A,2,，,，,A,n,B,称,B,是由,A,1,，,A,2,，,，,A,n,实施规则,R,而得。,设有重言式：,(A,1,A,2,A,n,),B,A,1,前提,A,2,前提,A,n,前提,B,结论,规则,R,：,在假设推理系统中的重言式既可以是公理系统中的公理及定理，也可以是利用真值表法验证的等值公式。,43,肯定前提律（,化简）,P,Q,前提,P,结论,推理的有效性由公理,(8),所保证。,一般地，,A,1,，,A,2,，,，,A,n,A,i,(i=1,，,2,，,，,n),即前提中的任何命题均可作为结论。,44,置换,(,替换,),任何命题公式都可以用及之等值的命题公式置换。,如果,A,=,B,，则,A,B,例,P,P,P,P,P,Q,PQ,PQ,P,Q,在公理系统中，导出规则,(,包括：替换,),在初学时一般不允许使用。,45,析取三段论,P,Q,大前提,P,小前提,Q,结 论,推理的有效性由永真公式：,(P,Q),P),Q,所保证。,46,拒取,P,Q,大前提,Q,小前提,P,结 论,推理的有效性由定理,3,所保证。,47,二、假设推理过程,定义,:,如果能够作出一系列合式公式序列,A,1,，,A,2,A,3,，,A,n,，,它们满足下列性质：,(1),诸,A,i,或为公理,/,定理之一,(,可以使用代入规则,),；,(2),或为公式,1,2,k,之一,(,对假设,i,不能代入,),；,(3),或由前面的,A,g,、,A,h,利用分离规则而得；,(4)A,n,=B,。,称这个公式序列,A,1,，,A,2,，,A,n,为由公式,1,，,2,，,，,k,证明,B,的证明过程。,1,，,2,，,，,k,B,48,三、推理定理,附加前提推理定理,(CP,规则,),如果,，,AB,，则,A,B,(,A,B),及,(,A),B,同真假,49,附加前提,推理定理,如果,A,1,，,A,2,，,，,A,n-1,，,A,n,，,AB,，,则,A,1,，,A,2,，,，,A,n-1,，,A,n,A,B,进而，有下面定理：,A,1,，,A,2,，,A,n-1,A,n,(A,B),A,1,，,A,2,，,，,A,n-2,A,n-1,(A,n,(A,B),依次类推可得定理：,A,1,(A,2,(,(A,n,(A,B),50,四、反证律,如果,，,A,B,且,，,A,B,这里,B,是一个公式。,则有,:,A,。,51,五、假设推理证明定理的方法,把待证公式的前件一一列出，注明为假设或前提。,按推理规则进行推理，但此时,不能对假设以及演绎公式实施代入规则,。,(3),当推导出待证公式的后件时，就完成了该定理的证明。,附加前提推理证明方法,52,反证法,(1),把待证公式的前件一一列出，,把待证公式的后件的否定列出，注明为假设或前提,。,(2),按推理规则进行推理，但此时,不能对假设以及演绎公式实施代入规则,。,(3),当推导出两个矛盾的结论时，就完成了该定理的证明。,53,例,1,：求证,(P,(Q,R),(P,Q),R),证明,(1),P,(Q,R),假设,(2),P,Q,假设,(3),(P,Q),P,公理,8,(4),(P,Q),Q,公理,9,(5),P,(3)(2),分离,(6),Q,(4)(2),分离,(7),Q,R,(1)(5),分离,(8),R,(6)(7),分离,54,例,1,：求证,(P,(Q,R),(P,Q),R),证明,:,(1),P,(Q,R),假设,(2),P,Q,假设,(3),P (2),化简,(4),Q (2),化简,(5),Q,R (1)(3),分离,(6),R (4)(5),分离,(4)R,在,(3),中用,R,代入,P,有错吗,?,不能对,(3),实施代入规则,!,55,例,3,(p25),求证：,(,P,P),P,证明：,(1),P,P,假设,(2),P,假设，结论的否定,(3),P,(1)(2),分离,显然，,(2),及,(3),矛盾。,由反证法，,结论得证。,56,定理,(P,R),(,(Q,R),(P,Q),证明,:,(1),P,R,假设,(2),Q,R,假设,(3),P,假设,(4),R,(1)(3),分离,(5),Q,(2)(4),拒取规则,即证得,:P,R,Q,R,P,Q,由推理定理,原公式得证,57,例,(,(S,Q)(,P,Q),S,),P,证明,:,（直接证明，不采用反证律）,(1),(S,Q)(,P,Q),S,假设,(2),S,Q,(1),化简,(3),P,Q,(1),化简,(4),S,(1),化简,(5),Q,(2)(4),分离,(6),P,(3)(5),拒取,58,例,(,(S,Q)(,P,Q),S,),P,解,:,(1),(S,Q)(,P,Q),S,假设,(2),S,Q,(1),化简,(3),P,Q,(1),化简,(4),S,(1),化简,(5),P,假设,结论的否定,(,置换,),(6),Q,(2)(4),分离,(7),Q,(3)(5),分离,显然，,(6),及,(7),矛盾。,由反证法，公式得证。,59,例,构造下面的假设推理证明,前提：,pq,r,q,rs,结论：,ps,证明：,pq,假设,r,q,假设,(3),rs,假设,p,附加假设,q (1)(4),析取三段论,r (2)(5),析取三段论,s (3)(6),分离,60,半反证法、,穷举法,若,A,1,，,A,2,，,，,A,n,B,A,1,，,A,2,，,，,A,n,B,则,A,1,，,A,2,，,，,A,n,B,若,A,1,，,A,2,，,，,A,n,则,A,1,，,A,2,，,，,A,n,61,例,写出对应下面的假设推理证明,解：记,p,：,今天是星期天,q,：去中山陵,r,：去玄武湖,s,：中山陵游玩的人多,前提：,p(qr),s,q,p,s,结论：,r,如果今天是星期天,则小组就到中山陵或玄武湖去游玩。如果中山陵游玩的人多，小组就不去中山陵游玩。今天是星期天，中山陵游玩的人多，所以小组去玄武湖。,62,例,4,的证明：,p(qr),假设,s,q,假设,p,假设,s,假设,(5),qr,(1)(3),分离,q (2)(4),分离,r (5)(6),析取三段论,(7),q,r,等值,(5),(8)r,6)(7),分离,63,例,构造下面推理的证明：,若明天是星期一或星期三，我就有课,.,若有课，今天必备课,.,我今天下午没备课,.,所以，明天不是星期一和星期三,.,解,设,p,：明天是星期一，,q,：明天是星期三，,r,：我有课，,s,：我备课,形式结构为,前提：,(,p,q,),r,r,s,s,结论：,p,q,64,直接证明法,(,续,),证明,r,s,前提引入,s,前提引入,r,拒取式,(,p,q,),r,前提引入,(,p,q,),拒取式,p,q,置换,前提：,(,p,q,),r,r,s,s,结论：,p,q,65,例,找出下列推理的有效结论。,如果我考试通过了，那么我很快乐。如果我,快乐，那么阳光灿烂。现在阳光不灿烂且天很暖。,因此我考试没通过。,解,设,p,：我考试通过了，,q,：我很快乐，,r,：阳光灿烂，,s,：天很暖。,前提：,p,q,，,q,r,，,r,s,结论：,p,66,前提：,p,q,，,q,r,，,r,s,结论：,p,（,1,）,pq,前提引入,（,2,）,qr,前提引入,（,3,）,pr,（,1,）（,2,）假言三段论,（,4,）,rs,前提引入,（,5,）,r,（,4,）化简,（,6,）,p,（,5,）（,3,）拒取式,所以有效结论是：我考试没通过。,67,例,3,证明是前题，的有效结论，即证明：,(C,D),(C,R),(D,S),(R,S),。,证明,：,CD,前提引入,CD,置换,DS,前提引入,CS ,CR,前 提,R,C ,RS ,R,S,置换,68,例,构造下面推理的证明,:,2,是素数或合数,.,若,2,是素数，则 是无理数,.,若 是无理数，则,4,不是素数,.,所以，如果,4,是素数，则,2,是合数,.,用附加前提证明法构造证明,解,设,p,：,2,是素数，,q,：,2,是合数，,r,：是无理数，,s,：,4,是素数,形式结构,前提：,p,q,p,r,r,s,结论：,s,q,69,证明,s,附加前提引入,p,r,前提引入,r,s,前提引入,p,s,假言三段论,p,拒取式,p,q,前提引入,q,析取三段论,前提：,p,q,p,r,r,s,结论：,s,q,70,例,构造下面推理的证明,前提：,(,p,q,),r,r,s,s,p,结论：,q,证明（用归缪法）,q,结论否定引入,p,p,合取,r,s,前提引入,s,前提引入,r,拒取式,(,p,q,),r,前提引入,(,p,q,),析取三段论,p,q,置换,p,析取三段论,p,前提引入,71,证,：,AB,前提,A,否定结论,B,(BC),前提,B,C,置换,B ,B,B,（,矛盾,）,练习,1,证明,(B,C),(A,B),A,6,、,课内练习,72,证,：,(A,C),否定结论,AC 1,置换,A 2,化简,C 2,化简,AB,前提,B 3,、,5,C,B,前提,B 4,、,7,B,B(,矛盾,)6,、,8,练习,2,证明,A,B,，,C,B,A,C,73,练习,2,证明,A,B,，,C,B,A,C,证,:(1),A,附加前提引入,(2),AB,前提,(3)B 1,、,2,(4)C,B,前提,(5),C 3,、,4,74,已知公理,A:(P,Q)P B:(P,Q),Q C:P(Q,(,P,Q,),及分离规则和代入规则，试用假设推理证明下面公式为本系统的定理,:(PR)(QS)(PQ,),(S R),例,(10,级期末试题,6,分,),75,证：（,1,）,PR,假设,（,2,）,(QS)(PQ,),假设,（,3,）,(,(QS)(PQ,),),(QS),公理（,A,）代入,（,4,）,(,(QS)(PQ,),),(PQ),公理（,B,）代入,（,5,）,QS,（,2,）（,3,）分离,（,6,）,PQ,（,2,）（,4,）分离,（,7,）,(PQ,),P,公理（,A,）,（,8,）,(PQ,),Q,公理（,B,）,（,9,）,P,（,6,）（,7,）分离,（,10,）,Q,（,6,）（,8,）分离,（,11,）,S,（,5,）（,10,）分离,（,12,）,S,(R,(S,R),公理（,C,）代入,（,13,）,R,(S,R),（,11,）（,12,）分离,（,14,）,R,（,1,）（,9,）分离,（,15,）,S,R,（,13,）（,14,）分离,76,本堂课的内容、重点及难点,公理推理过程,假设推理过程,只按分离规则代入规则组织公理推理过程,了解导出规则，灵活组织假设推理过程,公理推理定理,公理,分离规则、代入规则,假设推理系统,77,作业,03,2.2,2.3(1)(4),补,1,：已知公理,A:P,(,Q,P),B:(P,(,Q,R),(,P,Q,),(,P,R,),及分离规则和代入规则,证明公式,P,P,为定理。,（提示：共,6,式）,78,补,1,的证明,:,P,(Q,P),公理,A,(2)(P,(Q,R),(P,Q),(P,R),公理,B,(3)(P,(Q,P),(P,Q),(P,P),R,用,P,代入,(2),(4)(P,Q,),(P,P),(3)(1),分离,(5)(P,(Q,P),(P,P),Q,用,Q,P,代入,(4),(6)P,P,(5)(1),分离,79,课堂练习,设,A,、,B,、,C,为任意的三个命题公式。,(1),已知,AC=BC,，问：,A=B,一定成立吗？,(2),已知,AC=BC,，问：,A=B,一定成立吗？,(3),已知,A=,B,，问：,A=B,一定成立吗？,如果一定成立，试证明之。,如果不一定成立，试给出不成立的例子。,把题目抄写在作业本,(,或纸片,),上提交！,80,课堂练习的解答,A=B,不一定成立。,例如，对于,A=T,B=F,C=T,有,AC=BC,，但,AB.,(2)A=B,不一定成立。,例如，对于,A=T,B=F,C=T,有,AC=BC,，但,AB.,(3)A=B,一定成立。,证明如下：,A=,(,A)=,(,B)=B.,81,谢谢观赏,