語法和語義
研究命題邏輯需要使用公式表示複合命題的形式,並反映複合命題的邏輯特徵,組成這種公式的一組符號和規定怎樣由符號構成公式的一組規則,合在一起便構成一個人工符號語言。當把符號和公式看作是沒有意義的具體對象,只研究公式之間的關係時,這種研究稱為語法的;當對符號和公式予以解釋,例如把一部分符號解釋為命題聯結詞,把某些符號解釋成取真假二值為值的變元,並在這種解釋下研究公式的意義時,便稱這種研究為語義的。命題邏輯在描述和研究符號語言、即對象語言時,還要使用另一種語言,即元語言。元語言通常由某種自然語言並加上若干專門符號構成。關於整個命題邏輯系統的性質和系統特徵的研究,稱為元邏輯的研究。由元邏輯研究得到的關於整個邏輯系統的定理稱為元定理。命題形式
用特定的語詞把命題連線起來可以構成複合命題;從中起連線作用的語詞稱為命題聯結詞;構成複合命題的命題稱為支命題,支命題本身也可以是複合命題。命題邏輯研究複合命題的邏輯形式、推理形式和公理系統。傳統邏輯關於假言推理、選言推理和二難推理等的理論,都屬於命題邏輯的範圍。複合命題的形式可以公式明晰地表示。在經典命題邏輯里,這種公式通常由以下 3種符號組成:①表示任意命題的命題變元,它們是 p,q,r,p1 ,q1 ,...;②5個基本的命題聯結詞,即塡、∧、∨、→、凮;③用來顯示公式的結構層次的括弧(,)。5個基本的命題聯結詞依次稱為否定詞、合取詞、析取詞、蘊涵詞和等值詞;在漢語中,它們通常分別用語詞"並非"、"並且"、"或者(可兼的)"、"如果...則"以及"若且唯若"表達,在這5個聯結詞中,否定詞屬一元聯結詞,其餘 4個都是連線兩個命題以構成複合命題,稱為二元聯結詞。複合命題的形式都可以用這3類符號構成的公式表示。如塡p表示否定命題的形式,p∧q、p∨q、p→q、p凮q,分別依次表示合取、析取、蘊涵和等值命題的形式。它們是和 5個基本的聯結詞相應的5個基本的複合命題形式。命題聯結詞的解釋和真值函項
經典命題邏輯把命題看成或者真的或者假的,認為複合命題的真假可唯一地由其支命題的真假決定。命題的真和假叫做命題的真值。命題變元是取真值(真或假)為值的變元,也就是以真值組成的集合為變域的變元。聯結詞是施於命題以形成命題的運算元,特別是從命題的真值得出命題真值的運算元。命題形式是一種真值函項,即以真值集為變元的定義域,並以真值集為值域的函項。這種真值函項可以用真值表定義。5個基本命題形式的真值表為:這個真值表規定了其中聯結詞的意義。其中的1代表真,0代表假。從表中可以看出這 5個基本命題形式的值怎樣由其中變元的值決定。例如,最左邊的表表示,塡p 的值由p的值決定,當p的值為 1時,塡p的值為0;當p的值為0時,塡p的值為1。這也就是對塡的解釋。 聯結詞可以相互定義,例如,∨可用塡和→定義,即把p∨q定義為塡p→q。事實上,所有聯結詞都可以用某些基本聯結詞定義出來。例如,所有聯結詞都可以歸結到塡和→,或者塡和∧,或者塡和∨。常真式
常真式或稱重言式是經典命題邏輯的一個公式,稱為常真的。如果其中的命題變元不論賦予真值1或0,該公式的值常為 1;如果對命題變元的每一組真值賦值一公式的值常為 0,此公式便稱為常假式或矛盾式。命題邏輯的公式可以分為常真的、常假的、以及對命題變元的某些組賦值取值1而對其它賦值取值0的公式3種類型。常真式表達著命題邏輯的定律(規律),具有特殊的意義。例如p∨塡p、p∧(p→q)→q,都是常真式。前者表示排中律,後者是表示肯定前件假言推理的推理形式的公式。一個公式是不是常真的,可以用真值表方法確定,即由依據 5個基本命題形式的真值表所逐步構造出的真值表確定。下表可以說明怎樣用真值表確定一個公式的真值,確定一個公式是否常真。表中最後一橫行圈內的數碼錶示逐步求值的次序,縱列⑦是要確定其是否常真的公式的真值,因其全部是1,從而表明該公式常真,是一常真式。我們用元語言符號A 、B等表示任一公式,用喺A表示A是一常真式。還用A喺B表示對於A和B中出現的命題變元的每一組賦值,當A的值為1時,B的值必定也是1。喺與公理系統所用到的儱不同,前者是語義符號,而後者是語法方面的符號,它表示在系統中可以證明。按照常真式的定義,顯然有:一公式 A常真,若且唯若它的否定塡A常假。 公理系統 經典命題邏輯的常真式為數無窮,它們在一定意義上都表達邏輯定律。為了系統地研究和掌握這些邏輯定律,需要對它們作整體的考慮,將全部常真式都包括在一個系統之中。為此,可用公理方法將命題邏輯的全部定律系統化,從而得到一種形式系統,即稱為命題演算的公理系統。在一個形式系統中,其語法部分,包括作為出發點的初始符號、形成規則、公理和變形規則。以下陳述的是經20世紀波蘭邏輯學家J.盧卡西維茨簡化過的弗雷格的系統。該系統的初始符號為:①邏輯常項,即命題聯結詞,用塡、→表示;②命題變元,以p、q、r、p1 、p2 ,...表示;③括弧,即(,)。該系統的形成規則,在於規定怎樣組合起來的有窮長的符號序列是系統中的合式公式。這個系統的形成規則有 4條:①單獨一個命題變元x 是一合式公式; ②如果符號序列X是合式公式,則塡X是合式公式;③如果符號序列X,Y是合式公式,則(X→Y)是合式公式。④只有適合以上 3條的是合式公式。這個系統的公理共有 3條,即:
① 儱p →(q →p);
② 儱(p →(q →r))→((p→q)→(p →r));
③ 儱(塡p →塡q)→(q →p)。
變形規則也稱推理規則。變形規則有兩條:①代入規則是將一公式 A中出現的命題變元π處處代以公式 B,得到公式, 稱為代入,以"如果儱A,則儱"表示。②分離規則為"如果儱A→B並且儱A,則儱B"。
命題聯結詞∧、∨和凮可以通過定義引入,把
(A∧B)定義為塡(A→塡B);
(A∨B)定義為(塡A→B);
(A凮B)定義為(A→B)∧(B→A)。
在上述規則、定義中出現的符號 x,X,Y,A,B等,是元語言符號。x表示任意命題變元;X, Y 表示任意的符號序列;A,B表示任一合式公式;儱是語法符號,表示緊跟在儱後面的公式是系統中的定理。
公式的有窮序列 A1,A2,...,An稱為是一個證明,如果其中每一Ai(i=1,2,...,n)或者是公理,或者由在先的一個公式套用規則R1而得,或者由在先的兩個公式套用規則R2而得。一個證明 A1,A1,...,An也說是它的最後一個公式An的證明。
一個公式B是系統中的定理,如果它有一個證明,即存在一個證明 A1,A1,...,An,而An即是 B。根據定理的定義,每一公理都是定理。一個公式是定理,若且唯若它是可證明的。
定理和可證明性都是語法概念。
這個系統的語義,即對符號和公式的解釋,就是前面對於命題聯結詞和公式所作的解釋,這個解釋稱為標準語義。此外還可作其他非標準的解釋。在標準解釋下,所有公理都是常真式,並且變形規則保持常真性,即把變形規則套用於常真公式而得到的公式也是常真式。由此表明,所有定理都是常真式, 也就是"如果儱A,則喺A"。這是關於這個演算系統的一個重要的元定理,稱為可靠性定理。它的另一個重要的元定理是完全性定理,即凡常真式都是定理,可表示為"如果儱A,則儱A"。該系統還有一個重要的性質,即:在這個系統中不可能同時證明一個公式A及其否定塡A。這個性質稱為一致性。自然推理系統 命題邏輯也可以用另一種形式實現系統化,即構造自然推理系統。自然推理系統是一種邏輯演算。它與公理系統相比,是在自然推理系統中,並不給出公理而只給出一組適當的初始推演規則。這些推演規則規定從什麼前提能推出什麼結論,或者規定在某個推理關係成立的條件下,另一個推理關係也成立。一個與簡化過的弗雷格公理系統相應的自然推理系統,它的初始符號和形成規則和前者相同。這個系統共有 5條初始推演規則:
① A1,A1,...,An儱Ai(i=1,2,...,n),肯定前提規則;
② г儱Δ儱A(Δ不空),演繹推理傳遞規則;
③ 如果г,塡A儱B,並且г,塡A儱塡B,則г儱A,否定詞消去規則,或稱反證律;
④A→B,A儱B,蘊涵詞消去規則;
⑤ 如果г,A儱B,則г儱A→B,蘊涵詞引入規則。
在這5條規則中,A、B表示任一公式,г、Δ表示公式序列,儱表示前提和結論之間的推理關係。規則②表示從г能推出Δ,而從Δ能推出 A,則從г能推出 A,表明推理關係是傳遞的。在這一自然推理系統中,聯結詞∧、∨和凮也可以通過定義引入,並且從初始推演規則導出關於∧、∨和凮的推演規則。該系統對每一常真公式A,都有儱A,也就是說,凡常真式,都能不需前提而用推演規則推出;並且,如果儱A成立,則A為常真式。這個自然推理系統與簡化過的弗雷格的系統有如下關係,即一個公式 A是公理系統中定理,在自然推理系統中就有儱A;反之,如果儱A成立,則A是公理系統中的定理。同時,這個自然推理系統也具有一致性、可靠性和完全性這幾個重要的元邏輯性質。