Determining lower and upper bounds on probabilities of atomic propositions in sets of logical formulas represented by digraphs

In this paper we consider the problem of determining lower and upper bounds on probabilities of atomic propositions in sets of logical formulas represented by digraphs. We establish a sharp upper bound, as well as a lower bound that is not in general sharp. We show further that under a certain condition the lower bound is sharp. In that case, we obtain a closed form solution for the possible probabilities of the atomic propositions.The second author is partially supported by ONR grant N00014-92-J-1028 and AFOSR grant 91-0287.