命题逻辑的形式系统优秀课件.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

20、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 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 p

21、p 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等值置换等值置换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

22、）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 nT T1313 pqpqp pn nT T1414 p pqqqqp pn nT T1515 p pqpqpn nT T1616 p pqqqqn nT T1717 p p（q qr r）q q（p pr r）n nT T1818 p p（q qr r）（p pq q）r rn nT T1919 （p pq q）

23、rprp（q qr r）n nT T2020 p p（q qr r）（p pq q）r rn nT T2121 q q（p pr r）p p（q qr r）n nT T2222 pp（qpqpq q）n nT T2323 （pp（qrqr）（qq（prpr）第24页，本讲稿共39页简化证明（简化证明（5）n nT T2424 （pp（qrqr）（p pqrqr）n nT T2525 （pp（pqpq）（pqpq）n nT T2626 p p（q qr r）（p pq q）（p pr r）n nT T2727 p p（q qr r）（p pq q）（p pr r）n nT T2828 （pqpq

24、）（prpr）（pqpqr r）n nT T2929 p pp p（q q q qr r）n nT T3030 p pp p（q q q qr r）n nT T3131 （p pq q）（p p q q）n nT T3232 （p pq q）（p pq q）（q qp p）n nT T3333 （p pq q）（p pq q）（p p q q）n nT T3434 （p pq q）（p p q q）（p pq q）n n以上只是以上只是P P系统的部分定理，请读者自系统的部分定理，请读者自证。证。n n n n 第25页，本讲稿共39页33 P系统定理的演绎系统定理的演绎n n令令 是是P P

25、中中的的一一组组公公式式，它它们们可可以以是是P P中中的的公公理理或或定定理理，也也可可以以不不是是。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是是 中的一个公式（记为中的一个公式（记为HypHyp）；）；n n（3 3）A Ai i由由本本序序列列在在先先的的一一个个或或两两个个公公式式根根据据推推理理规规则则（系系统统内内的的基基本本变变形形规规则则

26、和和导导出出规规则则，但但对对假假设设前前提提公式不得使用代入规则）而得到。公式不得使用代入规则）而得到。n n如如果果这这样样一一个个演演绎绎存存在在，我我们们就就称称该该序序列列最最后后的的一一个个公公式式A An n以以 为为前前提提是是可可演演绎绎的的，或或称称A An n为为P P中中 的的后后承承，记记为为 A An n。当当假假设设前前提提集集为为空空集集时时，P P中中关关于于空空前前提提的的演演绎绎就就是是P P中中的的一一个个证证明明。A A是是P P中中的的定定理理，记记作作 A A，简简记记成成 A A。第26页，本讲稿共39页演绎定理演绎定理 n n令A、B为P中任意

27、公式，为P中任何公式集，如果，A B，那么 AB。意即如P中一前提集和另一前提A能推出B，那么，由本身可推出AB。当为空集时，如果由一前提A能推出B，那么，AB可无前提推出，即为P的定理（AB）。第27页，本讲稿共39页反证定理反证定理n n令A为P中任意公式，为P中任何公式集，如果，A ，那么 A。意即如果从P的一前提公式集和一命题公式A的否定推出了矛盾，则从该前提集可推出A。当为空集时，如果由一前提 A能推出，那么，A可无前提推出，即A为P的定理（A）。第28页，本讲稿共39页对对P系统部分定理的演绎证明系统部分定理的演绎证明（1）n nT13 pqpn n证：n n1p Hypn n2p

28、pq 公理2n n3pq 2，1分离n n4pqqp 公理3n n5qp 4，3分离n n6pqp 1，5演绎定理n n（又一附加的导出规则：从p可得qp）第29页，本讲稿共39页演绎证明（演绎证明（2）T T1414 p pqqqqp p证：证：1 1p pq Hypq Hyp2 2（p p q q）1 1定义定义2 2置换置换3 3p pqqqqp p 公理公理3 34 4 （q qp p）（p pq q）3 3假言易位假言易位 5 5 （p p q q）（q q p p）4 4代入代入p/p/q q，q/q/p p6 6 （q q p p）5 5，2 2分离分离7 7q q p 6 p

29、6定义定义2 2置换置换8 8 p pqqqqp 1p 1，7 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导导4 4）6 6p 5p 5，2 2分离分离7 7p 6p 6等值置换（等值置换（R R导导6

30、 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/pp/pq q4 4（p pq q）（p pq q）3 3定义定义1 1置换置换5 5（p

31、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 1pp（qrqr）HypHypn n2 2q Hypq Hypn n3 3p Hypp Hypn

32、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（由由于于演演绎绎定定理理的的引引入入，所所有有已已证证定定理理都都可可看看作作是是一一导导出出规规则则，而而且且象象上上节节导导出出规规则则中中前前提提与与结结论论前前的的断断定定符符都都可可去去掉掉。如如“换换头头”可表示为：从可表示为：从pp（qrqr）可得）可得qq（prpr）。）。）第33页，本讲稿共39页演绎证明

33、（演绎证明（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 pqr 2qr 2，6 6演绎定理演绎定理n n8 8（pp（qrqr）（p pqrqr）1 1，

34、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 命题逻辑的系统特征命题逻辑的系统特征 当我们把命题演算系统作为研究对象时，我们考察的当我们把命题演算系统作为研究对象时，我们考察的是形式不同的各命题逻辑系统共同的特征，也称元逻辑是形式不同的各命题逻辑系统共同的

35、特征，也称元逻辑问题，即一命题逻辑系统的所有可证公式或者说定理是问题，即一命题逻辑系统的所有可证公式或者说定理是否都是重言式，即可证的是否都是真的？这个问题称作否都是重言式，即可证的是否都是真的？这个问题称作系统的一致性问题。另一个问题是，是否所有命题逻辑系统的一致性问题。另一个问题是，是否所有命题逻辑的重言式都在一命题逻辑系统中可证，即真的是否都可的重言式都在一命题逻辑系统中可证，即真的是否都可证？这个问题称作系统的完全性问题。另外还有公理独证？这个问题称作系统的完全性问题。另外还有公理独立性问题，即一公理系统的每条公理，彼此应该互相独立性问题，即一公理系统的每条公理，彼此应该互相独立，不能

36、由一个公理而推出另一个公理；各演算系统间立，不能由一个公理而推出另一个公理；各演算系统间的关系问题，如的关系问题，如P P系统和系统和NPNP系统是等价的，即两系统的系统是等价的，即两系统的定理集是相同的，相对于某些给出的推理规则，能彼此定理集是相同的，相对于某些给出的推理规则，能彼此证明对方的公理和定理的是自己的公理或定理。以下我证明对方的公理和定理的是自己的公理或定理。以下我们仅考察一致性、完全性和独立性问题。们仅考察一致性、完全性和独立性问题。第36页，本讲稿共39页（一）一致性（一）一致性n n一一命命题题逻逻辑辑的的形形式式系系统统是是一一致致的的，即即该该系系统统的的所所有有定定理

37、理都都是是重重言言式式（语语义义一一致致）。或或者者说说并并非非该该系系统统的的一一切切公公式式都都是是定定理理（语语法法一一致致）。或或者者说说对对于于该该系系统统的的任任一一公公式式A A而而言言，A A和和 A A至至少少有有一一个个不不是是该该系系统统中中的的定定理理（古古典典的的语语法法一致）。一致）。n n如如何何能能确确定定或或证证明明一一个个命命题题演演算算系系统统的的所所有有定定理理都都是是重重言言式式？通通常常的的方方法法是是为为该该系系统统找找到到一一个个解解释释，使使得得：（1 1）命命题题演演算算的的公公理理都都是是真真命命题题（重重言言式式）；（2 2）应应用用命命

38、题题演演算算的的推推理理规规则则和和定定义义，都都能能保保证证从从重重言言式式只只能能推推出出重重言言式式。如如果果条条件件（1 1）、（2 2）都都满满足足了了，应应用用该该推推理理规规则则从从公公理理所所推推出出的的所所有有定定理理也也是是重重言式，则证明了该系统是（语义）一致的。言式，则证明了该系统是（语义）一致的。第37页，本讲稿共39页（二）完全性（二）完全性n n一命题逻辑的形式系统是完全的，即一切重言式都在该系统中可证（广义的、相对的或语义的完全性）。或者说，如果把在该系统不可证的公式作为新公理引进该系统，就会导致矛盾而使该系统不一致（狭义的、绝对的或语法的完全性）。或者说，对于该系统任一合式公式A而言，或者A是可证的，或者A是可证的（古典的完全性）。n n可以证明P系统是语义完全的和语法完全的。第38页，本讲稿共39页（三）独立性（三）独立性 n n所谓独立性就是公理的不可推出性。根据给定的推理规则，如果从一类公式推不出某一特定公式，那么这一公式对于那一类公式就是独立的。不过，若应用某些推理规则推不出来，而用另一些推理规则就可能推出来。所以，独立性总是相对于已给定的推理规则而言的。n n可以证明P系统的公理都是独立的。第39页，本讲稿共39页