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