Database Reference
In-Depth Information
is a disjoint-or, and therefore we
obtain the following rule, which is called the
Shannon-expansion rule
:
Obviously, every
∧
is an independent-and, and every
∨
Shannon expansion:
P ()
=
P(
|
X
=
a
i
)
·
P(X
=
a
i
)
(5.5)
i
=
0
,m
In contrast to the rules of independent-and, independent-or, and disjoint-or, Shannon ex-
pansion can always be applied.
We note that the disjoint-or rule has a natural dual, which is the following. If
1
∨
2
≡
true
,
then
P(
1
∧
2
)
=
P(
1
)
+
P(
2
)
−
1. Traditionally, this rule does not seem to have been used
in practice, so we do not include it in our discussion.
5.1.2 AN ALGORITHM FOR
P ()
The five rules can be combined into a simple non-deterministic algorithm for computing
P ()
,
shown in
Algorithm 2
. It proceeds recursively on the structure of the propositional formula
,
applying the rules described earlier, until it reaches an atomic formula
X
=
a
, when it simply looks
up its probability in a table.
We describe briefly how the algorithm works. Consider any propositional formula
.If
is a
conjunction
1
∧
2
∧
...
, then the algorithms tries to partition the conjuncts into independent sets.
For that, construct a graph whose nodes
V
correspond to the conjuncts
1
,
2
,...
,
and whose edges
(i, j)
correspond to pairs of conjuncts
i
,
j
={
1
,
2
,...
}
such that
Va r (
i
)
∩
Va r (
j
)
=
. Compute the connected components of this graph,
C
1
,C
2
...
, and define
i
=
j
∈
C
i
j
the
conjunction of all conjuncts in the component
C
i
. Then
=
1
∧
2
∧
...
and, moreover, the
formulas
1
,
2
,...
are independent. This explains the
independent AND
rule (
Algorithm 2
shows
the rule for only a conjunction of two formulas: it generalizes obviously to
m
≥
∅
2 formulas). Notice
that this rule can be applied only if there are
≥
2 connected components: otherwise, the algorithm
makes no progress. If
is a disjunction, then we proceed similarly and use the
independent OR
rule.
Alternatively, we can check whether
is disjunction of disjoint formulas and apply disjoint-or. If
is a negation, then we apply the negation rule. If everything else fails, then we can always apply the
Shannon expansion rule.
The algorithm is non-deterministic: the Shannon expansion step can always be applied even
if one of the other rules applies, and there are several choices for the order in which to eliminate
variables during the Shannon expansion steps.
Example 5.7
Consider the formula
=
(X
∨
Y)
∧
((Z
∧
U)
∨
(
¬
Z
∧
V))
. We can apply the
independent-and rule and obtain
P ()
=
P(
1
)
·
P(
2
),
where
1
=
X
∨
Y,
and
2
=
(Z
∧
U)
∨
(
¬
Z
∧
V).