传统的知识推理算法主要依赖于通用的定理证明器,因此会有明显的组合爆炸问题和半自动化问题,只能处理小规模的问题.在文[1]中,给出了一个实用而紧致的知识的语义模型--知识结构(knowledge structure),并给出相应的利用BDD(Binary Decision Diagram)的符号化计算方法,实验表明这种基于BDD的算法比传统方法有很大的优势,但这种基于BDD的方法在计算规模大的例子时仍存在明显的组合爆
80Journalof
Frontiers
of
Computer
Science
andTechnology计算机科学与探索2007,1(1
l
引言
认识论,即对知识的研究,从古希腊哲学家开
理一尝小规漠的问题(toyexamples)。
文【l】给出了一个吏用而紧致的知识的语义模etln’e)。这种方法本质上型:知识结构(knowledgestlM是基于语义的,但通过使用知识结构,给出了一种基于语法的简洁形式来表示Kfipke结构,而且可以随接转化成一个符号化布尔算法,借助符号化工具如
BDD(Binm3,DecisionDiagramn|_算,所以在一定程
始,在哲学中有很长的研究历史以及良好的传统Ⅲ。刘诸如“我们知道什么”。“什么能够被知道”、“说某人知道什么到底意味州么”等问题,在哲学文献中有很多讨论。rODWright在20世纪50年代的工作[31给出了对知识推理进行形式化分析的思想。1962年.Hintikkat41第一个以书本的形式给出了认知逻辑一知识逻辑的形式化研究。随后,关于知识的研究在哲学界蓬勃发展起来,主要兴趣之一是如何抓住知识的本质特征。各种关于知识的公理系统建立起来。最近,在不同领域(如经济学、语言学、人工智能以及理论计算机科学)的学者们都对知识推理产生兴趣。关于知识的研究也随之扩大.并在很多领域蓬勃发展起来,如博弈论、经济学、机器人、知识库等领域,来研究如机器人如何获得知识并进行推理以采取下一步行动、数据库何时回答“不知道”、商务智能体(a.
度上避免了状态爆炸问题。该知识结构框架既简单又强大,足以用来分析应用中的协议,如广泛使用的安全协议.实验表明这种基于BDD的算法比传统方法有更大的优势。但是这种基于J=;DD的方法存计算规模大的例子时还是有比较明显的组合爆炸问题。
艾章在知识结构(knowledgesrruetm'e)的语义基础上,通过挖掘知识结构语义中各元素的关系.将把知识的计算规约于可满足性问题(SAT),因为SATSolver在符号化计算方面在计算规模和效率上都要远远优越于BDD,并EL
SAT
solver的发展州当迅速。
gent)女n何收集信息以做决策等问题。其次.计算知识的复杂度也是一个研究方向。另外.知识推理研究
的重点是针对群体智能体(a
groupof
通过这种关系的揭示,还可以在计算复杂的公共知识时避免基于BDD方法f11中的繁琐的不动点计算。
下面将用实验结果来证实这种方法的有效性。
文章结构如下:先简单介绍认知逻辑的基本概念,然后介绍知识结构巾的一些技术结果.给出将这种语义计算规约于可满足性问题(SAT)的一些具体结果,接着将该方法应用于著名的”泥巴小孩”游戏和安全协议验证的实验结果,最后是相关工作和结论。
agents)的情况
(该文也如此),而非单个智能体(哲学家们偏向于研
究)的情况。这是因为对话、谈判、或者是分布式系统中进程问的协议,都是智能体间的交互行为口。
认知逻辑(或知识逻辑)一般认为起源于JaakkoHintikka在20世纪60年代早期的工作H,他描述了如何使用特定的模态逻辑来刻画知识的本质。在20
世纪80年代中期,Haivel'n和他的合作者发现s5认
知逻辑能够给出在分布式系统中进程(一般称之为agent)状态的自然解释。该模型即为所谓的解释系统
(interpreted
2认知逻辑
2.1语法
给定一个命题原子集合。,认知逻辑(知识逻辑)的良构公式(thewellfoundedformulas(wff))为以下定义的BNF:
system)模型日。研究发现.该模型在分布
式系统理论中起关键作用,已经成功应用到对通信协议的推理中日。然而,关于认知逻辑的工作还主要集中于理论方面的研究.例如:模态逻辑的各种变
(删)::=qblq(删)I(埘)A(wff>lK,(,4t'>LD,(wff)
lcc(wff)
简单的说,公式K。咖表示智能体i知道命题‘:b;D。咖表示在G中的所有智能体的分布式知识(d谆
tributed
种,完全性,计算复杂性。以及衍生的概念(如分布式
知识、公共知识)等。
对于认知逻辑相应的算法研究比较少.有基于证明的和基于语义的,例如文献[6—81。基于证明的方法依赖于多命题模态逻辑的证明器.所以处理规模和效率,及表达能力都不高;基于语义的对的问题是状态爆炸问题。闲此传统的
法主要面法只能处
knowledge)为咖;Cc币表示G中所有智能体
的公共知识(commonknowledge)为咖。这里K。、Dc和cG称为知识模态词(knowledgemodalities)。
认知逻辑的标准语义为Kfipke语义日。这种基于
对可满足性SAT问题求全解的算法研究及实现_IT/...在这 一推理算法中,每个子句有两个相关的指针,分别... 中医养生知识大全 女人养生之道 78份文档 笑翻...
2012 利用一种 SAT 问题全解算法求 Trivium 可滑动对戴江海, 戚文峰( 信息工程大学 信息工程学院, 河南 郑州 450002) 摘要: Trivium 是进入到 eSTREAM 计划最终...
实验结果验证了 这项新的正向推理技术的有效性,并...可满足性问题算法(TheSatisfiabilityProblem, 简称SAT...章简要介绍和说明了有关可满足性问题的基础知识和 ...
(如C,C++),或者学过数字电路的基本 知识的人,对...而且在自动化推理,人工智 能,资源调度,VLSI集成电路...电子科技大学硕士学位论文 1.1.2 SAT问题及其算法...
一种新的SAT问题预处理算法熊 伟.唐璞山(复旦大学专用集成电路与系统国家重点实验室.上海201203) 抽要:提出了一项新的正向推理技术:对祢扩展的一元子句推导(...
一种新的SAT问题预处理算法一种新的SAT问题预处理算法隐藏>> 20 年第 2卷...算法的 有 效性, 证明了 这项对 称扩展一元推导技术的 强大正 向 推理能力...
命题逻辑 可满足性问题的算法 分析[J]. 计算机科学...? BMC问题能够有效地规约成命题SAT问题。 只考虑一...它们的最短的推理出空 子句的归结证明长度是指数的...
改进了二种组合电路设计错误诊断DED(Design Error Diagnosis)算法。它使用多可满足性问题(SAT)求解技术,通过对布尔可满足解计数来实现对多个逻辑错误的诊断定位。...
产生了传统语言设计所不存在的错误可能性,或者使 得传统软件测试中的重点不再...基于范畴划 分方法构造测试层次算法, 将操作的输入空间划分为具有某些相同性质的...
规约为命题逻辑的可 满足性问题,从而可以使用 SAT ...魏小勇 基于OBDD的SMC中PRE操作的改进算法 2008(14...分析方法,在验证电子商务协议时,它的 逻辑推理能力...
热门文档