笔记 逻辑学导论 Week4

海勃朗逻辑 Herbrand Logic 是命题逻辑的一个扩展,增加了变量和量词

4.1Syntax 语法

海勃朗逻辑中不含命题常量,而是由三类常量和变量构成
三类常量为:
  1. 对象常量 object constants
  2. 函数常量 function constants
  3. 关系常量 relation constants
参数数量 Arity:函数常量和关系常量都有参数数量这个概念,它表示了一个函数、关系常量所能有点参数的数量。
一个Signature包含如下内容:
  1. 一系列的对象常量
  2. 一系列的函数常量
  3. 一系列的关系常量
  4. 以及上述函数常量和关系常量的参数数量
Term术语
术语可以是变量,可以是对象常量,也可以是一个代表了对象的函数术语
函数术语function term
是一个n-ary的函数包含了n个参数构成的一个表达
g(a,a) g(a,y) g(g(a),y) 可以嵌套
句子包含三类:
  1. 关系句 relational sentence
    由一个n-ary的关系常量包含了n个术语构成
    q(a,a) q(a,y) 不可嵌套
  2. 逻辑句 logical sentence
    与命题逻辑类似 如 p(a) V q
  3. 量句 quantified sentence
    包含全称的和存在的两类
  • 全称句universally quantified sentence
    (x .(p(x)  q(x,x)))
  • 存在句existentially quantified sentence
    (x .(p(x)  q(x,x)))
Ground和non-Ground表达
  • Ground表达不含任何变量
  • non-ground表达是包含了变量的表达
约束变量Bound variable 和自由变量Free variable
在句子∃x.q( x,y)中,x是约束变量,y是自由变量
 
开句open sentence 和 闭句closed sentence
  • 开句是包含了自由变量的句子,如 x.q( x,y)
  • 闭句是不含自由变量的句子,如 x.∀y.qx,y)

42.海勃朗Base

是由语言所能构成的一系列ground关系语句的集合。
 
  • 一个全称句如果要为真,那么需要所有实例都为真
  • 一个存在句如果要为真,那么需要至少有一个实例为真

4.3.海勃朗逻辑验证公式

  1. Law of the Excluded Middle排中律
  2. 1Double Negation双重否定
    2
  3. deMorgan's laws德·摩根定律
    3
  4. Common Quantifier Reversal通用量词逆转
    4
  5. Existential Distribution存在分配
    5
  6. Negation Distribution否定分配
    6

4.4有限海勃朗逻辑 Finite Herbrand Logic

FHL是海勃朗逻辑的一个子集,其中海勃朗base是有限的。FHL是同命题逻辑在表达上等价的。
要求
  1. 有限个对象常量
  2. 不含任何函数常量
将FHL语句转换为命题逻辑语句的步骤:
  1. 转换成前束形式 prenex form
  2. 计算grounding
  3. 用命题常量替代所有的ground关系语句
转换成前束形式 prenex form分三个步骤:
  1. 对不同量句中的变量进行重命名
  2. 利用量词分配规则将量词移至逻辑运算符外
  3. 对所有的自由量词做全称限定
例: y.p( x,y) ∨ ∃ y.q( y)
  1.  y.p( x,y) ∨ ∃ z.q( z).
  2.  y. z.(p (x, y) ∨ q( z)).
  3.  x. y. ∃z .(p( x,y) ∨ q(z))
grounding的计算:从一系列语句Δ开始,逐渐构建grounding Γ,直到Δ为空集为止。
规则:
  1. 如果φ ground则将其从Δ移至Γ
    Δ i+1 Δ i - { φ}
    Γ i+1 Γ i ∪ {φ }
  2. 如果语句是∀ν.φ[ν]的形式,则将语句从Δ 中移除,替换为目标的副本
    Δ i+1 Δ i - {  ν. φ[ ν]} ∪ { φ[ τ] | τ是一个对象常量}
    Γ i+1 Γ i
  3. 如果语句是 ν.φ[ν]的形式,则将语句从Δi中移除,替换为目标副本的相与
    Δi+1 = Δi - {∃ν.φ[ν]} ∪ {φ[τ1] ∨ ... ∨ φ[τn]}
    Γi+1 = Γi
例:{ p(a),  x.(p( x) ⇒ q( x)),  x.¬ q(x)}
Δ 0 = {{ p(a),  x.(p( x) ⇒ q( x)),  x.¬ q(x)}
Γ 0 = {}
 
Δ 1 = { ∀x .(p( x) ⇒ q( x)),  x.¬ q(x)}
Γ 1 = { p(a)}
 
Δ 2 = { p(a) ⇒ q(a), p(b) ⇒ q(b),  x.¬q( x)}
Γ 2 = { p(a)}
 
Δ 3 = { p(b) ⇒ q(b),  x.¬q( x)}
Γ 3 = { p(a), p(a) ⇒ q(a)}
 
Δ 4 = { ∃x .¬q( x)}
Γ 4 = { p(a), p(a) ⇒ q(a), p(b) ⇒ q(b)}
 
Δ 5 = {¬ q(a) ∨ ¬ q(b)}
Γ 5 = { p(a), p(a) ⇒ q(a), p(b) ⇒ q(b)}
 
Δ 6 = {}
Γ 6 = { p(a), p(a) ⇒ q(a), p(b) ⇒ q(b), ¬ q(a) ∨ ¬ q(b)}
 
用命题常量替代所有的ground关系语句
{ pa, pa ⇒ qa, pb ⇒ qb, ¬qa ∨ ¬ qb}
 

4.5 欧米茄海勃朗逻辑Omega Herbrand Logic

OHL是不含函数常量的海勃朗逻辑,与FHL不同的是,OHL可以有无限个对象常量
 
OHL的grounding技术与FHL不同,需要引进一个集合Λ
规则:
  1. 如果φ ground则将其从Δ移至Γ
    Δ i+1 Δ i - { φ}
    Λ i+1 Λ i
    Γ i+1 Γ i ∪ {φ }
  2. 如果语句是∀ν.φ[ν]的形式,将其从Δ移至Λ中,然后在Δ中替换为目标的副本Δ i+1 Δ i - {  ν. φ[ ν]} ∪ { φ[ τ 1], ... , φ[ τ k]}
    Λ i+1 Λ i ∪ { ν. φ[ ν]}
    Γ i+1 Γ i
  3. 如果语句是 ν.φ[ν]的形式,将其从Δ中移除,并且替换为未使用的常量的实例
    Δ i+1 Δ i - {  ν. φ[ ν]} ∪ { φ[ τ]} ∪ { ψ[ τ] |  μ. ψ[ μ∈ Λi }
    Λ i+1 Λ i
    Γ i+1 Γ i
示例:{ p(1),  x.( p(x) ⇒ q(x)),  x.¬q (x)}
 
Δ 0 = { p(1),  x.( p(x) ⇒ q(x)),  x.¬q( x)}
Λ 0 = {}
Γ 0 = {}
 
Δ 1 = { ∀x .(p( x) ⇒ q( x)),  x.¬ q(x)}
Λ 1 = {}
Γ 1 = { p(1)}
 
Δ 2 = { ∃x .¬q( x), p(1) ⇒ q(1)}
Λ 2 = { ∀x .(p( x) ⇒ q( x))}
Γ 2 = { p(1)}
 
Δ 3 = { p(1) ⇒ q(1), ¬ q(2), p(2) ⇒ q(2)}
Λ 3 = { ∀x .(p( x) ⇒ q( x))}
Γ 3 = { p(1)}
 
Δ 4 = {¬ q(2), p(2) ⇒ q(2)}
Λ 4 = { ∀x .(p( x) ⇒ q( x))}
Γ 4 = { p(1), p(1) ⇒ q(1)}
 
Δ 5 = { p(2) ⇒ q(2)}
Λ 5 = { ∀x .(p( x) ⇒ q( x))}
Γ 5 = { p(1), p(1) ⇒ q(1), ¬q(2)}
 
Δ 6 = {}
Λ 6 = { ∀x .(p( x) ⇒ q( x))}
Γ 6 = { p(1), p(1) ⇒ q(1), ¬q(2), p(2) ⇒ q(2)}

Leave a Reply

Your email address will not be published. Required fields are marked *