Rationality and maximal consistent sets for a&nbsp;fragment of ASPIC+ without undercut

Heyninck, Jesse; Straßer, Christian

doi:10.3233/AAC-200903

Rationality and maximal consistent sets for a fragment of ASPIC+ without undercut

Issue title: Argument strength

Guest editors: Gabriella Pigozzi and Srdjan Vesic

Article type: Research Article

Authors: Heyninck, Jesse^a | Straßer, Christian^{b; *}

Affiliations: [a] Department of Computer Science, Technische Universität Dortmund, Germany. E-mail: [email protected] | [b] Institute for Philosophy II, Ruhr-Universität Bochum, Germany. E-mail: [email protected]

Correspondence: [*] Corresponding author. E-mail: [email protected].

Keywords: Rationality postulates, ASPIC, maximal consistent sets

DOI: 10.3233/AAC-200903

Journal: Argument & Computation, vol. 12, no. 1, pp. 3-47, 2021

Published: 15 February 2021

Get PDF

Abstract

Structured argumentation formalisms, such as ASPIC+, offer a formal model of defeasible reasoning. Usually such formalisms are highly parametrized and modular in order to provide a unifying framework in which different forms of reasoning can be expressed. This generality comes at the price that, in their most general form, formalisms such as ASPIC+ do not satisfy important rationality postulates, such as non-interference. Similarly, links to other forms of knowledge representation, such as reasoning with maximal consistent sets of rules, are insufficiently studied for ASPIC+ although such links have been established for other, less complex forms of structured argumentation where defeasible rules are absent.

Clearly, for a formal model of defeasible reasoning it is important to understand for which range of parameters the formalism (a) displays a behavior that adheres to common standards of consistency, logical closure and logical relevance and (b) can be adequately described in terms of other well-known forms of knowledge representation.

In this paper we answer this question positively for a fragment of ASPIC+ without the attack form undercut by showing that it satisfies all standard rationality postulates of structured argumentation under stable and preferred semantics and is adequate for reasoning with maximal consistent sets of defeasible rules. The study is general in that we do not impose any other requirements on the strict rules than to be contrapositable and propositional and in that we also consider priorities among defeasible rules, as long as they are ordered by a total preorder and lifted by weakest link. In this way we generalize previous similar results for other structured argumentation frameworks and so shed further light on the close relations between assumption-based argumentation and ASPIC+.

1.Introduction

Structured argumentation is a family of formal approaches for the handling of defeasible and potentially inconsistent information. For this, many models of structured argumentation distinguish between strict and defeasible inference rules. Defeasible rules guarantee the truth of their conclusion only provisionally: from the antecedents of the rules we can infer their conclusion unless and until we encounter convincing counter-arguments. These defeasible rules can come in varying strengths. For example, in an epistemic reasoning context considerations of plausibility, typicality or likelihood may play a role in determining the strength of a defeasible conditional. In contexts of normative reasoning (such as legal or moral reasoning), the strength of defeasible conditionals may be determined by deontic or legal urgency (e.g., in view of the authority which issued them or their specificity). Strict rules, in contrast, are beyond doubt and therefore considered maximally strong: the truth of the antecedents is carried over to the conclusion.

Arguments constructed on the basis of a combination of strict and defeasible rules can be in conflict with one another. For example, one argument may conclude the contrary of the conclusion of another argument or may conclude that the application of a defeasible rule in another argument is not warranted in the circumstances under consideration. To represent and resolve such conflicts, a formal argumentation framework is constructed on the basis of the strict and defeasible rules. Argumentative attacks represent conflicts between arguments. Preferences over the defeasible rules used in constructing the arguments can be used to resolve conflicts between assumptions by turning attacks into defeats. There are several design choices available when specifying how to construct such an argumentation framework, which often have a severe impact on the inferential behaviour of the resulting formalism. In this paper, we study one specific formalism known as ASPIC+. ASPIC+ is a well-established formalism which has been applied to e.g. decision-making [52], risk-assessment [55] and legal reasoning [54] and provides argumentative characterisations of prioritised default logic [16] (cf. [59,60]) and preferred subtheories [15] (cf. [50]).

Example 1.

Nicki and Mary will go to a garden party (g) and were asked to bring a potato-salad.1 1 In Nicki’s opinion a good potato-salad has pickles in it (g⇒1p) but Mary has an allergy to pickles (g⇒2¬p). Since an allergy for pickles has precedence over a preference in taste, the rule based on the former is stronger than the rule based on the latter (which we express in the formal language by having a subscript 2 for g⇒2¬p and a subscript 1 for g⇒1p). Mary thinks they should bring a bottle of Quadruple beer as a gift for the host (l⇒1q) since the host likes beers (l). Since this is a very strong beer, in most cases, when handing over the gift, a warning should be issued (q⇒1w). However, the host is a beer connoisseur (b), and thus the previous rule of thumb does not apply (b⇒1¬n(q⇒1w)).

In [1 ,19] several rationality postulates have been proposed, which can be seen as minimal requirements any well-behaved structured argumentation formalism should fulfill. These requirements all have to do with the basic role of formal argumentation as a formalism for handling (logical) conflicts. For instance, we can require that the output of the formalism is logically consistent: it should not be possible to derive both a formula and its contrary. As an illustration, in Example 1 no structured argumentation formalism should output both that pickles should be added (p) and kept out (¬p) of the salad. In [53], it was proven that ASPIC+ satisfies the rationality postulates of closure and consistency given some basic restrictions on the strict rule base.

However, as has been observed in [57], ASPIC+ does not satisfy other standards such as Crash-Resistance and Non-Interference. Ideally, a reasoning system should not lose consequences if irrelevant information is added to the knowledge base. In Example 1, the fact that Mary and Nicki bring a beer (q) and warn the party host about the strength of the beer (w) should not be influenced by any considerations of what to put in the potato-salad (i.e. by adding {g⇒1p,g⇒2¬p} to the knowledge base). As demonstrated in [57] for ASPIC+, the lack of Crash-Resistance and Non-Interference is especially threatening if the underlying strict rules are domain-independent. This is typically the case if the strict rules are induced by an underlying logic such as classical logic (in short, CL).2 2 Given an inconsistent knowledge base and strict rules such as logical explosion, for any formula an argument with a contrary conclusion can be constructed.

So far, there are not many results that establish Crash-Resistance and Non-Interference for ASPIC+ and related systems.3 3 Some examples are:

[57] established non-interference for complete semantics for ASPIC-lite, a sub-system of ASPIC+ where priorities over defeasible rules are not taken into account and inconsistent arguments are filtered out. The latter is arguably a limitation, since checking consistency can be computationally unfeasible and since the inconsistency is typically demonstrated dialectically in real-word argumentation [27].
In [36] a system with restricted rebut is introduced that avoids logical explosion by using a sub-classical logic as a base logic. For any completeness-based semantics a weakened version of Non-Interference and Closure are shown for total pre-orders expressing priority relations between the defeasible rules. For multi-extension semantics a counter-example for full non-interference is provided.
Recently ASPIC⊖ [11,39,41] has been proposed. It is the first member of the ASPIC-family that satisfies all standard rationality postulates (including non-interference and crash-resistance) even when taking into account preorders over defeasible rules. ASPIC⊖ does not require filtering out inconsistent arguments. However, the rationality postulates hold only for the single-state grounded semantics, as it makes use of the attack form of unrestricted rebut, which violates the rationality postulates of closure and indirect consistency for multi-extension semantics such as the preferred and stable semantics (see e.g. [18, Example 2]).

In conclusion, there have been some recent steps towards rational, prioritised structured argumentation with defeasible rules, but it is still an open question whether it is possible to obtain a formalism that satisfies the four rationality postulates for a multi-state semantics and prioritised defeasible rules. In this paper, we show that this is possible given some basic restrictions on the language of the knowledge base, using the weakest link lifting for a fragment of ASPIC+. In more detail, we consider ASPIC+ without undercut, defeasible premises and undermining attacks and we assume the preference order over the defeasible rules to be total. We restrict our attention to propositional instantiations. As such, this paper presents an important move towards a full solution to an open problem mentioned both in [51] and [18]. Furthermore, when these restrictions are met, it is not necessary to filter out inconsistent arguments, thus bringing the formalism closer to dialectical practices.

Moreover, we demonstrate that when these resctrictions are met, the stable and the preferred semantics coincide. This result is interesting from a computational perspective, since it means we can now use the computationally less demanding proof theories for admissible semantics to show membership of a stable extension [31].

For several systems of structured argumentation characterizations of the extensions of frameworks under some argumentation semantics in terms of maximal consistent sets of premises have been obtained (see [6] for an overview). Such results are useful since they provide a link between argumentation and knowledge representation and they provide a basic sanity check on the behavior of an argumentation system. For systems with defeasible rules, such as ASPIC+, such results have not been obtained. One difficulty is the question of how to define consistent subsets of the premises in such contexts. In this contribution we will generalize approaches that have been proposed in the context of knowledge bases with strict and defeasible assumptions such as default assumptions [47] and ABA [12] to systems with defeasible inference rules such as ASPIC+. In this way we obtain further insights into the relation of ASPIC+ to other argumentation formalisms, thus tackling another open question formulated in [51].

Outline of this paper: In Section 2, we present the necessary preliminaries on the structured argumentation formalism ASPIC+. In Section 3 we review the rationality postulates for structured argumentation. Expert readers in formal argumentation may skip these sections and jump directly to Section 4, which contains the main contributions of this paper, namely: when considering (a fragment of) ASPIC+ without undercut attacks, stable and preferred extensions coincide (Section 4.1), all four rationality postulates are satisfied for the stable and preferred semantics (Section 4.2) and central argumentation semantics are characterized in terms of maximally consistent sets of defeasible rules (Section 4.3). In Section 5 we discuss related work. In the final Section 6 we make some concluding remarks, pointing out a connection with assumption-based argumentation and setting out avenues for further work.

2.Structured argumentation

In structured argumentation, information is given in the form of a knowledge base or argumentation system. In ASPIC+, such an argumentation system is built up from a formal language L, which can be used to formulate strict rules S of the form ϕ1,…,ϕn→ϕ, defeasible rules D of the form ϕ1,…,ϕn⇒ϕ and strict premises K. Strict rules are deductive in the sense that the truth of their antecedents ϕ1,…,ϕn necessarily implies the truth of their consequent ϕ, while defeasible rules allow for exceptions. In ASPIC+ arguments are modelled as derivations based on strict and defeasible rules and a set of premises.

Strict rules can have several classes of interesting instantiations. A first option is to use some logic L with an associated consequence relation ⊢L and require that ϕ1,…,ϕn→ϕ∈S iff {ϕ1,…,ϕn}⊢LA. Another option is to use what are often called domain dependent rules, as they are known from e.g. logic programming.

Unlike strict rules, a defeasible rule warrants the truth of its conclusion only provisionally: its application can be retracted in case counter-arguments are encountered. We assume that the defeasible rules D come with a naming function n:D→L. Furthermore, conflicts between elements of the language can be specified using a contrariness function ϕ‾.4 4 Finally, the user can specify preferences over the defeasible rules using a preorder ⩽⊆D×D. Formally, such an argumentation system is defined as follows:

Definition 1

Definition 1(Argumentation System).

An Argumentation System (AS) is a tuple (L,S,D,K,n,A‾,⩽) consisting of:

(1) a formal language L based on a set of atoms A;
(2) a set of strict rules S of the form ϕ1,…,ϕn→ϕ (where ϕ1,…,ϕn,ϕ∈L);
(3) a set of defeasible rules D of the form ϕ1,…,ϕn⇒ϕ (where ϕ1,…,ϕn,ϕ∈L);
(4) an S-consistent5 5 set of strict premises K⊆L;
(5) a naming function for the defeasible rules n:D→L;
(6) a contrariness function A‾ from L to 2L;
(7) a total preorder6 6 ⩽ over D.

Given a rule r=ϕ1,…,ϕn→ϕ resp. r=ϕ1,…,ϕn⇒ϕ, ϕ1,…,ϕn are called the antecedents and ϕ is called the consequent or head. We write body(r)={ϕ1,…,ϕn} and head(r)=ϕ. Where R is a set of rules we write body[R] for the set {body(r)∣r∈R} and head[R] for the set {head(r)∣r∈R}.

The naming function n will be important when considering the attack form undercut and the preorder ⩽ is important when considering different strengths of arguments (see Definition 4). Below we will sometimes consider argumentation systems without undercut and/or without priorities, in which case we omit n and/or ⩽ from the characterizing tuple.7 7

Example 2

Example 2(Example 1 continued).

To illustrate the above definitions, we illustrate how to capture the information from Example 1 in an argumentation system AS2=(L2,SCL,D2,K2,n2,A‾,⩽2) where:8 8

L2 is the closure of the set of atoms {g,p,q,l,w,b,α,β,γ,δ,ϵ} and the constants ⊥ and ⊤ under {¬,∧,∨};
SCL is the set of strict rules capturing classical logic CL as follows: ϕ1,…,ϕn→ϕ∈SCL iff {ϕ1,…,ϕn}⊢CLϕ and ϕ,ϕ1,…,ϕn∈L2;9 9
D2={g⇒1p;g⇒2¬p;l⇒1q;q⇒1w;b⇒1¬δ};
K2={g,b,l};
n2(g⇒1p)=α, n2(g⇒2¬p)=β, n2(l⇒1q)=γ, n2(q⇒1w)=δ, n2(b⇒1¬δ)=ϵ.
ϕ∈ψ‾ iff ϕ=¬ψ or ψ=¬ϕ or ϕ=⊥;10 10
ϕ⇒iψ⩽2ϕ′⇒jψ′ iff i⩽j (where ⩽ is the canonical order over N).

2.1.Argument construction

In structured argumentation systems like ASPIC+, acceptable arguments are determined using the semantics of abstract argumentation. In order to apply these semantics, an argumentation graph has to be constructed on the basis of the argumentation system. This is done by building arguments using premises and inference rules and by specifying defeats between these arguments on the basis of the contrariness function and the preference order of the argumentation system. We first define how arguments are constructed.11 11

Definition 2.

Let AS=(L,S,D,K,n,A‾,⩽) be an argumentation system. An argument a is one of the following:

(1) a=⟨ϕ⟩ where ϕ∈K
Conc(a)=ϕ, Sub(a)={a}, D(a)=∅;12 12
(2) a=⟨a1,…,an→ϕ⟩ where a1,…,an (with n⩾0) are arguments such that there is a strict rule Conc(a1),…,Conc(an)→ϕ∈S
Conc(a)=ϕ, Sub(a)={a}∪⋃i=1nSub(ai), and D(a)=⋃i=1nD(ai);
(3) a=⟨a1,…,an⇒ϕ⟩ where a1,…,an (with n⩾0) are arguments such that there is a defeasible rule Conc(a1),…,Conc(an)⇒ϕ∈D
Conc(a)=ϕ, Sub(a)={a}∪⋃i=1nSub(ai), and
D(a)={Conc(a1),…,Conc(an)⇒ϕ}∪⋃i=1nD(ai).

We lift the above notation as expected. E.g., where A is a set of arguments, Conc[A]={Conc(a)∣a∈A} and D[A]={D(a)∣a∈A}.

By Arg(AS) we denote the set of arguments that can be built from AS. An argument a will be called defeasible if D(a)≠∅ and strict otherwise.

Example 3

Example 3(Example 2 continued).

The following arguments (among others) can be constructed from AS2:

a1:⟨g⟩a1′:⟨l⟩a2:⟨a1⇒1p⟩a3:⟨a1⇒2¬p⟩a4:⟨a1′⇒1q⟩a5:⟨a4⇒1w⟩a6:⟨b⟩a7:a6⇒1¬δa8:⟨a2,a3→⊥⟩a9:⟨a4,a5→q∧w⟩

a1, a1′, and a6 are premise arguments. a2 is obtained by applying the defeasible rule g⇒1p to the argument a1. a3, a4 and a7 are obtained in a similar way. a5 is obtained by applying the rule q⇒1w to the defeasible rule argument a4 and thus is an example of how defeasible rules can be chained. a8 and a9 are two examples of the application of a strict rule: ex falso quodlibet in the case of a8 and conjunction introduction in the case of a9.

2.2.Attack and defeat

In ASPIC+ there are two ways in which arguments can conflict. The first type of attack, called rebut, is when an argument a concludes the contrary of the conclusion of an argument b. The second attack type is called undercut and occurs when an argument concludes that the application of a defeasible rule is not appropriate in the context at hand. More formally, an undercut from a on b occurs when a has as a conclusion n(r)‾ where r∈D(b).

Definition 3.

Let a,b∈Arg(AS) and b=b1…,bn⇒B:

a rebuts b iff Conc(a)∈Conc(b)‾;
a undercuts b iff Conc(a)∈n(Conc(b1)…,Conc(bn)⇒B)‾.

a attacks b iff a,b∈Arg(AS) and a rebuts13 13 b or a undercuts b.

To determine which rebuts result in a defeat we take into account the priorities over the rules used in constructing the arguments involved in the attack. For this we have to lift the order ⩽ over the defeasible rules D to a preference order ⪯ over the set of arguments Arg(AS) constructed on the basis of D. We will use the weakest link lifting (see e.g. [50]) according to which an argument is as strong as its weakest defeasible elements.

Exactly how the preference order ⪯ is taken into account when determining whether an attack is successful and results in a defeat depends on the nature of the attack that is being considered. When it comes to rebuttal, we follow [50] in assuming that a rebutting attack by argument a on argument b leads to defeat if a is not strictly weaker than b. Since in this paper we only work with total orders, this is equivalent to requiring that a is at least as strong as b. Concerning undercuts, the situation is a bit more complicated, as there is some debate as to what it means for an undercutter to be sufficiently strong for the attack to succeed. Are undercutting attacks successful independently of the strength of the arguments involved? Or should an undercutting attack by a on b lead to defeat only in case a is not strictly weaker (or even strictly stronger) than b? [50] works with a preference-independent notion of undercutting defeat according to which undercutting attacks always give rise to defeat. Their motivation, however, has been questioned by [10].14 14 In Definition 5 we follow what is the most frequent approach in the ASPIC-family, namely to assume that undercutting attacks are preference-independent. However, since our main results concern ASPIC-frameworks without undercut this choice is insignificant for this study.

Definition 4.

Where a,b∈Arg(AS), a⪯b iff there is an r∈D(a) such that for every r′∈D(b), r⩽r′.

We are now ready to define defeat based on the weakest link lifting:

Definition 5.

Where a,b∈Arg(AS), a defeats b (in symbols: (a,b)∈⇝(AS)) iff:15 15

a rebuts some b′∈Sub(b) and b′⪯a;16 16
a undercuts some b′∈Sub(b).

We define the argumentation framework based on an argumentation system AS as (Arg(AS),⇝(AS)).

Example 4

Example 4(Example 3 continued).

For the argumentation system AS2, we have the following argumentation framework:

Given an argumentation framework consisting of arguments and defeats between these arguments, Dung [29] provides various semantics for determining the acceptability status of an argument in the framework, which we introduce in the next section.

2.3.Argumentation semantics

A Dung-style abstract argumentation framework (in short, AF) is a pair (Arg,⇝) where Arg is a set of arguments and ⇝⊆Arg×Arg is a binary relation of attack. Relative to an AF, Dung defines a number of extensions – subsets of Arg – on the basis of which we can evaluate the arguments in Arg.

Definition 6

Definition 6(Extensions).

Let (Arg,⇝) be an argumentation framework and E⊆Arg:

E⇝a iff there is some b∈E such that b⇝a.
E is conflict-free iff there are no a,b∈E for which a⇝b.
E defends an argument a iff for every b∈Arg such that b⇝a then E⇝b.
E is a complete extension iff it is conflict-free and a∈E iff E defends a.
E is a preferred extension iff it is a set inclusion maximal complete extension.
E is the grounded extension iff it is the set inclusion minimal complete extension.17 17
E is a stable extension iff it is conflict-free and for every b∈Arg∖E, E⇝b.

We will use pref((Arg,⇝)) and stab((Arg,⇝)) to denote the set of preferred respectively stable extensions of an argumentation framework (Arg,⇝) and groun((Arg,⇝)) to denote its grounded extension. Given an argumentation system AS, we will also use pref(AS), stab(AS) resp. groun(AS) to denote pref((Arg(AS),⇝(AS))), stab((Arg(AS),⇝(AS))) resp. groun(((Arg(AS),⇝(AS))).

Example 5

Example 5(Example 4 continued).

The argumentation framework (Arg(AS2),⇝(AS2)) has as grounded extension that contains a1, a1′, a3, a4, a6, a7 but not a2, a5, a8 and a9. This extension is also the unique preferred extension. It is also stable as it attacks a2, a5, a8, a9, etc.

Based on these argumentation semantics, we define consequence relations:

Definition 7.

Where AF=(Arg(AS),⇝(AS)) and sem∈{pref,stab}:

AS∣∼sem∪ϕ if for some E∈sem(AS), there is some a∈E with Conc(a)=ϕ.
AS∣∼sem∩ϕ if for every E∈sem(AS), there is some a∈E with Conc(a)=ϕ.
AS∣∼grounϕ if there is some a∈groun(AS) with Conc(a)=ϕ.

3.Rationality postulates

The inferential behaviour of structured argumentation formalisms is often studied using so-called rationality postulates [19,20]. These properties ensure that argumentation-based inferences make sense from a logical and intuitive point of view.

In order to handle conflicts adequately, a minimal constraint on structured argumentation systems is that they do not allow for direct logical conflicts in any extension (selected according to some semantics sem). In other words, any extension should be consistent, i.e. there should be no two arguments a and b in the extension such that Conc(a)∈Conc(b)‾.

Postulate 1

Postulate 1(Direct Consistency).

sem satisfies Direct Consistency for an argumentation system AS if there is no E∈sem(AS) such that there are some a,b∈E for which Conc(a)∈Conc(b)‾.

The related (but stronger) postulate of indirect consistency requires not only that an extension does not contain two arguments that are in direct conflict, but requires that no conflict is derivable using the strict rules S from the conclusions of the arguments in the extension. In other words, indirect consistency requires that the set of conclusions of arguments in a given extension is consistent when closed under the strict rule base S.

Definition 8

Definition 8(R-proof).

Let Γ∪{ϕ} be a set of L-formulas and R a set of inference rules on L. An R-proof P of ϕ from Γ is a sequence ϕ1,…,ϕn where for each 1⩽i⩽n, ϕi∈Γ or ϕi is the head of a rule in R whose body only contains formulas in {ϕ1,…,ϕi−1}. We write Γ⊢Rϕ iff there is an R-derivation of ϕ based on Γ.

Fact 1.

Given a set of inference rules R, ⊢R is monotonic, reflexive and transitive.

Definition 9

Definition 9(S-consistency.).

Where S is a set of inference rules over L, a set Γ of formulas in L is S-inconsistent iff Γ⊢Sψ for some ϕ∈L such that Γ⊢Sϕ and ψ∈ϕ‾. Otherwise it is S-consistent.

Postulate 2

Postulate 2(Indirect Consistency).

sem satisfies Indirect Consistency for an argumentation system AS=(L,S,D,K,n,A‾,⩽) if for every E∈sem(AS), Conc[E] is S-consistent.

A third postulate is related to the interpretation of strict rules → as being truth preserving. Recall that a rule ϕ1,…,ϕn→ϕ means that whenever ϕ1 and … and ϕn are the case, ϕ is necessarily the case as well. This licenses us to require closure under strict rules of any extension. What this means is that, whenever arguments with conclusions ϕ1,…,ϕn are part of an extension (selected according to some semantics sem) and ϕ1,…,ϕn→ϕ is a strict rule we should find an argument for ϕ in that same extension as well.

Postulate 3

Postulate 3(Closure).

sem satisfies Closure for an argumentation system AS=(L,S,D,K,n,A‾,⩽) if for every E∈sem(AS), whenever Conc[E]⊢Sϕ then ϕ∈Conc[E].

Fact 2.

Direct consistency together with closure imply indirect consistency.

In [20] the property of Non-Interference was defined. Roughly speaking, a formalism is non-interferent if syntactically disjoint sets of formulas do not influence each others consequences. In more detail, when Γ∪{ϕ} and Γ′ are two syntactically disjoint sets, a non-interferent system will allow one to infer ϕ from Γ iff ϕ is inferable from Γ∪Γ′. A violation of non-interference thus means that syntactically disjoint knowledge bases influence each others outcomes. In most of the cases,18 18 a violation of non-interference is caused by an inadequate handling of inconsistencies (see Example 6 for a simple illustration): one inconsistency in the knowledge base can cause the whole system to crash since it contaminates the argumentation framework (i.e. the conflict spreads to all arguments, even to arguments which are syntactically disjoint from the inconsistent argument). A system crashing as the effect of an inconsistency is bad news, since it renders the formalism ineffective in extracting useful information from the knowledge base.

To give precise meaning to the notion of syntactic disjointedness (a crucial concept in the formulation of non-interference) we let Atoms(Δ) be the set of all atoms occurring in Δ (where Δ is a set of formulas and/or inference rules based on L). Two sets Δ and Δ′ are syntactically disjoint iff Atoms(Δ)∩Atoms(Δ′)=∅. Finally, we define Θ‾=⋃ϕ∈Θϕ‾. We now define two notions of syntactic disjointedness for argumentations systems. The former (Definition 10) is intended to cover cases in which two argumentation systems share the same base logic, so cases in which the strict rules of both systems are induced by the same logical system. In contrast, Definition 11 is indented to cover cases in which two argumentation systems are based on domain-specific strict rules (see also Footnote 2).

Definition 10.

Two argumentation systems AS=(L,S,D,K,n,A‾,⩽) and AS′=(L,S,D′,K′,n′,A‾,⩽′), based on the same strict rule set S, are syntactically disjoint iff D∪K∪head[D]‾∪K‾ and D′∪K′∪head[D′]‾∪K′‾ are syntactically disjoint.19 19

Definition 11.

Two argumentation systems, AS=(L,S,D,K,n,A‾,⩽) and AS′=(L,S′,D′,K′,n′,A‾,⩽′) are strictly syntactically disjoint iff D∪K∪head[D]‾∪K‾∪S∪head[S]‾ and D′∪K′∪head[D′]‾∪K′‾∪S′∪head[S′]‾ are syntactically disjoint.

Furthermore, given AS=(L,S,D,K,n,A‾,⩽) and D′⊆D, we will denote the set of arguments that can be constructed on the basis of D′ by Args(D′)={a∈Args(AS)∣D(a)⊆D′}.

Postulate 4

Postulate 4(Non-Interference).

Non-Interference20 20 is satisfied for a semantics sem if for any two syntactically disjoint argumentation system AS=(L,S,D,K,n,A‾,⩽) and AS′=(L,S,D′,K′,n′,A‾,⩽′), where K∪K′ is S-consistent, ⩽+ is such that ⩽ [⩽′] is the restriction of ⩽+ to D×D [D′×D′], and AS+=(L,S,D∪D′,K∪K′,n∪n′,A‾,⩽+), we have:21

sem(AS+)={Arg(D[E]∪D[E′])⊆Arg(AS+)∣E∈sem(AS),E′∈sem(AS′)}.21

Postulate 5

Postulate 5(Strict Non-Interference).

Strict Non-Interference is satisfied for a semantics sem if for any two strictly syntactically disjoint argumentation systems AS=(L,S,D,K,n,A‾,⩽) and AS′=(L,S′,D′,K′,n′,A‾,⩽′), where ⩽+ is such that ⩽ [⩽′] is the restriction of ⩽+ to D×D [D′×D′], and AS+=(L,S∪S′,D∪D′,K∪K′,n∪n′,A‾,⩽+), we have:

sem(AS+)={Arg(D[E]∪D[E′])⊆Arg(AS+)∣E∈sem(AS),E′∈sem(AS′)}.

As explained above, a violation of non-interference means that syntactically disjoint knowledge bases influence each other’s outcomes. We will first use the grounded extension to illustrate a violation of non-interference using a simplification of the argumentation system from Example 2.

Example 6.

AS 6=(LCL,SCL,D6,∅,A‾) where D6={⊤⇒q}. Clearly the argument a=⟨⊤⇒q⟩ is in the grounded extension.

Suppose now we move to the knowledge base AS6′=(LCL,SCL,D6′,∅,A‾) where D6′=D6∪{⊤⇒p;⊤⇒¬p}. Informally, AS6′ consists of AS6 supplemented with the syntactically disjoint rule base {⊤⇒p;⊤⇒¬p}. We would expect to still have a in the grounded extension since we only added information that is irrelevant to q. However, this is not the case. To see this, notice we have, among others, the following arguments:

a:⊤⇒qb1:⊤⇒pb2:⊤⇒¬pb:b1,b2→¬q

This gives rise to the following framework:

We see that since ⊢CL satisfies ex falso quodlibet, the contradiction between p and ¬p can be used to construct an argument for ¬q that attacks a. Since there is no unattacked argument that defends a from b, a is no longer in the grounded extension of AS6′. As such, non-interference is violated, since whereas .

To solve problems of this nature, [57,58] proposed to filter out inconsistent arguments like b. Indeed, if we restrict our attention to consistent arguments, a is unattacked and non-interference is satisfied for AS6′ under the grounded extension. This is no coincidence since [57] showed that for any semantics subsumed by complete semantics and given an argumentation system with the trivial priority order ⩽=D×D, non-interference, closure and consistency are satisfied when inconsistent arguments are filtered out. [57] was the first work to investigate and solve the problem of interference.22 22 However, it has been argued in [27] that filtering out inconsistent arguments might be problematic for several reasons. First, checking the consistency of an argument might be computationally intractable. For example, when the strict rules are based on propositional classical logic CL, checking consistency of an argument is NP-complete. Secondly, [27] give several reasons against the appropriateness of filtering out inconsistent arguments for modelling real-life argumentation. They observe that there are many examples of real-life argumentation where inconsistency of an argument is shown dialectically.23 23

When looking back at Example 6, it seems that some of these shortcomings can be overcome for preferred and stable semantics. In fact, when considering the preferred extensions of Arg(AS6′) (which coincide with the stable extensions), namely {a,b1} and {a,b2}, we see that a is part of both of these extensions and thus there is no interference problem. In more detail, every preferred extension contains a defeater of b (i.e. b1 respectively b2) that defends a from the inconsistent argument b. Thus, the question can be raised: is it even necessary to filter out inconsistent arguments when using semantics like the preferred or stable semantics? For argumentation systems without any restrictions on the language, this question has to be answered negatively:

Example 7.

AS7=(LCL,SCL,D7,∅,n,A‾) where

D7=⊤⇒p;p⇒¬n(⊤⇒p);p⇒q;p⇒¬q;⊤⇒s.

We have (among others) the following arguments:

a:⊤⇒sb:⊤⇒pc:b⇒¬n(⊤⇒p)d1:b⇒qd2:b⇒¬qd:d1,d2→¬s

We get the following argumentation framework:

Notice that in this argumentation framework, argument a is not in the unique preferred extension ∅, even though it is syntactically independent from all the other defeasible rules. In other words, a is part of the unique preferred extension in AS7′=(LCL,SCL,{⊤⇒s},∅,A‾), while adding the rules D7∖{⊤⇒s}, which are syntactically disjoint from {⊤⇒s}, results in interferent behaviour.

The problem in the above example can be avoided by filtering out the inconsistent d: in that case a will have no attacker and thus will be in the unique preferred extension.

In the following we will show that when omitting undercut from an ASPIC+ framework, all rationality postulates hold for preferred and stable semantics when the strict rules allow for contraposition. For these semantics it is inconsequential whether inconsistent arguments are removed. Moreover, we characterize these semantics in terms of maximal consistent sets of defeasible rules.

4.Results

We now present our meta-theoretic results. In this section we only consider argumentation frameworks without undercut attacks.

4.1.Preferred and stable semantics coincide

Our first result is that preferred and stable extensions coincide when S is contrapositive, i.e., it satisfies the following two requirements:24 24

S1	If Δ, ψ⊢Sϕ′ for some ϕ′∈ϕ‾, then Δ, ϕ⊢Sψ′ for some ψ′∈ψ‾; and
S2	If Δ⊢Sϕ′ for some ϕ′∈ϕ‾, then Δ∖{ϕ}⊢Sϕ′.

Often, S2 will simply follow from S1. More precisely, this is the case whenever S has theorems. We say that ϕ∈L is a theorem of S iff ⊢Sϕ.25 25

Fact 3.

If S has theorems, then S1 implies S2.

Proof.

Suppose γ is a theorem of S. Suppose Δ, ϕ⊢Sϕ′. By the monotonicity of ⊢S, γ, Δ, ϕ⊢Sϕ′. By S1, there is a γ′∈γ‾ such that Δ, ϕ⊢Sγ′. Again by S1, Δ, γ⊢Sϕ′ and by the transitivity of ⊢S, Δ⊢Sϕ′. □

Theorem 1.

For any AS=(L,S,D,K,A‾,⩽) where S satisfies S1 and S2, pref(AS)=stab(AS).

Proof.

This theorem is an immediate corollary of Theorem 9, proven in Appendix B. □

This result ensures that one can use dialectical proof theories for membership of an admissible extension (see e.g. [49]) to show that an argument belongs to a stable extension.

Checking whether an argument is contained in an admissible extension tends to be less demanding than checking if it is part of a stable extension [28], since the former requires us only to consider arguments that attack the argument in question, whereas the latter requires us to find a set that contains the argument in question and attacks every argument not in the set.26 26 However, it should be remarked that both checking whether an argument belongs to an admissible or a stable extension are in the worst case intractable [31].27 27

In the context of deductive argumentation with defeasible premises, results like Theorem 1 are well-known and are often strengthened by showing that the maximally conflict-free extensions (also called naive extensions) coincide with the preferred and stable extensions (see e.g. [9,37]).28 28 However, even for argumentation systems with the trivial prefence relation D×D over the set of defeasible rules D, maximally conflict-free extensions might not be stable or preferred, as shown by the following example:

Example 8.

Let AS8=(LCL,SCL,{⊤⇒p},{¬p},A‾). This argumentation framework has a unique stable extension which is also preferred: {a∈Arg(AS8)∣D(a)=∅}. However, the set {⟨⊤⟩⇒p} is conflict-free. Thus, there is a maximally conflict-free set that includes ⟨⊤⟩⇒p and this set is neither stable nor preferred.

4.2.Rationality postulates

The four rationality standards hold for both preferred and stable semantics (which coincide as shown in Theorem 1). The following theorem was shown for a slightly different setting in [53],29 29 and is proven in Appendix C.1:

Theorem 2.

pref and stab satisfy Direct Consistency, Closure and Indirect Consistency for any AS=(L,S,D,K,A‾,⩽) for which S satisfies S1 and S2.

Non-interference holds for strict rule bases that are uniform:30 30

Definition 12.

A rule set S is uniform iff for any two sets of formulas Γ, Γ′ in L and any formula ϕ in L such that Γ′ is S-consistent and syntactically disjoint from Γ∪{ϕ}, it holds that Γ⊢Sϕ iff Γ∪Γ′⊢Sϕ.

Non-Interference for ASPIC+ for prioritized rule bases was not shown before and is proven in Appendix C:

Theorem 3.

pref and stab satisfy Non-Interference for any argumentation systems whose sets of strict rules are uniform and satisfy S1 and S2.

In particular, this means that an argumentation system that is induced by classical logic satisfies non-interference. In more detail, we say that AS=(L,S,D,K,n,A‾,⩽) is induced by classical logic if L is closed under the classical connectives {¬,∧,∨} and S is the set of strict rules capturing classical logic CL (over L): ϕ1,…,ϕn→ϕ∈S iff {ϕ1,…,ϕn}⊢CLϕ. For a concrete example, see Example 2.

Fact 4.

Where AS=(L,S,D,K,n,A‾,⩽) is induced by classical logic, S is uniform and satisfies S1 and S2.

Given the uniformity of classical logic, Theorem 3 immediately implies the non-interference of any argumentation system induced by classical logic.

Theorem 4.

pref and stab satisfy Non-Interference for any argumentation system induced by classical logic.

Strict Non-Interference holds for systems with sets of strict rules that satisfy S1 and S2.

Theorem 5.

pref and stab satisfy Strict Non-Interference for any argumentation systems with sets of strict rules S that satisfy S1 and S2.

The reader may wonder why S1 and S2 are needed. We first note that both S1 and S2 are very much in line with the interpretation of strict rules S as truth-preserving rules. For example, S1 requires that if Δ⊢SA for some A∈B‾ (i.e. Δ implies the falsity of B), then if B is true, one of the members of Δ must be false. Likewise, S2 requires that if Δ can be used to derive A∈B‾, i.e. show that B is false, B does not have to be assumed true.

From the perspective of the argumentative rationality postulates, S1 ensures that whenever an argument a is attacked by an argument b=b1,…,bn→Conc(a)‾, we can construct the contraposed argument b2,…,bn,a→Conc(b1)‾. If we cannot do this, several rationality postulates are violated.

Example 9.

AS 9=({p,q,s,r,p′,q′,s′,r′},S9,D9,{s},A‾,⩽9) where S9={q→r′} and D9={s⇒q,s⇒r}, ϕ‾={ϕ′} and ϕ′‾={ϕ} for any ϕ∈L, and s⇒q<9s⇒r. We have the following arguments:

a:⟨s⟩b:a⇒qc:b→r′d:a⇒r

Notice that c attacks but does not defeat d since D(c)≺9D(d). Vice versa, d does not even attack c since c is a strict rule-argument, which cannot be attacked. Thus, the unique preferred extension of this argumentation framework includes a, b, c and d and thus this argumentation framework violates consistency since there are arguments for both r (namely c) and its contrary r′ (namely d).

S2 ensures, among other things, that a defeasible argument concluding an ⊢S-anti-theorem or contradiction (i.e., a formula ϕ for which ⊢Sϕ‾ such as p∧¬p in classical logic) is attacked by a strict argument (namely →ϕ‾). As such, S2 ensures there is always an argument that can defend any argument from an attack based on a “contradictory” formula. If this assumption is given up, non-interference can be violated for rule bases S that have explosive behavior:

Example 10.

Where L10={p,q,r,q′,r′}, D10={⇒1r}, D10′={⇒2p;p⇒1q;p⇒1q′}, p‾={p} (i.e. p is a falsity), q′‾={q}, q‾={q′}, r‾={r′}, r′‾={r}, and

S10={q,¬q→ϕ∣ϕ∈L10}∪{p→ϕ∣ϕ∈L10}∪{ϕ→p∣ϕ∈L10},

and ⩽′⊆(D10∪D10′)2 ranks the defeasible rules according to their subscripts, consider AS10=(L10,S10,D10,∅,A‾,⩽) and AS′10=(L10,S10,D10∪D10′,∅,A‾,⩽′). We get, for instance, the following arguments:

a1:⇒pa2:a1⇒qa3:a1⇒q′a4:a2,a3→r′a5:⇒r

This results in the following argumentation graph

This argumentation graph has the unique preferred extension ∅ and no stable extensions. Also, while r is in the grounded resp. in every preferred extension of AS10 it is not in the grounded resp. in any preferred extension of the aggregated framework. This means also non-interference does not hold. In sum, both the equivalence between stable and preferred semantics from Theorem 1 and non-interference are violated. Note while S satisfies S1, S2 does not hold since {p}⊢Sp while ⊬Sp (recall that p∈p‾).

4.2.1.A note on symmetric contraries

The reader might at this point be suspicious that the results above admit counter-examples in view of argumentation systems with assymetric contraries. For example, the following example seems at first sight to contradict Theorem 1:31 31

Example 11.

Let AS11=({p,q,⊤},S11,D11,∅,A‾) where S11=∅, D11={⊤⇒p;p⇒q}, q‾=∅ and p‾={q}. Then Args(AS11) consists, among others, of the following two arguments:

a:⟨⊤⟩⇒pb:a1⇒q

Notice that b defeats a and itself. Hence there is no stable extension while the unique preferred extension is ∅, thus {∅}=pref(AS11)≠stab(AS11)=∅.

However, the above example does not constitute a counterexample to Theorem 1, since in fact S11 violates S1. Indeed {q}⊢Sq and q∈p‾ yet there is no q′∈q‾ such that {p}⊢Sq′. In fact, for any rule base that satisfies S1, the set of contraries will be (pseudo-)symmetric in the sense that if there is a ϕ∈ψ‾ then there is a ϕ′∈ϕ‾ for which ψ⊢Sϕ′. Notice that this is weaker than symmetry as it is perhaps usually understood, i.e. if ϕ∈ψ‾ then ψ∈ϕ‾.

Fact 5.

If S satisfies S1 and ϕ∈ψ‾, there is a ϕ′∈ϕ‾ such that ψ⊢Sϕ′.

Proof.

Suppose that S satisfies S1 and ϕ∈ψ‾. Since ϕ⊢Sϕ, with S1 there is some ϕ′∈ϕ‾ for which ψ⊢Sϕ′. □

4.3.Characterization using maximally consistent sets

In this section we show that the preferred and stable semantics can be characterized in terms of maximally consistent sets of defeasible rules. Similar results have been proven for a multitude of formalisms for deductive argumentation with defeasible assumptions, for example for deductive argumentation based on classical logic [4,5,22,35], or on arbitrary Tarskian logics [2], sequent-based argumentation [7,8,13] or assumption-based argumentation [37,38]. However, to the best of our knowledge, such results have not been established for argumentation with defeasible rules. We start with non-prioritized framework in Section 4.3.1 and then move to the prioritized case in Section 4.3.2.

4.3.1.The non-prioritized case

We first present a simple but flawed idea of how to characterize argumentation extensions by means of maximal consistent sets of defeasible rules which we call naive rule maximizing. For this we first define what it means for a set of defeasible rules in D to be consistent, given a fixed context of strict rules S and of (strict) premises K.

Definition 13.

Where Δ⊆D, we define Δ⊢KSϕ by K⊢S∪Δϕ (see Definition 8).32 32

Where the context disambiguates, we simply write ⊢K instead of ⊢KS. Simply expressed, ϕ follows from Δ if it can be derived by applying modus ponens for premises in K and rules in S∪Δ. Where the context disambiguates, we will omit the sub-script K and simply write Δ⊢ϕ.

Definition 14.

Where Δ⊆D, Δ is ⊢KS-inconsistent iff there is a formula ϕ and a ψ∈ϕ‾ for which Δ⊢KSψ and Δ⊢KSϕ. Otherwise Δ is ⊢KS-consistent.

Where the context disambiguates, we will simply speak of (in)consistent sets Δ. In particular, for the following result we assume a fixed argumentation system AS=(L,S,D,K,A‾,⩽).

According to naive rule maximizing we collect as many defeasible rules as is consistently possible. Let for this MCSnaS,K(D) be the set of all ⊢KS-consistent Δ⊆D for which there is no ⊢KS-consistent Δ′⊆D such that Δ⊂Δ′.33 33 However, this approach does not characterize argumentation semantics (and other “conclusion-maximizing” approaches such as default logic), as the following simple example illustrates.

Example 12.

Let AS12=(LCL,SCL,D12,∅,A‾) where ψ∈ϕ‾ iff ψ=¬ϕ or ϕ=¬ψ and D12={r1:⊤⇒p,r2:p⇒q,r3:⊤⇒¬q}.

Then MCSnaSCL,∅={Δ1:{r1,r2},Δ2:{r1,r3},Δ3:{r2,r3}}. However, if we consider the argumentation framework based on the same ingredients, we will have two preferred (resp. stable) extensions: E1={a1,a2,…} and E2={a1,a3,…} where a1=⊤⇒p, a2=a1⇒q and a3=⊤⇒¬q. Note that both extensions contain a1=⊤⇒p. This contrasts with the maximal consistent set Δ3={r2,r3}.

The problem with the set {r2,r3} in our example is that it is not “grounded”: the rule r2 cannot be triggered: indeed, {r2,r3}⊬Kp where body(r2)={p}. This is why it does not correspond to an extension of the corresponding argumentation framework. In the following we will restrict our attention to those sets of defeasible rules that are grounded in the sense that Δ⊢ψ for each ψ∈body[Δ].

Definition 15.

Where Δ⊆D and r∈D, r is ⊢KS-triggered by Δ iff Δ⊢KSψ for each ψ∈body(r). We will also call Δ a ⊢KS-trigger set of r. Let ℘ˆS,K(D) be the set of all Δ∈℘(D) such that every r∈Δ is ⊢KS-triggered by Δ.

As before we will reduce clutter whenever the context disambiguates and simply say that r is triggered by Δ, talk of trigger sets of r and denote ℘ˆS,K by ℘ˆ.

Fact 6.

Where Δ∈℘ˆ(D), Δ is inconsistent iff there are ϕ∈head[Δ] and ψ∈ϕ‾ for which Δ⊢Kψ.

Proof.

For the right-to-left direction suppose there are ϕ∈head[Δ] and ψ∈ϕ‾ for which Δ⊢Kψ. Since Δ∈℘ˆ(D) also Δ⊢Kϕ and we are done. The left-to-right direction can be shown by an induction over the lengths of the proof of ϕ and ψ from Δ by making use of the contrapositably nature of the strict rules. We omit the technical details but give a simple example instead.

Example 13.

Suppose, where K={d,s,t}, Δ={d⇒e;u,t⇒p} and s→u and e,u→p′ are strict rules and p′∈p‾ we have the following two proofs (in tree form) demonstrating that Δ⊢Kp and Δ⊢Kp′:

P1=d⇒es→u→p′P2=t⇒p

By contraposition, also u,p→e′ is a rule for some e′∈e‾. So, we have the following proof

P3=t⇒ps→u→e′,

which shows that Δ⊢Ke′.

□

Definition 16.

MCSS,K(D) is the set of all consistent Δ∈℘ˆ(D) for which there is no consistent Δ′∈℘ˆ(D) such that Δ⊂Δ′.

Where the context disambiguates, we will omit the superscript and simply write MCS(D).

Example 14

Example 14(Example 12 cont.).

We have MCS(D)={Δ1:{r1,r2},Δ2:{r1,r3}}. Note that Δ1⊢Kp and Δ2⊢Kp just like both argumentation extensions contain arguments for p.

There is indeed a very close relationship between the set MCSS,K(D) and the preferred resp. stable extensions of AS=⟨L,S,D,K,A‾⟩. To state it we introduce one more notation.

Definition 17.

Where Δ⊆D let Arg(Δ)=df{a∈Arg(AS)∣D(a)⊆Δ} be the set of arguments that only make use of defeasible rules in Δ.

Our main result for non-prioritized argumentation can then be stated as follows:

Theorem 6.

For any AS=(L,S,D,K,A‾) where S satisfies S1 and S2,

pref(AS)=stab(AS)={Arg(Δ)∣Δ∈MCS(D)}.

There are two open question which we will address in the remainder of this section: (a) can the grounded semantics respectively (b) can the extensions of frameworks constructed on the basis of prioritized defeasible rule bases be represented in a similar way?

We start with a negative result concerning question (a). One may expect that the grounded extension can be characterized by ⋂MCS(D). We give the following counter-example:

Example 15

Example 15(Example 6 continued).

Recall AS6′ from Example 6. We have MCS(D6′)={{⊤⇒p,⊤⇒q},{⊤⇒¬p,⊤⇒q}}, {⊤⇒q}=⋂MCS(D6′) and {⊤⇒q}∈℘ˆ(D6′). However, the grounded extension is Arg(∅). Recall for this that the argument b=⟨⊤⇒p⟩,⟨⊤⇒¬p⟩→¬q attacks a=⟨⊤⇒q⟩. Note that q is implied by every MCS, but there is no argument for it in the grounded extension.

What we see in the example is contaminating behavior by the inconsistent argument a⊥ which attacks the syntactically disjoint b. This contamination does not occur when working with MCSs. One way to deal with this problem in the context of formal argumentation is to filter out inconsistent arguments such as a⊥ [57].34 34

Definition 18.

Let Arg⊤(AS) be the set of all consistent arguments a in Arg(AS), where a is consistent iff D(a) is consistent (see Definition 14). Similarly, where sem∈{pref,stab,groun}, let sem⊤(AS) be the set of extension of the restriction of ⟨Arg(AS),⇝(AS)⟩ to consistent arguments.

Indeed, once we filter out inconsistent arguments we can characterize also the grounded semantics. First we note a minor complication, namely, generally it does not hold that ⋂MCS(D)∈℘ˆ(D).

Example 16.

AS 16=(LCL,SCL,D16,∅,A‾) where ψ∈ϕ‾ iff ψ=¬ϕ or ϕ=¬ψ and D16={r1:⊤⇒p,r2:⊤⇒¬p,r3:p⇒q,r4:¬p⇒q,r5:q⇒s}. Then MCS(D16)={{r1,r3,r5},{r2,r4,r5}}. Note that ⋂MCS(D16)={r5}∉℘ˆ(D).

In the Appendix (Lemma 6) we show that there is a unique ⊂-maximal Δ∈℘ˆ(D) that is contained in ⋂MCS(D).

Definition 19.

We call the unique ⊆-maximal Δ∈℘ˆ(D) that is contained in ⋂MCS(D) the free set in D, denoted by Free(D).

The set Free(D) characterizes the grounded extension when filtering out inconsistent arguments.

Theorem 7.

Where AS=(L,S,D,K,A‾) and S satisfies S1 and S2, Arg(Free(D))=groun⊤(AS).

Naturally, the question arises whether for preferred and stable semantics the filtering of inconsistent arguments changes the extensions. The answer is no:

Theorem 8.

For any AS=(L,S,D,K,A‾) where S satisfies S1 and S2,

pref(AS)=stab(AS)=pref⊤(AS)=stab⊤(AS)={Arg(Δ)∣Δ∈MCS(D)}.

4.3.2.The prioritized case

We now move to prioritized frameworks. Stable and preferred extensions can be characterized by selecting a subset of MCS(D). For this, we introduce a new priority-sensitive notion of consistency. Recall that the defeasible rules in D are ranked by a total order ⩽. This means that, without loss of generality, we can assume that the defeasible rules in D are ranked relative to a (finite) set of natural numbers. We denote this ranking by R:D→N. Where Δ⊆D, let R[Δ]=dfmin({R(r)∣r∈Δ}) where R[∅]=dfω>R(r) for all r∈D. We then define:

Definition 20.

Δ∈℘ˆ(D) is ⊢KS-R-consistent iff it is ⊢KS-consistent and for all Θ∈℘ˆ(D) for which ⊥(Δ∪Θ) there is a Δ′∈℘ˆ(Δ) such that ⊥(Δ′∪Θ) and R[Δ′]⩾R[Θ]. We write MCSRS,K(D) for the set of all ⊢KS-R-consistent Δ for which there are no ⊢KS-R-consistent Θ such that Θ⊃Δ.

An R-consistent set Δ is a consistent set that “dominates” every set Θ that is inconsistent with it in the sense that we can always find a subset Δ′ of Δ that is already inconsistent with Θ but for which R[Δ′]⩾R[Θ]. This makes it rational to stick with an R-consistent set of rules Δ since whenever we are confronted with a set of rules Θ inconsistent with Δ, it is rational to disregard a rule in Θ because the conflict can be further localized in the conflict ⊥(Δ′∪Θ) and there is no reason to give up rules in Δ′ since R[Δ′]⩾R[Θ].

In order to avoid clutter we will again talk about R-consistent sets and write MCSR whenever the context disambiguates.

In the appendix we show that, as expected, the set of maximally R-consistent sets is exactly the set of all maximally consistent set that are R-consistent (Proposition 1).

Example 17

Example 17(Example 2 continued).

We consider a slight modification of AS2 that does not contain undercut: AS2′=(L2,SCL,D2′,K2,A‾,⩽) where D2′=D2∖{b⇒1¬δ}.

We have one set of rules that is maximally R-consistent: Θ={g⇒2¬p,l⇒1q,q⇒1w}. Note that any set Δ∈℘ˆ(D2′) that is inconsistent with Θ contains g⇒1p. Since R[{g⇒2¬p}]⩾R[Δ] and {g⇒2¬p}⊆Θ this suffices to show that Θ is R-consistent. Since Θ is also maximally consistent, it is maximally R-consistent as well. Our other maximally consistent set Θ′={g⇒1p,l⇒1q,q⇒1w} is not R-consistent since for Δ′={g⇒2¬p} we have ⊥(Δ′∪Θ′) and there is no Θ″∈℘ˆ(Θ′) for which ⊥(Θ″∪Δ′) and R[Θ″]⩾R[Δ′]. This is for the simple reason that any Θ″ for which ⊥(Θ″∪Δ′) will contain g⇒1p.

Maximal R-consistency can be used to characterize preferred and stable semantics, both for frameworks with and without consistent arguments.

Theorem 9.

Where AS=(L,S,D,K,A‾,⩽) and S satisfies S1 and S2,

pref(AS)=stab(AS)=pref⊤(AS)=stab⊤(AS)={Arg(Δ)∣Δ∈MCSR(D)}.

Our final question is whether we can characterize the grounded semantics in a similar way as in Theorem 7 also for the prioritized setting. The answer is negative, as the following example illustrates.

Example 18.

Consider AS18=(LCL,SCL,D18,∅,A‾,⩽) where ψ∈ϕ‾ iff ψ=¬ϕ or ϕ=¬ψ and

D18={r1:⊤⇒5p∧q,r2:⊤⇒5p∧¬q,r3:⊤⇒4¬p,r4:¬p⇒4¬s,r5:⊤⇒3s}.

We have, among others, the arguments:

a:⟨⊤⟩⇒p∧qa1:a→pa2:a→¬(p∧¬q)b:⟨⊤⟩⇒p∧¬qb1:a→pb2:a→¬(p∧q)c:⟨⟨⊤⟩⇒¬p⟩⇒¬sd:⟨⊤⟩⇒s

This gives rise to the following argumentation framework:

We have MCSR(D18)={{r1,r5},{r2,r5}} and so {r5}=⋂MCSR(D18). Note also that {r5}∈℘ˆ(D18) and so it is the unique ⊂-maximal set contained in ⋂MCSR(D18). Nevertheless, the grounded extension for this example does not include any defeasible arguments and so also not an argument for s.

5.Related work

As pointed out in the introduction, work on simultaneous satisfaction of all rationality postulates for members of the ASPIC-family is rather limited. The postulates of consistency and closure, on the other hand, have been more extensively investigated. They were first introduced in [1,19] and were subsequently proven for ASPIC+ in [50,53] where the strict rule base satisfies either contraposition or transposition. This line of work was continued in [32], where different variants of the weakest link lifting were studied. Let us therefore compare the conditions of contraposition and transposition to the conditions S1 and S2 used in this paper. Let −ϕ denote a contradictory of ϕ, i.e., a formula ψ for which ϕ∈ψ‾ and ψ∈ϕ‾. For the definitions of Tpos and Cpos we thus follow [50] in assuming

CPE Every formula ϕ has a contradictory ψ (so ϕ∈ψ‾ and ψ∈ϕ‾)

that every formula has a contradictory. Given an argumentation system (L,S,D,K,n,A‾,⩽), transposition and contraposition require the following:

Tpos If ϕ1,…,ϕn→ϕ∈S then for every 1⩽i⩽n, ϕ1,…,ϕi−1,−ϕ,ϕi+1,…,ϕn→−ϕi∈S.35 35
Cpos For any Δ⊆L, if Δ⊢Sϕ then for all ψ∈Δ, (Δ∖{ψ})∪{−ϕ}⊢S−ψ.

Unlike [50], in the setting of this paper we did not suppose CPE, i.e., the existence of contradictories. Note, however, that S1 implies that if some formula has a contrary, so does every.36 36 For most use cases of ASPIC this will coincide with the slightly stronger assumptions that

CTE For every formula ϕ, ∅≠ϕ‾.

Clearly, CPE implies CTE but not vice versa. Assuming CTE, we can define the variant of CPos (and analogous of Tpos):

Cpos⋆ For any Δ⊆L, if Δ⊢Sϕ, then for all ψ∈Δ, for all ψ′∈ψ‾, and for all ϕ′∈ϕ‾, (Δ∖{ψ})∪{ϕ′}⊢Sψ′.37 37

It will not surprise the reader that there is a close connection between the Cpos resp. Cpos^⋆ and requirement S1.

Fact 7.

Cpos implies S1 if for all ϕ∈L and all ϕ′∈ϕ‾, ϕ⊢S−ϕ′.

Proof.

Assume Δ, ψ⊢Sϕ′ for some ϕ′∈ϕ‾ and that Cpos is valid. By Cpos, Δ, −ϕ′⊢S−ψ. Since ϕ⊢S−ϕ′ and by the transitivity of ⊢S, Δ, ϕ⊢S−ψ. □

Fact 8.

Cpos^⋆ and CPE imply S1.

Proof.

Suppose Δ, ψ⊢Sϕ′ for some ϕ′∈ϕ‾. By Cpos^⋆ and CPE, Δ, −ϕ′⊢S−ψ. Since ϕ⊢Sϕ, by Cpos and CPE, ϕ′⊢S−ϕ and furthermore, ϕ⊢S−ϕ′. By the transitivity of ⊢S, Δ, ϕ⊢S−ψ. □

Fact 9.

Cpos^⋆ implies S1 if for all ϕ∈L and all ϕ′∈ϕ‾ there is a ϕ″∈ϕ′‾ for which ϕ⊢Sϕ″.

Proof.

Assume Δ, ψ⊢Sϕ′ for some ϕ′∈ϕ‾ and that Cpos^⋆ is valid. We have to show that Δ, ϕ⊢Sψ′ for some ψ′∈ψ‾. We suppose that ϕ⊢Sϕ″ for some ϕ″∈ϕ′‾. By Cpos^⋆, Δ, ϕ″⊢Sψ′ for some ψ′∈ψ‾. By the transitivity of ⊢S therefore Δ, ϕ⊢Sψ″. □

In particular, the requirement of Facts 7–9 hold if for all formulas ϕ all members of ϕ‾ are contradictories, i.e., if ϕ∈ϕ′‾ for all ϕ′∈ϕ‾.

Interestingly, even given CPE, we can easily find counter-examples to rationality postulates such as Consistency for frameworks satisfying Cpos (and similarly for Tpos).

Example 19.

Consider AS19=(L19,S19,D19,{⊤},A‾,⩽19), where L19={p,q,¬p,¬q,⊤,⊥}, S19={}, D19={r1:⊤⇒p,r2:⊤⇒q}, ⊤‾={⊥}, ⊥‾={⊤}, p‾={¬p}, ¬p‾={p}, q‾={¬q,p}, ¬q‾={q}, and r1⩽19r2.

Note that p is merely a contrary, not a contradictory of q, while ¬q and q are contradictories. We have the following arguments:

a:⟨⊤⟩⇒pb:⟨⊤⟩⇒q

Note that we have no defeats between a and b and so the only preferred, stable and grounded extension will include both arguments. Nevertheless, this extension is not consistent since the conclusions p and q are not consistent given that p∈q‾.

Note that while S19 satisfies Cpos and CPE, it does not satisfy S1 since p⊢S19p but not q⊢S19¬p.

The example also shows that S1 does not imply Cpos.

To see that neither Cpos, Cpos^⋆, nor Tpos implies S2, consider the following example: Let S=∅ and p‾={p}. Then we see that ⊢S is closed under Cpos and Tpos, however, it does not satisfy S2, as {p}⊢Sp‾ yet ∅⊬p‾. In view of Example 10, this means that Tpos and Cpos as studied in [50] are not sufficient to guarantee non-interference.

As Example 19 shows, only relying on Cpos (or Tpos) in combination with CPE does not suffice to get rationality postulates, such as Consistency. What is proposed in addition in [50] is to treat rebut defeats where the concluding formula of the attacking argument is a contrary (so not a contrapositive) of the conclusion of the attacked argument different from those rebuts with contradictory conclusions. While the latter case works as our Definition 5, in the former case argument strength is disregarded and any attack results in a defeat. While this move secures the standard rationality postulates (except for non-interference), it leads to what may be considered as counterintuitive behavior nevertheless. We give some examples.

Example 20

Example 20(Problems with “contrary-rebut”).

In all example below we treat ¬ϕ and ϕ as contradictories. Our examples concern two very weak versions of “interference”38 38 and a lightweight version of the well-known Cumulativity principle from non-monotonic logic.

Interference 1. Suppose AS1 has the rule base D={⊤⇒8p}, p has as a contrary r and the strict rules are induced by classical logic. Clearly, p will be a grounded consequence of AS1. Suppose further we add the rules D′={⊤⇒1q,⊤⇒1¬q} resulting in an extended system AS2. Now the argument ⟨⊤⇒1q⟩, ⟨⊤⇒1¬q⟩→r will defeat ⊤⇒8p and p will therefore not be a grounded consequence of AS2. Note that we only added weaker rules than the ones in AS1, both of which are syntactically disjoint from AS1, but this was sufficient to contaminate the framework.
Interference 2. In this example we will again add rules to a given AS3, this time rules that only extend arguments which are rejected in any extension of a given standard (completeness-based) semantics. Let AS3 be based on D3={⊤⇒100p,⊤⇒2¬p}. Clearly, the argument a=⊤⇒100p will be in any extension, while b=⊤⇒2¬p will be defeated in any extension. We now add the rules in D4={¬p⇒1q,q⇒1p′} resulting in AS4, where p has as a contrary p′. We note that these rules are weaker than those in D3 and they only extend our rejected b to c=b⇒1q⇒1p′. Interestingly, now c defeats a and so p will not be anymore a consequence of AS4.
Cumulativity lite. Suppose an argument a with conclusion ϕ and strength n (so n=min({m∣ϕ1,…,ϕk⇒mψ∈D(a)})) is contained in every preferred extension of AS. Then one would expect that adding a new rule ⊤⇒nϕ to the defeasible rules should lead to robust results. (In Appendix C.4 we show that our system satisfies our expectation.) Let AS5 come with the rules
D5={⊤⇒10p,p⇒10q,q∨r⇒1¬q,¬q⇒1p′},
and suppose p has as a contrary p′. We have, for instance, the following arguments:
a:⊤⇒10p⇒10qa′:a→q∨rb:a′⇒1¬qb′:b⇒1p′

This results in the framework to the left:

So a and a′ are contained in every preferred extension of AS5. Now if we add ⊤⇒10q∨r to D5 (resulting in AS6), we also get the argument c=⊤⇒10q∨r⇒1¬q and c′=c⇒1p′. This results in the graph to the right (omitting the nodes b and b′ for clutter reduction). Now, there is a preferred extension containing c and c′ in which a and a′ are defeated, so that p and q are not anymore consequences of AS6.

In order to avoid this kind of behavior we stuck in this paper to a uniform treatment of defeat where argument strength is considered for both rebuts, those with contrary and those with contradictory attacking formulas.

[30] goes beyond transposition and contraposition by formulating a condition called the self-contradiction axiom, which is implied by both transposition and contraposition. This self-contradiction axiom requires of an argumentation system AS=(L,S,D,K,A‾) that:

SCA

for any ⊆-minimally inconsistent39 39 set of formulas Σ⊆L, Σ⊢Sϕ′ for any ϕ∈Σ and some ϕ′∈ϕ‾.

[30] shows that this axiom is sufficient to guarantee the postulates of closure and consistency for argumentation systems without preferences over the defeasible rules. However, non-interference is not studied. In fact, self-contradiction alone is not sufficient to guarantee non-interference, even for argumentation systems without preferences. To see this, notice that in Example 10 the self-contradiction axiom is satisfied as: for all ϕ∈L10, {p}⊢Sϕ and {q,¬q}⊢Sϕ. However, as explained in Example 10, non-interference is not satisfied.

In this paper, we characterized the extensions of frameworks under some argumentation semantics in terms of maximal consistent sets of premises. As mentioned above, for structured argumentation with defeasible premises, such results are well-studied, see e.g. [6]. In contrast, for structured argumentation with defeasible rules such results were, to the best of our knowledge, not yet available. A series of different but related results are presented in [3], where structured argumentation formalisms allowing for reasoning with defeasible rules are studied. This paper studies the exact effects of various conditions on both the attack relation and the output of structured argumentation formalisms on the behaviour of various argumentation semantics. For example, it is shown for a conflict-dependent attack relation (which says that if a attacks b, then {Conc(c)∣c∈Sub(a)∪Sub(b)}⊢S⊥), the output of an argumentation system satisfies consistency, closure, closure under sub-arguments. Moreover, if every extension contains all strict arguments, for every stable extension E, D[E] is maximally consistent. It is also shown that if an attack relation is such that the number of stable extensions is the same as the number of maximally consistent subsets of defeasible rules, the stable and the preferred extensions coincide (as in Theorem 1) and coincide with the sets of arguments that can be constructed on the basis of maximally consistent subsets of defeasible rules (as in Theorem 9).

Although the results in [3] are similar in spirit to some of the results obtained in this paper, the set-up is quite different. While we obtain results for a specific system, [3] takes a reverse-engineering approach by studying requirements for structured argumentation formalisms that warrant desired results. Finally, in [3] priorities over the defeasible rules are not studied and arguments are assumed to be consistent and minimal, which is not required in the present study.

In [59 ,60] ASPIC+ is used to obtain an argumentative characterization of prioritised default logic [16]. For this it is noticed that the weakest link lifting is not adequate and therefore the structure preference order has to be used, a lifting tailored for the characterization of prioritised default logic. Since prioritised default logic gives rise to a single extension for totally ordered default theories, the resulting ASPIC+ frameworks also have a unique stable extension, which can be contrasted with ASPIC+ under weakest link (see e.g. Example 6). Furthermore, even though [59,60] show closure, direct and indirect consistency for the resulting formalism, non-interference is not mentioned.

6.Concluding discussion and outlook

The main contributions of this paper can be summarized as follows: ASPIC+ without undercut and defeasible premises, and with a strict contrapositable rule base satisfies all four rationality postulates under preferred and stable semantics (which coincide) and admits a representation in terms of maximal consistent subsets under the weakest link lifting for totally ordered defeasible rules. Furthermore, we showed that the grounded extension for non-prioritized argumentation systems contain the free defeasible rules, but for prioritized argumentation systems such a characterization does not work. We conclude this paper by explaining how these results shed further light on the close relationship between assumption-based argumentation and ASPIC+ and finally point to further work we plan on the basis of this paper.

6.1.Assumption-based argumentation

Besides the ASPIC-family, another popular approach to structured argumentation is assumption-based argumentation [12]. As the name suggests, it provides a formal model of reasoning with strict rules and defeasible assumptions. In contrast to ASPIC, it does not allow for the chaining of defeasible inference rules.40 40 Another major difference between these two formalisms is that in ABA, nodes in argumentation graphs consist of sets of defeasible assumptions, as opposed to structured arguments in the form of proof trees for a specific conclusion in ASPIC+. In this way, ABA can be seen as an abstraction to the level of equivalence-classes of arguments that are based on the same defeasible ingredients.

Formally, a prioritised ABA system ASABA=⟨L,Ab,S,K,A‾,⩽⟩ consists of a language L, a set of defeasible assumptions Ab⊆L, a set of strict rules formulated over L, a strict premise set K, a contrariness relation A‾:Ab→℘(L) and a preference relation ⪯ over Ab. Argumentation frameworks constructed on the basis of a prioritised ABA system ASABA are AF(ASABA)=(℘(Ab),⇝) where Δ⇝Θ iff (1) K∪Δ⊢SA for some A∈B‾ and some B∈Θ and (2) min(Δ)⩾B.41 41

Several results have indicated a strong connection between assumption-based argumentation and reasoning with maximally consistent subsets for both non-prioritized [37,43] and prioritized assumption-based systems [40,42]. Theorem 9 generalizes such insights to settings where defeasible inferences can be chained. This result thus shows that ABA and ASPIC+ give rise to similar output. What is still an open question, though, is whether the abstract perspective offered by ABA (i.e. to consider argumentation graphs on the basis of equivalence classes of arguments) can also be obtained in ASPIC+. A positive answer to this question would mean that it is possible to smoothly change perspectives between different levels of abstraction for argumentation based on defeasible rule bases. The more abstract perspective has the benefit that the set of arguments is bounded by the size of the powerset of defeasible elements, which implies that the set of arguments will be finite if the set of defeasible elements is finite. This stands in contrast with approaches with ASPIC+-style arguments, where even for a finite number of defeasible elements, the argumentation graph may contain an infinite number of arguments (since e.g. classical logic gives rise to an infinite number of conclusions for every premise set).

6.2.Outlook and further work

One limitation of this work is that the rationality postulates and the correspondence with maximally consistent sets have only been proven for argumentation systems without undercutting attacks, without defeasible premises and only for systems with totally ordered sets of defeasible rules. E.g., concerning undercut, Examples like 7 lead to interferent behaviour. Similarly, it is a challenge to generalize our results to non-total orders and to incorporate defeasible premises which may be incomparable in strength to some of the defeasible rules, in such a way that the rationality postulates are satisfied. This will be a topic for future work.

Furthermore, in this contribution we only considered the weakest link lifting. Our results do not cover another popular lifting for ASPIC+, the last link lifting. According to it, an argument is as strong as the last defeasible elements applied in the construction of the argument. A complication with the last link lifting concerns arguments in which we are dealing with several last defeasible links. We can, for instance, opt for the strongest of the last links (called elitist approach [50]) or the weakest (called democratic approach in [50]). It turns out that both approaches lead to violations of non-interference in the current setting. We paradigmatically present an example for the democratic approach.

Example 21

Example 21(Inspired by Example 6.7 in [57]).

AS 21=(LCL,SCL,D21,{s},A‾,⩽) where ϕ‾={ψ∣ψ⊢CL¬ϕ} and D21={s⇒1p;p⇒3q;s⇒2¬p∨¬q}. We have, among others, the following arguments:

a:⟨s⟩a1:a⇒1pa2:a⇒2¬p∨¬qa3:a1⇒3qa12:a1,a2→p∧¬qa13:a1,a3→p∧qa23:a2,a3→¬p∧qa⊥:a1,a2,a3→⊥

In this example we use the democratic last link lifting, which says that an argument b⪯lldc iff the ⩽-minimal last defeasible rule used in b is weaker than the ⩽-minimal last defeasible rule used in c. For example, a2⪯llda3 since the weakest last defeasible link of a2, s⇒2¬p∨¬q, is weaker than the weakest (and only) last defeasible link of a3, p⇒3q. For the same reason, a3⋠llda2. We get the following defeat diagram:

It can be seen that the unique preferred extension only contains strict arguments and arguments with the defeasible rule s⇒2¬p∨¬q. If we now add the syntactically disjoint rule ⊤⇒1t, the argument a123 defeats the argument ⊤⇒1t and thus interferes with the derivability of t.

It is interesting to note that AS21 is used in [57] to show that under last link, filtering out inconsistent arguments leads to violations of closure and consistency. Indeed, when a13, a23 and a⊥ are not part of the argumentation framework, a1, a2, a3, and a12 are all undefeated, meaning they are part of the unique preferred extension of Arg⊤(AS21). This means that this extension contains arguments for e.g. p, q and ¬p∨¬q, constituting a violation of indirect consistency and closure (since {p,q,¬p∨¬q}⊢CL⊥ but there is no argument for ⊥ in Arg⊤(AS21)). It is therefore an important avenue for future work to define a formalism that satisfies all four rationality postulates under the last link principle.

Notes

1 The notation used in this example will be properly introduced in Section 2.

2 In the context of ASPIC+ scholars often distinguish domain-dependent from domain-independent rules (see e.g., [53, Section 4] for a more detailed discussion). The latter hold for purely logical reasons which is why we deal with them typically when the set of strict rules is induced by a (Tarskian) logic, while the former cover typically cases in which the strict rules are not justified by a truth-preservational logical standard but rather by empirical insights.

3 For structured argumentation systems with defeasible premises (but without defeasible rules), on the other hand, the situation looks a lot better, see e.g. [9,27,37].

4 Note that ϕ‾ does not denote the set theoretic complement.

5 K is S-consistent iff there is no derivation based on rules in S from K of some ϕ∈K and some ψ∈ϕ‾. See also Def. 8.

6 A preorder is a binary relation that is reflexive and transitive.

7 More precisely, when omitting ⩽ we consider the preorder D×D.

8 We use subscripts to refer to the numbers of our examples.

9 In the examples that follow, we shall denote with SCL the rule set constructed in the same way as in this example, except that the language is changed relative to the example at hand.

10 In all the examples that follow where L is closed under ¬, we will treat ϕ‾ the same.

11 In this paper we will for the sake of simplicity omit several features of the original ASPIC+ framework of [53], such as defeasible premises and undermining attacks. We note that (in case no incomparabilities between the strength of defeasible premises and the strength of defeasible rules occur) defeasible premises γ can easily be modelled as a defeasible rule ⊤⇒γ and undermining attacks can be modelled as a rebuttals.

12 We note that D is a set of rules whereas D(a) is a function mapping arguments to subsets of D. This will not cause any confusion.

13 Some works [21,39,41] have studied forms of unrestricted rebut where the conclusion of the attacked argument need not be the head of a defeasible rule.

14 A preference-dependent notion of undercutting attack was for example also used by [11] in the context of deontic logic, with the aim of modelling a cautious, ‘austere’ style of reasoning.

15 Unlike [50], in our contribution we do not distinguish between defeats with contrary formulas from those with contradictory formulas. See a justification of our approach in the context of a richer discussion in Section 5.

16 [50,53] distinguish between rebuts where Conc(b)∈Conc(a)‾ and rebuts where Conc(b)∉Conc(a)‾. The latter they call contrary-rebut and treat differently, since in these works contrary-rebuts result in defeats regardless of the relative strength of a and b. We will have more to say about this in Section 5.

17 Dung [29] showed that for every AF (Arg,⇝) there is a unique grounded extension, which we denote by groun((Arg,⇝)).

18 In [41, Example 6.1] one finds an example of a violation of the related postulate of crash-resistance that is caused by an inadequate treatment of incomparable priorities instead of inconsistencies.

19 Notice that this notion of syntactic disjointedness would have to be more explicitly spelled out when generalizing the results of this paper to a first order language. For an example of how to do this, cf. [27, Notation 3].

20 A related rationality standard is Crash-Resistance. It follows from Non-Interference under some very weak criteria on the strict rule base (cf. [20]).

21 We here phrase Non-Interference in terms of the semantics rather than in terms of the nonmonotonic entailment. In the setting of this paper, the latter formulation is a direct corollary of our formulation.

22 Another recently proposed strategy to obtain non-interference for prioritized settings with the grounded semantics is to use a generalized non-restricted form of rebut [41].

23 [58] observes that filtering out inconsistent arguments does not work when using the last link lifting. Unfortunately, even though we show that for a wide class of frameworks filtering out inconsistent arguments is unnecessary, these results do not generalize to the last link lifting either, as we show in Example 21.

24 In Section 5 we give a detailed comparison between these assumptions and other definitions of contaposition found in the literature.

25 Note, however, that the requirement is non-trivial even in cases where S is induced by a logic, since some logics, such as the well-known 3-valued logic K3 lack theorems.

26 A similar observation has been made in [28], where it is shown that stable and preferred semantics coincide for deductive argumentation with defeasible premises.

27 To give substance to the intuition that checking membership of an admissible extension is less demanding than checking membership of a stable extension, it might be interesting to compare proof theories for these problems (see e.g. [49]) using criteria proposed to compare efficiency or computational demands of proof theories as proposed in e.g. [23,26].

28 This is not necessarily so in logic/sequent-based argumentation for specific choices of attack-forms as shown in [7].

29 In Section 5 we give a detailed comparison of the setting of [53] and the assumptions made in this paper.

30 Structural consequence relations ⊢S are also well-behaved in other respects, such as having a characteristic matrix (see [56, Theorem 3]).

31 This example was suggested to us by a reviewer.

32 We use the same ⊢ symbol in both Definitions 8 and 13: note, however, that its usage is disambiguated by the nature of the subscript and the nature of its left side, which is either a set of rules and a set of L-formulas (Def. 8), or a set of formulas in L and a set of rules (Def. 13).

33 This is the core mechanism behind constrained input-output logics [48].

34 In [39,41] an alternative solution to the problem of contamination is investigated that does not require to filter out inconsistent arguments but is instead based on a generalized notion of rebut attack.

35 This is the formulation from [50] while [19,53] only require “…then for some 1⩽i⩽n …”. [19] state the property explicitly only for ¬ instead of A‾. Similar comments apply to Cpos. The exact effect of the subtle differences between these different formulations of transposition, respectively contraposition and different assumptions on the contrariness relation A‾ are outside the scope of this paper but give rise to an interesting direction for future research.

36 Suppose ϕ′∈ϕ‾. Then {ψ,ϕ′}⊢Sϕ′ and so by S1, {ϕ,ϕ′}⊢Sψ′ for some ψ′∈ψ‾.

37 A similar example as Example 9 can be used to show that a weaker version of Cpos^⋆ which only demands “for some ψ′∈ψ‾ and for some ϕ′∈ϕ‾” instead of “for all ψ′∈ψ‾ and for all ϕ′∈ϕ‾” leads to problems with rationality postulates. Consider AS9′=({p,q,s,r,p′,q′,s′,r′},S9′,D9,∅,A‾,⪯9) where S9′={q→r′,r″→q′}, r‾=r″‾={r′}, r′‾={r,r″} and for all other atoms ϕ, ϕ‾={ϕ′} and ϕ′‾={ϕ}. We have the same arguments as in Example 9 and the counter-example to closure is thus analogous. Note that S9′ satisfies the weak version of Cpos.

38 We use this term in order to indicate that the addition of “irrelevant” information leads to contaminating effects (see also [14]). “Irrelevance” is disambiguated differently in the two versions considered.

39 On the most general level, [30] assumes that an argumentation system is built on the basis of an abstract logic (CN,CONTRA) over a language L where CN is a Tarskian consequence relation and CONTRA is a collection sets that is upward-closed and doesn’t contain CN(∅). A set Δ is inconsistent if Cn(Δ)∈CONTRA. For ASPIC+ with symmetric negation, [30] remarks that CONTRA can be instantiated by any set that contains both a formula and its contarry. In view of Definition 9, this can be seen to coincide with our notion of inconsistency.

40 Although it has been shown in [43] that, at least when preferences are not taken into account, ABA admits ASPIC+, and thus the chaining of defeasible rules, via a translation.

41 We compare here ASPIC+ with assumption-based argumentation with direct attacks, called ABAd in [40,44]. However, in the setting of this paper, the remarks made here generalize to assumption-based argumentation with reverse attacks (called ABAr in [40,44] and ABA+ in [25]), since it has been shown that ABAr and ABAd give rise to the same outcomes when a flat assumption-based framework satisfies S1 and S2 [42].

42 For simplicity we suppose here that our defeasible rules are ranked.

Acknowledgements

We would like to thank the anonymous reviewers of this manuscript for useful comments. The research of Jesse Heyninck was supported by the the FCT project RIVER (PTDC/CCI-COM/30952/2017), NOVA LINCS (UID/CEC/04516/2013) and the German National Science Foundation under the DFG-project CAR (Conditional Argumentative Reasoning) KE-1413/11-1.

Appendices

Appendix

AppendixProofs

The order of appearance of results in these appendix does not necessarily mirror the order of the statements of these results in the paper but is primarily based on logical dependency.

In order to avoid clutter, we will in the following proofs often slightly abuse notation by using ϕ‾ to denote an arbitrary representative of ϕ‾.

Appendix B.

Appendix B.Representation in terms of maximal consistent sets

B.1.The flat case

In what follows we shall assume a fixed AS=(L,S,D,K,A‾) where S satisfies S1 and S2. We start with some facts about set in ℘ˆ(D). We will usually write ⊢ instead of ⊢KS (see Def. 14).

Fact 10.

Where Δ∈℘ˆ(D) and Δ⊢ϕ, there is an argument a∈Arg(AS) with D(a)⊆Δ and conclusion ϕ.

Proof.

Suppose Δ∈℘ˆ(D) and Δ⊢ϕ. By Def. 14, K⊢S∪Δϕ. Thus, by Def. 8, there is a proof P of ϕ based on facts in K and rules in S and Δ. We construct a now exactly in terms of the structure of P. □

Fact 11.

Where Δ∈℘ˆ(D): K, head[Δ]⊢Sϕ iff Δ⊢ϕ.

Proof.

Suppose K, head[Δ]⊢Sϕ. By Def. 13 we have to show that K⊢S∪Δϕ. Since Δ∈℘ˆ(D) and by Def. 15, for each r∈Δ, Δ⊢ψ for all ψ∈body(r). So, K⊢S∪Δψ for all ψ∈body[Δ]. Also, by applying the rules in Δ we get K⊢S∪Δψ for all ψ∈head[Δ]. By our main supposition K⊢S∪Δϕ.

Suppose Δ⊢ϕ. By Def. 14, K⊢S∪Δϕ. By Def. 8, there is a proof P of ϕ from K using rules in S and Δ. Let {r1,…,rn}⊆Δ be the set of all defeasible rules used in P. Then, trivially, also K,{head(r1),…,head(rn)}⊢Sϕ. Thus, K, head[Δ]⊢Sϕ. □

Fact 12.

℘ˆ(D) is closed under ∪.

Proof.

Let Δ,Θ∈℘ˆ(D) and r∈Δ∪Θ. Without loss of generality let r∈Δ. Thus, r is triggered by Δ∈℘ˆ(Δ∪Θ) and so also by Δ∪Θ. □

Fact 13.

Where Δ∈℘ˆ(D) and r∈Δ, there is a Θ∈℘ˆ(Δ∖{r}) for which Θ⊢ψ for all ψ∈body(r).

Proof.

Consider a ψ∈body(r). Since Δ⊢ψ there is a proof P from Δ of ψ which we can, without loss of generality, assume to be minimal (in that no proper sub-proof of P establishes ψ). Let Δψ be the set of all r′∈Δ that are used in P. Note that if (modus ponens on) r were used in P, there would be a proper sub-proof of P that establishes ψ since ψ∈body(r). Thus, r∉Δψ. Moreover, since trivially all r′∈Δψ are used and thus triggered in P, Δψ∈℘ˆ(Δ).

Let Θ=⋃ϕ∈body(r)Δϕ where for each ϕ∈body(r), Δϕ is defined as in the previous paragraph. By Fact 12, Θ∈℘ˆ(Δ). Since for each ϕ∈body(r), Δϕ⊢ϕ, also Θ⊢ϕ for all ϕ∈body(r). Since r∉Δϕ for all ϕ∈body(r), also r∉Θ. □

Fact 14.

Where Δ∈℘ˆ(D) and r and r′ are two different rules in Δ, for any ⊂-minimal trigger sets Δr,Δr′∈℘ˆ(Δ) for r and r′ we have: (r′∉Δr∪{r} or r∉Δr′∪{r′}) and so (Δr∪{r}⊂Δ or Δr′∪{r′}⊂Δ).

Proof.

Let r,r′∈Δ such that r≠r′ and let Δr,Δr′∈℘ˆ(Δ) be ⊂-minimal trigger sets of r resp. r′. Assume Δr∪{r}=Δ. So, r′∈Δr. By Fact 13 and the ⊂-minimality of Δr, r∉Δr. Since Δr∈℘ˆ(D), there is a ⊂-minimal Δr′∈℘ˆ(Δr) that triggers r′. Since Δr′∪{r′}⊆Δr⊂Δ we are finished. □

Fact 15.

Where Δ∈℘ˆ(D) is finite and non-empty, there is a Δ′∈℘ˆ(Δ) such that Δ′⊂Δ and all r∈Δ are triggered by Δ′.

Proof.

Let Δ={r1,…,rn}∈℘ˆ(D). Assume for a contradiction that there is no Δ′∈℘ˆ(Δ) such that Δ′⊂Δ and Δ′ triggers all r∈Δ. This means that for each r∈Δ there is a π(r)∈Δ∖{r} for which there is no trigger set in Δ∖{r}. Thus, for r1 there is a π(r1)∈Δ∖{r1} such that every trigger set of π(r1) contains r1.

With some renumbering let π(r1)=r2. Also for r2 there is a π(r2) for which there is no trigger set in Δ∖{r2}. Suppose π(r2)=r1. However, then every trigger set of r2 includes r1 and every trigger set of r1 includes r2 which contradicts Fact 13 since then every trigger set of r1 includes r1.

After some renumbering let π(r2)=r3. Again, there is a π(r3) for which there is no trigger set in Δ∖{r3}. Suppose r2=π(r3). But then every trigger set (in Δ) of r2 contains r3 and vice versa, every trigger set of r3 (in Δ) contains r2. This is in contradiction with Fact 14. Suppose then that r1=π(r3). So any trigger set of r1 contains r3. However, every trigger set of r3 contains r2 and so every trigger set of r1 contains r2. Since every trigger set of r2 contains r1 this is impossible.

Altogether we can create a sequence ⟨r1,π(r1)=r2,π(r2)=r3,…,π(ri)=ri+1,…⟩. Since each member of the sequence is different from those before and since we only have n many rules we run into a contradiction. This means our assumptions was false. □

Fact 16.

Where Δ∈℘ˆ(D) is finite, Δ0=∅ and Δi+1 is the set of all r∈Δ triggered by Δi then Δ=⋃i⩾0Δi, ⟨Δi⟩i⩾0 is ⊆-monotonically increasing, and there is a minimal fixed point Δk=Δk+1.

Proof.

Note that in our construction for each i⩾0, Δi∈℘ˆ(D). Therefore also Δi+1⊇Δi. A fixed point is reached after finitely many steps since Δ is finite.

“⊆”: Let r∈Δ. Thus, there is a Λ0∈℘ˆ(Δ) that triggers r. By Fact 15, there is a Λ1∈℘ˆ(Λ0) that triggers every r∈Λ0 and for which Λ1⊂Λ0. We proceed iteratively: for Λi there is a Λi+1∈℘ˆ(Λi) that triggers each r∈Λi and Λi+1⊂Λi. Since ⟨Λi⟩i⩾0 is a ⊂-monotonically decreasing sequence and Λ0 is finite, we reach a minimal point Λl=∅. Note that by the construction, ⋃i=0l−1Λi⊆⋃i⩾0Δi. So, r∈⋃i⩾0Δi.

“⊇”: This holds trivially. □

Fact 17.

Where Δ∈℘ˆ(D) and ∅⊂Δ′⊆Δ, there is an r∈Δ′ such that some Δ″∈℘ˆ(Δ∖Δ′) triggers r.

Proof.

Let r0∈Δ′. Thus, there is a finite Δ0∈℘ˆ(Δ) that triggers r0. In view of Fact 13 we can safely assume r0∉Δ0. Let Δ0′=Δ′∩Δ0. If Δ0′=∅ we are finished since Δ0⊆Δ∖Δ′ triggers r0. Otherwise, for an arbitrary r1∈Δ0′ there is a Δ1∈℘ˆ(Δ0) that triggers r1. In view of Fact 13 we can safely assume r1∉Δ1. Let Δ1′=Δ′∩Δ1⊂Δ0′. If Δ1′=∅ we are done since then Δ1⊆Δ∖Δ′ triggers r1. Otherwise we continue in the same manner. Since ⟨Δi′⟩i⩾0 is a ⊂-decreasing sequence of finite sets, we reach the point where Δi′=∅ after finitely many steps at which point Δi triggers ri, Δi⊆Δ∖Δ′ and ri∈Δ′. □

The next result offers a Lindenbaum-like construction of maximal consistent sets of defeasible rules in ℘ˆ(D).

Lemma 1.

Where Θ∈℘ˆ(D) is consistent, there is a maximal consistent Δ∈℘ˆ(D) for which Δ⊇Θ.

Proof.

Let D be enumerated by ⟨r1,r2,…⟩. Where L=⟨l1,l2,…⟩ is a list let top(L)=l1. Let tr(Λ)=⟨rj1,rj2,…⟩ be a list of all the rules triggered by Λ except those in Λ (where ji<ji+1 for every index). We construct Δ=df⋃α⩾0Θα by a transfinite induction (bounded by ω2) as follows: (Θ0;R0;X0)=df(Θ;tr(Θ);∅), and for all successor ordinals α+1,

(Θα+1;Rα+1;Xα+1)=df(Θα∪{top(Rα)};tr(Θα∪{top(R)});Xα)if Θα∪{top(Rα)} is consistent,(Θα;Rα∖{top(Rα)};Xα∪{top(Rα)})else

and for all limit ordinals α, (Θα;Rα;Xα)=df(⋃β<αΘβ;⋂β<αRβ;⋃β<αXβ).

We first show (inductively) that each Θα is consistent. For Θ0 this holds by the supposition. For the inductive step consider first a successor ordinal α and suppose Θα is consistent. Then, by the construction also Θα+1 is consistent. Consider now a limit ordinal α and suppose for all β<α, Θβ is consistent. Assume for a contradiction that that Θα is inconsistent. Thus, there is a finite Θ′∪{r}⊆Θα such that Θ′⊢head(r)‾. Thus, there is a β<α for which Θ′∪{r}⊆Θβ. But then Θβ is inconsistent in contradiction to our inductive hypothesis.

Note also that in view of the construction (and Fact 12) ⟨Θα⟩α⩾0 is a monotonically ⊆-increasing sequence of sets in ℘ˆ(D). By Fact 12, Δ∈℘ˆ(D).

Suppose now that Δ is not consistent. Thus there is a rule ri∈Δ and a Δ′∈℘ˆ(Δ) for which Δ′⊢ψ‾ where ψ∈head(ri). Thus, there is a Θα for which Δ′⊆Θα. Also, since ri∈Δ, either ri∈Θβ where β=0, or for some β⩾1, ri=top(Rβ) and Θβ+1=Θβ∪{ri}. Clearly, Θβ⊆Θα or Θα⊆Θβ. So either, Θβ+1⊢ψ‾ or Θα⊢ψ‾ in contradiction to the consistency of Θβ+1 respectively of Θα. So Δ is consistent.

Suppose Δ is not maximal consistent. Thus, there is a consistent Λ∈℘ˆ(D) for which Δ⊂Λ. Let Λ∖Δ={r1′,…,rn′,…}. By Fact 17, some ri=rj′ is triggered by Δ. Thus, there is a Δ′∈℘ˆ(Δ) for which Δ′⊢ψ for all ψ∈body(ri). Thus, there is a minimal α for which Δ′⊆Θα. Note that ri′ is triggered by Θα and that ri′∉Xβ for any β⩾0 (since otherwise ⊥Λ by item (ii)). But since ri never enters Xl, for some m⩽i, ri=top(Rα+m) and by the consistency of Θα+m∪{ri}, it is added to Θα+m+1. This is a contradiction. □

In the following, given some proof P based on some (strict and/or defeasible) inference rules R, let topD(P) denote the set of the top (or last) defeasible rules used in P.

Fact 18.

If Δ∈℘ˆ(D), Θ∈MCS(D), and ⊥(Δ∪Θ), then Θ⊢ψ‾ for some ψ∈head[Δ].

Proof.

Since ⊥(Δ∪Θ), i.e., Θ∪Δ is inconsistent, there is a Λ∈℘ˆ(Θ∪Δ) for which Λ⊢ϕ‾ where ϕ∈head(r) for some r∈Θ∪Δ. If Λ⊆Θ, by the consistency of Θ, r∈Δ and so we are done. Otherwise, let Λ∖Θ={r1,…,rn}. By Fact 17, there is an ri∈Λ∖Θ for which some set in ℘ˆ(Λ∩Θ) triggers ri. Thus, Θ triggers ri and so Θ∪{ri}∈℘ˆ(D) is inconsistent (by the ⊆-maximality of Θ). Thus, there is a Ω∈℘ˆ(Θ∪{ri}) such that Ω⊢ψ‾ for some r′∈Θ∪{ri} such that ψ=head(r′).

If ri∉Ω then r′=ri by the consistency of Θ and our proof is finished.

Suppose now that ri∈Ω. Let P be a proof of ψ‾ from Ω. Let topD(P)={rk1,…,rkm}. Suppose first that ri∉topD(P). But then there is a proof of ψ‾ from Θ since each rki∈Θ and as such is triggered by some Θi∈℘ˆ(Θ). Let Θi+=Θi∪{rki}. Thus, ⋃1⩽i⩽mΘi+⊢ψ‾. Thus, by the consistency of Θ, r′=ri and we are done. Suppose now that ri∈topD(P). Without loss of generality, suppose ri=rkm. So, K,head(rk1),…,head(rkm)⊢Sψ‾. By S1, K,head(rk1),…,head(rkm−1),ψ⊢Shead(ri)‾.

If ri=r′, by S2, K,head(rk1),…,head(rkm−1)⊢Shead(ri)‾ and thus Θ1+,…,Θm−1+⊢head(ri)‾. Since, in view of Fact 12, Θ1+∪⋯∪Θm−1+∈℘ˆ(Θ) our proof is finished.

If ri≠r′, then r′∈Θ and since Θ triggers r′, there is a Θr′∈℘ˆ(Θ) that triggers r′. Thus, Θ1+,…,Θm−1+,Θr′∪{r′}⊢head(ri)‾. Since, in view of Fact 12, Θ1+∪⋯∪Θm−1+∪Θr′∪{r′}∈℘ˆ(Θ), our proof is finished. □

Lemma 2.

Where Θ∈℘ˆ(D) is consistent, there are no a,b∈Arg(Θ) such that a attacks b.

Proof.

Where a,b∈Arg(Θ), suppose a attacks b. Thus, there is an r∈D(b) such that D(a)⊢head(r)‾. This is in contradiction to the consistency of Θ since D(a)∈℘ˆ(Θ) and r∈Θ. □

Lemma 3.

Where Θ∈MCS(D), Arg(Θ)∈stab(AS) and Arg(Θ)∈stab⊤(AS).

Proof.

Let A=Arg(Θ), where Θ∈MCS(D). By Lemma 2, A is conflict-free. Consider now some b∈Arg(AS)∖A. Thus, D(b)∖Θ≠∅. Notice that since Θ∈MCS(D), ⊥(D(b)∪Θ) and hence, by Fact 18, there is a r′∈D(b) for which Θ⊢head(r′)‾. Thus, there is a Θ′∈℘ˆ(Θ) such that there is a proof from Θ′ with conclusion head(r′)‾. The corresponding argument a∈A with D(a)⊆Θ′ (see Fact 10) attacks b. □

The next fact follows since any defeater/attacker of a sub-argument of some argument a also defeats/attacks a.

Fact 19

Fact 19(Sub-Argument Closure).

Where A is a complete extension of AS, a∈A and b is a sub-argument of a, b∈A.

Fact 20.

Where A⊆Arg(AS) is closed under sub-arguments and r∈D[A], there is an argument a∈A with top-rule r.

Proof.

Suppose r∈D[A]. Thus, there is a b∈A with r∈D(b). Thus, there is a a∈Sub(b) with top-rule r. By sub-argument closure, a∈A. □

Lemma 4.

Where A∈pref(AS) (resp. A∈pref⊤(AS)), D[A] is consistent.

Proof.

Suppose Θ=D[A] is inconsistent. Thus, there is a finite Δ∈℘ˆ(Θ) and an r∈Θ for which Δ⊢head(r)‾.

Since Δ∪{r}⊆D[A] and by the sub-argument closure of A (Fact 19) and by Fact 20, for each r′∈Δ∪{r} there is a ar′∈A with top-rule r′. Let Δr′=D(ar′).

Since Δ⊢head(r)‾, Δ⋆=⋃{Δr′∣r′∈Δ∪{r}} is inconsistent and by Fact 12 Δ⋆∈℘ˆ(Θ). Let Δ⋆=⋃i=0kΔi⋆=Δk⋆ as in Fact 16. Thus, there is a minimal 1⩽l⩽k for which Δl⋆ is inconsistent. Let Δl⋆∖Δl−1⋆={rl1,…,rlm}. Let l′ be maximal in {l1,…,lm} such that Λ=Δl−1⋆∪{rl1,…,rl′} is consistent while Λ∪{rl′+1} is inconsistent. So, Λ∪{rl′+1}⊢head(r′)‾ for some r′ in Λ∪{rl′+1}. Note that Λ,Λ∪{rl′+1}∈℘ˆ(D). By Fact 11 (and the compactness of ⊢S), K′, head[Λ], head(rl′+1)⊢Shead(r′)‾ for some finite K′⊆K and by S1 and S2, K′, head[Λ]⊢Shead(rl′+1)‾.

Where Λ={r1′,…,rm′} and K′={κ1,…,κm} we have b=κ1,…,κm,ar1′,…,arm′→head(rl′+1)‾∈Arg⊤(AS) attacks arl′+1. Thus, there is a c∈A that attacks b. But this attack must take place in some ari′ in contradiction to the conflict-freeness of A. □

Lemma 5.

For every A∈pref(AS) (resp. A∈pref⊤(AS)) there is a Θ∈MCS(D) such that A=Arg(Θ). In signs: pref(AS)⊆Arg[MCS(D)] (resp. pref⊤(AS)⊆Arg[MCS(D)]).

Proof.

Suppose A∈pref(AS) (resp. A∈pref⊤(AS)) and let Θ=D[A]. By Lemma 4, Θ is consistent.

Assume now that it is not maximal consistent. By Lemma 1, there is a maximal consistent Δ∈℘ˆ(D) for which Δ⊃Θ. By Lemma 3, Arg(Δ) is stable and thus also admissible which contradicts the maximality of Θ. □

The following theorem follows immediately with Lemma 3 and Lemma 5.

Theorem 10.

Where AS=(L,S,D,K,A‾) and S satisfies S1 and S2,

pref(AS)=stab(AS)=pref⊤(AS)=stab⊤(AS)={Arg(Θ)∣Θ∈MCS(D)}.

B.2.Grounded semantics for flat frameworks

We first show that the free set exists (see Def. 19).

Lemma 6.

Where Ξ=⋂MCS(D), there is a unique ⊂-maximal Δ∈℘ˆ(D) that is contained in Ξ.

Proof.

Let {Δ1,…,Δn} be the set of all Δi∈℘ˆ(D) contained in Ξ. Then, by Fact 12, also Δ=⋃i=1nΔi∈℘ˆ(D). □

The following lemma shows that the free set in D can be constructed in a bottom-up iterative way.

Lemma 7.

Free(D)=⋃i⩾0Θi where Θ0=∅ and Θi+1 is the set of all r∈⋂MCS(D) that are triggered by Θi.

Proof.

“⊇”: This follows since by its construction, ⋃i⩾0Θi∈℘ˆ(D) and ⋃i⩾0Θi⊆MCS(D).

“⊆”: Assume for a contradiction that Free(D)∖⋃i⩾0Θi≠∅. By Fact 17, there is a r∈Free(D)∖⋃i⩾0Θi that is triggered by ⋃i⩾0Θi. But then r∈⋃i⩾0Θi. This is a contradiction. □

Lemma 8.

For all Δ∈℘ˆ(D), if ⊥(Δ∪Free(D)) then ⊥Δ.

Proof.

Suppose Δ∈℘ˆ(D) is consistent. By Lemma 1, there is a Ω∈MCS(D) such that Δ⊆Ω. Thus, Free(D)⊆Ω and so Δ∪Free(D) is consistent. □

Lemma 9.

There is no a∈Arg⊤(AS) that attacks some argument in Arg(Free(D)).

Proof.

Suppose some a∈Arg(AS) attacks a b∈Arg(Free(D)). Thus, D(a)⊢head(r)‾ for some r∈D(b). Thus, ⊥(D(a)∪Free(D)). By Lemma 8, ⊥D(a). □

Theorem 11.

Where AS=(L,S,D,K,A‾) and S satisfies S1 and S2, Arg(Free(D))=groun⊤(AS).

Proof.

“⊇”: Note that groun⊤(AS)⊆A for every preferred⊤ extension A of AS. This means that groun⊤(AS)⊆⋂pref⊤(AS) and by Theorem 10, groun⊤(AS)⊆Arg(⋂MCS(D)). Also D[groun⊤(AS)]∈℘ˆ(D) and so groun⊤(AS)⊆Arg(Free(D)).

“⊆”: By Lemma 9, Arg⊤(Free(D)) has no attackers in Arg⊤(AS). Thus, trivially Arg(Free(D))⊆groun⊤(AS). □

In view of Theorem 11 and Lemma 9 we have:

Corollary 1.

Where AS=(L,S,D,K,A‾) and S satisfies S1 and S2, groun⊤(AS) is the set of arguments in Arg⊤(AS) that have no attackers in Arg⊤(AS).

B.3.The prioritized case

In what follows we assume a fixed AS=(L,S,D,K,A‾,⩽) where S satisfies S1 and S2.

Fact 21.

Where Δ,Θ,Λ∈℘ˆ(D),

(1) R[Δ]⩾R[Δ∪Θ]
(2) if R[Δ]⩾R[Λ] and R[Θ]⩾R[Δ∪Λ] then R[Δ∪Θ]⩾R[Λ].

We again provide a Lindenbaum-like construction for showing the existence of maximal R-consistent superset of R-consistent sets in ℘ˆ(D).

Lemma 10.

Where Θ∈℘ˆ(D) is R-consistent, there is a maximal R-consistent Δ∈℘ˆ(D) such that Δ⊇Θ.

Proof.

Suppose D={r1,…,rn}. For any set of rules Ξ, let the function top(Ξ) return the rule with the lowest index. Our construction is similar to the one in Lemma 1.

We again let tr(Λ) be the set of all rules in D triggered by Λ except those in Λ. Where r∈tr(Λ) let trS(Λ,r)=df{Λ′∈℘ˆ(Λ)∣Λ′ triggers r}. Let trR(Λ,r)=dfmax({R[Λ′]∣Λ′∈trS(Λ,r)}). Finally, let trmax(Λ)=df{r∈tr(Λ)∣trR(Λ,r)=max({trR(Λ,r′)∣r′∈tr(Λ)})}. Informally, trmax(Λ) contains those rules triggered by Λ whose strongest trigger sets in Λ are strongest as compared to the strongest trigger sets of other triggered rules. We now construct Δ=df⋃α⩾0Θi via a transfinite induction (bounded by ω2) as follows: (Θ0;R0;X0)=df(Θ;trmax(Θ);∅) and, where α is a successor ordinal,

(Θα+1;Rα+1;Xα+1)=df(Θα∪{top(Rα)};trmax(Θα∪top(R));Xα)if not ⊥(Θα∪{top(Rα)})(Θα;Rα∖{top(Rα)};Xα∪{top(Rα)})else

and (Θα;Rα+1;Xα+1)=df(⋃β<αΘβ;⋂β<αRβ;⋃β<αXβ), where α is a limit ordinal.

(i) We first show (inductively) that each Θα is consistent. For Θ0 this holds by the supposition. For the inductive step consider first a successor ordinal α and suppose Θα is consistent. Then, by the construction also Θα+1 is consistent. Consider now a limit ordinal α and suppose for all β<α, Θβ is consistent. Assume for a contradiction that that Θα is inconsistent. Thus, there is a finite Θ′∪{r}⊆Θα such that Θ′⊢head(r)‾. Thus, there is a β<α for which Θ′∪{r}⊆Θβ. But then Θβ is inconsistent in contradiction to our inductive hypothesis.
(ii) In view of the construction (and Fact 12), ⟨Θα⟩α⩾0 is a monotonically ⊆-increasing sequence of sets in ℘ˆ(D). Also by Fact 12, Δ∈℘ˆ(D).
(iii) Our main work now is to show that each Θα is R-consistent for each ordinal α. This can be done inductively, where the base case holds by definition.

For the inductive step we first consider a limit ordinal α. Suppose Θβ is R-consistent for each β<α. Assume for a contradiction that Θα is not R-consistent. Thus, there is a Λ∈℘ˆ(D) such that ⊥(Θα∪Λ) and for all Θ′∈℘ˆ(Θα), R[Λ]>R[Θ′] if ⊥(Λ∪Θ′). Since ⊥(Θα∪Λ), by compactness of ⊢S there is a finite Θ″⊆Θα such that ⊥(Θ″∪Λ). Thus, there is a β<α for which Θ″⊆Θβ and so ⊥(Θβ∪Λ). Since by the inductive hypothesis, Θβ is R-consistent, there is a Θ′∈℘ˆ(Θβ)⊆℘ˆ(Θα) such that ⊥(Θ′∪Λ) and R[Θ′]⩾R[Λ], which is a contradiction.

We now consider a successor ordinal α=β+1. Assume for a contradiction that Θα=Θβ∪{r′} is not R-consistent. Therefore there is a Δ∈℘ˆ(D) that is inconsistent with Θα such that (†) for all Θ′∈℘ˆ(Θα) that are inconsistent with Δ, R[Δ]>R[Θ′]. If ⊥(Δ∪Θβ) then, by the inductive hypothesis, there would be a Θ″∈℘ˆ(Θβ)⊆℘ˆ(Θα) that is inconsistent with Δ and for which R[Θ″]⩾R[Δ]. So, Δ∪Θβ is consistent.

Since ⊥(Θα∪Δ), there is a Λ∈℘ˆ(Δ∪Θα) and a r∈Δ∪Θα for which Λ⊢ϕ‾, where head(r)=ϕ. Let P be the corresponding proof.

Let (TopD(P)∪{r})∩Θα={r1,…,rm} and (TopD(P)∪{r})∖Θα={rm+1,…,rn}. For each 1⩽j⩽m there is a R-maximal trigger set Ωj∈℘ˆ(Θβ). Let Ωj+=Ωj∪{rj}∈℘ˆ(Θα). Also, for each m<j⩽n there is a trigger set Δj∈℘ˆ(Δ). Let Δj+=Δj∪{rj}∈℘ˆ(Δ). Note that n>m since otherwise ⊥Θα.

By Fact 12, ⋃j=1mΩj+∈℘ˆ(Θα) and ⋃j=m+1nΔj+∈℘ˆ(Δ). By Fact 21, since ⊥(⋃j=1mΩj+∪Δ) and by (†), R[⋃j=1mΩj+]<R[Δ]⩽R[⋃j=m+1nΔj+].

Recall that Θα=Θβ∪{r′}. Without loss of generality let r′=rm. (Note for this that r′ must be among TopD(P) since otherwise TopD(P)∩Θα⊆Θβ and so ⋃j=1mΩj+⊆Θβ and hence ⊥(Θβ∪Δ) which was already shown to be impossible.)

Assume now for a contradiction that R[Δj+]>R[Ωm+] for some m<j⩽n. We now show that this means that this would imply that r′ is not added to Θβ but rather some r″∈Δj+. To see this let Δj+=⋃i=1kΔi as in Fact 16. Note that Δj+∖Θβ≠∅ since rj∉Θα. Thus, there is a minimal 1⩽l⩽k for which Δl∖Θβ≠∅. Thus, any r″∈Δl∖Θβ is triggered by Θβ: by ∅ if l=0 resp. by Δl−1⊆Θβ if l>0. Since not ⊥(Θβ∪{r″}) (recall that Θβ∪Δ is consistent), R[{r″}]⩾R[Δj+]>R[Ωm+] resp. R[Δl−1]⩾R[Δj+]>R[Ωm+], and Ωm is an R-maximal trigger set of r′, r′∉trmax(Θβ) which is a contradiction. Thus, (⋆) R[Δj+]⩽R[Ωm+] for every m<j⩽n.

Since ⋃j=1m−1Ωj+⊆Θβ, ⊥(Θβ∪Δ∪Ωm+). Since Θβ is by the inductive hypothesis R-consistent, there is a Θ″∈℘ˆ(Θβ) for which ⊥(Θ″∪Δ∪Ωm+) and R[Θ″]⩾R[Δ∪Ωm+]. By (⋆), Δj+⊆Δ and Fact 21, R[Θ″∪Ωm+]⩾R(Δ). Since, by Fact 12, Θ″∪Ωm+∈℘ˆ(Θα) this is a contradiction.

This concludes our inductive argument that each Θα is R-consistent. We now show that Δ is R-consistent. Suppose for this that ⊥(Δ∪Ω) for some Ω∈℘ˆ(D). Thus, there is a Δ′∈℘ˆ(Δ) and a r∈Δ′∪Ω such that Δ′∪Ω⊢head(r)‾ and so ⊥(Δ′∪Ω). Thus, there is a minimal β for which Δ′⊆Θβ. Thus, ⊥(Θβ∪Ω) and since Θβ is R-consistent, there is a Θβ′∈℘ˆ(Θβ) for which ⊥(Θβ′∪Ω) and R[Θβ′]⩾R[Ω]. Since Θβ′∈℘ˆ(Δ) this shows that Δ is R-consistent.

We still have to show that Δ is maximal R-consistent. Assume for a contradiction that there is an R-consistent Δ′∈℘ˆ(D) for which Δ′⊃Δ. By Fact 17, there is an r∈Δ′∖Δ that is triggered by Δ. So, there is a minimal β such that Δβ triggers r. Since Δ is consistent with r and therefore every Δα is consistent with r, r is never moved to Xα in our construction. Since r will eventually become top(Rα) for some α⩾β and so be in Θα+1, which is a contradiction to r∉Δ. □

As expected, maximal R-consistent sets are maximal consistent.

Lemma 11.

MCSR(D)⊆MCS(D).

Proof.

We show that an R-consistent set that is not maximally consistent cannot be maximally R-consistent. Suppose for this that Δ∈℘ˆ(D) is R-consistent. Suppose Θ∈MCS(D) and Θ⊃Δ. Since Θ∈℘ˆ(D), with Fact 17 there are rules in Θ∖Δ that are triggered by Δ and that are consistent with Δ (in view of the consistency of Θ). In our construction in the proof of Lemma 10 some rules in tr(Δ)∩Θ contain thus rules consistent with Δ. Some of these will eventually end up in top(trmax(Δ)) (after inconsistent maximally triggered rules have been removed to Xα). Since adding such rules to Δ results in a R-consistent set (as shown in the proof of Lemma 10), Δ is not maximal R-consistent. □

In fact, the maximal R-consistent sets are exactly those maximal consistent sets that are R-consistent:

Proposition 1.

Λ∈MCSR(D) iff Λ∈MCS(D) and Λ is R-consistent.

Proof.

The left-to-right direction is Lemma 11. Suppose Λ∈MCS(D) is R-consistent and assume Θ∈℘ˆ(D) is R-consistent and Θ⊃Λ. But then, by Lemma 11, Θ∈MCS(D) which contradicts that Λ∈MCS(D). □

We now investigate how maximal R-consistent sets are related to preferred and stable extensions.

Lemma 12.

Where Θ∈MCSR(D), Arg(Θ)∈stab(AS).

Proof.

By Lemma 11, Θ∈MCS(D) and so by Lemma 2, A=Arg(Θ) is conflict-free.

Suppose b∈Arg∖A. Thus, D(b)∈℘ˆ(D)∖℘ˆ(Θ). Since Θ is maximal consistent, by Fact 18, ⊥(D(b)∪Θ). Let Δ∈℘ˆ(D(b)) be ⊂-minimal with the property ⊥(Δ∪Θ). Thus, R[D(b)]⩽R[Δ].

Since Θ∈MCSR(D), there is a Θ′∈℘ˆ(Θ) such that ⊥(Θ′∪Δ) and R[Θ′]⩾R[Δ]. Thus, there is a Λ∈℘ˆ(Θ′∪Δ) and a r∈Θ′∪Δ for which Λ⊢ϕ‾, where ϕ=head(r). Let P a proof of ϕ‾ from Λ. Let TopD(P)={r1,…,rn} with head(ri)=ϕi for each 1⩽i⩽n and corresponding sub-proofs Pi with top-rules ri. Thus, K,ϕ1,…,ϕn⊢Sϕ‾.

We will assume that our proof P is such that r∉TopD(P). Note that one can simply transform a proof that doesn’t have this property in the following way. Assume that r=ri for some 1⩽i⩽n, say i=1. By S2, K,ϕ2,…,ϕn⊢Sϕ‾. We can now safely remove sub-proof P1 and obtain a proof of ϕ‾ from Λ with r∉TopD(P).

Suppose now that TopD(P)∖Θ′=∅ and so TopD(P)⊆Θ′. Then by the consistency of Θ, r∈Δ∖Θ. Since each r′∈TopD(P) has a trigger set in Θ′ we have Θ′⊢ϕ‾. So, by Fact 10, there is an argument a with D(a)⊆Θ′ and conclusion ϕ‾. This argument defeats b since in view of Fact 21, R[D(a)]⩾R[Θ′]⩾R[Δ]⩾R[D(b)].

Suppose now that TopD(P)∖Θ′≠∅. Let, after some renaming, TopD(P)∖Θ′={r1,…,rm}. Let for each m<i⩽n, Θi be a trigger set of ri in ℘ˆ(Θ′) and Θi+=Θi∪{ri}. Note that since Δ∈℘ˆ(D), for each 1⩽i⩽m there is a ⊂-minimal Δi∈℘ˆ(Δ) that triggers ri. Let Δi+=Δi∪{ri}.

Suppose first that Δi+⊊Δ for each 1⩽i⩽m. Thus, by the ⊂-minimality of Δ and the maximal consistency of Θ and since Θ∪Δi+ is consistent, Δi+⊆Θ. Thus, r∈Δ∖Θ since otherwise Θ⊢ϕ‾ for r∈Θ contra the consistency of Θ. Since Δ∈℘ˆ(D), there is a ⊂-minimal Δr∈℘ˆ(Δ) that triggers r. Assume Δr∪{r}⊊Δ. But then by the ⊂-minimality of Δ, Δr∪{r} is consistent with Θ and so Δr∪{r}⊆Θ which contradicts r∉Θ. So, Δr∪{r}=Δ. Note that any sub-argument c of b in which r is the top-rule will have D(c)=Δ and is defeated by an argument a∈Arg(Θ) with top defeasible rules {r1,…,rn} and D(a)=⋃i=1mΔi+∪⋃i=m+1nΘi+. Note for this that D(a)⊆Θ (since ⋃i=1mΔi+⊆Θ) and so a∈Arg(Θ). Also D(a)⊆Θ′∪Δ and since R[Θ′]⩾R[Δ] by Fact 21 also R[D(a)]⩾R[Δ].

Suppose now that there is a 1⩽i⩽m, say i=1, for which Δ1+=Δ. By Fact 14, for all 2⩽i⩽m, Δi+⊂Δ and by the ⊂-minimality of Δ and the maximal consistency of Θ, Δi+⊆Θ. Similarly, if r∈Δ there is a Δr∈℘ˆ(Δ) that triggers r and since r∉TopD(P), also r≠r1, and hence Δr+⊂Δ (where Δr+=Δr∪{r}). So Δr+⊆Θ. Else, if r∈Θ′∖Δ, there is a Δr∈℘ˆ(Θ′) that triggers r. Let also in this case Δr+=Δr∪{r}. Since K,ϕ1,…,ϕn⊢Sϕ‾, by S1, K,ϕ2,…,ϕn,ϕ⊢Sϕ1‾. Thus,

Δ2+,…,Δm+,Θm+1+,…,Θn+,Δr+⊢ϕ1‾.

Note that ⋃i=2mΔi+∪⋃i=m+1nΘi+∪Δr+⊆Θ. Let a∈Arg(Θ) be a proof of ϕ1‾ from ⋃i=2mΔi+∪⋃i=m+1nΘi+∪Δr+. Since any sub-proof c of b in which r1 is the top-rule will have D(c)=Δ, it is defeated by a since D(a)⊆Θ′∪Δ, R[Θ′]⩾R[Δ] and so, by Fact 21, R[D(a)]⩾R[D(c)]=R[Δ]. □

Fact 22.

If Θ∈℘ˆ(D) is consistent then Arg(Θ)=Arg⊤(Θ).

Lemma 13.

Where Θ∈MCSR(D), Arg⊤(Θ)∈stab⊤(AS).

Proof.

Let b∈Arg⊤(AS)∖Arg(Θ). By Lemma 12, there is an a∈Arg(Θ) that defeats b. By Fact 22, Arg(Θ)=Arg⊤(Θ) and so a∈Arg⊤(Θ). Also Arg⊤(Θ) is conflict-free since Arg(Θ) is conflict-free in view of Lemma 12. □

Definition 21.

Where Θ,Δ∈℘ˆ(D) we say that Θ is R-inconsistent with Δ iff ⊥(Θ∪Δ) and for all Θ′∈℘ˆ(Θ) for which ⊥(Θ′∪Δ), R[Θ′]<R[Δ].

Fact 23.

If Θ∈℘ˆ(D) is R-inconsistent (i.e., it is not R-consistent), then there is a Δ∈℘ˆ(D) such that Θ is R-inconsistent with Δ.

Fact 24.

If Θ∈℘ˆ(D) is R-inconsistent with Δ∈℘ˆ(D) then Δ is consistent.

Proof.

Assume for a contradiction that ⊥Δ. Since ∅∈℘ˆ(Θ), ⊥(∅∪Δ) and R[∅]⩾R[Δ], this is a contradiction to Θ being R-inconsistent with Δ. □

Fact 25.

If Θ∈℘ˆ(D) is R-inconsistent with Δ, Δ′∈℘ˆ(Δ) and ⊥(Θ∪Δ′) then Θ is R-inconsistent with Δ′.

Proof.

Consider an arbitrary Θ′∈℘ˆ(Θ) such that ⊥(Θ′∪Δ′). Thus, ⊥(Θ′∪Δ) and hence R[Θ′]<R[Δ]. Since by Fact 21 (Item 1), R[Δ]⩽R[Δ′], also R[Θ′]<R[Δ′]. Thus, Θ is R-inconsistent with Δ′. □

Lemma 14.

If A is a set of arguments in Arg(AS) that is closed under sub-arguments, D[A]=Θ is consistent and R-inconsistent with Δ∈℘ˆ(D) then there is a b∈Arg⊤(Δ∪Θ) and an a∈A such that (i) b defeats a and (ii) Sub(b)⊆A∪Arg(Δ).

Proof.

Let Θ=D[A] and suppose Θ is R-inconsistent with Δ. Since A is closed under sub-arguments, by Fact 20, for each r∈Θ there is an argument a∈A with top-rule r. Let AD be the set of all a∈A with defeasible top-rules.

Clearly, there is a set of arguments {a1,…,an}⊆AD that is closed under sub-arguments in AD such that ⊥(Δ∪D[{a1,…,an}]) and for all subsets A′⊂{a1,…,an}, Δ is consistent with D[A′]. For each 1⩽i⩽n let ϕi=head(ri) where ri is the top-rule of ai.

Let a∈{a1,…,an} be such that (i) R[D(a)]⩽R[D(ai)] for all 1⩽i⩽n and (ii) there is no b∈{a1,…,an} for which a∈Sub(b)∖{b}. Without loss of generality assume that a=an.

Since ⊥(Δ∪D[{a1,…,an}]), there is a r∈Δ∪D[{a1,…,an}] and a finite Δ′∈℘ˆ(Δ) such that Δ′∪D[{a1,…,an}]⊢head(r)‾. By Fact 12, Δ′∪D[{a1,…,an}]∈℘ˆ(D). Thus, by Fact 11, K′∪head[Δ′]∪{ϕ1,…,ϕn}⊢Shead(r)‾ for some finite K′⊆K. Since head(r)∈head[Δ′]∪{ϕ1,…,ϕn} and by S1, K′∪head[Δ′]∪{ϕ1,…,ϕn−1}⊢Sϕn‾ and Δ′∪D(a1)∪⋯∪D(an−1)⊢ϕn‾.

Let Δ′={r1′,…,rm′}. By Fact 25, Θ is R-inconsistent with Δ′. Since Δ′∈℘ˆ(D), by Fact 20, for each 1⩽i⩽m there is an argument di∈Arg⊤(Δ′) with top-rule ri′. Where K′={ψ1,…,ψl} let ki=⟨ψi⟩ for each 1⩽i⩽l. Let b=k1,…,kl,d1,…,dm,a1,…,an−1→ϕn‾∈Arg(Δ∪Θ). By the ⊂-minimality of {a1,…,an}, Δ′∪D[{a1,…,an−1}] is consistent and so b∈Arg⊤(AS).

Since Θ is R-inconsistent with Δ′ and ⊥(Δ′∪⋃i=1nD(ai)), R[Δ′]⩾R[⋃i=1nD(ai)]. Also, R[D(an)]⩽R[D(ai)] for all 1⩽i⩽n. Thus, R[D(an)]⩽R[⋃i=1n−1D(ai)]. Altogether, R[D(an)]⩽R[D(b)] and thus b defeats an. □

Lemma 15.

Where A∈pref(AS) (resp. A∈pref⊤(AS)), D[A] is consistent.

Proof.

Let AD be the set of all a∈A with defeasible top-rules. Suppose Θ=D[A] is inconsistent. Let {a1,…,an}⊆AD be a ⊂-minimal set of arguments in A that is closed under sub-arguments in AD (recall that A is closed under sub-arguments with Fact 19) and for which D[{a1,…,an}] is inconsistent. Note that by Fact 12, D[{a1,…,an}]∈℘ˆ(Θ). For each 1⩽i⩽n, let ri be the top-rule of ai, Δi=D(ai), and let ϕi=head(ri). Since ⊥D[{a1,…,an}], D[{a1,…,an}]⊢ϕl‾ for some 1⩽l⩽n. By Fact 11 and the compactness of S, there is a K′=⟨κ1,…,κm⟩⊆K for which K′,ϕ1,…,ϕn⊢ϕl.

Let 1⩽k⩽n be such that (†) R[Δk]⩽R[Δi] for all 1⩽i⩽n and such that there is no 1⩽k′⩽n for which ak∈Sub(ak′)∖{ak′}. By S1 and S2, K′,ϕ1,…,ϕk−1,ϕk+1,…,ϕn⊢Sϕk‾. Let b=⟨κ1⟩,…,⟨κm⟩,a1,…,ak−1,ak+1,…,an→ϕk‾. By the ⊂-minimality of {a1,…,an}, b∈Arg⊤(AS). By (†), D(b)⩾D(ak). Thus, b defeats ak and since A is preferred, there is a c∈A that defeats b. But this defeat must take place in some ai, where i∈{1,…,k−1,k+1,…,n}, in contradiction to the conflict-freeness of A. □

Lemma 16.

For every A∈pref(AS) (resp. A∈pref⊤(AS)) there is a Θ∈MCSR(D) such that A=Arg(Θ).

Proof.

Suppose A∈pref(AF) and let Θ=D[A]. Since for each a∈A, D(a)∈℘ˆ(D), by Fact 12 also Θ∈℘ˆ(D). By Lemma 15, Θ is consistent. By Fact 19, A is closed under sub-arguments.

Assume for a contradiction that Θ is not R-consistent. Thus by Fact 23, there is a Δ∈℘ˆ(D) such that Θ is R-inconsistent with Δ. Thus, by Lemma 14, there is a consistent b∈Arg(Θ∪Δ) such that (i) b defeats an a∈A with top-rule r and (ii) Sub(b)⊆A∪Arg(Δ).

Since A is preferred, there is a c∈A that defeats b and so R[D(c)]⩾R[D(b)]. By the conflict-freeness of A, the attack must be in some bi∈(Sub(b)∩Arg(Δ))∖A. Note that D(bi)∈℘ˆ(Δ) and so R[D(bi)]⩾R[Δ] by Fact 21. Since c defeats bi, R[D(c)]⩾R[D(bi)]⩾R[Δ]. Since D(c)∈℘ˆ(Θ) and ⊥(D(c)∪Δ) this contradicts the fact that Θ is R-inconsistent with Δ.

So, Θ is R-consistent. Suppose it is not maximal R-consistent. Thus, by Lemma 10, there is a maximal R-consistent Δ∈℘ˆ(D) for which Δ⊃Θ. Since by Lemma 12, Arg(Δ) is stable and Arg(Δ)⊃Arg(Θ) this contradicts that Arg(Θ) is preferred. □

Now we are in a position to prove Theorem 9:

Theorem 9.

For any AS=(L,S,D,K,A‾,⩽) where S satisfies S1 and S2,

{Arg(Θ)∣Θ∈MCSR(D)}=pref(AS)=stab(AS)=pref⊤(AS)=stab⊤(AS).

Proof.

Suppose A∈pref(AS) (resp. A∈pref⊤(AS)). By Lemma 16, D[A]∈MCSR(AS). By Lemmas 12 and 13, A∈stab(AS) and A∈stab⊤(AS).

Suppose A∈stab(AS) (resp. A∈stab⊤(AS)). As shown in [29], A∈pref(AS) (resp. A∈pref⊤(AS)). □

Appendix C.

Appendix C.Rationality postulates

C.1.Consistency and closure

The following corollary is a direct consequence of the characterization in terms of maximal consistent sets shown in Section B.

Corollary 2.

Where S satisfies S1 and S2, AS=(L,S,D,K,A‾,⩽) satisfies Direct Consistency, Consistency and Closure for stable and preferred semantics.

Proof.

We show closure. Suppose a1,…,an∈A∈pref(AS) and head(an),…,head(an)⊢Sϕ. By Theorem 10 resp. Theorem 9 and Lemma 11, D[A]∈MCS(D) and A=Arg(D[A]). Since also b=a1,…,an→ϕ∈Arg(D[A]), b∈A. □

C.2.Non-interference (Theorem 3)

In the following we assume that we have a uniform strict rule set S that serves as the basis for two argumentation systems AS=(L,S,D,K,A‾,⩽) and AS′=(L,S,D′,K′,A‾,⩽′). Also D∪K∪head[Δ]‾∪K‾ and D′∪K′∪head[Δ′]‾∪K′‾ are assumed to be syntactically disjoint, where Θ‾={ϕ‾∣ϕ∈Θ}. Finally, K∪K′ is assumed to be ⊢S-consistent.

Fact 26.

If Δ∈℘ˆ(D) is ⊢KS-consistent, then for any Θ⊆Δ, head[Θ]∪K is ⊢S-consistent.

Proof.

If Θ∪K is ⊢S-inconsistent, then there are ψ and ϕ∈ψ‾ such that Θ, K⊢Sϕ and Θ, K⊢Sψ. Since Δ∈℘ˆ(D), by Fact 11, also Δ⊢KSϕ and Δ⊢KSψ. Thus, Δ is ⊢KS-inconsistent. □

Lemma 17.

Where Δ∈℘ˆ(D∪D′) is ⊢K∪K′S-consistent, Δ∩D∈℘ˆ(D) is ⊢KS-consistent and Δ′∩D′∈℘ˆ(D′) is ⊢K′S-consistent.

Proof.

We first define

Δ1⊆Δ to be the set of rules r=ϕ1,…,ϕn⇒ψ for which ⊢K∪K′S⊢ϕk for each 1⩽k⩽n;
Δi+1⊆Δ to be the set of rules r=ϕ1,…,ϕn⇒ψ for which Δi⊢K∪K′Sϕk for each 1⩽k⩽n.

Since Δ∈℘ˆ(D∪D′), Δ=⋃i⩾1Δi. Also, by the construction, Δi∈℘ˆ(D∪D′) for each i⩾1. Clearly, also Δ∩D=⋃i⩾1Δi∩D.

We show that ⋃i⩾1Δi∩D∈℘ˆ(D) [resp. ⋃i⩾1Δi∩D′∈℘ˆ(D′)] via induction by showing that for each i⩾1, Δi∩D∈℘ˆ(D) and Δi∩D is ⊢KS-consistent [resp. Δi∩D′∈℘ˆ(D′) and Δi∩D′ is ⊢K′S-consistent]. Note that given Δi∩D∈℘ˆ(D) [resp. Δi∩D′∈℘ˆ(D′)], the ⊢KS-consistency of Δi∩D [resp. the ⊢K′S-consistency of Δi∩D′] follows directly from the ⊢K∪K′S-consistency of Δ.

Note that this is sufficient to show that Δ∩D∈℘ˆ(D) [resp. Δ∩D′∈℘ˆ(D′)] since then for every ϕ∈body[Δ∩D] there is an i⩾1 for which Δi∩D⊢KSϕ and so Δ∩D⊢KSϕ. Also the ⊢KS-consistency of Δ∩D [resp. the ⊢K′S-consistency of Δ∩D′] follows then directly from the ⊢K∪K′S-consistency of Δ.

(i=1). Let r=ϕ1,…,ϕn⇒ψ∈Δ1∩D. Then, ⊢K∪K′Sϕk for all 1⩽k⩽n. By Fact 11 and since trivially ∅∈℘ˆ(D∪D′), K∪K′⊢Sϕk. By the uniformity of the set of strict rules and since K∪K′ is ⊢S-consistent S, K⊢Sϕk and therefore Δ1∩D∈℘ˆ(D).
(i↦i+1). Suppose r=ϕ1,…,ϕn⇒ψ∈Δi+1∩D. Thus, Δi⊢K∪K′Sϕk for each 1⩽k⩽n. By Fact 11 and since Δi∈℘ˆ(D∪D′), K∪K′∪head[Δi]⊢Sϕk. Note that K′∪head[Δi∩D′] is ⊢K′S-consistent since by the inductive hypothesis Δi∩D′∈℘ˆ(D′) is consistent and thus with Fact 26 so is K′∪head[Δi∩D′]. Thus, by the uniformity of the set of strict rules S, K∪head[Δi∩D]⊢Sϕk. Since by the inductive hypothesis Δi∩D∈℘ˆ(D) and by Fact 11, Δi∩D⊢KSϕk. Therefore, Δi+1∩D∈℘ˆ(D).

□

Lemma 18.

If Δ∈℘ˆ(D), Δ′∈℘ˆ(D′), Δ′ is ⊢K′S-consistent, Λ∈℘ˆ(Δ∪Δ′), ϕ is syntactically disjoint from K′∪D′, and Λ⊢K∪K′Sϕ, then Λ∩D⊢KSϕ.

Proof.

Suppose Λ⊢K∪K′Sϕ and assume that Λ is ⊂-minimal with this property (and therefore finite). Let Λ=⋃i=1kΔi as in the proof of Fact 16. We now show by backwards induction on i that Δi+1∖Δi⊆D for each 0⩽i<k, where Δ0=∅.

We start with i=k−1. Let (Δi+1∖Δi)∩D={ϕ1,…,ϕn} and (Δi+1∖Δi)∩D′={ϕ1′,…,ϕm′}. Note that by the ⊂-minimality of Λ we have ϕ1,…,ϕn,ϕ1′,…,ϕm′,K,K′⊢Sϕ. By Fact 26 and since Δ′ is ⊢K′S-consistent, {ϕ1′,…,ϕm′}∪K′ is ⊢S-consistent and thus by uniformity, ϕ1,…,ϕn,K⊢Sϕ. By the ⊂-minimality of Λ, (Δi+1∖Δi)∩D′=∅.

For the inductive step consider some 0⩽i<k−1. Let (Δi+1∖Δi)∩D={ϕ1,…,ϕn} and (Δi+1∖Δi)∩D′={ϕ1′,…,ϕm′}. For each ψ∈body[Δi+2∖Δi+1], K,K′,ϕ1,…,ϕn,ϕ1′,…,ϕm′⊢Sψ. By the inductive hypothesis, Δi+2∖Δi+1⊆D. By Fact 26, {ϕ1′,…,ϕm′}∪K′ is ⊢S-consistent and thus by uniformity, ϕ1,…,ϕn,K⊢Sψ. Again, by the ⊂-minimality of Λ, (Δi+1∖Δi)∩D′=∅. □

Lemma 19.

Where Δ∈℘ˆ(D) and Δ′∈℘ˆ(D′) are ⊢KS-consistent resp. ⊢K′S-consistent, also Δ∪Δ′∈℘ˆ(D∪D′) is ⊢K∪K′S-consistent.

Proof.

Suppose Δ∈℘ˆ(D) and Δ′∈℘ˆ(D′) are ⊢KS-consistent resp. ⊢K′S-consistent. Clearly, Δ,Δ′∈℘ˆ(D∪D′). Thus, by Fact 12, Δ∪Δ′∈℘ˆ(D∪D′). Assume that Δ∪Δ′ is ⊢K∪K′S-inconsistent. By Fact 6, there is a Λ∈℘ˆ(Δ∪Δ′) and a ϕ∈head[Δ∪Δ′]‾ for which Λ⊢K∪K′Sϕ. Suppose, without loss of generality, that there is an r∈Δ for which ϕ∈head(r)‾. By Lemma 18 and since head(r)‾ is syntactically disjoint from K′∪D′, Λ∩D⊢KSϕ and hence Δ is ⊢KS-inconsistent, which is a contradiction. □

Proposition 2.

MCSS,K∪K′(D∪D′)={Λ∈℘ˆ(D∪D′)∣Λ∩D∈MCSS,K(D),Λ∩D′∈MCSS,K′(D′)}.

Proof.

“⊆”. Let Λ∈MCS(D∪D′). Let Λ′=Λ∩D′. We show that Λ′∈MCS(D′). By Lemma 17, Λ′∈℘ˆ(D′). For the same reason, Λ∩D∈℘ˆ(D) is consistent. Suppose there is a consistent Λ″⊃Λ′ for which Λ″∈℘ˆ(D′). By Lemma 19, Λ″∪Λ∈℘ˆ(D∪D′) is consistent. This is a contradiction since Λ″∪Λ⊃Λ. So, Λ′∈MCS(D′).

“⊇”. Let Δ∈MCS(D) and Δ′∈MCS(D′). By Lemma 19, Δ∪Δ′∈℘ˆ(D∪D′) is consistent. Assume there is a Λ∈℘ˆ(D∪D′) for which Λ⊃Δ∪Δ′ and Λ∈MCS(D∪D′). By the “⊆” direction, Λ∩D∈MCS(D) and Λ∩D′∈MCS(D′). Thus, Λ∩D⊃Δ or Λ∩D′⊃Δ′ which is a contradiction. □

Proposition 3.

MCSRS,K∪K′(D∪D′)={Λ∈℘ˆS,K∪K′(D∪D′)∣Λ∩D∈MCSRS,K(D),Λ∩D′∈MCSRS,K′(D′)}.

Proof.

“⊆”. Suppose Λ∈MCSR(D∪D′). Thus, by Lemma 11, Λ∈MCS(D∪D′). By Proposition 2, Λ∩D∈MCS(D) and Λ∩D′∈MCS(D′). We now show that Λ∩D∈MCSR(D). The case for Λ∩D′∈MCSR(D′) is analogous. By Proposition 1, we only have to show that Λ∩D is R-consistent.

Consider a Θ∈℘ˆ(D) for which ⊥((Λ∩D)∪Θ). Since Λ∈MCSR(D∪D′), there is a Λ′∈℘ˆ(Λ) for which ⊥(Λ′∪Θ) and R[Λ′]⩾R[Θ]. Since by Fact 21, for all Ω⊂Λ, R[Ω]⩾R[Λ] we can without loss of generality assume Λ to be ⊆-minimal with this property. Note that Λ′ is ⊢K∪K′S-consistent and therefore by Lemma 17, Λ′∩D∈℘ˆ(D) and Λ′∩D′∈℘ˆ(D′). We have to show that there is also a Λ″∈℘ˆ(Λ∩D) for which ⊥(Λ″∪Θ) and R[Λ″]⩾R[Θ]. If Θ is inconsistent we simply choose Λ″=∅. Consider the case in which Θ is consistent.

Since by Fact 12, Λ′∪Θ∈℘ˆ(D∪D′) and ⊥(Λ′∪Θ), by Lemma 19, (Λ′∩D)∪Θ is ⊢KS-inconsistent, or Λ′∩D′ is ⊢K′S-inconsistent. Since Λ∩D′ is ⊢K′S-consistent, (Λ′∩D)∪Θ is ⊢KS-inconsistent. Let Λ″=Λ′∩D, then, by Fact 21, R[Λ″]⩾R[Λ′]⩾R[Θ] and our proof is finished.

“⊇”. Suppose Δ∈MCSR(D) and Δ′∈MCSR(D′). By Lemma 11, Δ∈MCS(D) and Δ′∈MCS(D′). By Proposition 2, Δ∪Δ′∈MCS(D∪D′). By Proposition 1, we only have to show that Δ∪Δ′ is R-consistent. Suppose Θ∈℘ˆ(D∪D′) is such that ⊥(Θ∪Δ∪Δ′). We have to show that there is a Λ∈℘ˆ(Δ∪Δ′) for which ⊥(Λ∪Θ) and R[Λ]⩾R[Θ]. In case Θ is ⊢K∪K′S-inconsistent, Λ=∅ suffices.

Assume now that Θ is ⊢K∪K′S-consistent. Then, by Lemma 17, Θ∩D∈℘ˆ(D) and Θ∩D′∈℘ˆ(D′). By Fact 12, Δ∪(Θ∩D)∈℘ˆ(D) and Δ′∪(Θ∩D′)∈℘ˆ(D′). Since, also by Fact 12 Δ∪Δ′∪Θ∈℘ˆ(D∪D′), by Lemma 19, Δ∪(Θ∩D) is ⊢KS-inconsistent or Δ′∪(Θ∩D′) is ⊢K′S-inconsistent. Assume the former (the other case is analogous). Since Δ∈MCSR(D), there is a Λ∈℘ˆ(Δ)⊆℘ˆ(Δ∪Δ′) for which ⊥((Θ∩D)∪Λ) and R[Λ]⩾R[Θ∩D]. □

Theorem 3.

Where AS=(L,S,D,K,A‾,⩽), AS′=(L,S,D′,K′,A‾,⩽′) and AS⋆=(L,S,D∪D′,K∪K′,A‾,⩽⋆) where ⩽⋆ is such that ⩽⋆∩(D×D)=⩽ and ⩽⋆∩(D′×D′)=⩽′, S is uniform and satisfies S1 and S2, D∪K is syntactically disjoint with D′∪K′, and sem∈{pref,stab}, we have:

sem(AS⋆)={Arg(D[E]∪D[E′])⊆Arg(AS⋆)∣E∈sem(AS),E′∈sem(AS′)}.

Proof.

By Theorem 9, sem(AS⋆)={Arg(Δ)∣Δ∈MCSRS,K∪K′(D∪D′)}, sem(AS)={Arg(Δ)∣Δ∈MCSRS,K(D)}, and sem(AS′)={Arg(Δ)∣Δ∈MCSRS,K′(D′)}. Thus, by Proposition 3, sem(AS⋆)={Arg(D[E]∪D[E′])⊆Arg(AS⋆)∣E∈sem(AS),E′∈sem(AS′)}. □

C.3.Strict non-interference (Theorem 5)

In the following we assume two argumentation systems AS=(L,S,D,K,A‾,⩽) and AS′=(L,S′,D′,K′,A‾,⩽′) that are strictly syntactically disjoint.

Lemma 20.

Where Δ∈℘ˆS∪S′,K∪K′(D∪D′),

(1) Δ∩D∈℘ˆS,K(D) and Δ∩D′∈℘ˆS′,K′(D′),
(2) if Δ⊢K∪K′S∪S′ϕ and ϕ is syntactically disjoint with D′∪K′∪S′ then Δ∩D⊢KSϕ.

Proof.

Ad 2. Suppose Δ⊢K∪K′S∪S′ϕ. Thus, there is a (S∪S′∪Δ)-derivation of ϕ from K∪K′. Since ϕ is syntactically disjoint from S′∪K′∪Δ′, this proof does not make use of rules in (Δ∩D′)∪S′ and of premises in K′. Thus, K⊢S∪(Δ∩D)ϕ and so Δ∩D⊢KSϕ.

Ad 1. This follows immediately with Item 2. □

Lemma 21.

Where Δ∈℘ˆS,K(D) and Δ′∈℘ˆS′,K′(D′) are ⊢KS- resp. ⊢K′S′-consistent, also Δ∪Δ′∈℘ˆS∪S′,K∪K′(D∪D′) is ⊢K∪K′S∪S′-consistent.

Proof.

First note that by Fact 12, Δ∪Δ′∈℘ˆS∪S′,K∪K′(D∪D′). Assume that Δ∪Δ′ is ⊢K∪K′S∪S′-inconsistent. Thus, there is a Λ∈℘ˆS∪S′,K∪K′(Δ∪Δ′), a ϕ∈head[Δ∪Δ′], and a ψ∈ϕ‾ for which Λ⊢K∪K′S∪S′ψ. Suppose, without loss of generality, that there is an r∈Δ for which ϕ=head(r). By Lemma 20 and since ψ is syntactically disjoint from S′∪K′∪D′, Λ∩D⊢KSϕ‾ and hence Δ is ⊢KS-inconsistent. □

Proposition 4.

MCSS∪S′,K∪K′(D∪D′)={Λ∈℘ˆS∪S′,K∪K′(D∪D′)∣Λ∩D∈MCSS,K(D),Λ∩D′∈MCSS′,K′(D′)}.

Proof.

“⊆”. Let Λ∈MCSS∪S′,K∪K′(D∪D′) and Λ′=Λ∩D′. We show that Λ′∈MCSS′,K′(D′). By Lemma 20, Λ′∈℘ˆS′,K′(D′). Clearly, Λ′ is ⊢K′S′-consistent in view of the ⊢K∪K′S∪S′-consistency of Λ. For the same reason, Λ∩D∈℘ˆS,K(D) is ⊢KS-consistent. Suppose there is a ⊢K′S′-consistent Λ″⊃Λ′ for which Λ″∈℘ˆS′,K′(D′). By Lemma 21, Λ″∪Λ∈℘ˆS∪S′,K∪K′(D∪D′) is ⊢K∪K′S∪S′-consistent. This is a contradiction since Λ″∪Λ⊃Λ. So, Λ′∈MCSS′,K′(D′).

“⊇”. Let Δ∈MCSS,K(D) and Δ′∈MCSS′,K′(D′). By Lemma 21, Δ∪Δ′∈℘ˆS∪S′,K∪K′(D∪D′) is ⊢K∪K′S∪S′-consistent. Assume there is a Λ∈℘ˆS∪S′,K∪K′(D∪D′) for which Λ⊃Δ∪Δ′ and Λ∈MCSS∪S′,K∪K′(D∪D′). By the “⊆” direction, Λ∩D∈MCSS,K(D) and Λ∩D′∈MCSS′,K′(D′). Thus, Λ∩D⊃Δ or Λ∩D′⊃Δ′ which is a contradiction. □

Proposition 5.

MCSRS∪S′,K∪K′(D∪D′)={Λ∈℘ˆS∪S′,K∪K′(D∪D′)∣Λ∩D∈MCSRS,K(D),Λ∩D′∈MCSRS′,K′(D′)}.

Proof.

“⊆”. Suppose Λ∈MCSRS∪S′,K∪K′(D∪D′). Thus, by Lemma 11, Λ∈MCSS∪S′,K∪K′(D∪D′). By Proposition 4, Λ∩D∈MCSS,K(D) and Λ∩D′∈MCSS′,K′(D′). We now show that Λ∩D∈MCSRS,K(D). The case for Λ∩D′∈MCSRS′,K′(D′) is analogous. By Proposition 1, we only have to show that Λ∩D is R-consistent.

Assume Θ∈℘ˆS,K(D) for which ⊥((Λ∩D)∪Θ). Since Λ∈MCSRS∪S′,K∪K′(D∪D′), there is a Λ′∈℘ˆS∪S′,K∪K′(Λ) for which ⊥(Λ′∪Θ) and R[Λ′]⩾R[Θ]. So there is an r∈Λ′∪Θ for which Λ′∪Θ⊢K∪K′S∪S′ϕ where ϕ∈head(r)‾. We have to consider two cases: (a) r∈D and (b) r∈D′.

We first note that (b) is impossible since by Lemma 20 and since head(r)‾ is syntactically disjoint from (D∪S∪K), Λ′∩D′⊢K′S′ϕ and r∈Λ′∩D′ which implies that ⊥Λ′ (contradicting Λ∈MCSRS∪S′,K∪K′(D∪D′)).

Suppose thus (a). By Lemma 20, (Λ′∩D)∪Θ⊢KSϕ. Since by Fact 12, Λ′∪Θ∈℘ˆ(D∪D′), also by Lemma 20, (Λ′∩D)∪Θ∈℘ˆS,K(D). So, ⊥((Λ′∩D)∪Θ). Since Λ′∩D⊆Λ′, by Fact 21, R[Λ′∩D]⩾R[Λ′]⩾R[Θ]. This shows that Λ∩D is ⊢KS-R-consistent.

“⊇”. Suppose Δ∈MCSRS,K(D) and Δ′∈MCSRS′,K′(D′). By Lemma 11, Δ∈MCSS,K(D) and Δ′∈MCSS′,K′(D′). By Proposition 4, Δ∪Δ′∈MCSS∪S′,K∪K′(D∪D′). By Proposition 1, we only have to show that Δ∪Δ′ is R-consistent.

Suppose Θ∈℘ˆS∪S′,K∪K′(D∪D′) is such that ⊥(Θ∪Δ∪Δ′). Thus, there is an r∈Θ∪Δ∪Δ′ for which Θ∪Δ∪Δ′⊢K∪K′S∪S′ϕ where ϕ∈head(r)‾. We have two cases to consider: (a) r∈D and (b) r∈D′.

Suppose (without loss of generality) case (a). By Lemma 20, (Θ∩D)∪Δ⊢KSϕ and (Θ∩D)∪Δ∈℘ˆS,K(D). Thus, ⊥((Θ∩D)∪Δ). Since Δ∈MCSRS,K(D), there is a Λ∈℘ˆS,K(Δ) for which ⊥(Λ∪(Θ∩D)) and R[Λ]⩾R[Θ∩D]. Since Θ∩D⊆Θ, by Fact 21, R[Θ∩D]⩾R[Θ] and so R[Λ]⩾R[Θ]. Since Λ∈℘ˆS∪S′,K∪K′(Δ∪Δ′) this shows that Δ∪Δ′ is ⊢K∪K′S∪S′-R-consistent. □

Theorem 5. Where AS=(L,S,D,K,A‾,⩽), AS′=(L,S′,D′,K′,A‾,⩽′) and AS⋆=(L,S∪S′,D∪D′,K∪K′,A‾,⩽⋆) where ⩽⋆ is such that ⩽⋆∩(D×D)=⩽ and ⩽⋆∩(D′×D′)=⩽′, S is uniform and satisfies S1 and S2, AS and AS′ are strictly syntactically disjoint, and sem∈{pref,stab}, we have:

sem(AS⋆)={Arg(D[E]∪D[E′])⊆Arg(AS⋆)∣E∈sem(AS),E′∈sem(AS′)}.

Proof.

By Theorem 9, sem(AS⋆)={Arg(Δ)∣Δ∈MCSRS,K∪K′(D∪D′)}, sem(AS)={Arg(Δ)∣Δ∈MCSRS,K(D)}, and sem(AS′)={Arg(Δ)∣Δ∈MCSRS,K′(D′)}. Thus, by Proposition 5, sem(AS⋆)={Arg(D[E]∪D[E′])⊆Arg(AS⋆)∣E∈sem(AS),E′∈sem(AS′)}. □

C.4.Cumulativity lite

Where AS=(L,S,D,K,A‾,⩽) and a∈⋂pref(AS), n=min({k∣ϕ1,…,ϕm⇒kψ∈D(a)}),42 42 and ϕ is the conclusion of a, let AS+a=(L,S,D∪{⇒nϕ},K,A‾,⩽).

Definition 22

Definition 22(Cumulativity Lite.).

AS∣∼prefψ iff AS+a∣∼prefψ.

Where E∈pref(AS), let E+a=⋃b∈Eb[a/ar] where b[a/ar] the set of all arguments c which are identical to b except that possibly some subarguments a have been replaced with ar. E.g., in case a∉Sub(b), b[a/ar]={b} or a[a/ar]={a,ar}, or ⟨a,a→ϕ⟩[a/ar]={⟨a,a→ϕ⟩,⟨a,ar→ϕ⟩,⟨ar,a→ϕ⟩,⟨ar,ar→ϕ⟩}, etc. Note that

Fact 27.

Arg(AS+a)=⋃b∈Arg(AS)b[a/ar].

Fact 28.

If b defeats c then any b′∈b[a/ar] defeats any c′∈c[a/ar] or it defeats a.

Proof.

Note that b′ has the same strength as b and the same conclusion. Therefore, any argument defeated by b is also defeated by b′. Suppose now that b defeats c in the subargument d=d′⇒ψ. If b defeats a we’re done. Suppose it does not defeat a. Thus, d is not a sub-argument of a or ar. Hence, c′ has a sub-argument e=e′⇒ψ where e′∈d′[a/ar] and this argument is defeated by b and so also by b′. □

Cumulativity Lite then follows immediately in view of the following lemma.

Lemma 22.

pref(AS+a)={E+a∣E∈pref(AS)}.

Proof.

Consider E∈pref(AS) and E+a. We show that (i) E+a is admissible in AS+a.

Conflict-free. Assume for a contradiction that there are b,c∈E+a such that b defeats c. Thus, there are b′,c′∈E for which b∈b′[a/ar] and c∈c′[a/ar]. By Fact 28, b′ defeats c′ or a. This contradicts the conflict-freeness of E.
Admissibilitiy. Suppose some c∈Arg(AS+a) defeats some b∈E+a. Thus, there are b′∈E and c′∈Arg(AS) for which b∈b′[a/ar] and c∈c′[a/ar]. By Fact 28, c′ defeats b′ or a. Thus, there is a d∈E that defeats c′. By Fact 28, d defeats c or a. Since a∈E and by the conflict-freeness of E, d defeats c.

Consider E+∈pref(AS+a) and let E=E+∩Arg(AS). We show that (ii) E∈pref(AS).

We first show that (⋆) if b∈E then b[a/ar]⊆E+. Let b′∈b[a/ar]. Clearly, b and b′ defeat the same arguments (since they have the same strength and the same conclusion) an any argument c that defeats b′, by Fact 28, defeats b or a and is thus attacked by E+ in view of its admissibility. Thus, b′ is defended by E+ and due to its completeness in E+.
Conflict-free. Clearly, E is conflict-free since E+ is conflict-free.
Admissibility. Suppose some b∈Arg(AS) defeats some c∈E. By the admissibility of E+, there is a d∈E+ that defeats b. By (⋆), there is a d′∈E such that d∈d′[a/ar]. By Fact 28, also d′ defeats b.
Maximality. Suppose there is a E′∈pref(AS) for which E′⊃E. Let E″=E′+a. As shown in (i), E″ is admissible in AS+a. This is a contradiction to E+ being preferred since E″⊃E+.

Consider again a E∈pref(AS) and E+a. We now show that (iii) E+a is admissible in AS+a. By (i) it is admissible. Assume for a contradiction that there is a E′∈pref(AS+a) such that E′⊃E+a. Let c∈E′∖E+a. Thus, there is a c′∈Arg(AS) for which c∈c′[a/ar]. Since E+a is closed under [a/ar]-substitution, c′∉E. So, E′∩Arg(AS)⊃E. Since by (ii), E′∩Arg(AS) is admissible in AS this is a contradiction to the fact that E is preferred. □

References

[1]	L. Amgoud, Postulates for logic-based argumentation systems, International Journal of Approximate Reasoning 55: (9) ((2014) ), 2028–2048. doi:10.1016/j.ijar.2013.10.004.
[2]	L. Amgoud and P. Besnard, Logical limits of abstract argumentation frameworks, Journal of Applied Non-Classical Logics 23: (3) ((2013) ), 229–267. doi:10.1080/11663081.2013.830381.
[3]	L. Amgoud and P. Besnard, A formal characterization of the outcomes of rule-based argumentation systems, in: International Conference on Scalable Uncertainty Management, Springer, (2013) , pp. 78–91. doi:10.1007/978-3-642-40381-1_7.
[4]	L. Amgoud and C. Cayrol, Inferring from inconsistency in preference-based argumentation frameworks, Journal of Automated Reasoning (2002), 125–169. doi:10.1023/A:1021603608656.
[5]	L. Amgoud and S. Vesic, Handling inconsistency with preference-based argumentation, in: Scalable Uncertainty Management, A. Deshpande and A. Hunter, eds, Springer, (2010) , pp. 56–69. doi:10.1007/978-3-642-15951-0_11.
[6]	O. Arieli, A. Borg and J. Heyninck, A review of the relations between logical argumentation and reasoning with maximal consistency, Annals of Mathematics and Artificial Intelligence (2019), 1–40.
[7]	O. Arieli, A. Borg and C. Straßer, Reasoning with maximal consistency by argumentative approaches, Journal of Logic and Computation 28: (7) ((2018) ), 1523–1563, ISSN 0955-792X. doi:10.1093/logcom/exy027.
[8]	O. Arieli, A. Borg and C. Straßer, Prioritized sequent-based argumentation, in: Proc. AAMAS’18, ACM, (2018) , pp. 1105–1113.
[9]	O. Arieli and C. Straßer, Sequent-based logical argumentation, Journal of Argument and Computation 6: (1) ((2015) ), 73–99. doi:10.1080/19462166.2014.1002536.
[10]	P. Baroni, M. Giacomin and G. Guida, On the notion of strength in argumentation: Overcoming the epistemic/practical dichotomy, in: Proceedings of the 2001 ECSQARU Workshop: Adventures in Argumentation Toulouse, France, (2001) , pp. 1–8.
[11]	M. Beirlaen, J. Heyninck and C. Straßer, Structured argumentation with prioritized conditional obligations and permissions, Journal of Logic and Computation 29: (2) ((2018) ), 187–214. doi:10.1093/logcom/exy005.
[12]	A. Bondarenko, P.M. Dung, R.A. Kowalski and F. Toni, An abstract, argumentation-theoretic approach to default reasoning, Artificial intelligence 93: (1–2) ((1997) ), 63–101. doi:10.1016/S0004-3702(97)00015-5.
[13]	A. Borg, Equipping sequent-based argumentation with defeasible assumptions, in: Computational Models of Argument: Proceedings of COMMA 2018, Frontiers in Artificial Intelligence and Applications, Vol. 305: , IOS Press, (2018) .
[14]	A. Borg and C. Straßer, Relevance in structured argumentation, in: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, (2018) .
[15]	G. Brewka, Preferred subtheories: An extended logical framework for default reasoning, in: International Joint Conference on Artificial Intelligence, Vol. 89: , (1989) , pp. 1043–1048.
[16]	G. Brewka, Adding priorities and specificity to default logic, in: European Workshop on Logics in Artificial Intelligence, Springer, (1994) , pp. 247–260. doi:10.1007/BFb0021977.
[17]	M. Caminada, Dialogues and HY-arguments, in: 10th International Workshop on Non-Monotonic Reasoning, (2004) , pp. 94–99.
[18]	M. Caminada, Rationality postulates: Applying argumentation theory for non-monotonic reasoning, in: Handbook of Formal Argumentation, College Publications, (2018) .
[19]	M. Caminada and L. Amgoud, On the evaluation of argumentation formalisms, Artificial Intelligence 171: ((2007) ), 286–310. doi:10.1016/j.artint.2007.02.003.
[20]	M. Caminada, W.A. Carnielli and P.E. Dunne, Semi-stable semantics, Journal of Logic and Computation 22: (5) ((2012) ), 1207–1254. doi:10.1093/logcom/exr033.
[21]	M.W.A. Caminada, S. Modgil and N. Oren, Preferences and unrestricted rebut, Computational Models of Argument (2014).
[22]	C. Cayrol, On the relation between argumentation and non-monotonic coherence-based entailment, in: International Joint Conference on Artificial Intelligence, Morgan Kaufmann, (1995) , pp. 1443–1448.
[23]	S.A. Cook and R.A. Reckhow, The relative efficiency of propositional proof systems, The Journal of Symbolic Logic 44: (1) ((1979) ), 36–50. doi:10.2307/2273702.
[24]	K. Cyras, C. Schulz, F. Toni and X. Fan, 2017, Assumption-based argumentation: Disputes, explanations, preferences.
[25]	K. Cyras and F. Toni, ABA+: Assumption-based argumentation with preferences, in: Fifteenth International Conference on the Principles of Knowledge Representation and Reasoning, (2016) .
[26]	M. d’Agostino, Analytic inference and the informational meaning of the logical operators, Logique et Analyse (2014), 407–437.
[27]	M. D’Agostino and S. Modgil, Classical logic, argument and dialectic, Artificial Intelligence 262: ((2018) ), 15–51. doi:10.1016/j.artint.2018.05.003.
[28]	M. D’Agostino and S. Modgil, A study of argumentative characterisations of preferred subtheories, in: IJCAI, (2018) , pp. 1788–1794.
[29]	P.M. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artificial Intelligence 77: ((1995) ), 321–358. doi:10.1016/0004-3702(94)00041-X.
[30]	P.M. Dung and P.M. Thang, Closure and consistency in logic-associated argumentation, Journal of Artificial Intelligence Research 49: ((2014) ), 79–109. doi:10.1613/jair.4107.
[31]	P.E. Dunne and M. Wooldridge, Complexity of abstract argumentation, in: Argumentation in Artificial Intelligence, Springer, (2009) , pp. 85–104. doi:10.1007/978-0-387-98197-0_5.
[32]	S. Dyrkolbotn, T. Pedersen and J. Broersen, On elitist lifting and consistency in structured argumentation, Journal of Applied Logics – IfCoLog Journal of Logics and their Applications 5: (3) ((2018) ), 709–745.
[33]	D.M. Gabbay, Theoretical foundations for non-monotonic reasoning in expert systems, in: Logics and Models of Concurrent Systems, Springer, (1985) , pp. 439–457. doi:10.1007/978-3-642-82453-1_15.
[34]	H. Geffner and J. Pearl, Conditional entailment: Bridging two approaches to default reasoning, Artificial Intelligence 53: (2–3) ((1992) ), 209–244. doi:10.1016/0004-3702(92)90071-5.
[35]	N. Gorogiannis and A. Hunter, Instantiating abstract argumentation with classical logic arguments: Postulates and properties, Artificial Intelligence 175: (9–10) ((2011) ), 1479–1497. doi:10.1016/j.artint.2010.12.003.
[36]	D. Grooters and H. Prakken, Two aspects of relevance in structured argumentation: Minimality and paraconsistency, Journal of Artificial Intelligence Research 56: ((2016) ), 197–245. doi:10.1613/jair.5058.
[37]	J. Heyninck and O. Arieli, On the semantics of simple contrapositive assumption-based argumentation frameworks, in: Computational Models of Argument: Proceedings of COMMA 2018, Frontiers in Artificial Intelligence and Applications, Vol. 305: , IOS Press, (2018) .
[38]	J. Heyninck and O. Arieli, Simple contrapositive assumption-based frameworks, in: International Conference on Logic Programming and Nonmonotonic Reasoning, Springer, (2019) , pp. 75–88. doi:10.1007/978-3-030-20528-7_7.
[39]	J. Heyninck and C. Straßer, Revisiting unrestricted rebut and preferences in structured argumentation, in: Proceedings of the 26th International Joint Conference on Artificial Intelligence, AAAI Press, (2017) , pp. 1088–1092.
[40]	J. Heyninck and C. Straßer, A comparative study of assumption-based approaches to reasoning with priorities, in: Second Chinese Conference on Logic and Argumentation, (2018) .
[41]	J. Heyninck and C. Straßer, A fully rational argumentation system for preordered defeasible rules, in: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, International Foundation for Autonomous Agents and Multiagent Systems, (2019) , pp. 1704–1712.
[42]	J. Heyninck and C. Straßer, A comparative study of assumption-based approaches to reasoning with priorities, Journal of Applied Logics – IfColog Journal of Logics and their Applications (2019).
[43]	J. Heyninck and C. Straßer, Relations between assumption-based approaches in nonmonotonic logic and formal argumentation, 2016, preprint arXiv:1604.00162.
[44]	J. Heyninck, C. Straßer and P. Pardo, Assumption-based approaches to reasoning with priorities, in: Proceedings of the 1st Workshop on Advances in Argumentation in Artificial Intelligence, Ceur Workshop Proceedings, (2017) , pp. 58–72.
[45]	S. Kraus, D. Lehmann and M. Magidor, Nonmonotonic reasoning, preferential models and cumulative logics, Artificial Intelligence 44: (1–2) ((1990) ), 167–207. doi:10.1016/0004-3702(90)90101-5.
[46]	Z. Li, N. Oren and S. Parsons, On the links between argumentation-based reasoning and nonmonotonic reasoning, in: Theory and Applications of Formal Argumentation, E. Black, S. Modgil and N. Oren, eds, Springer International Publishing, Cham, (2018) , pp. 67–85. doi:10.1007/978-3-319-75553-3_5.
[47]	D. Makinson, Bridges from Classical to Nonmonotonic Logic, College Publications, (2005) .
[48]	D. Makinson and L. Van Der Torre, Input/output logics, Journal of philosophical logic 29: (4) ((2000) ), 383–408. doi:10.1023/A:1004748624537.
[49]	S. Modgil and M. Caminada, Proof theories and algorithms for abstract argumentation frameworks, in: Argumentation in Artificial Intelligence, Springer, (2009) , pp. 105–129. doi:10.1007/978-0-387-98197-0_6.
[50]	S. Modgil and H. Prakken, A general account of argumentation with preferences, Artificial Intelligence 195: ((2013) ), 361–397. doi:10.1016/j.artint.2012.10.008.
[51]	S. Modgil and H. Prakken, Abstract rule-based argumentation, Handbook of Formal Argumentation 1: ((2018) ), 286.
[52]	J. Müller and A. Hunter, An argumentation-based approach for decision making, in: 2012 IEEE 24th International Conference on Tools with Artificial Intelligence, Vol. 1: , IEEE, (2012) , pp. 564–571. doi:10.1109/ICTAI.2012.82.
[53]	H. Prakken, An abstract framework for argumentation with structured arguments, Argument and Computation 1: (2) ((2010) ), 93–124. doi:10.1080/19462160903564592.
[54]	H. Prakken, Formalising a legal opinion on a legislative proposal in the ASPIC+ framework, in: JURIX, Vol. 2012: , (2012) , pp. 119–128.
[55]	H. Prakken, D. Ionita and R. Wieringa, Risk assessment as an argumentation game, in: International Workshop on Computational Logic in Multi-Agent Systems, Springer, (2013) , pp. 357–373.
[56]	A. Urquhart, Basic many-valued logic, in: Handbook of Philosophical Logic, Handbook of Philosophical Logic, Springer, (2001) , pp. 249–295. doi:10.1007/978-94-017-0452-6_4.
[57]	Y. Wu, Between argument and conclusion. Argument-based approaches to discussion, inference and uncertainty, PhD thesis, Universite Du Luxembourg, 2012.
[58]	Y. Wu and M. Podlaszewski, Implementing crash-resistance and non-interference in logic-based argumentation, Journal of Logic and Computation 25: (2) ((2015) ), 303–333. doi:10.1093/logcom/exu017.
[59]	A.P. Young, S. Modgil and O. Rodrigues, Prioritised default logic as rational argumentation, in: Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, International Foundation for Autonomous Agents and Multiagent Systems, (2016) , pp. 626–634.
[60]	A.P. Young, S. Modgil and O. Rodrigues, Prioritised default logic as argumentation with partial order default priorities, 2016, preprint arXiv:1609.05224.