※ 引述《MathTurtle (恩典)》之銘言： : 我來補充一下好了。 : ※ 引述《cmlrdg (心之語)》之銘言： : Mendelson這本是本經典的好書, : 不過真的要讀完它也不是很容易, : 加油 ^^ 感謝MathTurtle大的補充 ^_^ 小弟才疏學淺, 是邏輯學入門新手 謝謝您點出我想法上的一些漏洞 :) : : ^^^^^^^^^^^^^^^ ^^^^^^^^^^^^ : : 是的... : : 簡單來說, 他的公理有A1, A2, 和A3三種型式 : : 每一個型式都有(可數)無限多個邏輯句子. : : 你可以發現若將上述的A, B, C看成Boolean variables, : : 則A1, A2, A3都是tautologies, 因此被列為axioms. : : 其他tautologies都可以藉由這些axioms透過inference rules(如modus ponens) : : 來"證明." : 用 tautology來說明axiom是什麼, 可以幫助理解, : 不過還是必須小心: : (1) tautology 本身並不是一個很清楚的概念 (except in something like TLP) : 而且多半預設了 true in all models 之類的 semantic notions. 我對於邏輯的認知 絕大多數來自於C. H. Papadimitriou的書 因此也採用了不少他的說法 :) 在這裡 我所謂的tautology 意思是指在truth table當中 truth value恆為true的句子 而句子當中的變數(至少就"形式"上而言)都是boolean 因此 在探討first-order logic的logical axioms(有別於 nonlogical axioms, 稍後說明:))時 他這本書裡提到有以下三種型式 (不多贅述) 1) "形式"上是boolean的tautology (例如 (for all x, x < y) => (for all x, x < y) "形式"上為p => p 為tautology. p這個"形式"上的boolean變數用來代表(for all x, x < y) 這個first-order句子) 2) 等號的關係 (例如 x = y => f(x) = f(y), 其中f是unary function symbol) 3) quantifiers (例如 (for all x ψ) => ψ) 而true in all models的句子 在Papadimitriou的書裡 叫做valid expression (我發現Papadimitriou的名詞跟其他作者所採用的似乎有些不同 XD 例如在first-order裡他不用interpretation這個名詞, 而一律用model 有別於其他書採用這兩個名詞並且意思不同) : (2) axioms 如你所言, 是透過infernece rules可以推導出這理論中的所有定理 : 的一些命題。這裡純粹是syntactic notions. : (3) 為何設定 A1 A2 A3這三個命題為axiom, 嚴格說並不是因為它們是tautology, : 而是因為這三條配合此系統的推論規則可以推導出所有的定理。 真的是非常感謝MathTurtle大 <(_ _)> 我忽略掉很重要的一點: 之所以把他列為axiom, 不光是他是tautology(或valid expression) 而是這幾個句子形成一個complete axioms set 也就是所有這個系統的tautologies都可以利用這個set裡的句子搭配 inference rules而證明出來 (我印象中在H. Enderton的書裡有看到 propostional logic是完全的axiomatizable 也就是存在有complete axioms set...不過我不太確定^^" 或許可以請MathTurtle大解說一下:P) 不過predicate logic就沒那麼幸運了 XD (K. Godel說predicate logic有些句子是valid卻不能證) : : 值得一提的是: : : 這個系統探討的邏輯句子應該只有Boolean logic而已, : : 跟real number system的axioms不太相同, : : (real number system的某些axioms寫成Boolean型態並非tautologies, : : 因此這些axioms更像是人規定的...XD) : : 邏輯句子也不同, : : 不過意義是一樣的. : : (都是作為證明之前的基本事實...也就是規定是對的, 不需要證明) : 應該這麼說, 一般設定實數系統包含了PA (Peano Arithmetics), : 而PA又包含了述詞邏輯系統(predicate logic), 再包含了命題邏輯系統, : 因此命題邏輯系統通常是被其它系統「預設」。 : 不過選哪些命題作為公理, 通常是看你的系統有哪些primitives, : 然後選一些足夠推導出所有定理的最小集合為公理。 : 這其實沒有什麼原因, 像是自然演譯法中, 你可以完全沒有公理。 : 而這裡的這三條, 主要是因為這個系統把 material implication 與 negation : 當成惟一的兩個primitives. : 實數系統當然需要多一些公理, 畢竟它有更多的primitives, : 像是大小就是最重要的一個要去characterise的東西。 : 我們不太能說實數系統的公理不是tautologies, : 如果你tautology 指的是necessary truth的話, : 實數系統裡的命題也都是necessary truth. : 當然如果你的tautology指的是true in all models, : 你當然可以construct 非實數系統的model使其公理為假, : 但這似乎不是證明這些不是tautology。 如同前面所描述的 true in all models的句子 若探討的是propostional logic時, 的的確確就是tautology; 若探討的是predicate logic時, 稱作valid expression. 而這些句子當中有些被列為(logical) axioms 也就是前述的那三種來源 在Papadimitriou的書裡, 把前述的三種axioms 稱為logical axioms 的原因在於 他們是"true in all models" 在任何model、任何theories (例如number theory, graph theory, group theory, etc.) 都成立 有別於logical axioms, Papadimitriou在他書中提到每個特定的theory (如 number theory) 都有專屬於自己的axioms, 這些稱為nonlogical axioms (nonlogical翻譯成中文的意思是"非"邏輯的; illogical翻譯成中文是 "不合"邏輯的...有差 XD) 這些就不是"true in all models"了 以Papadimitriou的說法來看 MathTurtle大所提到的PA 當中的數學歸納法公理應該就是nonlogical axiom了 (PA其他的axioms我就不清楚了, 跟PA不熟...XD) 原po說的關於實數系的axioms set 是logical axioms set和nonlogical axioms set的union 最後, 藉由這個話題 我來講一下我讀Papadimitriou的心得XD 在predicate logic裡(嚴格來說是first-order logic) Godel's incompleteness theorem說明的是 在number theory當中 沒有一個enumerable axioms set足以完全"捕捉"到整數的性質 或者說沒有一個enumerable axioms set可以過濾掉其他的models 只剩下我們想要的那一個 (給了一個(enumerable) axioms set, 可以滿足的models似乎可以有很多個 彼此之間的差異是沒有辦法用這些axioms來加以區別的) 不知道各位的看法如何? 有錯歡迎指正! 謝謝^^ 再一次感謝MathTurtle大的補充 讓我了解了更多:) : : 這個版上之前有人討論過, 你可以按z進入查一下 : : 大致上來說, well-formed formulas是用recursive方式定義: : : 1) Boolean variable (如p)是wff : : 2) 若p和q都是wffs, 則 p and q, p or q, not p都是wffs : : 上述所說是Boolean logic的wffs. : : 因此像 (p and q) => p 是一個wff. : : 希望有解決你的問題^^ : : 各位板大有錯請指正<(_ _)> : 如果要了解什麼是 wff, : 或許也要舉個不是wff 的例子, 下面三個都不是: : 1. p xxx q not : 2. p q ( not : 3. (p and q) and r) -- 我是新手@@, 感謝各位的指教 <(_ _)> --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 211.74.96.226