the different proofs to obtain the success probability, as a specific subprogram can allow several proofs and therefore contributes to the probability of each of these proofs. Indeed, in our example, all programs that are supersets of *{edge(c,e),edge(e,d),edge(c,d)}* contribute to the marginals of both proofs and would therefore be counted twice if summing the probabilities of the proofs. However, for mutually exclusive conjunctions, that is, conjunctions describing disjoint sets of subprograms, the probability is the sum of the individual probabilities. This situation can be achieved by adding *negated* random variables to a conjunction, thereby explicitly excluding subprograms covered by another part of the formula from the corresponding part of the sum. In the example, extending $ce \wedge ed$ to $ce \wedge ed \wedge \neg cd$ reduces the second part of the sum to those programs not covered by the first: $$P_s(path(c,d)|T)=P(cd \vee (ce\wedge ed)|T)$$$$= P(cd|T)+P(ce\wedge ed\wedge\neg cd|T)$$$$= 0\ldotp9 + 0\ldotp8\cdot0\ldotp5\cdot(1-0\ldotp9)=0\ldotp94$$

However, as the number of proofs grows, disjoining them gets more involved. Consider for example the query *path(a,d)* which has four different but highly interconnected proofs. In general, this problem is known as the *disjoint-sum-problem* or the two-terminal network reliability problem, which is \#P-complete [@Valiant1979].

Before returning to possible approaches 