On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning and Logic Programming

1. Introduction

Argumentation constitutes a major component of human's intelligence. The ability to engage in arguments is essential for humans to understand new problems, to perform scientific reasoning, to express, clarify and defend their opinions in their daily lives. The way humans argue is based on a very simple principle which is summarized succintly by an old saying "The one who has the last word laughs best". To illustrate this principle, let us take a look at an example [B 1 ], a mock argument between an Israeli and an Arab over who is responsible for blocking negotiation in Middle East.

Example Israeli: "Israel can not negotiate with the PLO because they don't even recognize Israel's right to exist"

Arab: "Israel doesn't recognize the PLO either"

The explicit content of the Israeli's utterance is that PLO's failure to recognize Israel blocks the negotiation. This establishes the responsibility of the PLO for blocking the negotiation by an implicit appeal to the following commonsense responsibility attribution rule: "If some actor performs some action which causes some state of affairs then that actor is responsible for that state of affairs unless its Bl,BFG,LS,Pl,THT,V]. In contrast, it is still not clear how to understand the acceptability of arguments. The lack of progress here leaves the question about the semantical relations between argumentation and the formal logic-based approaches to reasoning, especially nonmonotonic reasoning remaining open until today. This paper is devoted to study these problems.

Moore distinguished between default reasoning and autoepistemic reasoning [M]. According to him, default reasoning is drawing plausible inferences in the absence of information to the contrary while autoepistemic reasoning is like reasoning about one's own knowledge or beliefs. Thus default reasoning is like arguing with the Nature, where a conclusion, supported by some argument, can be drawn in the absence of any counterargument. On the other hand side, reasoning about one's own knowledge or beliefs is much like arguing with oneself. So both autoepistemic reasoning and default reasoning are forms of argumentation. This insight should not be very surprising as it may seem since all forms of reasoning with incomplete information rest on the simple intuitive idea that a defeasible statement can be believed only in the absence of any evidence to the contrary which is very much like the principle of argumentation. In [Dl], this idea has been applied to develop a simple and intuitive framework for semantics of logic programming unifying many other previously proposed approaches [GL,GRS,P3]. Later, Kakas, Kowalski and Tony [KKT] have pointed out that the framework given in [Dl] is in fact an argumentational approach to logic programming. This important insight constitutes a major source of inspiration and motivation for this paper.

This paper provides three novel results. The first one is a theory of acceptability of arguments which, in fact, is a formal account of the principle of argumentation. The second result shows that logic programming as well as many major formalisms to nonmonotonic and defeasible reasoning in AI and logic programming [R,M,MD,Pl,Dl,GL,KKT,SL] are argumentation systems. That means that all these systems are based on the same principle. They differ only by the structure of their arguments. The third result reveals that argumentation can be viewed as logic programming with negation as failure. This result introduces a general method for generating metainterpreters for argumentation systems, a method which is very much similar to the compiler-compiler idea in conventional programming.

2. A Theory of Acceptability of Arguments

Our theory is based on the notion of argumentation framework given in the following definition.

Definition 1 An argumentation framework is a pair AF = <AR, attacks> where AR is a set of arguments, and attacks ~AR x AR . ·

For two arguments A,B, the meaning of attacks(A,B) is that A represents an attack against B. For example, the exchange between the Israeli and the Arab in the introduction can be represented by an argumentation framework <AR,attacks> where AR = {11,12,A}, and attacks = {(II ,A),(A,Il ),(12,A)} with II ,I2 denoting the first and the second argument of the Israeli, respectively, and A denoting the argument of the Arab.

From now on, if not explicitly mentioned otherwise, we always refer to an arbitrary but fixed argumentation framework AF = <AR,attacks>.

A set S of arguments is said to be conflict-free if there are no two arguments A,B in S such that A attacks B or B attacks A.

For a rational agent G, an argument A is acceptable if G can defend A (from within his world) against all attacks on A. Further, it is reasonable to assume that a rational agent accepts an argument only if it is acceptable. That means that the set of all arguments accepted by a rational agent is a set of arguments which can defend itself against all attacks on it. This leads to the following definition of an admissible (for a rational agent) set of arguments.

Definition 2 (l) An argument A is acceptable wrt a setS of arguments iff for each argument B: if B attacks A then B is attacked by some argument in S.

(2) A conflict-free set of arguments S is admissible iff each argument in S is acceptable wrt S. ·

The (credulous) semantics of an argumentation framework is defined by the notion of preferred extension.

Definition 3 A preferred extension of an argumentation framework AF is a maximal (wrt set inclusion) admissible set of arguments of AF. ·

For example, the argumentation framework of the Arab-Israeli example has exactly one preferred extension E = {II ,12}.

The well-known Nixon diamond example [R] can be represented by an argumentation framework AF = <AR,attacks> with AR = {A,B}, and attacks = { (A,B),(B,A)} where A represents the argument "Nixon is anti-pacifist since he is a republican", and B represents the argument "Nixon is a pacifist since he is a quaker" . This argumentation framework has two preferred extensions, one in which Nixon is a pacifist and one in which Nixon is quaker.

Theorem 1 Let AF be an argumentation framework. Then

( 1) The set of all admissible sets of AF form a complete partial order wrt set inclusion.

(2) For each admissible setS of AF, there exists an preferred extension E of AF such that S ~ E.

(3) Every argumentation framework possesses at least one preferred extension. ·

To compare our approach with other approaches, we introduce the notion of stable extension.

Definition 4 A conflict-free set of arguments S is called a stable extension iff S attacks each argument which does not belong to S. ·

The relations between stable extension and preferred extension are clarified in the following lemma.

Lemma 1 Every stable extension is a preferred extension, but not vice versa. ·

It is not difficult to see that in both the Nixon diamond and the Arab-Israeli examples, preferred extension and stable extension semantics coincide.

Fixpoint Semantics and Grounded (Skeptical) Semantics

We show in the following paragraph that argumentation can be characterized by a fixpoint theory providing an elegant way to introduce grounded (skeptical) semantics.

Definition 5 The characteristic (unction of an argumentation framework AF = <AR,attacks>, denoted by FAF> is defined as follows: FAF: rR ~ rR where FA,(S) = {A I A is acceptable wrt S} ·

Lemma 2 (1) FA,(S) is conflict-free if Sis conflict-free. (2) S admissible iff Sis conflict-free and S ~ FA,(S). (3) FAF is monotonic (wrt set inclusion). ·

The skeptical semantic of an argumentation framework is defined by the following notion of grounded extension.

Definition 6 The grounded extension of an argumentation framework AF, denoted by GEAF> is the least [!Xed point of FAF' ·

Let AF be the argumentation framework of the Arab­ Israeli-example. Then FAF(<j>) = {I2}, FA/(<!>)= {11,12}, FA/(<!>)= FA/(<j>). Thus GEAF = {11,12}. Note that GEAF is also the only preferred extension of AF.

The following notion of complete extension provides the link between preferred extensions (credulous semantics), and grounded extension (skeptical semantics).

Definition 7 An admissible set of arguments S is called a complete extension iff each argument which is acceptable wrt

S, belongs to S. ·

Intuitively, the notion of complete extensions captures the kind of confident rational agents who believes in every thing he can defend.

It is easy to see that a conflict-free set of arguments E is a complete extension if and only if E is a fixpoint ofF AF·

Theorem 2 ( 1) Each preferred extension is a complete extension, but not vice versa.

(2) The grounded extension is the least (wrt set inclusion) complete extension.

( 3) The complete extensions form a complete semilattice 1 wrt set inclusion. ·

Having seen that, according to different intuitions, there are different semantics to argumentation, we are now interested in finding the conditions under which these different intuitions lead to the same semantics.

An argumentation framework is well-founded if there exists no infinite sequence Ao,A 1 , ... ,A., .. . such that for each i, Ai+J attacks Ai. An example for an well-founded argumentation framework is the Israeli-Arab example.

Theorem 3 Every well-founded argumentation framework has exactly one extension which is grounded, preferred and stable. ·

Now, we want to give a condition for the coincidence between stable extensions and preferred extensions. We say that an argument B potentially attacks A if there exists a finite sequence Ao, .. ,A2.+1 such that 1) A = Ao and B = A2n+J· and 2) for each i, OS:i!S:2n, Ai+J attacks Ai. Further, we say that an argument B indirectly defends A if there exists a finite sequence Ao ... ,A2· such that 1) A = Ao and B = A2 ·· and 2) for each i, OS:i<2n, Ai+J attacks Ai. An argument B is said to be controversial if there exists an argument A such that B both potentially attacks A and indirectly defends A. An argumentation framework is uncontroversial if none of its arguments is controversial. The Nixon diamond example is an example of an uncontroversial argumentation framework.

Theorem 4 Let AF be an uncontroversial argumentation framework. Then each preferred extension of AF is stable. ·

It follows immediately from the above theorem that every uncontroversial argumentation framework possesses at least one stable extension. This in fact gives the answer to an often asked question about the existence of stable semantics of knowledge representation formalisms like Reiter's default logic, logic programming or autoepistemic logic. Much works have been done to study this kind of questions [D2,K3,F,S,E] . The uncontroversity of argumentation frameworks is a generalization of the results given in these works.

3. Nonmonotonic Reasoning and Logic Programming as Argumentation

A number of different approaches to nonmonotonic reasoning have been proposed in AI [R,M2,MD,Pl,SL] which are very different at the first look. But it turns out that all of them are different forms of argumentation. Due to the lack of space, we only show in this chapter, that two of them, the Reiter's default logic, as representative of the extension-based approach [R,M2,MD] , and the Pollock's inductive defeasible logic, as representative of the argument­ based approach [Pl,SL,THT], are different forms of argumentations. Further we also show that logic programming is a form of argumentation.

Reiter's Default Logic As Argumentation

A default is an expression of the form (p:j 1 , . .. ,j/w) where p,j 1 , .. ,jk,w are closed first order sentences with p being called the premise, j 1 , ... jk the justifications and w the conclusion of the default. A default theory [R] is a pair (D,W) where D is a set of defaults and W is a set of closed first order sentences. A default theory is said to be consistent if W is consistent. A R-extension [R] of a default theory (D,W) is a closed first order theory E satisfying the following conditions: E = u{ W; I i is a natural number } where W0 = W, and W;+ 1 = Th(W;) u { w I 3(p:j1, ·· ,j/w) in D s.t. {j;} u E is consistent, and p e W; } with Th(W;) denoting the first order closure of the theory W;.

Let S be a set of defaults. The set of all justifications of defaults inS is denoted by Jus(S). A set K of justifications is said to be a support for a closed wff k wrt a default theory T=(D, W), denoted by T,K 1- k, if there is a sequence (e 0 ,e 1 , ··· ,en) with en= k such that for each e;, either e; e W or e; is a logical consequence of the preceding members in the sequence or e; is the conclusion w of a default (p:j 1' , ·· ,jk' /w) whose premise p is a preceding member in the sequence and whose justifications j 1' , ·· ,jk' belong to K.

For each default theory T = (D,W), the argumentation framework AF(T) = <AR.,.,attacksT> is defined by ART= { (K,k) I K ~jus(D): K is a minimal support fork wrt T}, and (K,k) attacksT (K',k') iff ...,k e K'.

For each first order theory S, and each set S' of arguments of AF(T), define arg(S) = { (K,k) e ART I Vj e K: (jJ uS is consistent}, andjlat(S') = { k I 3(K,k) e S'j It follows then

Theorem 5 LetT= (D, W) be a default theory. Let E be R­ extension ofT and E' be a stable extension of AF(T). Then

(1) arg(E) is a stable extension of AF(T)

(2)jlat(E') is a R-extension ofT. ·

The R-extension semantics of Reiter's default logic does not contain any information about the arguments supporting the beliefs. This can cause serious problem when a revision of the knowledge base is needed. Often, the systems turn out to be not cumulative [B2]. To fix this problem, it is necessary to design some mechanisms for keeping track of the arguments. Brewka [B2] has proposed a modification of Reiter's default logic where the justifications supporting a conclusion have to be considered together with the conclusion. In fact, Brewka's logic is very much similar to our argumentation frameworks AF(T). This suggests that it is meaningful and interesting to incorporate the idea of argumentation into nonmonotonic logic. The techniques developed in Gabbay's work [G] on labelled deductive systems may be useful here.

Pollock's Inductive Defeasible Logic as Grounded Argumentation

Given an argumentation framework .::;AR,attacks>, Pollock's theory of defeasible reasoning [PI] is based on a hierarchy of arguments defined as follows: 1) All arguments are level 0 argumenrs, and 2) An· argument is a levet n+ I argument iff it is not attacked by any level n argument. An argument is inde(easib.le iff there is an m such thaf for each; n>m~ the argument is a level n argument.

Let AR; denote the set of level i arguments.

It is clear that for each i, AR; = PIAF(AR;.1) where PIAF: 2AR ~ 2AR with PIAF(S) = { A I no argument in S attacks A }.

It is not difficult to see that FAF = PlAF o PlAF·

Let AR_1 = $, and AR;nf = u{ AR 2 ;. 1 I i;;::: 0 }, and GE be the grounded extension of AF.

The relations between Pollock's indefeasible arguments and our grounded extension semantics is illuminated in the theorem below.

Theorem 6 (I) For each i;;::O: <I> ~ AR 1 ~---~ AR2;.1 ~ ···

~ GE ~ ·--~ AR2; ~- --~ AR0 = AR

(2) An argument A is indefeasible iff A E ARinf

(3) AR;nt ~ GE ·

Logic Programming as Argumentation

A number of different approaches to semantics of logic programming has been proposed [Cl,Dl,GL,GRS,KM,P3]. But it turns out that all of them are different forms of argumentation. Due to the lack of space, we only show in this chapter, that two of them, the stable semantic [GL], and the well-founded semantic [GRS] correspond to the stable and grounded semantics, respectively, of argumentation frameworks gneralizing the results given in [D 1 ,KKT].

A logic program is a finite set of clauses of the form b 0 f-q, .. ,bm,...,bm+l····...,bm+n where b;'s are atoms. For a logic program P, Gp denotes the set of all ground instances of clauses in P.

A set of ground negative literals K is said to be a support for a ground atom k wrt P, denoted by P,K 1- k, if there is a sequence of ground atoms (e 0 , e 1 , ··· ,en) with en = k such that for each e;. either e;f- e Q, or e; is the head a clause e; f-~, .. ,ah,...,ah+l····...,ah+r in Gp such that the positive literals a 1 , ·· ,ah belong to the preceding members in the sequence and the negative literals ...,ah+l····...,~+r belong to K.

For each logic program P the argumentation framework AF(P) = <ARp.attacksp> is defined by ARp = { (K,k) I K is a minimal support for k wrt P}, and (K,k) attacksp (K',k') iff ...,k e K'.

The correspondence between the semantics of AF(P) and the semantics of P is showed in the following theorem.

Theorem 7 Let P be a logic program. Then

• (I) M is a stable model of P iff there is a stable extension E of AF(P) s.t. M = { k I 3(K,k) e E }.

(2) Let WFM be the well-founded model of P, and GE be the grounded extension of AF(P). Then WFM = u{ {kju K I (K,k) e GE }. ·

It is not difficult to see that if i> is call-consistent [D2,K3,S,F] then AF(P) is uncontroversial. It follows then immediately from theorems 4,7

Tli~rem g (I) The stable and preferred extension semantics of call-consistent logic· programs coincide.

1. There exists at least one stable model for each call-consistent logic program. ·

It is also easy to see that AF(P) is well-founded for locally stratified P. From this fact, it follows immediately the coincidence between stable and well-founded semantics of locally stratified logic programs, a well-known result in logic programming [P3].

4. Argumentation As Logic Programming: A Generator of Metainterpreters for Argumentation Systems

Any argumentation system is composed from two essential components: One for generating the arguments together with the attack-relationship between them. The other is for determining the acceptability of arguments. So we can think of an argumentation system as consisting of two units, an argument generation unit, AGU, and an argument processing unit, APU. The argument processing unit APU is in fact a very simple logic program consisting of the following two clauses:

• (Cl) acc(X) f- -,defeat( X)
• (C2) defeat(X) f- attack(Y,X),acc(Y)

where C2 means that an argument is defeated if it is attacked by an acceptable argument, and C I means that X is acceptable if it is not defeated (or equivalently, each clause which attacks X is defeated). The just described architecture of an argumentation system is illustrated by the following picture:

The following theorem shows the correctness of this architecture.

Theorem 9 Let AF=(AR,attacks) be an argumentation framework. Let P = APU + AGU = {CJ,C2} u {attacks(A,B)f-- I (A,B) e attacks}. Then

(1) E is a stable extension of AF iff ME is a stable model of P.

1. Eisa grounded extension of AF iff ME coincides with the set of all positive literals of the well-founded model ofP

where ME = {acc(A) I A E E} u {defeat(B) I B is attacked by some AeE} u {attacks(A,B)f-- I (A,B) e attacks}

·

The above architecture of argumentation systems is in fact a schema for generating metainterpreters for argumentation systems. In practice, to increase the efficiency of this metainterpreter, the well-developed techniques of partial evaluation and program transformation in logic programming should be applied.

Kowalski [K2] has pointed out that logic-based knowledge bases can be described by the equation "Knowledge Base = Knowledge + Logic". Logic-based knowledge bases can be viewed as argumentation systems where the knowledge is coded in the structure of the arguments and the logic is used to determine the acceptability of the arguments. In that sense, the above architecture of argument systems can be viewed as a schema for generating metainterpreters for knowledge bases.

Conclusions

The theory of argumentation frameworks proposed in this paper provides an unified foundation for the different approaches to knowledge representation and reasoning in AI, philosophy and logic programming. Therefore, our results can serve als the foundation for the development of knowledge representation formalisms capable of communicating knowledge among different knowledge representation systems. This is especially important in constructing large knowledge bases as such systems will require a sustained effort over a large geography by many teams which will be forced to use different knowledge representation languages in developing their subsystems since no single formalism to knowledge representation can satisfy all the "basic properties" of a knowledge base system[P2,K2] .

Our theory of argumentation in this paper considers only argumentation frameworks with one kind of conflicts between arguments. But there are often at least two kinds of conflicts between arguments in a real-world argumentation framework: Reductio Ad Absurdum conflict and the conflict between specific and more general knowledge [D3,PI,P2] . Hence, it is necessary to generalize the theory given in this paper to handle argumentation frameworks with more than one kinds of attacks between argumments. The semantics of such argumentation frameworks have been studied in [03] . Recently, a very interesting argumentation-based framework for nonmonotonic reasoning which can handle more than one kinds of conflicts has been developed by Bondarenko,Toni and Kowalski [BTK]. Still, more works need to be done to gain deeper insight into the nature of conflicts between arguments.

Acknowledgement

I am grateful to Bob Kowalski for his support, encouragement, and especially for the spiritful discussions with him which have been the major source of motivation and inspiration for me. Many thanks to Franchesca Tony and Kostas Stathis for their vital help with the literature. Thanks also to the anonymous referees for some constructive criticisms.

This paper has been partially supported by the Abduction Group at the Imperial College under a grant from Fujitsu.

Endnotes

A part i a l order (S ,:o;) i s a comp l e t e semilat tice iff e a ch nonempty s ubset o f S has a g l b and each i ncreas ing sequence of S has a lub.