命題邏輯

命題邏輯是邏輯學的一個分支。 它也稱為命題演算、句子演算、句子邏輯，有時也稱為零階邏輯。它涉及命題和命題之間的關係，包括基於它們的論證的構建。複合命題是透過邏輯連線詞連線命題而形成的。不包含邏輯連線詞的命題稱為原子命題。 與一階邏輯不同，命題邏輯不處理非邏輯物件、以及關於它們的謂詞或量詞。然而，命題邏輯的所有機制都包含在一階邏輯和高階邏輯中。從這個意義上說，命題邏輯是一階邏輯和高階邏輯的基礎。在邏輯和數學裡， 命題邏輯是一個形式系統, 有可以由以邏輯運算子結合原子命題來構成代表「命題」的公式，以及允許某些公式建構成「定理」的一套形式「證明規則」。術語.一般地說，演算是一個形式系統，包括一套語法表示式和一套定義了特定的二元關係的形式規則，這個二元關係可解釋為表示式空間上的邏輯等價關係。若形式系統會作為一個邏輯系統，其表示式會被解釋成數學陳述，且其規則，被稱之為「推理規則」，則一般會是保真的。在此設定下，規則可以被用來，從給定為真的陳述的公式中，推匯出表示真的陳述的公式來。公理的集合可能為空集、非空有限集、可數無限集或由公理模式所給定。形式文法遞迴地定義了語言的表示式和合式公式。之外，有時也可以給定一個語義，用以定義真值和賦值。命題運算的語言包括：一套運算子號，被稱之為「邏輯運算子」。一個合式公式是任一原子公式，或任一以運算子號依文法規則由原子公式建立起的公式。在下文中我們描述一種標準命題演算。很多不同的公式系統存在，它們都或多或少等價但在下列方面不同：採用了哪些推理規則。命題演算的一般描述.命題演算是一個形式系統formula_1，它的公式按如下方式構造：formula_7。在此一劃分中，formula_8是指元數為formula_9的運算元符號所構成的集合。在更熟知的命題演算中，formula_5一般被劃分如下：formula_11formula_12。一種常用的做法是把常數邏輯值當作一種零元運算元，即：formula_13。有些作者會用 ~ 來替代 ¬，也有的用 &amp; 或 formula_14 來取替 formula_15。邏輯值所構成的集合也有許多不同的符號表示，如 {假,真} 、{F,T} 或 {0,1} 來取替 {formula_16,formula_17}，這些都常見於各個論著之中。依據所使用的精確形式文法或文法形式化，可能需要以左括號""作語法上的輔助，用來完成公式的構造。formula_3的語言，亦稱之為「公式」或「合式公式」的集合，可由如下規則集合被歸納或遞迴地定義：透過重複應用這三個規則，可以建構出複雜的公式來。例如：示例 1 簡單的公理系統.設formula_29，這裡的formula_30定義如下：formula_32。功能齊全的套裝 邏輯運算子的Ω如下。採用否定和薀涵做為命題演算的兩個基本運算，相當於把omega集formula_34劃分如下：formula_35。formula_36。* formula_38* formula_39* formula_40示例 2 自然演繹系統.設formula_42，這裡的formula_30定義如下：formula_32。formula_35。formula_48。在此命題演算的例子中，轉換規則被解釋為所謂的「自然演繹系統」下之推理規則。這裡表述的特定系統沒有起始點，這意味著它對邏輯應用的解釋是從空公理集合中推匯出其定理的。此命題演算有十個推理規則。這些規則允許我們從給定的一組假定為真的公式中推匯出其他為真的公式。前九個只是簡單地指我們可以從其他合式公式推論出特定的合式公式。但是最後一個規則使用了假言假設作為推匯出的公式集合的一部分，來檢視我們是否能推匯出一個特定的其他公式。因為前九個規則不是這樣而通常被描述為“非假言”規則，而最後一個則被稱為“假言”規則。證明的例子.以下推導將用編號後的行的列表來表示，在每行之上有一個單一的公式和一個理由。論證的各個前提會在列表的首行給出。結論將在最後一行。一個推導稱為完備的，若所有行都是透過正確的應用一個規則而從前面的行得出的。下面是證明的一個例子：要證明：formula_51證明：formula_52可解釋為“假定A，推匯出A”。formula_53為“不假定任何東西，推匯出A蘊涵A”，或者“A蘊涵A是重言式”，或者“A蘊涵A是永真的”。規則的可靠性和完備性.以上規則的關鍵特性是它們是可靠的和完備的。非形式的說，這意味著規則都是正確的並且不再需要其他規則。這些要求可以如下這樣正式的提出。我們定義真值指派為把命題變數對映到真或假的函式。非形式的，這種真值指派可以被理解為對事件的可能狀態的描述，在這裡特定的陳述是真而其他為假。公式的語義因而可以被形式化，透過定義哪些"事件狀態"是設定為真的。我們透過如下規則定義這種真值指派A在什麼時候滿足特定公式：透過這個定義，我們現在可以形式化公式φ被特定公式集合S蘊涵的意義。非形式的，就是在使給定公式集合S成立的所有可能情況下公式φ也成立。這引申出下面的形式化定義：我們說公式集合S 語義蘊涵特定的公式φ，條件是滿足在S中的公式的所有真值指派也滿足φ。最後我們定義語法蘊涵，φ被S語法蘊涵，當且僅當我們可以在有限步驟內使用我們提出的上述推理規則推匯出它。這允許我們精確的公式化推理規則的可靠性和完備性的意思：上述的兩個例子都滿足可靠性和完備性。可靠性證明的梗概.符號約定：設G是命題集合。設φ、ψ和χ是命題。我們把“G語法蘊涵φ”寫成“G證明φ”，還有把“G語義蘊涵φ”寫成“G蘊涵φ”。我們要展示：(∀φ)(∀G)(如果G證明φ，則G蘊涵φ)我們注意到“G證明φ”有一個歸納定義，這給予我們直接的辦法來驗證“如果G證明φ，則……”形式的斷言。所以我們的證明是用歸納法進行的。假定對於任意的G和φ，如果G在n或更少的步數能證明φ，則G蘊涵φ。對於在第n+1步時，根據推理規則，由G及其n步以內證明的命題，可以推匯出新的命題。驗證：對於任意的這樣的新命題ψ，G蘊涵ψ。需要注意的是，對於自然演繹系統，基礎步驟II可以省略，因為它們根本沒有公理。基本上，基礎步驟II是要展示每個公理都是邏輯真理。基礎步驟證實了對於任何G，來自G的最簡單的可證明的語句都被G所蘊涵。一般的，歸納步驟的證明會較長，但不過是對所有推論規則按例分析，去展示每個規則都能“保持”語義蘊涵。透過可證明性的定義，除了G的成員、公理、或從規則推匯出的命題之外，沒有別的命題是可證明的；而這些命題都是語義上被蘊涵的，所以演繹演算是可靠的。完備性證明的梗概.我們採用同上面一樣的符號約定。我們要展示：如果G蘊涵φ，則G證明φ。我們透過反證法來進行：我們轉而展示如果G不證明φ，則G不蘊涵φ。G0=G。如果Gk ∪ {Ek+1}證明φ，則Gk+1=Gk。如果Gk ∪ {Ek+1}不證明φ，則Gk+1=Gk ∪ {Ek+1}。；；公理化演算.下面定義的命題演算透過公理的方式定義了多數邏輯運算元的語法並且它只使用一個推理規則。它也叫做標準命題演算。公理.設φ、χ和ψ表示合式公式。。公理有公理THEN-2可以被看作是“蘊涵關於蘊涵的分配律”。公理AND-1和AND-2對應於“合取除去”。在AND-1和AND-2之間的關係反映了合取運算元的交換律。公理AND-3對應於“合取介入”。公理OR-1和OR-2對應於“析取介入”。在OR-1和OR-2之間的關係反映了析取運算元的交換律。公理NOT-1對應於反證法。公理NOT-2說明了“從矛盾中可以推匯出任何東西”。公理NOT-3叫做排中律並反映了命題公式的語義求值：公式的真值要麼是真要麼是假。至少在經典邏輯中，沒有第三個真值。直覺邏輯不接受公理NOT-3。推理規則.推理規則是肯定前件：如果還使用雙箭頭的等價運算元的話，則要增加如下"自然"推理規則：元推理規則.設一個推導被表示為相繼式，各個假設在十字轉門的左側，而結論在十字轉門的右側。則演繹定理可以被陳述如下：如果相繼式formula_57已經被證明了，則也有可能證明相繼式formula_58。這個演繹定理自身沒有公式化為命題演算：它不是命題演算的定理，而是關於命題演算的一個定理。在這個意義上，它是元定理，相當於關於命題演算可靠性和完備性的定理。在另一方面，DT對於簡化語法上的證明過程是如此的有用以至於它看作和用做推理規則，同肯定前件一起使用。在這個意義上，DT對應於自然條件證明推理規則，它是在本條目中提出的第二個例子的命題演算的一部分。DT的逆定理也是有效的：如果相繼式formula_58已經被證明了，則也有可能證明相繼式formula_57實際上，DT的逆定理的有效性相對於DT而言是平凡的：如果formula_61則1：formula_622：formula_63並且可以演繹自3：formula_64透過肯定前件的方式，Q.E.D.DT的逆命題有著強有力的蘊涵：它可以用來把公理轉換成推理規則。例如，公理AND-1formula_65可以透過演繹定理的逆定理的方式被轉換成推理規則formula_66這是合取除去，是前面給出的自然演繹命題演算中使用的十個推理規則中的一個。證明的例子.下面是證明的一個例子，只涉及到公理THEN-1和THEN-2：要證明：A → A。證明：1.(A → ((B → A)→ A)) →((A → (B → A)) →(A → A))公理THEN-2透過φ = A, χ = B → A, ψ = A2. A →((B → A)→ A)公理THEN-1透過φ = A, χ = B → A3.(A → (B → A)) →(A → A)得自透過肯定前件。4. A →(B → A)公理THEN-1透過φ = A, χ = B5. A → A得自透過肯定前件。等價於等式邏輯.前面的公理化命題演算是希爾伯特風格演繹系統的一個例子。在這種命題系統中公理是用邏輯連結詞構建的項，而唯一的推理規則是肯定前件。等式邏輯在高等學校的抽象代數教學中被作為正式的標準，它是不同於希爾伯特系統的一類不同的演算。它的定理是等式而它的推理規則表達出等號的性質，也就是在容許代換的項上的相等關係。上述的經典命題演算等價於布林代數，而直覺命題演算等價於海廷代數。等價性是透過在兩個方向上轉換各自系統的定理來證明的。經典命題演算或直覺命題演算的定理Φ被分別轉換為布林代數或Heyting代數的等式Φ = 1。反過來布林代數或Heyting代數的定理x = y被分別轉換為定理經典名義演算或直覺命題演算的定理(x → y)∧(y → x)，它的標準簡寫是x ≡ y。在布林代數的情況下，x = y還可以被轉換為(x∧y)∨(¬x∧¬y)，但在直覺命題演算的情況下中不能這麼轉換。在布林代數和Heyting代數中，可以使用不等式x ≤ y代替等式。等式x = y可以被表達為一對不等式x ≤ y和y ≤ x。反過來不等式x ≤ y可被表達為等式x∧y = x或x∨y = y。不等式的重要性在於它對應於希爾伯特系統的演繹或蘊涵符號formula_67。蘊涵formula_68被轉換為代數框架下的不等式formula_69反過來代數不等式x ≤ y被轉換為蘊涵formula_70在實質條件右側，要麼不蘊涵之。同代數邏輯之間類似但更加複雜的相互轉換，對於自然演繹系統和相繼式演算也是可能的。後者的轉換可以被釋義為二值的，但是更有洞察力的釋義是作為集合，它的元素可以被理解為由範疇的態射組成的抽象證明。在這種釋義下相繼式演算的切規則對應於範疇的複合。其他邏輯演算.命題演算大概是在所有當前使用的邏輯演算中最簡單的一種。。它可以按很多方式來擴充套件。最直接的方式是開發一個更加複雜的邏輯演算，介入對所用於的句子的更精細的細節敏感的規則。在命題邏輯中的原子句子被分解成、變數、謂詞和量詞的時候，它們就生成了一階邏輯，或者叫做一階謂詞邏輯，它保留命題邏輯的所有規則並增加了一些新規則。。透過一階邏輯的工具，有可能公式化一些理論，要麼帶有顯式的公理要麼透過推理規則，而把它們自身當作邏輯演算。算術是其中最周知的理論；其他的還包括集合論和分體論。模態邏輯也提供了一種推理的變體，它不能在命題演算中捕獲。例如，從“必然地p”我們可以推出p。從p我們可以推出“可能地p”。多值邏輯是允許句子有除了“真”和“假”之外的值的邏輯。。這些邏輯經常要求與命題邏輯非常不同的運算裝置。