Database Reference
In-Depth Information
P(Q
W
)
=
P(h
30
∨
h
32
)
+
P(h
30
∨
h
33
)
+
P(h
31
∨
h
33
)
−
P(h
30
∨
h
32
∨
h
33
)
−
P(h
30
∨
h
31
∨
h
33
)
Each of the five expressions above can be computed using the rules. Thus, we can compute
P(Q
W
)
using the rules
provided
we are careful to cancel out terms in the inclusion-exclusion formula;
otherwise, we will get stuck trying to compute
P(H
3
)
(twice !).
The coefficients of the inclusion-exclusion formula are given by the
Möbius function in a lattice
;
we review it here, and also refer to
Figure 4.2
for a short primer.
A
lattice
is a partially ordered set
(L,
≤
)
where any two elements
x,y
∈
L
have a least upper
bound
x
y
. We will consider only finite lattices in this topic. It
follows that every subset
U
⊆
L
has a least upper bound
U
and a greatest lower bound
U
;in
particular,
L
has a minimum element 0
∨
y
and a greatest lower bound
x
∧
=
L
. A finite lattice
admits an alternative, equivalent definition, as an algebraic structure
(L,
∨
,
∧
,
0
,
1
)
, where
=
L
and a maximum element 1
∨
,
∧
are
binary operators that are associative, commutative, satisfy the absorption laws (
x
∨
(x
∧
y)
=
x
and
x
∧
(x
∨
y)
=
x
), and have neutral elements 0 and 1 respectively. The operations
∨
and
∧
are called
join
and
meet
respectively.
We define the Möbius function next:
Definition 4.11
The Möbius function
μ
L
:
L
×
L
→
int
is defined as follows:
μ
L
(u, u)
=
1
μ
L
(u, v)
=−
μ
L
(w, v)
w
:
u<w
≤
v
We drop the subscript
L
when it is clear from the context and write simply
μ(u, v)
.By
definition, if
u
≤
v
, then
μ(u, v)
=
0. For the most part of this topic, the second argument of the
Möbius function is 1, and we refer to
μ(u,
1
)
as “the Möbius value at
u
”. For a simple illustration,
consider the lattice in
Figure 4.1
, with 7 nodes. We compute
μ(u,
1
)
, for every node
u
in the lattice,
starting from the top node
1. By definition
μ(
1
,
1
)
=
1. Next,
μ(u
1
,
1
)
=−
μ(
1
,
1
)
=−
1, and
similarly
μ(u
2
,
1
)
μ(u
3
,
1
)
1. Next,
μ(u
4
,
1
)
1, and similarly
μ(u
5
,
1
)
=
=−
=−
(
1
−
1
−
1
)
=
=
1. Finally,
μ(
0
,
1
)
=−
(
1
−
−
−
+
+
1
)
=
0.
The Möbius function in a lattice generalizes the classical Möbius function on numbers and
has an elegant interpretation as the inverse of the zeta function in the incidence algebra defined by
the lattice
L
: we refer the reader to
Stanley
[
1997
] for background on the Möbius function. For our
purpose, we will simply use the definition above as given.
1
1
1
1
