數理邏輯之 命題

數理邏輯的一項重要任務是回答“什麼是證明？” 并試圖将“證明”這一概念（與之相關有可計算性概念）精确化。基于這個目的，數理邏輯需要設計适當的語言用于對計算機科學領域中遇到的情景模組化，以便于對它們作形式推理，得到我們想要的結論。

為了将證明精确化，所用的方法是什麼呢？數理邏輯在研究推理時要建立數學模型（我們稱這個數學模型為形式系統）ß對形式系統進行研究，必須用普通的自然語言（元語言）ß研究推理時不可避免要用到邏輯ß邏輯是由演算組成的ß在進行推理時需要用到精确的演算規則ß推理過程中所使用的語言必須無二義性，以便于構造有效的推理論證。

在計算機應用中，這就要求我們構造的論證必須是有效的且能在計算機上執行。是以，為了達到這樣的目的，通常的方法是引進一種符号語言，它能夠精确表達其意義。

先來看第一個例子：

例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)

為此，對于上述聯結符約定邦定的優先級：

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

 →是右結合的。

很熟悉是不是，仿佛回到了遙遠的高中。

這一節比較簡單，下一節我們說自然演算。