$\begin{array}{ccccccccccccccccc}w&-&\\ Pr&\mbox{\it Mo}B,H&\mbox{\it Pr}&B&\mbox{\it Pr}&B&\\ &&&&\\ &Pr&BL&G&\mbox{\it Pr}&B&\mbox{\it Pr}&L&G&w&\mbox{\it Pr}&B\\ &&&&\\ &Pr&BL&H&\mbox{\it Pr}&B&\mbox{\it Pr}&L&H&z&\mbox{\it Pr}&B\\ &&&&\\ &&&&\\ &Pr&\mbox{\it Pr}&\mbox{\it Pr}&\mbox{\it Pr}&B&\mbox{\it Pr}&B\\ &&&&\\ &Pr&\mbox{\it Pr}&\mbox{\it Pr}&\mbox{\it Pr}&B&\mbox{\it Pr}&B\\ &&&&\\ &Pr&\mbox{\it Pr}&\mbox{\it Pr}&\mbox{\it\{B},L&G&L&H}&\mbox{\it Pr}&A\\ &&&&\\ &&&&\\ &A&A&\mbox{\it\{B,L&G\}}\end{array}$

generally not 1.

In this section, we give the proofs of Theorems 4.7 and 4.8.

We need some technical preparations as follows. The next lemma helps us to show the

The following lemma helps us to show the local soundness and the local completeness

Pr BL G L H )) min(Pr BL G)); Pr BL H))) Pr BL G L H )) min(Pr BL G)); Pr BL H))) : By Lemma A.2 with B B B ; G fBg B B B ; H fBg B B B L G), and B L H), there is probabilistic interpretation Pr over B B ; C with (12). Hence, it holds Pr Mo B ; C and Pr B 0. By Lemma B.4 b), we get: Pr BL C)) Pr BL G L H)) min( ; x Pr B Pr L C)) Pr L G L H)) min(w ; z ; v + ; x + Pr B : 2
Finally, note that computing least upper bounds is more dicult than computing great- est lower bounds, since for each edge B C by Lemmata 3.1 and B.4 a), the greatest lower )) Pr B sub ject to Pr Mo B ; C and Pr B is always 0, but the least upper bound of Pr BCL C" )) Pr B sub ject to Pr Mo B ; C and Pr B is

bound of Pr BCL C"

## Appendix C. Proofs For Section 4.2

local soundness of the function H 
in Fusion Lemma C.5 For al l real numbers u ; u; v ; v; x ; x; y ; y (0; 1] with u u, ,
, y y, and u + , it holds:

min(u=v u; x=y u + 1) min(u =v u ; =y u + 1) : Proof. The claim can easily be veried (Lukasiewicz, 1996). 2

of the function H 
in Chaining and Fusion Lemma C.6 a) Let u, , , and y be real numbers from (0; 1]. For al l probabilistic interpretations Pr with Pr L C"
)) , the conditions u Pr B Pr BC , Pr C Pr BC ,

Pr C Pr CL C "
)), and y Pr L C")) Pr CL C ")) are equivalent to: