命题逻辑的形式系统优秀课件.ppt
《命题逻辑的形式系统优秀课件.ppt》由会员分享,可在线阅读,更多相关《命题逻辑的形式系统优秀课件.ppt(39页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、命题逻辑的形式系统命题逻辑的形式系统第1页,本讲稿共39页 第一节第一节 公理演算公理演算P系统的出法点系统的出法点(1 1)n n(一)(一)(一)(一)语法部分,关于对象语言的理论。语法部分,关于对象语言的理论。语法部分,关于对象语言的理论。语法部分,关于对象语言的理论。n n1 1初始符号:初始符号:n n(1 1)p p,q q,r r,s sn n(2 2),n n(3 3)(,)(,)n n2 2形成规则(形成规则(,A A,B B,C C等为元变项):等为元变项):n n()初始符号()初始符号(1 1)中的任意符号)中的任意符号 是一合式公式;是一合式公式;n n()如果符号序
2、列()如果符号序列A A是合式公式,则(是合式公式,则(A A)是合式公式;)是合式公式;n n()如如果果符符号号序序列列A A和和B B是是合合式式公公式式,则则(A AB B)是是合合式式公公式;式;n n()只有符合以上三条的符号序列是合式公式。()只有符合以上三条的符号序列是合式公式。第2页,本讲稿共39页第一节第一节 公理演算公理演算P系统的出法点(系统的出法点(2)n n3 3定义(用定义(用D D表示):表示):n nD D1 1(ABAB)=D=Df f(A AB B);(蕴涵);(蕴涵)n nD D2 2(A AB B)=D=Df f(A A B B);(合取);(合取)n
3、 nD D3 3(A AB B)=D=Df f(A AB B)(B BA A);(等值);(等值)n n4 4公公理理(用用A A表表示示公公理理,用用元元符符号号 表表示示其其跟跟随随的的公公式式是是本本系系统统要要肯定的):肯定的):n nA A1 1 (p pp p)p p);(重言律,或去析公理);(重言律,或去析公理)n nA A2 2 (pp(p pq q);(析取引入律,或加析公理);(析取引入律,或加析公理)n nA A3 3 (p pq q)(q qp p);(析取交换律,或交析公理);(析取交换律,或交析公理)n nA A4 4 (qrqr)(p pq q)(p pr r)
4、。(附附加加律律,或或蕴蕴析公理)析公理)第3页,本讲稿共39页第一节第一节 公理演算公理演算P系统的出法点(系统的出法点(3)n n5 5推理规则(或变形规则,用推理规则(或变形规则,用R R表示):表示):n nR R1 1(代代入入规规则则):在在一一个个合合式式公公式式A A中中,用用一一合合式式公公式式B B代代替替A A中中某某变变项项 的的每每一一次次出出现现(或或将将A A中中的的 全全部部代代以以B B),从从而而得得到到合式公式合式公式A A(/B/B)。即从)。即从 A A可得可得 A A(/B/B)。)。n nR R2 2(分离规则):从(分离规则):从A A和和ABA
5、B(或(或(A AB B)可得)可得B B。n nR R3 3(定定义义置置换换规规则则):定定义义两两边边的的定定义义项项可可以以互互相相替替换换。设设B=DB=Df fC C,A A(B B)为为包包含含公公式式B B的的A A公公式式,A A(B/CB/C)为为在在A A中中用用公公式式C C置换置换B B的公式。即从的公式。即从 A A(B B),可得),可得 A A(B/CB/C)。)。n n符号结合力规则:符号结合力规则:n n (1 1)公公式式最最外外面面的的一一对对括括号号可可省省略略,若若有有不不能能省省略略的的括括号号,其其结结合合力最优先;力最优先;n n (2 2)真
6、值联结词的结合力依下列次序递减:)真值联结词的结合力依下列次序递减:n n ,、,第4页,本讲稿共39页(二)语义部分,关于符号和公式二)语义部分,关于符号和公式解释的理论解释的理论 2 2关于形成规则关于形成规则关于形成规则关于形成规则例:判定例:判定(q qr r)(p pq q)(p pr r)是否为公式。)是否为公式。根据规则(根据规则(1 1),),p p,q q,r r是公式,因为它们都是字母表是公式,因为它们都是字母表中的字母,都属于中的字母,都属于,进而属于,进而属于A A。根据规则(。根据规则(2 2),),q q是公式,因为是公式,因为 q q为为 A A。根据规则(。根据
7、规则(3 3),),q qr r,p pq q,p pr r是公式,因为它们均为是公式,因为它们均为A AB B。再根据规则。再根据规则(2 2),),(q qr r),),(p pq q)是公式,它们可看作是)是公式,它们可看作是 A A。再两次根据规则(。再两次根据规则(3 3),最后判定),最后判定(q qr r)(p pq q)(p pr r)是公式,因为它们可看作是)是公式,因为它们可看作是A AB B。第5页,本讲稿共39页对公理的解释n n每一条公理都是本系统最基本的重言式,其真值,可用真值表方法判定。第6页,本讲稿共39页关于推理规则(1)(1)关于代入规则(R1)该规则要求只
8、有命题变项才能被代入,而其他多于一个符号的公式,例如p都不能被代入。但是,对于代入的公式B是没有限制的。另外,如果在A中的出现不止一次,那么在代入时必须到处都用同一公式B代替,不能用不同的公式代替,也不能有的不代替。第7页,本讲稿共39页举例:举例:n n设公式A为:pqqpn nA中被代入的变项为:qn n代入的公式B为:q合法代入(A(/B):pqqp不合法代入:pqqp(未对在A中的所以出现即每一个q进行代替)第8页,本讲稿共39页关于定义置换规则(关于定义置换规则(R3)n n这里的置换和前面的代入是不同的。置换要求置换公式和被置换公式是等值(或可互相定义)的,而且是在被置换公式出现的
9、某些位置上进行替换。代入则不要求代入公式和被代入公式等值,但必须在被代入公式出现的所有位置上进行替换。第9页,本讲稿共39页举例:举例:n n设公式A为:ppqn nA中被置换的公式B为:Pqn n置换的公式C为:qp(要求:B=dfC即pqqp)n n置 换 后 所 得 公 式(A(B/C):p(qp)第10页,本讲稿共39页关于符号省略规则关于符号省略规则 n n根据形成规则所构造的公式,其符号过多也过于复杂。我们可以作些简化。本规则是在保证不影响原公式固有层次的前提下,对公式的简化。例如根据本规则,P公理可简化为:n nA1pppn nA2ppqn nA3pqqpn nA4(qr)(pq
10、pr)第11页,本讲稿共39页 32 P系统定理的证明n n所所谓谓P P定定理理的的证证明明,乃乃是是一一有有穷穷的的公公式式序序列列A A1 1,A An n,其中每一公式,其中每一公式A Ai i(1in1in)都适合以下条件之一:)都适合以下条件之一:n n(1 1)A Ai i是一公理;是一公理;n n(2 2)A Ai i是一已证定理;是一已证定理;n n(3 3)A Ai i由由本本序序列列在在先先的的一一个个公公式式经经代代入入或或置置换换所所得得到;到;n n(4 4)A Ai i由由本本序序列列在在先先的的两两个个公公式式A Aj j和和A Ak k(其其形形式式分分别别为
11、为B B和和BABAi i,j j i i,k k i i)经分离所得到;)经分离所得到;n n(5 5)最后一个公式)最后一个公式A An n是要证明的定理。是要证明的定理。第12页,本讲稿共39页定理的证明定理的证明 T1(qr)(pq)(pr)证:1.(qr)(pqpr)公理42.(qr)(pqpr)1代入p/p3.(qr)(pq)(pr)2定义1置换第13页,本讲稿共39页T2 pp证:证:证:证:1 1 ppppq q 公理公理公理公理2 22 2 ppppp 1p 1代入代入代入代入q/pq/p3 3 p ppp pp 公理公理公理公理1 14 4、(qrqr)(pqpq)(prp
12、r)定理定理定理定理1 15 5、(p ppppp)(ppppp p)(pppp)4 4代入代入代入代入q/pq/pp p,r/pr/p6 6(ppppp p)(pppp)5 5,3 3分离分离分离分离7 7 pp 6pp 6,2 2分离分离分离分离第14页,本讲稿共39页T3 pp(略)T4 pp n n证:n n1pqqp 公理3n n2pppp 1代入p/p,q/pn n3pp 定理3n n4pp 3,2分离第15页,本讲稿共39页T5 pp(略)(略)T6 pp证:证:1 1 ppp p 定理定理5 52 2 ppp 1p 1代入代入p/p/p p3 3(qrqr)(p pqpqpr
13、r)公理公理4 44 4(ppp p)(p p ppppp p)3 3代入代入q/q/p p,r/r/p p5 5 p p ppppp 4p 4,2 2分离分离6 6 p p p p 定理定理4 47 7 p pp 5p 5,6 6分离分离8 8 p pqqqqp p 公理公理3 39 9(p pp p)(p pp p)8 8代入代入q/q/p p1010 p pp 9p 9,7 7分离分离1111 pp 10pp 10定义定义1 1置换置换第16页,本讲稿共39页T7(pq)(qp)证:证:1 1 ppp p 定理定理5 52 2 qqq 1q 1代入代入p/qp/q3 3(qrqr)(p
14、pqpqpr r)公理公理4 44 4(qqq q)(p pqq p pq q)3 3代入代入r/r/q q,p/p/p p5 5 p pqq p pq 4q 4,2 2分离分离6 6 p pqqqqp p 公理公理3 37 7(p pq q)(q q p p)6 6代入代入p/p/p p,q/q/q q8 8(qrqr)(pqpq)(prpr)定理定理1 19 9 (p pqqq q p p)(p pqq p pq q)(p pqqq q p p)8 8代入代入q/q/p pq q,r/r/q q p p,p/p/p pq q1010(p pqq p pq q)(p pqqq q p p)9
15、 9,7 7分离分离1111 p pqqq q p 10p 10,5 5分离分离1212(pqpq)(qq p p)1111定义定义1 1置换置换第17页,本讲稿共39页T8(pq)pq(略)(略)T9 pq(pq)n n证:n n1pp 定理5n n2 pq(pq)n n 1代入p/pqn n3pq(pq)n n 2定义2置换第18页,本讲稿共39页定理的简化证明定理的简化证明n n使证明简化的一个主要方法是把本系统中的公理和已证定使证明简化的一个主要方法是把本系统中的公理和已证定理当作推理规则使用。这些规则称作导出规则。列举如下:理当作推理规则使用。这些规则称作导出规则。列举如下:1.1.
16、析取交换规则:从析取交换规则:从 A AB B可得可得 B BA A公理公理3 32.2.附加规则:从附加规则:从 BCBC可得可得 A ABABAC C。公理。公理4 43.3.三段论规则:从三段论规则:从 BCBC和和 ABAB可得可得 ACAC。定理。定理1 14.4.假言易位规则:从假言易位规则:从 ABAB可得可得 BB A A。定理。定理7 75.5.等等值值构构成成规规则则:从从 ABAB和和 BABA可可得得 A AB B。定定义义3 36.6.等等值值置置换换规规则则:如如果果A A和和B B等等值值,即即 A AB B,则则从从 AA可可得得 BB。表表示示任任意意合合式式
17、公公式式,其其中中A A(或或B B)是是 的的子子公式。公式。A A,B B可相互置换。这是定义置换规则的扩充。可相互置换。这是定义置换规则的扩充。第19页,本讲稿共39页导出规则导出规则27 7结结合合括括号号省省略略规规则则:(1 1)从从(A AB B)C C可可得得 A AB BC C;(2 2)从)从(A AB B)C C可得可得 A AB BC C。8.8.条件互易规则:从条件互易规则:从 AA(BCBC)可得)可得 BB(ACAC)。)。9 9合取构成规则:从合取构成规则:从 AA(BCBC)可得)可得 A ABCBC。1010条件融合规则:从条件融合规则:从 AA(ABAB)
18、可得)可得 ABAB。以上以上8 8,9 9,1010三条规则都是相应定理的概括。三条规则都是相应定理的概括。1111求求否否定定规规则则:设设A A为为一一公公式式,A A中中没没有有和和出出现现(或或已已定定义义为为,或或),其其否否定定式式(记记为为A A-)用用以以下下方方法法可可得得:将将,互互换换,同同时时 将将和和 互互换换(为为任任一一命命题题变变项项)。例例如如,p p(q qr r)r r,其否定式为,其否定式为 p p(q q r r)r r。1212对对偶偶规规则则:设设A A,B B为为两两个个公公式式,在在其其中中和和不不出出现现。A A 和和B B 是是在在A A
19、和和B B中中把把和和互互换换的的结结果果。我我们们可可有有:(1 1)从从 ABAB可可得得 B B AA;(;(2 2)从)从 A AB B可得可得 A A B B。第20页,本讲稿共39页一些已证或待证定理的简化证明一些已证或待证定理的简化证明 n nT T2 2 ppppn n证:证:n n1 1 ppppq q 公理公理2 2n n2 2 ppppp 1p 1代入代入q/pq/pn n3 3 p ppp pp 公理公理1 1n n4 4 pp 2pp 2,3 3三段论三段论n nT T4 4 p p p pn n证:证:n n1 1 p pp p 公理公理3 3n n2 2 p p
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 命题逻辑 形式 系统 优秀 课件
限制150内