F1-37

Minimalizacja „oparta na kostkach”

•

Funkcję boolowską n zmiennych można przedstawić w postaci
n-wymiarowej kostki (n-kostki)

• Każdy wierzchołek (0-kostka) reprezentuje jeden z możliwych

2

n

mintermów

• Dwa wierzchołki są

sąsiednimi

, jeżeli opisujące je liczby

dwójkowe różnią się na jednej pozycji.

• Wierzchołki oznacza się odpowiednimi liczbami dwójkowymi b

k

lub równoważnikami dziesiętnymi k

– zaznacza się wierzchołki,

dla których k

∈ T lub k ∈ D.

• Zbiór 2

i

wierzchołków n-kostki tworzy i-(sub)kostkę opisaną

przez (n – i) zmiennych.

•

Krawędź

łącząca dwa sąsiednie wierzchołki stanowi

1-kostkę

opisaną (n – 1) zmiennymi (1-kostka

pokrywa

dwie 0-kostki)

•

2-kostka

jest

kwadratem

, a

3-kostka

jest

sześcianem.

•

Przykład:

T = {0, 4, 6, 7} i D = {3, 5}

Dwie 0-kostki 0 i 4 ► 1-kostka

l

l

x x

1 0

| Cztery 0-kostki 4,5,6,7 ► 2-kostka

x

2

0-kostka 5

wykorzystana

, 0-kostka 3

niewykorzystana

Forma minimalna:

l

l

x x

1 0

+ x

2

© J. Kalisz, WAT, 2008