命题逻辑

数理逻辑的较简单的基础部分，研究由命题经命题联结词构成的复合命题的逻辑性质，以及关于这样构成的命题间的推理关系。也可以说，它研究命题联结词的逻辑性质和相应的推理规律。命题逻辑分经典命题逻辑和非经典命题逻辑，后者如构造性逻辑、模态逻辑的命题逻辑部分。历史上最早研究命题逻辑的是古希腊麦加拉派的哲学家。现代对命题逻辑的研究始于19世纪中叶的G．布尔，他首次应用数学方法研究逻辑。命题演算是命题逻辑的形式系统，它是在19世纪末20世纪初最早建立的重要的完全的逻辑演算系统。它的奠基者是G．弗雷格及其后的G．皮亚诺和B．A．W．罗素等。

在命题逻辑中，只将复合命题分析成它的组成部分。凡是不经由联结词构成的命题都作为初始命题，不对它们的内部结构作进一步的分析，把它们看作是只具有真或假的区别的对象。

常用的命题联结词有：“非”、“并且”、“或者”、“如果、则”和“当且仅当”，分别称为否定词、合取词、析取词，蕴涵词和等值词，上面这5个联结词分别用下面5个符号表示：、∧、∨、→和(不同的作者使用的符号不都相同。)由命题A经使用否定词构成否定命题“非A”。由命题A，B经使用合取词、析取词、蕴涵词和等值词依次构成合取命题“A并且B”、析取命题“A或者B”，蕴涵命题“如果A，则B”和等值命题“A当且仅当B”。

为了分析和显示命题联结词的逻辑性质，使用命题变元p，q，r，…，命题变元表示任意的命题。使用命题变元和联结词的符号，上一段中说的否定命题、合取命题、析取命题、蕴涵命题和等值命题，可以依次表示成：p，p∧q，p∨q，p→q和pq。5个联结词表示5个真值函数：即p，p∧q，p∨q，p→q和pq的真值(真或假)由p和q的真值唯一地决定。当p的真值是真时，p的真值为假，当p的真值是假时，p的真值为真。当p和q的真值都是真时，p∧q的真值为真，在其它3种情况：p真且q假、p假且q真、p和q都假，p∧q的真值为假。当p和q的真值都是假时，p∨q的真值为假，在p和q的其它真值情况下，p∨q为真。当p的真值为真、q的真值为假时，p→q的真值为假，在p和q的其它真值情况下，p→q的真值为真。当p和q的真值同为真或同为假时，pq的真值为真，否则pq为假。p，p∧q，p∨q，p→q和pq的真值由p和q的真值唯一地决定，可以方便地用它们的真值表来列示(参见真值表)。

一命题A称为一组命题Γ的逻辑后承(在命题逻辑中，也特别地称为重言后承)，记作：ΓA，如果Γ中的命题都真时，则A也必真。“”表示推理关系。当不论构成命题A的初始命题的真值是真还是假，A的真值常为真，则称A为常真式，也称为重言式，记作：A。例如，p→p，p→p∨q。通过构造A的真值表，可以判定A是不是重言式。

命题逻辑中的重言式为数无穷，它们在一定意义上都表达逻辑定律。为了系统地研究和掌握这些逻辑定律，需要对它们作整体的考虑，将全部重言式都包括在一个系统之中。为此，可用公理方法将全部命题逻辑的定律系统化，从而得到一个形式系统，称为命题演算。下面构造命题演算P。

P的初始符号包括：①命题变元：p，q，r，…；②命题联结词：，∧，∨，→和；③技术性符号：(，)。

P的初始符号的有穷序列，称为表达式。表达式用字母X，Y，Z表示。(X，Y，Z不是P中的符号，而是元语言中的符号。)根据形成规则生成的表达式称为合式公式，简称公式。P的形成规则有以下3条：(1)单独一个命题变元是一合式公式；(2)如果X，Y是合式公式，则X，(X∧Y)，(X∨Y)，(X→Y)和(XY)是合式公式；(3)只有适合以上两条的是合式公式。

以上初始符号和形成规则两部分构成命题演算P的(形式)语言。

用字母A，B，C，D表示任意公式(A，B，C，D是语法变元，不是P中的符号)。

P的公理有以下15条：

1．A→(B→A)

2．(A→(A→B))→(A→B)

3．(A→B)→((B→C)→(A→C))

4．(A→B)→(B→A)

5．A→A

6．A→A

7．A∧B→A

8．A∧B→B

9．(A→B)→((A→C)→(A→B∧C))

10．A→A∨B

11．A→B∨A

12．(A→C)→((B→C)→(A∨B→C))

13．(AB)→(A→B)

14．(AB)→(B→A)

15．(A→B)→((B→A)→(AB))

以上15条都是公理模式，实际上每一条都代表无数条公理，凡是具有以上15条形状之一的公式，都是公理。例如，根据1．p→(q→p)，q→(p→q)，p→(q∧r→p)等等都是公理。采用公理模式，可以在推演规则中省去命题变元代入规则。

P的推演规则有一条，即：

分离规则：从A→B和A，可以推出B。A→B和A称为前提，B称为结论。

给定了公理和推演规则，一个命题演算就完全确定了。

公式的有穷序列A，…A，称为一个证明，如果其中每一A(i=1，…，n)或者是公理，或者是由两个在前的公式A和A(=A→A)应用分离规则而得。一个证明也说是它的最后一个公式A的证明。

一个公式A称为P的定理，如果它有一个证明，即存在一个证明A，…，A，而A即是A。根据定理的定义，每一公理都是定理。一个公式是定理，当且仅当它是可证明的。A是定理记作：┝A。“┝”为语法符号。

设Γ为公式的集合，A为任一公式。称A是从Γ(在P中)可推演的，记作Γ┝A，如果存在公式的有穷序列A，…，A，其中每一A(=i，…，n)或者是公理，或者是Γ中的公式，或者是由在前的两个公式应用分离规则而得，并且A即是A。公式序列A，…，A称为从Γ得出A的推演。

演绎定理：如果Γ，A┝B，则Γ┝A→B。

演绎定理是说，如果存在一个从前提Γ和A得出结论B的推演，则存在另一个从Γ得出A→B的推演。

定理、证明(可证明性)和推演等都是语法概念。它们只同公式的形状，和根据推演规则从公式到公式的变换有关，完全不涉及符号、公式等的意义。但是命题演算P的初始符号的名称暗示着它们的一种解释，即可把构成公式的符号解释成前面部分所说的命题变元和命题联结词。

容易验证，经解释后，P的公理都是重言式。推演规则具有保真性，即当前提为真时，经应用规则而得的结论也必真。把规则应用于公理而证明的定理都是重言式。系统P有

可靠性定理；凡定理都是重言式。如果Γ┝A，则ΓA。可靠性定理说明，P可靠地(正确地)反映了直观推理的逻辑规律。

从可靠性定理也可得出系统P是协调的，或者说在P中是推不出矛盾的，即不存在一个公式A，使得A和A都是系统中的定理。

命题演算P也具有完全性，即有

完全性定理：凡重言式都是P的定理。如果ΓA，则Γ┝A。完全性定理说明，系统P无遗漏地反映了命题逻辑的全部正确的推理规律。完全性定理由E．L．波斯特在1921年证明。

P中的每一公式都可变换成一个与它等值的析取范式，和一个与它等值的合取范式。应用合取范式，可以判定一个公式是不是重言式，并且，如果是重言式，则还可以得到它的一个证明。

命题演算P的初始符号，∧，∨，→和不是独立的，是可以相互定义的。例如，用和→，可以定义∧，∨，和。P的公理也不是独立的，即是说，去掉其中某些公理后，它们可在新的系统中证明，在新的系统中仍可证明全部重言式。但是P这样的系统有一个优点，每一个基本联结词都有一组公理刻划它的特征；并且具有各组公理自足的性质，即：在证明定理时，除了用到关于→的公理，只需用到所要证明的公式中出现的联结词的公理。

可靠性定理、协调性定理和完全性定理都不是P中的定理，而是关于P的定理。它们断言的是关于整个系统P的性质。

把P的公理稍作改变，即把公理5改为公理5′：A→(A→B)，并且去掉公理6，结果就得到直觉主义的命题演算系统。当然，在直觉主义系统中，联结词需作构造性的解释，联结词(除外)是不能相互定义的。

如果把命题变元看作是取0和1为值的变元，并且把联结词，∧，∨解释为运算“′”、“·”和“+”(即：0′=1，1′=0；1·1=1，1·0=0·1=0·0=0；1+1=0+1=1+0=1，0+0=0。)就得到一个定义在两个元素0和1上的布尔代数。