  We introduce a formal logical language, called conditional probability logic
(CPL), which extends first-order logic and which can express probabilities,
conditional probabilities and which can compare conditional probabilities.
Intuitively speaking, although formal details are different, CPL can express
the same kind of statements as some languages which have been considered in the
artificial intelligence community. We also consider a way of making precise the
notion of lifted Bayesian network, where this notion is a type of (lifted)
probabilistic graphical model used in machine learning, data mining and
artificial intelligence. A lifted Bayesian network (in the sense defined here)
determines, in a natural way, a probability distribution on the set of all
structures (in the sense of first-order logic) with a common finite domain $D$.
Our main result is that for every "noncritical" CPL-formula $\varphi(\bar{x})$
there is a quantifier-free formula $\varphi^*(\bar{x})$ which is "almost
surely" equivalent to $\varphi(\bar{x})$ as the cardinality of $D$ tends
towards infinity. This is relevant for the problem of making probabilistic
inferences on large domains $D$, because (a) the problem of evaluating, by
"brute force", the probability of $\varphi(\bar{x})$ being true for some
sequence $\bar{d}$ of elements from $D$ has, in general, (highly) exponential
time complexity in the cardinality of $D$, and (b) the corresponding
probability for the quantifier-free $\varphi^*(\bar{x})$ depends only on the
lifted Bayesian network and not on $D$. The main result has two corollaries,
one of which is a convergence law (and zero-one law) for noncritial
CPL-formulas.
