`
jishublog
  • 浏览: 861808 次
文章分类
社区版块
存档分类
最新评论

命题逻辑中的语法与语义,可靠性与完备性

 
阅读更多

命题逻辑中的语法与语义,可靠性与完备性

1导言


初学数理逻辑的时候,一个非常重要的点就是对可靠性与完备性概念的理解,这两个概念极为重要,却又经常让人觉得 难以理解。
说它重要是因为它涉及逻辑系统的基本框架,初学数理逻辑,最重要的倒不在于你有多高超的技巧去推导那些 公式,而在于对一些基本概念的理解和把握,这是思想层面的,如同学习概率论和数理统计不在于记住那几个公式和定理, 而在于获得一些基本的概率和统计的思想。TED演讲时,有一次一位在线教育的创始人谈到教育时说到,我们教授学生知识, 不是让他们仅仅记住那些公式,而是改变他们认识世界的方式。请大家一定记住这一点。同时也请注意,这句话不是在说 记住公式没有用。学习数理逻辑,要时刻提醒自己,我们需要去推导定理,但目的不在于此。 可靠性与完备性之所以让人难以理解,原因是多方面的。一方面是初学数理逻辑,根本不知道书上那些定理是要做什么,也 就是前面说的,对知识的整体没有一个宏观的把握,注意:这是教师的责任。另一方面在于对语法和语义不理解,经常将 二者混在一起看。而这一方面的“不理解”,又在于我们将现实世界的逻辑与形式系统中逻辑又混在一起看。 下面就谈一下我对可靠性与完备性的理解。特别需要说明的是,这是针对命题逻辑的,并且我也是初学,很可能有一些错误, 请不怀疑的怀疑,怀疑的指出。
要谈可靠性与完备性,需要先理解语法和语义,把这两个概念弄清楚了,理解可靠性与完备性就会水到渠成。

命题逻辑系统由语法和语义两部分组成。一旦定义了语法和语义,整个逻辑系统也就构建好了。下面我们开始构造命题逻辑系统。


2语法


我们首先从几个问题开始。


2.1语法是什么?


简单地说,语法就是一些规则的集合。那规则又是什么?规则是人为确定的一些原则,许多情况下,规则来源于现实世界, 同时又用于指导对现实世界的理解。我们举一个自然语言语法中的例子:

主语 + 谓语 + 宾语

这就是一个基本的语法规则,而且是人为定义的。在没有这个定义之前,它就存在于语言当中,人们将这种在自然语言中 广泛出现的形式总结成简单的规则,这样方便了我们对语言的学习与利用。我们把一些经常出现的规则集合在一些,就构成了语法。请一定记住,一旦这些规则被从现实世界中剥离出来,它们就有了一定程度的独立性,不信赖于具体的含义。 例如,"我 吃 饭",和 "饭 吃 我"都符合主谓宾结构,我们认为后者不正确不是因为主谓宾结构不对,而是它所表达的意思不正确,这是语义层面,而不是语法层面。


2.2命题逻辑中的语法是什么?


命题逻辑中的语法就是一些自然推导规则(Natural deduction rules)的集合。那自然推导规则又是什么?我们回到现实世界。现实世界中,我们常常会做一些推理。

例如,你肯定能:

从“我喜欢计算机科学,而且我也喜欢数学”中 推理出 “我喜欢计算机科学”。

你也能:

从“我经常编写程序,而且我也经常读书” 中 推理出“我经常编写程序”。

我们并没有意识到自己是在做推理,但是我们确确实实完成了一次推理,确且地说,是两次。并且我们发现这两次推理具有高度统一的形式:

A 而且 B 推出 A

其中的A和B被称作命题。我们可以把命题理解为可以判断真假的句子。
例如,“我喜欢计算机科学”是一个命题,但是“我喜欢文学吗?”就不是一个命题。
对比一下自然语言中语法规则的产生,这一次,我们再次将这些在现实世界中广泛出现的推理形式抽象出来,把他们组成一个集 合,于是,我们就有了下面这组命题逻辑的自然推导规则集合。


图1 命题逻辑的自然推导规则

解释一下这些符号的含义,例如:
φ ∧ ψ
—— ∧ e1
φ
其中的 φ , ψ 我们叫做公式。公式可以是以下这些形式:

p, q, p ∧ q, ¬ q, (p ∧ q) ∨ p, …

其中的 ∧ e1,我们叫做规则。e的意思是消除(elimination). 这条规则从 φ∧ψ 中消除了 ∧,只留下了前面的φ, e1中的 1 就是指 φ,因为它排在第1个,对比一下 ∧ e2就会明白了。

规则中的i表示引入(introduction). 规则的具体含义可参考1.至于其中的 ¬ , →, … ,我认为目前没有必要知道含义,你仅仅需要知道他们是一些推导规则就好了。虽然你们多半都知道含义,但是,现在把它们忘了吧。

请再一次又一次地记住,这些推导规则从现实世界中剥离出来后,就有了他们的独立性,和具体的含义无关,例如:

φ ∧ ψ
–——∧ e1
φ

我们只知道 φ 和 ψ 是命题,有真假,但是,不管他们是真是假,都不影响这条规则的成立。这一点请千万注意。 例如:

φ = "我不喜欢计算机科学" (当然,这是假的)

ψ = "我喜欢数学"

由上面的那条推导规则,可以推出φ,即"我不喜欢计算机科学",尽管这个结论是假的,但这和这条推导规则的成立无关。不能说, 这规则得出假的结论,所以这条规则就是不正确的。


2.3推理和推理的有效性


前面在引入自然推导规则时,我们举了一些例子,如自然语言中的对应形式,包括命题的真假,等等。这一切都是为了 理解这些规则是怎么来的。那么,从现在开始,请忘掉那些例子,让你的知识保留在只知道图1所示的自然推导规则表.我们现在仅仅知道这张规则表,那么,这些规则用来做什么呢? 这些规则可以用来推理。

2.3.1什么是推理

看下面这种形式:

φ12,…,φn|- ψ

这就叫一次推理(sequent).其中 φi叫做前提(premise), ψ 叫做结论(conclusion). 例如,下面这个形式就叫一次推理。

p, ¬¬(q ∧ r) |- ¬¬ p ∧ r

2.3.2什么是推理的有效性

推理有效性的概念与可靠性,完备性直接相关,所以一定保证你理解它的含义。 推理的有效性是指:使用图1中定义的自然推导规则以及前提(φi),可以得出结论(ψ)。

例如我们如果问: p, ¬¬(q ∧ r) |- ¬¬ p ∧ r 是不是有效的,那只需要看我们能不能仅根据自然推导规则,将前提转化为结论。转化的过程,我们叫做:证明(proof).
下面就是这个推导的证明:


图2 证明过程

上面的证明过程,例如第6行,最右面的∧i 3,5 表示使用第3,5行的公式和规则∧i, 得到第6行的公式。

关于语法部分,现在只需要知道两件事:一:公式及自然推导规则表;二:推理和推理的有效性。
下面开始语义部分。


3语义


3.1语义是什么?


简单地说,语义就是语言所表达的含义。同样以自然语言为例:

我吃饭

你很容易知道这句话是什么意思。但是你想过为什么你能知道这句话是什么意思吗
原因在于,首先你知道“我”是什么意思,“饭”是什么意思,其次你知道“吃”是什么意思。最后,你明白“我吃饭”三个字连在一起是什么意思。你可能觉得这是一句废话,但是后面提到命题逻辑时,你可能就会明白为什么在这儿说了一句废话。
关于这句话,还需要有两点要说明:
一是,这句话是一个主谓宾的结构,但是即使你不知道这个句子的语法,你仍然可以知道它的含义。
二是,在主谓宾结构中:

主语和宾语可以取的值其实是一个集合:{我,你,饭,计算机,书,….},

谓语可以取的值也是 一个集合:{吃,看,打,….}.

句子代表的含义也构成一个集合:{我吃饭的含义,我看书的含义,….}.

同时,在 “我吃饭”这个句子与“我吃饭的含义”之间存在着一种映射关系。语义中如果没有这种映射关系,那么你说“我吃饭”的时候, 别人可能觉得你在看书。


3.2命题逻辑中的语义是什么?


要问命题逻辑中的语义是指什么,我们首先需要知道命题逻辑中的语言指什么,如果我们连“句子”的概念都没有,那么我们如何知道“句子的含义”是什么呢?我们需要有这样一种观念,数理逻辑中,这些框架都是由我们人来定义的,如果没有语言, 那么:我们定义它。
对比自然语言中的句子,为什么我能给出

我吃饭

这样的句子呢?因为我知道句子的结构

主语 谓语 宾语

同时,还知道主语,谓语,宾语可以取值的集合

"我" ∈ {我,你,饭,计算机,书,…}

"饭" ∈ {我,你,饭,计算机,书,…}

"吃" ∈ {吃,看,打,…}


所以, 我们得到了一个句子:“我吃饭”。

在命题逻辑中,我们也有自己的“句子结构”,例如:

φ ∧ ψ

之所以没有自己的“句子”,是因为我们的公式 φ, ψ 没有自己的取值的集合,所以,
我们首先定义公式取值的集合:{T,F},T代表真,F代表假。
看到了吧,这和前面讲的“命题是可以判断真假的”是相关的。
有了取值集合,我们就可以定义自己的“句子”了:

T ∧ F

T ∨ T

T → F

我们知道,语义是指句子的含义,现在有了句子了,那么句子的含义是什么呢
从自然语言的例子中,我们知道句子的含义是一个集合,在命题逻辑里,“句子含义”的集合仍然由我们来定义,
命题逻辑中我们只关心真与假,所以,这个集合,我们仍然定义为:{T,F}

好了,现在我们有了“句子”,有了“句子含义”取值的集合,那么定义一个语义系统,还需要 什么呢?同样对比自然语言的例子中,我们最后说的那一点,还需要一种映射,将句子与句子的含义映射起来,即将 T ∧ F 等句子与 T, F映射起来。而这,就是耳熟能详,家喻户晓的, 真值表:


图3 真值表

有了真值表,我们才知道 T ∧ F 意味着什么, F → T 意味着什么。

至此,我们的语义系统就定义好了。


3.3语义蕴含(semantic entailment) 及其有效性


看下面这种形式:
φ1, φ2, …, φn|= ψ
其中的 |= 即表示蕴含关系,从上面语法和语义的讨论中,你可能已经明白了,这只是一种语法层面的定义, 那么蕴含的语义是什么呢?翻译为人话就是:当我说蕴含的时候,我是在说什么。
蕴含就是在说,如果 φ1, φ2, … , φn的取值都为T, 那么 ψ 的取值一定为 T.


例如: p ∧ q , q, r |= p .
当 p ∧ q 为T, q为T,r为T时, P一定为T. 所以 p ∧ q , q, r 蕴含 p.


那么,什么是蕴含的有效性呢?


例如我问: p ∨ q , q, r|= p 是有效的么?
我其实是在问, p ∨ q 为 T, q为T, r为T时, p一定为T么?
如果p一定为T, 那么 p ∨ q , q, r|= p 是有效的。否则,p ∨ q , q, r|= p 是无效的。

所以,如果我说 φ1, φ2, … , φn蕴含 ψ, 意思等同于:
φ1, φ2, …, φn|= ψ 是有效的。


至此,语义部分就介绍到这里。下面,开始介绍可靠性与完备性。


4可靠性与完备性(Soundness and Completeness)


经过了前面冗长的关于语法和语义的介绍,终于可以开始介绍可靠性与完备性了。在此之前,请保证你可以正确区分 |- 和 |= ,知道推理的有效性和语义蕴含的有效性意味着什么。

在完成命题逻辑系统的定义后,我们想知道这个系统的一切性质,其中最重要的性质就是可靠性与完备性。这一节的两个定理告诉我们,命题逻辑系统满足可靠性和完备性。

4.1可靠性(Soundness)


4.1.1可靠性是指什么?

可靠性定理:令 φ1, φ2, …, φn和 ψ 为命题逻辑中的公式,如果 φ1, φ2, …, φn|- ψ 是有效的, 那么 φ1, φ2, …, φn|= ψ 是有效的

这个定理是在说,我们为逻辑系统定义好语法和语义后,如果在语法上,我们可以利用推导规则,将φ1, φ2, …, φn转化为 ψ,

那么在语义上,如果φ1, φ2, …, φn 都为T, 那么ψ一定为T.

4.1.2为什么要引入可靠性的概念?

首先,我们需要理解,可靠性是逻辑系统满足的一个性质。如果有一天,我们构造了另一个逻辑系统,自己定义了 语法,定义了语义,那么,我们可能需要问一下自己:我定义的这个逻辑系统满足可靠性么?
上面的靠性定理是指在命题逻辑中,我们定义了语法:自然推导规则,推导及其有效性;我们定义了语义:真值表,语义蕴含及其有效性。在由这些定义构成的一个命题逻辑系统中,像可靠性定理描述的那样的性质是满足的。一旦我们 证明了一个逻辑系统满足了可靠性,我们就可以利用这个好的性质来做一些事。

4.1.3可靠性有什么用?

现在我们明白了,之前定义的命题逻辑系统满足可靠性。现在,我们就可以利用这一点来做一点事了。
我们可以利用逻辑系统的可靠性来确定:有一些证明是不存在的


例如:在命题逻辑系统中给定前提 φ1, φ2, …, φn, 能否证明 ψ ?这其实是在问:
φ1, φ2, … , φn|- ψ 是否是有效的。


如果这个前提和结论非常复杂,那么你很可能证明不出来,因为证明通常是需要一点灵感的,而灵感通常是难得的。 但是,你证明不出来不能说明这个证明不存在。那我们应该怎么做呢?
有了可靠性定理,我们就可以将问题转化为: φ1, φ2, … , φn|= ψ 是否是有效的。

而这个问题,我们完全可以用真值表来确定。
假如我们用真假表确定了, φ1, φ2, … , φn|= ψ 是无效的, 那么,我们完全可以断言:
φ1, φ2, … , φn|- ψ 是无效的。即证明不存在。
因为根据可靠性定理,如果 φ1, φ2, …, φn|- ψ 是有效的, 那么 φ1, φ2, …, φn|= ψ 是有效的, 与我们根据真值表得出的结论相矛盾。


5完备性(Completeness)


5.1完备性是指什么?


完备性定理:令 φ1, φ2, …, φn和 ψ 为命题逻辑中的公式,如果 φ1, φ2, …, φn|= ψ 是有效的, 那么 φ1, φ2, …, φn|- ψ 是有效的。
可以看出,这和可靠性定理的定义正好相反。这其实是在说,在一个逻辑系统中,如果从语义上看, φ1, φ2, …, φn|= ψ 是有效的, 那么我们一定可以为φ1, φ2, …, φn|- ψ 找到一个证明。
在命题逻辑中,完备性定理也是成立的。具体的证明过程参考1

5.2完备性有什么用?

与可靠性一样,完备性也是逻辑系统的性质。那么完备性有什么用呢?在一个逻辑系统中,如果我们知道一些前提是 真的,即 φ1, φ2, …,φn都为真,那么,我们想知道在这样的条件下,结论 ψ 也一定是真吗?即我们想知道 φ1, φ2, …, φn|= ψ 是否是有效的。那么我们可能想找一个由φ1, φ2, …, φn到 ψ 的证明,即利用推导规则将 φ1, φ2, …, φn转化为 φ. 这时候,完备性就会告诉我们, 如果 φ1, φ2, …, φn|= ψ 是有效的,那么,这样 的证明一定存在。假如你的逻辑系统不满足完备性,那么即使φ1, φ2, …, φn|= ψ 是有效的,但是它的证明也可能 不存在,那你的努力可能就是徒劳的。


6结束

关于可靠性与完备性的讨论到这里就结束了,这只是我学习参考资料1第1章的一些体会,这本书相当不错,特别推荐给诸位。如果有什么问题,欢迎随时讨论。


参考:

1Michael Huth, Mark Ryan. 面向计算科学的数理逻辑——系统建模与推理. 2005

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics