

![0_image_0.png](0_image_0.png)

![0_image_1.png](0_image_1.png)

Lemma 4.1 For all kernel atoms aˆ of S and all literals l 6= ¬aˆ, if l **is consistent** with S then l is so with S ∪ {aˆ}.

Proof. Suppose l is consistent with S, but inconsistent with S ∪ {aˆ}**, and**
so cancels all models of MOD(S ∪ {aˆ}) including MN(S ∪ {aˆ}**). Since** l 6= ¬aˆ,
l cancels all models of MN(S ∪ {¬aˆ}**) as well. By the kernel property of ˆ**a, MN(S ∪ {¬aˆ}) = MOD(S ∪ {¬aˆ}). So l cancels all models of MOD(S**) and**
becomes inconsistent with S **— a contradiction.** ✷
Theorem 4.3 For all S, tk(S) is consistent with S**. There is no superset of**
tk(S) **possessing this property.**
Proof. By induction on the serial number of kernel atoms of S **numbered**
arbitrarily in tk(S) = {aˆ1**, . . . ,** aˆk}.

Base. Include ˆa1 into S producing S1 = S ∪ {aˆ1}; ˆa1 **is consistent with** S,
so S1 is consistent; but ˆa1 cancels all models of S containing ¬aˆ1 **such that**
MOD(S1) = MOD(S) − MOD(S ∪ {¬aˆ1}) = MOD(S ∪ {aˆ1}) 6= ∅,
MOD(S1 ∪ {aˆ1}) = MOD(S1), MOD(S1 ∪ {¬aˆ1}) = ∅.

It turns out that for 1 < i ≤ k every ˆai ∈ tk(S) is a kernel atom of S1**. Indeed,**
(i) by Lemma 4.1 ˆaiis consistent with S1 **since it is consistent with** S;
(ii)
MN(S1 ∪ {¬aˆi}) = MN(S ∪ {¬aˆi}) − MOD(S **∪ {¬**aˆ1});