抽象辩证框架三值接受条件的计算论证核心概念

可在www.sciencedirect.com在线获取理论计算机科学电子笔记344（2019）3-23www.elsevier.com/locate/entcs论抽象辩证框架的三值接受条件JoaoAlcAlcohantara1巴西福塔莱萨大学计算机科学系SamyS'a2UniversidadeFederaldoCear‘a菜ad‘a，Brazil摘要抽象辩证框架（ADFs）是Dung的抽象论证框架（af s）的推广由此产生的扩展是足够强大的，不仅可以模拟原来的攻击关系AFs，但也有其他类型的依赖关系和参数之间的相互作用。ADFs的最近发展提出了一种涉及三值接受条件的替代形式化，将ADFs的原始定义与三值论证标记的概念联系起来，这是计算论证文献中的核心概念在本文中，我们修改了在这种三值方法下定义的一些主要语义，并证明了我们的定义与AFs的已知语义是等价的关键词：抽象辩证框架，论证标签，论证，知识表示，不确定性。1引言知识表示和推理领域的一个主要问题是回答如何通过推理得出结论。 一个可能的途径是诉诸形式逻辑来象征性地表示解决问题所需的知识，并确保所执行的推理是合理和完整的。一个持续的趋势存在于计算论证的子领域，其中论证和计算机科学之间的联系被利用来执行演绎和非单调或可废止的推理[22，23，30，31，25]。1电子邮件地址：jnando@lia.ufc.br2电子邮件：samy@ufc.brhttps://doi.org/10.1016/j.entcs.2019.07.0021571-0661/© 2019作者。出版社：Elsevier B.V.这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。4J. 阿尔坎塔拉湾Sá/理论计算机科学电子笔记344（2019）3在这种趋势下，推理过程的特点是构建和评估论点，这（粗略地说）可以被理解为一组理由的有效性特定的索赔。这一领域的核心参考，Dung[15] 将参数建模为抽象实体，其中定义了攻击关系。Dung提出了被计算论证界广泛采用的重要概念，例如论证可接受性的概念。这个概念建立在这样的直觉上，即要接受一个主张c，一个人需要同时具有一个论证A支持C，并证明拒绝所有其他论证是合理的，与A.简而言之，在逻辑学中，推理过程集中于论证中的推理，而在论证中，推理过程还涉及论证之间的相互作用。Dung方法的一个关键创新从数学的角度来看，这样得到的论证框架是一个有向图，其节点是论点，边表示论点之间的冲突。论证框架的语义返回可接受的论证集，即框架的扩展。应该清楚的是，不同的可接受性标准将指定不同的语义，包括Dung的Dung的论证框架取得了显著的普及，但他们也受到了批评。一个有争议的问题是，他们声称有限的表达能力的AFs，因为他们缺乏某些功能，这是常见的几乎每一种形式的论证，以发现在实践中[6]。事实上，在Dung的论证框架中，原子论证之间唯一的相互作用是由攻击关系给出的。 正如[5]中所概述的，许多扩展AF的可以在文献中找到;其中包括具有支持关系的AF[12，13，20，21]，攻击攻击[19]和权重的AFs[18，16，14]。在这样的动机下，Brewka和Woltran在[6，4]中引入了抽象辩证框架（ADFs），这是Dung论证框架的推广，允许表达参数之间的任意关系。他们的方法试图统一几种不同的AFs扩展，并以一种有原则的、系统的方式推广Dung在ADF中，除了攻击关系外，参数可以相互支持，或者一组参数可以联合当群体中的每一个成员都没有足够的力量去攻击另一个成员时[3]。这种额外的表达性是通过将每个节点（参数）与其二值接受条件相关联来获得的，这些条件可以表示为任意的命题公式。直觉是，如果一个论证的相关接受条件被接受，那么这个论证就被接受了.简而言之，我们可以将ADF描述为依赖图+接受条件。文献[1]中提出了ADF的另一种形式化，其中作者引入了参数的三值接受条件。这一举动的动机是理解在AF语义中，给定的参数可以是J. 阿尔坎塔拉湾Sá/理论计算机科学电子笔记344（2019）35接受、拒绝或待定，但[6，4]的二值接受条件没有显式地将参数评估为待定。由于这种差异，[1]的所得ADFs产生相对简单的形式化，其保持[6]的相同结果，同时还捕获AFs[29，8]的半稳定语义，这在[6]中没有考虑。为了说明差异，我们提供了一个例子。例1.1设A={a，b，c}是一组参数。 为了描述ADF，我们需要 明确其接受条件。 考虑下面的两个场景，其中对于每个参数s∈A，其相关的接受条件表示为写在s右侧方括号内的命题公式：我：一[b];B[<$b];c[T]II：a [（bc）（<$bc）（bc）];B [<$b];c[T]从场景I中我们可以观察到，如果b或c被接受，则a被接受;如果b不被接受，则b被接受，并且c总是被接受。假设这些接受条件采用两值方法，我们得出结论，方案II显然等同于方案II。I. 然而，由于参数本身是根据三值标记进行评估的，因此可以理解的是，接受条件仅根据两个真值进行评估。通过提出一个三价值的方法，我们基本上是在不接受和拒绝之间做出区分。在这种情况下，上面的两个场景将不等价：假设我们有c是可接受的，b是未定义的。在场景I中，我们有a也将被接受;在场景II中，只有c将被接受，因为只有当我们接受或显式拒绝b时，a才能被接受。在本文中，我们利用[1]的形式化并修改他们对完全标号的定义，以寻求直接后果算子的定点，该定点关于逻辑编程理论中常用的真值排序是最小的。正如我们将展示的，这种差异将保证对于每个adf，ADF语义和Dung的af语义之间的等价结果其接受条件模拟某些AF的攻击关系。因此在该结果中，ADF语义将被证明扩展用于AF的众所周知的语义，诸如完全、稳定、优选和接地语义[15]以及半稳定语义[29，8]。本文的主要内容如下。首先，我们回顾了必要的背景，Dung接下来，我们提出了ADFs与三值接受条件，容纳重要的概念，如完全标号和直接后果操作符ΓD。在随后的部分中，我们通过提出与AFs相对应的ADFs的子类来检查ADF s和AFs之间的关系。我们的一些主要结果将在这一点上介绍。最后，我们对所得结果进行了讨论，并对今后的工作提出了建议6J. 阿尔坎塔拉湾Sá/理论计算机科学电子笔记344（2019）32预赛在本节中，我们概述了与（抽象）辩论框架相关的主要定义[15]。我们特别感兴趣的是如何抽象argu- mentation语义可以制定的标签。在这篇文章中，我们将把自己限制在有限的论证框架上。定义2.1[论证框架][15]是一个对（Ar，att），其中Ar是一个有限的参数集，att<$Ar× Ar。参数通过攻击关系att与其他参数相关：参数A攻击Bi <$（A，B）∈att。一个论证框架可以被看作是一个有向图，其中的论点是节点，每个攻击是一个箭头。给定一个论证框架，我们主要感兴趣的是计算其语义。[15]的传统方法是通过基于可接受性的概念（见[15]）识别参数集（称为扩展）来实现的我们将在这项工作中考虑的方法是最初在[7]中引入的抽象论证语义的另一种形式化，使用参数标记而不是参数扩展：2.2.2[参数标签][7]设（Ar，att）为AF。标签是一个全函数L：Ar：{in，out，unec}。我们在（L）中 写 为{A| L（A）= in}，out（L）for {A| L（A）= out}和unec（L）对于{A| L（A）= unec}。有时，我们将标号L写成三元组（Ar1，Ar2，Ar3），其中Ar1=in（L），Ar2=out（L），Ar3=unec（L）。标签in旨在表示参数被明确接受;标签out旨在表示参数被拒绝，标签unec旨在表示参数的状态未决定，即，对于争论是否应该被接受，没有达成任何裁决。 我们接着回顾可容许标签的定义：定义2.3[可接受的标记][2]设（Ar，att）为AF。• 如果所有攻击者都被贴上标签，则称标签内的论点是合法的。出去• 如果一个标签外的参数至少有一个攻击者是标签内的，那么它就被称为合法的外参数。一个标号L是可容许的，如果每个标号内变元合法地在且每个标签外的论点在法律上是不成立的。根据这个定义，对于任何论证框架，所有论证都是unec的标签是可接受的。通过加强在可容许性的特征化中所采用的基本要求，我们得到完全标记的概念2.4.4[完全标记] [9]设（Ar，att）为AF。一个标号L是完备的，对于每个自变量A∈Ar它成立，J. 阿尔坎塔拉湾Sá/理论计算机科学电子笔记344（2019）37一BC(i) L（A）=in i，则每个攻击A的B∈Ar都有L（B）=out。(ii) 存在B∈Ar攻击A使得L（B）=in.(iii) L（A）=unec i ≠不是每个攻击A的B∈Ar都有L（B）=out且没有B∈Ar攻击A有L（B）=in。值得注意的是，每一个完整的标签都是可以接受的。下面的示例说明了两种类型的参数标注：例2.5考虑AF=（Ar，att），其中Ar={A1，A2，A3}并且att={（A1，A2），（A2，A1），（A2，A3）}。我们有• Admissible labellings: ({},{},{A,B,C}), ({A},{B},{C}), ({A,C},{B},{}),({B} , {A} , {C}), ({B} , {A, C} , {}).• 完整的标签：（{}，{}，{A，B，C}），（{A，C}，{B}，{}），（{B}，{A，C}，{}）。现在我们可以用标注来定义AF定义2.6[7，10]设L是AF的所有完全参数标号的集合。然后• L是AF的接地参数标号，如果L ∈L且$LJ∈L使得在（L）中，j）在（L）中。• L是AF的优选论元标号，如果L∈L且$LJ∈L使得在（LJ）中in（L）.• 当L ∈L且unec（L）=∞时，L是f的稳定标号.• L是AF的半稳定辐角标号，如果L ∈L且$LJ∈L使得unec（LJ）unec（L）.请注意，完整的论元标签如何构成刻画这些语义的基本概念：例2.7设AF=（Ar，att）是一个抽象论证框架，使得Ar={A，B，C，D}且att={（A，A），（B，A），（C，B），（C，D），（D，C）}。我们-皮克特空军关于语义，AF有：• 完整的标签：（{}，{}，{A，B，C，D}），（{B，D}{A，C}，{}）和（{C}，{B，D}，{A}）。• 固定标签：（{}，{}，{A，B，C，D}）。• 首选标签：（{B，D}{A，C}，{}）和（{C}，{B，D}，{A}）。• 稳定标记：（{B，D}{A，C}，{}）。• 半稳定标记：（{B，D}{A，C}，{}）。8J. 阿尔坎塔拉湾Sá/理论计算机科学电子笔记344（2019）3一BDC图1.一、一个抽象的论证框架，有6个论点。很明显，只要框架至少有一个稳定标记，半稳定标记就与稳定标记一致。另一个重要的结果显示如何参数标签相互关系被证明在[7，11]：定理2.8[7，11]设L是论证框架F =（Ar，att）的完全论元标号。它持有• 在（L）中是最大的（w.r.t.集合包含）是F_i的所有完全论元标号中最大的（w.r.t.集合包含）在F的所有完全论元标号中。• 在（L）中是最小的（w.r.t.集合包含）是最小的（w.r.t.集合包含）。因此，关于完全标记，我们可以说，最大化（相应地）。最小化）标签等于最大化（相应地，最小化）标签。这一结果将在第4节（定理4.4）中使用，以保证我们将为抽象辩证框架（定义3.9）定义的语义是定义2.6中的语义的扩展。3抽象辩证框架抽象辩证框架在[6]中被引入，以将参数（在那里称为陈述）视为抽象和原子实体。它可以被看作是一个有向图，其节点表示可以接受或不接受的语句。此外，节点之间的链接表示依赖关系：节点s的状态仅取决于其父节点（表示为par（s））的状态，即与s有直接链接的节点。在本文中，我们将对这种方法做一个小小的改变：而不是诉诸par（s）的子集来评估s的状态，我们将通过诉诸Lit（s）的子集来使语句之间的依赖性更加明确Lit（s）=par（s）sJ|sJ∈par（s）一个集合M∈Lit（s）是相容的，如果没有陈述s∈par（s）使得{s，<$s}嗯。 我们记为Cs={MLit（s）|M是一致的}所有的集合J. 阿尔坎塔拉湾Sá/理论计算机科学电子笔记344（2019）39Sϕϕ），其中CCs| s ∈SLit的一致子集。我们将把a∈S称为正数（分别为）。否定的）陈述，如果a∈M（分别<$a∈M）。现在，我们可以相应地改变抽象辩证法框架的原始定义[6]，以获得以下结果：定义3.1[抽象辩证框架]抽象辩证框架是元组D=（S，L，C），其中• S是一组语句（位置，节点），• LS×S是一组链路，• C ={C s|s∈S}是一组全函数Cs：Cs→{in，out}，每个语句s对应一个，使得对任意M∈Cs，如果Cs（M）= in，则Cs（MJ）= in，对任意MJ<$M。Cs称为s的接受条件。用于语句s的函数Cs旨在确定s的接受状态，其与之前一样仅取决于其父节点par（s）的状态。新颖之处在于，现在对于每个节点s∈S，其接受条件Cs明确指定了s被接受的确切条件，从而为（部分）三值设置提供了空间直觉，• 如果存在M∈Cs使得Cs（M）=in且M中的每个肯定陈述都被接受而M中的每个否定陈述都被拒绝，则s将被接受• s将被拒绝，如果对于每个M<$Cs使得Cs（M）=in，存在M中的被拒绝的肯定陈述或M中的被接受的否定陈述。• 否则，S将被定义3.1表示验收条件ADF（S，L，C）在C中的接受条件也可以用两种替代方式表示：• 任 何 函 数 Cs∈C 都 可 以 用 导 致 s 被 接 受 的 Cs 的 子 集 的 集 合 来 表 示 ， 即 ，Cin={M∈Cs|C s（M）= in}。我们将指出这一点S在in.在……• 任何函数Cs∈C也可以表示为词汇表Cs上的一个命题公式Ss，如下所示：伊希斯{a1，.，am，<$b1，.，<$bn}∈Cina1···am<$b1···bn如果m = n = 0，则相应的a1···a m<$$>b1···b n<$T，其中T是常数，其值始终为。如果不存在M∈Cs使得C s（M）= in，则φ s∈ φ，其中φ是一个常数，总是求值为out。我们将通过将ADF表示为（S，L，C）来指示这种替代方案，其中C指的是集合{\fnSimHei\bord1\shad1\pos（200，288）}|s ∈ S}。当将ADF称为（S，L，C）时，我们将假设接受公式隐式地指定节点所依赖的父节点然后之间的链接的集合L将ADF表示为（S，L，C），=.10J. 阿尔坎塔拉湾Sá/理论计算机科学电子笔记344（2019）3SS⎧⎪⎨语句可以忽略，ADF可以表示为（S，C），其中L由（a，b）∈Li恢复，其中a出现在φb中。3.23-ADF的有值标签为了定义语句s上的ADFs的不同语义，我们将求助于容许标号的概念：定义3.2[容许标号]设D=（S，C）是ADF。一个三值标记是一个映射v：S→{in，out，undc}，它将值（in）、（out）或（undc）赋给每个语句s。根据Kleene的强三值逻辑[ 17 ]，标签将被扩展到为语句上的公式赋值有时，方便时，我们将把S上的标号v称为集合V ={s|s∈S且v（s）= in}<${<$s|s∈S且v（s）= out}。显然，如果既不是s∈S也不是<$s∈S，则v（s）=unec。一个三值标号v是Di∈S的容许标号，如果v（s）undc，则v（s）=v（s）。可接受的标签也可以描述如下：命题3.3Let D=（S，L，Cin）beanADF.给定一个表示v的值：S→{in，out，unec}，设M v={s|v（s）= in}{<$s|v（s）=out}。则对任意s∈S，v是Di ∈ N的容许标号• s∈Mv i <$Mv <$Lit（s）∈Cin;• <$s∈Mv i <$对于所有的MJ∈C，我们有MJMv。标签in、out和unec在信息排序≤i或真值排序≤t下是部分排序的：• undc≤iout和undc≤iin，而in和out是不可比较的。≤ i的预期含义是in和out比unec更能提供信息。对（{in，out，unec}，≤i）是完备交半格，即， V={in，out，unec}的每个非空子集具有最大下界（meet），并且每个有向子集B ∈ V（B的任何两个元素在B中具有上界）具有最小上界。 这个交，用Hi表示，定义如下：对于每个x，y ∈ {in，out，unec}，xHiy=inif x=y=inoutif x=y=out否则，• out≤tunec ≤tin.≤ t的预期含义是捕获程度真实性对（{in，out，unec}，≤t）是完全格，即，V ={in，out，unec}的每个非空子集都有一个最大的下界（meet），J. 阿尔坎塔拉湾Sá/理论计算机科学电子笔记344（2019）311⎧⎪⎨⎧⎪⎨由Ht表示的最小上界（join）和由Ht表示的最小上界（join）。对于每个x，y∈{in，out，unec}，we definexHty=如果x=y=inoutif x=outor y=out否则，xHty=inif x=inory=in outif x=y=out否则，将信息序≤i推广到S上的标号v1，v2：v1≤iv2i ≠v1（s）≤iv2（s）.设VS是环上所有三值标号的集合，S.对（Vs，≤i）是一个完备交半格，其中对所有s∈S，交运算Hi由v1Hiv2=v1（s）Hiv2（s）给出.对于每个s∈S，赋值v（s）=unec是这个半格的最小元。类似地，真值序≤t被推广到S上的标号v1，v2：v1≤tv2i∈v1（s）≤tv2（s），对所有s∈S.设VS是S上所有三值标号的集合。对（Vs，≤t）是一个完备格，其中该格的交运算Ht由v1Htv2=v1（s）Htv2（s）给出，对所有s∈S.此外，这个格的并运算Ht由v1Htv2=v1（s）Htv2（s）给出，对所有s∈S.对于每个s∈S，赋值v（s）=out是这个格的最小元素，而对于每个s∈S，赋值v（s）=in是它的最大元素。除了可接受的标号，完全标号是定义ADF语义的关键概念：定义3.4[完整的定义]LetD=（S，L，Ci n）bea nADF. S上的一个三值标号v是完备的，且v是≤t-极小标号使得对所有s∈S，v（s）= v（s）。这意味着如果v是adf D的完全标号，则不存在标号vJ使得vJ

下载后可阅读完整内容，剩余1页未读，立即下载