Database Reference
In-Depth Information
P(Y
∨
Z)
=
1
−
(
1
−
P(Y))
·
(
1
−
P(Z))
, also because of independence, which leads to:
P ()
=
P(X)
·
(
1
−
(
1
−
P(Y))
·
(
1
−
P (Z)))
For the general approach, we need a definition.
Definition 5.1
For a propositional formula
denote by
Va r ()
the set of propositional variables
on which
depends. More precisely,
Va r ()
consists of all variables
X
such that there exists an
assignment
θ
to the other
n
−
1 variables, and two values
a, b
∈
such that
[
θ
∪{
X
→
Dom
X
a
}] =
[
θ
∪{
X
→
b
}]
.
Intuitively,
Va r ()
consists of all the variables used in
, and it is called the
support
of
.
One needs to be careful when computing the support
Va r ()
because not all variables that occur
syntactically in
are part of the support. Instead, one needs to simplify
first, then
Va r ()
consists
of all variables that still occur in
. For example, if
=
Y
∨
XY
then
does not depend on
X
because the absorption law simplifies it to
=
Y
and therefore
Va r ()
={
Y
}
. The definition above
takes care of this by requiring that
[
θ
]
actually depend on
X
.
Two propositional formulas
1
,
2
are called
syntactically independent
if
Va r (
1
)
∩
Definition 5.2
Va r (
2
)
=∅
.
The following is easy to check:
Proposition 5.3
If
1
,
2
,...,
k
are pairwise syntactically independent, then the probabilistic events
1
,
2
,...,
k
are independent.
Our first two rules for computing
P ()
are
independent-and
and the
independent-or
rules and
are defined as follows. If
1
,
2
are syntactically independent, then:
Independent-and:
P(
1
∧
2
)
=
P(
1
)
·
P(
2
)
(5.1)
Independent-or:
P(
1
∨
2
)
=
1
−
(
1
−
P(
1
))
·
(
1
−
P(
2
))
(5.2)
Checking if two formulas are syntactically independent is co-NP-complete in general, because
SAT can be reduced to syntactic dependence: if
is a formula and
X
a variable that does not occur
in
, then
X
and
X
are syntactically dependent iff
is satisfiable. In practice, however, it
suffices to use a sufficient condition for syntactical independence. Given a propositional formula
expression
, denote
V ()
the set of variables that occur in
. Obviously,
V ()
can be computed
in polynomial time, and
Va r ()
⊆
V ()
. For example, for the expression
=
Y
∨
XY
, we have
Va r ()
={
Y
}
∧
and
V ()
={
X, Y
}
. Then, for any two formulas
1
,
2
,if
V(
1
)
∩
V(
2
)
=∅
,
then
1
and
2
are syntactically independent: the condition
V(
1
)
∩
V(
2
)
=∅
can be computed
