
## Appendix A. Properties Of Pdb

In this appendix, we list some properties of PDB defined by a parameterized logic program DB = F ∪ R in a countable first-order language L . 69  First of all, PDB assigns consistent probabilities70 to every closed formula ¢ in L by PDB($) dcf PDB({w E SDB | w |= $})
while guaranteeing continuity in the sense that

$$\begin{array}{r c l}{{\operatorname*{lim}_{n\to\infty}P_{D\!B}\left(\,\phi(t_{1})\wedge\,\cdot\,\cdot\,\cdot\,\wedge\,\phi(t_{n})\,\right)}}&{{=}}&{{P_{D\!B}\left(\,\forall\,x\,\phi(\,x\,)\,\right)}}\\ {{\operatorname*{lim}_{n\to\infty}P_{D\!B}\left(\,\phi(t_{1})\vee\,\cdot\,\cdot\,\vee\,\phi(t_{n})\,\right)}}&{{=}}&{{P_{D\!B}\left(\,\exists\,x\,\phi(\,x\,)\,\right)}}\end{array}$$

where t 1 ,t 2 ,... is an enumeration of ground terms in L.

The next proposition, Proposition A.1, relates PDB to the Herbrand model. To prove it, we need some terminology. A factor is a closed formula in prenex disjunctive normal form Q 1 · · Q n M where Q i (1 < i < n) is either an existential quantification or a universal quantification and M a matrix. The length of quantifications n is called the rank of the factor. Define Φ as a set of formulas made out of factors, conjunctions and disjunctions.

Associate with each formula $ in Φ a multi-set r($) of ranks by

$$r(\phi)=\left\{\begin{array}{c c c}{{\emptyset}}&{{\mathrm{if}}}&{{\phi\ \mathrm{is\ a\ factor\ with\ no\ quantification}}}\\ {{\{\ n\}}}&{{\mathrm{if}}}&{{\phi\ \mathrm{is\ a\ factor\ with\ rank\ }n}}\\ {{r(\phi_{1})\uplus r(\phi_{2})}}&{{\mathrm{if}}}&{{\phi=\phi_{1}\vee\ \phi_{2}\ \mathrm{or}\ \phi=\phi_{1}\wedge\phi_{2}.}}\end{array}\right.$$

Here U stands for the union of two multi-sets. For instance {1, 2, 3} U{2, 3, 4} = {1, 2, 2, 3, 3, 4}. We use the multi-set ordering in the proof of Proposition A.1 because the usual induction on the complexity of formulas does not work.

Lemma A.1 Let φ be a boolean formula made out of ground atoms in L.  PDB(φ) =
PF({v E ΩF | MDB(v) |= ¢}).

(Proof) We have only to prove the lemma about a conjunction of atoms of the form D 11 ^
··· ∧ D x n ( x i E {0, 1 }, 1 ≤ i ≤ n ).

$$P_{\mathit{DB}}(\,D_{1}^{x_{1}}\wedge\cdots\wedge D_{n}^{x_{n}})=P_{\mathit{DB}}(\{\,\omega\in\Omega_{\mathit{DB}}\mid\omega\models D_{1}^{x_{1}}\wedge\cdots\wedge D_{n}^{x_{n}}\})$$ $$=P_{\mathit{DB}}(\,D_{1}=x_{1},\ldots,D_{n}=x_{n})$$ $$=P_{F}(\{\,\nu\in\Omega_{F}\mid M_{\mathit{DB}}(\nu)\models D_{1}^{x_{1}}\wedge\cdots\wedge D_{n}^{x_{n}}\})$$ Q.E.D.  
Proposition A.1 Let φ be a closed formula in L. Pdb(φ) = P F ({ν ∈ Ω F | Mdb(ν) |= φ}).