2.Preliminaries
In the current section, we briefly restate some of the basic concepts in formal argumentation theory, including strong admissibility. For current purposes, we restrict ourselves to finite argumentation frameworks. We note that the focus on finite structures is not imposed in Dung’s original work and some study of infinite frameworks has been carried out, e.g. on realizability by Baumann and Spanring [5], modelling and description of infinite systems in Baroni et al. [2].
Definition 1.
(Dung [8]) An argumentation framework is a pair (X,A) where X is a finite set of entities, called arguments, and A a binary relation on X. For any p,q∈X we say that p attacks q if ⟨p,q⟩∈A.
Definition 2.
Let (X,A) be an argumentation framework, x∈X and S⊆X. We define {x}+ as {y∈X∣x attacks y}, {x}− as {y∈X∣y attacks x}, S+ as ⋃{{x}+∣x∈X}, and S− as ⋃{{x}−∣x∈X}. The set S is said to be conflict-free if S∩S+=∅. A set S is said to defend x iff {x}−⊆S+. The characteristic function F:2X→2X is defined as F(S)={x∣S defends x}.
Definition 3.
Let (X,A) be an argumentation framework. A subset S of X is said to be:
an admissible set if S is conflict-free and S⊆F(S);
a complete extension if S is conflict-free and S=F(S);
a grounded extension if S is the smallest (w.r.t. ⊆) complete extension;
a preferred extension if S is a maximal (w.r.t. ⊆) complete extension.
We use the notation
cf for the collection of conflict-free sets and, similarly,
adm,
com,
gr and
pr respectively to denote the forms above so that, e.g.
adm(H) describes those subsets of arguments in
H that are admissible, i.e.
S∈adm(H) if and only if
S is admissible.
It is well known (being illustrated in Dung’s original paper [8]) that for any af, H,
pr(H)⊆adm(H)⊆cf(H).
Furthermore while
com(H)⊆adm(H) (“every complete set is admissible”) the converse does not necessarily hold so that one may have admissible sets that are not complete.
The examples presented above are just a small selection of those approaches that have been studied. We refer the interested reader to the treatment of Baroni, Caminada and Giacomin [1] for a comprehensive overview. The concept of strong admissibility was first introduced by Baroni and Giacomin [3]. For current purposes we will, however, apply the equivalent definition of Caminada [6].
Definition 4.
Let (X,A) be an argumentation framework. A subset S of X is strongly admissible if every x∈S is defended by some T⊆S∖{x}, T being also strongly admissible.
It can be shown that each strongly admissible set is an admissible subset of the grounded extension [7].
To illustrate, consider the example in Fig. 1 from Caminada [6].
Fig. 1.
We have
{∅,{A},{D},{A,C},{A,D},{A,C,D},{A,C,F},{D,F},{A,C,D,F}}
as the strongly admissible sets. The grounded extension of this framework being
{A,C,D,F}. Every strongly admissible set is a subset of
{A,C,D,F}. Notice that the sets
{{G},{H},{F},{C,H},{C,H,F}}
are all admissible, however none of these are
strongly admissible.
3.Signatures and realizability
An arbitrary semantics, σ, describes a set of subsets of X so that for an af, H,
σ(H)={S⊆X:S satisfies the criteria of σ}.
For example, with
σ=cf and
H=(X,A), we have
cf(H)={S⊆X:S+∩S=∅}.
Definition 5.
The signature of a semantics σ, denoted Σσ is
Σσ={S⊆2X:∃H with σ(H)=S }.
The counterpart to the concept of signature is that of being realizable.
Definition 6.
Let S⊆2X, that is to say a set of subsets of X. The set S is said to be realizable with respect to a semantics σ if there is an af, H=(Z,A) for which X⊆Z and σ(H)=S.
Notice that in this definition we allow arguments z∈Z which are not acceptable with respect to the conditions specified by σ: so-called auxiliary arguments. The form whereby such additional arguments are not permitted is dubbed “compact realizability” and has been studied (together with divers other formulations) in Baumann [4].
With regard to these notions of signature and realizability the central question of interest, discussed in Dunne et al. [10,11] is the following:
For an argumentation semantics, σ, describe necessary and sufficient conditions, Π:22X→{⊤,⊥}, under which,
a. For all afs H, Π(σ(H)) holds. (signature)
b. For all S⊆2X that satisfy Π(S), there is an af H for which σ(H)=S. (realizable)
In [
11] characterization of such conditions are presented for (among others)
σ∈{adm,com,pr}, i.e. admissible, complete, and preferred semantics.
In the current work we consider the case of strong admissibility denoting the relevant semantics as σ=str.
It turns out that we may identify some requirements for membership in Σstr from a number of properties already known from Baroni and Giacomin [3] and Caminada [6].
We first introduce some further notational ideas.
Definition 7.
As is standard we distinguish N (the set of positive integers {1,2,3,…}) and W (the set of non-negative integers {0}∪N).
Let S be a subset of 2X. The set which we denote [S] is the system S[k] formed by setting S[0]=S and for k>0
S[k]=⋃(P,Q)∈S[k−1]×S[k−1]{{P∪Q}}
until the point
S[k]=S[k−1] is reached.
We say that S is []-closed if S=[S], i.e. k=1 in the process just described since S=S[0] (by definition) and S[0]=S[1].
As a small example of the process of forming [S] suppose we have
S={{1},{2},{3,4},{3,4,5}},S[0]={{1},{2},{3,4},{3,4,5}},S[1]=S[0]∪{{1,2},{1,3,4},{1,3,4,5},{2,3,4},{2,3,4,5}},S[2]=S[1]∪{{1,2,3,4},{1,2,3,4,5}},S[3]=S[2].
A final idea, is that of a decomposition of a system of sets.
Definition 8.
Given a system of sets S⊆2X its r-partial decomposition, denoted Δr(S) is formed as an ordered sequence of subsets of S which we denote (S(0),S(1),…,S(r)) with the S(i)⊆S pairwise disjoint, i.e. S(i)∩S(j)=∅.
Δr(S) is formed from S by applying the following process.
If ∅∉S then Δr(S)=∅. Otherwise,
Δr(S)=({∅})if r=0 and ∅∈S,(Δr−1(S);S(r))if r>0.
In this
Δr−1(S)=(S(0),S(1),…,S(r−1)) the
(r−1)-partial decomposition of
S. The system of sets in
S(r) (
r>0) contains
all subsets of
S of the form
{{{y}∪T}:y∉⋃i=0r−1⋃U∈S(i)U and T is ⊆-minimal in [⋃i=0r−1S(i)] with y∪T∈S}.
If
∅∉S or the process used to define
S(r) cannot be applied further then
S(r)=∅. Using this convention every system of subsets of
2X has some
r-partial decomposition, although for
r large enough (
r>|X| for example),
S(r)=∅.
Definition 9.
We say that S⊆2X is decomposable if for some r∈W
S=[⋃i=0rS(i)]
with
(S(0),…,S(r)) formed using
S according to the prescription given. If
S is decomposable we denote its full decomposition by
Δ(S) without indicating
r.
Again, as a small illustration, suppose that
S={∅,{1},{2},{1,3},{2,4},{1,3,5},{2,4,6},{1,3,5,7},{1,2,3,4,7}}.
We have,
S(0)={∅}.
To form
S(1) we can only use
single element sets from
S, leading to
S(1)={{1},{2}}.
Notice that
{1}∪∅∈S and that
∅∈[S(0)] is a minimal such set. We further observe that if there are no sets
S∈S for which
|S|=1 then
S has (at best) a 0-partial decomposition.
Continuing this example, in order to form S(2) we must identify those minimal sets T∈[S(0)∪S(1)] together with those single elements, x, for which {x}∪T∈S. In the example we find these to be
{1} with 3,{2} with 4
so giving
S(2)={{1,3},{2,4}}.
In forming
S(3) the range of sets we may choose from are those
T∈[S(0)∪S(1)∪S(2)] and we require single elements,
x, with which
{x}∪T∈S and
T is a minimal set. Here we find
{1,3} with 5,{2,4} with 6
giving
S(3)={{1,3,5},{2,4,6}}.
Notice that {1,2,3,4,7}, although in S with {1,2,3,4}∈[S(0)∪S(1)∪S(2)] cannot be included in S(3): the reason being because of the set {1,3,5,7} in S. The element, 5, is first introduced in S(3) so any sets in S containing 5 and some as yet unrecovered item (such as 7) cannot be built until 5 is available. If it were the case that {1,3,5,7}∉S then we could add {1,2,3,4,7} to S(3) via {1,2,3,4}∈[S(0)∪S(1)∪S(2)].
The final stage of the decomposition of S forms S(4) as
S(4)={{1,2,3,4,7},{1,3,5,7}}.
We stress the distinction between S(k)=∅ and S(0)={∅}: the former case describes the situation where either no further expansion (or any expansion whatsoever) via the process of Definition 8, is possible. Thus if ∅∉S then S(k)=∅ for all k∈W. Similarly, noting the requirement for new members of X to be used when progressing from S(k) to S(k+1), it is easily seen that S(r)=∅ whenever r>|X|.
We further note the requirement that T witnessing {y}∪T∈S(k) is minimal with respect to ⊆, e.g. if y is a new element introduced in forming S(k), and {{u,v,w},{u,v},{v,w}}⊆[S(k−1)] then S(k) could contain {u,v,y} or {v,w,y} or {{u,v,y},{v,w,y}}: in all three cases, however, S(k) would not contain {u,v,w,y}. Similarly were {u,v,w,y}∈S(k) then neither {u,v,y} nor {v,w,y} would be.
Two properties of decomposable systems are given in the next lemmata.
Lemma 1.
Let S⊆2X. For all k∈W, Δk(S) is unique.
Proof.
Let S⊆2X have an r-partial decomposition
Δr(S)=(S(0),S(1),…,S(r)).
Suppose, for the sake of contradiction, that
(T(0),T(1),…,T(r)) is an
r-partial decomposition of
S differing from
Δr(S).
Choose p∈W to be the least value for which S(p)≠T(p). Since it is the case that S(p)≠T(p) we must have some subset S∈S for which S∈S(p) but S∉T(p) (or vice-versa).
By definition S∈S(p) indicates that, in addition to S∈S, we have S=U∪{y}, U∈[⋃k=0p−1S(k)] and no strict subset V of U for which V∈[⋃k=0p−1S(k)] and V∪{y}∈S. Furthermore
y∉⋃i=0p−1⋃W∈S(i)W.
We have chosen
p as the smallest value for which
S(p)≠T(p) and so
S(p−1)=T(p−1). In consequence,
[⋃k=0p−1S(k)]=[⋃k=0p−1T(k)] and, hence,
U is a minimal set (wrt ⊆) in
[⋃k−0p−1T(k)] for which
{y}∪U∈S. It is also the case that
y∉⋃i=0p−1⋃W∈T(i)W.
The inclusion of
y∪U as part of
S(p) or
T(p) is dependent only on
S (since
U must be a minimal set for which
y∪U∈S) and the structure of
[⋃k=0p−1S(k)] (respectively
[⋃k=0p−1T(k)]). The underlying set
S is the same regardless of how it is decomposed. We have, however, chosen
p as the least value at which
S(p)≠T(p). Now we obtain the required contradiction since in order for
S(p) to differ from
T(p) would require
[⋃i=0p−1S(p−1)]≠[⋃i=0p−1T(p−1)]
so contradicting the choice of
p.
We conclude that the r-partial decomposition of S is unique. □
Lemma 2.
Let (S(0),…,S(r)) be the r-partial decomposition of S and Y be
Y=⋃i=1r⋃T∈S(i)T={x1,x2,…,xt}.
Then Y may be partitioned into disjoint sets (T1,T2,…,Tk) each having an associated qi with
1⩽q1<q2<⋯<qk=r
and for all 1⩽p<k
⋃j=1pTj=⋃i=1qp⋃S∈S(i)S
but
⋃j=1pTj≠⋃i=1qp−1⋃S∈S(i)S;⋃j=1pTj≠⋃i=1qp+1⋃S∈S(i)S.
Proof.
The partition simply follows the ordering by which individual elements of X are added to S(i) so that,
T1={y:{y}∈S},T2={y:{y}∪U∈S,U⊆T1,y∉T1,and U is a minimal such subset of T1},⋯
and, in general,
Ti = {y:y∪U∈S,U⊆⋃j=1i−1Tj,y∉⋃j=1i−1Tj,and U minimal}.
□
Before presenting our main results it may be helpful to look at two example systems both of which are decomposable.
Consider S defined as
{∅,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3},{1,4},{1,2,4},{1,3,4},{1,2,3,4},{2,3,5},{1,2,3,5},{1,2,3,4,5}}.
This has a 2-decomposition as
S(0)={∅},S(1)={{1},{2},{3}},S(2)={{1,4},{2,3,5}}.
Each set in
S(2) is formed as the union of a new argument (4 or 5) with a set in
[S(1)]. Notice that
{1,2,3,4,5}∉S(2) but is in
[S(2)] (via
{1,4}∪{2,3,5}).
We cannot defer adding {2,3,5} to a later level: the definition states that since we are able to include {2,3,5} in S(2) it is required to do so.
The system [S∪{{1,4,5}}], is also decomposable, however, now the decomposition would be
S(0)={∅}S(1)={{1},{2},{3}}S(2)={{1,4}}S(3)={{1,4,5},{2,3,5}}
Now we cannot add
{2,3,5} to
S(2) since we cannot add
{1,4,5} at the same time:
{1,4}∉[S(1)] and
{1,5}∉[S(1)] and since 1 occurs as an element of sets in
S(1) a decomposition including
{1,4,5} would need
{1,4}∈[S(1)].
It is also the case that both systems of sets are in Σstr as can easily be seen by inspecting Fig. 2.
Fig. 2.
Realization of str(H) for example system.
The implied partitions from Lemma 2 being
({1,2,3};{4,5})first case,({1,2,3};{4};{5})second case.
On the other hand, a system such as
{∅,{1},{1,2},{1,3,4},{1,2,3,4}}
is not decomposable (this system, however, is
[]-closed) since there is no way of including
{1,3,4} in a decomposition.
Applying the process described in Definition 8 would yield
S(0)={∅},S(1)={{1}},S(2)={{1,2}}
and no further expansion is possible.
Were the set {1,3} to be added the resulting system would be decomposable. Applying the process described in Definition 8 would then yield
S(0)={∅},S(1)={{1}},S(2)={{1,2},{1,3}},S(3)={{1,3,4}}.
4.Strongly admissible systems are decomposable
With the concept of decomposability we obtain Theorem 1. We note that the partition structure and its properties in relationship to the characteristic function are used (although not explicity phrased as such) in the algorithm of Caminada and Dunne [7] by which verification of a set as strongly admissible is shown to be decidable in polynomial time.
Theorem 1.
Let X be a finite set of n arguments and S⊆2X.
If S∈Σstr then S is decomposable.
Proof.
Consider any S∈Σstr and let H=(X,A) be any af witnessing the realizability of S, i.e. for which str(H)=S.
To begin consider the following partition of
{x∈X:∃S∈str(H) with x∈S}.
This partition is formed as
(P0;P1;…;Pt) with
Pi=FHi and
FHi=∅if i=0,FH(FHi−1)∖FHi−1if i>0.
Here
FH(U) is the characteristic function of conflict-free sets
U with respect to
H=(X,A) so that
FH(U)={x∈X:∀y∈{x}−∃zy∈Us.t.⟨zy,y⟩∈A}.
Notice that this
is a partition of
{x∈X:∃S∈str(H) with x∈S} and, furthermore the grounded extension,
GE(H) satisfies,
GE(H)=⋃i=0tPi.
This partition will form the basis for constructing the decomposition of
S as
(S(0),S(1),…,S(t)).
Fix
S(0)={∅} and
S(1)={{x}:x∈P1}. Every
{x}∈S(1) satisfies
x∈FH1=FH(∅) so not only is
{x}∈S, i.e.
str(H) but also every subset of
P1 (such corresponding to some union of a subset of
S(1)) is in
S.
Now suppose we continue this construction relative to elements (S(k−1), k⩾2) already built (via the template specified in Definition 8) and the system S. Consider which sets would be included in S(k). We have S∈S(k) whenever S=y∪U and
y∉⋃i=0k−1⋃T∈S(i)T
and
U is a ⊆-minimal set in
[⋃i=0k−1S(i)] for which
y∪U∈S.
We now argue that for all k, the proposition, Q(k) holds, where
Q(k)≡{(S∈S and S⊆⋃i=0kPi)⇔S∈[⋃i=0kS(i)]}.
This will establish the Theorem:
S∈Σstr⇒S is decomposable.
To see this is the case, notice that Q(k) treats S=str(H) as a sequence of sets built by adding single arguments, y, (according to the partition (P0;P1;…;Pr) described earlier) to (minimal) strongly admissible sets, S, that defend y, i.e. have y∈FH(S). Noting the closure of str(H) under set union, so that S∈str(H) and T∈str(H) leads to S∪T∈str(H), applying the closure operation […] to S(i) ensures that all S∈[S(i)] are also in str(H).
We have already shown that Q(1) and Q(0) hold.
Suppose, as an inductive hypothesis, we have demonstrated Q(k) for all 0⩽k⩽r−1 for some r⩽t (t being the number of classes in the partition of {x∈X:∃S∈str(H) with x∈S} from Lemma 2).
Consider Pr. By definition, Pr contains FH(FHr−1)∖FHr−1 and (from the construction) no argument y∈Pr occurs in
⋃i=0r−1⋃T∈S(i)T.
From the fact that
y∈FH(FHr−1)∖FHr−1 we can find some strongly admissible subset,
U, using
only arguments in
⋃i=0r−1Pi which defends
y. To see this just work back from
k=r−1 constructing
Wr−1 (the subset of
Pr−1 that defends
y which, since
y∈FH(FHr−1)∖FHr−1, is well-defined); then
Wr−2 as the subset of
Pr−2 that collectively defends
Wr−1 and, in general,
Wj as the subset of
Pj that defends
Wj+1. The set
⋃j=0r−1Wi
is in
str(H) (thence also in
S). Furthermore
every set,
U, for which
U is formed as the union of sets
{Vi:Vi⊆Pi with Vi⊆FH(Vi−1)∖Vi−1 (and 1⩽i⩽r−1)}
is in
str(H) and thus in
[⋃i=0r−1S(i)]
from the inductive assumption
Q(r−1). The argument
y is such that
y∪U∈S and we have just seen that this can be rewritten as
y∪⋃i=0r−1ViVi⊆Pi.
Now, since we can find
some set,
U with
y∪U∈S and
U⊆⋃i=0r−1Pi we can certainly find a
minimal such set. Furthermore such minimal sets can be divided by exactly the same process, i.e. expressed as the union of sets
{Zi:Zi⊆Pi with Zi⊆FH(Zi−1)∖Zi−1, 1⩽i⩽r−1}.
We deduce that for every
y∈Pr we can identify minimal subsets
U1,…,Ur for which
y∪Ui∈S and
S(r) including
y∪Ui. Hence every set formed in
[⋃i=0rS(i)]
is in
str(H).
We have shown,
S∈[⋃i=0rS(i)]⇒S∈S.
To complete the proof we need
S∈str(H)⇒S∈[⋃i=0rS(i)].
We have already demonstrated the inductive base:
S⊆P1 (the only case, other than
S=∅ for which
S∈str(H) and
S∈[S(0)∪S(1)]). Hence assume, as inductive hypothesis, it has been shown for all
0⩽k⩽r−1 (
r⩽t) that
(S∈str(H) and S⊆⋃i=0r−1Pi)⇒S∈[⋃i=0r−1S(i)].
We extend this to argue that
(S∈str(H) and S⊆⋃i=0rPi)⇒S∈[⋃i=0rS(i)].
Let
S∈str(H) with
S⊆⋃i=0rPi. If
S∩Pr=∅ then no further argument is required (the case has been dealt with under our Inductive assumptions). Thus consider
S∩Pr={y1,y2,…,ym}.
We know that – by the definition of strongly admissible – there is some subset,
U of
S∖{y1,…,ym} such that
U∈str(H) and, furthermore
yi∈FH(U) for each
i. Notice that from the construction of
Pr it cannot be the case that
yi is needed to defend attacks upon
yj. We know that
U∈str(H) and
U⊆⋃i=0r−1Pi. Therefore, from the inductive hypothesis
U∈[⋃i=0r−1S(i)].
For the construction of
S(r) we have sets
U1,U2,…,Um for which
yi∪Ui∈S
with
Ui a ⊆ smallest set in
⋃i=1r−1Pi with
Ui∈str(H). We now have,
{U1,U2,…,Um}⊆[⋃i=0r−1S(i)](I.H.)
and
yi∪Ui∈S(r) (from the minimality of
Ui). Hence
⋃i=1m(yi∪Ui)∈[⋃i=0rS(i)]
and
⋃i=1mUi⊆U∈[⋃i=0r−1S(i)].
Hence,
U∪⋃i=1m(yi∪Ui)=U∪{y1,…,ym}∈[⋃i=0rS(i)].
Completing the argument that if
S∈Σstr then
S is decomposable. □
If we look at the case from Fig. 1, we had str(H) as,
{∅,{A},{D},{A,C},{A,D},{A,C,D},{A,C,F},{D,F},{A,C,D,F}}.
Since this is (self-evidently) a set of sets formed by the strongly admissible sets of an
af, the result of Theorem
1 asserts that this system is decomposable. Such a decomposition is given by
S(0)={∅},S(1)={{A},{D}},S(2)={{A,C}}},S(3)={{A,C,F},{D,F}}
with which every
S∈str(H) is formed by taking the union of (sometimes more than 2) appropriate sets from
(S(0),S(1),S(2),S(3)), e.g.
{A,C,D} is
{A,C}∪{D} the former in
S(2), the latter in
S(1). We further note that we cannot include
{D,F} in
S(2) despite
{D}∈S(1): the reason being the need to include all minimal sets with
F at the same time, however
{A,C,F} is one such set and
C first appears in
S(2) delaying
{A,C,F} to
S(3).
5.Decomposable systems are strongly admissible
We now complete the characterization of strong admissibility, the first part of which was demonstrated in Theorem 1 by showing that any system of sets S which is decomposable is in Σstr, i.e. there is an af, H, for which str(H)=S. We need some additional preliminaries.
Given y∈X and H define FH−1(y) to be the subset of 2X∖{y} for which S∈FH−1(y) if {y}∪S is conflict-free, y∈FH(S)∖S and for all strict subsets T of S y∉FH(T)∖T.
The concept FH−1(y) was introduced in Dunne [9] where it is dubbed the “inverse characteristic function” of y with respect to H.11
Lemma 3.
Let T⊂2X∖{y} all of whose members are incomparable, i.e. if (P,Q)∈T×T then P⊄Q and Q⊄P. Let Z=⋃T∈TT. There is an af H=(X,A) in which {y}∪Z⊆X and T=FH−1(y).
Proof.
Given T as described in the Lemma statement consider the (monotone) Boolean function fT over the propositional variables Z=(z1,z2,…,zn) defined via
fT(z1,…,zn)≡⋁T∈T(⋀zi∈Tzi).
It is clearly the case that
fT[S]=⊤ if and only if
S⊇T for some
T∈T. The specification of
fT is given in implicant form, i.e. as a disjunction of product terms. It is, however, well known that any Boolean function has an equivalent specification in
implicate form, i.e as a conjunction of clauses. It follows that we can translate
T to another system of subsets over
Z,
P={P1,P2,…,Pm}
with the sets in
P being incomparable and
fT(z1,…,zn)≡⋀k=1m(⋁zi∈Pkzi).
Build the
af H=(X,A) with
X=Z∪{y}∪{p1,p2,…,pm} m being the number of clause sets in
P. Add attacks
⟨pk,y⟩ for each
1⩽k⩽m and an attack
⟨zi,pj⟩ whenever
zi∈Pj∈P. If
U⊇T∈T then
U+={p1,p2,…,pm} since the implicant (disjunction of product terms using
T) and implicate (conjunction of clauses using
P) describe exactly the same propositional function. In order for
fT[S]=⊤ to hold some
T∈T must describe a subset of
S, or (equivalently),
S must include at least one
zi from every clause
Pk∈P. From the latter interpretation we see that each attack on
y is defended by
T+, i.e.
t∈FH(T)∖T and no strict subset of
T suffices to defend
y. □
We note that the relationship between “sets of arguments providing a defence against attacks on y” and the well-known formalisms from propositional logic of cnf and dnf has already been often exploited in formal argumentation. A similar use to that of Lemma 3 is found in Dunne et al. [11].
It is shown in [9, Thm. 4] that this construction is optimal. Given some incomparable system of subsets, S, with P the set of clauses in the unique minimal cnf equivalent to fS(Z), any af in which: for all S∈S, S∪{y} is conflict-free and S+⊇{y}− must be such that |{y}−|⩾|P|.
In particular, the realization of an af, H=(X,A) in which FH−1(y)=T for some incomparable system of subsets T drawn from Z may use exponentially many auxiliary arguments. This is not only in cases for which |T|∼2|Z|, e.g. when |Z|=2n and T comprises all subsets of size n from Z. Perhaps less obviously, one might have (again with |Z|=2n) |T|=n but, with the construction used, 2n auxiliary arguments in X. For example if
T={{zi,zn+i}:1⩽i⩽n}.
The implicant form of
fT(z1,…,z2n) used in the proof of Lemma
3 is
⋁i=1nzi∧zn+i.
The implicate form giving rise to the system of sets
P has
2n clauses leading to
|X|=1+n+2n.
The principal importance of Lemma 3, is as a vehicle by which to establish Theorem 2.
Theorem 2.
If S⊆2X is decomposable then S∈Σstr.
Proof.
Given S⊆2X which is decomposable let
(S(0),S(1),…,S(r))
be the decomposition of
S and
(P0;P1;…;Pt) the partition of
⋃i=1r⋃S∈S(i)S described in Lemma
2 (recalling that
P0={∅}). We use an inductive construction to build,
Hk satisfying
str(Hk)=[⋃i=0kS(i)].
The inductive bases (
k=0 and
k=1) are easily dealt with. In the former case, since
S(0)={∅}, we can use any
H0 for which every
x∈X is attacked by at least one other argument. In the case of
k=1,
H1 comprises the arguments in
P1 only with
A1=∅.
Now let us assume, inductively that we have built Ht for all t⩽k−1. We wish to form Hk. From the properties of the partition and formulation of the decomposition of S we know that each set in S(k) has the form y∪U where y∉⋃i=1k−1Pi and U is a subset minimal set in [⋃i=0k−1S(i)] for which y∪U∈S. For each y∈Pk define
G(y)={{U}:y∪U∈S(k)}.
We wish to develop
Hk−1 to
Hk in such a way that
G(y)⊆str(Hk). These subsets,
G(y) must be such that
G(y)=FHk−1(y).
We can now apply the outcome of Lemma
3. Identify each of the arguments contributing to sets in
G(y) (all such arguments being in
Hk−1) and then use the result of Lemma
3 to add the required defences of
y as minimal sets in
str(Hk).
This suffices to complete the inductive proof. □
Returning to the system presented in Fig. 1, we saw that this corresponds to the system of sets
{∅,{A},{D},{A,C},{A,D},{A,C,D},{A,C,F},{D,F},{A,C,D,F}}
which has decomposition
S(0)={∅},S(1)={{A},{D}},S(2)={{A,C}}},S(3)={{A,C,F},{D,F}}.
In forming the
af with
str(H)=[S(0)∪S(1)] we require only the two arguments
{A,D} and
A=∅. To add
S(2) we have a new argument (
C) which requires
A as a defender. Thus we can add
{C} and an argument
x together with attacks
⟨A,x⟩ and
⟨x,C⟩. Finally we must account for the cases in
S(3) which introduce
F which can be defended by either
D alone or by
{A,C}. We can extend the framework constructed so far adding arguments
{y,F} with
⟨y,F⟩∈A. Now, however, we need both
⟨C,y⟩∈A and
⟨D,y⟩∈A. The first will ensure
{A,C,F}∈str(H) and the second that
{D,F}∈str(H).
Combining Theorem 1 and Theorem 2 gives
Corollary 1.
Let S⊆2X.
S∈Σstr⇔S is decomposable.
