命题逻辑

维基百科，自由的百科全书

在数理逻辑中命题演算或句子演算是原子公式是命题变量的形式演绎系统。(相对于谓词逻辑，它是量化的并且它的原子公式是谓词函数；和模态逻辑，它可以是非真值泛函的。)

演算是用来证明有效的公式(就是说它的定理)和论证(argument)的逻辑系统。它是公理或公理模式的集合(它可以为空或是可数无限集合)，和推导有效的推理的推理规则。形式文法(或语法)递归定义语言的表达式和合式公式(wff)。此外给出定义真值和求值(或释义)的语义。它允许我们确定哪个 wff 是有效的(也就是定理)。

在命题演算中语言由命题变量(或者叫占位符(placeholder))和句子/判决算子(或者叫连结词)。wff 是任何原子公式或在句子操作符之上建造的公式。

在下文中我们描述一种标准命题演算。很多不同的公式系统存在，它们都或多或少等价但在下列方面不同：(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 和一个理由(justification)的形式展示出来。采用什么前提或应用了什么规则。结论将在最后一行。推导将被看作完备的，条件是所有行都是通过正确的应用一个规则而从前面的行得出的。

(作为一种对比的方式，参见证明树)。

[编辑] 公理

我们的公理集合是空集。

[编辑] 推理规则

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

双重否定除去: 从 wff ¬ ¬ φ，我们可以推出 φ。
合取介入: 从任何 wff φ 和任何 wff ψ，我们可以推出 ( φ ∧ ψ )。
合取除去: 从任何 wff ( φ ∧ ψ )，我们可以推出 φ 和 ψ。
析取介入: 从任何 wff φ，我们可以推出 (φ ∨ ψ) 和 (ψ ∨ φ)，这里的 ψ 是任何 wff。
析取除去: 从 ( φ ∨ ψ )、( φ → χ ) 和 ( ψ → χ ) 形式的wff，我们可以推出 χ。
双条件介入: 从 ( φ → ψ ) 和 ( ψ → φ ) 形式的 wff，我们可以推出 ( φ ↔ ψ )。
双条件除去: 从 wff ( φ ↔ ψ )，我们可以推出 ( φ → ψ ) 和 ( ψ → φ )。
肯定前件(条件除去): 从 φ 和 ( φ → ψ ) 形式的 wff，我们可以推出 ψ。
条件证明(条件介入): 如果在假定假设 φ 的时候可以推导出 ψ，我们可以推出 ( φ → ψ )。
反证证明(否定介入): 如果在假定假设 φ 的时候可以推导出 ψ 和 ¬ ψ，我们可以推出 ¬ φ。

[编辑] 证明的例子

下面是(语法上的)证明的一个例子:
要证明: $A \rightarrow A$
证明:

编号	wff	理由
1	A	前提
2	A $\vee$ A	析取介入自 (1)
3	(A $\vee$ A) $\wedge$ A	合取介入自 (1) 和 (2)
4	A	合取除去自 (3)
5	A $\vdash$ A	总结 (1) 到 (4)
6	$\vdash$ A $\rightarrow$ A	条件证明自 (5)

解释 $A \vdash A$ 为 "假定 A，推导出 A"。读 $\vdash A \rightarrow A$ 为 "不假定任何东西，推导出 A 蕴涵 A" ，或者 "A 蕴涵 A 是重言式" ，或者 "A 蕴涵 A 是永真的"。

[编辑] 常用的基本论证形式

名字	相继式	描述
演算的基本论证形式
肯定前件论式	(p → q) ∧ p ├ q	如果 p 则 q; p; 所以, q
否定后件论式	(p → q) ∧ ¬q ├ ¬p	如果 p 则 q; 非 q; 所以, 非 p
假言三段论式	(p → q) ∧ (q → r) ├ (p → r)	如果 p 则 q; 如果 q 则 r; 所以, 如果 p 则 r
选言三段论式	(p ∨ q) ∧ ¬p ├ q	要么 p 要么 q; 非 p; 所以, q
创造性二难论式	(p → q) ∧ (r → s) ∧ (p ∨ r) ├ (q ∨ s)	如果 p 则 q; 并且如果 r 则 s; 但是要么 p 要么 r; 所以, 要么 q 要么 s
破坏性二难论式	(p → q) ∧ (r → s) ∧ (¬q ∨ ¬s) ├ (¬p ∨ ¬r)	如果 p 则 q; 并且如果 r 则 s; 但是要么非 q 要么非 s; 所以，要么非 p 要么非 r
简化论式	(p ∧ q) ├ p	p 与 q 为真; 所以，p 为真
合取式	p, q ├ (p ∧ q)	p 与 q 分别为真; 所以，它们结合起来是真
增加论式	p ├ (p ∨ q)	p 是真; 所以析取式(p 或 q)为真
合成论式	(p → q) ∧ (p → r) ├ p → (q ∧ r)	如果 p 则 q; 并且如果 p 则 r; 所以，如果 p 是真则 q 与 r 为真
De Morgan 定律(1)	¬(p ∧ q) ├ (¬p ∨ ¬ q)	(p 与 q)的否定等价于(非 p 或非 q)
De Morgan 定律(2)	¬(p ∨ q) ├ (¬p ∧ ¬ q)	(p 或 q)的否定等价于(非 p 与非 q)
交换律(1)	(p ∨ q) ├ (q ∨ p)	(p 或 q)等价于(q 或 p)
交换律(2)	(p ∧ q) ├ (q ∧ p)	(p 与 q)等价于(q 与 p)
结合律(1)	p ∨ (q ∨ r) ├ (p ∨ q) ∨ r	p 或(q 或 r)等价于(p 或 q)或 r
结合律(2)	p ∧ (q ∧ r) ├ (p ∧ q) ∧ r	p 与(q 与 r)等价于(p 与 q)与 r
分配律(1)	p ∧ (q ∨ r) ├ (p ∧ q) ∨ (p ∧ r)	p 与(q 或 r)等价于(p 与 q)或(p 与 r)
分配律(2)	p ∨ (q ∧ r) ├ (p ∨ q) ∧ (p ∨ r)	p 或(q 与 r)等价于(p 或 q)与(p 或 r)
双重否定律	p ├ ¬¬p	p 等价于非 p 的否定
换位律	(p → q) ├ (¬q → ¬p)	如果 p 则 q 等价于如果非 q 则非 p
实质蕴涵律	(p → q) ├ (¬p ∨ q)	如果 p 则 q 等价于要么非 p 要么 q
实质等价律(1)	(p ↔ q) ├ (p → q) ∨ (q → p)	(p 等价于 q) 意味着, 要么(如果 p 是真则 q 是真)要么(如果 q 是真则 p 是真)
实质等价律(2)	(p ↔ q) ├ (p ∧ q) ∨ (¬q ∧ ¬p)	(p 等价于 q) 意味着, 要么(p 与 q 都是真)要么(p 和 q 都是假)
输出律	(p ∧ q) → r ├ p → (q → r)	从(如 p 与 q 为是真则 r 是真)我们可以证明(如果 q 是真则 r 为真的条件是 p 为真)
输入律	p → (q → r) ├ (p ∧ q) → r
重言式	p ├ (p ∨ p)	p 是真等价于 p 是真或 p 是真
排中律	├ (p ∨ ¬p)	p 或非 p 是真

[编辑] 规则的可靠性和完备性

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

我们定义真值指派为把命题变量映射到真或假的函数。非形式的，这种真值指派可以被理解为对事件的可能状态(或可能性世界)的描述，在这里特定的陈述是真而其他为假。公式的语义因而可以被形式化，通过对它们把那些"事件状态"认定为真的定义。

我们通过如下规则定义这种真值 A 在什么时候满足特定 wff:

A 满足命题变量 P 当且仅当 A(P) = 真
A 满足 ¬ φ 当且仅当 A 不满足 φ
A 满足 (φ ∧ ψ) 当且仅当 A 满足 φ 与 ψ 二者
A 满足 (φ ∨ ψ) 当且仅当 A 满足 φ 和 ψ 中至少一个
A 满足 (φ → ψ) 当且仅当没有 A 满足 φ 但不满足 ψ 的事例
A 满足 (φ ↔ ψ) 当且仅当 A 满足 φ 与 ψ 二者，或则不满足它们中的任何一个

通过这个定义，我们现在可以形式化公式 φ 被特定公式集合 S 蕴涵的意义。非形式的，就是在使给定公式集合 S 成立的所有可能情况下公式 φ 也成立。这导引出了下面的形式化定义: 我们说 wff 的集合 S 语义蕴涵(蕴涵：entail 或 imply)特定的 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)

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

I. 基础。展示: 如果 A 是 G 的成员则 G 蕴涵 A
[II. 基础。展示: 如果 A 是公理，则 G 蕴涵 A
III. 归纳步骤: (a) 假定对于任意的 G 和 A，如果 G 证明 A 则 G 蕴涵 A。(如果需要的话，对 B、C 等做同样的假定)

(b) 对于针对 A 的推论的规则的，导出一个新的句子 B 的每个可能的应用，展示 G 蕴涵 B。

(N.B. 对于上述演算基础步骤 II 可以省略，它是自然演绎系统而没有公理。基本上，它涉及展示每个公理都是(语义上)逻辑真理。)

基础步骤证实了对于任何 G 来自 G 的最简单的可证明的语句都被 G 所蕴涵。(这是简单的，因为集合蕴涵它的任何一个成员是语义事实，这是平凡的(trivial))。归纳步骤将有系统的覆盖所有的进一步的可证明的句子--通过考虑我们能够使用推理规则达成逻辑结论的每种情况--并展示如果一个新句子是可证明的，它也是在逻辑上被蕴涵的。(例如，我们可能有一个告诉我们从 "A" 可以推导出 "A 或 B"。在 III.(a) 中我们假定如果 A 是可证明的则是被蕴涵的。我们也知道如果 A 是可证明的，则 "A 或 B" 是可证明的。我们必须展示接着 "A 或 B" 也是被蕴涵的。我们求助于语义定义和我们所做的假定来完成。我们假定了 A 从 G 是可证明出来的。所以它也被 G 所蕴涵。所以使 G 全部为真的任何语义求值也使 A 为真。此外通过"或"的语义定义，使 A 为真的任何求值都使 "A 或 B" 为真。所以使 G 的全部为真的任何求值都使 "A 或 B" 为真。所以 "A 或 B"被蕴涵了。)一般的，归纳步骤将由有一定长度的，却是推论的所有规则的简单的逐个例的分析组成的，它展示每个"保持的"语义蕴涵。

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

[编辑] 完备性证明的梗概

(这通常是非常困难的证明方向。)

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

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

I. G 不证明 A。(假定)
II. 如果 G 不证明 A，则我们可以构造一个(有限的)"最大化的集合" G*，它是 G 的超集并且不证明 A。
- (a)在这个语言的所有句子上加置一个"次序"。(比如，字母表次序)，并把它们编号为 E1, E2, . . .
- (b)归纳的定义集合(G0, G1 . . . )的一个序列(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 的并集。(就是说，G* 在任何 Gn 中的所有句子的集合)。
- (d) 可以容易的展示 (i) G* 包含(是其超集) G (通过 (b.i))；(ii) G* 不证明 A (因为如果它证明 A 则某些句子被增加到某个 Gn 上而导致它证明了 A; 但是这被定义所排除)；和 (iii) G* 是(关于 A) "最大化的集合": 如果任何更多的句子不管怎样的被增加到 G*，它就会证明 A。(因为如果有可能增加任何更多的句子，再次根据定义，在构造 Gn 期间被遇到的时候它们就应当已经被增加进去了。)
III. 如果 G* 是(关于 A)的最大化集合，则它是"类真理的"。这意味着它包含句子 "A"，只在它不包含非-A 的句子的条件下; 如果它包含 "A" 并且包含 "如果 A 则 B"，则它也包含 "B"；以此类推。
IV. 如果 G* 是类真理的，则有这个语言的 "G*-规范"求值: 它使在 G* 中每个句子为真而在 G* 之外的所有句子为假，而仍然遵守在这个语言的语义合成(composition)的法则。
V. G*-规范求值将使我们最初的集合 G 全部为真，而使 A 为假。
VI. 如果有在其上 G 是真而 A 是假的求值，则 G 不(语义上)蕴涵 A。

Q.E.D.