Rules Represent Causal Knowledge: Causal Modeling with Abductive Logic Programs

Abstract

Pearl observes that causal knowledge enables predicting the efects of interventions, whereas descriptive knowledge only permits drawing conclusions from observations. This paper brings Pearl's approach to causality and interventions into stratified abductive logic programming. It shows how stable models of such programs can be given a causal interpretation by building on philosophical foundations developed in recent work by Bochman and Eelink et al. In particular, it translates abductive logic programs into the causal systems of Eelink et al., thereby clarifying the informal causal reading of logic program rules. The main results establish that the stable model semantics for stratified programs conforms to key philosophical principles of causation, including causal suficiency, natural necessity, and the irrelevance of unobserved efects. This justifies the use of stratified abductive logic programs as a framework for causal modeling and for predicting the efects of interventions.

1. Introduction

After being a central topic of philosophical inquiry for over two millennia, causality entered the mainstream of artificial intelligence research through the work of Pearl [ 1 ]. A key feature of his account is that causal knowledge goes beyond descriptive knowledge in the questions it can address: while descriptive knowledge permits only inferences from observations, causal knowledge enables reasoning about the efects of external interventions such as actions on the modeled system.

Example 1.1. Consider a road that passes through a field with a sprinkler. Assume the sprinkler is turned

on by a weather sensor when it is sunny. Suppose further that it rains whenever it is cloudy, and that the road becomes wet if either it rains or the sprinkler is activated. Finally, assume that a wet road is dangerous.

Observing that the sprinkler is on, one might conclude that the weather is sunny. However, actively intervening and switching the sprinkler on does not cause the weather to become sunny. To predict the efect of such an intervention, one needs causal—not merely descriptive—knowledge.

Since evaluating the efects of possible actions is one of the primary motivations for modeling in the first place, this has paved the way for the adoption of causal frameworks across a wide variety of domains [ 2, 3, 4 ]. networks and structural causal models. road is dangerous.

CEUR

ceur-ws.org

Pearl [1] models these causal mechanisms as a system of structural equations:

∶= ∶= ∶= ¬ ∶= ∨ ∶=

Since the mechanisms do not specify whether it is cloudy, Pearl [1] treats as an external variable or error

term. The solutions of the corresponding causal model ℳ are obtained by solving Equations (1) for = ⊤ and = ⊥ . If the sprinkler is observed to be on, then according to Equations (1), it must be sunny.

The intervention of manually switching the sprinkler on is represented by modifying the causal mechanism for the sprinkler so that it is on regardless of the weather. This is captured in the structural equations below: (1) (2) (3) (4) ∶= ⊤ ∶= ∨ ∶=

Again, is considered an external variable, and the solutions of the corresponding causal model ℳ represent

the possible states of the world after the intervention of switching the sprinkler on manually. Note that is now true independently of the weather.

In philosophy, the idea that causal explanations are given by rules of the form “ causes ” is well established, for instance, in René Descartes’ Principles of Philosophy II:37 (see the translation by Miller and Miller [ 5 ]). This makes abductive logic programming [ 6 ] a natural target formalism for representing causal knowledge. An abductive logic program consists of a set of rules P and a set of propositions , called abducibles. Similar to external variables in Pearl’s causal models, abducibles are independently assumed to be either true or false.

Rückschloß and Weitkämper [ 7 ] apply Clark completion [ 8 ] to relate probabilistic logic programming to Pearl’s theory of causality, thereby transferring Pearl’s notion of intervention. Similarly, abductive logic programs can be translated into causal models, enabling a principled treatment of interventions. Example 1.3. The situation in Example 1.1 gives rise to the rules: ← ← ← ← ←

← ¬ ← ← ⊤ ← ← Since can be either true or false, it is considered an abducible; that is, ∶= {} . Reading Pearl’s “∶=” sign as logical equivalence “↔,” the Clark completion [ 8 ] implies that the models of the resulting abductive logic program coincide with the solutions of the causal model ℳ in Equations (1) of Example 1.2.

Intervening and switching the sprinkler on manually results in the rules:

Again, Clark completion [8] yields that the models of the resulting abductive logic program coincide with

the solutions of the causal model ℳ in Equations (2) of Example 1.2.

Notably, this approach provides an informal semantics for abductive logic programs, where each rule ℎ ← 1, … , is interpreted as “ 1 ∧ … ∧ causes ℎ”. However, translating abductive logic programs into causal models via the Clark completion [ 8 ] and replacing logical equivalence “↔” with Pearl’s “∶=” sign can lead to counterintuitive results when cyclic causal relations are involved.

Example 1.4. Assume ℎ1 and ℎ2 are two neighboring houses. Let denote the event that House ℎ is on

ifre, and the event that House ℎ starts burning, for ∈ {1, 2}. It is reasonable to assume that a fire in

House ℎ1 leads to a fire in House ℎ2, and vice versa.

This situation can be modeled by the cyclic abductive logic program , consisting of the abducibles ∶= { 1, 2} and the rules: 1 ← 1 2 ← 2 2 ← 1 1 ← 2 (5)

Proceeding as in Example 1.3, forming the Clark completion [8] and replacing logical equivalence “↔”

with Pearl’s “∶=” sign relates to a causal model that admits a solution corresponding to the structure ∶= { 1, 2}. In , both houses are on fire even though neither house actually started to burn. This contradicts the intuition that houses do not spontaneously catch fire merely because they influence each other.

This work extends the applicability of Pearl’s ideas to stratified abductive logic programs with cyclic causal relations. Building on prior work by Bochman [ 9 ] and Eelink et al. [ 10 ], it connects logic programming to explanations that satisfy Principles 1–5 from philosophy, as stated below.

Principle 1 (Causal Foundation). Causal explanations originate from external premises, whose explana

tions lie beyond a given scope.

Principle 2 (Natural Necessity). “…given the existence of the cause, the efect must necessarily follow.” (Thomas Aquinas: Summa Contra Gentiles II:35.4; translation by Anderson [11])

Principle 3 (Suficient Causation) . “…there is nothing without a reason, or no efect without a cause.” (Gottfried Wilhelm Leibniz: First Truths; translation by Loemker [12], p. 268)

Principle 4 (Causal Irrelevance [13]). Efects beyond the given scope have no influence on beliefs.

Principle 5 (Non-Interference). The impact of interventions is restricted to the direction from causes to

efects.

If propositions can only be explained through other propositions, the resulting explanations are either cyclic or lead to an infinite regress. As Aristotle argues in his Posterior Analytics (see Barnes’ translation [14, pp. 117–118]), infinite chains and cyclical arguments are not genuinely explanatory. To circumvent this problem, Principle 1 assumes that explanations take place within a given scope, just as explanations in chemistry rely on results from physics. Principle 2 states that every statement that can be explained indeed takes place, and Principle 3 states that every statement that takes place can be explained. Principle 4 states that extending the scope and including further efects does not change the result of the initial explanations. For example, if one adds a rule ← to Equations (3) of Example 1.3, stating that somebody is injured if the road is dangerous, this does not afect the causal explanation of why the road is dangerous. Finally, Principle 5 states that the efect of interventions propagates exclusively from causes to efects. As illustrated in Example 1.1, this means, for instance, that switching on the sprinkler manually has no efect on the weather.

Theorem 4.2 translates abductive logic programs into the causal systems of Eelink et al. [ 10 ], thereby relating the stable model semantics to Principles 1, 2, and 3. Theorem 4.3 shows that Principle 4 implies 5. Finally, Theorem 4.4 establishes that stratified programs satisfy Principle 4.

Overall, the results show that stratified abductive logic programs under the stable model semantics conform to these principles, supporting their use in causal modeling and the prediction of efects from external interventions.

2. Preliminaries

This section recalls the foundations of the present work: Pearl’s causal models [ 1 ], abductive logic programs [ 6 ], and the logical theories of causality developed by Bochman [ 9 ] and Eelink et al. [ 10 ]. 2.1. Pearl’s Causal Models Pearl [ 1 ] suggests modeling causal relationships with deterministic functions. This leads to the following definition of structural causal models.

Definition 2.1 (Causal Model [1, §7.1.1]). A (structural) causal model ℳ with internal variables V and external variables U is a system of equations that includes one structural equation of the form ∶= (Pa( ), Error( )) for each internal variable ∈ V. Here, the parents Pa( ) ⊆ V of are a subset of internal variables, the error term Error( ) ⊆ U is a subset of external variables, and the causal mechanism of is a function that maps each assignment of values to Pa( ) and Error( ) to a value of .

A solution of the structural causal model ℳ is an assignment of values to the variables in V ∪ U that

satisfies all structural equations.

Notation 2.2. The parents Pa( ) and error terms Error( ) of an internal variable ∈ V are typically

evident from the causal mechanism . Accordingly, this work omits explicit references to Pa(⋅)and Error(⋅). Example 2.1. The causal model ℳ in Example 1.2 has external variables U ∶= {}, internal variables V ∶= { , , , }

, Structural Equations (1), and solutions: 1 ∶ 2 ∶ = ⊤ = ⊥ = ⊤ = ⊥ = ⊥ = ⊤ = ⊤ = ⊤ = ⊤ = ⊤

In artificial intelligence, causal models are particularly valuable because they can represent external interventions. As explained in Chapter 7 of Pearl [ 1 ], the key idea is to construct a modified model that incorporates the minimal changes to the structural equations required to enforce an external intervention.

Definition 2.3 (Modified Causal Model) . Fix a causal model ℳ. Let I be a subset of internal variables

with a value assignment i. The modified model or submodel ℳi is the model obtained from ℳ by replacing, for each variable ∈ I, the structural equation ∶= (Pa( ), Error( )) with ∶= i( ).

Notation 2.4. Let ∈ V be a Boolean internal variable of a structural causal model ℳ. In this case, one

writes ℳ ∶= ℳ ∶=⊤ and ℳ¬ ∶= ℳ ∶=⊥ .

Example 2.2. The causal model ℳ from Example 1.2 is the modified model corresponding to the value assignment ∶= ⊤ . It has the following solutions: 1 ∶ 2 ∶ = ⊤, = ⊥, = ⊤, = ⊥, = ⊤, = ⊤, = ⊤, = ⊤, = ⊤ = ⊤

These represent the possible states of the system after manually switching on the sprinkler.

Remark. As in Example 1.2, actions often force a variable in a causal model to take on a new value.

Pearl [1] emphasizes that submodels ℳi typically arise from performing actions that set certain variables

to specific values, a process formalized by the introduction of the do-operator. 2.2. Abductive Logic Programming This work adopts standard notation for propositions, (propositional) formulas, and structures. A structure is identified with the set of propositions true in it. The term world denotes a consistent set of literals that is maximal with respect to inclusion. Since identifying structures with the set of literals they render true yields a one-to-one correspondence between worlds and structures, the two terms are used interchangeably. world {, , ¬, , }

Example 2.3. A structure in the propositional alphabet ∶= {, , , , } of Example 2.1 is a complete state description such as 1 in Example 2.1. It is identified with the set of propositions {, , , } and the

Fix a propositional alphabet . Logic programs consist of rules or clauses.

Definition

2.5 a formula of (Clauses and

Logic

Programs).

A the form (ℎ ← ( 1 ∧ ( 2 ∧ (... ∧ ))...)), (normal) which is clause also

is denoted as ℎ ← 1 ∧ ... ∧ , ℎ ← 1, ..., or head() ← body() .

Here, head() ∶= ℎ is an atom, referred If body() = ∅ and = (ℎ ← ⊤) , one denotes by ℎ and calls a fact. to as the head of the clause and body() ∶= { 1, ..., } is a finite set of literals, known as the body of .

A logic program P is a finite set of clauses. The

dependence graph of P is the directed graph over the alphabet defined as follows: there is an edge → if and only if there exists a clause ∈ P such that head() = and body() ∩ {, ¬} ≠ ∅

. It is denoted by graph(P).

An edge →− in graph(P) is negative if there exists a clause ∈ P such that head() = and ¬ ∈ body() . Similarly, an edge →+ is positive if there exists a clause ∈ P such that head() = and ∈ body() . Note that an edge may be both negative and positive simultaneously.

A cycle in graph(P) is a finite alternating sequence of nodes and edges of the

form → 1 → 2 → ⋯ → → that begins and ends at the same node . The program P is acyclic if its dependence graph graph(P) contains no cycle. It is stratified if its dependence graph does not contain a cycle with a negative edge.

Clark [ 8 ] translates acyclic programs P to propositional formulas, stating that a valid proposition in a model needs to have a reason, i.e., a support in .

Definition 2.6 (Clark Completion, Supported Model Semantics). Let P be a logic program. The Clark completion of P is the set of formulas comp(P) ∶= { ↔

⋁ ∈ P, head()= ⋀ body() }

. ∈

A supported model of P is a model of the Clark completion ⊧ comp(P).

Remark. If there is no clause ∈ P with head() = for a proposition ∈ , then ↔ ⊥ ∈ comp(P), since the disjunction over the empty set evaluates to false.

Example 2.4. Rules (3) define an acyclic logic program

Example 2.1.

P whose unique supported model is 2 in

Although the supported model semantics is formally well-defined for general propositional logic programs, i.e., it associates a unique (possibly empty) set of models to each program P, it yields counterintuitive results for cyclic programs.

Example 2.5. Rules (5) define a stratified logic program P with two supported models: 1 ∶= ∅ and 2 ∶= { 1, 2}. In 2, both houses are on fire, even though there is no initial cause for either to start burning – contradicting everyday intuition.

For general, potentially cyclic programs, Gelfond and Lifschitz [ 15 ] argue that the stable model semantics provides a more appropriate notion of a model. Rather than adopting the more common formulation via reducts, this work follows the equivalent definition based on unfounded sets, originally introduced by Saccà and Zaniolo [ 16 ] and listed as Definition D in Lifschitz [ 17 ].

Definition 2.7 (Unfounded Sets and Stable Models). Let be a structure, ⊆ a non-empty subset of

the set of atoms that are true in , and P a logic program. Then, is an unfounded set with respect to and P if, for each ∈ , every rule in P with head has some body literal that is either not true in or belongs to .

A structure is a stable model of P if it satisfies every clause of P when interpreted as a propositional formula and if there is no unfounded set ⊆ with respect to and P.

Example 2.6. In Example 2.5, the only stable model is 1, as intended. The set 2 is not stable because it

is unfounded with respect to itself and the program P.

Gelfond and Lifschitz [ 15 ] prove the following results:

Theorem 2.1 (Supported and Stable Models). Every stable model of a logic program is also a supported

model □ .

Theorem 2.2 (Stable Models of Stratified Programs) . Every stratified program has a unique stable

model. □

Abductive logic programming was identified as a distinct branch of logic programming by Kakas and Mancarella [ 6 ], with the goal of providing an explanation for a given set of observations in terms of so-called abducibles.

Definition 2.8 (Abductive Logic Program [18]). An integrity constraint IC is an expression of the form ⊥ ← 1 ∧ ... ∧ also written ⊥ ← body( ) , where body(IC) is a finite set of literals.

An abductive logic program is a triplet ∶= ( P, , IC) consisting of a logic program P, a finite set of integrity constraints IC and a set of abducibles ⊆ such that no abducible ∈ is the head of a clause in P. Finally, is acyclic or stratified if the underlying logic program P is.

In the context of databases, integrity constraints serve as sanity checks on data [19, Chapter 9]. In a causal setting, they are used to represent observations; that is, they ensure that the knowledge encoded by the causal rules in the program P and the explanations in is consistent with the given observations.

Example 2.7. Let P denote the logic program in Example 2.4. Since the causal knowledge in Example 1.1 is

expected to be insuficient to explain whether it is cloudy, is declared as the only abducible, that is, ∶= {} . One may also observe that the sprinkler is on, leading to the integrity constraint IC ∶= {⊥ ← ¬}. Together, this yields the abductive logic program ∶= ( P, , IC).

Lastly, the various semantics of an abductive logic program are recalled.

Definition 2.9 (Models of Abductive Logic Programs). A stable or supported model ⊆ of the abductive logic program ∶= ( P, , IC) satisfies the integrity constraints IC, i.e., ⊧ IC (meaning ⊧ b̸ody(IC)) for all IC ∈ IC and is a stable or supported model of the program P ∪ ( ∩ ) . The set ∶= ∩ is then called the explanation of . In this context, the program is consistent if it has at least one model for every choice of abducibles.

Remark. If the abductive logic program ∶= ( P, , IC) is not consistent, there exists a truth-value assignment on such that has no model with explanation . In this case, one would conclude, against the direction of cause and efect, that is impossible, contradicting Principle 4.

Example 2.8. The abductive logic program in Example 1.3 has two stable and supported models, namely 1

and 2 from Example 2.1, with explanations 1 ∶= {} and 2 ∶= ∅, respectively.

Since only 2 is consistent with the observation that the sprinkler is on, expressed by the integrity

constraint ⊥ ← ¬ , it is the only supported model of the abductive logic program in Example 2.7.

Rückschloß and Weitkämper [ 7 ] connect probabilistic logic programming to Pearl’s theory of causality. Following their approach, the Clark completion [ 8 ] of abductive logic programs without integrity constraints gives rise to causal models, thereby transferring Pearl’s notion of an intervention: Definition 2.10 (CM-Semantics). Let ∶= ( P, , ∅) be an abductive logic program without integrity constraints. The causal model semantics of is the causal model CM(P) that is given by the external variables , the internal variables ∖ and the structural equations ∶= ⋁ ⋀ body() . ∈ P head()=

To represent the intervention of forcing the atoms in I ⊆ ∖ to attain values according to the

assignment i, the modified (abductive logic) program i ∶= (Pi, i, ∅) is obtained from by the modifications below:

Remove all clauses from P for which head() ∈ i or ¬head() ∈ i.

Add a fact to Pi whenever ∈ i.

Remark. By construction, a structure is a solution of CM(P) if and only if it is a supported model of P.

Moreover, by construction, CM(Pi) = CM(P)i.

Example 2.9. In Example 1.3, Rules (4) correspond to the modified program that corresponds to the

assignement ∶= ⊤ . 2.3. Bochman’s Logical Theory of Causality and Causal Systems To verify that the stable model semantics is causally meaningful, this contribution builds upon the work of Bochman [ 9 ] and Eelink et al. [ 10 ]. Both rely on the idea that causal knowledge should be expressed in the form of rules.

Definition 2.11 (Causal Rules and Causal Theories). A (literal) causal rule is an expression of the form 1 ∧ ... ∧ ⇒ , also denoted by { 1, ..., } ⇒ , where 1, ..., , are literals. One calls 1 ∧ ⋯ ∧ the cause and the efect of . Informally, means that 1 ∧ ⋯ ∧ causes . If, in addition, ∈ is an atom, the rule is atomic. A default rule is a causal rule of the form ⇒ for one literal . A causal theory is a set of causal rules Δ. It is called atomic if it contains only atomic causal rules.

Remark. Note that causation “⇒” is not reflexive; that is, ⇒ does not hold for all literals . Bochman [9]

interprets default rules of the form ⇒ as indicating that the literal is self-explained, meaning it can serve as a starting point for a causal explanation.

Example 2.10. The situation in Example 1.4 gives rise to the following causal theory Δ: 1 ⇒ 1 ¬ 1 ⇒ ¬ 1 2 ⇒ 2 ¬ 2 ⇒ ¬ 2 1 ⇒ 1 ¬ 1 ⇒ ¬ 1 2 ⇒ 2 ¬ 2 ⇒ ¬ 2 1 ⇒ 2 2 ⇒ 1

The default rule ¬ 1 ⇒ ¬ 1 expresses that no explanation is required for House 1 not burning; that is,

House 1 is assumed not to burn unless an explanation for 1 is given. Since both default rules 1 ⇒ 1 and ¬ 1 ⇒ ¬ 1 are included in Δ, the truth value of 1 can be chosen freely.

Bochman [ 9 ] extends the rules in a causal theory to an explainability relation.

Definition 2.12. Let Δ be a causal theory. The binary relation (⇛Δ)/2 of explainability is defined inductively from the causal rules as follows:

If ⇒ , then ⇛ Δ . (Causal rules) If ⇛ Δ , then ∪ ′ ⇛Δ . (Literal Monotonicity) If ′ ⇛Δ and ∪ {} ⇛ Δ ′, then ∪ ′ ⇛Δ ′. (Literal Cut) {, ¬} ⇛ Δ for all propositions and literals . (Literal Contradiction) If ⇛ Δ , it is said that explains .

Remark. Bochman [9] initially allows causal rules of the form ⇒ and explainability relations of

the form ⇛ , where and are arbitrary formulas. He argues that explainability (⇛)/2 satisfies all the properties of material implication “→”, except reflexivity (i.e., → does not necessarily hold).

Given a causal theory Δ in the sense of Definition 2.11, this work restricts attention to explainability

relations as characterized in Definition 2.12. Theorem 4.23 in Bochman [ 9 ] then provides the basis for this characterization.

Example 2.11. In Example 2.10, one finds that 1 ⇛Δ 1 and 2 ⇛Δ 2, even though the causal theory Δ does not explicitly assert that 1 or 2 are defaults.

Bochman’s semantics [ 9 ] for causal theories is grounded in Principles 2 and 3:

Definition 2.13 (Causal World Semantics). A causal world for a causal theory Δ is a world such that,

for every literal , the following formalization of Principles 2 and 3 hold: Formalization of Principle 2: If ⇛ Δ , then ∈ .

Formalization of Principle 3: If ∈ , then ⇛ Δ .

The causal world semantics Causal(Δ) is the set of all causal worlds of Δ.

Bochman [ 9 ] gives the following alternative characterisation for the causal worlds of a causal theory Δ.

Definition 2.14 (Completion of Causal Theories). The completion of a causal theory Δ is the set of

formulas comp(Δ) ∶= { ↔

⋁ } ⇒∈Δ

.

literal Theorem 2.3 (Completion of Causal Theories [20, Theorem 8.115]). The causal world semantics Causal(Δ) of a causal theory Δ coincides with the set of all models of its completion:

Causal(Δ) = { world: ⊧ comp(Δ)}. □ Example 2.12. In Example 2.10, the theory Δ has the causal world ∶= { 1, 2}, which contradicts everyday causal reasoning as explained in Example 1.4. Note that is a causal world of Δ since the framework of causal theories allows for the cyclic explanations in Example 2.11.

To avoid cyclic explanations as in Example 2.11. Eelink et al. [ 10 ] extend Bochman’s causal theories [ 9 ] to accommodate a set of external premises ℰ that do not require further explanation. Motivated by the ideas in Aristotles’s Posterior Analytics, they additionally apply Principle 1. This leads them to the set-up of causal systems: Definition 2.15 (Causal System). A causal system CS ∶= (Δ, ℰ , ) consists of a causal theory Δ called the causal knowledge of CS, a set of literals ℰ called the external premises of CS and a set of formulas called the observations of CS. The causal system CS is without observations if = ∅ . Otherwise, the causal system CS observes something. The causal system CS applies default negation if every negative literal ¬ for ∈ is an external premise, i.e., ¬ ∈ ℰ and no external premise is an efect of a causal rule in Δ. Further, the system CS is atomic if Δ is an atomic causal theory.

The causal theory Δ(CS) ∶= Δ ∪ { ⇒ ∣ ∈ ℰ } is called the explanatory closure of CS. A causally founded explanation is an explanation ⇛ Δ(CS) such that ⊆ ℰ .

A causally founded world is a world such that ⊧ and for every literal the following formaliza

tions of Principles 2 and 3 are satisfied: Formalization of Principle 2:

If there exists a causally founded explanation ∩ ℰ ⇛ Δ(CS) , then ∈ .

Formalization of Principle 3:

If ∈ , then there exists a causally founded explanation ∩ ℰ ⇛ Δ(CS) .

Eelink et al. [ 10 ] argue that causally founded explanations can be used to formalize Principle 1. Formalization 1 (Principle 1). All causal explanations ⇛ Δ(CS) are causally founded.

Example 2.13. Example 1.4 gives rise to the causal system with default negation and without ob

servations, defined as CS ∶= (Δ, ℰ , ∅), where Δ ∶= { 1 ⇒ 2, 2 ⇒ 1} is an atomic causal theory and ℰ ∶= { , ¬ , ¬ }=1,2 the set of external premises. The explanatory closure Δ(CS) of CS coincides with the causal theory in Example 2.10. Note that the cyclic explanations from Example 2.11 are not causally founded. Hence, the world in Example 2.12 is not causally founded.

3. Problem Statement

Example 1.4 shows that abductive logic programming under the causal model semantics can yield counterintuitive results in the presence of cyclic causal relationships. From the perspective of logic programming, such issues are typically addressed by applying the stable model semantics of Gelfond and Lifschitz [ 15 ]. However, it remains an open question whether this approach admits a causally meaningful interpretation that accounts for interventions.

4. Results

Throughout this section, we fix a propositional alphabet . We begin by introducing the Bochman transformation, which identifies abductive logic programs with causal systems featuring default negation [ 10 ], as defined in Definition 2.15.

Informally, the Bochman transformation interprets clauses ℎ ← 1 ∧ … ∧ as “ 1 ∧ … ∧ causes ℎ,” treats the abducibles as external premises whose explanations lie beyond the given scope, and regards the integrity constraints as observations.

Definition 4.1 (Bochman Transformation). The Bochman transformation of an abductive logic program ∶= ( P, , IC) is the causal system with default negation CS( ) ∶= (Δ, ℰ , ) , where Δ ∶= {body() ⇒ head() ∣ ∈ P}, ℰ ∶= ∪ {¬ ∣ ∈ } , and ∶= IC.

Example 4.1. Let be the abductive logic program in Example 1.4. The causal system in Example 2.13 is

the Bochman transformation CS( ) of .

Let ∶= ( P, , IC) be an abductive logic program. We show that the stable models of correspond to the causally founded worlds of its Bochman transformation CS( ) ∶= (Δ, ℰ , ) . Together with Formalization 1 and Definition 2.15, this supports that the stable model semantics follows from Principles 1, 2, and 3.

We begin by relating unfounded sets to explainability in causal theories.

Definition 4.2 (Internal and External Explanations). Let Δ be an atomic causal theory, a model of the

propositional theory obtained by reading the causal rules in Δ as logical implications, and ⊆ a set of positive literals true in .

An -external explanation is an expression of the form ⇛ Δ , where ∈ and is a set of literals that are true in and do not belong to . An -internal explanation is an expression of the form ⇛ Δ that is not -external.

Let be a causally founded world of the Bochman transformation CS( ) . Definition 4.1 ensures that a subset ⊆ of atoms true in can be unfounded with respect to any program extending the underlying logic program P only if every rule ⇒ in Δ corresponds to an -internal explanation ⇛ Δ .

Lemma 4.1. Let Δ, and be as in Definition 4.2. If every rule ⇒ in Δ corresponds to an -internal

explanation ⇛ Δ , then every other explanation ′ ⇛Δ ′ is also -internal as well.

Proof. By Definition 2.12, ′ ⇛Δ ′ follows from the rules in Δ through iterated applications of literal cut, literal monotonicity and literal contradiction. So it sufices to show that as long as the rules in the premises to those three inference rules are -internal, then so is their consequence.

We use the notation of Definition 2.12.

For literal monotonicity, the statement is clear, since if ∪ ′ is a set of literals true in and not in , then so is its subset .

Since is a structure, and ¬ can never both be true in . Therefore, literals contradiction can never yield an -external explanation.

So it only remains to consider literal cut. Assume for contradiction that ∪ ′ ⇛Δ ′ is -external despite both premises ′ ⇛Δ and ∪ {} ⇛ Δ ′ being -internal. Then ∪ ′ is a set of literals true in and not in , and therefore so are and ′. Thus, since both premises are -internal, the atom must not be in and also not true in . However, this contradicts the fact that is a model of the propositional theory corresponding to the rules of Δ. Indeed, note that (literal) cut, monotonicity and contradiction are all true for propositional logic, where the triple arrow is read as logical implication. Thus, since ⇛ Δ is obtained from rules in Δ using those three axioms, is a model of → and of and thus of , yielding the desired contradiction.

With Lemma 4.1 at hand, we can now prove our first result.

Theorem 4.2 (Bochman Transformation). The Bochman transformation is a bijection from abductive

logic programs to causal systems with default negation.

An abductive logic program ∶= ( P, , IC) has a stable model if and only if is a causally founded world with respect to its Bochman transformation CS( ) ∶= (Δ, ℰ , ) .

Proof. By construction the Bochman transformation is a bijection between abductive logic programs and causal systems with default negation. Since the integrity constraints are carried over unchanged by the Bochman transformation as observations, we can assume without loss of generality that is without integrity constraints.

First, we show that every stable model of P ∪ ( ∩ ) is a causal founded world of CS( ) =∶ (Δ, ℰ , ∅) .

Let be such a stable model. We need to show for all literals that ∩ ℰ ⇛ Δ(CS) if and only if ∈ . Note that since the rules in Δ correspond precisely to the clauses of the underlying logic program P, the Clark completion of P coincides with the completion of the explanatory closure Δ(CS). Since every stable model is also a supported model, the structure is a model of the completion of Δ(CS( )) .

For any set Λ of literals, we introduce the notation (Λ) to indicate the set of all literals such that Λ ⇛Δ(CS( )) . Thus, Theorem 2.3 states that () = and by literal monotonicity ( ∩ ℰ ) ⊆ .

It remains to show that ⊆ ( ∩ℰ ) , or, in other words, that ∶= ∖ ( ∩ℰ ) = ∅ . Note first that since all negated literals are in ℰ, is a set of positive literals. We show that if it were non-empty, were an unfounded set. Assume that is not unfounded. Then, there would be a ∈ and a clause ← 1, … , such that all of 1, … , are in ∖ = ( ∩ ℰ ) . However, this implies that ∩ ℰ ⇛ Δ(CS( )) for ∈ 1, … , and therefore by -fold iteration of the (literal) cut, that ∩ ℰ ⇛ Δ(CS( )) and thus that ∈ ( ∩ ℰ )

. This in turn contradicts ∈ , and thus concludes the proof that = ∅ since stable models contain no non-empty unfounded sets of atoms. Overall, we have shown that ( ∩ ℰ ) = and therefore that is a causally founded world of CS( ) .

We turn to the converse direction, showing that every causally founded world of CS( ) is a stable model of . By Theorem 2.3, every causally founded world of CS( ) is a model of the propositional theory corresponding to the clauses of P.

So it remains to show that has no unfounded sets of atoms with respect to P ∪ ( ∩ ) . Assume it does have such a set, say .

As is a causally founded world, we obtain ∩ ℰ ⇛ Δ(CS( )) for any ∈ . Since every abducible atom true in corresponds to a fact of P ∪ ( ∩ ) , the unfounded set must be disjoint from and thus from ℰ. Therefore, ∩ ℰ ⇛ Δ(CS( )) is -external.

By Lemma 4.1, this implies that one of the rules of Δ(CS( )) is -external and thus that is not an unfounded subset of .

This concludes the proof that is a stable model of P ∪ ( ∩ ) as claimed.

According to Theorem 4.2, Principles 1, 2, and 3, together with Formalization 1 and Definition 2.15, entail that a causal interpretation of abductive logic programming necessarily yields the stable model semantics of Gelfond and Lifschitz [ 15 ]. This raises the question of whether every abductive logic program admits such a causal interpretation.

Example 4.2. Let denote the event that a farmer is ecological, and ℎ the event that it is hot. Further, let

denote that pests survive the weather, that there are pests in the field, and that the farmer applies toxin.

Assume pests survive if it is hot. If no toxin is applied, pests remain; toxin is applied if pests are present and the farmer is not ecological. These relations define an abductive logic program with abducibles ∶= {ℎ, } and rules P: ← , ¬, ← ¬, , ← ℎ.

The program

has no stable model with explanation ∶= {ℎ} . Hence, it concludes against the causal direction, namely that it cannot be hot if the farmer is not ecological. This contradicts everyday intuition as well as Principle 4.

We argue that to represent causal knowledge, an abductive logic program must also satisfy Principle 4, as explored by Williamson [ 13 ] in the context of Bayesian networks. In abductive logic programming, we interpret Principle 4 as the following semantic constraint: Formalization 2 (Principle 4). Let ∶= ( P, , IC) be a consistent abductive logic program. For a set ⊆ of propositions, let > denote the set of all propositions ∉ that are descendants in the dependency graph ∶= graph(P) of some proposition in . Finally, denote by P> the program consisting of all clauses ∈ P with head() ∈ > .

Then, satisfies Principle 4 if and only if for every set ⊆ and every ∖ > -structure , the program P>, ∶= P> ∪ has at least one stable model; that is, it is not possible to falsify with P> .

Remark. Williamson [13] proposes Principle 4 in the context of maximum entropy as a weakening of the

Markov assumption in Bayesian networks [1]. Accordingly, the above formalization could be viewed as a deterministic analogue of the Markov assumption.

Example 4.3. The program in Example 4.2 does not satisfy Principle 4.

We argue that every abductive logic program satisfying Principle 4 under the above formalization admits a causal interpretation under the stable model semantics. This raises the question of whether can also be used to predict the efects of external interventions.

According to Pearl [ 1 ], the joint act of observing and intervening leads to counterfactual reasoning, which lies beyond the scope of this contribution. Therefore, we restrict our interest to programs without integrity constraints and argue that they admit a meaningful representation of interventions if Principle 5 holds. Finally, the following result shows that Principle 4 implies Principle 5. Theorem 4.3. Let ∶= ( P, , ∅) be an abductive logic program without integrity constraints that satisfies Principle 4, and let i be an assigment on a set of propositions ⊆ .

Define < ∶= ∖ ( > ∪ ) , P< ∶= { ∈ P ∣ head() ∈ < } and < ∶= (P< , , ∅) . Then, the following are equivalent: 1. < = ∩ < for some stable model of , i.e., < is a reduct of . 2. < is a stable model of < .

3. < = i ∩ < for some stable model i of i, i.e., < is a reduct of i.

Proof. The proof rests on the splitting lemma [21]. For any set of propositions ⊆ denote by ≥ ∶= > ∪ . Let be the set of all clauses with heads in , and write P∗ for the set of all clauses with heads in ∗ , where ∗ ∈ {<, ≥, >}. Finally, set ∗ ∶= (P∗ , , ∅) .

Let be a world. By abuse of notation, for an abductive logic program ∶= (, , ∅) we denote the logic program ∪ ( ∩ ) also by .

We first show the equivalence of 2 and 3, that stable models of < are precisely the reducts of stable models of i. Note first that < = i< . Now consider the splitting ( i< , i , i> ). This is indeed a splitting, since after intervention the propositions in have no ancestors at all. Therefore, every reduct of a stable model of i to < is a stable model of i< = < . For the other direction, let be a stable model of < = i< . Since i>, consists only of facts, it clearly has a stable model, say . By assumption, the program >, = i>, has a stable model, which by the splitting lemma is also a stable model of i and extends .

Now we turn to the equivalence of 1 and 2. Note first that for any , ( < , ≥ ) is a splitting of . Therefore, every reduct of a stable model of to < is a stable model of < .

So let be such a stable model of < . We need to show that can be extended to a stable model of . Denote < by ′. We note that ′ is closed under predecessors since ≥ is clearly closed under successors. We employ the splitting ( ′, ∖ ( ′ ∪ > ′), > ′). Note that the vocabularies used in ′ and in ∖ ( ′ ∪ > ′) are disjoint, since if a head occurring in ∖ ( ′ ∪ > ′) would be a successor of a proposition in ′, it would lie in > ′, and ′ is closed under predecessors. Since if the vocabularies of two logic programs are disjoint, the stable models of their union are precisely the unions of their stable models and is consistent (therefore ∖ ( every stable model of ′ extends to a stable model of ∖ from Formalization 2. ′ ∪ > ′) has at least one stable model), > ′. The result now follows immediately

Finally, we obtain that stratified abductive logic programs under the stable model semantics satisfy Principle 4, as formulated in Formalization 2.

Theorem 4.4. Every stratified abductive logic program satisfies Principle 4.

Proof. If ∶= ( P, , IC) is stratified, then so is P>, for every S ⊆ and every -structure . Therefore, the program P>, has (precisely) one stable model. □

5. Conclusion and Related work

Let ∶= ( P, , IC) be an abductive logic program. This work proposes a causal interpretation of that reads each clause ℎ ← 1, … , ∈ P as “ 1 ∧ ⋯ ∧ causes ℎ,” interprets the abducibles as external premises with explanations beyond a given scope, and treats the integrity constraints IC as observations. Theorem 4.2 then shows that Principles 1–3, as formulated in Formalization 1 and Definition 2.15, entail the stable model semantics [ 15 ].

However, Example 4.2 illustrates that general programs may violate Principle 4 and, therefore, do not admit a causal interpretation.

Fortunately, Theorem 4.4 confirms that stratified programs respect this principle, supporting their causal interpretability under the stable model semantics.

In the absence of observations (IC = ∅), Theorem 4.3 shows that Principle 4 implies 5. Hence, stratified programs without integrity constraints support reliable predictions under interventions.

Several authors have explored the relation between causal logic and logic programming. To our knowledge, the earliest results appeared in the context of causally enriched versions of the situation calculus [22, 23, 24]. McCain [25] and Lin and Wang [26] translate causal constraints of such languages into disjunctive logic programs with classical negation. McCain’s transformation [25] is extended to a broader class of causal theories, including first-order ones, by Ferraris et al. [ 27]. This line of work relies on classical negation, thus departing from the standard framework of negation as failure. Its aim is to make causal theories executable, rather than to provide a causal semantics for logic programs.

Conversely, some authors have investigated how logic programs themselves might admit a causal interpretation. This includes work by Giunchiglia et al. [28] and Bochman [29], who, under the stable model semantics, translate a logic programming clause of the form ← ,⃗¬ ⃗ into the causal rule ⋀¬⃗⇒ (⋀⃗→ ). Compared to the Bochman transformation in Definition 4.1, which yields the rule ,⃗¬ ⃗⇒ , this formulation is more dificult to interpret. In particular, as noted by Eelink et al. [10, §2.2.2], the use of embedded logical implication within a causal reasoning framework is far less transparent than the use of ordinary propositions. This formulation also implies that logic programs correspond only to causal rules of a highly specific syntactic form. From this perspective, logic programs could not express causal dependencies between positive atoms, which would severely limit their causal expressiveness. Moreover, to our knowledge, these works do not address the feasibility of modeling interventions, nor do they consider Principles 1, 4 and 5.

The Bochman transformation in Definition 4.1 maps a fact ℎ to a rule of the form ⊤ ⇒ ℎ, whose interpretation remains open [10, Remark 1.1]. Future work should investigate suitable causal readings of such rules, identify the class of programs satisfying Principle 4, and extend the framework to disjunctive programs. While this work addresses whether a program can meaningfully represent the efect of all interventions, it remains to be explored when a program contains suficient information to represent particular interventions, and whether Principle 5, appropriately formalized, is in fact equivalent to Principle 4.

Declaration on Generative AI

During the preparation of this work, the authors used ChatGPT in order to: Grammar and spelling check, Paraphrase and reword. After using this tool, the authors reviewed and edited the content as needed and take full responsibility for the publication’s content. [18] M. Denecker, A. C. Kakas, Abduction in logic programming, in: Computational Logic: Logic Programming and Beyond, Springer, 2002, pp. 402–436. URL: https://doi.org/10.1007/3-540-45628-7_16. [19] J. Chomicki, G. Saake (Eds.), Logics for databases and information systems, Kluwer Academic

Publishers, USA, 1998. URL: https://dl.acm.org/doi/10.5555/294135. [20] A. Bochman, Explanatory Nonmonotonic Reasoning, World Scientific, 2005. URL: https://doi.org/ 10.1142/5707. [21] V. Lifschitz, H. Turner, Splitting a logic program, in: Logic Programming, Proceedings of the Eleventh International Conference on Logic Programming, Santa Marherita Ligure, Italy, June 13-18, 1994, MIT Press, 1994, pp. 23–37. URL: https://www.cs.utexas.edu/~ai-lab/?lif94e. [22] F. Lin, Embracing causality in specifying the indirect efects of actions, in: Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI 95, Montréal Québec, Canada, August 20-25 1995, 2 Volumes, Morgan Kaufmann, 1995, pp. 1985–1993. URL: http: //ijcai.org/Proceedings/95-2/Papers/123.pdf. [23] N. McCain, H. Turner, Causal theories of action and change, in: Proceedings of the Fourteenth National Conference on Artificial Intelligence AAAI 97, AAAI Press / The MIT Press, 1997, pp. 460–465. URL: http://www.aaai.org/Library/AAAI/1997/aaai97-071.php. [24] E. Giunchiglia, V. Lifschitz, An action language based on causal explanation: Preliminary report, in: Proceedings of the Fifteenth National Conference on Artificial Intelligence AAAI 98, AAAI Press / The MIT Press, 1998, pp. 623–630. URL: http://www.aaai.org/Library/AAAI/1998/aaai98-088.php. [25] N. McCain, Causality in commonsense reasoning about actions, Ph.D. thesis, University of Texas at Austin, 1997. [26] F. Lin, K. Wang, From causal theories to logic programs (sometimes), in: Logic Programming and Nonmonotonic Reasoning, 5th International Conference, Springer, 1999, pp. 117–131. URL: https://doi.org/10.1007/3-540-46767-X_9. [27] P. Ferraris, J. Lee, Y. Lierler, V. Lifschitz, F. Yang, Representing first-order causal theories by logic programs, Theory and Practice of Logic Programming 12 (2012) 383–412. URL: https: //doi.org/10.1017/S1471068411000081. [28] E. Giunchiglia, J. Lee, V. Lifschitz, N. McCain, H. Turner, Nonmonotonic causal theories, Artificial

Intelligence 153 (2004) 49–104. URL: https://doi.org/10.1016/j.artint.2002.12.001. [29] A. Bochman, A causal logic of logic programming, in: Principles of Knowledge Representation and Reasoning: Proceedings of the Ninth International Conference, AAAI Press, 2004, pp. 427–437. URL: http://www.aaai.org/Library/KR/2004/kr04-045.php.

References

[1] J. Pearl , Causality, Cambridge University Press, 2000 . URL: https://doi.org/10.1017/ CBO9780511803161.

[2] S. Arif , M. A. MacNeil, Applying the structural causal model framework for observational causal inference in ecology , Ecological Monographs 93 ( 2023 ) e1554 . URL: https://doi.org/10.1002/ecm. 1554.

[3] C. Gao , Y. Zheng , W. Wang , F. Feng , X. He , Y. Li , Causal inference in recommender systems: A survey and future directions , ACM Transactions on Information Systems 42 ( 2024 ) 88 : 1 - 88 : 32 . URL: https://doi.org/10.1145/3639048.

[4] X. Wu , S. Peng , J. Li , J. Zhang , Q. Sun , W. Li , Q. Qian , Y. Liu , Y. Guo , Causal inference in the medical domain: a survey , Applied Intelligence 54 ( 2024 ) 4911 - 4934 . URL: https://doi.org/10.1007/ s10489-024-05338-9.

[5] V. Miller , R. Miller , René Descartes: Principles of Philosophy, Springer Dordrecht, 1982 . URL: https://doi.org/10.1007/ 978 -94-009-7888-1.

[6] A. C. Kakas , P. Mancarella , Generalized stable models: A semantics for abduction , in: 9th European Conference on Artificial Intelligence, ECAI 1990 , 1990 , pp. 385 - 391 . URL: https://www.academia. edu/50323356/Generalized_stable_ models_a_semantics_for_abduction.

[7] K. Rückschloß , F. Weitkämper , Exploiting the full power of Pearl's causality in probabilistic logic programming , in: Proceedings of the International Conference on Logic Programming 2022 Workshops , volume 3193 of CEUR Workshop Proceedings, CEUR-WS.org , 2022 . URL: https://ceur-ws. org/ Vol- 3193 /paper1PLP.pdf.

[8] K. L. Clark , Negation as failure , in: Logic and Data Bases , Springer US , 1978 , pp. 293 - 322 . URL: https://dl.acm.org/doi/book/10.5555/578615.

[9] A. Bochman , A Logical Theory of Causality , The MIT Press, 2021 . URL: https://doi.org/10.7551/ mitpress/12387.001.0001.

[10] G. Eelink , K. Rückschloß , F. Weitkämper , How artificial intelligence leads to knowledge why: An inquiry inspired by Aristotle's Posterior Analytics , 2025 . URL: https://arxiv.org/abs/2504.02430. arXiv: 2504 . 02430 .

[11] J. F. Anderson , Summa Contra Gentiles, 2 : Book Two : Creation, University of Notre Dame Press, 1956 . URL: https://doi.org/10.2307/j.ctvpj74rh.

[12] G. W. Leibniz , First truths , in: Philosophical Papers and Letters , Springer Netherlands, 1989 , pp. 267 - 271 . URL: https://doi.org/10.1007/ 978 -94-010-1426-7_ 31 .

[13] J. Williamson , Foundations for Bayesian Networks, Springer Netherlands, 2001 , pp. 75 - 115 . URL: https://doi.org/10.1007/ 978 -94-017-1586- 7 _ 4 .

[14] J. Barnes , The Complete Works of Aristotle . Volume One., Princeton University Press, 1995 . URL: https://doi.org/10.2307/j.ctt5vjv4w.

[15] M. Gelfond , V. Lifschitz , The stable model semantics for logic programming , in: Proceedings of International Logic Programming Conference and Symposium , MIT Press, 1988 , pp. 1070 - 1080 . URL: http://www.cs.utexas.edu/users/ai-lab? gel88 .

[16] D. Saccà , C. Zaniolo , Stable models and non-determinism in logic programs with negation , in: Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems , ACM Press, 1990 , pp. 205 - 217 . URL: https://doi.org/10.1145/298514.298572.

[17] V. Lifschitz , Thirteen definitions of a stable model , in: Fields of Logic and Computation , Springer, 2010 , pp. 488 - 503 . URL: https://doi.org/10.1007/978-3- 642 -15025-8_ 24 .