第2章 命题逻辑.ppt

1,第2章命题逻辑,2.1命题逻辑基本概念2.2命题逻辑等值演算2.3范式2.4命题逻辑推理理论,2,数理逻辑是研究推理的数学学科，它着重于推理过程以及推理是否正确的研究。数理逻辑包含：逻辑演算(命题演算与谓词演算)、公理集合论、证明论、递归函数论、模型论，其中逻辑演算是其他各部分的基础,3,2.1命题逻辑基本概念,2.1.1命题与联结词命题与真值(简单命题,复合命题)联结词(,)2.1.2命题公式及其分类命题公式及其赋值真值表命题公式的分类,4,2.1.1命题与联结词,推理是从前提出发，推出结论的逻辑思维过程。推理1若华盛顿是美国的首都，则多伦多是加拿大的首都。华盛顿是美国的首都，则多伦多是加拿大的首都。推理2若今年是2004年，则明年是2005年。明年是2005年，所以今年是2004年。命题:判断结果唯一的陈述句，不能可真可假。命题的真值:判断的结果,真或假真命题:真值为真的命题假命题:真值为假的命题注意:感叹句、祈使句、疑问句都不是命题陈述句中的悖论以及判断结果不惟一确定的也不是命题,5,例1下列句子中那些是命题？(1)北京是中华人民共和国的首都.(2)2+58.(3)x+53.(4)你会开车吗？(5)2050年元旦北京是晴天.(6)这只兔子跑得真快呀！(7)请关上门！(8)我正在说谎话.,真命题,假命题,真值不确定,疑问句,感叹句,祈使句,悖论,(1),(2),(5)是命题,(3),(4),(6)(8)都不是命题,真值确定,但未知,实例,6,简单命题与复合命题,简单命题(原子命题):简单陈述句构成的命题简单命题的符号化:用p,q,r,pi,qi,ri(i1)表示用“1”表示真，用“0”表示假复合命题:由简单命题通过联结词联结而成的陈述句例如如果明天天气好,我们就出去郊游设p:明天天气好,q:我们出去郊游,如果p,则q又如张三一面喝茶一面看报设p:张三喝茶,q:张三看报,p并且q,7,联结词与复合命题,定义2.1设p为命题,复合命题“非p”(或“p的否定”)称为p的否定式,记作p,符号称作否定联结词,并规定p为真当且仅当p为假例如p:2是合数,p:2不是合数,p为假,p为真定义2.2设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式,记作pq,称作合取联结词,并规定pq为真当且仅当p与q同时为真例如p:2是偶数,q:2是素数,pq:2是偶素数,p为真,q为真,pq为真,8,实例,例2将下列命题符号化.(1)王晓既用功又聪明.(2)王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功.(4)张辉与王丽都是三好生.(5)张辉与王丽是同学.解,记p:王晓用功,q:王晓聪明,(1)pq,(2)pq,(3)pq,(4)记r:张辉是三好生,s:王丽是三好生,rs,(5)简单命题,记t:张辉与王丽是同学,9,联结词与复合命题(续),定义2.3设p,q为命题,复合命题“p或q”称作p与q的析取式,记作pq,称作析取联结词,并规定pq为假当且仅当p与q同时为假.例如张三和李四至少有一人会英语设p:张三会英语,q:李四会英语,符号化为pq相容或与排斥或例如这件事由张三和李四中的一人去做设p:张三做这件事,q:李四做这件事应符号化为(pq)(pq),10,实例,例3将下列命题符号化(1)2或4是素数.(2)2或3是素数.(3)4或6是素数.(4)元元只能拿一个苹果或一个梨.(5)王晓红生于1975年或1976年.解,记p:2是素数,q:3是素数,r:4是素数,s:6是素数,(1)pr,(2)pq,(3)rs,(4)记t:元元拿一个苹果,u:元元拿一个梨,真值:1,真值:1,真值:0,(tu)(tu),(5)记v:王晓红生于1975年,w:王晓红生于1976年,(vw)(vw),又可形式化为vw,11,联结词与复合命题(续),定义2.4设p,q为二命题,复合命题“如果p,则q”称作p与q的蕴涵式,记作pq,并称p是蕴涵式的前件,q为蕴涵式的后件.称作蕴涵联结词,并规定,pq为假当且仅当p为真且q为假.例如如果明天天气好,我们就出去郊游设p:明天天气好,q:我们出去郊游,形式化为pq,12,蕴涵联结词(续),pq的逻辑关系:q为p的必要条件,p为q的充分条件“如果p,则q”的多种表述方式：若p,就q只要p,就qp仅当q只有q才p除非q,才p除非q,否则非p当p为假时，pq为真(不管q为真,还是为假),13,实例,例4设p:天冷,q:小王穿羽绒服，将下列命题符号化(1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候.,注意：pq与qp等值（真值相同）,pq,pq,qp或pq,pq,qp,qp,pq或qp,qp,14,联结词与复合命题(续),定义2.5设p,q为命题,复合命题“p当且仅当q”称作p与q的等价式,记作pq,称作等价联结词.并规定pq为真当且仅当p与q同时为真或同时为假.pq的逻辑关系:p与q互为充分必要条件例如这件事张三能做好,且只有张三能做好设p:张三做这件事,q:这件事做好了形式化为:pq,15,实例,例5求下列复合命题的真值(1)2+24当且仅当3+36.(2)2+24当且仅当3是偶数.(3)2+24当且仅当太阳从东方升起.(4)2+25当且仅当美国位于非洲.(5)f(x)在x0处可导的充要条件是它在x0处连续.,1,0,1,1,0,16,联结词与复合命题(续),联结词优先级:(),同级按从左到右的顺序进行,17,命题联结词测试程序：,#includestdio.h#includeconio.hmain()intp,q;printf(ptqtpqtpqtpqn);for(p=0;p=1;p+)for(q=0;q=1;q+)printf(%dt%dt%dt%dt%dn,p,q,p|q,p,18,例：将下列复合命题符号化,(1)除非你已满16周岁，否则只要你身高不足4英尺就不能乘公园滑行铁道。p：你已满16周岁q：你身高不足4英尺r：你能乘公园滑行铁道(2)只有你主修计算机科学或不是新生，你才可以从校园网访问因特网。p：你主修计算机科学q：你是新生r：你可以从校园网访问因特网(3)不管你或他努力与否，比赛定会取胜。p：你努力q：他努力r：比赛定会取胜(4)选修过“高等数学”或“微积分”的学生可以选修本课。p：选修过“高等数学q：选修过“微积分r：可以选修本课(5)学过“离散数学”或“数据结构”，但不是两者都学过的学生，必须再选学“计算机算法”这门课。p：学过“离散数学q：学过“数据结构”r：再选学“计算机算法”,19,解：,(1)除非你已满16周岁，否则只要你身高不足4英尺就不能乘公园滑行铁道。(qr)p或pqr或rpq(2)只有你主修计算机科学或不是新生，你才可以从校园网访问因特网。rpq或pqr(3)不管你或他努力与否，比赛定会取胜。(pq)(pq)r(pq)(pq)(pq)(pq)r(4)选修过“高等数学”或“微积分”的学生才可以选修本课。rpq或pqr(若去掉才则改为pqr)(5)学过“离散数学”或“数据结构”，但不是两者都学过的学生，必须再选学“计算机算法”这门课。(相当于只要.就)(pq)(pq)r,20,2.2.2命题公式及其分类,命题常项:简单命题命题变项:取值0(真)或1(假)的变元定义2.6合式公式(命题公式,公式)递归定义如下：(1)单个命题常项或变项是合式公式,并称作原子合式公式(2)若A是合式公式,则(A)也是合式公式(3)若A,B是合式公式,则(AB),(AB),(AB),(AB)也是合式公式(4)只有有限次地应用(1)(3)形成的符号串才是合式公式说明:(1)元语言符号与对象语言符号(2)在不影响运算顺序时,括号可以省去例如0,p,pq,(pq)(pr),pqr,(pq)r,21,合式公式的层次,定义2.7(1)单个命题变项或命题常项是0层公式(2)称A是n+1(n0)层公式是指下面情况之一：(a)A=B,B是n层公式(b)A=BC,其中B,C分别为i层和j层公式,且n=max(i,j)(c)A=BC,其中B,C的层次及n同(b)(d)A=BC,其中B,C的层次及n同(b)(e)A=BC,其中B,C的层次及n同(b)例如p0层p1层pq2层(pq)r3层(pq)r)(rs)4层,22,公式的赋值,定义2.8设p1,p2,pn是出现在公式A中全部的命题变项,给p1,p2,pn指定一组真值,称为对A的一个赋值或解释.使公式为真的赋值称作成真赋值,使公式为假的赋值称作成假赋值说明:(1)赋值记作=12n,i=0或1,诸i之间不加标点符号(2)通常赋值与命题变项之间按下标或字母顺序对应,即当A的全部命题变项为p1,p2,pn时,给A赋值12n是指p1=1,p2=2,pn=n;当A的全部命题变项为p,q,r,时,给A赋值123是指p=1,q=2,r=3,23,实例,例6公式A=(p1p2p3)(p1p2)000是成真赋值,001是成假赋值公式B=(pq)r000是成假赋值,001是成真赋值,24,真值表,例7给出公式的真值表(1)(qp)qp,真值表:命题公式在所有可能的赋值下的取值的列表含n个变项的公式有2n个赋值,25,实例(续),(2)(pq)q,26,实例(续),(3)(pq)r,27,命题公式的分类,重言式(永真式):无成假赋值的命题公式矛盾式(永假式):无成真赋值的命题公式可满足式:非矛盾式的命题公式注意:重言式是可满足式，但反之不真.例如上例中(1)(qp)qp为重言式(2)(pq)q为矛盾式(3)(pq)r为非重言式的可满足式,28,2.2命题逻辑等值演算,2.2.1等值式与等值演算等值式与基本等值式真值表法与等值演算法2.2.2联结词完备集真值函数联结词完备集与非联结词和或非联结词,29,2.2.1等值式与等值演算,定义2.11若等价式AB是重言式,则称A与B等值,记作AB,并称AB是等值式说明:(1)是元语言符号,不要混同于和=(2)A与B等值当且仅当A与B在所有可能赋值下的真值都相同,即A与B有相同的真值表(3)n个命题变项的真值表共有个,故每个命题公式都有无穷多个等值的命题公式(4)可能有哑元出现.在B中出现,但不在A中出现的命题变项称作A的哑元.同样,在A中出现,但不在B中出现的命题变项称作B的哑元.哑元的值不影响命题公式的真值.,30,真值表法,例1判断(pq)与pq是否等值解,结论:(pq)(pq),31,真值表法(续),例2判断下述3个公式之间的等值关系:p(qr),(pq)r,(pq)r解,p(qr)与(pq)r等值,但与(pq)r不等值,32,#includestdio.h#includeconio.hintyh(intp,intq)return!p|q;main()intp,q,left,right,bz=0;for(p=0;p=1;p+)for(q=0;q=1;q+)left=yh(p,yh(q,p);right=yh(!p,yh(p,!q);if(left!=right)bz=1;break;if(bz=0)printf(“等价式成立”);elseprintf(“等价式不成立”);getch();,验证,p(qp)=p(pp),33,基本等值式,双重否定律AA幂等律AAA,AAA交换律ABBA,ABBA结合律(AB)CA(BC)(AB)CA(BC)分配律A(BC)(AB)(AC)A(BC)(AB)(AC)德摩根律(AB)AB(AB)AB吸收律A(AB)A,A(AB)A,34,基本等值式(续),零律A11,A00同一律A0A,A1A排中律AA1矛盾律AA0蕴涵等值式ABAB等价等值式AB(AB)(BA)假言易位ABBA等价否定等值式ABAB归谬论(AB)(AB)A,35,等值演算,等值演算:由已知的等值式推演出新的等值式的过程置换规则:若AB,则(B)(A)例3证明p(qr)(pq)r证p(qr)p(qr)（蕴涵等值式）(pq)r（结合律）(pq)r（德摩根律）(pq)r（蕴涵等值式）,36,实例,等值演算不能直接证明两个公式不等值.证明两个公式不等值的基本思想是找到一个赋值使一个成真,另一个成假.例4证明:p(qr)(pq)r方法一真值表法（见例2）方法二观察法.容易看出000使左边成真,使右边成假.方法三先用等值演算化简公式,再观察.,37,实例,例5用等值演算法判断下列公式的类型(1)q(pq)解q(pq)q(pq)（蕴涵等值式）q(pq)（德摩根律）p(qq)（交换律，结合律）p0（矛盾律）0（零律）该式为矛盾式.,38,实例(续),(2)(pq)(qp)解(pq)(qp)(pq)(qp)（蕴涵等值式）(pq)(pq)（交换律）1该式为重言式.,39,实例(续),(3)(pq)(pq)r)解(pq)(pq)r)(p(qq)r（分配律）p1r（排中律）pr（同一律）非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.,总结:A为矛盾式当且仅当A0;A为重言式当且仅当A1说明:演算步骤不惟一,应尽量使演算短些。,40,2.2.2联结词完备集,定义2.12称F:0,1n0,1为n元真值函数,n元真值函数共有个每一个命题公式对应于一个真值函数每一个真值函数对应无穷多个命题公式,41,2元真值函数,42,联结词完备集,定义2.13设S是一个联结词集合,如果任何n(n1)元真值函数都可以由仅含S中的联结词构成的公式表示,则称S是联结词完备集定理2.1下述联结词集合都是完备集:(1)S1=,(2)S2=,(3)S3=,(4)S4=,(5)S5=,(6)S6=,AB(AB)(BA),ABAB,AB(AB)(AB),AB(AB),AB(A)BAB,43,复合联结词,与非式:pq(pq),称作与非联结词或非式:pq(pq),称作或非联结词pq为真当且仅当p,q不同时为真pq为真当且仅当p,q不同时为假定理2.2,是联结词完备集证p(pp)pppq(pq)(pq)(pq)(pq)得证是联结词完备集.对于可类似证明.,44,2.3范式,2.3.1析取范式与合取范式简单析取式与简单合取式析取范式与合取范式2.3.2主析取范式与主合取范式极小项与极大项主析取范式与主合取范式主范式的用途,45,2.3.1析取范式与合取范式,定义2.15文字:命题变项及其否定的统称简单析取式:有限个文字构成的析取式如p,q,pp,pqr,简单合取式:有限个文字构成的合取式如p,q,qq,pqr,定理2.3(1)一个简单析取式是重言式当且仅当它同时含某个命题变项和它的否定。(2)一个简单合取式是矛盾式当且仅当它同时含某个命题变项和它的否定。,46,析取范式与合取范式,定义2.16析取范式:由有限个简单合取式组成的析取式A1A2Ar,其中A1,A2,Ar是简单合取式合取范式:由有限个简单析取式组成的合取式A1A2Ar,其中A1,A2,Ar是简单析取式范式:析取范式与合取范式的统称定理2.4(1)一个析取范式是矛盾式当且仅当它的每一个简单合取式都是矛盾式。(2)一个合取范式是重言式当且仅当它的每一个简单析取式都是重言式。,47,范式存在定理,定理2.5任何命题公式都存在着与之等值的析取范式与合取范式.证求公式A的范式的步骤：(1)消去A中的,ABABAB(AB)(AB)(2)否定联结词的内移或消去AA(AB)AB(AB)AB,48,范式存在定理(续),(3)使用分配律A(BC)(AB)(AC)求合取范式A(BC)(AB)(AC)求析取范式例1求(pq)r的析取范式与合取范式解(pq)r(pq)r(pq)r析取范式(pr)(qr)合取范式注意:公式的析取范式与合取范式不惟一.,49,例：,50,解：,设p:王教授是苏州人，q:王教授是上海人，r:王教授是杭州人(下标为1表示全对，下标为2表示对一半，下标为3表示全错)甲：A1=pqA2=(pq)(pq)A3=pq乙：B1=pqB2=(pq)(pq)B3=pq丙：C1=qrC2=(qr)(qr)C3=qr复合命题：E=(A1B2C3)(A1B3C2)(A2B1C3)(A2B3C1)(A3B1C2)(A3B2C1),A1B2C3=(pq)(pq)(pq)(qr)=0A1B3C2=(pq)(pq)(qr)(qr)=pqrA2B1C3=A2B3C1=A3B2C1=0A3B1C2=pqrE=(pqr)(pqr)=pqr所以王教授是上海人。,51,#includestdio.h#includeconio.hmain()intp,q,r,A1,A2,A3,B1,B2,B3,C1,C2,C3,E;for(p=0;p=1;p+)for(q=0;q=1;q+)for(r=0;r=1;r+)A1=!p,程序：,52,2.3.2主析取范式与主合取范式,定义2.17在含有n个命题变项的简单合取式(简单析取式)中,若每个命题变项均以文字的形式出现且仅出现一次，而且第i(1in)个文字(按下标或字母顺序排列)出现在左起第i位上,称这样的简单合取式(简单析取式)为极小项(极大项)说明:(1)n个命题变项产生2n个极小项和2n个极大项(2)2n个极小项(极大项)均互不等值(3)用mi表示第i个极小项,其中i是该极小项成真赋值的十进制表示.用Mi表示第i个极大项,其中i是该极大项成假赋值的十进制表示,mi(Mi)称为极小项(极大项)的名称.,53,极小项与极大项(续),定理2.6设mi与Mi是由同一组命题变项形成的极小项和极大项,则miMi,Mimi,p,q形成的极小项与极大项,54,主析取范式与主合取范式,主析取范式:由极小项构成的析取范式主合取范式:由极大项构成的合取范式例如，n=3,命题变项为p,q,r时，(pqr)(pqr)m1m3是主析取范式(pqr)(pqr)M1M5是主合取范式定理2.7任何命题公式都存在着与之等值的主析取范式和主合取范式,并且是惟一的.,55,求主析取范式的步骤,设公式A含命题变项p1,p2,pn(1)求A的析取范式A=B1B2Bs,其中Bj是简单合取式j=1,2,s(2)若某个Bj既不含pi,又不含pi,则将Bj展开成BjBj(pipi)(Bjpi)(Bjpi)重复这个过程,直到所有简单合取式都是长度为n的极小项为止(3)消去重复出现的极小项,即用mi代替mimi(4)将极小项按下标从小到大排列,56,求主合取范式的步骤,设公式A含命题变项p1,p2,pn(1)求A的合取范式A=B1B2Bs,其中Bj是简单析取式j=1,2,s(2)若某个Bj既不含pi,又不含pi,则将Bj展开成BjBj(pipi)(Bjpi)(Bjpi)重复这个过程,直到所有简单析取式都是长度为n的极大项为止(3)消去重复出现的极大项,即用Mi代替MiMi(4)将极大项按下标从小到大排列,57,实例,例1(续)求(pq)r的主析取范式与主合取范式解(1)(pq)r(pq)rpq(pq)1同一律(pq)(rr)排中律(pqr)(pqr)分配律m4m5r(pp)(qq)r同一律,排中律(pqr)(pqr)(pqr)(pqr)m0m2m4m6分配律得(pq)rm0m2m4m5m6可记作(0,2,4,5,6),58,实例(续),(2)(pq)r(pr)(qr)prp0r同一律p(qq)r矛盾律(pqr)(pqr)分配律M1M3qr(pp)qr同一律,矛盾律(pqr)(pqr)分配律M3M7得(pq)rM1M3M7可记作(1,3,7),59,快速求法,设公式含有n个命题变项,则长度为k的简单合取式可展开成2n-k个极小项的析取例如公式含p,q,rq(pqr)(pqr)(pqr)(pqr)m2m3m6m7长度为k的简单析取式可展开成2n-k个极大项的合取例如pr(pqr)(pqr)M1M3,60,实例,例2(1)求A(pq)(pqr)r的主析取范式解用快速求法(1)pq(pqr)(pqr)m2m3pqrm1r(pqr)(pqr)(pqr)(pqr)m1m3m5m7得Am1m2m3m5m7(1,2,3,5,7),61,实例(续),(2)求Bp(pqr)的主合取范式解p(pqr)(pqr)(pqr)(pqr)M4M5M6M7pqrM1得BM1M4M5M6M7(1,4,5,6,7),62,主析取范式的用途,(1)求公式的成真赋值和成假赋值设公式A含n个命题变项,A的主析取范式有s个极小项,则A有s个成真赋值,它们是极小项下标的二进制表示,其余2n-s个赋值都是成假赋值例如(pq)rm0m2m4m5m6成真赋值:000,010,100,101,110;成假赋值:001,011,111,63,主析取范式的用途(续),(2)判断公式的类型设A含n个命题变项，则A为重言式当且仅当A的主析取范式含2n个极小项A为矛盾式当且仅当A的主析取范式不含任何极小项,记作0A为可满足式当且仅当A的主析取范式中至少含一个极小项,64,实例,例3用主析取范式判断公式的类型:A(pq)q(2)Bp(pq)(3)C(pq)r解(1)A(pq)q(pq)q0矛盾式(2)Bp(pq)1m0m1m2m3重言式(3)C(pq)r(pq)r(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m0m1m3m5m7非重言式的可满足式,65,主析取范式的用途(续),(3)判断两个公式是否等值例4用主析取范式判断下面2组公式是否等值:(1)p与(pq)(pq)解pp(qq)(pq)(pq)m2m3(pq)(pq)(pq)(pq)(pq)(pq)m2m3故p(pq)(pq),66,实例(续),(2)(pq)r与p(qr)解(pq)r(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m1m3m5m6m7p(qr)(pq)(pr)(pqr)(pqr)(pqr)(pqr)m5m6m7故(pq)rp(qr),67,实例,例5某单位要从A,B,C三人中选派若干人出国考察,需满足下述条件:(1)若A去,则C必须去;(2)若B去,则C不能去;(3)A和B必须去一人且只能去一人.问有几种可能的选派方案?解记p:派A去,q:派B去,r:派C去(1)pr,(2)qr,(3)(pq)(pq)求下式的成真赋值A=(pr)(qr)(pq)(pq),68,实例(续),求A的主析取范式A=(pr)(qr)(pq)(pq)(pr)(qr)(pq)(pq)(pq)(pr)(rq)(rr)(pq)(pq)(pq)(pq)(pr)(pq)(rq)(pq)(pq)(pq)(pr)(pq)(rq)(pq)(pqr)(pqr)成真赋值:101,010结论:方案1派A与C去,方案2派B去,69,主合取范式,由主析取范式求主合取范式设,没有出现的极小项是,其中t=2n-s,于是,70,主合取范式(续),例6求A=(pqr)(pqr)(pqr)的主合取范式解Am1m3m7M0M2M4M5M6矛盾式的主合取范式含全部2n个极大项重言式的主合取范式不含任何极大项,记作1,71,2.4命题逻辑推理理论,2.4.1推理的形式结构推理的前提与结论,正确推理推理定律2.4.2自然推理系统P推理规则直接证明法,附加前提证明法,归谬法(反证法),归结证明法,72,2.4.1推理的形式结构,定义2.20若对于每组赋值,A1A2Ak为假,或者当A1A2Ak为真时,B也为真,则称由前提A1,A2,Ak推B的推理有效或推理正确,并称B是有效的结论定理2.8由前提A1,A2,Ak推出B的推理正确当且仅当A1A2AkB为重言式.,73,推理的形式结构,形式(1)A1A2AkB形式(2)前提:A1,A2,Ak结论:B推理正确记作A1A2AkB判断推理是否正确的方法:真值表法等值演算法主析取范式法构造证明法,74,实例,例1判断下面推理是否正确:(1)若今天是1号,则明天是5号.今天是1号.所以,明天是5号.解设p:今天是1号,q:明天是5号推理的形式结构为(pq)pq证明用等值演算法(pq)pq(pq)p)q(pq)p)qpqq1得证推理正确,75,实例(续),(2)若今天是1号,则明天是5号.明天是5号.所以今天是1号解设p:今天是1号,q:明天是5号.推理的形式结构为(pq)qp证明用主析取范式法(pq)qp(pq)qp(pq)q)pqp(pq)(pq)(pq)(pq)m0m2m301是成假赋值,所以推理不正确.,76,推理定律重言蕴涵式,A(AB)附加律(AB)A化简律(AB)AB假言推理(AB)BA拒取式(AB)BA析取三段论(AB)(BC)(AC)假言三段论(AB)(BC)(AC)等价三段论(AB)(CD)(AC)(BD)构造性二难(AB)(AB)B构造性二难(特殊形式)(AB)(CD)(BD)(AC)破坏性二难,77,自然推理系统P,自然推理系统P由下述3部分组成:1.字母表(1)命题变项符号:p,q,r,pi,qi,ri,(2)联结词:,(3)括号与逗号:(),2.合式公式3.推理规则(1)前提引入规则(2)结论引入规则(3)置换规则,78,自然推理系统P(续),79,自然推理系统P(续),80,直接证明法,例2在自然推理系统P中构造下面推理的证明:前提:pq,qr,ps,s结论:r(pq)证明ps前提引入s前提引入p拒取式pq前提引入q析取三段论qr前提引入r假言推理r(pq)合取推理正确,r(pq)是有效结论,81,实例,例3构造推理的证明:若明天是星期一或星期三,我就有课.若有课,今天必需备课.我今天下午没备课.所以,明天不是星期一和星期三.解设p:明天是星期一,q:明天是星期三，r:我有课，s:我备课前提:(pq)r,rs,s结论:pq,82,实例(续),前提:(pq)r,rs,s结论:pq证明rs前提引入