=Paper=
{{Paper
|id=Vol-1195/long18
|storemode=property
|title=Argumentation for Propositional Logic and Nonmonotonic Reasoning
|pdfUrl=https://ceur-ws.org/Vol-1195/long18.pdf
|volume=Vol-1195
|dblpUrl=https://dblp.org/rec/conf/cilc/KakasTM14
}}
==Argumentation for Propositional Logic and Nonmonotonic Reasoning==
https://ceur-ws.org/Vol-1195/long18.pdf
Argumentation for Propositional Logic and
Nonmonotonic Reasoning
Antonis Kakas, Francesca Toni, and Paolo Mancarella
1
University of Cyprus, Cyprus
antonis@cs.ucy.ac.cy
2
Imperial College London, UK
ft@imperial.ac.uk
3
Università di Pisa, Italy
paolo@di.unipi.it
Abstract. Argumentation has played a significant role in understanding
and unifying under a common framework di↵erent forms of defeasible
reasoning in AI. Argumentation is also close to the original inception of
logic as a framework for formalizing human argumentation and debate.
In this context, the purpose of this paper is twofold: to draw a formal
connection between argumentation and classical reasoning (in the form of
Propositional Logic) and link this to support defeasible, Non-Monotonic
Reasoning in AI. To this e↵ect, we propose Argumentation Logic and
show properties and extensions thereof.
1 Introduction
Over the past two decades argumentation has played a significant role in under-
standing and unifying under a common framework defeasible Non-Monotonic
Reasoning (NMR) in AI [16, 10, 3]. Moreover, a foundational role for argumenta-
tion has emerged in the context of problems requiring human-like commonsense
reasoning, e.g. as found in the area of open and dynamic multi-agent systems to
support context-dependent decision making, negotiation and dialogue between
agents (e.g. see [14, 9]). This foundational role of argumentation points back to
the original inception of logic as a framework for formalizing human argumen-
tation.
This paper reexamines the foundations of classical logical reasoning from
an argumentation perspective, by formulating a new logic of arguments, called
Argumentation Logic (AL), and showing how this relates to Propositional Logic.
AL is formulated by bringing together argumentation theory from AI and the
syllogistic view of logic in Natural Deduction (ND). Its definition rests on a re-
interpretation of Reductio ad Absurdum (RA) through a suitable argumentation
semantics. One consequence of this is that in AL the implication connective
behaves like a default rule that still allows a form of contrapositive reasoning.
The reasoning in AL is such that the ex-falso rule where everything can be
derived from an inconsistent theory does not apply and hence an inconsistent
part of a theory does not trivialize the whole reasoning with that theory.
272
A. Kakas et al. Argumentation for Propositional Logic and Nonmonotonic Reasoning
The main motivation for studying this argumentation perspective on logical
reasoning is to examine its use to bring together classical reasoning and non-
monotonic commonsense reasoning into a single unified framework. The paper
presents a preliminary investigation into building such a NMR framework based
on AL that integrates into the single representation framework of AL classical
reasoning, as in Propositional Logic including forms of Reductio ad Absurdum,
with defeasible reasoning. In particular, we study, in the context of examples,
the possible use of preferences over sentences of an AL theory to capture NMR
defeasible reasoning and naturally combine this with the classical reasoning of
AL. Our vision is for all forms of reasoning to be captured in the argumentation
reasoning of AL and its extensions with preferences.
This paper is an extract of [13].
2 Preliminaries on Natural Deduction
Let L be a Propositional Logic language and ` denote the provability relation of
Natural Deduction (ND) in Propositional Logic.4 Throughout the paper, theories
and sentences will always refer to theories and sentences wrt L. We assume that
? stands for ^ ¬ , for any 2 L.
Definition 1. Let T be a theory and a sentence. A direct derivation for
(from T ) is a ND derivation of (from T ) that does not contain any application
of RA. If there is a direct derivation for (from T ) we say that is directly
derived (or derived modulo RA) from T , denoted T`M RA .
Example 1. Let T1 = {↵ ! ( ! )}. The following is a direct derivation for
↵ ^ ! (from T1 ):
d↵ ^ hypothesis
↵ ^E
↵ ! ( ! ) from T
! !E
^E
c !E
↵^ ! !I
Thus, T1 `M RA ↵ ^ ! (and, trivially, T1 ` ↵ ^ ! ). Consider now
T2 = {¬(↵ _ )}. The following
d↵ hypothesis
↵_ _I
¬(↵ _ ) from T
?c ^I
¬↵ RA
is a ND derivation of ¬↵ that is not direct. Since there is no direct derivation of
¬↵, T2 ` ¬↵ but T2 6`M RA ¬↵.
4
See the appendix for a review of the ND rules that we use.
273
A. Kakas et al. Argumentation for Propositional Logic and Nonmonotonic Reasoning
Definition 2. A theory T is classically inconsistent i↵ T ` ?. A theory T
is directly inconsistent i↵ T `M RA ?. A theory T is (classically or directly)
consistent i↵ it is not (classically or directly, respectively) inconsistent.
Trivially, if a theory is classically consistent then it is directly consistent. How-
ever, a directly consistent theory may be classically inconsistent, as the following
example shows.
Example 2. Consider T1 = {↵ ! ?, ¬↵ ! ?}. T1 is classically inconsistent,
since T1 ` ? as follows:
d↵ hypothesis
↵ ! ? from T
?c !E
¬↵ RA
d¬↵ hypothesis
¬↵ ! ? from T
?c !E
↵ RA
? ^I
However, T1 is directly consistent, since T1 6`M RA ?. Consider instead T2 =
{↵, ¬↵}. T2 is classically and directly inconsistent, since T2 `M RA ?, as follows:
↵ from T
¬↵ from T
? ^I
We will use a special kind of ND derivations, that we call Reduction ad Absur-
dum Natural Deduction (RAND). These are ND derivations with an outermost
application of RA:
Definition 3. A RAND derivation of ¬ 2 L from T is a ND derivation of ¬
from T of the form
d hypothesis
.. ..
. .
.
?c ..
¬ RA
A sub-derivation (of some 2 L) of a derivation d is a RAND sub-derivation
of d i↵ it is a RAND derivation.
The ND derivation of ¬↵ given T2 in example 1 is a RAND derivation. Also,
given T1 in example 2, the sub-derivations5
d↵ d¬↵
↵!? ¬↵ ! ?
?c ?c
¬↵ ↵
of the derivation (d) of ? are RAND sub-derivations (of d).
5
If clear from the context, we omit to give the ND rules used.
274
A. Kakas et al. Argumentation for Propositional Logic and Nonmonotonic Reasoning
3 Argumentation Logic Frameworks
Given a propositional theory we will define a corresponding argumentation frame-
work as follows.
Definition 4. The argumentation logic (AL) framework corresponding to a the-
ory T is the triple hArgsT , AttT , Def T i defined as follows:
– ArgsT = {T [ ⌃|⌃ ✓ L} is the set of all extensions of T by sets of sentences
in L;
– given a, b 2 ArgsT , with a = T [ , b = T [ , such that 6= {}, (b, a) 2
AttT i↵ a [ b `M RA ?;
– given a, d 2 ArgsT , with a = T [ , (d, a) 2 Def T i↵
1. d = T [ {¬ } (d = T [ { }) for some sentence 2 (respectively
¬ 2 ), or
2. d = T [ {} and a `M RA ?.
In the remainder, b attacks a (wrt T ) stands for (b, a) 2 AttT and d defends or
is a defence against a (wrt T ) stands for (d, a) 2 Def T .
Note also that, since T is fixed, we will often equate arguments T [ ⌃ to sets of
sentences ⌃. So, for example, we will refer to T [ {} = T as the empty argument.
Similarly, we will often equate a defence to a set of sentences. In particular, when
d = T [ defends/is a defence against a = T [ we will say that defends/is
a defence against (wrt T ).
The attack relation between arguments is defined in terms of a direct deriva-
tion of inconsistency. Note that, trivially, for a = T [ , b = T [ , (b, a) 2 AttT
i↵ T [ [ `M RA ?. The following example illustrates our notion of attack:
Example 3. Given T1 = {↵ ! ( ! )} in example 1, {↵, } attacks {¬ } (and
vice-versa), {↵,¬ } attacks { } (and vice-versa), {↵,¬↵} attacks { } (and vice-
versa) as well as any non-empty set of sentences (and vice-versa).
Note that the attack relationship is symmetric except for the case of the empty
argument. Indeed, for a, b both non-empty, it is always the case that a attacks b i↵
b attacks a. However, the empty argument cannot be attacked by any argument
(as the attacked argument is required to be non-empty), but the empty argument
can attack an argument. For example, given T2 = {↵, ¬↵} in example 2, {}
attacks {↵} and {} attacks { } (for any 2 L), since T `M RA ?. Finally, note
that our notion of attack includes the special case of attack between a sentence
and its negation, since, for any theory T , { } attacks {¬ } (and vice-versa), for
any 2 L.
The notion of defence is a subset of the attack relation. In the first case of the
definition we defend against an argument by adopting the complement6 of some
sentence in the argument, whereas in the second case we defend against any
directly inconsistent set using the empty argument. Then, in example 3, {¬↵}
6
The complement of a sentence is ¬ and the complement of a sentence ¬ is .
275
A. Kakas et al. Argumentation for Propositional Logic and Nonmonotonic Reasoning
defends against the attack {↵, } and {} defends against the (directly inconsis-
tent) attack {↵, ¬↵}. Note that the empty argument cannot be defended against
if T is directly consistent. Finally, note that when T is directly inconsistent the
attack and defence relationships trivialise, in the sense that any two non-empty
arguments attack each other, the empty argument attacks any argument, and
any argument can be defended against by the empty argument.
4 Argumentation Logic
In this section we assume that T is directly consistent.
As conventional in argumentation, we define a notion of acceptability of sets
of arguments to determine which conclusions can be dialectically justified (or
not) from a given theory. Our definition of acceptability and non-acceptability
is formalised in terms of the least fix point of (monotonic) operators on the
cartesian product of the set of arguments/sentences in L, as follows:
Definition 5. Let hArgsT , AttT , Def T i be the AL framework corresponding to
a directly consistent theory T , and R the set of binary relations over ArgsT .
– The acceptability operator AT :R!R is defined as follows: for any acc 2 R
and a, a0 2 ArgsT :
(a, a0 ) 2 AT (acc) i↵
• a ✓ a0 , or
• for any b 2 ArgsT such that b attacks a wrt T ,
⇤ b 6✓ a0 [ a, and
⇤ there exists d 2 ArgsT that defends against b wrt T such that (d, a0 [
a) 2 acc.
– The non-acceptability operator NT : R ! R is defined as follows: for any
nacc 2 R and a, a0 2 ArgsT :
(a, a0 ) 2 NT (nacc) i↵
• a 6✓ a0 , and
• there exists b 2 ArgsT such that b attacks a wrt T and
⇤ b ✓ a0 [ a, or
⇤ for any d 2 ArgsT that defends against b wrt T , (d, a0 [ a) 2 nacc.
These AT and NT operators are monotonic wrt set inclusion and hence their
repeated application starting from the empty binary relation will have a least
fixed point.
Definition 6. ACC T and N ACC T denote the least fixed points of AT and NT
respectively. We say that a is acceptable wrt a0 in T i↵ ACC T (a, a0 ), and a is
not acceptable wrt a0 in T i↵ N ACC T (a, a0 ).
Thus, given the AL framework hArgsT , AttT , Def T i (for T directly consistent)
and a, a0 2 ArgsT :
276
A. Kakas et al. Argumentation for Propositional Logic and Nonmonotonic Reasoning
– ACC T (a, a0 ), i↵
• a ✓ a0 , or
• for all b 2 ArgsT such that b attacks a:
⇤ b 6✓ a0 [ a, and
⇤ there exists d 2 ArgsT such that d defends against b and
ACC T (d, a0 [ a);
T
– N ACC (a, a0 ), i↵
• a 6✓ a0 and
• there exists b 2 ArgsT such that b attacks a and
⇤ b ✓ a0 [ a, or
⇤ for all d 2 ArgsT such that d defends against b it holds that
N ACC T (d, a0 [ a).
We will often equate the (non-)acceptability of an argument T [ wrt an argu-
ment T [ 0 to the (non-)acceptability of the set of sentences wrt the set of
sentences 0 .
Note that non-acceptability, N ACC T (a, a0 ), is the same as the classical nega-
tion of ACC T (a, a0 ), i.e. N ACC T (a, a0 ) = ¬ACC T (a, a0 ). We choose to give
the definition of non-acceptability explicitly to aid readibility. We will use these
two versions of non-acceptability interchangeably.
Note that the empty argument is always acceptable, wrt any other argument.
Note also that the “canonical” attack of a sentence on its complement (i.e. of
T [ { } on T [ {¬ } and vice-versa) does not a↵ect the acceptability relation
as it can always be defended against by this complement itself.
The following examples illustrate non-acceptability.
{¬O } {↵}
O
(since T [{¬ }`M RA ?) (since T [{↵}[{ }`M RA ?)
{} { KS }
{¬O }
(since T [{¬ }`M RA ?)
{}
Fig. 1. Illustration of N ACC T ({¬ }, {}) (left) and N ACC T ({↵}, {}) (right), for ex-
ample 4.
Example 4. Let T = {↵ ^ ! ?, ¬ ! ?}. T is classically and directly consis-
tent, T [ {¬ } is classically and directly inconsistent, and T [ {↵} is classically
inconsistent but directly consistent. It is easy to see that N ACC T ({¬ }, {})
holds, as illustrated in figure 1 (left)7 , since {¬ } 6✓ {}, b = {} attacks {¬ }
7
Here and throughout the paper we adopt the following graphical convention: " de-
notes an attack and * denotes a defence.
277
A. Kakas et al. Argumentation for Propositional Logic and Nonmonotonic Reasoning
and {} ✓ {¬ }. Also, N ACC T ({↵}, {}) holds, as illustrated in figure 1 (right).
Indeed:
– since {↵} 6✓ {}, b = { } attacks {↵} and {¬ } is the only defence against b,
to prove that N ACC T ({↵}, {}) it suffices to prove that N ACC T ({¬ }, {↵});
– since {¬ } 6✓ {↵}, b = {} attacks {¬ } and {} ✓ {↵, ¬ }, it follows that
N ACC T ({¬ }, {↵}) holds as required.
Note that if an argument a is attacked by the empty argument, then it is ac-
ceptable wrt a0 i↵ a ✓ a0 , since there is no defence against the empty argument.
This observation is used in the following example.
Example 5. Given T = T1 = {↵ ! ?, ¬↵ ! ?} in example 2, N ACC T ({↵}, {})
and N ACC T ({¬↵}, {}) both hold. Indeed, for N ACC T ({↵}, {}), {↵} is attacked
by {}.
The following example shows a case of non-acceptability making use of a non-
empty attack for the base case.
Example 6. Let T = {↵ ^ ¬ ! ?, ^ ! ?, ↵ ^ ^ ¬ ! ?}. T is classically
(and directly) consistent, and T [ {↵} is classically inconsistent but directly
consistent. N ACC T ({↵}, {}) holds, as illustrated in figure 2. Indeed:
{↵}
O
(since T [{↵}[{¬ }`M RA ?)
{¬KS }
{O}
(since T [{ }[{ }`M RA ?)
{ KS }
{¬O }
(since T [{↵, }[{¬ }`M RA ?)
{↵, }
Fig. 2. Illustration of N ACC T ({↵}, {}) for example 6.
– since {↵} 6✓ {}, b = {¬ } attacks {↵} and { } is the only defence against b,
to prove that N ACC T ({↵}, {}) it suffices to prove that N ACC T ({ }, {↵});
– since { } 6✓ {↵}, b0 = { } attacks { } and {¬ } is the only defence against
b0 , to prove N ACC T ({ }, {↵}) it suffices to prove N ACC T ({¬ }, {↵, });
– since {¬ } 6✓ {↵, }, b00 = {↵, } attacks {¬ } and b00 ✓ {↵, , ¬ },
N ACC T ({¬ }, {↵, }) and so N ACC T ({ }, {↵}) and N ACC T ({↵}, {}) hold.
The following example illustrates non-acceptability in the case of an empty (and
thus classically consistent) theory.
278
A. Kakas et al. Argumentation for Propositional Logic and Nonmonotonic Reasoning
Example 7. For T = {}, N ACC T ({¬( _¬ )}, {}) holds, as illustrated in figure 3.
Also, trivially, N ACC T ({ ^ ¬ }, {}) holds, since it is attacked by the empty
argument.
{¬( _O ¬ )}
{¬KS }
{O}
{¬( _ ¬ )}
Fig. 3. Illustration of N ACC T ({¬( _ ¬ )}, {}) for example 7.
A novel, alternative notion of entailment can be defined for theories that are
directly consistent in terms of the (non-) acceptability semantics for AL frame-
works, as follows:
Definition 7. Let T be a directly consistent theory and 2 L. Then is AL-
entailed by T (denoted T |=AL ) i↵ ACC T ({ }, {}) and N ACC T ({¬ }, {}).
This is motivated by the argumentation perspective, where an argument is held
if it can be successfully defended and it cannot be successfully objected against.
In the remainder of the paper we will study properties of |=AL and discuss
extensions thereof to support NMR.
5 Basic Properties
The following result gives a core property of the notion of AL-entailment wrt the
notion of direct derivation in Propositional Logic, for directly consistent theories.
Proposition 1. Let T be a directly consistent theory and 2 L such that
T `M RA . Then T |=AL .
Proof: Let a = T [ be any attack against { }, i.e. T [ { } [ `M RA ?. Since
T `M RA then T [ `M RA ?. Since T is directly consistent, 6= {}. Hence
any such a can be defended against by the empty argument. Since ACC T ({}, ⌃),
for any ⌃ ✓ L, then ACC T ({ }, {}) holds. Moreover, since T `M RA , neces-
sarily T [ {¬ } `M RA ?. Hence the empty argument attacks {¬ } and thus
N ACC T ({¬ }, {}) holds. QED
279
A. Kakas et al. Argumentation for Propositional Logic and Nonmonotonic Reasoning
The following theorem shows (one half of) the link of AL with Propositional
Logic by showing how the RA rule, deleted from the ND proof system within
`M RA , can be recovered back through the notion of non-acceptability.8
Theorem 1. Let T be a directly consistent theory and 2 L. If N ACC T ({ }, {})
holds then there exists a RAND derivation of ¬ from T .9
d↵ d↵
d¬ d
?c c(↵)
¬¬ ↵^
?c
↵^ ¬
?c ?c
¬↵ ¬↵
Fig. 4. Two RAND derivations of ¬↵ in example 4: d1 (left) and d2 (right).
For example, the RAND derivation corresponding to the proof of N ACC T ({↵},{})
in figure 1 is d1 in figure 4.10 Here, the inner RAND derivation in d1 corresponds
to the non-acceptability of the defence {¬ } against the attack { } against {↵}.
Derivation d2 in figure 1 is an alternative RAND of ¬↵, but this cannot be ob-
tained from any proof of N ACC T ({↵}, {}), because there is a defence against
the attack { } given by the empty set (in other words, d2 does not identify a
useful attack, that cannot be defenced against, for proving non-acceptability).
6 AL for Propositional Logic
The following result gives a core property of the notion of non-acceptability for
classically consistent theories.
Proposition 2. Let T be classically consistent and 2 L. If N ACC T ({¬ }, {})
holds then ACC T ({ }, {}) holds.
Proof: By theorem 1, since N ACC T ({¬ }, {}), then T ` . Suppose, by con-
tradiction, that ACC T ({ }, {}) does not hold. Then N ACC T ({ }, {}) holds
(since N ACC T ({ }, {})=¬ACC T ({ }, {})) and by theorem 1 there is a RAND
derivation of ¬ from T and thus T ` ¬ . This implies that T is classically
8
The other half of this result shows how (under some conditions) a RAND derivation
of ¬ implies N ACC T ({ }, {}), proven in [12].
9
The proof of this theorem is included in [13].
10
Here and elsewhere in the paper, c( ), for any 2 L, indicates that is the hypoth-
esis of an ancestor sub-derivation copied within the current sub-derivation.
280
A. Kakas et al. Argumentation for Propositional Logic and Nonmonotonic Reasoning
inconsistent: contradiction. Hence ACC T ({ }, {}) holds. QED
Thus, in Propositional Logic, trivially AL-entailment reduces to the notion of
non-acceptability:
Corollary 1. Let T be a classically consistent theory and 2 L. Then T |=AL
i↵ N ACC T ({¬ }, {}).
The following property sanctions that AL-entailment implies classical derivabil-
ity:
Corollary 2. Let T be a classically consistent theory and 2 L. If T |=AL
then T ` .
Proof: If N ACC T ({¬ }, {}), then, by theorem 1, there is a RAND derivation
of ¬¬ from T and thus T ` . QED
This corollary gives that consequences of a classically consistent theory under
|=AL are classical consequences too. Proposition 1 sanctions that direct conse-
quences are not lost by |=AL . However, in general not all classical consequences
are retrieved by |=AL , namely the converse of corollary 2 does not hold, as the
following example shows.
Example 8. Let T = {¬↵}. We show that T 6|=AL ↵ ! by showing that
N ACC T ({¬(↵ ! )}, {}) does not hold. A standard ND derivation of ↵ !
from T is:
d↵
d¬
c(↵)
¬↵ from T
?c
¬¬ RA
c ¬E
↵! !I
This does not help with determining N ACC T ({¬(↵ ! )},{}). This is related
to the fact that the inconsistency in the inner RAND derivation of ¬¬ is de-
rived without the need of the hypothesis, ¬ , of this RAND derivation. In gen-
eral, any RAND derivation of ¬¬(↵ ! ) (and hence of ↵ ! ) from this
theory, T , contains such a RAND sub-derivation relying on the inconsistency
of the copy of ↵ from a (!I) sub-derivation, with ¬↵ from T . This means that
N ACC T ({¬(↵ ! )}, {}) cannot hold, since, otherwise, by theorem 1, we would
have a RAND derivation of ¬¬(↵ ! ) without such a sub-derivation. This is be-
cause by construction of the corresponding RAND derivation given by theorem 1
the existence of such a RAND sub-derivation would violate the non-acceptability
of some defence in the assumed non-acceptability of ¬(↵ ! ).
This example shows, in particular, that implication is not material implication
under |=AL .
281
A. Kakas et al. Argumentation for Propositional Logic and Nonmonotonic Reasoning
7 AL for Non-Monotonic Reasoning-Discussion
Here we present a first investigation on how AL can be used as a basis for NMR
unifying classical and defeasible reasoning, in the context of the well known
tweety example. Our examination is based on the (expected) need to extend AL
with preferences and the observation that when a theory is (directly) inconsis-
tent we have the possibility to reason with its sub-theories, considering these as
arguments that support their conclusions under AL. For the illustration we use
the following (abbreviations of) sentences:
bf = [bird(tweety) ! f ly(tweety)]
p¬f = [penguin(tweety) ! ¬f ly(tweety)]
pb = [penguin(tweety) ! bird(tweety)]
¬f = [¬f ly(tweety)] p = [penguin(tweety)]
¬b¬p = [¬bird(tweety) ! ¬penguin(tweety)]
Example 9. Let T = { bf , pb , ¬f } (T is classically consistent). It is easy
to see that T |=AL ¬bird(tweety) as {} attacks {bird(tweety)} and therefore
N ACC T ({bird(tweety)}, {}). Similarly, T |=AL ¬penguin(tweety). In absence
of other information, we believe that these conclusions are legitimate/desirable.
Note that AL does not distinguish default rules and facts and it supports con-
trapositive reasoning with the single form of implication it allows. In example 9,
default logic [19] would derive the same conclusions only by labelling T as facts,
but would not derive either conclusion if the first sentence were labelled as a
default rule, as conventional.
Example 10. Let T = { bf , pb , ¬f , p¬f } (T classically consistent, obtained
by adding p¬f to T in example 9). As in example 9, T |=AL ¬bird(tweety) and
T |=AL ¬penguin(tweety). From a commonsense reasoning perspective, this is
counter-intuitive, as it disregards the newly added sentence and the alternative
possibility for ¬f ly(tweety) it supports, namely penguin(tweety).
By comparison, default logic with the first and last sentences in T labelled as
default rules (as conventional) would (sceptically) derive no conclusion as to
whether tweety is (or not) a bird or penguin. Arguably, this is too sceptical a
behaviour. Note that we have the same counter-intuitive behaviour of deriving
¬penguin(tweety) when the sentence ¬f ly(tweety) is deleted from the theory of
example 10. In order to accommodate within AL the intuitive kind of reasoning
pointed out for these examples, we can extend AL with priorities over sentences,
so that, in particular, exceptions may override rules, in the spirit of prioritised
default logic [4, 5] and other approaches to supporting reasoning with priori-
ties [7]. In our illustration, these priorities may be drawn from the partial order
¬f , p , pb , ¬b¬p > p¬f > bf . The challenge is to incorporate these priorities
without imposing a separation amongst sentences (as done instead in prioritised
and standard default logic) and without imposing a specific structure on the
defeasible knowledge (the default rules) so as to achieve, e.g., the behaviour of
282
A. Kakas et al. Argumentation for Propositional Logic and Nonmonotonic Reasoning
AL in example 9. In example 10, the given priorities may be used to identify the
sub-theory { pb , ¬f , p¬f } as the strongest and thus entail penguin(tweety).
By introducing priorities we can also use preference-based argumentation,
as in e.g. [14, 18], to distinguish between strengths of AL-entailment from sub-
theories, and, in particular, allow for stronger sub-theories to dominate, as
illustrated by the following example:
Example 11. Let T ={ bf , p , ¬f , ¬b¬p } (T is directly but not classically con-
sistent). Then, correctly, in absence of other information, T 6|=AL bird(tweety)
and T6|=AL¬bird(tweety). The sub-theories T1 = { bf , ¬f } and T2 = { p , ¬b¬p }
AL-entail ¬bird(tweety) and bird(tweety) respectively and hence dispute each
other. If we now take into account ¬b¬p > bf , then, under a preference-based
argumentation approach, T2 would dominate T1 and thus T would correctly
entail bird(tweety).
The core technical challenge of using priorities over sentences is to under-
stand how these could influence the reasoning by contradiction a↵orded by RA
in AL. In our illustrative setting we want the priorities (especially p¬f >
bf ) to restrict the application of RA. There are other cases, however, where
RA gives intuitive results and should not be restricted. For example, from the
theory {bird(tweety), pb , p¬f , bf } with pb > p¬f > bf we expect that
¬penguin(tweety) is entailed since f ly(tweety) is an intuitive default conclusion
of this theory and then, by RA, penguin(tweety) cannot be entailed (as otherwise
through the stronger sentence of p¬f , the sentence ¬f ly(tweety) would follow).
Similarly, given the theory {f ly(tweety), pb , p¬f , bf } with pb > p¬f > bf ,
we expect that ¬penguin(tweety) is entailed as penguin(tweety) would give
¬f ly(tweety) due to the higher strength of p¬f . To accommodate such cases
it may be necessary to use the priority information more tightly within the
definition of AL, i.e. within the definition of (non-)acceptability.
8 Related Work
AL is based on a notion of acceptability of arguments which is in the same
spirit as that in [8, 11] for capturing the semantics of negation as failure in
Logic Programming. These notions of acceptability are global in the sense that
acceptable and non-acceptable arguments are all defined at the same time. This
view has also recently been taken in [6, 20] where the argumentation semantics
is defined through the notion of a global labelling of arguments as IN, OUT or
UNDECIDED.
The link of argumentation to NMR has been the topic of extensive study for
many years. Most of these studies either separate in the language the classical
reasoning from the defeasible part of the theory (e.g. in Default Logic) or restrict
the classical reasoning (e.g. in LP with NAF) or indeed as in the case of circum-
scription [17] the theory is that of classical logic but a complex prescription of
model selection is imposed on top of the classical reasoning.
283
A. Kakas et al. Argumentation for Propositional Logic and Nonmonotonic Reasoning
Recently, [2] proposed an argumentation framework based upon classical logic
with the aim (that we share) to use argumentation to reason with possibly incon-
sistent classical theories, beyond the realms of classical logic. In their approach,
arguments are defined in terms of sub-theories of a given (typically inconsistent)
theory and they have minimal and consistent supports (wrt the full classical con-
sequence relation). Attacks are defined in terms of a notion of canonical undercut
that relies on arguments for the negation of the support of attacked argument.
Further, the evaluation of arguments is given through a related tree structure of
defeated or undefeated nodes.
Other works that aim for a tighter link between classical and defeasible rea-
soning include the work of Amgoud and Vesic [1], studying the problem of han-
dling inconsistency using argumentation with priorities over sentences, and [21],
who have adapted the approach of [2] to Description Logic and have proposed
an argumentation-based operator to repair inconsistencies. Our approach di↵ers
from these works in that it starts with providing an alternative understanding
of Propositional Logic in argumentation terms on which to base any further de-
velopment of reasoning with inconsistent or defeasible theories. In comparison
with our approach, these other works can be seen more as a form of belief re-
vision, based on argumentation, for classically inconsistent theories rather than
a re-examination of classical logic through argumentation to provide a uniform
basis for classical and defeasible reasoning.
9 Conclusion and Future Work
We have presented Argumentation Logic (AL) and shown how it allows us to
understand classical reasoning in Propositional Logic in terms of argumenta-
tion. Its definition rests on capturing semantically the Reductio ad Absurdum
rule through a suitable notion of acceptability of arguments. One property of
the ensuing AL is that the interpretation of implication is di↵erent from that of
material implication. Further results on the relationship between AL and Propo-
sitional Logic including how AL can completely capture the entailment of PL
are given in [12].
Given the significant role that argumentation has played in understanding
under a common framework NMR in AI we have examined the problem of how
we could unify classical reasoning and NMR within the framework of AL. In this
context, we have considered the following questions: How could we use AL as
the underlying logic to build a NMR framework? Can AL with its propositional
language provide a single representation framework for classical and defeasible
reasoning without any distinctions on the type of sentences allowed in a given
theory? In particular, can we understand AL as a NMR framework with sen-
tences that would behave as default rules but also as classical rules, with a form
of contrapositive reasoning with these rules allowed? In this paper we have iden-
tified this problem and the challenges it poses, and studied these questions in
the context of examples.
284
A. Kakas et al. Argumentation for Propositional Logic and Nonmonotonic Reasoning
Our preliminary investigation suggests the need for an extension of AL to ac-
commodate preferences amongst sentences. Many existing frameworks for NMR
use, either explicitly or implicitly, preferences to capture defeasible reasoning,
e.g. [4, 5] for Default Logic [19]. Also many frameworks of argumentation rely on
some form of preference between arguments, e.g. [14, 15, 18] to capture a notion
of (relative) strength of arguments through which the attack relation between
arguments can be realized. One way therefore to study this problem of inte-
grating classical and defeasible reasoning is to use some form of preference on
the sentences of AL theories, and adapt existing approaches of reasoning with
preferences to AL.
A Appendix: Natural Deduction
We use the following rules, for any , , 2 L:
, ^ ^
^I : ^E : ^E : _I :
^ _
d ... c ¬¬ d . . . ?c
_I : !I : ¬E : ¬I :
_ ! ¬
_ , d . . . c, d . . . c , !
_E : !E:
where d⇣, . . .c is a (sub-)derivation with ⇣ referred to as the hypothesis. ¬I is
also called Reduction ad Absurdum (RA).
References
1. Amgoud, L., Vesic, S.: Handling inconsistency with preference-based argumen-
tation. In: Deshpande, A., Hunter, A. (eds.) SUM. Lecture Notes in Computer
Science, vol. 6379, pp. 56–69. Springer (2010)
2. Besnard, P., Hunter, A.: Elements of Argumentation. MIT Press (2008)
3. Bondarenko, A., Dung, P.M., Kowalski, R.A., Toni, F.: An abstract,
argumentation-theoretic approach to default reasoning. Artificial Intelligence 93(1–
2), 63–101 (1997)
4. Brewka, G.: Reasoning about priorities in default logic. In: Hayes-Roth, B., Korf,
R.E. (eds.) AAAI. pp. 940–945. AAAI Press / The MIT Press (1994)
5. Brewka, G., Eiter, T.: Prioritizing default logic. In: Hölldobler, S. (ed.) Intellectics
and Computational Logic. Applied Logic Series, vol. 19, pp. 27–45. Kluwer (2000)
6. Caminada, M.W.A., Gabbay, D.M.: A logical account of formal argumentation.
Studia Logica 93(2-3), 109–145 (2009)
7. Delgrande, J.P., Schaub, T., Tompits, H., Wang, K.: A classification and survey of
preference handling approaches in nonmonotonic reasoning. Computational Intel-
ligence 20(2), 308–334 (2004)
8. Dung, P.M., Kakas, A.C., Mancarella, P.: Negation as failure revisited. In: Tech-
nical Report, University of Pisa (1992)
9. Dung, P.M., Thang, P.M., Toni, F.: Towards argumentation-based contract nego-
tiation. In: Besnard, P., Doutre, S., Hunter, A. (eds.) Proceedings of the Second
International Conference on Computational Models of Argument (COMMA’08).
Frontiers in Artificial Intelligence and Applications, vol. 172, pp. 134–146. IOS
Press (2008)
285
A. Kakas et al. Argumentation for Propositional Logic and Nonmonotonic Reasoning
10. Dung, P.: On the acceptability of arguments and its fundamental role in non-
monotonic reasoning, logic programming and n-person games. Artif. Intell. 77,
321–357 (1995)
11. Kakas, A.C., Mancarella, P., Dung, P.M.: The acceptability semantics for logic
programs. In: ICLP. pp. 504–519 (1994)
12. Kakas, A., Toni, F., Mancarella, P.: Argumentation logic. Tech. rep., Department
of Computer Science, University of Cyprus, Cyprus (April 2012)
13. Kakas, A., Toni, F., Mancarella, P.: Argumentation for propositional logic and
nonmonotonic reasoning. In: Working notes of the 11th International Symposium
on Logical Formalizations of Commonsense Reasoning (2013)
14. Kakas, A.C., Moraitis, P.: Argumentation based decision making for autonomous
agents. In: The Second International Joint Conference on Autonomous Agents &
Multiagent Systems, AAMAS 2003, July 14-18, 2003, Melbourne, Victoria, Aus-
tralia, Proceedings. pp. 883–890. ACM (2003)
15. Kowalski, R.A., Toni, F.: Abstract argumentation. Artificial Intelligence and Law
4(3–4), 275–296 (1996)
16. Lin, F., Shoham, Y.: Argument systems: A uniform basis for nonmonotonic rea-
soning. In: Brachman, R.J., Levesque, H.J., Reiter, R. (eds.) Proceedings of the 1st
International Conference on Principles of Knowledge Representation and Reason-
ing (KR’89). Toronto, Canada, May 15-18 1989. pp. 245–255. Morgan Kaufmann
(1989)
17. McCarthy, J.: Circumscription - a form of non-monotonic reasoning. Artificial In-
telligence 13(1-2), 27–39 (1980)
18. Modgil, S., Prakken, H.: A general account of argumentation with preferences.
Artificial Intelligence (2012), in Press
19. Reiter, R.: A logic for default reasoning. Artificial Intelligence 13(1-2), 81–132
(1980)
20. Wu, Y., Caminada, M.: A labelling-based justification status of arguments. Studies
in Logic 3(4), 12–29 (2010)
21. Zhang, X., Zhang, Z., Xu, D., Lin, Z.: Argumentation-based reasoning with incon-
sistent knowledge bases. In: Canadian Conference on AI. pp. 87–99 (2010)
286