# 命題邏輯 首先我們用一個簡單的邏輯系統來介紹一些必要的符號。"$\displaystyle A:=B$"代表$\displaystyle A$是$\displaystyle B$這一連串符號的代稱(我們稱為**符號定義**)。 在這個簡單的系統裡，**關注於敘述之間的推理關係，不去煩惱敘述的構成細節**。如此一來我們稱這個邏輯系統為**命題邏輯**(Propositional calculus)。我們用英文大寫字母$\displaystyle A_1, A_2, A_3$來代表一段基本敘述，稱為**敘述字母**(statement letter)，並可以下標數碼來進一步分辨。(事實上就是承認**自然數**先於邏輯而存在)。 我們姑且先**假設每段敘述都有真假之分**，其中$\top$代表真；和$\bot$代表假。 ## 否定 在邏輯上最簡單的概念就是**否定**(negation)了，否定一段敘述字母$\displaystyle A$我們用$\neg A$代表。我們用一個表稱為**真值表**(truth table)描述它在邏輯上的真假狀況。真值表的意思是，"如果$\displaystyle A$是假的，那否定$\displaystyle A$的敘述是真的"。 | $\displaystyle A$ | $\neg A$ | | -------- | -------- | | $\top$ | $\bot$ | $\bot$ | $\top$ ## 實質條件 日常對話裡常常會說，"開了電視才會看到新聞"；或是"加熱夠久以後水會沸騰"。但沒看電視一樣可以上網看新聞；就算沒有加熱，只要外界壓力夠低，低溫也有可能有沸騰的現象。以敘述字母代表敘述的話，上面兩個範例都是$A$是真的話會得到$\displaystyle B$為真，但$\displaystyle A$為假的情況下$\displaystyle B$可為真也可為假。這個邏輯的關係被稱為**實質條件**(material conditional )，以真值表表示就是： | $\displaystyle A$ | $\displaystyle B$ |$A\Rightarrow B$ | -------- | -------- | -------- | | $\top$ | $\top$ | $\top$ | $\bot$ |$\bot$ | $\top$ | $\top$ | $\bot$ | $\bot$ | $\bot$ | $\top$ | $\top$ 一般日常所說的因果關係，會額外要求如果$\displaystyle B$為真的話，那$\displaystyle A$就要為真。這正對應著我們下面會提到的**實質雙條件**。 ## 且和或 我們可以直觀的從真值表定義下面兩個邏輯連接詞： |$\displaystyle A$ | $\displaystyle B$ | $A\wedge B$ | -------- | -------- | -------- | | $\top$ | $\top$ | $\top$ | $\bot$ | $\bot$ | $\bot$ | $\top$ | $\bot$ | $\bot$ | $\bot$ | $\top$ | $\bot$ | $\displaystyle A$ | $\displaystyle B$ | $A\vee B$ | -------- | -------- | -------- | | $\top$ | $\top$ | $\top$ | $\bot$ | $\bot$ | $\bot$ | $\top$ | $\bot$ | $\top$ | $\bot$ | $\top$ | $\top$ $A\wedge B$就是所謂的**且**，也可以形式的定義為**不可能$\displaystyle A$是對的情況下推出$\displaystyle B$是錯的**，也就是 $A\wedge B:=\neg( A\Rightarrow \neg B)$ 另一方面，**或**($A\vee B$)也可以形式的定義為**若$\displaystyle A$是錯的則$\displaystyle B$是對的**，也就是 $A\vee B:=\neg A\Rightarrow B$ 讀者可以自行畫出真值表，證明這個形式定義跟真值表一致。 ## 實質雙條件 我們很直觀的把$\displaystyle A$跟$\displaystyle B$間的**實質雙條件**(material biconditional)定義為$\displaystyle A$可以推出$\displaystyle B$且$\displaystyle B$可以推出$\displaystyle A$，也就是 $A \Leftrightarrow B:= (A\Rightarrow B)\wedge(B\Rightarrow A)$ 以真值表表示就是 |$\displaystyle A$ | $\displaystyle B$ | $A\Leftrightarrow B$ | -------- | -------- | -------- | | $\top$ | $\top$ | $\top$ | $\bot$ | $\bot$ | $\top$ | $\top$ | $\bot$ | $\bot$ | $\bot$ | $\top$ | $\bot$ ## 合式公式 跟一般的語言一樣，數學敘述有一定的文法規則才能清楚表達。這樣在一套數學理論裡符合文法規則的敘述稱為**合式公式**(well-formed formulas)，簡寫為$\displaystyle wf$。在命題邏輯裡我們用以下的文法規則規定甚麼是一段合式公式： :::success $\displaystyle (1)$敘述字母是$\displaystyle wf$。 $\displaystyle (2)$如果$\mathcal{A},\mathcal{B}$是$\displaystyle wf$，則$\neg\mathcal{A},\,\mathcal{A}\Rightarrow \mathcal{B}$也都是 $\displaystyle wf$。而$\neg,\Rightarrow$被稱為命題連接詞(propositional connectives) $\displaystyle (3)wf$只能透過上面兩個規則建構出來。 ::: 記住我們第二條文法規則可以這麼簡單，是因為其他的命題連結詞可以用否定跟實質條件組合出來。我們習慣用草寫的大寫英文字母去表達合式公式。 就像一般的語言一樣，符合文法規則讓人聽得懂的話，是有真有假的，合式公式也是有真有假。不管組成的它的敘述字母的真假怎麼取，一段合式公式如果都是真的稱為**恆等式**(tautology)，反之都是假的合式公式則稱為**矛盾**(contradiction)。例如對敘述字母$\displaystyle A$ $A\Rightarrow A$ 就是恆等式；而 $A\wedge(\neg A)$ 就是矛盾。 對於合式公式的恆等式，我們有以下最直觀，但重要的modus ponens律，簡稱MP律： :::success **元定理(MP律)**： 若$\mathcal{A}$, $\mathcal{A}\Rightarrow\mathcal{B}$兩個都是恆等式，則$\mathcal{B}$也是恆等式。 ::: 這個"元定理"以後抽象化以後，將在命題邏輯的形式理論裡被當成**唯一的推理規則**。 事實上我們還可以從合式公式去稍稍推廣邏輯推理的觀念；回憶一下我們一開始就假設組成合式公式的敘述字母都是有真有假，它們的真假可以決定合式公式的真假，所以**如果每個讓$\mathcal{A}$為真的真假組合，都會讓$\mathcal{B}$是真的話**，我們稱**$\mathcal{A}$在邏輯上推出$\mathcal{B}$**($\mathcal{A}$logically implies $\mathcal{B}$) 。讀者可以自己簡單證明，**$\mathcal{A}$在邏輯上推出$\mathcal{B}$等價於$\mathcal{A}\Rightarrow\mathcal{B}$是恆等式**。 另外我們說**$\mathcal{A}$在邏輯上等價於$\mathcal{B}$**($\mathcal{A}$is logically equivalent to $\mathcal{B}$)，如果**任何的敘述字母的真假組合，都會讓兩者同為真或是同為假**，一樣可以證明**$\mathcal{A}$在邏輯上等價於$\mathcal{B}$當且僅僅當$\mathcal{A}\Leftrightarrow\mathcal{B}$是恆等式。 ## 括弧規則 為了讓合式公式的書寫更加便捷，我們做以下的規定： :::success (1)從左方開始判斷。 (2)括弧內的命題連接詞是最優先施用的。 (3)作用於同個敘述字母(或是以括弧包起來的$\displaystyle wf$)的命題連接詞，我們依照$\neg,\,\wedge,\,\vee,\,\Rightarrow,\,\Leftrightarrow$的順序施用。 ex. $\neg A\wedge B$的完整表示法是$(\neg A)\wedge B$。 $A\wedge (D\Rightarrow E)\vee (\neg C)$的完整表示法是$[A\wedge (D\Rightarrow E)]\vee (\neg C)$ (4)以上規則都無法判別施用順序的話，以最靠近左端的命題連接詞為先施用。 ::: ## 取代 事實上判別一段合式公式真假值的時候，不用每次都以敘述字母為基礎去判定，我們有以下兩個"元定理"(metatheorem)描述命題邏輯取代的性質 :::success **元定理**： 如果合式公式$\mathcal{T}$是恆等式，內含的敘述字母是$\displaystyle A_1,A_2,....,A_n$。如果取一組合式公式$\mathcal{A}_1,\mathcal{A}_2,....,\mathcal{A}_n$去依序取代$\displaystyle A_1,A_2,....,A_n$，得到新的合式公式$\mathcal{T}'$，則$\mathcal{T}'$也會是恆等式。 ::: :::success **元定理**： 合式公式$\mathcal{T}_A$裡內含合式公式$\mathcal{A}$，設合式公式$\mathcal{T}_B$是把$\mathcal{T}_A$裡內含的$\mathcal{A}$都取代成$\mathcal{B}$而生成的。那麼$[(\mathcal{A}\Leftrightarrow\mathcal{B})\Rightarrow(\mathcal{T}_A\Leftrightarrow\mathcal{T}_B)]$是恆等式。 ::: (此元定理可以推論出如果$\mathcal{A},\mathcal{B}$在邏輯上等價，則$\mathcal{T}_A,\mathcal{T}_B$在邏輯上也是等價的。) 以上兩個元定理都可以透過命題連結詞的定義去簡單證明，在此不贅述。但這兩個定理在我們建立抽象的邏輯理論時，會占有很重要的基石地位。 ## 真值函數 在進入形式的邏輯理論之前，我們岔題一下，去討論一個在電腦的設計上很有用的結果。 想抽象一點，我們可以把前面所介紹的命題連接詞當成一種"神奇的黑箱"，只要給它敘述字母的真假值，就會給你邏輯關係是真是假的結果。更抽象的來說，我們可以把命題連接詞當成一種"對應"，每一組敘述字母的真假值都對到唯一的一個真假值，就像每個商品都有自己的價格一樣。事實上這就是數學上**函數**的概念。 思考一下，我們定義"函數"的時候，是要指定是哪一群東西(一堆商品)被對應到哪一群東西(代表價格的數字們)。這個"一群"的概念在數學上對應著**集合**的概念；也就是我們要能區分每一個個體(每個商品從外觀都很容易的區分)，而且還要有一個準則去劃分它們是哪個群體的(商品的意思是，在商店裡可以用錢交換而得到的任何物體)。但有些龜毛的數學家發現，有些劃分群體的準則會造成自相矛盾的結果，像著名的**羅素悖論**。所以我們想要討論"集合"這個觀念的話，我們必須小心翼翼地羅列出劃分群體需要遵守的規則，也就是**集合論的公理**。但小心翼翼討論這些公理所需要的邏輯規則，我們還沒完全學完。所以在這裡討論"真值函數"，也就是剛剛提到的**敘述字母的真假值跟邏輯關係真假的對應關係**，要採用一種半直觀的方法討論，等到有一個正式的**公理化集合論**，就可以輕鬆地把這些直觀的觀念嚴謹化。 回憶一下我們用實質條件跟否定，就可以形式的定義"且"和"或"。那一般來說，一個內含敘述字母$\displaystyle A_1,A_2,....,A_n$的任意合式公式$\mathcal{T}$，它的真值函數$f_{\mathcal{T}}$如果用真值表表示成下面這個樣子： | $\displaystyle A_1$ | $\displaystyle A_2$ | .... | $\displaystyle A_n$ |$\mathcal{T}$ | -------- | -------- | -------- | -------- | -------- | | $\top$ | $\top$ | .... | $\top$ | $f_{\mathcal{T}}(\top,\top,....,\top)$ | $\bot$ | $\bot$ | .... | $\bot$ | $f_{\mathcal{T}}(\bot,\bot,....,\bot)$ | $\cdot$ | $\cdot$ | .... | $\cdot$ | $\cdot$ | $\cdot$ | $\cdot$ | .... | $\cdot$ | $\cdot$ | $\cdot$ | $\cdot$ | .... | $\cdot$ | $\cdot$ | $\cdot$ | $\cdot$ | .... | $\cdot$ | $\cdot$ $f_{\mathcal{T}}(\top,\top,....,\top)$的意思只是照函數$f_{\mathcal{T}}$的規則下，"輸入"$\top,\top,....,\top$所得到的對應值。那它能不能被命題連接詞組合出來呢? 如果真值表的第$\displaystyle i$列($i\le 2^n$)的真值函數值為真；為了要湊出$\top$，我們在這列取$\bot$值的敘述字母前面加$\neg$，然後跟其他敘述字母用"$\wedge$"接起來，寫清楚就是 $\mathcal{C}_i:=(\bigwedge_{A_k=\top}A_k)\wedge[\bigwedge_{A_j=\bot}(\neg A_j)]$ 我們偷懶的用大寫的"$\wedge$"符號代表連續用"且"連接而成的合式公式，大寫的"$\wedge$"下面說明被連接的$\displaystyle A_k$們需要滿足甚麼條件，而不用麻煩的列舉他們；同樣的偷懶寫法對"$\vee$"也適用。那麼這樣定義的合式公式$\mathcal{C}_i$在第$\displaystyle i$列一定為真；另一方面只要稍稍跟這列的真假值組合不同，就會導致$\mathcal{C}_i$為假。把這些取函數值為真的列所生成的$\mathcal{C}_i$用"或"連接起來，就是我們尋找的$\mathcal{T}$一般表達式。說清楚一點，以$\displaystyle f_i$代表第$\displaystyle i$列的真值函數值，那麼 $\mathcal{T}\Leftrightarrow(\bigvee_{f_i=\top}\mathcal{C}_i)$ 是恆等式，也就是兩者在邏輯上等價。因為"或"只要一者為真結果就為真；但另一方面為，函數值為假的某列，它的真假值組合代進任意的$\mathcal{C}_i$都必然為假，而且假用"或"連結起來還是假的，所以這條合式公式的確重現$\mathcal{T}$真值表的狀況；一方面也證明了任意的真值函數可以用$\neg,\wedge,\vee$三者構造出來。 那麼更進一步的，有沒有一個"雙元"的命題連接詞(也就是像"或"一樣吃兩個"輸入值")，可以構造出所有的真值函數呢?這個問題的重要性在於，電腦是基於二進位演算的"黑箱子"；我們可以把$\top$當成$\displaystyle 1$；$\bot$當成$\displaystyle 0$，由此可以把電腦所有的功能拆成真值函數，如果能確定真值函數可以用更少的命題連接詞構成，那用**電晶體**去組合出邏輯電路的時候，可以依據一定的運算規則減少需要使用的電晶體數量。 如果一個"雙元"命題連接詞可以配出所有的真值函數，第一個要配的就是$\neg$；唯一配的方法就是重複輸入同一個敘述字母的真假值來構造。假設這個命題連接詞用符號"$\star$"代表，那 |$\displaystyle A$ | $\displaystyle B$ | $A\star B$ | -------- | -------- | -------- | | $\top$ | $\top$ | $\bot$ | $\bot$ | $\bot$ | $\top$ | $\top$ | $\bot$ | $\displaystyle ?$ | $\bot$ | $\top$ | $\displaystyle ?$ 要完全決定這個命題連接詞，只剩下真值組合不相等的兩個部分；如果把兩個$\displaystyle ?$取為相異值，可以發現不是$(A\star B)$邏輯上等價於$(\neg A)$；不然就是$(A\star B)$邏輯上等價於$(\neg B)$。但依照我們上面的討論，$\neg$是不足以構築出所有真值函數的；故兩個$\displaystyle ?$只能取相同值。 如果取的是$\top$的話，我們稱為**NAND**或是**謝費爾豎線**(Sheffer stroke)，以"$\mid$"代表 | $A$ | $B$ | $A\mid B$ | -------- | -------- | -------- | | $\top$ | $\top$ | $\bot$ | $\bot$ | $\bot$ | $\top$ | $\top$ | $\bot$ | $\top$ | $\bot$ | $\top$ | $\top$ 事實上它就是 $\neg(A\wedge B)$ 這就是它的名子"NAND"的來源。然後注意到，$(A\vee B)$邏輯上等價於$\neg(\neg A\wedge\neg B)$("或"就是不可能全部都是假的)，所以NAND的確可以構造出所有的真值函數。 如果取的是$\bot$，我們稱它為**NOR**，以$\downarrow$代表它 |$A$ | $B$ | $A\downarrow B$ | -------- | -------- | -------- | | $\top$ | $\top$ | $\bot$ | $\bot$ | $\bot$ | $\top$ | $\top$ | $\bot$ | $\bot$ | $\bot$ | $\top$ | $\bot$ 事實上它就是 $\neg(A\vee B)$ 然後讀者自己畫表驗證，$A\vee B$邏輯上等價於$[(\neg A)\downarrow(\neg B)]$，然後因為剛剛說過"且"可以用"或"跟否定拼湊出來，所以NOR也可以生成所有真值函數。更詳細有關於電腦跟邏輯的關聯，可以參閱**布林代數**、**數位邏輯**和**可計算性理論**。 我們在這裡提供一個網站，可以根據你寫出的合式公式計算真值表 https://www.erpelstolz.at/gateway/formular-uk-zentral.html
Last changed by  
 
Cheng David
1202

Read more

一階邏輯

簡介 不同於命題邏輯，自一階邏輯，我們開始關心一段敘述如何組成。 從一般語言敘述的構成來看，如果我們不照慣例，而把所有的東西都說得清清楚楚的話，照理來說一段敘述應該是 "主詞+動詞+受詞"、"主詞+動詞"、"主詞+動詞謂語+修飾詞"的主要架構，配上動詞、主詞和受詞的修飾語或修飾子句構成的。但數學關心的，只是一個對象有怎麼樣的狀態，則另一個對象會有怎樣的狀態，也就是"主詞+動詞謂語+修飾詞"的架構配上推理的關係。描述狀態不外乎辨識特徵，事實上跟定義"集合"的本質，也就是辨別一個群體的共通性做的事是一樣的。 一段敘述都有它敘述的對象；比如說「業界(有人)對這個產品有興趣」、「(所有)外國旅客入境前都要防疫隔離」；邏輯學上，"有人"(更一般的說存在一個人)跟"所有人"(注意到所有外國旅客是不是本國籍且身在我國的所有人的略語)這兩個表述敘述對象範圍的詞語被稱為量詞(quantifier)。顯然外國的旅客不只一個，這就是需要在語意上說明描述範圍的變數(variable)，也就是每個變數都有它的取值範圍。(外國旅客是從所有人類裡取值，找有外國國籍且身在我國的人類) 數理邏輯上，"所有的變數$\displaystyle x$的取值滿足合式公式$\mathcal{A}$"以$(\forall x)\mathcal{A}$代表；類似的"存在變數$\displaystyle x$的取值滿足合式公式$\mathcal{A}$"以$(\exists x)\mathcal{A}$代表，其實也就是$\neg(\forall x)(\neg\mathcal{A})$。類似的，$(\forall x)\mathcal{A}$就是$\neg(\exists x)(\neg\mathcal{A})$。 要構成一段敘述，我們還需要其他要素；比如說"這個產品"就是一個常數(constant)；有興趣代表著一種人和產品之間的關係；類似的，外國旅客的"定義"是來自國家和入境旅客的國籍隸屬"關係"。在邏輯學上我們用謂詞符號(predicate letter)去形式的表示"關係"。

5/19/2023
希爾伯特空間

粗略來說，希爾伯特空間是裝配了內積和"收斂性"的複線性空間，增加了"無窮但可數"基底的存在可能性。 本條目的數學用語請參考線性空間、拓撲空間和距離空間。 基本定義 內積空間 複線性空間$\displaystyle H$，裝配$g:H^2\to\mathbb{C}$（$\displaystyle g(x,y)$簡寫為$\langle x,y\rangle$） 滿足 :::success (1)$(\forall x\in H)(\forall y\in H)(\langle x,y\rangle=\overline{\langle x,y\rangle})$ (內積沒有交換律，對調為共軛複數)

5/1/2023
常用的邏輯定理

用語說明 前提假設以Hyp簡記 推論元定理以"D"簡記。 由推論元定理可以知道$\vdash\mathcal{A}\Rightarrow\mathcal{B}$和$\mathcal{A}\vdash\mathcal{B}$是一樣的意思。所以證明過程中，你會看到代號D跟中途運用定理的代號寫在一起的簡記法，因為我們有時候會用$\mathcal{A}\vdash\mathcal{B}$的形式表達定理。 另外有兩個常用的推論，是來自於推論元定理 :::success $\displaystyle (D1)$$\mathcal{A}\Rightarrow\mathcal{B},\mathcal{B}\Rightarrow\mathcal{C}\vdash\mathcal{A}\Rightarrow\mathcal{C}$

7/8/2022
形式理論

元邏輯 研究一個邏輯系統，好比一個語言學家研究英文的文法跟規則，他需要其他語言來當一個客觀的參照，避免陷入自己解釋自己的矛盾循環中。我們要研究的邏輯語言稱為目標語言(object language)，研究邏輯系統時，用來客觀參照目標語言的語言稱為元語言(metalanguage)，元語言的邏輯也會稱為元邏輯(metalogic)。而在元邏輯下，推出目標語言的有關性質特稱為元定理(metatheorem)。 事實上我們採用的元語言只是比較有條理的中文，配上一些邏輯符號: :::success (1)$\displaystyle \to$：實質條件意義下的推理 (2)$\ulcorner$, $\urcorner$：引用一段目標語言的敘述 :"「他是醫生」這句話是肯定句"，和"他是醫生"有使用上的差別，元語言的引號就跟前者代表引用這句話並做語言學的說明是一樣的，但後者是單純的使用這句話。

11/1/2021
Read more from Cheng David
Published on HackMD