命題邏輯及其形式化系統的侷限

命題邏輯（Propositional Logic）這個概念來自於西方現代數學領域，作為 ... 也正是數理邏輯應用於實際，特別是應用於電腦科學推動了其自身的發展。

命題邏輯及其形式化系統的侷限 首頁 最新 HTML CSS JavaScript jQuery Python3 Python2 Java C C++ Go SQL 首頁 最新 Search 命題邏輯及其形式化系統的侷限 2019-02-02254 前言： 命題邏輯（Propositional Logic）這個概念來自於西方現代數學領域，作為人類理性智慧對世界本質探索的第一次重大飛躍，對人類整個現代文明的推進起到了極其重要的作用。

命題邏輯系統中所反映出來的基本思想，對我們來說卻從不陌生。

公元前6世紀，古希臘出現了一大批從事“智慧”職業的人們，後世的人們普遍稱呼這些前輩為哲學家，學者，辯論者等等。

而同時期，在中古也處於一個極其相似的歷史階段。

在中國同樣出現了一批從事“智慧”職業的人，我們將他們統稱為諸子百家。

這些人有一些共同的特點，他們通過自己的觀察和獨立的思考，對整個世界的執行方式和各種現象進行了高度的抽象和概括。

所有這些先賢們抽象出來的規律，奠定了現代邏輯學的思想基礎。

公元前6世紀，古希臘克里特島人埃匹門尼德（Epimenides）說過一句著名的話： 所有的克里特島人都說謊。

這就是著名的說謊者悖論。

隨後這個說謊者悖論產生了各種其他形式，這種邏輯的遊戲甚至成為了很多詭辯者的尚方寶劍。

律師，政客，辯論家，甚至是很多的學者，在這樣的背景下將這個工具打磨的愈加的完善。

漸漸的隨著知識的積累，作為整個人類的大文明體系，對這種思想的本質也越發的看的清楚。

而被看清楚不光是這種工具的力量，更有這種思想工具的侷限性。

正文： 在數理邏輯中，命題邏輯被定義為一種由邏輯運算子結合原子命題構成代表“命題”的公式，以及允許某些公式構成“定理”的形式化系統。

接下來對命題邏輯的討論不考慮命題本身內部的構造，單純將整個命題邏輯體系抽象為一種形式化的系統，所有的運算和證明都只在命題邏輯體系的基礎上引申，不涉及更細節的解剖。

命題邏輯系統的形式化 以形式系統的角度來看，命題邏輯由以下的因素構成： 1. 邏輯運算子：﹁ ∧ ∨ → ↔ ( ) 2. 原子命題：即不包含其他命題作為其組成部分的命題。

3. 推理規則：這裡取較為通用的是個推理規則作為整個系統的規則基礎。

因為本質上在命題邏輯的系統下可以構建無數條永真式命題，這裡只取其中較為基礎的一部分。

a）雙重否定：﹁﹁P=P b）結合律: (P∨Q)∨R=P∨(Q∨R), (P∧Q)∧R=P∧(Q∧R), (P↔Q)↔R=P↔(Q↔R), (P→Q)→R ≠ P→(Q→R) c）交換律： P∧Q=Q∧P P∨Q=Q∨P P↔Q=Q↔P P→Q↔Q→P d）分配律 e）等冪律 f）吸收律 g）德摩根律 h）同一律 i）零律 ... 以上的三個部分構成了命題邏輯的整個體系系統。

從形式上看，對於任何一個以原子命題為運算最小元的邏輯運算，都可以通過以上的邏輯符號和邏輯規則的作用下，轉化成一定的形式，並最終獲得一定的結果。

可以想象最早總結出這些邏輯規則的邏輯學家內心是怎樣的心情。

世界上所有的問題都可以通過一定程度的抽象，轉換成一種邏輯形式的運算，如果可以製造出一種計算的機器，人們只需要把問題輸入進去就能根據這些特定的規則得到一定的結果。

後來的電腦科學的出現和這些邏輯學家的成果有著極其密切的關係。

當然，命題邏輯系統本身並沒有強大到可以完全支撐起這一切。

連線詞 ∧、 ∨、﹁同構成計算機的與門，或門和非閘電路，從而命題邏輯是計算機硬體電路的表示、分析和設計的重要工具。

也正是數理邏輯應用於實際，特別是應用於電腦科學推動了其自身的發展。

命題邏輯系統完備性的證明 在命題邏輯系統內，有﹁ ∧ ∨ → ↔ 這些不同的邏輯運算子（其中左括號“（”，右括號“）”在邏輯演算中起到的作用類似於控制運算的優先順序，當然在特定的規則表示方法下，可以消除，這裡不做深入討論），但是在實際的邏輯運算中可以通過一定的規則和帶入，可以消除一部分符號，因此，存在只使用其中的一部分符號就可以表示命題邏輯體系內所有命題的情形，即具有完備性。

下面我將嘗試證明兩個命題的真偽，來進一步討論，命題邏輯系統的完備性。

當然實際的情況下還需要考慮命題是合式公式的嚴格限定，但在此處不做深入討論，即預設所有命題都是符合條件的合式公式。

命題一 {﹁、∧}和{﹁、∨}都是完備的。

證明： 假定  {﹁、∧}和{﹁、∨}  是完備系統 則有 在命題邏輯系統中所有的命題，僅使用{﹁、∧}/{﹁、∨}  即可完全表示 這裡先以{﹁、∧}為例， 令複合命題G包含命題邏輯所有的邏輯運算子﹁ ∧ ∨ → ↔ 1. P左↔Q右部分 在邏輯運算的過程中“↔”左右布林型別保持一致，這裡轉換成“=”，拆分為兩部分命題的兩部分分別證明布林值相等即可。

反覆使用該規則到所有↔消去。

2. P左→Q右部分 在邏輯運算中，此處需要利用一條恆等式規則，P→Q=﹁P∨Q(該恆等式的證明不困難，構造真值表即可得)可以將命題中所有的P左→Q右部分，轉換成P左∧Q右的形式。

反覆使用改規則到所有→符號消去。

3.  P左∨Q右部分 此處又需要藉助另一恆等式，根據著名的德摩根律有﹁(P∨Q)=﹁P∧﹁ Q，根據此規則，所有P左∨Q右部分可轉換成﹁（﹁P左∧﹁Q右部分）的形式，反覆使用該規則，到所有∨消去。

至此，命題邏輯中{∨、→、↔}全部都消去，即複合命題G在{﹁、∧}下完備。

又命題G包含了所有命題邏輯運算的符號， 因此對於所有命題{﹁、∨}是完備的。

同理可以證明{﹁、∨}是完備的。

（同樣使用析取式的德摩根律即可） 命題二  {→、∧}是不完備的。

證明： 如果要證明{→、∧}不完備，只需在該符號體系下構建一個不能僅使用該符號體系表達的命題即可。

令一命題G包含﹁符號，在該符號體系內，﹁符號無法轉換成任意一種形式。

而包含﹁符號的命題一定存在，因此{→、∧}系統不完備。

命題二得證。

注：同樣的，利用反證法，還可以證明{﹁、∧、∨、↔}也是不完備的。

命題邏輯系統在描述自然語言邏輯系統方面的侷限 在實際的邏輯系統中還存在一些特殊的情況，無法在命題邏輯的系統下進行有效的表示。

在命題邏輯系統出現之後，很快就有人發現了這些問題的地方，並嘗試對命題邏輯體系進行完善和修補。

這些工作的結果產生了很多邏輯的細分方向，多值邏輯，模態邏輯，不確定和非單調邏輯等。

接下來，通過一些簡單的例子對命題邏輯體系的侷限性進行進一步的說明。

例如：命題P表示所有的同學考試都及格了。

命題Q表示肯定有同學考試及格了。

在這個例子裡面，如果用命題邏輯的系統表示，是兩個不同的命題，分別是命題P、Q。

但是深入這個命題內部，我們會發現一個重要的資訊：這兩個命題表示的發生的事件都是“考試及格”這個動作，唯一不同的地方是一個是“所有同學”都發生了這個動作，另一個是“肯定有同學”即一部分同學發生了這個動作。

在邏輯命題系統下，如果只看命題的形式化後的符號，無法精確的判斷出這兩個命題之間還有這樣的關係。

也就是說，在命題邏輯系統下，這兩個命題包含的邏輯資訊發生了丟失。

這兩個命題其實表達的都是“**考試及格了”這一動作，僅僅是發生動作主體的範圍有所不同。

再例如：說謊者悖論所表述的命題，在正常的常識思維下，這樣的命題只會推匯出矛盾，因而不會存在這樣的怪物存在。

但是，在命題邏輯的系統下，最小的邏輯運算單元是原子命題。

所有這樣在常識上不正常的怪物，在命題邏輯的系統下，都生存的很好。

隨著現代數學的發展，這些邏輯悖論會繼續以一種新的形式進化，然後推動著體系的進一步完善。

其實，一直到現在為止，這一過程仍然在進行當中，現代數理邏輯體系當中依然存在著各種形式的悖論怪物。

而這些怪物才是推動現代數學進一步發展的真正原動力，也同時作為異端提醒著人類，我們的理性和智慧有極限，如何突破這些極限決定著整個人類文明下一步的發展。

參考資料： 《邏輯學是什麼》陳波 北京大學出版社 2002 《離散數學教程》 耿素雲 屈婉玲 王捍貧 北京大學出版社 2002 《數理邏輯與集合論》 石純一 王家廞 清華大學出版社 《數理邏輯》（美）Herbert. B. Enderton 譯者沈復興 陳磊 孫運傳2006 相關文章 命題邏輯及其形式化系統的侷限 淺析邏輯代數、命題邏輯、一階邏輯、高階邏輯和數理邏輯 102411命題邏輯 一階邏輯及其到KripkeStructure的轉換 命題邏輯--主析取主合取正規化 離散數學複習--第一章：命題邏輯 文字及其格式化 神奇語言pythonwhile語句邏輯運算格式化 AutoML詳解及其在推薦系統中的應用、優缺點 H.264的技術優勢及其在H.323系統中的應用 linux核心啟動流程（涉及到根檔案系統的問題） 回車符和換行符及其在不同系統上的區別 奇異值分解SVD簡介及其在推薦系統中的簡單應用 Don’tTest,Verify.|哪個故事真正符合你對形式化驗證的想象？ 三、3：django的請求生命週期以及圖書管理系統作業 分類導航 HTML/CSS HTML教程 HTML5教程 CSS教程 CSS3教程 JavaScript JavaScript教程 jQuery教程 Node.js教程 服務端 Python教程 Python3教程 Linux教程 Docker教程 Ruby教程 Java教程 JSP教程 C教程 C++教程 Perl教程 Go教程 PHP教程 正則表達式 資料庫 SQL教程 MySQL教程 PostgreSQL教程 SQLite教程 MongoDB教程 Redis教程 Memcached教程 行動端 IOS教程 Swift教程 Advertisement 三度辭典 Copyright©2016-2021IT閱讀  Itread01.comAllRightsReserved. 0.001291036605835