Rationality and maximal consistent sets for a fragment of ASPIC+ without undercut
Structured argumentation formalisms, such as , offer a formal model of defeasible reasoning. Usually such formalisms are highly parametrized and modular in order to provide a unifying framework in which different forms of reasoning can be expressed. This generality comes at the price that, in their most general form, formalisms such as do not satisfy important rationality postulates, such as non-interference. Similarly, links to other forms of knowledge representation, such as reasoning with maximal consistent sets of rules, are insufficiently studied for although such links have been established for other, less complex forms of structured argumentation where defeasible rules are absent.
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 without the attack form undercut by showing that it satisfies all standard rationality postulates of structured argumentation under stable and preferred semantics and is adequate for reasoning with maximal consistent sets of defeasible rules. The study is general in that we do not impose any other requirements on the strict rules than to be contrapositable and propositional and in that we also consider priorities among defeasible rules, as long as they are ordered by a total preorder and lifted by weakest link. In this way we generalize previous similar results for other structured argumentation frameworks and so shed further light on the close relations between assumption-based argumentation and .
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 . is a well-established formalism which has been applied to e.g. decision-making , risk-assessment  and legal reasoning  and provides argumentative characterisations of prioritised default logic  (cf. [59,60]) and preferred subtheories  (cf. ).
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 () but Mary has an allergy to pickles (). Since an allergy for pickles has precedence over a preference in taste, the rule based on the former is stronger than the rule based on the latter (which we express in the formal language by having a subscript 2 for and a subscript 1 for ). Mary thinks they should bring a bottle of Quadruple beer as a gift for the host () since the host likes beers (l). Since this is a very strong beer, in most cases, when handing over the gift, a warning should be issued (). However, the host is a beer connoisseur (b), and thus the previous rule of thumb does not apply ().
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 () of the salad. In , it was proven that satisfies the rationality postulates of closure and consistency given some basic restrictions on the strict rule base.
However, as has been observed in , does not satisfy other standards such as Crash-Resistance and Non-Interference. Ideally, a reasoning system should not lose consequences if irrelevant information is added to the knowledge base. In Example 1, the fact that Mary and Nicki bring a beer (q) and warn the party host about the strength of the beer (w) should not be influenced by any considerations of what to put in the potato-salad (i.e. by adding to the knowledge base). As demonstrated in  for , the lack of Crash-Resistance and Non-Interference is especially threatening if the underlying strict rules are domain-independent. This is typically the case if the strict rules are induced by an underlying logic such as classical logic (in short, CL).22 Given an inconsistent knowledge base and strict rules such as logical explosion, for any formula an argument with a contrary conclusion can be constructed.
So far, there are not many results that establish Crash-Resistance and Non-Interference for and related systems.33 Some examples are:
 established non-interference for complete semantics for ASPIC-lite, a sub-system of where priorities over defeasible rules are not taken into account and inconsistent arguments are filtered out. The latter is arguably a limitation, since checking consistency can be computationally unfeasible and since the inconsistency is typically demonstrated dialectically in real-word argumentation .
In  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 [11,39,41] has been proposed. It is the first member of the ASPIC-family that satisfies all standard rationality postulates (including non-interference and crash-resistance) even when taking into account preorders over defeasible rules. does not require filtering out inconsistent arguments. However, the rationality postulates hold only for the single-state grounded semantics, as it makes use of the attack form of unrestricted rebut, which violates the rationality postulates of closure and indirect consistency for multi-extension semantics such as the preferred and stable semantics (see e.g. [18, Example 2]).
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 . In more detail, we consider without undercut, defeasible premises and undermining attacks and we assume the preference order over the defeasible rules to be total. We restrict our attention to propositional instantiations. As such, this paper presents an important move towards a full solution to an open problem mentioned both in  and . Furthermore, when these restrictions are met, it is not necessary to filter out inconsistent arguments, thus bringing the formalism closer to dialectical practices.
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 .
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  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 , such results have not been obtained. One difficulty is the question of how to define consistent subsets of the premises in such contexts. In this contribution we will generalize approaches that have been proposed in the context of knowledge bases with strict and defeasible assumptions such as default assumptions  and ABA  to systems with defeasible inference rules such as . In this way we obtain further insights into the relation of to other argumentation formalisms, thus tackling another open question formulated in .
Outline of this paper: In Section 2, we present the necessary preliminaries on the structured argumentation formalism . In Section 3 we review the rationality postulates for structured argumentation. Expert readers in formal argumentation may skip these sections and jump directly to Section 4, which contains the main contributions of this paper, namely: when considering (a fragment of) without undercut attacks, stable and preferred extensions coincide (Section 4.1), all four rationality postulates are satisfied for the stable and preferred semantics (Section 4.2) and central argumentation semantics are characterized in terms of maximally consistent sets of defeasible rules (Section 4.3). In Section 5 we discuss related work. In the final Section 6 we make some concluding remarks, pointing out a connection with assumption-based argumentation and setting out avenues for further work.
In structured argumentation, information is given in the form of a knowledge base or argumentation system. In , such an argumentation system is built up from a formal language , which can be used to formulate strict rules of the form , defeasible rules of the form and strict premises . Strict rules are deductive in the sense that the truth of their antecedents necessarily implies the truth of their consequent ϕ, while defeasible rules allow for exceptions. In arguments are modelled as derivations based on strict and defeasible rules and a set of premises.
Strict rules can have several classes of interesting instantiations. A first option is to use some logic L with an associated consequence relation and require that iff . Another option is to use what are often called domain dependent rules, as they are known from e.g. logic programming.
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 come with a naming function . Furthermore, conflicts between elements of the language can be specified using a contrariness function .44 Finally, the user can specify preferences over the defeasible rules using a preorder . Formally, such an argumentation system is defined as follows:
Definition 1(Argumentation System).
An Argumentation System (AS) is a tuple consisting of:
(1) a formal language based on a set of atoms ;
(2) a set of strict rules of the form (where );
(3) a set of defeasible rules of the form (where );
(5) a naming function for the defeasible rules ;
(6) a contrariness function from to ;
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 1 continued).
To illustrate the above definitions, we illustrate how to capture the information from Example 1 in an argumentation system where:88
In structured argumentation systems like , acceptable arguments are determined using the semantics of abstract argumentation. In order to apply these semantics, an argumentation graph has to be constructed on the basis of the argumentation system. This is done by building arguments using premises and inference rules and by specifying defeats between these arguments on the basis of the contrariness function and the preference order of the argumentation system. We first define how arguments are constructed.1111
Let be an argumentation system. An argument a is one of the following:
By we denote the set of arguments that can be built from . An argument a will be called defeasible if and strict otherwise.
Example 3(Example 2 continued).
The following arguments (among others) can be constructed from :
2.2.Attack and defeat
In there are two ways in which arguments can conflict. The first type of attack, called rebut, is when an argument a concludes the contrary of the conclusion of an argument b. The second attack type is called undercut and occurs when an argument concludes that the application of a defeasible rule is not appropriate in the context at hand. More formally, an undercut from a on b occurs when a has as a conclusion where .
Let and :
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 to a preference order ⪯ over the set of arguments constructed on the basis of . We will use the weakest link lifting (see e.g. ) according to which an argument is as strong as its weakest defeasible elements.
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  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?  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 .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.
Where , iff there is an such that for every , .
We are now ready to define defeat based on the weakest link lifting:
We define the argumentation framework based on an argumentation system as .
Example 4(Example 3 continued).
For the argumentation system , we have the following argumentation framework:
Given an argumentation framework consisting of arguments and defeats between these arguments, Dung  provides various semantics for determining the acceptability status of an argument in the framework, which we introduce in the next section.
A Dung-style abstract argumentation framework (in short, AF) is a pair where is a set of arguments and is a binary relation of attack. Relative to an AF, Dung defines a number of extensions – subsets of – on the basis of which we can evaluate the arguments in .
Let be an argumentation framework and :
iff there is some such that .
is conflict-free iff there are no for which .
defends an argument a iff for every such that then .
is a complete extension iff it is conflict-free and iff defends a.
is a preferred extension iff it is a set inclusion maximal complete extension.
is the grounded extension iff it is the set inclusion minimal complete extension.1717
is a stable extension iff it is conflict-free and for every , .
Example 5(Example 4 continued).
The argumentation framework has as grounded extension that contains , , , , , but not , , and . This extension is also the unique preferred extension. It is also stable as it attacks , , , , etc.
Based on these argumentation semantics, we define consequence relations:
Where and :
if for some , there is some with .
if for every , there is some with .
if there is some with .
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 ). In other words, any extension should be consistent, i.e. there should be no two arguments a and b in the extension such that .
Postulate 1(Direct Consistency).
satisfies Direct Consistency for an argumentation system if there is no such that there are some for which .
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 from the conclusions of the arguments in the extension. In other words, indirect consistency requires that the set of conclusions of arguments in a given extension is consistent when closed under the strict rule base .
Let be a set of -formulas and a set of inference rules on . An -proof of ϕ from Γ is a sequence where for each , or is the head of a rule in whose body only contains formulas in . We write iff there is an -derivation of ϕ based on Γ.
Given a set of inference rules , is monotonic, reflexive and transitive.
Where is a set of inference rules over , a set Γ of formulas in is -inconsistent iff for some such that and . Otherwise it is -consistent.
Postulate 2(Indirect Consistency).
satisfies Indirect Consistency for an argumentation system if for every , is -consistent.
A third postulate is related to the interpretation of strict rules → as being truth preserving. Recall that a rule means that whenever and … and are the case, ϕ is necessarily the case as well. This licenses us to require closure under strict rules of any extension. What this means is that, whenever arguments with conclusions are part of an extension (selected according to some semantics ) and is a strict rule we should find an argument for ϕ in that same extension as well.
satisfies Closure for an argumentation system if for every , whenever then .
Direct consistency together with closure imply indirect consistency.
In  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 and are two syntactically disjoint sets, a non-interferent system will allow one to infer ϕ from Γ iff ϕ is inferable from . A violation of non-interference thus means that syntactically disjoint knowledge bases influence each others outcomes. In most of the cases,1818 a violation of non-interference is caused by an inadequate handling of inconsistencies (see Example 6 for a simple illustration): one inconsistency in the knowledge base can cause the whole system to crash since it contaminates the argumentation framework (i.e. the conflict spreads to all arguments, even to arguments which are syntactically disjoint from the inconsistent argument). A system crashing as the effect of an inconsistency is bad news, since it renders the formalism ineffective in extracting useful information from the knowledge base.
To give precise meaning to the notion of syntactic disjointedness (a crucial concept in the formulation of non-interference) we let be the set of all atoms occurring in Δ (where Δ is a set of formulas and/or inference rules based on ). Two sets Δ and are syntactically disjoint iff . Finally, we define . We now define two notions of syntactic disjointedness for argumentations systems. The former (Definition 10) is intended to cover cases in which two argumentation systems share the same base logic, so cases in which the strict rules of both systems are induced by the same logical system. In contrast, Definition 11 is indented to cover cases in which two argumentation systems are based on domain-specific strict rules (see also Footnote 2).
Two argumentation systems and , based on the same strict rule set , are syntactically disjoint iff and are syntactically disjoint.1919
Two argumentation systems, and are strictly syntactically disjoint iff and are syntactically disjoint.
Furthermore, given and , we will denote the set of arguments that can be constructed on the basis of by .
Non-Interference2020 is satisfied for a semantics if for any two syntactically disjoint argumentation system and , where is -consistent, is such that ⩽  is the restriction of to , and , we have:21
Postulate 5(Strict Non-Interference).
Strict Non-Interference is satisfied for a semantics if for any two strictly syntactically disjoint argumentation systems and , where is such that ⩽  is the restriction of to , and , we have:
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.
where . Clearly the argument is in the grounded extension.
Suppose now we move to the knowledge base where . Informally, consists of supplemented with the syntactically disjoint rule base . We would expect to still have a in the grounded extension since we only added information that is irrelevant to q. However, this is not the case. To see this, notice we have, among others, the following arguments:
This gives rise to the following framework:
We see that since satisfies ex falso quodlibet, the contradiction between p and can be used to construct an argument for that attacks a. Since there is no unattacked argument that defends a from b, a is no longer in the grounded extension of . As such, non-interference is violated, 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 under the grounded extension. This is no coincidence since  showed that for any semantics subsumed by complete semantics and given an argumentation system with the trivial priority order , non-interference, closure and consistency are satisfied when inconsistent arguments are filtered out.  was the first work to investigate and solve the problem of interference.2222 However, it has been argued in  that filtering out inconsistent arguments might be problematic for several reasons. First, checking the consistency of an argument might be computationally intractable. For example, when the strict rules are based on propositional classical logic , checking consistency of an argument is NP-complete. Secondly,  give several reasons against the appropriateness of filtering out inconsistent arguments for modelling real-life argumentation. They observe that there are many examples of real-life argumentation where inconsistency of an argument is shown dialectically.2323
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 (which coincide with the stable extensions), namely and , we see that a is part of both of these extensions and thus there is no interference problem. In more detail, every preferred extension contains a defeater of b (i.e. respectively ) that defends a from the inconsistent argument b. Thus, the question can be raised: is it even necessary to filter out inconsistent arguments when using semantics like the preferred or stable semantics? For argumentation systems without any restrictions on the language, this question has to be answered negatively:
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 , while adding the rules , which are syntactically disjoint from , results in interferent behaviour.
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 framework, all rationality postulates hold for preferred and stable semantics when the strict rules allow for contraposition. For these semantics it is inconsequential whether inconsistent arguments are removed. Moreover, we characterize these semantics in terms of maximal consistent sets of defeasible rules.
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 is contrapositive, i.e., it satisfies the following two requirements:2424
If Δ, for some , then Δ, for some ; and
If for some , then .
Often, will simply follow from . More precisely, this is the case whenever has theorems. We say that is a theorem of iff .2525
If has theorems, then implies .
Suppose γ is a theorem of . Suppose Δ, . By the monotonicity of , γ, Δ, . By , there is a such that Δ, . Again by , Δ, and by the transitivity of , . □
For any where satisfies and , .
This result ensures that one can use dialectical proof theories for membership of an admissible extension (see e.g. ) 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 , 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 .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 over the set of defeasible rules , maximally conflict-free extensions might not be stable or preferred, as shown by the following example:
Let . This argumentation framework has a unique stable extension which is also preferred: . However, the set is conflict-free. Thus, there is a maximally conflict-free set that includes and this set is neither stable nor preferred.
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 ,2929 and is proven in Appendix C.1:
and satisfy Direct Consistency, Closure and Indirect Consistency for any for which satisfies and .
Non-interference holds for strict rule bases that are uniform:3030
A rule set is uniform iff for any two sets of formulas Γ, in and any formula ϕ in such that is -consistent and syntactically disjoint from , it holds that iff .
Non-Interference for for prioritized rule bases was not shown before and is proven in Appendix C:
and satisfy Non-Interference for any argumentation systems whose sets of strict rules are uniform and satisfy and .
In particular, this means that an argumentation system that is induced by classical logic satisfies non-interference. In more detail, we say that is induced by classical logic if is closed under the classical connectives and is the set of strict rules capturing classical logic (over ): iff . For a concrete example, see Example 2.
Where is induced by classical logic, is uniform and satisfies and .
Given the uniformity of classical logic, Theorem 3 immediately implies the non-interference of any argumentation system induced by classical logic.
and satisfy Non-Interference for any argumentation system induced by classical logic.
Strict Non-Interference holds for systems with sets of strict rules that satisfy and .
and satisfy Strict Non-Interference for any argumentation systems with sets of strict rules that satisfy and .
The reader may wonder why and are needed. We first note that both and are very much in line with the interpretation of strict rules S as truth-preserving rules. For example, requires that if for some (i.e. Δ implies the falsity of B), then if B is true, one of the members of Δ must be false. Likewise, requires that if Δ can be used to derive , i.e. show that B is false, B does not have to be assumed true.
From the perspective of the argumentative rationality postulates, ensures that whenever an argument a is attacked by an argument , we can construct the contraposed argument . If we cannot do this, several rationality postulates are violated.
where and , and for any , and . We have the following arguments:
Notice that c attacks but does not defeat d since . Vice versa, d does not even attack c since c is a strict rule-argument, which cannot be attacked. Thus, the unique preferred extension of this argumentation framework includes a, b, c and d and thus this argumentation framework violates consistency since there are arguments for both r (namely c) and its contrary (namely d).
ensures, among other things, that a defeasible argument concluding an -anti-theorem or contradiction (i.e., a formula ϕ for which such as in classical logic) is attacked by a strict argument (namely ). As such, ensures there is always an argument that can defend any argument from an attack based on a “contradictory” formula. If this assumption is given up, non-interference can be violated for rule bases that have explosive behavior:
Where , , , (i.e. p is a falsity), , , , , and
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 it is not in the grounded resp. in any preferred extension of the aggregated framework. This means also non-interference does not hold. In sum, both the equivalence between stable and preferred semantics from Theorem 1 and non-interference are violated. Note while satisfies , does not hold since while (recall that ).
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
Let where , , and . Then consists, among others, of the following two arguments:
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 violates . Indeed and yet there is no such that . In fact, for any rule base that satisfies , the set of contraries will be (pseudo-)symmetric in the sense that if there is a then there is a for which . Notice that this is weaker than symmetry as it is perhaps usually understood, i.e. if then .
If satisfies and , there is a such that .
Suppose that satisfies and . Since , with there is some for which . □
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 , 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 to be consistent, given a fixed context of strict rules and of (strict) premises .
Where the context disambiguates, we simply write instead of . Simply expressed, ϕ follows from Δ if it can be derived by applying modus ponens for premises in and rules in . Where the context disambiguates, we will omit the sub-script and simply write .
Where , Δ is -inconsistent iff there is a formula ϕ and a for which and . Otherwise Δ is -consistent.
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 be the set of all -consistent for which there is no -consistent such that .3333 However, this approach does not characterize argumentation semantics (and other “conclusion-maximizing” approaches such as default logic), as the following simple example illustrates.
Let where iff or and .
Then . However, if we consider the argumentation framework based on the same ingredients, we will have two preferred (resp. stable) extensions: and where , and . Note that both extensions contain . This contrasts with the maximal consistent set .
The problem with the set in our example is that it is not “grounded”: the rule cannot be triggered: indeed, where . This is why it does not correspond to an extension of the corresponding argumentation framework. In the following we will restrict our attention to those sets of defeasible rules that are grounded in the sense that for each .
Where and , r is -triggered by Δ iff for each . We will also call Δ a -trigger set of r. Let be the set of all such that every is -triggered by Δ.
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 by .
Where , Δ is inconsistent iff there are and for which .
For the right-to-left direction suppose there are and for which . Since also and we are done. The left-to-right direction can be shown by an induction over the lengths of the proof of ϕ and ψ from Δ by making use of the contrapositably nature of the strict rules. We omit the technical details but give a simple example instead.
Suppose, where , and and are strict rules and we have the following two proofs (in tree form) demonstrating that and :
By contraposition, also is a rule for some . So, we have the following proof
is the set of all consistent for which there is no consistent such that .
Where the context disambiguates, we will omit the superscript and simply write .
Example 14(Example 12 cont.).
We have . Note that and just like both argumentation extensions contain arguments for p.
There is indeed a very close relationship between the set and the preferred resp. stable extensions of . To state it we introduce one more notation.
Where let be the set of arguments that only make use of defeasible rules in Δ.
Our main result for non-prioritized argumentation can then be stated as follows:
For any where satisfies and ,
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 . We give the following counter-example:
Example 15(Example 6 continued).
Recall from Example 6. We have , and . However, the grounded extension is . Recall for this that the argument attacks . Note that q is implied by every MCS, but there is no argument for it in the grounded extension.
What we see in the example is contaminating behavior by the inconsistent argument which attacks the syntactically disjoint b. This contamination does not occur when working with MCSs. One way to deal with this problem in the context of formal argumentation is to filter out inconsistent arguments such as .3434
Let be the set of all consistent arguments a in , where a is consistent iff is consistent (see Definition 14). Similarly, where , let be the set of extension of the restriction of to consistent arguments.
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 .
where iff or and . Then . Note that .
In the Appendix (Lemma 6) we show that there is a unique ⊂-maximal that is contained in .
We call the unique ⊆-maximal that is contained in the free set in , denoted by .
The set characterizes the grounded extension when filtering out inconsistent arguments.
Where and satisfies and , .
Naturally, the question arises whether for preferred and stable semantics the filtering of inconsistent arguments changes the extensions. The answer is no:
For any where satisfies and ,
4.3.2.The prioritized case
We now move to prioritized frameworks. Stable and preferred extensions can be characterized by selecting a subset of . For this, we introduce a new priority-sensitive notion of consistency. Recall that the defeasible rules in are ranked by a total order ⩽. This means that, without loss of generality, we can assume that the defeasible rules in are ranked relative to a (finite) set of natural numbers. We denote this ranking by . Where , let where for all . We then define:
is -R-consistent iff it is -consistent and for all for which there is a such that and . We write for the set of all -R-consistent Δ for which there are no -R-consistent Θ such that .
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 of Δ that is already inconsistent with Θ but for which . This makes it rational to stick with an R-consistent set of rules Δ since whenever we are confronted with a set of rules Θ inconsistent with Δ, it is rational to disregard a rule in Θ because the conflict can be further localized in the conflict and there is no reason to give up rules in since .
In order to avoid clutter we will again talk about R-consistent sets and write whenever the context disambiguates.
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 2 continued).
We consider a slight modification of that does not contain undercut: where .
We have one set of rules that is maximally R-consistent: . Note that any set that is inconsistent with Θ contains . Since and this suffices to show that Θ is R-consistent. Since Θ is also maximally consistent, it is maximally R-consistent as well. Our other maximally consistent set is not R-consistent since for we have and there is no for which and . This is for the simple reason that any for which will contain .
Maximal R-consistency can be used to characterize preferred and stable semantics, both for frameworks with and without consistent arguments.
Where and satisfies and ,
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.
Consider where iff or and
This gives rise to the following argumentation framework:
We have and so . Note also that and so it is the unique ⊂-maximal set contained in . Nevertheless, the grounded extension for this example does not include any defeasible arguments and so also not an argument for s.
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 in [50,53] where the strict rule base satisfies either contraposition or transposition. This line of work was continued in , where different variants of the weakest link lifting were studied. Let us therefore compare the conditions of contraposition and transposition to the conditions and used in this paper. Let denote a contradictory of ϕ, i.e., a formula ψ for which and . For the definitions of Tpos and Cpos we thus follow  in assuming
CPE Every formula ϕ has a contradictory ψ (so and )
Unlike , in the setting of this paper we did not suppose CPE, i.e., the existence of contradictories. Note, however, that implies that if some formula has a contrary, so does every.3636 For most use cases of ASPIC this will coincide with the slightly stronger assumptions that
CTE For every formula ϕ, .
It will not surprise the reader that there is a close connection between the Cpos resp. Cpos⋆ and requirement .
Cpos implies if for all and all , .
Assume Δ, for some and that Cpos is valid. By Cpos, Δ, . Since and by the transitivity of , Δ, . □
Cpos⋆ and CPE imply .
Suppose Δ, for some . By Cpos⋆ and CPE, Δ, . Since , by Cpos and CPE, and furthermore, . By the transitivity of , Δ, . □
Cpos⋆ implies if for all and all there is a for which .
Assume Δ, for some and that Cpos⋆ is valid. We have to show that Δ, for some . We suppose that for some . By Cpos⋆, Δ, for some . By the transitivity of therefore Δ, . □
In particular, the requirement of Facts 7–9 hold if for all formulas ϕ all members of are contradictories, i.e., if for all .
Interestingly, even given CPE, we can easily find counter-examples to rationality postulates such as Consistency for frameworks satisfying Cpos (and similarly for Tpos).
Consider , where , , , , , , , , , and .
Note that p is merely a contrary, not a contradictory of q, while and q are contradictories. We have the following arguments:
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 satisfies Cpos and CPE, it does not satisfy since but not .
The example also shows that does not imply Cpos.
To see that neither Cpos, Cpos⋆, nor Tpos implies , consider the following example: Let and . Then we see that is closed under Cpos and Tpos, however, it does not satisfy , as yet . In view of Example 10, this means that Tpos and Cpos as studied in  are not sufficient to guarantee non-interference.
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  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(Problems with “contrary-rebut”).
In all example below we treat and ϕ as contradictories. Our examples concern two very weak versions of “interference”3838 and a lightweight version of the well-known Cumulativity principle from non-monotonic logic.
Interference 1. Suppose has the rule base , p has as a contrary r and the strict rules are induced by classical logic. Clearly, p will be a grounded consequence of . Suppose further we add the rules resulting in an extended system . Now the argument , will defeat and p will therefore not be a grounded consequence of . Note that we only added weaker rules than the ones in , both of which are syntactically disjoint from , but this was sufficient to contaminate the framework.
Interference 2. In this example we will again add rules to a given , this time rules that only extend arguments which are rejected in any extension of a given standard (completeness-based) semantics. Let be based on . Clearly, the argument will be in any extension, while will be defeated in any extension. We now add the rules in resulting in , where p has as a contrary . We note that these rules are weaker than those in and they only extend our rejected b to . Interestingly, now c defeats a and so p will not be anymore a consequence of .
Cumulativity lite. Suppose an argument a with conclusion ϕ and strength n (so ) is contained in every preferred extension of . Then one would expect that adding a new rule to the defeasible rules should lead to robust results. (In Appendix C.4 we show that our system satisfies our expectation.) Let come with the rules
This results in the framework to the left:
So a and are contained in every preferred extension of . Now if we add to (resulting in ), we also get the argument and . This results in the graph to the right (omitting the nodes b and for clutter reduction). Now, there is a preferred extension containing c and in which a and are defeated, so that p and q are not anymore consequences of .
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.
 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 that:30] shows that this axiom is sufficient to guarantee the postulates of closure and consistency for argumentation systems without preferences over the defeasible rules. However, non-interference is not studied. In fact, self-contradiction alone is not sufficient to guarantee non-interference, even for argumentation systems without preferences. To see this, notice that in Example 10 the self-contradiction axiom is satisfied as: for all , and . However, as explained in Example 10, non-interference is not satisfied.
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. . 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 , 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 ), the output of an argumentation system satisfies consistency, closure, closure under sub-arguments. Moreover, if every extension contains all strict arguments, for every stable extension , is maximally consistent. It is also shown that if an attack relation is such that the number of stable extensions is the same as the number of maximally consistent subsets of defeasible rules, the stable and the preferred extensions coincide (as in Theorem 1) and coincide with the sets of arguments that can be constructed on the basis of maximally consistent subsets of defeasible rules (as in Theorem 9).
Although the results in  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,  takes a reverse-engineering approach by studying requirements for structured argumentation formalisms that warrant desired results. Finally, in  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] is used to obtain an argumentative characterization of prioritised default logic . For this it is noticed that the weakest link lifting is not adequate and therefore the structure preference order has to be used, a lifting tailored for the characterization of prioritised default logic. Since prioritised default logic gives rise to a single extension for totally ordered default theories, the resulting frameworks also have a unique stable extension, which can be contrasted with under weakest link (see e.g. Example 6). Furthermore, even though [59,60] show closure, direct and indirect consistency for the resulting formalism, non-interference is not mentioned.
6.Concluding discussion and outlook
The main contributions of this paper can be summarized as follows: without undercut and defeasible premises, and with a strict contrapositable rule base satisfies all four rationality postulates under preferred and stable semantics (which coincide) and admits a representation in terms of maximal consistent subsets under the weakest link lifting for totally ordered defeasible rules. Furthermore, we showed that the grounded extension for non-prioritized argumentation systems contain the free defeasible rules, but for prioritized argumentation systems such a characterization does not work. We conclude this paper by explaining how these results shed further light on the close relationship between assumption-based argumentation and and finally point to further work we plan on the basis of this paper.
Besides the ASPIC-family, another popular approach to structured argumentation is assumption-based argumentation . 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 . In this way, ABA can be seen as an abstraction to the level of equivalence-classes of arguments that are based on the same defeasible ingredients.
Formally, a prioritised ABA system consists of a language , a set of defeasible assumptions , a set of strict rules formulated over , a strict premise set , a contrariness relation and a preference relation ⪯ over . Argumentation frameworks constructed on the basis of a prioritised ABA system are where iff (1) for some and some and (2) .4141
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 give rise to similar output. What is still an open question, though, is whether the abstract perspective offered by ABA (i.e. to consider argumentation graphs on the basis of equivalence classes of arguments) can also be obtained in . A positive answer to this question would mean that it is possible to smoothly change perspectives between different levels of abstraction for argumentation based on defeasible rule bases. The more abstract perspective has the benefit that the set of arguments is bounded by the size of the powerset of defeasible elements, which implies that the set of arguments will be finite if the set of defeasible elements is finite. This stands in contrast with approaches with -style arguments, where even for a finite number of defeasible elements, the argumentation graph may contain an infinite number of arguments (since e.g. classical logic gives rise to an infinite number of conclusions for every premise set).
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 , the last link lifting. According to it, an argument is as strong as the last defeasible elements applied in the construction of the argument. A complication with the last link lifting concerns arguments in which we are dealing with several last defeasible links. We can, for instance, opt for the strongest of the last links (called elitist approach ) or the weakest (called democratic approach in ). It turns out that both approaches lead to violations of non-interference in the current setting. We paradigmatically present an example for the democratic approach.
Example 21(Inspired by Example 6.7 in ).
where and . We have, among others, the following arguments:
In this example we use the democratic last link lifting, which says that an argument iff the ⩽-minimal last defeasible rule used in b is weaker than the ⩽-minimal last defeasible rule used in c. For example, since the weakest last defeasible link of , , is weaker than the weakest (and only) last defeasible link of , . For the same reason, . We get the following defeat diagram:
It can be seen that the unique preferred extension only contains strict arguments and arguments with the defeasible rule . If we now add the syntactically disjoint rule , the argument defeats the argument and thus interferes with the derivability of t.
It is interesting to note that is used in  to show that under last link, filtering out inconsistent arguments leads to violations of closure and consistency. Indeed, when , and are not part of the argumentation framework, , , , and are all undefeated, meaning they are part of the unique preferred extension of . This means that this extension contains arguments for e.g. p, q and , constituting a violation of indirect consistency and closure (since but there is no argument for ⊥ in ). It is therefore an important avenue for future work to define a formalism that satisfies all four rationality postulates under the last link principle.
1 The notation used in this example will be properly introduced in Section 2.
2 In the context of scholars often distinguish domain-dependent from domain-independent rules (see e.g., [53, Section 4] for a more detailed discussion). The latter hold for purely logical reasons which is why we deal with them typically when the set of strict rules is induced by a (Tarskian) logic, while the former cover typically cases in which the strict rules are not justified by a truth-preservational logical standard but rather by empirical insights.
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 does not denote the set theoretic complement.
5 is -consistent iff there is no derivation based on rules in from of some and some . See also Def. 8.
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 the rule set constructed in the same way as in this example, except that the language is changed relative to the example at hand.
10 In all the examples that follow where is closed under ¬, we will treat the same.
11 In this paper we will for the sake of simplicity omit several features of the original framework of , such as defeasible premises and undermining attacks. We note that (in case no incomparabilities between the strength of defeasible premises and the strength of defeasible rules occur) defeasible premises γ can easily be modelled as a defeasible rule and undermining attacks can be modelled as a rebuttals.
12 We note that is a set of rules whereas is a function mapping arguments to subsets of . This will not cause any confusion.
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  in the context of deontic logic, with the aim of modelling a cautious, ‘austere’ style of reasoning.
15 Unlike , 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 and rebuts where . The latter they call contrary-rebut and treat differently, since in these works contrary-rebuts result in defeats regardless of the relative strength of a and b. We will have more to say about this in Section 5.
17 Dung  showed that for every AF there is a unique grounded extension, which we denote by .
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. ).
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 .
23  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 is induced by a logic, since some logics, such as the well-known 3-valued logic K3 lack theorems.
26 A similar observation has been made in , 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. ) 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 .
29 In Section 5 we give a detailed comparison of the setting of  and the assumptions made in this paper.
30 Structural consequence relations are also well-behaved in other respects, such as having a characteristic matrix (see [56, Theorem 3]).
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 -formulas (Def. 8), or a set of formulas in and a set of rules (Def. 13).
33 This is the core mechanism behind constrained input-output logics .
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  while [19,53] only require “…then for some …”.  state the property explicitly only for ¬ instead of . Similar comments apply to Cpos. The exact effect of the subtle differences between these different formulations of transposition, respectively contraposition and different assumptions on the contrariness relation are outside the scope of this paper but give rise to an interesting direction for future research.
36 Suppose . Then and so by , for some .
37 A similar example as Example 9 can be used to show that a weaker version of Cpos⋆ which only demands “for some and for some ” instead of “for all and for all ” leads to problems with rationality postulates. Consider where , , and for all other atoms ϕ, and . We have the same arguments as in Example 9 and the counter-example to closure is thus analogous. Note that satisfies the weak version of Cpos.
38 We use this term in order to indicate that the addition of “irrelevant” information leads to contaminating effects (see also ). “Irrelevance” is disambiguated differently in the two versions considered.
39 On the most general level,  assumes that an argumentation system is built on the basis of an abstract logic over a language where is a Tarskian consequence relation and is a collection sets that is upward-closed and doesn’t contain . A set Δ is inconsistent if . For with symmetric negation,  remarks that can be instantiated by any set that contains both a formula and its contarry. In view of Definition 9, this can be seen to coincide with our notion of inconsistency.
40 Although it has been shown in  that, at least when preferences are not taken into account, ABA admits , and thus the chaining of defeasible rules, via a translation.
41 We compare here with assumption-based argumentation with direct attacks, called in [40,44]. However, in the setting of this paper, the remarks made here generalize to assumption-based argumentation with reverse attacks (called in [40,44] and in ), since it has been shown that and give rise to the same outcomes when a flat assumption-based framework satisfies and .
42 For simplicity we suppose here that our defeasible rules are ranked.
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.
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 to denote an arbitrary representative of .
Appendix B.Representation in terms of maximal consistent sets
B.1.The flat case
In what follows we shall assume a fixed where satisfies and . We start with some facts about set in . We will usually write ⊢ instead of (see Def. 14).
Where and , there is an argument with and conclusion ϕ.
Suppose and . By Def. 14, . Thus, by Def. 8, there is a proof of ϕ based on facts in and rules in and Δ. We construct a now exactly in terms of the structure of . □
Where : , iff .
Suppose , . By Def. 13 we have to show that . Since and by Def. 15, for each , for all . So, for all . Also, by applying the rules in Δ we get for all . By our main supposition .
Suppose . By Def. 14, . By Def. 8, there is a proof of ϕ from using rules in and Δ. Let be the set of all defeasible rules used in . Then, trivially, also . Thus, , . □
is closed under ∪.
Let and . Without loss of generality let . Thus, r is triggered by and so also by . □
Where and , there is a for which for all .
Consider a . Since there is a proof from Δ of ψ which we can, without loss of generality, assume to be minimal (in that no proper sub-proof of establishes ψ). Let be the set of all that are used in . Note that if (modus ponens on) r were used in , there would be a proper sub-proof of that establishes ψ since . Thus, . Moreover, since trivially all are used and thus triggered in , .
Let where for each , is defined as in the previous paragraph. By Fact 12, . Since for each , , also for all . Since for all , also . □
Where and r and are two different rules in Δ, for any ⊂-minimal trigger sets for r and we have: ( or ) and so ( or ).
Let such that and let be ⊂-minimal trigger sets of r resp. . Assume . So, . By Fact 13 and the ⊂-minimality of , . Since , there is a ⊂-minimal that triggers . Since we are finished. □
Where is finite and non-empty, there is a such that and all are triggered by .
Let . Assume for a contradiction that there is no such that and triggers all . This means that for each there is a for which there is no trigger set in . Thus, for there is a such that every trigger set of contains .
With some renumbering let . Also for there is a for which there is no trigger set in . Suppose . However, then every trigger set of includes and every trigger set of includes which contradicts Fact 13 since then every trigger set of includes .
After some renumbering let . Again, there is a for which there is no trigger set in . Suppose . But then every trigger set (in Δ) of contains and vice versa, every trigger set of (in Δ) contains . This is in contradiction with Fact 14. Suppose then that . So any trigger set of contains . However, every trigger set of contains and so every trigger set of contains . Since every trigger set of contains this is impossible.
Altogether we can create a sequence . Since each member of the sequence is different from those before and since we only have n many rules we run into a contradiction. This means our assumptions was false. □
Where is finite, and is the set of all triggered by then , is ⊆-monotonically increasing, and there is a minimal fixed point .
Note that in our construction for each , . Therefore also . A fixed point is reached after finitely many steps since Δ is finite.
“⊆”: Let . Thus, there is a that triggers r. By Fact 15, there is a that triggers every and for which . We proceed iteratively: for there is a that triggers each and . Since is a ⊂-monotonically decreasing sequence and is finite, we reach a minimal point . Note that by the construction, . So, .
“⊇”: This holds trivially. □
Where and , there is an such that some triggers r.
Let . Thus, there is a finite that triggers . In view of Fact 13 we can safely assume . Let . If we are finished since triggers . Otherwise, for an arbitrary there is a that triggers . In view of Fact 13 we can safely assume . Let . If we are done since then triggers . Otherwise we continue in the same manner. Since is a ⊂-decreasing sequence of finite sets, we reach the point where after finitely many steps at which point triggers , and . □
The next result offers a Lindenbaum-like construction of maximal consistent sets of defeasible rules in .
Where is consistent, there is a maximal consistent for which .
Let be enumerated by . Where is a list let . Let be a list of all the rules triggered by Λ except those in Λ (where for every index). We construct by a transfinite induction (bounded by ) as follows: , and for all successor ordinals ,
We first show (inductively) that each is consistent. For this holds by the supposition. For the inductive step consider first a successor ordinal α and suppose is consistent. Then, by the construction also is consistent. Consider now a limit ordinal α and suppose for all , is consistent. Assume for a contradiction that that is inconsistent. Thus, there is a finite such that . Thus, there is a for which . But then is inconsistent in contradiction to our inductive hypothesis.
Note also that in view of the construction (and Fact 12) is a monotonically ⊆-increasing sequence of sets in . By Fact 12, .
Suppose now that Δ is not consistent. Thus there is a rule and a for which where . Thus, there is a for which . Also, since , either where , or for some , and . Clearly, or . So either, or in contradiction to the consistency of respectively of . So Δ is consistent.
Suppose Δ is not maximal consistent. Thus, there is a consistent for which . Let . By Fact 17, some is triggered by Δ. Thus, there is a for which for all . Thus, there is a minimal α for which . Note that is triggered by and that for any (since otherwise by item (ii)). But since never enters , for some , and by the consistency of , it is added to . This is a contradiction. □
In the following, given some proof based on some (strict and/or defeasible) inference rules , let denote the set of the top (or last) defeasible rules used in .
If , , and , then for some .
Since , i.e., is inconsistent, there is a for which where for some . If , by the consistency of Θ, and so we are done. Otherwise, let . By Fact 17, there is an for which some set in triggers . Thus, Θ triggers and so is inconsistent (by the ⊆-maximality of Θ). Thus, there is a such that for some such that .
If then by the consistency of Θ and our proof is finished.
Suppose now that . Let be a proof of from Ω. Let . Suppose first that . But then there is a proof of from Θ since each and as such is triggered by some . Let . Thus, . Thus, by the consistency of Θ, and we are done. Suppose now that . Without loss of generality, suppose . So, . By , .
If , by , and thus . Since, in view of Fact 12, our proof is finished.
If , then and since Θ triggers , there is a that triggers . Thus, . Since, in view of Fact 12, , our proof is finished. □
Where is consistent, there are no such that a attacks b.
Where , suppose a attacks b. Thus, there is an such that . This is in contradiction to the consistency of Θ since and . □
Where , and .
Let , where . By Lemma 2, is conflict-free. Consider now some . Thus, . Notice that since , and hence, by Fact 18, there is a for which . Thus, there is a such that there is a proof from with conclusion . The corresponding argument with (see Fact 10) attacks b. □
The next fact follows since any defeater/attacker of a sub-argument of some argument a also defeats/attacks a.
Fact 19(Sub-Argument Closure).
Where is a complete extension of , and b is a sub-argument of a, .
Where is closed under sub-arguments and , there is an argument with top-rule r.
Suppose . Thus, there is a with . Thus, there is a with top-rule r. By sub-argument closure, . □
Where (resp. ), is consistent.
Suppose is inconsistent. Thus, there is a finite and an for which .
Since and by the sub-argument closure of (Fact 19) and by Fact 20, for each there is a with top-rule . Let .
Since , is inconsistent and by Fact 12 . Let as in Fact 16. Thus, there is a minimal for which is inconsistent. Let . Let be maximal in such that is consistent while is inconsistent. So, for some in . Note that . By Fact 11 (and the compactness of ), , , for some finite and by and , , .
Where and we have attacks . Thus, there is a that attacks b. But this attack must take place in some in contradiction to the conflict-freeness of . □
For every (resp. ) there is a such that . In signs: (resp. ).
Suppose (resp. ) and let . By Lemma 4, Θ is consistent.
Assume now that it is not maximal consistent. By Lemma 1, there is a maximal consistent for which . By Lemma 3, is stable and thus also admissible which contradicts the maximality of Θ. □
The following theorem follows immediately with Lemma 3 and Lemma 5.
Where and satisfies and ,
B.2.Grounded semantics for flat frameworks
We first show that the free set exists (see Def. 19).
Where , there is a unique ⊂-maximal that is contained in Ξ.
Let be the set of all contained in Ξ. Then, by Fact 12, also . □
The following lemma shows that the free set in can be constructed in a bottom-up iterative way.
where and is the set of all that are triggered by .
“⊇”: This follows since by its construction, and .
“⊆”: Assume for a contradiction that . By Fact 17, there is a that is triggered by . But then . This is a contradiction. □
For all , if then .
Suppose is consistent. By Lemma 1, there is a such that . Thus, and so is consistent. □
There is no that attacks some argument in .
Suppose some attacks a . Thus, for some . Thus, . By Lemma 8, . □
Where and satisfies and , .
“⊇”: Note that for every extension of . This means that and by Theorem 10, . Also and so .
“⊆”: By Lemma 9, has no attackers in . Thus, trivially . □
In view of Theorem 11 and Lemma 9 we have:
Where and satisfies and , is the set of arguments in that have no attackers in .
B.3.The prioritized case
In what follows we assume a fixed where satisfies and .
(2) if and then .
We again provide a Lindenbaum-like construction for showing the existence of maximal R-consistent superset of R-consistent sets in .
Where is R-consistent, there is a maximal R-consistent such that .
Suppose . For any set of rules Ξ, let the function return the rule with the lowest index. Our construction is similar to the one in Lemma 1.
We again let be the set of all rules in triggered by Λ except those in Λ. Where let . Let . Finally, let . Informally, contains those rules triggered by Λ whose strongest trigger sets in Λ are strongest as compared to the strongest trigger sets of other triggered rules. We now construct via a transfinite induction (bounded by ) as follows: and, where α is a successor ordinal,
(i) We first show (inductively) that each is consistent. For this holds by the supposition. For the inductive step consider first a successor ordinal α and suppose is consistent. Then, by the construction also is consistent. Consider now a limit ordinal α and suppose for all , is consistent. Assume for a contradiction that that is inconsistent. Thus, there is a finite such that . Thus, there is a for which . But then is inconsistent in contradiction to our inductive hypothesis.
(ii) In view of the construction (and Fact 12), is a monotonically ⊆-increasing sequence of sets in . Also by Fact 12, .
(iii) Our main work now is to show that each is R-consistent for each ordinal α. This can be done inductively, where the base case holds by definition.
For the inductive step we first consider a limit ordinal α. Suppose is R-consistent for each . Assume for a contradiction that is not R-consistent. Thus, there is a such that and for all , if . Since , by compactness of there is a finite such that . Thus, there is a for which and so . Since by the inductive hypothesis, is R-consistent, there is a such that and , which is a contradiction.
We now consider a successor ordinal . Assume for a contradiction that is not R-consistent. Therefore there is a that is inconsistent with such that (†) for all that are inconsistent with Δ, . If then, by the inductive hypothesis, there would be a that is inconsistent with Δ and for which . So, is consistent.
Since , there is a and a for which , where . Let be the corresponding proof.
Let and . For each there is a R-maximal trigger set . Let . Also, for each there is a trigger set . Let . Note that since otherwise .
By Fact 12, and . By Fact 21, since and by (†), .
Recall that . Without loss of generality let . (Note for this that must be among since otherwise and so and hence which was already shown to be impossible.)
Assume now for a contradiction that for some . We now show that this means that this would imply that is not added to but rather some . To see this let as in Fact 16. Note that since . Thus, there is a minimal for which . Thus, any is triggered by : by ∅ if resp. by if