跳到內容

Reading note

Dirk van Dalen, Logic and Structure, ch. 1: Propositional Logic

我的邏輯學閱讀筆記。

洪偉的作者圖像
Author

洪偉

偉鐸資訊技術長、台大哲學博士候選人與哲學普及寫作者,長期投入 AI、公共議題與 TRPG。

Published: at 04:29 PM
編輯本頁下載圖卡

閱讀來源:Vandalen 2013

Table of contents

Open Table of contents

命題與連接詞

定義 1.1.1 命題邏輯的語言

命題邏輯的語言由下列符號組成:

  1. 命題符號:p0p_0, p1p_1, p2p_2, …,
  2. 連詞:∨\vee, ∧\wedge, →\rightarrow, ¬\neg, ↔\leftrightarrow, ⊥\bot,
  3. 輔助符號:((, ))。

定義 1.1.2 命題集合 PROPPROP

命題集合 PROPPROP 是符合下述性質的最小集合 XX:

  1. pi∈X(i∈N)p_i \in X(i \in N) 且 ⊥∈X\bot\in X,
  2. ϕ,ψ∈X⇒(ϕ∨ψ),(ϕ∧ψ),(ϕ→ψ),(ϕ↔ψ)∈X\phi,\psi \in X \Rightarrow (\phi\vee\psi), (\phi\wedge\psi), (\phi\rightarrow\psi), (\phi\leftrightarrow\psi) \in X,
  3. ϕ∈X⇒(¬ϕ)∈X\phi\in X\Rightarrow(\neg\phi)\in X。

註:

  1. pip_i 和 ⊥\bot 稱為原子命題(atomic proposition),構成的集合定義為 ATOMATOM。
  2. 「⇒\Rightarrow」是表達「若…則…」的後設邏輯語言,ϕ,ψ\phi, \psi 是表達集合成員的後設邏輯語言。
  3. 這裡「最小」的意義是集合的最小,即 PROPPROP 包含於所有滿足上述性質的集合。
  4. ⊥\bot 為集合中的邏輯常數(logic constant)。
  5. 輔助符號不可省略。
  6. 這三項性質定義了三種顯然排他的形式。

定理 1.1.3 歸納法原理

令 AA 是一個性質,若下述條件成立,則:若 ϕ∈PROP\phi \in PROP,A(ϕ)A(\phi) 成立。

  1. 對於任意 ii,A(pi)A(p_i),
  2. A(⊥)A(\bot),
  3. A(ϕ),A(ψ)⇒A((ϕ□ψ))A(\phi), A(\psi) \Rightarrow A((\phi \square \psi)),□∈{∨,∧,→,↔}\square \in \{ \vee, \wedge, \rightarrow, \leftrightarrow \},
  4. A(ϕ)⇒A((¬ϕ))A(\phi) \Rightarrow A((\neg \phi))。

證明:

  1. X={ϕ∈PROP∣A(ϕ)}X = \{ \phi \in PROP | A(\phi)\},X⊂PROPX \subset PROP。
  2. XX 滿足 1.2 的所有性質,因此 PROP⊂XPROP \subset X。

註:往後,當我們將 □\square 用於二元連接詞時,表示所有二元連接詞的統稱,不再另外說明。

定義 1.1.4 構成序列 formation sequence

序列 ⟨ϕi∣i≤n⟩\langle \phi_i | i \leq n \rangle 稱為 ϕ\phi(=ϕn= \phi_n)的構成序列,意思是,對於所有 ii,滿足:

  1. ϕi∈ATOM\phi_i \in ATOM,或
  2. ϕi=(ϕj□ϕk)\phi_i = (\phi_j \square \phi_k),j,k<ij,k<i,或
  3. ϕi=(¬ϕj)\phi_i = (\neg \phi_j),j<ij<i。

定理 1.1.5 構成序列與命題的充要條件

PROPPROP 是所有有構成序列的表達式的集合。

證明:以 1.3 歸納法原理證明這個集合滿足 1.2 定義的所有性質。

定理 1.1.6 遞迴定義 recursive definition

令 H□:A2→AH_\square: A^2 \rightarrow A、H¬:A→AH_\neg: A \rightarrow A、Hat:ATOM→AH_{at}: ATOM \rightarrow A,則存在滿足下述條件唯一的 F:PROP→AF: PROP \rightarrow A:

  1. F(ϕ)=Hat(ϕ)F(\phi) = H_{at}(\phi),對所有 ϕ∈ATOM\phi \in ATOM,
  2. F((ϕ□ψ))=H□(F(ϕ),F(ψ))F((\phi \square \psi)) = H_\square(F(\phi), F(\psi)),
  3. F((¬ϕ))=H¬(F(ϕ))F((\neg \phi)) = H_\neg(F(\phi))。

證明:

  1. 存在性證明:以 1.3 歸納法原理證明對於所有的命題 FF 都定義完善。
  2. 唯一性證明:以 1.3 歸納法原理證明,對於任一滿足上述條件的 G:PROP→AG: PROP \rightarrow A,則 G=FG = F。

例子:

語句的剖析樹(parsing tree)因此是合法且唯一的。

語句 ϕ\phi 的秩(rank) r(ϕ)r(\phi) 因此也是合法且唯一的:

  1. r(ϕ)=0r(\phi) = 0,若 ϕ∈ATOM\phi \in ATOM,
  2. r((ϕ□ψ))=max⁡(r(ϕ),r(ψ))+1r((\phi \square \psi)) = \max(r(\phi), r(\psi)) + 1,
  3. r((¬ϕ))=r(ϕ)+1r((\neg \phi)) = r(\phi) + 1。

語句 ϕ\phi 的子構句(subformula)的集合 Sub(ϕ)Sub(\phi) 因此也是合法且唯一的:

  1. Sub(ϕ)={ϕ}Sub(\phi) = \{ \phi \},若 ϕ∈ATOM\phi \in ATOM,
  2. Sub((ϕ□ψ))=Sub(ϕ)∪Sub(ψ)∪{(ϕ□ψ)}Sub((\phi \square \psi)) = Sub(\phi) \cup Sub(\psi) \cup \{ (\phi \square \psi) \},
  3. Sub((¬ϕ))=Sub(ϕ)∪{(¬ϕ)}Sub((\neg \phi)) = Sub(\phi) \cup \{ (\neg \phi) \}。

定理 1.1.7 秩的歸納法原理

對於任意 ϕ∈PROP\phi \in PROP,若滿足下述條件,則 A(ϕ)A(\phi) 成立:

證明:不難證明 1.7 的歸納法原理與 1.3 歸納法原理等價。

語義學 semantics

從本節開始,我們開始省略輔助符號。並且,由於語義學定理大多可以歸納法證明,我在此也將略過不提。

定義 1.2.1 賦值函數

v:PROP→{0,1}v: PROP \rightarrow \{0,1\} 稱為賦值函數(valuation function),意思是對於所有 ϕ,ψ∈PROP\phi, \psi \in PROP,滿足下述條件:

  1. v(ϕ∧ψ)=min⁡(v(ϕ),v(ψ))v(\phi \wedge \psi) = \min(v(\phi), v(\psi)),
  2. v(ϕ∨ψ)=max⁡(v(ϕ),v(ψ))v(\phi \vee \psi) = \max(v(\phi), v(\psi)),
  3. v(ϕ→ψ)=max⁡(1−v(ϕ),v(ψ))v(\phi \rightarrow \psi) = \max(1 - v(\phi), v(\psi)),
  4. v(ϕ↔ψ)=1−∣v(ϕ)−v(ψ)∣v(\phi \leftrightarrow \psi) = 1 - |v(\phi) - v(\psi)|,
  5. v(¬ϕ)=1−v(ϕ)v(\neg \phi) = 1 - v(\phi)。
  6. v(⊥)=0v(\bot) = 0。

定理 1.2.2 賦值函數的唯一性

對原子命題賦值相同的賦值函數是唯一的。

證明:根據定理 1.6,歸納定義。

註:

  1. 由於定義 2.1 是遞迴的,vv 可以只定義在 ATOMATOM 上,然後擴展到 PROPPROP 上。
  2. 若 vv 是賦值,對於一個語句 ϕ\phi,⟦ϕ⟧v\llbracket \phi \rrbracket_v 代表 ϕ\phi 的值。

定義 1.2.3 模型

  1. ϕ\phi 是恆真句(tautology),若對於所有 vv,v(ϕ)=1v(\phi) = 1。寫作 ⊨ϕ\models \phi,
  2. 若 Γ\Gamma 是命題集合,Γ⊨ϕ\Gamma\models \phi 表示對於所有 vv,若 ψ∈Γ,v(ψ)=1\psi\in\Gamma, v(\psi) = 1,則 v(ϕ)=1v(\phi) = 1。

註:可以寫作 ⟦ϕ⟧=1\llbracket \phi \rrbracket = 1,表示容許任意賦值。

定義 1.2.4 取代

ϕ[ψ/p]\phi[\psi / p] 表示(p∈ATOMp \in ATOM):

  1. 若 ϕ∈ATOM\phi \in ATOM 且 ϕ≠p\phi \neq p,則 ϕ[ψ/p]=ϕ\phi[\psi / p] = \phi,
  2. 若 ϕ=p\phi = p,則 ϕ[ψ/p]=ψ\phi[\psi / p] = \psi,
  3. (ϕ1□ϕ2)[ψ/p]=ϕ1[ψ/p]□ϕ2[ψ/p](\phi_1 \square \phi_2)[\psi / p] = \phi_1[\psi / p] \square \phi_2[\psi / p],
  4. (¬ϕ)[ψ/p]=¬ϕ[ψ/p](\neg \phi)[\psi / p] = \neg \phi[\psi / p]。

定理 1.2.5 取代定理

若 ⊨ϕ1↔ϕ2\models \phi_1 \leftrightarrow \phi_2,則 ⊨ϕ1[ψ/p]↔ϕ2[ψ/p]\models \phi_1[\psi / p] \leftrightarrow \phi_2[\psi / p]。

引理 1.2.6 取代定理的推廣

  1. ⟦ϕ1↔ϕ2⟧v≤⟦ψ[ϕ1/p]↔ψ[ϕ2/p]⟧v\llbracket \phi_1 \leftrightarrow \phi_2 \rrbracket _v \leq \llbracket \psi[\phi_1 / p] \leftrightarrow \psi[\phi_2 / p] \rrbracket _v。
  2. ⊨(ϕ1↔ϕ2)→(ψ[ϕ1/p]↔ψ[ϕ2/p])\models (\phi_1 \leftrightarrow \phi_2) \rightarrow (\psi[\phi_1 / p] \leftrightarrow \psi[\phi_2 / p])。

命題邏輯的諸性質

性質 1.3.1

結合律:

  1. ⊨(ϕ∨ψ)∨σ↔ϕ∨(ψ∨σ)\models (\phi \lor \psi) \lor \sigma \leftrightarrow \phi \lor (\psi \lor \sigma)
  2. ⊨(ϕ∧ψ)∧σ↔ϕ∧(ψ∧σ)\models (\phi \land \psi) \land \sigma \leftrightarrow \phi \land (\psi \land \sigma)

交換律:

  1. ⊨(ϕ∨ψ)↔(ψ∨ϕ)\models (\phi \lor \psi) \leftrightarrow (\psi \lor \phi)
  2. ⊨(ϕ∧ψ)↔(ψ∧ϕ)\models (\phi \land \psi) \leftrightarrow (\psi \land \phi)

分配律:

  1. ⊨(ϕ∨(ψ∧σ))↔((ϕ∨ψ)∧(ϕ∨σ))\models (\phi \lor (\psi \land \sigma)) \leftrightarrow ((\phi \lor \psi) \land (\phi \lor \sigma))
  2. ⊨(ϕ∧(ψ∨σ))↔((ϕ∧ψ)∨(ϕ∧σ))\models (\phi \land (\psi \lor \sigma)) \leftrightarrow ((\phi \land \psi) \lor (\phi \land \sigma))

笛摩根律:

  1. ⊨¬(ϕ∨ψ)↔(¬ϕ∧¬ψ)\models \neg (\phi \lor \psi) \leftrightarrow (\neg \phi \land \neg \psi)
  2. ⊨¬(ϕ∧ψ)↔(¬ϕ∨¬ψ)\models \neg (\phi \land \psi) \leftrightarrow (\neg \phi \lor \neg \psi)

冪等律:

  1. ⊨ϕ∨ϕ↔ϕ\models \phi \lor \phi \leftrightarrow \phi
  2. ⊨ϕ∧ϕ↔ϕ\models \phi \land \phi \leftrightarrow \phi

雙重否定:

性質 1.3.2

若 ⊨ϕ→ψ\models \phi \rightarrow \psi,則:

  1. ⊨ϕ∧ψ↔ϕ\models \phi \land \psi \leftrightarrow \phi
  2. ⊨ϕ∨ψ↔ψ\models \phi \lor \psi \leftrightarrow \psi

性質 1.3.3

  1. ⊨ϕ⇒⊨ϕ∧ψ↔ψ\models \phi \Rightarrow \models \phi \land \psi \leftrightarrow \psi,
  2. ⊨ϕ⇒⊨¬ϕ∨ψ↔ψ\models \phi \Rightarrow \models \neg \phi \lor \psi \leftrightarrow \psi,
  3. ⊨⊥∨ϕ↔ϕ\models \bot \lor \phi \leftrightarrow \phi,
  4. ⊨⊤∧ϕ↔ϕ\models \top \land \phi \leftrightarrow \phi。

性質 1.3.4

  1. ⊨(ϕ↔ψ)↔(ϕ→ψ)∧(ψ→ϕ)\models (\phi \leftrightarrow \psi) \leftrightarrow (\phi \rightarrow \psi) \land (\psi \rightarrow \phi),
  2. ⊨(ϕ→ψ)↔(¬ϕ∨ψ)\models (\phi \rightarrow \psi) \leftrightarrow (\neg \phi \lor \psi),
  3. ¬ϕ↔(ϕ→⊥)\neg \phi \leftrightarrow (\phi \rightarrow \bot),
  4. ⊨⊥↔ϕ∧¬ϕ\models \bot \leftrightarrow \phi \land \neg \phi。

引理 1.3.5 等價關係 ≈\approx

ϕ≈ψ\phi\approx\psi 表示 ⊨ϕ↔ψ\models \phi \leftrightarrow \psi,ϕ≈ϕ\phi\approx\phi 是在 PROPPROP 上的等價關係,

定理 1.3.6 ¬,∨\neg, \lor 的語義完備性

若 δ\delta 是一個 nn 元邏輯連詞,存在函數 ff 使得 ⟦δ(p1,...,pn)⟧=f(⟦p1⟧,...,⟦pn⟧)\llbracket \delta(p_1,...,p_n) \rrbracket = f(\llbracket p_1 \rrbracket,...,\llbracket p_n \rrbracket),則我們說 δ\delta 是由其賦值函數所定義的。

對於由其賦值函數所定義的 nn 元邏輯連詞 δ\delta,存在只由 p1,...,pn,¬,∨p_1,...,p_n, \neg, \lor 構成的語句 ϕ\phi,使得 ⊨ϕ↔δ(p1,...,pn)\models \phi \leftrightarrow \delta(p_1,...,p_n)。

定義 1.3.7 連續連詞

1 選言

⋁i=00ϕi=ϕ0\bigvee_{i=0}^0 \phi_i = \phi_0

⋁i≤0n+1ϕi=(⋁i≤0nϕi)∨ϕn+1\bigvee_{i \leq 0}^{n+1} \phi_i = (\bigvee_{i \leq 0}^n \phi_i) \lor \phi_{n+1}

2 連言

⋀i=0nϕi=ϕ0\bigwedge_{i = 0}^n \phi_i = \phi_0

⋀i≤0n+1ϕi=(⋀i≤0nϕi)∧ϕn+1\bigwedge_{i \leq 0}^{n+1} \phi_i = (\bigwedge_{i \leq 0}^n \phi_i) \land \phi_{n+1}

定義 1.3.8 標準式

ϕ=⋀j⋁iϕi,j\phi = \bigwedge_j\bigvee_i\phi_{i,j},其中 ϕi,j\phi_{i,j} 是原子命題或帶 ¬\neg 連詞的原子命題,稱為連言標準式(conjunctive normal form)。

ϕ=⋁j⋀iϕi,j\phi = \bigvee_j\bigwedge_i\phi_{i,j},其中 ϕi,j\phi_{i,j} 是原子命題或帶 ¬\neg 連詞的原子命題,稱為選言標準式(disjunctive normal form)。

定理 1.3.9 標準式的存在性

對於任意語句 ϕ\phi,存在連言標準式 ϕ∧\phi^\land 與選言標準式 ϕ∨\phi^\lor,使得 ⊨ϕ↔ϕ∧↔ϕ∨\models \phi \leftrightarrow \phi^\land \leftrightarrow \phi^\lor。

定義 1.3.10 否定函數

⋆:PROP→PROP\star: PROP \rightarrow PROP 遞迴定義如下:

  1. ϕ⋆=¬ϕ\phi^\star = \neg \phi,若 ϕ∈ATOM\phi \in ATOM,
  2. (ϕ∨ψ)⋆=(ϕ⋆∧ψ⋆)(\phi \lor \psi)^\star = (\phi^\star \land \psi^\star),
  3. (ϕ∧ψ)⋆=(ϕ⋆∨ψ⋆)(\phi \land \psi)^\star = (\phi^\star \lor \psi^\star)。
  4. (¬ϕ)⋆=¬ϕ⋆(\neg \phi)^\star = \neg \phi^\star。

性質 1.3.11 否定函數的性質

ϕ⋆≈¬ϕ\phi^{\star} \approx \neg \phi。

定義 1.3.12 共軛函數 duality function

共軛函數 d:PROP→PROPd: PROP \rightarrow PROP 遞迴定義如下:

  1. ϕd=ϕ\phi^d = \phi,若 ϕ∈ATOM\phi \in ATOM,
  2. (ϕ∨ψ)d=ϕd∧ψd(\phi \lor \psi)^d = \phi^d \land \psi^d,
  3. (ϕ∧ψ)d=ϕd∨ψd(\phi \land \psi)^d = \phi^d \lor \psi^d。
  4. (¬ϕ)d=¬ϕd(\neg \phi)^d = \neg \phi^d。

定理 1.3.13 共軛定理

若 ⊨ϕ↔ψ\models \phi \leftrightarrow \psi,則 ⊨ϕd↔ψd\models \phi^d \leftrightarrow \psi^d。

自然演繹法

定義 1.4.1 自然演繹法的演繹集合

演繹集合是最小的滿足下面性質的樹的集合 XX:

給定任意一棵演繹樹,前提集合 Γ\Gamma 是所有不可消除的葉節點的集合,結論是樹的根節點。

定義 1.4.2 可推導性

引理 1.4.3 可推導性的性質

定理 1.4.4 一些定理

完備性

證明步驟如下:

  1. 證明命題邏輯系統是健全的。
  2. 證明(語法的)最大一致集存在(透過 Zorn’s Lemma)。
  3. 透過最大一致集,建立能使最大一致集都為真的賦值函數。亦即,命題邏輯系統存在模型。
  4. 亦即,不存在模型中為不為真,但能證明的命題。
  5. 1 和 4 共同蘊含了完備性。

引理 1.5.1 健全性

若 Γ⊢ϕ\Gamma \vdash \phi,則 Γ⊨ϕ\Gamma \models \phi。

證明:以歸納法直接證明。

定義 1.5.2 一致性

Γ\Gamma 是一致的,若 Γ⊬⊥\Gamma \not\vdash \bot。

引理 1.5.3 不一致性的等價性質

以下條件是等價的:

  1. Γ\Gamma 不是一致的。
  2. 存在 ϕ\phi 使得 Γ⊢ϕ\Gamma \vdash \phi 與 Γ⊢¬ϕ\Gamma \vdash \neg \phi。
  3. 對於所有 ϕ\phi,Γ⊢ϕ\Gamma \vdash \phi。

引理 1.5.4 一致性的等價性質

以下條件是等價的:

  1. Γ\Gamma 是一致的。
  2. 不存在 ϕ\phi 使得 Γ⊬ϕ\Gamma \not\vdash \phi 與 Γ⊬¬ϕ\Gamma \not\vdash \neg \phi。
  3. 存在 ϕ\phi 使得 Γ⊬ϕ\Gamma \not\vdash \phi。

引理 1.5.5

若存在賦值 vv 使得 ⟦ϕ⟧v=1,∀ϕ∈Γ\llbracket \phi \rrbracket_v = 1, \forall \phi \in \Gamma,則 Γ⊬⊥\Gamma \not \vdash \bot。

定理 1.5.6

Γ∪{ϕ}⊢⊥⇒Γ⊢¬ϕ\Gamma \cup \{ \phi \} \vdash \bot \Rightarrow \Gamma \vdash \neg \phi。

證明:根據引理 5.1。

定義 1.5.7 最大一致集合

Γ\Gamma 是最大一致的,若且唯若

引理 1.5.8 最大一致集存在引理

對於任意的 Γ⊬⊥\Gamma \not \vdash \bot,存在 Γ⋆\Gamma^\star 是最大一致的,且 Γ⊂Γ⋆\Gamma\subset\Gamma^\star。

證明:定義 ⟨Γi⟩\langle \Gamma_i \rangle 序列如下:

  • Γ0=Γ\Gamma_0 = \Gamma,
  • 若 Γi∪{ϕi}⊬⊥\Gamma_i \cup \{ \phi_i \} \not \vdash \bot,Γi+1=Γi∪{ϕi}\Gamma_{i+1} = \Gamma_i \cup \{ \phi_i \},否則 Γi+1=Γi\Gamma_{i+1} = \Gamma_i。
  • Γ⋆=⋃iΓi\Gamma^\star = \bigcup_i \Gamma_i。

其中 ⟨ϕi⟩\langle \phi_i \rangle 是給所有的命題語句的一個排序。

可以證明 Γ⋆\Gamma^\star 是最大一致的。

引理 1.5.9

若 Γ\Gamma 是最大一致的,則 Γ\Gamma 是演繹封閉的。

定理 1.5.10

若 Γ\Gamma 是最大一致的,則:

  1. 對於所有 ϕ\phi 要嘛 ϕ∈Γ\phi\in\Gamma 要嘛 ¬ϕ∈Γ\neg\phi\in\Gamma。
  2. 對於所有 ϕ,ψ\phi, \psi,ϕ→ψ∈Γ\phi\rightarrow\psi\in\Gamma 若且唯若 ϕ∈Γ⇒ψ∈Γ\phi\in\Gamma\Rightarrow\psi\in\Gamma。
  3. ϕ∈Γ\phi\in\Gamma 若且唯若 ¬ϕ∉Γ\neg\phi\not\in\Gamma。
  4. ¬ϕ∈Γ\neg\phi\in\Gamma 若且唯若 ϕ∉Γ\phi\not\in\Gamma。

引理 1.5.11 模型存在引理

若 Γ\Gamma 是一致的,存在賦值 vv 使得 ⟦ϕ⟧v=1,∀ϕ∈Γ\llbracket \phi \rrbracket_v = 1, \forall \phi \in \Gamma。

證明:

定義 Γ⋆\Gamma^\star 是最大一致的,且 Γ∈Γ⋆\Gamma\in\Gamma^\star。

定義 v(pi)=1,pi∈Γ⋆v(p_i) = 1, p_i\in\Gamma^\star 與 v(pi)=0,pi∉Γ⋆v(p_i) = 0, p_i\not\in\Gamma^\star,並遞迴地擴充成賦值函數。

以歸納法證明:⟦ϕ⟧v=1\llbracket \phi \rrbracket_v = 1 若且唯若 ϕ∈Γ⋆\phi \in \Gamma^\star。

推論 1.5.12

若 Γ⊬ϕ\Gamma\not\vdash\phi,存在賦值 vv 使得 ⟦ψ⟧v=1,∀ψ∈Γ\llbracket \psi \rrbracket_v = 1, \forall \psi \in \Gamma 且 ⟦ϕ⟧v=0\llbracket \phi \rrbracket_v = 0。

亦即:若 Γ⊬ϕ\Gamma\not\vdash\phi,則 Γ⊭ϕ\Gamma\not\models\phi。

定理 1.5.13 完備性定理

Γ⊨ϕ\Gamma \models \phi 若且唯若 Γ⊢ϕ\Gamma \vdash \phi。

其他連接詞

定義 1.6.1 三個連接詞

引理 1.6.2 一些重要性質

定理 1.6.3

參考文獻

註釋

編輯本頁

Comments

留言

    Podcast

    關於語音摘要

    此語音摘要由 Google NotebookLM 提供,不完全代表作者本人對文章的理解。