《逻辑学》（第三版）课件 第3章 命题逻辑的自然演绎系统

命题逻辑的自然演绎系统马克思主义理论研究和建设工程重点教材《逻辑学》（第三版）第三章命题逻辑的自然演绎系统目

录第一节证明与子证明第二节推理规则第三节系统NP中的推导第四节无前提推导与演绎定理

自然演绎是一种证明系统，最早是在二十世纪三十年代由德国逻辑学家根岑（GerhardGentzen1909—1945）和波兰逻辑学家雅思可夫斯基（StanisławJaśkowski1906—1965）提出并发展起来的。在这样的系统中，逻辑推理过程是按推理规则进行的，一个自然演绎系统是一些推理规则构成的系统。第一节证明与子证明

逻辑学所讲的证明是从前提到结论的推理过程。对任意有限多个命题的集合

={A1,…,An}和命题A，我们用记号

A表示从前提A1,…,An推出结论A。一个证明是从前提出发合乎逻辑地推出结论的过程，“合乎逻辑地”意思是符合逻辑规则。自然演绎就是这样一个推理规则系统，告诉我们如何运用推理规则证明一个推理是有效的。在自然演绎系统中，一个证明是从前提出发连续有限多次应用规则达到结论的过程。为了介绍命题逻辑的自然演绎系统，我们采用下面这种证明格式

最后一步是要证明的结论，前面每一步要么是前提，要么是应用规则得到的。第一节证明与子证明

一个证明可以非常简单，例如，从“如果a是偶数，那么a能被2整除”和“a是偶数”推出“a能被2整除”。一个证明也可以比较复杂。例如，一个数学命题“在实数范围内，存在两个无理数a和b，使得ab（a的b次方）是有理数”的经典证明如下：考虑c=2的平方根这个数。已知它是无理数。假设d=cc是有理数，那么结论成立。假设d不是有理数，那么d是无理数。所以dc=cc

c=c2=2是有理数。所以结论成立。由于d要么是有理数，要么不是有理数，所以结论成立。这个证明是由几部分组成的：从“d是有理数”推出结论；从“d不是有理数”推出结论；最后根据分情况证明得到结论。第一节证明与子证明

证明本身也可以由许多子证明组成。在数学证明中，人们常常需要证明一些引理，再证明所需要的定理。这些引理的证明实际上是定理证明的一部分，称为子证明。因此，一个复杂的证明是由一些子证明按结构构造起来的。在命题逻辑的自然演绎系统中，含有子证明的复杂证明具有如下一般形式：

其中包含对C的证明和D的证明，注意对D的证明是C的一级子证明，而C的证明是B的一个级证明。第二节推理规则

命题逻辑的自然演绎系统记为NP，它是有许多规则组成的。推理规则分为两类：一类规则与证明的结构有关，称为结构规则；一类规则与联结词的使用有关，称为联结词规则。在具体应用规则进行证明的过程中，我们将在证明的左侧以数字标示证明步骤，而每一步的根据则写在右侧。第二节推理规则一、结构规则（一）假设规则（hyp）：在证明的任何地方可以引入假设A，但引入假设就需要引入新的子证明，该子证明依赖于假设A。

hyp表示hypothesis的缩写，写在右侧表示公式A是临时引入的假设。每当用hyp规则，我们就引入一个子证明，在格式上往右侧退一格。

这个规则在数学证明中很常见，例如反证法，为了证明命题B，先假设

B，然后证得一对矛盾命题C和

C，这样假设不成立，所以B成立。这种证明方法临时引入了假设B，在书写证明过程中要往右退一格。第二节推理规则（二）重复规则（reit）：在证明过程中，一个子证明中某一步可以重复上一级子证明中的某一步。

二、联结词规则

在命题逻辑中有五个联结词，对每个联结词

都有两条规则：引入规则和消去规则。我们用

I表示联结词

的引入规则，用

E表示联结词

的消去规则。联结词规则与联结词的意义有关。下面分别说明五个联结词的规则。第二节推理规则（一）合取引入规则(

I）

在同一级证明中，如果证明A并且证明B，就可以证明A

B。这是显然的，如果A和B都是真的，那么A

B也一定是真的。例如：在证明中得到“a是偶数”和“a大于2”，自然可以推出“a是大于2的偶数”。第二节推理规则（二）合取消去规则（

E）

在同一级证明中，如果证明A

B，就可以证明A；也可以证明B。这是显然的，如果A

B是真的，那么A和B都是真的。例如，在证明中得到“a是大于2的偶数”，立即可得“a是偶数”和“a大于2”。第二节推理规则（三）蕴涵引入规则（

I）

在一级证明中，为了证明A

B，只要先假设A，然后证明B。这是显然的，因为假设A真可以证明B真，所以A

B是真的。例如：为了证明“如果a大于2，那么2a2大于8”，首先我们要临时引入假设“a大于2”，然后证明“2a2大于8”。这样就证明了所需要证明的命题。第二节推理规则

蕴涵引入规则也叫作条件证明，即为了证明充分条件命题A

B，只要假设A成立而后证明B成立。注意:临时引入假设A，往右退一格，引入从A到B的一级子证明。从A到B的证明结束后，结论A

B回到上一级证明的位置，这一步也称为“消除”临时引入的假设，因为对A

B的证明不依赖于假设A是真的。每当临时引入假设，最终都要消除。否则，整个证明依赖于临时引入的假设，这是不正确的。蕴涵引入规则还有一种特殊情况，如下是蕴涵引入规则的直接应用：在证明过程中，假设已经得到B，那么直接可以得到A

B。为了证明A

B，原本需要假设A，再证明B，但是B已经有了，所以无需再假设A去证明B。这里临时引入假设的消除是空消除。第二节推理规则（四）蕴涵消去规则（

E）

在一级证明中，如果证明了A

B，然后又证明了A，就可以证明B。这是显然的，因为假设A

B真和A真就可以得到B真。例如，假设在证明中得到“如果a大于2，那么2a2大于8”；然后又得到“a大于2”。很自然就推出“2a2大于8”。第二节推理规则（五）否定引入规则（

I

）

在一级证明中，为了证明

A，先假设A，然后证明一对矛盾命题B和

B。这样就可以证明

A。这种证明方法在数学中俗称“归谬法”,从假设A引出一对矛盾命题，由此推出A不成立，即

A成立。

注意：临时引入假设A，往右退一格，引入从A到B和

B的一级子证明.子证明结束后，结论

A回到上一级证明，这样就消除了临时引入的假设。第二节推理规则（六）否定消去规则（

E）

在一级证明中，为了证明A，先假设A的否定命题

A，然后证明一对矛盾命题B和

B。这样就可以证明A。这种证明方法在数学中俗称“反证法”，从假设

A引出一对矛盾命题，就证明了

A不成立，所以A成立。

注意:临时引入假设

A，往右退一格，引入从

A到B和

B的一级子证明。子证明结束后，结论A回到上一级证明，这样就消除了临时引入的假设。第二节推理规则（七）析取引入规则（

I）

在一级证明中，为了证明A

B，只需要证明A或者证明B。这是显然的，因为如果A是真的，那么A

B是真的；如果B是真的，那么A

B也是真的。第二节推理规则（八）析取消去规则（

E）

在一级证明中，如果已经得到A

B，然后假设A可以得到C，再假设B也可以得到C，这样就可以证明C。这种证明方法在数学中俗称“分情况证明”，意思是A

B告诉我们有两种情况A和B，在两种情况下分别都可以证明C，所以C成立。

注意：在运用析取消去规则时，临时引入假设A，证明往右退一格，然后证明C；同时临时引入假设B，然后证明C。从A到C和从B到C的证明是同一级的两个子证明，这两个部分完成以后，结论C回到上一级证明，这样就消除了临时引入的假设。第二节推理规则（九）等值引入规则（

I）

在一级证明中，为了证明A

B，只要先假设A，然后证明B；再假设B，然后证明A。例如，“一个三角形是等边三角形当且仅当它的三个角相等”，首先假设“一个三角形是等边三角形”，证明“它的三个角相等”；同样，再假设“一个三角形的三个角相等”，证明“它是等边三角形”。这就就得到所要证明的等值命题。

注意：临时引入假设A，证明往右退一格，然后证明B；同时临时引入假设B，然后证明A。从A到B和从B到A的证明是同一级的两个子证明，这两个部分完成以后，结论A

B回到上一级证明，这样就消除了临时引入的假设。第二节推理规则（十）等值消去规则（

E）

在一级证明中，如果证明了A

B，然后又证明了A，就可以证明B；同理，如果证明了A

B，然后又证明了B，就可以证明A。第二节推理规则

命题逻辑的自然演绎系统NP是由前面的结构规则和联结词规则组成的。在系统NP中，我们可以从前提集出发推导或演绎出结论A，记为

NPA。有时为方便起见，可省略下标NP。这样一个推导（演绎）是满足如下条件的证明：（1）该证明中每个公式要么是前提，要么是临时引入的假设，要么是通过对同一级子证明中前面的公式应用联结词规则得到的。（2）在最外层证明中，A是最后一步，前提属于

。（3）通过假设规则而临时引入的每个假设，都通过（

I）、（

I）、（

E）、（

E）、（

I）等联结词规则而被消除。为区分临时引入的假设和前提，在证明中，如果某一步是前提，则在右侧我们标记pre。前提不同于临时引入假设的规则hyp。当我们用hyp规则时，必须引入一级子证明，而前提的使用不引入子证明。第三节系统NP中的推导

一、合取规则的运用1.运用要求

在使用“合取引入规则（∧I）”与“合取消除规则（∧E）”时，我们要确保由规则所推导出来的结论与其前提处于同一个子证明之中。第三节系统NP中的推导第三节系统NP中的推导

这里步骤[1]是前提，右侧标记pre表示。步骤[2]是从[1]运用重复规则得到的。步骤[3]是从[1]和[2]用合取引入规则得到的。每一步右侧书写得到该步骤所依据的规则。第三节系统NP中的推导

第三节系统NP中的推导

案例分析：证明策略一（从结论想起）注意：前面三个例子表明，一个自然演绎推演和我们玩积木类似，是一个先把前提拆开再重新组合成结论的过程。分析：为避免少走弯路，一个最直接的证明策略是从结论想起，寻找需要完成的子证明。总结：采取逆向思维，从结论想起。第三节系统NP中的推导二、蕴涵规则的运用第三节系统NP中的推导第三节系统NP中的推导第三节系统NP中的推导

第三节系统NP中的推导

第三节系统NP中的推导

第三节系统NP中的推导三、否定规则的运用第三节系统NP中的推导第三节系统NP中的推导第三节系统NP中的推导第三节系统NP中的推导

第三节系统NP中的推导

例7和例8合起来就是双重否定律的证明第三节系统NP中的推导

第三节系统NP中的推导

第三节系统NP中的推导四、析取规则的运用第三节系统NP中的推导2.5结论为析取式，使用析取消除规则的情形。在实际运用中，我们经常会对结论为析取式的推导使用析取消去规则，而非析取引入规则。一般而言的依据是，前题中不能直接证得结论的某个析取支（如析取支不出现在前提中，或都是在蕴涵式的前件中出现等）。再者，前提中有析取式作为前提（或易证的推论）。第三节系统NP中的推导第三节系统NP中的推导

第三节系统NP中的推导

第三节系统NP中的推导五、等值规则的运用第三节系统NP中的推导第三节系统NP中的推导第三节系统NP中的推导

第三节系统NP中的推导

第三节系统NP中的推导

第三节系统NP中的推导六、综合运用综合运用各种联结词规则，可以证明任何有效的命题逻辑推理形式。对任何公式A和B，我们用A┤├B表示：在系统NP中，A├B并且B├A。

第三节系统NP中的推导

案例分析：证明策略二（推迟选择）注意：上个例子要证明一个析取命题，但我们不能通过只证明一个析取支，再用析取引入的方式来证明。分析：选取任何一个析取支来证明，都可能会面临丢失关于另外一个析取支的相关信息。总结：这个时候的证明策略是推迟选择，从前提想起或使用反证法。第三节系统NP中的推导

第三节系统NP中的推导第三节系统NP中的推导（3）德摩根律：（i）

(A

B)┤├

A

B（ii）

(A

B)┤├

A

B

第三节系统NP中的推导

关于（i），再证明

A

B

(A

B)如下：第三节系统NP中的推导第三节系统NP中的推导第三节系统NP中的推导第三节系统NP中的推导第三节系统NP中的推导第三节系统NP中的推导

第三节系统NP中的推导实例演示已知：如果小王很瘦小，那么小李不是汉族人或者小美长得不高。如果小美长得高，那么小丽很可爱。如果小丽很可爱并且小李是汉族人，那么小王很瘦小。小李是汉族人。能否推演出“小美长得不高”？

第三节系统NP中的推导

第三节系统NP中的推导

第三节系统NP中的推导

第三节系统NP中的推导

第三节系统NP中的推导第四节无前提推导与演绎定理

对于前提集是空集的情况，称为无前提的推导。对任何公式A，如果在NP中存在对它的证明，称A在系统NP中是可证的。实际上，任何重言式在NP中都是可证的；反之，任何在NP中可证的公式都是重言式。那么有前提的推导和无前提的推导之间是什么关系呢？第四节无前提推导与演绎定理

第四节无前提推导与演绎定理根据演绎定理我们可以得到如下结论：对任何公式A和B，（1）A

B当且仅当

A

B；（2）A┤├B当且仅当

A

B。这里（1）告诉我们，无前提的推导

A

B等价于有前提的推导A

B；同样，无前提的推导

A

B等价于带前提的推导A┤├B。对任何公式集

，，A，B

NPC当且仅当

，A

B

NPC。这个结论的证明可以从系统NP中推导的定义直接得到，即如下两个证明是可以相互转化的：

第四节无前提推导与演绎定理试证明逻辑规律：

(A

(B

C))

((A

B)

(A

C))证明：根据演绎定理，只要证明A

(B

C),A

B,A

C。第四节无前提推导与演绎定理根据前面第二节证明的一些逻辑规律，我们可以得到：（1）分配律：

A

(B

C)

(A

B)

(A

C)

A

(B

C)

(A

B)

(A

C)（2）选言三段论：

((A

B)

A)

B

((A

B)

B)

A（3）德摩根律：

(A

B)

A

B

(A

B