命題演算是命題邏輯的公理化，任務是使用演算手段來討論命題邏輯，有自然演算和公理演算兩種方式。公理演算是給出公理，根據確定的推理規則推導出一系列重言式；自然演算不給出公理，利用一系列推理規則推出定理。
基本介紹
- 中文名：命題演算
- 外文名：Propositional calculus
- 演算方式：自然演算和公理演算
命題和邏輯連線詞,合式公式,真值表、永真式,命題演算中的等價關係,
命題和邏輯連線詞
命題分為兩類，一類是不能再分解為更簡單命題的命題，這種命題稱為簡單命題；另一類是可以分解為更簡單命題的命題，這種命題稱為複合命題。
在命題演算中，用符號A、B、C…或A1，A2，B1，B2，…等等表示簡單命題。當命題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，A1，A2，…，An是出現在P、Q中的命題變元，當給A1，A2，…，An以任一組真值指派時，P和Q的取值都相同，則稱合式公式P和合式公式Q等價，記為P<=>Q。
命題演算中的等價關係
用真值表來判定一個wff的取值情形，可以看到當wff中具有兩個變元時，對變元的真值指派有22種不同情形；有三個變元時，有23種不同情形。一般情況下，當wff中有雙個不同變元時，各種真值指派的組合是2n種，即真值表中有2n行需要計算，這樣增長的計算量是相當大的，因此我們可以將一個給定的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.
