supposing that the truth of the body causes the truth of one of the atoms in the head non-deterministically chosen on the basis of the annotations.

An LPAD theory T **consists of a finite set of** *annotated disjunctive clauses***. These**
clauses have the following form
(H1 : α1) ∨ (H2 : α2) ∨ . . . ∨ (Hh : αh) : −B1, B2**, . . . B**b where the His are logical atoms, the Bis are logical literals and the αi**s are real**
numbers in the interval [0, **1] such that** Ph i=1 αi ≤ **1. If** Ph i=1 αi < **1, the head of**
the clause implicitly contains an extra atom null **that does not appear in the body**
of any clause and whose annotation is 1−Ph i=1 αi. If C is the clause above, H(**C, i**)
is Hi, α(C, i) is αi and body(C) is B1, B2**, . . . B**b.

The semantics of a non-ground theory T **is defined through its grounding** g(T )
and Vennekens et al. (2004) require that g(T **) is finite.**
An *atomic choice* χ is a triple (C, θ, i) where C ∈ T , θ **is a substitution that**
grounds C and i ∈ {1, . . . , n} where n **is the number of atoms in the head of**
C. (C, θ, i) means that, for the ground clause Cθ, the head H(C, i) : α(C, i**) was**
chosen. A *selection* σ **is a set of atomic choices such that for each clause** Cθ in g(T ) there exists one and only one atomic choice (C, θ, i) in σ**. We denote the set of all**
selections of a program T by ST .

A selection σ identifies a normal logic program Tσ = {(H(C, i) : −**body**(C))θ|
(C, θ, i) ∈ σ} **that is called an** *instance* of T . A probability distribution is defined over the space of instances by assuming independence among **the choices**
made for each clause, thus the probability Pσ of an instance Tσ is given by Pσ = Q(C,θ,i)∈σ α(**C, i**).

The meaning of the instances of an LPAD is given by the well-founded semantics.

For each instance Tσ, we require that its well-founded model W F(Tσ**) is total, since**
we want to model uncertainty only by means of disjunctions.

The probability of a formula Q **is given by the sum of the probabilities of the**
instances in which the formula is true according to the well-founded semantics:

$$\mathcal{D})=\sum_{\sigma\in\mathcal{S}_{T},W F(T_{\sigma})\models Q}P_{\sigma}$$

An LPAD T can be translated into a Bayesian network β(T **) that has a Boolean**
random variable for each ground atom plus a random variable choiceCθ **for each**
grounding Cθ of each clause C of T **whose values are the atoms in the head of** Cθ plus **null**.

choiceCθ assumes value H(C, i)θ with probability α(C, i**) if the configuration of**
its parents makes the body true, while it assumes value null **with probability 1 if**
the configuration makes the body false. The parents of ground atom A **are all the**
choiceCθ variables such that A appears in the head of Cθ. A **assumes value true**
with probability 1 if one of the parent choice variables assumes value A**, otherwise**
it assumes value false with probability 1.

Various approaches have been proposed for computing the probability of queries from an LPAD. Riguzzi (2008) discusses an extension of SLG resolution, called SLGAD, that is able to compute the probability of queries by repeatedly branching on