数理逻辑之 命题

数理逻辑的一项重要任务是回答“什么是证明？” 并试图将“证明”这一概念（与之相关有可计算性概念）精确化。基于这个目的，数理逻辑需要设计适当的语言用于对计算机科学领域中遇到的情景建模，以便于对它们作形式推理，得到我们想要的结论。

为了将证明精确化，所用的方法是什么呢？数理逻辑在研究推理时要建立数学模型（我们称这个数学模型为形式系统）ß对形式系统进行研究，必须用普通的自然语言（元语言）ß研究推理时不可避免要用到逻辑ß逻辑是由演算组成的ß在进行推理时需要用到精确的演算规则ß推理过程中所使用的语言必须无二义性，以便于构造有效的推理论证。

在计算机应用中，这就要求我们构造的论证必须是有效的且能在计算机上执行。因此，为了达到这样的目的，通常的方法是引进一种符号语言，它能够精确表达其意义。

先来看第一个例子：

例1  
①If the train arrives late and there are no taxis at the station, then John is late for his meeting.  
②John is not late for his meeting.  
③The train did arrive late.  
④Therefore, there were taxis at the station.           

看完这个例子，直觉告诉我们,这一论证是有效的：

 ①  ③告诉我们,如果车站没有出租车,那么John必迟到；②告诉我们John没有迟到.。

因此车站一定有出租车。

上述的论证有以下结构:

语句序列               前提  
        therefore              结论             

我们说，如果“Therefore” 后的语句逻辑地从前面的语句序列进行推断，这个论证就是有效的。

为了加深印象再看一个同样的例子（刚开始概念可能比较简单，但是我们说的稍微详细一些）：

例2  
①If it is raining, and Jane does not have her umbrella with her, then she will get wet.  
②Jane is not wet.  
③It is raining.  
④Therefore, Jane has her umbrella with her.           

 ① ③告诉我们， 如果Jane不带雨伞,那么Jane被雨淋显。②告诉我们 Jane没有被雨淋湿。

因此Jane 一定带了雨伞。

这俩例子有同样的结构（可能你自己总结的结构会不一样）：

If p and not q then r  
    Not r   
    p  
    Therefore, q             

在进行逻辑推理时，我们仅仅关注这些句子的逻辑结构。即，我们仅考察论证形式。在实际应用这种“论证形式”时，我们会考虑这些句子的实际意义。在上述两个实例中,前提和结论都是简单命题构成。

为了使论证严密，我们需要设计一个语言，利用这一语言，能够表示这些语句并使论证形式突显。我们先讨论命题逻辑语言。命题逻辑语言基于命题或陈述句。原则上，我们约定这些命题或陈述句不是真就是假。

 断言是一个陈述句。一个命题是一个或真或假而不能两者都是的陈述句。如果命题是真, 我们说它的真值为真，如果命题是假, 我们说它的真值是假。

例如以下的陈述句都是命题，因为它们不是真就是假：

（1）The sum of the numbers 3 and 5 equals 8.  
    （2）Jane reacted violently to Jack’s accusations.  
    （3）Every even natural number >2 is the sum of two prime numbers.  
    （4）John owes James two pounds.  
    （5）All eggs which are not square are round.             

这个我们有几个约定：

①对于那些非陈述句的语句，不在我们的考虑范围内。

例如：下述都不是命题:

(a)             x+y＞4                       (c)   真好啊!  
    (b)             x=3                          (d)  你去哪里?             

 (a)和(b)是断言，但不是命题, 因为它的真值取决于x和y的值。  (c)和(d)都不是陈述句, 所以不是命题。

②我们主要考虑涉及计算机系统或计算机程序的精确命题，我们不仅要确切说明这些命题，而且要检验一个给定的程序或系统是否按现有的规范（工程设计书）运行。为此，我们需要设计推理演算。从直觉上说，如果所有的前提是正确的，那么我们推出的结论也是正确的。

给定任一个关于计算机程序的真实性质，在我们的推理演算中是否能找到一个论证，使得该论证的结论就是那个真实性质？这是一个难解问题。比如上述例子中命题3中的情况那样（哥德巴赫猜想）。

我们下面要设计的逻辑是符号化的。我们将所有英语命题构成的某个足够大的子集转化成一系列的符号串。这样做使我们仅关注论证形式。其重要意义是：由于计算机系统或软件的工程设计书都是这样的命题序列。这样做使得对这些工程设计书的自动化处理成为可能。

那么怎么做呢？将某些命题作为原子命题或不可分命题。例如，“6 是偶数”是一个原子命题。对于每个原子命题，用一个不同符号来记它，这些符号可以是：p, q, r, … 或 p1, p2, p3, … 。对于复合命题，我们把它们表示成这些原子命题的组合。比如：

例3  
p:  I won the lottery last week.  
q:  I purchased a lottery ticket.  
r:  I won last week’s sweepstakes.            

为了表示更复杂的命题，我们需要引入表示联结词的符号。最常用的联结词及用于表示它们的符号如下：

非p  ﹁p   p的否定             

 I did not win the lottery last week.

It is not true that I won the lottery last week.  

p或q     p∨q     p与q的析取  
p与q     p∧q       p与q的合取  
如果p那么q       p→q  p与q间的蕴含，q是p的逻辑结果。p是p→q 的前提（假设），q是它的结论。           

 以上每个联结词可以作为规则，利用这些联结词可以构造更为复杂的命题。

比如：

p∧q → ﹁r∨q

这样表示也许存在模糊。在计算机处理时可能要求加上括号。即 (p∧q) → (﹁r∨q)

为此，对于上述联结符约定邦定的优先级：

 ﹁ 优先于∨和∧， ∨和∧优先于→。

 →是右结合的。

很熟悉是不是，仿佛回到了遥远的高中。

这一节比较简单，下一节我们说自然演算。