资源预览内容
第1页 / 共55页
第2页 / 共55页
第3页 / 共55页
第4页 / 共55页
第5页 / 共55页
第6页 / 共55页
第7页 / 共55页
第8页 / 共55页
第9页 / 共55页
第10页 / 共55页
亲,该文档总共55页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第四章 命题逻辑的自然演绎系统,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),(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日星期一,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),(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推出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 化简 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) 前提 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)(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,间接证明规则,否定消去规则(记为_): 间接证明 如果从和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,否定消去规则(记为_),例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、
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号