A novel argumentation semantics of defeasible logic programs (DeLP) is presented. Our goal is to build a semantics, which respects existing semantics and intuitions of “classical” logic programming. Generalized logic programs (GLP) are selected as an appropriate formalism for studying both undermining and rebutting. Our argumentation semantics is based on a notion of conflict resolution strategy (CRS), in order to achieve an extended flexibility and generality. Our argumentation semantics is defined in the frame of assumption-based framework (ABF), which enables a unified view on different non-monotonic formalisms. We present an embedding of DeLP into an instance of ABF. Consequently, argumentation semantics defined for ABF are applicable to DeLP. Finally, DeLP with CRS is embedded into GLP. This transformation enables to commute argumentation semantics of a DeLP via semantics of the corresponding GLP.
Defeasible Logic Programs (DeLPs) [
Example 1. Brazil is the home team, and has a key player injured. Home teams tend to work the hardest, and who works the hardest usually wins. The team who has a key player injured does not usually win. The program is formalized into the DeLP: ! home r1 : home ) works_hard r2 : works_hard ) wins ! key _player _injured
r3 : key _player _injured ) not wins
In the program from Example 1 there are two strict and three defeasible rules. The strict rules are facts, hence home and key _player _injured should always be true. Based on the first fact we are able to derive that Brazil should win, using the two defeasible rules r1 and r2, while based on the second fact we are able to derive that Brazil should not win, again relying on a defeasible rule, in this case r3. Hence there is a conflict which somehow should be resolved.
Various approaches to DeLP typically rely on argumentation theory in order to determine which rules should be upheld and which should be defeated. However, as it can be perceived from Example 1, it is not always immediately apparent how this should be decided.
According to García and Simari [
Some approaches, like ASPIC+, allow to specify a preference relation on rules. In such a case conflict resolution may take this into account. Specifically, ASPIC+ has two built-in conflict resolution strategies, weakest-link principle by which the rule with smallest preference is defeated among those involved in each conflict, and last-link principle by which only the rules immediately causing the conflict are considered and the least preferred is defeated.
We observe that more ways to resolve conflicts may be needed. This is due to the fact that defeasible rules are domain specific, a different conflict resolution strategy may be needed for a different domain, or in distinct application. We therefore argue that the conflict resolution strategy should be a user-specified parameter of the framework, and any DeLP framework should allow a generic way how to specify it (alongside some predefined strategies).
Some of the semantics proposed for DeLP satisfy the well accepted rationality
properties for defeasible reasoning, such as consistency (extensions should be
conflict-free) and closure (extensions should be closed w.r.t. the strict rules),
as defined by Caminada and Amgoud [
In our previous work [
All proofs can be found in a technical report which appears at http:// kedrigern.dcs.fmph.uniba.sk/reports/download.php?id=58. 2
Generalized logic programs and assumption-based frameworks provide a background for our investigation. We are aiming at a computation of our argumentation semantics of DeLP in the frame of classical logic programs. Generalized logic programs (with default negations in the heads of rules) are selected as a simplest LP-formalism, which enables to consider both undermining and rebutting.
Assumption-based frameworks are used in our paper as a basis for building a semantics of DeLP. ABF is a general and powerful formalism providing a unified view on different non-monotonic formalisms using argumentation semantics. 2.1
We will consider propositional generalized logic programs (GLPs) in this paper.
Let At be a set of atoms and not At = fnot A j A 2 At g be a set of default literals. A literal is an atom or a default literal. The set of all literals is denoted by LAt . If L = not A and A 2 At , then by not L we denote A. If S LAt , then not S = fnot A j A 2 S g.
A rule over LAt is an expression r of the form L1; : : : ; Ln ! L0 where 0 n and Li 2 LAt for each 0 i n. The literal head (r ) = L0 is called the head of r and the set of literals body (r ) = fL1; : : : ; Lng is called the body of r .
A generalized logic program is a finite set of rules. We will often use only the term program. If At is the set of all atoms used in a program P, it is said that P is over At . If heads of all rules of a program P are atoms, it is said that P is normal. A program P is called positive if the head of every rule is an atom and the body of every rule is a set of atoms or propositional constants t; u; f .
Note that a GLP P can be viewed as consisting of two parts, a normal logic program P+ = fr 2 P j head (r ) 2 At g (also called the positive part of P) and a set of “constraints” P = P n P+ (also called the negative part of P).
Our definitions of some basic semantic notions follow the ideas of
Przymusinski [
sistent, if it does not contain a pair A; not A where A 2 At . A partial interpretation is a consistent set of literals. A total interpretation is a partial interpretation
Each interpretation can be viewed as a mapping I : At 7! f0; 21 ; 1g where I (A) = 0 if not A 2 I , I (A) = 12 if A 62 I and not A 62 I , and I (A) = 1 if A 2 I . A valuation given by an interpretation I is a mapping ^I : LAt 7! f0; 12 ; 1g where ^I(A) = I (A) and ^I(not A) = 1 I (A) for each atom A 2 At , and ^I(t) = 1, ^I(u) = 12 , ^I(f ) = 0. An interpretation I satisfies a rule r (denoted I j= r ) iff ^I(head (r )) ^I(body (r )) = minf^I(L) j L 2 body (r )g.
Definition 2 (Model). An interpretation I is a model of a generalized logic program P iff I satisfies each rule in P.
As usual in logic programming, “classical” model, as defined above, are too broad and a number of more fine-grained semantics, based on certain notion of minimality are used. We proceed by defining these semantics summarily for GLPs. Not all of them were thoroughly investigated in literature, however we use analogy with other classes of logic programs, especially normal logic programs.
The notions of truth ordering and knowledge ordering on partial interpretations will be needed. For a partial interpretation I , let T (I ) = fA 2 At j I (A) = 1g and F (I ) = fA 2 At j I (A) = 0g.
pretations, then – I – I t J iff T (I ) k J iff T (I )
T (J ) and F (I ) T (J ) and F (I )
F (J ), F (J ).
Definition 4 (Program Reduct). Let I be an interpretation. The reduct of a normal logic program P is a positive logic program PI obtained from P by replacing in every rule of P all default literals which are true (resp. unknown, resp. false) in I by propositional constant t (resp. u, resp. f ).
Finally a fixed-point condition is expressed on a reduced program, which is formally captured by the operator P .
interpretation. By P (I ) we denote the t-least model of PI .
Definition 6 (Semantics Family for GLPs). Let P be a generalized logic program and I be a model of P. Then – I is a partial stable model of P iff P+ (I ) = I – I is a well-founded model of P iff I is a k-minimal partial stable model of P – I is a maximal stable model of P iff I is a k-maximal partial stable model of P – I is a least-undefined stable model of P iff I is a partial stable model of P with subset-minimal fA 2 At j I (A) = 12 g – I is a total stable model of P iff I is a partial stable model of P which is total
The produced semantics properly generalize existing semantics for normal logic programs.
Proposition 1. If P is a normal logic program, the notion of partial stable
model in Definition 6 coincides with the definition of partial stable models in [
tion 6 coincides with the definition of stable models in [
Assumption-based frameworks (ABF) [
An ABF is constructed over a deductive system. A deductive system is a pair (L; R) where L is a language and R is a set of inference rules over L. A language is a set L of all well-formed sentences. Each inference rule r over L is of the form '1; : : : ; 'n ! '0 where 0 n and 'i 2 L for each 0 i n. The sentence head (r ) = '0 is called the head of r and the set of sentences body (r ) = f'1; : : : ; 'ng is called the body of r .
A theory is a set S L of sentences. A sentence ' is an immediate consequence of a theory S iff there exists an inference rule r 2 R with head (r ) = ' and body (r ) S . A sentence ' is a consequence of a theory S iff there is a sequence '1; : : : ; 'n, 0 < n, of sentences such that ' = 'n and for each 0 < i n holds 'i 2 S or 'i is an immediate consequence of f'1; : : : ; 'i 1g. By CnR(S ) we denote the set of all consequences of S .
An assumption-based framework is a tuple F = (L; R; A; ) where (L; R) is a deductive system, A L is a set of assumptions, and : A 7! L is a mapping called contrariness function. We say that is the contrary of an assumption .
A context is a set A of assumptions. We say that is conflict-free iff f ; g * CnR( ) for each assumption . A context is closed iff = CnR( ) \ A, i.e., only such assumptions, which are members of , are derivable from . A context attacks an assumption iff 2 CnR( ). A context defends an assumption iff each closed context attacking contains an assumption attacked by .
ABFs enable to apply argumentation semantics to sets of assumptions and, consequently, subtle and rich semantic characterizations of sets of assumptions (and of their consequences) can be specified. A closed context is – attack-free iff does not attack an assumption in ; – admissible iff is attack-free and defends each assumption in ; – complete iff is admissible and contains all assumptions defended by ; – grounded iff is a subset-minimal complete context; – preferred iff is a subset-maximal admissible context; – semi-stable iff is a complete context such that [ f 2 A j attacks g is subset-maximal; – stable iff is attack-free and attacks each assumption which does not belong to . 3
Our knowledge can be divided according to its epistemological status into two
categories: on the one hand, one that is gained by deductively valid reasoning
and on the other hand, knowledge that is reached by defeasible reasoning [
The argumentation process usually consists of five steps [
Two kinds of arguments can usually be constructed in the language of defeasible logic programs. Default arguments correspond to default literals. Deductive arguments are constructed by chaining of rules.
We define several functions prems, rules and vuls denoting premises (i.e. default literals) and rules occurring in an argument. Intended meaning of vuls(A) is a set of vulnerabilities of an argument A (i.e., weak parts which can be defeated) consisting of premises and names of defeasible rules of an argument A. Definition 8 (Argument). Let P = (S; D; name) be a defeasible logic program. An argument A for a literal L is 1. a default argument L where L is a default literal.
prems(A) = fLg rules(A) = ; 2. a deductive argument [A1; : : : ; An L] where 0 an argument for a literal Li, and r = L1; : : : ; Ln n, each Ai, 0 < i
n, is prems(A) = prems(A1) [ rules(A) = rules(A1) [ [ prems(An) [ rules(An) [ fr g For both kinds of an argument A,
vuls(A) = prems(A) [ name(rules(A) \ D) Example 2. Consider a defeasible logic program consisting of the only defeasible rule r : not b ) a. Two default arguments A1 = [not a], A2 = [not b] and one deductive argument A3 = [A2 ) a] can be constructed. We can see that vuls(A1) = fnot ag, vuls(A2) = fnot bg, vuls(A3) = fnot b; not r g.
The difference between a default and a deductive argument for a literal not A
is in the policy of how the conflict is resolved. Syntactical conflict between
arguments is formalized in the following definition. As usual in the literature [
The first kind is called a rebutting conflict and the second kind is called an undermining conflict.
The previous definition just identifies the conflict, but does not say how to
resolve it; the notion of conflict resolution (to be formalized below) captures a
possible way to do so. In our paper, conflicts are not resolved through attack
between arguments as in [
Definition 10 (Conflict Resolution). Let P be a defeasible logic program. A conflict resolution is a tuple = (A; B ; V ) where C = (A; B ) is a conflict, A is an argument for not L, and V is a default literal – not L if C is an undermining conflict; or – name(r ) where r is a defeasible rule in rules(A)[rules(B ) if C is a rebutting conflict.
Let = (A; B ; V ) be a conflict resolution. The contrary of V is called the resolution of , and denoted by res( ). The set of vulnerabilities of , denoted by vuls( ), is defined as: vuls( ) = (vuls(A) [ vuls(B )) whenever V 2 vuls(A) \ vuls(B ) (vuls(A) [ vuls(B )) n fV g otherwise
Usually, there may be more ways how to resolve a conflict and a conflict resolution may resolve other conflicts as well, thus causing other conflict resolutions to be irrelevant or inapplicable. Intuitively, if all vulnerabilities in vuls( ) are undefeated (i.e. true), then in order to resolve the conflict in , the contrary res( ) of the chosen vulnerability in should be concluded (i.e. true). Notions of vuls( ) and res( ) will be used for definition of the argumentation semantics in the next subsection.
Example 3. Consider the defeasible logic program P = fnot a ! ag and undercutting arguments A = [not a] and B = [[not a] ! a]. Then = (A; B ; not a) is a conflict resolution with res( ) = a and vuls( ) = fnot ag. Please note that although not a has to be removed to resolve conflict between A and B , it remains a vulnerability of since not a is self-attacking.
Example 4. Consider the following defeasible logic program P r1 : ) a r2 : ) b a ! not c b ! c and arguments A = [[ ) a] ! not c] and B = [[ ) b] ! c]. The rebutting conflict (A; B ) can be resolved in two different ways, namely 1 = (A; B ; not r1) is a conflict resolution with res( ) = r1 and vuls( ) = fnot r2g, and 2 = (A; B ; not r2) is another conflict resolution with res( ) = r2 and vuls( ) = fnot r1g.
The previous example shows that there are more reasonable ways how to
resolve rebutting conflicts. We show two examples of different conflict
resolution strategies – the weakest-link and the last-link strategy inspired by ASPIC+
[
Example 5. Given the defeasible logic program r1 : ) b r2 : b ) a r3 : ) not a and the preference order r1 r3, r1 r2, r2
r3, deductive arguments are A1 = [ ) b]
A2 = [A1 ) a]
A3 = [ ) not a] Then R1 = f(A3; A2; not r3)g is the last-link strategy and R2 = f(A3; A2; not r1)g is the weakest-link strategy.
In the weakest-link strategy from Example 5, a non-last defeasible rule r1 is
used as a resolution of the conflict. Please note that in [
In the previous subsection, definition of an argument structure, conflicts identification and examples of various conflict resolutions were discussed. However, the status of literals and the actual semantics has not been stated.
Argumentation semantics for defeasible logic programs will be formalized
within ABF – a general framework, where several existing non-monotonic
formalisms have been embedded [
Definition 11 (Instantiation). Let P = (S; D; name) be a defeasible logic program built over the language LAt and R be a set of conflict resolutions. An assumption based framework respective to P and R is (L; R; A; ) where – L = LAt [ LN , – R = S [ fbody (r ) [ fname(r )g ! head (r ) j r 2 Dg [ fvuls( ) ! res( ) j
Rg, – A = not At [ not N , – not A = A for each atom A 2 At [ N . 2 Example 6. Consider the defeasible logic program P and the conflict resolution strategy R = f 1; 2g from Example 4. Assumption-based framework respective to P and R is following: – L = fa; not a; b; not b; c; not cg [ fr1; not r1; r2; not r2g – R = fb ! not c; a ! cg [ fnot r1 ! b; not r2 ! ag [ fnot r1 ! r2; not r2 ! r1g – A = fnot a; not b; not cg [ fnot r1; not r2g – not A = A for each A 2 fa; b; cg [ fr1; r2g
Now we define the actual semantics for defeasible logic programs. Given an ABF F = (L; R; A; ), by F + we denote its flattening – that is, F + is the ABF (L; fr 2 R j head (r ) 2= Ag; A; ).
Definition 12 (Extension). Let P = (S; D; name) be a defeasible logic program, R be a set of conflict resolutions, and F = (L; R; A; ) an assumptionbased framework respective to P and R. A set of literals E L is
F + with CnR(E ) E and CnR(E 0) E 0; 2. a grounded extension of P with respect to R iff E is a subset-minimal complete extension of P with respect to R; 3. a preferred extension of P with respect to R iff E is a subset-maximal complete extension of P with respect to R;
of P with respect to R with subset-minimal E 0 n E ;
with respect to R and E 0 = E . where E 0 = L n not E .
Example 7. Consider the assumption-based framework from Example 6. Then E1 = ;, E2 = fnot r1; r2; not a; b; not cg, and E3 = fr1; not r2; a; not b; cg are complete extensions of P with respect to R. Furthermore, E1 is the grounded extension and E2, E3 are preferred, semi-stable and stable extensions of P with respect to R. The argumentation semantics defined above allows us to deal with conflicting rules and to identify the extensions of a DeLP, given a CRS, and hence it constitutes a reference semantics. This semantics is comparable to existing argumentation-based semantics for DeLP, and, as we show below, it satisfies the expected desired properties of defeasible reasoning. In this section we investigate on the relation of the argumentation-based semantics and classical logic programming. As we show, an equivalent semantics can be obtained by transforming the DeLP and the given CRS into a classical logic program, and computing the respective class of models.
In fact the transformation that is required is essentially the same which we used to embed DeLPs with CRS into ABFs. The names of rules become new literals in the language, intuitively if name(r ) becomes true it means that the respective defeasible rule is defeated. By default name(r ) holds and so all defeasible rules can be used unless the program proves otherwise. The conflict resolution strategy R to be used is encoded by adding rules of the form vuls( ) ! res( ) for each conflict resolution 2 R, where the head of such rules is always an atom and the body is a set of default literals.
Formally the transformation is defined as follows: Definition 13 (Transformation). Let P = (S; D; name) be a defeasible logic program and R be a set of conflict resolutions. Transformation of P with respect to R into a generalized logic program, denoted as T (P; R), is defined as T (P; R) = S [ fbody (r ) [ fname(r )g ! head (r ) j r 2 Dg [
fvuls( ) ! res( ) j 2 Rg
Thanks to the transformation, we can now compute the semantics of each DeLP, relying on the semantics of generalized logic programs. Given a DeLP P and the assumed CRS R, the extensions of P w.r.t. R corresponds to the respective class of models. Complete extensions correspond to partial stable models, the grounded extension to the well-founded model, preferred extensions to maximal stable models, semi-stable extensions to least-undefined stable models, and stable extensions to total stable models.
Proposition 2. Let P be a defeasible logic program and R be a set of conflict resolutions. Then 1. E is a complete extension of P with respect to R iff E is a partial stable model of T (P; R).
A remarkable special case happens when the input program P does not contain defeasible rules, and hence it is a regular GLP. In such a case our argumentation-based semantics exactly corresponds to the respective class of models for the GLP. This shows complete backward compatibility of our semantics with the underlying class of logic programs.
Proposition 3. Let S be a generalized logic program and P = (S; ;; ;) a defeasible logic program with the empty set of conflict resolutions. Then 1. E is a complete extension of P iff E is a partial stable model of S.
model of S.
4
In this section we will have a look on desired properties for defeasible reasoning, and show that our semantics satisfies these properties. The properties are formulated in general, that is, they should be satisfied for any a defeasible logic program P, any set of conflict resolutions R, and any extension E of P w.r.t. R.
The first two properties formulated below are well known, they were
proposed by Caminada and Amgoud [
Property 1 (Closure). Let R0 = S [ fbody (r ) [ fname(r )g ! head (r ) j r 2 Dg. Then CnR0 (E ) E .
The consistency property [
Property 2 (Consistency). E is consistent.
In addition we propose two new desired properties which are concerned with handling of the default assumptions. Reasoning with default assumptions is a fixed part of the semantics of GLPs (and most other classes of logic programs), and therefore in DeLPs it should be governed by similar principles. The first property (dubbed positive defeat ) requires that for each default literal not A, this literal should be always defeated in any extension E such that there is a conflict resolution 2 R whose assumptions are all upheld by E ; and, in such a case the opposite literal A should be part of the extension E .
Property 3 (Positive Defeat). For each atom A 2 LN , if there exists a conflict resolution 2 R with res( ) = A and vuls( ) E then A 2 E .
The previous property handles all cases when there is an undefeated evidence against not A and requires that A should hold. The next property (dubbed negative defeat ) handles the opposite case. If there is no undefeated evidence against not A, in terms of a conflict resolution 2 R whose assumptions are all upheld by E , then not A should be part of the extension E .
Property 4 (Negative Defeat). For each default literal not A 2 LN , if for each conflict resolution 2 R with res( ) = A holds not vuls( ) \ E 6= ; then not A 2 E .
Closure and consistency trivially hold for our semantics, as the semantics was designed with these properties in mind. They are assured by the definition of complete extension of a DeLP (Definition 12).
respect to a set of conflict resolutions R has the property of closure.
respect to a set of conflict resolutions R is consistent.
Satisfaction of a positive and a negative defeat properties follow from the instantiation of an ABF (Definition 11), where an inference rule vuls( ) ! res( ) is added for every conflict resolution 2 R.
respect to a set of conflict resolutions R has the property of positive defeat.
respect to a set of conflict resolutions R has the property of negative defeat. 5
There are two well-known argumentation-based formalisms with defeasible
inference rules – defeasible logic programs [
Francesca Toni’s paper [
The paper [
Caminada et al. [
In this paper we investigated the question of how to define semantics for defeasible logic programs, which satisfies both the existing rationality postulates from the area of structured argumentation and is also aligned with LP semantics and intuitions. To achieve these objectives, we diverged from the usual argumentation process methodology. Most importantly, conflicts are not resolved by attacking some of the conflicting arguments, but by attacking some of the weak parts of an argument called vulnerabilities. Main contributions are as follows: – We presented an argumentation semantics of defeasible logic programs, based on conflict resolution strategies within assumption-based frameworks, whose semantics satisfies desired properties like consistency and closedness under the set of strict rules. – We constructed a transformational semantics, which takes a defeasible logic program and a conflict resolution strategy as an input, and generates a corresponding generalized logic program. As a consequence, a computation of argumentation semantics of DeLP in the frame of GLP is enabled. – Equivalence of a transformational and an argumentation semantics is provided.
This work resulted from the Slovak–Greek bilateral project “Multi-context Reasoning in Heterogeneous environments”, registered on the Slovak side under no. SK-GR-0070-11 with the APVV agency and co-financed by the Greek General Secretariat of Science and Technology and the European Union. It was further supported from the Slovak national VEGA project no. 1/1333/12. Martin Baláž and Martin Homola are also supported from APVV project no. APVV-0513-10.