命题逻辑的自然演绎系统.ppt

《命题逻辑的自然演绎系统.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章命题逻辑的自然演绎系统自然演绎系统NP命题逻辑的自然演绎系统NP是由形式语言L′和一组推导（变形）规则构成的。其中形式语言L′包括初始符号、形成规则和定义。构建命题逻辑的形式系统，可以采用公理化方法，也可采用自然演绎的方法。为接近人们日常思维的实践，采用自然演绎的方法来构建命题逻辑的一个形式系统NP。7/25/20212初始符号(1)甲类符号：p1,p2,p3,…；(2)乙类符号：，∧，∨，→；(3)丙类符号：(，)。这些符号构成的有穷长的序列叫做符号串，例如:p,p∧q，p∨q,p→q；(p∧q

2、)→r，p∧(q→r)，…；((p→∨q→pq)，(((p→q∧r)∨)，…按照形成规则形成的符号串称为合式公式。7/25/20213形成规则(1)任何单个的命题变元p是合式公式；(2)如果A是合式公式，则(A)是合式公式；(3)如果A和B是合式公式，则(A∧B)、(A∨B)、(A→B)是合式公式；只有（1）----到（3）形成的符号串是合式公式。7/25/20214定义定义是用来表示缩写的，定义两边的符号串可以相互代替。如：(AB)=df(A→B)∧(B→A)。形式语言L′的全体合式公式记为Form(L

3、′)。形式语言L′是我们研究对象，叫对象语言。讨论对象语言的语言叫元语言或语法语言。7/25/20215形成规则的作用（1）以递归的方式定义合式公式。（2）提供一种能行、可判定的方法判定任一符号串是不是合式公式。（3）检验合式公式的性质。如:(((p∨q)∧(p))→q)的形成过程是：p，q，(p∨q)，(p)，((p∨q)∧(p))，q，(((p∨q)∧(p))→q)。这个字符串是反复运用形成规则而形成的，因此它是合式公式。7/25/20216合式公式的子公式合式公式的子公式：在生成合式公式的过程中，

4、每一步所生成的公式都是这一生成的合式公式的子公式。如：A的子公式是A和A；A∧B的子公式是A、B和A∧B；A∨B的子公式是A、B和A∨B；A→B的子公式是A、B和A→B。如：p，q，（p∨q），(p)，((p∨q)∧(p))，(((p∨q)∧(p))→q)都是(((p∨q)∧(p))→q)的子公式。主联结词：辖域最大的联结词。(((p∨q)∧(p))→q)的主联结词是→。省略括号的约定：(1)公式最外层的括号可以省略。(2)联结词的结合力依下列次序递减：，∧，∨，→，。如：(((p∨q)∧(

5、p))→q)可简记为(p∨q)∧p→q。7/25/20217推演规则（1）整推规则（2）置换规则（3）条件证明规则（4）间接证明规则7/25/20218整推规则1.合取引入规则(记为∧+)：从A和B推出A∧B；2.合取消去规则(记为∧_):从A∧B推出A；从A∧B推出B；3.析取引入规则(记为∨+)：从A推出A∨B；从B推出A∨B；4.析取消去规则(记为∨_):从A∨B和A推出B；从A∨B和B推出A；5.肯定前件（记为MP)从A→B和A推出B;6.否定后件规则（记为MT);从A→B和B推出A;7/25

6、/20219条件证明规则5.蕴涵引入规则(记为→+)：条件证明如果从公式集Γ和A推出B，则从Γ推出A→B；7/25/202110例1：┐R→（H→T）R→HT→S┐H∴H→S⑴┐R→（H→T）前提⑵R→H前提⑶T→S前提⑷┐H前提⑸┐R⑵⑷否后⑹H→T⑴⑸肯前⑺H→S⑶⑹假言三段论7/25/202111例2：B→┐AB∧（C→D）A∨C∴D⑴B→┐A⑴B→┐A前提⑵B∧（C→D）前提⑶A∨C前提⑷B⑵化简⑸C→D⑵化简⑹┐A⑴⑷肯前⑺C⑶⑹否析⑻D⑸⑺肯前7/25/202112例3：F∨G→（H→（I↔K））H

7、∧IH∨M→F∴I↔K⑴F∨G→（H→（I↔K））前提⑵H∧I前提⑶H∨M→F前提⑷H⑵化简⑸H∨M⑷附加⑹F⑶⑸肯前⑺F∨G⑹附加⑻H→（I↔K）⑴⑺肯前⑼I↔K⑷⑻肯前7/25/202113练习：1.┐M→（N→L）J→K┐MM∨（N∨J）∴L∨K7/25/202114⑴┐M→（N→L）前提⑵J→K前提⑶┐M前提⑷M∨（N∨J）前提⑸N→L⑴⑶肯前⑹N∨J⑶⑷否析⑺L∨K⑵⑸⑹二难推理7/25/2021152.┐P→（R→┐Q）P→┐Q┐S∨┐R→┐┐Q┐S∴┐R7/25/202116⑴┐P→（R→┐Q）前

8、提⑵P→┐Q前提⑶┐S∨┐R→┐┐Q前提⑷┐S前提⑸┐S∨┐R⑷附加⑹┐┐Q⑶⑸肯前⑺┐P⑵⑹否后⑻R→┐Q⑴⑺肯前⑼┐R⑹⑻否后7/25/2021173.┐P∨┐Q→┐（R→S）┐P（R→S）∨（T→U）┐U∴┐T7/25/202118⑴┐P∨┐Q→┐（R→S）前提⑵┐P前提⑶（R→S）∨（T→U）前提⑷┐U前提⑸┐P∨┐Q⑵附加⑹┐（R→S）⑴⑸肯前⑺T→U⑶⑹否析⑻┐T⑷⑺否后7