
## 3. Distribution Semantics

In this section, we introduce parameterized logic programs and define their declarative se­
mantics. The basic idea is as follows. We start with a set F of probabilistic facts (atoms)
and a set R of non-unit definite clauses. Sampling from F determines a set F ′ of true atoms, and the least Herbrand model of F ′ ∪ R determines the truth value of every atom in DB = F ∪ R. Hence every atom can be considered as a random variable, taking on 1
(true) or 0 (false). In what follows, we formalize this process and construct the underlying probability space for the denotation of DB.

## 3.1 Basic Distribution Pf

Let DB = FUR be a definite clause program in a first-order language L with countably many variables, function symbols and predicate symbols where F is a set of unit clauses ( facts ) and R a set of non-unit clauses ( rules ). In the sequel, unless otherwise stated, we consider for simplicity DB as the set of all ground instances of the clauses in DB , and assume that F and R consist of countably infinite ground clauses (the finite case is similarly treated).

We then construct a probability space for DB in two steps. First we introduce a probability space over the Herbrand interpretations 11 of F i.e. the truth assignments to ground atoms in F . Next we extend it to a probability space over the Herbrand interpretations of all ground atoms in L by using the least model semantics (Lloyd, 1984; Doets, 1994).

Let A 1 , A 2 , . . . be a fixed enumeration of atoms in F . We regard an infinite vector ω =
(x 1 , x 2 , . . ) of 0s and 1s as a Herbrand interpretation of F in such a way that for i = 1, 2, . .

Ai is true (resp. false) if and only if xi = 1 (resp. xi = 0). Under this isomorphism, the set of all possible Herbrand interpretations of F coincides with the Cartesian product:

$$\Omega_{F}\ {\stackrel{\mathrm{def}}{=}}\ \prod_{i=1}^{\infty}\left\{0,\,1\right\}_{i}.$$

We construct a probability measure P F over the sample space Ω F 12 from a collection of finite joint distributions Pfn 1 (A1 = x 1 , . . , An = xn ) (n = 1 , 2 , . . , xi E {0 , 1 }, 1 < i < n )
such that

$$0\leq P_{F}^{\{n\}}(A_{1}=x_{1},\ldots,A_{n}=x_{n})\leq1$$ $$\sum_{x_{1},\ldots,x_{n}}P_{F}^{\{n\}}(A_{1}=x_{1},\ldots,A_{n}=x_{n})=1\tag{3}$$ $$\sum_{x_{n+1}}P_{F}^{\{n+1\}}(A_{1}=x_{1},\ldots,A_{n+1}=x_{n+1})=P_{F}^{\{n\}}(A_{1}=x_{1},\ldots,A_{n}=x_{n}).$$
$\blacksquare$
The last equation is called the compatibility condition . It can be proved (Chow & Teicher, 1997) from the compatibility condition that there exists a probability space ( Ω F, F, P F )
where P F is a probability measure on F , the minimal σ algebra containing open sets of Ω F , such that for any n,