F1-28
© J. Kalisz, WAT, 2008
0
)
Formy boolowskie 4
•
Dekompozycja: twierdzenie Shannona o rozkładzie
sumacyjnym funkcji logicznej
względem jednej
zmiennej (x
0
):
l
n
n
n
n
n
n
f x
x
x
f x
x
x
f x
x
x
1
2
0
1
2
0
1
2
)
)
(
,
,...,
(
,
,...,1
(
,
,...,0
−
−
−
−
−
−
=
+
Np. funkcja trzech zmiennych
l
l
l
l
l
l
l
f x x x
x x x
x x x
x x x
x x x
x x
x x x
2
1
0
2 1 0
2 1 0
2 1 0
2 1
0
2 1
2 1
0
)
(
, ,
(
)
(
)
=
=
+
+
+
+
po rozkładzie zawiera dwie funkcje o dwu zmiennych (x
1
i x
2
).
• Rozłożenie względem
drugiej
zmiennej (x
2
):
1
2
0
1
2
1 0
1
2
1 0
1
2
1 0
1
2
1 0
)
)
)
)
(
,
,...,
(
,
,...,1,1
(
,
,...,1,0
(
,
,...,0,1
(
,
,...,0,0
l
n
n
n
n
n
n
l
l
l
n
n
n
n
f x
x
x
f x
x
x x
f x
x
x x
f x
x
x x
f x
x
x x
−
−
−
−
−
−
−
−
−
−
=
+
+
+
)
+
• Rozkład sumacyjny funkcji logicznej względem
wszystkich
(n)
zmiennych wykorzystuje 2
n
iloczynów o n literałach
czyli mintermów P
k
(X )
f(X) =
n
k
k
k
P (X)f(X )
2
1
0
−
=
∑
Jest to
kanoniczna forma sumacyjna
, czyli suma
1-mintermów
– tych mintermów P
k
(X), dla których f(X
k
) = 1.
•
Każdą funkcję logiczną można przedstawić w postaci
kanonicznej formy sumacyjnej