人工智能逻辑中国科学院计算技术研究所智能信息处理重点实验室主要内容逻辑简介逻辑程序设计非单调逻辑缺省逻辑限定逻辑真值维护系统情景演算
1,逻辑简介逻辑的历史逻辑系统命题逻辑谓词逻辑
1.1 逻辑的历史
Aristotle—— 逻辑学
Leibnitz—— 数理逻辑
Gottlob Frege (1848-1925)—— 一阶谓词演算系统,,符号论,
20世纪 30年代，数理逻辑广泛发展
1.2 逻辑系统一个逻辑系统是定义语言和它的含义的方法。
逻辑系统中的一个逻辑理论是该逻辑的语言的一个语句集合，它包括：
逻辑符号集合,在所有该逻辑的逻辑理论中均出现的符号；
非逻辑符号集合,不同的逻辑理论中出现的不同的符号；
语句规则,定义什么样的符号串是有意义的；
证明,什么样的符号串是一个合理的证明；
语义规则,定义符号串的语义。
逻辑 程序语言逻辑符号 保留字或者符号非逻辑符号 用户自定义的符号 (变量名，函数名等 )
语句规则 构造一个程序的语句规则语义规则 定义程序做什么的语句规则推理规则、公理和证明 没有逻辑与程序语言的对比一个 证明 是一个语法结构，它由符号串根据一定的规则组成。它包括假设和结论。
逻辑公理 和 推理规则 的集合。推理规则是可以从一个语句的集合得到另一语句的集合。
公理化逻辑中的证明就是一个语句序列，使得其中的每个语句要么是逻辑公理，要么是一个假设，
要么是由前面的语句通过推理规则得到的。
在语法上，如果存在一个从假设?到?的证明，
则记为,称?由?可推导出的，或 可证明的 。
是可推导出的，则记为
,称?为可证明的。
是 不协调的,如果存在一个语句?
使得?和?的否定均可由?推导得出。
一致的,或 相容的 (consistent)，
如果不存在逻辑系统的公式 A，使得?A与A同时成立。
证 明 (语法 )
语言的 解释 是在某个论语 (domain)中定义非逻辑符号。语句的语义是在解释下定义出语言 L的真假值。
I是 L的一个解释，且?在 I中为真，则记为
I,称作 I满足?,或者 I 是?的一个 模型 。
和一个语句?,如果对每个解释 I,有 I 蕴含 I,换言之，如果 I 是?
的一个模型则 I也是?的一个模型，则记为,我们称?为?的一个 逻辑结果 。
解 释 (语义 )
可靠性 (reliable)
一个逻辑是可靠的，如果它的证明保持真假值，
即在任何解释 I下，如果 I是? 的模型，且?可由?推导出，则 I也是?的一个模型。即，一个逻辑是可靠的，
如果对任何语句集合?和语句?,蕴涵 。
可靠性和完备性完备性 (complete)
一个逻辑是完备的，如果任何永真语句是可证的。
即，对任何语句集合?和语句?,蕴涵 。
如果一个逻辑是完备的，则该逻辑的证明系统已强到可以推出任何永真式。
G?del完备性定理,一阶逻辑是完备的可判定的可判定的 (decidable)，如果存在一个算法对逻辑中的任一公式 A，可确定? A是否成立。否则，称为是 不可判定的 (undecidable) 。
对该系统的定理做出肯定的判断，但对非定理的公式过程未必终止，因而未必能作出判断。这时称逻辑是 半可判定的 。
可判定性一阶逻辑是不可判定的，但它是半可判定的。
1.3 命题逻辑命题是可以确定其真假的陈述句。
Bolle提出了布尔代数。
语言,?,?； 公式，原子公式公理模式,
◆ (A?(B? A))
◆ ((A?(B? C))? ((A? B)?(A? C)))
◆ (((?A))?(?B)? (B? A))
推理规则,分离规则 (modus ponens,MP规则 )
B
BAA?,
1.4 谓词逻辑 (一阶逻辑 )
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?,
谓词逻辑与命题逻辑的区别
谓词逻辑给出了原子语句的内部结构，将原子公式看作是事物直接的关系；
它引入了“推广” (泛化 )，加强了逻辑的表示能力和推理能力。这样，我们可以说某种性质对某个对象是成立的，或对所有的对象成立，
或不对任何对象成立。
2,逻辑程序设计消解原理 (归结原理 )
Horn逻辑
Prolog逻辑程序设计语言
2.1 消解原理例：
C1 =?P∨ Q∨ R C2 = P∨ Q
则 C1与 C2消解后的结果为,Q∨ R
若子句集 S能导出空子句?(有否证 )，则称 S
是不可满足的。
S? A iff SA
Q
QPP?,
Q
QPP,
2.2 Horn逻辑文字,原子公式 (正文字 )或原子公式的否定 (负文字 )。
P,Q,?R
子句,若干文字的析取。P∨ Q∨ R
Horn子句,
L1∨ L2∨ … ∨ Ln中如果至多只含一个正文字，
那么该子句称为 Horn子句。
Horn子句 P∨?Q1∨?Q2∨ … ∨?Qn通常表示为：
P? Q1,Q2,…,Qn
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)，与事实匹配，产生目标? 。因而调用成功，输出,是,。
2.3 Prolog
Prolog(Programming in logic)语言是以 Horn子句逻辑为基础的高级程序设计语言。
1972年，法国马赛大学的 Alain,Colmerauer提出了 Prolog的雏型。
1975年,Prolog被用于问题求解系统。
此后，它在许多领域获得了应用，如关系数据库、
定理证明、智能问题求解、计算机辅助设计、规划生成等领域。
Prolog的构成事实,关于对象性质和关系的事实语句；
student(john),married(tom,mary)
规则,关于对象性质和关系的定义规则语句；
它与事实的不同在于，规则所定义的性质、关系依赖与其它的性质和关系，因此规则呈蕴涵语句形式。
B:— A,如果 A则 B”
bird(x),— animal(x),has(x,feather)
问题,关于对象性质或关系的询问。
— student(john)
— married(mary,x)
Prolog的执行方式搜索,在程序中自上而下地搜索事实和规则；
匹配,将目标中的项与事实和规则进行匹配；
回溯,当目标中一项失败时，如果目标中有已经成功的的项 (应在失败项的左边 )，那末就重新调用这些成功项中最右边的一个，谋求新的成功。
Prolog语言的基本文法
Prolog语言的最基本语言成分是 项 (term)，一个项或者是 常量,或者是 变量,或者是一个 结构 。
常量,是指对象和对象之间的特定关系的名；
整数,如 0,22,1586等；
原子,如 John,student,likes,sister-of
变量,表示任意的对象，它与 FOL中的变元相同；
Prolog中变量可以用大写字母，下划线，以及由它们开头的字母串。如 X,Y,Answer,_value等。
结构,是常量和变量的序列，它由一个函子 (函词或谓词 )和该函子的自变量所组成。如：
likes(john,X) married(mary,jack)
例：
(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是朋友
Prolog的基本特点
Horn子句逻辑是 Prolog的基础。
Prolog既是一种逻辑程序设计语言，又是一个逻辑系统。
Prolog是一种描述性语言，它是一种面向问题的语言，你只需要告诉它要做什么，即给出问题的形式描述，而不需要知道应该如何做。
Prolog完全依靠匹配、回溯 来进行搜索。 Prolog的求解过程是一个寻求否证的消解过程。
Prolog也使用元语言种的谓词，有很强的描述能力。
Prolog采用统一的数据结构 —— 项，它包含控制成分，且有专门进行数值计算和符号处理的模块。
3,非单调逻辑单调逻辑非单调逻辑区别
3.1 单调逻辑在现有知识的基础上，通过严密的逻辑论证和推理获得的新知识必须与已有的知识相一致。
A,A?B?B
推理系统的定理集合随着推理过程的进行而单调地增大。
单调性：
(1)?∈ Th(? )
(2) 若?12,则 Th(?1)? Th(?2)
(3) Th(Th(? )) ＝ Th(? ) (不动点 )
3.2 非单调逻辑推理系统的定理集合并不随着推理过程的进行而单调地增大，新推出地定理很可能会否定、
改变原来地一些定理，使得原来能够解释地某些现象变得不能解释了。
新规则：
(4)P (不动点 )
4,缺省逻辑
1980年,Reiter提出了缺省逻辑 (Default Logic)。
,一般情况下鸟是会飞的,
,鸵鸟不会飞,,企鹅不会飞,
)(
)(:)(
xf l y
xM f l yxB i r d
会飞会飞”与系统不矛盾“是鸟
x
xx,
4.1 缺省规则一个缺省规则是如下形式的规则：
)(
)(,),(:)( 1
x
xMxMx n
(x):称为前提条件
i(x):称为缺省条件，或检验条件
(x):称为结论为简便，通常情况下可以省略检验条件中的 M。
规则的使用：
出检验条件的否定i(x)，则可以得出结论成立。
4.2 缺省理论一个 缺省理论?由两个部分组成，即缺省规则集 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?
4.3 缺省理论的扩充定义,对命题集合 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})。
例 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})
5.限定推理
1980年,McCarthy提出了一种非单调的推理 —
—
限定推理 (Circumscription)。
基本思想,从某些事实 A出发能够推出具有某一性质的 P的对象就是满足性质 P的全部对象。只有当发现其它对象也具有该性质时，才修改这种看法。
6.真值维护系统 TMS
1979年,Doyle提出了一种非单调推理系统 ——
真值维护系统 (Truth Maintenance System)
真值维护系统是大型推理系统的的一个子系统，
实现知识库中信念 (belief)的修改与维护。其基本问题有：
必须在不完全的、有限的信息基础上作出假设的决策，使得该假设成为知识库的信念；
当这些决策的结论被以后的事实证明为错误时，如何对其信念进行修正。
基本数据结构,
结点,表示信念理由,表示信念的原因信念既包括已知的知识，也包括假设的知识。
基本操作,
新结点的形成 —— 将信念赋予该结点；
新理由的加入 —— 把某个信念与该结点联接起来实现过程,
默认假设的形成；
相关性回溯过程。
6.1 信念知识表示每一个命题或规则均称为结点，它分为两类：
IN-结点,相信为真
OUT-结点,不相信为真，或无理由相信为真，
或当前没有任何有效的理由。
每个结点附有理由表，表示具体结点的有效性：
支持表 SL,所在结点的信念的原因，理由；
条件证明 CP,出现矛盾的原因。
(SL(<IN-结点表 >)(<OUT-结点表 >))
IN-结点表中的 IN-结点表示知识库中的已知知识 ;
OUT-结点表中的 OUT-结点表示这些结点的否定。
例 1:
(1) 现在是夏天 (SL( )( ))
(2) 天气很潮湿 (SL(1)( ))
结点 (1)不依赖于任何别的结点中的当前信念或默认信念,因而这种结点称为前提 ;
结点 (2)则依赖于当前结点 (1)的信念,
所以，与一阶逻辑不同的是,TMS可以撤消前提,
并可以对知识库作适当修改,
（ 1）支持表 SL
例 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中,它仅利用证实来维持一个相容的信念数据库,而它本身并不产生证实,
(CP <结论 > <IN-假设 > <OUT-假设 >)
如果结论结点为 IN-结点,以及下列条件成立,
(1) IN假设中的每个结点都是 IN-结点 ;
(2) OUT-假设中的每个结点都是 OUT-结点,
那么条件证明 CP是 有效的,
一般说来,OUT-假设总是空集,TMS要求假设集划分成两个不相交的子集,分别为不导致矛盾的假设和导致矛盾的假设,
通常只要在 IN-假设中的结点为 IN,OUT-假设中的结点为 OUT,则结论结点为 IN.
（ 2）条件证明 CP
6.2 默认假设令 {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.
6.3 相关回溯当知识库中出现不一致时,TMS将寻找并删除已做的一个不正确的默认逻辑,恢复一致性,它包括三个步骤,
(1) 从产生的矛盾结点开始,回溯跟踪该矛盾结点的理由充足的支持以寻找矛盾的假设集,并从中去掉至少一个假设信念以消除矛盾,
(2) 构造一个结点记录矛盾产生的原因,
(3) 从 S中选取假设 A(即不合理假设 ),并证实列在其理由充足的支持条件中的一个 OUT-结点,
(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.进而矛盾就消除了,
7 情景演算情景演算是一种一阶逻辑语言，主要是用来表示动态变化的世界的。世界的所有变化过程都是,动作,的结果。
一个可能世界历史可以简单表示为动作的序列，它是通过称之为情景的一阶项所表示的。
常量 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)]所组成的，它们按照从右到左的方式组织。
定义 1 定义 Lsitcalc语言的动作理论 D为如下形式：
D = ∑? Dss? Dap? Duna? DSo
其中：
∑：基础的、针对情景演算的独立于领域的公理。
Dap：动作前提条件公理；
Dss：后续状态公理；
Duna：针对原子动作的唯一命名公理；
DSo：描述初始情形的公理。
基于情景演算的一些基本理论和方法，我们利用它们来刻画主体的复杂动作和过程，将主体的各个部件加以描述。
<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＝
<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＝
动作理论与情景演算的研究
◆ MaCarthy针对动态领域中的问题求解和逻辑程序设计提出了情景演算 。
◆ Reiter,Fangzhen Lin,Pirria,Lifschitz等人主要将情景演算进行了一些扩充，对状态约束、动作理论、
动态关系等方面进行了深入的研究，并以数据库、机器人等动态领域为背景，做了一些逻辑程序设计以及应用等研究。
◆ Levesque和 Reiter提出了一种新的动态逻辑设计语言
Golog / ConGolog
◆ Baral等人重点对状态的描述、动作的表示与推理以及动态领域中的知识表示等方面做了一些工作，提出了一种逻辑程序设计语言 A-Prolog，
参考文献史忠植,,高级人工智能,,科学出版社，
1998。
陆钟万,,面向计算机科学的数理逻辑,,
科学出版社,2000。
王元元,,计算机科学中的逻辑学,,科学出版社,1989。
1,逻辑简介逻辑的历史逻辑系统命题逻辑谓词逻辑
1.1 逻辑的历史
Aristotle—— 逻辑学
Leibnitz—— 数理逻辑
Gottlob Frege (1848-1925)—— 一阶谓词演算系统,,符号论,
20世纪 30年代，数理逻辑广泛发展
1.2 逻辑系统一个逻辑系统是定义语言和它的含义的方法。
逻辑系统中的一个逻辑理论是该逻辑的语言的一个语句集合，它包括：
逻辑符号集合,在所有该逻辑的逻辑理论中均出现的符号；
非逻辑符号集合,不同的逻辑理论中出现的不同的符号；
语句规则,定义什么样的符号串是有意义的；
证明,什么样的符号串是一个合理的证明；
语义规则,定义符号串的语义。
逻辑 程序语言逻辑符号 保留字或者符号非逻辑符号 用户自定义的符号 (变量名，函数名等 )
语句规则 构造一个程序的语句规则语义规则 定义程序做什么的语句规则推理规则、公理和证明 没有逻辑与程序语言的对比一个 证明 是一个语法结构，它由符号串根据一定的规则组成。它包括假设和结论。
逻辑公理 和 推理规则 的集合。推理规则是可以从一个语句的集合得到另一语句的集合。
公理化逻辑中的证明就是一个语句序列，使得其中的每个语句要么是逻辑公理，要么是一个假设，
要么是由前面的语句通过推理规则得到的。
在语法上，如果存在一个从假设?到?的证明，
则记为,称?由?可推导出的，或 可证明的 。
是可推导出的，则记为
,称?为可证明的。
是 不协调的,如果存在一个语句?
使得?和?的否定均可由?推导得出。
一致的,或 相容的 (consistent)，
如果不存在逻辑系统的公式 A，使得?A与A同时成立。
证 明 (语法 )
语言的 解释 是在某个论语 (domain)中定义非逻辑符号。语句的语义是在解释下定义出语言 L的真假值。
I是 L的一个解释，且?在 I中为真，则记为
I,称作 I满足?,或者 I 是?的一个 模型 。
和一个语句?,如果对每个解释 I,有 I 蕴含 I,换言之，如果 I 是?
的一个模型则 I也是?的一个模型，则记为,我们称?为?的一个 逻辑结果 。
解 释 (语义 )
可靠性 (reliable)
一个逻辑是可靠的，如果它的证明保持真假值，
即在任何解释 I下，如果 I是? 的模型，且?可由?推导出，则 I也是?的一个模型。即，一个逻辑是可靠的，
如果对任何语句集合?和语句?,蕴涵 。
可靠性和完备性完备性 (complete)
一个逻辑是完备的，如果任何永真语句是可证的。
即，对任何语句集合?和语句?,蕴涵 。
如果一个逻辑是完备的，则该逻辑的证明系统已强到可以推出任何永真式。
G?del完备性定理,一阶逻辑是完备的可判定的可判定的 (decidable)，如果存在一个算法对逻辑中的任一公式 A，可确定? A是否成立。否则，称为是 不可判定的 (undecidable) 。
对该系统的定理做出肯定的判断，但对非定理的公式过程未必终止，因而未必能作出判断。这时称逻辑是 半可判定的 。
可判定性一阶逻辑是不可判定的，但它是半可判定的。
1.3 命题逻辑命题是可以确定其真假的陈述句。
Bolle提出了布尔代数。
语言,?,?； 公式，原子公式公理模式,
◆ (A?(B? A))
◆ ((A?(B? C))? ((A? B)?(A? C)))
◆ (((?A))?(?B)? (B? A))
推理规则,分离规则 (modus ponens,MP规则 )
B
BAA?,
1.4 谓词逻辑 (一阶逻辑 )
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?,
谓词逻辑与命题逻辑的区别
谓词逻辑给出了原子语句的内部结构，将原子公式看作是事物直接的关系；
它引入了“推广” (泛化 )，加强了逻辑的表示能力和推理能力。这样，我们可以说某种性质对某个对象是成立的，或对所有的对象成立，
或不对任何对象成立。
2,逻辑程序设计消解原理 (归结原理 )
Horn逻辑
Prolog逻辑程序设计语言
2.1 消解原理例：
C1 =?P∨ Q∨ R C2 = P∨ Q
则 C1与 C2消解后的结果为,Q∨ R
若子句集 S能导出空子句?(有否证 )，则称 S
是不可满足的。
S? A iff SA
Q
QPP?,
Q
QPP,
2.2 Horn逻辑文字,原子公式 (正文字 )或原子公式的否定 (负文字 )。
P,Q,?R
子句,若干文字的析取。P∨ Q∨ R
Horn子句,
L1∨ L2∨ … ∨ Ln中如果至多只含一个正文字，
那么该子句称为 Horn子句。
Horn子句 P∨?Q1∨?Q2∨ … ∨?Qn通常表示为：
P? Q1,Q2,…,Qn
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)，与事实匹配，产生目标? 。因而调用成功，输出,是,。
2.3 Prolog
Prolog(Programming in logic)语言是以 Horn子句逻辑为基础的高级程序设计语言。
1972年，法国马赛大学的 Alain,Colmerauer提出了 Prolog的雏型。
1975年,Prolog被用于问题求解系统。
此后，它在许多领域获得了应用，如关系数据库、
定理证明、智能问题求解、计算机辅助设计、规划生成等领域。
Prolog的构成事实,关于对象性质和关系的事实语句；
student(john),married(tom,mary)
规则,关于对象性质和关系的定义规则语句；
它与事实的不同在于，规则所定义的性质、关系依赖与其它的性质和关系，因此规则呈蕴涵语句形式。
B:— A,如果 A则 B”
bird(x),— animal(x),has(x,feather)
问题,关于对象性质或关系的询问。
— student(john)
— married(mary,x)
Prolog的执行方式搜索,在程序中自上而下地搜索事实和规则；
匹配,将目标中的项与事实和规则进行匹配；
回溯,当目标中一项失败时，如果目标中有已经成功的的项 (应在失败项的左边 )，那末就重新调用这些成功项中最右边的一个，谋求新的成功。
Prolog语言的基本文法
Prolog语言的最基本语言成分是 项 (term)，一个项或者是 常量,或者是 变量,或者是一个 结构 。
常量,是指对象和对象之间的特定关系的名；
整数,如 0,22,1586等；
原子,如 John,student,likes,sister-of
变量,表示任意的对象，它与 FOL中的变元相同；
Prolog中变量可以用大写字母，下划线，以及由它们开头的字母串。如 X,Y,Answer,_value等。
结构,是常量和变量的序列，它由一个函子 (函词或谓词 )和该函子的自变量所组成。如：
likes(john,X) married(mary,jack)
例：
(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是朋友
Prolog的基本特点
Horn子句逻辑是 Prolog的基础。
Prolog既是一种逻辑程序设计语言，又是一个逻辑系统。
Prolog是一种描述性语言，它是一种面向问题的语言，你只需要告诉它要做什么，即给出问题的形式描述，而不需要知道应该如何做。
Prolog完全依靠匹配、回溯 来进行搜索。 Prolog的求解过程是一个寻求否证的消解过程。
Prolog也使用元语言种的谓词，有很强的描述能力。
Prolog采用统一的数据结构 —— 项，它包含控制成分，且有专门进行数值计算和符号处理的模块。
3,非单调逻辑单调逻辑非单调逻辑区别
3.1 单调逻辑在现有知识的基础上，通过严密的逻辑论证和推理获得的新知识必须与已有的知识相一致。
A,A?B?B
推理系统的定理集合随着推理过程的进行而单调地增大。
单调性：
(1)?∈ Th(? )
(2) 若?12,则 Th(?1)? Th(?2)
(3) Th(Th(? )) ＝ Th(? ) (不动点 )
3.2 非单调逻辑推理系统的定理集合并不随着推理过程的进行而单调地增大，新推出地定理很可能会否定、
改变原来地一些定理，使得原来能够解释地某些现象变得不能解释了。
新规则：
(4)P (不动点 )
4,缺省逻辑
1980年,Reiter提出了缺省逻辑 (Default Logic)。
,一般情况下鸟是会飞的,
,鸵鸟不会飞,,企鹅不会飞,
)(
)(:)(
xf l y
xM f l yxB i r d
会飞会飞”与系统不矛盾“是鸟
x
xx,
4.1 缺省规则一个缺省规则是如下形式的规则：
)(
)(,),(:)( 1
x
xMxMx n
(x):称为前提条件
i(x):称为缺省条件，或检验条件
(x):称为结论为简便，通常情况下可以省略检验条件中的 M。
规则的使用：
出检验条件的否定i(x)，则可以得出结论成立。
4.2 缺省理论一个 缺省理论?由两个部分组成，即缺省规则集 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?
4.3 缺省理论的扩充定义,对命题集合 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})。
例 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})
5.限定推理
1980年,McCarthy提出了一种非单调的推理 —
—
限定推理 (Circumscription)。
基本思想,从某些事实 A出发能够推出具有某一性质的 P的对象就是满足性质 P的全部对象。只有当发现其它对象也具有该性质时，才修改这种看法。
6.真值维护系统 TMS
1979年,Doyle提出了一种非单调推理系统 ——
真值维护系统 (Truth Maintenance System)
真值维护系统是大型推理系统的的一个子系统，
实现知识库中信念 (belief)的修改与维护。其基本问题有：
必须在不完全的、有限的信息基础上作出假设的决策，使得该假设成为知识库的信念；
当这些决策的结论被以后的事实证明为错误时，如何对其信念进行修正。
基本数据结构,
结点,表示信念理由,表示信念的原因信念既包括已知的知识，也包括假设的知识。
基本操作,
新结点的形成 —— 将信念赋予该结点；
新理由的加入 —— 把某个信念与该结点联接起来实现过程,
默认假设的形成；
相关性回溯过程。
6.1 信念知识表示每一个命题或规则均称为结点，它分为两类：
IN-结点,相信为真
OUT-结点,不相信为真，或无理由相信为真，
或当前没有任何有效的理由。
每个结点附有理由表，表示具体结点的有效性：
支持表 SL,所在结点的信念的原因，理由；
条件证明 CP,出现矛盾的原因。
(SL(<IN-结点表 >)(<OUT-结点表 >))
IN-结点表中的 IN-结点表示知识库中的已知知识 ;
OUT-结点表中的 OUT-结点表示这些结点的否定。
例 1:
(1) 现在是夏天 (SL( )( ))
(2) 天气很潮湿 (SL(1)( ))
结点 (1)不依赖于任何别的结点中的当前信念或默认信念,因而这种结点称为前提 ;
结点 (2)则依赖于当前结点 (1)的信念,
所以，与一阶逻辑不同的是,TMS可以撤消前提,
并可以对知识库作适当修改,
（ 1）支持表 SL
例 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中,它仅利用证实来维持一个相容的信念数据库,而它本身并不产生证实,
(CP <结论 > <IN-假设 > <OUT-假设 >)
如果结论结点为 IN-结点,以及下列条件成立,
(1) IN假设中的每个结点都是 IN-结点 ;
(2) OUT-假设中的每个结点都是 OUT-结点,
那么条件证明 CP是 有效的,
一般说来,OUT-假设总是空集,TMS要求假设集划分成两个不相交的子集,分别为不导致矛盾的假设和导致矛盾的假设,
通常只要在 IN-假设中的结点为 IN,OUT-假设中的结点为 OUT,则结论结点为 IN.
（ 2）条件证明 CP
6.2 默认假设令 {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.
6.3 相关回溯当知识库中出现不一致时,TMS将寻找并删除已做的一个不正确的默认逻辑,恢复一致性,它包括三个步骤,
(1) 从产生的矛盾结点开始,回溯跟踪该矛盾结点的理由充足的支持以寻找矛盾的假设集,并从中去掉至少一个假设信念以消除矛盾,
(2) 构造一个结点记录矛盾产生的原因,
(3) 从 S中选取假设 A(即不合理假设 ),并证实列在其理由充足的支持条件中的一个 OUT-结点,
(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.进而矛盾就消除了,
7 情景演算情景演算是一种一阶逻辑语言，主要是用来表示动态变化的世界的。世界的所有变化过程都是,动作,的结果。
一个可能世界历史可以简单表示为动作的序列，它是通过称之为情景的一阶项所表示的。
常量 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)]所组成的，它们按照从右到左的方式组织。
定义 1 定义 Lsitcalc语言的动作理论 D为如下形式：
D = ∑? Dss? Dap? Duna? DSo
其中：
∑：基础的、针对情景演算的独立于领域的公理。
Dap：动作前提条件公理；
Dss：后续状态公理；
Duna：针对原子动作的唯一命名公理；
DSo：描述初始情形的公理。
基于情景演算的一些基本理论和方法，我们利用它们来刻画主体的复杂动作和过程，将主体的各个部件加以描述。
<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＝
<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＝
动作理论与情景演算的研究
◆ MaCarthy针对动态领域中的问题求解和逻辑程序设计提出了情景演算 。
◆ Reiter,Fangzhen Lin,Pirria,Lifschitz等人主要将情景演算进行了一些扩充，对状态约束、动作理论、
动态关系等方面进行了深入的研究，并以数据库、机器人等动态领域为背景，做了一些逻辑程序设计以及应用等研究。
◆ Levesque和 Reiter提出了一种新的动态逻辑设计语言
Golog / ConGolog
◆ Baral等人重点对状态的描述、动作的表示与推理以及动态领域中的知识表示等方面做了一些工作，提出了一种逻辑程序设计语言 A-Prolog，
参考文献史忠植,,高级人工智能,,科学出版社，
1998。
陆钟万,,面向计算机科学的数理逻辑,,
科学出版社,2000。
王元元,,计算机科学中的逻辑学,,科学出版社,1989。
