《命题逻辑的形式系统》由会员分享，可在线阅读，更多相关《命题逻辑的形式系统（39页珍藏版）》请在金锄头文库上搜索。
1、第五章 命题逻辑的形式系统,第一节 公理演算P系统的出发点 第二节 P系统定理的证明 第三节 P系统定理的演绎 第四节 自然演算NP系统 第五节 命题逻辑的系统特征,第一节 公理演算P系统的出法点（1）,（一） 语法部分，关于对象语言的理论。 1初始符号： （1）p，q，r，s （2）， （3）（，） 2形成规则（，A，B，C等为元变项）： （）初始符号（1）中的任意符号是一合式公式； （）如果符号序列A是合式公式，则（A）是合式公式； （）如果符号序列A和B是合式公式，则（AB）是合式公式； （）只有符合以上三条的符号序列是合式公式。,第一节 公理演算P系统的出法点（2）,3定义（用D表示）
2、： D1（AB）=Df（AB）；（蕴涵） D2（AB）=Df（AB）；（合取） D3（AB）=Df（AB）（BA）；（等值）4公理（用A表示公理，用元符号表示其跟随的公式是本系统要肯定的）： A1 （pp）p）；（重言律，或去析公理） A2 （p（pq）；（析取引入律，或加析公理） A3 （pq）（qp）；（析取交换律，或交析公理） A4 （qr）（pq）（pr）。（附加律，或蕴析公理）,第一节 公理演算P系统的出法点（3）,5推理规则（或变形规则，用R表示）： R1（代入规则）：在一个合式公式A中，用一合式公式B代替A中某变项的每一次出现（或将A中的全部代以B），从而得到合式公式A（/B）。
3、即从A可得A（/B）。 R2（分离规则）：从A和AB（或（AB）可得B。 R3（定义置换规则）：定义两边的定义项可以互相替换。设B=DfC，A（B）为包含公式B的A公式，A（B/C）为在A中用公式C置换B的公式。即从 A（B），可得 A（B/C）。 符号结合力规则：（1）公式最外面的一对括号可省略，若有不能省略的括号，其结合力最优先；（2）真值联结词的结合力依下列次序递减：，、，,(二）语义部分，关于符号和公式解释的理论,2关于形成规则 例：判定（qr）（pq）（pr）是否为公式。根据规则（1），p，q，r是公式，因为它们都是字母表中的字母，都属于，进而属于A。根据规则（2），q是公式，因为q
4、为A。根据规则（3），qr，pq，pr是公式，因为它们均为AB。再根据规则（2），（qr），（pq）是公式，它们可看作是A。再两次根据规则（3），最后判定（qr）（pq）（pr）是公式，因为它们可看作是AB。,对公理的解释,每一条公理都是本系统最基本的重言式，其真值，可用真值表方法判定。,关于推理规则（1）,（1）关于代入规则（R1）该规则要求只有命题变项才能被代入，而 其他多于一个符号的公式，例如p都不能被 代入。但是，对于代入的公式B是没有限制 的。另外，如果在A中的出现不止一次，那 么在代入时必须到处都用同一公式B代替，不 能用不同的公式代替，也不能有的不代替。,举例：,设公式A为：pq
5、qp A中被代入的变项为：q 代入的公式B为：q 合法代入（A（/B）：pqqp 不合法代入：pqqp（未对在A中的所以出现即每一个q进行代替）,关于定义置换规则（R3）,这里的置换和前面的代入是不同的。置换要求置换公式和被置换公式是等值（或可互相定义）的，而且是在被置换公式出现的某些位置上进行替换。代入则不要求代入公式和被代入公式等值，但必须在被代入公式出现的所有位置上进行替换。,举例：,设公式A为：ppq A中被置换的公式B为：Pq 置换的公式C为：qp（要求：B=dfC即pqqp） 置换后所得公式（A（B/C）：p（qp）,关于符号省略规则,根据形成规则所构造的公式，其符号过多也过于复杂
6、。我们可以作些简化。本规则是在保证不影响原公式固有层次的前提下，对公式的简化。例如根据本规则，P公理可简化为： A1ppp A2ppq A3pqqp A4（qr）（pqpr）,32 P系统定理的证明,所谓P定理的证明，乃是一有穷的公式序列A1，An，其中每一公式Ai（1in）都适合以下条件之一： （1）Ai是一公理； （2）Ai是一已证定理； （3）Ai由本序列在先的一个公式经代入或置换所得到； （4）Ai由本序列在先的两个公式Aj和Ak（其形式分别为B和BAi，ji，ki）经分离所得到； （5）最后一个公式An是要证明的定理。,定理的证明,T1（qr）（pq）（pr） 证： 1.（qr）（p
7、qpr） 公理4 2.（qr）（pqpr） 1代入p/p 3.（qr）（pq）（pr）2定义1置换,T2 pp,证： 1ppq 公理2 2ppp 1代入q/p 3ppp 公理1 4、（qr）（pq）（pr） 定理1 5、（ppp）（ppp）（pp） 4代入q/pp，r/p 6（ppp）（pp） 5，3分离 7pp 6，2分离,T3 pp（略）T4 pp,证： 1pqqp 公理3 2pppp 1代入p/p，q/p 3pp 定理3 4pp 3，2分离,T5 pp （略）T6 pp,证： 1pp 定理5 2pp 1代入p/p 3（qr）（pqpr） 公理4 4（pp）（pppp）3代入q/p，r/p
8、 5pppp 4，2分离 6pp 定理4 7pp 5，6分离 8pqqp 公理3 9（pp）（pp） 8代入q/p 10pp 9，7分离 11pp 10定义1置换,T7 （pq）（qp）,证：1pp 定理5 2qq 1代入p/q 3（qr）（pqpr） 公理4 4（qq）（pqpq） 3代入r/q，p/p 5pqpq 4，2分离 6pqqp 公理3 7（pq）（qp） 6代入p/p，q/q 8（qr）（pq）（pr） 定理1 9 （pqqp）（pqpq） （pqqp） 8代入q/pq，r/qp， p/pq 10（pqpq）（pqqp） 9，7分离 11pqqp 10，5分离 12（pq）（qp
9、） 11定义1置换,T8 （pq）pq（略） T9 pq（pq）,证： 1pp 定理5 2 pq（pq）1代入p/pq 3pq（pq） 2定义2置换,定理的简化证明,使证明简化的一个主要方法是把本系统中的公理和已证定理当作推理规则使用。这些规则称作导出规则。列举如下： 1.析取交换规则：从AB可得BA公理3 2.附加规则：从BC可得ABAC。公理4 3.三段论规则：从BC和AB可得AC。定理1 4.假言易位规则：从AB可得BA。定理7 5.等值构成规则：从AB和BA可得AB。定义3 6.等值置换规则：如果A和B等值，即AB，则从A可得B。表示任意合式公式，其中A（或B）是的子公式。A，B可相互
10、置换。这是定义置换规则的扩充。,导出规则2,7结合括号省略规则：（1）从（AB）C可得ABC；（2）从（AB）C可得ABC。 8. 条件互易规则：从A（BC）可得B（AC）。 9合取构成规则：从A（BC）可得ABC。 10条件融合规则：从A（AB）可得AB。 以上8，9，10三条规则都是相应定理的概括。11求否定规则：设A为一公式，A中没有和出现（或已定义为，或），其否定式（记为A-）用以下方法可得：将，互换，同时将和互换（为任一命题变项）。例如，p（qr）r，其否定式为p（qr）r。 12对偶规则：设A，B为两个公式，在其中和不出现。A和B是在A和B中把和互换的结果。我们可有：（1）从 AB可得 BA；（2）从 AB可得 AB。,一些已证或待证定理的简化证明,T2 pp 证： 1ppq 公理2 2ppp 1代入q/p 3ppp 公理1 4pp 2，3三段论 T4 pp 证： 1pp 公理3 2pp 1析取交换,
