Rationality and maximal consistent sets for a fragment of ASPIC+ without undercut
Abstract
Structured argumentation formalisms, such as
Clearly, for a formal model of defeasible reasoning it is important to understand for which range of parameters the formalism (a) displays a behavior that adheres to common standards of consistency, logical closure and logical relevance and (b) can be adequately described in terms of other well-known forms of knowledge representation.
In this paper we answer this question positively for a fragment of
1.Introduction
Structured argumentation is a family of formal approaches for the handling of defeasible and potentially inconsistent information. For this, many models of structured argumentation distinguish between strict and defeasible inference rules. Defeasible rules guarantee the truth of their conclusion only provisionally: from the antecedents of the rules we can infer their conclusion unless and until we encounter convincing counter-arguments. These defeasible rules can come in varying strengths. For example, in an epistemic reasoning context considerations of plausibility, typicality or likelihood may play a role in determining the strength of a defeasible conditional. In contexts of normative reasoning (such as legal or moral reasoning), the strength of defeasible conditionals may be determined by deontic or legal urgency (e.g., in view of the authority which issued them or their specificity). Strict rules, in contrast, are beyond doubt and therefore considered maximally strong: the truth of the antecedents is carried over to the conclusion.
Arguments constructed on the basis of a combination of strict and defeasible rules can be in conflict with one another. For example, one argument may conclude the contrary of the conclusion of another argument or may conclude that the application of a defeasible rule in another argument is not warranted in the circumstances under consideration. To represent and resolve such conflicts, a formal argumentation framework is constructed on the basis of the strict and defeasible rules. Argumentative attacks represent conflicts between arguments. Preferences over the defeasible rules used in constructing the arguments can be used to resolve conflicts between assumptions by turning attacks into defeats. There are several design choices available when specifying how to construct such an argumentation framework, which often have a severe impact on the inferential behaviour of the resulting formalism. In this paper, we study one specific formalism known as
Example 1.
Nicki and Mary will go to a garden party (g) and were asked to bring a potato-salad.11 In Nicki’s opinion a good potato-salad has pickles in it (
In [1 ,19] several rationality postulates have been proposed, which can be seen as minimal requirements any well-behaved structured argumentation formalism should fulfill. These requirements all have to do with the basic role of formal argumentation as a formalism for handling (logical) conflicts. For instance, we can require that the output of the formalism is logically consistent: it should not be possible to derive both a formula and its contrary. As an illustration, in Example 1 no structured argumentation formalism should output both that pickles should be added (p) and kept out (
However, as has been observed in [57],
So far, there are not many results that establish Crash-Resistance and Non-Interference for
[57] established non-interference for complete semantics for ASPIC-lite, a sub-system of
In [36] a system with restricted rebut is introduced that avoids logical explosion by using a sub-classical logic as a base logic. For any completeness-based semantics a weakened version of Non-Interference and Closure are shown for total pre-orders expressing priority relations between the defeasible rules. For multi-extension semantics a counter-example for full non-interference is provided.
Recently
In conclusion, there have been some recent steps towards rational, prioritised structured argumentation with defeasible rules, but it is still an open question whether it is possible to obtain a formalism that satisfies the four rationality postulates for a multi-state semantics and prioritised defeasible rules. In this paper, we show that this is possible given some basic restrictions on the language of the knowledge base, using the weakest link lifting for a fragment of
Moreover, we demonstrate that when these resctrictions are met, the stable and the preferred semantics coincide. This result is interesting from a computational perspective, since it means we can now use the computationally less demanding proof theories for admissible semantics to show membership of a stable extension [31].
For several systems of structured argumentation characterizations of the extensions of frameworks under some argumentation semantics in terms of maximal consistent sets of premises have been obtained (see [6] for an overview). Such results are useful since they provide a link between argumentation and knowledge representation and they provide a basic sanity check on the behavior of an argumentation system. For systems with defeasible rules, such as
Outline of this paper: In Section 2, we present the necessary preliminaries on the structured argumentation formalism
2.Structured argumentation
In structured argumentation, information is given in the form of a knowledge base or argumentation system. In
Strict rules can have several classes of interesting instantiations. A first option is to use some logic L with an associated consequence relation
Unlike strict rules, a defeasible rule warrants the truth of its conclusion only provisionally: its application can be retracted in case counter-arguments are encountered. We assume that the defeasible rules
Definition 1
Definition 1(Argumentation System).
An Argumentation System (AS) is a tuple
(1) a formal language
(2) a set of strict rules
(3) a set of defeasible rules
(5) a naming function for the defeasible rules
(6) a contrariness function
The naming function n will be important when considering the attack form undercut and the preorder ⩽ is important when considering different strengths of arguments (see Definition 4). Below we will sometimes consider argumentation systems without undercut and/or without priorities, in which case we omit n and/or ⩽ from the characterizing tuple.77
Example 2
Example 2(Example 1 continued).
To illustrate the above definitions, we illustrate how to capture the information from Example 1 in an argumentation system
2.1.Argument construction
In structured argumentation systems like
Definition 2.
Let
(1)
(2)
(3)
By
Example 3
Example 3(Example 2 continued).
The following arguments (among others) can be constructed from
2.2.Attack and defeat
In
Definition 3.
Let
a rebuts b iff
a undercuts b iff
To determine which rebuts result in a defeat we take into account the priorities over the rules used in constructing the arguments involved in the attack. For this we have to lift the order ⩽ over the defeasible rules
Exactly how the preference order ⪯ is taken into account when determining whether an attack is successful and results in a defeat depends on the nature of the attack that is being considered. When it comes to rebuttal, we follow [50] in assuming that a rebutting attack by argument a on argument b leads to defeat if a is not strictly weaker than b. Since in this paper we only work with total orders, this is equivalent to requiring that a is at least as strong as b. Concerning undercuts, the situation is a bit more complicated, as there is some debate as to what it means for an undercutter to be sufficiently strong for the attack to succeed. Are undercutting attacks successful independently of the strength of the arguments involved? Or should an undercutting attack by a on b lead to defeat only in case a is not strictly weaker (or even strictly stronger) than b? [50] works with a preference-independent notion of undercutting defeat according to which undercutting attacks always give rise to defeat. Their motivation, however, has been questioned by [10].1414 In Definition 5 we follow what is the most frequent approach in the ASPIC-family, namely to assume that undercutting attacks are preference-independent. However, since our main results concern ASPIC-frameworks without undercut this choice is insignificant for this study.
Definition 4.
Where
We are now ready to define defeat based on the weakest link lifting:
We define the argumentation framework based on an argumentation system
Example 4
Example 4(Example 3 continued).
For the argumentation system
Given an argumentation framework consisting of arguments and defeats between these arguments, Dung [29] provides various semantics for determining the acceptability status of an argument in the framework, which we introduce in the next section.
2.3.Argumentation semantics
A Dung-style abstract argumentation framework (in short, AF) is a pair
Definition 6
Definition 6(Extensions).
Let
Example 5
Example 5(Example 4 continued).
The argumentation framework
Based on these argumentation semantics, we define consequence relations:
Definition 7.
Where
3.Rationality postulates
The inferential behaviour of structured argumentation formalisms is often studied using so-called rationality postulates [19,20]. These properties ensure that argumentation-based inferences make sense from a logical and intuitive point of view.
In order to handle conflicts adequately, a minimal constraint on structured argumentation systems is that they do not allow for direct logical conflicts in any extension (selected according to some semantics
Postulate 1
Postulate 1(Direct Consistency).
The related (but stronger) postulate of indirect consistency requires not only that an extension does not contain two arguments that are in direct conflict, but requires that no conflict is derivable using the strict rules
Definition 8
Definition 8(R
Let
Fact 1.
Given a set of inference rules
Definition 9
Definition 9(S
Where
Postulate 2
Postulate 2(Indirect Consistency).
A third postulate is related to the interpretation of strict rules → as being truth preserving. Recall that a rule
Postulate 3
Postulate 3(Closure).
Fact 2.
Direct consistency together with closure imply indirect consistency.
In [20] the property of Non-Interference was defined. Roughly speaking, a formalism is non-interferent if syntactically disjoint sets of formulas do not influence each others consequences. In more detail, when
To give precise meaning to the notion of syntactic disjointedness (a crucial concept in the formulation of non-interference) we let
Definition 10.
Two argumentation systems
Definition 11.
Two argumentation systems,
Furthermore, given
Postulate 4
Postulate 4(Non-Interference).
Non-Interference2020 is satisfied for a semantics
Postulate 5
Postulate 5(Strict Non-Interference).
Strict Non-Interference is satisfied for a semantics
As explained above, a violation of non-interference means that syntactically disjoint knowledge bases influence each other’s outcomes. We will first use the grounded extension to illustrate a violation of non-interference using a simplification of the argumentation system from Example 2.
Example 6.
Suppose now we move to the knowledge base
This gives rise to the following framework:
We see that since 
whereas 
.
To solve problems of this nature, [57,58] proposed to filter out inconsistent arguments like b. Indeed, if we restrict our attention to consistent arguments, a is unattacked and non-interference is satisfied for
When looking back at Example 6, it seems that some of these shortcomings can be overcome for preferred and stable semantics. In fact, when considering the preferred extensions of
Example 7.
We have (among others) the following arguments:
We get the following argumentation framework:
Notice that in this argumentation framework, argument a is not in the unique preferred extension ∅, even though it is syntactically independent from all the other defeasible rules. In other words, a is part of the unique preferred extension in
The problem in the above example can be avoided by filtering out the inconsistent d: in that case a will have no attacker and thus will be in the unique preferred extension.
In the following we will show that when omitting undercut from an
4.Results
We now present our meta-theoretic results. In this section we only consider argumentation frameworks without undercut attacks.
4.1.Preferred and stable semantics coincide
Our first result is that preferred and stable extensions coincide when
S1 | If Δ, |
S2 | If |
Often,
Fact 3.
If
Proof.
Suppose γ is a theorem of
Theorem 1.
For any
This result ensures that one can use dialectical proof theories for membership of an admissible extension (see e.g. [49]) to show that an argument belongs to a stable extension.
Checking whether an argument is contained in an admissible extension tends to be less demanding than checking if it is part of a stable extension [28], since the former requires us only to consider arguments that attack the argument in question, whereas the latter requires us to find a set that contains the argument in question and attacks every argument not in the set.2626 However, it should be remarked that both checking whether an argument belongs to an admissible or a stable extension are in the worst case intractable [31].2727
In the context of deductive argumentation with defeasible premises, results like Theorem 1 are well-known and are often strengthened by showing that the maximally conflict-free extensions (also called naive extensions) coincide with the preferred and stable extensions (see e.g. [9,37]).2828 However, even for argumentation systems with the trivial prefence relation
Example 8.
Let
4.2.Rationality postulates
The four rationality standards hold for both preferred and stable semantics (which coincide as shown in Theorem 1). The following theorem was shown for a slightly different setting in [53],2929 and is proven in Appendix C.1:
Theorem 2.
Non-interference holds for strict rule bases that are uniform:3030
Definition 12.
A rule set
Non-Interference for
Theorem 3.
In particular, this means that an argumentation system that is induced by classical logic satisfies non-interference. In more detail, we say that
Fact 4.
Where
Given the uniformity of classical logic, Theorem 3 immediately implies the non-interference of any argumentation system induced by classical logic.
Theorem 4.
Strict Non-Interference holds for systems with sets of strict rules that satisfy
Theorem 5.
The reader may wonder why
From the perspective of the argumentative rationality postulates,
Example 9.
Notice that c attacks but does not defeat d since
Example 10.
Where
This results in the following argumentation graph
This argumentation graph has the unique preferred extension ∅ and no stable extensions. Also, while r is in the grounded resp. in every preferred extension of
4.2.1.A note on symmetric contraries
The reader might at this point be suspicious that the results above admit counter-examples in view of argumentation systems with assymetric contraries. For example, the following example seems at first sight to contradict Theorem 1:3131
Example 11.
Let
Notice that b defeats a and itself. Hence there is no stable extension while the unique preferred extension is ∅, thus
However, the above example does not constitute a counterexample to Theorem 1, since in fact
Fact 5.
If
Proof.
Suppose that
4.3.Characterization using maximally consistent sets
In this section we show that the preferred and stable semantics can be characterized in terms of maximally consistent sets of defeasible rules. Similar results have been proven for a multitude of formalisms for deductive argumentation with defeasible assumptions, for example for deductive argumentation based on classical logic [4,5,22,35], or on arbitrary Tarskian logics [2], sequent-based argumentation [7,8,13] or assumption-based argumentation [37,38]. However, to the best of our knowledge, such results have not been established for argumentation with defeasible rules. We start with non-prioritized framework in Section 4.3.1 and then move to the prioritized case in Section 4.3.2.
4.3.1.The non-prioritized case
We first present a simple but flawed idea of how to characterize argumentation extensions by means of maximal consistent sets of defeasible rules which we call naive rule maximizing. For this we first define what it means for a set of defeasible rules in
Where the context disambiguates, we simply write
Definition 14.
Where
Where the context disambiguates, we will simply speak of (in)consistent sets Δ. In particular, for the following result we assume a fixed argumentation system
According to naive rule maximizing we collect as many defeasible rules as is consistently possible. Let for this
Example 12.
Let
Then
The problem with the set
Definition 15.
Where
As before we will reduce clutter whenever the context disambiguates and simply say that r is triggered by Δ, talk of trigger sets of r and denote
Fact 6.
Where
Proof.
For the right-to-left direction suppose there are
Example 13.
Suppose, where
By contraposition, also
Definition 16.
Where the context disambiguates, we will omit the superscript and simply write
Example 14
Example 14(Example 12 cont.).
We have
There is indeed a very close relationship between the set
Definition 17.
Where
Our main result for non-prioritized argumentation can then be stated as follows:
Theorem 6.
For any
There are two open question which we will address in the remainder of this section: (a) can the grounded semantics respectively (b) can the extensions of frameworks constructed on the basis of prioritized defeasible rule bases be represented in a similar way?
We start with a negative result concerning question (a). One may expect that the grounded extension can be characterized by
Example 15
Example 15(Example 6 continued).
Recall
What we see in the example is contaminating behavior by the inconsistent argument
Definition 18.
Let
Indeed, once we filter out inconsistent arguments we can characterize also the grounded semantics. First we note a minor complication, namely, generally it does not hold that
Example 16.
In the Appendix (Lemma 6) we show that there is a unique ⊂-maximal
Definition 19.
We call the unique ⊆-maximal
The set
Theorem 7.
Where
Naturally, the question arises whether for preferred and stable semantics the filtering of inconsistent arguments changes the extensions. The answer is no:
Theorem 8.
For any
4.3.2.The prioritized case
We now move to prioritized frameworks. Stable and preferred extensions can be characterized by selecting a subset of
Definition 20.
An R-consistent set Δ is a consistent set that “dominates” every set Θ that is inconsistent with it in the sense that we can always find a subset
In order to avoid clutter we will again talk about R-consistent sets and write
In the appendix we show that, as expected, the set of maximally R-consistent sets is exactly the set of all maximally consistent set that are R-consistent (Proposition 1).
Example 17
Example 17(Example 2 continued).
We consider a slight modification of
We have one set of rules that is maximally R-consistent:
Maximal R-consistency can be used to characterize preferred and stable semantics, both for frameworks with and without consistent arguments.
Theorem 9.
Where
Our final question is whether we can characterize the grounded semantics in a similar way as in Theorem 7 also for the prioritized setting. The answer is negative, as the following example illustrates.
Example 18.
Consider
This gives rise to the following argumentation framework:
We have
5.Related work
As pointed out in the introduction, work on simultaneous satisfaction of all rationality postulates for members of the ASPIC-family is rather limited. The postulates of consistency and closure, on the other hand, have been more extensively investigated. They were first introduced in [1,19] and were subsequently proven for
CPE Every formula ϕ has a contradictory ψ (so
Unlike [50], in the setting of this paper we did not suppose CPE, i.e., the existence of contradictories. Note, however, that
CTE For every formula ϕ,
It will not surprise the reader that there is a close connection between the Cpos resp. Cpos⋆ and requirement
Fact 7.
Cpos implies
Proof.
Assume Δ,
Fact 8.
Cpos⋆ and CPE imply
Proof.
Suppose Δ,
Fact 9.
Cpos⋆ implies
Proof.
Assume Δ,
In particular, the requirement of Facts 7–9 hold if for all formulas ϕ all members of
Interestingly, even given CPE, we can easily find counter-examples to rationality postulates such as Consistency for frameworks satisfying Cpos (and similarly for Tpos).
Example 19.
Consider
Note that p is merely a contrary, not a contradictory of q, while
Note that we have no defeats between a and b and so the only preferred, stable and grounded extension will include both arguments. Nevertheless, this extension is not consistent since the conclusions p and q are not consistent given that
Note that while
The example also shows that
To see that neither Cpos, Cpos⋆, nor Tpos implies
As Example 19 shows, only relying on Cpos (or Tpos) in combination with CPE does not suffice to get rationality postulates, such as Consistency. What is proposed in addition in [50] is to treat rebut defeats where the concluding formula of the attacking argument is a contrary (so not a contrapositive) of the conclusion of the attacked argument different from those rebuts with contradictory conclusions. While the latter case works as our Definition 5, in the former case argument strength is disregarded and any attack results in a defeat. While this move secures the standard rationality postulates (except for non-interference), it leads to what may be considered as counterintuitive behavior nevertheless. We give some examples.
Example 20
Example 20(Problems with “contrary-rebut”).
In all example below we treat
Interference 1. Suppose
Interference 2. In this example we will again add rules to a given
Cumulativity lite. Suppose an argument a with conclusion ϕ and strength n (so
and suppose p has as a contraryThis results in the framework to the left:
So a and
In order to avoid this kind of behavior we stuck in this paper to a uniform treatment of defeat where argument strength is considered for both rebuts, those with contrary and those with contradictory attacking formulas.
[30] goes beyond transposition and contraposition by formulating a condition called the self-contradiction axiom, which is implied by both transposition and contraposition. This self-contradiction axiom requires of an argumentation system
In this paper, we characterized the extensions of frameworks under some argumentation semantics in terms of maximal consistent sets of premises. As mentioned above, for structured argumentation with defeasible premises, such results are well-studied, see e.g. [6]. In contrast, for structured argumentation with defeasible rules such results were, to the best of our knowledge, not yet available. A series of different but related results are presented in [3], where structured argumentation formalisms allowing for reasoning with defeasible rules are studied. This paper studies the exact effects of various conditions on both the attack relation and the output of structured argumentation formalisms on the behaviour of various argumentation semantics. For example, it is shown for a conflict-dependent attack relation (which says that if a attacks b, then
Although the results in [3] are similar in spirit to some of the results obtained in this paper, the set-up is quite different. While we obtain results for a specific system, [3] takes a reverse-engineering approach by studying requirements for structured argumentation formalisms that warrant desired results. Finally, in [3] priorities over the defeasible rules are not studied and arguments are assumed to be consistent and minimal, which is not required in the present study.
In [59 ,60]
6.Concluding discussion and outlook
The main contributions of this paper can be summarized as follows:
6.1.Assumption-based argumentation
Besides the ASPIC-family, another popular approach to structured argumentation is assumption-based argumentation [12]. As the name suggests, it provides a formal model of reasoning with strict rules and defeasible assumptions. In contrast to ASPIC, it does not allow for the chaining of defeasible inference rules.4040 Another major difference between these two formalisms is that in ABA, nodes in argumentation graphs consist of sets of defeasible assumptions, as opposed to structured arguments in the form of proof trees for a specific conclusion in
Formally, a prioritised ABA system
Several results have indicated a strong connection between assumption-based argumentation and reasoning with maximally consistent subsets for both non-prioritized [37,43] and prioritized assumption-based systems [40,42]. Theorem 9 generalizes such insights to settings where defeasible inferences can be chained. This result thus shows that ABA and
6.2.Outlook and further work
One limitation of this work is that the rationality postulates and the correspondence with maximally consistent sets have only been proven for argumentation systems without undercutting attacks, without defeasible premises and only for systems with totally ordered sets of defeasible rules. E.g., concerning undercut, Examples like 7 lead to interferent behaviour. Similarly, it is a challenge to generalize our results to non-total orders and to incorporate defeasible premises which may be incomparable in strength to some of the defeasible rules, in such a way that the rationality postulates are satisfied. This will be a topic for future work.
Furthermore, in this contribution we only considered the weakest link lifting. Our results do not cover another popular lifting for
Example 21
Example 21(Inspired by Example 6.7 in [57]).
In this example we use the democratic last link lifting, which says that an argument
It can be seen that the unique preferred extension only contains strict arguments and arguments with the defeasible rule
It is interesting to note that
Notes
1 The notation used in this example will be properly introduced in Section 2.
2 In the context of
3 For structured argumentation systems with defeasible premises (but without defeasible rules), on the other hand, the situation looks a lot better, see e.g. [9,27,37].
4 Note that
5
6 A preorder is a binary relation that is reflexive and transitive.
7 More precisely, when omitting ⩽ we consider the preorder
8 We use subscripts to refer to the numbers of our examples.
9 In the examples that follow, we shall denote with
10 In all the examples that follow where
11 In this paper we will for the sake of simplicity omit several features of the original
12 We note that
13 Some works [21,39,41] have studied forms of unrestricted rebut where the conclusion of the attacked argument need not be the head of a defeasible rule.
14 A preference-dependent notion of undercutting attack was for example also used by [11] in the context of deontic logic, with the aim of modelling a cautious, ‘austere’ style of reasoning.
15 Unlike [50], in our contribution we do not distinguish between defeats with contrary formulas from those with contradictory formulas. See a justification of our approach in the context of a richer discussion in Section 5.
16 [50,53] distinguish between rebuts where
17 Dung [29] showed that for every AF
18 In [41, Example 6.1] one finds an example of a violation of the related postulate of crash-resistance that is caused by an inadequate treatment of incomparable priorities instead of inconsistencies.
19 Notice that this notion of syntactic disjointedness would have to be more explicitly spelled out when generalizing the results of this paper to a first order language. For an example of how to do this, cf. [27, Notation 3].
20 A related rationality standard is Crash-Resistance. It follows from Non-Interference under some very weak criteria on the strict rule base (cf. [20]).
21 We here phrase Non-Interference in terms of the semantics rather than in terms of the nonmonotonic entailment. In the setting of this paper, the latter formulation is a direct corollary of our formulation.
22 Another recently proposed strategy to obtain non-interference for prioritized settings with the grounded semantics is to use a generalized non-restricted form of rebut [41].
23 [58] observes that filtering out inconsistent arguments does not work when using the last link lifting. Unfortunately, even though we show that for a wide class of frameworks filtering out inconsistent arguments is unnecessary, these results do not generalize to the last link lifting either, as we show in Example 21.
24 In Section 5 we give a detailed comparison between these assumptions and other definitions of contaposition found in the literature.
25 Note, however, that the requirement is non-trivial even in cases where
26 A similar observation has been made in [28], where it is shown that stable and preferred semantics coincide for deductive argumentation with defeasible premises.
27 To give substance to the intuition that checking membership of an admissible extension is less demanding than checking membership of a stable extension, it might be interesting to compare proof theories for these problems (see e.g. [49]) using criteria proposed to compare efficiency or computational demands of proof theories as proposed in e.g. [23,26].
28 This is not necessarily so in logic/sequent-based argumentation for specific choices of attack-forms as shown in [7].
29 In Section 5 we give a detailed comparison of the setting of [53] and the assumptions made in this paper.
30 Structural consequence relations
31 This example was suggested to us by a reviewer.
32 We use the same ⊢ symbol in both Definitions 8 and 13: note, however, that its usage is disambiguated by the nature of the subscript and the nature of its left side, which is either a set of rules and a set of
33 This is the core mechanism behind constrained input-output logics [48].
34 In [39,41] an alternative solution to the problem of contamination is investigated that does not require to filter out inconsistent arguments but is instead based on a generalized notion of rebut attack.
35 This is the formulation from [50] while [19,53] only require “…then for some
36 Suppose
37 A similar example as Example 9 can be used to show that a weaker version of Cpos⋆ which only demands “for some
38 We use this term in order to indicate that the addition of “irrelevant” information leads to contaminating effects (see also [14]). “Irrelevance” is disambiguated differently in the two versions considered.
39 On the most general level, [30] assumes that an argumentation system is built on the basis of an abstract logic
40 Although it has been shown in [43] that, at least when preferences are not taken into account, ABA admits
41 We compare here
42 For simplicity we suppose here that our defeasible rules are ranked.
Acknowledgements
We would like to thank the anonymous reviewers of this manuscript for useful comments. The research of Jesse Heyninck was supported by the the FCT project RIVER (PTDC/CCI-COM/30952/2017), NOVA LINCS (UID/CEC/04516/2013) and the German National Science Foundation under the DFG-project CAR (Conditional Argumentative Reasoning) KE-1413/11-1.
Appendices
Appendix
AppendixProofs
The order of appearance of results in these appendix does not necessarily mirror the order of the statements of these results in the paper but is primarily based on logical dependency.
In order to avoid clutter, we will in the following proofs often slightly abuse notation by using
Appendix B.
Appendix B.Representation in terms of maximal consistent sets
B.1.The flat case
In what follows we shall assume a fixed
Fact 10.
Where
Proof.
Suppose
Fact 11.
Where
Proof.
Suppose
Suppose
Fact 12.
Proof.
Let
Fact 13.
Where
Proof.
Consider a
Let
Fact 14.
Where
Proof.
Let
Fact 15.
Where
Proof.
Let
With some renumbering let
After some renumbering let
Altogether we can create a sequence
Fact 16.
Where
Proof.
Note that in our construction for each
“⊆”: Let
“⊇”: This holds trivially. □
Fact 17.
Where
Proof.
Let
The next result offers a Lindenbaum-like construction of maximal consistent sets of defeasible rules in
Lemma 1.
Where
Proof.
Let
We first show (inductively) that each
Note also that in view of the construction (and Fact 12)
Suppose now that Δ is not consistent. Thus there is a rule
Suppose Δ is not maximal consistent. Thus, there is a consistent
In the following, given some proof
Fact 18.
If
Proof.
Since
If
Suppose now that
If
If
Lemma 2.
Where
Proof.
Where
Lemma 3.
Where
Proof.
Let
The next fact follows since any defeater/attacker of a sub-argument of some argument a also defeats/attacks a.
Fact 19
Fact 19(Sub-Argument Closure).
Where
Fact 20.
Where
Proof.
Suppose
Lemma 4.
Where
Proof.
Suppose
Since
Since
Where
Lemma 5.
For every
Proof.
Suppose
Assume now that it is not maximal consistent. By Lemma 1, there is a maximal consistent
The following theorem follows immediately with Lemma 3 and Lemma 5.
Theorem 10.
Where
B.2.Grounded semantics for flat frameworks
We first show that the free set exists (see Def. 19).
Lemma 6.
Where
Proof.
Let
The following lemma shows that the free set in
Lemma 7.
Proof.
“⊇”: This follows since by its construction,
“⊆”: Assume for a contradiction that
Lemma 8.
For all
Proof.
Suppose
Lemma 9.
There is no
Proof.
Suppose some
Theorem 11.
Where
Proof.
“⊇”: Note that
“⊆”: By Lemma 9,
In view of Theorem 11 and Lemma 9 we have:
Corollary 1.
Where
B.3.The prioritized case
In what follows we assume a fixed
Fact 21.
Where
(1)
(2) if
We again provide a Lindenbaum-like construction for showing the existence of maximal R-consistent superset of R-consistent sets in
Lemma 10.
Where
Proof.
Suppose
We again let
(i) We first show (inductively) that each
(ii) In view of the construction (and Fact 12),
(iii) Our main work now is to show that each
For the inductive step we first consider a limit ordinal α. Suppose
We now consider a successor ordinal
Since
Let
By Fact 12,
Recall that
Assume now for a contradiction that
Since
This concludes our inductive argument that each
We still have to show that Δ is maximal R-consistent. Assume for a contradiction that there is an R-consistent
As expected, maximal R-consistent sets are maximal consistent.
Lemma 11.
Proof.
We show that an R-consistent set that is not maximally consistent cannot be maximally R-consistent. Suppose for this that
In fact, the maximal R-consistent sets are exactly those maximal consistent sets that are R-consistent:
Proposition 1.
Proof.
The left-to-right direction is Lemma 11. Suppose
We now investigate how maximal R-consistent sets are related to preferred and stable extensions.
Lemma 12.
Where
Proof.
By Lemma 11,
Suppose
Since
We will assume that our proof
Suppose now that
Suppose now that
Suppose first that
Suppose now that there is a
Note that
Fact 22.
If
Lemma 13.
Where
Proof.
Let
Definition 21.
Where
Fact 23.
If
Fact 24.
If
Proof.
Assume for a contradiction that
Fact 25.
If
Proof.
Consider an arbitrary
Lemma 14.
If
Proof.
Let
Clearly, there is a set of arguments
Let
Since
Let
Since Θ is R-inconsistent with
Lemma 15.
Where
Proof.
Let
Let
Lemma 16.
For every
Proof.
Suppose
Assume for a contradiction that Θ is not R-consistent. Thus by Fact 23, there is a
Since
So, Θ is R-consistent. Suppose it is not maximal R-consistent. Thus, by Lemma 10, there is a maximal R-consistent
Now we are in a position to prove Theorem 9:
Theorem 9.
For any
Appendix C.
Appendix C.Rationality postulates
C.1.Consistency and closure
The following corollary is a direct consequence of the characterization in terms of maximal consistent sets shown in Section B.
Corollary 2.
Where
C.2.Non-interference (Theorem 3)
In the following we assume that we have a uniform strict rule set
Fact 26.
If
Proof.
If
Lemma 17.
Where
Proof.
We first define
We show that
Note that this is sufficient to show that
(
(
Lemma 18.
If
Proof.
Suppose
We start with
For the inductive step consider some
Lemma 19.
Where
Proof.
Suppose
Proposition 2.
Proof.
“⊆”. Let
“⊇”. Let
Proposition 3.
Proof.
“⊆”. Suppose
Consider a
Since by Fact 12,
“⊇”. Suppose
Assume now that Θ is
Theorem 3.
Where
C.3.Strict non-interference (Theorem 5)
In the following we assume two argumentation systems
Lemma 20.
Where
(1)
(2) if
Proof.
Ad 2. Suppose
Ad 1. This follows immediately with Item 2. □
Lemma 21.
Where
Proof.
First note that by Fact 12,
Proposition 4.
Proof.
“⊆”. Let
“⊇”. Let
Proposition 5.
Proof.
“⊆”. Suppose
Assume
We first note that (b) is impossible since by Lemma 20 and since
Suppose thus (a). By Lemma 20,
“⊇”. Suppose
Suppose
Suppose (without loss of generality) case (a). By Lemma 20,
Theorem 5. Where
C.4.Cumulativity lite
Where
Definition 22
Definition 22(Cumulativity Lite.).
Where
Fact 27.
Fact 28.
If b defeats c then any
Proof.
Note that
Cumulativity Lite then follows immediately in view of the following lemma.
Lemma 22.
Proof.
Consider
Conflict-free. Assume for a contradiction that there are
Admissibilitiy. Suppose some
Consider
We first show that (⋆) if
Conflict-free. Clearly,
Admissibility. Suppose some
Maximality. Suppose there is a
Consider again a
References
[1] | L. Amgoud, Postulates for logic-based argumentation systems, International Journal of Approximate Reasoning 55: (9) ((2014) ), 2028–2048. doi:10.1016/j.ijar.2013.10.004. |
[2] | L. Amgoud and P. Besnard, Logical limits of abstract argumentation frameworks, Journal of Applied Non-Classical Logics 23: (3) ((2013) ), 229–267. doi:10.1080/11663081.2013.830381. |
[3] | L. Amgoud and P. Besnard, A formal characterization of the outcomes of rule-based argumentation systems, in: International Conference on Scalable Uncertainty Management, Springer, (2013) , pp. 78–91. doi:10.1007/978-3-642-40381-1_7. |
[4] | L. Amgoud and C. Cayrol, Inferring from inconsistency in preference-based argumentation frameworks, Journal of Automated Reasoning (2002), 125–169. doi:10.1023/A:1021603608656. |
[5] | L. Amgoud and S. Vesic, Handling inconsistency with preference-based argumentation, in: Scalable Uncertainty Management, A. Deshpande and A. Hunter, eds, Springer, (2010) , pp. 56–69. doi:10.1007/978-3-642-15951-0_11. |
[6] | O. Arieli, A. Borg and J. Heyninck, A review of the relations between logical argumentation and reasoning with maximal consistency, Annals of Mathematics and Artificial Intelligence (2019), 1–40. |
[7] | O. Arieli, A. Borg and C. Straßer, Reasoning with maximal consistency by argumentative approaches, Journal of Logic and Computation 28: (7) ((2018) ), 1523–1563, ISSN 0955-792X. doi:10.1093/logcom/exy027. |
[8] | O. Arieli, A. Borg and C. Straßer, Prioritized sequent-based argumentation, in: Proc. AAMAS’18, ACM, (2018) , pp. 1105–1113. |
[9] | O. Arieli and C. Straßer, Sequent-based logical argumentation, Journal of Argument and Computation 6: (1) ((2015) ), 73–99. doi:10.1080/19462166.2014.1002536. |
[10] | P. Baroni, M. Giacomin and G. Guida, On the notion of strength in argumentation: Overcoming the epistemic/practical dichotomy, in: Proceedings of the 2001 ECSQARU Workshop: Adventures in Argumentation Toulouse, France, (2001) , pp. 1–8. |
[11] | M. Beirlaen, J. Heyninck and C. Straßer, Structured argumentation with prioritized conditional obligations and permissions, Journal of Logic and Computation 29: (2) ((2018) ), 187–214. doi:10.1093/logcom/exy005. |
[12] | A. Bondarenko, P.M. Dung, R.A. Kowalski and F. Toni, An abstract, argumentation-theoretic approach to default reasoning, Artificial intelligence 93: (1–2) ((1997) ), 63–101. doi:10.1016/S0004-3702(97)00015-5. |
[13] | A. Borg, Equipping sequent-based argumentation with defeasible assumptions, in: Computational Models of Argument: Proceedings of COMMA 2018, Frontiers in Artificial Intelligence and Applications, Vol. 305: , IOS Press, (2018) . |
[14] | A. Borg and C. Straßer, Relevance in structured argumentation, in: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, (2018) . |
[15] | G. Brewka, Preferred subtheories: An extended logical framework for default reasoning, in: International Joint Conference on Artificial Intelligence, Vol. 89: , (1989) , pp. 1043–1048. |
[16] | G. Brewka, Adding priorities and specificity to default logic, in: European Workshop on Logics in Artificial Intelligence, Springer, (1994) , pp. 247–260. doi:10.1007/BFb0021977. |
[17] | M. Caminada, Dialogues and HY-arguments, in: 10th International Workshop on Non-Monotonic Reasoning, (2004) , pp. 94–99. |
[18] | M. Caminada, Rationality postulates: Applying argumentation theory for non-monotonic reasoning, in: Handbook of Formal Argumentation, College Publications, (2018) . |
[19] | M. Caminada and L. Amgoud, On the evaluation of argumentation formalisms, Artificial Intelligence 171: ((2007) ), 286–310. doi:10.1016/j.artint.2007.02.003. |
[20] | M. Caminada, W.A. Carnielli and P.E. Dunne, Semi-stable semantics, Journal of Logic and Computation 22: (5) ((2012) ), 1207–1254. doi:10.1093/logcom/exr033. |
[21] | M.W.A. Caminada, S. Modgil and N. Oren, Preferences and unrestricted rebut, Computational Models of Argument (2014). |
[22] | C. Cayrol, On the relation between argumentation and non-monotonic coherence-based entailment, in: International Joint Conference on Artificial Intelligence, Morgan Kaufmann, (1995) , pp. 1443–1448. |
[23] | S.A. Cook and R.A. Reckhow, The relative efficiency of propositional proof systems, The Journal of Symbolic Logic 44: (1) ((1979) ), 36–50. doi:10.2307/2273702. |
[24] | K. Cyras, C. Schulz, F. Toni and X. Fan, 2017, Assumption-based argumentation: Disputes, explanations, preferences. |
[25] | K. Cyras and F. Toni, ABA+: Assumption-based argumentation with preferences, in: Fifteenth International Conference on the Principles of Knowledge Representation and Reasoning, (2016) . |
[26] | M. d’Agostino, Analytic inference and the informational meaning of the logical operators, Logique et Analyse (2014), 407–437. |
[27] | M. D’Agostino and S. Modgil, Classical logic, argument and dialectic, Artificial Intelligence 262: ((2018) ), 15–51. doi:10.1016/j.artint.2018.05.003. |
[28] | M. D’Agostino and S. Modgil, A study of argumentative characterisations of preferred subtheories, in: IJCAI, (2018) , pp. 1788–1794. |
[29] | P.M. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artificial Intelligence 77: ((1995) ), 321–358. doi:10.1016/0004-3702(94)00041-X. |
[30] | P.M. Dung and P.M. Thang, Closure and consistency in logic-associated argumentation, Journal of Artificial Intelligence Research 49: ((2014) ), 79–109. doi:10.1613/jair.4107. |
[31] | P.E. Dunne and M. Wooldridge, Complexity of abstract argumentation, in: Argumentation in Artificial Intelligence, Springer, (2009) , pp. 85–104. doi:10.1007/978-0-387-98197-0_5. |
[32] | S. Dyrkolbotn, T. Pedersen and J. Broersen, On elitist lifting and consistency in structured argumentation, Journal of Applied Logics – IfCoLog Journal of Logics and their Applications 5: (3) ((2018) ), 709–745. |
[33] | D.M. Gabbay, Theoretical foundations for non-monotonic reasoning in expert systems, in: Logics and Models of Concurrent Systems, Springer, (1985) , pp. 439–457. doi:10.1007/978-3-642-82453-1_15. |
[34] | H. Geffner and J. Pearl, Conditional entailment: Bridging two approaches to default reasoning, Artificial Intelligence 53: (2–3) ((1992) ), 209–244. doi:10.1016/0004-3702(92)90071-5. |
[35] | N. Gorogiannis and A. Hunter, Instantiating abstract argumentation with classical logic arguments: Postulates and properties, Artificial Intelligence 175: (9–10) ((2011) ), 1479–1497. doi:10.1016/j.artint.2010.12.003. |
[36] | D. Grooters and H. Prakken, Two aspects of relevance in structured argumentation: Minimality and paraconsistency, Journal of Artificial Intelligence Research 56: ((2016) ), 197–245. doi:10.1613/jair.5058. |
[37] | J. Heyninck and O. Arieli, On the semantics of simple contrapositive assumption-based argumentation frameworks, in: Computational Models of Argument: Proceedings of COMMA 2018, Frontiers in Artificial Intelligence and Applications, Vol. 305: , IOS Press, (2018) . |
[38] | J. Heyninck and O. Arieli, Simple contrapositive assumption-based frameworks, in: International Conference on Logic Programming and Nonmonotonic Reasoning, Springer, (2019) , pp. 75–88. doi:10.1007/978-3-030-20528-7_7. |
[39] | J. Heyninck and C. Straßer, Revisiting unrestricted rebut and preferences in structured argumentation, in: Proceedings of the 26th International Joint Conference on Artificial Intelligence, AAAI Press, (2017) , pp. 1088–1092. |
[40] | J. Heyninck and C. Straßer, A comparative study of assumption-based approaches to reasoning with priorities, in: Second Chinese Conference on Logic and Argumentation, (2018) . |
[41] | J. Heyninck and C. Straßer, A fully rational argumentation system for preordered defeasible rules, in: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, International Foundation for Autonomous Agents and Multiagent Systems, (2019) , pp. 1704–1712. |
[42] | J. Heyninck and C. Straßer, A comparative study of assumption-based approaches to reasoning with priorities, Journal of Applied Logics – IfColog Journal of Logics and their Applications (2019). |
[43] | J. Heyninck and C. Straßer, Relations between assumption-based approaches in nonmonotonic logic and formal argumentation, 2016, preprint arXiv:1604.00162. |
[44] | J. Heyninck, C. Straßer and P. Pardo, Assumption-based approaches to reasoning with priorities, in: Proceedings of the 1st Workshop on Advances in Argumentation in Artificial Intelligence, Ceur Workshop Proceedings, (2017) , pp. 58–72. |
[45] | S. Kraus, D. Lehmann and M. Magidor, Nonmonotonic reasoning, preferential models and cumulative logics, Artificial Intelligence 44: (1–2) ((1990) ), 167–207. doi:10.1016/0004-3702(90)90101-5. |
[46] | Z. Li, N. Oren and S. Parsons, On the links between argumentation-based reasoning and nonmonotonic reasoning, in: Theory and Applications of Formal Argumentation, E. Black, S. Modgil and N. Oren, eds, Springer International Publishing, Cham, (2018) , pp. 67–85. doi:10.1007/978-3-319-75553-3_5. |
[47] | D. Makinson, Bridges from Classical to Nonmonotonic Logic, College Publications, (2005) . |
[48] | D. Makinson and L. Van Der Torre, Input/output logics, Journal of philosophical logic 29: (4) ((2000) ), 383–408. doi:10.1023/A:1004748624537. |
[49] | S. Modgil and M. Caminada, Proof theories and algorithms for abstract argumentation frameworks, in: Argumentation in Artificial Intelligence, Springer, (2009) , pp. 105–129. doi:10.1007/978-0-387-98197-0_6. |
[50] | S. Modgil and H. Prakken, A general account of argumentation with preferences, Artificial Intelligence 195: ((2013) ), 361–397. doi:10.1016/j.artint.2012.10.008. |
[51] | S. Modgil and H. Prakken, Abstract rule-based argumentation, Handbook of Formal Argumentation 1: ((2018) ), 286. |
[52] | J. Müller and A. Hunter, An argumentation-based approach for decision making, in: 2012 IEEE 24th International Conference on Tools with Artificial Intelligence, Vol. 1: , IEEE, (2012) , pp. 564–571. doi:10.1109/ICTAI.2012.82. |
[53] | H. Prakken, An abstract framework for argumentation with structured arguments, Argument and Computation 1: (2) ((2010) ), 93–124. doi:10.1080/19462160903564592. |
[54] | H. Prakken, Formalising a legal opinion on a legislative proposal in the ASPIC+ framework, in: JURIX, Vol. 2012: , (2012) , pp. 119–128. |
[55] | H. Prakken, D. Ionita and R. Wieringa, Risk assessment as an argumentation game, in: International Workshop on Computational Logic in Multi-Agent Systems, Springer, (2013) , pp. 357–373. |
[56] | A. Urquhart, Basic many-valued logic, in: Handbook of Philosophical Logic, Handbook of Philosophical Logic, Springer, (2001) , pp. 249–295. doi:10.1007/978-94-017-0452-6_4. |
[57] | Y. Wu, Between argument and conclusion. Argument-based approaches to discussion, inference and uncertainty, PhD thesis, Universite Du Luxembourg, 2012. |
[58] | Y. Wu and M. Podlaszewski, Implementing crash-resistance and non-interference in logic-based argumentation, Journal of Logic and Computation 25: (2) ((2015) ), 303–333. doi:10.1093/logcom/exu017. |
[59] | A.P. Young, S. Modgil and O. Rodrigues, Prioritised default logic as rational argumentation, in: Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, International Foundation for Autonomous Agents and Multiagent Systems, (2016) , pp. 626–634. |
[60] | A.P. Young, S. Modgil and O. Rodrigues, Prioritised default logic as argumentation with partial order default priorities, 2016, preprint arXiv:1609.05224. |
