形式邏輯筆記/第五章

導航：首頁 > 程式語言、邏輯學>形式邏輯筆記> 形式邏輯筆記/第五章

形式語義 (formal semantics)

其中任何一個命題字母，他本身不意味語意，假設我要把「我不是貓」和「我是貓」套用到 X 這個命題字母，那就會有語意指涉的問題了。

因此我們需要知道什麼使命題為真或假，所以需要將真的概念特徵化 (characterization）。

• 元語言：比如自然語言
• 目標語言：比如形式邏輯符號用法

5.1命題邏輯的語義

v(X) = 1 指我們估值 X 為 1（真）或0（偽）。v 是 valuation 函數。

命題如何知道是真的？不只是符號的詮釋而已。假設詮釋是：「今天X咖啡店來了3位客人」，也不一定恆真恆假。要知道其來客量才知道真假。

所以「註解(interpretation)+世界的狀態=真偽」

命題真值賦予：a{P) = 1 若 P 為真（詮釋在這世上為真），0則為假。像是真值表上的一列那樣。

a不是命題邏輯。

真值估值函數 v 定義

• 若A是命題字母，v(A) = a(A)
• 若A是~B對於一些命題B，那麼若 v(B) = 0 則 v(A) = 1 ，否則 v(A) = 0
• 如 A 是 B & C，對於一些命題字母 B, C，則若 v(B) = 1 且 v(c) = 1 則 v(A) = 1，否則v(A) = 0
• 如 A 是 B OR C，對於一些命題字母 B, C，則若 v(B) = 0 且 v(c) = 0 則 v(A) = 0，否則v(A) = 1
• 如 A 是 B -> C，對於一些命題字母 B, C，則若 v(B) = 1 且 v(c) = 0 則 v(A) = 0，否則v(A) = 1
• 如 A 是 B <-> C，對於一些命題字母 B, C，則若 v(B) = v(c) 則 v(A) = 1，否則v(A) = 0

（語義）蘊涵

A蘊涵(entail)B寫成，$A_{1},A_{2},...\models B$，指$A_{i}$為真的情況下，B不可能為假（即也為真）。

• $\models C$：C是恆真句
• ⊨ ¬C：C是矛盾句
• 若兩者都不是，則爲部分為真句。
• 「$P_{1},P_{2},...,\therefore C$是於命題邏輯valid的」↔$P_{1},P_{2},...,\models C$
• 命題邏輯中A, B邏輯等同↔(A⊨B & B⊨A)
• 邏輯一致性的定義：

「${A_{1},A_{2},...}$的集合是命題邏輯裏一致的」↔有至少一個真值賦值，讓所有命題為真。

（若是都沒有，那麼邏輯上是不一致的）

5.2量化邏輯的詮釋與模式(model)

形式的，命題邏輯的語義嚴格的是真值賦值。

若是他們有同樣的真值賦值，兩個註釋是一樣的。

• 謂詞邏輯的解釋是：
  1. 有論域
  2. 謂詞有語義意義
  3. 任何常量指涉的對象

如果拿命題邏輯的語義化來對謂詞邏輯進行語義的詮釋，會犧牲量化詞、謂詞和term的關係。

我們不能用真值表，因為謂詞本身無真和偽。

比如「……是女人」不能保證恆為真。

我們需要使用 extension（外延），就是對於所有 x 中，使謂詞 F x 為真的 x 的集合。比如說：「阿嬌、阿花、小莉……」是「……是女人」的外延。

有些謂詞的 extension 是無限多的。一般而言，謂詞的外延是註釋的結果加上一些事實 (facts)。

有些時候，外延可以列出來，如：

extension(TricolorOfSignal) = {Green, Red, Yellow}。

若是 UD是所有顏色，則∃x TricolorOfSignal(x) 為真，∀x TricolorOfSignal(x)為偽（顏色超過紅黃綠）。

常量的意義決定哪一個UD的成員被挑出來，被挑出來的稱爲常量的 referent。常量字母像人名，referent像指涉的東西。一個常量字母可以指涉同一個referent，就像「岳飛」和「岳鵬舉」指同一個人。

• 集合：{a, b, c, ...}，內容元素不要求順序，空集合寫為∅。

• 模型
  • 包含常數的指涉（函數）、論域 UD、以及謂詞的外延（extension，是枚舉）。類似這樣的形式（其中論域是 UD、謂詞是 H、常數是 f）：
    • UD = {臺北、新北、桃園、台中、臺南、高雄}
    • extension(H) = {臺北, 新北, 桃園}#註：H指在北臺灣
    • f = {臺南}
  • 不需用知道臺灣地理知識就可以推估說 H f 是真的還是假的。
    • 第二個模型
    • UD = {1,2,...,10}
    • N x = N 是負數
      • extension(N) = {}
    • L x y = x 大於 y
      • 這需要用「有序tuple」(ordered tuple)的概念
      • extension(L) = {<10,9>, <10, 8>, ..., <2,1>}

5.3 同一性的語義

• x = y 是謂詞，所有的 UD 的 item 都滿足
• ∀x x = x 是全真句。
• x = y 的 UD 隨模型而異。
• (referent(a) = referent(b)) →(P a = P b, Q a = Q b, ∀ x R x a = R x b)
• 假設有個模型：
  • UD = {Alice, Bob}
  • referent(a) = Alice
  • referent(b) = Bob
  • for all predicate P, extension(P) = {}
  • 因為對於所有的 P，P a 是 false，P b 是 false，¬P a <-> ¬P b 為真，所以 P a <-> P b 為真。
  • 但 a ≠ b。

5.4 處理模型

• QL 的下列三式定義：
  • 全真句：任何模型均爲真，⊨C
  • 矛盾句：任何模型均爲假，⊨¬C
  • 非全真句：不是全真句且不是矛盾句
  • argument $P_{1},P_{2},...,P_{n},\therefore C$ 有效 (valid)↔$\{P_{1},P_{2},...,P_{n}\}\models C$。否則 invalid。
  • A, B 邏輯等同↔A⊨B且B⊨A。
  • 集合{A, B, ...} 具邏輯一致性↔至少有一個模型使得所有命題為真。否則為不一致性。
• 證明 ∀ x A x x -> B d 是非全真句：
  • 首先證明它不是全真句，用部分模型(partial model)證明：
    • UD = {臺北}
    • extension(A) = {<臺北, 臺北>} # x y 是同一座城市
    • extension(B) = {} # B 非城市
    • d = 臺北
    • ∀ x A x x -> B d 是假
  • 再次證明它不是矛盾句：
    • extension(A) = {<臺北, 臺北>} # x y 是同一座城市
    • extension(B) = {臺北} # B 是城市
    • d = 臺北
    • ∀ x A x x -> B d 是真
  • ∃x S x 和∀ x S x 邏輯不等同的證明：
    • UD = {a, b}
    • extension(S) = a
    • 因為∃x S x為真，∀ x S x為假，所以(∃x S x⊨∀ x S x)為假，邏輯故不等同。
• 有時候我們如果要證明一個句子是全真句，要用到所有模型，這不可能完全列舉。

模式推論表

可以證明的敘述 K （¬K不可證）	方法
K非全真句	建構一個K為假的模式
K非矛盾句	建構一個K為真的模式
K是非全真句	建構一個K為假的模式，和另一個K為真的模式
K, L邏輯不等價	建構一個K, L 真假值相異的模式
命題集合A一致	建構一個A中的命題均爲真的模式
P,∴C不成立 (invalid)	建構一個模式，P為真，C為假。

謂詞邏輯的真值

• 我們需要引用「滿足」的概念。
• a(x)，指 UD 有一個變數指派到 x，若是a(x) 在 extension(F)，則∃ x F x滿足 (satisfied)。
• 若是對於所有變量𝐱，以及指代所有論域對象 (object) 的Ω，a[小明|x]代表指代小明這個對象給x，a[Ω|x]指代所有論域的變數於x。
• ∀x P x 在模式𝐌滿足<->P x 在模式𝐌以a[Ω|x]滿足。

形式化定義

• 若A是well-formed formula(wff)，形式為$Pt_{1},t_{2},...,t_{n}$，且$\Omega i$是$t_{i}$挑出來的常數，則滿足函數 s 的公式為：
• s (A, a) =
  • if <$\Omega _{1},...,\Omega _{n}$>在 模式 M 的　extension(P) 裏面，then 1
  • else 0

其中若$t_{i}$是常數，那麼$\Omega _{i}=referent(t_{i})$；若$t_{i}$為變數，則$\Omega _{i}=a(t_{i})$。

若 A = ¬B，B是wff，則

• S(A, a) =
  • if S(B,a) = 0 then 1
  • else 0

若 A = B&C，B, C是wff，則

• S(A, a) =
  • if S(B,a) = 1 and if S(C,a) = 1 then 1
  • else 0

其他運算子可以依此類推。

• 真值
  • 模式M的命題A若爲真↔一些變數指派滿足A於M。
  • 量化邏輯的真值是模型的真值。

ForAll X 形式邏輯筆記

第一章 什麼是邏輯 - 第二章 命題邏輯 - 第三章 真值表 - 第四章 量化邏輯 - 第五章 形式語義- 第六章 證明