目錄
Open 目錄
結構
定義 1.1 結構 structure
結構是一個序列 A=⟨A,R1,...,Rn,F1,...,Fm,{ci∣i∈I}⟩,其中 A 是非空集合、R1,...,Rn 是 A 的關係、F1,...,Fm 是 A 的函數、ci(i∈I) 是 A 的(常數)元素。
定義 1.2 相似性類型 similarity type
A=⟨A,R1,...,Rn,F1,...,Fm,{ci∣i∈I}⟩ 的相似性類型是一個序列 ⟨r1,...,rn;a1,...,am;κ⟩,其中 Ri⊂Ari,Fj:Aaj→A,κ=∣I∣。
相似性類型的語言
給定 ⟨r1,...,rn;a1,...,am;κ⟩ 是 ⟨A,R1,...,Rn,F1,...,Fm,{ci∣i∈I}⟩ 的相似性類型。
定義 2.1 語詞集
TERM(語詞集)是滿足下述性質的最小集合 X:
- 常元 Const:ciˉ∈X(i∈I);
- 變元 Var:xi∈X(i∈N);
- 函數封閉性:若 t1,...,tai∈X,則 fi(t1,...,tai)∈X。
定義 2.2 構句集
FORM(構句集)是滿足下述性質的最小集合 X:
- ⊥∈X;
- 若 ri=0則 πi∈X(即 π 是命題符號);
- 若 t1,...,tri∈TERM,則 πi(t1,...,tri)∈X;
- 若 t1,t2∈TERM,則 (t1=t2)∈X;
- 若 ϕ,ψ∈X,則 (ϕ∧ψ),(ϕ∨ψ),(ϕ→ψ),(ϕ↔ψ)∈X(寫作 (ϕ□ψ));
- 若 ϕ∈X,則 (¬ϕ)∈X;
- 若 ϕ∈X,則 ∀xiϕ,∃xiϕ∈X。
定理 2.3 歸納法與遞迴性
參考命題邏輯的定理 1.3與1.6,不難證明 TERM 和 FORM 都滿足一般與遞迴的歸納法原理。
一般歸納法原理過於繁瑣,這裡不再贅述。
語詞集的遞迴性
令 H0:Var∪Const→A,H1:Aai→A,則存在唯一的函數 H:TERM→A 使得:
- 對於所有的變元或常元 t,H(t)=H0(t);
- H(fi(t1,...,tai))=H1(H(t1),...,H(tai))。
構句集的遞迴性
令 Hat:At→A,H□:A2→A,H¬:A→A,H∀:A→A,H∃:A→A,則存在唯一的函數 H:FORM→A 使得:
- 對於所有的原子式 t,H(t)=Hat(t);
- H(t1□t2)=H□(H(t1),H(t2));
- H(¬ϕ)=H¬(H(ϕ));
- H(∀xiϕ)=H∀(H(ϕ));
- H(∃xiϕ)=H∃(H(ϕ))。
定義 2.4 自由變元
TERM:
- FV(ciˉ)=∅;
- FV(xi)={xi};
- FV(fi(t1,...,tai))=FV(t1)∪...∪FV(tai)。
FORM:
- FV(⊥)=∅;
- 若 π 是命題符號,則 FV(π)=∅;
- FV(t1=t2)=FV(t1)∪FV(t2);
- FV(πi(t1,...,tri))=FV(t1)∪...∪FV(tri);
- FV(ϕ□ψ)=FV(ϕ)∪FV(ψ);
- FV(¬ϕ)=FV(ϕ);
- FV(∀xiϕ)=FV(ϕ)∖{xi};
- FV(∃xiϕ)=FV(ϕ)∖{xi}。
定義 2.5 封閉語詞和封閉構句
- 若 FV(t)=∅,則 t 稱為封閉語詞。封閉語詞集合寫作 TERMc。
- 若 FV(ϕ)=∅,則 ϕ 稱為封閉構句或語句。語句集合寫作 SENT。
- 無量詞的構句稱為開放構句。
定義 2.6 拘束變元
TERM:
- BV(ciˉ)=∅;
- BV(xi)=∅;
- BV(fi(t1,...,tai))=BV(t1)∪...∪BV(tai)。
FORM:
- BV(⊥)=∅;
- 若 π 是命題符號,則 BV(π)=∅;
- BV(t1=t2)=BV(t1)∪BV(t2);
- BV(πi(t1,...,tri))=BV(t1)∪...∪BV(tri);
- BV(ϕ□ψ)=BV(ϕ)∪BV(ψ);
- BV(¬ϕ)=BV(ϕ);
- BV(∀xiϕ)=BV(ϕ)∪{xi};
- BV(∃xiϕ)=BV(ϕ)∪{xi}。
定義 2.7 替代
TERM:
令 s 和 t 是兩個語詞,則 s[t/x] 定義如下:
- c[t/x]=c;
- 若 y 不是 x,則 y[t/x]=y;
- 若 y 即是 x,則 y[t/x]=t;
- (f(t1,...,tai))[t/x]=f(t1[t/x],...,tai[t/x])。
FORM 的語詞替代:
令 ϕ 是一個構句,t 是一個語詞,則 ϕ[t/x] 定義如下:
- ⊥[t/x]=⊥;
- 若 π 是命題符號,則 π[t/x]=π;
- (t1=t2)[t/x]=t1[t/x]=t2[t/x];
- (πi(t1,...,tri))[t/x]=πi(t1[t/x],...,tri[t/x]);
- (ϕ□ψ)[t/x]=ϕ[t/x]□ψ[t/x];
- (¬ϕ)[t/x]=¬ϕ[t/x];
- 若 y 不是 x,則 (∀yϕ)[t/x]=∀yϕ[t/x];
- 若 y 即是 x,則 (∀yϕ)[t/x]=∀yϕ;
- 若 y 不是 x,則 (∃yϕ)[t/x]=∃yϕ[t/x];
- 若 y 即是 x,則 (∃yϕ)[t/x]=∃yϕ。
FORM 的構句替代:
令 ϕ 和 ψ 是兩個構句,則 ϕ[ψ/π] 定義如下:
- 若 ϕ 即是 π,則 ϕ[ψ/π]=ψ;
- 若 ϕ 不是 π,但 ϕ 是原子語句,則 ϕ[ψ/π]=ϕ。
- 若 ϕ=ϕ1□ϕ2,則 ϕ[ψ/π]=ϕ1[ψ/π]□ϕ2[ψ/π];
- 若 ϕ=¬ϕ1,則 ϕ[ψ/π]=¬ϕ1[ψ/π];
- 若 ϕ=∀xiϕ1,則 ϕ[ψ/π]=∀xiϕ1[ψ/π];
- 若 ϕ=∃xiϕ1,則 ϕ[ψ/π]=∃xiϕ1[ψ/π]。
定義 2.8 自由語詞
在 ϕ 中,t 對 x 是自由的,代表下述性質之一被滿足:
- ϕ 是原子的,
- ϕ=ϕ1□ϕ2,且 t 對 x 在 ϕ1 或 ϕ2 中是自由的,
- ϕ=¬ϕ1,且 t 對 x 在 ϕ1 中是自由的,
- ϕ=∃yψ,且若 x∈FV(ϕ),則 y∈FV(t) 而 t 對 x 在 ψ 中是自由的。
- ϕ=∀yψ,且若 x∈FV(ϕ),則 y∈FV(t) 而 t 對 x 在 ψ 中是自由的。
引理 2.9
在 ϕ 中,t 對 x 是自由的,當且僅當 ϕ[t/x] 的變數 t 未被量詞拘束。
證明:對 ϕ 做歸納法。
定義 2.10 自由構句
在 σ 中,ϕ 對 π 是自由的,代表下述性質之一被滿足:
- σ 是原子的,
- σ=σ1□σ2,且 ϕ 對 π 在 σ1 或 σ2 中是自由的,
- σ=¬σ1,且 ϕ 對 π 在 σ1 中是自由的,
- σ=∃yψ,且若 π 在 σ 中出現,則 y∈FV(ϕ) 而 ϕ 對 π 在 ψ 中是自由的。
- σ=∀yψ,且若 π 在 σ 中出現,則 y∈FV(ϕ) 而 ϕ 對 π 在 ψ 中是自由的。
引理 2.11
在 σ 中,ϕ 對 π 是自由的,當且僅當 σ[ϕ/π] 的變數 ϕ 未被量詞拘束。
定義 2.12 擴充語言
A 的擴充語言 L(A) 由語言 L、A 的類型加上 ∣A∣ 中的常元所構成。我們將屬於 ∣A∣ 的 a 的常元符號標註為 aˉ。
語義學
定義 2.13 封閉語詞與構句的詮釋
TERMc:
L(A) 在 A 的封閉語詞的詮釋是一個函數 (.)A:TERMc→∣A∣ 滿足(使用 Scott brackets 標記):
- [[ciˉ]]A=ci;
- [[a]]A=a;
- [[Fi(t1,...,tai)]]A=Fi([[t1]]A,...,[[tai]]A)。
SENT:
L(A) 在 A 的語句的詮釋是一個函數 (.)A:SENT→{0,1} 滿足:
- [[⊥]]A=0;
- [[Rˉ]]A=R;
- [[Rˉi(t1,...,tri)]]A=1 當且僅當 [[t1]]A,...,[[tri]]A∈Ri;
- [[t1=t2]]A=1 當且僅當 [[t1]]A=[[t2]]A;
- [[ϕ∧ψ]]A=min([[ϕ]]A,[[ψ]]A);
- [[ϕ∨ψ]]A=max([[ϕ]]A,[[ψ]]A);
- [[ϕ→ψ]]A=max(1,1−[[ϕ]]A+[[ψ]]A);
- [[ϕ↔ψ]]A=1−∣[[ϕ]]A−[[ψ]]A∣;
- [[¬ϕ]]A=1−[[ϕ]]A;
- [[∀xiϕ]]A=mina∈∣A∣[[ϕ[a/xi]]]A;
- [[∃xiϕ]]A=maxa∈∣A∣[[ϕ[a/xi]]]A。
定義 2.14 ⊨
A⊨ϕ 當且僅當 [[ϕ]]A=1。
定義 2.15 宇封閉句 universal closure
令 FV(ϕ)=z1,...,zn,則 Cl(ϕ):=∀z1...zkϕ 是 ϕ 的宇封閉句。
透過宇封閉句,我們可以將詮釋從封閉語句擴展到所有構句,由於對於所有的封閉構句 ψ,Cl(ψ)=ψ,因此這個定義是合法的:
定義 2.16
A⊨ϕ 當且僅當 A⊨Cl(ϕ)。
定義 2.17
- ⊨ϕ 當且僅當 A⊨ϕ 對所有的 A 成立。
- A⊨Σ 當且僅當 A⊨ϕ 對所有的 ϕ∈Σ 成立。
- Γ⊨ϕ 當且僅當若 A⊨Γ,則 A⊨ϕ。
引理 2.18 構句的邏輯意涵
對於語句 ϕ 和 ψ,下列等價性成立:
- A⊨ϕ∧ψ 當且僅當 A⊨ϕ 和 A⊨ψ;
- A⊨ϕ∨ψ 當且僅當 A⊨ϕ 或 A⊨ψ;
- A⊨¬ϕ 當且僅當 A⊨ϕ;
- A⊨ϕ→ψ 當且僅當 A⊨ϕ 蘊含 A⊨ψ;
- A⊨ϕ↔ψ 當且僅當 A⊨ϕ 等價於 A⊨ψ;
- A⊨∀xiϕ 當且僅當 A⊨ϕ[aˉ/xi] 對所有的 a∈∣A∣;
- A⊨∃xiϕ 當且僅當 A⊨ϕ[aˉ/xi] 對某個 a∈∣A∣。
述詞邏輯
定理 2.19 量詞拘束構句的等價性
- ⊨¬∀x¬ϕ↔∃xϕ;
- ⊨¬∃x¬ϕ↔∀xϕ。
定理 2.20 量詞的結構規則
- ⊨∀x∀yϕ↔∀y∀xϕ;
- ⊨∃x∃yϕ↔∃y∃xϕ;
- ⊨∀xϕ↔ϕ,當 x∈FV(ϕ);
- ⊨∃xϕ↔ϕ,當 x∈FV(ϕ)。
定理 2.21 量詞的分配規則
- ⊨∀x(ϕ∧ψ)↔(∀xϕ∧∀xψ);
- ⊨∃x(ϕ∨ψ)↔(∃xϕ∨∃xψ);
- ⊨∀x(ϕ∨ψ)↔(∀xϕ∨ψ),當 x∈FV(ψ);
- ⊨∃x(ϕ∧ψ)↔(∃xϕ∧ψ),當 x∈FV(ψ)。
引理 2.22 替代的交換律
- x∈FV(r) 和 y 是相異變數,則 (t[s/x])[r/y]=(t[r/y])[s[r/y]/x];
- x∈FV(s) 和 y 是相異變數,且 t 和 s 對於 x 和 y 在 ϕ 是自由的,則 (ϕ[t/x])[s/y]=(ϕ[s/y])[t[s/y]/x];
- ψ 對於 π 在 ϕ 是自由的,並且 t 對於 x 在 ϕ 和 ψ 中是自由的,則 (ϕ[ψ/π])[t/x]=(ϕ[t/x])[ψ[t/x]/π];
- ϕ 和 ψ 對於 π1、π2 在 σ 是自由的,ψ 對於 π2 在 ϕ 中是自由的,並且 π1 在 ψ 中沒有出現,則 (σ[ϕ/π1])[ψ/π2]=(σ[ψ/π2])[ϕ[ψ/π2]/π1]。
推論 2.23
- z∈FV(t),則 t[aˉ/x]=(t[z/x])[aˉ/z];
- z∈FV(ϕ) 且 z 對於 x 在 ϕ 中是自由的,則 ϕ[aˉ/x]=(ϕ[z/x])[aˉ/z]。
定理 2.24 拘束變數的變換
若 x 和 y 對於 z 在 ϕ 中是自由的,且 x,y∈FV(ϕ),則 ⊨∃xϕ[x/z]↔∃yϕ[y/z] 且 ⊨∀xϕ[x/z]↔∀yϕ[y/z]。
推論 2.25
所有構句都等價一個沒有變元同時是自由又拘束的構句。
定理 2.26 替代定理
- ⊨t1=t2→s[t1/x]=s[t2/x];
- ⊨t1=t2→(ϕ[t1/x]↔ϕ[t2/x]);
- ⊨(ϕ↔ψ)→(σ[ϕ/π]↔σ[ψ/π])。
推論 2.27
- [[s[t/x]]]=[[s[[[t]]ˉ/x]]];
- [[ϕ[t/x]]]=[[ϕ[[[t]]ˉ/x]]]。
一個構句 ϕ 是前束標準式,當且僅當 ϕ=Q1x1...Qnxnψ,其中 Qi 是量詞,{Qi} 可以是 ∅,ψ 是開放構句,且 x1,...,xn 是互異的變數。
定理 2.29 前束標準句的存在
對於每一個構句 ϕ,存在一個等價的前束標準句。
定義 2.30 一元述詞與量詞作用域 unary predicate and scope of quantifier
若 P 是一個一元述詞符號,則 (∀x∈P)ϕ:=∀x(P(x)→ϕ),(∃x∈P)ϕ:=∃x(P(x)∧ϕ)。