2009-8-20 史忠植 高级人工智能 1
高级人工智能第二章 人工智能逻 辑史忠植中国科学院计算技术研究所
2009-8-20 史忠植 高级人工智能 2
第二章 人工智能逻辑
2.1 逻辑 -----重要的形式工具
2.2 非单调逻辑
2.3 默认逻辑
2.4 限定逻辑
2.5 自认知逻辑
2.6 真值维护系统
2.7 情景演算的逻辑基础
2.8 动态描述逻辑
2009-8-20 史忠植 高级人工智能 3
逻辑的历史
Aristotle—— 逻辑学
Leibnitz—— 数理逻辑
Gottlob Frege (1848-1925)—— 一阶谓词演算系统,,符号论,
20世纪 30年代，数理逻辑广泛发展
2009-8-20 史忠植 高级人工智能 4
重要的形式工具 ──逻辑在本世纪 30年代以后，数学方法广泛渗透与运用于数理逻辑，使得数理逻辑成为数学领域中与代数、几何等并列的学科之一。现代数理逻辑可以分为逻辑运算、证明论、公理集合论、递归论和模型论。
2009-8-20 史忠植 高级人工智能 5
关于知识的表示与推理智能行为的基础是知识，尤其是所谓的常识性知识。
人类的智能行为对于知识的依赖主要表现在对于知识的利用，即利用已经具有的知识进行分析、猜测、判断、
预测等等。人类利用知识可以预测未来，由已知的情况推测未知的情况、由发生的事件预测还未发生的事件等等。但是，当人们希望计算机具有智能行为时，除了告诉计算机如何像人一样地利用知识以外（对于知识进行推理），一个更为基础和先行的工作是如何使计算机具有知识（对于知识进行表示），即在计算机上如 何表达人类的知识。
2009-8-20 史忠植 高级人工智能 6
关于知识的表示与推理多数的基于逻辑的智能系统使用一阶逻辑或者它的一些扩张形式 。 一阶逻辑的优点是它具有相当强的表达能力 。 有的人工智能专家坚信所有的人工智能中的知识表示问题完全可以在一阶逻辑的框架中得以实现 。 一阶逻辑在表达不确定性知识时其表达能力也是很强的 。 例如,
x P(x)
表达在所考虑的论域中存在一个具有性质 P的对象,而具体的是哪一个对象具有此性质则是待确定的；再如,
P? Q
表示 P和 Q这两个性质之间有一个是成立的,至于到底是哪一个成立则是根据具体的情况而定的 。
2009-8-20 史忠植 高级人工智能 7
关于知识的表示与推理有人坚信从本质上看,一阶逻辑对于知识表示 是足够的,
但从实际应用的角度看,为方便,清楚和简洁起见,知识表示不一定非得从一阶逻辑出发 。 事实上,人 们从实际应用出发已经发明和建立了许多适用于不同目的的逻辑系统 。
(1) 为了表示关于认知的有关概念,如相信,知道,愿望,意图,目标,承诺等等,人们引进了刻划各种认知概念的 模态逻辑 ；
(2) 为了刻划智能系统中的时间因素,人们在逻辑系统中引进时间的概念,提出了各种 时序逻辑 ；
2009-8-20 史忠植 高级人工智能 8
关于知识的表示与推理
(3) 为了描述各种不确定的和不精确的概念,人们引进了所谓 模糊逻辑 ；模糊逻辑是直接建立在自然语言上的逻辑系统,
与其它逻辑系统相比较,它考虑了更多的自然语言的成分 。 按照其创始人 Zadeh的说法就是词语上的计算,表示为一个公式,即,
fuzzy logic＝ computing with words；
(4) 人类的知识与人类的活动是息息相关的,人类正是在各种活动和行为中获得知识的 。 因此,行为或者动作的概念在智能系统中是一个关键的概念 。 动作的概念与一般逻辑中的静态的概念很不相同,它是一个动态的概念,动作的发生影响着智能系统的性质 。 对于动作的考虑,给人工智能界带来了许多难题,如框架问题,量词问题等等 。 为了刻划动作的概念,人们引进了一些新的逻辑体系来刻划它 。
2009-8-20 史忠植 高级人工智能 9
关于知识的表示与推理
(5) 计算机对于人类进行决策时进行若干方面的支持已经成为计算机应用的一个重要方面 。 人类在决策时,对于各种方案和目标有一定的偏好和选择 。 这时,偏爱,就成为了一个基本的概念 。 为了表述和模拟人类在决策时的选择的规律和行为,
对于,偏爱,这个词的研究就是不可避免的 。 于是,基于管理科学的所谓的偏爱逻辑被提出并加以研究 。
(6) 时间是智能系统中最重要的几个概念之一 。 人类使用各类副词来对时间概念加以描述 。 例如,,一会儿,,相当长,,断断续续地,,偶尔,等等,这一类词在我们的日常生活中比比皆是 。 含有这些词的句子显然是很难用经典的时序逻辑来刻划的,于是有人引进了一种逻辑系统专门刻划这类句子 。 其基本思想是利用数学中积分的思想,通过对时间的某种像积分那样的表示和运算来形式化这些句子 。
2009-8-20 史忠植 高级人工智能 10
逻辑系统一个逻辑系统是定义语言和它的含义的方法。
逻辑系统中的一个逻辑理论是该逻辑的语言的一个语句集合，它包括：
逻辑符号集合,在所有该逻辑的逻辑理论中均出现的符号；
非逻辑符号集合,不同的逻辑理论中出现的不同的符号；
语句规则,定义什么样的符号串是有意义的；
证明,什么样的符号串是一个合理的证明；
语义规则,定义符号串的语义。
2009-8-20 史忠植 高级人工智能 11
逻辑 程序语言逻辑符号 保留字或者符号非逻辑符号 用户自定义的符号 (变量名，函数名等 )
语句规则 构造一个程序的语句规则语义规则 定义程序做什么的语句规则推理规则、公理和证明 没有逻辑与程序语言的对比
2009-8-20 史忠植 高级人工智能 12
在语法上，如果存在一个从假设?到?的证明，
则记为,称?由?可推导出的，或 可证明的 。
如果在没有任何假设下?是可推导出的，则记为
，称?为可证明的。
称一个假设?是 不协调的,如果存在一个语句?
使得?和?的否定均可由?推导得出。
称一个逻辑系统是 一致的,或 相容的 (consistent)，
如果不存在逻辑系统的公式 A，使得?A与A同时成立。
证 明 (语法 )
2009-8-20 史忠植 高级人工智能 13
一个 证明 是一个语法结构，它由符号串根据一定的规则组成。它包括假设和结论。
在公理化逻辑中，逻辑给出一个 逻辑公理 和 推理规则 的集合。推理规则是可以从一个语句的集合得到另一语句的集合。
公理化逻辑中的证明就是一个语句序列，使得其中的每个语句要么是逻辑公理，要么是一个假设，
要么是由前面的语句通过推理规则得到的。
证 明
2009-8-20 史忠植 高级人工智能 14
语言的 解释 是在某个论语 (domain)中定义非逻辑符号。语句的语义是在解释下定义出语言 L的真假值。
如果 I是 L的一个解释，且?在 I中为真，则记为
I,称作 I满足?,或者 I 是?的一个 模型 。
类似地，给定一个语句?和一个语句?,如果对每个解释 I,有 I 蕴含 I,换言之，如果 I 是?
的一个模型则 I也是?的一个模型，则记为,我们称?为?的一个 逻辑结果 。
解 释 (语义 )
2009-8-20 史忠植 高级人工智能 15
可靠性 (reliable)
一个逻辑是可靠的，如果它的证明保持真假值，
即在任何解释 I下，如果 I是? 的模型，且?可由?推导出，则 I也是?的一个模型。即，一个逻辑是可靠的，
如果对任何语句集合?和语句?,蕴涵 。
可靠性和完备性完备性 (complete)
一个逻辑是完备的，如果任何永真语句是可证的。
即，对任何语句集合?和语句?,蕴涵 。
如果一个逻辑是完备的，则该逻辑的证明系统已强到可以推出任何永真式。
G?del完备性定理,一阶逻辑是完备的
2009-8-20 史忠植 高级人工智能 16
可判定的一个逻辑称为是 可判定的 (decidable)，如果存在一个算法对逻辑中的任一公式 A，可确定? A是否成立。否则，称为是 不可判定的 (undecidable) 。
如果上述算法虽不一定存在，却有一个过程，可对该系统的定理做出肯定的判断，但对非定理的公式过程未必终止，因而未必能作出判断。这时称逻辑是 半可判定的 。
可判定性一阶逻辑是不可判定的，但它是半可判定的。
2009-8-20 史忠植 高级人工智能 17
命题逻辑
命题是可以确定其真假的陈述句。
Bolle提出了布尔代数。
语言,?,?； 公式，原子公式公理模式,
◆ (A?(B? A))
◆ ((A?(B? C))? ((A? B)?(A? C)))
◆ (((?A))?(?B)? (B? A))
推理规则,分离规则 (modus ponens,MP规则 )
B
BAA?,
2009-8-20 史忠植 高级人工智能 18
谓词逻辑 (一阶逻辑 )
Frege谓词演算语言,?,?,?,?,(,)；常元，变元，函词，谓词；公式公理模式,
◆ (A?(B? A))
◆ ((A?(B? C))? ((A? B)?(A? C)))
◆ (((?A)?(?B))? (B? A))
◆?vA? Atv (t对 A中变元 v可代入 )
◆?v(A?B)? (?vAvB)
◆ AvA (v在 A中无自由出现 )
推理规则,分离规则
B
BAA?,
2009-8-20 史忠植 高级人工智能 19
谓词逻辑与命题逻辑的区别
谓词逻辑给出了原子语句的内部结构，将原子公式看作是事物直接的关系；
它引入了“推广” (泛化 )，加强了逻辑的表示能力和推理能力。这样，我们可以说某种性质对某个对象是成立的，或对所有的对象成立，
或不对任何对象成立。
2009-8-20 史忠植 高级人工智能 20
逻辑程序设计
消解原理 (归结原理 )
Horn逻辑
Prolog逻辑程序设计语言
2009-8-20 史忠植 高级人工智能 21
归结原理例：
C1 =?P∨ Q∨ R C2 = P∨ Q
则 C1与 C2消解后的结果为,Q∨ R
若子句集 S能导出空子句?(有否证 )，则称 S
是不可满足的。
S? A iff SA
Q
QPP?,
Q
QPP,
2009-8-20 史忠植 高级人工智能 22
Horn逻辑
文字,原子公式 (正文字 )或原子公式的否定 (负文字 )。
P,Q,?R
子句,若干文字的析取。P∨ Q∨ R
Horn子句,
L1∨ L2∨ … ∨ Ln中如果至多只含一个正文字，
那么该子句称为 Horn子句。
Horn子句 P∨?Q1∨?Q2∨ … ∨?Qn通常表示为：
P? Q1,Q2,…,Qn
2009-8-20 史忠植 高级人工智能 23
Horn子句的类型：
◆ 过程,P? Q1,Q2,…,Qn
◆ 事实,P?
◆ 目标,? Q1,Q2,…,Qn
◆ 空子句,?
例,◆ 过程,AT(dog,x)? AT (Zhang,x)
◆ 事实,AT (Zhang,train)?
◆ 目标,? AT(dog,train)
首先目标中过程调用 AT(dog,train)与过程名 AT(dog,x)
匹配，合一为 {train/x}，调用过程 AT(Zhang,x)，从而产生新目标? AT (Zhang,train)，与事实匹配，产生目标? 。因而调用成功，输出,是,。
2009-8-20 史忠植 高级人工智能 24
Prolog
Prolog(Programming in logic)语言是以 Horn子句逻辑为基础的高级程序设计语言。
1972年，法国马赛大学的 Alain,Colmerauer提出了 Prolog的雏型。
1975年,Prolog被用于问题求解系统。
此后，它在许多领域获得了应用，如关系数据库、
定理证明、智能问题求解、计算机辅助设计、规划生成等领域。
2009-8-20 史忠植 高级人工智能 25
Prolog的构成
事实,关于对象性质和关系的事实语句；
student(john),married(tom,mary)
规则,关于对象性质和关系的定义规则语句；
它与事实的不同在于，规则所定义的性质、关系依赖与其它的性质和关系，因此规则呈蕴涵语句形式。
B:— A,如果 A则 B”
bird(x),— animal(x),has(x,feather)
问题,关于对象性质或关系的询问。
— student(john)
— married(mary,x)
2009-8-20 史忠植 高级人工智能 26
Prolog语言的基本文法
Prolog语言的最基本语言成分是项 (term)，一个项或者是常量，或者是变量，或者是一个结构。
常量,是指对象和对象之间的特定关系的名；
整数,如 0,22,1586等；
原子,如 John,student,likes,sister-of
变量,表示任意的对象，它与 FOL中的变元相同；
Prolog中变量可以用大写字母，下划线，以及由它们开头的字母串。如 X,Y,Answer,_value等。
结构,是常量和变量的序列，它由一个函子 (函词或谓词 )和该函子的自变量所组成。如：
likes(john,X) married(mary,jack)
2009-8-20 史忠植 高级人工智能 27
例：
(1) likes(bell,sports)
(2) likes(mary,smith)
(3) likes(mary,sports)
(4) likes(jones,smith)
(5) friend(john,X),— likes(X,sports),likes(X,smith) (规则 )
(6)?— friends(john,Y) (问题 )
(事实 )
(7)?— likes(X,sports),likes(X,smith)
(8)?— likes(bell,smith) (bell / X)
(7)?— likes(X,sports),likes(X,smith)
(8)?— likes(mary,smith) (mary / X)
Y = mary,John与 Mary是朋友
2009-8-20 史忠植 高级人工智能 28
Prolog的执行方式搜索,在程序中自上而下地搜索事实和规则；
匹配,将目标中的项与事实和规则进行匹配；
回溯,当目标中一项失败时，如果目标中有已经成功的的项 (应在失败项的左边 )，那末就重新调用这些成功项中最右边的一个，谋求新的成功。
2009-8-20 史忠植 高级人工智能 29
Prolog的基本特点
Horn子句逻辑是 Prolog的基础。
Prolog既是一种逻辑程序设计语言，又是一个逻辑系统。
Prolog是一种描述性语言，它是一种面向问题的语言，你只需要告诉它要做什么，即给出问题的形式描述，而不需要知道应该如何做。
Prolog完全依靠匹配、回溯 来进行搜索。 Prolog的求解过程是一个寻求否证的消解过程。
Prolog也使用元语言种的谓词，有很强的描述能力。
Prolog采用统一的数据结构 —— 项，它包含控制成分，且有专门进行数值计算和符号处理的模块。
2009-8-20 史忠植 高级人工智能 30
逻辑程序设计
PROLOG
B? A1,…,An
B?
A1,…,An
2009-8-20 史忠植 高级人工智能 31
单调逻辑
在现有知识的基础上，通过严密的逻辑论证和推理获得的新知识必须与已有的知识相一致。
A,A?B?B
推理系统的定理集合随着推理过程的进行而单调地增大。
单调性：
(1)?∈ Th(? )
(2) 若?12,则 Th(?1)? Th(?2)
(3) Th(Th(? )) ＝ Th(? ) (不动点 )
2009-8-20 史忠植 高级人工智能 32
非单调逻辑推理系统的定理集合并不随着推理过程的进行而单调地增大，新推出地定理很可能会否定、
改变原来地一些定理，使得原来能够解释地某些现象变得不能解释了。
新规则：
(4)P (不动点 )
2009-8-20 史忠植 高级人工智能 33
非单调逻辑推理系统的定理集合并不随推理过程的进行而单调地增大,新推出的定理很可能会否定、改变原来的一些定理,使得原来能够解释的某些 现象变得不能解释了。
2009-8-20 史忠植 高级人工智能 34
非单调逻辑推理系统的定理集合并不随推理过程的进行而单调地增大,新推出的定理很可能会否定、改变原来的一些定理,使得原来能够解释的某些 现象变得不能解释了。
t1<t2 F(t1)?F(t2)
2009-8-20 史忠植 高级人工智能 35
非单调逻辑鸟会飞鸵鸟是鸟所以,鸵鸟会飞
2009-8-20 史忠植 高级人工智能 36
非单调推理
1 John在时刻 t1是活着的
2 Dell在时刻 t2>t1把子弹装进枪膛
3 Dell在时刻 t3>t2举 枪对 John射击
4 问题,John在时刻 t4>t3还 是活着吗？
2009-8-20 史忠植 高级人工智能 37
非单调逻辑设?表示推理规则集,则单调逻辑语言
Th(?)={A|A}
(1)Th(?)
(2) if?12,then Th(?1)? Th(?2)
(3) Th(Th(?)) = Th(?) (不动点 )
(4) ifP,then MP
其中 M模态词
2009-8-20 史忠植 高级人工智能 38
默认 逻辑
1980年,Reiter提出了默认缺省逻辑 (Default Logic)。
“一般情况下鸟是会飞的”
“鸵鸟不会飞”,企鹅不会飞”
)(
)(:)(
xf l y
xM f l yxB i r d
会飞会飞”与系统不矛盾“是鸟
x
xx,
2009-8-20 史忠植 高级人工智能 39
默认 规则一个默认规则是如下形式的规则：
)(
)(,),(:)( 1
x
xMxMx n
(x):称为前提条件
i(x):称为缺省条件，或检验条件
(x):称为结论为简便，通常情况下可以省略检验条件中的 M。
规则的使用：
出检验条件的否定i(x)，则可以得出结论成立。
2009-8-20 史忠植 高级人工智能 40
默认理论一个 默认理论?由两个部分组成，即 默认 规则集 D和公式集 W，一般用二元组来表示?＝ <D,W >
若 D中的规则是闭规则时，则?为闭缺省理论。
定义,设?＝ <D,W >为一闭缺省理论,?为 关于 D的一个算子,?作用于任意的命题集合 S，而其值为满足下列三个性质的最小命题集合?(S)：
(1) W(S)
(2) Th(?(S)) =?(S)，其中 Th(?(S)) = {A|?(S)? A}
(3) 如果 D中有规则,
且?∈?(S),1,…,m?S,那么?∈?(S)
nMM,,,1?
2009-8-20 史忠植 高级人工智能 41
默认 理论的扩充定义,对命题集合 E，如果?(E) = E，则 E称为关于
D的算子?的 不动点 (fixpoint)。此时称 E为 默认 理论
＝ <D,W >的一个 扩充 (extension)。
例 1：设 D ＝ { },W ＝?，计算 默认理论?＝ <D,W >的 扩充。
F
C
C
B
B
A
:,:,:
＝ <D,W >有唯一的扩充 E ＝ Th({?B,?F})。
2009-8-20 史忠植 高级人工智能 42
例 2：设
D ＝ { }，
W ＝ {B,C?F∨A,A∧CE}，计算 默认 理论
＝ <D,W >的 扩充。
G
AFAEC
E
EAF
C
CB
A
A,:,:,:,:
＝ <D,W >有三个扩充
E1 ＝ Th(W?{A,C})
E2 ＝ Th(W?{A,E})
E3 ＝ Th(W?{C,E,G})
2009-8-20 史忠植 高级人工智能 43
封闭默认理论的扩展设封闭默认理论? = <D,W>,?为关于 D的一个算符,? 作用于任意的命题集合 S,其值为满足下列三个性质的最小命题集合?(S):
(1) W (S);
(2) Th(?(S)) =?(S); 这里,Th(? (S))为命题集 {A |?(S)
A};
(3)如果有默认规则
)(
)(,),(:)( 1
XW
XMXMX n
2009-8-20 史忠植 高级人工智能 44
封闭默认理论的扩展命题集合 E称为关于 D的算符?的固定点,如果?(E) =E,
此时又称 E为?= <D,W>$ 的一个扩充 。
有了扩充的概念,便可定义非单调的,推出,概念 。
如果命题 A包含在默认理论? 的一个扩充中,那么称 A在?
中可推出,记为 | 。
扩充 E必须 ① 含有所有的已知事实 ;
② 在关系 |? 下是封闭的 ;
③ 其前提被 E满足,默认条件与 E相容的任意默认的结论必须也在 E中 。
)(
)(,),(:)( 1
XW
XMXMX n
2009-8-20 史忠植 高级人工智能 45
封闭默认理论的扩展具有扩展的存在条件将显得十分重要 。 下面我们讨论三种情况 。
(1) 不含任何默认的理论 <{ },W>,这种理论退化到一阶逻辑理论,
在这里它虽有唯一的一个扩展 Th(W),但对默认推理毫无意义和作用 。
(2) 一个默认理论 <D,W>称为规范默认理论,如果 D中默认规则均有如下形式,
)(
)(:)(
XW
XMWX?
2009-8-20 史忠植 高级人工智能 46
封闭默认理论的扩展如果一个理论中的所有默认都是规范的,则该理论称为规范理论 。 由于每个规范默认的结论与其合理条件相同,因而这种缺省不会导致不一致性,不会证伪其它已用过的默认的合理条件 。 因此我们说规范默认理论是行为良好
(well-behaved) 的理论,并且可以证明,任何规范默认理论必定至少有一个扩充 。
2009-8-20 史忠植 高级人工智能 47
封闭默认理论的扩展
(3) 半规 范默 认 理论 (Seminormal Default
Theory),虽然规范默认理论至少有一个扩充,
从而保证了系统知识库 W的一致性 。 然而现实世界中许多事物,现象是无法用规范默认表示的,而用如下形式的默认则可有效地进行处理,
MMX?:)(
2009-8-20 史忠植 高级人工智能 48
封闭默认理论的扩展为了保证半规范默认理论具有一个扩充,
必须对它的默认加以限制,Reiter给出了一个半规范默认理论至少具有一个扩充的充分条件,
这个条件要求封闭的半规范默认理论是有序的,。 有序性建立在一个偏序关系?上,这个偏序要求,如果在推导 β的过程中用到了 α,则 α?
β。 Etheringthon在这种基础上给出了求算偏序关系及其扩充的算法,并讨论了算法的收敛性问题 。
2009-8-20 史忠植 高级人工智能 49
限定推理
1980年,McCarthy提出了一种非单调的推理 —
—
限定推理 (Circumscription)。
基本思想,从某些事实 A出发能够推出具有某一性质的 P的对象就是满足性质 P的全部对象。只有当发现其它对象也具有该性质时，才修改这种看法。
2009-8-20 史忠植 高级人工智能 50
限定逻辑限定逻辑 CIRC是一种极小化逻辑。下面，从一个基于极小模型定义的命题限定出发，给出限定的基本定义,进而给出一阶限定的基本结果，并将它推广。
定义 2.1 设 L0是一个命题语言,p1,p2是在命题语言 L0 中的两个赋值。称 p1小于 p2,记为 p1? p2,当且仅当对任一命题变元 x,如果 p1(x) = l,则 p2(x) = l。
2009-8-20 史忠植 高级人工智能 51
限定逻辑定义 2.2 设 A 是一个公式，称 A的一个赋值 p是极小的，当且仅当不存在 A的其它赋值 p'使得 p'? p。
显然,?是一个偏序关系。 p1? p2表示 p1包含的真命题比 p2 少。极小赋值包含的真命题极小。
定义 2.3 极小后承M。 设 A,B是两个公式,AM B
当且仅当 B在所有 A 的极小模型中都为真。
极小模型是非单调的，它以命题的极小化作为优先模型的准则。
2009-8-20 史忠植 高级人工智能 52
限定逻辑定义 2.4 设 A是一个包含命题集 P = {p1,p2,...,
pn} 的公式，一个 A的赋值 p称为? Z-极小赋值，当且仅当不存在 A的其它赋值 p‘使得 p? p’,定义如下：设 p1,
p2 是两个赋值,p1? Z- p2 当且仅当对任一 z? Z,
若 p1 (Z) = l,则 p2 (Z)= l。
2009-8-20 史忠植 高级人工智能 53
限定逻辑定义 2.5 命题限定P 或 CIRC(A,P)。设 A是一个包含命题集的公式,? 是一个公式,AP? 当且仅当? 在所有 A的? p- 极小赋值中都为真。
定理 2.1 Ap? 当且仅当 AP?
2009-8-20 史忠植 高级人工智能 54
限定逻辑定义 2.6 令 L是一个一阶语言,T是一个 L的公式，它包含谓词元组集?。设 M[T]和 M*[T]是公式 T的两个模型。
定义 M*[T]优先于 M[T],记为 M*[T]? M[T],当且仅当
(1) M和 M*有相同的对象域，
(2) 除?外，公式 T中所有的其它关系和函数常数在 M和 M*都有相同的解释，
(3)?在 M*中的外延是?在 M中的子集。
2009-8-20 史忠植 高级人工智能 55
限定逻辑一个理论 T的模型 M称为优先的，当且仅当不存在 T的其它模型 M'使得 M'M。
定义 2.7 Mm是?的最小模型，当且仅当
M Mm,M = Mm
2009-8-20 史忠植 高级人工智能 56
限定逻辑例如 设论域 D={1,2}
T=?x?y(P(y)?Q(x,y))
=[(P(1)?Q(1,1)) (P(2)?Q(1,2))]?
[(P(1)?Q(2,1)) (P(2)?Q(2,2))]
M,P(1) P(2) Q(1,1)? Q(1,2) Q(2,1)? Q(2,2)
T T F T F T
M*,P(1) P(2) Q(1,1)? Q(1,2) Q(2,1)? Q(2,2)
F T F T F T
2009-8-20 史忠植 高级人工智能 57
自认知逻辑
Moore 考虑自认知理论 T 对于一组初始前提 A 是可靠的，
当且仅当 T 中的每一个自认知解释器是一个 T 中的自认知模型，其中全部 A 的公式为真。一个理想的理性主体的信念必须满足下列条件：
(1) 设 P1,...,Pn? T,and P1,...,Pn Q,
则 Q? T。
(2) 设 P? T,则 BP? T。
(3) 设 P? T,则 ~BP? T。
2009-8-20 史忠植 高级人工智能 58
自认知逻辑在这种情况下，主体不能再得到更进一步的结论，
因此,Moore称上述理论为稳定自认知理论。当然，下列条件也成立：
(4) 如果 BP? T,则 P? T。
(5) 如果 ~ BP? T,则 P? T。
2009-8-20 史忠植 高级人工智能 59
真值维护系统 TMS
1979年,Doyle提出了一种非单调推理系统 ——
真值维护系统 (Truth Maintenance System)
真值维护系统是大型推理系统的的一个子系统，
实现知识库中信念 (belief)的修改与维护。其基本问题有：
必须在不完全的、有限的信息基础上作出假设的决策，使得该假设成为知识库的信念；
当这些决策的结论被以后的事实证明为错误时，如何对其信念进行修正。
2009-8-20 史忠植 高级人工智能 60
基本数据结构,
结点,表示信念理由,表示信念的原因信念既包括已知的知识，也包括假设的知识。
基本操作,
新结点的形成 —— 将信念赋予该结点；
新理由的加入 —— 把某个信念与该结点联接起来实现过程,
默认假设的形成；
相关性回溯过程。
2009-8-20 史忠植 高级人工智能 61
信念知识表示每一个命题或规则均称为结点，它分为两类：
IN-结点,相信为真
OUT-结点,不相信为真，或无理由相信为真，
或当前没有任何有效的理由。
每个结点附有理由表，表示具体结点的有效性：
支持表 SL,所在结点的信念的原因，理由；
条件证明 CP,出现矛盾的原因。
2009-8-20 史忠植 高级人工智能 62
(SL(<IN-结点表 >)(<OUT-结点表 >))
IN-结点表中的 IN-结点表示知识库中的已知知识 ;
OUT-结点表中的 OUT-结点表示这些结点的否定。
例 1:
(1) 现在是夏天 (SL( )( ))
(2) 天气很潮湿 (SL(1)( ))
结点 (1)不依赖于任何别的结点中的当前信念或默认信念,因而这种结点称为前提 ;
结点 (2)则依赖于当前结点 (1)的信念,
所以，与一阶逻辑不同的是,TMS可以撤消前提,
并可以对知识库作适当修改,
（ 1）支持表 SL
2009-8-20 史忠植 高级人工智能 63
例 2:
(1) 现在是夏天 (SL( )( ))
(2) 天气很潮湿 (SL(1)(3))
(3) 天气很干燥若结点 (1)是 IN,结点 (3)是 OUT,则结点 (2)才为 IN.
若在某个时刻出现结点 (3)的证据,则结点 (2)就变为
OUT,因为它不再有一个有效的证实,象结点 (2)这样的结点称为假设,它与非空的 OUT结点表的 SL证实有关,OUT结点 (3)是结点 (2)的证实的一部分,但如果结点 (3)不存在,就不能这样表示了,
在 TMS中,它仅利用证实来维持一个相容的信念数据库,而它本身并不产生证实,
2009-8-20 史忠植 高级人工智能 64
(CP <结论 > <IN-假设 > <OUT-假设 >)
如果结论结点为 IN-结点,以及下列条件成立,
(1) IN假设中的每个结点都是 IN-结点 ;
(2) OUT-假设中的每个结点都是 OUT-结点,
那么条件证明 CP是有效的,
一般说来,OUT-假设总是空集,TMS要求假设集划分成两个不相交的子集,分别为不导致矛盾的假设和导致矛盾的假设,
通常只要在 IN-假设中的结点为 IN,OUT-假设中的结点为 OUT,则结论结点为 IN.
（ 2）条件证明 CP
2009-8-20 史忠植 高级人工智能 65
默认假设令 {F1,F2,…,Fn}表示所有可能的侯选的默认假设结点集,G表示选择默认假设的原因的结点,即由 G
引起在 {F1,…,Fn}中进行缺省选择,这样我们结合结点 Node(Fi)以如下理由,
(SL(G)(F1,…,Fi-1,Fi+1,…,Fn))
而选取 Fi为默认假设,
如果不存在任何其它关于如何进行选择的信息，
则可以认为除 Fi之外其它任何时候选都不是可信的．
这样 Fi为 IN,其它 Fj(i? j)均为 OUT.但如果接收到一个有效的理由支持某个其它的侯选 Fj,则 Fj就为 IN,
而导致 Fi的假设失败而变为 OUT.
2009-8-20 史忠植 高级人工智能 66
相关回溯当知识库中出现不一致时,TMS将寻找并删除已做的一个不正确的默认逻辑,恢复一致性,它包括三个步骤,
(1) 从产生的矛盾结点开始,回溯跟踪该矛盾结点的理由充足的支持以寻找矛盾的假设集,并从中去掉至少一个假设信念以消除矛盾,
(2) 构造一个结点记录矛盾产生的原因,
(3) 从 S中选取假设 A(即不合理假设 ),并证实列在其理由充足的支持条件中的一个 OUT-结点,
2009-8-20 史忠植 高级人工智能 67
(4) 矛盾 (SL(1,3)( ))
(周三 14:00没有空会议室 )
例 3:
(1) 会议日期为星期三 (SL( )(2))
(2) 会议日期不应是星期三
(3) 会议时间为 14:00 (SL(32,40,61)())
(5) 不相容 (CP4 (1,3)( ))
(2) 会议日期不应是星期三 (SL(5)( ))
结点 (2)与结点 (5)为 IN,就引起结点 (1)为 OUT,因为结点 (1)的证实依赖于结点 (2)是 OUT.结点 (4)现在也变成 OUT.进而矛盾就消除了,
2009-8-20 史忠植 高级人工智能 68
情景演算情景演算是一种一阶逻辑语言，主要是用来表示动态变化的世界的。世界的所有变化过程都是,动作,的结果。
一个可能世界历史可以简单表示为动作的序列，它是通过称之为情景的一阶项所表示的。
常量 S0表示初始情景，即动作还没有发生时的情景。
do(?,s)表示在情景 s中 执行动作?之后的后继情景。
do(put(A,B),s)表示当世界状态为 s时，将 A放到 B上的结果这种情景。
do(putdown(A)),do(walk(L)),do(pickup(A))
是一种表示世界历史由动作序列 [pickup(A),walk(L),
putdown(A)]所组成的，它们按照从右到左的方式组织。
2009-8-20 史忠植 高级人工智能 69
定义 1 定义 Lsitcalc语言的动作理论 D为如下形式：
D = ∑? Dss? Dap? Duna? DSo
其中：
∑：基础的、针对情景演算的独立于领域的公理。
Dap：动作前提条件公理；
Dss：后续状态公理；
Duna：针对原子动作的唯一命名公理；
DSo：描述初始情形的公理。
2009-8-20 史忠植 高级人工智能 70
基于情景演算的一些基本理论和方法，我们利用它们来刻画主体的复杂动作和过程，将主体的各个部件加以描述。
<1> 原子动作
Do(a,s,s?) Poss(a[s],s) ∧ s? = do(a[s],s)
<2> 检验动作
Do(φ?,s,s?) φ[s] ∧ s = s?
<3> 顺序动作
Do([δ1,δ2],s,s?) (?s* ),Do([δ1],s,s* ) ∧ Do([δ2],s*,s?)
def＝
def＝
def＝
2009-8-20 史忠植 高级人工智能 71
<4> 两个动作的不确定选择
Do((δ1 | δ2),s,s?) (?s* ),Do(δ1,s,s?) ∨ Do(δ2,s,s?)def＝
<5> 动作参数的不确定选择
Do((πx) δ(x),s,s?) (?x),Do(δ(x),s,s?)def＝
<6> 不确定反复
Do(δ*,s,s?) (?P),{(?s1)P(s1,s1) ∧ (?s1,s2,s3)
[P(s1,s2) ∧ Do(δ,s2,s3)? P(s1,s3)]}
P(s,s?)
def＝
2009-8-20 史忠植 高级人工智能 72
动作理论与情景演算的研究
◆ MaCarthy针对动态领域中的问题求解和逻辑程序设计提出了情景演算 。
◆ Reiter,Fangzhen Lin,Pirria,Lifschitz等人主要将情景演算进行了一些扩充，对状态约束、动作理论、
动态关系等方面进行了深入的研究，并以数据库、机器人等动态领域为背景，做了一些逻辑程序设计以及应用等研究。
◆ Levesque和 Reiter提出了一种新的动态逻辑设计语言
Golog / ConGolog
◆ Baral等人重点对状态的描述、动作的表示与推理以及动态领域中的知识表示等方面做了一些工作，提出了一种逻辑程序设计语言 A-Prolog，
2009-8-20 史忠植 高级人工智能 73
参考文献
史忠植,,高级人工智能,,科学出版社，
1998。
陆钟万,,面向计算机科学的数理逻辑,,
科学出版社,2000。
王元元,,计算机科学中的逻辑学,,科学出版社,1989。
高级人工智能第二章 人工智能逻 辑史忠植中国科学院计算技术研究所
2009-8-20 史忠植 高级人工智能 2
第二章 人工智能逻辑
2.1 逻辑 -----重要的形式工具
2.2 非单调逻辑
2.3 默认逻辑
2.4 限定逻辑
2.5 自认知逻辑
2.6 真值维护系统
2.7 情景演算的逻辑基础
2.8 动态描述逻辑
2009-8-20 史忠植 高级人工智能 3
逻辑的历史
Aristotle—— 逻辑学
Leibnitz—— 数理逻辑
Gottlob Frege (1848-1925)—— 一阶谓词演算系统,,符号论,
20世纪 30年代，数理逻辑广泛发展
2009-8-20 史忠植 高级人工智能 4
重要的形式工具 ──逻辑在本世纪 30年代以后，数学方法广泛渗透与运用于数理逻辑，使得数理逻辑成为数学领域中与代数、几何等并列的学科之一。现代数理逻辑可以分为逻辑运算、证明论、公理集合论、递归论和模型论。
2009-8-20 史忠植 高级人工智能 5
关于知识的表示与推理智能行为的基础是知识，尤其是所谓的常识性知识。
人类的智能行为对于知识的依赖主要表现在对于知识的利用，即利用已经具有的知识进行分析、猜测、判断、
预测等等。人类利用知识可以预测未来，由已知的情况推测未知的情况、由发生的事件预测还未发生的事件等等。但是，当人们希望计算机具有智能行为时，除了告诉计算机如何像人一样地利用知识以外（对于知识进行推理），一个更为基础和先行的工作是如何使计算机具有知识（对于知识进行表示），即在计算机上如 何表达人类的知识。
2009-8-20 史忠植 高级人工智能 6
关于知识的表示与推理多数的基于逻辑的智能系统使用一阶逻辑或者它的一些扩张形式 。 一阶逻辑的优点是它具有相当强的表达能力 。 有的人工智能专家坚信所有的人工智能中的知识表示问题完全可以在一阶逻辑的框架中得以实现 。 一阶逻辑在表达不确定性知识时其表达能力也是很强的 。 例如,
x P(x)
表达在所考虑的论域中存在一个具有性质 P的对象,而具体的是哪一个对象具有此性质则是待确定的；再如,
P? Q
表示 P和 Q这两个性质之间有一个是成立的,至于到底是哪一个成立则是根据具体的情况而定的 。
2009-8-20 史忠植 高级人工智能 7
关于知识的表示与推理有人坚信从本质上看,一阶逻辑对于知识表示 是足够的,
但从实际应用的角度看,为方便,清楚和简洁起见,知识表示不一定非得从一阶逻辑出发 。 事实上,人 们从实际应用出发已经发明和建立了许多适用于不同目的的逻辑系统 。
(1) 为了表示关于认知的有关概念,如相信,知道,愿望,意图,目标,承诺等等,人们引进了刻划各种认知概念的 模态逻辑 ；
(2) 为了刻划智能系统中的时间因素,人们在逻辑系统中引进时间的概念,提出了各种 时序逻辑 ；
2009-8-20 史忠植 高级人工智能 8
关于知识的表示与推理
(3) 为了描述各种不确定的和不精确的概念,人们引进了所谓 模糊逻辑 ；模糊逻辑是直接建立在自然语言上的逻辑系统,
与其它逻辑系统相比较,它考虑了更多的自然语言的成分 。 按照其创始人 Zadeh的说法就是词语上的计算,表示为一个公式,即,
fuzzy logic＝ computing with words；
(4) 人类的知识与人类的活动是息息相关的,人类正是在各种活动和行为中获得知识的 。 因此,行为或者动作的概念在智能系统中是一个关键的概念 。 动作的概念与一般逻辑中的静态的概念很不相同,它是一个动态的概念,动作的发生影响着智能系统的性质 。 对于动作的考虑,给人工智能界带来了许多难题,如框架问题,量词问题等等 。 为了刻划动作的概念,人们引进了一些新的逻辑体系来刻划它 。
2009-8-20 史忠植 高级人工智能 9
关于知识的表示与推理
(5) 计算机对于人类进行决策时进行若干方面的支持已经成为计算机应用的一个重要方面 。 人类在决策时,对于各种方案和目标有一定的偏好和选择 。 这时,偏爱,就成为了一个基本的概念 。 为了表述和模拟人类在决策时的选择的规律和行为,
对于,偏爱,这个词的研究就是不可避免的 。 于是,基于管理科学的所谓的偏爱逻辑被提出并加以研究 。
(6) 时间是智能系统中最重要的几个概念之一 。 人类使用各类副词来对时间概念加以描述 。 例如,,一会儿,,相当长,,断断续续地,,偶尔,等等,这一类词在我们的日常生活中比比皆是 。 含有这些词的句子显然是很难用经典的时序逻辑来刻划的,于是有人引进了一种逻辑系统专门刻划这类句子 。 其基本思想是利用数学中积分的思想,通过对时间的某种像积分那样的表示和运算来形式化这些句子 。
2009-8-20 史忠植 高级人工智能 10
逻辑系统一个逻辑系统是定义语言和它的含义的方法。
逻辑系统中的一个逻辑理论是该逻辑的语言的一个语句集合，它包括：
逻辑符号集合,在所有该逻辑的逻辑理论中均出现的符号；
非逻辑符号集合,不同的逻辑理论中出现的不同的符号；
语句规则,定义什么样的符号串是有意义的；
证明,什么样的符号串是一个合理的证明；
语义规则,定义符号串的语义。
2009-8-20 史忠植 高级人工智能 11
逻辑 程序语言逻辑符号 保留字或者符号非逻辑符号 用户自定义的符号 (变量名，函数名等 )
语句规则 构造一个程序的语句规则语义规则 定义程序做什么的语句规则推理规则、公理和证明 没有逻辑与程序语言的对比
2009-8-20 史忠植 高级人工智能 12
在语法上，如果存在一个从假设?到?的证明，
则记为,称?由?可推导出的，或 可证明的 。
如果在没有任何假设下?是可推导出的，则记为
，称?为可证明的。
称一个假设?是 不协调的,如果存在一个语句?
使得?和?的否定均可由?推导得出。
称一个逻辑系统是 一致的,或 相容的 (consistent)，
如果不存在逻辑系统的公式 A，使得?A与A同时成立。
证 明 (语法 )
2009-8-20 史忠植 高级人工智能 13
一个 证明 是一个语法结构，它由符号串根据一定的规则组成。它包括假设和结论。
在公理化逻辑中，逻辑给出一个 逻辑公理 和 推理规则 的集合。推理规则是可以从一个语句的集合得到另一语句的集合。
公理化逻辑中的证明就是一个语句序列，使得其中的每个语句要么是逻辑公理，要么是一个假设，
要么是由前面的语句通过推理规则得到的。
证 明
2009-8-20 史忠植 高级人工智能 14
语言的 解释 是在某个论语 (domain)中定义非逻辑符号。语句的语义是在解释下定义出语言 L的真假值。
如果 I是 L的一个解释，且?在 I中为真，则记为
I,称作 I满足?,或者 I 是?的一个 模型 。
类似地，给定一个语句?和一个语句?,如果对每个解释 I,有 I 蕴含 I,换言之，如果 I 是?
的一个模型则 I也是?的一个模型，则记为,我们称?为?的一个 逻辑结果 。
解 释 (语义 )
2009-8-20 史忠植 高级人工智能 15
可靠性 (reliable)
一个逻辑是可靠的，如果它的证明保持真假值，
即在任何解释 I下，如果 I是? 的模型，且?可由?推导出，则 I也是?的一个模型。即，一个逻辑是可靠的，
如果对任何语句集合?和语句?,蕴涵 。
可靠性和完备性完备性 (complete)
一个逻辑是完备的，如果任何永真语句是可证的。
即，对任何语句集合?和语句?,蕴涵 。
如果一个逻辑是完备的，则该逻辑的证明系统已强到可以推出任何永真式。
G?del完备性定理,一阶逻辑是完备的
2009-8-20 史忠植 高级人工智能 16
可判定的一个逻辑称为是 可判定的 (decidable)，如果存在一个算法对逻辑中的任一公式 A，可确定? A是否成立。否则，称为是 不可判定的 (undecidable) 。
如果上述算法虽不一定存在，却有一个过程，可对该系统的定理做出肯定的判断，但对非定理的公式过程未必终止，因而未必能作出判断。这时称逻辑是 半可判定的 。
可判定性一阶逻辑是不可判定的，但它是半可判定的。
2009-8-20 史忠植 高级人工智能 17
命题逻辑
命题是可以确定其真假的陈述句。
Bolle提出了布尔代数。
语言,?,?； 公式，原子公式公理模式,
◆ (A?(B? A))
◆ ((A?(B? C))? ((A? B)?(A? C)))
◆ (((?A))?(?B)? (B? A))
推理规则,分离规则 (modus ponens,MP规则 )
B
BAA?,
2009-8-20 史忠植 高级人工智能 18
谓词逻辑 (一阶逻辑 )
Frege谓词演算语言,?,?,?,?,(,)；常元，变元，函词，谓词；公式公理模式,
◆ (A?(B? A))
◆ ((A?(B? C))? ((A? B)?(A? C)))
◆ (((?A)?(?B))? (B? A))
◆?vA? Atv (t对 A中变元 v可代入 )
◆?v(A?B)? (?vAvB)
◆ AvA (v在 A中无自由出现 )
推理规则,分离规则
B
BAA?,
2009-8-20 史忠植 高级人工智能 19
谓词逻辑与命题逻辑的区别
谓词逻辑给出了原子语句的内部结构，将原子公式看作是事物直接的关系；
它引入了“推广” (泛化 )，加强了逻辑的表示能力和推理能力。这样，我们可以说某种性质对某个对象是成立的，或对所有的对象成立，
或不对任何对象成立。
2009-8-20 史忠植 高级人工智能 20
逻辑程序设计
消解原理 (归结原理 )
Horn逻辑
Prolog逻辑程序设计语言
2009-8-20 史忠植 高级人工智能 21
归结原理例：
C1 =?P∨ Q∨ R C2 = P∨ Q
则 C1与 C2消解后的结果为,Q∨ R
若子句集 S能导出空子句?(有否证 )，则称 S
是不可满足的。
S? A iff SA
Q
QPP?,
Q
QPP,
2009-8-20 史忠植 高级人工智能 22
Horn逻辑
文字,原子公式 (正文字 )或原子公式的否定 (负文字 )。
P,Q,?R
子句,若干文字的析取。P∨ Q∨ R
Horn子句,
L1∨ L2∨ … ∨ Ln中如果至多只含一个正文字，
那么该子句称为 Horn子句。
Horn子句 P∨?Q1∨?Q2∨ … ∨?Qn通常表示为：
P? Q1,Q2,…,Qn
2009-8-20 史忠植 高级人工智能 23
Horn子句的类型：
◆ 过程,P? Q1,Q2,…,Qn
◆ 事实,P?
◆ 目标,? Q1,Q2,…,Qn
◆ 空子句,?
例,◆ 过程,AT(dog,x)? AT (Zhang,x)
◆ 事实,AT (Zhang,train)?
◆ 目标,? AT(dog,train)
首先目标中过程调用 AT(dog,train)与过程名 AT(dog,x)
匹配，合一为 {train/x}，调用过程 AT(Zhang,x)，从而产生新目标? AT (Zhang,train)，与事实匹配，产生目标? 。因而调用成功，输出,是,。
2009-8-20 史忠植 高级人工智能 24
Prolog
Prolog(Programming in logic)语言是以 Horn子句逻辑为基础的高级程序设计语言。
1972年，法国马赛大学的 Alain,Colmerauer提出了 Prolog的雏型。
1975年,Prolog被用于问题求解系统。
此后，它在许多领域获得了应用，如关系数据库、
定理证明、智能问题求解、计算机辅助设计、规划生成等领域。
2009-8-20 史忠植 高级人工智能 25
Prolog的构成
事实,关于对象性质和关系的事实语句；
student(john),married(tom,mary)
规则,关于对象性质和关系的定义规则语句；
它与事实的不同在于，规则所定义的性质、关系依赖与其它的性质和关系，因此规则呈蕴涵语句形式。
B:— A,如果 A则 B”
bird(x),— animal(x),has(x,feather)
问题,关于对象性质或关系的询问。
— student(john)
— married(mary,x)
2009-8-20 史忠植 高级人工智能 26
Prolog语言的基本文法
Prolog语言的最基本语言成分是项 (term)，一个项或者是常量，或者是变量，或者是一个结构。
常量,是指对象和对象之间的特定关系的名；
整数,如 0,22,1586等；
原子,如 John,student,likes,sister-of
变量,表示任意的对象，它与 FOL中的变元相同；
Prolog中变量可以用大写字母，下划线，以及由它们开头的字母串。如 X,Y,Answer,_value等。
结构,是常量和变量的序列，它由一个函子 (函词或谓词 )和该函子的自变量所组成。如：
likes(john,X) married(mary,jack)
2009-8-20 史忠植 高级人工智能 27
例：
(1) likes(bell,sports)
(2) likes(mary,smith)
(3) likes(mary,sports)
(4) likes(jones,smith)
(5) friend(john,X),— likes(X,sports),likes(X,smith) (规则 )
(6)?— friends(john,Y) (问题 )
(事实 )
(7)?— likes(X,sports),likes(X,smith)
(8)?— likes(bell,smith) (bell / X)
(7)?— likes(X,sports),likes(X,smith)
(8)?— likes(mary,smith) (mary / X)
Y = mary,John与 Mary是朋友
2009-8-20 史忠植 高级人工智能 28
Prolog的执行方式搜索,在程序中自上而下地搜索事实和规则；
匹配,将目标中的项与事实和规则进行匹配；
回溯,当目标中一项失败时，如果目标中有已经成功的的项 (应在失败项的左边 )，那末就重新调用这些成功项中最右边的一个，谋求新的成功。
2009-8-20 史忠植 高级人工智能 29
Prolog的基本特点
Horn子句逻辑是 Prolog的基础。
Prolog既是一种逻辑程序设计语言，又是一个逻辑系统。
Prolog是一种描述性语言，它是一种面向问题的语言，你只需要告诉它要做什么，即给出问题的形式描述，而不需要知道应该如何做。
Prolog完全依靠匹配、回溯 来进行搜索。 Prolog的求解过程是一个寻求否证的消解过程。
Prolog也使用元语言种的谓词，有很强的描述能力。
Prolog采用统一的数据结构 —— 项，它包含控制成分，且有专门进行数值计算和符号处理的模块。
2009-8-20 史忠植 高级人工智能 30
逻辑程序设计
PROLOG
B? A1,…,An
B?
A1,…,An
2009-8-20 史忠植 高级人工智能 31
单调逻辑
在现有知识的基础上，通过严密的逻辑论证和推理获得的新知识必须与已有的知识相一致。
A,A?B?B
推理系统的定理集合随着推理过程的进行而单调地增大。
单调性：
(1)?∈ Th(? )
(2) 若?12,则 Th(?1)? Th(?2)
(3) Th(Th(? )) ＝ Th(? ) (不动点 )
2009-8-20 史忠植 高级人工智能 32
非单调逻辑推理系统的定理集合并不随着推理过程的进行而单调地增大，新推出地定理很可能会否定、
改变原来地一些定理，使得原来能够解释地某些现象变得不能解释了。
新规则：
(4)P (不动点 )
2009-8-20 史忠植 高级人工智能 33
非单调逻辑推理系统的定理集合并不随推理过程的进行而单调地增大,新推出的定理很可能会否定、改变原来的一些定理,使得原来能够解释的某些 现象变得不能解释了。
2009-8-20 史忠植 高级人工智能 34
非单调逻辑推理系统的定理集合并不随推理过程的进行而单调地增大,新推出的定理很可能会否定、改变原来的一些定理,使得原来能够解释的某些 现象变得不能解释了。
t1<t2 F(t1)?F(t2)
2009-8-20 史忠植 高级人工智能 35
非单调逻辑鸟会飞鸵鸟是鸟所以,鸵鸟会飞
2009-8-20 史忠植 高级人工智能 36
非单调推理
1 John在时刻 t1是活着的
2 Dell在时刻 t2>t1把子弹装进枪膛
3 Dell在时刻 t3>t2举 枪对 John射击
4 问题,John在时刻 t4>t3还 是活着吗？
2009-8-20 史忠植 高级人工智能 37
非单调逻辑设?表示推理规则集,则单调逻辑语言
Th(?)={A|A}
(1)Th(?)
(2) if?12,then Th(?1)? Th(?2)
(3) Th(Th(?)) = Th(?) (不动点 )
(4) ifP,then MP
其中 M模态词
2009-8-20 史忠植 高级人工智能 38
默认 逻辑
1980年,Reiter提出了默认缺省逻辑 (Default Logic)。
“一般情况下鸟是会飞的”
“鸵鸟不会飞”,企鹅不会飞”
)(
)(:)(
xf l y
xM f l yxB i r d
会飞会飞”与系统不矛盾“是鸟
x
xx,
2009-8-20 史忠植 高级人工智能 39
默认 规则一个默认规则是如下形式的规则：
)(
)(,),(:)( 1
x
xMxMx n
(x):称为前提条件
i(x):称为缺省条件，或检验条件
(x):称为结论为简便，通常情况下可以省略检验条件中的 M。
规则的使用：
出检验条件的否定i(x)，则可以得出结论成立。
2009-8-20 史忠植 高级人工智能 40
默认理论一个 默认理论?由两个部分组成，即 默认 规则集 D和公式集 W，一般用二元组来表示?＝ <D,W >
若 D中的规则是闭规则时，则?为闭缺省理论。
定义,设?＝ <D,W >为一闭缺省理论,?为 关于 D的一个算子,?作用于任意的命题集合 S，而其值为满足下列三个性质的最小命题集合?(S)：
(1) W(S)
(2) Th(?(S)) =?(S)，其中 Th(?(S)) = {A|?(S)? A}
(3) 如果 D中有规则,
且?∈?(S),1,…,m?S,那么?∈?(S)
nMM,,,1?
2009-8-20 史忠植 高级人工智能 41
默认 理论的扩充定义,对命题集合 E，如果?(E) = E，则 E称为关于
D的算子?的 不动点 (fixpoint)。此时称 E为 默认 理论
＝ <D,W >的一个 扩充 (extension)。
例 1：设 D ＝ { },W ＝?，计算 默认理论?＝ <D,W >的 扩充。
F
C
C
B
B
A
:,:,:
＝ <D,W >有唯一的扩充 E ＝ Th({?B,?F})。
2009-8-20 史忠植 高级人工智能 42
例 2：设
D ＝ { }，
W ＝ {B,C?F∨A,A∧CE}，计算 默认 理论
＝ <D,W >的 扩充。
G
AFAEC
E
EAF
C
CB
A
A,:,:,:,:
＝ <D,W >有三个扩充
E1 ＝ Th(W?{A,C})
E2 ＝ Th(W?{A,E})
E3 ＝ Th(W?{C,E,G})
2009-8-20 史忠植 高级人工智能 43
封闭默认理论的扩展设封闭默认理论? = <D,W>,?为关于 D的一个算符,? 作用于任意的命题集合 S,其值为满足下列三个性质的最小命题集合?(S):
(1) W (S);
(2) Th(?(S)) =?(S); 这里,Th(? (S))为命题集 {A |?(S)
A};
(3)如果有默认规则
)(
)(,),(:)( 1
XW
XMXMX n
2009-8-20 史忠植 高级人工智能 44
封闭默认理论的扩展命题集合 E称为关于 D的算符?的固定点,如果?(E) =E,
此时又称 E为?= <D,W>$ 的一个扩充 。
有了扩充的概念,便可定义非单调的,推出,概念 。
如果命题 A包含在默认理论? 的一个扩充中,那么称 A在?
中可推出,记为 | 。
扩充 E必须 ① 含有所有的已知事实 ;
② 在关系 |? 下是封闭的 ;
③ 其前提被 E满足,默认条件与 E相容的任意默认的结论必须也在 E中 。
)(
)(,),(:)( 1
XW
XMXMX n
2009-8-20 史忠植 高级人工智能 45
封闭默认理论的扩展具有扩展的存在条件将显得十分重要 。 下面我们讨论三种情况 。
(1) 不含任何默认的理论 <{ },W>,这种理论退化到一阶逻辑理论,
在这里它虽有唯一的一个扩展 Th(W),但对默认推理毫无意义和作用 。
(2) 一个默认理论 <D,W>称为规范默认理论,如果 D中默认规则均有如下形式,
)(
)(:)(
XW
XMWX?
2009-8-20 史忠植 高级人工智能 46
封闭默认理论的扩展如果一个理论中的所有默认都是规范的,则该理论称为规范理论 。 由于每个规范默认的结论与其合理条件相同,因而这种缺省不会导致不一致性,不会证伪其它已用过的默认的合理条件 。 因此我们说规范默认理论是行为良好
(well-behaved) 的理论,并且可以证明,任何规范默认理论必定至少有一个扩充 。
2009-8-20 史忠植 高级人工智能 47
封闭默认理论的扩展
(3) 半规 范默 认 理论 (Seminormal Default
Theory),虽然规范默认理论至少有一个扩充,
从而保证了系统知识库 W的一致性 。 然而现实世界中许多事物,现象是无法用规范默认表示的,而用如下形式的默认则可有效地进行处理,
MMX?:)(
2009-8-20 史忠植 高级人工智能 48
封闭默认理论的扩展为了保证半规范默认理论具有一个扩充,
必须对它的默认加以限制,Reiter给出了一个半规范默认理论至少具有一个扩充的充分条件,
这个条件要求封闭的半规范默认理论是有序的,。 有序性建立在一个偏序关系?上,这个偏序要求,如果在推导 β的过程中用到了 α,则 α?
β。 Etheringthon在这种基础上给出了求算偏序关系及其扩充的算法,并讨论了算法的收敛性问题 。
2009-8-20 史忠植 高级人工智能 49
限定推理
1980年,McCarthy提出了一种非单调的推理 —
—
限定推理 (Circumscription)。
基本思想,从某些事实 A出发能够推出具有某一性质的 P的对象就是满足性质 P的全部对象。只有当发现其它对象也具有该性质时，才修改这种看法。
2009-8-20 史忠植 高级人工智能 50
限定逻辑限定逻辑 CIRC是一种极小化逻辑。下面，从一个基于极小模型定义的命题限定出发，给出限定的基本定义,进而给出一阶限定的基本结果，并将它推广。
定义 2.1 设 L0是一个命题语言,p1,p2是在命题语言 L0 中的两个赋值。称 p1小于 p2,记为 p1? p2,当且仅当对任一命题变元 x,如果 p1(x) = l,则 p2(x) = l。
2009-8-20 史忠植 高级人工智能 51
限定逻辑定义 2.2 设 A 是一个公式，称 A的一个赋值 p是极小的，当且仅当不存在 A的其它赋值 p'使得 p'? p。
显然,?是一个偏序关系。 p1? p2表示 p1包含的真命题比 p2 少。极小赋值包含的真命题极小。
定义 2.3 极小后承M。 设 A,B是两个公式,AM B
当且仅当 B在所有 A 的极小模型中都为真。
极小模型是非单调的，它以命题的极小化作为优先模型的准则。
2009-8-20 史忠植 高级人工智能 52
限定逻辑定义 2.4 设 A是一个包含命题集 P = {p1,p2,...,
pn} 的公式，一个 A的赋值 p称为? Z-极小赋值，当且仅当不存在 A的其它赋值 p‘使得 p? p’,定义如下：设 p1,
p2 是两个赋值,p1? Z- p2 当且仅当对任一 z? Z,
若 p1 (Z) = l,则 p2 (Z)= l。
2009-8-20 史忠植 高级人工智能 53
限定逻辑定义 2.5 命题限定P 或 CIRC(A,P)。设 A是一个包含命题集的公式,? 是一个公式,AP? 当且仅当? 在所有 A的? p- 极小赋值中都为真。
定理 2.1 Ap? 当且仅当 AP?
2009-8-20 史忠植 高级人工智能 54
限定逻辑定义 2.6 令 L是一个一阶语言,T是一个 L的公式，它包含谓词元组集?。设 M[T]和 M*[T]是公式 T的两个模型。
定义 M*[T]优先于 M[T],记为 M*[T]? M[T],当且仅当
(1) M和 M*有相同的对象域，
(2) 除?外，公式 T中所有的其它关系和函数常数在 M和 M*都有相同的解释，
(3)?在 M*中的外延是?在 M中的子集。
2009-8-20 史忠植 高级人工智能 55
限定逻辑一个理论 T的模型 M称为优先的，当且仅当不存在 T的其它模型 M'使得 M'M。
定义 2.7 Mm是?的最小模型，当且仅当
M Mm,M = Mm
2009-8-20 史忠植 高级人工智能 56
限定逻辑例如 设论域 D={1,2}
T=?x?y(P(y)?Q(x,y))
=[(P(1)?Q(1,1)) (P(2)?Q(1,2))]?
[(P(1)?Q(2,1)) (P(2)?Q(2,2))]
M,P(1) P(2) Q(1,1)? Q(1,2) Q(2,1)? Q(2,2)
T T F T F T
M*,P(1) P(2) Q(1,1)? Q(1,2) Q(2,1)? Q(2,2)
F T F T F T
2009-8-20 史忠植 高级人工智能 57
自认知逻辑
Moore 考虑自认知理论 T 对于一组初始前提 A 是可靠的，
当且仅当 T 中的每一个自认知解释器是一个 T 中的自认知模型，其中全部 A 的公式为真。一个理想的理性主体的信念必须满足下列条件：
(1) 设 P1,...,Pn? T,and P1,...,Pn Q,
则 Q? T。
(2) 设 P? T,则 BP? T。
(3) 设 P? T,则 ~BP? T。
2009-8-20 史忠植 高级人工智能 58
自认知逻辑在这种情况下，主体不能再得到更进一步的结论，
因此,Moore称上述理论为稳定自认知理论。当然，下列条件也成立：
(4) 如果 BP? T,则 P? T。
(5) 如果 ~ BP? T,则 P? T。
2009-8-20 史忠植 高级人工智能 59
真值维护系统 TMS
1979年,Doyle提出了一种非单调推理系统 ——
真值维护系统 (Truth Maintenance System)
真值维护系统是大型推理系统的的一个子系统，
实现知识库中信念 (belief)的修改与维护。其基本问题有：
必须在不完全的、有限的信息基础上作出假设的决策，使得该假设成为知识库的信念；
当这些决策的结论被以后的事实证明为错误时，如何对其信念进行修正。
2009-8-20 史忠植 高级人工智能 60
基本数据结构,
结点,表示信念理由,表示信念的原因信念既包括已知的知识，也包括假设的知识。
基本操作,
新结点的形成 —— 将信念赋予该结点；
新理由的加入 —— 把某个信念与该结点联接起来实现过程,
默认假设的形成；
相关性回溯过程。
2009-8-20 史忠植 高级人工智能 61
信念知识表示每一个命题或规则均称为结点，它分为两类：
IN-结点,相信为真
OUT-结点,不相信为真，或无理由相信为真，
或当前没有任何有效的理由。
每个结点附有理由表，表示具体结点的有效性：
支持表 SL,所在结点的信念的原因，理由；
条件证明 CP,出现矛盾的原因。
2009-8-20 史忠植 高级人工智能 62
(SL(<IN-结点表 >)(<OUT-结点表 >))
IN-结点表中的 IN-结点表示知识库中的已知知识 ;
OUT-结点表中的 OUT-结点表示这些结点的否定。
例 1:
(1) 现在是夏天 (SL( )( ))
(2) 天气很潮湿 (SL(1)( ))
结点 (1)不依赖于任何别的结点中的当前信念或默认信念,因而这种结点称为前提 ;
结点 (2)则依赖于当前结点 (1)的信念,
所以，与一阶逻辑不同的是,TMS可以撤消前提,
并可以对知识库作适当修改,
（ 1）支持表 SL
2009-8-20 史忠植 高级人工智能 63
例 2:
(1) 现在是夏天 (SL( )( ))
(2) 天气很潮湿 (SL(1)(3))
(3) 天气很干燥若结点 (1)是 IN,结点 (3)是 OUT,则结点 (2)才为 IN.
若在某个时刻出现结点 (3)的证据,则结点 (2)就变为
OUT,因为它不再有一个有效的证实,象结点 (2)这样的结点称为假设,它与非空的 OUT结点表的 SL证实有关,OUT结点 (3)是结点 (2)的证实的一部分,但如果结点 (3)不存在,就不能这样表示了,
在 TMS中,它仅利用证实来维持一个相容的信念数据库,而它本身并不产生证实,
2009-8-20 史忠植 高级人工智能 64
(CP <结论 > <IN-假设 > <OUT-假设 >)
如果结论结点为 IN-结点,以及下列条件成立,
(1) IN假设中的每个结点都是 IN-结点 ;
(2) OUT-假设中的每个结点都是 OUT-结点,
那么条件证明 CP是有效的,
一般说来,OUT-假设总是空集,TMS要求假设集划分成两个不相交的子集,分别为不导致矛盾的假设和导致矛盾的假设,
通常只要在 IN-假设中的结点为 IN,OUT-假设中的结点为 OUT,则结论结点为 IN.
（ 2）条件证明 CP
2009-8-20 史忠植 高级人工智能 65
默认假设令 {F1,F2,…,Fn}表示所有可能的侯选的默认假设结点集,G表示选择默认假设的原因的结点,即由 G
引起在 {F1,…,Fn}中进行缺省选择,这样我们结合结点 Node(Fi)以如下理由,
(SL(G)(F1,…,Fi-1,Fi+1,…,Fn))
而选取 Fi为默认假设,
如果不存在任何其它关于如何进行选择的信息，
则可以认为除 Fi之外其它任何时候选都不是可信的．
这样 Fi为 IN,其它 Fj(i? j)均为 OUT.但如果接收到一个有效的理由支持某个其它的侯选 Fj,则 Fj就为 IN,
而导致 Fi的假设失败而变为 OUT.
2009-8-20 史忠植 高级人工智能 66
相关回溯当知识库中出现不一致时,TMS将寻找并删除已做的一个不正确的默认逻辑,恢复一致性,它包括三个步骤,
(1) 从产生的矛盾结点开始,回溯跟踪该矛盾结点的理由充足的支持以寻找矛盾的假设集,并从中去掉至少一个假设信念以消除矛盾,
(2) 构造一个结点记录矛盾产生的原因,
(3) 从 S中选取假设 A(即不合理假设 ),并证实列在其理由充足的支持条件中的一个 OUT-结点,
2009-8-20 史忠植 高级人工智能 67
(4) 矛盾 (SL(1,3)( ))
(周三 14:00没有空会议室 )
例 3:
(1) 会议日期为星期三 (SL( )(2))
(2) 会议日期不应是星期三
(3) 会议时间为 14:00 (SL(32,40,61)())
(5) 不相容 (CP4 (1,3)( ))
(2) 会议日期不应是星期三 (SL(5)( ))
结点 (2)与结点 (5)为 IN,就引起结点 (1)为 OUT,因为结点 (1)的证实依赖于结点 (2)是 OUT.结点 (4)现在也变成 OUT.进而矛盾就消除了,
2009-8-20 史忠植 高级人工智能 68
情景演算情景演算是一种一阶逻辑语言，主要是用来表示动态变化的世界的。世界的所有变化过程都是,动作,的结果。
一个可能世界历史可以简单表示为动作的序列，它是通过称之为情景的一阶项所表示的。
常量 S0表示初始情景，即动作还没有发生时的情景。
do(?,s)表示在情景 s中 执行动作?之后的后继情景。
do(put(A,B),s)表示当世界状态为 s时，将 A放到 B上的结果这种情景。
do(putdown(A)),do(walk(L)),do(pickup(A))
是一种表示世界历史由动作序列 [pickup(A),walk(L),
putdown(A)]所组成的，它们按照从右到左的方式组织。
2009-8-20 史忠植 高级人工智能 69
定义 1 定义 Lsitcalc语言的动作理论 D为如下形式：
D = ∑? Dss? Dap? Duna? DSo
其中：
∑：基础的、针对情景演算的独立于领域的公理。
Dap：动作前提条件公理；
Dss：后续状态公理；
Duna：针对原子动作的唯一命名公理；
DSo：描述初始情形的公理。
2009-8-20 史忠植 高级人工智能 70
基于情景演算的一些基本理论和方法，我们利用它们来刻画主体的复杂动作和过程，将主体的各个部件加以描述。
<1> 原子动作
Do(a,s,s?) Poss(a[s],s) ∧ s? = do(a[s],s)
<2> 检验动作
Do(φ?,s,s?) φ[s] ∧ s = s?
<3> 顺序动作
Do([δ1,δ2],s,s?) (?s* ),Do([δ1],s,s* ) ∧ Do([δ2],s*,s?)
def＝
def＝
def＝
2009-8-20 史忠植 高级人工智能 71
<4> 两个动作的不确定选择
Do((δ1 | δ2),s,s?) (?s* ),Do(δ1,s,s?) ∨ Do(δ2,s,s?)def＝
<5> 动作参数的不确定选择
Do((πx) δ(x),s,s?) (?x),Do(δ(x),s,s?)def＝
<6> 不确定反复
Do(δ*,s,s?) (?P),{(?s1)P(s1,s1) ∧ (?s1,s2,s3)
[P(s1,s2) ∧ Do(δ,s2,s3)? P(s1,s3)]}
P(s,s?)
def＝
2009-8-20 史忠植 高级人工智能 72
动作理论与情景演算的研究
◆ MaCarthy针对动态领域中的问题求解和逻辑程序设计提出了情景演算 。
◆ Reiter,Fangzhen Lin,Pirria,Lifschitz等人主要将情景演算进行了一些扩充，对状态约束、动作理论、
动态关系等方面进行了深入的研究，并以数据库、机器人等动态领域为背景，做了一些逻辑程序设计以及应用等研究。
◆ Levesque和 Reiter提出了一种新的动态逻辑设计语言
Golog / ConGolog
◆ Baral等人重点对状态的描述、动作的表示与推理以及动态领域中的知识表示等方面做了一些工作，提出了一种逻辑程序设计语言 A-Prolog，
2009-8-20 史忠植 高级人工智能 73
参考文献
史忠植,,高级人工智能,,科学出版社，
1998。
陆钟万,,面向计算机科学的数理逻辑,,
科学出版社,2000。
王元元,,计算机科学中的逻辑学,,科学出版社,1989。
