《命题逻辑的形式系统精选PPT.ppt》由会员分享，可在线阅读，更多相关《命题逻辑的形式系统精选PPT.ppt（39页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、命题逻辑的形式系统命题逻辑的形式系统第1页，此课件共39页哦 第一节第一节 公理演算公理演算P系统的出法点系统的出法点（1）n n（一）（一）语法部分，关于对象语言的理论。语法部分，关于对象语言的理论。语法部分，关于对象语言的理论。语法部分，关于对象语言的理论。n n1初始符号：初始符号：n n（1 1）p p，q，r r，sn n（2 2），n n（3 3）（，）（，）n n2 2形成规则（，A A，B，C C等为元变项）：等为元变项）：n n（）初始符号（）初始符号（1 1）中的任意符号是一合式公式；n n（）如果符号序列A是合式公式，则（A A）是合式公式；）是合式公式；n n（）如如果
2、果符符号号序序列列A A和和B是是合合式式公公式式，则则（AB）是合式公式；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 nD D3 3（A AB B）=D=Df f（A AB B）（B BA A）；（等值）；（等值）n n4 4公公理理（用用A A表表示示公公理理，用用元元符符号号 表表
3、示示其其跟跟随随的的公公式式是是本本系系统统要要肯定的）：肯定的）：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）。（附附加加律律，或或蕴蕴析析公理）公理）第3页，此课件共39页哦第一节第一节 公理演算公理演算P系统的出法点（系统的出法点（3）n n5 5推理规则（或变形规则，用推理
4、规则（或变形规则，用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和和ABAB（或（或（A AB B）可得）可得B B。n nR R3 3（定定义义置置换换规规则则）：定定义义两两边边的的定定义义项项可可以以互互相相替替换换。设设B=DB=Df
5、 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）真值联结词的结合力依下列次序递减：）真值联结词的结合力依下列次序递减：n n ，、，第4页，此课件共39页哦(二）语义部分，关于符号和公式二）语义部分，关于符号和公式解释
6、的理论解释的理论 2 2关于形成规则关于形成规则关于形成规则关于形成规则例：判定例：判定（q qr r）（p pq q）（p pr r）是否为公式。）是否为公式。根据规则（1），p，q，r是公式，因为它们都是字母表中的字母，都属于，进而属于，进而属于A。根据规则（2），），q q是公式，因为 q为为A。根据规则（3），q qr r，pq，p pr r是公式，因为它们均为A AB B。再根据规则（2），（q qr r），），（pq）是公式，它们可看作是 A。再两次根据规则（3），最后判定（qr）（pq）（pr）是公式，因为它们可看作是）是公式，因为它们可看作是AB。第5页，此课件共39页哦对公理
7、的解释n n每一条公理都是本系统最基本的重言式，其真值，可用真值表方法判定。第6页，此课件共39页哦关于推理规则（1）（1）关于代入规则（R1）该规则要求只有命题变项才能被代入，而其他多于一个符号的公式，例如p都不能被代入。但是，对于代入的公式B是没有限制的。另外，如果在A中的出现不止一次，那么在代入时必须到处都用同一公式B代替，不能用不同的公式代替，也不能有的不代替。第7页，此课件共39页哦举例：举例：n n设公式A为：pqqpn nA中被代入的变项为：qn n代入的公式B为：q合法代入（A（/B）：pqqp不合法代入：pqqp（未对在A中的所以出现即每一个q进行代替）第8页，此课件共39页
8、哦关于定义置换规则（关于定义置换规则（R3）n n这里的置换和前面的代入是不同的。置换要求置换公式和被置换公式是等值（或可互相定义）的，而且是在被置换公式出现的某些位置上进行替换。代入则不要求代入公式和被代入公式等值，但必须在被代入公式出现的所有位置上进行替换。第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根据形成规则所构造的公式，其符号过多也过于复杂。我们可以作些简化。本规则是在保
9、证不影响原公式固有层次的前提下，对公式的简化。例如根据本规则，P公理可简化为：n nA1pppn nA2ppqn nA3pqqpn nA4（qr）（pqpr）第11页，此课件共39页哦 32 P系统定理的证明n n所所谓谓P P定定理理的的证证明明，乃乃是是一一有有穷穷的的公公式式序序列列A1 1，A An，其中每一公式Ai i（1in1in）都适合以下条件之一：n n（1 1）A Ai i是一公理；n n（2）A Ai i是一已证定理；是一已证定理；n n（3 3）A Ai i由本序列在先的一个公式经代入或置换所得到；n n（4 4）Ai由由本本序序列列在在先先的的两两个个公公式式Aj j和
10、A Ak（其形式分别为B B和BABAi i，j i，k ki）经分离所得到；n n（5 5）最后一个公式）最后一个公式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 ppq 公理公理22 ppp 1代入代入q/p3 3 p ppp pp 公理公理14 4、（qr）（pq）（pr）定理定理定理定理15、（p ppppp）（ppppp p）（pppp）4代入代入
11、q/pp，r/p6（ppp）（pp）5，3分离分离分离分离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 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
12、，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 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
13、 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 9，7 7分离分离1111 p pqqq q p 10p 10，5 5分离分离1212（pqpq）（qq p p）1111定义定义1 1置换
14、置换第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.析取交换规则：从析取交换规则：从 A AB B可得 B BA A公理3 32.附加规则：从 BCBC可得 ABAC。公理4 43.三段论规
15、则：从三段论规则：从BC和 AB可得可得AC。定理1 14.假言易位规则：从ABAB可得 BB A。定理75.5.等值构成规则：从等值构成规则：从ABAB和BABA可得 A AB。定义。定义36.等等值值置置换换规规则则：如如果果A A和和B B等等值值，即即 AB B，则从A可可得得 BB。表示任意合式公式，其中A（或B）是是的子公式。A，B B可相互置换。这是定义置换规则的扩充。可相互置换。这是定义置换规则的扩充。第19页，此课件共39页哦导出规则导出规则27 7结结合合括括号号省省略略规规则则：（1 1）从从（A AB B）C C可可得得 A AB BC C；（2 2）从）从（A AB
16、B）C C可得可得 A AB BC C。8.8.条件互易规则：从条件互易规则：从 AA（BCBC）可得）可得 BB（ACAC）。）。9 9合取构成规则：从合取构成规则：从 AA（BCBC）可得）可得 A ABCBC。1010条件融合规则：从条件融合规则：从 AA（ABAB）可得）可得 ABAB。以上以上8 8，9 9，1010三条规则都是相应定理的概括。三条规则都是相应定理的概括。1111求求否否定定规规则则：设设A A为为一一公公式式，A A中中没没有有和和出出现现（或或已已定定义义为为，或或），其其否否定定式式（记记为为A A-）用用以以下下方方法法可可得得：将将，互互换换，同同时时 将将
17、和和 互互换换（为为任任一一命命题题变变项项）。例例如如，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和和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
18、公理公理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 p 1p 1析取交换析取交换第21页，此课件共39页哦简化证明（简化证明（2）n nT T6 6 ppppn n证：证：n n1 1 ppp p 定理定理5 5n n2 2 ppp 1p 1代入代入p/p/p pn n3 3 p p ppppp 2p 2附加附加n n4 4 p p p p 定理定理4 4n n5 5 p
19、pp 3p 3，4 4分离分离n n6 6 p pp 5p 5析取交换析取交换n n7 7 pp 6pp 6定义定义1 1置换置换n nT T1010 p pp pn n证：证：n n1 1 ppp p 定理定理5 5n n2 2 pp pp 定理定理6 6n n3 3 p pp 1p 1，2 2等值构成等值构成 第22页，此课件共39页哦简化证明（简化证明（3）n nT T7 7 （pqpq）（qq p p）n n证：证：n n1 1 p pqqqqp p 公理公理3 3n n2 2 p pqqqq p 1p 1代入代入p/p/p pn n3 3 p pqqq q p 2p 2等值置换等值置
20、换n n4 4（pqpq）（qq p p）3 3定义置换定义置换1 1n nT T1111 （p pq q）p p q qn n证：证：n n1 1 （p pq q）p p q q 定理定理8 8n n2 2 p p qq（p pq q）定理定理9 9n n3 3 （p pq q）p p q 1q 1，2 2等值构成等值构成n nT T1212 （p pq q）p p q qn n证：证：n n1 1 （p pq q）p p q q 定理定理1111n n2 2 （p pq q）p p q 1q 1对偶对偶第23页，此课件共39页哦简化证明（简化证明（4）n nT1313 pqpqp pn n
21、T1414 pqqpn nT1515 p pqpqpn nT1616 p pqqqqn nT17 p（qr）q q（pr）n nT T1818 p p（q qr r）（p pq q）r rn nT T1919（pq）rp（q qr r）n nT T20 p（q qr r）（pq）r rn nT T2121 q（p pr r）p（qr）n nT22 p（qpqpq q）n nT23（p（qrqr）（qq（prpr）第24页，此课件共39页哦简化证明（简化证明（5）n nT24（p（qr）（p pqrqr）n nT25 （pp（pq）（pq）n nT T2626 p（qr）（p pq q）（pr）
22、n nT T2727 p（qr）（pq）（pr）n nT T2828（pqpq）（prpr）（pqpqr r）n nT29 pp（qqr）n nT T30 pp p（q qr）n nT31 （pq）（p p q q）n nT T3232 （p pq q）（pq）（q qp p）n nT T33 （pq q）（pq）（p q）n nT3434 （p pq q）（pq）（p pq q）n n以上只是P系统的部分定理，请读者自系统的部分定理，请读者自证。证。n n n n 第25页，此课件共39页哦33 P系统定理的演绎系统定理的演绎n n令令是P中的一组公式，它们可以是P中的公理或定理，也可以不是
23、。P中中以以为前提的演绎是一有穷的公式序列A A1，An n，其其中中每每一一公公式式A Ai（1in1in）都适合下列条件之一：n n（1）Ai i是一公理或定理；是一公理或定理；n n（2 2）Ai是 中的一个公式（记为Hyp）；n n（3 3）Ai i由由本本序序列列在在先先的的一一个个或或两两个个公公式式根根据据推推理理规规则则（系系统统内内的的基基本本变变形形规规则则和和导导出出规规则则，但但对对假假设设前前提提公公式式不不得得使用代入规则）而得到。使用代入规则）而得到。n n如果这样一个演绎存在，我们就称该序列最后的一个公式An n以以为前提是可演绎的，或称A An n为P P中
24、的后承，记为 A An。当当假假设设前前提提集集为为空空集集时时，P P中关于空前提的演绎就是P P中的一个证明。A是是P中的定理，记作A，简记成A A。第26页，此课件共39页哦演绎定理演绎定理 n n令A、B为P中任意公式，为P中任何公式集，如果，A B，那么 AB。意即如P中一前提集和另一前提A能推出B，那么，由本身可推出AB。当为空集时，如果由一前提A能推出B，那么，AB可无前提推出，即为P的定理（AB）。第27页，此课件共39页哦反证定理反证定理n n令A为P中任意公式，为P中任何公式集，如果，A ，那么 A。意即如果从P的一前提公式集和一命题公式A的否定推出了矛盾，则从该前提集可推
25、出A。当为空集时，如果由一前提 A能推出，那么，A可无前提推出，即A为P的定理（A）。第28页，此课件共39页哦对对P系统部分定理的演绎证明系统部分定理的演绎证明（1）n nT13 pqpn n证：n n1p Hypn n2ppq 公理2n n3pq 2，1分离n n4pqqp 公理3n n5qp 4，3分离n n6pqp 1，5演绎定理n n（又一附加的导出规则：从p可得qp）第29页，此课件共39页哦演绎证明（演绎证明（2）T T1414 pqqp证：证：1p pq Hypq Hyp2 2（pq q）1定义2置换置换3pqqp 公理公理34 4 （q qp p）（pq）3 3假言易位假言易
26、位 5 5 （pq q）（q q p p）4 4代入代入p/p/q，q/q/p p6 （q q p p）5，2分离分离7 7q p 6定义2 2置换8 8 p pqqqqp 1p 1，7演绎定理演绎定理（合取交换的导出规则：从p pq q可得q qp p）第30页，此课件共39页哦演绎证明（演绎证明（3）T T1515 p pqpqp证：证：1 1p pq Hypq Hyp2 2（p p q q）1 1定义定义2 2置换置换3 3ppppq q 公理公理2 24 4 pp p p q 3q 3代入代入p/p/p p，q/q/q q5 5（p p q q）p 4p 4假言易位（假言易位（R R导
27、导4 4）6 6p 5p 5，2 2分离分离7 7p 6p 6等值置换（等值置换（R R导导6 6）8 8 p pqp 1qp 1，7 7演绎定理演绎定理（导导 出出 规规 则则：从从p pq q可可 得得p p。与与 此此 相相 同同 的的 方方 法法，可可 证证 定定 理理T T1616 p pqqqq，得得导导出出规规则则：从从p pq q可可得得q q。它它们们是是合合取取分分解解规则）规则）第31页，此课件共39页哦演绎证明（演绎证明（4）T T2222 pp（qpqpq q）证：证：1 1p Hypp Hyp2 2pp pp 定理定理2 23 3p pqpqpq 2q 2代入代入p
28、/pp/pq q4 4（p pq q）（p pq q）3 3定义定义1 1置换置换5 5（p p q q）（p pq q）4 4等值置换等值置换6 6 p p（q q（p pq q）5 5析取结合（析取结合（R R导导7 7）7 7 q q（p pq q）6 6，1 1分离分离8 8qpqpq 7q 7定义置换定义置换9 9 pp（qpqpq q）1 1，8 8演绎定理演绎定理（合取组合的导出规则：从（合取组合的导出规则：从p p和和q q可得可得p pq q）第32页，此课件共39页哦演绎证明（演绎证明（5）n nT T2323 （pp（qrqr）（qq（prpr）n n证：证：n n1 1
29、pp（qrqr）HypHypn n2 2q Hypq Hypn n3 3p Hypp Hypn n4 4qr 1qr 1，3 3分离分离n n5 5r 4r 4，2 2分离分离n n6 6pr 3pr 3，5 5演绎定理演绎定理n n7 7qq（prpr）2 2，6 6演绎定理演绎定理n n8 8（pp（qrqr）（qq（prpr）1 1，7 7演绎定理演绎定理n n（由由于于演演绎绎定定理理的的引引入入，所所有有已已证证定定理理都都可可看看作作是是一一导导出出规规则则，而而且且象象上上节节导导出出规规则则中中前前提提与与结结论论前前的的断断定定符符都都可可去去掉掉。如如“换换头头”可可表示为
30、：从表示为：从pp（qrqr）可得）可得qq（prpr）。）。）第33页，此课件共39页哦演绎证明（演绎证明（6）n nT T2424 （pp（qrqr）（p pqrqr）n n该该定定理理的的证证明明分分两两步步，先先证证前前件件蕴蕴涵涵后后件件，再再证证后后件件蕴蕴涵涵前前件件。即：即：n n证：证：（pp（qrqr）（p pqrqr）n n1 1pp（qrqr）HypHypn n2 2p pq Hypq Hypn n3 3p 2p 2合取分解合取分解n n4 4q 2q 2合取分解合取分解n n5 5qr 1qr 1，3 3分离分离n n6 6r 5r 5，4 4分离分离n n7 7p
31、pqr 2qr 2，6 6演绎定理演绎定理n n8 8（pp（qrqr）（p pqrqr）1 1，7 7演绎定理演绎定理n n（合取构成的导出规则：从（合取构成的导出规则：从pp（qrqr）可得）可得p pqrqr）第34页，此课件共39页哦演绎证明（演绎证明（7）再证：（pqr）（p（qr）1pqr Hyp2p Hyp3q Hyp4pq 2，3合取组合5r 1，4分离6qr 3，5演绎定理7p（qr）2，6演绎定理8（pqr）（p（qr）1，7演绎定理 第35页，此课件共39页哦35 命题逻辑的系统特征命题逻辑的系统特征 当我们把命题演算系统作为研究对象时，我们考察的是形式不同的各命题逻辑系
32、统共同的特征，也称元逻辑问题，即一命题逻辑系统的所有可证公式或者说定理是否都是重言式，即可证的是否都是真的？这个问题称作系统的一致性问题。另一个问题是，是否所有命题逻辑的重言式都在一命题逻辑系统中可证，即真的是否都可的重言式都在一命题逻辑系统中可证，即真的是否都可证？这个问题称作系统的完全性问题。另外还有公理独立性问题，即一公理系统的每条公理，彼此应该互相独立性问题，即一公理系统的每条公理，彼此应该互相独立，不能由一个公理而推出另一个公理；各演算系统间的关系问题，如P系统和系统和NPNP系统是等价的，即两系统的系统是等价的，即两系统的定理集是相同的，相对于某些给出的推理规则，能彼此定理集是相同
33、的，相对于某些给出的推理规则，能彼此证明对方的公理和定理的是自己的公理或定理。以下我们仅考察一致性、完全性和独立性问题。们仅考察一致性、完全性和独立性问题。第36页，此课件共39页哦（一）一致性（一）一致性n n一命题逻辑的形式系统是一致的，即该系统的所有定理都是重言式（语义一致）。或者说并非该系统的一切公式都是定理（语法一致）。或者说对于该系统的任一公式A而而言言，A和 A至少有一个不是该系统中的定理（古典的语法一致）。n n如何能确定或证明一个命题演算系统的所有定理都是重言式？通常的方法是为该系统找到一个解释，使得：（1 1）命题演算的公理都是真命题（重言式）；（2 2）应应用用命命题题演
34、演算算的的推推理理规规则则和和定定义义，都都能能保保证证从从重重言言式式只只能能推推出出重重言言式式。如如果果条条件件（1 1）、（2）都满足了，应用该推理规则从公理所推出的所有定理也是重言式，则证明了该系统是（语义）一致的。第37页，此课件共39页哦（二）完全性（二）完全性n n一命题逻辑的形式系统是完全的，即一切重言式都在该系统中可证（广义的、相对的或语义的完全性）。或者说，如果把在该系统不可证的公式作为新公理引进该系统，就会导致矛盾而使该系统不一致（狭义的、绝对的或语法的完全性）。或者说，对于该系统任一合式公式A而言，或者A是可证的，或者A是可证的（古典的完全性）。n n可以证明P系统是语义完全的和语法完全的。第38页，此课件共39页哦（三）独立性（三）独立性 n n所谓独立性就是公理的不可推出性。根据给定的推理规则，如果从一类公式推不出某一特定公式，那么这一公式对于那一类公式就是独立的。不过，若应用某些推理规则推不出来，而用另一些推理规则就可能推出来。所以，独立性总是相对于已给定的推理规则而言的。n n可以证明P系统的公理都是独立的。第39页，此课件共39页哦