
## 6.2 Consistency In Src And Logics

To translate SRC-DEDUCTION in logics, a starting point could be to extend the logical translation of SGC-CONSISTENCY given in Th. 7 to a translation of SRC-CONSISTENCY.

However, the following theorem points out the limitations of this approach. Theorem 9 Let K = (G,R,C) be a KB. If there exists a SG G such that Φ(S), Φ(G), Φ(R), Φ(C) = Φ(G') and not Φ(S),Φ(G),Φ(R) = Φ(G'), where Φ(C) is the translation of the constraints of C considered as rules, then K is inconsistent. However, the converse is false in the general case.

Proof: We first prove the positive part of this theorem. If there exists such a graph G ′ ,
then (Th. 4) there is a ( R ∪ C )-derivation (considering the colored graphs of C as rules) G = G 0 , . . , G k such that G ′ projects to G k . See that G k cannot be deduced from ( G, R ), otherwise G ′ would also be deducible from ( G , R ). Let us consider the first G i from this derivation that is not deducible from ( G, R ). Then Gi is obtained from Gi –1 (a graph R-deducible from G ) by applying a rule Cq E C following a projection π . Since Gj –1 is deducible from ( G, R ), then there exists a graph H R -derivable from G such that G i –1 projects into H . Let us call π ′ such a projection, and consider the projection π ′ = π ′ o π of the hypothesis/trigger of the rule/constraint C g into H . We now have to prove that 1)
H π"-violates C q , and 2) this violation is not R-restorable. Suppose 1) or 2) is false. Then there would exist a graph H ′ R -derived from H such that π ′′ can be extended to a projection Π of C q as a whole in the irredundant form of H ′ . This is absurd, since Π is a projection of G i in a graph R -derivable from G .

The counterexample presented in Fig. 14 is sufficient to prove the negative part of the theorem.

P Sfrag replacemen

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

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

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

Figure 14: A counterexample to Th. 9 It is immediate to check that every graph that can be { R, C }-derived from G can also be { R }-derived from G . However, the projection of the trigger of C into the unique node of G defines a violation of C that will never be restored.

□
We will study in the next section (Th. 11) a particular case of rules where the converse of Th. 9 is true.

## 6.3  Undecidability Of The Associated Deduction Problems

Theorem 10 (Complexity in SEC/SRC ) SEC-DEDUCTION is semi-decidable. Both SRC-
CONSISTENCY and SRC-DEDUCTION are truly undecidable.