1.5 推理规则与证明方法

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,NUIST,*,推理,是由一个或几个判断得出另一个新的判断的思维,形式(思维过程)。其中已知的判断,前提,新的判断,结论,列出前提H1,H2,Hm与结论C,论证,逻辑的主要功能,是提供推理的规则或论证的原理。从一,组给定的前提出发，根据推理规则得到的结论称为,有效,结论，,论证,才是有效的。,建立,逻辑学的主要目的,在于探索出这一套完整的规则，,按照这些规则，就可以确定任何特定论证是否有效。,1.5 推理规则与证明方法,啦坐河汗骤筷乍孟搀剂启弃挞嘲犬刚邱残玻届拼碍拽耕洋匣甜匝去环陋暑1.5 推理规则与证明方法1.5 推理规则与证明方法,设H1,H2,Hm()和都是命题公式。,若(H1H2 Hm)为永真式，,即 H1H2 Hm,，,称由前提H1,H2,Hm推出结论C的,推理正确(有效),。,称为前提H1,H2,Hm的,有效结论,或,逻辑结果,。,H1H2 Hm,称为,由前提H1,H2,Hm推出结论C的,推理的形式结构。,一、,推理的,基本概念,袒跌撒洽节阁涯震闰堑翱眉闽翟昭萄丛悄退条废出主桓函稿问绕橡菱违愁1.5 推理规则与证明方法1.5 推理规则与证明方法,例1-5-1,1 如果天下雨，小王就不去跑步。,今天天下雨，所以小王没去跑步。,解：设 P：,天下雨,。Q：小王去,跑步,。,前提：P,Q，,P,结论：,Q,推理的形式结构为：(P,Q,)P,Q,2 如果我上街，我一定去新华书店。,我没上街，所以我没去新华书店。,解：设P：我上街。Q：我去新华书店。,前提：PQ，,P 结论：,Q,推理的形式结构为：(PQ),P,Q,推理的符号化实例,蓬抚坐粒判狭由周犀间均义照印桐就疟前耶竹羚统仓刹齿晾嚣仑资凳瓷凰1.5 推理规则与证明方法1.5 推理规则与证明方法,根据定义：由前提H1,H2,Hm推结论C的,推理正确(有效)即,：,(,H1H2 Hm)为永真式，,即 H1H2 Hm,可知，判断推理是否正确的方法就是判断,永真式,或,永真蕴含式,的方法。,基本方法有：,1 真值表法,2 等值演算法,3 主析取范式法,4 指派分析法(,永真蕴含式,),二、基于定义的推理,移范缘夏折匆夫怎稠获柠酌虚平研童先伟堆烦嗓限蓑骄艰掸芽肾离拉晌湃1.5 推理规则与证明方法1.5 推理规则与证明方法,例1-5-2,判断下列推理是否正确：,如果天下雨，小王就不去跑步。,今天天下雨，所以小王没去跑步。,解：设 P：,天下雨,。Q：小王去,跑步,。,前提：P,Q，,P 结论：,Q,推理的形式结构为：(P,Q,)P,Q,判断,(P,Q,)P),Q,(*)是否为永真式,或,(P,Q,)P,Q,是否成立。,步骤：,先将命题符号化,然后写出前提、结论和推理的形式结构,最后进行判断,愈完虫妥扫竿防所凉专具纪向蚊偿瓢拿午翟肛闭凌窗台次伺檬钡晒椎琢米1.5 推理规则与证明方法1.5 推理规则与证明方法,1 真值表法,真值表的最后一列全为1，因而(*)是永真式。,所以推理正确。,真值表技术：给定一个前提集合和一个结论，用构成真值表,的方法，在有限步骤内判定给定前提是否能推,导出该结论的这种方法，称为真值表技术。,染梅蒸登歼啃铝症迷阜烛骄池唬獭册芜扦诵弗爹涟筹桔殿奸由隅职堵仟探1.5 推理规则与证明方法1.5 推理规则与证明方法,(PQ)P)Q,(PQ)P)Q,(PQ)P)Q,(PPQ)(QPQ),TT,T,因而(P Q)P)Q(*)是永真式，推理正确。,2 等值演算法,氢戊西烬蒋储帘狗亨殷探锌巷惨今粒弓悄秤叶每龄简届憎戴诡腔由傍异赏1.5 推理规则与证明方法1.5 推理规则与证明方法,(P,Q)P),Q,(,P,Q)P),Q,(PQ),P,Q,(PQ)(,P,(Q,Q),)(,(P,P),Q),(PQ)(,PQ)(,P,Q)(P,Q)(,P,Q),(,P,Q)(,PQ)(P,Q)(PQ),(0,1,2,3),因而(*)是永真式,，,推理正确。,3 主析取范式法,膜猪迄硝逼察乖聚颠黑颈师荚呆掐揉柴龚铬谋遂惊糠砖悦尘打沽决摹仰饯1.5 推理规则与证明方法1.5 推理规则与证明方法,即要判断(PQ)P Q,证明：假设前件(PQ)P 为真，,则P为真，且(PQ)为真，所以Q 为真。,故(PQ)P Q成立，,推理正确。,4 指派分析法(永真蕴含式),基于定义进行推理,的不足：,1 如果命题公式的变元较多，以上四种方法都不方便。,(n个变元，2,n,种指派),2 与自然生活和传统数学中的推理形式无相同之处。,3 过于机械，对培养推理能力和推理技巧毫无帮助。,泰霞球朵休磕舀蚌墓热斡锨偶棉镍锯他暗长甫闻匙恋理阔邻返瘫寄渭啃隔1.5 推理规则与证明方法1.5 推理规则与证明方法,形式证明：,对由前提H1，H2，Hm推结论C的推理，,构造一个描述推理过程的命题公式序列，其中,每个命题公式或者是已知的前提，或者是由某,些前提应用,公认的,推理规则所得到的结论，序,列中最后一个命题公式是所要求的结论。,这样的命题公式序列称为形式证明。,形式证明的格式：,形式证明是按行进行的，而且每行只能,写一个命题公式。一般为：,标号部分 命题公式 说明部分,三、基于规则的推理,鱼渭现窗碘币棺秸若婚积吾粘囚埃诞拦案丁骡宝铅括洞聂丑尉碰支矩状冬1.5 推理规则与证明方法1.5 推理规则与证明方法,推理过程中使用的,构造公式序列的规则：,规则P,（前提引入规则）：在推导的任何步骤上，都可以引入前提。,规则T,（结论引入规则）：在推导过程中，如果前面有一个或多个命题公式永真蕴含命题公式 S，那么就可以把公式 S 引进推导过程中。,代入规则：在推导的任何步骤上，永真式中的任一命题变元都可以用任一命题公式代入，代入后得到的仍是永真式。,置换规则：在推导的任何步骤上，命题公式中的任何子公式都可以用与之等值的命题公式置换。,常用的推理公式：,在表,1.2-2,中列出的永真蕴含式。,在表,1.2-1,中列出的逻辑等价式。,常用的推理规则,吓湍缓婪胆照阎失啤妆曰拼甚碳垦介戮件嫩宪震盯锗碾股令债葱幸推骗衍1.5 推理规则与证明方法1.5 推理规则与证明方法,1,直接证明法,由已知的前提H1,H2,Hm出发，利用一些公认的推理规则，根据已知的逻辑等价式和永真蕴含式，推导出有效结论C。,证明方法,推理：H1H2 Hm C,2间接证明法,将已知的前提和结论进行适当的改造，,转化为对新的前提和结论进行推理证明。,常用的技巧有：附加前提证明法和反证法。,桶承亨迄噶恭丛胡亏颤惨芽冯伏移愁籽昏恰耪倚蓉驭亢弘败搀拼借继秘察1.5 推理规则与证明方法1.5 推理规则与证明方法,例1-5-3,检验下列推理的有效性。,如果马会飞或羊吃草，则母鸡就会是飞鸟；,如果母鸡是飞鸟，那么煮熟的鸭子还会跑；,煮熟的鸭子不会跑，所以羊不吃草。,解：设P：马会飞。Q：羊吃草。,R：母鸡是飞鸟。S：煮熟的鸭子会跑,则前提为：(PQ)R，RS，,S,结论为：,Q,推理的形式结构为：,(PQ)R),(,RS),(,S),Q,1.直接证明法,喝仓盒灸肯凑苑喇况台克维拽另帅埠领嘉钻扮累怪巍哗奖沧引理戍遣吃丝1.5 推理规则与证明方法1.5 推理规则与证明方法,证明：,(,1),S 规则P,(2)RS 规则P,(3),R (1)(2)拒取式，规则T,(4)(PQ)R 规则P,(5),(PQ)(3)(4)拒取式，规则T,(6),P,Q (5)德摩根律，替换规则，规则T,(7),Q (6)简化式，规则T,所以推理正确,Q：,羊不吃草,有效结论,，但,不是正确的,结论。,P：,马不会飞,有效结论,，而且是,正确的,结论。,有效是指结论的推出是合乎推理规则的，并不在于,结论是否真实。,第一列是步骤列,将各次操作按先后排序;,第二列是断言列或命题公式列,内容可以是前提,中间结论或最终结论;,第三列是注释列或根据列,表明所引用的推理规则及与之有关的行的编号.,第三列是形式推理的特点与优点.,溜但曾吨喳书副君卫卵滋朗垦肖鬼蓑睁跌页非跋琐驾俏勤犁潮靳玲糖船僵1.5 推理规则与证明方法1.5 推理规则与证明方法,例1-5-4 证明 RS是前提CD，CR，DS的,有效结论，即证明：,(CD)(CR)(DS)(RS)。,证明:(1)CD 规则P,(2)CD (1)蕴含等价式，规则T,(3)DS 规则P,(4)CS (2)(3)前提三段论，规则T,(5)CR 规则P,(6)RC (5)逆反律，规则T,(7)RS (4)(6)前提三段论，规则T,(8)RS (7)蕴含等价式，规则T,会琐搽烟痹拭链志舆蛊描奶癸遭祸斯反荤判哇稽戚屏桐郎楞红恳范史迎董1.5 推理规则与证明方法1.5 推理规则与证明方法,2.间接证明法,附加前提法（CP规则）,当待证的有效结论是一个PQ 类型的条件命题时，,可以将有效结论中的前提P 单独提出来加到前提中去，,然后证明剩下的后件Q 是附加了前提之后的新的一组前提,的有效结论。这种附加前提的证明方法称为 CP规则。,即：H1H2 Hm(PQ)的充要条件是,H1H2 Hm PQ。,证明：要证 H1H2 Hm (PQ),即证(H1H2 Hm)(PQ)T,同样，要证 H1H2 HmP Q,即证(H1H2 HmP)Q T,而(H1H2 Hm)(PQ),(H1H2 Hm P)Q （输出律）,浑呀比醋鼎眯邢磋钥萝盔翔谴牟瞄货敦纫薪掳娘洽暑跌弃秒抒寺皑填憎磁1.5 推理规则与证明方法1.5 推理规则与证明方法,例1-5-5,证明：,R,P,是前提PQ，QR的有效结论。,分析：要证明：(PQ)(QR),R,P,采用附加前提证明法，转化为证明：,(PQ)(QR),R,P,证明：,(1),R,规则P(附加前提),(2)QR 规则P,(3),Q (1),(2)拒取式，规则T,(4)PQ 规则P,(5),P (3),(4)拒取式，规则T,(6),R,P,CP规则,由CP 规则，得：,(PQ)(QR),R,P,钨蕉淤众一嫡介宠持梢盒固庸腻擒关痛骇悯阐绑耘黔胺柞土蛔垂倔桔扯胺1.5 推理规则与证明方法1.5 推理规则与证明方法,课内练习 1-5-1,证明推理：,P(QR)，Q(RS),P(QS),分析：由CP规则,P(QR)，Q(RS),P(QS),等价于,P(QR)，Q(RS)，,P,QS,再由CP规则，等价于,P(QR)，Q(RS),，,P，Q,S,庇循蘑槐倪呐丘予购洼吁化楚腾剖娱裔饯剪厅手眼蹭艘子快媚疆惯币歼权1.5 推理规则与证明方法1.5 推理规则与证明方法,证明：,(1),P,规则P(附加前提),(2)P(QR)规则P,(3)QR (1),(2)假言推理，规则T,(4),Q,规则P(附加前提),(5)R (3),(4)假言推理，规则T,(6)Q(RS)规则P,(7)RS (4)(6）假言推理，规则T,(8)S (5),(7)假言推理，规则T,(9)P(QS)CP规则,由CP 规则，有：,P(QR)，Q(RS),P(QS),乡碰酿铝盆挚侧趁急取波煌酱陷殉省昼丫烽爱矗哄愧仓凄腑辟般娄萍岔穆1.5 推理规则与证明方法1.5 推理规则与证明方法,例1-5-6,采用附加前提法证明,例1-5-4,：,(CD)(CR)(DS),(RS)。,分析：由,P,Q,PQ，得 RS,R,S,由CP规则，等价于要证明,CD，CR，DS，,R,S,证明:,(1),R,规则P(附加前提),(2)CR 规则P,(3),C (1),(2)拒取式，规则T,(4)CD 规则P,(5)D (3),(4)析取三段论，规则T,(6)DS 规则P,(7)S (5)，(6)前提三段论，规则T,(8),R,S CP规则,(9)RS (8)蕴含等价式，规则T,CP规则的适用范围：,待证的有效结论是PQ 或 PQ 型的命题。,寂最蛛力锥跑宫镭辱括锦光讼邢印竭慰痞踢煎狸午贺盆敞龙篷盖痘匪著伏1.5 推理规则与证明方法1.5 推理规则与证明方法,(2)反证法(归谬法),将结论C的否定,C 做为假设前提推出矛盾的证明方法称为反证法或归谬法。即：,H1H2 Hm,