强不一致性及其在知识库中的应用

¬KK•K人工智能267（2019）78强不一致性GerhardBrewkaa，MatthiasThimma，b，MarkusUlbrichta，a德国莱比锡大学计算机科学系b德国科布伦茨-兰道大学网络科学与技术研究所（WeST）Ar t i cl e i nf o a b st r a ct文章历史：2017年10月12日收到收到修订版，2018年10月30日接受，2018年11月11日在线发售2018年关键词：非单调推理不一致处理最小不一致子集计算复杂度知识库的最小不一致子集在命题逻辑中起着重要的作用，特别是在诊断、公理精确定位和不一致度量方面。事实证明，对于非单调推理，需要一个更强的概念。在本文中，我们开发了这样一个概念，称为强不一致。我们表明，在一个任意的逻辑，单调或不最小的强不一致子集起着类似的作用，最小的不一致子集在命题逻辑。特别是，我们证明了著名的最小不一致子集和最大一致子集的击中集之间的对偶推广到任意逻辑，如果使用的强概念的不一致。我们调查各种相关的推理问题的复杂性，并提出了一个通用的算法计算最小的强不一致的知识库的子集。 我们还展示了我们的新概念的应用潜力，专注于公理精确定位和不一致性测量。2018 Elsevier B.V.保留所有权利。1. 介绍本文的主要内容是不一致性，更确切地说是公式的最小不一致子集的概念在知识库中。这个概念对于经典逻辑或更一般的单调逻辑来说是非常有趣的，至少有以下原因：知识库的诊断与修复：不一致知识库的一致性可以通过计算机恢复-求出的最小不相容子集的最小碰集，并消去该碰集的元素。 的 结果将是[66]的最大一致子集。公理精确定位：在允许反驳证明的逻辑中，与公式p不一致的前提的最小子集可以被视为对p的解释，也就是说，负责p被蕴涵的前提不一致性度量：在文献中存在知识库不一致程度的各种突出的数值度量，这些度量取决于最小不一致子集（的数量），例如[43]。然而，这个概念-已经被证明在单调逻辑中非常有用-当涉及到基于形式主义的非单调推理时，如Reiter的默认逻辑[ 65 ]，回答集编程（ASP）[ 34，33，17 ]或抽象论证[ 27 ]，其价值相当有限*通讯作者。电子邮件地址：mulbricht@informatik.uni-leipzig.de（M.Ulbricht）。https://doi.org/10.1016/j.artint.2018.11.0020004-3702/ 2018 Elsevier B. V.保留所有权利。目录可在ScienceDirect人工智能www.elsevier.com/locate/artint··G. Brewka等人 /人工智能267（2019）78-11779KK联系我们联系我们关于我们关于我们联系我们在证明这一点之前，让我们提到，在其他情况下，概念需要加强，以便在非单调逻辑的上下文中变得有用。一个很好的例子是对等。在命题逻辑中，等价是重要的，因为它保证了可替换性：只要两个公式F和Fr是等价的，也就是说，模型，并且F是G的子公式，则在G中用Fr代替F得到与G等价的公式。 在非单调形式主义不再是这种情况。 例如，两个逻辑程序P1c不是b.和p2C.具有相同的（单一）稳定模型，但可替代性不成立。1例如，替换P3C不是B，B.与事实 即， moving from P1B.到 P2B. ，更改 P3. 这种观察导致了一系列关于所谓强等价的文献，这是一个更适合于非单调推理的等价概念（例如参见[55，31，61]）。我们在这里提到强等价并不是因为它与不一致密切相关，而是因为它有助于说明这篇论文的目标是什么。当涉及到非单调推理时，标准等价不是一个非常有用的概念，这一观察导致了一整套有趣的工作，研究更强的等价概念。类似地，从观察到最小不一致子集对于非单调推理不是很有用开始，我们的目标是这是一个更强的概念，它与经典逻辑的标准概念相一致，但对非单调逻辑更有用。现在让我们证明为什么最小不一致子集不能在非单调形式主义中扮演与经典逻辑相同的角色。考虑逻辑程序P4一不是A，不是B，B. .该方案是一致的，并具有稳定的模型 B.但是，它有一个不一致的子集，即 一 不是a不是b 这也是最小不一致子集。然而，由于P4是一致的，所以根本没有什么需要修复的。还请注意，文献中关于不一致性度量的标准假设之一是，知识库的不一致性值应该是0，如果是一致的.因此，这个例子也表明，最小不一致子集的数目的概念在定义非单调形式主义的不一致测度时是没有用的。本文的主要目标是发展和研究一个更强的概念不一致。我们将引入所谓的强不相容子集，它将经典的概念充分推广到非单调的情况，并研究这些集合中的极小子集。特别是，我们表明，我们的研究对象确实可以发挥同样的作用，为非单调推理的定期最小不一致子集的单调本文的贡献如下：1. 我们的结果适用于任意逻辑。因此，我们需要从形式上定义我们所说的逻辑。我们建立在[16]中逻辑的抽象表征的基础上，但适当地扩展了这个框架，以捕获同样抽象的一致性概念。此外，我们引入了一个新的概念，涵盖逻辑的单调性与多信念集。2. 我们定义了知识库的强不一致子集，这是本文的中心概念，并证明了强不一致子集和极大一致子集之间的广义对偶定理。这个定理将Reiter著名的碰集定理推广3. 我们通过研究公理精确定位和不一致性度量中的应用证明了我们的概念的有用性。(a) 公理精确定位的目的是确定负责某个蕴涵的公理。因此，它概括了检测不一致的时候，有一个公式表示矛盾。我们证明了强不一致性到所谓强解释的直接概括提供了正确的形式基础在任意逻辑中的公理精确定位(b) 同样，我们表明，各种不一致的措施，这是基于最小的不一致子集可以变成足够的措施，非单调逻辑切换到强不一致。4. 我们研究了强不一致和强等价之间的关系，给出了一个相容性结果。此外，我们还证明了以强一致性作为出发点，在对偶的结果类似的强不一致。5. 我们建立各种决策问题的复杂性结果（最小）强不一致。此外，我们提出了一个通用的算法计算强不一致的子集。本文的组织如下：我们首先在第2节中提出我们的抽象逻辑概念，它基于多上下文系统领域的类似描述[16]。我们还定义了单调逻辑的含义。第3节然后介绍- 引入了强不相容，证明了强不相容集与极大相容集之间的广义对偶结果。第四节讨论了我们的新概念在公理精确定位和不一致性度量中的应用。第五节研究了强不一致与强等价之间的关系，以及强一致的概念。计算方面的强不一致性，包括复杂性分析和计算强不一致子集的通用算法，研究在第6节。第7节讨论相关工作。第8节结束本文是会议文件的一个基本扩展版本[18]。特别是，会议版本没有证明，只有对潜在应用的初步讨论，没有考虑公理精确定位，以及对相关工作的有限讨论。1 逻辑程序的正式介绍在2.3节中提供.80G. Brewka等人 /人工智能267（2019）78-117：→K=10KK一一|=⇒⇔|=¬ ∧∨∈一一一一一一一一一一一一2. 背景本文建立了适用于任意逻辑的结果。因此，我们需要正式定义我们的意思。从逻辑上来说。任何一种逻辑的核心都是语法和语义。语法通常是根据可能出现在知识库中的格式良好的公式来指定的。语义可以用潜在的结果关系来描述。由于我们想要涵盖可能产生多个后果集（这里称为信念集）的逻辑，因此我们需要能够将知识库与多个信念集相关联。此外，存在知识库和信念集不具有相同语法的情况。 因此，我们需要提供方法来指定信念集是什么。我们将遵循[ 16 ]中逻辑的特征，其中逻辑由知识库的集合KB、信念集合的集合BS和可接受性函数ACC给出KB2个BS。我们在本文中的分析假设知识库是一套公式。信念集合的元素将被称为信念。此外，一致和不一致的信念集之间的区别是至关重要的工作在这里。 因此，我们需要以抽象的方式描述不一致性，而不需要对信念集的语法（例如否定的可用性）进行任何假设。 我们通过识别不一致的信念集的子集来做到这一点这导致了Brewka和Eiter的特征描述的以下扩展定义2.1. 逻辑L是元组L=（WF，BS，INC，ACC），其中WF是格式良好的公式的集合，BS是信念集合的集合，INC→BS是不一致信念集合的向上闭合2集合，并且ACC：2WF→2BS分配信念集合的集合每个子组的WF。L的知识库K是WF的有限子集。知识库K称为不一致当且仅当ACC（K）≠INC。因此，当知识库的所有信念集都不一致时，知识库就是 注意，这包括以下情况： 中国（），就是在哪里完全没有信念。一个知识库是一致的，即使它的一些（但不是全部）信念设置在INC。在本文的其余部分，我们有时会说，L=（WF，BS，INC，ACC）我们的框架这是指1. WF是L的合式公式的集合，2. BS是L的某个知识库可能拥有的所有信念（后果）集合3. INC包含被认为在L中不一致的信念集，4. ACC给每个知识库K精确地分配被L认为对K是可能的信念集。在下面的小节中，我们提供了定义2.1的实例，用于命题逻辑，量化布尔公式，答案集编程[34，33，17]和抽象论证框架[27]。我们提出这些实例来展示定义2.1的通用性，以模拟广泛的逻辑。2.1. 命题逻辑设A是一组命题原子（命题签名）。任何原子A都是一个合式的分子式wrt。 A.如果φ和φ是合式公式wrt. A，则φ，φ，φ也是格式良好的公式wrt。 A（我们还假设通常的缩写，故有相应的定义）。设WFP是wrt的合式公式集。 A.让被经典蕴涵关系，即如果所有的蕴涵关系模型也是经典命题语义中的蕴涵关系模型，则为蕴涵关系。 现在，BSP正是演绎闭集，即。BSP ={K} WFP |K ={φ |K |= φ}}。然后定义ACCP（K），对于每个K∈WFP，它是一个只包含K的演绎闭包的单例，即。A AACCP（K）={{φ |K |= φ}}对于所有KWFP. 设INCP= {WFP}，即唯一不一致的信念集是所有公式的集合。 然后，命题签名A上的逻辑LP可以定义为LP=（WFP，BSP，INCP，ACCP）2S上闭表示B∈S，B<$Br蕴涵Br∈S.G. Brewka等人 /人工智能267（2019）78-11781一一的1一Q、XKQ、XQ、XQ、X的1={{}}KK的1的1Q、XQ、XQ、XQ、XQ、XQ、XQ、XQ、XQ、XQ、XQBF QBF QBFQBF实施例2.2. 考虑命题签名A1= {a，b}和由下式给出的知识库K1，K2：K1={a，a<$b}K2={a，<$a}然后ACCP1（K1）={{a，a <$b，b，a <$a，b <$b，. }}ACCP1（K2）= {WFP}注意，由于ACCP（K2）<${WFP} =INCP， K 1 是一致的 ，而K 2 是不一致 的。很明显，命题逻辑在定义2.1之后讨论的意义上被LP恰当地模型化了。2.2. 量化布尔公式量化布尔公式（QBF）是一个公式= Q1X1. QmXmφwhichhquanti fiersQ1，. ，Qm∈{λ，λ}，pair-wisedisjointtsetsofvariablesX1，. ，Xm，以及m个φ在变量X1，... 100米如果φ相对于量化器评估为真，则QBF为真，例如，x1x2）是真的，因为对于x 1的每个真值，都可以找到x 2的真值，使得x1x2的值为真。一个QBF矩阵是前束正规形式，如果量化器Q1，...，Q m在m和m之间交替。我们也可以将量化的布尔公式转换到我们的一般逻辑框架中。 给定量化器Q= {Q1，...，Qm}以及变量集合X= {X1，...，Xm}，我们定义相应的逻辑L=（WF，BS，INC ，ACC ）如下：QBFQ、X是X 1 中 所 有 原 子 上 的 格式良好的布尔公式的集合. 100米 我们让BSQBF={{}，{}}，其中直观地，如果QBF评估为真，则{}是伪置信集，并且如果QBF评估为假，则{}是伪置信集我们就把它当作一个[n]。对于知识库K= {C1，...，设φ（K）=C1φ. ACCr和定义ACCQBF通过Q、 XACCQBF（K）=.{}，如果Q1X1.. .QmXmφ（K），Q、XQ、 X{}否则。现在，当且仅当知识库是一致的时，公式的值为true我们将在后面的第6节中使用QBF。实施例2.3. 设Q= {x，x}，X= {x1，x2}. 让K= {x1<$x2，x1<$$> x2}Kr= {x1<$x2，x2<$x1}，即， φ（K）=（x1<$x2）<$（x1<$$>x2）和φ（Kr）=（x1<$x2）<$（x2<$x1）。 现在注意到，x1是真的，x1并不自由因此，我们正式获得ACCQBF（K）={{}}，ACCQBF（Kr）={{k}}。由于不一致信念集的集合是通过INCQBF给出的，我们看到这是一致的，而r是不一致的-对应于QBF是否评估为真。请注意，根据定义，逻辑LQBF=（WFQBF，BSQBF，INCQBF，ACCQBF）正确建模QBF。WF82G. Brewka等人 /人工智能267（2019）78-117一如果P>ASPWF一一一一一一的1的1一一一一一一一一一一一一一2.3. 回答集编程我们现在将考虑在答案集语义下的选言逻辑程序，参见。[34、33、17]。又设A是命题原子的集合，令Lit（A）= A <${<$a|a ∈ A}是对应文字的集合。选言规则r是形式r：l0.lk←lk+1，.，lm，而不是lm+1，...，不是LN。（一）其中0≤k≤n l0，...，l n∈Lit（A），并设WFASP是所有这样的规则的集合. 对于规则r，我们将head（r）= {l0，.，l k}，pos（r）= {l k+1，.，l m}，并且neg（r）= {l m+1，.，l n}。如果m=n=k，则r被写为head（r）而不是head（r）←，如果另外k = 0成立，则该规则被称为事实。对于更多的语法糖，我们称之为形式规则r：a←l1，.，lm，而不是lm+1，...，不是ln，不是a。（二）其中，a是在给定程序P中的其他地方不出现的原子。直观的含义是，不允 许 P 的答案集包含所有的文字l1，...，l m，并且没有文字l m+1，.，ln.我们使用既定的速记法←l1，.，lm，而不是lm+1，...，不是LN。对于形式（2）的约束一个集合PWFASP也简称为逻辑程序。此外，信念集是文字的任何集合，即，BSASP=2Lit（A）。一一是一个没有默认否定的逻辑程序，即为所有r∈P我们有neg（r）一= m- 则模型M是任何集合M∈BSASP使得对于所有r∈P，如果pos（r）<$M，则head（r）<$M/=<$。如果M是P的包含两个互补文字的模型，则M=Lit（ A）。 M是一个极小模型，如果它是一个模型，并且不存在一个模型Mr满足Mr≠M。对于一个逻辑程序P∈WFASP，回答集M是任意集合M∈BSASP，使得M是该逻辑A A无缺省否定的程序PM定义为PM ={head（r）← pos（r）|head（r）<$pos（r），neg（r）∈ P，neg（r）<$M =<$}。然后我们定义ACCASP，ACCASP（P）= {M|M是P的答案集}对于所有的PWFASP. 最后，Lit（ A）是唯一不一致的信念集INCASP ={Lit（A）}。这给了我们一个逻辑LASP =（WFASP，BSASP，INCASP，ACCASP）。回想一下，由于我们的定义2.1，如果ACC（K）不一致，则知识库K是不一致的。注意，这个定义抓住了逻辑程序P可能不一致的两个原因：要么P只有Lit（ A）作为答案集，在这种情况下，ACCASP（P）={Lit（A）}= INCASP或P根本没有答案集，在这种情况下 ， ACCASP（P）=整数INCASP。实施例2.4. 考虑命题签名 A= {a，b}，逻辑程序 P，Pr 给定通过P={b.，<$b ←不是a. }Pr ={a.， b.，<$b ←不是a. }然后ACCASP（P）={}ACCASP（Pr）={{a，b}}观察到 P 不一致，而 Pr是一致的。显然，LASP正确地建模了ASP。现在让WFASP表示形式为（1）且k=0的所有规则的集合然后，A A aLASP=（WFASP，BSASP，INCASP，ACCASP）G. Brewka等人 /人工智能267（2019）78-11783是对应于回答集语义下的正常逻辑程序的逻辑84G. Brewka等人 /人工智能267（2019）78-117== ∈∈∈\∈∈⊆一一一关于我们一一一1nn+1n+2m−1M一1n+1n+2），…，（m− 1一一一一一一BCD一BCFig. 1. 例2.5中的论证框架AF。图2. 例2.5中的论证框架AFr。2.4. 抽象论证框架我们的最终知识表示形式主义被认为是定义2.1的具体实例，是抽象的论证框架[27]。在原始公式中，抽象论证框架AF是有向图AF（ A， R），其中 一 表示参数和关系 R 模型“攻击”，即， 对于a，bA，如果（a，b）R那么A是B的反证，我们说A攻击B。 抽象论证框架只在这个抽象层次上考虑论证问题，不考虑论证的内部结构，也不考虑攻击关系是如何推导出来的。语义被赋予一个抽象的论证框架 AF（A，R）通过识别集合 E一组可以被“联合接受”的参数（称为扩展）。关于如何定义“共同接受”，文献提供了各种方法原则上，任何语义都可以形式化为一般逻辑L，但我们在这里只考虑稳定语义，因为它是少数几个存在实际不一致框架的语义之一。 一个集合E A称为稳定扩张，如果没有参数a，bE加上（a，b）R，对于每个C一E有一个E加上（a，c）R.注意 一个抽象的论证框架可能没有、只有一个或多个稳定的扩展。为了将抽象的论证框架转换为我们的逻辑框架，设A是一些通用的论证集（与之前使用的命题签名相当）。一个良构公式要么是一个参数a∈A（说明参数a在图中），要么是一对参数（a， b）∈A×A（说明有参数a和b，并且存在从参数a到参数b的攻击），即，WFAAF=A（A×A）。为S={a，...，a、（a，a），.， （a），a）} AWFAAF我们写AF（S）=（{a，.，一一}，{（a，a一个一个一）），以注意由S表示的有向图。信念集则是参数的任意集合，即，BSAAF=2A，INCAAF= 1 A，以及A AACCAAF的定义为：ACCAAF（S）= {EA|E是AF（S）的稳定扩张}观察到， 如果出现以下情况，则认为S/WFAAF不一致 AF（ S）没有任何稳定的扩展，即， ACCAAF（S）==A AINCAAFA.这给了我们一个逻辑LAAF=（WFAAF，BSAAF，INCAAF，ACCAAF）实施例2.5. 考虑两个抽象论证框架 AF 和 AFr在图1A和1B中描绘的词汇表Aa、b、c、d上。1和2，分别。这些框架可以在我们的一般逻辑中建模为集合S， Sr=AAF，S={（ a， b），（ b， a），（ c， c），（ c， b）}Sr={（a，b），（b，a），（c，c），（c，b），（d，c）}更准确地说，我们有 AF（S）=AF 和 AF（Sr）=AFr。 然后ACCAAF（S）= 1000ACCAAF（Sr）={{a，d}，{b，d}}观察到S是不一致的，而Sr是一致的。同样，很容易看出，LAAF正确的模型论证框架下稳定的语义。读者可以验证其他逻辑的广泛范围也可以建模，例如一阶逻辑，模态逻辑，概率和模糊逻辑。MMG. Brewka等人 /人工智能267（2019）78-11785一一一QBF QBFQBFKK一KK一一一一2.5. 单调与非单调逻辑如前所述，本文的中心问题是研究非单调逻辑的行为。因此，我们给出了一个形式定义的“单调”逻辑在我们的然后我们将证明这个定义是行为良好的。我们的定义概括了[16]中的定义。 后者要求单调逻辑将唯一的信念集与知识库相关联，而我们的定义表明，对于具有多个信念集的逻辑，可以定义一个合理的单调性概念。定义2.6. 逻辑L=（WF，BS，INC，ACC）是怀疑单调的，只要K∈Kr∈WF意味着：1. 若Br∈ACC（Kr），则对某个B∈ACC（K），B∈Br.当K∈Kr∈WF意味着：2. 若B∈ACC（K），则对某个Br∈ACC（Kr），B∈Br。L是单调的，如果它是怀疑地和轻信地单调的。3顾名思义，怀疑单调保证了基于信念集交集的怀疑推理是单调的，而轻信单调保证了基于信念集并集的轻信推理是单调的。[4]这两个概念对于具有单信念集的逻辑显然是一致的我们将称一个知识库（怀疑地，轻信地）单调，只要它的相关逻辑是。这是轻微的虐待因为单调性是逻辑的属性，而不是知识库的属性。 然而，在许多情况下，保留实际的逻辑隐含并没有坏处，只要没有混淆的风险，我们更喜欢简单的术语为了使读者熟悉定义2.6，我们正式证明以下简单的观察。2.7号提案如上面所建模的命题逻辑，即，逻辑LP=（WFP，BSP，INCP，ACCP）A a a a A是单调的证据 设K，Kr ∈ WFP是两个命题知识库，即，命题公式的集合令KKr。根据定义，我们有ACCP（K）= {{φ|K φ}}，ACCP（Kr）= {{φ|Krφ}}由于K<$Kr，命题逻辑的单调性产生关于我们|Kφ}{φ|Krφ}。（三）现在我们看到定义2.6中的两项如下：1. “ Br∈ACCP（Kr）. 由于ACCP（Kr）是单例，我们得出结论： Br= {φ|Krφ}。 以验证由于定义2.6，P是单调逻辑，我们需要找到一个集合B ∈ ACCP（K），其中B ∈ Br。不过唯一的可能集合B是B ={φ|由于（3），我们有B <$Br，因此逻辑是弱单调的。2. “□换句话说，LP是单调的，因为ACCP包含一个集合，该集合只能通过添加更多信息来变得更大A A这符合单调逻辑的直觉作为第二个例子，让我们考虑一下QBF的逻辑2.8号提案如上所述的QBF，即，逻辑LQBF =（WF，BS，INC，ACC ）Q、 X是单调的Q、XQ、XQ、XQ、X[3]轻信单调与赖特的半单调概念有关然而，半单调性是特定于缺省逻辑的，并不捕获任意逻辑。此外，它只考虑添加默认值。4在严格偏偏好序下具有固定前提P的偏好子理论[15]提供了一个怀疑单调逻辑的例子但不是单调的。知识库是一组形式为p>q（p比q更受欢迎）的偏好表达式。的信念集是优先子理论的P下的顺序表示在 （如果不表示严格偏序，则信念集是P）。添加首选项可能会删除首选的子理论，但永远不会引入新的。因此，这种逻辑是怀疑论意义上的单调。它不是单调的，因为偏好的子理论可能会随着新的偏好信息而消失。L86G. Brewka等人 /人工智能267（2019）78-117Q、XK={{}}=K=一一一R一KK一一一一一一一一一一一一一一一一一证据设K，Kr=WFQBF=WFQBF。令KKr。首先假设ACCQBF（K）= {{k}}，即，QBFQ 1 X 1，...， Qm Xmφ（K）评估为false。 由于K<$Kr成立，合取φ（Kr）包含φ（K）作为子公式，即， 形式为φ（Kr）=φ（K）φ（K）因此，由于命题逻辑的单调性Q 1 X 1，...， Q m Xmφ（Kr）结果也是false20 1 9 - 04 - 2200：01：000 ），即， 我们可以选择B Br来证明定义2.6中所要求的条件。现在假设ACCQBF（K）= {{}}，即，QBFQ 1 X 1，...， Qm Xmφ（K）评估为true。在这种情况下，另一个QBF也可以评估为真或假。在第一种情况下，我们又有ACCQBF（K）=ACCQBF（Kr）。在后一种情况下，ACCQBF（K）= {{}}并且ACCQBF（Kr）= {{}}。因此，定义2.6的两个条件都可以看到。□作为我们的最后一个例子，我们表明，ASP没有默认否定是怀疑单调。这是一个非常简单的例子，一种怀疑论上的单调逻辑，但不是轻信的单调逻辑。因此，让WFASP-而不是WFASP是所有规则的集合。A A形式（1），其中m=n。 考虑一下逻辑LASP−not =（WFASP−not，BSASP，INCASP，ACCASP）。示例2.9. 让 P，Pr是由下式给出的两个程序：P = {a ∈ b. }，Pr ={a ≠ b.， a ← b. }。程序P有两个答案集{a}和{b}，因此，ACCASP（P）= {{a}，{b}}。我们还观察到，ACCASP（Pr）={{a}}。 因此，怀疑单调性的条件得到满足：如果 Br∈ACCASP（Pr），则 Br={a}。 为了显示存在一个集合B∈ACCASP（P），其中B∈Br，我们选择B= {a}。 然而，这个例子已经表明，LASP-不 不A A令人信服的单调性：没有Pr的答案集是{b}的超集。我们可以证明这个框架的一般怀疑单调性。2.10号提案没有如上所述的默认值的ASP，即，逻辑LASP-非=（WFASP-非，BSASP，INCASP，ACCASP）是怀疑单调的。证据 让 P，PrWFASP−not. 让 普雷普河 设Br是P r的答案集，即， Br∈ACCASP（Pr）. 由于Br是一个极小模型，Pr的一个模型，它也是P P r的一个模型。现在，有一个集合B∈Br，它是P的一个极小模型。因为B是一个答案集，B∈ACCASP（P）。 □逻辑L_ASP和L_AAF不是怀疑单调的，这由于示例2.4和2.5已经可以看出。在A A示例2.4程序 P 的子集 Pr. 然而， ACCASP（Pr）= {{a，b}}，因此如果 Br∈ACCASP（Pr），则 Br= {a，b}。以来ACCASP（P）= π，则不存在B∈ACCASP（P）且B∈Br.因此，这个例子表明ASP不是怀疑单调的。类似地，示例2.5说明了对于LAAF也是如此。在例2.4和例2.5中，我们看到存在不一致的知识库和一致的超集r。这在弱单调逻辑中是不可能的，这是一个非常简单但也非常重要的观察。引理2.11. 设L =（WF，BS，INC，ACC）是怀疑单调的，K ∈ Kr.如果K是不一致的，那么Kr也是不一致的。证据 让 K是不一致的，即， ACC（K）公司 让 克尔克河 如果 Br∈ACC（Kr），则 BBrfor a B∈ACC（K）. 然而，B∈ACC（K）意味着B∈INC，由于INC是上闭的，B ∈INC. 因此，ACC（Kr）公司。 □G. Brewka等人 /人工智能267（2019）78-11787K KKRH H H KKH K K HH HHK K H∈K= KK={}K={{}在本文的其余部分，它将变得明显，在引理2.11中描述的属性-不一致的知识库的超集是不一致的，以及-是最重要的一个，我们需要为了证明我们的结果（怀疑）单调逻辑。此外，我们需要处理的单调逻辑和非单调逻辑（怀疑地）之间的主要区别是引理2.11不适用于后一种情况。 然而，单调逻辑、奇异逻辑和轻信单调逻辑之间的区别不会起核心作用。在本文的其余部分，我们将简单地区分单调和非单调逻辑，以便于介绍。 然而，我们要强调的是，下面所有关于单调逻辑的形式结果都是基于引理2.11的，因此它们也适用于怀疑单调逻辑。3. 强不一致性设L（WF，BS，INC，ACC）是L.我们将在本节的其余部分中隐式地保留L。 我们使用I（）表示所有不一致子集的集合，. 一个集合I（）称为极小不相容的，如果r∈ R蕴涵r是相容的。我们让Imin（）是的所有极小不一致子集的集合。一致子集的称为极大- 一致，如果Çr意味着R是不一致的。 我们让 C=（）及C max（）表示所有相容且极大的 - 一致的子集 ，分别。在本节中，我们证明了本文最核心的结果之一。 Reiter在[66]中指出了知识库的最大相容子集与最小不相容子集之间的对偶--著名的碰集对偶。 它是在诊断的背景下陈述的，可以很容易地提升到一阶逻辑，或者更一般地说，任何单调框架。我们的强不一致性概念将有助于推广到任意逻辑，这是考虑普通不一致性的这种扩展当然，为了推广赖特定义3.1. 设M是集合的集合。我们称S为M的一个碰集，如果对每个M ∈ M，S <$M/=<$。M的一个碰集S是M的最小碰集，如果S∈S蕴涵Sr不是M的碰集。实施例3.2. 考虑命题知识库a，ab，b，c，C.我们有I min（）一个一个一b，b，c，C . 有6个最小碰集I min（ ）， a，c，a，c，...，B、C、D、E、在单调的情况下，我们有下面的对偶结果。在[66]中，它在系统描述的诊断设置中进行了说明。在任意单调逻辑的情况下，它是民间传说。我们在这里明确地陈述它，以便在我们的环境中证明它。定理3.3（MinHS对偶）。设K是单调知识库。则S是Imin（K）的极小碰集当且仅当K\S∈Cmax（K）.尽管这个定理是命题3.11第二项和下面的定理3.12的推论，我们给出了这个结果的直接证明通过这样做，我们可以对单调逻辑的定义有一个更好的直觉证据 “R首先证明H∈C（K）。 假设H是不一致的。 因此，H包含一个极小不相容子集H<$H。由于Hr=K\S我们有SHr=产生矛盾，因为S被假定为Imin（K）的击中集。 因此，H∈C（K）。现在，为了证明H∈Cmax（K），我们证明了任何具有H<$Hr<$K的集合Hr都是不相容的。这样的Hr具有以下形式Hr=H<$M，其中H/=M<$K\H。因此，它认为，M/=MS。由于S被假定为Imin（K）的极小碰集，S\M不是Imin（K）的碰集。Imin（K）。因此，Hr=H<$M=（K\S）<$M=K\（S\M）包含不一致的集合。由于引理2.11Hr本身是不一致的。“ 设H=K\S。 如果S不是Imin（K）的碰集，那么如上所述，我们看到H包含一个不相容子集，产生一个矛盾。因此，S是Imin（K）的一个击中集。现在假设有一个集合SrS也是Imin（K）的一个碰集。假设w。L. O. G. Sr是最小的。然后，K\Sr∈C（K），如上所示。然而， S r <$ S 隐含 K\ S <$K \ S r。 因此，K\S在C（K）中不是最大的，这是一个矛盾。□88G. Brewka等人 /人工智能267（2019）78-117K实施例3.4. 再考虑K= {a，a<$b，<$b，c，<$c}。如已经讨论的，Imin（K）= {{a，a，<$b}，{c，<$c}}。考虑从上面的第一个命中集，即，{a，c}。实际上，K\ {a，c} = {a<$b，<$b，<$c}是最大一致的。可以证明K恰好有6个最大相容子集对应于Imin（K）的命中集。对于非单调逻辑，这不再是真的，因为一致的知识库可能包含不一致的子集。因此，我们不能在Cmax（K）中找到所有集合。 下面的示例说明了不需要的行为。示例3.5. 考虑如下给出的逻辑程序P病人：一杯咖啡。a ← b.C不是B。<$c←不是b。观察P是不一致的：最后两个规则需要b，否则会产生矛盾。 虽然是 因为P的答案集不可能包含b，因为防止b被包含在最小模型中。我们看到I min（P）= {{c← not b.，<$c←不是b。}}。通过从P中移除Imin（P）的极小碰集，我们得到P\ {c← not b. }：a a ab。a ← b.<$c←不是b。P\ {<$c<$notb. }：a a ab。a ← b.C不是B。两者都是P的极大相容子集，但第三个极大相容子集P\ {a ← b. }：a {\displaystyle b}。C不是B。<$c←不是b。失踪了为了使定理3.3推广到非单调情形，我们考虑对不一致性作适当的修正。定义3.6. 对H，K<$WF，其中H<$K，称H是强K-不相容的，如果H<$Hr<$K蕴涵Hr是不相容的.如果没有混淆的危险，我们简称H为强不相容。换句话说，知识库K的子集是强K-不一致的，如果它的所有超集在知识库内，K也不一致直觉上，我们可以想到K中的一个冲突，它不能用K本身的公式来解决实施例3.7. 再次考虑K= {a，a<$b，<$b，c，<$c}。回想一下，{c，<$c}是K的不一致子集。当然，任何一套Hr与{c，<$c}<$Hr<$K也是不一致的因此，{c，<$c}是强K-不一致的。更一般地说，引理2.11确保了只要我们的逻辑是单调的，单纯不一致性和强不一致性就一致（参见。下面的提议3.11让我们考虑一个涉及非单调逻辑的例子，看看我们的定义在起作用。示例3.8.(a) 再次考虑上面的逻辑程序P。病人：一杯咖啡。a ← b.C不是B。<$c←不是b。记得 H= {c← not b.， <$c←不是b。}是的不一致子集 P. 然而，有一个一致的程序Hr，HHrP，即Hr：a birth b.C不是B。<$c←不是b。因此，H不是强P-不相容的。然而，G：a ← b。C不是B。<$c←不是b。是强P-不一致的(b) 现在考虑图3所示的论证框架。根据我们在2.4节中的逻辑，这个框架对应于知识库S= {（a，b），（b，c），（c，c）}。回想一下，我们考虑了稳定扩张。因此，我们看到{（c，c）}是S的不相容子集，因为没有稳定扩张。 然而，相应的框架到{（b，c），（c，c）}确实有一个稳定的扩展，即{b}。因此，{（c，c）}不是强S-不一致的。然而，可以看到{（a，b），（c，c）}是强S-不一致的。G. Brewka等人 /人工智能267（2019）78-11789{← <$←}R一BC图3. 例3.8中的论证框架AF。在著名的碰集对偶的情况下（见定理3.3），我们感兴趣的是最小冲突。定义3.9. 对H，K <$WF，其中H <$K，H是极小强K-不相容的，如果H是强K-不相容的且Hr <$H这意味着Hr不是强K-不相容的。设SI（K）表示K的所有强K-不相容子集的集合，SImin（K）表示K的所有极小强K-不相容子集的集合.示例3.10.(a) 再次考虑上面的逻辑程序P。病人：一杯咖啡。a ← b.C不是B。<$c←不是b。我们已经找到了强不相容集G：a ← b。C不是B。<$c←不是b。正如已经指出的，c不是b，C不是B。并不是很不一致因此我们看到G甚至是极小强不相容的。读者可以验证不存在其它极小强P-不相容集.因此，SImin（P）={{c ← not b.，<$c ←不是b.， a ← b. }}。(b) 再次考虑论证框架 S= {（a，b），（b，c），（c，c）}。 我们看到 SI最小值（S）={{（a，b），（c，c）}}。本文收集了单调和非单调逻辑中SI（K）和SImin（K）的一些基本性质3.11号提案K是一个知识库。1. 如果K是单调的，则I（K）= SI（K）。2. 如果K是单调的，则Imin（K）= SImin（K）。3. K是不相容的当且仅当SI（K）/= λ当且仅当K∈SI（K）.4. 若H是强K-不相容的且H<$Kr<$K，则H是强Kr-不相容的.证据 设L是单调逻辑，K是知识库。1. I（K）∈S I（K）是明确的：IfH∈/I（K），即，H是一致的，n个H不能被定义为不一致的-初始化。rWeshowI（K）S I（K）：L etHK. L ∈H∈rI（K）. 因此，Hr是不一致的。你给莱姆打电话了。11个，每个chHr，H也不一致特别地，每个H与H<$H<$K是不一致的。因此，H是强不一致的。2. 这是第一项的必然结果现在让L成为任意逻辑。如上所述，让K成为一个知识库。3. 如果K是不一致的，则K∈SI（K），因此SI（K）/= π。 如果SI（K）/= H，则存在一个集合H使得每个Hr与H <$H<$K不一致。特别是，K本身是不一致的。 因此，K是不一致的当且仅当SI（K）/= π。 我们同样发现K是不相容的当且仅当K∈ SI（K）。4. 设H∈SI（K）.因此，每个Hr与H<$Hr<$K是不一致的。 现在让KrK。 因此，每个Hr与H<$Hr<$Kr也是不一致的。因此，H∈SI（Kr）。这就完成了我们的证明。 □90G. Brewka等人 /人工智能267（2019）78-117KKKK=KKK={<$$>}K={{<$<$} {}}∨现在，我们可以将定理3.3推广到非单调的情况。定理3.12（广义MinHS对偶）。K是一个知识库。则S是SImin（K）