文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 一种规约于可满足性问题SAT的知识推理算法
侵权投诉

一种规约于可满足性问题SAT的知识推理算法

传统的知识推理算法主要依赖于通用的定理证明器,因此会有明显的组合爆炸问题和半自动化问题,只能处理小规模的问题.在文[1]中,给出了一个实用而紧致的知识的语义模型--知识结构(knowledge structure),并给出相应的利用BDD(Binary Decision Diagram)的符号化计算方法,实验表明这种基于BDD的算法比传统方法有很大的优势,但这种基于BDD的方法在计算规模大的例子时仍存在明显的组合爆

苏玎乐等:一种规约于可满足-哇河题(SAT)的知识推理算法

可能十}f=界的语义是很抽象的,无法计算。因此文11]中给出了一种等价的和可f;卜算的浯义:知识结构

(knowledgestructure)。r面将介绍它的语义定义。

2.2语义

2.2.1可能1址界沿义

‘个Kripkc结构是一个多元组M=(Ⅳ,口,K.,

…,K。),其中Ⅳ足一个状态集(states

or

worlds),口

是一个赋值函数.将布尔原子公式的值和每个状态联系起来.即对于每个原子命题P和状态”∈形.

口(∞)(p)∈ftrue,false}。K一一,E。称为形上的等价关

系。按照常规,一和口”用来表示在Kripke结构M中

的关系K.和函数F。在下文中,若}下文清楚,忽略

上标M。对丁任何"∈W,定义K,(")=仲’l(钾,协’)∈Ⅳ。}。也就是说,K。(Ⅲ)是agenti在状态”所认为的所有的可能世界集合。

一个局势(situation)是个Kripke结构M和状态w的二元组(M,")。一个公式咖在这个局势(M,”)下成立(表示为(M,Ⅲ)}咖)由以下归纳定义给出:对丁原子命题P,(M,叫)忙P当且仪当7r…(训)(P)=trlle。命题的“和取”和“非”依此类推。最后,(M,Ⅲ)}

K.Ⅱ当且仅当对于所有的伽7∈《(埘),(M,删7)}OL。这样,一个agenti知道a(i.e.,K

,∞当且仅当“在所有这个agent所认为的可能世界中都成立。更进‘步,对于agent集合GC{l,…,n),(M,")=_『)c““{且仅当刘于所有的埘’En。。撂:1(埘),(M,州’)}“;而(M,”)}C,d当且仅当对于G中的所有可能的agent

的有限序列(i∥..,i。),(M,埘)}“^K¨…,K;d。对

于一组状态集合A,定义(村,d)bd当且仪当对所有

川∈A,(M,川)}d。

2.2.2知识结构

一个含有n个agent的知识结构(knowledge

structure

Fwith

H

agents)是一个多元组(r,0,0.,

…,0。),其中P是一个有限的布尔变量集合,0是VL的有限的布尔公式集合.对于每个agen{i,0.是v的子集。y中的变量称为r的系统变量(systemvariables),而0.中的变量称为agenti的可观察变量

(observable

variables)。D为公共知识库(common

8l

knowledge

base)。V的一个满足@的赋值称为r的

一个状态(state)。这里用被赋予tn]e的变量集合米表不一个变量集合的一个赋值。因此@用符号化的方法表示了所有ⅡJ能的状态集合。最后,给定一个状态州.定义埘n0.为ageifl:在状态仲的局部状态,即i在全局状态”的局部状态。

这里汀丁以把‘个14a'ipke结构Ⅳ(r)=(∥,口,K..…,K)和一个知识结构r联系起米,其中:【1)W足r中的所有可能的状态,也就是所有满足0的赋值集合;(2)对于任何seⅣ,赋值口(s)与s相同;(3)利于任何agenti和两个r中的状态”和训’,wK.删7当且仅当"n0.=w7n0.。

2.2.3基于知识结构的知识推理

下面回顾义…中的一些基于知识结构的知识推

理的相关技术结果。

给定一命题变量集合P,文章有时不对P的子集

和它相应的特征函数(即P的一个真值赋值)加以区分。如果p中的每一个命题变量都在P中m现,称公

式妒在P上。方便起见,将true作为对总是有效的命

题公式的缩写,如pV]P,这里p是P中的一个原子命题,]tl'l/e缩写为false。

用b表示真值赋值和公式之间通常的满足关系。另外,对于公式集r和公式妒,用r}妒表示:对于每个赋值盯,如果对于所有d∈F有盯}“,则矿}妒。

给定命题公式妒和命题变量P.则用妒(TY—lle

L)表

示妒中的P用true替换后的结果。类似地可定义妒

(击)。“变量忘记”(Variable

forgetti“g)嘲或“消除

中间项”(eliminations

of

middleterms){‘Ol定义如下。

定义1令妒为P上的一个公式集台,并且y∈P。“在驴中忘记r”记为jy妒,即P上的一个量化公式.可归纳定义如下:

(1)j踟=妒;

(2)j眵】妒邓(盎。)V妒(击);

(3)j(ru扣j)驴=jr(]细)妒)。

方便起见,用V哳表示]]v(7妒)。

显然,]y妒是独立于v的妒的一个逻辑推论,并且足妒的最强推论。有关变量忘记其它

面的性

上一页第3页

你可能喜欢

热门文档

相关文档

  • 对可满足性SAT问题求全解的算法研究及实现

    对可满足性SAT问题求全解的算法研究及实现_IT/...在这 一推理算法中,每个子句有两个相关的指针,分别... 中医养生知识大全 女人养生之道 78份文档 笑翻...

  • 利用一种SAT问题全解算法求Trivium可滑动对

    2012 利用一种 SAT 问题全解算法求 Trivium 可滑动对戴江海, 戚文峰( 信息工程大学 信息工程学院, 河南 郑州 450002) 摘要: Trivium 是进入到 eSTREAM 计划最终...

  • 可满足性问题DPLL算法研究

    实验结果验证了 这项新的正向推理技术的有效性,并...可满足性问题算法(TheSatisfiabilityProblem, 简称SAT...章简要介绍和说明了有关可满足性问题的基础知识和 ...

  • 基于集合理论的SAT算法的设计与实现

    (如C,C++),或者学过数字电路的基本 知识的人,对...而且在自动化推理,人工智 能,资源调度,VLSI集成电路...电子科技大学硕士学位论文 1.1.2 SAT问题及其算法...

  • 一种新的SAT问题预处理算法

    一种新的SAT问题预处理算法熊 伟.唐璞山(复旦大学专用集成电路与系统国家重点实验室.上海201203) 抽要:提出了一项新的正向推理技术:对祢扩展的一元子句推导(...

  • 一种新的SAT问题预处理算法

    一种新的SAT问题预处理算法一种新的SAT问题预处理算法隐藏>> 20 年第 2卷...算法的 有 效性, 证明了 这项对 称扩展一元推导技术的 强大正 向 推理能力...

  • SAT问题及其转换公式

    命题逻辑 可满足性问题的算法 分析[J]. 计算机科学...? BMC问题能够有效地规约成命题SAT问题。 只考虑一...它们的最短的推理出空 子句的归结证明长度是指数的...

  • 一种改进的基于SAT的多错误诊断算法

    改进了二种组合电路设计错误诊断DED(Design Error Diagnosis)算法。它使用多可满足性问题(SAT)求解技术,通过对布尔可满足解计数来实现对多个逻辑错误的诊断定位。...

  • 一种基于形式规约说明的类测试框架

    产生了传统语言设计所不存在的错误可能性,或者使 得传统软件测试中的重点不再...基于范畴划 分方法构造测试层次算法, 将操作的输入空间划分为具有某些相同性质的...

  • 基于SAT工具的限界模型检测归约方法

    规约为命题逻辑的可 满足性问题,从而可以使用 SAT ...魏小勇 基于OBDD的SMC中PRE操作的改进算法 2008(14...分析方法,在验证电子商务协议时,它的 逻辑推理能力...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email