数学逻辑学论文-

哈尔滨师范大学

题 目 命题逻辑在数学教学中的应用

学 生

指导教师 鲍曼

年 级 2013

专 业 信息与计算科学

系 别 数学系

学 院 数学科学学院

哈尔滨师范大学

年 月

论 文 提 要

本文主要讨论了命题逻辑与数学以及数学教学之间的关系 , 并说明中学数学教师学习命题逻辑的重要意义以及命题逻辑对于培养中学数学教师的作用，命题逻辑是一个以命题为基本研究对象的数学化的逻辑系统, 命题逻辑是数理逻辑的基础, 也是计算机科学与技术的理论基础。为了深入理解命题逻辑, 将命题逻辑与一般的数学进行比较, 从各个方面简要总结和论述命题逻辑中数学的一些思想和方法, 使得读者能从中体会到数学的一些思想和方法在命题逻辑中的应用，对应的对我们在数学教学方面合理的应用命题逻辑有着不可取代的帮助。

命题逻辑在数学教学中的应用

赵力博

摘 要：本文主要讨论了命题逻辑与数学以及数学教学之间的关系 , 并说明中学数学教

师学习命题逻辑的重要意义以及命题逻辑对于培养中学数学教师的作用，命题逻辑是一个以命题为基本研究对象的数学化的逻辑系统, 命题逻辑是数理逻辑的基础, 也是计算机科学与技术的理论基础。为了深入理解命题逻辑, 将命题逻辑与一般的数学进行比较, 从各个方面简要总结和论述命题逻辑中数学的一些思想和方法, 使得读者能从中体会到数学的一些思想和方法在命题逻辑中的应用，对应的对我们在数学教学方面合理的应用命题逻辑有着不可取代的帮助。

关键词：命题逻辑 数学教学 数理逻辑

最早人们是使用自然语言研究逻辑，在某种情况下，由于自然语言容易产生二义性，这给逻辑的研究带来了很大的麻烦和不便。由于数学的严密性，为了克服这种弊端，人们便在逻辑的研究中引进数学的方法，这样就产生了数理逻辑。数理逻辑是从量的侧面来研究逻辑的。从模型化的观点来看，数理逻辑是研究“数学思维”的一种数学模型。数理逻辑又称符号逻辑，这种方法的优点是表达简洁，推理方便、概括性好、易于分析。

命题逻辑是一个以命题为基本研究对象的数学化的逻辑系统，命题逻辑是数理逻辑的基础，是计算机科学与技术的理论基础。对命题逻辑的理解直接影响数理逻辑的其他内容的学习和理解。既然命题逻辑是一种用数学的方法研究逻辑而形成的学科，那么就需要关注在命题逻辑中体现的数学的思想和方法。本文就是命题逻辑中数学的一些思想和方法做简要的总结和论述。

为了研究的方便，首先对命题进行量化。尽管具体的命题很多，但从真值的角度来看，只有2个——真命题和假命题。规定真命题的真值为1，假命题的真值0。这样就完成了对命题的量化。

引进逻辑运算符、规定逻辑运算规则，从而形成了一整套命题定律

数学实际上是一系列的”运算“，这种”运算“能在任何符号的集合上，根据一定的公设来进行。

命题逻辑引进了相当于数学中的代数运算符一样的逻辑运算符¬，∧，∨，→，等，同时命题逻辑以真值表的形式规定如何进行运算，也规定在有多种逻辑运算符参加的运算中逻辑运算符的优先级，这就相当于再数学中先算乘方、开方、再算乘法、除法，最后计算加法、减法一样。逻辑连结词运算的优先级从高到低为¬，∧，∨，→，。从而也形成了一整套命题定律。

与数学一样，命题逻辑也引进命题常量和变量，这样使逻辑的研究发生重大的变革，逻辑的研究也进入变量时代，这是一种质的飞跃，也可以数数理逻辑是一种变量逻辑、变量数学。这样逻辑的研究就能像数学一样进行演算和推理。这为逻辑的研究带来了及其丰富的思想和方法。

命题逻辑也引进像数学的代数式一样的命题公式。袋鼠学中的袋鼠实际上是用数学运算符按一定的规则联结数学运算对象而成的一个字符串，而命题公式则是用逻辑运算符按一定的规则联结逻辑运算对象而成的一个字符串；命题公式和数学式都是一个字符串，他们唯一的区别是运算符、运算对象和运算规则不同，其余都是相同。如果从更抽象的角度来看，只有运算规则不同。所以把一个命题公式可以看成一个代数式，对命题公式施行一些与数学很类似的一些变换和演算。例如数学中在代数式的所以变量的值给定的情况下，可以求代数式的值。命题逻辑中在一个命题公式的所有变量的值给定情况下，就可以求命题公式的值。如果抽象的看，求代数式的值和求命题公式的值没有本质的区别。

函数是数学研究的重点，也是数学的核心，函数是研究变量关系的一种重要的工具和模型。在完成前面一些工作以后，命题逻辑自然也引进命题函数。如：

G(P，Q ，R)=P∧Q →R

就是一个三元命题函数。命题函数的引进正式宣告了数理逻辑的诞生。对于一个n 元命题函数G(P 1, P 2, ⋅⋅⋅, P n ) ，P 1, P 2, ⋅⋅⋅, P n 是n 个变元，而P i （i=1，2，„，n ）的取值范围都是｛0，1｝，因为他的定义域为{0,1他的值域为｛0，1｝。这样n 元命题函数G （P }n 。1, P 2, ⋅⋅⋅, P n ）是从{0,1}n →[0，1]的一个函数。

这样数学中的一些思想和方法就可以应用与逻辑的研究之中。如可以像求函数的函数值一样求命题函数的真值，对命题公式做与对函数式做恒等变形一样的等值演算。

下面举几个例子说明：

例1 已知G(P，Q)= ¬(P∧Q) →(¬P∨(¬P ∨Q)), 求G （1，0）。

解：

G(1，0)= ¬（1∧0）→（¬1∨（¬1∨0））

= ¬0→（0∨（0∨0））

=1→(0∨0)

=1→0

=0

例2 化简G （P ，Q ）=¬(P∧Q) →(¬P∨(¬P ∨Q))

解：

G （P ，Q ）=(P∧Q) ∨(¬P ∨(¬P ∨Q))

=(P∧Q) ∨(¬P ∨Q)

=（P ∨¬P ∨Q ）∧(Q∨¬P ∨Q)

=1∧(¬P ∨Q)

=¬P ∨Q

命题逻辑中的代入规则，实际上就是数学中换元的思想和方法在逻辑的研究中的再现与应用。运用基本的永真式和基本的永假式与命题逻辑中的代入规则可以产生大量的永真式和永假式。

例3 判断命题公式G=（P ∧Q →R）∨¬(P∧Q →R)的类型

解：令S=P∧Q →R，则G=S∨¬S=1，显然该命题公式是永真式。

在下文中我们描述一种标准命题演算。很多不同的公式系统存在，它们都或多或少等价但在下列方面不同：(1)它们的语言; (2) 它们有哪些公理; (3)采用了哪些推理规则。

语言的构成:

字母表的大写字母，表示命题变量。它们是原子公式。惯例上，使用拉丁字母(A, B, C) 或希腊字母(χ, φ, ψ)，但是不能混合使用。

表示连结词(connective)(或逻辑算子) 的符号: ¬、∧、∨、→、。(我们可以使用更少的算子，因为一些算子是简写形式 — 例如，P → Q 等价于 ¬ P ∨ Q) 。

左右圆括号: (，) 。

合式公式(wff)的集合右如下规则递归的定义:

基础: 字母表的字母(通常是大写的，如A 、B 、φ、χ 等) 是 wff 。

归纳条款 I: 如果 φ 是 wff ，则 ¬ φ 是 wff 。

归纳条款 II 如果 φ 和 ψ 是 wff ，则 (φ ∧ ψ)、(φ ∨ ψ)、(φ → ψ) 和 (φ ψ) 是 wff 。

闭包条款: 其他东西都不是 wff 。

重复的应用这三个公式允许生成复杂的 wff 。例如:

通过规则 1，A 是 wff 。

通过规则 2，¬A 是 wff 。

通过规则 1，B 是 wff 。

通过规则 3，(¬A ∨ B ) 是 wff 。

为了简单化，我们使用自然演绎系统，它没有公理；或者等价的说，它有空的公理集合。

使用我们的演算的推导将用编号后的行的列表，在每行之上有一个单一的 wff 和一个理由的形式展示出来。任何前提都在上部，并带有 "p" 作为它们的断定。结论将在最后一行。推导将被看作完备的，条件是所有行都是通过正确的应用一个规则而从前面的行得出的。

公理

我们的公理集合是空集。

推理规则

我们的命题演算有十个推理规则。这些规则允许我们从给定的一组假定为真的公式中推导出其他为真的公式。前八个简单的陈述我们可以从其他 wff 推论出特定的 wff 。但是最后两个规则使用了假言推理，这意味着在规则的前提中我们可以临时的假定一个假设作为推导出的公式集合的一部分，来查看我们是否能推导出一个特定的其他公式。因为前八个规则不是这样而通常被描述为非假言规则，而最后两个就叫做假言规则。

双重否定除去

从 wff ¬ ¬ φ，我们可以推出 φ。

合取介入

从任何 wff φ 和任何 wff ψ，我们可以推出 ( φ ∧ ψ ) 。

合取除去

从任何 wff ( φ ∧ ψ ) ，我们可以推出 φ 和 ψ。

析取介入

从任何 wff φ，我们可以推出 (φ ∨ ψ) 和 (ψ ∨ φ)，这里的 ψ 是任何 wff 。 析取除去

从 ( φ ∨ ψ ) 、( φ → χ ) 和 ( ψ → χ ) 形式的wff ，我们可以推出 χ。 双条件介入

从 ( φ → ψ ) 和 ( ψ → φ ) 形式的 wff ，我们可以推出 ( φ ψ ) 。 双条件除去

从 wff ( φ ψ ) ，我们可以推出 ( φ → ψ ) 和 ( ψ → φ ) 。

肯定前件

从 φ 和 ( φ → ψ ) 形式的 wff ，我们可以推出 ψ。

条件证明

如果在假定假设 φ 的时候可以推导出 ψ，我们可以推出 ( φ → ψ ) 。 反证证明

如果在假定假设 φ 的时候可以推导出 ψ 和 ¬ ψ，我们可以推出 ¬ φ。 规则的可靠性和完备性

这组规则的关键特性是它们是可靠的和完备的。非形式的，这意味着规则是正确的并且不再需要其他规则。这些要求可以如下这样正式的提出。

我们定义真值指派为把命题变量映射到真或假的函数。非形式的，这种真值指派可以被理解为对事件的可能状态的描述，在这里特定的陈述是真而其他为假。公式的语义因而可以被形式化，通过对它们把那些" 事件状态" 认定为真的定义。 我们通过如下规则定义这种真值 A 在什么时候满足特定 wff:

A 满足命题变量 P 当且仅当 A(P) = 真

A 满足 ¬ φ 当且仅当 A 不满足 φ

A 满足 (φ ∧ ψ) 当且仅当 A 满足 φ 与 ψ 二者

A 满足 (φ ∨ ψ) 当且仅当 A 满足 φ 和 ψ 中至少一个

A 满足 (φ → ψ) 当且仅当没有 A 满足 φ 但不满足 ψ 的事例

A 满足 (φ ψ) 当且仅当 A 满足 φ 与 ψ 二者，或则不满足它们中的任何一个

通过这个定义，我们现在可以形式化公式 φ 被特定公式集合 S 蕴涵的意义。非形式的，就是在使给定公式集合 S 成立的所有可能情况下公式 φ 也成立。这导引出了下面的形式化定义: 我们说 wff 的集合 S 语义蕴涵特定的 wff φ，条件是满足在 S 中的公式的所有真值指派也满足 φ。

最后我们定义语法蕴涵，φ 被 S 语法蕴涵，当且仅当我们可以在有限步骤内使用我们提出的上述推理规则推导出它。这允许我们精确的公式化推理规则的可靠性和完备性的意义:

可靠性

如果 wff 集合 S 语法蕴涵 wff φ，则 S 语义蕴涵 φ

完备性

如果 wff 集合 S 语义蕴涵 wff φ，则 S 语法蕴涵 φ

对上述规则集合这些都成立。

可靠性证明的梗概

符号约定: 设 "G" 是涉及语句集合的变量。设 "A" 、"B" 和 "C" 是涉及句子的变量。我们把 "G 语法蕴涵 A" 写成 "G 证明 A" 。我们把 "G 语义蕴涵 A" 写成 "G 蕴涵 A" 。

我们要展示: (A)(G)

我们注意到 "G 证明 A" 有一个归纳定义，这给予我们直接的办法来证实，如果 G 证明 A ，则 . . ." 形式的断言。所以我们的证明是用归纳法进行的。

I. 基础。展示: 如果 A 是 G 的成员则 G 蕴涵 A

[II. 基础。展示: 如果 A 是公理，则 G 蕴涵 A

III. 归纳步骤: (a) 假定对于任意的 G 和 A ，如果 G 证明 A 则 G 蕴涵 A 。 (b) 对于针对 A 的推论的规则的，导出一个新的句子 B 的每个可能的应用，展示 G 蕴涵 B 。

基础步骤证实了对于任何 G 来自 G 的最简单的可证明的语句都被 G 所蕴涵。归纳步骤将有系统的覆盖所有的进一步的可证明的句子--通过考虑我们能够使用推理规则达成逻辑结论的每种情况--并展示如果一个新句子是可证明的，它也是在逻辑上被蕴涵的。一般的，归纳步骤将由有一定长度的，却是推论的所有规则的简单的逐个例的分析组成的，它展示每个" 保持的" 语义蕴涵。

通过可证明性的定义，除了 G 的成员、公理、或从规则得出的句子之外没有是可证明的；所以如果所有这些都是语义上被蕴涵的，则演绎演算是可靠的。 完备性证明的梗概

我们接受同上面一样的符号约定。

我们要展示: 如果 G 蕴涵 A ，则 G 证明 A 。我们通过反证法来进行: 我们转而展示如果 G 不证明 A ，则 G 不蕴涵 A 。

I. G 不证明 A 。

II. 如果 G 不证明 A ，则我们可以构造一个" 最大化的集合" G*，它是 G 的超集并且不证明 A 。

(a)在这个语言的所有句子上加置一个" 次序" 。并把它们编号为 E1, E2, . . . (b)归纳的定义集合的一个序列(series) Gn 为如下 (i)G0=G。 (ii) 如果 {Gk, E(k+

1)} 证明 A ，则 G(k+1)=Gk。 (iii) 如果 {Gk, E(k+1)} 不证明 A ，则 G(k+1)={Gk, E(k+1)} (c)定义 G* 为所有 Gn 的并集。 (d) 可以容易的展示 (i) G* 包含(是其超集) G (通过 (b.i))；(ii) G* 不证明 A (因为如果它证明 A 则某些句子被增加到某个 Gn 上而导致它证明了 A; 但是这被定义所排除) ；和 (iii) G* 是(关于 A) " 最大化的集合": 如果任何更多的句子不管怎样的被增加到 G*，它就会证明 A 。 III. 如果 G* 是的最大化集合，则它是" 类真理的" 。这意味着它包含句子 "A" ，只在它不包含非-A 的句子的条件下; 如果它包含 "A" 并且包含 " 如果 A 则 B" ，则它也包含 "B" ；以此类推。

IV. 如果 G* 是类真理的，则有这个语言的 "G*-规范" 求值: 它使在 G* 中每个句子为真而在 G* 之外的所有句子为假，而仍然遵守在这个语言的语义合成的法则。

V. G*-规范求值将使我们最初的集合 G 全部为真，而使 A 为假。

VI. 如果有在其上 G 是真而 A 是假的求值，则 G 不蕴涵 A 。 Q.E.D. 可供选择的演算

有可能定义其他版本的命题演算，它通过公理的方式定义了多数逻辑算子的语法，并且它只使用一个推理规则。

公理

设 φ、χ 和 ψ 表示合式公式。公理有

THEN-1: φ → (χ → φ)

THEN-2: (φ → (χ → ψ)) → ((φ → χ) → (φ → ψ))

AND-1: φ ∧ χ → φ

AND-2: φ ∧ χ → χ

AND-3: φ → (χ → (φ ∧ χ))

OR-1: φ → φ ∨ χ

OR-2: χ → φ ∨ χ

OR-3: (φ → ψ) → ((χ → ψ) → (φ ∨ χ → ψ))

NOT-1: (φ → χ) → ((φ → ¬ χ) → ¬ φ)

NOT-2: φ → (¬ φ → χ)

NOT-3: φ ∨ ¬ φ

公理 THEN-2 可以被看作是" 关于蕴涵的蕴涵的分配特性" 。公理 AND-1 和 A ND-2 对应于" 合取除去" 。在 AND-1 和 AND-2 之间的关系反映了合取算子的交换性。公理 AND-3 对应于" 合取介入" 。公理 OR-1 和 OR-2 对应于" 析取介入" 。在 OR-1 和 OR-2 之间的关系反映了析取算子的交换性。公理 NOT-1 对应于" 反证法" 。公理 NOT-2 说明了" 从矛盾中可以推导出任何东西" 。公理 NOT-3 叫做" 排中律" 并反映了命题公式的语义求值: 公式可以有的真值要么是真要么是假。至少在经典逻辑中，没有第三个真值。直觉逻辑不接受公理 NOT-3。

推理规则

推理规则是肯定前件:

\phi, \ \phi \rightarrow \chi \vdash \chi .

如果还使用双箭头的等价算子的话，则要增加如下" 自然" 推理规则:

IFF-1: \phi \leftrightarrow \chi \vdash \chi \rightarrow \phi

IFF-2: \phi \rightarrow \chi, \ \chi \rightarrow \phi \vdash \phi \leftrightarrow \chi

元推理规则

设示范被表示为相继式，假设在十字转门的左侧而结论在十字转门的右侧。则演绎定理可以被陈述如下:

如果相继式

\phi_1, \ \phi_2, \ ... , \ \phi_n, \ \chi \vdash \psi 已经被证明了，则也有可能证明相继式

\phi_1, \ \phi_2, \ ..., \ \phi_n \vdash \chi \rightarrow \psi 。

这个演绎定理自身没有公式化为命题演算: 它不命题演算的定理，而是关于命题演算的一个定理。在这个意义上，它是元定理，相当于关于命题演算可靠性和完备性的定理。

在另一方面，DT 对与简化语法上的证明过程是如此的有用以至于它看作和用做推理规则，同肯定前件一起使用。在这个意义上，DT 对应于自然条件证明推理规则，它是在本文中提出的第一个版本的命题演算的一部分。

DT 的逆定理也是有效的:

如果相继式

\phi_1, \ \phi_2, \ ..., \ \phi_n \vdash \chi \rightarrow \psi

已经被证明了，则也有可能证明相继式

\phi_1, \ \phi_2, \ ... , \ \phi_n, \ \chi \vdash \psi 实际上，DT 的逆定理的有效性相对于 DT 而言是平凡的:

如果

\phi_1, \ ... , \ \phi_n \vdash \chi \rightarrow \psi 则

1: \phi_1, \ ... , \ \phi_n, \ \chi \vdash \chi \rightarrow \psi

2: \phi_1, \ ... , \ \phi_n, \ \chi \vdash \chi

并且可以演绎自 (1) 和 (2)

3: \phi_1, \ ... , \ \phi_n, \ \chi \vdash \psi

通过肯定前件的方式，Q.E.D.

DT 的逆命题有着强有力的蕴涵: 它可以用来把公理转换成推理规则。例如，公理 AND-1,

\vdash \phi \wedge \chi \rightarrow \phi

可以通过演绎定理的逆定理的方式被转换成推理规则

\phi \wedge \chi \vdash \phi

这是合取除去，是第一个版本的命题演算中使用的十个推理规则中的一个。 利用数学的思想和方法研究逻辑是数理逻辑最主要的特征，也是逻辑研究的新境界。学习数理逻辑一定要看到数学在命题逻辑中的影子，否则就无法正确地理解命题逻辑的真含。

参考文献：

【1】 张忠志. 离散数学[M].北京：高等教育出版社，2002.

【2】 李盘林，李丽双，李洋，等，离散数学[M].北京：高等教育出版社，1999.

【3】 任现淼. 计算机数学基础（上册）——离散数学[M].2版. 北京：中央广播电视大学

出版社，2000.