Category Archives: Logic

笔记 逻辑学导论 Week6

课程地址 https://class.coursera.org/intrologic-003/class/index

1归纳

归纳是由特殊到一半的推理,即如果一个模式的各个实例都为真,则会让人尝试想用一个全称量词来限定这个模式。
  • 不完全归纳是在不检验所有实例情况下做出的归纳。
  • 完全归纳则是在检验所有情况后作出的归纳。

2有限归纳

对于一个有限语言,如果我们知道所有的实例都为真,则可以用一个全称两次来限定这个模式。
例,对于一个由对象常量σ1, ... , σn,如果我们知道φ[σ 1]...φ [σ n]均为真,则可以归纳出ν.φ[ν]。
这一规则叫有限闭合域规则(Finite Domain Closure)简称DC

3线性归纳 Linear Induction

如果一个语言只由一个对象常量a和一个单参数函数s构成,则虽然语言是无限的,但是可以利用线性归纳规则进行归纳。
li

4树型归纳 Tree Induction

如果一个语言由一个对象常量a和两个单参数函数f和g构成,语言也是无限的,可以利用树型归纳规则来进行归纳。
tt
ti

5 结构化归纳

是最普遍的归纳。规则如下
si
可以用这样的案例理解:
如果已知盐酸和硫酸是两种酸,又知道,对于任意两种酸,将他们混合后的得到的必然也是酸,则可以归纳出,一切酸都是酸(不太准确,待重新思考)
作业思路:
9.2 是有限闭合域,要归纳出对一切X均成立,则需要得出对于X的四个实例都要成立。
9.4 主要在于UE规则使用时可以用任何能替代X的术语替代X。

笔记 逻辑学导论 Week5

课程地址 https://class.coursera.org/intrologic-003/class/index

1海勃朗逻辑证明

当且仅当满足一些列前提的真值指派都能够同样满足结论时,我们说这一系列的前提能够在逻辑上蕴含这个结论。
因为海勃朗逻辑中有函数常量,因而真值指派的可能数量是无限大的。(函数可以嵌套)通过罗列各种真值指派情况的方式也是可以用来判但蕴含是否成立,但是通常需要一些限制。

2证明

海勃朗逻辑中的形式化证明同命题逻辑中类似,因为量词的存在,需要四条新的规则:

规则1Universal Introduction (UI)

UI

从任意语句到这些语句的全称量化版的语句
注v不能在φ或者任何一个当前假设中free.例如,我们通过假设p(x)获得了q(x),但是不能得出∀x.q(x),而只能先有II得到p(x)=>q(x)然后得到∀x.(p(x)=>q(x))
例:hates(jane,y)可以推出∀y.hates(jane,y),或∀x.hates(jane,y)

规则2 Universal Elimination (UE)

从一般到特殊
UE
 
注τ一定要能够替代φ中变量v
例:x.hates (jane,x)可以推出hates(jane,x)或hates(jane,y)或hates(jane,jill)

规则3 Existential Introduction (EI)

EI

注v不能在φ中出现.
例:hates(jill,jill)可以推出x.hates (x,x)或x.hates (jill,x)或y.hates (x,jill)等

规则4 Existential Elimination (EE).

EE

注:v不可出现于ψ中
例:已知x.(hates (jane,x)  ¬nicejane))和x.hates (jane,x),可得¬nice(jane))。
前提1:如果简恨任何人,则简都不算是好女孩
前提2:存在一个简恨的人
结论:简不是好女孩
一个形式化证明的示例:
给定前提1:所有人都至少爱一个人
和前提2:如果一个人是一个恋爱中的人,则所有的人都爱他;
求证:jack爱jill
ex1
实际上可以证明在给定的前提下,任何人爱任何人。
ex2

3海勃朗归结规则 Herbrand Resolution Principle

海勃朗逻辑中的归结规则同命题逻辑的命题归结规则类似,但是需要一些新的步骤。

4子句模式

海勃朗命题归结只对子句形式(clausal form)的表达可用
转换为子句模式的一般步骤:

第一步 I Implications out

φ  ψ  ¬ φ  ψ
φ  ψ  φ  ¬ψ
φ  ψ   φ  ψ )  (φ  ¬ ψ)

第二步 N negations in

¬¬φ  φ
¬(φ  ψ)  ¬φ  ¬ψ
¬(φ  ψ)  ¬φ  ¬ψ
¬ν .φ → ∃ν φ
¬ν .φ → ∀ν φ

第三步 S Standardize variables

对变量进行重命名,让每一个量词都只为一限定一个变量
x.(px) ⇒ ∃ x.q(x)) → ∀x.(px) ⇒ ∃ y.q(y))

第四步 E Existentials out

分两种情况
情况1,存在量词不在任何一个全称量词的限定中
    则:去除所有的存在量词,用一个新的常量来替代这个变量
    例x.px)  p(a)
情况2,存在量词在一个或多个全称量词的限定中
    则,因为存在量词限定的变量的值可能会受到相关全称量词的值的影响,我们用一个新的函数(以全称量词所限定的变量作为值)来替代存在量词所限定的变量。
    例:x.(px) ∧ ∃ z.q(xyz)) → ∀x.(px)  q(xyf(xy)))

第五步 A Alls out

去掉全称量词
例:x.(px)  q(xyf(xy)))  p(x)  q(xyf(xy))

第六步 D Disjunctions in

将表达式转换成conjunctive normal form
φ  ( ψ  χ )  (φ  ψ)  ( φ  χ )
(φ  ψ)  χ  (φ  χ)  ( ψ  χ )
φ  ( φ1  ...  φn)  φ  φ1  ...  φn
(φ1  ...  φn )  φ  φ 1  ...  φn  φ
φ  ( φ1  ...  φn)  φ  φ1  ...  φn
(φ1  ...  φn )  φ  φ 1  ...  φn  φ

第七步 O Operators out

去除与、或运算符,转变成子句形式
φ1  ...  φn  φ1
                          → ...
                          → φn
φ1  ...  φn  {φ 1, ... , φn}
 
在命题逻辑中任何语句的子句形式都和原语句是逻辑上等价的,但在海勃朗逻辑中并不一定是如此。

5合一 Unification

合一是判断两个表达是否能够通过适当的变量替换而统一起来的一个过程。
一个替换substitution是一个术语到变量的有限映射。
例如:{xay f(b), z v}
被替换的变量构成了替换的领域domain
替换这些变量的术语则构成了替换的范围range
上例中的domain是{x,y,z}range是{a, b, v}
 
当且仅当range内的所有替换术语都对于领域中的变量是自由的时,称一个替换是pure的。
{x←a, y←f(b), z←x}便是一个impure的替换
如果一个替换是pure的,则同样规则替换多次的结果是一致的,如果是impure的,则可能会不一致。
给定两河或更多次替换,可能可以定义一个一次替换达到前面两次或多次替换的效果。
一个合一子unifier如果具有具有最大的广泛性,则称为mgu。对于同样的两个表达,可能有多于一个的最广合一子。
计算最广合一子的步骤:
可能性1如果两个表达是形似的,则不作任何事
可能性2如果两个表达不形似,并且都是由常量构成,则失败,无法替换
可能性3如果两个表达不形似,且其中一个表达是一个变量,
   然 则:检查变量是否有一个限定,如果有,则尝试在第二个表达式中对这个限定进行统一。
   否则:检查第二个表达式是否含有该变量,
         如果是:则失败
         如果不:则尝试对第二个表达式中的变量进行限定
可能性4剩下的情况是两个表达都是一系列的句,则对其中每一项都进行上述转变。
例:p(x,x)和p(a,y).
mgu

6归结规则

与命题逻辑中类似
resolution

factor的概念:
如果一个子句Φ中的literal的一个子集具有一个最广合一子γ,那么通过运用γ对Φ进行替换的结果 Φ'就成为是一个factor.
 

7归结推理Resolution Reasoning

同命题逻辑类似。
 
称一个resolution derivation是对一系列的子句形式前提通过有限步骤的子句终结最终得出结论的过程,其中每一个子句都要么是前提要么是通过对先前存在的子句运用归结规则所得到的子句。
reasoning

8不可满足性 Unsatisfiable

如果一系列子句形式的前提通过有限步骤的归结推理最终得到空集,则表示前提的一系列子句是不可满足的。

9逻辑蕴含

利用不可满足性知道,如果想知道一系列的前提Δ是否蕴含φ的问题,可以转变为判断Δ φ}是否是不可满足的的问题。在海勃朗逻辑中就变成将Δ φ}转变成子句形式,然后判断是否能归结推理出空集的问题。
 
以2中人人爱爱人人的例子为例:
前提为
x. y.loves(xy)
u. v.w .(loves(v,w)  loves(uv))
目标结论为
x. y.loves(xy)
即转变便为
{loves(x,f(x))}
{¬loves(v,w), loves(u,v)}
{¬loves(a,b)}
是否能归结推理出空集的问题
kkk
种种原因本周未能听完,待日后再补了。
作业7.5和7.6的提示:
7.5已知前提AX:(P(X)=>q(X))和EX:P(X)目标结论为EX:q(X),只需提出假设p(X),然后运用新规则去前提的量词限定然后运用老规则得出q(X),再运用新规则加上存在量词限定即可,注意假设后的子证明中的结论不能直接进行UI规则,需要先用II退出子证明。
7.6最后需要用EE,因而可以直接假设前提2中去除EY后的所有内容,主要是在子证明中需要通过AE来拆分语句,核心在于证明f(X,Z)。

笔记 逻辑学导论 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)}

笔记 逻辑学导论 命题归结

课程地址 https://class.coursera.org/intrologic-003/class/index

命题归结Propositional Resolution是命题逻辑中非常给力的推理规则。

1 Clausal Form 子句形式

命题归结只对子句形式的表达适用,因此在使用之前必须将前提和结论转化成子句形式。
一些概念:
一个literal字符可以是一个不可以再分割的原子语句atomic sentence,也可以是一个原子语句的否定。如p和¬p
一个子句表达clause expression可以是一个字符也可以是字符的相与。如¬p V  q
一个子句是用集合包含子句表达中的字符后得到接形式。如{¬p, q}
转化的一般过程为I、N、D、O
  • I:Implication Out
    I
  • N:Negation
    N
  • D: Distribution
    D
  • O: Operators
    O
一个转化示例:
Ex1

2归结规则 Resolution Principle

如果给定一个子句中包含chi并且知道另一个子句中包含chi的否定,则根据归结规则可将两个子句合并起来并同时去除chi和chi的否定。
prrp

3 示例:

给定子句{¬p, r}{¬q,r}{p,q}是否可以推导出结论{r}?
Ex2
4不可满足定理
当且仅当Δ 与 {¬φ}的交集是无法满足的时候Δ |= φ
可以将Δ ∪ {¬φ}写成子句模式,然后看是否能够归结出空集{},如果可以,则表示确实无法满足。

笔记 逻辑学导论 Week3

课程地址 https://class.coursera.org/intrologic-003/class/index

3.1 证明 Proof

逻辑上的证明是对句子进行符号上的操作,而不是枚举所有可能的真值指派来进行判断。其结果必然与通过枚举真值指派的各种情况所得结果是相同的。

分两种类型:
  1. Linear Proof 线性证明
  2. Structured Proof 结构化的证明

3.2 Linear Proof

是从一系列前提出发,根据一系列的推演规则,推导出结论的过程
模式Schema
是一个使用元变量来对满足逻辑语言中语法规则的语句的表达
例:a=>b是模式φ=>ψ的一个实例(instance)
推演规则rule of inference
推演规则由一系列模式(Schema)所构成的推理模式(Pattern),这些模式包括一些前提和一个或更多个结论。
在横线之上写前提,在横线之下写结论:
如Implication Elimination(IE) 写作:
3-1
推演规则的实例是将句子中的元变量用具体的变量来替换掉后所得的结果,如:
3-2

3.3常用的公理集 Axiom Schemata

Mendelson 门德尔森公理集包括四条规则IE、IC、ID和CR
  1. Implication Elimination(IE)
    3-1
  2. Implication Creation schema (IC):
    IC
  3. The Implication Distribution schema (ID):
    ID
  4. The Contradiction Realization schema (CR):
    CR

3.4 Linear proof示例:

前提为p=>q和q=>r问是否能推导出p=>r?
Ex1

3.5结构化证明Structured Proofs

在Structured Proof中我们可以提出假设,但是每次提出假设都将使得假设和假设后得出的语句置于一个subproof的下位句组里,在句组里可以使用一般的推演规则,但是只有使用了结构化的推演规则(II)后才能将得到的结论用于上位句组中。
例:
Ex2

3.6 Fitch

Fitch是一个证明系统,包含了10条推演规则,其中9条是普通推演规则,1条(II)是结构化推演规则
  • AI 和 AE
    AIAE
  • OI 和 OE
    OIOE
  • NI 和 NE
    NINE
  • II 和 IE
    IIIE
  • EI 和 EE
    EIEE

3.7 可靠性和完备性 Soundness and Completeness

可靠性:
当且仅当所有可证明的结论都是逻辑上蕴含的,即
sound
时我们说一个证明系统是可靠的。
完备性:
当且仅当所有逻辑结论都是可被证明的,即
comp
时我们说一个证明系统是完备的。