【面向計算機的數理邏輯/軟體理論基礎筆記】一階謂詞邏輯系統的語義解釋、指派、可滿足性

解釋

• 定義：在命題邏輯中，我們需要對将命題中的複雜的語言符号轉換成我們可以進行計算的邏輯公式，這個過程我們叫做解釋，用符号 I I I表示解釋的内容。
• 在一階語言 L \mathcal{L} L中， L \mathcal{L} L的解釋 I I I的組成如下：
  • 論域：是一個非空的集合，用符合 D I D_I DI​表示。
  • 個體常元：解釋 I I I中所用到的個體常元都包含在論域 D I D_I DI​中，就是解釋 I I I中所用到的這些個體常元 a ˉ i \bar{a}_i aˉi​在論域 D I D_I DI​中都能找到相對應的 a i a_i ai​
  • 謂詞符： L \mathcal{L} L中的謂詞符号 A i n A_i^n Ain​對應與 D I D_I DI​上的 n n n元關系 A ˉ i n ⊆ D I n \bar{A}_i^n \subseteq D_I^n Aˉin​⊆DIn​
  • 函數符： L \mathcal{L} L中的函數符号 f i n f_i^n fin​對應與 D I D_I DI​的 n n n元運算符 f ˉ i n : D I n → D I \bar{f}_i^n:D_I^n \to D_I fˉ​in​:DIn​→DI​
• 例題一：
  • 對于整數語言 L Z \mathcal{L}_Z LZ​的解釋 I I I有：
    • 論域： D I = { 0 , ± 1 , ± 2 , ± 3 , ⋅ ⋅ ⋅ } D_I=\{0,\pm1,\pm2,\pm3, · · · \} DI​={0,±1,±2,±3,⋅⋅⋅}
    • 個體常元： a ˉ = 0 \bar{a}=0 aˉ=0
    • 謂詞符： A 1 2 ˉ : = \bar{A_1^2}:= A12​ˉ​:=“ = = =”， A 2 2 ˉ : = \bar{A_2^2}:= A22​ˉ​:=“ < < <”
    • 函數符： f 1 1 ˉ ( x ) = x + 1 \bar{f_1^1}(x)=x+1 f11​ˉ​(x)=x+1， f 1 2 ˉ ( x , y ) = x + y \bar{f_1^2}(x,y)=x+y f12​ˉ​(x,y)=x+y
  • 問題：說明公式 ( ∀ x 1 ) ( ∀ x 2 ) ( ∃ x 3 ) A 1 2 ( f 2 1 ( x 1 , x 3 ) , x 2 ) (\forall x_1)(\forall x_2)(\exist x_3)A_1^2(f_2^1 (x_1, x_3), x_2) (∀x1​)(∀x2​)(∃x3​)A12​(f21​(x1​,x3​),x2​)的含義
  • 答案：在整數集中，對于任何整數 x x x與 y y y總有整數 z z z使得 x + z = y x + z = y x+z=y

指派（變量代換）

• 定義：設 L \mathcal{L} L是一階語言， I I I是 L \mathcal{L} L的一個解釋， L \mathcal{L} L在 I I I中的指派 v v v是從 L \mathcal{L} L的項集 T \mathcal{T} T到 D I D_I DI​的一個映射，公式表示為：

  v : T → D I v :\mathcal{T} \to D_I v:T→DI​

  • 這個映射公式就是指派的意思，其中
    • v ( a i ) = a i ˉ v(a_i) = \bar{a_i} v(ai​)=ai​ˉ​
    • v ( f i n ( t 1 , t 2 , . . . , t n ) = f i n ˉ ( v ( t 1 ) , v ( t 2 ) , . . . , v ( t n ) ) v(f_i^n (t_1, t_2,..., t_n) = \bar{f_i^n} (v(t_1), v(t_2),..., v(t_n)) v(fin​(t1​,t2​,...,tn​)=fin​ˉ​(v(t1​),v(t2​),...,v(tn​))
• 例題二
  • 自然數語言 L N \mathcal{L}_N LN​中
    • N = { 0 , 1 , 2 , . . . } N=\{ 0,1,2,... \} N={0,1,2,...}
    • 指派 v : T → D I v :\mathcal{T} \to D_I v:T→DI​滿足
      • v ( a ) = 0 v(a)=0 v(a)=0
      • v ( f 1 1 ( x ) ) = f 1 1 ˉ ( v ( x ) ) = v ( x ) + 1 v(f_1^1(x))=\bar{f_1^1}(v(x))=v(x)+1 v(f11​(x))=f11​ˉ​(v(x))=v(x)+1
      • v ( f 1 2 ( x , y ) ) = f 1 2 ˉ ( v ( x ) , v ( y ) ) = v ( x ) + v ( y ) v(f_1^2(x,y))=\bar{f_1^2}(v(x),v(y))=v(x)+v(y) v(f12​(x,y))=f12​ˉ​(v(x),v(y))=v(x)+v(y)
      • v ( f 2 2 ( x , y ) ) = f 2 2 ˉ ( v ( x ) , v ( y ) ) = v ( x ) × v ( y ) v(f_2^2(x,y))=\bar{f_2^2}(v(x),v(y))=v(x)\times v(y) v(f22​(x,y))=f22​ˉ​(v(x),v(y))=v(x)×v(y)
  • 問題：若 v ( x 1 ) = 1 , v ( x 2 ) = 2 v(x_1)=1,v(x_2)=2 v(x1​)=1,v(x2​)=2，那麼 v ( f 1 2 ( x 1 , x 2 ) ) v(f_1^2(x_1,x_2)) v(f12​(x1​,x2​))等于多少
  • 答案： v ( f 1 2 ( x 1 , x 2 ) ) = f 1 2 ˉ ( v ( x 1 ) , v ( x 2 ) ) = v ( x 1 ) + v ( x 2 ) = 1 + 2 = 3 v(f_1^2(x_1,x_2))=\bar{f_1^2}(v(x_1),v(x_2))=v(x_1)+v(x_2)=1+2=3 v(f12​(x1​,x2​))=f12​ˉ​(v(x1​),v(x2​))=v(x1​)+v(x2​)=1+2=3
• 等價指派：指派 v v v的 i − i- i−等價指派 v ′ v′ v′也是一個指派，且滿足對于任意的 j j j，當 j ≠ i , v ′ ( x j ) = v ( x j ) j \neq i, v′(x_j ) = v(x_j ) j​=i,v′(xj​)=v(xj​)，其中 x i , x j x_i,x_j xi​,xj​都是一階語言 L \mathcal{L} L的變量
  • 應用：
    • 設 v ⊨ ( ∀ x i ) A v \models (\forall x_i)A v⊨(∀xi​)A，則對于 v v v的任意 i − i- i−等價指派 w w w都有 w ⊨ A w \models A w⊨A
    • 設 v ⊨ ( ∃ x i ) A v \models (\exists x_i)A v⊨(∃xi​)A，則存在 v v v的 i − i- i−等價指派 w w w有 w ⊨ A w \models A w⊨A
    • 設 v ⊨ ( ∀ x i ) A v \models (\forall x_i)A v⊨(∀xi​)A，則對于 v v v的任意 i − i- i−等價指派 v v v有 v ⊨ A v \models A v⊨A

    或者寫作：

    • 設 v ⊨ ( ∀ x i ) A ( x i ) v \models (\forall x_i)A(x_i) v⊨(∀xi​)A(xi​)，則對于 v v v的任意 i − i- i−等價指派 w w w都有 w ⊨ A ( x i ) w \models A(x_i) w⊨A(xi​)
    • 設 v ⊨ ( ∃ x i ) A ( x i ) v \models (\exists x_i)A(x_i) v⊨(∃xi​)A(xi​)，則存在 v v v的 i − i- i−等價指派 w w w有 w ⊨ A ( x i ) w \models A(x_i) w⊨A(xi​)
    • 設 v ⊨ ( ∀ x i ) A ( x i ) v \models (\forall x_i)A(x_i) v⊨(∀xi​)A(xi​)，則對于 v v v的任意 i − i- i−等價指派 v v v有 v ⊨ A ( x i ) v \models A(x_i) v⊨A(xi​)

  v ′ v' v′是與 v v v的 i − i- i−等價指派，反映了 “差的不多”的意思，即它們的指派最多隻能在 i i i處不同（也就是除在 j ≠ i j \neq i j​=i的時候都相同），其他地方的指派必須完全一樣（就是 v ′ ( x j ) = v ( x j ) v′(x_j ) = v(x_j ) v′(xj​)=v(xj​)），如果 i i i處的指派相同當然也可以。

• 設 v v v是一階語言 L \mathcal{L} L的一個指派， A A A是 L \mathcal{L} L中的一個公式， v ⊨ A v \models A v⊨A（ v v v滿足 A A A）歸納定義為
  • v ⊨ A v \models A v⊨A：若 A A A是原子公式 A i n ( t 1 , t 2 , . . . , t n ) A_i^n (t_1, t_2,..., t_n) Ain​(t1​,t2​,...,tn​)，當且僅當 ( v ( t 1 ) , v ( t 2 ) , . . . , v ( t n ) ) ∈ A i n ˉ (v(t_1), v(t_2),..., v(t_n)) \in \bar{A_i^n} (v(t1​),v(t2​),...,v(tn​))∈Ain​ˉ​（即 A i n ˉ ( v ( t 1 ) , v ( t 2 ) , . . . , v ( t n ) ) \bar{A_i^n}(v(t_1), v(t_2),..., v(t_n)) Ain​ˉ​(v(t1​),v(t2​),...,v(tn​))結果為真）時， v ⊨ A v \models A v⊨A成立
  • v ⊨ ¬ A v \models \neg A v⊨¬A：當且僅當 v ⊭ A v \nvDash A v⊭A（即 v v v不滿足 A A A）時， v ⊨ ¬ A v \models \neg A v⊨¬A成立
  • v ⊨ A → B v \models A \to B v⊨A→B：當且僅當若 v ⊨ A v \models A v⊨A則 v ⊨ B v \models B v⊨B成立時， v ⊨ A → B v \models A \to B v⊨A→B成立
  • v ⊨ ( ∀ x i ) A v \models (\forall x_i)A v⊨(∀xi​)A：當且僅當對于每一個與 v v v的 i − i- i−等價指派 v ′ v′ v′都有 v ′ ⊨ A v′ \models A v′⊨A
• 指派的滿足性：由歸納定義可知，任一公式 A A A以及任一指派 v v v, v v v滿足 A A A與 v v v滿足 ¬ A \neg A ¬A二者有一個且隻有一個成立，是以我們通常約定，若 v v v滿足 A A A，則 v ( A ) = 1 v(A) = 1 v(A)=1，若 v v v不滿足 A A A，則 v ( A ) = 0 v(A) = 0 v(A)=0。
  • 是以，則有
    • v ( ¬ A ) = ¬ v ( A ) v(\neg A)=\neg v(A) v(¬A)=¬v(A)
    • v ( A → B ) = v ( A ) → v ( B ) v(A \to B) =v(A)\to v(B) v(A→B)=v(A)→v(B)
    • v ( ( ∀ x i ) A ) = ∧ { v ′ ( A ) ∣ v ′ v((\forall x_i)A)=\wedge \{v'(A)|v' v((∀xi​)A)=∧{v′(A)∣v′與 v v v的 i − i- i−等價 } \} }
  • 對于其他邏輯算子，容易得到
    • v ⊨ A ∨ B v \models A \vee B v⊨A∨B 當且僅當 v ⊨ A v \models A v⊨A或 v ⊨ B v \models B v⊨B成立
    • v ⊨ A ∧ B v \models A \wedge B v⊨A∧B 當且僅當 v ⊨ A v \models A v⊨A和 v ⊨ B v \models B v⊨B都成立
    • v ⊨ ( ∃ x i ) A v \models (\exists x_i)A v⊨(∃xi​)A 當且僅當存在一個與 v v v的 i − i- i−等價指派 v ′ v′ v′使得 v ′ ⊨ A v′ \models A v′⊨A
• 例題三
  • 自然數語言 L N \mathcal{L}_N LN​中， a a a是 L N \mathcal{L}_N LN​的個體常元
  • 設公式 A = A 1 2 ( f 1 2 ( x 1 , x 2 ) , f 2 2 ( x 1 , x 2 ) ) A = A_1^2(f_1^2 (x_1, x_2), f_2^2 (x_1, x_2)) A=A12​(f12​(x1​,x2​),f22​(x1​,x2​))
  • 解釋 I I I為：
    • v ( f 1 2 ( x , y ) ) = f 1 2 ˉ ( v ( x ) , v ( y ) ) = v ( x ) + v ( y ) v(f_1^2(x,y))=\bar{f_1^2}(v(x),v(y))=v(x)+v(y) v(f12​(x,y))=f12​ˉ​(v(x),v(y))=v(x)+v(y)
    • v ( f 2 2 ( x , y ) ) = f 2 2 ˉ ( v ( x ) , v ( y ) ) = v ( x ) × v ( y ) v(f_2^2(x,y))=\bar{f_2^2}(v(x),v(y))=v(x)\times v(y) v(f22​(x,y))=f22​ˉ​(v(x),v(y))=v(x)×v(y)
    • A 1 2 ˉ : = \bar{A_1^2}:= A12​ˉ​:=“ = = =”。
  • 問題：
    • 問題1：若定義指派 v v v為 v ( a ) = 0 , v ( x i ) = i v(a) = 0, v(x_i) = i v(a)=0,v(xi​)=i，則 v v v是否滿足 A A A
    • 問題2：若定義指派 v ′ v' v′為 v ′ ( a ) = 0 , v ′ ( x i ) = i v'(a) = 0, v'(x_i) = i v′(a)=0,v′(xi​)=i，則 v ′ v' v′是否滿足 A A A
  • 答案：

    • 問題1答案：

      f 1 2 ( x 1 , x 2 ) = v ( x 1 ) + v ( x 2 ) = 1 + 2 = 3 f_1^2(x_1,x_2)=v(x_1)+v(x_2)=1+2=3 f12​(x1​,x2​)=v(x1​)+v(x2​)=1+2=3

      f 2 2 ( x 1 , x 2 ) = v ( x 1 ) × v ( x 2 ) = 1 × 2 = 2 f_2^2(x_1,x_2)=v(x_1)\times v(x_2)=1\times 2=2 f22​(x1​,x2​)=v(x1​)×v(x2​)=1×2=2

      A = A 1 2 ( f 1 2 ( x 1 , x 2 ) , f 2 2 ( x 1 , x 2 ) ) = A 1 2 ( 3 , 2 ) = ( 3 = 2 ) = 0 A = A_1^2(f_1^2(x_1,x_2),f_2^2(x_1,x_2))=A_1^2(3,2)=(3=2)=0 A=A12​(f12​(x1​,x2​),f22​(x1​,x2​))=A12​(3,2)=(3=2)=0

      因為 A A A的最終結果為 0 0 0，是以 v ⊭ A v \nvDash A v⊭A

    這裡(3=2)表示判斷3是否等于2，因為不相等，是以結果為0

    • 問題2答案：

      f 1 2 ( x 1 , x 2 ) = v ( x 1 ) + v ( x 2 ) = 2 + 2 = 4 f_1^2(x_1,x_2)=v(x_1)+v(x_2)=2+2=4 f12​(x1​,x2​)=v(x1​)+v(x2​)=2+2=4

      f 2 2 ( x 1 , x 2 ) = v ( x 1 ) × v ( x 2 ) = 2 × 2 = 4 f_2^2(x_1,x_2)=v(x_1)\times v(x_2)=2\times 2=4 f22​(x1​,x2​)=v(x1​)×v(x2​)=2×2=4

      A = A 1 2 ( f 1 2 ( x 1 , x 2 ) , f 2 2 ( x 1 , x 2 ) ) = A 1 2 ( 3 , 2 ) = ( 4 = 4 ) = 1 A = A_1^2(f_1^2(x_1,x_2),f_2^2(x_1,x_2))=A_1^2(3,2)=(4=4)=1 A=A12​(f12​(x1​,x2​),f22​(x1​,x2​))=A12​(3,2)=(4=4)=1

      因為 A A A的最終結果為 1 1 1，是以 v ⊨ A v \models A v⊨A

• 例題四
  • 設公式 B = ( ∀ x 1 ) ( x 1 ≥ x 2 ) B = (\forall x_1)(x_1 \geq x_2) B=(∀x1​)(x1​≥x2​)
  • 問題：
    • 問題1：定義指派 v ( x 1 ) = 3 v(x_1) = 3 v(x1​)=3， v ( x 2 ) = 0 v(x_2) = 0 v(x2​)=0，則 v v v是否滿足 A A A
    • 問題2：定義指派 v ′ ( x 1 ) = 3 v′(x_1) = 3 v′(x1​)=3， v ′ ( x 2 ) = 3 v′(x_2) = 3 v′(x2​)=3，則 v v v是否滿足 A A A
  • 答案：
    • 因為已經對 x 1 x_1 x1​和 x 2 x_2 x2​進行指派，是以我們直接将他們的值拿去比較即可
    • 問題1答案： 3 ≥ 0 3 \geq 0 3≥0結果是正确的，此時 B = 1 B=1 B=1，是以是以 v ⊨ B v \models B v⊨B
    • 問題2答案： 3 ≥ 3 3 \geq 3 3≥3結果是錯誤的，此時 B = 0 B=0 B=0，是以是以 v ⊭ B v \nvDash B v⊭B

• 對于給定的一個公式，在同一解釋下，可能有兩個不同的指派分别滿足或不滿足該公式；
• 在不同解釋下, 可能一個解釋下的所有指派都滿足該公式，而另一解釋下有指派不滿足該公式。

• 項替換定理

  • 定義：設 L \mathcal{L} L是一階語言， I I I是 L \mathcal{L} L的一個解釋， A ( x i ) A(x_i) A(xi​)是屬于 F ( L ) \mathcal{F(L)} F(L)的一個公式， x i x_i xi​是 A ( x i ) A(x_i) A(xi​)的自由變元。設項 t t t關于 x i x_i xi​自由， v v v是 L \mathcal{L} L在 I I I中的指派， v ′ v′ v′是與 v v v的 i − i- i−等價指派，且 v ′ ( x i ) = v ( t ) v′(x_i) = v(t) v′(xi​)=v(t)，則

    v ⊨ A ( t ) 當 且 僅 當 v ′ ⊨ A ( x i ) v \models A(t) 當且僅當v′ \models A(x_i) v⊨A(t)當且僅當v′⊨A(xi​)

  • 推論：

    v ⊨ ( ∃ x i ) A ( x i ) 當 且 僅 當 有 個 體 常 元 c 使 得 v ⊨ A ( c ) v \models (\exists x_i)A(x_i) 當且僅當有個體常元c使得v \models A(c) v⊨(∃xi​)A(xi​)當且僅當有個體常元c使得v⊨A(c)

• 自由變元重要性定理

  • 定義：設 L \mathcal{L} L是一階語言， I I I是 L \mathcal{L} L的一個解釋， A ∈ F ( L ) A \in \mathcal{F(L)} A∈F(L)， v , w v, w v,w是 I I I中的兩個指派. 若對于 A A A中的每個自由變元 x i x_i xi​都有 v ( x i ) = w ( x i ) v(x_i) = w(x_i) v(xi​)=w(xi​)，則

    w ⊨ A 當 且 僅 當 v ⊨ A w \models A當且僅當v \models A w⊨A當且僅當v⊨A

公式的可滿足性

• 定義：設 L \mathcal{L} L是一階語言， I I I是 L \mathcal{L} L的一個解釋， A ∈ F ( L ) A \in \mathcal{F(L)} A∈F(L)。若對 I I I中的每個指派 v v v，都有 v ⊨ A v \models A v⊨A，則稱 A A A是可滿足的， I I I是 A A A的一個模型, 記作 I ⊨ A I \models A I⊨A(稱 A A A關于 I I I是真公式)。沒有模型的公式稱為不可滿足的。

  • 解釋 I I I滿足公式 A A A是一個整體性概念，與單個指派 v v v滿足 A A A完全不同
  • 對于任一個解釋 I I I而言， I I I不可能同時是 A A A與 ¬ A \neg A ¬A的模型，即 A ∧ ¬ A A \wedge \neg A A∧¬A沒有模型

• 定理：
  • 若 I ⊨ A → B I \models A \to B I⊨A→B且 I ⊨ A I \models A I⊨A，則 I ⊨ B I \models B I⊨B
  • I ⊨ A → B I \models A \to B I⊨A→B且 I ⊨ B → C I \models B \to C I⊨B→C，則 I ⊨ A → C I \models A \to C I⊨A→C
  • I ⊨ A ∧ B 當 且 僅 當 I ⊨ A 且 I ⊨ B I \models A \wedge B 當且僅當 I \models A 且 I \models B I⊨A∧B當且僅當I⊨A且I⊨B
  • I ⊨ A 或 I ⊨ B 可 以 推 出 I ⊨ A ∨ B I\models A 或 I \models B 可以推出 I \models A \vee B I⊨A或I⊨B可以推出I⊨A∨B
  • 若 I ⊨ A I \models A I⊨A則 I ⊨ ( ∃ x i ) A I \models (\exists x_i)A I⊨(∃xi​)A
  • I ⊨ A 當 且 僅 當 I ⊨ ( ∀ x i ) A I \models A 當且僅當 I \models (\forall x_i)A I⊨A當且僅當I⊨(∀xi​)A
  • I ⊨ A 當 且 僅 當 I ⊨ ( ∀ y 1 ) ( ∀ y 2 ) ⋅ ⋅ ⋅ ( ∀ y n ) A I \models A 當且僅當 I \models (\forall y_1)(\forall y_2)· · ·(\forall y_n)A I⊨A當且僅當I⊨(∀y1​)(∀y2​)⋅⋅⋅(∀yn​)A

鞏固習題

（習題摘自《軟體理論基礎》32頁，第二章第 2.2小節習題）

• 習題一：

  • 設 L \mathcal{L} L是一階語言，它有 1 1 1個個體常元 a 1 a1 a1， 1 1 1個函數符 f 1 2 f_1^2 f12​和 1 1 1個謂詞符 A 1 2 A_1^2 A12​，設公式 A A A為

    ( ∀ x 1 ) ( A 1 2 ( x 1 , a 1 ) → A 1 2 ( f 1 2 ( x 1 , x 1 ) , a 1 ) ) (\forall x_1)(A_1^2(x_1,a_1)\to A_1^2(f_1^2(x_1,x_1),a_1)) (∀x1​)(A12​(x1​,a1​)→A12​(f12​(x1​,x1​),a1​))

    \qquad (a)設 L \mathcal{L} L的解釋 I I I的解釋域 D I D_I DI​是整數集合 Z , a 1 ˉ = 0 , f 1 2 ˉ ( x , y ) = x × y , A 1 2 ˉ ( x , y ) Z,\bar{a_1} = 0, \bar{f_1^2}(x, y) = x \times y,\bar{A_1^2}(x, y) Z,a1​ˉ​=0,f12​ˉ​(x,y)=x×y,A12​ˉ​(x,y)為 x < y x < y x<y，問公式 A A A在此解釋下的意義是什麼？是真是假？

    \qquad (b)把解釋 I I I稍作改變，記為 I ′ I' I′，設 f 1 2 ˉ ( x , y ) = x + y \bar{f_1^2}(x, y) = x + y f12​ˉ​(x,y)=x+y，其餘不變，問公式 A A A在此解釋 I ′ I' I′下的意義是什麼？是真是假？

    \qquad (c)把解釋 I I I稍作改變，記為 I ′ ′ I'' I′′，設 A 1 2 ˉ ( x , y ) \bar{A_1^2}(x, y) A12​ˉ​(x,y)表示 x = y x = y x=y，其餘不變，問公式 A A A在此解釋 I ′ ′ I'' I′′下的意義是什麼？是真是假？

  • 答案：

    \qquad (a)将解釋帶入後，公式變為： ( ∀ x 1 ) ( ( x 1 < 0 ) → ( x 1 × x 1 < 0 ) ) (\forall x_1)((x_1 < 0)\to (x_1 \times x_1< 0)) (∀x1​)((x1​<0)→(x1​×x1​<0))，公式意義為：對于任意的 x 1 x_1 x1​都有當 x 1 x_1 x1​小于零時， x 1 × x 1 x_1 \times x_1 x1​×x1​也小于零。當 x 1 x_1 x1​小于零時， x 1 x_1 x1​為負數，兩個負數相乘，結果為正數，是以 x 1 × x 1 < 0 x_1 \times x_1< 0 x1​×x1​<0是錯誤的，是以公式 A A A在此解釋下為假。

    \qquad (b)将解釋帶入後，公式變為： ( ∀ x 1 ) ( ( x 1 < 0 ) → ( x 1 + x 1 < 0 ) ) (\forall x_1)((x_1 < 0)\to (x_1 + x_1< 0)) (∀x1​)((x1​<0)→(x1​+x1​<0))，公式意義為：對于任意的 x 1 x_1 x1​都有當 x 1 x_1 x1​小于零時， x 1 + x 1 x_1 + x_1 x1​+x1​也小于零。當 x 1 x_1 x1​小于零時， x 1 x_1 x1​為負數，兩個負數相加，結果依然為負數，是以 x 1 + x 1 < 0 x_1 + x_1< 0 x1​+x1​<0是正确的，是以公式 A A A在此解釋下為真。

    \qquad (c)将解釋帶入後，公式變為： ( ∀ x 1 ) ( ( x 1 = 0 ) → ( x 1 × x 1 = 0 ) ) (\forall x_1)((x_1 = 0)\to (x_1 \times x_1= 0)) (∀x1​)((x1​=0)→(x1​×x1​=0))，公式意義為：對于任意的 x 1 x_1 x1​都有當 x 1 x_1 x1​等于零時， x 1 × x 1 x_1 \times x_1 x1​×x1​也等于零。當 x 1 x_1 x1​等于零時， x 1 x_1 x1​為零，兩個零相乘，結果仍然為零，是以 x 1 × x 1 = 0 x_1 \times x_1= 0 x1​×x1​=0是正确的，是以公式 A A A在此解釋下為真。

• 習題二：

  • 設一階語言 L \mathcal{L} L中的公式 A A A為

    ( ∀ x 1 ) ( A 1 1 ( x 1 ) → A 1 1 ( f 1 1 ( x 1 ) ) ) (\forall x_1)(A_1^1(x_1)\to A_1^1(f_1^1(x_1))) (∀x1​)(A11​(x1​)→A11​(f11​(x1​)))

    公式 B B B為

    ( ∀ x 1 ) ( A 1 2 ( x 1 , x 2 ) → A 1 2 ( x 1 , x 2 ) ) (\forall x_1)(A_1^2(x_1,x_2)\to A_1^2(x_1,x_2)) (∀x1​)(A12​(x1​,x2​)→A12​(x1​,x2​))

    試分别作出不同的解釋，使 A A A與 B B B有時為真，有時為假。

  • 答案：
    • 對于公式 A A A：
      • 設 L \mathcal{L} L的解釋 I I I的解釋域 D I D_I DI​是整數集合 Z , f 1 1 ˉ ( x ) = x , A 1 1 ˉ ( x ) Z, \bar{f_1^1}(x) = x, \bar{A_1^1}(x) Z,f11​ˉ​(x)=x,A11​ˉ​(x)為 x < 0 x < 0 x<0，則此時公式 A A A在解釋 I I I下變為 ( ∀ x 1 ) ( ( x 1 < 0 ) → ( x 1 < 0 ) ) (\forall x_1)((x_1 < 0) \to (x_1 < 0)) (∀x1​)((x1​<0)→(x1​<0))，可以看出公式 A A A為真；
      • 設 L \mathcal{L} L的解釋 I I I的解釋域 D I D_I DI​是整數集合 Z , f 1 2 ˉ ( x ) = − x , A 1 2 ˉ ( x ) Z, \bar{f_1^2}(x) = -x, \bar{A_1^2}(x) Z,f12​ˉ​(x)=−x,A12​ˉ​(x)為 x < 0 x < 0 x<0，則此時公式 A A A在解釋 I I I下變為 ( ∀ x 1 ) ( ( x 1 < 0 ) → ( − x 1 < 0 ) ) (\forall x_1)((x_1 < 0) \to (-x_1 < 0)) (∀x1​)((x1​<0)→(−x1​<0))，可以看出公式 A A A為假；
    • 對于公式 B B B：
      • 設 L \mathcal{L} L的解釋 I I I的解釋域 D I D_I DI​是整數集合 Z , A 1 2 ˉ ( x 1 , x 2 ) Z, \bar{A_1^2}(x_1,x_2) Z,A12​ˉ​(x1​,x2​)為 x 1 < x 2 x_1 < x_2 x1​<x2​，則此時公式 A A A在解釋 I I I下變為 ( ∀ x 1 ) ( ( x 1 < x 2 ) → ( x 2 < x 1 ) ) (\forall x_1)((x_1 < x_2) \to (x_2 < x_1)) (∀x1​)((x1​<x2​)→(x2​<x1​))，可以看出公式 B B B為假；
      • 設 L \mathcal{L} L的解釋 I I I的解釋域 D I D_I DI​是整數集合 Z , A 1 2 ˉ ( x 1 , x 2 ) Z, \bar{A_1^2}(x_1,x_2) Z,A12​ˉ​(x1​,x2​)為 x 1 = x 2 x_1 = x_2 x1​=x2​，則此時公式 A A A在解釋 I I I下變為 ( ∀ x 1 ) ( ( x 1 = x 2 ) → ( x 2 = x 1 ) ) (\forall x_1)((x_1 = x_2) \to (x_2 = x_1)) (∀x1​)((x1​=x2​)→(x2​=x1​))，可以看出公式 B B B為真；
• 習題三：
  • 證明：在任何一階語言 L \mathcal{L} L中，公式 ( ∀ x i ) A ( x i ) → A ( x i ) (\forall x_i)A(x_i) \to A(x_i) (∀xi​)A(xi​)→A(xi​)在 L \mathcal{L} L的任何解釋下都真的。
  • 答案：
    • 證明：設 I I I是 L \mathcal{L} L的任一解釋， v v v是 L \mathcal{L} L在 I I I下的任一指派，再設 v ⊨ ( ∀ x i ) A v \models (\forall x_i)A v⊨(∀xi​)A，則對于 v v v任一 i − i- i−等價指派 w w w都有 w ⊨ A w \models A w⊨A，而 v v v是自身的 i − i- i−等價于，是以 v ⊨ A v \models A v⊨A。 這表明 v ⊨ ( ∀ x i ) A → A v \models (\forall x_i)A \to A v⊨(∀xi​)A→A。故 ( ∀ x i ) A → A (\forall x_i)A \to A (∀xi​)A→A是邏輯有效的。
    • 解釋：假設有一個關于 v v v的 i − i- i−指派等價 w w w，那麼因為 v ⊨ ( ∀ x i ) A v \models (\forall x_i)A v⊨(∀xi​)A，是以這個 i − i- i−指派等價 w ⊨ A w \models A w⊨A，是以，我們假設這個 w w w就是 v v v本身，進而 v ⊨ A v \models A v⊨A( v v v的 i − i- i−等價指派可以是自身)，是以，我們由 v ⊨ ( ∀ x i ) A v \models (\forall x_i)A v⊨(∀xi​)A得到了 v ⊨ A v \models A v⊨A。故 ( ∀ x i ) A → A (\forall x_i)A \to A (∀xi​)A→A是邏輯有效的。