《命题逻辑自然演绎系统》由会员分享，可在线阅读，更多相关《命题逻辑自然演绎系统（55页珍藏版）》请在金锄头文库上搜索。
1、第四章 命题逻辑的自然演绎系统,2018年12月17日星期一,2,自然演绎系统NP,命题逻辑的自然演绎系统NP是由形式语言L 和一组推导（变形）规则构成的。其中形式语言L 包括初始符号、形成规则和定义。,构建命题逻辑的形式系统，可以采用公理化方法，也可采用自然演绎的方法。为接近人们日常思维的实践，采用自然演绎的方法来构建命题逻辑的一个形式系统NP。,2018年12月17日星期一,3,初始符号,(1)甲类符号：p1, p2, p3, ； (2)乙类符号：，； (3)丙类符号：(，)。 这些符号构成的有穷长的序列叫做符号串，例如: p, pq，pq, pq； (pq)r，p(qr)，； (pqpq
2、)，(pqr)， 按照形成规则形成的符号串称为合式公式。,2018年12月17日星期一,4,形成规则,(1)任何单个的命题变元p是合式公式； (2)如果A是合式公式，则(A)是合式公式； (3)如果A和B是合式公式，则(AB)、(AB)、(AB)是合式公式； 只有（1）-到（3）形成的符号串是合式公式。,2018年12月17日星期一,5,定义,定义是用来表示缩写的，定义两边的符号串可以相互代替。 如：(AB)=df(AB)(BA)。 形式语言L 的全体合式公式记为Form(L )。 形式语言L 是我们研究对象，叫对象语言。 讨论对象语言的语言叫元语言或语法语言。,2018年12月17日星期一,
3、6,形成规则的作用,（1）以递归的方式定义合式公式。 （2）提供一种能行、可判定的方法判定任一符号串是不是合式公式。 （3）检验合式公式的性质。 如:(pq)(p)q)的形成过程是：p，q，(pq)，(p)，(pq)(p)，q ，(pq)(p)q)。这个字符串是反复运用形成规则而形成的，因此它是合式公式。,2018年12月17日星期一,7,合式公式的子公式,合式公式的子公式：在生成合式公式的过程中，每一步所生成的公式都是这一生成的合式公式的子公式。如： A的子公式是A和A； AB 的子公式是A、B和AB； AB 的子公式是A、B和AB； AB 的子公式是A、B和AB。 如：p，q，（pq），(
4、p)，(pq)(p)，(pq)(p)q)都是(pq)(p)q)的子公式。 主联结词：辖域最大的联结词。 (pq)(p)q)的主联结词是。 省略括号的约定： (1)公式最外层的括号可以省略。 (2)联结词的结合力依下列次序递减：，。 如：(pq)(p)q)可简记为(pq)pq。,2018年12月17日星期一,8,推演规则,（1）整推规则 （2）置换规则 （3）条件证明规则 （4）间接证明规则,2018年12月17日星期一,9,整推规则,1.合取引入规则(记为+)： 从A和B推出AB； 2.合取消去规则(记为_): 从AB推出A；从AB推出B； 3.析取引入规则(记为+)： 从A推出AB；从B推出
5、AB； 4.析取消去规则(记为_): 从AB和A推出B；从AB和B推出A； 5.肯定前件（记为MP) 从AB和A推出B; 6.否定后件规则（记为MT); 从AB和B推出A;,2018年12月17日星期一,10,条件证明规则,5.蕴涵引入规则(记为+)： 条件证明 如果从公式集和A推出B，则从推出AB；,2018年12月17日星期一,11,例1： R（HT） RH TS H HS R（HT） 前提 RH 前提 TS 前提 H 前提 R 否后 HT 肯前 HS 假言三段论,2018年12月17日星期一,12,例2：BA B（CD） AC D BA BA 前提 B（CD） 前提 AC 前提 B 化简
6、 CD 化简 A 肯前 C 否析 D 肯前,2018年12月17日星期一,13,例3：FG（H（IK） HI HMF IK FG（H（IK） 前提 HI 前提 HMF 前提 H 化简 HM 附加 F 肯前 FG 附加 H（IK） 肯前 IK 肯前,2018年12月17日星期一,14,练习：,1. M（NL） JK M M（NJ） LK,2018年12月17日星期一,15, M（NL） 前提 JK 前提 M 前提 M（NJ） 前提 NL 肯前 NJ 否析 LK 二难推理,2018年12月17日星期一,16,2. P（RQ） PQ SRQ S R,2018年12月17日星期一,17, P（RQ）
7、前提 PQ 前提 SRQ 前提 S 前提 SR 附加 Q 肯前 P 否后 RQ 肯前 R 否后,2018年12月17日星期一,18,3. PQ（RS） P （RS）（TU） U T,2018年12月17日星期一,19, PQ（RS） 前提 P 前提 （RS）（TU） 前提 U 前提 PQ 附加 （RS） 肯前 TU 否析 T 否后,2018年12月17日星期一,20,条件证明规则,步 骤： 1.引入假设 2.撤销假设 （适用于蕴含式）,2018年12月17日星期一,21,蕴涵引入规则(记为+),又称条件证明规则或演绎定理，是把从推出AB的推理转化为从和临时的假设A推出B的推理。 即：（AB）（
8、AB） 本规则实质就是条件输入（输出）规则的运用 最适于证明结论为蕴涵式的推论。,前提集,结论,假设前提,2018年12月17日星期一,22,蕴涵引入规则(记为+),例1：FG HF GH FG 前提 HF 前提 G 条件假设 G 双重否定 F 否析律 F 双重否定 H 否后律 H 双重否定 GH 条件证明,2018年12月17日星期一,23,蕴涵引入规则(记为+),例2：AB CB(DE) A(DE) AB 前提 CB(DE) 前提 A 条件假设 B 肯前律 CB 附加 DE 肯前律 A(DE) 条件证明,2018年12月17日星期一,24,间接证明规则,否定消去规则(记为_)： 间接证明
9、如果从和A推出BB，则从推出A。 步骤： 1.否定结论 2.提出矛盾 3.肯定结论,2018年12月17日星期一,25,否定消去规则(记为_),又称间接证明或反证法，是把由推出A的推理转化为由和临时的假设A推出BB的推理。 最适于证明结论不是蕴涵式的推论。,2018年12月17日星期一,26,否定消去规则(记为_),例1：AB AB A (1) AB 前提 (2) AB 前提 (3) A 间接假设 (4) A (3)，_ (5) B (1)，(4)，_ (6) B (2)，(4)，_ (7) BB (5)，(6)，+ (8) A (3)(7)，间接证明,2018年12月17日星期一,27,否定
10、消去规则(记为_),例2：A(BC)(CD)，CD / A (1) A(BC) (CD) A1 (2)CD A2 (3) C (2)_ (4) D (2)_ (5) A H1 (6) A (5)_ (7) (BC)(CD) (1)，(6)_ (8) CD (7)_ (9) D (3)，(8)_ (10) DD (4)，(9)+ (11)A (5)(10)- (消去H1),2018年12月17日星期一,28,蕴涵引入（条件证明）规则与 否定消去（间接证明）规则,在做题过程中二者可以交替使用，既可以先用蕴涵引入（条件证明）规则再用否定消去（间接证明）规则，也可以先用否定消去（间接证明）规则再用蕴涵引入（条件证明）规则。,2018年12月17日星期一,29,练习,1、
