2019描述逻辑ALC中关于伪子概念极小改变的R-演算-王雨晖 , 眭跃飞.pdf

上善若水

11页

0次

2022-05-23

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2019,30(12):3683−3693 [doi: 10.13328/j.cnki.jos.005596] http://www.jos.org.cn

描述逻辑 ALC 中关于伪子概念极小改变的 R-演算

∗

王雨晖

1,2,3

眭跃飞

1,2

(中国科学院计算技术研究所智能信息处理重点实验室,北京 100190)

(中国科学院大学计算机与控制学院,北京 100049)

(中国再保险(集团)股份有限公司信息技术中心,北京 100033)

通讯作者: 王雨晖, E-mail: yhwang_ict@qq.com

摘要: AGM 公设是用于信念修正的(被一个单一信念修正),而 DP 公设是用于迭代修正的(被一个有限的信念序

列修正).李未给出了对于 R-构型(configuration)

的 R-演算,其中,

是一个原子公式或原子公式否定的集合,而

是

一个有限的公式集合. 为了在修正过程中能够保留断言中尽可能多的信息,将考虑一种新的极小改变的定

义:伪子概念极小改变(U-极小改变),其中,U是一种伪子概念的关系;之后,在此基础上给出一种新的 R-演算 T

,它

是关于U-极小改变可靠和完备的,使得

在 T

中可以被约减为一个理论

∪

(记作

ΔΓ ΔΘ

⇒A )当且仅当

是

关于

的一个U-极小改变.

关键词: 描述逻辑;信念修正;R-演算;伪子概念;U-极小改变

中图法分类号: TP18

中文引用格式: 王雨晖, 眭跃飞.描述逻辑 ALC 中关于伪子概念极小改变的 R-演算.软件学报,2019,30(12):3683−3693.

http://www.jos.org.cn/1000-9825/5596.htm

英文引用格式: Wang YH, Sui YF. R-calculus for pseudo-subconcept-minimal change in description logic ALC. Ruan Jian Xue

Bao/Journal of Software, 2019,30(12):3683−3693 (in Chinese). http://www.jos.org.cn/1000-9825/5596.htm

R-calculus fo r Pseudo-s ubc oncep t-nini mal Cha nge in Descriptio n Logic ALC

WANG Yu-Hui

1,2,3

, SUI Yue-Fei

1,2

(Key Laboratory of Intelligent Information Processing, Institute of Computing Technology, Chinese Academy of Sciences, Beijing

100190, China)

(School of Computer and Control Engineering, University of Chinese Academy of Sciences, Beijing 100049, China)

(Information Technology Center, China Reinsurance (Group) Corporation, Beijing 100033, China)

Abstra ct : The AGM postulates are for the belief revision (revision by a single belief), and the DP postulates are for the iterated revision

(revision by a finite sequence of beliefs). Li gave an R-calculus for R-configurations

, where

is a set of atomic formulas or the

negations of atomic formulas, and

is a finite set of formulas. With an idea to preserve as much as possible information of statements to

be revised, another definition of the minimal change is considered: pseudo-subconcept-minimal (U-minimal) change, where U is the

pseudo-subconcept relation, and then give a new R-calculus T

which is sound and complete with respect to U-minimal change such that

is reduced to a theory

∪

in T

(denoted by

ΔΓ ΔΘ

⇒A

) if and only if

is a U-minimal change of

Key words: description logics; belief revision; R-calculus; pseudo-subconcepts; U-minimal change

∗ 基金项目: 国家重点基础研究发展计划(973)(2005CB321901); 软件开发环境国家重点实验室开放课题(SKLSDE-2010KF-06)

Foundation item: National Program on Key Basic Research Project (973)(2005CB321901); Open Fund of the State Key Laboratory

of Software Development Environment (SKLSDE-2010KF-06)

收稿时间: 2017-12-26; 修改时间: 2018-03-17; 采用时间: 2018-05-01

3684

Journal of Software 软件学报 Vol.30, No.12, December 2019

信念修正是接受一个新信念和更新我们已有信念的过程,它的发展是哲学以及后来的计算机科学所需要

的.在计算机科学中,为了更新数据库,Doyle

[1]

提出了保真系统(truth maintenance systems),自此,信念修正成为人

工智能中的一个重要分支;而在哲学中,信念逻辑中的逻辑研究也需要考虑人类信念是如何更新和修正的.

由 Alchourrón,Gärdenfors 和 Makinson

[2−4]

提出的 AGM 公设是一个修正算子应该满足的基本条件集合,它

是用公式 A 去修正理论 K,使得如果 KA⇒K′,则 K′是 K∪{A}的极大协调子集.

李未

[5]

给出了基于一阶逻辑

[6]

的 Gentzen-型推导系统 R-演算,用来将 R-构型(configuration)

归约到协调

理论

∪

是

∪

的极大协调子集,其中,

是协调公式集合,而

是协调的原子或原子公式否定的集合.在这

里,

相当于迭代修正



.因此,推导系统给出了具体的修正算子,并且证明是满足 AGM 公设的.

对于描述逻辑 ALC, 存在这样的 R-演算 S

DL[7]

: 其中 R-构型

可以被归约为理论

∪

( 记为

ΔΓ ΔΘ

⇒A ),当且仅当

是

关于

的一个集合包含极小改变(⊆-极小改变)(记为

ΔΓ ΔΘ

⇒B ).这里,

是

的子理论,并且它与

是极大的、协调的(maximal consistent)(不是极大协调的(maximally consistent)),即:对任

何理论

满足

⊂

⊆

与

是不协调的.在这里,我们用

来表示

∪

.因此,R-演算 S

关于⊆-极小改变是可靠

的和完备的

⊆-

极小改变

[8−10]

是关于集合包含关系的,即:如果

⇒

在 R-演算中是可证的,则

是

关于

的一个极

小改变,如果对于任意的公式 A∈

∪

GA 都蕴含有

∪

A¬A.因此,我们称

是

关于

的⊆-极大协调子集.

针对⊆-极小改变和 R-演算 S

,我们来看具体的例子.已知 Tony 是一位男生,性格开朗,四肢健全,即:在

我们的知识库当中,存在着这样一条断言(HavingarmsHavingle gs)(Tony).然而一次突发的事故让 Tony 失去了

双腿,也使得关于 Tony 产生了一条新的事实断言¬Havinglegs(Tony).因此,我们就需要对于原有知识库中的断

言做出修正

.而按照之前 R-演算 S

当中的修正规则,我们将得到如下修正:

(Tony) | ( )(Tony) (Tony)Havinglegs Havingarms Havinglegs Havinglegs¬⇒¬A .

可以看到,经过修正后的知识库中将只剩下断言¬Havi ngle gs(Tony),即 Tony 依然是有胳膊的断言没有了,

这当然不是我们想要的.直观地,我们应当获得这样的修正:

¬Havingle gs(Tony)|(HavingarmsHa vin glegs )(Tony)⇒¬Havinglegs(Tony),Havingarms(Tony).

显然,S

中的规则 ()S



是会删除掉

中过多的有效信息的.

因此在本文中,我们将考虑另一种极小改变的定义:

伪子公式极小改变(U-极小改变),其中,U是伪子公式关系,如同子公式关系(subformula relation)≤;

而公式 A 是另一个公式 B 的伪子公式(pseudo-subformula of B),如果删除 B 中某些子公式可以得到 A.

在描述逻辑中,我们也有类似地对于极小改变的定义

[11]

.在描述逻辑中,我们有概念的次子概念(para-

subconcepts)

和伪子概念(pseudo-subconcepts),对应于子公式和伪子公式,并且基于此,我们给出关于U

-极小改

变可靠和完备的

R-演算 T

.需要注意的是,这里的极小改变并不是关于描述逻辑中的断言,而是关于概念的.比

如,概念集合 X 是概念集合 Y 关于概念集合 Z 的一个U

-极小改变.具体地,我们定义:

对于概念的伪子概念极小改变(U

-极小改变),其中,U

是伪子概念关系,既不同于描述逻辑中的子概念

关系

,也不同于次子概念(para-subconcept)关系(对应于传统逻辑中的子公式关系),其中,

概念 C 是另一个概念 D 的伪子概念,如果通过删除 D 中若干个原子概念符号可以得到 C.

显然,新的极小改变将使我们在修正的过程中,可以将修正的最小单元降到原子概念级,可以做到在修正的

过程中只剔除掉那些与新事实产生矛盾的原子概念,从而可以最大限度地保留原有断言中的有效信息.

相应地,我们也将给出如下的 R-演算:

R-

构型

在 R-演算 T

中可以被归约为理论

∪

(记为

ΓΔΘ

⇒A ,即

⇒

在 Gentzen 型推导系

统

中是可证的),当且仅当

是

关于

的U

-极小改变(记作

ΓΔΘ

⇒B ).这是对于 T

的可靠性定理

和完备性定理

of 11

免费下载

软件学报计算机技术

关注

评论