Database Reference
In-Depth Information
a constant polynomial, it must depend on at least one of these variables, say
x
i,j
1
. Then the poly-
nomial
P(
1
)
must also depend on
x
i,j
1
. Similarly, the polynomial
P(
2
)
must depend on some
variable
x
i,j
2
, with the same index
i
. Then, the identity
P(
1
)
2
)
implies that
the latter polynomial contains the product
x
i,j
1
·
x
i,j
2
, violating either condition (a) (when
j
1
=
j
2
)
or condition (b) (when
j
1
=
·
P(
2
)
=
P(
1
∧
j
2
), which is a contradiction. This proves the claim.
5.1.1.2 Rule 3: Disjoint OR
To motivate the next heuristics, consider the formula
3
=¬
X
∧¬
Y
∨
X
∧
Y
above. Since the
two events
¬
X
∧¬
Y
and
X
∧
Y
are disjoint probabilistic events, we have:
P(
3
)
=
P(
¬
X
∧¬
Y)
+
P(X
∧
Y)
=
(
1
−
P(X))
·
(
1
−
P(Y))
+
P(X)
·
P(Y)
Two propositional formulas
1
,
2
are called
disjoint
if the formula
1
∧
2
is
Definition 5.5
not satisfiable.
The
disjoint-or
rule is the following. If
1
,
2
are disjoint formulas, then:
Disjoint-or:
P(
1
∨
2
)
=
P(
1
)
+
P(
2
)
(5.3)
5.1.1.3 Rule 4: Negation
It is easy to push the probability operator past negation:
P(
¬
)
=
−
P ()
Negation:
1
(5.4)
5.1.1.4 Rule 5: Shannon Expansion
We illustrate Shannon's expansion using the following example:
=
XY
∨
XZ
∨
YZ
.None
of our prior rules apply immediately here. Instead, we write it as a disjoint-or:
=
(
∧
X)
∨
(
∧¬
X)
; hence,
P ()
=
P(
∧
X)
+
P(
∧¬
X)
. Denote
|
X
=
Y
∨
Z
∨
YZ
≡
Y
∨
Z
the formula obtained from
by substituting
X
with
true
. Similarly,
|
¬
X
=
YZ
. Then,
we have
P ()
=
P(
|
X
∧
X)
+
P(
|
¬
X
∧¬
X)
=
P(Y
∨
Z)
·
P(X)
+
P(YZ)
·
(
1
−
P(X))
=
(
1
−
(
1
P(X))
.
In general, given a propositional formula
, a random variable
X
, and a value
a
∈
−
P(Y))
·
(
1
−
P (Z)))
·
P(X)
+
P(Y)
·
P(Z)
·
(
1
−
Dom
X
,
denote
|
X
=
a
the formula obtained from
by substituting all occurrences of
X
with
a
. Note that
the formula
|
X
=
a
does not depend on the variable
X
:
X
∈
Va r (
|
X
=
a
)
Let
Dom
X
={
a
0
,a
1
,...,a
m
}
Definition 5.6
. Then the Shannon expansion of a propositional
formula
is:
≡
|
X
=
a
0
∧
(X
=
a
0
)
∨
|
X
=
a
1
∧
(X
=
a
1
)
∨
...
∨
|
X
=
a
m
∧
(X
=
a
m
)
