命题逻辑公理化优秀课件.ppt

《命题逻辑公理化优秀课件.ppt》由会员分享，可在线阅读，更多相关《命题逻辑公理化优秀课件.ppt（15页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、命题逻辑公理化第1页，本讲稿共15页形式化与公理化此前我们讨论命题逻辑,是从语义角度,非形式化地、不严谨地进行解释性的讨论.而数学传统追求的是严格的形式化、公理化系统.形式化:符号化,只有语法定义,并无语义解释.公理化:从初始符号串(公理)出发,根据符号变换规则,推导出其他符号串(定理).具体的公理化系统:语法+语义形式的公理化系统:语法.欧氏几何就是一个经典的公理化系统.Lu Chaojun,SJTU 2第2页，本讲稿共15页形式系统的组成形式系统组成:初始符号:可用符号的集合.形成规则(wff定义):规定如何构成合法的符号串(wff).初始公式(公理):进行推导的出发点.变形规则(推理规则

2、):规定如何从几个wff经过符号变换得出另一wff.建立了形式系统,即可进行推理,从老wff产生新的wff(定理).不是所有wff都是定理.Lu Chaojun,SJTU 3第3页，本讲稿共15页例:一个形式系统形式系统:初始符号:,形成规则:,的任意有限序列都是wff.初始公式:令x是任一串,系统有唯一公理(模式)A1:xx变形规则:令x,y,z表示任意串.R1:若xyz是定理,则 xyz也是定理.在此系统里可以证明是定理.证明:(1)A1x/(2).(1)R1此系统有意义吗?试试这个解释:解释为+,解释为=.Lu Chaojun,SJTU 4第4页，本讲稿共15页命题逻辑的重言式公理系统命

3、题逻辑的重言式可组成一个公理系统.后面给出这个形式化公理系统.该系统的语义可以是:初始符号表示有真假的命题及真值联结词;初始命题是重言式;从公理出发,利用推理规则,可以推导出定理.定理都是重言式该系统推出的都是重言式,而且能推出所有重言式.Lu Chaojun,SJTU 5第5页，本讲稿共15页命题逻辑公理系统初始符号命题符号:A,B,C,联结词:,辅助符号:(,)可证符号:|(后接公式,表示该公式在系统中是可证明的)Lu Chaojun,SJTU 6第6页，本讲稿共15页命题逻辑公理系统(续)形成规则(1)命题符号是公式;(2)若是公式,则是公式;(3)若和是公式,则 是公式;(4)公式仅限

4、于此.Lu Chaojun,SJTU 7第7页，本讲稿共15页命题逻辑公理系统(续)定义D1.定义为()D2.定义为 D3.定义为()()这是为了简化公式表达.也可将作为初始符号,并增加相应形成规则.Lu Chaojun,SJTU 8第8页，本讲稿共15页命题逻辑公理系统(续)公理A1.|(P P)PA2.|P (P Q)A3.|(P Q)(Q P)A4.|(Q R)(P Q)(P R)Lu Chaojun,SJTU 9第9页，本讲稿共15页命题逻辑公理系统(续)变形规则(推理规则)R1.代入规则:若|,则|p/.(将公式中的某符号p处处代以公式,称为代入,结果记作 p/.)R2.分离规则:若

5、|,|,则|.R3.置换规则:定义的左右方可互相替换.设对公式施以置换后得到公式.若|,则|.Lu Chaojun,SJTU 10第10页，本讲稿共15页定理的证明设有公式序列1,2,n.如果每个i(1in)(1)或者是公理之一;(2)或者是由前面的一个或两个h和k(h,k i)实施推理规则而得;则称此公式序列是定理n 的一个证明.Lu Chaojun,SJTU 11第11页，本讲稿共15页例:定理证明定理1:|(QR)(PQ)(PR)(1)|(QR)(PQ)(PR)A4(2)|(QR)(PQ)(PR)(1)代入P/P(3)|(QR)(PQ)(PR)(2)置换D2定理2:|PP(1)P(PQ)

6、A2(2)P(PP)(1)代入Q/P(3)(PP)PA1(4)(QR)(PQ)(PR)定理1(5)(PP)P)(P(PP)(PP)(4)代入Q/PP,R/P(6)(P(PP)(PP)(3)(5)分离(7)PP(2)(6)分离Lu Chaojun,SJTU 12第12页，本讲稿共15页公理系统的性质协调性(相容性,一致性,不矛盾性)推出的定理都是真的;或和不都是定理.完备性(完全性)所有定理均能在系统中推出.独立性公理不能被其他公理推出.Lu Chaojun,SJTU 13第13页，本讲稿共15页命题逻辑公理系统的性质系统是协调的:推出的定理都是重言式.系统是完备的:所有重言式都能推出.Lu Chaojun,SJTU 14第14页，本讲稿共15页Lu Chaojun,SJTU 15End第15页，本讲稿共15页