命题演算(推理理论).ppt
1,第四讲 命题逻辑的推理理论,命题逻辑的推理理论也称为命题演算主要内容一、推理的形式结构二、推理定律和推理规则三、逻辑证明方法,2,数理逻辑的推理理论主要研究推理的“思维过程”，为推理提供一定的推理规则。它只关心从前提得到结论这种推理的正确有效性。无论前提是否真得正确，它总是假设其是成立的。所以推理的正确性和结论的正确性可能是不一致的。推理理论在应用上常常是将一些定理，定律，公理和条件作为前提，通过推理得到新的定理。,引言,3,一、推理的形式结构,定义1 设A1,A2,Ak,B为命题公式.若对于每组赋值，A1A2 Ak 为假，或当A1A2Ak为真时，B也为真，则称由前提A1,A2,Ak推出结论B的推理是有效的或正确的,并称B是有效结论或称B可由A1,A2,Ak逻辑推出.,定理1 由命题公式A1,A2,Ak 推B的推理正确当且仅当A1A2AkB为重言式,4,推理的形式结构,2.A1A2AkB 若推理正确,记为A1 A2 Ak B3.前提：A1,A2,Ak 结论：B,推理的形式结构1.A1,A2,Ak B 若推理正确,记为A1,A2,An B,5,二、推理定律重言蕴涵式,1.A(AB)附加律 2.(AB)A 化简律3.(AB)A B 假言推理4.(AB)B A 拒取式 5.(AB)B A 析取三段论6.(AB)(BC)(AC)假言三段论7.(AB)(BC)(AC)等价三段论8.(AB)(CD)(AC)(BD)构造性二难(AB)(AB)B 构造性二难(特殊形式)9.(AB)(CD)(BD)(AC)破坏性二难每个等值式可产生两个推理定律如,由AA可产生 AA 和 AA,6,推理规则,(1)前提引入规则(P)在推理过程中，可以随时引入已知的前提。(2)结论引入规则(T)在推理过程中，前面已推出的有效结论都可作为后续推理的前提引用。(3)置换规则(R)在推理过程中，命题公式中的子公式都可以用与之等值的命题公式置换，得到证明的公式序列的另一公式。(4)代入规则(S)在推理过程中，重言式中的任一命题变元都可以用一命题公式代入，得到的仍是重言式。,7,推理规则,(4)假言推理规则(6)化简规则(8)假言三段论规则,(5)附加规则(7)拒取式规则(9)析取三段论规则,8,推理规则,(10)构造性二难推理规则(12)合取引入规则,(11)破坏性二难推理规则,9,三、逻辑证明方法,判断有效结论的过程就是论证过程。基本方法：（1）真值表法（2）直接证明法（3）间接证明法（反证法）具体：等值演算、主析取范式、构造证明法等,10,例：判断下列推理是否正确。今天杨尚树或去网吧或去教室。他没去教室，所以他去网吧了。设 p：杨尚树去网吧。q：杨尚树去教室。则，前提：p q,q 结论：p 推理的形式结构：(p q)q)p,真值表法,11,真值表法,该命题公式为重言式，说明推理正确，所以杨尚树去网吧,(p q)q)p,12,推理实例,例1 判断下面推理是否正确(1)若今天是1号，则明天是5号.今天是1号.所以,明天是5号.(2)若今天是1号，则明天是5号.明天是5号.所以,今天是1号.,解 设 p：今天是1号，q：明天是5号.(1)推理的形式结构:,(pq)pq,用等值演算法(pq)pq(pq)p)q pqq 1 由定理1可知推理正确,13,推理实例,(2)推理的形式结构:,(pq)qp,用主析取范式法(pq)qp(pq)qp(pq)q)p qp(pq)(pq)(pq)(pq)m0m2m3 结果不含m1,故01是成假赋值，所以推理不正确,14,例2 构造下面推理的证明：若明天是星期一或星期三，我明天就有课.若我明天有课，今天必备课.我今天没备课.所以，明天不是星期一、也不是星期三.解(1)设命题并符号化 设 p：明天是星期一，q：明天是星期三，r：我明天有课，s：我今天备课,(2)写出证明的形式结构 前提：(pq)r,rs,s 结论：pq,15,直接证明法,(2)写出证明的形式结构 前提：(pq)r,rs,s 结论：pq(3)证明（证明过程三列式）序号 当前得到的结论 当前得到结论的理由 rs P(前提引入)s P r T I(拒取式)(pq)r P(pq)T E(拒取式)pq TE 德摩根率,16,附加前提证明法,附加前提证明法 适用于结论为蕴涵式(CP规则)欲证 前提：A1,A2,Ak 结论：CB等价地证明 前提：A1,A2,Ak,C 结论：B理由：(A1A2Ak)(CB)(A1A2Ak)(CB)(A1A2AkC)B(A1A2AkC)B,17,附加前提证明法实例,例3 构造下面推理的证明 2是素数或合数.若2是素数，则 是无理数.若 是无理数，则4不是素数.所以，如果4是素数，则2是合数.解 用附加前提证明法构造证明(1)设 p：2是素数，q：2是合数，r：是无理数，s：4是素数(2)推理的形式结构 前提：pq,pr,rs 结论：sq,18,附加前提证明法实例,(3)证明 s CP规则 pr P rs P ps T I(假言三段论)p T I(拒取式)pq P q TI(析取三段论),19,归谬法（反证法）,归谬法(反证法)欲证 前提：A1,A2,Ak 结论：B做法 在前提中加入B，推出矛盾.理由 A1A2AkB(A1A2Ak)B(A1A2AkB)(A1A2AkB)0 A1A2AkB0,20,归谬法实例,例4 前提：(pq)r,rs,s,p 结论：q证明 用归缪法 q P(附加前提)rs P s P r TI（拒取式）(pq)r P,21,(pq)TI(析取三段论)pq TE 德摩根率 p TI(析取三段论)p P pp(矛盾）TI（合取引入）反证法,11 p,
