Possibilistic Logic Underlies Abstract Dialectical Frameworks

1 Introduction

Formal argumentation is one of the major approaches to knowledge representation. In the seminal paper [Dung, 1995], abstract argumentation frameworks were conceived of as directed graphs where nodes represent arguments and edges between these nodes represent attacks. So-called argumentation semantics determine which sets of arguments can be reasonably upheld together given such an argumentation graph. Various authors have remarked that other relations between arguments are worth consideration. E.g. in [Cayrol and Lagasquie-Schiex, 2005], bipolar argumentation frameworks are developed, where arguments can support as well as attack each other. The last decades saw a proliferation of such extensions of the original formalism of [Dung, 1995], and it is often hard to compare the resulting different dialects of the argumentation formalisms. To cope with the resulting multiplicity, [Brewka and Woltran, 2010; Brewka et al., 2013] introduced abstract dialectical argumentation that aims to unify these different dialects. Just like in [Dung, 1995], abstract dialectical frameworks (in short, ADFs) are directed graphs. In contradistinction to abstract argumentation frameworks, however, in ADFs, edges between nodes do not necessarily represent attacks but can encode any relationship between arguments. Such a generality is achieved by associating an acceptance condition with each argument, which is a Boolean formula in terms of the parents of the argument that expresses the conditions under which an argument can be accepted. As such, ADFs can capture all major extensions of abstract argumentation and offer a general framework for argumentation based inference.

The semantics of ADFs are based on three-valued interpretations assigning one of three truth values true (T), false (F), and undecided (U) to arguments. Even though in various papers on ADFs, Kleene's three-valued logic is mentioned [Brewka et al., 2013; Polberg et al., 2013; Linsbichler, 2014], the exact role of this logic, or for that matter any other monotonic three-valued logic, in ADFs is not clear. In this paper, we make an in-depth investigation of which three-valued logics underlie abstract dialectical frameworks, i.e. which threevalued logics allow to straightforwardly encode all semantical concepts used in ADFs. The entry point of this investigation is the notion of a model of an ADF, which was mentioned in [Brewka et al., 2013] but barely considered afterwards. In contradistinction to a claim made by [Brewka et al., 2013], the notion of a model of an ADF as based on Kleene's logic is ill-conceived. We then investigate on which logics a sound notion of model can be based, and we show that possibilistic logic [Dubois and Prade, 1998] is able to provide an adequate notion of model. In fact, this is the most conservative logic to provide such a notion. Possibilistic logic can therefore be viewed as a monotonic base logic underlying ADFs. Based on this observation, we characterize strong equivalence of ADFs and we generalize the semantics of ADFs to allow for possibility distributions as generalized three-valued interpretations as a basic semantic unit for ADFs. We illustrate the fruitfulness of this generalization by allowing for possibilistic constraints on arguments.

Outline of This Paper. We state all necessary preliminaries in Sec. 2 on propositional logic (Sec. 2.1), three-valued logics (Sec. 2.2), possibility theory (Sec.2.3) and ADFs (Sec. 2.4). In Sec. 3, we first recall and generalize the notion of model for an ADF (Sec. 3.1), and then show that possibilistic logic underlies ADFs in Section 3.2 and thereafter making a study of the relation between truth-functional three-valued logics and ADFs. Thereafter, we characterise strong equivalence for ADFs (Sec. 4) and generalize ADFs to possibilistic ADFs in Sec. 5. Related work is discussed in Sec. 6 and in Sec. 7 the paper is concluded.

2 Preliminaries

In this section the necessary preliminaries on propositional logic (Section 2.1), three-valued logics (Section 2.2), possibility theory (Section 2.3), and abstract dialectical argumentation (Section 2.4) are introduced.

2.1 Propositional Logic

For a set At of atoms let L(At) be the corresponding propositional language constructed using the usual connectives ∧ (and), ∨ (or), and ¬ (negation). A (classical) interpretation (also called possible world) ω for a propositional language L(At) is a function ω : At → {T, F}. Let Ω(At) denote the set of all interpretations for At. At(φ) is the set of all atoms used in a formula φ ∈ L(At). We simply write Ω if the set of atoms is implicitly given. An interpretation ω satisfies (or is a model of) an atom a ∈ At, denoted by ω |= a, if and only if ω(a) = T. The satisfaction relation |= is extended to formulas as usual. As an abbreviation we sometimes identify an interpretation ω with its complete conjunction, i. e., if a1, . . . , an ∈ At are those atoms that are assigned T by ω and an+1, . . . , am ∈ At are those propositions that are assigned F by ω we identify ω by a1 . . . anan+1 . . . am (or any permutation of this). For Φ ⊆ L(At) we also define ω |= Φ if and only if ω |= φ for every φ ∈ Φ. Define the set of models [X] = {ω ∈ Ω(At) | ω |= X} for every formula or set of formulas X. A (set of) formula(s) X1 entails another (set of) formula(s) X2, denoted by X1 ⊢PL X2, if [X1] ⊆ [X2].

2.2 Three-valued Logics

A 3-valued interpretation for a set of atoms At is a function v : At → {T, F,U}, which assigns to each atom in At either the value T (true, accepted), F (false, rejected), or U (unknown). The set of all three-valued interpretations for a set of atoms At is denoted by V(At). A 3-valued interpretation v can be extended to arbitrary propositional formulas over At using various logic systems L. Therefore, we will, given an interpretation v ∈ V(At), denote the truth-value assigned by a logic system L to a formula φ as vL (φ). 1 Thus, a logic system L is defined as a function assigning a truth value to every formula-interpretation-pair. The (three-valued) models of a formula φ ∈ L(At) for a logic system L are defined as V L (φ) = {v ∈ V(At) | vL (φ) = T}. 2 A consequence relation ⊢L⊆ ℘(L(At)) × L(At)) can then be defined as usual by setting Γ ⊢L φ iff V L (φ) ⊇ ⋂γ∈Γ V L (γ). Thus, a logic system L : V(At) × L(At) → {T, F, U} gives rise to a consequence relation which is most commonly associated with a logic, and we shall therefore often refer to logic systems as simply logics. We say a three-valued logic L is truth-functional for an n-ary connective ∗, if for every

1 Notice that vL (α) = vL′ (α) for any α ∈ At and any two threevalued logics L and L′ .

2 Notice that we assume that T is the only designated value. In e.g. paraconsistent logics, also U is taking as a second designated value. However, we stick to the orthodoxy for ADFs and interpret the third truth-value U as "unknown" and therefore not designated.

φ1, . . . , φn, φ′1 , . . . , φ′n ∈ L(At), vL (φi) = vL (φ′i ) for every 1 ≤ i ≤ n implies vL (∗(φ1, . . . , φn)) = vL (∗(φ′1 , . . . , φ′n )).

We also introduce a rather weak notion of relevance, which expresses that the truth-value of atoms not occurring in a formula φ should not have any impact on the truth-value assigned by L to that formula φ. In more detail, a logic L satisfies relevance iff for any φ ∈ L(At) and s ∈ At, if s ̸∈ At(φ) then for any v1, v2 ∈ V(At), v1(s′ ) = v2(s′ ) for any s′ ∈ At \ {s} implies vL 1 (φ) = vL 2 (φ).

We assume two commonly-used orders ≤i and ≤T over {T, F,U}. ≤i is obtained by making U the minimal element: U <i T and U <i F and this order is lifted pointwise as follows (given two valuations v,w over At): v ≤i w iff v(s) ≤i w(s) for every s ∈ At. ≤T is defined by F ≤T U ≤T T and can be lifted pointwise similarly.

It will sometimes prove useful to compare logics w.r.t. their conservativeness. In more detail, given two logics L and L′ , L is at least as conservative than L′ iff for every φ ∈ L(At) and every v ∈ V(At), vL (φ) ≤i vL′ (φ).

As an example, we consider Kleene's logic K.

Kleene's Logic K

A 3-valued interpretation v can be extended to arbitrary propositional formulas over At via Kleene semantics [Kleene et al., 1952]: vK(¬φ) = F iff vK(φ) = T, vK(¬φ) = T iff vK(φ) = F, and vK(¬φ) = U iff vK(φ) = U; vK(φ ∧ ψ) = T iff vK(φ) = vK(ψ) = T, vK(φ ∧ ψ) = F iff vK(φ) = F or vK(ψ) = F, and vK(φ ∧ ψ) = U otherwise; vK(φ ∨ ψ) = T iff vK(φ) = T or vK(ψ) = T, vK(φ ∨ ψ) = F iff vK(φ) = vK(ψ) = F, and vK(φ ∨ ψ) = U otherwise. Notice that Kleene's Logic K is truth-functional and satisfies semantic relevance.

2.3 Possibility Theory and Possibilistic Logic

In this subsection, we recall possibility theory and possibilistic logic. For more details, cf. [Dubois and Prade, 1993].

Preliminaries from Possibility Theory

Given a set of atoms At, a possibility distribution is a mapping π : Ω(At) → [0, 1]. We denote the set of possibility distributions over At by P(At). π is normal if there is some ω ∈ Ω(At) s.t. π(ω) = 1. Possibility distributions can be compared using the specificity order ≤s [Dubois and Prade, 1986], by stating that π ≤s π′ iff π(ω) ≤ π′ (ω) for every ω ∈ Ω(At) and any two possibility distributions π and π′ . A possibility distribution induces two important measures or degrees, the possibility degree Ππ : L(At) → [0, 1] and the necessity degree Nπ : L(At) → [0, 1]. They are defined as Ππ(φ) = sup{π(ω) | ω |= φ} and Nπ(φ) = 1 - Ππ(¬φ) = inf{1-π(ω) | ω |= ¬φ}.

Possibilistic Logic

In [Dubois and Prade, 1998], a three-valued logic inspired by possibility theory is presented which is based on defining lower and upper bounds of the evaluation of a formula using a possibility and a necessity measure. In more detail, given a three-valued interpretation v over At, the set of two-valued interpretations extending a valuation v is defined as [v]2 =

Definition 1. Given v ∈ V(At), the necessity measure Nv and the possibility measure Πv based on v are functions : Nv : L(At) → {T, F} and Πv : L(At) → {T, F}

We obtain the evaluation vposs : L(At) → {T, F, U} as: 4

Thus, vposs (φ) = T[F] means that φ is necessary true[false] (i.e. Nv(φ) = Πv(φ) = T[F]) whereas vposs (φ) = U means that φ is possibly true(Πv(φ) = T) but not necessarily so (Πv(φ) = F). Notice that poss is not truth-functional but satisfies relevance.

Example 1. Consider the interpretation v over {a, b} with v(a) = v(b) = U. Notice that Nv(a ∨ ¬a) = T and thus vposs (a ∨ ¬a) = T. However, Nv(a ∨ b) = Nv(¬a) = F and Πv(a ∨ b) = Πv(¬a) = T. Thus, even though v(a) = vposs (¬a) = v(b) = U, vposs (a ∨ b) ̸= vposs (a ∨ ¬a).

Remark 1. It can be seen that the possibility and necessity measures given a three-valued interpretation v defined in Definition 1 are particular cases of possibility and necessity measures given a possibility distribution π. In more detail, given an interpretation v, set πv(ω) = 1 if ω ∈ [v]2 and πv(ω) = 0 otherwise. Then Πv(φ) = T[F] iff Ππ(v) = 1[0] and Nv(φ) = T[F] iff Nπ(v) = 1[0]. We call the set of possibility distributions π : Ω(At) → {0, 1} the set of binary possibility distributions. Clearly, the set of normal binary possibility distributions coincides with {πv | v ∈ V(At)}.

2.4 Abstract Dialectical Frameworks

We recall technical details on ADFs [Brewka et al., 2013]. An ADF D is a tuple D = (At,L,C) where At is a set of statements, L ⊆ At × At is a set of links, and C = {Cs}s∈At is a set of total functions Cs : 2parD(s) → {T, F} for each s ∈ At with parD(s) = {s′ ∈ At | (s′ , s) ∈ L} (also called acceptance functions). An acceptance function Cs defines the cases when the statement s can be accepted (truth value T), depending on the acceptance status of its parents in D. By abuse of notation, we will often identify an acceptance function Cs by its equivalent acceptance condition which models the acceptable cases as a propositional formula. Notice that this is a purely notational convention, as any total function Cs as described above has an equivalent propositional formula and vice versa. D(At) denotes the set of all ADFs which can be formulated on the basis of At. In this paper, we restrict attention to ADFs with a finite set of statements At.

3 In [Ciucci et al., 2014], [v]2 is called an epistemic set and denoted by Ev.

4 Notice that this enumeration of cases is exhaustive, as for any v ∈ V(At) and any φ ∈ L(At), Nv(φ) ≤T Πv(φ).

Example 2. We consider the following ADF D1 = ({a, b, c}, L, C) with L = {(a, b), (b, a), (a, c), (b, c)} and: Ca = ¬b, Cb = ¬a, Cc = ¬a ∨ ¬b. Informally, the acceptance conditions can be read as "a is accepted if b is not accepted", "b is accepted if a is not accepted" and "c is accepted if a or b is not accepted".

An ADF D = (At,L,C) is interpreted through 3-valued interpretations V(At). The topic of this paper is which logics can be used to extend v to complex formulas in way that is suited for ADFs. Given a set of valuations V ⊆ V, ⊓iV (s) := v(s) if for every v′ ∈ V , v(s) = v′ (s) and ⊓iV (s) = U otherwise. The characteristic operator is defined by ΓD(v) : At → {T, F,U} where s ↦→ ⊓i{w(Cs) | w ∈ [v]2 }. Thus, ΓD(v) assigns to s the truth-value that all two-valued extensions of v assign to the condition Cs of s, if they agree on Cs, and U otherwise.

Definition 2. Let D = (At,L,C) be an ADF with v : At → {T, F,U} an interpretation v is: a 2-valued model iff v ∈ Ω(At) and v(s) = v(Cs) for every s ∈ At; admissible for D iff v ≤i ΓD(v); complete for D iff v = ΓD(v); preferred for D iff v is ≤i-maximal among the admissible interpretations for D; grounded for D iff v is ≤i-minimal among the complete interpretations for D. We denote by 2mod(D), Adm(D), Com(D), Prf(D), respectively Grn(D) the sets of 2-valued models and admissible, complete, preferred, respectively grounded interpretations of D.

Example 3 (Example 2 continued). The ADF of Example 2 has three complete models: v1, v2, v3 with: v1(a) = T, v1(b) = F, v1(c) = T; v2(a) = F, v2(b) = T, v2(c) = T; and v3(a) = U, v3(b) = U, v3(c) = U. v3 is grounded whereas v1 and v2 are preferred as well as 2-valued models.

3 Logics for ADFs

In this section, we ask the question of which three-valued logics qualify as a logic for ADFs. We first recall the notion of a model for ADFs as introduced by [Brewka et al., 2013] and show it is flawed, after which we define models parametrized to a logic. In section 3.2, we show that models parametrized to possibilistic logic gives rise to a plausible notion of model. Finally, in Section 3.3, we show that truth-functional logics that give rise to plausible notions of models are strictly less conservative than possibilistic logic.

3.1 ADF-Models

In [Brewka et al., 2013], models are defined as follows:

Definition 3. v ∈ V(At) is a model of an ADF D = (At,L,C) iff v(s) ̸= U implies v(s) = vK(Cs) for every s ∈ At.

[Brewka et al., 2013] claims that: "admissible interpretations (as well as the special cases complete and preferred interpretations to be defined now) are actually three-valued models." This claim is false:

Example 4. D = ({a, b}, L, C) with Ca = b ∨ ¬b and Cb = b. Consider the interpretation v with v(a) = T and v(b) = U. Since ⊓i[v]2 (b ∨ ¬b) = T and ⊓i[v]2 (b) = U, v is complete. However, vK(b ∨ ¬b) = U and thus v(a) ̸= vK(Ca), i.e. v is not a model.

Kleene's logic is only used in [Brewka et al., 2013] in the definition of models. For all of the other semantics, no reference to Kleene's logic is made. Instead, the ΓD-operator, which makes use of the completions [v]2 of an interpretation v, is used. Thus, models are the only concepts based on Kleene's logic in [Brewka et al., 2013]. We can accordingly generalize the concept of a model by parameterizing it with a logic L as follows:

Definition 4. Given a logic L : V(At) × L(At) → {T, F, U} and an ADF D, the set of L-models of D is ML (D) := {v ∈ V | for every s ∈ At if v(s) ̸= U then v(s) = vL (Cs)}.

A minimal condition on the set of models, inspired by the above quote from [Brewka et al., 2013], is that it includes all the admissible models:

Definition 5. A logic L is admissible-preserving if ML (D) ⊇ Adm(D).

Notice that any admissible-preserving logic L also guarantees that ML (D) ⊇ Sem(D) for any Sem ∈ {Prf , Grn, Com} since for any Sem-interpretation v, v is admissible.

The following result is a central first insight in the class of admissible-preserving logics:

Lemma 1. A logic L satisfying relevance is admissiblepreserving iff vL (φ) ≥i ⊓i[v]2 (φ) for every v ∈ V(At) and every φ ∈ L(At). 5

3.2 Possibilistic Logic Preserves Admissibility

In this section, we show that possibilistic logic poss underlies ADFs. We first make the following crucial observation, which show that for any interpretation, vposs is identical to ⊓i[v]2 , a central technical notion in the semantics of ADFs.

Lemma 2. For any v ∈ V(At) and φ ∈ L(At), ⊓i[v]2 (φ) = vposs (φ).

From this it follows that poss is admissible-preserving. Moreover, the set of models of an ADF under the logic poss collapses to the set of admissible interpretations:

Proposition 1. Possibilistic logic poss is admissiblepreserving, and for any ADF D, Mposs (D) = Adm(D).

Finally, we notice that the central ΓD-function, can be easily captured in possibilistic logic. Indeed, for any ADF D = (At,L,C), v ∈ V(At) and s ∈ At, ΓD(v)(s) = vposs (Cs) (this is immediate fromLemma 2). From this, it follows that, for any ADF D = (At,L,C), Com(D) = {v ∈ V(s) | v(s) = vposs (Cs) for every s ∈ At}.

Remark 2. We draw some consequences from the results above for the case of abstract argumentation frameworks (in short, AFs) [Dung, 1995]. An AF is a tuple (Args,⇝) where Args represents a set of arguments and ⇝⊆ Args × Args is an attack relation between arguments. We denote by A+ = {B ∈ Args : B ⇝ A} the set of attackers of A. It it shown in [Brewka et al., 2013] that AFs can be translated in ADFs as follows: given (Args,⇝), D(Args,⇝) = (Args,⇝,C) where CA = ∧B∈Args:B∈A+ ¬B. Notice that for any A ∈ Args, CA is a conjunction of negated literals.

5 In view of spatial restrictions, proofs can be found in the online appendix: http://mthimm.de/misc/Kleene w appendix.pdf.

For such formulas, Kleene's logic K and Poss coincide, i.e. vK(φ) = vPoss (φ) for any φ built up solely from negated atoms using ∨ and ∧ [Ciucci et al., 2014, Prop. 4.5]. Thus, for any AF (Args,⇝), v is complete iff v(A) = vK(CA) for every A ∈ Args. This was also mentioned implicitly in [Baumann and Heinrich, 2020], where the computational advantages of K were pointed out. Likewise, other classes of formulas for which (the non-truth-functional) poss is equivalent to (the truth-functional) K, is useful for classes of ADFs, such as bipolar ADFs [Brewka and Woltran, 2010].

3.3 Truth-Functional Logics

We show that for any admissible-preserving three-valued logic (truth-functional or otherwise), either the logic coincides with poss or the logic assigns a determinate truth-value T or F to at least one formula φ (relative to at least one interpretation v) to which poss assigns U. More formally, poss is the most conservative admissible-preserving logic.

Proposition 2. For any admissible preserving logic L, if there is a φ ∈ L(At) and a v ∈ V(At) s.t. vL (φ) ̸= vposs (φ), then L is strictly less conservative than poss.

It can be shown that any truth-functional admissiblepreserving logic is strictly less conservative than poss:

Proposition 3. No truth-functional logic L at least as conservative as poss is admissible-preserving.

4 Strong Equivalence

Strong equivalence [Lifschitz et al., 2001] is a notion of equivalence for non-monotonic formalisms which states that two knowledge bases (in this case, ADFs) are strongly equivalent if after the addition of any new information, the knowledge bases are equivalent (i.e. the semantics coincide). On the basis of the results in Section 3.2, we derive a characterisation of strong equivalence for ADFs.

In more detail, we show that strong equivalence for ADFs coincides with pairwise equivalence of acceptance conditions under classical logic. This is not surprising, as equivalence under classical logic coincides with possibilistic logic:

Proposition 4. For any φ, ψ ∈ L(At), V poss (φ) = V poss (ψ) iff φ and ψ are PL-equivalent (i.e. [φ] = [ψ]).

For many formalisms, addition of knowledge can be modelled using set-theoretic union. For ADFs, this is not feasible for several reasons. Firstly, combining two ADFs under settheoretic union does not result in a new ADF but rather in a set of ADFs. Secondly, one has to ensure that one models appropriately the combination of two ADFs with shared atoms. Consider e.g. two ADFs D1 = ({a},L1,C 1 a ) and D2 = ({a}, L2, C 2 a ) with C 1 a = a and C 2 a = ¬a. Clearly, the combination of ADFs has to be modelled on the basis of some logical operator combining C 1 a and C 2 a in a single new condition Ca. We specify a general model of addition of ADFs which allows for the combination of conditions using either disjunction or conjunction. Given a set of atoms At, an andor-assignment for At is a mapping ⊙ : At → {∧, ∨}. Intuitively, an and-or-assignment specifies for every atom s ∈ At whether conditions for s will be combined using ∧ or using ∨. We now define the combination of two ADFs:

Definition 6. Let D1 = (At1,L1,C1) and D2 = (At2, L2, C2) be two ADFs and ⊙ an and-or-assignment for At. Define D1 ⋓⊙ D2 = (At1 ∪ At2, L1 ∪ L2, C ⊙) with and C ⊙ = {C ⊙ s }s∈At, where: 6

Example 5. Consider D as in Example 2, D′ = ({a, b, d},L′ ,C) with Ca = b, Cb = d ∧ ¬a and Cd = ¬a, and ⊙(a) = ⊙(b) = ∧ and ⊙(c) = ⊙(d) = ∨. Then D1⋓⊙D2 = ({a, b, c, d}, L1∪L2, C ⊙) where: C ⊙ a = ¬b∧b, C ⊙ b = ¬a ∧ d ∧¬a, C ⊙ c = ¬a ∨¬b and C ⊙ d = ¬a.

We now define strong equivalence for ADFs as follows:

Definition 7. Two ADFs D1 = (At,L1,C1) and D2 = (At, L2, C2) are strongly equivalent under semantics Sem iff for any D ∈ D(At) and any and-or-assignment ⊙ for At, Sem(D1 ⋓⊙ D) = Sem(D2 ⋓⊙ D).

For all of the semantics considered in this paper, pairwise equivalence of conditions under classical logic is a sufficient and necessary condition for strong equivalence:

Proposition 5. Let some Sem ∈ {Adm, Com, Prf, Grn} and two ADFs D1 = (At,L1,C1) and D2 = (At,L2,C2) be given. Then: for every s ∈ At, C s 1 ≡PL C s 2 iff D1 and D2 are strongly equivalent under semantics Sem.

We notice that when considering abstract argumentation frameworks or logic programs, our results do not apply without further restrictions. Indeed, addition of an argument as e. g. studied in [Oikarinen and Woltran, 2011; Gaggl and Strass, 2014] can be represented as a combination of the two representative AFs where ⊙ assigns ∧ to any atom. This is a weaker notion of addition of ADFs, in the sense that our notion properly subsumes the notion of addition used by [Oikarinen and Woltran, 2011; Gaggl and Strass, 2014]. Therefore, our notion of strong equivalence is also stronger, and thus our results do not subsume the results of e. g. [Oikarinen and Woltran, 2011]. The study of weaker notions of strong equivalence is left for future work.

5 ADFs in Possibility Theory

We now look further into the perspective offered by possibility theory on ADFs. In more detail, based on the results from Sec. 3.2, we unpack the semantics of ADFs in possibility theory. We first show how all semantic concepts from ADFs correspond to notions from possibility theory. We use these correspondences to define possibilistic ADFs.

5.1 ADFs Interpreted in Possibility Theory

In this section we interpret the semantics of ADFs in possibility theory, and generalize them to possibility distributions.

We start by looking closer at the information ordering. Recall that one interpretation v is less or equally informative than v′ iff v′ assigns the same determinate truth-value to every atom s for which v assigns a determinate truthvalue. It turns out that this is equivalent to requiring that: Nv(s) ≤ Nv′(s) and Πv(s) ≥ Πv′(s) for every s ∈ At, or, equivalently:

6 Our notion of composition of ADFs is clearly a generalization of that of [Gaggl and Strass, 2014].

We now derive that ≤s and ≤i are each-others converses when we look at three-valued interpretations (or equivalently, normal binary possibility distributions): 7

Proposition 6. For any interpretations v, v′ ∈ V(At), v ≤i v′ iff πv′ ≤s πv.

Based on Fact 1, we can define the information-ordering ≤i over the set of possibility distributions P(At) as follows: π ≤i π′ iff Ππ(s) ≥ Ππ′(s) and Ππ(s) ≥ Ππ′(s) for every s ∈ At. In other words, more informative possibility distributions assign lower possibility measures to literals. This might seem at first counter-intuitive, but when rephrased in terms of the dual necessity measures, this becomes clearer:

Proposition 6 only generalizes to the setting of non-binary possibility distributions in one direction: indeed ≤i as defined over possibility distributions is a generalization of the reverse specificity-ordering:

The following examples shows that the reverse direction of Proposition 6 does not generalize from V(At) to P(At).

Example 6. Consider π, π′ ∈ P({a, b}), where π(ab) = π(ab) = π(ab) = 1 and π(ab) = 0.1 whereas π′ (ab) = π′ (ab) = π′ (a b) = 1 and π(ab) = 0.1. Notice that π ≤i π′ and π′ ≤i π. However, π and π′ are ≤s incomparable, as π(ab) ≤ π′ (ab) and π(ab) ≤ π′ (ab).

We now characterize admissible and complete interpretations in terms of possibility and necessity measures. Admissible interpretations correspond to possibility distributions for which every node s has: (1) a degree of necessity equal or less than the degree of necessity of the corresponding condition Cs; and (2) a degree of possibility equal or higher than the degree of possibility of the corresponding condition Cs. In other words, the interval formed by the degree of possibility and necessity of Cs is a sub-interval of the correspondent interval for s. Completeness strengthens this by requiring the necessity, respectively the possibility degree, of a node to be equal to the corresponding degree of its condition.

Proposition 7. Given an ADF D = (At,L,C) and v ∈ V(At): (1) v is admissible iff for every s ∈ At, Nv(s) ≤ Nv(Cs) and Πv(s) ≥ Πv(Cs). (2) v is complete iff for every s ∈ At, Nv(s) = Nv(Cs) and Πv(s) = Πv(Cs).

We generalize ADF-semantics to possibility distributions:

Definition 8. Given an ADF D = (At,L,C) and a normal possibility distribution π ∈ P(At): π is admissible (for D) iff Ππ(¬s) ≥ Ππ(¬Cs) and Ππ(s) ≥ Ππ(Cs) for every s ∈ At; π is complete (for D) iff Ππ(¬s) = Ππ(¬Cs) and Ππ(s) =

7 Recall that ≤s is defined in Section 2.3.

Ππ(Cs) for every s ∈ At; π is grounded (for D) iff π is a ≤iminimal complete possibility distribution; π is preferred (for D) iff π is a ≤i-maximal admissible possibility distribution.

These semantics satisfy basic argumentative properties:

Proposition 8. Given an ADF D = (At,L,C): (1) there exists a unique grounded possibility distribution for π; (2) any preferred possibility distribution for π is complete.

The above proposition is shown by defining a function GD : P(At) →P(At) that returns, for a possibility distribution π, a new possibility distribution GD(π) s.t. for any s ∈ At, ΠGD (π)(s) = Ππ(Cs) and ΠGD (π)(¬s) = Ππ(¬Cs). It can be shown that this GD-function is a faithful generalization of the ΓD-operator.

Thus, the information order and the semantics of ADFs can be straightforwardly rephrased using possibility measures Π and necessity measures N. On the basis of this interpretation, the semantics for ADFs were generalized from threevalued interpretations - which can be viewed as binary possibility distributions) - to arbitrary possibility distributions, and shown to satisfy basic properties.

5.2 Possibilistic ADFs

We now introduce possibilistic ADFs as a a quantitative extension of ADFs, which can assign a degree of plausibility to the acceptance of nodes. This allows, among others, the incorporation of possibilistic constraints on nodes.

Definition 9. An ADF with possibilistic constraints (pADF) is a tuple D = (At, L, C, ρ) where (At, L, C) is an ADF and ρ : At → [0, 1].

The intuitive interpretation of ρS is that they form an upper limit on the possibility of the nodes of an pADF.

Definition 10. Given a pADF D = ((At, L, C, ρ), a normal possibility distribution π : S → [0, 1] is: p-permissible (for D) iff Ππ(s) ≤ ρ(s) for every s ∈ At; p-admissible (for D) iff it is admissible and p-permissible for D; p-complete (for D) iff it is complete and p-permissible for D; p-grounded (for D) if it is ≤i-least specific p-complete interpretation for D; p-preferred (for D) if it is a ≤i-maximal p-admissible interpretation for D.

Example 7. Let D = ({a, b, c},L, {Ca = ¬b ∧ ¬c,Cb = ¬a,Cc = c}, {ρ(a) = 1, ρ(b) = 0.8, ρ(c) = 0.4}). Consider now: ω π1 π2 ω π1 π2 ω π1 π2 ω π1 π2 abc 0.4 0 abc 0.8 0 abc 0.4 0 abc 1 1 abc 0.4 0 abc 0.8 0 abc 0.4 0 abc 0.8 0 π1 is p-grounded and π2 is p-preferred for D. Notice that the grounded possibility distribution for D = ({s, c},L, {Cs = ¬c,Cc = ¬s}) is not p-complete for D. Indeed, the grounded extension for D is given by π3(ω) = 1 for every ω ∈ Ω({a, b, c}). π3 is not p-complete since Ππ3 (b) = 1 > ρ(b) = 0.8.

We remark here that a unique p-grounded extension might not exist for a given pADF. Furthermore, there might be pADFs for which there do not exist even p-admissible extensions. If we change e.g. ρ(a) = 0.9 in the pADF from Ex. 7, no normal p-admissible possibility distribution exists.

A pADF for which no p-admissible extensions exist can be seen as faultily specified model. This is not unlike the requirements formulated for epistemic approaches to probablistic argumentation [Hunter and Thimm, 2017].

6 RelatedWork

In this paper, we have investigated three-valued monotonic logics underlying ADFs. To the best of our knowledge, this work is the first systematic such study, but some works contain some similar results or questions. In [Baumann and Heinrich, 2020], it is shown that there is no truth-functional threevalued logic L s.t. for every v ∈ V(At) and every φ ∈ L(At), vL (φ) = ⊓i[v]2 (φ). Lemma 1 generalizes this result. Our paper continues where [Baumann and Heinrich, 2020] stopped, since we show which truth-functional logics are admissiblepreserving, and there is a monotonic three-valued logic, poss, for which vposs (φ) = ⊓i[v]2 (φ) for every v ∈ V(At) and every φ ∈ L(At). In [Heyninck and Kern-Isberner, 2020] ADFs are translated in (auto)epistemic logic, related to poss [Ciucci and Dubois, 2012].

With respect to the possibilistic ADFs introduced in this paper, we make a comparison with weighted ADFs [Brewka et al., 2018]. Weighted ADFs generalize ADFs by allowing interpretations which map nodes to elements of VU, which is a complete partial order constructed on the basis of a chosen set V of values combined with the U-value, which forms the ≤i-least element under the information order over VU. This is a very general model of weighted argumentation, which possibilistic ADFs cannot lay claim to. On the other hand, in possibilistic ADFs, there is no need to postulate an additional value U, since it arises naturally from the possiblistic semantics as a discrepancy between the necessity measure N and the possibility measure Π. [Wu et al., 2016] defines fuzzy argumentation frameworks, where arguments and attacks are assigned a degree of belief. These semantics are dependent on the syntactical structure of argumentation frameworks. Furthermore, possibilistic logic and fuzzy logic are far from equivalent, in particular w.r.t. truthfunctionality. For example, a fuzzy degree of belief in two conjuncts allows to determine the degree of belief in a conjunction, in contradistinction to possibility theory. Other approaches to possibilistic argumentation [Alsinet et al., 2008; Nieves and Confalonieri, 2011] make use of non-Dungean semantics, and therefore less related.

7 Conclusion

The central result of this paper is that possibilistic logic is the most conservative admissible-preserving logic, and allows to straightforwardly codify all central semantical notions from ADFs. Furthermore, we applied this insight by (1) characterising strong equivalence and (2) proposing possibilistic ADFs, which allow for quantitative reasoning in ADFs in a way that faithfully generalizes (qualitative) reasoning in ADFs. We believe that the connection between possibility theory on the one hand, and (abstract) argumentation and ADFs on the other hand, will provide a useful tool for work argumentation by transferring results and insights from possibility theory in argumentation.

Acknowledgements

The research reported here was supported by the Deutsche Forschungsgemeinschaft under grant KE 1413/11-1. The work of Jesse Heyninck was partially supported by Fonds Wetenschappelijk Onderzoek - Vlaanderen (project G0B2221N). We thank Jonas Schumacher for comments.