人工智能逻辑

人工智能逻辑

第二章2024/2/41主要内容逻辑简介逻辑程序设计非单调逻辑默认逻辑限定逻辑真值维护系统情景演算动态描述逻辑2024/2/42逻辑简介逻辑的历史逻辑系统命题逻辑谓词逻辑2024/2/43逻辑的历史Aristotle——逻辑学Leibnitz——数理逻辑GottlobFrege(1848-1925)——一阶谓词演算系统,《符号论》20世纪30年代，数理逻辑广泛发展2024/2/44逻辑系统

一个逻辑系统是定义语言和它的含义的方法。逻辑系统中的一个逻辑理论是该逻辑的语言的一个语句集合，它包括：逻辑符号集合：在所有该逻辑的逻辑理论中均出现的符号；非逻辑符号集合：不同的逻辑理论中出现的不同的符号；语句规则：定义什么样的符号串是有意义的；证明：什么样的符号串是一个合理的证明；语义规则：定义符号串的语义。2024/2/45逻辑程序语言逻辑符号保留字或者符号非逻辑符号用户自定义的符号(变量名，函数名等)语句规则构造一个程序的语句规则语义规则定义程序做什么的语句规则推理规则、公理和证明没有逻辑与程序语言的对比2024/2/46

一个证明是一个语法结构，它由符号串根据一定的规则组成。它包括假设和结论。在公理化逻辑中，逻辑给出一个逻辑公理和推理规则的集合。推理规则是可以从一个语句的集合得到另一语句的集合。

公理化逻辑中的证明就是一个语句序列，使得其中的每个语句要么是逻辑公理，要么是一个假设，要么是由前面的语句通过推理规则得到的。证明2024/2/47

在语法上，如果存在一个从假设

到

的证明，则记为

⊢

，称

由

可推导出的，或可证明的。如果在没有任何假设下

是可推导出的，则记为⊢

，称

为可证明的。称一个假设

是不协调的，如果存在一个语句

使得

和

的否定均可由

推导得出。称一个逻辑系统是一致的，或相容的(consistent)，如果不存在逻辑系统的公式A，使得⊢A与⊢¬A同时成立。证明(语法)2024/2/48

语言的解释是在某个论域(domain)中定义非逻辑符号。语句的语义是在解释下定义出语言L的真假值。如果I是L的一个解释，且

在I中为真，则记为I

⊨

，称作I满足

，或者I是

的一个模型。类似地，给定一个语句

和一个语句

，如果对每个解释I

，有I

⊨

蕴含I

⊨

，换言之，如果I是

的一个模型则I也是

的一个模型，则记为

⊨

，我们称

为

的一个逻辑结果。解释(语义)2024/2/49可靠性(reliable)一个逻辑是可靠的，如果它的证明保持真假值，即在任何解释I下，如果I是

的模型，且

可由

推导出，则I也是

的一个模型。即，一个逻辑是可靠的，如果对任何语句集合

和语句

，

⊢

蕴涵

⊨

。可靠性和完备性完备性(complete)一个逻辑是完备的，如果任何永真语句是可证的。即，对任何语句集合

和语句

，

⊨

蕴涵

⊢

。如果一个逻辑是完备的，则该逻辑的证明系统已强到可以推出任何永真式。Gődel完备性定理：一阶逻辑是完备的2024/2/410可判定的一个逻辑称为是可判定的(decidable)，如果存在一个算法对逻辑中的任一公式A，可确定⊢

A是否成立。否则，称为是不可判定的(undecidable)。如果上述算法虽不一定存在，却有一个过程，可对该系统的定理做出肯定的判断，但对非定理的公式过程未必终止，因而未必能作出判断。这时称逻辑是半可判定的。可判定性一阶逻辑是不可判定的，但它是半可判定的。2024/2/411现代逻辑学与计算机科学、计算语言学和人工智能的关系表逻辑自然语程序人工逻辑指令与直数据库复杂性智能体未来展望言处理控制智能编程陈式语言理论理论理论时序逻辑√√√√√√√√广泛应用模态逻辑√√√√√√√√非常活跃算法证明√√√√√√√√非单调推理√√√√√√√意义重大概率和模糊√√√√√√√目前主流直觉主义逻辑√√√√√√√√主要替代者高阶逻辑，λ-演算√√√√√√更具中心作用经典逻辑片断√√√√√√前景诱人资源和子结构逻辑√√√√纤维化和组合逻辑√√√√√√可自我指称谬误理论在适当语境逻辑动力学√√动态逻辑观论辩理论游戏√前景光明对象层次/元层次√√总起中心作用机制:溯因缺省相干√√逻辑的一部分与神经网络的联系极重要，刚开始时间-行动-修正模型√√一类新模型加标演绎系统√√√√√逻辑学的统一框架2024/2/412命题逻辑命题是可以确定其真假的陈述句。Bolle提出了布尔代数。语言:

¬，； 公式，原子公式公理模式:

◆(A

(B

A))

◆((A

(B

C))

((A

B)

(A

C)))

◆(((¬A))

(¬B)

(B

A))推理规则:分离规则(modusponens，MP规则)2024/2/413谓词逻辑(一阶逻辑)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)

◆A

vA(v在A中无自由出现)推理规则:分离规则2024/2/414谓词逻辑与命题逻辑的区别谓词逻辑给出了原子语句的内部结构，将原子公式看作是事物直接的关系；它引入了“推广”(泛化)，加强了逻辑的表示能力和推理能力。这样，我们可以说某种性质对某个对象是成立的，或对所有的对象成立，或不对任何对象成立。2024/2/415逻辑程序设计归结原理(消解原理)Horn逻辑Prolog逻辑程序设计语言2024/2/416归结原理例：

C1=¬P∨Q∨R C2=P∨Q则C1与C2归结后的结果为：Q∨R

若子句集S能导出空子句⊓(有否证)，则称S是不可满足的。反证法：S⊢AiffS

¬A

⊢⊓2024/2/417Horn逻辑文字：原子公式(正文字)或原子公式的否定(负文字)。P,Q,¬R子句：若干文字的析取。¬P∨Q∨RHorn子句：子句L1∨L2∨…∨Ln中如果至多只含一个正文字，那么该子句称为Horn子句。

Horn子句P∨¬Q1∨¬Q2∨…∨¬Qn通常表示为：P

Q1,Q2,…,Qn2024/2/418Horn子句的类型

◆过程：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)，与事实匹配，产生目标⊓。因而调用成功，输出“是”。2024/2/419

PrologProlog(Programminginlogic)语言是以Horn子句逻辑为基础的高级程序设计语言。1972年，法国马赛大学的Alain.Colmerauer提出了Prolog的雏型。1975年，Prolog被用于问题求解系统。此后，它在许多领域获得了应用，如关系数据库、定理证明、智能问题求解、计算机辅助设计、规划生成等领域。2024/2/420Prolog的构成事实：关于对象性质和关系的事实语句；student(john)，married(tom,mary)规则：关于对象性质和关系的定义规则语句；它与事实的不同在于，规则所定义的性质、关系依赖与其它的性质和关系，因此规则呈蕴涵语句形式。

B:—

A “如果A则B”bird(x):—animal(x)，has(x,feather)问题：关于对象性质或关系的询问。

?—student(john)

?—married(mary，x)2024/2/421Prolog的执行方式搜索：在程序中自上而下地搜索事实和规则；匹配：将目标中的项与事实和规则进行匹配；回溯：当目标中一项失败时，如果目标中有已经成功的的项(应在失败项的左边)，那末就重新调用这些成功项中最右边的一个，谋求新的成功。2024/2/422Prolog语言的基本文法Prolog语言的最基本语言成分是项(term)，一个项或者是常量，或者是变量，或者是一个结构。常量：是指对象和对象之间的特定关系的名；

整数，如0，22，1586等；

原子，如John，student，likes，sister-of变量：表示任意的对象，它与FOL中的变元相同；

Prolog中变量可以用大写字母，下划线，以及由它们开头的字母串。如X,Y,Answer,_value等。结构：是常量和变量的序列，它由一个函子(函词或谓词)和该函子的自变量所组成。如：likes(john,X) married(mary,jack)2024/2/423例子(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是朋友2024/2/424Prolog的基本特点Horn子句逻辑是Prolog的基础。Prolog既是一种逻辑程序设计语言，又是一个逻辑系统。Prolog是一种描述性语言，它是一种面向问题的语言，你只需要告诉它要做什么，即给出问题的形式描述，而不需要知道应该如何做。Prolog完全依靠匹配、回溯来进行搜索。Prolog的求解过程是一个寻求否证的消解过程。Prolog也使用元语言种的谓词，有很强的描述能力。Prolog采用统一的数据结构——项，它包含控制成分，且有专门进行数值计算和符号处理的模块。2024/2/425非单调逻辑单调逻辑非单调逻辑区别2024/2/426单调逻辑在现有知识的基础上，通过严密的逻辑论证和推理获得的新知识必须与已有的知识相一致。A，A

B

B推理系统的定理集合随着推理过程的进行而单调地增大。单调性：

(1)

∈

Th(

) (2)若

1⊆

2，则Th(

1)⊆Th(

2) (3)Th(Th(

))＝Th(

) (不动点)2024/2/427非单调逻辑推理系统的定理集合并不随着推理过程的进行而单调地增大，新推出的定理很可能会否定、改变原来的一些定理，使得原来能够解释的某些现象变得不能解释了。新规则：

(4)

⊬¬P (不动点)2024/2/428默认逻辑1980年，Reiter提出了默认逻辑(DefaultLogic)。

“一般情况下鸟是会飞的”

“鸵鸟不会飞”

“企鹅不会飞”2024/2/429默认规则

一个默认规则是如下形式的规则：

(x):称为前提条件

i(x):称为默认条件，或检验条件

(x):称为结论为简便，通常情况下可以省略检验条件中的M。规则的使用：如果规则的前提条件满足，且现有的知识导不出检验条件的否定¬

i(x)，则可以得出结论成立。2024/2/430默认理论

一个默认理论

由两个部分组成，即默认规则集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)2024/2/431默认理论的扩充定义：对命题集合E，如果

(E)=E，则E称为关于D的算子

的不动点(fixpoint)。此时称E为默认理论

＝<D,W>的一个扩充(extension)。例1：设D

＝{ }，W

＝

，计算默认理论

＝<D,W>的扩充。

＝<D,W>有唯一的扩充E

＝Th({¬B,¬F})。2024/2/432默认理论的扩充例2：设D

＝{ }，W

＝{B,C

F∨A,A∧C

¬E}，计算默认理论

＝<D,W>的扩充。

＝<D,W>有三个扩充E1

＝Th(W

{A,C})E2

＝Th(W

{A,E})E3

＝Th(W

{C,E,G})2024/2/433限定推理1980年，McCarthy提出了一种非单调的推理——限定推理(Circumscription)。基本思想：从某些事实A出发能够推出具有某一性质的P的对象就是满足性质P的全部对象。只有当发现其它对象也具有该性质时，才修改这种看法。2024/2/434限定逻辑

限定逻辑CIRC是一种极小化逻辑。下面，从一个基于极小模型定义的命题限定出发，给出限定的基本定义,进而给出一阶限定的基本结果，并将它推广。定义2.1设L0是一个命题语言，p1,p2是在命题语言L0

中的两个赋值。称p1小于p2

，记为p1

p2,当且仅当对任一命题变元x,如果p1(x)=l,则p2(x)=l。2024/2/435限定逻辑

定义2.2设A

是一个公式，称A的一个赋值p是极小的，当且仅当不存在A的其它赋值p'使得p'

p。显然,

是一个偏序关系。p1

p2表示p1包含的真命题比p2

少。极小赋值包含的真命题极小。定义2.3极小后承

M。设A,B是两个公式，A

M

B

当且仅当B在所有A

的极小模型中都为真。极小模型是非单调的，它以命题的极小化作为优先模型的准则。2024/2/436限定逻辑

定义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。

2024/2/437限定逻辑

定义2.5命题限定

P

或CIRC(A,P)。设A是一个包含命题集的公式，

是一个公式，A

P

当且仅当

在所有A的

p-

极小赋值中都为真。

定理2.1A

p

当且仅当A

P

2024/2/438限定逻辑

定义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中的子集。2024/2/439限定逻辑

一个理论T的模型M称为优先的，当且仅当不存在T的其它模型M'使得M'

M。定义2.7Mm是

的最小模型，当且仅当

M

Mm,M=Mm

2024/2/440限定逻辑

例如设论域D={1,2}T=xy(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)TTFTFTM*:P(1)P(2)Q(1,1)Q(1,2)Q(2,1)Q(2,2)FTFTFT

2024/2/441真值维护系统TMS1979年，Doyle提出了一种非单调推理系统——真值维护系统(TruthMaintenanceSystem)

真值维护系统是大型推理系统的的一个子系统，实现知识库中信念(belief)的修改与维护。其基本问题有：必须在不完全的、有限的信息基础上作出假设的决策，使得该假设成为知识库的信念；当这些决策的结论被以后的事实证明为错误时，如何对其信念进行修正。2024/2/442基本数据结构:

结点：表示信念

理由：表示信念的原因信念既包括已知的知识，也包括假设的知识。基本操作：

新结点的形成——将信念赋予该结点；

新理由的加入——把某个信念与该结点联接起来实现过程： 默认假设的形成； 相关性回溯过程。真值维护系统TMS2024/2/443信念知识表示每一个命题或规则均称为结点，它分为两类：

IN-结点：相信为真

OUT-结点：不相信为真，或无理由相信为真， 或当前没有任何有效的理由。每个结点附有理由表，表示具体结点的有效性：

支持表SL：所在结点的信念的原因，理由；

条件证明CP：出现矛盾的原因。2024/2/444(SL(<IN-结点表>)(<OUT-结点表>))IN-结点表中的IN-结点表示知识库中的已知知识;OUT-结点表中的OUT-结点表示这些结点的否定。例1:(1)现在是夏天 (SL()())(2)天气很潮湿 (SL(1)())结点(1)不依赖于任何别的结点中的当前信念或默认信念,因而这种结点称为前提;结点(2)则依赖于当前结点(1)的信念.所以，与一阶逻辑不同的是,TMS可以撤消前提,并可以对知识库作适当修改.（1）支持表SL信念知识表示2024/2/445例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中,它仅利用证实来维持一个相容的信念数据库,而它本身并不产生证实.信念知识表示2024/2/446(CP<结论><IN-假设><OUT-假设>)如果结论结点为IN-结点,以及下列条件成立: (1)IN假设中的每个结点都是IN-结点; (2)OUT-假设中的每个结点都是OUT-结点.那么条件证明CP是有效的.一般说来,OUT-假设总是空集.TMS要求假设集划分成两个不相交的子集,分别为不导致矛盾的假设和导致矛盾的假设.通常只要在IN-假设中的结点为IN,OUT-假设中的结点为OUT,则结论结点为IN.（2）条件证明CP信念知识表示2024/2/447默认假设

令{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.2024/2/448相关回溯当知识库中出现不一致时,TMS将寻找并删除已做的一个不正确的默认逻辑,恢复一致性.它包括三个步骤: (1)从产生的矛盾结点开始,回溯跟踪该矛盾结点的理由充足的支持以寻找矛盾的假设集,并从中去掉至少一个假设信念以消除矛盾. (2)构造一个结点记录矛盾产生的原因. (3)从S中选取假设A(即不合理假设),并证实列在其理由充足的支持条件中的一个OUT-结点.2024/2/449

(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.进而矛盾就消除了.相关回溯2024/2/450情景演算

情景演算是一种一阶逻辑语言，主要是用来表示动态变化的世界的。世界的所有变化过程都是“动作”的结果。一个可能世界历史可以简单表示为动作的序列，它是通过称之为情景的一阶项所表示的。

常量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)]所组成的，它们按照从右到左的方式组织。

2024/2/451定义1定义Lsitcalc语言的动作理论D为如下形式：D=∑⋃Dss⋃Dap

⋃Duna⋃DSo

其中：

∑：基础的、针对情景演算的独立于领域的公理。

Dap：动作前提条件公理；

Dss：后续状态公理；

Duna：针对原子动作的唯一命名公理；

DSo：描述初始情形的公理。

情景演算2024/2/452

基于情景演算的一些基本理论和方法，我们利用它们来刻画主体的复杂动作和过程，将主体的各个部件加以描述。

<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＝情景演算2024/2/453<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＝情景演算2024/2/454动作理论与情景演算的研究◆MaCarthy针对动态领域中的问题求解和逻辑程序设计提出了情景演算。◆

Reiter，FangzhenLin，Pirria，Lifschitz等人主要将情景演算进行了一些扩充，对状态约束、动作理论、动态关系等方面进行了深入的研究，并以数据库、机器人等动态领域为背景，做了一些逻辑程序设计以及应用等研究。

◆

Levesque和Reiter提出了一种新的动态逻辑设计语言

Golog/ConGolog◆Baral等人重点对状态的描述、动作的表示与推理以及动态领域中的知识表示等方面做了一些工作，提出了一种逻辑程序设计语言

A-Prolog，

2024/2/455描述逻辑

DescriptionLogics◆

什么是描述逻辑？◆为什么用描述逻辑？◆描述逻辑的研究进展◆描述逻辑的体系结构◆描述逻辑的构造算子◆描述逻辑的推理问题◆我们的工作2024/2/456什么是描述逻辑(DL)？

一种基于对象的知识表示的形式化，也叫概念表示语言或术语逻辑。建立在概念和关系(Role)之上

－概念解释为对象的集合 －关系解释为对象之间的二元关系源于语义网络和KL-ONE是一阶逻辑FOL的一个可判定的子集具有合适定义的语义(基于逻辑)2024/2/457描述逻辑的特点◆是以往表示工具的逻辑重构和统一形式化 －

框架系统

(Frame-basedsystems)

－

语义网络

(SemanticNetworks)

－

面向对象表示

(OOrepresentation)

－

语义数据模型

(Semanticdatamodels)

－

类型系统

(Typesystems)

－

特征逻辑

(FeatureLogics)◆

具有很强的表达能力◆是可判定的，总能保证推理算法终止2024/2/458描述逻辑的应用

◆概念建模◆查询优化和视图维护◆自然语言语义◆智能信息集成◆信息存取和智能接口◆工程的形式化规范◆术语学和本体论◆规划◆…2024/2/459为什么用描述逻辑？若直接使用一阶逻辑，而不附加任何约束，则：◆知识的结构将被破坏，这样就不能用来驱动推理◆对获得可判定性和有效的推理问题来说，其表达能力太高，（也许是太抽象了）◆对兴趣表达，但仍然可判定的理论，其推理能力太低。DL的重要特征是：◆很强的表达能力；◆可判定性，它能保证推理算法总能停止，并返回正确的结果。2024/2/460在众多知识表示的形式化方法中，描述逻辑在十多年来受到人们的特别关注，主要原因在于以下三点:◆它们有清晰的模型-理论机制;◆它们很适合于通过概念分类学来表示应用领域；◆它们提供了很用的推理服务。它们可以被认为是从基于框架的表示形式化向着精确的语义特征方向发展。此外，描述逻辑将分类学中表示和推理（专业推理）与在分类学中项的事实或实例的表示和推理（断言推理）区别开来。为什么用描述逻辑？2024/2/461描述逻辑的研究进展◆描述逻辑的基础研究 研究描述逻辑的构造算子、表示和推理的基本问题，如可满足性、包含检测、一致性、可判定性等。 一般都在最基本的ALC的基础上在扩展一些构造算子，如数量约束、逆关系、特征函数、关系的复合等。

TBox和Abox上的推理问题、包含检测算法等。

Schmidt-Schaub

和Smolka首先建立了基于描述逻辑ALC的Tableau算法，该算法能在多项式时间内判断描述逻辑ALC概念的可满足性问题。2024/2/462描述逻辑的扩展研究

A.Artale和E.Franconi(1998)提出了一个知识表示系统，用时间约束的方法将状态、动作和规划的表示统一起来。 为了能让描述逻辑处理模态词，F.Baader将模态操作引入描述逻辑，证明了该描述逻辑公式的可满足性问题是可判定的。

Wolter等对具有模态算子的描述逻辑进行了深入系统的调查分析，并证明在恒定的领域假设下多种认知和时序描述逻辑是可判定的。

另外如时序扩展(Artale,Wolter)、模糊扩展(Straccia)等。2024/2/463描述逻辑在许多领域中被作为知识表示的工具，如 信息系统（Catarci,1993） 数据库（Borgida,1995;Bergamaschi1992;Sheth,1993） 软件工程(Devambu,1991)

网络智能访问（Levy，

1996；

Blanco，1994） 规划（Seida,1992）等

Horrocks对表达能力较强的描述逻辑进行了研究，并建立了一些逻辑框架和系统，如FaCT，SHIQ等。他和DieterFensel等人将描述逻辑、语义网和DAML结合起来，提出了DAML+OIL，其中以描述逻辑作为核心的表示和推理基础。并在XML及其RDF上面进行了扩展，用描述逻辑来研究语义网络和本体论。描述逻辑的应用研究2024/2/464研究背景语义Web[Bemers-Lee1998,2006]

描述逻辑：OWL的逻辑基础[Horrocks2003]特点：描述能力+可判定；有效的判定算法和推理机制。局限：不能处理动态领域中与动作相关的知识。OWLLiteOWLDLOWLFullSHIF(D)SHOIN(D)不可判定65描述逻辑的体系结构一个描述逻辑系统包含四个基本组成部分：1）表示概念和关系（Role）的构造集2）Tbox——关于概念术语的断言3）Abox——关于个体的断言4）Tbox和Abox上的推理机制。

2024/2/466◆概念

——解释为一个领域的子集

例子：所有在校学习的人员的集合构成“学生”概念 又如：孩子，已婚的，哺乳动物等概念{x|Student(x)}，{x|Married(x)}◆

关系(Roles)——属性(二元谓词，关系)例子：朋友，爱人，{<x,y>|Friend(x,y)}，{<x,y>|Loves(x,y)}DL的基本元素——概念和关系2024/2/467知识库TBox(模式)Man≐Human⊓MaleHappy-father≐Human⊓

∃Has-child.Female⊓

…Abox(数据)John:Happy-father<John,Mary>:Has-child推理系统接口2024/2/468TBox语言TBox语言是描述领域结构的公理的集合定义:引入概念的名称A≐

C,A

⊑

CFather≐

Man⊓

∃

has-child.HumanHuman⊑

Animal⊓

Biped包含：声明包含关系的公理C

⊑

D

(C≐

D

C

⊑

D

，D

⊑

C)∃

has-degree.Masters⊑

∃

has-degree.Bachelors一个解释I满足：C≐

D

iffCI

=DI C⊑

D

iffCI

⊆

DI一个解释I满足TBoxT

iff它满足T中的每个公理(I⊨T)2024/2/469◆概念断言

——表示一个对象是否属于某个概念

a:C例如：Tom是个学生，表示为

Tom

:Student 或者 Student(Tom)

John

:Man⊓

∃

has-child.Female◆关系断言

——表示两个对象是否满足一定的关系

<a,b>:R例如：John有个孩子叫Mary

<John,

Mary>

:has-childABox语言是描述具体情形的公理的集合ABox语言2024/2/470语义解释一个解释I满足：a:

C

iffaI

∈

CI

<a,b>:R

iff<aI,bI>

∈RI一个解释I满足ABoxA

iff它满足A中的每个公理记为：I⊨A一个解释I满足知识库

=<T,A

>

iff它满足T和A

记为：I⊨

2024/2/471

语法和语义构造算子语法语义例子原子概念AAI⊆△IHuman原子关系RRI⊆△I

△Ihas-child对概念C,D和关系(role)R合取C⊓DCI∩DIHuman⊓Male析取C⊔DCI⋃

DIDoctor⊔Lawyer非¬C△I\C¬Male存在量词∃

R.C{x|∃y.<x,y>∈

RI∧y∈CI}∃

has-child.Male全称量词∀R.C{x|∀y.<x,y>∈

RI

y∈CI}∀

has-child.Doctor2024/2/472一般地，描述逻辑依据提供的构造算子，在简单的概念和关系上构造出复杂的概念和关系。通常DL至少包含以下算子： ◆合取(⊓)，吸取(⊔)，非(¬) ◆量词约束：存在量词(∃)，全称量词(∀)最基本的DL称之为ALC例如，ALC中概念Happy-father定义为：

Man⊓

∃

has-child.Male

⊓

∃

has-child.Female

⊓

∀has-child.(Doctor⊔

Lawyer)DL中的构造算子2024/2/473构造算子语法语义例子数量约束≥nR.C{x||{y|<x,y>∈

RI,y∈CI}

|≥n}≥3

has-child.Male≤nR.C{x||{y|<x,y>∈

RI,y∈CI}

|≤n}≤3

has-child.Male逆R-{<y,x>|<x,y>∈

RI}has-child-传递闭包R*(RI)*has-child*DL中的其它算子topT△IMale⊔

¬MaleBottom

Man⊓

¬Man另外，有两个类似于FOL中的全集(true)和空集(false)的算子2024/2/474DL中添加算子一般地，在描述逻辑中添加不同的算子，则得到不同表达能力的描述逻辑，其复杂性问题也不尽相同。例如，在ALC的基础上添加逆(-)算子，则构成ALCI若再加上数量约束算子(≥n,≤n)，则构成ALCIQ。若在描述逻辑中添加时序算子，则构成为时序描述逻辑(TemporalDescriptionLogic)，例如，可以添加：

Until算子U：C

U

D Since算子S：CSD还可以加入其它算子，如模态算子□，

，○等。2024/2/475描述逻辑中的推理1)

一致性（协调性consistency）2)可满足性(satisfiability)3)包含检测（subsumption）4)实例检测

(instancechecking)5)Tableaux算法6）可判定性7）计算复杂性2024/2/476一致性检测(Consistency)◆知识库<T,A>是协调的吗？ 即检测是否有<T,A>的模型(解释)I？◆C关于TboxT是协调的吗？

即检测是否有T的模型I使得C

≠

？2024/2/477概念可满足性(Satisfiablity)

对一个概念C，如果存在一个解释I使得CI是非空的，则称概念C是可满足的，否则是不可满足的。

检验一个概念的可满足性，实际上就是看是否有解释使得这个概念成立。例如：概念Male⊓

Female，即需要检测是否有性别既是男的又是女的这样的人。若确实是没有这种两性人，则我们断言，这个概念是不可满足的。又如概念：student⊓worker，它是可满足的。即代表那些在职学生的集合。定理：概念C是可满足的，当且仅当C不包含于

。

2024/2/478◆在知识库中检测：

C⊑

D？ 即检测CI

⊆

DI是否在所有的解释中成立？概念包含(Subsumption)例如：

bird⊑animal computer⊑equipment◆在Tbox中检测：

C⊑

D？ 即检测CI

⊆

DI是否在TboxT