constraints KB denoted Pr KB i Pr is model of all H G)[u ; u KB KB is satisable i model of KB exists. H G)[u ; u is logical consequence of KB; denoted KB H G)[u ; u ], i each model of KB is also model of H G)[u ; u ]. For conditional constraint H G)[u ; u and set of conditional constraints KB let u denote the set of all real numbers u [0; 1] for which there exists model Pr of KB with u Pr G Pr GH and Pr G 0. Now, we easily verify that H G)[u ; u is logical consequence of KB i u inf u and u sup u This observation yields canonical notion of tightness for logical consequences of con-
$$\begin{array}{c c}{{s a t i s f i a b l e}}\\ {{K B}}&{{H}}\end{array}$$  $$\begin{array}{c c}{{u}}&{{}}\\ {{u}}&{{P r}}\end{array}G$$

i it computes the tight answer to any given query from

In the framework of conditional constraints over propositional events, the optimization problem of deciding whether propositional formula in conjunctive normal form is satisable;

see especially the survey by Garey and Johnson, 1979).

Surprisingly, the optimization problem of computing the tight answer to probabilistic

can be polynomially-reduced to the optimization problem of computing the tight answer

This observation yields canonical notion of tightness for logical consequences of con- ditional constraints. The conditional constraint H G)[u ; u is tight logical consequence of KB; denoted KB tight H G)[u ; u ], i u inf u and u sup u The set u is closed interval in the real line (Frisch Haddawy, 1994). Note that for u we canonically dene inf u max [0; 1] and sup u min [0; 1] 0. Thus, u i KB Gj>)[0; 0] i KB tight H G)[1; 0] i KB H G)[u ; u for all u ; u [0; 1]. Based on the just introduced notion of tight logical consequence, probabilistic deduction

problems and their solutions are more formally specied as follows. probabilistic know ledge base B; KB consists of set of basic events B and set of conditional constraints KB over GB with u u for all H G)[u ; u KB probabilistic query to probabilistic knowledge base B; KB is an expression of the form E)[ ; x with E ; F GB and two dierent variables and Its tight answer is the substitution f =u ; =u g with u ; u [0; 1] such that KB tight E)[u ; u (we call f =u g the tight lower answer and f =u g the tight upper answer). correct answer is substitution f =u ; =u g with u ; u [0; 1] such that KB E)[u ; u ]. Finally, we dene the notions of soundness and of completeness related to inference

3  $\begin{array}{c}prob\,ba\,b\,b\,l\,is\,t\,c\\ E\end{array}$ ! 
$\begin{array}{l}correct\:\:an\,sw\,err\\ E\;\;\;u\;\;,u\end{array}$  . 

Finally, we dene the notions of soundness and of completeness related to inference rules and to techniques for probabilistic deduction. An inference rule KB H G)[u ; u is sound i KB H G)[u ; u ], where H G)[u ; u is conditional constraint and KB is set of conditional constraints. It is sound and local ly complete i KB tight H G)[u ; u ]. technique for probabilistic deduction is sound for set of probabilistic queries i it com- putes correct answer to any given query from It is sound and global ly complete for

## 2.2 Computational Complexity

lem of computing the tight answer to probabilistic query is immediately NP-hard, since it

generalizes the satisability problem for classical propositional logic (the NP-complete prob-
query remains NP-hard even if we just consider conditional constraints over basic events:

Theorem 2.1 The optimization problem of computing the tight answer to a probabilistic query over basic events that is directed to a probabilistic know ledge base over basic events is NP-hard.

Proof. The NP-complete decision problem of graph 3-colorability (Garey Johnson, 1979)

$$\begin{array}{c}{{\mathrm{N}}}\\ {{\mathrm{N}}}\end{array}$$
