Argumentation for Practical Reasoning: An Axiomatic Approach

Abstract

An argument system could be viewed as a pair of a set of argument and a binary attack relation between arguments. The semantics of argumentation rests on the acceptability of arguments and the structure of arguments and their attack relations. While there is a relatively good understanding of the acceptability of arguments, the same can not be said about their structure and attack relations. In this paper, we present an axiomatic analysis of the attack relations of rule-based argument systems by presenting a set of simple and intuitive properties and showing that they indeed determine an uniquely defined common attack relations for rule-based argument systems.

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

People of all walks of life get involved in argumentation on a daily basis. Arguing could be viewed as one of the most intellectual important activities of humans during their entire lives. Peoples of different cultures, countries, times often have different arguments based on different world views, rules, norms, conventions, beliefs and assumptions ect. For example, Harry Potter’s arguments are based on the “science” of witch crafts and vampires while the Inca peoples in the pre-Columbus time believed in human sacrifices. Despite their often distinctly “incomparable” arguments, humans could understand each other (if they make an effort). How could it be possible?

Humans may have different ways to build their arguments but they all share similar ways of drawing conclusions from a given set of arguments. Such “similar ways” seem to be captured by an old saying “he/she who laughs last laughs best” that seems to be understood and employed by every rational human being. The saying could be viewed in fact as an common mechanism for drawing conclusions from conflicting arguments. Research on argumentation could be viewed as efforts to understand the structure and dynamics of this common mechanism.

Example 1

Consider a dialogue between a boy and his parents.

• Father to Boy: Stop playing play with the ipad as you have not finished your homework yet.

• Boy to Father: Come on Dad ! There is no school tomorrow.

• Father to Boy: Well, today is not a school holiday.

• Boy to Mother: Mum, I do not need to do my homework because there is no school tomorrow, right ?

• Father to Mother: Of course he needs to do it.

• Mother to both Son and Father: Guys, I have things to do. Sort out your quarrel by yourself.

In essence the dialogues is about which of the following two arguments should be accepted:

Boy’s argument B: No school tomorrow, no homework.

Father’s argument F: There is school today, hence homework.

Arguments B, F attack each other and obviously neither father nor son gives up their argument. In other words, their sets of accepted arguments are $\{F\}, \{B\}$ respectively. As the mother refuses to be partisan, her set of accepted arguments is empty.

This simple dialogue reveals a fundamental issue in practical argumentation:

Different agents will get different conclusions (or semantics) from a same set of arguments.

In other words, a central issue in practical argumentation is the question: What arguments do rational people accept in an exchange of arguments and how do we know that some of them could be the “consensus” of the “debate”?

or more formally, Can we provide a formal model of argument systems for practical reasoning ?

At its most abstraction, an argument system could be viewed as an argumentation framework [23] consisting of a set of arguments and a binary attack relation between them. Though simple, argumentation frameworks are powerful enough to provide a sophisticated account of the acceptance of arguments representing different ways peoples could draw conclusions from exchanges of arguments.

While there is a good understanding about the acceptability of arguments due to an extensive amount of research [2, 4, 5, 10, 15, 23, 26], more need to be done to gain a better understanding about the structure of arguments and their attack relations. In experimental domains like experimental medicine, arguments often have no internal structure as the purpose of the experiments is to uncover the underlining rules [32]. In contrast, arguments in commonsense reasoning and legal domains are often based on rules [6, 20]. In both medicine and legal domains as well as in commonsense reasoning, one could easily imagine arguments based on both complex rules and uncertainties. The complex structure of arguments often lead to challenging questions about the structure of their attack relations.

In this paper, we will first give an overview of the works on the acceptability of arguments wrt abstract argumentation. The main part of the paper is focused on rule-based argument systems as they are the most researched instances of abstract argumentation. We conclude with a discussion on probabilistic argumentation.¹

There are extensive research on rule-based systems (see for example [9, 11, 17, 28, 29, 35, 36, 38–40]). Distinct semantics have been proposed that could lead to contradictory answers to the same query as the following example illustrates.

Example 2

Consider a knowledge base K (adapted from [11, 12, 18]), consisting of three defeasible rules

$$d_1: \,Dean \Rightarrow Professor \quad d_2:\,\,Professor \Rightarrow Teach \quad d_3:\,\,\,Administrator \Rightarrow \lnot Teach$$

and two strict rules

$$r:\,\,Dean \rightarrow Administrator\quad r': \lnot Administrator \rightarrow \lnot Dean$$

with $\,\,d_1 \prec d_3 \prec d_2$ ².

Suppose we know some Dean. The question is whether the dean teaches.

Proposed approaches in literature deal with this example differently. Modgil and Prakken [35] in their influential ASPIC+ framework proposed four attack relations where one of them leads to semantics with respect to which the dean does not teach while the other three as well as the prominent non-argument-based approach of Brewka and Eiter [11] lead to conclusion that the dean does teach.

The example illustrates the need to establish general principles for characterizing and evaluation of possible semantics for rule-based systems.

2 Abstract Argumentation

An abstract argumentation framework [23] is defined simply as a pair $AF=(AR, att)$ where AR is a set of arguments and $att \subseteq AR \times AR$ and $(A,B) \in att$ means that A attacks B.

A set of argument S attacks (or is attacked by) an argument A (or a set of arguments R) if some argument in S attacks (or is attacked by) A (or some argument in R); S is conflict-free if it does not attack itself. A set of arguments S defends an argument A if S attacks each attack against A.

S is admissible if S is conflict-free and defends each argument in it. A complete extension is an admissible set of arguments containing each argument it defends. A preferred extension is a maximal admissible set of arguments. A stable extension is a conflict-free set of arguments that attacks every argument not belonging to it.

It is well-known that both preferred and stable extensions are complete but not vice versa.

The characteristic function of AF is defined by

$$ F_{AF}(S) = \{A \mid A \in AR, S \text { defends } A\}. $$

Since $F_{AF}$ is a monotonic function, there exists a least fixed point of $F_{AF}$. The grounded extension is defined as the least fixed point of $F_{AF}$.

As complete extensions coincide with conflict-free fixed points of $F_{AF}$, the grounded extension is also the least complete extension.

Example 1 can be represented as an argumentation framework (AR, att) where $AR = \{F,B\}$ and $att = \{(F,B), (B,F)\}$.

There are two preferred extensions that are also stable: $\{F\}, \{B\}$. There are three complete extensions $\emptyset ,\{F\}, \{B\}$. The grounded extension is hence empty.

Conceptually, the grounded extension represents an agent who is skeptical in its reasoning where other extensions represent agents who are credulous.

In Example 1, both father and son stick to their guns. The mother, who does not want to get drawn into the discussion as none of the presented arguments could be accepted without any bias, represents a skeptical reasoner.

3 Defeasible Knowledge Bases

In this section, we recall the basic notions and notations on knowledge bases from [18]. We assume a non-empty set $\mathcal L$ of ground atoms (also called a positive literal) and their classical negations (also called negative literals). A set of literals is said to be contradictory iff it contains an atom a and its negation $\lnot a$. We distinguish between domain atoms representing propositions about the concerned domains and non-domain atoms of the form $ab_d$ representing the non-applicability of defeasible rules d (even if the premises of d hold).

We distinguish between strict and defeasible rules as often done in the literature [18, 27, 28, 35, 36, 41]. A defeasible (resp. strict) rule r is of the form $b_1,\ldots ,b_n \Rightarrow h$ (resp. $b_1,\ldots ,b_n \rightarrow h$) where $b_1,\ldots ,b_n$ are domain literals and h is a domain literal or an atom of the form $ab_d$. The set $\{b_1,\ldots ,b_n \}$ (resp. the literal h) is referred to as the body (resp. head) of r and denoted by bd(r) (resp. hd(r)).

Definition 1

• 1. A rule-based system is a triple $\mathcal{R} = (RS,RD, \preceq )$ where

  • (a) RS is a set of strict rules,

  • (b) RD is a set of defeasible rules,   and

  • (c) $\preceq \,$ is a transitive relation over RD representing the preferences between defeasible rules, whose strict core is $\prec$ (i.e. $d \prec d'$ iff $d \preceq d'$ and $d' \not \preceq d$ for $d, d' \in RD$.)

• 2. A knowledge base is defined as a pair $K = (\mathcal{R},BE)$ consisting of a rule-based system $\mathcal{R}$, and a set of ground domain literals BE, the base of evidence of K, representing unchallenged observations, facts ect..

  For convenience, knowledge base K is often written directly as a quadruple $(RS,RD,\preceq ,BE)$ where RS, RD, $\preceq$ or BE of K are often referred to by $RS_K, RD_K, \preceq _K$ or $BE_K$ respectively.

Definition 2

Let $K = (RS,RD,\preceq ,BE)$ be a knowledge base. An argument wrt K is a proof tree defined inductively as follows:

• 1. For each $\alpha \in BE$, $[\alpha ]$ is an argument with conclusion $\alpha$.

• 2. Let r be a rule of the forms $\,\alpha _1,\ldots ,\alpha _n \rightarrow /\Rightarrow \alpha$, $\,\,n \ge 0,$ from $RS \cup RD$ and $\,\,A_1,\ldots ,A_n\,\,$ be arguments with conclusions $\alpha _i$, $1\le i \le n$, respectively. Then $A = \,[ A_1,\ldots ,A_n, r]$ is an argument with conclusion $\alpha$ and last rule r denoted by cnl(A) and last(A) respectively.

• 3. Each argument wrt K is obtained by applying the above steps 1, 2 finitely many times.

Example 3

Consider a rule-based system $\mathcal R$ whose sets of rules are from Example 2 together with a precedence relation consisting of just $d_2 \prec d_3$. Suppose we know some dean who is also a professor.

The considered knowledge base is represented by $K = (RS,RD,\preceq ,BE)$ with $RS = \{r, r'\}$, $RD = \{d_1, d_2, d_3\}$, $\preceq \,=\, \{ (d_2,d_3)\}$ and $BE = \{D,P\}$.³

Relevant arguments can be found in Fig. 1 where $A_1 = [[D],d_1]$, $A_2 = [A_1,d_2]$, $A'_2 = [[P],d_2]$, $A_3 = [\, [[D],r], d_3]$.

Fig. 1.

Dean example

Notation 1

The set of all arguments wrt a knowledge base K is denoted by $\mathbf{AR_{K}}$. The set of the conclusions of arguments in a set $S \subseteq AR_K$ is denoted by $\mathbf{cnl(S)}$.

A strict argument is an argument containing no defeasible rule. An argument is defeasible iff it is not strict. A defeasible argument A is called basic defeasible iff last(A) is defeasible.

For any argument A, the set of defeasible rules appearing in an argument A is denoted by $\mathbf{dr(A)}$. The set of last defeasible rules in A, denoted by $\mathbf{ldr(A)}$, is $\{last(A)\}$ if A is basic defeasible, otherwise it is equal $\,\,ldr(A_1) \cup \ldots \cup ldr(A_n)$ where $A = [ A_1,\ldots ,A_n, r]$.

An argument B is a subargument of an argument A iff $B = A$ or $A = [ A_1,\ldots ,A_n,r]$ and B is a subargument of some $A_i$. B is a proper subargument of A if B is a subargument of A and $B \ne A$.

Definition 3

Let K be a knowledge base.

• 1. The closure of a set of literals $X \subseteq \mathcal{L}$ wrt knowledge base K, denoted by $CN_{K}(X)$, is the union of X and the set of conclusions of all strict arguments wrt knowledge base $(RS_K,RD_K,\preceq _K,X_{dom})$ with $X_{dom}$ (the set of all domain literals in X) acting as a base of evidence. X is said to be closed iff $X = CN_{K}(X)$. X is said to be inconsistent iff its closure $CN_{K}(X)$ is contradictory. X is consistent iff it is not inconsistent. We also often write $X \vdash _{K} l\,\,$ iff $\,\,l \in CN_K(X)$.

• 2. K is said to be consistent iff its base of evidence $BE_K$ is consistent.

As the notions of closure, consistency depend only on the set of strict rules in the knowledge base, we often write $X \vdash _{RS} l$ or $l \in CN_{RS}(X)$ for $X \vdash _{K} l$ or $l \in CN_{K}(X)$ respectively.

Definition 4

Let $\mathcal{R} = (RS,RD,\preceq )$ be a rule-based system and $K = (\mathcal{R},BE)$ be a knowledge base.

• 1. $\mathcal R$ and K are said to be closed under transposition [13] iff for each strict rule of the form $\,\,b_1,\ldots ,b_n \rightarrow h\,$ in RS s.t. h is a domain literal, all the rules of the forms $\,\,b_1,\ldots ,b_{i-1},\lnot h,b_{i+1},\ldots ,b_n \rightarrow \lnot b_i\,$, $1\le i\le n$, also belong to RS.

• 2. $\mathcal R$ and K are said to be closed under contraposition [36, 37] iff for each set of domain literals S, each domain literal $\lambda$, if $S\vdash _{RS} \lambda$ then for each $\sigma \in S$, $\,\,S \setminus \{\sigma \} \cup \{\lnot \lambda \} \vdash _{RS} \lnot \sigma$.

• 3. $\mathcal R$ and K are said to satisfy the self-contradiction property [21] iff for each minimal inconsistent set of domain literals $X \subseteq \mathcal{L}$, for each $x \in X$, it holds: $\,\,X \vdash _{RS} \lnot x$.

Lemma 1

[18] Let $\mathcal R$ be a rule-based system that is closed under transposition or contraposition. Then $\mathcal R$ satisfies the property of self-contradiction.

Definition 5

(Attack Relation) An attack relation for a knowledge base K is a relation $att \subseteq AR_K \times AR_K$ such that there is no attack against strict arguments, i.e. for each strict argument $B \in AR_K$, there is no argument $A \in AR_K$ such that $(A,B) \in att$.

For convenience, we often say A attacks B wrt att for $(A,B) \in att$.

3.1 Basic Postulates

We recall the postulates of consistency and closure from [13] and of subargument closure from [1, 34, 35]. For simplicity, we combine the postulate of closure and the postulate of subargument closure into one.

Definition 6

Let att be an attack relation for a knowledge base K.

• att is said to satisfy the consistency postulate iff for each complete extension E of $(AR_K,att)$, the set cnl(E) of conclusions of arguments in E is consistent.

• att is said to satisfy the closure postulate iff for each complete extension E of $(AR_K,att)$, the set cnl(E) of conclusions of arguments in E is closed and E contains all subarguments of its arguments.

For ease of reference, the above two postulates are often referred to as basic postulates.

4 Sufficient Properties for Basic Postulates

As the basic postulates are more about the “output” of attack relations rather than about their structure, we present below two simple properties about the structure of attack relation that ensures the holding of the basic postulates. We first introduce some simple notations.

We say A undercuts B (at B’) if $B'$ is basic defeasible and $cnl(A) = ab_{last(B')}$. We say A rebuts B (at $B'$) iff $B'$ is a basic defeasible subargument of B and the conclusions of A and $B'$ are contradictory.

We say A directly attacks B if A attacks B and A does not attack any proper subargument of B.

An argument A is said to be generated by a set S of arguments iff all basic defeasible subarguments of A are subarguments of arguments in S. For an example, let $S = \{B_0, B_1\}$ (see Fig. 2). Let consider $A_0$. The set of basic defeasible subarguments of $A_0$ is $\{\,[ d_0]\}$. It is clear that $[d_0]$ is a subargument of $B_0$. Hence $A_0$ is generated by S. Similarly, $A_1$ is also generated by S.

Definition 7

(Strong Subargument Structure) Attack relation att is said to satisfy the property of strong subargument structure for K iff for all $A, B \in AR_K$, followings hold:

• 1. If A undercuts B then A attacks B wrt att.

• 2. A attacks B (wrt att) iff A attacks a basic defeasible subargument of B (wrt att).

• 3. If A directly attacks B (wrt att) then A undercuts B (at B) or rebuts B (at B).

We present the first result showing that strong subargument property is sufficient to guarantee the postulate of closure.

Lemma 2

Let att be an attack relations for knowledge base K satisfying the property of strong subargument structure. Then att satisfies the postulate of closure.

Proof

(Sketch) From condition 2 in Definition 7, it follows that each attack against an argument generated by complete extension E is an attack against E. The lemma holds obviously.    $\square$

A set S of arguments is said to be inconsistent if the set of the conclusions of its arguments, cnl(S), is inconsistent. We introduce below a new simple property of inconsistency resolving.

Definition 8

(Inconsistency Resolving) We say attack relation assignment att satisfies the inconsistency-resolving property for K iff for each finite set of arguments $S \subseteq AR_K$, if S is inconsistent then S is attacked (wrt att(K)) by some argument generated by S.

As we will show later, the inconsistency-resolving property is satisfied by common conditions like closure under transposition, or contradiction or the property of self-contradiction.

Example 4

Consider the basic knowledge base K consisting of just the rules appearing in arguments in Fig. 2. The set $S = \{B_0, B_1\}$ is inconsistent. The argument $A_0$ is generated by S. Let $att = \{(X,Y)\,|\, X$ rebuts Y}. It is obvious that S is attacked by $A_0$. It is clear that att is inconsistency-resolving.

Fig. 2.

Generated arguments

We present now the first important result.

Theorem 1

Let $att, att'$ be attack relations for knowledge base K.

• 1. If $att \subseteq att'$ and att is inconsistency-resolving for K then $att'$ is also inconsistency-resolving for K;

• 2. If att satisfies the strong subargument structure and inconsistency-resolving then att satisfies the postulate of consistency.

Proof

(Sketch) Assertion 1 follows easily from the definition of inconsistency-resolving. We only need to show assertion 2. From condition 2 in Definition 7, it follows that each argument generated by a complete extension E belongs to E. Therefore, if E is inconsistent then E is not conflict-free. Since E is conflict-free, E is hence consistent.    $\square$

5 Regular Attack Relation Assignments

In general, attack relations satisfying the basic postulates do not capture the semantics of prioritized rules. To see this point, consider a simple knowledge base consisting of exactly two defeasible rules $d_0:\,\,\Rightarrow a$ and $d_1\,\,\Rightarrow \lnot a$ with $d_0 \prec d_1$. There are only two arguments $A_0, A_1$ as given in Fig. 3.

Fig. 3.

Effective rebuts

The attack relation $att = \{\,(A_0,A_1), (A_1, A_0)\,\}$ has two extensions $E_i = \{A_i\}$, $i = 0,1$. It is obvious that $E_0$ satisfies both properties of inconsistency-resolving and strong subargument structure. As the prime purpose of the preference of $d_1$ over $d_0$ is to rule out extension $E_0$, attack relation att does not capture the expected semantics.

Dung [18, 24] has proposed several simple and natural properties referred to as ordinary properties, to capture the intuition of prioritized rules. We recall and adapt them below. We also motivate and explain their intuitions. We also present two novel concepts of regular attack relations and regular attack relation assignments that lie at the heart of the semantics of prioritized rules.

5.1 A Minimal Interpretation of Priorities

We first recall from [18] the effective rebut property stating a “minimal interpretation” of a preference $d_0 \prec d_1$ that in situations when both are applicable but accepting both $d_0, d_1$ is not possible, $d_1$ should be preferred.

Definition 9

(Effective Rebut) We say that attack relation att satisfies the effective rebut property for a knowledge base K iff for all arguments $A_0, A_1 \in AR_K$ such that each $A_i$, $i = 0,1$, contains exactly one defeasible rule $d_i$ (i.e. $dr(A_i) = \{d_i\}$), and $A_0$ rebuts $A_1$, it holds that $A_0$ attacks $A_1$ wrt att iff $d_0 \not \prec d_1$.

In Fig. 3, the effective rebut property dictates that $A_1$ attacks $A_0$ but not vice versa.

5.2 Propagating Attacks

Example 5

Consider the knowledge base in Example 3.

While the effective rebut property determines that $A_3$ attacks $A'_2$ (see Fig. 1) but not vice versa (because $d_2 \prec d_3$), it does not say whether $A_3$ attack $A_2$.

Looking at the structure of $A_2, A'_2$, we can say that $A_2$ is a weakening of $A'_2$ as the undisputed fact P on which $A_2'$ is based is replaced by a defeasible belief P (supported by argument $A_1$). Therefore if $A_3$ attacks $A'_2$ then it is natural to expect that $A_3$ should attack $A_2$ too.

The above analysis also shows that attacks generated by the effective rebut property, could be propagated to other arguments based on a notion of weakening of arguments. We recall this notion as well as the associated property of attack monotonicity from [18] below.

Let $A, B \in AR_{K}$ and $AS \subseteq AR_K$. Intuitively, B is a weakening of A by AS if B is obtained by replacing zero, one or more premises of A by arguments in AS whose conclusions coincide with the premises.

Definition 10

B is said to be a weakening of A by AS iff

• 1. $A = [\alpha ]$ for $\alpha \in BE$, and ($B = [\alpha ]$ or $B \in AS$ with $cnl(B) = \alpha$), or

• 2. $A = [ A_1,\ldots ,A_n,r]$ and $B = [B_1,\ldots ,B_n,r]$ where each $B_i$ is a weakening of $A_i$ by AS. By $A \downarrow AS$ we denote the set of all weakenings of A by AS.

For an illustration, consider again the arguments in Fig. 1. It is clear that $[P] \downarrow \{A_1\} = \{[P], A_1\}$, $A_2' \downarrow \{A_1\} = \{A'_2,A_2\}$.

The attack monotonicity property states that if an argument A attacks an argument B then A also attacks all weakening of B. Moreover if a weakening of A attacks B then A also attacks B.

Definition 11

(Attack Monotonicity) We say attack relation att satisfies the property of attack monotonicity for knowledge base K iff for all $A, B \in AR_{K}$ and for each weakening C of A for each weakening D of B, the following assertions hold:

• 1. If $(A, B) \in att$ then $(A,D) \in att$.

• 2. If $(C,B) \in att$ then $(A,B) \in att$.

We next recall the link-oriented property in [18] which is based on an intuition that attacks are directed towards links in arguments implying that if an argument A attacks an argument B then it should attack some part of B.

Definition 12

(Link-Orientation) We say that attack relation att satisfies the property of link-orientation for K iff for all arguments $A,B, C \in AR_K$ such that C is a weakening of B by $AS \subseteq AR_K$ (i.e. $C \in B\downarrow AS$), it holds that if A attacks C (wrt att) and A does not attack AS (wrt att) then A attacks B (wrt att).

In real world conversation, if you claim that my argument is wrong, I would naturally ask which part of my argument is wrong. The link-oriented property could be viewed as representing this intuition.

Example 6

Consider again arguments in Fig. 1. Suppose $d_2$ is now preferred to $d_3$ (i.e. $d_3 \prec d_2$). The effective rebut property dictates that $A_3$ does not attack $A'_2$. Does $A_3$ still attack $A_2$ ? Suppose $A_3$ attacks $A_2$. Since $A_3$ does not attack $A_1$ that is a subargument of $A_2$, we expect that $A_3$ should attack some other part of $A_2$. In other words, we expect that $A_3$ attacks $A'_2$. But this is a contradiction to the effective rebut property stating that $A'_2$ attack $A_3$ but not vice versa. Hence $A_3$ does not attack $A_2$.

In other words, the link-orientation property has propagated the “non-attack relation” between $A_3,A_2'$ to a “non-attack relation” between $A_3,A_2$.

We present below a novel concept of regular attack relations.

Notation 2

For ease of reference, we refer to the properties of inconsistency-resolving, strong subargument structure, effective rebuts, attack monotonicity and link-orientation as regular properties.

Definition 13

(Rgular Attack Relation) An attack relation is said to be regular iff it satisfies all regular properties.

5.3 Attack Relation Assignments: Propagating Attacks Across Knowledge Bases

While regular attack relations are natural and intuitive, they are still not sufficient for determining an intuitive semantics of prioritized rules. The example below illustrates this point.

Example 7

Consider a knowledge base $K_0$ obtained from knowledge base K in Example 3 by revising the evidence base to $BE = \{D\}$. It is clear that arguments $A_1, A_2, A_3$ belong to $AR_{K_0}$ while $A'_2$ is not an argument in $AR_{K_0}$.

As $A'_2$ does not belong to $AR_{K_0}$, the effective rebuts property does not “generate” any attacks between arguments in $AR_{K_0}$. How could we determine the attack relation for $K_0$?

As both $A_2, A_3$ belong to $AR_{K}$, $AR_{K_0}$ and the two knowledge bases $K_0, K$ have identical rule-based system, we expect that the attack relations between their common arguments should be identical. In other words, because $A_3$ attacks $A_2$ wrt K (see Example 5), $A_3$ should attack $A_2$ also wrt $K_0$. This intuition is captured by the context-independence property [18] linking attack relations between arguments across the boundary of knowledge bases.

The example also indicates that attack relations of knowledge bases with the same rule-based system should be considered together. This motivates the introduction of the attack relation assignment in Definitions 14, 15.

Definition 14

Let $\mathcal{R} = (RS,RD,\preceq )$ be a rule-based system. The class consisting of all consistent knowledge bases of the form $(\mathcal{R},BE)$ is denoted by $\mathcal{C}_\mathcal{R}$.

A rule-based system $\mathcal R$ is said to be sensible iff the set $\mathcal{C}_\mathcal{R}$ is not empty. From now on, whenever we mention a rule-based system, we mean a sensible one.

Definition 15

(Attack Relation Assignment) An attack relation assignment atts for a rule-based system $\mathcal R$ is a function assigning to each knowledge base $K \in \mathcal{C}_\mathcal{R}$ an attack relation $atts(K) \subseteq AR_K \times AR_K$.

We next recall the context-independence property stating that the attack relation between two arguments depends only on the rules appearing in them and their preferences.

Definition 16

(Context-Independence) We say attack relation assignment atts for a rule-based system $\mathcal R$ satisfies the property of context-independence iff for any two knowledge bases $K, K' \in \mathcal{C}_\mathcal{R}$ and for any two arguments A, B from $\,AR_{K} \cap AR_{K'}\,$, it holds that $\,\,(A,B) \in atts(K)\,\,\,\, \text{ iff }\,\,\,\,(A,B) \in atts(K')$

The context-independence property is commonly accepted in many well-known argument-based systems like the assumption-based framework [8, 25], the ASPIC+ approach [35, 37].

We can now present a central result, the introduction of the regular attack relation assignments.

Definition 17

(Regular Attack Relation Assignments) An attack relation assignment atts for a rule-based system $\mathcal R$ is said to be regular iff it satisfies the property of context-independence and for each knowledge base $K \in \mathcal{C}_\mathcal{R}$, atts(K) is regular.

The set of all regular attack relation assignments for $\mathcal R$ is denoted by $RAA_\mathcal{R}$.

For attack relation assignments $atts, atts'$, define $atts \subseteq atts'$ iff $\forall K \in \mathcal{C}_\mathcal{R}$, $atts(K) \subseteq atts'(K)$.

5.4 Minimal Removal Intuition

A key purpose of introducing priorities between defeasible rules is to remove certain undesired attacks while keeping the set of removed attacks to a minimum. The following very simple example illustrates the idea.

Fig. 4.

Minimal removal

Example 8

Consider a knowledge base consisting of just four defeasible rules and four arguments $A, A_1, B, B_1$ as seen in Fig. 4. Without any preference between the rules, we have $A, A_1$ attack each other. Similarly $B, B_1$ attack each other.

Suppose that for whatever reason $d_3$ is strictly less preferred than $d_2$ (i.e. $d_3 \prec d_2$). The introduction of the preference $d_3 \prec d_2$ in essence means that the attack of $B_1$ against B should be removed, but it does not say anything about the other attacks. Hence they should be kept, i.e. the attacks that should be removed should be kept to a minimum.

Let $\mathcal R$ be a rule-based system and $K \in \mathcal{C}_\mathcal{R}$. The basic attack relation assignment for $\mathcal R$, denoted by Batts is defined by: $\forall K \in \mathcal{C}_\mathcal{R}$, $Batts(K) = \{(A,B) \,|\, A$ undercuts or rebuts B}. Further let atts be a regular attack relation assignment. From the strong subargument structure property, it is clear that $atts \subseteq Batts$. $\forall K \in \mathcal{C}_\mathcal{R}$, the set $Batts(K) \setminus atts(K)$ could be viewed as the set of attacks removed from Batts(K) due to the priorities between defeasible rules.

Combining the “minimal-removal intuition” with the concept of regular attack relation assignment suggests that the semantics of $\mathcal R$ should be captured by regular attack relations atts such that $\forall K \in \mathcal{C}_\mathcal{R}$, the set $Batts(K) \setminus atts(K)$ is minimal, or equivalently the set atts(K) is maximal. As we will see in the next section, such maximal attack relation assignment indeed exists.

6 The Upper Semilattice of Regular Attack Relation Assignments

6.1 Preliminaries: Semilattice

We introduce the concept of semilattice. A partial order⁴ $\le$ on a set S is a upper-semilattice (resp. lower-semilattice) [16] iff each subset of S has a supremum (resp. infimum) wrt $\le$. The supremum (resp. infimum) of a set $X \subseteq S$ of a upper (resp. lower) semilattice S is often denoted by $\sqcup X$ (resp. $\sqcap X$) and the upper (resp. lower) semilattice is often denoted as a triple $(S,\le ,\sqcup )$ (resp. $(S,\le ,\sqcap )$).

It follows immediately that each upper (resp. lower) semilattice S has an unique greatest (resp. least) element denoted by $\sqcup S$ (resp. $\sqcap S$).

6.2 Semilattice Structure of $RAA_\mathcal{R}$

From now on until the end of this section, we assume an arbitrary but fixed rule-based system $\mathcal{R} = (RS,RD,\preceq )$.

Let $\mathcal A$ be a non-empty set of attack relation assignments. Define $\sqcup \mathcal{A}$ by:

$\forall K \in {\mathcal{C}_\mathcal{R}}$:    $(\sqcup \mathcal{A})(K) \,=\, \bigcup \{\,atts(K)\,|\, atts \in \mathcal{A}\,\}$

The following simple lemma and theorem present a deep insight into the structure of regular attack assignments.

Lemma 3

Let $\mathcal A$ be a non-empty set of regular attack relation assignments. The $\,\sqcup \mathcal{A}\,$ is also regular.

Proof

(Sketch) The proof is not difficult though rather lengthy as we just need to check in a straightforward way for each regular property.    $\square$

It follows immediately.

Theorem 2

Suppose the set $RAA_\mathcal{R}$ of regular attack relation assignments is not empty. Then $(RAA_\mathcal{R}, \subseteq , \sqcup )$ is an upper semilattice.    $\square$

Definition 18

Suppose the set $RAA_\mathcal{R}$ of all regular attack relation assignments for $\mathcal R$ is not empty. The canonical attack relation assignment of $\mathcal R$ denoted by $\mathbf{Att_\mathcal{R}}$ is defined by: $\mathbf{Att_\mathcal{R}}\,=\, \sqcup RAA_\mathcal{R}$.

Even though in general, regular attack relation assignments (and hence the canonical one) may not exist (as the Example 9 below shows), they exist under natural conditions that we believe most practical rule-based systems satisfy, like the property of self-contradiction or closure under transposition or contraposition as proved in Theorem 3 below.

Example 9

Consider a rule-based system $\mathcal R$ consisting of $d_0:\, \Rightarrow a$ $d_1:\, \Rightarrow b$ $r:\,a \rightarrow \lnot b$ and $d_0 \prec d_1$. Suppose atts be a regular attack relation assignment for $\mathcal{C}_\mathcal{R}$. Let $K = (\mathcal{R},\emptyset )$. The arguments for K are given in Fig. 5. From the property of effective rebut, it is clear that $(A,B) \not \in att(K)$. Hence $atts(K) = \emptyset$. The inconsistency-resolving property is not satisfied by atts(K), contradicting the assumption that atts is regular. Therefore there exists no regular attack relation assignment for $\mathcal{C}_K$.

Fig. 5.

Non-existence of regular assignments

It turns out that a special type of attack relations, the normal attack relations introduced in [18] is regular if the rule-based systems is closed under transposition or contraposition or self-contradiction.

Let K be a knowledge base and $A, B \in AR_K$. We say that A normal-rebuts B (at X) iff A rebuts B (at X) and there is no defeasible rule $d \in ldr(A)$ such that $d \prec last(X)$.

The normal attack relation assignment [18] $atts_{nr}$ is defined by: For any knowledge base $K\in \mathcal{R}$ and any arguments $A, B \in AR_{K}$, $(A,B) \in atts_{nr}(K)$ if and only if A undercuts B or A normal-rebuts B.

We present below a central result.

Theorem 3

Suppose the rule-based system $\mathcal R$ satisfies the self-contradiction property. Then the normal attack relation assignment $atts_{nr}$ is regular and the canonical assignment $Att_\mathcal{R}$ exists and $atts_{nr}\,\subseteq \, Att_\mathcal{R}$.

Proof

(Sketch) From Theorem 2 and the definition of the canonical attack relation, we only need to show that $atts_{nr}$ is regular.

It is straightforward to show that for each $K \in \mathcal{C}_\mathcal{R}$, the attack relation $atts_{nr}(K)$ satisfies the properties of strong subargument structure, attack monotonicity, effective rebuts and link-orientation. Further it is also obvious that $atts_{nr}$ satisfies the context-independence property. Let $K \in \mathcal{C}_\mathcal{R}$. We show that $atts_{nr}(K)$ satisfies the inconsistency-resolving property. Let $S \subseteq AR_K$ s.t. S is inconsistent. Let $S'$ be the set of all basic defeasible subarguments of S and $S_0$ be a minimal inconsistent subset of $S'$. Let $A \in S_0$ s.t. last(A) is minimal (wrt $\prec$) in $\{last(X)\,|\, X \in S_0\}$. From the self-contradiction property, $cnl(S_0) \vdash \lnot hd(last(A))$. We could then construct an argument B such that B attacks A and all basic defeasible subarguments of B are subarguments of arguments in $S_0$.    $\square$.

It follows immediately

Lemma 4

Suppose the rule-based system $\mathcal R$ satisfies the self-contradiction property. For each $K \in \mathcal{C}_\mathcal{R}$ and all $A, B \in AR_K$ such that A rebuts B (at B) and $(A,B) \not \in Att_\mathcal{R}(K)$, there is $d \in ldr(A)$ such that $d \prec last(B)$.

Though the normal and canonical attack relations do not coincide in general, they are equivalent in the sense that they have identical sets of stable extensions.

Theorem 4

Suppose the rule-based system $\mathcal R$ satisfies the property of self-contradiction. Then for each $K \in \mathcal{C}_\mathcal{R}$, $E \subseteq AR_K$ is a stable extension wrt $atts_{nr}(K)$ iff E is a stable extension wrt $Att_\mathcal{R}(K)$.

Proof

(Sketch) We first show that for each $atts \in RAA_\mathcal{R}$, each stable extension of $(AR_K,atts(K))$ is also a stable extension of $(AR_K,atts_{nr}(K))$. Hence each stable extension of $(AR_K,Att_\mathcal{R}(K))$ is also stable extension of $(AR_K,atts_{nr}(K))$. The theorem follows then from Lemma 5 below.    $\square$

Lemma 5

Let $atts, atts'$ be regular attack relation assignments for $\mathcal R$ such that $atts \subseteq atts'$. Then

• 1. each stable extension of $(AR_K, atts(K))$ is a stable extension of $(AR_K,atts'(K))$; and

• 2. each stable extension of $(AR_K, atts(K))$ is a stable extension of $(AR_K,Att_\mathcal{R}(K))$.

Proof

(Sketch) (1) Let E be a stable extension of $(AR_K, atts(K))$. It is clear that E attacks each argument in $AR_K \setminus E$ wrt $atts'(K)$. If E is not conflict-free wrt $atts'(K)$, E is inconsistent (since both $atts, atts'$ have the same set of undercuts) and hence not conflict-free wrt atts(K) (a contradiction). Hence E is conflict-free (and hence stable) wrt $atts'(K)$. (2) Follows immediately from (1) and the definition of $Att_\mathcal{R}$.    $\square$

7 Credulous Cumulativity of Regular Semantics

A key property satisfied by many argument-based and non-argument-based approaches to reasoning with prioritized rules is the credulous cumulativity property [18] stating intuitively that if some beliefs in your belief set are confirmed in the reality then your belief set will not change because of it.

A set $S \subseteq \mathcal{L}$ is said to be a belief set of knowledge base K wrt an attack relation assignment atts iff there is a stable extension E of $(AR_{K},atts(K))$ such that $S = cnl(E)$.

Definition 19

(Credulous Cumulativity) We say attack relation assignment atts satisfies the property of credulous cumulativity for $\mathcal R$ if and only if for each $K \in \mathcal{C}_\mathcal{R}$, for each belief set S of K wrt atts and for each finite subset $\varOmega \subseteq S$ of domain literals, $K +\varOmega = (RS_K,RD_K,\prec _K, BE_K \cup \varOmega )$ belongs to $\mathcal{C}_\mathcal{R}$, and S is a belief set of $K +\varOmega$ wrt atts.

For an illustration, consider again Example 2. Suppose $\{D,P,T\}$ is a belief set of K. Then the property of credulous cumulativity dictates that $\{D,P,T\}$ is also a belief set of $K + \{P\} = (RS_K,RD_K,\prec _K, \{D,P\})$. We state now an important result of this paper.

Theorem 5

The credulous cumulativity property is satisfied by all regular attack relation assignments.

Proof

(Sketch) Let $atts \in RAA_\mathcal{R}$, $K \in \mathcal{C}_\mathcal{R}$ and E be a stable extension of $(AR_{K},atts(K))$, $S = cnl(E)$ and $\varOmega \subseteq S$ be a finite set of domain literals. Further let $K' = K + \varOmega$ and $E' = \{ X \in AR_{K'}\,|\, \exists Y \in E, AS \subseteq E \,s.t. \, cnl(AS) \subseteq \varOmega \,\text{ and } \, Y \in X \downarrow AS \,\}$. It is clear that $E \subseteq E'$ and $cnl(E) = cnl(E')$ and $BE \cup \varOmega \subseteq S$. We show that $E'$ is a stable extension of $(AR_{K'},att(K'))$ by showing that it is conflict-free and attacks each argument not belonging to it. The theorem follows from the fact that $cnl(E) = cnl(E')$.    $\square$

Attack relation assignments satisfying the credulous cumulativity property together with all other regular properties except the inconsistency resolving one are defined as ordinary attack relation assignments in [18]. Theorem 5 implies directly that regular attack relation assignments are ordinary.

8 The Lower SemiLattice Structure of Value-Based Semantics

The value-based approaches to argumentation [3, 7, 35–37] define the semantics of defeasible knowledge bases by first defining a preference relation between arguments and then using the preference relation to define attack relation between arguments. We show in this section that the preference relations between arguments have a lower semilattice structure and hence a least one that characterizes the common semantics.

We first introduce a new operator about a “structured intersection” of relations that is needed to characterize the structure of preference relations between arguments.

Any relation $R \subseteq X \times X$ over a set X could be decomposed into a disjoint union of a strict core, denoted by $R_{st}$ and symmetric core, denoted by $R_{sy}$ as follows: $R\,=\, R_{st}\,\cup \,R_{sy}$ where $R_{st} \,=\, \{ (a,b) \in R \,|\, (b,a) \not \in R\,\}$ and $R_{sy} \,=\, \{ (a,b) \in R \,|\, (b,a) \in R\,\}$.

For any relations $R, R' \subseteq X \times X$, we introduce a “strong intersection”-operator $R \, \sqcap \,R'$ by: $\,\,R \, \sqcap \,R' = \,\, (R_{st}\,\cap \,R'_{st}) \,\, \cup \,\,(R_{sy}\,\cap \,R'_{sy})$.

Further define a partial order $R\, \ll \, R'$ by: $R\, \ll \,R'$ iff $R_{st}\,\subseteq R'_{st}$ and $R_{sy}\,\subseteq R'_{sy}$.

Definition 20

An argument preference assignment (or ap-assigment for short) for a rule-based system $\mathcal R$ is a function $\varGamma$ assigning to each knowledge base $K \in \mathcal{C}_\mathcal{R}$, a relation $\sqsubseteq _{\varGamma ,K} \,\,\subseteq \,\, AR_K\times AR_K$ (whose strict core is $\sqsubset _{\varGamma ,K}$) representing a preference relation between arguments in $AR_K$ where strict arguments are not strictly less preferred than any other arguments.

Definition 21

Let $\varGamma$ an ap-assignment defined for $\mathcal R$. The attack relation assignment derived from $\varGamma$ and denoted by $\mathbf{atts_{\varGamma }}$, is defined by: For each $K \in \mathcal{C}_\mathcal{R}$ and all $A, B \in AR_K$, $\,\,(A,B) \in atts_{\varGamma }(K)$ iff A undercuts B or A rebuts B (at $B'$) and $A \not \sqsubset _{\varGamma ,K}B'$.

Definition 22

An ap-assignment $\varGamma$ is regular for $\mathcal R$ iff its derived attack relation assignment $atts_{\varGamma }$ is regular.

The set of all regular ap-assignments for $\mathcal R$ is denoted by $AP_\mathcal{R}$.

Notation 3

The “strong intersection”-operator is expanded for non-empty set $\mathcal P$ of ap-assignments and denoted by $\sqcap \mathcal{P}$ as follows: $(\sqcap \mathcal{P})(K) = \sqcap \{\varGamma (K)\,|\, \varGamma \in \mathcal{P}\}$.

For ap-assignments $\varGamma _0, \varGamma _1$, we write $\varGamma _0 \ll \varGamma _1$ iff for each $K \in \mathcal{C}_\mathcal{R}$, $\varGamma _0(K) \ll \varGamma _1(K)$.

It is easy to see that $\varGamma _0 \ll \varGamma _1$ implies $att_{\varGamma _1} \subseteq att_{\varGamma _0}$. The following lemma shows that the “strong intersection” forms an infimum operation for regular ap-assignments.

Lemma 6

Let $\mathcal P$ be a non-empty set of regular apr-assignments for $\mathcal R$. Then $\sqcap \mathcal{P}$ is regular.

Proof

(Sketch) It is not difficult to see that the equation $atts_{\sqcap \mathcal{P}} = \sqcup \{atts_{\varGamma }\,|\, \varGamma \in \mathcal{P}\}$ holds. The regularity of $\sqcap \mathcal{P}$ follows from lemma 3.    $\square$

It follows immediately from Lemma 6.

Theorem 6

If $AP_\mathcal{R}$ is non-empty then $(AP_\mathcal{R}, \ll , \sqcap )$ forms a lower semilattice with $\,\, CA_\mathcal{R} = \sqcap AP_\mathcal{R}\,\,$ being the least regular ap-assignment for $\mathcal R$ and is referred to as the canonical ap-assignment.    $\square$

9 Discussion and Conclusions

Regular properties interact. While the attack monotonicity and link-prientation properties propagate respectively the attack relations and non-attack relations within the boundary of a knowledge base, context-independence propagates the attack (and non-attack) relations across knowledge base boundaries.

A more liberal notion of unrestricted rebut where a basic defeasible argument could directly attack a non-basic defeasible argument is studied in [13, 14]. Intuitively an unrestricted rebut is a rebut against a set of defeasible rules without explicitly rebutting any individual rule in it. It would be interesting to see how this notion of rebut interacts with the regular properties.

It is often necessary to combine normative reasoning with causal and probabilistic reasoning in practical reasoning.

Example 10

(see [22]) John sues Henry for the damage caused to him when he drove off the road to avoid hitting Henry’s cow. John’s argument is:

J: Henry should pay for the damage because Henry is the owner of the cow and the cow caused the accident.

Henry counter-attacks by stating that,

$H_1$: John was negligent, for evidence at the accident site shows that John was driving fast.

$H_2$: The cow was mad and the madness of the cow should be viewed as a force-majeure.

John’s argument is based on a common norm (or law) that owners are responsible for the damages caused by their animals. Henry’s first argument is based on the causal relationship between John’s fast driving and the accident. Henry’s second argument is based on the legal concept of force-majeure and the probability of the event of a cow getting mad. Can John win the case?

The chance of John winning the case depends on how probable the judge considers Henry’s arguments. Suppose the judge dismisses the madness of the cow as improbable, then the probability of Henry’s second argument is 0. Therefore the chance for John to win depends on the probability of Henry’s first argument. Suppose the judge considers the probability that John was driving fast to be 0.4, then the probability for John’s argument to stand is 0.6, and John would win the case. However, if the judge considers the probability of the event “John’s driving fast” to be 0.7, then Henry would win the case because the probability for John’s argument to stand is 0.3 only.

Dung and Thang developed a probabilistic argumentation framework in [22] to model applications involving both causal and norm-based reasoning as illustrated in this example. Other works include [30, 31, 33].