AI - Ch10 邏輯(3), 命題邏輯 propositional logic

命題邏輯 (propositional logic)
命題邏輯 (propositional logic) ，又稱語句邏輯 (sentential logic)，是最簡單的邏輯形式系統。學習邏輯者通常也以它為起點。其他較複雜的邏輯系統包括謂詞邏輯 (predicate logic)，模態邏輯 (modal logic)，及多值邏輯 (many-value logic) 等。

我們可視邏輯系統為一組規則，這組規則告訴我們如何以某些特殊符號建構出合乎邏輯語法的句子，及如何再從這些句子構造証明。構作邏輯系統必須清楚陳明三組規則：

1. 形式語言的語法規則：從形式語言中的詞匯構造合乎邏輯語法的句子，並分辨合文法及不合文法的符號串。這組規則與自然語言如中文及英語的文法規則很相似。
2. 形式語言的語意規則：提供對句子的語意解釋。這組規則告訴我們形式語言中句子的意義，以及在何種情形下句子為真或為假。
3. 構造証明的規則：從中得知從某些特定的初始假設可推導出什麼結論。

有些句子合乎文法，有些則否。例如，符號串「小丙最愛打架。」 與「哲學是一無聊的學科。」均屬合乎中文文法的句子。「愛打架小強最」與「學科無聊的是一哲學」則不然。




ㄧ、語法 (syntax)
任何語言由兩大部分構成，基本詞彙 (basic vocabulary) 與文法規則 (grammatical rules)。文法用來定義合法的邏輯符號：

• 邏輯連接詞：
• 「非」（¬）
• 「與」（∧）
• 「或」（∨）
• 「條件」（→）
• 「雙條件」（↔）
• 語句符號：$A$、$A_1$、$A_2$... $B$、$B_1$、$B_2$...（數量為可數、無限大）。
• 括號：$($ 和 $)$。

為了減少需要的括號的數量，有以下的優先規則：¬高於∧，∧高於∨，∨高於→。例如，P ∨ Q ∧ ¬ R → S是 (P ∨ (Q ∧ (¬ R)) → S的簡便寫法。

構作完構式 (Well-Formed Formulas)
現在讓我們將「語句邏輯的表達式」(SL 表達式) 界定為任何由一個或以上的命題邏輯詞彙構成的符號串。因此，下面的符號串皆為 SL 表達式：

• P
• ((P∨Q)&R)
• ((((PPR&→
• ((P→Q)&(R→S))
• P∨∨R)))))))))))))))→→V&QQ
• (((P↔Q)∨((R→S)&(S→T)))

並非任何 SL 表達式都合乎文法。合乎文法的SL表達式稱作「完構式」(Well-Formed Formulas, WFF)。完構式可根據以下的文法規則建構：

1. 任何語句字母皆為完構式。
2. 若 φ 為一完構式，則 ~φ 也為一完構式。
3. 若 φ 與 ψ 皆為完構式，則(φ&ψ)，(φ∨ψ)，(φ→ψ)，及 (φ↔ψ)為完構式。
4. 只有經由規則1-3產生的表達式才為完構式。

二、語意 (semantics)
語意學的基本概念就是解釋某個語言中的語詞及語句的意義。

• 單稱語詞(singular terms)：單稱語詞指涉對象就是其語意值。
• 通稱語詞(general terms)：通稱語詞的語意值就是具有該語詞描述的性質的對象形成的集合(即外延)。
• 真假值(truth-value)：語句的語意值則為真假值(truth-value)。

語意學中，我們需知道何謂句子或語句的真值 (truth-value)。許多句子有真假可言，稱作「陳述句」的句子之性質。通常以 'T(或1)' 與 'F(或0)' 來分別表示真假二值。

邏輯的一個主要目的是要提供一些系統的方法以判斷論証的對確性。真值表法 (truth-table method) 就為此方法之一種。原則上，任何命題邏輯的論證無論多複雜，應用此方法都能得知它是否為對。

命題邏輯中的語意學假設

• 二值原則 : 句子要不是真的就是假的，不能既真又假，也不能既不真也不假。這假設稱作「二值原則」。並非所有邏輯系統的語意論也依此假設，如模糊邏輯與多值邏輯。
• 真值函映原則 : 在古典邏輯中出現的語句連接詞均為真值函映的連接詞。也就是說，真值函映指的是「輸入」都有真假值，「輸出」也都有真假值，不能「輸入」有真假值，「輸出」沒有真假值，這目前不在這種邏輯系統討論。
• 外延原則 : 外延原則指的是所有公式都是由它的個別部分決定的。與語句內容本身的內容或意義無關。

語句連詞的基本真值表 (basic truth-table of sentential connectives)
連詞的意義彰顯在其聯系語句的功用，要理解連詞的意義我們必須知道包含它們的複合句在何時為真，何時為假。

命題邏輯中有五個連詞 ('~'，'&'，'∨'，'→'，'↔')。由這些連詞構成的複合句之真值完全由其組成句之真值決定。因此，得知個別組成句的真值我們也能得知整個複句的真值。具有此性質的語句連詞稱作「真值函項連詞」 (truth-functional connectives)。

邏輯狀態 (logical status)
真值表提供的訊息可讓我們得知任一WFF的邏輯狀態。命題邏輯的邏輯狀態通常被區分為三類：

1. 恆真句 (tautology) : 當一個WFF在其包含的語句字母的所有真值賦與下都為真，我們便稱它為「恆真句」。
2. 適然句 (contingent sentence) : 適然句即既非不一致又非恆真的WFF。換言之，若一WFF為適然句，那至少有一個真值賦與可令其真，也至少有一個真值賦與可令其假。例如，所有語句字母都屬適然句。某些複合句如 "(P&Q)" , "(P∨Q)" 亦如是。
3. 不一致句 (inconsistent/contradictory sentence) : 當一個完構式在其包含的語句字母的所有真值賦與下都為假，我們便稱它為「不一致句」。如果一個WFF不是不一致的，則它便是一致的。

其他的邏輯狀態的陳述 (此區名詞適用於其他的邏輯，如一階邏輯)：

• 有效性(valid) : 如果一個句子是有效的，則在每一個解釋之下皆為真。例如 : TRUE, ¬FALSE, (P∨¬P)。
• 可滿足的(satisfiable) : 如果一個句子是可滿足的，則存在某個解釋使其為真。例如 : TRUE, P, ¬P。
• 不可滿足的(unsatisfiable) : 如果一個句子是可滿足的，則在每一個解釋之下皆為假。例如 : ¬TRUE, FALSE, ¬(P∨¬P)。

[用心去感覺] tautologies 和 valid 的不同

簡單的說是 tautologies 是只用在命題邏輯恆真式，而 valid 是對所有邏輯恆真的通稱，兩個並非等價，詳細請看下面解說。

If the domain of the variable x is finite and determined then truth tables maintain the tautology = validity of propositional logic.

BUT! tautologies are those valid sentences whose validity turns on their propositional logic features. That is, tautologies are sentences that're logical truths, and the reason why any particular tautology is a logical truth is that its sentential connectives, and NOT its quantificational features, make it a logical truth.

Some examples: P v -P;  ∀xP(x)->P(a);

These are both logical truths because it's true that there is no interpretation of either sentence where it comes out false. But in the first case, that's due to features of "v" and "-" (specifically, the truth tables for these), and in the second case, it's due to OTHER clauses in the semantics : ones that aren't concerned with "v", "-", "->", or "&". Instead, the clauses that govern interpreting constants and universally quantified sentences make the second example a logical truth.

To illustrate this, do as has been done earlier in the thread, and translate "∀xP(x)-->P(a)" into sentential logic. Well, how do we go about that? First we identify the components. OK, we've got "∀xP(x)" and also "P(a)." Alright, now, since these aren't WFFs of sentential logic, we swap these for symbols that are. Since "∀xP(x)" and "P(a)" are different sentences, their SL analogues ought to be different. That is, we don't get a good SL translation of "∀xP(x)-->P(a)" with "P -->P". So we get "P --> Q" and this sentence has the very truth table that appears below. 

∀xP(x)   P(a)     ∀xP(x)→P(a)

T        T    T

F        T    T

T        F    F

F        F    T

Checking that confirms that "P-->Q" is not a tautology. Interestingly, there is a sentence that is logically true that is a substitution instance of "P --> Q": it's "∀xP(x)-->P(a)"! And the logical-truth-iness of this sentence doesn't turn on it's SL features, as above.

三、蘊涵 (Implication, entailment)
在命題邏輯和謂詞邏輯中用來描述在兩個句子或句子的集合之間的聯繫。

語義蘊涵

• 符號：$A \models B$，表示陳述句子集合A語義上蘊涵句子集合B。
• 定義：集合A蘊涵集合B，若且唯若在其中A中所有句子都為真的所有模型(model)中，在B中的所有句子也是真的。

如果對於公式X有$\varnothing \models X$則$X$被稱為「有效的(valid)」或是「重言式」。


邏輯蘊涵

• 符號：$A \vdash B$，陳述句子集合A邏輯蘊涵句子集合B。它可以讀作"B可以證明自A"。
• 定義：A邏輯蘊涵B，如果通過假定所有A中所有的句子並通過對它們應用一個有限序列的推理規則（比如來自命題演算的），你可以推導出B中的所有句子。

當然，這與特定的邏輯（證明演算）有關。在討論多個邏輯的情況下，在$\vdash$符號上放置下標是很有用的。


在語義和邏輯蘊涵之間的聯繫
理想上，語義蘊涵（semantic consequence）和邏輯蘊涵（syntactic consequence）等價，但這不總是可行。（參見哥德爾不完備定理，它陳述了包含為真但不能證明的句子的一些語言，比如算術）

在這種情況下，把等價分成兩部分是有用的：

• 完備性 (Completeness) : 演繹系統S對於語言L是完備的，若且唯若$A \models_L X \to A \vdash_S X$：就是說，所有有效的論證都是可證明的。
  If something really is true, the system is capable of proving it.
• 可靠性 (Soundness) : 演繹系統S對於語言L是可靠的，若且唯若$A \vdash_S X \to A \models_L X$：就是說，所有可證明的論證都是有效的，沒有無效的論證是可證明的。
  If the system (claims to) prove something is true, it really is true.

1. 完備且可靠的話，則總是可以得到答案且總是正確！
2. 可靠性與完備性互為逆命題。
3. 一些邏輯系統不擁有上述所有性質：比如庫爾特·哥德爾的哥德爾不完備定理證明了，沒有任何一個蘊涵皮亞諾公理的算術形式系統可以同時滿足相容性和完備性。同時他的針對沒有通過特定公理擴展為帶有等式的算術形式系統的一階謂詞邏輯的定理，證實了它們可以同時滿足相容性和完備性。

[補充] 邏輯蘊涵與實質蘊涵的聯繫：在很多情況下，蘊涵符合於實質蘊涵：就是說，$A, X \models Y$若且唯若$A \models X \to Y$。但是在一些多值邏輯中這不是真的。


[例題] inference and logic status
In each of the following,

• KB is a set of sentences, 
• {} is the empty set of sentences, 
• S is a single sentence. 

Recall that

• KB ╞ S is read “KB entails S” and means that S must be true whenever all the statements in KB are true, 
• KB ├ S is read “KB derives S” and means that S can be produced by applying the rules of inference to KB.

則各種陳述的配對如下：

1. Sound : KB ├ S 則 KB ╞ S
2. Unsound : KB ├ S 則 KB ╞ S 不一定成立
3. Complete : KB ╞ S 則 KB ├ S 
4. Incomplete : KB ╞ S 則 KB ├ S 不一定成立
5. Valid : S be given in advance.  {} ╞ S
6. Satisfied : S be given in advance.  for some KB_1, KB_1 ╞ S, but for some other KB_2, KB_2 ╞¬ S

References

思方網 : [H17] 簡單語句邏輯 (非常詳細，好文好站!)
http://philosophy.hku.hk/think/chi/formal.php

Wiki - 蘊含
http://zh.wikipedia.org/wiki/蕴涵

Wiki - 推理規則
http://zh.wikipedia.org/wiki/推理规则

Wiki - 歸結
http://zh.wikipedia.org/wiki/归结原理

Wiki - 完備性
https://zh.wikipedia.org/wiki/%E5%AE%8C%E5%A4%87%E6%80%A7

Wiki - 可靠性定理
https://zh.wikipedia.org/wiki/%E5%8F%AF%E9%9D%A0%E6%80%A7%E5%AE%9A%E7%90%86

交大胡毓志教授人工智慧講義