命題演算

命題演算

命題演算是命題邏輯的公理化,任務是使用演算手段來討論命題邏輯,有自然演算和公理演算兩種方式。公理演算是給出公理,根據確定的推理規則推導出一系列重言式;自然演算不給出公理,利用一系列推理規則推出定理。

命題和邏輯連線詞

命題分為兩類,一類是不能再分解為更簡單命題的命題,這種命題稱為簡單命題;另一類是可以分解為更簡單命題的命題,這種命題稱為複合命題。

在命題演算中,用符號A、B、C…或A,A,B,B,…等等表示簡單命題。當命題A取值“真”時,又稱A具有值T(True),當命題A取值“假”時,又稱A具有值F(False),T和F稱為命題常數。為了方便也可將T記為1,將F記為0。現在引入邏輯連線詞,並通過它們從簡單命題 “構造”複合命題.

若A、B是命題,首先引入5種基本的邏輯連線詞:

(1)¬:否定詞,¬A讀為 “非A”,表示對命題A的否定,即和命題A對立的命題。當命題A取值為0時,¬A取值為1;反之,當命題A取值為1時,¬A取值為0.

(2)∧:合取詞,A∧B讀為“A並且B”。若且唯若命題A和B都取值為1時,命題A∧B才取值1,否則取值0。

(3)V:析取詞,AVB讀為“A或者B”。若且唯若命題A和B都取值0時,命題AVB才取值0,否則取值1。

(4)→:蘊涵詞,A→B讀為“若A則B”,若且唯若命題A是真命題,並且命題B是假命題時,A→B才是假命題。在命題A→B中,A稱為前件,B稱為後件.

(5)~:等值詞,A~B讀為“A等值於B”,或“A和B等值”,若且唯若命題A和B同時是真命題或同時是假命題時,A~B才是真命題。

合式公式

能成為命題的式子稱為合式公式,簡記為wff。

定義1

(1)一個命題變元是wff。

(2)若P是一個wff,則¬P是一個wff。

(3)若P和Qwff,則(P∧Q)、(PVQ)、(P→Q)和(P~Q)都是wff。

(4)wff只限於有限次使用(1)、(2)、(3)所得到的符號串.

這個定義實際上是由兩部分組成的,第一部分是(1)、(2)、(3)條,它們是wff的形成規則,其中的第一條無連線詞,直接生成wff;第二條和第三條是對已有的wff進行連線,構成新的wff。根據(1)、(2)、(3),下面的式子都是wff:¬(PVQ),¬(P∧Q),(P→(Q→R)),(((P→Q)∧(Q→R))~(P→R))。

但前三條只說明了什麼樣的符號串是wff,而沒有說明什麼樣的符號串不是wff,為了指明這一點,(4)是必要的。

定義2

如果A和B都是wff,B是A的一部分,則稱B是A的部分合式公式或子公式,部分合式公式簡記為wfp。

在一個wff中,每一個邏輯連線詞都有其相應的作用範圍,稱為這一範圍為該連線詞的轄區,轄區的具體規定如下:

如果¬B是wffA的wfp,則B稱為緊靠在它左方的否定詞在A中的轄區。

如果(B→C)是wffA的wfp,則B和C稱為(B→C)中→的轄區,B是它的左轄區,C是它的右轄區。

真值表、永真式

在對一個wff中的所有命題變元都作了代入後,就得到一個命題,進行不同的代入,所得到的各個命題,其真假值可能是不同的。對於一個合式公式,計算它在不同的代入下的取值,可以通過真值表來進行。所謂真值表,即將一個wff的每個命題變元在各種真值指派下的取值的情形列成的表。

定義1:對於一個wff的命題變元無論作何指派,所得到的值永為T,即命題永遠是真命題,則稱該Wf為永真公式或重言式,並稱它是有效的。

定義2 :對於一個wff的命題變元無論作何指派,所得到的值永為F,即命題永遠是假命題,則稱該wff為永假公式或不可滿足公式。

定義3: 不是永真公式的wff稱為非永真公式,不是永假公式的wff稱為可滿足公式.

定義4: 若P和Q是wff,A,A,…,A是出現在P、Q中的命題變元,當給A,A,…,A以任一組真值指派時,P和Q的取值都相同,則稱合式公式P和合式公式Q等價,記為P<=>Q。

命題演算中的等價關係

用真值表來判定一個wff的取值情形,可以看到當wff中具有兩個變元時,對變元的真值指派有2 種不同情形;有三個變元時,有2 種不同情形。一般情況下,當wff中有雙個不同變元時,各種真值指派的組合是2 種,即真值表中有2 行需要計算,這樣增長的計算量是相當大的,因此我們可以將一個給定的wff化簡,即找出和它等價的、但比較簡單的wff,從而使求值的工作簡化。下面所給出的是一些常用的等價關係:

1.等冪律 P∨P<=>P; P∧P<=>P.

2.交換律 P∨Q<=>QVP;P∧Q<=>Q∧P.

3.結合律 (P∨Q)∨R<=>P∨(QVR);(P∧Q)∧R<=>P∧(Q∧R).

4.分配律 P∨(Q∧R)<=>(P∨Q)∧(P∨R); P∧(Q∨R)二(P∧Q)∨(P∧R).

5.吸收律 P∨(P∧Q)<=>P; P∧(P∨Q<=>P.

6.德.摩根律¬(P∨Q)<=>¬P∧¬Q;¬(P∧Q)<=>¬P∨¬Q.

7.同一律 P∨F<=>P; P∧T<=>P.

8.零律 P∧F<=>F; P∨T<=>T.

9.否定律 P∨¬P<=>T; P∧¬P<=>F.

10.雙否定律¬¬P<=>P.

相關詞條

相關搜尋

熱門詞條

聯絡我們