On Argumentation with Purely Defeasible Rules

Abstract

aspic $^{+}$ is one of the most widely used systems for structured arguments and includes the use of both strict and defeasible rules. Here we consider using just the defeasible part of aspic $^{+}$. We show that using the resulting system, it is possible, in a well defined sense, to capture the same information as using aspic $^{+}$ with strict rules.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Argumentation theory is concerned with the way that intelligent agents discuss whether some statement holds. In the past few years, formal argumentation frameworks have been heavily studied and applications have been proposed in fields such as natural language processing, the semantic web and multi-agent systems. Studying argumentation provides results which help in developing tools and applications in these areas. Dung’s seminal work [8] tells us how to handle the conflicts between arguments. However, it says nothing about the structure of arguments, or how to construct arguments and attack relationships from a knowledge base. Providing the logical basis for argumentation has been the subject of several authors, including [4, 9, 10]. This paper is concerned with we the work that started with the aspic [2] framework, and we briefly summarise this work below.

Following [2, 6] pointed out that aspic may lead to some non-intuitive results, suggested that all argumentation frameworks must satisfy three rationality postulates in order to avoid these anomalies, and showed how aspic could be modified to satisfy them. [12] presented an extension of aspic, called aspic $^{+}$, which also satisfies the postulates under certain restrictions. [1, 13] provide further discussion of the approach. [11] modified the aspic $^{+}$ framework, to develop a more general structured framework for argumentation with preferences. [5, 14] presented some examples where aspic-like systems could lead to non-intuitive results and gave solutions. Finally, [7] looked at a new variation of aspic $^{+}$ which still satisfies the rationality postulates while loosening the restriction on rebut that aspic $^{+}$ requires to satisfy the rationality postulates.

Here we continue this line of work, considering another variation of aspic $^{+}$ which only contains defeasible elements. We find that, like the system in [7], our system can both loosen the restrictions on aspic $^{+}$ and still satisfy the rationality postulates, while being able to establish exactly the same set of conclusions as aspic $^{+}$ from the corresponding knowledge-base.

2 Background

2.1 Abstract  Argumentation

An abstract argumentation framework [8] is a pair $AF=\langle \mathcal {A},Defeats \rangle$, where $\mathcal {A}$ is a set of arguments, and Defeats is a binary relation collecting all pairs of arguments A and B such that A defeats B, i.e. $Defeats \subseteq \mathcal {A} \times \mathcal {A}$. An argument is called acceptable iff it can defend itself, that is, all of its defeaters have been defeated. A subset S of $\mathcal {A}$ is said to be conflict-free if there are no arguments in S that defeat an argument in S. Given an abstract argumentation framework, one is typically interested in which of the arguments are acceptable. This is done through argument-based semantics, which define different ways to determine acceptability. [8] defines several semantics — complete, grounded, preferred and stable. A given semantics will specify some (possibly empty) sets of acceptable arguments for a given argumentation framework. These sets are also called argument-based extensions, or simply extensions. The conclusions of the arguments in an extension are called the justified conclusions.

The state-of-the-art way to establish the extensions is through the labeling approach, which is nicely summarized by [3]. This approach can be described in terms of a labeling function $LF$ which maps from arguments to a set of labels $\{\mathtt {IN}, \mathtt {OUT}, \mathtt {UNDEC}\}$. Not all labelings are helpful in determining acceptability, and we determine the helpful labelings through the idea of legality. For a legal labeling $LF$, an argumentation framework, $\langle \mathcal {A}, Defeats \rangle$, and an argument $x\in \mathcal {A}$:

• 1. x is legally $\mathtt {IN}$ iff x is labeled $\mathtt {IN}$ and every $y \in \mathcal {A}$ that defeats x is labeled $\mathtt {OUT}$.

• 2. x is legally $\mathtt {OUT}$ iff x is labeled $\mathtt {OUT}$ and there is at least one $y \in \mathcal {A}$ that defeats x and is labeled $\mathtt {IN}$.

• 3. x is legally $\mathtt {UNDEC}$ iff there is no $y \in \mathcal {A}$ that defeats x such that y is labeled $\mathtt {IN}$, and there is at least one $y \in \mathcal {A}$ that defeats x such that y is labeled $\mathtt {UNDEC}$.

Note that the $\mathtt {UNDEC}$ state occurs when x cannot be labeled $\mathtt {IN}$ (because it has at least one defeater that is not $\mathtt {OUT}$), and cannot be labeled $\mathtt {OUT}$ (because it has no $\mathtt {IN}$ defeater). If an argument is not legally labeled, it is said to be illegally labeled. More precisely, an argument is illegally labeled l, where $l\in \{\mathtt {IN}, \mathtt {OUT},\mathtt {UNDEC}\}$, if it is not legally labeled l.

With the notion of legality tying labelings to Defeats relations, we can identify acceptable sets of arguments through the notions of admissibility and completeness. An admissible labeling has no arguments that are illegally $\mathtt {IN}$, and no arguments that are illegally $\mathtt {OUT}$. A complete labeling is an admissible labeling that, in addition, has no arguments that are illegally $\mathtt {UNDEC}$. Then, given a complete labeling $LF$, we have: (1) $LF$ is a grounded labeling iff there is no complete labeling with a smaller set of $\mathtt {IN}$ arguments; (2) $LF$ is a preferred labeling iff there is no complete labeling with a larger set of $\mathtt {IN}$ arguments; and (3) $LF$ is a stable labeling if it contains no $\mathtt {UNDEC}$ arguments.

The labeling approach exactly matches Dung’s semantics [8]. If $LF$ is a complete labeling, then every x labeled $\mathtt {IN}$ by $LF$ is in the complete extension, and so on for grounded, preferred and stable labelings. If an argument is in a given extension, we say that it is justified in the corresponding semantics.

2.2 ASPIC$^{+}$ Argumentation Framework

Next, we review the aspic $^{+}$ argumentation framework in [11]. This defines two kinds of inference rules: strict rules (denoted $\rightarrow$), meaning the conclusion is always accepted without any exception, and defeasible rules (denoted $\Rightarrow$), meaning the conclusion is accepted unless there is an exception.

Definition 1

(ASPIC $^{+}$ Argumentation System). An argumentation system is a triple $AS = \langle \mathcal {L}, \mathcal {R}, n \rangle$ where:

• $\mathcal {L}$ is a logical language closed under negation $\bar{\cdot }$.

• $\mathcal {R}= \mathcal {R}_s \cup \mathcal {R}_d$ is a set of strict ($\mathcal {R}_s$) and defeasible ($\mathcal {R}_d$) inference rules of the form $\phi _1, \ldots , \phi _n \rightarrow \phi$ and $\phi _1, \ldots , \phi _n \Rightarrow \phi$ respectively (where $\phi _i, \phi$ are meta-variables ranging over wff in $\mathcal {L}$), and $\mathcal {R}_s \cap \mathcal {R}_d = \emptyset$.

• $n : \mathcal {R}_d \mapsto \mathcal {L}$ is a naming convention for defeasible rules.

We say that a set of propositions in $\mathcal {L}$ is consistent iff there do not exist two propositions a and $a'$ such that $a=\overline{a'}$, and it is helpful to think of completing the set of strict rules by considering all the negative connections between propositions mentioned in a strict rule:

Definition 2

(Closure under Transposition). If $\mathcal {R}_s$ is a set of strict rules, we say $\mathcal {R}_s$ is closed under transposition iff if $\phi _1, \ldots , \phi _n \rightarrow \phi \in \mathcal {R}_s$, then $\phi _1, \ldots ,\phi _{i-1}, \overline{\phi }, \phi _{i+1}, \ldots , \phi _n \rightarrow \overline{\phi }_i \in \mathcal {R}_s$ ($i=1 \ldots n$)

Definition 3

(ASPIC $^{+}$ Knowledge Base). A knowledge base in an argumentation system $\langle \mathcal {L}, \mathcal {R}, n \rangle$ is a set $\mathcal {K} \subseteq \mathcal {L}$ consisting of two disjoint subsets $\mathcal {K}_n$ (the axioms) and $\mathcal {K}_p$ (the ordinary premises).

The above definitions distinguish the premises and the inference rules into two sets, the set of strict elements ($\mathcal {R}_s$ and $\mathcal {K}_n$) and the set of defeasible elements ($\mathcal {R}_d$ and $\mathcal {K}_p$).

Definition 4

(ASPIC $^{+}$ Argumentation Theory). An argumentation theory AT is a pair $\langle AS, \mathcal {K} \rangle$ of an argumentation system AS and a knowledge base $\mathcal {K}$.

Before defining precisely what an argument is, we need to introduce some notions which can be defined just understanding that an argument is made up of some subset of the knowledge $\mathcal {K}$, along with a sequence of rules, that lead to a conclusion. Given this, $\mathtt {Prem}(\cdot )$ returns all the premises, $\mathtt {Conc}(\cdot )$ returns the conclusion and $\mathtt {TopRule}(\cdot )$ returns the last rule in the argument. $\mathtt {Sub}(\cdot )$ returns all the sub-arguments of a given argument, that is all the arguments that are subset of the given argument.

Definition 5

(Argument). An argument A from of an argumentation theory $AT = \langle \langle \mathcal {L}, \mathcal {R}, n\rangle , \mathcal {K}\rangle$ is:

• 1. $\phi$ if $\phi \in \mathcal {K}$ with: $\mathtt {Prem}$(A) = $\{\phi \}$; $\mathtt {Conc}$(A) = $\{\phi \}$; $\mathtt {Sub}$(A) = $\{A\}$; $\mathtt {TopRule}$(A) = undefined.

• 2. $A_1, \ldots , A_n \rightarrow \mathrm {(or\ \Rightarrow )}\ \phi$ if $A_i$ are arguments such that there exists a strict (or defeasible) rule $\mathtt {Conc}(A_1), \ldots , \mathtt {Conc}(A_n) \rightarrow \mathrm {(or\ \Rightarrow )}\ \phi$ in $\mathcal {R}_s$(or $\mathcal {R}_d$). $\mathtt {Prem}(A) = \mathtt {Prem}(A_1) \cup \ldots \cup \mathtt {Prem}(A_n); \mathtt {Conc}(A) = \phi ; \mathtt {Sub}(A) = \mathtt {Sub}(A_1) \cup \ldots \cup \mathtt {Sub}(A_n) \cup \{A\}; \mathtt {TopRule}(A) = \mathtt {Conc}(A_1), \ldots , \mathtt {Conc}(A_n) \rightarrow \mathrm {(or\ \Rightarrow )}\ \phi$.

We write $\mathcal {A}$(AT) to denote the set of arguments from the theory AT.

We say that an argument A is consistent iff $\{\mathtt {Conc}(A') | A' \in \mathtt {Sub}(A)\}$ is consistent. We further say that an argument A is strict if A only contains strict rules, that is $\mathcal {R}_s \ne \emptyset$ and $\mathcal {R}_d = \emptyset$;¹. Similarly, we say: A is defeasible if A contains at least one defeasible rule, $\mathcal {R}_d \ne \emptyset$; A is firm if A only contains axioms, $\mathcal {K}_n \ne \emptyset$, $\mathcal {K}_p = \emptyset$; A is plausible if A contains ordinary premises.

An argument can be attacked in three ways: on its ordinary premises, on its conclusion, or on its inference rules:

Definition 6

(ASPIC $^{+}$ Attack). An argument A attacks an argument B iff A undermines, rebuts or undercuts B, where:

• A undermines B (on $B'$) iff $\mathtt {Conc}$(A) $= \overline{\phi }$ for some $B'=\phi \in \mathtt {Prem}(B)$ and $\phi \in \mathcal {K}_p$.

• A rebuts B (on $B'$) iff $\mathtt {Conc}$(A) $= \overline{\phi }$ for some $B' \in \mathtt {Sub}(B)$ of the form $B''_1, \ldots , B''_2 \Rightarrow \phi$.

• A undercuts B (on $B'$) iff $\mathtt {Conc}$(A) $= \overline{n(r)}$ for some $B' \in \mathtt {Sub}(B)$ such that $\mathtt {TopRule}(B)$ is a defeasible rule r of the form $\phi _1, \ldots , \phi _n \Rightarrow \phi$.

We denote “A attacks B” by (A, B).

Note that, in the aspic $^{+}$ attack relation, rebutting is restricted. That is an argument with a strict $\mathtt {TopRule}$ can rebut an argument with a defeasible $\mathtt {TopRule}$, but not vice versa.

Attacks can be distinguished as to whether they are preference-dependent (rebutting and undermining) or preference-independent (undercutting). The former succeed only when the attacker is preferred. The latter succeed whether or not the attacker is preferred.

Definition 7

(Preference Ordering). A preference ordering $\preceq$ is a binary relation over arguments, i.e., $\preceq \ \subseteq \mathcal {A} \times \mathcal {A}$, where $\mathcal {A}$ is the set of all arguments constructed from the knowledge base in an argumentation system. We say A’s preference level is less than or equal to that of B iff $A \preceq B$.

In general, neither aspic $^{+}$ nor our defeasible system make any assumptions on the properties of the preference ordering, but in establishing a relationship between the two systems, we make use of the weakest link principle from [11]. This assumes two pre-orderings $\le , \le '$ over $\mathcal {R}_d$ and $\mathcal {K}_p$ respectively, and combines them into $A \prec B$ if:

• the defeasible rules in A include a rule which is weaker than (strictly less than according to $\le$) all the defeasible rules in B, and

• the ordinary premises in A include an ordinary premise which is weaker (strictly less than according to $\le '$) all the ordinary premises in B.

$A \prec B$ is then defined as usual as $A \preceq B$ and $B \not \preceq$ A. By combining the definition of arguments, attack relations and preference ordering, we have the following definitions:

Definition 8

(Structured Argumentation Framework). A structured argumentation framework is a triple $\langle \mathcal {A}, att, \preceq \rangle$, where $\mathcal {A}$ is the set of all arguments constructed from the knowledge in the argumentation system, att is the attack relation, $\preceq$ is an preference ordering on $\mathcal {A}$.

Definition 9

(ASPIC $^{+}$ Defeat).  A defeats B iff A undercuts B, or if A rebuts/undermines B on $B'$ and $B'$’s preference level is less than or equal to that of A ($B' \preceq A$).

Then the idea of an argumentation framework follows from Definitions 5 and 9.

Definition 10

(Argumentation Framework). An (abstract) argumentation framework AF corresponding to a structured argumentation framework $SAF = \langle \mathcal {A}, att, \preceq \rangle$ is a pair $\langle \mathcal {A}, Defeats \rangle$ such that Defeats is the defeat relation on $\mathcal {A}$ determined by SAF.

Example 1

(adapted from [11]). Consider that we have the argumentation system $AS = \langle \mathcal {L}, \mathcal {R}, n \rangle$ where: $\mathcal {L}= \{a, b, c, d, e, f, \overline{a}, \overline{b}, \overline{c}, \overline{d}, \overline{e}, \overline{f},\}$, $\mathcal {R}$ is $\mathcal {R}_s = \{d,f \rightarrow \overline{b}\}$ and $\mathcal {R}_d = \{a \Rightarrow b; \overline{c} \Rightarrow d; e \Rightarrow f; a \Rightarrow \overline{nd} \}$ and $n(\overline{c} \Rightarrow d) = nd$. We then add the knowledge-based $\mathcal {K}$ such that $\mathcal {K}_n = \emptyset$ and $\mathcal {K}_p = \{ a; \overline{c}; e ; \overline{e} \}$ to get the argumentation theory $AT = \langle AS, \mathcal {K}\rangle$. From this we can construct the arguments:

$$ \begin{array}{lllll} A_1 = [a]; A_2 = [A_1 \Rightarrow b]; A_3 = [A_1 \Rightarrow \overline{nd}]; \\ B_1 = [\overline{c}]; B_2 = [B_1 \Rightarrow d]; B'_1 = [e]; B'_2=[B'_1 \Rightarrow f]; B=[B_2,B'_2 \rightarrow \overline{b}]; \\ C = [\overline{e}]; \end{array} $$

Let’s call this set of arguments $\mathbf {A}$, so that: $\mathbf {A} = \{A_1, A_2, A_3, B_1, B_2, B'_1, B'_2, B, C\}$. Note that $\mathtt {Prem}(B) = \{\overline{c}; e\}$, $\mathtt {Sub}(B) = \{B_1;B_2;B'_1;B'_2;B\}$, $\mathtt {Conc}(B) = \overline{b}$, and $\mathtt {TopRule}(B) =d,f \rightarrow \overline{b}$. The attacks between these arguments are shown in Fig. 1(a). These make up the set $att = \{(C, B'_1), (B'_1, C), (C, B'_2), (C, B), (B, A_2), (A_3, B_2), (A_3, B)\}$ With a preference order $\preceq$ defined by : $A_2 \prec B; C \prec B; C \prec B'_1; C \prec B'_2$, we have the structured argumentation framework $\langle \mathbf {A}, att, \preceq \rangle$. This structured argumentation framework establishes a defeat relation $Defeats = \{(B'_1, C), (B, A_2), (A_3, B), (A_3, B_2)\}$ which is shown in Fig. 1(b). With this, we can finally write down the argumentation framework $\langle \mathbf {A}, Defeats\rangle$. Note that this is not a rational aspic $^{+}$ framework, since the strict rules are not closed under transposition, but serves to explain the concepts introduced above.

Fig. 1.

The attack and defeat relations from Example 1. A dotted arrow shows undercutting, a dashed arrow shows rebutting, and a solid arrow shows undermining.

3 ASPIC $_{D}^{+}$: A Purely Defeasible System

3.1 Definition

The full definition of aspic $_{D}^{+}$ starts from a variation on the aspic $^{+}$  notion of an argumentation system where there are only defeasible elements:

Definition 11

( ASPIC $_{D}^{+}$  Argumentation System). An argumentation system is a triple $AS_D = \langle \mathcal {L}, \mathcal {R}_d, n \rangle$ where:

• $\mathcal {L}$ is a logical language closed under negation $\bar{\cdot }$.

• $\mathcal {R}_d$ is a set of defeasible inference rules of the form $\phi _1, \ldots , \phi _n \Rightarrow \phi$ (where $\phi _i, \phi$ are meta-variables ranging over wff in $\mathcal {L}$).

• $n : \mathcal {R}_d \mapsto \mathcal {L}$ is a naming convention for defeasible rules.

Definition 12

( ASPIC $_{D}^{+}$ Knowledge Base). A knowledge base in an argumentation system $\langle \mathcal {L}, \mathcal {R}_d, n \rangle$ is a set $\mathcal {K}_p$ of ordinary premises.

Definition 13

( ASPIC $_{D}^{+}$ Argumentation Theory). An argumentation theory $AT_D$ is a pair $\langle AS, \mathcal {K}_p \rangle$ of an argumentation system AS and a set of ordinary premises $\mathcal {K}_p$.

Arguments in aspic $_{D}^{+}$  are then defined as in Definition 5, but there are no strict rules or axioms so there are no strict or firm arguments.

Since any aspic $_{D}^{+}$  argumentation theory is an aspic $^{+}$  argumentation theory with an empty set of strict rules and an empty set of axioms, we have:

Proposition 1

For a given language $\mathcal {L}$, $\mathbf {AT_D}$, the set of all possible aspic $_{D}^{+}$ argumentation theories, is a subset of $\mathbf {AT}$, the set of all possible aspic $^{+}$ argumentation theories.

Proof. Pick any aspic $_{D}^{+}$ theory $AT_D\in \mathbf {AT_D}$. By definition this is a pair $\langle AS_D, \mathcal {K}_p \rangle$ where $AS_D = \langle \mathcal {L}, \mathcal {R}_d, n \rangle$. It is also an aspic $^{+}$ theory $AT\in \mathbf {AT}$ where $AT = \langle AS, \mathcal {K}_p\rangle$ (an aspic $^{+}$ theory with no axioms) and $AS = \langle \mathcal {L}, \mathcal {R}_d, n \rangle$ (an aspic $^{+}$ theory with no strict rules). Having made no specific assumptions about the composition of $AT_D$, the result holds for all possible aspic $_{D}^{+}$ theories.

However, despite the fact that the set of all possible aspic $_{D}^{+}$ theories is a subset of all possible aspic $^{+}$ theories, we can translate any specific aspic $^{+}$ theory into a specific aspic $_{D}^{+}$ theory. We demonstrate this by defining a translation:

Definition 14

(Defeasible version).  aspic $_{D}^{+}$ theory $AT_D$ is the defeasible version of aspic $^{+}$ theory $AT = \langle AS, \mathcal {K}_n\cup \mathcal {K}_p\rangle$ where $AS = \langle \mathcal {L}, \mathcal {R}_s\cup \mathcal {R}_p, n \rangle$ iff:

• $AS_D = \langle \mathcal {L}, \mathcal {R}_d\cup \mathcal {R}_{d'}, n' \rangle$, where $\mathcal {R}_{d'} = \{\phi _1, \ldots , \phi _n \Rightarrow \phi \mid \phi _1, \ldots , \phi _n \rightarrow \phi \in \mathcal {R}_s\}$ and $n'$ is n extended to name all the rules in $\mathcal {R}_{d'}$.

• $AT_D = \langle AS_D, \mathcal {K}_p\cup \mathcal {K}_{p'} \rangle$, where $\mathcal {K}_{p'} = \{\phi \mid \phi \in \mathcal {K}_n\}$.

If $AT_D$ is the defeasible version of AT, we call $AS_D$ the defeasible version of AS and write $AT_D= def(AT)$ and $AS_D = def(AS)$. We call the set of rules $\mathcal {R}_{d'}$ that were strict in AT the set of converted rules, and the set of premises $\mathcal {K}_{p'}$ that were axioms in AT are the set of converted premises. The defeasible version of an argument $A\in \mathcal {A}(AT)$ is an argument $A_D\in \mathcal {A}(AT_D)$ such that every axiom in A is replaced by the corresponding converted premise, and every struct rule in A is replaced by the corresponding converted rule.

In other words, $AT_D$ is the defeasible version of AT, if every axiom of AT becomes an ordinary premise of $AT_D$, and every strict rule in AT becomes a defeasible rule of AT, while all other components of AT are unchanged.

Given a preference order $\preceq$ over the elements of an aspic $^{+}$ theory AT, we will need to specify the preference order $\preceq _D$ over the defeasible version of the theory. One way to specify $\preceq _D$ is as follows in terms of the pre-orderings over the rules and premises of $AT_D$.

Definition 15

(Strict-first preference ordering). Given an aspic $^{+}$ theory $AT=\langle \langle \mathcal {L}, \mathcal {R}_s\cup \mathcal {R}_d, n \rangle , \mathcal {K}_n\cup \mathcal {K}_p \rangle$ and preference orders $\le$ and $\le '$ over the defeasible rules and premises of that theory, the strict-first preference orderings $\le _{sf}$ and $\le '_{sf}$ over the rules and premises of the defeasible version of AT, $AT_D= \langle \langle \mathcal {L}, \mathcal {R}_d\cup \mathcal {R}_{d'}, n' \rangle , \mathcal {K}_p\cup \mathcal {K}_{p'} \rangle$ are such that:

• For every $r, r'\in \mathcal {R}_{d}$, $r \le _{sf} r'$ iff $r \le r'$, and for every $k, k'\in \mathcal {K}_{p}$, $k\le '_{sf}k'$ iff $k\le ' k'$.

• For any $r\in \mathcal {R}_{d}$ and any $r'\in \mathcal {R}_{d'}$, $r <_{sf} r'$, and for every $r', r''\in \mathcal {R}_{d'}$, $r'=_{sf} r''$.

• For any $k\in \mathcal {K}_{p}$ and any $k'\in \mathcal {K}_{p'}$, $k <'_{sf} k'$, and for every $k', k''\in \mathcal {K}'_p$, $k' ='_{sf} k''$.

where $r =_{sf} r'$ if $r\le _{sf}r'$ and $r'\le _{sf}r$, $r <_{sf} r'$ if $r\le _{sf}r'$ and $r'\not \le _{sf}r$, $k ='_{sf} k'$ if $k\le '_{sf}k'$ and $k'\le '_{sf}k$, and $k <'_{sf} k'$ if $k\le '_{sf}k'$ and $k'\not \le '_{sf}k$.

In other words, all the elements of $AT_D$ that were defeasible in AT have the same preference order as in AT, and all elements that were strict in AT are strictly higher in the preference order than any element that was defeasible in AT. The notion of attack in aspic $_{D}^{+}$ differs from that in aspic $^{+}$ in that there is no restriction on rebut, and any rule can be undercut:

Definition 16

( ASPIC $_{D}^{+}$ Attack). An argument A attacks an argument B iff A undermines, rebuts or undercuts B, where:

• A undermines B (on $B'$) iff $\mathtt {Conc}$(A) $= \overline{\phi }$ for some $B'=\phi \in \mathtt {Prem}(B)$.

• A rebuts B (on $B'$) iff $\mathtt {Conc}$(A) $= \overline{\phi }$ for some $B' \in \mathtt {Sub}(B)$.

• A undercuts B (on $B'$) iff $\mathtt {Conc}$(A) $= \overline{n(r)}$ for some $B' \in \mathtt {Sub}(B)$.

With these definitions, we can once again combine the definition of arguments, attack relations and the preference ordering from Definition 7 to get notions of a structured argumentation framework and defeat that are the same as for aspic $^{+}$. To begin to understand the relationship between aspic $^{+}$ and aspic $_{D}^{+}$, consider this version of Example 1:

Example 2

Consider the aspic $_{D}^{+}$ argumentation system $AS_D$ which is the defeasible version of the system AS in Example 1. We have $\mathcal {R}_d = \{a \Rightarrow b; \overline{c} \Rightarrow d; e \Rightarrow f; a \Rightarrow \overline{nd}; d,f \Rightarrow \overline{b} \}$, $\mathcal {K}_p = \{ a; \overline{c}; e ; \overline{e} \}$, and $n(\overline{c} \Rightarrow d) = nd$. We can construct the arguments:

$$ \begin{array}{lll} A_1 = [a]; A_2 = [A_1 \Rightarrow b]; A_3 = [A_1 \Rightarrow \overline{nd}]; \\ B_1 = [\overline{c}]; B_2 = [B_1 \Rightarrow d]; B'_1 = [e]; B'_2=[B'_1 \Rightarrow f]; B=[B_2,B'_2 \Rightarrow \overline{b}]; \\ C = [\overline{e}]; \end{array} $$

Compared with the attacks in Example 1, there is an additional attack here: $A_2$ rebuts B. With the same preference ordering $\preceq$ over arguments as in Example 1, the defeat relation remains same.

3.2 Properties of ASPIC $_{D}^{+}$

We begin by showing that aspic $_{D}^{+}$ satisfies the three rationality postulates that were introduced in [6] and since then have been considered the basic requirement of a sensible argumentation system. Without strict rules, two of these postulates follow immediately.

Proposition 2

(Closure under Strict Rules). The conclusions of any extension an aspic $_{D}^{+}$ theory are closed under strict rules.

Proof. With no strict rules, the conclusion follows immediately.

Proposition 3

(Direct Consistency). The conclusions of any extension of an aspic $_{D}^{+}$ theory are consistent.

Proof. Suppose the conclusions of one of the extensions E are inconsistent, i.e., there exist two arguments $A,A' \in E$ such that $\mathtt {Conc}(A) = \overline{\mathtt {Conc}(A')}$. If $\mathtt {Conc}(A) \in \mathcal {K}$, by Definition 6, then $A'$ undermines A. On the other hand, if $\mathtt {Conc}(A) \not \in \mathcal {K}$, by Definition 6, then $A'$ rebuts A. Either way, $A'$ attacks A in any case. Similarly, A attacks $A'$.

According to Definition 9, at least one of the attack relations is a defeat relation. Therefore, E is not conflict-free and thus E is not an extension under Dung’s semantics. The contradicition defeats the assumption of inconsistency and the result holds.

Proposition 4

(Indirect Consistency). The closure under strict rules of the conclusions of any extension of an aspic $_{D}^{+}$ theory is consistent.

Proof. With no strict rules, this follows immediately from Proposition 3.

Despite the triviality of two of the results, it is worth noting that there are no restrictions on the semantics for which these results hold — they hold for all the standard Dung semantics. Thus aspic $_{D}^{+}$ goes further than the aspic- of [7] in extending the scope of reasoning possible with unrestricted rebut since aspic- only satisfied the rationality postulates for the grounded semantics. Of course, this extension is achieved by giving up strict rules, and it is natural to ask what the consequence is for what can be represented in an aspic $_{D}^{+}$ theory. Would using aspic $_{D}^{+}$ mean any restriction on what can be represented? Our main result is to show that there is no restriction on what can be represented in aspic $_{D}^{+}$ compared with what can be represented in aspic $^{+}$ in the sense that for any aspic $^{+}$ theory we can build an aspic $_{D}^{+}$ theory with the same justified conclusions. We start with the observation that:

Proposition 5

For a given language $\mathcal {L}$, there is a defeasible version $AT_D$ of any aspic $^{+}$ argumentation theory AT.

Proof. Consider the clauses of Definition 14 as a series of rewrite rules. Any AT can be converted into its defeasible version by turning every axiom into an ordinary premise and every strict rule into a defeasible rule.

This means that whatever information we have in an aspic $^{+}$ theory, we can capture it in an aspic $_{D}^{+}$ theory — we don’t lose the ability to represent information about the world by using aspic $_{D}^{+}$ rather than aspic $^{+}$. However, it is not just representing information that is important. The set of arguments that can be constructed from a theory, and, in particular, the justified conclusions of a theory are also important.

Proposition 6

Given an aspic $^{+}$ theory AT and its defeasible version $AT_D$, $|\mathcal {A}(AT)| = |\mathcal {A}(AT_D)|$ and for every $A\in AT$ there is exactly one $A_D\in \mathcal {A}(AT_D)$ such that $A_D$ is the defeasible version of A.

Proof. We show there is a 1-to-1 map between $\mathcal {A}(AT)$ and $\mathcal {A}(AT_D)$. For each argument that is just a premise or an axiom $A=[\phi ]$, we have $A_D=[\phi ]$ that is just a premise; for each argument $A=[A_1, \ldots , A_n \Rightarrow \phi ]$, we have $A_D=[A_{1_D}, \ldots , A_{n_D} \Rightarrow \phi ]$; for each argument $A=[A_1, \ldots , A_n \rightarrow \phi ]$, we have $A_D=[A_{1_D}, \ldots , A_{n_D} \Rightarrow \phi ]$.

Thus any aspic $^{+}$ theory can be turned into an aspic $_{D}^{+}$ theory, and we can generate the same number of arguments, but arguments that had strict components will now only have defeasible components. Furthermore, there are preference orderings such that the same preferences exist between aspic $_{D}^{+}$ arguments as between the corresponding aspic $^{+}$ arguments:

Proposition 7

Consider the set of arguments $\mathcal {A}$ of an aspic $^{+}$ theory AT and the set of arguments $\mathcal {A}_D$ constructed from the defeasible version of the theory $AT_D$. If the preference order over $AT_D$ is the strict-first version of that over AT, then using the weakest link principle, for any $A, B\in \mathcal {A}$, and $A_D, B_D\in \mathcal {A_D}$ where $A_D, B_D$ are the defeasible versions of A and B, $A_D \preceq _D B_D$ iff $A \preceq B$.

Proof. Let $AT=\langle AS, \mathcal {K}_n\cup \mathcal {K}_p \rangle$ and $AT_D=\langle AS_D, \mathcal {K}_{p'}\cup \mathcal {K}_p\rangle$. Consider the preference order $\le$ over rules in AT, and the preference order $\le '$ over premises. Let $\langle \le _D,\le '_D \rangle$ contain all the relations in $\langle \le ,\le ' \rangle$. Since $AF_D$ has more defeasible elements than AF, we need to determine where these elements fit in the ordering. With a strict-first ordering, the translated strict rules/axioms have the highest preference ordering, and so the weakest links in $\mathcal {A}(AT_D)$ are not the translated strict rules/axioms. Furthermore, all the remaining rules/premises in $AT_D$ have the same preference ordering as in AT. Therefore, $AT_D$ and AT have the same preference ordering over arguments.

In other words, using the weakest link principle, we can take a set of aspic $^{+}$ arguments create the defeasible versions of those arguments and still have the same preference ordering as over the original set of arguments. This allows us to show our main result, that we can construct a defeasible version of a given aspic $^{+}$ framework such that the justified conclusions of both theories are the same.

Proposition 8

Consider a rational aspic $^{+}$ theory AT and its defeasible version $AT_D$ where the preference ordering over $AT_D$ is the strict-first version of the ordering over AT. Under the weakest link principle, the justified conclusions of AT and $AT_D$ are the same.

Proof. From Proposition 6 we know that for every argument in $\mathcal {A}(AT_D)$, there is an argument in $\mathcal {A}(AT)$, with the same conclusion, and vice versa. From Proposition 7, we know that under the weakest link principle, the preference order $\preceq$ over $\mathcal {A}(AT_D)$is the same as the preference order $\preceq _D$ over $\mathcal {A}(AT_D)$. Now, consider the attack relations att and $att_D$ over $\mathcal {A}(AT)$ and $\mathcal {A}(AT_D)$. If $(A, A') \in att$, then $(A_D, A'_D) \in att_D$ and there is an attack between the defeasible versions of the arguments $A_D$ and $A'_D$. However, $att_D$ can contains more attacks. $(A_D, A_D')$ can be in $att_D$ when $(A, A') \not \in att$ iff (1) $A'$ is (just) an axiom in AT or (2) $A'$ has a strict $\mathtt {TopRule}$ and the attack is not permitted by restricted rebut. We now show, in turn, that these additional attacks do not affect the justified conclusions.

First, if $A'$ is an axiom, then $A'_D$, which as a lone premise that is the defeasible version of an axiom, has the highest possible preference. Thus it can only be defeated by an $A_D$ that has the highest level of preference. Such an argument is the defeasible version of a strict argument. However, if A was strict, AT would not be rational (it would have two strict elements in conflict). Therefore, we have the same defeat relations over $\mathcal {A}(AT)$ and $\mathcal {A}(AT_D)$ and hence the same justified conclusions for AT and $AT_D$.

Second, if $\mathtt {TopRule}(A')$ is strict, there are two sub-cases that concern us. (a) If $A_D \prec A'_D$, the attack does not become a defeat. Thus $AF_D$ and AF have the same defeat relation, therefore they have the same justified conclusions. (b) If $A'_D \preceq A_D$, then there is one more defeat relation over $\mathcal {A}(AT_D)$ than over $\mathcal {A}(AT)$. We will show that this additional defeat relation has no effect. Consider applying all the defeat relations except this additional one — there are three possibilities for the status of $A'_D$ which will be mirrored by the status of $A'$ which does not have to contend with this additional defeat, and for each of these, we have to consider all three possibilities for the status of $A_D$.

• (1) $A_D'$ is labeled $\mathtt {IN}$. If $A_D$ is labeled $\mathtt {IN}$, then AT has two $\mathtt {IN}$ arguments, A and $A'$, and the conclusions of these arguments are in the set of justified conclusions. However, since $A_D$ and $A'_D$ rebut one another, the conclusions of A and $A'$ are contradictory, violating direct consistency. Thus A and $A'$ cannot both be $\mathtt {IN}$, and so neither can $A_D'$ and $A_D$ before the application of the new defeat. If $A_D$ is labeled $\mathtt {OUT}$  then adding the defeat relation $(A_D, A'_D)$ has no effect. If $A_D$ is labelled $\mathtt {IN}$, the situation is more complicated. We start by noting that A will also be $\mathtt {UNDEC}$, and then consider how this can be the case. A has a strict top rule, so $A'= [A'_1, \ldots , A'_n \rightarrow a]$ where the top rule is $p_1, \ldots , p_n \rightarrow a$. Similarly, $A=[A_1, \ldots , A_n \Rightarrow \overline{a}]$ with a top rule $q_1, \ldots , q_n \Rightarrow \overline{a}$. By closure under transposition, there exists a strict rule $p_1, \ldots , p_{i-1}, \overline{a}, p_{i+1}, \ldots , p_n \rightarrow \overline{p_i}$ in AT. Since $A'_D \preceq A_D$, it is not possible for $A'$ to be strict, so $A'$ has at least one defeasible sub-argument, and hence a sub-argument with a defeasible top-rule. Lets assume that this is one of the $A'_1, \ldots , A'_n$ that combine with the strict top rule, and call it $A'_i$. Using the strict rule from the transposition of the top rule, we get an argument $B=[A'_1, \ldots , A'_{i-1}, A, A'_{i+1}. \ldots , A'_n \rightarrow \overline{p_i}]$ which rebuts $A'$. B is A plus the $A'_j$, $j\ne i$, and the transposed strict rule. If $A'_1, \ldots , A'_n$ do not have defeasible top rules, then we chain the corresponding transposed stricttop rule(s) to B to build an argument that attacks $A'$ further down the argument tree until we get an argument, call it $B'$, which rebuts $A'$ on its defeasible sub-argument. Now, $A' \preceq B'$ since $A' \preceq A$ and $B'$ is A plus some sub-arguments of $A'$ and a sequence of strict (transposed) rules. Therefore $B'$ defeats $A'$. Moreover, any defeater of $B'$ must be a defeater of A or $A'$. Next we consider the labeling. Since $A'$ is labeled $\mathtt {IN}$, all the defeaters of $A'$ are labeled $\mathtt {OUT}$. Since A is labeled $\mathtt {UNDEC}$, all the defeaters of A are labeled $\mathtt {OUT}$ or $\mathtt {UNDEC}$. Therefore, the defeaters of B, which are the defeaters of A or $A'$, are labelled $\mathtt {OUT}$ or $\mathtt {UNDEC}$. Thus B is labeled $\mathtt {IN}$ or $\mathtt {UNDEC}$. Since B defeats $A'$, $A'$ can not be labeled $\mathtt {IN}$, contradicting what we started with.

• (2) $A_D'$ is labeled $\mathtt {OUT}$. Adding one more defeat relation $(A_D, A_D')$ has no effect.

• (3) $A_D'$ is labeled $\mathtt {UNDEC}$. If $A_D$ is labeled $\mathtt {OUT}$ or $\mathtt {UNDEC}$, then adding the defeat relation $(A_D, A_D')$ has no effect. However, if $A_D$ is labeled $\mathtt {IN}$, then applying the last defeat relation means that $A_D'$ will now be labeled $\mathtt {OUT}$ while $A'$, which does not have to contend with $(A, A')$, will be $\mathtt {UNDEC}$.

So $A_D'$ cannot be initially labeled $\mathtt {IN}$. If it is labelled $\mathtt {OUT}$, the status of $A'_D$ cannot change as a result of the additional defeat. If $A_D'$ is initially labeled $\mathtt {UNDEC}$, the status of $A'_D$ can change. However, by showing that $A'_D$ does not defeat any other arguments we can show that this change does not affect the justified conclusions. Consider an argument $B \in \mathcal {A}(AT_D)$ that is attacked by $A'_D$. $A'_D$ cannot undercut B since the conclusion of $A'_D$ is not a “rule” (if it were a rule, there would be no rebut between $A_D$ and $A'_D$ and there would be no new defeat relation to consider). $A'_D$ can not undermine B since the conclusion of $A'_D$ is not a premise because we know that $A'$ and hence $A'_D$ has a $\mathtt {TopRule}$. So we can only be dealing with a rebut, and since we already know that $A_D$ rebuts $A_D$, B has to be an argument of which $A_D$ is a sub-argument. Since $A'_D \prec A_D$, $A'_D$ does not defeat B.

Thus, in all of these three sub-cases of (b), the additional defeat $(A_D, A'_D)$ has no effect on the status of the arguments in $\mathcal {A}(AT_D)$, again there is no difference between the justified conclusions of AT and $AT_D$, and the result holds.

This result justifies our claim that aspic $_{D}^{+}$ makes it possible to represent the same information as aspic $^{+}$. Given an aspic $^{+}$ theory, we can encode the information in purely defeasible form in an aspic $_{D}^{+}$ theory that gives us exactly the same set of (justified) conclusions. The following example helps to show how this is possible.

Example 3

Consider that we start with the following theory $AT_1$ (given the same language as before), closed under transposition:

$$\begin{aligned} \begin{array}{ll} \mathcal {R}_d = \{a \Rightarrow b; b' \Rightarrow \overline{c} \} &{}\qquad \mathcal {R}_s = \{a' \rightarrow b'; b \rightarrow c; \overline{b'} \rightarrow \overline{a'}; \overline{c} \rightarrow \overline{b}\} \\ \mathcal {K}_n = \{a; a'\} &{}\qquad \mathcal {K}_p = \emptyset \end{array} \end{aligned}$$

Then we can construct the following arguments:

$$ \begin{array}{llll} A_1=[a] &{} A_2= [A_1 \Rightarrow b] &{} A_3= [A_2 \rightarrow c] \\ B_1=[a'] &{} B_2= [B_1 \rightarrow b'] &{} B_3= [B_2 \Rightarrow \overline{c}] &{} B_4=[B_3 \rightarrow \overline{b}] \end{array} $$

The attack relations are shown in Fig. 2(a). Now we translate this framework to the aspic $_{D}^{+}$ theory $AT_2$:

$$\begin{aligned} \begin{array}{ll} \mathcal {R}_d = \{a \Rightarrow b; b' \Rightarrow \overline{c} \} &{}\qquad \mathcal {R}'_d = \{a' \Rightarrow b'; b \Rightarrow c; \overline{b'} \Rightarrow \overline{a'}; \overline{c} \Rightarrow \overline{b}\} \\ \mathcal {K}'_n = \{a; a'\} &{}\qquad \mathcal {K}_p = \emptyset \end{array} \end{aligned}$$

Then we can construct the following arguments:

$$ \begin{array}{llll} A_1=[a] &{} A_2= [A_1 \Rightarrow b] &{} A_3= [A_2 \Rightarrow c] \\ B_1=[a'] &{} B_2= [B_1 \Rightarrow b'] &{} B_3= [B_2 \Rightarrow \overline{c}] &{} B_4=[B_3 \Rightarrow \overline{b}] \end{array} $$

The attack relations are shown in Fig. 2(d). Now let’s consider the different possible preference orderings over rules:

• (a) $a \Rightarrow b = b' \Rightarrow \overline{c}$ ². By the weakest link principle, all the attack relations are defeat relations, see Fig. 2(a) and (d). Here $AT_2$ has additional defeat relations, but they are directed at arguments that are already defeated. Under the grounded semantics, the set of arguments in the extension is $\{A_1,B_1,B_2\}$ and $\{A_1,B_1,B_2\}$, and the justified conclusions are $\{a, a',b'\}$ and $\{a, a',b'\}$.

• (b) $a \Rightarrow b < b' \Rightarrow \overline{c}$. By the weakest link principle, the defeat relations are shown in Fig. 2(b) and (e). Again $AT_2$ has an additional defeat relation, but again it has no effect on the justified conclusions. Under the grounded semantics, the set of arguments in the extension is $\{A_1,B_1,B_2,B_3,B_4\}$, $\{A_1,B_1,B_2,B_3,B_4\}$ and $\{A_1,A_2,B_1,B_2,B_3\}$, and the justified conclusions are $\{a,\overline{b}, a',b',\overline{c}\}$ and $\{a,\overline{b}, a',b',\overline{c}\}$.

• (c) $a \Rightarrow b > b' \Rightarrow \overline{c}$. By the weakest link principle, the defeat relations are shown in Fig. 2(c) and (f). As before $AT_2$ has additional defeats, but they have no effect. Under the grounded semantics, the set of arguments in the extension is $\{A_1,A_2,A_3,B_1,B_2\}$, and $\{A_1,A_2,A_3,B_1,B_2\}$, and the justified conclusions are $\{a,b, a',b',c\}$ and $\{a,b, a',b',c\}$.

For all the cases, the justified conclusions of $AT_1$ and $AT_2$ are exactly same.

Fig. 2.

Attack and defeat relations for $AT_1$ and $AT_2$. (a) Attack relations for $AT_1$ and Defeat relations for $AT_1$ in case (a), (b) Defeat relations for $AT_1$ case (b), (c) Defeat relations for $AT_1$ in case (c), (d) Attack relations for $AT_2$ and Defeat relations for $AT_2$ in case (a), (e) Defeat relations for $AT_2$ case (b), (f) Defeat relations for $AT_2$ case c)

4 Conclusion

We have shown that aspic $_{D}^{+}$, the defeasible subset of aspic $^{+}$, has the same functionality in terms of knowledge representation as aspic $^{+}$. Both formalisms draw the same justified conclusions from corresponding argumentation systems. In addition, aspic $_{D}^{+}$ goes further than aspic $^{+}$and aspic- in the sense of satisfying the rationality postulates with unrestricted rebut for all of Dung’s semantics. In our view, this justifies the choice of aspic $_{D}^{+}$ in any application that might use aspic $^{+}$. Proposition 5 tells us that using aspic $_{D}^{+}$ means we can represent exactly the same information that we could in aspic $^{+}$, and Proposition 8 tells us that provided that we encode strict rules as defeasible rules with the highest level of preference and use the weakest link principle, the same set of justified conclusions will be obtained as if we had used aspic $^{+}$. In that sense, we do not lose anything over what is possible in aspic $^{+}$ by using aspic $_{D}^{+}$. In addition, and in contrast to aspic $^{+}$, we do not have to impose any restrictions on aspic $_{D}^{+}$ in order for it to accord to the rationality principles, which, as [7] points out, is rather counter-intuitive and hard to explain to users.