引言

      我们在生活和工作中进行大量的推理。

刚才有没有下雨呢，你打开门发现路面是干的，就知道没有下雨。你实际上已经进行了推理：如果下雨，则路湿。现在路没有湿，所以没下雨。

孩子对妈妈说，如果明天放假我就回家，第二天孩子没有回家。妈妈推出孩子没有放假。

上面是两个具体的推理，它们都是这个模式：如果p那么q，非q，所以非p。

   有人戏言说，连狗都会推理。回家的路上，有左右两条路，狗嗅了嗅，左边的路没有它的味道，它就往右边走了。狗的推理如下：回家的路不是左就是右，现在知道不是左边的路，所以是右边的路。这里的推理模式是这样的：要么p要么q，非p，所以q。

推理的本质是从前提推出结论，有效推理就是前提为真时结论必然为真。

我们下面介绍命题逻辑系统，这个系统能产生所有有效的命题推理。

先解释几个概念。

什么是命题逻辑。

命题逻辑就是关于命题推理的逻辑。上面的所有推理都属于命题推理。它利用命题联结词的性质进行推理，命题联结词指的是并且、或者、如果那么这类联结命题的词。

举个例子，这个推理就不属于命题推理：所有的人都要呼吸，张三是人，所以张三需要呼吸。这个推理利用了“所有”这个词的性质，而它不是命题联结词。

命题逻辑系统

联结词

这里介绍命题推理系统。它包括这些联结词：并非、并且、或者、如果那么、当且仅当。分别用符号﹁、∧、∨、→、↔表示，而命题也用字母符号表示。比如p→q，表示如果p那么q，p∧﹁q，表示p并且﹁q。利用这些符号我们可以构造复杂的命题，比如：(p↔q)∨(p→(q→(﹁p∧r)))。

我们规定：

p∧q =_df ﹁(p→﹁q)

p∨q =_df﹁p→q

p↔q =_df(p→q)∧(q→p)

就是说，左边的命题可以用右边的命题是等价的。只有联结词﹁和→是基本的，∧、∨、↔都用它们来定义。

   公理系统

命题逻辑系统有很多种，比如公理化系统、自然推理系统、sequent系统等。这里讨论的是公理化系统。它就像我们以前学过的几何证明一样，从几条公理出发，通过推理得到结论。

公理：

1、p→(q→p)

2、 (p→(q→r))→((p→q)→(p→r))

3、 (﹁p→﹁q)→( q→p)

推理规则：

从p和p→q，推出q

这条推理规则又叫分离规则。上面的公理和推理规则中的p、q、r可以代表任何命题。比如r→(s→r)也是公理，它只是把p换成了r，q换成了s。(p∨q)→((r∧s)→(p∨q))也是公理，它把p换成了p∨q，q换成了r∧s。

上面的公理中，仅出现﹁和→，没有出现∧、∨、↔。

定理和推理

通过公理和推理规则证明的任何一个命题都是定理，记作⊢A，表示A是定理，亦即A是无条件成立的。如果一个命题还需要其他前提才能证明得到，则记作A ⊢B，表示A是前提，B是结论。从定义可知，任何公理都是定理。

下面举例说明。

定理：⊢p→p

证明：

(1)、 (p→((p→p)→p))→((p→(p→p))→(p→p))

(2)、 p→((p→p)→p)

(3)、(p→(p→p))→(p→p)

(4)、p→(p→p)

(5)、p→p

说明：(1)是公理2，它把q换成p→p，r换成p；(2)是公理1，它把q换成p→p；(3)是(1)和(2)通过分离规则得到；(4)是公理1，它把q换成p；(5)是(3)和(4)通过分离规则得到。

定理：⊢p∨﹁p

证明：

(1)、 p→p

(2)、﹁p→﹁p

(3)、 p∨﹁p

说明：(1)在前面已证，(2)是将(1)中的p换成﹁p，(3)是根据联结词∨的定义从(2)得到。

定理：p∨q，﹁p ⊢q

(1)、 p∨q

(2)、﹁p→q

(3)、﹁p

(4)、q

说明：(1)和(3)是前提，(2)是根据联结词∨的定义从(1)得到，(4)根据(2)和(3)通过分离规则得到。

命题逻辑中有一个重要的定理叫演绎定理，利用它能简化证明的过程。

演绎定理

  如果Γ,A ⊢B ，那么Γ⊢A→B。

  这里Γ是命题集（可以是空集），A和B是任意命题。如果某个命题集Γ和命题A推出B，则从Γ可推出A→B。这个定理的证明从略。

定理：p→q，q→r ⊢p→r

要证明p→q，q→r ⊢p→r，根据演绎定理，只要证明p→q，q→r，p ⊢r 就行了。现在来证明这一点。

(1)、 p→q

(2)、q→r

(3)、 p

(4)、 q

(5)、 r

真值语义

     真值表

研究逻辑系统的一个很重要的目的是希望找出所有的有效推理，即前提真则结论真的推理。每一个命题都有真假。命题分为简单命题和复合命题，有时又叫原子命题和分子命题。天是蓝的，草是绿的，这一类称之为简单命题，天是蓝的或者草是绿的，是复合命题。复合命题的真值由构成它的简单命题和联结词决定。具体的方式见下面的真值表。

上面的表格中用1表示真，0表示假。第一个格中，当p为真时，﹁p为假，p为假时，﹁p为真。第二个表格第一行表示，当p和q都为假时，p→q 为真。其他行的意思类似。

有了这两个真值表，我们可得出所有其他命题的真值表。比如p∧q，我们根据它的定义，它和﹁(p→﹁q)等价，我们得出﹁(p→﹁q)的真值表就是它的真值表。同样，可得出p∨q，p↔q的真值表。

再举个例子。

在这些真值表中，你会发现p→q的真值语义和我们日常理解的不一样，比如按它的理解，p真q真则p→q真，所以“如果1+1=2则草是绿的”这句话是真的。

逻辑学中p→q这种异常的含义把叫做蕴含怪论。之所以这样定义它的真值，是为了在数学上处理更方便，就像物理学研究中假设无摩擦一样。p→q的真值定义保留了p→q最本质的特征，当p→q为真，且p为真时，q为真。

思考：要么p要么q、除非p否则q，这两个联结词的真值表是怎样的，这两个联结词怎样用前面的联结词定义。

联结词完全集

可以把联结词看作是一个函数，比如∧是一个二元函数，∧(0,0)=0，∧(0,1)=1，∧(1,0)=1，∧(1,1)=1。

可以证明任何真值函数都可以用{﹁，∧}、{﹁，∨}、{﹁，→}的任一种表示。

举例说明第一种情况：

f(0)=0，f(1)=1。则f(x)= x

f(0)=0，f(1)=0。则f(p)=x∧﹁x

f(0,0)=0，f(0,1)=0，f(1,0)=1，f(1,1)=1，则f(x,y)=﹁(﹁(x∧﹁y)∧﹁(﹁x∧y))

实际上我们可以定义一个联结词↓，使得它能表示所有真值函数。它是这样定义的：↓(0,0)=1，↓(0,1)=0，↓(1,0)=0，↓(1,1)=0。可以证明它能表示所有函数。