the attack relation. For ha, a′i ∈ R we say that the argument a attacks the argument a′. We use the notation R+(x) = {y | hx, yi ∈ R} and R−(y) = {x | hx, yi ∈ R}. This notation extends point-wise to sets, e.g. R−(X) = Sx∈X R−(x). We use the convention that R+(∅) = R−(∅) = ∅.
The most well-known semantics for argumentation, first introduced in [
Definition 21 Given any argumentation framework F = hA, Ri and a subset A ⊆ A, we define D(A) = {x ∈ A | R−(x) ⊆ R+(A)}, the set of vertices defended by A. We say that – A is conflict-free if R+(A) ⊆ A \ A, i.e. if there are no two arguments in A that attack each other. – A is admissible if it is conflict free and A ⊆ D(A). The set of all admissible sets in F is denoted a(F). – A is complete if it is conflict free and A = D(A). The set of all complete sets in F is denoted c(F). – A is the grounded set if it is complete and there is no complete set B ⊆ A such that B ⊂ A, it is denoted g(F). – A is preferred if it is admissible and not strictly contained in any admissible set.
The set of all preferred sets in F is denoted p(F). – A is stable if R+(A) = A \ A. The set of all stable sets in F is denoted s(F) – A is semi-stable if it is admissible and there is no admissible set B such that
A ∪ R+(A) ⊂ B ∪ R+(B). The set of all semi-stable sets in F is denoted by ss(F). For any S ∈ {a, c, g, p, s, ss}, one also says that A ∈ S(F) is an extension (of the type prescribed by S). Given a framework F and an argument a ∈ A, we say that a is credulously accepted with respect to some S ∈ {a, c, g, p, s, ss} just in case there is some set A ∈ S(F) such that a ∈ A. If a ∈ A for every A ∈ S(F), we say that A is skeptically accepted with respect to S. If an argument is neither credulously nor skeptically accepted with respect to a semantics, it is rejected.1 Intuitively, if an argument is credulously accepted, then it is involved in some line of argument that is successful; it is potentially useful, and should be considered further. If an argument is skeptically accepted, it is involved in all successful lines of arguments; it is beyond reproach, and arguing against it should be considered useless.
Notice that it follows from Definition 21 that the empty set is admissible and that all stable sets are semi-stable, all semi-stable sets are preferred, all preferred sets are complete and all complete sets are admissible. Also, it is not hard to see that the grounded extension is contained in every complete set of arguments. In Figure 1, we give two argumentation frameworks, F and F′, that serve as examples. In the framework F, every argument is attacked by some argument, and from this it follows that we have g(F) = ∅, i.e., the grounded extension is the empty set. The non-empty conflict-free sets are the singletons {a}, {b} and {c}, but we observe that a does not defend himself against the attack he receives from c (since there is no attack (a, c)), and that c does not defend himself against the attack he receives from b. So the only possible nonempty admissible set is {b}. It is indeed admissible; b is attacked only by a and he defends himself, attacking a in return. In fact, since b also attacks c, the set {b} is the unique stable set of this framework. It follows that s(F) = p(F) = ss(F) = {{b}} 1Arguments that are credulously but not skeptically accepted are typically called defensible and a(F) = c(F) = {∅, {b}}. For a more subtle example, consider F′. The first thing to notice here is that we have an unattacked argument a, so the grounded extension is non-empty. In fact, the framework is such that all semantics from Definition 21 behave differently. It might look a bit unruly, but there are many self-attacking arguments that can be ruled out immediately (since they are not in any conflict-free sets), and it is easy to verify that the extensions of F′ under the different semantics are the following: g(F′) = {a}, s(F′) = ∅, ss(F′) = {{a, d, g}} a(F′) = {∅, {a}, {a, c}, {a, c, e}, {d}, {a, d}, {a, d, g}, {d, g}} p(F′) = {{a, d, g}, {a, c, e}}, c(F′) = {{a}, {a, d, g}, {a, c, e}, {a, d}}
Notice that s(F′) = ∅ - no stable set exists in the framework. That stable sets are not guaranteed to exist is a major objection against what is otherwise a fairly conclusive notion of success - an internally consistent set of arguments that defeats all others. Other semantics for argumentation can - to quite some extent - be seen as attempts at arriving at a reasonable notion of success that is weak enough so that interesting extensions always exists, while still strong enough so that it is adequate for applications and have interesting theoretical properties. As we will see later, this is intimately related to the problem of inconsistency handling in logic, with stable sets not existing in a framework precisely when the corresponding propositional theory is not classically consistent.
Argumentation has close links to established concepts in both graph theory and logic. We start by briefly accounting for the link with what is known as kernels in the theory of directed graphs. Given a directed graph (digraph) D = hD, N i with N ⊆ D × D, a set K ⊆ D is a kernel in D if
N −(K) = D \ K
Kernels were introduced by Von Neumann and Morgenstern in [
N +(L) ⊆ N −(L) ⊆ D \ L
←−
It is easy to verify that a local kernel in D is an admissible set in D and vice versa.
These two observations seem valuable to argumentation, since in graph theory, several
interesting results and techniques have been found, especially concerning the question
TF = {x ↔
^
¬y | x ∈ A}
of finding structural conditions that ensure the existence of kernels, see e.g. [
In this paper, we will describe some connections between argumentation and logic,
and we will not explore the link with kernels any further. What is important for us,
is that digraphs inspire a normal form for propositional theories where an assignment
is satisfying iff it gives rise to a kernel in the corresponding digraph, see [
A propositional formula, φ, is said to be in graph normal form iff φ = x ↔ Vy∈X ¬y
for propositional letters {x} ∪ X. In [
y∈R−(x) For instance, the argumentation theory for the framework F depicted in Figure 1, consists of the following equivalences: (1) (2) a ↔ ¬b ∧ ¬c, b ↔ ¬a, c ↔ ¬b
We observe that the only satisfying assignment in classical logic is δ : A → {0, 1} such that δ(a) = δ(c) = 0 and δ(b) = 1, corresponding to the fact that the only successful line of argument under stable semantics is the set containing the argument b, defeating a and c.
Argumentation theories are written using graph normal form, and we can also move in the opposite direction. The construction seems to be of independent interest, so we will present it here. It provides, in particular, a simple way in which results and techniques from argumentation can be applied to logic. Solving SAT, for instance, becomes the search for a stable set, while the other semantics for argumentation could provide new and useful ways in which to extract information from inconsistent theories.
For a positive natural number n, let [n] = {1, . . . , n}. Then, for any theory, T = {x1 ↔ Vx∈X1 ¬x, . . . , xn ↔ Vx∈Xn ¬x}, we define an argumentation framework FT = hFT , RT i as follows
AT = Si∈[n] ({xi} ∪ Xi ∪ {x¯ | x ∈ Xi ∧ ∀i ∈ [n] : x 6= xi})
RT = (Si∈[n]{(x, xi) | x ∈ Xi}) ∪ {(x, x¯), (x¯, x) | x ∈ AT }
2The connection has been noted, for instance in [
3Equisatisfiable means that for every satisfying assignment to one there is a satisfying assignment to the other, i.e., the assignments are not necessarily the same (the addition of new propositional letters must be permitted)
We introduce a fresh argument x¯ for every propositional letter x that does not occur to the left of any equivalence. The reason is that we do not want to force acceptance of x when viewed as an argument. Rather, x should be open for both acceptance and rejection, depending on the rest of the theory. This is achieved by adding the symmetric attack {(x, x¯), (x¯, x)}.
Let I = {x¯ | x ∈ A} denote all the arguments from FT that do not correspond to propositional letters used in T. Given a function α : X → Y , let α|Z denote its restriction to domain Z ⊆ X. Also, given δ : X → {0, 1}, we let δ¯ denote the boolean evaluation of formulas induced by δ according to classical logic.
Given a stable set E ⊆ FT , consider δE : A → {0, 1} defined by δE(x) = 1 iff x ∈ E (meaning that δE(x) = 0 for all x ∈ AT \ E). It is not hard to show that δE|AT \I is a satisfying assignment for T in classical logic, i.e., that δ¯E(φ) = 1 for all φ ∈ T . Similarly, if we are given a satisfying assignment δ : AT \ I → {0, 1}, we obtain the stable set Eδ = {x ∈ AT | δ(x) = 1} ∪ {x¯ ∈ I | δ(x) = 0}.
The constructions given in this section are completely analogous to the ones given
in [
When we succeed in giving semantics for argumentation in terms of logical
consequence and consistency, we no longer need to consider just atomic arguments and
statements about them specified in some informal or semi-formal way. Rather, one can
now use logic, and form a propositional formula which can then be evaluated against
the theory corresponding to the framework. For instance, given a framework F with
a ∈ A, we have that a is not credulously accepted with respect to stable semantics iff
TF is a model of ¬a, i.e., iff we have TF |= ¬a. For another example, consider how
one may write simply a → b to indicate that every successful line of argument which
involves accepting a must also involve accepting b. More generally, when we succeed
in providing a formulation in terms of a known logic, we can use reasoning systems
developed for this logic both to address standard notions from argumentation such
as credulous and skeptical acceptance, and also to check how arbitrary propositional
formulas fare with respect to an argumentation theory; formulas that can now be seen
as statements about interaction among arguments in the underlying argumentation
framework. Conversely, we may use techniques developed in argumentation theory to
analyze logical theories in graph normal form - something that might prove
particularly useful for algorithmic problems, since the digraph structure of argumentation
frameworks should prove particularly useful in this regard. We remark that interesting
results have already been obtained which exploits digraph-properties for tackling
algorithmic problems concerning the semantic properties of argumentation frameworks,
see e.g., [
It seems, in light of this, that the search for nice logical accounts of argumentation
is a highly worthwhile direction of research. In fact, it has recently been taken up by
logicians coming at argumentation from a more theoretical, less application-oriented,
angle, see e.g., [
Argumentation and Lukasiewicz logic L3
In this section we will characterize the complete extensions logically. This necessitates
a move away from classical logic. In Caminada and Gabbay [
Here, we directly link L3 to argumentation by showing that any satisfying
assignment to TF gives rise to a complete extension in F and vice versa. The argument we
give proceeds by showing that an assignment is satisfying iff it is what is known in
argumentation theory as a complete Caminada labeling. While not technically
challenging, this result seems nice, since it implies that skeptical and credulous acceptance
of arguments with respect to the complete semantics reduces to logical consequence and
satisfiability in L3. We remark, in particular, that Lukasiewicz three-valued logic
admits a nice proof theory, see e.g., [
Given a propositional language over connectives {¬, ∧, →} and propositional alphabet A, the semantics of logic L3 is defined as follows.
Definition 31 Given an assignment δ : A → {0, 1/2, 1} its extension, δ¯, is defined inductively on complexity of formulas.
– δ¯(a) = δ(a) for all a ∈ A – δ¯(¬φ) = 1 − δ¯(φ) – δ¯(φ → ψ) = min{1, (1 − α¯(φ)) + α¯(φ)} – δ¯(φ ∧ ψ) = min{α¯(φ), α¯(ψ)}
The consequence relation of Lukasiewicz logic is |=L⊆ 2 × L, defined such that Φ |=L φ iff for all δ : A → {0, 1/2, 1}, we have that δ¯(φ) = 1 whenever δ¯(ψ) = 1 for all ψ ∈ Φ,
Notice that φ → ψ obtains semantic value 1 (”true”) under some assignment just in case ψ does not receive a lower semantic value than φ. Defining φ ↔ ψ = (φ → ψ) ∧ (ψ → φ) as usual, one also notices that φ ↔ ψ obtains the value 1 just in case φ and ψ obtain the same semantic value.
Next we define the complete Caminada labellings, not using the original definition, but the equivalence stated and proven in [7, Proposition 1, p. 6-7] Definition 32 A function δ : A → {0, 1/2, 1} is a complete Caminada labeling iff for all x ∈ A we have: L – If δ(x) = 1 then for all y ∈ R−(x) : δ(y) = 0 – If δ(x) = 0 then there is y ∈ R−(x) : δ(y) = 1 – If δ(x) = 1/2 then there is y ∈ R−(x) such that δ(y) = 1/2 and there is no z ∈ R−(x) such that δ(z) = 1
In [7, Theorem 2], the authors prove that if δ : A → {0, 1/2, 1} is a complete Caminada labeling then δ1 = {x ∈ A | δ(x) = 1} is a complete extension for F. They also show that if E ⊆ A is a complete extension, then there is a corresponding complete Caminada labeling δE : A → {0, 1/2, 1}, defined as follows: – δE(x) = 1 for all x ∈ E – δE(x) = 0 for all x ∈ R+(E) – δE(x) = 1/2 for all x ∈ A \ (E ∪ R+(E))
In the following, we prove that a complete Caminada labeling can be equivalently
defined as a satisfying assignment for TF in the logic L3. This shows that the results
from [
Theorem 33 Given an argumentation framework F, we have that δ : A → {0, 1/2, 1} is a complete Caminada labeling iff δ¯(φ) = 1 for all φ ∈ TF.
Proof. ⇒) Assume that δ : A → {0, 1/2, 1} is a complete Caminada labeling and consider an arbitrary φ = x ↔ Vy∈R−(x) ¬y ∈ TF. We need to show that δ¯(x ↔ Vy∈R−(x) ¬y) = 1. There are three cases: – δ(x) = 1. Since δ is a complete Caminada labeling we have, for all y ∈ R−(x), δ(y) = 0. It follows that δ¯(¬y) = 1 for all y ∈ R−(x). Since all conjuncts are true, we conclude that δ¯(Vy∈R−(x) ¬y) = 1 = δ(x) = δ¯(x). So δ¯(φ) = 1 as desired. – δ(x) = 0. Since δ is a complete Caminada labeling it follows that there is some y ∈ R−(x) such that δ(y) = 1. Then δ¯(¬y) = 0, so it follows that δ¯(Vy∈R−(x) ¬y) = 0 = δ(x) = δ¯(x). So δ¯(φ) = 1 as desired. – δ(x) = 1/2. Since δ is a complete Caminada labeling, there is some y ∈ R−(x) such that δ(y) = 1/2. It also follows that there is no z ∈ R−(x) such that δ(z) = 1. From this we conclude that 1/2 = min{δ¯(y) | y ∈ R−(x)} which means δ¯(Vy∈R−(x) ¬y) = 1/2 = δ(x) = δ¯(x). So δ¯(φ) = 1 as desired. ⇐) Assume that δ : A → {0, 1/2, 1} is a satisfying assignment for TF, i.e. that δ¯(φ) = 1 for all φ ∈ TF. Consider arbitrary φ = x ↔ Vy∈R−(x) ¬y ∈ TF. Again there are three cases: – δ(x) = 1. Since δ¯(φ) = 1, we have δ¯(Vy∈R−(x) ¬y) = 1. It follows that δ¯(¬y) = 1 and therefore δ(y) = 0 for all y ∈ R−(x). So the criterion of Definition 32 is met in this case. – δ(x) = 0. Since δ¯(φ) = 1, we have δ¯(Vy∈R−(x) ¬y) = 0. It follows that δ¯(¬y) = 0, and therefore δ(y) = 1 for some y ∈ R−(x). So the criterion of Definition 32 is met. – δ(x) = 1/2. Since δ¯(φ) = 1, we have δ¯(Vy∈R−(x) ¬y) = 1/2. This means that 1/2 = min{δ¯(¬y) | y ∈ R−(x)}. So there must be some y ∈ R−(x) such that δ¯(¬y) = 1/2, which means δ(y) = 1/2. Also, it follows that there is no z ∈ R−(x) such that δ¯(¬z) = 0. So there is no z ∈ R−(x) such that δ(z) = 1, meaning that the criterion of Definition 32 is met in this case as well. We conclude by stating the following corollary, which sums up the immediate consequences for argumentation. We let ⊥ denote contradiction in L3.
Corollary 34 Given an argumentation framework F. An argument a ∈ A is skeptically accepted with respect to complete semantics iff TF |=L a and credulously accepted iff TF ∪ {a} 6|=L ⊥.
Proof. For the first claim, remember that a ∈ A is said to be skeptically accepted with respect to complete semantics iff for all complete extensions E ⊆ A we have a ∈ E iff δ(a) = 1 for all complete Caminada labellings δ : A → {0, 1/2, 1}. By Theorem 33 this is the same as saying that δ(a) = 1 for all δ such that δ¯(φ) = 1 for all φ ∈ TF. By Definition 31, this is the same as TF |=L a. The second claim follows similarly. ✷
As already noted, the logical approach means that we can form complex statements to express various claims about arguments and their interaction in the framework. For the case of complete semantics, we may write, for instance, a ↔ ¬a to indicate that the argument a can be neither defeated nor accepted. It is not hard to see that this formula is true in a model TF iff neither a nor any of its attackers is credulously accepted with respect to the complete semantics. So it does capture the intended meaning, and we believe that the formula is a beautiful representation of an argument having malfunctioned, becoming instead a paradox: an argument such that accepting it is logically equivalent with defeating it!
Using a logical language to talk about argumentation provides clarity, but also sheds light on subtleties that we might not otherwise come to fully appreciate. As an example, consider again the framework F′ from Figure 1. With some thought, we see that in order for both h and i to be defeated, it is necessary to use d to defeat h (since using e will defeat g - the only attacker of i except i itself). But if we try the formula (¬h ∧ ¬i) → d and check if it follows logically from TF′ in L3, we find that it does not. The explanation for this is that implication in L3 treats an argument that is neither accepted nor defeated as closer to truth than an argument that is defeated. Since there is a complete set ({a,c,e}) such that d is defeated while i is neither accepted nor defeated, it follows from this that a countermodel to the implication can be found. Still, it is possible to express a claim that correctly describes the state of affairs that obtains. In fact, after some thought, it is seen that the claim we stated informally - that you must accept d to defeat both h and i - while true, actually serves to misrepresent the situation at hand. For what we actually have is something stronger, namely that in order for h and i to obtain any of the two classical values (true/false or, if you like, defeated/accepted), we have to accept d. This we can express by the implication (¬(h ↔ ¬h) ∧ ¬(i ↔ ¬i)) → d, and now we observe that this implication does indeed follow logically from TF′. Also, we obtain the further logical consequence (¬(h ↔ ¬h) ∧ ¬(i ↔ ¬i)) → (¬h ∧ ¬i) which is also stronger than the original intuition that we had. Thus, what seemed at first sight a shortcoming of the logical approach really suggested a more precise analysis of the situation, one that we might not as easily have arrived at without a logical formulation.
Conclusion
In this paper we have observed how argumentation frameworks can be viewed as
propositional theories in graph normal form. We have shown that this makes it possible to
capture the stable and complete semantics using classical and three-valued Lukasiewicz
logic respectively. Moreover, we have argued that argumentation theories provide a
nice way in which to talk about argumentation in a logical language. It is much more
straightforward than the modal approach from [