斯坦福《逻辑学导论》第六周学习笔记

斯坦福大学的《逻辑学导论》课程几乎是每个希望干出一番事业的有理性人类梦寐以求的课程,它不是教授自亚里士多德以来的逻辑学史内容,也不是简单的教授符号使用和逻辑思维方法,而是传授思想。这门课通过研究逻辑学方法,学习组织信息和系统的推理工具,生成合逻辑的结论,以启迪我们将其应用在数学、科学、工程、商业、法律等领域。1

喜多一,喜多一,喜多一,本周课程过分了。

首先,本周课程没有视频,只有卡片。我不知道卡片有什么意义。

其次,在6.1的卡片中,毫无前奏,毫无铺垫,直接丢了下面的一个公式,我的妈妈!看不懂啊。

6.1的卡片

最后,我一直在想这一章的笔记该怎么来写。

词项逻辑

如果你和我一样看不懂6.1的卡片,那我们握握手,我们都属于智商低的一分子,这种教学思维跳跃感我们受不了。我们看不懂源于两个问题:第一,为什么要引入词项逻辑(Relational Logic),很可能是我英语不好,它那些个句子我根本看不懂。

Unfortunately, when we want to say things more generally, we find that Propositional Logic is inadequate. Suppose, for example, that we wanted to say that, in general, if one person knows a second person, then the second person knows the first. Suppose, as before, that we believe that Jack knows Jill. How do we express the general fact in a way that allows us to conclude that Jill knows Jack? Here, Propositional Logic is inadequate; it gives us no way of succinctly encoding this more general belief in a form that captures its full meaning and allows us to derive such conclusions. 不幸的是,当我们想要说一些更普遍的事情,就会发现命题逻辑的局限性。例如,我们想说,在一般情况下,如果一个人知道另一个人,那么另一个人也知道第一个人。像之前一样,假设我们知道“Jack知道Jill”,我们如何用逻辑推导出“Jill知道Jack”,形式的表达这个一般的事实?命题逻辑不够用了,它没办法使我们捕捉全部信息,并允许我们推导出一些结论的形式,简洁编码这些更普遍的信念。

好吧。让我来举例说明为什么要抛开前面学的命题逻辑(Propositional Logic),进入看起来更复杂(貌似只是它教案没写好)的词项逻辑(Relational Logic)。

命题逻辑只能判断和表达像下面这样的句子:

  • 北京是中国的首都。
  • 共产党是我们的母亲。
  • 中华人民共和国的主席是习大大。

词项逻辑可以进行下面的判断:

  • 所有鸟都不是哺乳动物。所以,所有哺乳动物不是鸟。
  • 所有清华学生都勤奋好学,有些在座的是清华学生。所以有些在座的勤奋好学。

variables and quantifiers

现在我们来解释这两个词。什么是变量和量词。

  • 所有鸟都不是哺乳动物。所以,所有哺乳动物不是鸟。

这句话把名词抠掉,可以变成这样:所有S都不是P。所以,所有P不是S。而,讲义为什么说这是two new linguistic features之一,真是不理解

例子的【所有】和【有些】是量词,这是新引入的词项逻辑的特点,并不难理解。

Problem 6.1

Say whether each of the following expressions is a syntactically legal sentence of Relational Logic. Assume that red, green, jim, and molly are object constants. Assume that color is a unary relation constant, and assume that parent is a binary relation constant.
a. parent(red, green)
b. color(jim, green)
c. color(color(blue))
d. parent(molly, molly)
e. parent(molly, z)
f. ∃x.parent(molly, x)
g. ∃y.parent(molly, jim)
h. ∀z.(z(jim, molly) ⇒ z(molly, jim))

第一题,就出来这么些没见过的“玩法”,喜多一。

首先,我们需要知道【谓词的概念】,也就是这里所谓的color和*parent*都是谓词。不知道为啥把它们翻译成谓词(可能是老翻译家干的好事?“所谓”的意思么)。其实它相当于“主系表”里的表语。比如“我是人”,“我”是主词,“是”是系词,“人”是表语,或者说谓词。

那么题中所列parent(red, green)的意思是:红色与绿色 是 父母亲。

上题之所以合法(legal)的原因在于题目说color这个谓词是一元的,也就是括号中只能有一个变量;parent这个谓词是二元的,也就是说括号中可以有两个变量,而逻辑是纯形式的,不需要管内在含义是否正确。

题目c*color(color(blue))*,错误在于谓词本身不能放在谓词当中。

那么后面三道题,我自己需要中文解释,否则看不懂讲义中下面的内容是什么意思:

A universally quantified sentence is used to assert that all objects have a certain property. For example, the following expression is a universally quantified sentence asserting that, if p holds of an object, then q holds of that object and itself. (∀x.(p(x) ⇒ q(x,x)))

  • 首先,符号∀是指全称量词,意思是“所有”,∃是特称量词,意思是“有一个”。
  • 其次,∃x.parent(molly, x)的意思是:有一个x,它和molly是parent。
  • 最后,∀x.(p(x) ⇒ q(x,x)的意思:所有的x,都能使性质是p的x推导出性质是q的x和x集合。

最后一题h错误的原因在于该句子没有写谓词,z只是一个变量,并不是题给的谓词(color和*parent*)。

谓词逻辑

本课程直接从词项逻辑跳到谓词逻辑,什么是专名也不讲,就这么直接略过了。然而,将词语(变元)区分为个体词与概念词两种其实是逻辑学的一个难点,是逻辑学从亚里士多德传统(词项逻辑)而来的一个创新,进化到了现代的逻辑理论(命题逻辑也是现代逻辑)。

好吧,讲义中给的例子又无法看懂。它这次出乎意料的还来了八卦:

The semantics of Relational Logic presented here is termed Herbrand semantics. It is named after the logician Herbrand, who developed some of its key concepts. As Herbrand is French, it should properly be pronounced "air-brahn". However, most people resort to the Anglicization of this, instead pronouncing it "her-brand". (One exception is Stanley Peters, who has been known at times to pronounce it "hare-brained".) 这里出现的关系逻辑语义称为Herbrand语义,是以逻辑学家Herbrand的名字命名的,他发展了一些关键概念。Herbrand是法国人,准确的发音应该是“air-brahn”。不过大多数人都发成“her-brand”的音。(例外是Stanley Peters,他经常说成“hare-brainer”)

什么鬼!

我们看下面的句子:

1 白马是马。所以,骑白马是骑马。
2 关于是刘备的兄弟,张飞是关羽的兄弟,所以张飞是刘备的兄弟。
3 黄蓉是黄药师的女儿,郭襄是黄蓉的女儿。所以,郭襄是黄药师的女儿。

第一句和第二句还没什么,第三句就能发现其可笑了,这样的推理是无效的。我们要想判断这类命题是否有效,使用上面“量词”的办法就不再有效了。我们必须要通过学习谓词逻辑,认识逻辑推理的内部结构,认识个体词、谓词与量词之间的关系。

常元、变元

注意这俩单词的差异:

  • 常元:constant
  • 变元:variable

A term is defined to be a variable or an object constant. Terms typically denote objects presumed or hypothesized to exist in the world; and, as such, they are analogous to noun phrases in natural language, e.g. Joe or someone. 项被定义成等同于常元或变元。项一般指事物被推测或假设在可能的世界中存在,它们类似于自然语言中的名词

Problem 6.2

6.2题

第一题:How many ground terms are there in this language?答案如上所述原因,n个常元(object constant),就有n个项。

第二题:How many ground atomic sentences are there in this language?这个答案很简单,题目说它是一个二元结构,n个常元就有$n^2$种简单句(不可再分的基础句)。

第三题:How many distinct truth assignments are possible for this language?我们根据第一、二章的知识知道,n个句子,有$2^n$种赋值情况,那么$n^2$种简单句就有$2^n^2$种赋值情况。

Problem 6.3-6.4

这俩题比较简单,看得懂6.1节的公式也就没有问题了,它就只是第一、二章的知识。

翻译:箱子(块)场景应用

6.5

如图,块模型是一个典型的人工智能应用。大多数人看到这个图会把它理解为五个积木块的位置组合。为了描述这个场景,我们采用5个常元:场景中的每一块积木都被编号。{a, b, c, d, e}对应于五个积木块。然后,我们用5个关系谓词来表示这些积木块互相之间的关系:{on, above, stack, clear, table}。

  • on谓词表示一块积木在另一块积木的上面(不间隔积木块)。
  • above谓词表示一块积木在另一块积木的上面(可间隔积木块)。
  • stack谓词表示三个积木块之间的关系,这三个积木块一个放在另一个上面。
  • clear谓词表示没有积木块在它的上面,其在最顶层。
  • table谓词表示积木块直接放在最下面的平台上。

由于on用来表示两个箱子之间的关系,就是二元函数,同样的,above也是二元函数,stack关系为三元,clear和table都只是一元。

下面的图表中,黑色表示句子真值为真,灰色表示句子真值为假:

6.5翻译

其他above, stack, clear, table都可以转换为on关系的表达式:

  • 一块积木满足clear关系,当且仅当它自己上面没有积木,即:∀y.(clear(y) ⇔ ¬∃x.on(x,y))
  • 一块积木满足table关系,当且仅当它自己不在其他积木上:∀x.(table(x) ⇔ ¬∃y.on(x,y))
  • 三块积木之间满足stack关系,当且仅当第一个在第二个且第二个在第三个上:∀x.∀y.∀z.(stack(x,y,z) ⇔ on(x,y) ∧ on(y,z))
  • 一块积木above另一块,当且仅当第一块在第二块上或在第二块之上的另一块上:∀x.∀z.(above(x,z) ⇔ on(x,z) ∨ ∃y.(on(x,y) ∧ above(y,z)))
  • 没有积木可以above它自己:¬∃x.above(x,x)

Problem 6.5

A sentence φ is consistent with a set Δ of sentences if and only if there is a truth assignment that satisfies all of the sentences in Δ ∪ {φ}. Say whether each of the following sentences is consistent with the sentences about on and above shown above. Be careful. It's tricky.

大家还记得consistence的意思吗?这里的意思就相当于为真

我们按照题给公式,把a, b, c三题的表达式写出来:

  • above(a,c): ∀a.∀c.(above(a,c) ⇔ on(a,c) ∨ ∃c.(on(a,b) ∧ above(b,c))),on(a,b), on(b,c)均为真,句子可得到真的真值属性。
  • above(a,a): 注意看题目中we have dropped the axiom ∀x.¬above(x,x),句子可得到真的真值属性。
  • above(c,a): ∀c.∀a.(above(c,a) ⇔ on(c,a) ∨ ∃c.(on(b,a) ∧ above(c,b))),你看的出来这个句子可得到真的真值属性吗?

一开始我也想不通,喜多一,后来我干脆把块状图画了出来:

6.5图示

有两种情况的原因在于on谓词并不能明确说明两个元素之间的关系,比如on(a,b)是指“a在b下”还“是b在a下”,所以above(a,c)与above(c,a)的真值属性实际上是等同的。

有效性、或然性、不满足性(Validity, Contingency, and Unsatsfiability)

  • 一个句子是可满足的,当且仅当至少有一种赋值使整个句子的真值为真。
  • 一个句子是可证伪的,当且仅当至少有一种赋值使整个句子的真值为假。
  • 一个句子是不可满足(Unsatsfiability)的,当且仅当没有任何一种赋值使整个句子的真值为真,即,无论我们用任何一种赋值,句子的真值总是为假。
  • 一个句子是或然(Contingency)的,当且仅当它即可满足又可证伪,即,句子的真值性既不恒为真,也并非恒为假。
  • 一个句子是有效(Validity)的,表示句子的真值属性恒为真。

以下的一些变化不会改变句子的真值属性:

  • p(a) ⇔ ¬¬p(a)
  • ¬(p(a) ∧ q(a,b)) ⇔ (¬p(a) ∨ ¬q(a,b))
  • ¬(p(a) ∨ q(a,b)) ⇔ (¬p(a) ∧ ¬q(a,b))
  • ∀x.∀y.q(x,y) ⇔ ∀y.∀x.q(x,y)
  • ∃x.∃y.q(x,y) ⇔ ∃y.∃x.q(x,y))
  • ∃y.∀x.q(x,y) ⇒ ∀x.∃y.q(x,y)
  • ¬∀x.p(x) ⇔ ∃x.¬p(x)

Problem 6.6

这道题懂了上面内容的话,就挺简单。看不出来的话,就用真值表算一算吧,例如:

6.6题

Problem 6.7

In particular, a set of ground premises in Relational Logic logically entails a ground conclusion in Relational Logic if and only if the corresponding set of Propositional Logic premises logically entails the corresponding Propositional Logic conclusion.

看懂这句话,题目迎刃而解,关系逻辑中的逻辑蕴含概念与之前学习的命题逻辑的逻辑蕴涵概念一样

吓死你妈妈三千

In this chapter, we start by extending the Fitch system from Propositional Logic to General Relational Logic.

大家还记得第四周时候的困境吧?没有忘吧,那些个坑爹证明的日子,第七周目又要来了。

In this chapter, we explore an alternative to Relational Logic, called General Relational Logic, in which we can name infinitely many objects with a finite vocabulary.

不过万幸啊,斯坦福的课程竟然给了我们苟延残喘的机会,那种困境是第七周目的内容。这周更新的六、七两章实际上可能只是原来第六章的内容。

总的来说,第七章的内容与第六章基本是重复的,我们终于看到斯坦福大人说废话了!这种“垃圾”书我劝还是从写的好,简直写的跟网络小说一样——都不挨着。

表达方法

我真的不懂这是怎么回事了,对于这本网络小说,我真是受够了!现在他又重新定义了一次表达方法:

  • object constants,也许可以翻译成常元,它的性质是必须出现在最里层的括号中。
  • function constant 也许可以翻译成谓词(功能词),它的性质是本身不能囊括自身。
  • relation constant 也许可以翻译成关系词,它可以处理谓词。

相信你看不懂我上面在说什么鬼,我也不知道,我也不知道这本网络小说在说什么鬼——你们自己去看吧。

Problem 7.1

差不多就行了,喜多一,我还以为是精神分裂症患者出的练习题呢。看懂了上面的话,你做起来应该挺简单的——有病要吃药啊,老师!

7.1题

翻译:皮亚诺运算

我们在处理自然语言的时候,如何面对它的无限性呢?即如何表达或存储无限多的常量呢。

一个办法是使用简单的对象常量和一元谓词(功能词)来表示自然语言。比如,我们可以用谓词不断的复写常量,如s(0)表示数字1,s(s(0))表示数字2。

不过,仅仅如此还不够,我们还需要用到逻辑句和量化句(logical sentences and quantified sentences)才行。

先看same关系,下面的句子用0和1定义了它:

∀x.same(x,x)
∀x.(¬same(0,s(x)) ∧ ¬same(s(x),0))
∀x.∀y.(¬same(x,y) ⇒ ¬same(s(x),s(y)))

显然上述公式完全描述了same关系是怎样的:

把上面的公式直观的写出来看,举例来说:

same(0,0)
same(s(0),s(0))
same(s(s(0)),s(s(0)))
...

上面的公式告诉我们:same关系对它自身总是有效,即真值属性为性。

7.2题解

第二个公式告诉我们:0不与它的衍生复合项相同,并且与自己的相反的否命题的真值属性为真。

第三个公式告诉我们:任意衍生复合的非全同复合项不能满足same关系。

通过same关系这样的方法,我们就可以定义运算中的其他关系。下面的公理用0,s和same定义了plus关系,0加上任何数都是原数,如果x加y得z,那么把x的后继加上y就得到z的后继。最后,我们得到plus函数公理:

∀y.plus(0,y,y)
∀x.∀y.∀z.(plus(x,y,z) ⇒ plus(s(x),y,s(z)))
∀x.∀y.∀z.∀w.(plus(x,y,z) ∧ ¬same(z,w) ⇒ ¬plus(x,y,w))

乘法公理系统是类似的,0乘任何数是0,如果数字z是x和y的乘积,w是y和z的和,那么w就是x的后继与y的乘积。我们像之前一样有了一个函数公理:

∀y.times(0,y,0)
∀x.∀y.∀z.∀w.(times(x,y,z) ∧ plus(y,z,w) ⇒ times(s(x),y,w))
∀x.∀y.∀z.∀w.(times(x,y,z) ∧ ¬same(z,w) ⇒ ¬times(x,y,w))

下面,我们试着用这样的方法处理传统数学公式,比如下面这样:

$x^2 + 2y = 4z$

我们知道这个方程的解是:x=4, y=8, z=8.

于是我们可以这样表达上面的方程式:∃x.∃y.∃z.∀u.∀v.∀w.(times(x,x,u) ∧ times(2,y,v) ∧ plus(u,v,w) ⇒ times(4,z,w))

看起来有点乱,但是可行。(ps:我觉得不只有点乱而已)我们总是能添加一些语法到符号中,清掉一些语言上的混淆东西,使它看起来像是传统数学符号。

ps:我们终于知道蛇精病的这一章是要干什么了,答案是彻底转化日常语言,怪不得罗素说过:当我知道了量词以后,我的生活再也没有回到原来的样子。

Problem 7.2

7.2题解

看题,看题,神经病出这种题,不知道意义在哪里。

第一道,也就是第一个公式,same关系只对它自身有效,所以答案是no。
第二道,plus函数的第一项+第二项应该等于第三项,等于,答案是yes。
第三道,times函数的第一项与第二项的乘积应该等于第三项,显然不等于,答案是no。
第四道,times函数的第一项与第二项的乘积应该等于第三项,可能等于——假设s(0)是1,s(s(s(0)))是3,答案是yes。

翻译:链表

不好意思,根本看不懂,这里是什么意思,神经病在搞什么。

也许是我英语不好,希望有人能把下面的题解释一下,发我邮箱,万分感谢。

Problem 7.3

7.3题解

我根本没懂构造链表函数的意义,所以也没看懂7.3节给的公式是什么意思。我也不懂让我们根据公式让判断表达式书写是否正确,对学习有什么意义。

翻译:伪英语

“伪英语”是一个正式语言,目的是为了接近英语语法。定义“伪英语”语法的一个方法用巴克斯范式(BNF)写语法规则。举例来说,句子是名词短语后跟一个动词短语,一个名词短语或者是一个名词或被and隔开的两个名词。一个动词短语是一个后跟名词短语。名词或者是Mary或者是Pat或者是Quincy。动词是like或likes。
::=
::=
::= "and"
::=
::= "mary" | "pat" | "quincy"
::= "like" | "likes"

我们可以使用关系逻辑来形式化伪英语语法。下面显示的句子表达了用BNF规则描述的语法。(我们已经省略了全称量词来使规则更可读。)这里我们用定义在列表部分的append关系。
np(x) ∧ vp(y) ∧ append(x,y,z) => sentence(z)
noun(x) => np(x)
noun(x) ∧ noun(y) ∧ append(x,and,z) ∧ append(z,y,w) => np(w)
verb(x) ∧ np(y) ∧ append(x,y,z) => vp(z)
noun(mary)
noun(pat)
noun(quincy)
verb(like)
verb(likes)

使用这些句子,我们可以用逻辑蕴涵程序枚举语法合法的句子,如下所示。
mary likes pat
pat and quincy like mary
mary likes pat and quincy

BNF范式和对应公理化的一个缺点是在主语和动词之间的数字没有一致关系。因此,用这些规则,我们可以得到下面的表达式,在自然英语中不合语法。
× mary like pat
× pat and quincy likes mary

幸运的是,我们可以通过多详述一些规则来解决问题。特别是,我们可以加一个论证给一些关系来表明表达式是单数还是复数。这里0代表单数,1代表复数。然后用这个来组织数字不一致的单词序列。
np(x,w) ∧ vp(y,w) ∧ append(x,y,z) => sentence(z)
noun(x) => np(x,0)
noun(x) ∧ noun(y) ∧ append(x,and,z) ∧ append(z,y,w) => np(w,1)
verb(x,w) ∧ np(y,v) ∧ append(x,y,z) => vp(z,w)
noun(mary)
noun(pat)
noun(quincy)
verb(like,1)
verb(likes,0)

使用这些规则,上面语法正确的句子保证还是句子。但是语法不正确的序列被阻止了。其他语法特征能以相似方式形式化,如,性别一致的代词(he versus she),所有格形容词(his versus her),反身代词(like himself and herself)等等。

Problem 7.4

7.4题解

这一题还比较好理解,它教我们计算机是怎么理解语言的,二进制的算法是怎样理解语言的(不过问题来了,我为什么要对计算机的具体算法了解的那么清楚,我为什么要了解机器语言而不是编程语言)。

a对是因为它符合自然语言语法,而b不符合。c对的道理是同样的,d错的道理我不懂,因为英语不好。

元逻辑(用逻辑形式化逻辑:用关系逻辑来形式化命题逻辑信息)

在关系逻辑中:not是-,and是∧,or是∨,如果是=>,当且仅当是<=>。

我们用谓词逻辑的函数表达它们:

  • 确定命题逻辑的项:

proposition(p)
proposition(q)
proposition(r)

  • 然后定义逻辑运算符:

∀x.(sentence(x) ⇒ negation(not(x)))
∀x.(sentence(x) ∧ sentence(y) ⇒ conjunction(and(x,y)))
∀x.(sentence(x) ∧ sentence(y) ⇒ disjunction(or(x,y)))
∀x.(sentence(x) ∧ sentence(y) ⇒ implication(if(x,y)))
∀x.(sentence(x) ∧ sentence(y) ⇒ biconditional(iff(x,y)))

  • 最后写出表达式:

∀x.(proposition(x) ⇒ sentence(x))
∀x.(negation(x) ⇒ sentence(x))
∀x.(conjunction(x) ⇒ sentence(x))
∀x.(disjunction(x) ⇒ sentence(x))
∀x.(implication(x) ⇒ sentence(x))
∀x.(biconditional(x) ⇒ sentence(x))

  • 有效性 valid(or(x,not(x)) <=> sentence(x)
  • 完整性 proves(x,y) <=> entails(x,y)
  • 定理证明 proves(and(x,y),z) <=> proves(x,implies(y,z))

在使用它们的时候,我们可以这样写:

∀x.(sentence(x) ∧ sentence(y) ⇒ ai(x,y,and(x,y)))
∀x.(sentence(x) ∧ sentence(y) ⇒ ae(and(x,y),x))
∀x.(sentence(x) ∧ sentence(y) ⇒ ae(and(x,y),y))

具体的使用方法,我们在下一周目会讲到。

Problem 7.5

7.5题解

b不对是因为谓词逻辑应该用disjunction而不是conjunction;d不知道为什么不对,知道的朋友不用发我邮箱了——不爱陪这神经病书玩了。


  1. MOOC果壳中文站:http://mooc.guokr.com/course/359/Introduction-to-Logic/  

2015-11-05 02:10 intrologic
Comments
Write a Comment