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

Abstract

Structured argumentation formalisms, such as ${\mathrm{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 ${\mathrm{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 ${\mathrm{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 ${\mathrm{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 ${\mathrm{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 ${\mathrm{ASPIC}}^{+}$ . ${\mathrm{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

¹

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

In Nicki’s opinion a good potato-salad has pickles in it ( $\mathit{g}{\Rightarrow }_1\mathit{p}$ ) but Mary has an allergy to pickles ( $\mathit{g}{\Rightarrow }_2\neg \mathit{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 $\mathit{g}{\Rightarrow }_2\neg \mathit{p}$ and a subscript 1 for $\mathit{g}{\Rightarrow }_1\mathit{p}$ ). Mary thinks they should bring a bottle of Quadruple beer as a gift for the host ( $\mathit{l}{\Rightarrow }_1\mathit{q}$ ) 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 ( $\mathit{q}{\Rightarrow }_1\mathit{w}$ ). However, the host is a beer connoisseur (b), and thus the previous rule of thumb does not apply ( $\mathit{b}{\Rightarrow }_1\neg \mathit{n}\mathrm{(}\mathit{q}{\Rightarrow }_1\mathit{w}\mathrm{)}$ ).

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 ( $\neg \mathit{p}$ ) of the salad. In [53], it was proven that ${\mathrm{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], ${\mathrm{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 $\{\mathit{g}{\Rightarrow }_1\mathit{p}\mathrm{,}\mathit{g}{\Rightarrow }_2\neg \mathit{p}\}$ to the knowledge base). As demonstrated in [57] for ${\mathrm{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

²

In the context of ${\mathrm{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.

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 ${\mathrm{ASPIC}}^{+}$ and related systems.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].

Some examples are:

• [57] established non-interference for complete semantics for ASPIC-lite, a sub-system of ${\mathrm{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 ${\mathrm{ASPIC}}^{\ominus }$ [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. ${\mathrm{ASPIC}}^{\ominus }$ 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 ${\mathrm{ASPIC}}^{+}$ . In more detail, we consider ${\mathrm{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 ${\mathrm{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 ${\mathrm{ASPIC}}^{+}$ . In this way we obtain further insights into the relation of ${\mathrm{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 ${\mathrm{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) ${\mathrm{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 ${\mathrm{ASPIC}}^{+}$ , such an argumentation system is built up from a formal language $\mathcal{L}$ , which can be used to formulate strict rules $\mathcal{S}$ of the form ${\mathit{\varphi }}_1\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{n}}\to \mathit{\varphi }$ , defeasible rules $\mathcal{D}$ of the form ${\mathit{\varphi }}_1\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{n}}\Rightarrow \mathit{\varphi }$ and strict premises $\mathcal{K}$ . Strict rules are deductive in the sense that the truth of their antecedents ${\mathit{\varphi }}_1\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{n}}$ necessarily implies the truth of their consequent ϕ, while defeasible rules allow for exceptions. In ${\mathrm{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 ${⊢}_{\mathbf{L}}$ and require that ${\mathit{\varphi }}_1\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{n}}\to \mathit{\varphi }\in \mathcal{S}$ iff $\{{\mathit{\varphi }}_1\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{n}}\}{⊢}_{\mathbf{L}}\mathit{A}$ . 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 $\mathcal{D}$ come with a naming function $\mathit{n}:\mathcal{D}\to \mathcal{L}$ . Furthermore, conflicts between elements of the language can be specified using a contrariness function $\overline{\phantom{\mathit{\varphi }}}$ .4

⁴

Note that $\overline{\phantom{\mathit{\varphi }}}$ does not denote the set theoretic complement.

Finally, the user can specify preferences over the defeasible rules using a preorder $⩽\subseteq \mathcal{D}\times \mathcal{D}$ . Formally, such an argumentation system is defined as follows:

Definition 1 (Argumentation System).

An Argumentation System (AS) is a tuple $\mathrm{(}\mathcal{L}\mathrm{,}\mathcal{S}\mathrm{,}\mathcal{D}\mathrm{,}\mathcal{K}\mathrm{,}\mathit{n}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}⩽\mathrm{)}$ consisting of:

a formal language $\mathcal{L}$ based on a set of atoms $\mathcal{A}$ ;

a set of strict rules $\mathcal{S}$ of the form ${\mathit{\varphi }}_1\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{n}}\to \mathit{\varphi }$ (where ${\mathit{\varphi }}_1\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{n}}\mathrm{,}\mathit{\varphi }\in \mathcal{L}$ );

a set of defeasible rules $\mathcal{D}$ of the form ${\mathit{\varphi }}_1\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{n}}\Rightarrow \mathit{\varphi }$ (where ${\mathit{\varphi }}_1\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{n}}\mathrm{,}\mathit{\varphi }\in \mathcal{L}$ );

an $\mathcal{S}$ -consistent5

⁵

$\mathcal{K}$ is $\mathcal{S}$ -consistent iff there is no derivation based on rules in $\mathcal{S}$ from $\mathcal{K}$ of some $\mathit{\varphi }\in \mathcal{K}$ and some $\mathit{\psi }\in \bar{\mathit{\varphi }}$ . See also Def. 8.

set of strict premises $\mathcal{K}\subseteq \mathcal{L}$ ;

a naming function for the defeasible rules $\mathit{n}:\mathcal{D}\to \mathcal{L}$ ;

a contrariness function $\overline{\phantom{\mathit{A}}}$ from $\mathcal{L}$ to $2^{\mathcal{L}}$ ;

a total preorder6

⁶

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

⩽ over $\mathcal{D}$ .

Given a rule $\mathit{r}={\mathit{\varphi }}_1\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{n}}\to \mathit{\varphi }$ resp. $\mathit{r}={\mathit{\varphi }}_1\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{n}}\Rightarrow \mathit{\varphi }$ , ${\mathit{\varphi }}_1\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{n}}$ are called the antecedents and ϕ is called the consequent or head. We write $\mathsf{body}\mathrm{(}\mathit{r}\mathrm{)}=\{{\mathit{\varphi }}_1\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{n}}\}$ and $\mathsf{head}\mathrm{(}\mathit{r}\mathrm{)}=\mathit{\varphi }$ . Where $\mathcal{R}$ is a set of rules we write $\mathsf{body}[\mathcal{R}]$ for the set $\{\mathsf{body}\mathrm{(}\mathit{r}\mathrm{)}\mid \mathit{r}\in \mathcal{R}\}$ and $\mathsf{head}[\mathcal{R}]$ for the set $\{\mathsf{head}\mathrm{(}\mathit{r}\mathrm{)}\mid \mathit{r}\in \mathcal{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

⁷

More precisely, when omitting ⩽ we consider the preorder $\mathcal{D}\times \mathcal{D}$ .

Example 2 (Example 1 continued).

To illustrate the above definitions, we illustrate how to capture the information from Example 1 in an argumentation system ${\mathsf{AS}}_{\text{2}}=\mathrm{(}{\mathcal{L}}_{\text{2}}\mathrm{,}{\mathcal{S}}_{\mathsf{CL}}\mathrm{,}{\mathcal{D}}_{\text{2}}\mathrm{,}{\mathcal{K}}_{\text{2}}\mathrm{,}{\mathit{n}}_{\text{2}}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}{⩽}_{\text{2}}\mathrm{)}$ where:8

⁸

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

• ${\mathcal{L}}_{\text{2}}$ is the closure of the set of atoms $\{\mathit{g}\mathrm{,}\mathit{p}\mathrm{,}\mathit{q}\mathrm{,}\mathit{l}\mathrm{,}\mathit{w}\mathrm{,}\mathit{b}\mathrm{,}\mathit{\alpha }\mathrm{,}\mathit{\beta }\mathrm{,}\mathit{\gamma }\mathrm{,}\mathit{\delta }\mathrm{,}\mathit{ϵ}\}$ and the constants ⊥ and ⊤ under $\{\neg \mathrm{,}\wedge \mathrm{,}\vee \}$ ;

• ${\mathcal{S}}_{\mathsf{CL}}$ is the set of strict rules capturing classical logic $\mathsf{CL}$ as follows: ${\mathit{\varphi }}_1\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{n}}\to \mathit{\varphi }\in {\mathcal{S}}_{\mathsf{CL}}$ iff $\{{\mathit{\varphi }}_1\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{n}}\}{⊢}_{\mathsf{CL}}\mathit{\varphi }$ and $\mathit{\varphi }\mathrm{,}{\mathit{\varphi }}_1\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{n}}\in {\mathcal{L}}_2$ ;9

  ⁹

  In the examples that follow, we shall denote with ${\mathcal{S}}_{\mathsf{CL}}$ the rule set constructed in the same way as in this example, except that the language is changed relative to the example at hand.

• ${\mathcal{D}}_{\text{2}}=\{\mathit{g}{\Rightarrow }_1\mathit{p};\mathit{g}{\Rightarrow }_2\neg \mathit{p};\mathit{l}{\Rightarrow }_1\mathit{q};\mathit{q}{\Rightarrow }_1\mathit{w};\mathit{b}{\Rightarrow }_1\neg \mathit{\delta }\}$ ;

• ${\mathcal{K}}_{\text{2}}=\{\mathit{g}\mathrm{,}\mathit{b}\mathrm{,}\mathit{l}\}$ ;

• ${\mathit{n}}_{\text{2}}\mathrm{(}\mathit{g}{\Rightarrow }_1\mathit{p}\mathrm{)}=\mathit{\alpha }$ , ${\mathit{n}}_{\text{2}}\mathrm{(}\mathit{g}{\Rightarrow }_2\neg \mathit{p}\mathrm{)}=\mathit{\beta }$ , ${\mathit{n}}_{\text{2}}\mathrm{(}\mathit{l}{\Rightarrow }_1\mathit{q}\mathrm{)}=\mathit{\gamma }$ , ${\mathit{n}}_{\text{2}}\mathrm{(}\mathit{q}{\Rightarrow }_1\mathit{w}\mathrm{)}=\mathit{\delta }$ , ${\mathit{n}}_{\text{2}}\mathrm{(}\mathit{b}{\Rightarrow }_1\neg \mathit{\delta }\mathrm{)}=\mathit{ϵ}$ .

• $\mathit{\varphi }\in \bar{\mathit{\psi }}$ iff $\mathit{\varphi }=\neg \mathit{\psi }$ or $\mathit{\psi }=\neg \mathit{\varphi }$ or $\mathit{\varphi }=\perp$ ;10

  ¹⁰

  In all the examples that follow where $\mathcal{L}$ is closed under ¬, we will treat $\overline{\phantom{\mathit{\varphi }}}$ the same.

• $\mathit{\varphi }{\Rightarrow }_{\mathit{i}}\mathit{\psi }{⩽}_{\text{2}}{\mathit{\varphi }}^{\prime }{\Rightarrow }_{\mathit{j}}{\mathit{\psi }}^{\prime }$ iff $\mathit{i}⩽\mathit{j}$ (where ⩽ is the canonical order over $\mathbb{N}$ ).

2.1. Argument construction

In structured argumentation systems like ${\mathrm{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

¹¹

In this paper we will for the sake of simplicity omit several features of the original ${\mathrm{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 $\top \Rightarrow \mathit{\gamma }$ and undermining attacks can be modelled as a rebuttals.

Definition 2.

Let $\mathsf{AS}=\mathrm{(}\mathcal{L}\mathrm{,}\mathcal{S}\mathrm{,}\mathcal{D}\mathrm{,}\mathcal{K}\mathrm{,}\mathit{n}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}⩽\mathrm{)}$ be an argumentation system. An argument a is one of the following:

$\mathit{a}=⟨\mathit{\varphi }⟩$ where $\mathit{\varphi }\in \mathcal{K}$

$\mathsf{Conc}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{\varphi }$ , $\mathsf{Sub}\mathrm{(}\mathit{a}\mathrm{)}=\{\mathit{a}\}$ , $\mathcal{D}\mathrm{(}\mathit{a}\mathrm{)}=\varnothing$ ;12

¹²

We note that $\mathcal{D}$ is a set of rules whereas $\mathcal{D}\mathrm{(}\mathit{a}\mathrm{)}$ is a function mapping arguments to subsets of $\mathcal{D}$ . This will not cause any confusion.

$\mathit{a}=⟨{\mathit{a}}_1\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{n}}\to \mathit{\varphi }⟩$ where ${\mathit{a}}_1\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{n}}$ (with $\mathit{n}⩾0$ ) are arguments such that there is a strict rule $\mathsf{Conc}\mathrm{(}{\mathit{a}}_1\mathrm{)}\mathrm{,}\dots \mathrm{,}\mathsf{Conc}\mathrm{(}{\mathit{a}}_{\mathit{n}}\mathrm{)}\to \mathit{\varphi }\in \mathcal{S}$

$\mathsf{Conc}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{\varphi }$ , $\mathsf{Sub}\mathrm{(}\mathit{a}\mathrm{)}=\{\mathit{a}\}\cup {\bigcup }_{\mathit{i}=1}^{\mathit{n}}\mathsf{Sub}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}$ , and $\mathcal{D}\mathrm{(}\mathit{a}\mathrm{)}={\bigcup }_{\mathit{i}=1}^{\mathit{n}}\mathcal{D}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}$ ;

$\mathit{a}=⟨{\mathit{a}}_1\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{n}}\Rightarrow \mathit{\varphi }⟩$ where ${\mathit{a}}_1\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{n}}$ (with $\mathit{n}⩾0$ ) are arguments such that there is a defeasible rule $\mathsf{Conc}\mathrm{(}{\mathit{a}}_1\mathrm{)}\mathrm{,}\dots \mathrm{,}\mathsf{Conc}\mathrm{(}{\mathit{a}}_{\mathit{n}}\mathrm{)}\Rightarrow \mathit{\varphi }\in \mathcal{D}$

$\mathsf{Conc}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{\varphi }$ , $\mathsf{Sub}\mathrm{(}\mathit{a}\mathrm{)}=\{\mathit{a}\}\cup {\bigcup }_{\mathit{i}=1}^{\mathit{n}}\mathsf{Sub}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}$ , and

$\mathcal{D}\mathrm{(}\mathit{a}\mathrm{)}=\{\mathsf{Conc}\mathrm{(}{\mathit{a}}_1\mathrm{)}\mathrm{,}\dots \mathrm{,}\mathsf{Conc}\mathrm{(}{\mathit{a}}_{\mathit{n}}\mathrm{)}\Rightarrow \mathit{\varphi }\}\cup {\bigcup }_{\mathit{i}=1}^{\mathit{n}}\mathcal{D}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}$ .

We lift the above notation as expected. E.g., where $\mathcal{A}$ is a set of arguments, $\mathsf{Conc}[\mathcal{A}]=\{\mathsf{Conc}\mathrm{(}\mathit{a}\mathrm{)}\mid \mathit{a}\in \mathcal{A}\}$ and $\mathcal{D}[\mathcal{A}]=\{\mathcal{D}\mathrm{(}\mathit{a}\mathrm{)}\mid \mathit{a}\in \mathcal{A}\}$ .

By $\mathsf{Arg}\mathrm{(}\mathsf{AS}\mathrm{)}$ we denote the set of arguments that can be built from $\mathsf{AS}$ . An argument a will be called defeasible if $\mathcal{D}\mathrm{(}\mathit{a}\mathrm{)}\ne \varnothing$ and strict otherwise. Example 3 (Example 2 continued).

The following arguments (among others) can be constructed from ${\mathsf{AS}}_{\text{2}}$ : $$\begin{array}{cccccc}{\mathit{a}}_1:\hfill & ⟨\mathit{g}⟩\hfill & {\mathit{a}}_1^{\prime }:\hfill & ⟨\mathit{l}⟩\hfill & {\mathit{a}}_2:\hfill & ⟨{\mathit{a}}_1{\Rightarrow }_1\mathit{p}⟩\hfill \\ {\mathit{a}}_3:\hfill & ⟨{\mathit{a}}_1{\Rightarrow }_2\neg \mathit{p}⟩\hfill & {\mathit{a}}_4:\hfill & ⟨{\mathit{a}}_1^{\prime }{\Rightarrow }_1\mathit{q}⟩\hfill & {\mathit{a}}_5:\hfill & ⟨{\mathit{a}}_4{\Rightarrow }_1\mathit{w}⟩\hfill \\ {\mathit{a}}_6:\hfill & ⟨\mathit{b}⟩\hfill & {\mathit{a}}_7:\hfill & {\mathit{a}}_6{\Rightarrow }_1\neg \mathit{\delta }\hfill & {\mathit{a}}_8:\hfill & ⟨{\mathit{a}}_2\mathrm{,}{\mathit{a}}_3\to \perp ⟩\hfill \\ {\mathit{a}}_9:\hfill & ⟨{\mathit{a}}_4\mathrm{,}{\mathit{a}}_5\to \mathit{q}\wedge \mathit{w}⟩\hfill \end{array}$$ ${\mathit{a}}_1$ , ${\mathit{a}}_1^{\prime }$ , and ${\mathit{a}}_6$ are premise arguments. ${\mathit{a}}_2$ is obtained by applying the defeasible rule $\mathit{g}{\Rightarrow }_1\mathit{p}$ to the argument ${\mathit{a}}_1$ . ${\mathit{a}}_3$ , ${\mathit{a}}_4$ and ${\mathit{a}}_7$ are obtained in a similar way. ${\mathit{a}}_5$ is obtained by applying the rule $\mathit{q}{\Rightarrow }_1\mathit{w}$ to the defeasible rule argument ${\mathit{a}}_4$ and thus is an example of how defeasible rules can be chained. ${\mathit{a}}_8$ and ${\mathit{a}}_9$ are two examples of the application of a strict rule: ex falso quodlibet in the case of ${\mathit{a}}_8$ and conjunction introduction in the case of ${\mathit{a}}_9$ .

2.2. Attack and defeat

In ${\mathrm{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 $\overline{\mathit{n}\mathrm{(}\mathit{r}\mathrm{)}}$ where $\mathit{r}\in \mathcal{D}\mathrm{(}\mathit{b}\mathrm{)}$ .

Definition 3.

Let $\mathit{a}\mathrm{,}\mathit{b}\in \mathsf{Arg}\mathrm{(}\mathsf{AS}\mathrm{)}$ and $\mathit{b}={\mathit{b}}_1\dots \mathrm{,}{\mathit{b}}_{\mathit{n}}\Rightarrow \mathit{B}$ :

a rebuts b iff $\mathsf{Conc}\mathrm{(}\mathit{a}\mathrm{)}\in \overline{\mathsf{Conc}\mathrm{(}\mathit{b}\mathrm{)}}$ ;

a undercuts b iff $\mathsf{Conc}\mathrm{(}\mathit{a}\mathrm{)}\in \overline{\mathit{n}\mathrm{(}\mathsf{Conc}\mathrm{(}{\mathit{b}}_1\mathrm{)}\dots \mathrm{,}\mathsf{Conc}\mathrm{(}{\mathit{b}}_{\mathit{n}}\mathrm{)}\Rightarrow \mathit{B}\mathrm{)}}$ .

a attacks b iff $\mathit{a}\mathrm{,}\mathit{b}\in \mathsf{Arg}\mathrm{(}\mathsf{AS}\mathrm{)}$ and a rebuts13

¹³

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.

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 $\mathcal{D}$ to a preference order ⪯ over the set of arguments $\mathsf{Arg}\mathrm{(}\mathsf{AS}\mathrm{)}$ constructed on the basis of $\mathcal{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

¹⁴

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.

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 $\mathit{a}\mathrm{,}\mathit{b}\in \mathsf{Arg}\mathrm{(}\mathsf{AS}\mathrm{)}$ , $\mathit{a}⪯\mathit{b}$ iff there is an $\mathit{r}\in \mathcal{D}\mathrm{(}\mathit{a}\mathrm{)}$ such that for every ${\mathit{r}}^{\prime }\in \mathcal{D}\mathrm{(}\mathit{b}\mathrm{)}$ , $\mathit{r}⩽{\mathit{r}}^{\prime }$ .

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

Definition 5.

Where $\mathit{a}\mathrm{,}\mathit{b}\in \mathsf{Arg}\mathrm{(}\mathsf{AS}\mathrm{)}$ , a defeats b (in symbols: $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in ⇝\mathrm{(}\mathsf{AS}\mathrm{)}$ ) iff: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.

• a rebuts some ${\mathit{b}}^{\prime }\in \mathsf{Sub}\mathrm{(}\mathit{b}\mathrm{)}$ and ${\mathit{b}}^{\prime }⪯\mathit{a}$ ;16

  ¹⁶

  [50,53] distinguish between rebuts where $\mathsf{Conc}\mathrm{(}\mathit{b}\mathrm{)}\in \overline{\mathsf{Conc}\mathrm{(}\mathit{a}\mathrm{)}}$ and rebuts where $\mathsf{Conc}\mathrm{(}\mathit{b}\mathrm{)}\notin \overline{\mathsf{Conc}\mathrm{(}\mathit{a}\mathrm{)}}$ . 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.

• a undercuts some ${\mathit{b}}^{\prime }\in \mathsf{Sub}\mathrm{(}\mathit{b}\mathrm{)}$ .

We define the argumentation framework based on an argumentation system $\mathsf{AS}$ as $\mathrm{(}\mathsf{Arg}\mathrm{(}\mathsf{AS}\mathrm{)}\mathrm{,}⇝\mathrm{(}\mathsf{AS}\mathrm{)}\mathrm{)}$ .

Example 4 (Example 3 continued).

For the argumentation system ${\mathsf{AS}}_{\text{2}}$ , 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 $\mathrm{(}\mathsf{Arg}\mathrm{,}⇝\mathrm{)}$ where $\mathsf{Arg}$ is a set of arguments and $⇝\subseteq \mathsf{Arg}\times \mathsf{Arg}$ is a binary relation of attack. Relative to an AF, Dung defines a number of extensions – subsets of $\mathsf{Arg}$ – on the basis of which we can evaluate the arguments in $\mathsf{Arg}$ .

Definition 6 (Extensions).

Let $\mathrm{(}\mathsf{Arg}\mathrm{,}⇝\mathrm{)}$ be an argumentation framework and $\mathcal{E}\subseteq \mathsf{Arg}$ :

$\mathcal{E}⇝\mathit{a}$ iff there is some $\mathit{b}\in \mathcal{E}$ such that $\mathit{b}⇝\mathit{a}$ .

$\mathcal{E}$ is conflict-free iff there are no $\mathit{a}\mathrm{,}\mathit{b}\in \mathcal{E}$ for which $\mathit{a}⇝\mathit{b}$ .

$\mathcal{E}$ defends an argument a iff for every $\mathit{b}\in \mathsf{Arg}$ such that $\mathit{b}⇝\mathit{a}$ then $\mathcal{E}⇝\mathit{b}$ .

$\mathcal{E}$ is a complete extension iff it is conflict-free and $\mathit{a}\in \mathcal{E}$ iff $\mathcal{E}$ defends a.

$\mathcal{E}$ is a preferred extension iff it is a set inclusion maximal complete extension.

$\mathcal{E}$ is the grounded extension iff it is the set inclusion minimal complete extension.17

¹⁷

Dung [29] showed that for every AF $\mathrm{(}\mathsf{Arg}\mathrm{,}⇝\mathrm{)}$ there is a unique grounded extension, which we denote by $\mathtt{groun}\mathrm{(}\mathrm{(}\mathsf{Arg}\mathrm{,}⇝\mathrm{)}\mathrm{)}$ .

$\mathcal{E}$ is a stable extension iff it is conflict-free and for every $\mathit{b}\in \mathsf{Arg}\setminus \mathcal{E}$ , $\mathcal{E}⇝\mathit{b}$ .

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

Example 5 (Example 4 continued).

The argumentation framework $\mathrm{(}\mathsf{Arg}\mathrm{(}{\mathsf{AS}}_{\text{2}}\mathrm{)}\mathrm{,}⇝\mathrm{(}{\mathsf{AS}}_{\text{2}}\mathrm{)}\mathrm{)}$ has as grounded extension that contains ${\mathit{a}}_1$ , ${\mathit{a}}_1^{\prime }$ , ${\mathit{a}}_3$ , ${\mathit{a}}_4$ , ${\mathit{a}}_6$ , ${\mathit{a}}_7$ but not ${\mathit{a}}_2$ , ${\mathit{a}}_5$ , ${\mathit{a}}_8$ and ${\mathit{a}}_9$ . This extension is also the unique preferred extension. It is also stable as it attacks ${\mathit{a}}_2$ , ${\mathit{a}}_5$ , ${\mathit{a}}_8$ , ${\mathit{a}}_9$ , etc.

Based on these argumentation semantics, we define consequence relations:

Definition 7.

Where $\mathit{AF}=\mathrm{(}\mathsf{Arg}\mathrm{(}\mathsf{AS}\mathrm{)}\mathrm{,}⇝\mathrm{(}\mathsf{AS}\mathrm{)}\mathrm{)}$ and $\mathtt{sem}\in \{\mathtt{pref}\mathrm{,}\mathtt{stab}\}$ :

$\mathit{A}\mathit{S}{\mid \sim }_{\mathtt{sem}}^{\cup }\mathit{\varphi }$ if for some $\mathcal{E}\in \mathtt{sem}\mathrm{(}\mathsf{AS}\mathrm{)}$ , there is some $\mathit{a}\in \mathcal{E}$ with $\mathsf{Conc}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{\varphi }$ .

$\mathit{A}\mathit{S}{\mid \sim }_{\mathtt{sem}}^{\cap }\mathit{\varphi }$ if for every $\mathcal{E}\in \mathtt{sem}\mathrm{(}\mathsf{AS}\mathrm{)}$ , there is some $\mathit{a}\in \mathcal{E}$ with $\mathsf{Conc}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{\varphi }$ .

$\mathit{A}\mathit{S}{\mid \sim }_{\mathtt{groun}}\mathit{\varphi }$ if there is some $\mathit{a}\in \mathtt{groun}\mathrm{(}\mathsf{AS}\mathrm{)}$ with $\mathsf{Conc}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{\varphi }$ .

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 $\mathtt{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 $\mathsf{Conc}\mathrm{(}\mathit{a}\mathrm{)}\in \overline{\mathsf{Conc}\mathrm{(}\mathit{b}\mathrm{)}}$ .

Postulate 1 (Direct Consistency).

$\mathtt{sem}$ satisfies Direct Consistency for an argumentation system $\mathsf{AS}$ if there is no $\mathcal{E}\in \mathtt{sem}\mathrm{(}\mathsf{AS}\mathrm{)}$ such that there are some $\mathit{a}\mathrm{,}\mathit{b}\in \mathcal{E}$ for which $\mathsf{Conc}\mathrm{(}\mathit{a}\mathrm{)}\in \overline{\mathsf{Conc}\mathrm{(}\mathit{b}\mathrm{)}}$ .

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 $\mathcal{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 $\mathcal{S}$ .

Definition 8 ( $\mathcal{R}$ -proof).

Let $\mathrm{\Gamma }\cup \{\mathit{\varphi }\}$ be a set of $\mathcal{L}$ -formulas and $\mathcal{R}$ a set of inference rules on $\mathcal{L}$ . An $\mathcal{R}$ -proof $\mathbb{P}$ of ϕ from Γ is a sequence ${\mathit{\varphi }}_1\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{n}}$ where for each $1⩽\mathit{i}⩽\mathit{n}$ , ${\mathit{\varphi }}_{\mathit{i}}\in \mathrm{\Gamma }$ or ${\mathit{\varphi }}_{\mathit{i}}$ is the head of a rule in $\mathcal{R}$ whose body only contains formulas in $\{{\mathit{\varphi }}_1\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{i}-1}\}$ . We write $\mathrm{\Gamma }{⊢}_{\mathcal{R}}\mathit{\varphi }$ iff there is an $\mathcal{R}$ -derivation of ϕ based on Γ.

Fact 1.

Given a set of inference rules $\mathcal{R}$ , ${⊢}_{\mathcal{R}}$ is monotonic, reflexive and transitive.

Definition 9 ( $\mathcal{S}$ -consistency.).

Where $\mathcal{S}$ is a set of inference rules over $\mathcal{L}$ , a set Γ of formulas in $\mathcal{L}$ is $\mathcal{S}$ -inconsistent iff $\mathrm{\Gamma }{⊢}_{\mathcal{S}}\mathit{\psi }$ for some $\mathit{\varphi }\in \mathcal{L}$ such that $\mathrm{\Gamma }{⊢}_{\mathcal{S}}\mathit{\varphi }$ and $\mathit{\psi }\in \bar{\mathit{\varphi }}$ . Otherwise it is $\mathcal{S}$ -consistent.

Postulate 2 (Indirect Consistency).

$\mathtt{sem}$ satisfies Indirect Consistency for an argumentation system $\mathsf{AS}=\mathrm{(}\mathcal{L}\mathrm{,}\mathcal{S}\mathrm{,}\mathcal{D}\mathrm{,}\mathcal{K}\mathrm{,}\mathit{n}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}⩽\mathrm{)}$ if for every $\mathcal{E}\in \mathtt{sem}\mathrm{(}\mathsf{AS}\mathrm{)}$ , $\mathsf{Conc}[\mathcal{E}]$ is $\mathcal{S}$ -consistent.

A third postulate is related to the interpretation of strict rules → as being truth preserving. Recall that a rule ${\mathit{\varphi }}_1\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{n}}\to \mathit{\varphi }$ means that whenever ${\mathit{\varphi }}_1$ and … and ${\mathit{\varphi }}_{\mathit{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 ${\mathit{\varphi }}_1\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{n}}$ are part of an extension (selected according to some semantics $\mathtt{sem}$ ) and ${\mathit{\varphi }}_1\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{n}}\to \mathit{\varphi }$ is a strict rule we should find an argument for ϕ in that same extension as well.

Postulate 3 (Closure).

$\mathtt{sem}$ satisfies Closure for an argumentation system $\mathit{A}\mathit{S}=\mathrm{(}\mathcal{L}\mathrm{,}\mathcal{S}\mathrm{,}\mathcal{D}\mathrm{,}\mathcal{K}\mathrm{,}\mathit{n}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}⩽\mathrm{)}$ if for every $\mathcal{E}\in \mathtt{sem}\mathrm{(}\mathsf{AS}\mathrm{)}$ , whenever $\mathsf{Conc}[\mathcal{E}]{⊢}_{\mathcal{S}}\mathit{\varphi }$ then $\mathit{\varphi }\in \mathsf{Conc}[\mathcal{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 $\mathrm{\Gamma }\cup \{\mathit{\varphi }\}$ and ${\mathrm{\Gamma }}^{\prime }$ are two syntactically disjoint sets, a non-interferent system will allow one to infer ϕ from Γ iff ϕ is inferable from $\mathrm{\Gamma }\cup {\mathrm{\Gamma }}^{\prime }$ . A violation of non-interference thus means that syntactically disjoint knowledge bases influence each others outcomes. In most of the cases,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.

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 $\mathsf{Atoms}\mathrm{(}\mathrm{\Delta }\mathrm{)}$ be the set of all atoms occurring in Δ (where Δ is a set of formulas and/or inference rules based on $\mathcal{L}$ ). Two sets Δ and ${\mathrm{\Delta }}^{\prime }$ are syntactically disjoint iff $\mathsf{Atoms}\mathrm{(}\mathrm{\Delta }\mathrm{)}\cap \mathsf{Atoms}\mathrm{(}{\mathrm{\Delta }}^{\prime }\mathrm{)}=\varnothing$ . Finally, we define $\bar{\mathrm{\Theta }}={\bigcup }_{\mathit{\varphi }\in \mathrm{\Theta }}\bar{\mathit{\varphi }}$ . 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 $\mathsf{AS}=\mathrm{(}\mathcal{L}\mathrm{,}\mathcal{S}\mathrm{,}\mathcal{D}\mathrm{,}\mathcal{K}\mathrm{,}\mathit{n}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}⩽\mathrm{)}$ and ${\mathsf{AS}}^{\prime }=\mathrm{(}\mathcal{L}\mathrm{,}\mathcal{S}\mathrm{,}{\mathcal{D}}^{\prime }\mathrm{,}{\mathcal{K}}^{\prime }\mathrm{,}{\mathit{n}}^{\prime }\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}{⩽}^{\prime }\mathrm{)}$ , based on the same strict rule set $\mathcal{S}$ , are syntactically disjoint iff $\mathcal{D}\cup \mathcal{K}\cup \overline{\mathsf{head}[\mathcal{D}]}\cup \bar{\mathcal{K}}$ and ${\mathcal{D}}^{\prime }\cup {\mathcal{K}}^{\prime }\cup \overline{\mathsf{head}[{\mathcal{D}}^{\prime }]}\cup \overline{{\mathcal{K}}^{\prime }}$ are syntactically disjoint.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].

Definition 11.

Two argumentation systems, $\mathsf{AS}=\mathrm{(}\mathcal{L}\mathrm{,}\mathcal{S}\mathrm{,}\mathcal{D}\mathrm{,}\mathcal{K}\mathrm{,}\mathit{n}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}⩽\mathrm{)}$ and ${\mathsf{AS}}^{\prime }=\mathrm{(}\mathcal{L}\mathrm{,}{\mathcal{S}}^{\prime }\mathrm{,}{\mathcal{D}}^{\prime }\mathrm{,}{\mathcal{K}}^{\prime }\mathrm{,}{\mathit{n}}^{\prime }\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}{⩽}^{\prime }\mathrm{)}$ are strictly syntactically disjoint iff $\mathcal{D}\cup \mathcal{K}\cup \overline{\mathsf{head}[\mathcal{D}]}\cup \bar{\mathcal{K}}\cup \mathcal{S}\cup \overline{\mathsf{head}[\mathcal{S}]}$ and ${\mathcal{D}}^{\prime }\cup {\mathcal{K}}^{\prime }\cup \overline{\mathsf{head}[{\mathcal{D}}^{\prime }]}\cup \overline{{\mathcal{K}}^{\prime }}\cup {\mathcal{S}}^{\prime }\cup \overline{\mathsf{head}[{\mathcal{S}}^{\prime }]}$ are syntactically disjoint.

Furthermore, given $\mathsf{AS}=\mathrm{(}\mathcal{L}\mathrm{,}\mathcal{S}\mathrm{,}\mathcal{D}\mathrm{,}\mathcal{K}\mathrm{,}\mathit{n}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}⩽\mathrm{)}$ and ${\mathcal{D}}^{\prime }\subseteq \mathcal{D}$ , we will denote the set of arguments that can be constructed on the basis of ${\mathcal{D}}^{\prime }$ by $\mathsf{Args}\mathrm{(}{\mathcal{D}}^{\prime }\mathrm{)}=\{\mathit{a}\in \mathsf{Args}\mathrm{(}\mathsf{AS}\mathrm{)}\mid \mathcal{D}\mathrm{(}\mathit{a}\mathrm{)}\subseteq {\mathcal{D}}^{\prime }\}$ .

Postulate 4 (Non-Interference).

Non-Interference20

²⁰

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

is satisfied for a semantics $\mathtt{sem}$ if for any two syntactically disjoint argumentation system $\mathsf{AS}=\mathrm{(}\mathcal{L}\mathrm{,}\mathcal{S}\mathrm{,}\mathcal{D}\mathrm{,}\mathcal{K}\mathrm{,}\mathit{n}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}⩽\mathrm{)}$ and ${\mathsf{AS}}^{\prime }=\mathrm{(}\mathcal{L}\mathrm{,}\mathcal{S}\mathrm{,}{\mathcal{D}}^{\prime }\mathrm{,}{\mathcal{K}}^{\prime }\mathrm{,}{\mathit{n}}^{\prime }\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}{⩽}^{\prime }\mathrm{)}$ , where $\mathcal{K}\cup {\mathcal{K}}^{\prime }$ is $\mathcal{S}$ -consistent, ${⩽}^{+}$ is such that ⩽ [ ${⩽}^{\prime }$ ] is the restriction of ${⩽}^{+}$ to $\mathcal{D}\times \mathcal{D}$ [ ${\mathcal{D}}^{\prime }\times {\mathcal{D}}^{\prime }$ ], and ${\mathsf{AS}}^{+}=\mathrm{(}\mathcal{L}\mathrm{,}\mathcal{S}\mathrm{,}\mathcal{D}\cup {\mathcal{D}}^{\prime }\mathrm{,}\mathcal{K}\cup {\mathcal{K}}^{\prime }\mathrm{,}\mathit{n}\cup {\mathit{n}}^{\prime }\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}{⩽}^{+}\mathrm{)}$ , we have:

²¹

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.

$$\begin{array}{c}\mathtt{sem}\mathrm{\left(}{\mathsf{AS}}^{+}\mathrm{\right)}=\left\{\mathsf{Arg}\mathrm{\right(}\mathcal{D}[\mathcal{E}]\cup \mathcal{D}\left[{\mathcal{E}}^{\prime }\right]\mathrm{)}\subseteq \mathsf{Arg}\mathrm{(}{\mathsf{AS}}^{+}\mathrm{)}\mid \mathcal{E}\in \mathtt{sem}\mathrm{(}\mathsf{AS}\mathrm{)}\mathrm{,}{\mathcal{E}}^{\prime }\in \mathtt{sem}\mathrm{(}{\mathsf{AS}}^{\prime }\mathrm{\left)}\right\}.{}^{21}\end{array}$$

Postulate 5 (Strict Non-Interference).

Strict Non-Interference is satisfied for a semantics $\mathtt{sem}$ if for any two strictly syntactically disjoint argumentation systems $\mathsf{AS}=\mathrm{(}\mathcal{L}\mathrm{,}\mathcal{S}\mathrm{,}\mathcal{D}\mathrm{,}\mathcal{K}\mathrm{,}\mathit{n}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}⩽\mathrm{)}$ and ${\mathsf{AS}}^{\prime }=\mathrm{(}\mathcal{L}\mathrm{,}{\mathcal{S}}^{\prime }\mathrm{,}{\mathcal{D}}^{\prime }\mathrm{,}{\mathcal{K}}^{\prime }\mathrm{,}{\mathit{n}}^{\prime }\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}{⩽}^{\prime }\mathrm{)}$ , where ${⩽}^{+}$ is such that ⩽ [ ${⩽}^{\prime }$ ] is the restriction of ${⩽}^{+}$ to $\mathcal{D}\times \mathcal{D}$ [ ${\mathcal{D}}^{\prime }\times {\mathcal{D}}^{\prime }$ ], and ${\mathsf{AS}}^{+}=\mathrm{(}\mathcal{L}\mathrm{,}\mathcal{S}\cup {\mathcal{S}}^{\prime }\mathrm{,}\mathcal{D}\cup {\mathcal{D}}^{\prime }\mathrm{,}\mathcal{K}\cup {\mathcal{K}}^{\prime }\mathrm{,}\mathit{n}\cup {\mathit{n}}^{\prime }\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}{⩽}^{+}\mathrm{)}$ , we have: $$\begin{array}{c}\mathtt{sem}\mathrm{\left(}{\mathsf{AS}}^{+}\mathrm{\right)}=\left\{\mathsf{Arg}\mathrm{\right(}\mathcal{D}[\mathcal{E}]\cup \mathcal{D}\left[{\mathcal{E}}^{\prime }\right]\mathrm{)}\subseteq \mathsf{Arg}\mathrm{(}{\mathsf{AS}}^{+}\mathrm{)}\mid \mathcal{E}\in \mathtt{sem}\mathrm{(}\mathsf{AS}\mathrm{)}\mathrm{,}{\mathcal{E}}^{\prime }\in \mathtt{sem}\mathrm{(}{\mathsf{AS}}^{\prime }\mathrm{\left)}\right\}.\end{array}$$

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.

${\mathsf{AS}}_{\text{ 6}}=\mathrm{(}{\mathcal{L}}_{\mathsf{CL}}\mathrm{,}{\mathcal{S}}_{\mathsf{CL}}\mathrm{,}{\mathcal{D}}_{\text{6}}\mathrm{,}\varnothing \mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{)}$ where ${\mathcal{D}}_{\text{6}}=\{\top \Rightarrow \mathit{q}\}$ . Clearly the argument $\mathit{a}=⟨\top \Rightarrow \mathit{q}⟩$ is in the grounded extension.

Suppose now we move to the knowledge base ${\mathsf{AS}}_{\text{6}}^{\prime }=\mathrm{(}{\mathcal{L}}_{\mathsf{CL}}\mathrm{,}{\mathcal{S}}_{\mathsf{CL}}\mathrm{,}{\mathcal{D}}_{\text{6}}^{\prime }\mathrm{,}\varnothing \mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{)}$ where ${\mathcal{D}}_{\text{6}}^{\prime }={\mathcal{D}}_{\text{6}}\cup \{\top \Rightarrow \mathit{p};\top \Rightarrow \neg \mathit{p}\}$ . Informally, ${\mathsf{AS}}_{\text{6}}^{\prime }$ consists of ${\mathsf{AS}}_{\text{6}}$ supplemented with the syntactically disjoint rule base $\{\top \Rightarrow \mathit{p};\top \Rightarrow \neg \mathit{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: $$\begin{array}{cccc}\mathit{a}:\hfill & \top \Rightarrow \mathit{q}\hfill & {\mathit{b}}_1:\hfill & \top \Rightarrow \mathit{p}\hfill \\ {\mathit{b}}_2:\hfill & \top \Rightarrow \neg \mathit{p}\hfill & \mathit{b}:\hfill & {\mathit{b}}_1\mathrm{,}{\mathit{b}}_2\to \neg \mathit{q}\hfill \end{array}$$

This gives rise to the following framework:

We see that since ${⊢}_{\mathsf{CL}}$ satisfies ex falso quodlibet, the contradiction between p and $\neg \mathit{p}$ can be used to construct an argument for $\neg \mathit{q}$ that attacks a. Since there is no unattacked argument that defends a from b, a is no longer in the grounded extension of ${\mathsf{AS}}_{\text{6}}^{\prime }$ . 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 ${\mathsf{AS}}_{\text{6}}^{\prime }$ 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 $⩽=\mathcal{D}\times \mathcal{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

²²

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].

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 $\mathsf{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

²³

[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.

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 $\mathsf{Arg}\mathrm{(}{\mathsf{AS}}_{\text{6}}^{\prime }\mathrm{)}$ (which coincide with the stable extensions), namely $\{\mathit{a}\mathrm{,}{\mathit{b}}_1\}$ and $\{\mathit{a}\mathrm{,}{\mathit{b}}_2\}$ , 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. ${\mathit{b}}_1$ respectively ${\mathit{b}}_2$ ) 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.

${\mathsf{AS}}_{\text{7}}=\mathrm{(}{\mathcal{L}}_{\mathsf{CL}}\mathrm{,}{\mathcal{S}}_{\mathsf{CL}}\mathrm{,}{\mathcal{D}}_{\text{7}}\mathrm{,}\varnothing \mathrm{,}\mathit{n}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{)}$ where $$\begin{array}{c}{\mathcal{D}}_{\text{7}}=\left\{\begin{array}{cc}\hfill \top \Rightarrow \mathit{p};\hfill & \hfill \mathit{p}\Rightarrow \neg \mathit{n}\mathrm{(}\top \Rightarrow \mathit{p}\mathrm{)};\hfill \\ \hfill \mathit{p}\Rightarrow \mathit{q};\hfill & \hfill \mathit{p}\Rightarrow \neg \mathit{q};\hfill & \hfill \top \Rightarrow \mathit{s}\hfill \end{array}\right\}.\end{array}$$

We have (among others) the following arguments: $$\begin{array}{cccccc}\mathit{a}:\hfill & \top \Rightarrow \mathit{s}\hfill & \mathit{b}:\hfill & \top \Rightarrow \mathit{p}\hfill & \mathit{c}:\hfill & \mathit{b}\Rightarrow \neg \mathit{n}\mathrm{(}\top \Rightarrow \mathit{p}\mathrm{)}\hfill \\ {\mathit{d}}_1:\hfill & \mathit{b}\Rightarrow \mathit{q}\hfill & {\mathit{d}}_2:\hfill & \mathit{b}\Rightarrow \neg \mathit{q}\hfill & \mathit{d}:\hfill & {\mathit{d}}_1\mathrm{,}{\mathit{d}}_2\to \neg \mathit{s}\hfill \end{array}$$

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 ${\mathsf{AS}}_{\text{7}}^{\prime }=\mathrm{(}{\mathcal{L}}_{\mathsf{CL}}\mathrm{,}{\mathcal{S}}_{\mathsf{CL}}\mathrm{,}\{\top \Rightarrow \mathit{s}\}\mathrm{,}\varnothing \mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{)}$ , while adding the rules ${\mathcal{D}}_{\text{7}}\setminus \{\top \Rightarrow \mathit{s}\}$ , which are syntactically disjoint from $\{\top \Rightarrow \mathit{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 ${\mathrm{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 $\mathcal{S}$ is contrapositive, i.e., it satisfies the following two requirements:24

²⁴

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

S1

If Δ, $\mathit{\psi }{⊢}_{\mathcal{S}}{\mathit{\varphi }}^{\prime }$ for some ${\mathit{\varphi }}^{\prime }\in \bar{\mathit{\varphi }}$ , then Δ, $\mathit{\varphi }{⊢}_{\mathcal{S}}{\mathit{\psi }}^{\prime }$ for some ${\mathit{\psi }}^{\prime }\in \bar{\mathit{\psi }}$ ; and

S2

If $\mathrm{\Delta }{⊢}_{\mathcal{S}}{\mathit{\varphi }}^{\prime }$ for some ${\mathit{\varphi }}^{\prime }\in \bar{\mathit{\varphi }}$ , then $\mathrm{\Delta }\setminus \{\mathit{\varphi }\}{⊢}_{\mathcal{S}}{\mathit{\varphi }}^{\prime }$ .

Often, $\mathbf{S}\mathbf{2}$ will simply follow from $\mathbf{S}\mathbf{1}$ . More precisely, this is the case whenever $\mathcal{S}$ has theorems. We say that $\mathit{\varphi }\in \mathcal{L}$ is a theorem of $\mathcal{S}$ iff ${⊢}_{\mathcal{S}}\mathit{\varphi }$ .25

²⁵

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

Fact 3.

If $\mathcal{S}$ has theorems, then $\mathbf{S}\mathbf{1}$ implies $\mathbf{S}\mathbf{2}$ .

Proof.

Suppose γ is a theorem of $\mathcal{S}$ . Suppose Δ, $\mathit{\varphi }{⊢}_{\mathcal{S}}{\mathit{\varphi }}^{\prime }$ . By the monotonicity of ${⊢}_{\mathcal{S}}$ , γ, Δ, $\mathit{\varphi }{⊢}_{\mathcal{S}}{\mathit{\varphi }}^{\prime }$ . By $\mathbf{S}\mathbf{1}$ , there is a ${\mathit{\gamma }}^{\prime }\in \bar{\mathit{\gamma }}$ such that Δ, $\mathit{\varphi }{⊢}_{\mathcal{S}}{\mathit{\gamma }}^{\prime }$ . Again by $\mathbf{S}\mathbf{1}$ , Δ, $\mathit{\gamma }{⊢}_{\mathcal{S}}{\mathit{\varphi }}^{\prime }$ and by the transitivity of ${⊢}_{\mathcal{S}}$ , $\mathrm{\Delta }{⊢}_{\mathcal{S}}{\mathit{\varphi }}^{\prime }$ . □

Theorem 1.

For any $\mathsf{AS}=\mathrm{(}\mathcal{L}\mathrm{,}\mathcal{S}\mathrm{,}\mathcal{D}\mathrm{,}\mathcal{K}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}⩽\mathrm{)}$ where $\mathcal{S}$ satisfies $\mathbf{S}\mathbf{1}$ and $\mathbf{S}\mathbf{2}$ , $\mathtt{pref}\mathrm{(}\mathsf{AS}\mathrm{)}=\mathtt{stab}\mathrm{(}\mathsf{AS}\mathrm{)}$ .

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

²⁶

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

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

²⁷

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].

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

²⁸

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

However, even for argumentation systems with the trivial prefence relation $\mathcal{D}\times \mathcal{D}$ over the set of defeasible rules $\mathcal{D}$ , maximally conflict-free extensions might not be stable or preferred, as shown by the following example: Example 8.

Let ${\mathsf{AS}}_{\text{8}}=\mathrm{(}{\mathcal{L}}_{\mathsf{CL}}\mathrm{,}{\mathcal{S}}_{\mathsf{CL}}\mathrm{,}\{\top \Rightarrow \mathit{p}\}\mathrm{,}\{\neg \mathit{p}\}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{)}$ . This argumentation framework has a unique stable extension which is also preferred: $\{\mathit{a}\in \mathsf{Arg}\mathrm{(}{\mathsf{AS}}_{\text{8}}\mathrm{)}\mid \mathcal{D}\mathrm{(}\mathit{a}\mathrm{)}=\varnothing \}$ . However, the set $\{⟨\top ⟩\Rightarrow \mathit{p}\}$ is conflict-free. Thus, there is a maximally conflict-free set that includes $⟨\top ⟩\Rightarrow \mathit{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

²⁹

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

and is proven in Appendix C.1:

Theorem 2.

$\mathtt{pref}$ and $\mathtt{stab}$ satisfy Direct Consistency, Closure and Indirect Consistency for any $\mathsf{AS}=\mathrm{(}\mathcal{L}\mathrm{,}\mathcal{S}\mathrm{,}\mathcal{D}\mathrm{,}\mathcal{K}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}⩽\mathrm{)}$ for which $\mathcal{S}$ satisfies $\mathbf{S}\mathbf{1}$ and $\mathbf{S}\mathbf{2}$ .

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

³⁰

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

Definition 12.

A rule set $\mathcal{S}$ is uniform iff for any two sets of formulas Γ, ${\mathrm{\Gamma }}^{\prime }$ in $\mathcal{L}$ and any formula ϕ in $\mathcal{L}$ such that ${\mathrm{\Gamma }}^{\prime }$ is $\mathcal{S}$ -consistent and syntactically disjoint from $\mathrm{\Gamma }\cup \{\mathit{\varphi }\}$ , it holds that $\mathrm{\Gamma }{⊢}_{\mathcal{S}}\mathit{\varphi }$ iff $\mathrm{\Gamma }\cup {\mathrm{\Gamma }}^{\prime }{⊢}_{\mathcal{S}}\mathit{\varphi }$ .

Non-Interference for ${\mathrm{ASPIC}}^{+}$ for prioritized rule bases was not shown before and is proven in Appendix C:

Theorem 3.

$\mathtt{pref}$ and $\mathtt{stab}$ satisfy Non-Interference for any argumentation systems whose sets of strict rules are uniform and satisfy $\mathbf{S}\mathbf{1}$ and $\mathbf{S}\mathbf{2}$ .

In particular, this means that an argumentation system that is induced by classical logic satisfies non-interference. In more detail, we say that $\mathsf{AS}=\mathrm{(}\mathcal{L}\mathrm{,}\mathcal{S}\mathrm{,}\mathcal{D}\mathrm{,}\mathcal{K}\mathrm{,}\mathit{n}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}⩽\mathrm{)}$ is induced by classical logic if $\mathcal{L}$ is closed under the classical connectives $\{\neg \mathrm{,}\wedge \mathrm{,}\vee \}$ and $\mathcal{S}$ is the set of strict rules capturing classical logic $\mathsf{CL}$ (over $\mathcal{L}$ ): ${\mathit{\varphi }}_1\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{n}}\to \mathit{\varphi }\in \mathcal{S}$ iff $\{{\mathit{\varphi }}_1\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{n}}\}{⊢}_{\mathsf{CL}}\mathit{\varphi }$ . For a concrete example, see Example 2.

Fact 4.

Where $\mathsf{AS}=\mathrm{(}\mathcal{L}\mathrm{,}\mathcal{S}\mathrm{,}\mathcal{D}\mathrm{,}\mathcal{K}\mathrm{,}\mathit{n}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}⩽\mathrm{)}$ is induced by classical logic, $\mathcal{S}$ is uniform and satisfies $\mathbf{S}\mathbf{1}$ and $\mathbf{S}\mathbf{2}$ .

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

Theorem 4.

$\mathtt{pref}$ and $\mathtt{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 $\mathbf{S}\mathbf{1}$ and $\mathbf{S}\mathbf{2}$ .

Theorem 5.

$\mathtt{pref}$ and $\mathtt{stab}$ satisfy Strict Non-Interference for any argumentation systems with sets of strict rules $\mathcal{S}$ that satisfy $\mathbf{S}\mathbf{1}$ and $\mathbf{S}\mathbf{2}$ .

The reader may wonder why $\mathbf{S}\mathbf{1}$ and $\mathbf{S}\mathbf{2}$ are needed. We first note that both $\mathbf{S}\mathbf{1}$ and $\mathbf{S}\mathbf{2}$ are very much in line with the interpretation of strict rules S as truth-preserving rules. For example, $\mathbf{S}\mathbf{1}$ requires that if $\mathrm{\Delta }{⊢}_{\mathcal{S}}\mathit{A}$ for some $\mathit{A}\in \bar{\mathit{B}}$ (i.e. Δ implies the falsity of B), then if B is true, one of the members of Δ must be false. Likewise, $\mathbf{S}\mathbf{2}$ requires that if Δ can be used to derive $\mathit{A}\in \bar{\mathit{B}}$ , i.e. show that B is false, B does not have to be assumed true.

From the perspective of the argumentative rationality postulates, $\mathbf{S}\mathbf{1}$ ensures that whenever an argument a is attacked by an argument $\mathit{b}={\mathit{b}}_1\mathrm{,}\dots \mathrm{,}{\mathit{b}}_{\mathit{n}}\to \overline{\mathsf{Conc}\mathrm{(}\mathit{a}\mathrm{)}}$ , we can construct the contraposed argument ${\mathit{b}}_2\mathrm{,}\dots \mathrm{,}{\mathit{b}}_{\mathit{n}}\mathrm{,}\mathit{a}\to \overline{\mathsf{Conc}\mathrm{(}{\mathit{b}}_1\mathrm{)}}$ . If we cannot do this, several rationality postulates are violated.

Example 9.

${\mathsf{AS}}_{\text{ 9}}=\mathrm{(}\{\mathit{p}\mathrm{,}\mathit{q}\mathrm{,}\mathit{s}\mathrm{,}\mathit{r}\mathrm{,}{\mathit{p}}^{\prime }\mathrm{,}{\mathit{q}}^{\prime }\mathrm{,}{\mathit{s}}^{\prime }\mathrm{,}{\mathit{r}}^{\prime }\}\mathrm{,}{\mathcal{S}}_{\text{9}}\mathrm{,}{\mathcal{D}}_{\text{9}}\mathrm{,}\{\mathit{s}\}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}{⩽}_{\text{9}}\mathrm{)}$ where ${\mathcal{S}}_{\text{9}}=\{\mathit{q}\to {\mathit{r}}^{\prime }\}$ and ${\mathcal{D}}_{\text{9}}=\{\mathit{s}\Rightarrow \mathit{q}\mathrm{,}\mathit{s}\Rightarrow \mathit{r}\}$ , $\bar{\mathit{\varphi }}=\{{\mathit{\varphi }}^{\prime }\}$ and $\overline{{\mathit{\varphi }}^{\prime }}=\{\mathit{\varphi }\}$ for any $\mathit{\varphi }\in \mathcal{L}$ , and $\mathit{s}\Rightarrow \mathit{q}{\mathrm{<}}_9\mathit{s}\Rightarrow \mathit{r}$ . We have the following arguments: $$\begin{array}{cccc}\mathit{a}:\hfill & ⟨\mathit{s}⟩\hfill & \mathit{b}:\hfill & \mathit{a}\Rightarrow \mathit{q}\hfill \\ \mathit{c}:\hfill & \mathit{b}\to {\mathit{r}}^{\prime }\hfill & \mathit{d}:\hfill & \mathit{a}\Rightarrow \mathit{r}\hfill \end{array}$$

Notice that c attacks but does not defeat d since $\mathcal{D}\mathrm{(}\mathit{c}\mathrm{)}{\prec }_{\text{9}}\mathcal{D}\mathrm{(}\mathit{d}\mathrm{)}$ . 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 ${\mathit{r}}^{\prime }$ (namely d).

$\mathbf{S}\mathbf{2}$ ensures, among other things, that a defeasible argument concluding an ${⊢}_{\mathcal{S}}$ -anti-theorem or contradiction (i.e., a formula ϕ for which ${⊢}_{\mathcal{S}}\bar{\mathit{\varphi }}$ such as $\mathit{p}\wedge \neg \mathit{p}$ in classical logic) is attacked by a strict argument (namely $\to \bar{\mathit{\varphi }}$ ). As such, $\mathbf{S}\mathbf{2}$ 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 $\mathcal{S}$ that have explosive behavior: Example 10.

Where ${\mathcal{L}}_{\text{10}}=\{\mathit{p}\mathrm{,}\mathit{q}\mathrm{,}\mathit{r}\mathrm{,}{\mathit{q}}^{\prime }\mathrm{,}{\mathit{r}}^{\prime }\}$ , ${\mathcal{D}}_{\text{10}}=\{{\Rightarrow }_1\mathit{r}\}$ , ${\mathcal{D}}_{\text{10}}^{\prime }=\{{\Rightarrow }_2\mathit{p};\mathit{p}{\Rightarrow }_1\mathit{q};\mathit{p}{\Rightarrow }_1{\mathit{q}}^{\prime }\}$ , $\bar{\mathit{p}}=\{\mathit{p}\}$ (i.e. p is a falsity), $\overline{{\mathit{q}}^{\prime }}=\{\mathit{q}\}$ , $\bar{\mathit{q}}=\{{\mathit{q}}^{\prime }\}$ , $\bar{\mathit{r}}=\{{\mathit{r}}^{\prime }\}$ , $\overline{{\mathit{r}}^{\prime }}=\{\mathit{r}\}$ , and $$\begin{array}{c}{\mathcal{S}}_{\text{10}}=\{\mathit{q}\mathrm{,}\neg \mathit{q}\to \mathit{\varphi }\mid \mathit{\varphi }\in {\mathcal{L}}_{\text{10}}\}\cup \{\mathit{p}\to \mathit{\varphi }\mid \mathit{\varphi }\in {\mathcal{L}}_{\text{10}}\}\cup \{\mathit{\varphi }\to \mathit{p}\mid \mathit{\varphi }\in {\mathcal{L}}_{\text{10}}\}\mathrm{,}\end{array}$$ and ${⩽}^{\prime }\subseteq {\mathrm{(}{\mathcal{D}}_{\text{10}}\cup {\mathcal{D}}_{\text{10}}^{\prime }\mathrm{)}}^2$ ranks the defeasible rules according to their subscripts, consider ${\mathsf{AS}}_{\text{10}}=\mathrm{(}{\mathcal{L}}_{\text{10}}\mathrm{,}{\mathcal{S}}_{\text{10}}\mathrm{,}{\mathcal{D}}_{\text{10}}\mathrm{,}\varnothing \mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}⩽\mathrm{)}$ and ${\mathsf{A}{S}^{\prime }}_{\text{10}}=\mathrm{(}{\mathcal{L}}_{\text{10}}\mathrm{,}{\mathcal{S}}_{\text{10}}\mathrm{,}{\mathcal{D}}_{\text{10}}\cup {\mathcal{D}}_{\text{10}}^{\prime }\mathrm{,}\varnothing \mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}{⩽}^{\prime }\mathrm{)}$ . We get, for instance, the following arguments: $$\begin{array}{cccccc}{\mathit{a}}_1:\hfill & \Rightarrow \mathit{p}\hfill & {\mathit{a}}_2:\hfill & {\mathit{a}}_1\Rightarrow \mathit{q}\hfill & {\mathit{a}}_3:\hfill & {\mathit{a}}_1\Rightarrow {\mathit{q}}^{\prime }\hfill \\ {\mathit{a}}_4:\hfill & {\mathit{a}}_2\mathrm{,}{\mathit{a}}_3\to {\mathit{r}}^{\prime }\hfill & {\mathit{a}}_5:\hfill & \Rightarrow \mathit{r}\hfill \end{array}$$

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 ${\mathsf{AS}}_{\text{10}}$ 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 $\mathcal{S}$ satisfies $\mathbf{S}\mathbf{1}$ , $\mathbf{S}\mathbf{2}$ does not hold since $\{\mathit{p}\}{⊢}_{\mathcal{S}}\mathit{p}$ while ${⊬}_{\mathcal{S}}\mathit{p}$ (recall that $\mathit{p}\in \bar{\mathit{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

³¹

This example was suggested to us by a reviewer.

Example 11.

Let ${\mathsf{AS}}_{\text{11}}=\mathrm{(}\{\mathit{p}\mathrm{,}\mathit{q}\mathrm{,}\top \}\mathrm{,}{\mathcal{S}}_{\text{11}}\mathrm{,}{\mathcal{D}}_{\text{11}}\mathrm{,}\varnothing \mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{)}$ where ${\mathcal{S}}_{\text{11}}=\varnothing$ , ${\mathcal{D}}_{\text{11}}=\{\top \Rightarrow \mathit{p};\mathit{p}\Rightarrow \mathit{q}\}$ , $\bar{\mathit{q}}=\varnothing$ and $\bar{\mathit{p}}=\{\mathit{q}\}$ . Then $\mathsf{Args}\mathrm{(}{\mathsf{AS}}_{\text{11}}\mathrm{)}$ consists, among others, of the following two arguments: $$\begin{array}{cccc}\mathit{a}:\hfill & ⟨\top ⟩\Rightarrow \mathit{p}\hfill & \mathit{b}:\hfill & {\mathit{a}}_1\Rightarrow \mathit{q}\hfill \end{array}$$

Notice that b defeats a and itself. Hence there is no stable extension while the unique preferred extension is ∅, thus $\{\varnothing \}=\mathtt{pref}\mathrm{(}{\mathsf{AS}}_{\text{11}}\mathrm{)}\ne \mathtt{stab}\mathrm{(}{\mathsf{AS}}_{\text{11}}\mathrm{)}=\varnothing$ .

However, the above example does not constitute a counterexample to Theorem 1, since in fact ${\mathcal{S}}_{\text{11}}$ violates $\mathbf{S}\mathbf{1}$ . Indeed $\{\mathit{q}\}{⊢}_{\mathcal{S}}\mathit{q}$ and $\mathit{q}\in \bar{\mathit{p}}$ yet there is no ${\mathit{q}}^{\prime }\in \bar{\mathit{q}}$ such that $\{\mathit{p}\}{⊢}_{\mathcal{S}}{\mathit{q}}^{\prime }$ . In fact, for any rule base that satisfies $\mathbf{S}\mathbf{1}$ , the set of contraries will be (pseudo-)symmetric in the sense that if there is a $\mathit{\varphi }\in \bar{\mathit{\psi }}$ then there is a ${\mathit{\varphi }}^{\prime }\in \bar{\mathit{\varphi }}$ for which $\mathit{\psi }{⊢}_{\mathcal{S}}{\mathit{\varphi }}^{\prime }$ . Notice that this is weaker than symmetry as it is perhaps usually understood, i.e. if $\mathit{\varphi }\in \bar{\mathit{\psi }}$ then $\mathit{\psi }\in \bar{\mathit{\varphi }}$ . Fact 5.

If $\mathcal{S}$ satisfies $\mathbf{S}\mathbf{1}$ and $\mathit{\varphi }\in \bar{\mathit{\psi }}$ , there is a ${\mathit{\varphi }}^{\prime }\in \bar{\mathit{\varphi }}$ such that $\mathit{\psi }{⊢}_{\mathcal{S}}{\mathit{\varphi }}^{\prime }$ .

Proof.

Suppose that $\mathcal{S}$ satisfies $\mathbf{S}\mathbf{1}$ and $\mathit{\varphi }\in \bar{\mathit{\psi }}$ . Since $\mathit{\varphi }{⊢}_{\mathcal{S}}\mathit{\varphi }$ , with $\mathbf{S}\mathbf{1}$ there is some ${\mathit{\varphi }}^{\prime }\in \bar{\mathit{\varphi }}$ for which $\mathit{\psi }{⊢}_{\mathcal{S}}{\mathit{\varphi }}^{\prime }$ . □

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 $\mathcal{D}$ to be consistent, given a fixed context of strict rules $\mathcal{S}$ and of (strict) premises $\mathcal{K}$ .

Definition 13.

Where $\mathrm{\Delta }\subseteq \mathcal{D}$ , we define $\mathrm{\Delta }{⊢}_{\mathcal{K}}^{\mathcal{S}}\mathit{\varphi }$ by $\mathcal{K}{⊢}_{\mathcal{S}\cup \mathrm{\Delta }}\mathit{\varphi }$ (see Definition 8).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 $\mathcal{L}$ -formulas (Def. 8), or a set of formulas in $\mathcal{L}$ and a set of rules (Def. 13).

Where the context disambiguates, we simply write ${⊢}_{\mathcal{K}}$ instead of ${⊢}_{\mathcal{K}}^{\mathcal{S}}$ . Simply expressed, ϕ follows from Δ if it can be derived by applying modus ponens for premises in $\mathcal{K}$ and rules in $\mathcal{S}\cup \mathrm{\Delta }$ . Where the context disambiguates, we will omit the sub-script $\mathcal{K}$ and simply write $\mathrm{\Delta }⊢\mathit{\varphi }$ .

Definition 14.

Where $\mathrm{\Delta }\subseteq \mathcal{D}$ , Δ is ${⊢}_{\mathcal{K}}^{\mathcal{S}}$ -inconsistent iff there is a formula ϕ and a $\mathit{\psi }\in \bar{\mathit{\varphi }}$ for which $\mathrm{\Delta }{⊢}_{\mathcal{K}}^{\mathcal{S}}\mathit{\psi }$ and $\mathrm{\Delta }{⊢}_{\mathcal{K}}^{\mathcal{S}}\mathit{\varphi }$ . Otherwise Δ is ${⊢}_{\mathcal{K}}^{\mathcal{S}}$ -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 $\mathit{A}\mathit{S}=\mathrm{(}\mathcal{L}\mathrm{,}\mathcal{S}\mathrm{,}\mathcal{D}\mathrm{,}\mathcal{K}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}⩽\mathrm{)}$ .

According to naive rule maximizing we collect as many defeasible rules as is consistently possible. Let for this ${\mathsf{MCS}}_{\mathsf{na}}^{\mathcal{S}\mathrm{,}\mathcal{K}}\mathrm{(}\mathcal{D}\mathrm{)}$ be the set of all ${⊢}_{\mathcal{K}}^{\mathcal{S}}$ -consistent $\mathrm{\Delta }\subseteq \mathcal{D}$ for which there is no ${⊢}_{\mathcal{K}}^{\mathcal{S}}$ -consistent ${\mathrm{\Delta }}^{\prime }\subseteq \mathcal{D}$ such that $\mathrm{\Delta }\subset {\mathrm{\Delta }}^{\prime }$ .33

³³

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

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 ${\mathsf{AS}}_{\text{12}}=\mathrm{(}{\mathcal{L}}_{\mathsf{CL}}\mathrm{,}{\mathcal{S}}_{\mathsf{CL}}\mathrm{,}{\mathcal{D}}_{\text{12}}\mathrm{,}\varnothing \mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{)}$ where $\mathit{\psi }\in \bar{\mathit{\varphi }}$ iff $\mathit{\psi }=\neg \mathit{\varphi }$ or $\mathit{\varphi }=\neg \mathit{\psi }$ and ${\mathcal{D}}_{\text{12}}=\{{\mathit{r}}_1:\top \Rightarrow \mathit{p}\mathrm{,}{\mathit{r}}_2:\mathit{p}\Rightarrow \mathit{q}\mathrm{,}{\mathit{r}}_3:\top \Rightarrow \neg \mathit{q}\}$ .

Then ${\mathsf{MCS}}_{\mathsf{na}}^{{\mathcal{S}}_{\mathsf{CL}}\mathrm{,}\varnothing }=\{{\mathrm{\Delta }}_1:\{{\mathit{r}}_1\mathrm{,}{\mathit{r}}_2\}\mathrm{,}{\mathrm{\Delta }}_2:\{{\mathit{r}}_1\mathrm{,}{\mathit{r}}_3\}\mathrm{,}{\mathrm{\Delta }}_3:\{{\mathit{r}}_2\mathrm{,}{\mathit{r}}_3\}\}$ . However, if we consider the argumentation framework based on the same ingredients, we will have two preferred (resp. stable) extensions: ${\mathcal{E}}_1=\{{\mathit{a}}_1\mathrm{,}{\mathit{a}}_2\mathrm{,}\dots \}$ and ${\mathcal{E}}_2=\{{\mathit{a}}_1\mathrm{,}{\mathit{a}}_3\mathrm{,}\dots \}$ where ${\mathit{a}}_1=\top \Rightarrow \mathit{p}$ , ${\mathit{a}}_2={\mathit{a}}_1\Rightarrow \mathit{q}$ and ${\mathit{a}}_3=\top \Rightarrow \neg \mathit{q}$ . Note that both extensions contain ${\mathit{a}}_1=\top \Rightarrow \mathit{p}$ . This contrasts with the maximal consistent set ${\mathrm{\Delta }}_3=\{{\mathit{r}}_2\mathrm{,}{\mathit{r}}_3\}$ .

The problem with the set $\{{\mathit{r}}_2\mathrm{,}{\mathit{r}}_3\}$ in our example is that it is not “grounded”: the rule ${\mathit{r}}_2$ cannot be triggered: indeed, $\{{\mathit{r}}_2\mathrm{,}{\mathit{r}}_3\}{⊬}_{\mathcal{K}}\mathit{p}$ where $\mathsf{body}\mathrm{(}{\mathit{r}}_2\mathrm{)}=\{\mathit{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 $\mathrm{\Delta }⊢\mathit{\psi }$ for each $\mathit{\psi }\in \mathsf{body}[\mathrm{\Delta }]$ .

Definition 15.

Where $\mathrm{\Delta }\subseteq \mathcal{D}$ and $\mathit{r}\in \mathcal{D}$ , r is ${⊢}_{\mathcal{K}}^{\mathcal{S}}$ -triggered by Δ iff $\mathrm{\Delta }{⊢}_{\mathcal{K}}^{\mathcal{S}}\mathit{\psi }$ for each $\mathit{\psi }\in \mathsf{body}\mathrm{(}\mathit{r}\mathrm{)}$ . We will also call Δ a ${⊢}_{\mathcal{K}}^{\mathcal{S}}$ -trigger set of r. Let ${\hat{\mathrm{\wp }}}^{\mathcal{S}\mathrm{,}\mathcal{K}}\mathrm{(}\mathcal{D}\mathrm{)}$ be the set of all $\mathrm{\Delta }\in \mathrm{\wp }\mathrm{(}\mathcal{D}\mathrm{)}$ such that every $\mathit{r}\in \mathrm{\Delta }$ is ${⊢}_{\mathcal{K}}^{\mathcal{S}}$ -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 ${\hat{\mathrm{\wp }}}^{\mathcal{S}\mathrm{,}\mathcal{K}}$ by $\hat{\mathrm{\wp }}$ .

Fact 6.

Where $\mathrm{\Delta }\in \hat{\mathrm{\wp }}\mathrm{(}\mathcal{D}\mathrm{)}$ , Δ is inconsistent iff there are $\mathit{\varphi }\in \mathsf{head}[\mathrm{\Delta }]$ and $\mathit{\psi }\in \bar{\mathit{\varphi }}$ for which $\mathrm{\Delta }{⊢}_{\mathcal{K}}\mathit{\psi }$ .

Proof.

For the right-to-left direction suppose there are $\mathit{\varphi }\in \mathsf{head}[\mathrm{\Delta }]$ and $\mathit{\psi }\in \bar{\mathit{\varphi }}$ for which $\mathrm{\Delta }{⊢}_{\mathcal{K}}\mathit{\psi }$ . Since $\mathrm{\Delta }\in \hat{\mathrm{\wp }}\mathrm{(}\mathcal{D}\mathrm{)}$ also $\mathrm{\Delta }{⊢}_{\mathcal{K}}\mathit{\varphi }$ 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 $\mathcal{K}=\{\mathit{d}\mathrm{,}\mathit{s}\mathrm{,}\mathit{t}\}$ , $\mathrm{\Delta }=\{\mathit{d}\Rightarrow \mathit{e};\mathit{u}\mathrm{,}\mathit{t}\Rightarrow \mathit{p}\}$ and $\mathit{s}\to \mathit{u}$ and $\mathit{e}\mathrm{,}\mathit{u}\to {\mathit{p}}^{\prime }$ are strict rules and ${\mathit{p}}^{\prime }\in \bar{\mathit{p}}$ we have the following two proofs (in tree form) demonstrating that $\mathrm{\Delta }{⊢}_{\mathcal{K}}\mathit{p}$ and $\mathrm{\Delta }{⊢}_{\mathcal{K}}{\mathit{p}}^{\prime }$ : $$\begin{array}{l}\hfill {\mathit{P}}_1=\left.\begin{array}{c}\hfill \mathit{d}\Rightarrow \mathit{e}\hfill \\ \hfill \mathit{s}\to \mathit{u}\hfill \end{array}\right]\to {\mathit{p}}^{\prime }{\mathit{P}}_2=\mathit{t}\Rightarrow \mathit{p}\end{array}$$

By contraposition, also $\mathit{u}\mathrm{,}\mathit{p}\to {\mathit{e}}^{\prime }$ is a rule for some ${\mathit{e}}^{\prime }\in \bar{\mathit{e}}$ . So, we have the following proof $$\begin{array}{c}{\mathit{P}}_3=\left.\begin{array}{c}\hfill \mathit{t}\Rightarrow \mathit{p}\hfill \\ \hfill \mathit{s}\to \mathit{u}\hfill \end{array}\right]\to {\mathit{e}}^{\prime }\mathrm{,}\end{array}$$ which shows that $\mathrm{\Delta }{⊢}_{\mathcal{K}}{\mathit{e}}^{\prime }$ .

 □

Definition 16.

${\mathsf{MCS}}^{\mathcal{S}\mathrm{,}\mathcal{K}}\mathrm{(}\mathcal{D}\mathrm{)}$ is the set of all consistent $\mathrm{\Delta }\in \hat{\mathrm{\wp }}\mathrm{(}\mathcal{D}\mathrm{)}$ for which there is no consistent ${\mathrm{\Delta }}^{\prime }\in \hat{\mathrm{\wp }}\mathrm{(}\mathcal{D}\mathrm{)}$ such that $\mathrm{\Delta }\subset {\mathrm{\Delta }}^{\prime }$ .

Where the context disambiguates, we will omit the superscript and simply write $\mathsf{MCS}\mathrm{(}\mathcal{D}\mathrm{)}$ .

Example 14 (Example 12 cont.).

We have $\mathsf{MCS}\mathrm{(}\mathcal{D}\mathrm{)}=\{{\mathrm{\Delta }}_1:\{{\mathit{r}}_1\mathrm{,}{\mathit{r}}_2\}\mathrm{,}{\mathrm{\Delta }}_2:\{{\mathit{r}}_1\mathrm{,}{\mathit{r}}_3\}\}$ . Note that ${\mathrm{\Delta }}_1{⊢}_{\mathcal{K}}\mathit{p}$ and ${\mathrm{\Delta }}_2{⊢}_{\mathcal{K}}\mathit{p}$ just like both argumentation extensions contain arguments for p.

There is indeed a very close relationship between the set ${\mathsf{MCS}}^{\mathcal{S}\mathrm{,}\mathcal{K}}\mathrm{(}\mathcal{D}\mathrm{)}$ and the preferred resp. stable extensions of $\mathsf{AS}=⟨\mathcal{L}\mathrm{,}\mathcal{S}\mathrm{,}\mathcal{D}\mathrm{,}\mathcal{K}\mathrm{,}\overline{\phantom{\mathit{A}}}⟩$ . To state it we introduce one more notation.

Definition 17.

Where $\mathrm{\Delta }\subseteq \mathcal{D}$ let $\mathsf{Arg}\mathrm{(}\mathrm{\Delta }\mathrm{)}{=}_{\mathsf{df}}\{\mathit{a}\in \mathsf{Arg}\mathrm{(}\mathsf{AS}\mathrm{)}\mid \mathcal{D}\mathrm{(}\mathit{a}\mathrm{)}\subseteq \mathrm{\Delta }\}$ 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 $\mathsf{AS}=\mathrm{(}\mathcal{L}\mathrm{,}\mathcal{S}\mathrm{,}\mathcal{D}\mathrm{,}\mathcal{K}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{)}$ where $\mathcal{S}$ satisfies $\mathbf{S}\mathbf{1}$ and $\mathbf{S}\mathbf{2}$ , $$\begin{array}{c}\mathtt{pref}\mathrm{(}\mathsf{AS}\mathrm{)}=\mathtt{stab}\mathrm{(}\mathsf{AS}\mathrm{)}=\{\mathsf{Arg}\mathrm{(}\mathrm{\Delta }\mathrm{)}\mid \mathrm{\Delta }\in \mathsf{MCS}\mathrm{(}\mathcal{D}\mathrm{)}\}.\end{array}$$

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 $\bigcap \mathsf{MCS}\mathrm{(}\mathcal{D}\mathrm{)}$ . We give the following counter-example:

Example 15 (Example 6 continued).

Recall ${\mathsf{AS}}_{\text{6}}^{\prime }$ from Example 6. We have $\mathsf{MCS}\mathrm{(}{\mathcal{D}}_{\text{6}}^{\prime }\mathrm{)}=\{\{\top \Rightarrow \mathit{p}\mathrm{,}\top \Rightarrow \mathit{q}\}\mathrm{,}\{\top \Rightarrow \neg \mathit{p}\mathrm{,}\top \Rightarrow \mathit{q}\}\}$ , $\{\top \Rightarrow \mathit{q}\}=\bigcap \mathsf{MCS}\mathrm{(}{\mathcal{D}}_{\text{6}}^{\prime }\mathrm{)}$ and $\{\top \Rightarrow \mathit{q}\}\in \hat{\mathrm{\wp }}\mathrm{(}{\mathcal{D}}_{\text{6}}^{\prime }\mathrm{)}$ . However, the grounded extension is $\mathsf{Arg}\mathrm{(}\varnothing \mathrm{)}$ . Recall for this that the argument $\mathit{b}=⟨\top \Rightarrow \mathit{p}⟩\mathrm{,}⟨\top \Rightarrow \neg \mathit{p}⟩\to \neg \mathit{q}$ attacks $\mathit{a}=⟨\top \Rightarrow \mathit{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 ${\mathit{a}}_{\perp }$ 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 ${\mathit{a}}_{\perp }$ [57].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.

Definition 18.

Let ${\mathsf{Arg}}^{\top }\mathrm{(}\mathsf{AS}\mathrm{)}$ be the set of all consistent arguments a in $\mathsf{Arg}\mathrm{(}\mathsf{AS}\mathrm{)}$ , where a is consistent iff $\mathcal{D}\mathrm{(}\mathit{a}\mathrm{)}$ is consistent (see Definition 14). Similarly, where $\mathtt{sem}\in \{\mathtt{pref}\mathrm{,}\mathtt{stab}\mathrm{,}\mathtt{groun}\}$ , let ${\mathtt{sem}}^{\top }\mathrm{(}\mathsf{AS}\mathrm{)}$ be the set of extension of the restriction of $⟨\mathsf{Arg}\mathrm{(}\mathsf{AS}\mathrm{)}\mathrm{,}⇝\mathrm{(}\mathsf{AS}\mathrm{)}⟩$ 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 $\bigcap \mathsf{MCS}\mathrm{(}\mathcal{D}\mathrm{)}\in \hat{\mathrm{\wp }}\mathrm{(}\mathcal{D}\mathrm{)}$ .

Example 16.

${\mathsf{AS}}_{\text{ 16}}=\mathrm{(}{\mathcal{L}}_{\mathsf{CL}}\mathrm{,}{\mathcal{S}}_{\mathsf{CL}}\mathrm{,}{\mathcal{D}}_{\text{16}}\mathrm{,}\varnothing \mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{)}$ where $\mathit{\psi }\in \bar{\mathit{\varphi }}$ iff $\mathit{\psi }=\neg \mathit{\varphi }$ or $\mathit{\varphi }=\neg \mathit{\psi }$ and ${\mathcal{D}}_{\text{16}}=\{{\mathit{r}}_1:\top \Rightarrow \mathit{p}\mathrm{,}{\mathit{r}}_2:\top \Rightarrow \neg \mathit{p}\mathrm{,}{\mathit{r}}_3:\mathit{p}\Rightarrow \mathit{q}\mathrm{,}{\mathit{r}}_4:\neg \mathit{p}\Rightarrow \mathit{q}\mathrm{,}{\mathit{r}}_5:\mathit{q}\Rightarrow \mathit{s}\}$ . Then $\mathsf{MCS}\mathrm{(}{\mathcal{D}}_{\text{16}}\mathrm{)}=\{\{{\mathit{r}}_1\mathrm{,}{\mathit{r}}_3\mathrm{,}{\mathit{r}}_5\}\mathrm{,}\{{\mathit{r}}_2\mathrm{,}{\mathit{r}}_4\mathrm{,}{\mathit{r}}_5\}\}$ . Note that $\bigcap \mathsf{MCS}\mathrm{(}{\mathcal{D}}_{\text{16}}\mathrm{)}=\{{\mathit{r}}_5\}\notin \hat{\mathrm{\wp }}\mathrm{(}\mathcal{D}\mathrm{)}$ .

In the Appendix (Lemma 6) we show that there is a unique ⊂-maximal $\mathrm{\Delta }\in \hat{\mathrm{\wp }}\mathrm{(}\mathcal{D}\mathrm{)}$ that is contained in $\bigcap \mathsf{MCS}\mathrm{(}\mathcal{D}\mathrm{)}$ .

Definition 19.

We call the unique ⊆-maximal $\mathrm{\Delta }\in \hat{\mathrm{\wp }}\mathrm{(}\mathcal{D}\mathrm{)}$ that is contained in $\bigcap \mathsf{MCS}\mathrm{(}\mathcal{D}\mathrm{)}$ the free set in $\mathcal{D}$ , denoted by $\mathsf{Free}\mathrm{(}\mathcal{D}\mathrm{)}$ .

The set $\mathsf{Free}\mathrm{(}\mathcal{D}\mathrm{)}$ characterizes the grounded extension when filtering out inconsistent arguments.

Theorem 7.

Where $\mathsf{AS}=\mathrm{(}\mathcal{L}\mathrm{,}\mathcal{S}\mathrm{,}\mathcal{D}\mathrm{,}\mathcal{K}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{)}$ and $\mathcal{S}$ satisfies $\mathbf{S}\mathbf{1}$ and $\mathbf{S}\mathbf{2}$ , $\mathsf{Arg}\mathrm{(}\mathsf{Free}\mathrm{(}\mathcal{D}\mathrm{)}\mathrm{)}={\mathtt{groun}}^{\top }\mathrm{(}\mathsf{AS}\mathrm{)}$ .

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 $\mathsf{AS}=\mathrm{(}\mathcal{L}\mathrm{,}\mathcal{S}\mathrm{,}\mathcal{D}\mathrm{,}\mathcal{K}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{)}$ where $\mathcal{S}$ satisfies $\mathbf{S}\mathbf{1}$ and $\mathbf{S}\mathbf{2}$ , $$\begin{array}{c}\mathtt{pref}\mathrm{(}\mathsf{AS}\mathrm{)}=\mathtt{stab}\mathrm{(}\mathsf{AS}\mathrm{)}={\mathtt{pref}}^{\top }\mathrm{(}\mathsf{AS}\mathrm{)}={\mathtt{stab}}^{\top }\mathrm{(}\mathsf{AS}\mathrm{)}=\{\mathsf{Arg}\mathrm{(}\mathrm{\Delta }\mathrm{)}\mid \mathrm{\Delta }\in \mathsf{MCS}\mathrm{(}\mathcal{D}\mathrm{)}\}.\end{array}$$

4.3.2. The prioritized case

We now move to prioritized frameworks. Stable and preferred extensions can be characterized by selecting a subset of $\mathsf{MCS}\mathrm{(}\mathcal{D}\mathrm{)}$ . For this, we introduce a new priority-sensitive notion of consistency. Recall that the defeasible rules in $\mathcal{D}$ are ranked by a total order ⩽. This means that, without loss of generality, we can assume that the defeasible rules in $\mathcal{D}$ are ranked relative to a (finite) set of natural numbers. We denote this ranking by $\mathcal{R}:\mathcal{D}\to \mathbb{N}$ . Where $\mathrm{\Delta }\subseteq \mathcal{D}$ , let $\mathcal{R}[\mathrm{\Delta }]{=}_{\mathsf{df}}min\mathrm{(}\{\mathcal{R}\mathrm{(}\mathit{r}\mathrm{)}\mid \mathit{r}\in \mathrm{\Delta }\}\mathrm{)}$ where $\mathcal{R}[\varnothing ]{=}_{\mathsf{df}}\mathit{\omega }\mathrm{>}\mathcal{R}\mathrm{(}\mathit{r}\mathrm{)}$ for all $\mathit{r}\in \mathit{D}$ . We then define:

Definition 20.

$\mathrm{\Delta }\in \hat{\mathrm{\wp }}\mathrm{(}\mathcal{D}\mathrm{)}$ is ${⊢}_{\mathcal{K}}^{\mathcal{S}}$ -R-consistent iff it is ${⊢}_{\mathcal{K}}^{\mathcal{S}}$ -consistent and for all $\mathrm{\Theta }\in \hat{\mathrm{\wp }}\mathrm{(}\mathcal{D}\mathrm{)}$ for which $\perp \mathrm{(}\mathrm{\Delta }\cup \mathrm{\Theta }\mathrm{)}$ there is a ${\mathrm{\Delta }}^{\prime }\in \hat{\mathrm{\wp }}\mathrm{(}\mathrm{\Delta }\mathrm{)}$ such that $\perp \mathrm{(}{\mathrm{\Delta }}^{\prime }\cup \mathrm{\Theta }\mathrm{)}$ and $\mathcal{R}[{\mathrm{\Delta }}^{\prime }]⩾\mathcal{R}[\mathrm{\Theta }]$ . We write ${\mathsf{MCS}}_{\mathcal{R}}^{\mathcal{S}\mathrm{,}\mathcal{K}}\mathrm{(}\mathcal{D}\mathrm{)}$ for the set of all ${⊢}_{\mathcal{K}}^{\mathcal{S}}$ -R-consistent Δ for which there are no ${⊢}_{\mathcal{K}}^{\mathcal{S}}$ -R-consistent Θ such that $\mathrm{\Theta }\supset \mathrm{\Delta }$ .

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 ${\mathrm{\Delta }}^{\prime }$ of Δ that is already inconsistent with Θ but for which $\mathcal{R}[{\mathrm{\Delta }}^{\prime }]⩾\mathcal{R}[\mathrm{\Theta }]$ . 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 $\perp \mathrm{(}{\mathrm{\Delta }}^{\prime }\cup \mathrm{\Theta }\mathrm{)}$ and there is no reason to give up rules in ${\mathrm{\Delta }}^{\prime }$ since $\mathcal{R}[{\mathrm{\Delta }}^{\prime }]⩾\mathcal{R}[\mathrm{\Theta }]$ .

In order to avoid clutter we will again talk about R-consistent sets and write ${\mathsf{MCS}}_{\mathcal{R}}$ 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 2 continued).

We consider a slight modification of ${\mathsf{AS}}_{\text{2}}$ that does not contain undercut: ${\mathsf{AS}}_{\text{2}}^{\prime }=\mathrm{(}{\mathcal{L}}_{\text{2}}\mathrm{,}{\mathcal{S}}_{\mathsf{CL}}\mathrm{,}{\mathcal{D}}_{\text{2}}^{\prime }\mathrm{,}{\mathcal{K}}_{\text{2}}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}⩽\mathrm{)}$ where ${\mathcal{D}}_{\text{2}}^{\prime }={\mathcal{D}}_{\text{2}}\setminus \{\mathit{b}{\Rightarrow }_1\neg \mathit{\delta }\}$ .

We have one set of rules that is maximally R-consistent: $\mathrm{\Theta }=\{\mathit{g}{\Rightarrow }_2\neg \mathit{p}\mathrm{,}\mathit{l}{\Rightarrow }_1\mathit{q}\mathrm{,}\mathit{q}{\Rightarrow }_1\mathit{w}\}$ . Note that any set $\mathrm{\Delta }\in \hat{\mathrm{\wp }}\mathrm{(}{\mathcal{D}}_{\text{2}}^{\prime }\mathrm{)}$ that is inconsistent with Θ contains $\mathit{g}{\Rightarrow }_1\mathit{p}$ . Since $\mathcal{R}[\{\mathit{g}{\Rightarrow }_2\neg \mathit{p}\}]⩾\mathcal{R}[\mathrm{\Delta }]$ and $\{\mathit{g}{\Rightarrow }_2\neg \mathit{p}\}\subseteq \mathrm{\Theta }$ 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 ${\mathrm{\Theta }}^{\prime }=\{\mathit{g}{\Rightarrow }_1\mathit{p}\mathrm{,}\mathit{l}{\Rightarrow }_1\mathit{q}\mathrm{,}\mathit{q}{\Rightarrow }_1\mathit{w}\}$ is not R-consistent since for ${\mathrm{\Delta }}^{\prime }=\{\mathit{g}{\Rightarrow }_2\neg \mathit{p}\}$ we have $\perp \mathrm{(}{\mathrm{\Delta }}^{\prime }\cup {\mathrm{\Theta }}^{\prime }\mathrm{)}$ and there is no ${\mathrm{\Theta }}^{″}\in \hat{\mathrm{\wp }}\mathrm{(}{\mathrm{\Theta }}^{\prime }\mathrm{)}$ for which $\perp \mathrm{(}{\mathrm{\Theta }}^{″}\cup {\mathrm{\Delta }}^{\prime }\mathrm{)}$ and $\mathcal{R}[{\mathrm{\Theta }}^{″}]⩾\mathcal{R}[{\mathrm{\Delta }}^{\prime }]$ . This is for the simple reason that any ${\mathrm{\Theta }}^{″}$ for which $\perp \mathrm{(}{\mathrm{\Theta }}^{″}\cup {\mathrm{\Delta }}^{\prime }\mathrm{)}$ will contain $\mathit{g}{\Rightarrow }_1\mathit{p}$ .

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

Theorem 9.

Where $\mathsf{AS}=\mathrm{(}\mathcal{L}\mathrm{,}\mathcal{S}\mathrm{,}\mathcal{D}\mathrm{,}\mathcal{K}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}⩽\mathrm{)}$ and $\mathcal{S}$ satisfies $\mathbf{S}\mathbf{1}$ and $\mathbf{S}\mathbf{2}$ , $$\begin{array}{c}\mathtt{pref}\mathrm{(}\mathsf{AS}\mathrm{)}=\mathtt{stab}\mathrm{(}\mathsf{AS}\mathrm{)}={\mathtt{pref}}^{\top }\mathrm{(}\mathsf{AS}\mathrm{)}={\mathtt{stab}}^{\top }\mathrm{(}\mathsf{AS}\mathrm{)}=\{\mathsf{Arg}\mathrm{(}\mathrm{\Delta }\mathrm{)}\mid \mathrm{\Delta }\in {\mathsf{MCS}}_{\mathcal{R}}\mathrm{(}\mathcal{D}\mathrm{)}\}.\end{array}$$

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 ${\mathsf{AS}}_{\text{18}}=\mathrm{(}{\mathcal{L}}_{\mathsf{CL}}\mathrm{,}{\mathcal{S}}_{\mathsf{CL}}\mathrm{,}{\mathcal{D}}_{\text{18}}\mathrm{,}\varnothing \mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}⩽\mathrm{)}$ where $\mathit{\psi }\in \bar{\mathit{\varphi }}$ iff $\mathit{\psi }=\neg \mathit{\varphi }$ or $\mathit{\varphi }=\neg \mathit{\psi }$ and $$\begin{array}{c}{\mathcal{D}}_{\text{18}}=\{{\mathit{r}}_1:\top {\Rightarrow }_5\mathit{p}\wedge \mathit{q}\mathrm{,}{\mathit{r}}_2:\top {\Rightarrow }_5\mathit{p}\wedge \neg \mathit{q}\mathrm{,}{\mathit{r}}_3:\top {\Rightarrow }_4\neg \mathit{p}\mathrm{,}{\mathit{r}}_4:\neg \mathit{p}{\Rightarrow }_4\neg \mathit{s}\mathrm{,}{\mathit{r}}_5:\top {\Rightarrow }_3\mathit{s}\}.\end{array}$$ We have, among others, the arguments: $$\begin{array}{cccccc}\mathit{a}:\hfill & ⟨\top ⟩\Rightarrow \mathit{p}\wedge \mathit{q}\hfill & {\mathit{a}}_1:\hfill & \mathit{a}\to \mathit{p}\hfill & {\mathit{a}}_2:\hfill & \mathit{a}\to \neg \mathrm{(}\mathit{p}\wedge \neg \mathit{q}\mathrm{)}\hfill \\ \mathit{b}:\hfill & ⟨\top ⟩\Rightarrow \mathit{p}\wedge \neg \mathit{q}\hfill & {\mathit{b}}_1:\hfill & \mathit{a}\to \mathit{p}\hfill & {\mathit{b}}_2:\hfill & \mathit{a}\to \neg \mathrm{(}\mathit{p}\wedge \mathit{q}\mathrm{)}\hfill \\ \mathit{c}:\hfill & ⟨⟨\top ⟩\Rightarrow \neg \mathit{p}⟩\Rightarrow \neg \mathit{s}\hfill & \mathit{d}:\hfill & ⟨\top ⟩\Rightarrow \mathit{s}\hfill \end{array}$$

This gives rise to the following argumentation framework:

We have ${\mathsf{MCS}}_{\mathcal{R}}\mathrm{(}{\mathcal{D}}_{\text{18}}\mathrm{)}=\{\{{\mathit{r}}_1\mathrm{,}{\mathit{r}}_5\}\mathrm{,}\{{\mathit{r}}_2\mathrm{,}{\mathit{r}}_5\}\}$ and so $\{{\mathit{r}}_5\}=\bigcap {\mathsf{MCS}}_{\mathcal{R}}\mathrm{(}{\mathcal{D}}_{\text{18}}\mathrm{)}$ . Note also that $\{{\mathit{r}}_5\}\in \hat{\mathrm{\wp }}\mathrm{(}{\mathcal{D}}_{\text{18}}\mathrm{)}$ and so it is the unique ⊂-maximal set contained in $\bigcap {\mathsf{MCS}}_{\mathcal{R}}\mathrm{(}{\mathcal{D}}_{\text{18}}\mathrm{)}$ . 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 ${\mathrm{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 $\mathbf{S}\mathbf{1}$ and $\mathbf{S}\mathbf{2}$ used in this paper. Let $-\mathit{\varphi }$ denote a contradictory of ϕ, i.e., a formula ψ for which $\mathit{\varphi }\in \bar{\mathit{\psi }}$ and $\mathit{\psi }\in \bar{\mathit{\varphi }}$ . For the definitions of Tpos and Cpos we thus follow [50] in assuming

Every formula ϕ has a contradictory ψ (so $\mathit{\varphi }\in \bar{\mathit{\psi }}$ and $\mathit{\psi }\in \bar{\mathit{\varphi }}$ )

that every formula has a contradictory. Given an argumentation system $\mathrm{(}\mathcal{L}\mathrm{,}\mathcal{S}\mathrm{,}\mathcal{D}\mathrm{,}\mathcal{K}\mathrm{,}\mathit{n}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}⩽\mathrm{)}$ , transposition and contraposition require the following:

• If ${\mathit{\varphi }}_1\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{n}}\to \mathit{\varphi }\in \mathcal{S}$ then for every $1⩽\mathit{i}⩽\mathit{n}$ , ${\mathit{\varphi }}_1\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{i}-1}\mathrm{,}-\mathit{\varphi }\mathrm{,}{\mathit{\varphi }}_{\mathit{i}+1}\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{n}}\to -{\mathit{\varphi }}_{\mathit{i}}\in \mathcal{S}$ .35

  ³⁵

  This is the formulation from [50] while [19,53] only require “…then for some $1⩽\mathit{i}⩽\mathit{n}$ …”. [19] state the property explicitly only for ¬ instead of $\overline{\phantom{\mathit{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 $\overline{\phantom{\mathit{A}}}$ are outside the scope of this paper but give rise to an interesting direction for future research.

• For any $\mathrm{\Delta }\subseteq \mathcal{L}$ , if $\mathrm{\Delta }{⊢}_{\mathcal{S}}\mathit{\varphi }$ then for all $\mathit{\psi }\in \mathrm{\Delta }$ , $\mathrm{(}\mathrm{\Delta }\setminus \{\mathit{\psi }\}\mathrm{)}\cup \{-\mathit{\varphi }\}{⊢}_{\mathcal{S}}-\mathit{\psi }$ .

Unlike [50], in the setting of this paper we did not suppose CPE, i.e., the existence of contradictories. Note, however, that $\mathbf{S}\mathbf{1}$ implies that if some formula has a contrary, so does every.36

³⁶

Suppose ${\mathit{\varphi }}^{\prime }\in \bar{\mathit{\varphi }}$ . Then $\{\mathit{\psi }\mathrm{,}{\mathit{\varphi }}^{\prime }\}{⊢}_{\mathcal{S}}{\mathit{\varphi }}^{\prime }$ and so by $\mathbf{S}\mathbf{1}$ , $\{\mathit{\varphi }\mathrm{,}{\mathit{\varphi }}^{\prime }\}{⊢}_{\mathcal{S}}{\mathit{\psi }}^{\prime }$ for some ${\mathit{\psi }}^{\prime }\in \bar{\mathit{\psi }}$ .

For most use cases of ASPIC this will coincide with the slightly stronger assumptions that

• For every formula ϕ, $\varnothing \ne \bar{\mathit{\varphi }}$ .

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

• For any $\mathrm{\Delta }\subseteq \mathcal{L}$ , if $\mathrm{\Delta }{⊢}_{\mathcal{S}}\mathit{\varphi }$ , then for all $\mathit{\psi }\in \mathrm{\Delta }$ , for all ${\mathit{\psi }}^{\prime }\in \bar{\mathit{\psi }}$ , and for all ${\mathit{\varphi }}^{\prime }\in \bar{\mathit{\varphi }}$ , $\mathrm{(}\mathrm{\Delta }\setminus \{\mathit{\psi }\}\mathrm{)}\cup \{{\mathit{\varphi }}^{\prime }\}{⊢}_{\mathcal{S}}{\mathit{\psi }}^{\prime }$ .37

  ³⁷

  A similar example as Example 9 can be used to show that a weaker version of Cpos^⋆ which only demands “for some ${\mathit{\psi }}^{\prime }\in \bar{\mathit{\psi }}$ and for some ${\mathit{\varphi }}^{\prime }\in \bar{\mathit{\varphi }}$ ” instead of “for all ${\mathit{\psi }}^{\prime }\in \bar{\mathit{\psi }}$ and for all ${\mathit{\varphi }}^{\prime }\in \bar{\mathit{\varphi }}$ ” leads to problems with rationality postulates. Consider ${\mathsf{AS}}_{\text{9}}^{\prime }=\mathrm{(}\{\mathit{p}\mathrm{,}\mathit{q}\mathrm{,}\mathit{s}\mathrm{,}\mathit{r}\mathrm{,}{\mathit{p}}^{\prime }\mathrm{,}{\mathit{q}}^{\prime }\mathrm{,}{\mathit{s}}^{\prime }\mathrm{,}{\mathit{r}}^{\prime }\}\mathrm{,}{\mathcal{S}}_{\text{9}}^{\prime }\mathrm{,}{\mathcal{D}}_{\text{9}}\mathrm{,}\varnothing \mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}{⪯}_{\text{9}}\mathrm{)}$ where ${\mathcal{S}}_{\text{9}}^{\prime }=\{\mathit{q}\to {\mathit{r}}^{\prime }\mathrm{,}{\mathit{r}}^{″}\to {\mathit{q}}^{\prime }\}$ , $\bar{\mathit{r}}=\overline{{\mathit{r}}^{″}}=\{{\mathit{r}}^{\prime }\}$ , $\overline{{\mathit{r}}^{\prime }}=\{\mathit{r}\mathrm{,}{\mathit{r}}^{″}\}$ and for all other atoms ϕ, $\bar{\mathit{\varphi }}=\{{\mathit{\varphi }}^{\prime }\}$ and $\overline{{\mathit{\varphi }}^{\prime }}=\{\mathit{\varphi }\}$ . We have the same arguments as in Example 9 and the counter-example to closure is thus analogous. Note that ${\mathcal{S}}_{\text{9}}^{\prime }$ satisfies the weak version of Cpos.

It will not surprise the reader that there is a close connection between the Cpos resp. Cpos^⋆ and requirement $\mathbf{S}\mathbf{1}$ .

Fact 7.

Cpos implies $\mathbf{S}\mathbf{1}$ if for all $\mathit{\varphi }\in \mathcal{L}$ and all ${\mathit{\varphi }}^{\prime }\in \bar{\mathit{\varphi }}$ , $\mathit{\varphi }{⊢}_{\mathcal{S}}-{\mathit{\varphi }}^{\prime }$ .

Proof.

Assume Δ, $\mathit{\psi }{⊢}_{\mathcal{S}}{\mathit{\varphi }}^{\prime }$ for some ${\mathit{\varphi }}^{\prime }\in \bar{\mathit{\varphi }}$ and that Cpos is valid. By Cpos, Δ, $-{\mathit{\varphi }}^{\prime }{⊢}_{\mathcal{S}}-\mathit{\psi }$ . Since $\mathit{\varphi }{⊢}_{\mathcal{S}}-{\mathit{\varphi }}^{\prime }$ and by the transitivity of ${⊢}_{\mathcal{S}}$ , Δ, $\mathit{\varphi }{⊢}_{\mathcal{S}}-\mathit{\psi }$ . □

Fact 8.

Cpos ^⋆ and CPE imply $\mathbf{S}\mathbf{1}$ .

Proof.

Suppose Δ, $\mathit{\psi }{⊢}_{\mathcal{S}}{\mathit{\varphi }}^{\prime }$ for some ${\mathit{\varphi }}^{\prime }\in \bar{\mathit{\varphi }}$ . By Cpos^⋆ and CPE, Δ, $-{\mathit{\varphi }}^{\prime }{⊢}_{\mathcal{S}}-\mathit{\psi }$ . Since $\mathit{\varphi }{⊢}_{\mathcal{S}}\mathit{\varphi }$ , by Cpos and CPE, ${\mathit{\varphi }}^{\prime }{⊢}_{\mathcal{S}}-\mathit{\varphi }$ and furthermore, $\mathit{\varphi }{⊢}_{\mathcal{S}}-{\mathit{\varphi }}^{\prime }$ . By the transitivity of ${⊢}_{\mathcal{S}}$ , Δ, $\mathit{\varphi }{⊢}_{\mathcal{S}}-\mathit{\psi }$ . □

Fact 9.

Cpos ^⋆ implies $\mathbf{S}\mathbf{1}$ if for all $\mathit{\varphi }\in \mathcal{L}$ and all ${\mathit{\varphi }}^{\prime }\in \bar{\mathit{\varphi }}$ there is a ${\mathit{\varphi }}^{″}\in \overline{{\mathit{\varphi }}^{\prime }}$ for which $\mathit{\varphi }{⊢}_{\mathcal{S}}{\mathit{\varphi }}^{″}$ .

Proof.

Assume Δ, $\mathit{\psi }{⊢}_{\mathcal{S}}{\mathit{\varphi }}^{\prime }$ for some ${\mathit{\varphi }}^{\prime }\in \bar{\mathit{\varphi }}$ and that Cpos^⋆ is valid. We have to show that Δ, $\mathit{\varphi }{⊢}_{\mathcal{S}}{\mathit{\psi }}^{\prime }$ for some ${\mathit{\psi }}^{\prime }\in \bar{\mathit{\psi }}$ . We suppose that $\mathit{\varphi }{⊢}_{\mathcal{S}}{\mathit{\varphi }}^{″}$ for some ${\mathit{\varphi }}^{″}\in \overline{{\mathit{\varphi }}^{\prime }}$ . By Cpos^⋆, Δ, ${\mathit{\varphi }}^{″}{⊢}_{\mathcal{S}}{\mathit{\psi }}^{\prime }$ for some ${\mathit{\psi }}^{\prime }\in \bar{\mathit{\psi }}$ . By the transitivity of ${⊢}_{\mathcal{S}}$ therefore Δ, $\mathit{\varphi }{⊢}_{\mathcal{S}}{\mathit{\psi }}^{″}$ . □

In particular, the requirement of Facts 7–9 hold if for all formulas ϕ all members of $\bar{\mathit{\varphi }}$ are contradictories, i.e., if $\mathit{\varphi }\in \overline{{\mathit{\varphi }}^{\prime }}$ for all ${\mathit{\varphi }}^{\prime }\in \bar{\mathit{\varphi }}$ .

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 ${\mathsf{AS}}_{\text{19}}=\mathrm{(}{\mathcal{L}}_{\text{19}}\mathrm{,}{\mathcal{S}}_{\text{19}}\mathrm{,}{\mathcal{D}}_{\text{19}}\mathrm{,}\{\top \}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}{⩽}_{\text{19}}\mathrm{)}$ , where ${\mathcal{L}}_{\text{19}}=\{\mathit{p}\mathrm{,}\mathit{q}\mathrm{,}\neg \mathit{p}\mathrm{,}\neg \mathit{q}\mathrm{,}\top \mathrm{,}\perp \}$ , ${\mathcal{S}}_{\text{19}}=\{\}$ , ${\mathcal{D}}_{\text{19}}=\{{\mathit{r}}_1:\top \Rightarrow \mathit{p}\mathrm{,}{\mathit{r}}_2:\top \Rightarrow \mathit{q}\}$ , $\bar{\top }=\{\perp \}$ , $\bar{\perp }=\{\top \}$ , $\bar{\mathit{p}}=\{\neg \mathit{p}\}$ , $\overline{\neg \mathit{p}}=\{\mathit{p}\}$ , $\bar{\mathit{q}}=\{\neg \mathit{q}\mathrm{,}\mathit{p}\}$ , $\overline{\neg \mathit{q}}=\{\mathit{q}\}$ , and ${\mathit{r}}_1{⩽}_{\text{19}}{\mathit{r}}_2$ .

Note that p is merely a contrary, not a contradictory of q, while $\neg \mathit{q}$ and q are contradictories. We have the following arguments: $$\begin{array}{cc}\mathit{a}:\hfill & ⟨\top ⟩\Rightarrow \mathit{p}\hfill \\ \mathit{b}:\hfill & ⟨\top ⟩\Rightarrow \mathit{q}\hfill \end{array}$$

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 $\mathit{p}\in \bar{\mathit{q}}$ .

Note that while ${\mathcal{S}}_{\text{19}}$ satisfies Cpos and CPE, it does not satisfy $\mathbf{S}\mathbf{1}$ since $\mathit{p}{⊢}_{{\mathcal{S}}_{\text{19}}}\mathit{p}$ but not $\mathit{q}{⊢}_{{\mathcal{S}}_{\text{19}}}\neg \mathit{p}$ .

The example also shows that $\mathbf{S}\mathbf{1}$ does not imply Cpos.

To see that neither Cpos, Cpos^⋆, nor Tpos implies $\mathbf{S}\mathbf{2}$ , consider the following example: Let $\mathcal{S}=\varnothing$ and $\bar{\mathit{p}}=\{\mathit{p}\}$ . Then we see that ${⊢}_{\mathcal{S}}$ is closed under Cpos and Tpos, however, it does not satisfy $\mathbf{S}\mathbf{2}$ , as $\{\mathit{p}\}{⊢}_{\mathcal{S}}\bar{\mathit{p}}$ yet $\varnothing ⊬\bar{\mathit{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 (Problems with “contrary-rebut”).

In all example below we treat $\neg \mathit{\varphi }$ and ϕ as contradictories. Our examples concern two very weak versions of “interference”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.

and a lightweight version of the well-known Cumulativity principle from non-monotonic logic.

• Interference 1. Suppose ${\mathsf{AS}}_1$ has the rule base $\mathcal{D}=\{\top {\Rightarrow }_8\mathit{p}\}$ , p has as a contrary r and the strict rules are induced by classical logic. Clearly, p will be a grounded consequence of ${\mathsf{AS}}_1$ . Suppose further we add the rules ${\mathcal{D}}^{\prime }=\{\top {\Rightarrow }_1\mathit{q}\mathrm{,}\top {\Rightarrow }_1\neg \mathit{q}\}$ resulting in an extended system ${\mathsf{AS}}_2$ . Now the argument $⟨\top {\Rightarrow }_1\mathit{q}⟩$ , $⟨\top {\Rightarrow }_1\neg \mathit{q}⟩\to \mathit{r}$ will defeat $\top {\Rightarrow }_8\mathit{p}$ and p will therefore not be a grounded consequence of ${\mathsf{AS}}_2$ . Note that we only added weaker rules than the ones in ${\mathsf{AS}}_1$ , both of which are syntactically disjoint from ${\mathsf{AS}}_1$ , but this was sufficient to contaminate the framework.

• Interference 2. In this example we will again add rules to a given ${\mathsf{AS}}_3$ , this time rules that only extend arguments which are rejected in any extension of a given standard (completeness-based) semantics. Let ${\mathsf{AS}}_3$ be based on ${\mathcal{D}}_3=\{\top {\Rightarrow }_{100}\mathit{p}\mathrm{,}\top {\Rightarrow }_2\neg \mathit{p}\}$ . Clearly, the argument $\mathit{a}=\top {\Rightarrow }_{100}\mathit{p}$ will be in any extension, while $\mathit{b}=\top {\Rightarrow }_2\neg \mathit{p}$ will be defeated in any extension. We now add the rules in ${\mathcal{D}}_4=\{\neg \mathit{p}{\Rightarrow }_1\mathit{q}\mathrm{,}\mathit{q}{\Rightarrow }_1{\mathit{p}}^{\prime }\}$ resulting in ${\mathsf{AS}}_4$ , where p has as a contrary ${\mathit{p}}^{\prime }$ . We note that these rules are weaker than those in ${\mathcal{D}}_3$ and they only extend our rejected b to $\mathit{c}=\mathit{b}{\Rightarrow }_1\mathit{q}{\Rightarrow }_1{\mathit{p}}^{\prime }$ . Interestingly, now c defeats a and so p will not be anymore a consequence of ${\mathsf{AS}}_4$ .

• Cumulativity lite. Suppose an argument a with conclusion ϕ and strength n (so $\mathit{n}=min\mathrm{(}\{\mathit{m}\mid {\mathit{\varphi }}_1\mathrm{,}\dots \mathrm{,}{\mathit{\varphi }}_{\mathit{k}}{\Rightarrow }_{\mathit{m}}\mathit{\psi }\in \mathcal{D}\mathrm{(}\mathit{a}\mathrm{)}\}\mathrm{)}$ ) is contained in every preferred extension of $\mathsf{AS}$ . Then one would expect that adding a new rule $\top {\Rightarrow }_{\mathit{n}}\mathit{\varphi }$ to the defeasible rules should lead to robust results. (In Appendix C.4 we show that our system satisfies our expectation.) Let ${\mathsf{AS}}_5$ come with the rules $$\begin{array}{c}{\mathcal{D}}_5=\{\top {\Rightarrow }_{10}\mathit{p}\mathrm{,}\mathit{p}{\Rightarrow }_{10}\mathit{q}\mathrm{,}\mathit{q}\vee \mathit{r}{\Rightarrow }_1\neg \mathit{q}\mathrm{,}\neg \mathit{q}{\Rightarrow }_1{\mathit{p}}^{\prime }\}\mathrm{,}\end{array}$$ and suppose p has as a contrary ${\mathit{p}}^{\prime }$ . We have, for instance, the following arguments: $$\begin{array}{cccc}\mathit{a}:\hfill & \top {\Rightarrow }_{10}\mathit{p}{\Rightarrow }_{10}\mathit{q}\hfill & {\mathit{a}}^{\prime }:\hfill & \mathit{a}\to \mathit{q}\vee \mathit{r}\hfill \\ \mathit{b}:\hfill & {\mathit{a}}^{\prime }{\Rightarrow }_1\neg \mathit{q}\hfill & {\mathit{b}}^{\prime }:\hfill & \mathit{b}{\Rightarrow }_1{\mathit{p}}^{\prime }\hfill \end{array}$$

  This results in the framework to the left:

  So a and ${\mathit{a}}^{\prime }$ are contained in every preferred extension of ${\mathsf{AS}}_5$ . Now if we add $\top {\Rightarrow }_{10}\mathit{q}\vee \mathit{r}$ to ${\mathcal{D}}_5$ (resulting in ${\mathsf{AS}}_6$ ), we also get the argument $\mathit{c}=\top {\Rightarrow }_{10}\mathit{q}\vee \mathit{r}{\Rightarrow }_1\neg \mathit{q}$ and ${\mathit{c}}^{\prime }=\mathit{c}{\Rightarrow }_1{\mathit{p}}^{\prime }$ . This results in the graph to the right (omitting the nodes b and ${\mathit{b}}^{\prime }$ for clutter reduction). Now, there is a preferred extension containing c and ${\mathit{c}}^{\prime }$ in which a and ${\mathit{a}}^{\prime }$ are defeated, so that p and q are not anymore consequences of ${\mathsf{AS}}_6$ .

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 $\mathsf{AS}=\mathrm{(}\mathcal{L}\mathrm{,}\mathcal{S}\mathrm{,}\mathcal{D}\mathrm{,}\mathcal{K}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{)}$ that: SCA

for any ⊆-minimally inconsistent39

³⁹

On the most general level, [30] assumes that an argumentation system is built on the basis of an abstract logic $\mathrm{(}\mathsf{CN}\mathrm{,}\mathsf{CONTRA}\mathrm{)}$ over a language $\mathcal{L}$ where $\mathsf{CN}$ is a Tarskian consequence relation and $\mathsf{CONTRA}$ is a collection sets that is upward-closed and doesn’t contain $\mathsf{CN}\mathrm{(}\varnothing \mathrm{)}$ . A set Δ is inconsistent if $\mathsf{Cn}\mathrm{(}\mathrm{\Delta }\mathrm{)}\in \mathsf{CONTRA}$ . For ${\mathrm{ASPIC}}^{+}$ with symmetric negation, [30] remarks that $\mathsf{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.

set of formulas $\mathrm{\Sigma }\subseteq \mathcal{L}$ , $\mathrm{\Sigma }{⊢}_{\mathcal{S}}{\mathit{\varphi }}^{\prime }$ for any $\mathit{\varphi }\in \mathrm{\Sigma }$ and some ${\mathit{\varphi }}^{\prime }\in \bar{\mathit{\varphi }}$ .

[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 $\mathit{\varphi }\in {\mathcal{L}}_{\text{10}}$ , $\{\mathit{p}\}{⊢}_{\mathcal{S}}\mathit{\varphi }$ and $\{\mathit{q}\mathrm{,}\neg \mathit{q}\}{⊢}_{\mathcal{S}}\mathit{\varphi }$ . 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 $\{\mathsf{Conc}\mathrm{(}\mathit{c}\mathrm{)}\mid \mathit{c}\in \mathsf{Sub}\mathrm{(}\mathit{a}\mathrm{)}\cup \mathsf{Sub}\mathrm{(}\mathit{b}\mathrm{)}\}{⊢}_{\mathcal{S}}\perp$ ), 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 $\mathcal{E}$ , $\mathcal{D}[\mathcal{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] ${\mathrm{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 ${\mathrm{ASPIC}}^{+}$ frameworks also have a unique stable extension, which can be contrasted with ${\mathrm{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: ${\mathrm{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 ${\mathrm{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

⁴⁰

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

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 ${\mathrm{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 $\mathit{A}{\mathit{S}}_{\mathsf{ABA}}=⟨\mathcal{L}\mathrm{,}\mathsf{Ab}\mathrm{,}\mathcal{S}\mathrm{,}\mathcal{K}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}⩽⟩$ consists of a language $\mathcal{L}$ , a set of defeasible assumptions $\mathsf{Ab}\subseteq \mathcal{L}$ , a set of strict rules formulated over $\mathcal{L}$ , a strict premise set $\mathcal{K}$ , a contrariness relation $\overline{\phantom{\mathit{A}}}:\mathsf{Ab}\to \mathrm{\wp }\mathrm{(}\mathcal{L}\mathrm{)}$ and a preference relation ⪯ over $\mathsf{Ab}$ . Argumentation frameworks constructed on the basis of a prioritised ABA system $\mathit{A}{\mathit{S}}_{\mathsf{ABA}}$ are $\mathit{A}\mathit{F}\mathrm{(}\mathit{A}{\mathit{S}}_{\mathsf{ABA}}\mathrm{)}=\mathrm{(}\mathrm{\wp }\mathrm{(}\mathsf{Ab}\mathrm{)}\mathrm{,}⇝\mathrm{)}$ where $\mathrm{\Delta }⇝\mathrm{\Theta }$ iff (1) $\mathcal{K}\cup \mathrm{\Delta }{⊢}_{\mathcal{S}}\mathit{A}$ for some $\mathit{A}\in \bar{\mathit{B}}$ and some $\mathit{B}\in \mathrm{\Theta }$ and (2) $min\mathrm{(}\mathrm{\Delta }\mathrm{)}⩾\mathit{B}$ .41

⁴¹

We compare here ${\mathrm{ASPIC}}^{+}$ with assumption-based argumentation with direct attacks, called ${\mathrm{ABA}}^{\mathit{d}}$ in [40,44]. However, in the setting of this paper, the remarks made here generalize to assumption-based argumentation with reverse attacks (called ${\mathrm{ABA}}^{\mathit{r}}$ in [40,44] and ${\mathrm{ABA}}^{+}$ in [25]), since it has been shown that ${\mathrm{ABA}}^{\mathit{r}}$ and ${\mathrm{ABA}}^{\mathit{d}}$ give rise to the same outcomes when a flat assumption-based framework satisfies $\mathbf{S}\mathbf{1}$ and $\mathbf{S}\mathbf{2}$ [42].

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 ${\mathrm{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 ${\mathrm{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 ${\mathrm{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 ${\mathrm{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 (Inspired by Example 6.7 in [57]).

${\mathsf{AS}}_{\text{ 21}}=\mathrm{(}{\mathcal{L}}_{\mathsf{CL}}\mathrm{,}{\mathcal{S}}_{\mathsf{CL}}\mathrm{,}{\mathcal{D}}_{\text{21}}\mathrm{,}\{\mathit{s}\}\mathrm{,}\overline{\phantom{\mathit{A}}}\mathrm{,}⩽\mathrm{)}$ where $\bar{\mathit{\varphi }}=\{\mathit{\psi }\mid \mathit{\psi }{⊢}_{\mathsf{CL}}\neg \mathit{\varphi }\}$ and ${\mathcal{D}}_{\text{21}}=\{\mathit{s}{\Rightarrow }_1\mathit{p};\mathit{p}{\Rightarrow }_3\mathit{q};\mathit{s}{\Rightarrow }_2\neg \mathit{p}\vee \neg \mathit{q}\}$ . We have, among others, the following arguments: $$\begin{array}{cccc}\mathit{a}:\hfill & ⟨\mathit{s}⟩\hfill & {\mathit{a}}_1:\hfill & \mathit{a}{\Rightarrow }_1\mathit{p}\hfill \\ {\mathit{a}}_2:\hfill & \mathit{a}{\Rightarrow }_2\neg \mathit{p}\vee \neg \mathit{q}\hfill & {\mathit{a}}_3:\hfill & {\mathit{a}}_1{\Rightarrow }_3\mathit{q}\hfill \\ {\mathit{a}}_{12}:\hfill & {\mathit{a}}_1\mathrm{,}{\mathit{a}}_2\to \mathit{p}\wedge \neg \mathit{q}\hfill & {\mathit{a}}_{13}:\hfill & {\mathit{a}}_1\mathrm{,}{\mathit{a}}_3\to \mathit{p}\wedge \mathit{q}\hfill \\ {\mathit{a}}_{23}:\hfill & {\mathit{a}}_2\mathrm{,}{\mathit{a}}_3\to \neg \mathit{p}\wedge \mathit{q}\hfill & {\mathit{a}}_{\perp }:\hfill & {\mathit{a}}_1\mathrm{,}{\mathit{a}}_2\mathrm{,}{\mathit{a}}_3\to \perp \hfill \end{array}$$

In this example we use the democratic last link lifting, which says that an argument $\mathit{b}{⪯}_{\mathtt{lld}}\mathit{c}$ iff the ⩽-minimal last defeasible rule used in b is weaker than the ⩽-minimal last defeasible rule used in c. For example, ${\mathit{a}}_2{⪯}_{\mathtt{lld}}{\mathit{a}}_3$ since the weakest last defeasible link of ${\mathit{a}}_2$ , $\mathit{s}{\Rightarrow }_2\neg \mathit{p}\vee \neg \mathit{q}$ , is weaker than the weakest (and only) last defeasible link of ${\mathit{a}}_3$ , $\mathit{p}{\Rightarrow }_3\mathit{q}$ . For the same reason, ${\mathit{a}}_3{⋠}_{\mathtt{lld}}{\mathit{a}}_2$ . 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 $\mathit{s}{\Rightarrow }_2\neg \mathit{p}\vee \neg \mathit{q}$ . If we now add the syntactically disjoint rule $\top {\Rightarrow }_1\mathit{t}$ , the argument ${\mathit{a}}_{123}$ defeats the argument $\top {\Rightarrow }_1\mathit{t}$ and thus interferes with the derivability of t.

It is interesting to note that ${\mathsf{AS}}_{\text{21}}$ is used in [57] to show that under last link, filtering out inconsistent arguments leads to violations of closure and consistency. Indeed, when ${\mathit{a}}_{13}$ , ${\mathit{a}}_{23}$ and ${\mathit{a}}_{\perp }$ are not part of the argumentation framework, ${\mathit{a}}_1$ , ${\mathit{a}}_2$ , ${\mathit{a}}_3$ , and ${\mathit{a}}_{12}$ are all undefeated, meaning they are part of the unique preferred extension of ${\mathsf{Arg}}^{\top }\mathrm{(}{\mathsf{AS}}_{\text{21}}\mathrm{)}$ . This means that this extension contains arguments for e.g. p, q and $\neg \mathit{p}\vee \neg \mathit{q}$ , constituting a violation of indirect consistency and closure (since $\{\mathit{p}\mathrm{,}\mathit{q}\mathrm{,}\neg \mathit{p}\vee \neg \mathit{q}\}{⊢}_{\mathsf{CL}}\perp$ but there is no argument for ⊥ in ${\mathsf{Arg}}^{\top }\mathrm{(}{\mathsf{AS}}_{\text{21}}\mathrm{)}$ ). It is therefore an important avenue for future work to define a formalism that satisfies all four rationality postulates under the last link principle.