logo  

人工智能入门——理论与工程

人工智能入门——理论与工程
作者: 陈安廉

摘要:研究人工智能


数理逻辑讲义


2021-09-14 14:10:12

目录

一,联结词

二,真值函项与真值指派

三,命题演算公理系统

四,自然推理系统

五,一阶谓词演算公理系统

六,一阶谓词演算的自然推理系统

七,含等词的一阶谓词演算自然推理系统

八,高阶逻辑

九,多值逻辑


第一章:联结词

1.1  n元组

设集合V={a,b},V为V上的所有n元组的集合。

当n=2时,得V2={<a,a>,<a,b>,<b,a>,<b,b>}。

很明显,V21={<a,a>},V22=<a,b>},V23={<b,a>},V24={<b,b>},这四个集合都是V2的子集且基数都为1。

 

1.2  一元联结词

设:

V25= V21V24 ={<a,a><b,b>

V26= V22V23={<a,b><b,a>

V27= V21V3={<a,a><b,a>

V28= V22V4={<a,b><b,b>


        Vij  是一个二元组集合,这些二元组的值之间存在一些分布规律,例如需要满足集合的元素不可重复的约束:任意两个二元组,当第一个值相等时,第二个值不能相等。除了这个元素不可重复的约束之外,我们对这些二元组进行比较,还能发现其他一些约束。我们可以一种操作描述来描述这些约束,即在二元组某个位置上出现特定的值之后,其他位置上可以放入的值受到了某种约束:只能放特定的值或者不可以放特定的值。          

通过遍历观察,可以发现,对V25的每一个元素,如果在第一个位置上放上任意的x,就意味着第二个位置会出现相同的x。因为<a,a><b,b>}集合中的任意元素都满足了一种分布规律:第一个位置上的值与第二个位置上的值是一样的。

对于V26中的任意元素,如果在第一个位置放上x,则在第二个位置必须放入与第一个位置的x不同值。又由于V只有两个元素,所以补集总是另一个,即与x不同的另一个值。

对于V27,在第一个位置放置任意的x,第二个位置都必须放入a。

对于V28,在第一个位置放入任意的x,第二个位置都必须放入b。

 

通常称V25为“么联结词”。称V26为否定联结词。称V27和V28为常联结词。

为直观地看出它们的差别,可以制出以下表格:

 

xV27V25V26V28
aaabb
babab


1.3  二元联结词

同样可以考察V, V={<a,a,a>,<a,a, b>,<a,b,a>,<a,b,b>,<b,a,a><b,a,b><b,b,a><b,b,b>

在V3中任取四个元素组成V3的子集,则有C(8,4)= 70个这样的子集。其中一些子集具有这样的特征:即存在着两个元素,当它们的前两个数相同时,第三个数不同。具有这个特征的子集有C(6,2)*4-C(4,2) = 54个。易得,不具有这个特征的子集有70-54=16个。我们把不具有这个特征的集合叫做函数。这些子集使得我们可以从前两个位置上的值推导出第三个位置上的唯一的值。

这十六个子集分别为:

V31= {<a,a,a>,<a,b,a>,<b,a,a>,<b,b,a>

V32= {<a,a,a>,<a,b,a>,<b,a,a>,<b,b,b>

V33= {<a,a,a>,<a,b,a>,<b,a,b>,<b,b,a>

V34= {<a,a,a>,<a,b,a>,<b,a,b>,<b,b,b>

V35= {<a,a,a>,<a,b,b>,<b,a,a>,<b,b,a>

V36= {<a,a,a>,<a,b,b>,<b,a,a>,<b,b,b>

V37= {<a,a,a>,<a,b,b>,<b,a,b>,<b,b,a>

V38= {<a,a,a>,<a,b,b>,<b,a,b>,<b,b,b>

V39= {<a,a,b>,<a,b,a>,<b,a,a>,<b,b,a>

V310= {<a,a,b>,<a,b,a>,<b,a,a>,<b,b,b>

V311= {<a,a,b>,<a,b,a>,<b,a,b>,<b,b,a>

V312= {<a,a,b>,<a,b,a>,<b,a,b>,<b,b,b>

V313= {<a,a,b>,<a,b,b>,<b,a,a>,<b,b,a>

V314= {<a,a,b>,<a,b,b>,<b,a,a>,<b,b,b>

V315= {<a,a,b>,<a,b,b>,<b,a,b>,<b,b,a>

V316= {<a,a,b>,<a,b,b>,<b,a,b>,<b,b,b>

 

V31和V316称为常联结词;

V34和V36是投影联结词;

V311和V313是二元否定词;

V39称为“或非词”,常用记号表示之,也称为皮尔斯记号;

V315称为“与非词”

V33,V35称为“蕴含否定词”

V37称为“异或词”

V32称为合取词;

V38称为析取词

V310称为等价词;

V312和V314称为蕴含词;

 

对他们的命名是不重要的。命名的意义只在于分类的方便以及容易记住,命名并不增加V3i的性质。

V称为(i-1)元联结词。

 

1.4  联结词之间的关系

 

V27={<a,a><b,a>

V26={<a,b><b,a>

V32= {<a,a,a>,<a,b,a>,<b,a,a>,<b,b,b>

V26中的所有元素都具有这样的特征,第一个元素与第二个元素不一样。如果我们用V26去限制V32,即使得V32中的元素也具有这个特征,不具有这个特征的则排除掉,则得到一个新的集合V26·V32={<a,b,a>,<b,a,a>}。

这个新集合的意义是,在无论在第一个位置和第二个位置放入任何的元素(注意,所放入的元素必须使得组成的三元组是V26·V32),第三个位置上出现的总是a;而V27的意义与此相同,无论在除了最后一个位置外的所有前面的位置中放入任何元素,最后一个位置出现的总是a。我们使用≡符号来表述这种限制的叠加关系。

V27V26·V32

V27p∧┐p

 

V32={<a,a,a>,<a,b,a>,<b,a,a>,<b,b,b>

V26={<a,b><b,a>

V38={<a,a,a>,<a,b,b>,<b,a,b>,<b,b,b>

对V32中的每一个元素中的第一个数与第二个数进行V26替换,则得到新的集合V321= {<b,b,a>,<b,a,a>,<a,b,a>,<a,a,b>},然后又对新集合V321的第三个元素进行V26的替换,得到更新的集合V321= {<b,b,b>,<b,a,b>,<a,b,b>,<a,a,a>},这个最新集合实际上等同于V38

pq(p∧┐q)

 

定义  Vni是用g1,g2,…,gn可表示的,如果在g1,g2,…,gn进行有限次限制或替换可形成Vni。

定义  当联结词组g1,g2,…gm可表示所有一元、二元联结词时,称其为完备联结词组(complete group of connectives)。

 

 




第二章  真值函项与真值指派

 

2.1  联结词与布尔代数

第一章关于联结词的讨论是一种数学研究,即对集合V={a,b}的研究。这个研究给出了Vn中的一些运算关系。这些运算关系实际上就是布尔代数的一种简便的说明。这个说明之所以说是简便的,是因为它避免了引入“偏序集”、“格”等概念——要简便地解释这两个概念可不是一件容易的事——也能让人直观地明白联结词的来源。

 

2.2   逻辑联结词是真值函项

在未对V中的元素做语义解释的情况下,Vn的种种运算仅仅是一种数学结构。但是,人们在语言实践中,发现我们语言的使用规则(是逻辑规则,不是语法规则)总是与这个结构相契合,即可以用联结词来分析我们的语言。

当我们对V进行一种解释,即不再把V中的元素看成是没有个性而只具有在V中的结构特征时,它就不再是纯结构的没有意义的符号了。我们发现,语句总是与真假联系在一起的。对于一个语句,我们可以说它是真的,也可以说它是假的;当然了,如果它是真的,我们说“它是假的”,我们所说的就是假的,因为我们说某个语句是假的,这个“说”本身也形成了一个语句。我们把T(即真)和F(即假)替换下V={a,b}中的那两个元素,即形成V={T,F}。从数学方面来讲,V={a,b}和V={T,F}并没有实质的不同。

V={a,b}中,a和b是对称,即在任何运算中把a和b完成对调过来,仍然成立。但在V={T,F}中就不是这么回事了,全部对调T和F并不使得运算仍然成立。原因在于Vn(T,F)中的运算只是Vn(a,b)中的一部分。

T和F,我们称为“真值”。

定义  对于任意的f(x1,x2,…xn),如果它的值是真值,我们就称f为真值函项。

Vn(T,F)中的运算我们称为“逻辑联结词”。很明显,逻辑联结词是真值函项。

 

2.3  一个语句是真值函项

前面我们已经提到了,语句总是与真假联系起来的,也就是语句是具有真值的。

为什么一个语句具有真值,这属于纯粹的哲学问题了。逻辑学只是假定每一个语句都具有真值,即赋予每一个语句具有真值,叫真值指派。

 

2.4  数学与逻辑学

 

这个引出真值函项与真值指派的过程,很容易让人觉得数学是逻辑的基础,但这种印象是错误的。理由有很多,其中包括:

i)真值指派的解释不能在纯数学中得到;

ii)可以在一种不太严格的意义上讲,某种数学结构与逻辑结构的同态只是偶然的,建立逻辑公理系统的过程中并未真的考虑了数学结构。

iii)数学的任何一个定理都要以逻辑为基础才能得到理解,一个定理除了它本身的内容外,它还包含着一个意思,即:这个定理是真的。

所以,逻辑是数学的必要基础而非反过来。但逻辑是不是数学的充要基础呢,这就很有争议了,罗素的回答是肯定的,并致力于把数学还原为逻辑,并在很多方面取得了重大成就。这种观点被称为逻辑主义。