1. 命題邏輯

December 26, 2021

Dirk van Dalen, Logic and Structure, 4th.

1.1 命題與連接詞

〔定義 1.1.1 字母〕 命題邏輯由以下字母構成:

  1. 命題符號(proposition symbols):p0p_0p1p_1p2p_2 ……,
  2. 連接詞(connectives):\wedge\vee\rightarrow¬\neg\leftrightarrow\bot
  3. 輔助符號(auxiliary symbols):(())

〔定義 1.1.2 構式規則(formation rule)〕 命題集合 PROPPROP 是最小的滿足以下性質的集合 X

  1. pi(iN)Xp_i(i\in \mathbb{N})\in XX\bot\in X
  2. ϕ,ψX(ϕψ),(ϕψ),(ϕψ),(ϕψ)X\phi, \psi \in X \Rightarrow (\phi \wedge \psi), (\phi \vee \psi), (\phi \rightarrow \psi), (\phi \leftrightarrow \psi) \in X,或縮寫成 (ϕψX)(\phi \Box \psi \in X)
  3. ϕX(¬ϕ)X\phi \in X \Rightarrow (\neg \phi) \in X

〔定理 1.1.3 歸納法原理〕AA 是一個性質,則 A(ϕ)A(\phi) 對所有的 ϕPROP\phi \in PROP 成立,若:

  1. A(pi)A(p_i),對於所有 ii,以及 A()A(\bot)
  2. A(ϕ),A(ψ)A((ϕψ))A(\phi), A(\psi) \Rightarrow A((\phi \Box \psi))
  3. A(ϕ)A((¬ϕ))A(\phi) \Rightarrow A((\neg\phi))

說明:我們將定理 1.1.3 的應用稱之為「以在 ϕ\phi 上的歸納法證明」。


〔定義 1.1.4 構式序列〕 ϕi(inN)\langle \phi_i \rangle (i \leq n \in \mathbb{N}) 稱為 ϕ\phi 的構式序列(formation sequence),若對於所有 ii

  1. ϕi\phi_i 是原子語句,或
  2. 存在 j,k<ij, k < i 使得 ϕi=(ϕjϕk)\phi_i = (\phi_j \Box \phi_k),或
  3. 存在 j<ij < i 使得 ϕi=(¬ϕj)\phi_i = (\neg \phi_j)

性質

  1. 所有命題都有偶數數量的括號。
  2. 所有命題都有構式序列。
  3. PROPPROP 是一個所有表述都有構式序列的集合(〔定理 1.1.5〕)。

〔定理 1.1.6 遞迴定義〕 給定 H:A2AH_\Box: A^2 \rightarrow AH¬:A2AH_\neg: A^2 \rightarrow AHat:AAH_{at}: A \rightarrow A 的由運算子自然定義的函數,存在唯一的函數 F:PROPAF: PROP \rightarrow A 使得:

  • F(ϕ)=Hat(ϕ)F(\phi) = H_{at}(\phi),對於原子語句 ϕ\phi
  • F((ϕψ))=H(F(ϕ),F(ψ))F((\phi \Box \psi)) = H_\Box (F(\phi), F(\psi))
  • F((¬ϕ))=H¬(F(ϕ))F((\neg \phi)) = H_\neg(F(\phi))

證明:以歸納法證明唯一性與存在性(取一個關係集合的聯集,並證明這個聯集也是一個函數)。


〔定義 1.1.7 子句式〕 子句式的集合 Sub(ϕ)Sub(\phi) 遞迴定義如下:

  • Sub(ϕ)={ϕ}Sub(\phi) = \{ \phi \} 對於原子語句 ϕ\phi
  • Sub(ϕ1ϕ2)=Sub(ϕ1)Sub(ϕ2){ϕ1ϕ2}Sub(\phi_1 \Box \phi_2) = Sub(\phi_1) \cup Sub(\phi_2) \cup \{ \phi_1 \Box \phi_2 \}
  • Sub(¬ϕ)=Sub(ϕ){¬ϕ}Sub(\neg \phi) = Sub(\phi) \cup \{\neg \phi\}

說明

  1. 根據 〔定理 1.1.6〕,子句式集合是良好定義的。
  2. ψSub(ϕ)\psi \in Sub(\phi),可以寫作 ψϕ\psi \prec \phi

〔定義 1.1.8 秩上的歸納法原理(Induction on rank-Principle)〕r(ψ)<r(ϕ)[A(ψ)]A(ϕ)\forall r(\psi) < r(\phi) [A(\psi)] \Rightarrow A(\phi),則 ϕPROP[A(ϕ)]\forall \phi \in PROP[A(\phi)],其中 rr 遞迴定義如下:

  • r(ϕ)=0r(\phi) = 0,對於原子語句 ϕ\phi
  • ϕ=ψ1ψ2\phi = \psi_1 \Box \psi_2,則 r(ϕ)=max(ψ1,ψ2)+1r(\phi) = max(\psi_1, \psi_2) + 1
  • ϕ=¬ψ\phi = \neg \psi,則 r(ϕ)=r(ψ)+1r(\phi) = r(\psi) + 1

1.2 語義學

〔定義 1.2.1 賦值(valuation)〕 v:PROP{0,1}v: PROP \rightarrow \{0,1\} 是一個賦值,若:

  • v(ϕψ)=min(v(ϕ),v(ψ))v(\phi \wedge \psi) = min(v(\phi), v(\psi))
  • v(ϕψ=max(v(ϕ),v(ψ))v(\phi \vee \psi = max(v(\phi), v(\psi))
  • v(ϕψ)=0v(ϕ)=1v(\phi \rightarrow \psi) = 0 \Leftrightarrow v(\phi) = 1v(ψ)=0v(\psi) = 0
  • v(ϕψ)=1v(ϕ)=v(ψ)v(\phi \leftrightarrow \psi) = 1 \Leftrightarrow v(\phi) = v(\psi)
  • v(¬ϕ)=1v(ϕ)v(\neg \phi) = 1 - v(\phi)
  • v()=0v(\bot) = 0

〔定理 1.2.2 賦值唯一性〕vv 是從原子語句到 {0,1}\{0,1\} 的滿足 v()=0v(\bot) = 0 的函數,則存在唯一的賦值 .v\llbracket . \rrbracket_v 使得對於所有原子語句 ϕ\phiϕv=v(ϕ)\llbracket \phi \rrbracket_v = v(\phi)


〔引理 1.2.3 真值函數〕 若對於所有在 ϕ\phi 中出現的 pip_iv(pi)v(pi)v(p_i) - v'(p_i),則 ϕv=ϕv\llbracket \phi \rrbracket_v = \llbracket \phi \rrbracket_{v'}


〔定義 1.2.4 恆真句(tautology)〕

  1. ϕ\phi 是一個恆真句,若且唯若,對於所有賦值 vvϕv=1\llbracket \phi \rrbracket_v = 1
  2. 簡寫成 ϕ\models \phi
  3. Γ\Gamma 是一個命題集合,Γϕ\Gamma \models \phi,若且唯若,對於所有使得 ψΓ[ψv=1]\forall \psi \in \Gamma [\llbracket \psi \rrbracket_v = 1] 的賦值 vvϕv=1\llbracket \phi \rrbracket_v = 1

〔定義 1.2.5 替代〕 ϕ[ψ/pi]\phi [\psi / p_i],代表以 ψ\psi 替代在 ϕ\phi 中出現的所有原子語句 pip_i

說明:可以更嚴謹地以遞迴定義。


〔定理 1.2.6 替代定理〕ϕ1ϕ2\models \phi_1 \leftrightarrow \phi_2,則 ψ[ϕ1/p]ψ[ϕ2/p]\psi[\phi_1/p] \leftrightarrow \psi[\phi_2/p]pp 是一個原子語句。

性質〔引理 1.2.7〕

  1. ϕ1ϕ2vψ[ϕ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 \phi[\phi_2 / p])

1.3 命題邏輯的一些性質

〔定理 1.3.1〕 以下命題為恆真句:

  1. 結合性(associativity):
    • (ϕψ)σϕ(ψσ)(\phi \vee \psi) \vee \sigma \leftrightarrow \phi \vee (\psi \vee \sigma)
    • (ϕψ)σϕ(ψσ)(\phi \wedge \psi) \wedge \sigma \leftrightarrow \phi \wedge (\psi \wedge \sigma)
  2. 交換性(commutativity):
    • ϕψψϕ\phi \vee \psi \leftrightarrow \psi \vee \phi
    • ϕψψϕ\phi \wedge \psi \leftrightarrow \psi \wedge \phi
  3. 分配性(distributivity):
    • ϕ(ψσ)(ϕψ)(ϕσ)\phi \vee (\psi \wedge \sigma) \leftrightarrow (\phi \vee \psi) \wedge (\phi \vee \sigma)
    • ϕ(ψσ)(ϕψ)(ϕσ)\phi \wedge (\psi \vee \sigma) \leftrightarrow (\phi \wedge \psi) \vee (\phi \wedge \sigma)
  4. 迪・摩根律(De Morgan’s laws):
    • ¬(ϕψ)¬ϕ¬ψ\neg (\phi \vee \psi) \leftrightarrow \neg \phi \wedge \neg \psi
    • ¬(ϕψ)¬ϕ¬ψ\neg (\phi \wedge \psi) \leftrightarrow \neg \phi \vee \neg \psi
  5. 冪等性(idempotency):
    • ϕϕϕ\phi \vee \phi \leftrightarrow \phi
    • ϕϕϕ\phi \wedge \phi \leftrightarrow \phi
  6. 雙重否定律(double negation law):
    • ¬¬ϕϕ\neg \neg \phi \leftrightarrow \phi

〔引理 1.3.2〕ϕψ\models \phi \rightarrow \psi,則 ϕψϕ\models \phi \wedge \psi \leftrightarrow \phiϕψψ\models \phi \vee \psi \leftrightarrow \psi


〔引理 1.3.3〕

  1. ϕϕψψ\models \phi \Leftrightarrow \models \phi \wedge \psi \leftrightarrow \psi
  2. ϕ¬ϕψψ\models \phi \Leftrightarrow \models \neg \phi \vee \psi \leftrightarrow \psi
  3. ψϕ\models \bot \vee \psi \leftrightarrow \phi
  4. ψϕ\models \top \wedge \psi \leftrightarrow \phi

〔定理 1.3.4〕

  1. (ϕψ)(ϕψ)(ψϕ)\models (\phi \leftrightarrow \psi) \leftrightarrow (\phi \rightarrow \psi) \wedge (\psi \rightarrow \phi)
  2. (ϕψ)(¬ϕψ)\models (\phi \rightarrow \psi) \leftrightarrow (\neg \phi \vee \psi)
  3. (ϕψ)(¬ϕψ)\models (\phi \vee \psi) \leftrightarrow (\neg \phi \rightarrow \psi)
  4. ϕψ¬(¬ϕ¬ψ)\models \phi \vee \psi \leftrightarrow \neg (\neg \phi \wedge \neg \psi)
  5. ϕψ¬(¬ϕ¬ψ)\models \phi \wedge \psi \leftrightarrow \neg (\neg \phi \vee \neg \psi)
  6. ¬ϕϕ\models \neg \phi \leftrightarrow \phi \rightarrow \bot
  7. ϕ¬ϕ\models \top \leftrightarrow \phi \wedge \neg \phi

我們將 ϕψ\models \phi \leftrightarrow \psi 簡寫成 ϕψ\phi \approx \psi


〔引理 1.3.5〕 \approx 是一個等同關係(equivalence relation)。


Sheffer stroke: ϕψ=¬(ϕψ)\phi | \psi = \neg (\phi \wedge \psi)


〔定理 1.3.6〕 對於任何一個由賦值所定義的 nn 列連接詞 $\text{\textdollar},存在一個只包含 p1p_1、……、pnp_n\vee¬\neg 的命題 γ\gamma,使得 γ$(p1,...,pn)\models \gamma \leftrightarrow \text{\textdollar}(p_1, ..., p_n)

證明:透過歸納法。定義 $1\text{\textdollar}_1$2\text{\textdollar}_2 使得

  • $1(p2,...,pn+1)=$(,p2,...,pn+1)\text{\textdollar}_1(p_2,...,p_{n+1}) = \text{\textdollar}(\bot, p_2, ..., p_{n+1})
  • $2(p2,...,pn+1)=$(,p2,...,pn+1)\text{\textdollar}_2(p_2,...,p_{n+1}) = \text{\textdollar}(\top, p_2, ..., p_{n+1})

假設 $i(p2,...,pn+1)σi\models \text{\textdollar}_i (p_2, ..., p_{n+1}) \leftrightarrow \sigma_i

γ\gamma 定義為 (p1σ2)(¬p1σ1)(p_1 \rightarrow \sigma_2) \wedge (\neg p_1 \rightarrow \sigma_1),並證明 $(p1,...,pn+1)γ\models \text{\textdollar}(p_1,... ,p_{n+1}) \leftrightarrow \gamma


〔定義 1.3.7〕

  • i0ϕi=ϕ0\displaystyle\bigwedge_{i \leq 0} \phi_i = \phi_0
  • in+1ϕi=inϕiϕn+1\displaystyle\bigwedge_{i \leq n+1} \phi_i = \bigwedge_{i \leq n} \phi_i \wedge \phi_{n+1}
  • i0ϕi=ϕ0\displaystyle\bigvee_{i \leq 0} \phi_i = \phi_0
  • in+1ϕi=inϕiϕn+1\displaystyle\bigvee_{i \leq n+1} \phi_i = \bigvee_{i \leq n} \phi_i \vee \phi_{n+1}

〔定義 1.3.8:連言與選言標準式〕

  • ϕ=ϕij\phi = \bigwedge \bigvee \phi_{ij},其中 ϕij\phi_{ij} 都是原子語句或是原子語句加上 ¬\negϕ\phi 稱為一個連言標準式(conjunctive normal form)。
  • ϕ=ϕij\phi = \bigvee \bigwedge \phi_{ij},其中 ϕij\phi_{ij} 都是原子語句或是原子語句加上 ¬\negϕ\phi 稱為一個選言標準式(disjunctive normal form)。

〔定理 1.3.9〕 對於任何 ϕ\phi,存在連言標準式 ϕ\phi^{\wedge} 和選言標準式 ϕ\phi^{\vee},使得 ϕϕϕ\phi \approx \phi^{\wedge} \approx \phi^{\vee}


〔定義 1.3.10〕 輔助對應(auxiliary mapping):PROPPROP^\ast: PROP \rightarrow PROP 遞迴定義如下:

  • ϕ=¬ϕ\phi^{\ast} = \neg \phi,其中 ϕ\phi 是原子語句,
  • (ϕψ)=ϕψ(\phi \wedge \psi)^{\ast} = \phi^{\ast} \vee \psi^{\ast}
  • (ϕψ)=ϕψ(\phi \vee \psi)^{\ast} = \phi^{\ast} \wedge \psi^{\ast}
  • (¬ϕ)=¬ϕ(\neg \phi)^{\ast} = \neg \phi^{\ast}

〔引理 1.3.11〕 ϕ=¬ϕ\llbracket\phi^\ast\rrbracket=\llbracket\neg\phi\rrbracket

性質

  • ϕ¬ϕ\phi^\ast\approx\neg\phi〔系理 1.3.12〕

〔定義 1.3.13〕 對偶對應(duality mapping)d:PROPPROP^d: PROP \rightarrow PROP 遞迴定義如下:

  • ϕd=ϕ\phi^d = \phi,其中 ϕ\phi 是原子語句,
  • (ϕψ)d=ϕdψd(\phi \wedge \psi)^d = \phi^d \vee \psi^d
  • (ϕψ)d=ϕdψd(\phi \vee \psi)^d = \phi^d \wedge \psi^d
  • (¬ϕ)d=¬ϕd(\neg \phi)^d = \neg \phi^d

〔定理 1.3.14 對偶定理〕 ϕϕϕdψd\phi \approx \phi \Leftrightarrow \phi^d \approx \psi^d

1.4 自然演繹法

演繹規則

引入規則

ϕψ(I)ϕψ\begin{aligned} \phi &\quad \psi \enspace _{(\wedge I)} \\\hline \phi &\wedge \psi \end{aligned}


[ϕ]...ψ(I)ϕψ\begin{aligned} &[\phi]\\ &...\\ &\psi \enspace _{(\rightarrow I)} \\ \hline \phi &\rightarrow \psi \end{aligned}

移出規則

ϕψ(E)ϕ\begin{aligned} \phi &\wedge \psi \enspace _{(\wedge E)} \\\hline &\phi \end{aligned}


ϕψ(E)ψ\begin{aligned} \phi &\wedge \psi \enspace _{(\wedge E)} \\\hline &\psi \end{aligned}


ϕϕψ(E)ψ\begin{aligned} \phi &\quad \phi \rightarrow \psi \enspace _{(\rightarrow E)} \\\hline &\psi \end{aligned}

矛盾規則

()ϕ\begin{aligned} &\bot \enspace _{(\bot)} \\\hline &\phi \end{aligned}


[¬ϕ]...(RAA)ϕ\begin{aligned} [\neg &\phi]\\ &...\\ &\bot \enspace _{(RAA)} \\ \hline &\phi \end{aligned}


〔定義 1.4.1〕 演繹集合(the set of derivations)是滿足下列性質的最小集合:

(1) 對於所有 ϕPROP\phi\in PROP,單一元素樹 ϕX\phi \in X

(2 \wedge)

Dϕ ,DϕX\begin{matrix}D\\ \phi\end{matrix} \ , \begin{matrix}D'\\ \phi'\end{matrix} \in X,則 DϕDϕϕϕX\begin{matrix} \begin{matrix}D\\ \phi\end{matrix} \quad \begin{matrix}D'\\ \phi'\end{matrix} \\ \hline \phi \wedge \phi' \end{matrix} \in X

DϕψX\begin{matrix} D \\ \phi \wedge \psi \end{matrix} \in X,則 Dϕψϕ,DϕψψX\begin{aligned} &D \\ \phi &\wedge \psi \\ \hline &\phi \end{aligned}, \begin{aligned} &D \\ \phi &\wedge \psi \\ \hline &\psi \end{aligned} \in X

(2 \rightarrow)

ϕDψX\begin{matrix}\phi \\ D \\ \psi\end{matrix} \in X,則 [ϕ]DψϕϕX\begin{matrix} [\phi] \\ D \\ \psi \\ \hline \phi \rightarrow \phi \end{matrix} \in X

Dϕ,DϕψX\begin{matrix} D \\ \phi \end{matrix},\begin{matrix} D' \\ \phi \rightarrow \psi \end{matrix} \in X,則 DϕDϕψψX\begin{matrix} \begin{matrix} D \\ \phi \end{matrix} \quad \begin{matrix} D' \\ \phi \rightarrow \psi \end{matrix} \\ \hline \psi \end{matrix} \in X

(2 \bot)

DX\begin{matrix} D \\ \bot \end{matrix} \in X,則 DϕX\begin{matrix} D \\ \bot \\ \hline \phi \end{matrix} \in X

¬ϕDX\begin{matrix} \neg \phi \\ D \\ \bot \end{matrix} \in X,則 [¬ϕ]DϕX\begin{matrix} [\neg\phi] \\ D \\ \bot \\ \hline \phi \end{matrix} \in X


〔定義 1.4.2〕 Γϕ\Gamma \vdash \phi 的意思是「可以以 Γ\Gamma(一個命題集合)的命題作為假設演繹出 ϕ\phi」。


〔引理 1.4.3〕

  1. ϕΓ\phi \in \Gamma,則 Γϕ\Gamma\vdash\phi
  2. Γϕ,ΓψΓΓϕψ\Gamma \vdash \phi, \Gamma' \vdash \psi \Rightarrow \Gamma \cup \Gamma' \vdash \phi \wedge \psi
  3. ΓϕψΓϕ\Gamma \vdash \phi \wedge \psi \Rightarrow \Gamma \vdash \phiΓψ\Gamma \vdash \psi
  4. Γ{ϕ}ψΓϕψ\Gamma \cup \{\phi\} \vdash \psi \Rightarrow \Gamma \vdash \phi \rightarrow \psi
  5. Γϕ,ΓϕψΓΓψ\Gamma \vdash \phi, \Gamma' \vdash \phi \rightarrow \psi \Rightarrow \Gamma \cup \Gamma' \vdash \psi
  6. ΓΓϕ\Gamma \vdash \bot \Rightarrow \Gamma \vdash \phi
  7. Γ{¬ϕ}Γϕ\Gamma \cup \{ \neg \phi \} \vdash\bot \Rightarrow \Gamma\vdash\phi

〔定理 1.4.4〕

  1. ϕ(ψϕ)\vdash \phi\rightarrow(\psi\rightarrow\phi)
  2. ϕ(¬ϕψ)\vdash \phi\rightarrow(\neg\phi\rightarrow\psi)
  3. (ϕψ)[(ψσ)(ϕσ)]\vdash (\phi\rightarrow\psi)\rightarrow[(\psi\rightarrow\sigma)\rightarrow(\phi\rightarrow\sigma)]
  4. (ϕψ)(¬ψ¬ϕ)\vdash (\phi\leftrightarrow\psi)\rightarrow(\neg\psi\rightarrow\neg\phi)
  5. ¬¬ϕϕ\vdash \neg\neg\phi\leftrightarrow\phi
  6. [ϕ(ψσ)](ϕψσ)\vdash [\phi\rightarrow(\psi\rightarrow\sigma)]\leftrightarrow(\phi\wedge\psi\rightarrow\sigma)
  7. (ϕ¬ϕ)\vdash \bot\leftrightarrow(\phi\wedge\neg\phi)

1.5 完備性

〔定理 1.5.1 健全性〕 ΓϕΓϕ\Gamma \vdash \phi \Rightarrow \Gamma \vDash \phi

證明: 以歸納法證明。


〔定義 1.5.2 (語法的)一致性〕Γ\Gamma\nvdash\bot,則我們說 Γ\Gamma 是一致的。


〔引理 1.5.3〕 以下三個條件是等同的:

  1. Γ\Gamma 是一致的,
  2. 不存在 ϕ\phi 使得 Γϕ\Gamma\vdash\phiΓ¬ϕ\Gamma\vdash\neg\phi
  3. 存在一個 ϕ\phi 使得 Γϕ\Gamma\nvdash\phi

〔引理 1.5.4〕 若存在賦值 vv 使得,對於所有 ψΓ\psi\in\Gammaψv=1\llbracket\psi\rrbracket_v = 1,則 Γ\Gamma 是一致的。


〔引理 1.5.5〕〕

  1. Γ{¬ϕ}\Gamma\cup\{\neg\phi\} 是不一致的 \Rightarrow Γϕ\Gamma\vdash\phi
  2. Γ{ϕ}\Gamma\cup\{\phi\} 是不一致的 \Rightarrow Γ¬ϕ\Gamma\vdash\neg\phi

〔定義 1.5.6〕 一個集合 Γ\Gamma 是最大一致的(maximally consistent),若且唯若

  1. Γ\Gamma 是一致的,
  2. ΓΓ\Gamma \sube \Gamma'Γ\Gamma' 是一致的 Γ=Γ\Rightarrow \Gamma = \Gamma'

〔引理 1.5.7〕 對於任何一致的集合 Γ\Gamma,存在一個包含 Γ\Gamma 的最大一致集合 Γ\Gamma^*

證明

Γ0=ΓΓn+1={Γn{ϕn}若 Γ 是一致的,Γn其他。Γ={Γnn0}\begin{aligned}\Gamma_0 &= \Gamma\\\Gamma_{n+1}&=\begin{cases}\Gamma_n\cup\{\phi_n\} &\text{若 }\Gamma\text{ 是一致的,}\\\Gamma_n &\text{其他。}\end{cases}\\\Gamma^*&=\bigcup\{\Gamma_n | n \geq 0 \}\end{aligned}

顯然,ΓΓ\Gamma \sube \Gamma^*。可以證明 Γ\Gamma^* 是一個最大一致集合。


〔引理 1.5.8〕Γ\Gamma 是最大一致的,則 Γ\Gamma 是演繹封閉的。


〔引理 1.5.9〕Γ\Gamma 是最大一致的,則

  1. 對於所有 ϕ\phi,要嘛 ϕΓ\phi\in\Gamma,要嘛 ¬ϕΓ\neg\phi\in\Gamma
  2. ϕ,ψ,ϕψΓ(ϕΓψΓ)\phi,\psi,\phi\rightarrow\psi\in\Gamma \Leftrightarrow (\phi\in\Gamma\Rightarrow\psi\in\Gamma)

證明:透過〔引理 1.5.5〕與〔引理 1.5.8〕。


〔系理 1.5.10〕Γ\Gamma 是最大一致的,則 ϕΓ¬ϕΓ\phi\in\Gamma\Leftrightarrow\neg\phi\notin\Gamma¬ϕΓϕΓ\neg\phi\in\Gamma\Leftrightarrow\phi\notin\Gamma


〔引理 1.5.11 存在性定理〕Γ\Gamma 是一致的,則存在賦值 vv 使得,對於所有 ψΓ\psi\in\Gammaψv=1\llbracket\psi\rrbracket_v = 1

證明:考慮 Γ\Gamma^*(〔引理 1.5.7〕)。

定義 vvv(pi)={1若 piΓ0其他。v(p_i)=\begin{cases}1 &\text{若 }p_i\in\Gamma^*\text{,}\\0&\text{其他。}&\end{cases},將 vv 拓展到 v\llbracket \enspace \rrbracket_v

再以歸納法證明 ϕv=1ϕΓ\llbracket\phi\rrbracket_v = 1 \Leftrightarrow \phi \in \Gamma^*(需要〔引理 1.5.8〕與〔引理 1.5.9〕)。


〔系理 1.5.12〕 Γϕ\Gamma\nvdash\phi\Leftrightarrow 存在賦值 vv 使得,對於所有 ψΓ\psi\in\Gammaψv=1\llbracket\psi\rrbracket_v = 1 並且 ϕv=0\llbracket\phi\rrbracket_v = 0

證明ΓϕΓ{¬ϕ}\Gamma\nvdash\phi\Leftrightarrow\Gamma\cup\{\neg\phi\} 是一致的 \Leftrightarrow 存在賦值 vv 使得,對於所有 ψΓ{¬ϕ}\psi\in\Gamma\cup\{\neg\phi\}ψv=1\llbracket\psi\rrbracket_v = 1


〔定理 1.5.13 完備性定理〕 ΓϕΓϕ\Gamma\vdash\phi\Leftrightarrow\Gamma\vDash\phi

證明:根據〔定理 1.5.1〕,\Rightarrow 成立。

Γϕ\Gamma\nvdash\phi,根據〔系理 1.5.12〕,Γϕ\Gamma\nvDash\phi

1.6 其他連接詞

〔定義 1.6.1〕

  • ϕψ¬(¬ϕψ)\phi\vee\psi\coloneqq\neg(\neg\phi\wedge\psi)
  • ¬ϕϕ\neg\phi\coloneqq\phi\rightarrow\bot
  • ϕψ(ϕψ)(ψϕ)\phi\leftrightarrow\psi\coloneqq(\phi\rightarrow\psi)\wedge(\psi\rightarrow\phi)

〔引理 1.6.2〕

  1. ϕϕψ\phi\vdash\phi\vee\psiψϕψ\psi\vdash\phi\vee\psi
  2. Γ,ϕσ\Gamma,\phi\vdash\sigmaΓ,ψσΓ,ϕψσ\Gamma,\psi\vdash\sigma \Rightarrow \Gamma,\phi\wedge\psi\vdash\sigma
  3. ϕ,¬ϕ\phi,\neg\phi\vdash\bot
  4. Γ,ϕΓ¬ϕ\Gamma,\phi\vdash\bot\Rightarrow\Gamma\vdash\neg\phi
  5. ϕψ,ϕψ\phi\leftrightarrow\psi,\phi\vdash\psiϕψ,ψϕ\phi\leftrightarrow\psi,\psi\vdash\phi
  6. Γ,ϕψ\Gamma,\phi\vdash\psiΓ,ψϕΓϕψ\Gamma,\psi\vdash\phi \Rightarrow\Gamma\vdash\phi\leftrightarrow\psi

〔定理 1.6.3〕

  • ϕψ¬(¬ϕ¬ψ)\vdash\phi\vee\psi\leftrightarrow\neg(\neg\phi\wedge\neg\psi)
  • ¬ϕ(ϕ)\vdash\neg\phi\leftrightarrow(\phi\rightarrow\bot)
  • (ϕψ)(ϕψ)(ψϕ)\vdash(\phi\leftrightarrow\psi)\leftrightarrow(\phi\rightarrow\psi)\wedge(\psi\rightarrow\phi)

Profile picture

Written by Wei Hung who is thinking. You should follow them on Twitter