
## Acknowledgements

want to thank Thomas Eiter for valuable comments on an earlier version of this paper. This paper is an extended and revised version of paper that appeared in Principles of Know ledge Representation and Reasoning: Proceedings of the 6th International Conference pp. 380{391.

## Appendix A. Preliminaries Of The Proofs For Sections 4.1 To 4.3

4.7, 4.8, and 4.9. In the sequel, we use the notation

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

 $\begin{array}{ccc}a\:ll\:i,&\quad\{&,\quad\}\,i\\ \\ ll\ n,\:m&\quad\{&,\quad\},\\ \\ \textit{for}\:all\ n,\:m&\quad\{&,\quad\}\end{array}$  $\begin{array}{ccc}\square\\ \\ \end{array}$
as an abbreviation of the following system of equations:

(11)

The next lemma provides the optimal values of two linear programs to be solved in the

Lemma A.1 Let r ; r ; c ; c with r + r c + c . For al l i; j f ; g:

a) min(ri; cj max i;j subject to (11) and n;m for al l n; m f ; g. b) max(0; ri c j min i;j subject to (11) and n;m for al l n; m f ; g. Proof. The claims can easily be veried (Lukasiewicz, 1996). 2

am very grateful to Michael Wellman and the referees for their useful comments. also

In this section, we make some technical preparations for the proofs of Theorems 4.1, 4.2,

proofs of Theorems 4.1, 4.2, 4.7, 4.8, and 4.9.

Let us assume that conditional constraint tree is the union of two subtrees that have

just one node in common. model of each subtree and third model related to the

common node can now be combined to model of the whole conditional constraint tree.

This important result follows from the next lemma.

Lemma A.2 Let B and B be sets of basic events with B \ B . Let B be a new basic event that is not contained in B B . Let Pr and Pr be probabilistic interpretations on the atomic events over B [ fB g and B [ fB g, respectively. Let B and B be conjunctive events over B and B , respectively. Let Pr be a probabilistic interpretation on the atomic events over fB ; B ; B g with Pr H0 H1 Pr H0 H1 and Pr H0 H2 Pr H0 H2 for al l atomic events H , H , and H over fB g, fB g, and fB g, respectively.

There is a probabilistic interpretation Pr on the atomic events over B [ B [ fB g with:

Pr H0 H1 H2 Pr H0 H1 H2 ; Pr H0 A1 Pr H0 A1 ; and Pr H0 A2 Pr H0 A2

(12)
