Proof. The claims can be veried by straightforward arithmetic transformations based on the properties of probabilistic interpretations. 2 completeness of the functions H  H  H 
and H 
Proof of Theorem 4.1. The claims are proved by induction on the recursive denition of H 
The case C B : : : Bk is tackled by iteratively splitting C into two conjunctive events. Thus, it is reduced to C GH with conjunctive events G and H that are disjoint in their basic events. For C B we dene u Pr C B), Pr B C), and H C; C").

For C B : : : Bk hence C GH let H  B ; G and H  B ; H). a) All models Pr Mo B ; C with Pr B satisfy the indicated condition. In the sequel, let Pr Mo B ; C with Pr B 0.

Basis: Let C B Since C L C), we get:

After these preparations, we are now ready to prove the global soundness and the global

 Pr B Pr B Pr BC Pr BL C)) : Induction: Let C B For all models Pr Mo C; C"), we get by the induction hypothesis )). Thus, Pr satises the same conditions. Since L C"L C
$$P r\;\;B L\;\;C\;\;\;\;.$$

Pr C Pr CL C"

and by Lemmata A.1 and B.4 a), we then get:

b)

 Pr B max(0; u u v + ux v Pr B Pr BL C")) Pr BL C)) : Let C GH For all Pr Mo B ; G and Pr Mo B ; H), we get by the induction hypothesis Pr B Pr BL G)) and Pr B Pr BL H)). Thus, Pr satises the same conditions. Since L G L H L GH L C and by Lemmata A.1 and B.4 b):

max(0; v + 1) Pr B Pr BL G L H)) Pr BL C)) :
Basis: Let C B model Pr Mo B ; C such that Pr B 0, Pr B) =  Pr B Pr BL C)), and Pr BL C)) is given by B ; B ; 1. Induction: Let C B Let the model Pr of f C B)[u; u ; B C)[v; v g with Pr B and Pr C be dened like in the proof of Theorem 3.2. We now choose an appropriate model Pr Mo C; C"). Let us rst consider the

case 0, = 1, or not L C"C By the induction hypothesis, there exists model Pr Mo C; C" with Pr C 0, Pr C Pr CL C")), and Pr CL C"))
i L C"C Let us next assume = 0, 1, and L C"C By Theorem 3.2, there exists model Pr 00 Mo C; C"with Pr 00 CL C")) 0. By the induction hypothesis, there exists model Pr 0 Mo C; C" with Pr 0C and Pr 0C Pr 0CL C")).

Hence, there exists model Pr Mo C; C"with Pr C and min(1 v; Pr 00 CL C")) Pr 00 C)) Pr C Pr CL C")) :
By Lemma 3.1, we can choose Pr and Pr with Pr C Pr C and Pr B C

Pr CL C"
)). By Lemmata A.1 and B.4 a), we can choose the probabilistic interpretation
