3. 非单调逻辑
单调逻辑 非单调逻辑 区别
3.1 单调逻辑
在现有知识的基础上，通过严密的逻辑论证和 推理获得的新知识必须与已有的知识相一致。
A，AB B
推理系统的定理集合随着推理过程的进行而单 调地增大。
单调性：
(1) ∈ Th( )
(2) 若 1 ⊆ 2 ，则Th(1) ⊆ Th(2)
(3) Th(Th( )) ＝ Th( )
系统的定理做出肯定的判断，但对非定理的公式过 程未必终止，因而未必能作出判断。这时称逻辑是 半可判定的。
一阶逻辑是不可判定的，但它是半可判定的。
1.3 命题逻辑
命题是可以确定其真假的陈述句。 Bolle提出了布尔代数。 语言: ¬，； 公式，原子公式 公理模式:
◆(A (B A)) ◆((A (B C)) ((A B) (A C))) ◆(((¬A))(¬B) (B A)) 推理规则:分离规则(modus ponens，MP规则)
类似地，给定一个语句和一个语句 ，如果对 每个解释I ，有I ⊨ 蕴含I ⊨ ，换言之，如果I 是 的一个模型则I也是的一个模型，则记为 ⊨ ，我 们称为的一个逻辑结果。
可靠性和完备性
可靠性(reliable)
一个逻辑是可靠的，如果它的证明保持真假值，
即在任何解释I下，如果I是 的模型，且可由推导 出，则I也是的一个模型。即，一个逻辑是可靠的， 如果对任何语句集合和语句 ， ⊢蕴涵 ⊨ 。
2.3 Prolog
Prolog(Programming in logic)语言是以Horn子句 逻辑为基础的高级程序设计语言。 1972年，法国马赛大学的Alain. Colmerauer提 出了Prolog的雏型。 1975年，Prolog被用于问题求解系统。 此后，它在许多领域获得了应用，如关系数据库、 定理证明、智能问题求解、计算机辅助设计、规 划生成等领域。
逻辑
程序语言
逻辑符号
保留字或者符号
非逻辑符号
用户自定义的符号(变量名， 函数名等)
语句规则
构造一个程序的语句规则
语义规则
定义程序做什么的语句规则
推理规则、公理和证明 没有
证明
一个证明是一个语法结构，它由符号串根据一定 的规则组成。它包括假设和结论。
在公理化逻辑中，逻辑给出一个逻辑公理和推理 规则的集合。推理规则是可以从一个语句的集合得到 另一语句的集合。
完备性(complete)
一个逻辑是完备的，如果任何永真语句是可证的。
即，对任何语句集合和语句 ， ⊨蕴涵 ⊢ 。
如果一个逻辑是完备的，则该逻辑的证明系统已强到 可以推出任何永真式。 Gődel完备性定理：一阶逻辑是完备的
可判定性
可判定的
一个逻辑称为是可判定的(decidable)，如果存在 一个算法对逻辑中的任一公式 A，可确定⊢ A是否成 立。否则，称为是不可判定的(undecidable) 。 如果上述算法虽不一定存在，却有一个过程，可对该
文字：原子公式(正文字)或原子公式的否定(负文字)。 P, Q, ¬R
子句：若干文字的析取。¬P∨Q∨R Horn子句：
L1∨L2∨… ∨Ln中如果至多只含一个正文字， 那么该子句称为Horn子句。
Horn子句P∨ ¬Q1∨ ¬Q2∨…∨ ¬Qn通常表示为： P Q1, Q2, …, Qn
Horn子句的类型：
1.2 逻辑系统
逻辑系统中的一个逻辑理论是该逻辑的语言的一 个语句集合，它包括：
逻辑符号集合：在所有该逻辑的逻辑理论中均出现的符号； 非逻辑符号集合：不同的逻辑理论中出现的不同的符号； 语句规则：定义什么样的符号串是有意义的； 证明：什么样的符号串是一个合理的证明； 语义规则：定义符号串的语义。
逻辑与程序语言的对比
Y = mary，John与Mary是朋友
Prolog的基本特点
Horn子句逻辑是Prolog的基础。 • Prolog既是一种逻辑程序设计语言，又是一个逻辑
系统。 • Prolog是一种描述性语言，它是一种面向问题的语
言，你只需要告诉它要做什么，即给出问题的形式 描述，而不需要知道应该如何做。 • Prolog完全依靠匹配、回溯来进行搜索。Prolog的 求解过程是一个寻求否证的消解过程。 • Prolog也使用元语言种的谓词，有很强的描述能力。 • Prolog采用统一的数据结构——项，它包含控制成 分，且有专门进行数值计算和符号处理的模块。
(不动点)
3.2 非单调逻辑
推理系统的定理集合并不随着推理过程的进行 而单调地增大，新推出地定理很可能会否定、 改变原来地一些定理，使得原来能够解释地某 些现象变得不能解释了。
新规则：
(4) ⊬ ¬ P
(不动点)
4. 缺省逻辑
1980年，Reiter提出了缺省逻辑(Default Logic)。 “一般情况下鸟是会飞的” “鸵鸟不会飞” “企鹅不会飞”
◆过程：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)，与事实匹配，产生目 标⊓ 。因而调用成功，输出“是”。
B C F 理论＝ <D,W >的扩充。
＝ <D,W >有唯一的扩充E ＝ Th({¬B, ¬F})。
例2：设
D ＝ { : A , B : C , F A : E , C E : A, F A }，
AC
E
G
W ＝ {B, CF∨A, A∧C ¬E}，计算缺省理论 ＝ <D,W >的扩充。
＝ <D,W >有三个扩充
E1 ＝ Th(W{A, C}) E2 ＝ Th(W{A, E}) E3 ＝ Th(W{CMcCarthy提出了一种非单调的推理— — 限定推理(Circumscription)。 基本思想：从某些事实A出发能够推出具有某一性质 的P的对象就是满足性质P的全部对象。只有当发 现其它对象也具有该性质时，才修改这种看法。
Prolog中变量可以用大写字母，下划线，以及由它们 开头的字母串。如X, Y, Answer, _value等。
• 结构：是常量和变量的序列，它由一个函子(函词 或谓词)和该函子的自变量所组成。如：
likes(john, X) married(mary, jack)
例：
(1) likes(bell, sports)
问题：关于对象性质或关系的询问。
?— student(john)
?— married(mary，x)
Prolog的执行方式
搜索：在程序中自上而下地搜索事实和规则；
匹配：将目标中的项与事实和规则进行匹配；
回溯：当目标中一项失败时，如果目标中有已经 成功的的项(应在失败项的左边)，那末就重新调 用这些成功项中最右边的一个，谋求新的成功。
A, A B B
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) (vA vB)
高级人工智能
第二章 人工智能逻辑
第一部分
史忠植
中国科学院计算技术研究所
主要内容
逻辑简介 逻辑程序设计 非单调逻辑 缺省逻辑 限定逻辑 真值维护系统 情景演算
1. 逻辑简介
逻辑的历史 逻辑系统 命题逻辑 谓词逻辑
1.1 逻辑的历史
Aristotle——逻辑学 Leibnitz——数理逻辑 Gottlob Frege (1848-1925)——一阶谓词 演算系统,《符号论》 20世纪30年代，数理逻辑广泛发展
(3) 如果D中有规则 : M1,, Mn，
且∈(S)，¬1, …, ¬m ∉ S ，那么∈(S)
4.3 缺省理论的扩充
定义：对命题集合E，如果(E) = E，则E称为关于 D的算子的不动点(fixpoint)。此时称E为缺省理论
＝ <D,W >的一个扩充(extension)。 例1：设D ＝ { : A , : B , : C }，W ＝ ，计算缺省
Prolog语言的基本文法
Prolog语言的最基本语言成分是项(term)，一个 项或者是常量，或者是变量，或者是一个结构。 • 常量：是指对象和对象之间的特定关系的名；
整数，如0，22，1586等； 原子，如John，student，likes，sister-of
• 变量：表示任意的对象，它与FOL中的变元相同；
公理化逻辑中的证明就是一个语句序列，使得 其中的每个语句要么是逻辑公理，要么是一个假设，
要么是由前面的语句通过推理规则得到的。
证 明(语法)
在语法上，如果存在一个从假设到的证明， 则记为 ⊢ ，称由可推导出的，或可证明的。
是可推导出的，则记为 ⊢ ，称为可证明的。
称一个假设是不协调的，如果存在一个语句 使得和的否定均可由推导得出。
4.2 缺省理论
缺省理论由两个部分组成，即缺省规则 集D和公式集W，一般用二元组来表示 ＝ <D,W > 若D中的规则是闭规则时，则为闭缺省理论。
定义：设＝ <D,W >为一闭缺省理论， 为关于D的 一个算子，作用于任意的命题集合S，而其值为满 足下列三个性质的最小命题集合(S)：